Fall Term, 1998
Course Materials Index |
Course Description & Regulations |
Instructor Contact Information |
The approximate dates on which the various topics of the course will be presented, along with an indication of which pages or sections of the textbook(s) are to be read in connection with each topic, are given in the following table. Students should read the indicated sections prior to each class or lab session (but should be sure to attend the session even if they haven't read the relevant material).
Lab and programming assignments are due at the start of the lab session
on the dates indicated below.
| DATES | TOPIC | READING |
|---|---|---|
| Sept. 9 | Algorithms, Data Structures, and Abstract Data Types Reference Parameters, Templates, and Function Parameters |
1.1 |
| 11 | NO LAB SESSION | |
| 14 | Algorithm Efficiency and the Sorting Problem | 1.2 |
| 16 | The Search Problem | 1.3 |
| 18 | LAB 1: Divide-and-Conquer Search Algorithms | |
| 21 | Empirical Efficiency Analysis -- Shellsort | 1.4 |
| 23 | Pointers, Dynamic Data, and Reference Types | Dale 967-990, 1030-1033 |
| 25 | LAB 2: Shellsort and Related Algorithms | |
| 28 | Abstract Data Types (ADT's) and C++ Classes | 2.1; Dale 990-1001, 1018-1030 |
| 30 | Operator Overloading Extending ADT's by Inheritance |
2.2; review Dale 909-920 |
| Oct. 2 | LAB ASSIGNMENT 1 DUE PROGRAM 1: A Randomizing Array |
|
| 5 | The List ADT Polymorphism and Virtual Functions The Array Implementation |
3.1, 3.2 (first part); Dale 1046-1050; review Dale 925-930 |
| 7 | The Linked List | 3.2, 3.3; Dale 1050-1082, 1111 |
| 9 | LAB ASSIGNMENT 2 DUE LAB 3: Using a List ADT Implementation -- The Josephus Problem |
|
| 12 | THANKSGIVING HOLIDAY | |
| 14 | Hash Tables and the Keyed Collection ADT | 11.2 |
| 16 | LAB ASSIGNMENT 3 DUE PROGRAM 2: Implementing a Linked List |
|
| 19 - 22 |
NO CLASS SESSIONS -- instructor at a programming languages conference |
|
| 23 | PROGRAMMING ASSIGNMENT 1 DUE LAB 4: Hashing Functions |
|
| 26 | The Queue ADT Circular Arrays Radix Sort |
4.1 - 4.3 |
| 28 | The Stack ADT Parsing and Evaluating Arithmetic Expressions |
5.1 - 5.3 |
| Oct. 29 - Nov. 1 | FALL BREAK | |
| Nov. 2 | MID-TERM EXAM | |
| 4 | Recursion Quicksort |
6.1 - 6.2; Dale Ch. 19 |
| 6 | LAB ASSIGNMENT 4 DUE PROGRAM 3: Quicksort |
|
| 9 | Mergesort | 6.3 |
| 11 | REMEMBRANCE DAY HOLIDAY | |
| 13 | PROGRAMMING ASSIGNMENT 2 DUE LAB 5: Parsing with Priority Functions |
|
| 16 | The Binary Tree ADT -- Implementations and Traversals | 7.1 - 7.2 |
| 18 | Binary Search Trees Height-Balanced Trees |
7.3, 7.6 |
| 20 | LAB ASSIGNMENT 5 DUE PROGRAM 4: Level-Order Traversal of a Binary Tree |
|
| 23 | Heaps, Priority Queues, and Heapsort Internal Sorting: The Theoretical Bound on Efficiency |
7.4, 12.1 |
| 25 | The General Tree ADT The Union-Find Problem |
8.1, 8.2, 8.4 |
| 27 | PROGRAMMING ASSIGNMENT 3 DUE LAB 6: Binary Search Trees |
|
| 30 | Graphs and Networks: Terminology, ADT's, and Implementations | 9.1 - 9.3 |
| Dec. 2 | Shortest Path Algorithms Transitive Closure |
9.4 |
| 4 | LAB ASSIGNMENT 6 DUE Preparing for the final exam |
|
| 7 | Minimum Spanning Trees | 9.5 |
| 9 | Topological Ordering | 9.6 |
| 11 | PROGRAMMING ASSIGNMENT 4 DUE Preparing for the final exam |
|
| Tuesday, Dec. 22 | FINAL EXAM (9:00 a.m. - 12:00 noon, Gymnasium) | |
|
Course Materials Index |
Top of this Document |
Instructor Contact Information |