ECS 36C Programming Assignment #1 (50 points) Winter 2020
Due: Friday, January 17th, Write-ups: 4:00pm; Programs: 11:59pm. Filenames: timetest.cpp, bags.cpp, balance.cpp, authors.csv
authors.csv should be in the format (with no space characters!):
First line:
For example:
hpotter@ucdavis.edu,Potter,Harry fflintstone@ucdavis.edu,Flintstone,Fred
Use handin to turn in just your files to p1 in cs36c. Do not turn in any Weiss files, object files, makefiles, or executable files! You will find copies of my own executables in ~ssdavis/36c/p1. All programs will be compiled and tested on Linux PCs. All programs must match the output of mine, except that the CPU times may be different. Do not get inventive in your format! Programs are graded with shell scripts. If your program asks different questions, or has a different wording for its output, then it may receive a zero!
#1. Timetest: (30 points with 25 points for write-up and 5 points for timetest.cpp, 15 minutes)
Write a driver program, timetest.cpp, that will ask for a filename and repeatedly asks the user for the ADT to
which he/she wishes to apply the commands from the specified file. You will then run your program and note the performance of ADT in a two or three page typed, double-spaced write-up. Hand written reports will receive no points! We will be storing only integers for this assignment. The format of each file will be:
First Line: A string describing the contents of the file.
Second Line: {
The two commands in the files are: 1) insert: ‘i’ followed by an integer and a space character; and 2) delete ‘d’ followed by an integer and a space. Since only the list ADTs can delete a specific value, you need delete the specific value for only those three implementations. For stack, simply pop the next integer, and queue simply dequeue the next integer, no matter what the value is specified by the delete command. Some ADT constructors require a maximum size parameter. You should hard code this to 500,001.
Your driver program will need all of the following files from ~ssdavis/36c/p1: CPUTimer.h, LinkedList.cpp, StackAr.cpp, dsexceptions.h, CursorList.cpp, LinkedList.h, StackAr.h, CursorList.h, QueueAr.cpp, StackLi.cpp, vector.cpp, QueueAr.h, StackLi.h, vector.h, SkipList.h, SkipList.cpp, File1.dat, File2.dat, File3.dat, and File4.dat. You may copy the .h and .cpp files, but you should simply link to the .dat files using the UNIX ln command.: ln –s ~ssdavis/36c/p1/*.dat . (Note the period to indicate your current directory.)
To make CursorList compile you should add the following line below your #includes, and pass cursorSpace in the CursorList constructor:
vector
After you’ve completed your program, apply File1.dat, File2.dat, File3.dat, and File4.dat three times to each ADT and record the values returned. You will find the shell script run3.sh in ~ssdavis/36c/p1 that will do that for you, assuming the name of your executable is a.out. Just type “run3.sh”, and then look at the file “results” to see the times for all eighteen runs.
In your write-up, have a table that contains the values for each run, and the average for each ADT for each file. Another table should contain the time complexity for each ADT for each file; this should include five big-O values: 1) individual insertion; 2) individual deletion; 3) entire series of insertions (usually N times that of an individual insertion); 4) entire series of deletions (usually N times that of an individual deletion); and 5) entire file. These two tables are not counted as part of the required two or three pages need to complete the assignment. For each ADT, you should explain how the structure of each file determined the big-0. Concentrate on why ADTs took longer or shorter with different files. Do not waste space reiterating what is already in the tables. For example, you could say “Stacks perform the same on the
three files containing deletions because they could ignored the actual value specified to be deleted.” The last section of the paper should compare the ADTs with each other. Most of the differences can be directly explained by their complexity differences. The lion’s share of the last section should explain why some ADTs with the same complexities have different times. In particular, why is the CursorList slower than the normal list? You should step through Weiss’ code with gdb for the answer.
The members of a team may run the program together, but each student must write their own report. Turn in this write-up to the appropriate slot in 2131 Kemper. If you declare ct as a CPUTimer then the essential loop will be:
do {
choice = getChoice();
ct.reset();
switch (choice)
{
case 1: RunList(filename); break;
case 2: RunCursorList(filename); break;
case 3: RunStackAr(filename); break;
case 4: RunStackLi(filename); break;
case 5: RunQueueAr(filename); break;
case 6: RunSkipList(filename); break;
}
cout << "CPU time: " << ct.cur_CPUTime() << endl;
} while(choice > 0);
A sample run of the program follows:
% timetest.out
Filename >> File2.dat
ADT Menu
0. Quit
1. LinkedList
2. CursorList
3. StackAr
4. StackLi
5. QueueAr
6. SkipList
Your choice >> 1
CPU time: 15.66
ADT Menu
0. Quit
1. LinkedList
2. CursorList
3. StackAr
4. StackLi
5. QueueAr
6. SkipList
Your choice >> 0
CPU time: 0
%
#2 (10 points, 15 minutes) Name your file bags.cpp You are to write a program that simulates the actions of luggage handling for a large aircraft. Luggage is loaded into containers as the luggage arrives. When a container is full, or there is no more luggage, it is loaded into the aircraft. At the destination, the containers are unloaded with the last on being the first off. As each container is unloaded its bags are unloaded in the same order as they were loaded, i.e., last on being the
last off. You are to write a program that takes a command line parameter of filename followed by an integer. The file contains a list of bags (shorts) in the order they arrive. The integer on the command line will indicate the number of bags each container will hold. Your program should output to the screen the order of the bags as they are unloaded. Three sample data files, bags25.txt, bags37.txt, and bags100.txt, as well as my executable, bags.out, are in ~ssdavis/36c/p1.
Further specifications: The only variables you can use are Weiss stack(s), pointer(s) to stack(s), Weiss queue(s), pointer(s) to queue(s), one ifstream, argv from the command line, and one short which can only hold the bag number read from the file.
[ssdavis@lect1 p1]$ cat bags25.txt
16 24 25 3 20 18 7 17 4 15 13 22 2 12 10 5 8 1 11 21 19 6 23 9 14
[ssdavis@lect1 p1]$ bags.out bags25.txt 7
6 23 9 14 10 5 8 1 11 21 19 17 4 15 13 22 2 12 16 24 25 3 20 18 7 [ssdavis@lect1 p1]$ bags.out bags25.txt 10
19 6 23 9 14 13 22 2 12 10 5 8 1 11 21 16 24 25 3 20 18 7 17 4 15 [ssdavis@lect1 p1]$
#3. Exercise 3.21b. (10 points, 25 minutes) Filename: balance.cpp
You may not use the STL, and should use the appropriate Weiss data structure(s). Weiss does have a string
class in string.cpp and mystring.h. You may not maintain a count of the tokens, and must use stack(s). You may assume that all of the Weiss files used for timetest.cpp will be available, when the shell script executes “g++ balance.cpp”. Your program should take the name of the C++ file as a its only command line parameter, and report “OK” if all four types of pairings are balanced throughout, otherwise it should report the line number and symbol of the first unpaired element. Line numbers start at 1. Text within “/*” “*/” comments should be ignored. In C++, it is an error if an unpaired token came between any pair of tokens, e.g., “{ ( }”, or “( ] )”. You will find the four test files as well my balance.out in ~ssdavis/36c/p1.
[ssdavis@lect1 p1]$ cat balance1.txt
1
/* Unterminated comment
end.
[ssdavis@lect1 p1]$ balance.out balance1.txt Unmatched /* on line #2
[ssdavis@lect1 p1]$ cat balance2.txt
*/
whoops
[ssdavis@lect1 p1]$ balance.out balance2.txt Unmatched */ on line #1
[ssdavis@lect1 p1]$ cat balance3.txt
1
{} [ whoops
[ssdavis@lect1 p1]$ balance.out balance3.txt Unmatched [ on line #3
[ssdavis@lect1 p1]$ cat balance4.txt
[ (({ /* ( */} )) ]
[)]
[ssdavis@lect1 p1]$ balance.out balance4.txt Unmatched ) on line #2
[ssdavis@lect1 p1]$
[ssdavis@lect1 p1]$ balance.out StackAr.cpp OK
[ssdavis@lect1 p1]$