ECS 60 Programming Assignment #1 (50 points) Summer SSII 2016
This assignment can be done in groups of two.
Submit Filenames: timetest.cpp, LongInt.cpp, LongInt.h, writeup.pdf
Use handin to turn in just your files to cs60. Do not turn in any Weiss files, object files, makefiles, or executable files! Place all authors’ names on only the first line of timetest.cpp, and LongInt.cpp. You will find copies of my own executables, along with additional files you may need, in ~neff/60/p1 on CSIF. 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) The purpose of this question is to explore how different ADTs affect the runtime of a program. The program simply inserts and/or deletes data items from an ADT. The sequence of insert and delete operations is specified in a data file. You will find four data files (File1.dat, File2.dat, File3.dat, and File4.dat) in ~neff/60/p1 that model different types of behavior and you should use these to analyze the performance of different ADTs. The first line of each data file summarizes the operations in the file. You will submit a typed, double-spaced, 2-4 page report (writeup.pdf) that summarizes your findings on the performance of each ADT for these different sets of oeprations. Also submit the driver program described below.
Start by writing a driver program, timetest.cpp, that will ask for the name of an input file that contains a list of commands and then repeatedly ask the user for the ADT to which he/she wishes to apply those commands. The program should support the following ADTs: LinkedList, CursorList, StackAr, StackLi, QueueAr, SkipList (code from the textbook is provided for each of these). You will then run this program to analyze the ADTs.
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: {<command (char)> [values associated with command]}+
The two commands in the files for this assignment are: 1) insert: ‘i’ followed by an integer value and a space character; and 2) delete: ‘d’ followed by an integer value and a space (e.g. “i0 i1 i2 i3 ”). Since only the list ADTs can delete a specific value, you need to 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 value is specified by the delete command. Some ADT constructors require a maximum size parameter. You should hard code this to 1,000,001.
Your driver program will need all of the following files from ~neff/60/p1: CPUTimer.h, LinkedList.cpp, StackAr.cpp, dsexceptions.h, CursorList2.cpp, LinkedList.h, StackAr.h, CursorList2.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. To make CursorList compile you should add the following line below your #includes, and pass cursorSpace in the CursorList constructor:
vector<CursorNode <int> > cursorSpace;
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 ~neff/60/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, include 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 the operations of each ADT for each file; this should include five big-O values for each ADT: 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. 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 ignore 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 and collaborate on their report. 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:
[p1]$ 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
[p1]$
#2. LongInt (20 points, 1 hour) Filenames: LongInt.cpp, LongInt.h
The program LongIntMain.cpp adds unsigned integers of UNLIMITED length. It uses the class LongInt. Write the implementation code for the LongInt class. LongIntMain.cpp, and a Makefile are provided in ~neff/60/p1. You may not alter either of these files. You may assume that the user will enter only digits for the numbers, but the number of digits entered may be very large. You may not read the digits into an array, nor may you use the STL (Standard Template Library). Your two files will be copied into a directory where LongIntMain.cpp, Makefile, and the Weiss files used for timetest will be located. The script will then run make using my Makefile. Hints: I used Weiss List, Weiss StackLi, isdigit(), peek(), and a static local variable
[p1]$ cat LongIntMain.cpp
#include <iostream>