Assignment 8, due Tuesday April 18 at noon.
You must submit your program electronically via gsubmit
on csa.
Under no circumstances will late assignments be accepted.
The code you submit must conform with the programming
guidelines.
Program Description
In this assignment you will implement and use a heap. You will use a heap
to store 3-letter airport codes, and then your program will print out the
airport codes in decreasing alphabetical order.
Write and submit three files:
-
heap.cpp -- implementation of your heap ADT
-
heap.h -- member functions associated with your heap ADT
-
main.cpp -- the main program
Airport Code Index
Write a top-level program that constructs a heap containing 3-letter airport
codes. Your program should first read an input file, building a heap of
the codes by inserting them into the heap one at a time. Your program should
then print out a listing of airport codes in decreasing alphabetical
order. As your program prints each airport code, it should be deleted
from the heap.
This program program takes one command-line argument: the input file
name. Here is an example
input file. You can assume that files conform to the 3-letter, uppercase
airport code convention. Here is the resulting output
for the example file. Your output file should match this format
exactly. To see if your output matches, you can use the Unix command diff.
Note: it is possible that the same airport occurs multiple times
in an input file. Your program must ensure that each possible airport code
appears only once in the heap.
Note: templates must be used in implementing the heap class.
Extra Credit
Prepare an O-notation analysis of the above program. Given that there are
N airport codes in the input, derive the worst case time complexity of:
-
inserting an item in the heap
-
deleting an item from the heap
-
searching for an item in the heap
-
constructing a heap containing all N items
Submit this analysis in written form at beginning of lecture on the assignment
due date.
Grading Criteria
Refer to the grading criteria file: p8.criteria
Academic Honesty and Collaboration
Cooperation is recommended in understanding various concepts and system
features. But the actual
solution of the assignments, the programming and debugging must be
your individual work, except for
what you specifically credit to other sources. (Your grade will be
based on your own contribution.) For
example, copying without attribution any part of someone else's program
is plagiarism, even if you
modify it and even if the source is a textbook. The University takes
acts of cheating and plagiarism
very seriously: first time violators are routinely suspended for a
semester.