This project contains both written and electronic (programming) parts. The electronic parts (code) must be submitted according to the instructions on this page. The written parts must be typed or neatly written, and handed in to the instructor.
Both parts of this project are due before the beginning of class on Friday, February 10. Late submissions will not be accepted, in accordance with the class policy. Students with excused absences on that date may email the written portion by the deadline in addition to handing in a paper copy at the earliest opportunity.
The year is 1984 and the world is ruled by just a few super-states. One of them, Oceania, is dominant and controls both North and South America, sourthern Africa, and Australia. It is engaged in a perpetual, unwinnable war with the other super-powers for the purpose of subjugating its own citizens.
To support the perpetual war, the Oceania Military Academy (OMA) churns out an amazingly high number of graduates every year (in the millions), and the process of selecting which part of the military service they will each enter is a daunting task. This being Oceania, the students themselves (called Proles) have no say in their own service selection. Instead, they are all ranked by each of the different communities, who then take turns in picking which Proles they will get.
Your task is to design an algorithm and write a computer program that reads in the names of the \(k\) different communities, as well as the \(n\) Proles and their rankings in each community, and prints the results of the service selection. This works similarly to a draft: the \(k\) communities, in the order they were read in, take turns picking, one at a time, until there are no more Proles left. For each pick at each iteration, the community chooses the highest-ranking Prole (according to its own ranking) that has not been picked yet.
Specifically, the input, which should be read from standard in, contains in order
For example, consider the following sample input file:
3 Tanks Infantry Paratrooper 5 Bill 4 5 1 Suzy 1 1 4 John 2 4 5 Kate 3 2 3 Mike 5 3 2
The Tanks community will choose Suzy first. Then the Infantry would like to choose Suzy but can't, so they pick Kate instead. Next the Paratroopers pick Bill, and so on. The correct output would be
Suzy Tanks Kate Infantry Bill Paratrooper John Tanks Mike Infantry
The following C++ programs are available to help you. You can download them all at once (in a gzipped tarball) from this link. Download the file, then type
tar xzvf proj2.tar.gz from the linux command line to extract the files into a folder called
random-names.txt. A huge file with random alien names is provided in the tarball linked above.
Here is a pseudocode description of the algorithm that appears in the selection.cpp file.
Simple OMA service selection algorithm
n, and n k-tuples of rankings. Each ranking, for each community is an integer between 1 and n.
Output: The list of service selections
Read the rankings into an array
for i from 0 to n-1 do
r := 1
c := i mod k
Find Prole p with rank r by community c using linear search
while p is marked
print the names of Prole p and community c
The first two tasks are written, and the last is electronic. See the instructions at the top of this assignment for how to submit each part.
Analyze my "simple service selection algorithm" described above and provided in code. Use both sources (pseudocode and actual code) to help you understand the algortihm. I want (at least) a big-O analysis of the worst-case cost, in terms of k and n. Try to make your analysis as tight as possible.
Describe an improved algorithm for the same problem in pseudocode, and give a worst-case big-O analysis, in terms of k and n. Try to give a tight analysis, and try to design your algorithm to be as efficient as possible. If necessary, you may assume that k is much smaller than n. So for example, \(O(kn)\) time is much better than \(O(n^2)\) time.
Implement your improved algorithm, along with any other tweaks you can think of, so that your code is as fast as possible. I recommend that you follow my example and code in C++, but you may use any programming language that you wish, as long as it runs in the linux environment in the labs. In any case, your improved program should be in a single file called
sel.EXT, where EXT is
cpp or another extension depending on your language. If you don't use C++, you must also submit a
README.txt file with instructions on how to compile and run your program.
Bonus: The fastest (correct) program on a large sample input of my choosing will receive a 10% bonus on the grade for this project.