CS 2213 Advanced Programming, Fall 2000 Programming Assignment 1

Due In Class, Thursday, October 26, 2000

In this assignment you will modify your heapsort from the last assignment so that it can sort an array of strings.

The first step is to get your heapsort from Programming Assignment 0 working correctly.

Part 0: Fixing your heapsort from Programming Assignment 0.
You must do this part even if your hepasort is already working.
Create a directory called assign1 for this assignment.
Create a subdirectory of this called part0. Copy all of your files from your Part 1 of Programming Assignment 0 into this directory. Get a new copy of heaptester.o from /usr/local/courses/cs2213/fall2000/prog1. This will replace the one from Programming Assignment 0. This does a better test on the creation of the heap to make sure you do this according to the algorithm discussed in class.

Do not go on to Part 3 until you have this working correctly, but you may do parts 1 and 2. It should take less than one second to sort an array of size 100,000 using the machines in the lab. Make sure the tester indicates that both the heap and the sort were correct.

Part 1: Creating an array of strings

Put all of the files for this in a directory called part1 which is a subdirectory of assign1.

In this part you will use the getLine from Part 1 of Lab Assignment 3 to create an array of strings.
If you don't have this working yet, you can temporarily use the getLine from Part 0 using a large values of INIT_ALLOC.

Write a main program called gettest.c which will use getLine to read lines from standard input until an error or an end of file occurs. Recall that getLine indicates an end of file by returning a string of length zero. After all of the lines have been read in, output the lines. The lines will be put in an array. Since you do not know how large this array will be, you can assume a maximum size of 100,000. That is, read at most 100,000 lines or until an end of file occurs.

You can declare the array as follows: 

#define MAXSIZE 100000
char *mystrings[MAXSIZE];
Test the program to make sure it is working.

Part 2: Making a filter

Make a directory called part2 which is a subdirectory of assign1. Copy you programs for part1 and modify them to make gettest into a filter by having it output the lines after all of the lines have been read in. The only output produced by your program should be the output of the lines read in. It should not output your name.

Copy the file /usr/local/courses/cs2213/fall2000/prog1/test.in into the part2 directory. Now execute
gettest < test.in > test.out

This uses your test file as input and creates an output file. If your program is working correctly these two files should be identical. Test this with:
diff test.in test.out

If they are identical diff will not produce any output.

Copy gettest.c into slowsort.c. Now convert slowsort into a (slow) sorting filter by calling the program
bubblesortstringpointerpointer
from the notes between the input and the output.

Run your program as before:
slowsort < test.in > test.out

Look at test.out to see that it is sorted.

You can test to see if the sort was done correctly by using the system sort function:
sort test.in > test.sort

Now run diff:
diff test.out test.sort

Part 3: A faster sort

Copy all of the files from your part0 and part2 directories into a part3 directory. Rewrite you heapsort from assignment 0 so that it sorts an array of strings like in bubblesortstringpointerpointer. Change the names of the functions so that your heapsort functions look like: 

   void makeHeapStrings(char *vals[], int size);
   void sortHeapStrings(char *vals[], int size);

Rename slowsort.c to fastsort.c and have it call your heapsort by calling makeHeapStrings followed by sortHeapStrings.

You can rename the file with
mv slowsort.c fastsort.c

Modify the makefile so that it works with these new files. Be sure to use lint. You should lint all of the appropriate files together. Test it as before.

You can see how much faster the heapsort is by testing it on the file /usr/local/courses/cs2213/fall2000/prog1/test.in. It should take less than 1 second to sort this using the heapsort once it is read in. The bubble sort will take several minutes.

Part 4: The final test

Make a part4 subdirectory of assign1 and copy all of the files from part3 into this directory. Rename fastsort.c to fastsorttest.c and change the makefile accordingly. Make sure everything still works.

Get a copy of the file /usr/local/courses/cs2213/fall2000/prog1/heapstringtester.o and modify your makefile so that it compiles this with your fastsorttest.c. This file contains a function makeAndTestPointer() which will test your new heapsort. Modify fastsorttest.c so that all it does is call this function once. Save the output generated.

Part 5: Handing in the programs

Print out the cover page using
lp /usr/local/courses/cs2213/fall2000/cover1.ps

The cover sheet tells you what needs to be handed in. You will consecutively number the pages of your printout and put the page numbers of the various parts on the cover sheet. Be sure to fill in the cover sheet completely.

Staple everything together and hand it in at the beginning of class on the due date.