Assigned Wednesday 1/8/03. Due via HSP at 11:10 AM, Monday, 1/13/03. Implement the ArrayStack class whose interface is in array_stack.h. Put your implementation in a file called array_stack.cpp, and submit only array_stack.cpp. You should, of course, have another file containing a main program that tests your stack, but you should not submit it. Your main program must not be in array_stack.cpp.
Start early, keep in touch, and have fun.
Assigned Monday 1/13/03, due via HSP by noon, Monday, 1/20/03. Complete the implementation of the ListString class found in list_string.cpp and list_string.h. You should not modify list_string.h. The class as it stands has a small amount of functionality already, which you can test using liststringmain.cpp.
Assigned Wednesday, 1/22/03, due via HSP by 11:10 AM, Monday, 1/27/03. Mazes.
Assigned Monday, 1/27/03, due on paper at 11:10 AM, Monday, 2/3/03. Timing.
Assigned Friday, 2/14/03, due 11:10 AM, Wednesday, 2/19/03. Write a program that takes a text file from standard input and prints (1) an alphabetized list of all the words in the file with the number of times each word occurs, and (2) the same list, sorted in decreasing order by occurrence count. Create a binary search tree class to do the counting. Ideally, you should use a template to make your BST more generally useful.
Assigned Wednesday 2/19/03, due 11:10 AM Wednesday, 2/26/03. Same problem as before (counting words), but this time with several techniques: (1) using your BST from the previous assignment, (2) using my AVL tree avl.h (see avltester.cpp for an example of how to use it), (3) using a hash table with chaining, and (4) using a hash table with quadratic probing. Pick a nice big text file, and time runs of each of the above. You should run the hash tables with three or four different sizes (e.g. too small, medium, medium large, and too large) to see how running time is affected by table size.
Next, take a big alphabetized file (I have such a file stored at /Accounts/courses/cs117/ondich/words.txt--go ahead and copy it into your account, but get rid of it when you're not using it--it's pretty big). Run your various programs on this input, and record the times.
Along with your source code, hand in a text file containing the results of your timing plus a discussion of what the timing results teach you about the relative merits of BSTs, AVL trees, and hash tables.
Assigned Friday 2/28/03, due 5:00PM Sunday, 3/16/03. The final project.
1/3/03. Read Chapter 1 of Kruse.
1/8/03. Chapter 2.
1/15/03. Sections 3.1-3.4 and Chapter 4.
1/27/03. Sections 7.1-6, 8.1-3.
1/31/03. Sections 8.6-7.
2/3/03. Sections 10.1-3.
2/17/03. Section 10.4.
2/19/03. Sections 8.9, 9.1-9.4, 9.6-9.8.
2/26/03. Chapter 12.