This version lists all topics we will cover, by chapter and date. In addition, it gives the assignments, both exercises and machine problems, through to the Midterm Exam on 2/17. The notes "(avail. online)" mean that the Sedgewick source code is available through our course web pages.

Thurs 1/8 C++, Ch. 2. Including Euclid's algorithm for the gcd.

Mon 1/12 Elementary Data Structures, Ch. 3. Lists, stacks, queues. Reading due: Chs. 1, 2, 3.

Tues 1/13 Ch. 3, continued.

Thurs 1/15 Quiz #1, GCD code, lists, and stacks

Mon 1/19 Trees, Ch. 4. Reading due: Ch. 4.

Tues 1/20 Ch. 4, continued. Read Ch. 5 pgs. 60-61. Exercises due: Ch 4. #1-8. Machine prob. due: Ch 4. #9 (this was difficult).

Thurs 1/22 Code Warrior IDE demos

Mon 1/26 Analysis of Algorithms, Ch. 6. Reading due: Ch. 6.

Tues 1/27 Analysis (cont.). Read Ch. 7.

Thurs 1/29 Elementary Sorting, Ch. 8. Selection and insertion sorts. Reading due: Ch. 8 pgs. 93-107, 112-113.

Mon 2/2 Quicksort, Ch. 9. Reading due: Ch. 9.

Tues 2/3 Priority Queues, Ch. 11. Reading due: Ch. 11.

Thur 2/5 Priority Queues (cont.). Exercises due: Ch. 8, #s 3 and 8. Ch. 9, #s 4 and 5. Machine problem due: Use the simple form of QS on pg. 118 (avail. online) to sort an array of 32 integers. Add a global counter to count the total number of times QS is entered. Compare the count for the cases: Random array, sorted array, backwards sorted array. (For randomization, you could use the last two digits from successive numbers in a phone book.)

Mon 2/9 Elementary Searching Methods, Ch. 14. Reading due: Ch. 14. Machine problem due: You are to use quicksort to sort a collection of 7 records of class info (that you create and fill by hand) that each contain a int slot num and a string slot name. Only the pointers in an array are swapped, but the comparisons use the data from the records pointed to. Modify the quicksort code of pg. 122 (avail. online) to sort records by the num keys, and separately, by their name key. Note that strcmp(s1, s2) returns <0 if s1<s2, 0 if s1==s2, and >0 if s1>s2. You'll need to write your own function using it that will return only two values. Use a templated stack (pgs. 33 and 95) or redefine the functions swap and the stack data type to handle each type. This problem involves straightforward C++ coding, nothing tricky.

Tues 2/10 Elementary Searching Methods (cont.). Exercises due: Ch 11. #1, 3, 4, 7.

Thurs 2/12 Hashing, Ch. 16. Reading due: Ch. 16.

Mon 2/16 String Searching, Ch. 19. Reading due: Ch. 19. I will give you a review for the Midterm, which will cover the following: All chapters that have been assigned, through Ch. 16 (not including today's Ch. 19). It is a closed-book, closed-notes exam. You will not be asked to write code, but you will have to read and understand code. A major task will be to draw the progress of various algorithms on paper, such as sorting and searching algorithms, and heap manipulations. For numerical problems, you should demonstrate that you know how to estimate answers, rather than relying entirely on calculators or lengthy manual calculations.

Machine problem due (previously due, 2/12): Priority queues: You are to study the operation of the heap-based routines by instrumenting the code to see how it functions. Get the code from pg. 147 (avail. online) working for integers. Be sure to use the first version, not the indirect heap form later in the chapter. Build a heap of 32 two-digit numbers between 1 and 99, inserted in random order. Then remove four elements and then insert four new ones. Instrument upheap and downheap so that they report (print) the items exchanged and their positions, producing a trace of these critical operations. Print out an explanation of what you're doing first, an announcement of what each insert or remove is going to do, blank lines between successive inserts or removes, and then the specific exchange information. Pick out some of the operations performed and do them by hand, on paper, to see if they agree with the traces and turn this work in also. Then do the same for heapsort. You may want to use I/O manipulators <iomanip.h> to make your output more readable, and write output functions rather than just messy I/O statements in the middle of your heap functions.

Tues 2/17 MIDTERM EXAM - Entire class period.

The assignments will be added to the dates below later.

Thurs 2/19 String Searching, Ch. 19

Mon 2/23 Pattern Matching, Ch. 20

Tues 2/24 Pattern Matching (cont.)

Thurs 1/26 File Compression, Ch. 22

Mon 3/2 Elementary Graph Algorithms, Ch. 29

Tues 3/3 Weighted Graphs, Ch. 31

Thurs 3/5 Weighted Graphs (cont.)

Mon 3/9 Random Numbers, Ch. 35

Tues 3/10 catch-up time

Thurs 3/12 Review for Final Exam

Back to teaching Gateway