Programming Assignment #1 Solution

Filenames: timetest.cpp, LongInt.cpp, LongInt.h , authors.csv




authors.csv should be in the format:

First line: <e-mail of first partner <comma <family name of first partner <comma <given name of first partner




Second line (if needed): <e-mail of second partner <comma <family name of second partner <comma <given name of second partner




For example:

hpotter@ucdavis.edu,Potter,Harry




fflintstone@ucdavis.edu,Flintstone,Fred







Use handin to turn in just your files to cs60. Do not turn in any Weiss files, object files, makefiles, or executable files! You will find copies of my own executables in ~ssdavis/60/p1. All programs will be compiled and tested on CSIF 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: {<command (char) [values associated with command]}+




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 2,500,000.




Your driver program will need all of the following files from ~ssdavis/60/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 all those files.




To make CursorList compile you should add the following line below your #includes, and pass cursorSpace in the CursorList constructor:




vector<CursorNode <int cursorSpace(2500001);




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/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, 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);




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

Quit
LinkedList
CursorList
StackAr
StackLi
QueueAr



SkipList Your choice 1 CPU time: 15.66



ADT Menu

Quit
LinkedList
CursorList
StackAr
StackLi
QueueAr



SkipList Your choice 0 CPU time: 0
%




#2 (20 points, 1 hour) Filenames: LongInt.cpp, LongInt.h




I have written a program, LongIntMain.cpp, to add 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 ~ssdavis/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. 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 we will run make using my Makefile. Hints: I used Weiss List, Weiss StackLi, isdigit(), peek(), and a static local variable.




[ssdavis@lect1 p1]$ cat LongIntMain.cpp

#include <iostream

#include "LongInt.h"

using namespace std;




int main()

{

LongInt int1, int2, int3;




cout << "Please enter first long integer "; cin int1;




cout << "Please enter second long integer "; cin int2;

int3 = int1 + int2;




cout << int3 << endl;

return 0;

}




[ssdavis@lect1 p1]$ LongInt.out




Please enter first long integer 172340958712349871234931287 Please enter second long integer 432598741390874309587243098572340985723098571908731924 432598741390874309587243098744681944435448443143663211 [davis@lect1 p1]$