CMSC-341 Spring 2003
Project 4
Assigned |
Wednesday 4/9/03 |
Due |
Tuesday 4/22/03 11:59pm
|
Updates |
10 April 2003, 9:00am
Someone noticed that the author's BinaryHeap.C file was not
guarded. It has been editted to add a guard.
10 April 2003
The author's BinaryHeap.C file was not guarded. This has been fixed.
Adding new public methods to the author's code should not be necessary and is not permitted
|
In class we discussed the implementation of Priority Queues
using a min binary heap. Max binary heaps are similar, providing a partial
ordering from the max value at the root to smaller values. In
this project, you will implement a median binary heap using both a min
and max heap.
The median value of a set of values is the one in the "middle".
If we have an even number of values listed a sorted array, we define
the middle to be at index N/2 - 1. For example, the median of
the six values {1, 2, 3, 4, 5, 6} is 3, located at index 6/2 - 1 = 2.
Note that if the array were split in half, 3 is the maximum of the
"smaller half" of the values.
If we have an odd number of values, we
define the median to be at index floor(N/2). For example,
the median of the seven values {11, 12, 13, 14, 15, 16, 17} is 14, located at index
floor(7/2) = 3. Note that integer division provides the same result.
Note also that if the array were split appoximately in half,
14 is either the minumum of the "larger half" of the values or
the maximum of the "smaller half" of the values, depending on which "half" you
choose to place it.
Description
One interesting set of statistics about a given area (county, state, city, country)
is information about the salaries and occupations of the people who live there. In this project,
we will read salary and occupation information from a file and report salary
and occupation information as the population grows. This is such a popular area
that no one ever leaves.
The format of the information read from the file will is
described below
Classes
To implement this project you will create the following classes
- A class to encapsulate the salary and occupation information read from the file.
The design and implementation of this class is left to you.
- A class to store the salary and occupation class and provide pertinent data for
reporting. Since this class must be able to determine the median salary,
it should use a median heap.
This class must support the following public operations as well as appropriate
constructors, destructors, etc.
- a O( 1 ) method to return the current population
- a O( 1 ) method to return information about the median salary
- a O( 1 ) method to return information about the biggest salary
- a O( 1 ) method to return information about the smallest salary
- a O( 1 ) method to return the average salary
- A median heap class template for use by the class above.
Hint: a median heap uses both a min heap and a max heap.
The median heap should support the usual heap operations
-- insert, findMedian, isFull, isEmpty, deleteMedian, makeEmpty,
as well as any necessary constructors, destructors, etc.
A summary of things to do
- Copy the author's min binary heap code (BinaryHeap.H/C) from Mr. Frey's
public directory /afs/umbc.edu/users/d/e/dennis/pub/CMSC341 to your directory.
- If necessary modify the author's code to allow duplicate values
- Duplicate the author's min binary heap code and modify it to
create a max binary heap class template.
- Use the min and max heaps to implement the median binary heap class template
- Create a class to encapsulate the salary/occupation information read from the file
- Create a class to store the encapsulated salary/occupation information and
provide the required data for printing
- Write main() in Proj4.C to read the file, store the data and periodically
report the data.
- Copy and answer the questions (341-Spring03-p4_questions.txt)
from Mr. Frey's public directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj4
- Submit your project
- Use submitmake and submitrun to verify your submittal
Project 4 will be invoked with two (2) command line arguments in this
order
- The name of the file of salary and occupation information to read
- An integer, N, that tells how often to report the required information;
i.e. after every Nth person has moved into the area.
The Input File
The input file will contain salary/occupation pairs representing a new person
moving into the area. There may of course be many people with the same
occupation, who may have the same or different salaries.
Each non-blank line will contain an integer salary followed by one or
more blanks, followed by an occupation which may contain embedded blanks.
You may assume that any non-blank line is well formatted. For example the file
might look like this
100000 Doctor
125000 Family Dentist
150000 Plumber
22000 Lecturer
110000 Doctor
150000 Attorney
Sample Output
After every N persons have moved in (see The Command Line above),
your program will display the following information with appropriate labels.
- The current population
- The smallest salary and associated occupation
- The median salary and associated occupation
- The largest salary and associated occupation
- The average salary
In case there are multiple smallest or largest salaries, any "smallest"
salary/occupation or "largest" salary/occupation may be reported.
Similarly, if there are multiple occupations
with the same median salary, any of them may be reported.
Although your output need not match this sample exactly,
your output must be formatted in columns in a similar manner.
linux3[43]% Proj4 p4data.dat 10
Population : 10
Smallest Salary : 10000, Tailor
Largest Salary : 120000, Doctor
Median Salary : 50000, High School Teacher
Average Salary : 44000
Population : 20
Smallest Salary : 10000, Tailor
Largest Salary : 130000, Baby Sitter
Median Salary : 60000, High School Principal
Average Salary : 47500
linux3[44]%
Project Submission
Because you are submitting your own makefile, you are free to name your
files whatever you like, with the following restrictions:
- All class definitions appear in .H files. Header files may NOT contain
any code.
- All class implementations appear in .C files.
- The name of your executable MUST BE Proj4 (upper-case 'P'). The
submitrun program and the scripts that we use to grade your files assume
that you follow this convention for naming your executable.
What to submit
- The author's BinaryHeap.H and .C files even if not modified.
- All .H and .C files you modified or created
- Your makefile
- Your copy of the questions with your answers
Submit Tools
There are a number of tools available to you to check on
your submittal. It is your responsibility to ensure that the submittal is
correct and will result in a successful compilation of your project. Do not
wait till the last minute to submit your files. Give yourself enough time
to check that your submittal is correct.
If you don't submit a project correctly, you will not get credit for
it. Why throw away all that hard work you did to write the project? Check
your submittals. Make sure they work. Do this before the due date.
Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/.
One of the tools provided by the submit program is submitls. It
lists the names of the files you have submitted.
Additionally, there are two programs which are not part of the
UCS submit program. They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are
named submitmake and submitrun. You can use
these programs to make or run your submitted projects.
To access these programs, do one of the following
- Create an alias in your .cshrc file (the preferred method)
alias submitmake /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/submitmake
alias submitrun /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/submitrun
- Type the full path name everytime you run them
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/submitmake cs341 Proj4
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/submitrun cs341 Proj4 inputfile
- Copy them to your directory
You will have to give yourself permission to execute these programs
after you have copied them. This is accomplished using the chmod command
The syntax is similar to that for submit:
submitmake <class> <project>
Example: submitmake cs341 Proj4
This makes the project, and shows you the report from the make utility.
It cleans up the directory after making the project (removes .o files), but
leaves the executable in place.
submitrun <class> <project> [command-line args]
Example: submitrun cs341 Proj4 test.dat 10
This runs the project, assuming there is an executable (i.e. submitmake
was run successfully) and that test.dat is in your local (not submittal)
directory.
Your project will be tested using a variety of command lines, some of which
will be invalid.
Your project will also be tested using a variety of command files which
will test various conditions which your code should handle.
Project grading is described in the
Project Policy handout.
Your answers to
341-Spring03-p4_questions.txt
are worth 10% of your project grade.
Cheating in any form will not be tolerated. Please re-read the
Project
Policy handout for further details on honesty in doing projects for
this course.
Remember, the due date is firm. Submittals made after 11:59pm of the
due date will not be accepted. Do not submit any files after that time.