Anne Dawson: CSCI201A_LAB6_FA04.htm

Last updated: Saturday 9th October 2004, 14:42 PT

This document is subject to change without notice.

Please report any errors or omissions in this document:

adawson@coquitlamcollege.com

Special instructions: For this assignment you may work in teams of 2, or alone.

This lab is due at the end of the lab session.

CSCI201A

Data and Program Organization (Data Structures)

Fall 2004

Lab Assignment 6

Implementing a Priority Queue with a singly linked list of nodes.

Step 1

Study the following:

Note: you do not type in the code of your program until Step 4.

Using a linked list of node structures (or objects) write a program to generate a priority queue of nodes, where each node contains an integer value (which is non-unique). You should implement an insert(int) method for node insertions, and a deleteMin() method to remove the node of highest priority.

Step 2

Write the algorithms (use comments in the source code) for the insert() and deleteMin() functions (methods).

Step 3

Development the pseudocode for your functions (methods) from your algorithms. Write the pseudocode of your functions (methods) using comments in the source code.

Step 4

Using your pseudocode as a guide, implement your program in the C++ or Java language.

Your program should start with a comment block that contains the following information:

# File: lab6.cpp or lab6.java

# Purpose: Implementation of a Priority Queue using a Linked List.

# Programmer: [your name]

# Partner: [your partner's name]

# Course: CSCI201A

# Date: Thursday 14th October 2004

# Test data:

Step 5

Test your functions (methods) by writing a driver program and supplying your own test data.

You should test your program with at least 3 sets of test data. Show your test data and results in comments at the top of your program.

Step 6

At the end of the class, save your program file (lab6.cpp or lab6.java) to your folder on the network in:

CSCI201A\Week06\Lab06

Program points will be based on the following marking scheme:

Marking Scheme:

CSCI201A - Lab 6 - Implementing a Priority Queue with a singly linked list of nodes.

Student name(s):

Category	Points	Description
Algorithm	5	An informal description of the steps that must be taken to solve the problem. ref: http://www.coquitlamcollege.com/adawson/Pseudocode.htm
Pseudocode	10	A formal description of the steps that must be taken to solve the problem. http://www.coquitlamcollege.com/adawson/Pseudocode.htm
Comments	10	The program is commented appropriately, including algorithm, pseudocode and test data.
Style	15	The source code should be indented properly, use meaningful variable names and identifiers, use good programming practices, etc. See the book, website and lecture notes for examples.
Output	10	Screen prompts and results should be user-friendly.
deleteMin()	10	Implemented as per algorithm.
insert(X)	20	Implemented as per algorithm.
Completeness	10	The program should be complete.
Test	10	Comments in the code explain how the code was tested.

Assignment Presentations : In the next class, a random selection of lab assignment programs will be presented to the CSCI201A group.