This website is preserved for historical and scholarly reference and is no longer actively maintained.
Tentative Class Schedule
CP SC 241
-- 9:45 a.m. MTWThF -- G 33 Jordan
Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss
Optional text: C++ Primer, Third Edition by Stanley B. Lippman and Josee Lajoie
Wednesday, June 30 -- Mechanics of class organization
Chapter 1 (Introduction): Basic concepts and mathematics (pages 1 - 7 )
Review of recursion (pages 7 - 11)
Thursday, July 1 --
Chapter 1 (Introduction): C++ classes (pages 11 - 19)
Lab 1: Introduction to Unix
Friday, July 2 --
Finish Chapter 1 (pages 19 - 37)
Monday, July 5 -- Classes do not meet (no lab)
Tuesday, July 6 --
Chapter 2, pages 41 - 61 (Algorithm Analysis)
Wednesday, July 7 --
Chapter 3, pages 69 - 81, Linked Lists
(skip polynomial ADT, multilists. return to Radix sort later)
Thursday, July 8 --
Chapter 3, pages 93 - 100, Stacks and Applications
Friday, July 9 --
Chapter 3, pages 110 - 116, Queues and Applications
Saturday, July 10 --
Chapter 4, pages 121 - 164, Binary Trees, Analysis, Traversals.
Monday, July 12 --
Chapter 5, pages 181 - 188, Hashing using separate chaining
Lab 4: Self-adjusting lists
Tuesday, July 13 --
Chapter 5, pages 188 - 200, Hashing using open addressing
Wednesday, July 14 -- Hour Quiz I covers through hashing using separate chaining
Thursday, July 15 --
Chapter 6, pages 211 - 223, Priority Queues and applications
Friday, July 16 --
Chapter 8, pages 303 - 311, Disjoint Set ADT
Monday, July 19 --
Chapter 8, pages 312 - 314, Path compression in Disjoint Set ADT
Chapter 9, pages 327 - 330, graphs and graph representation
Lab 7: Exercise 6.12, page 247. Timing building of heaps.
Tuesday, July 20 --
Chapter 9, pages 360 - 362, Kruskal's Algorithm.
Chaoter 7, pages 260 - 264, Heapsort.
Lab 8: Timing Heapsort. Refer to pages 260 - 264 of text.
Wednesday, July 21 -- last day to drop
Chapter 9, pages 330 - 339, topological sort and shortest path algorithms
Thursday, July 22 --
Chapter 9, pages 333 - 346, shortest path algorithms.
Lab 9: Building a graph class.
Friday, July 23 --
Chapter 9, pages 356 - 360, Dijkstra's Algorithm.
Monday, July 26 --
Chapter 9, pages 362 - 371, Depth-first search and Hamiltonian Cycles.
Computation of estimated running time of programs based on growth rate.
Lab 10: Determine growth rate of mystery program.
Tuesday, July 27 --
Chapter 9, pages 368 - 371, Euler Circuits;
pages 374 - 379, Introduction to NP-Completeness.
An algorithm for finding Hamiltonian cycles.
Lab 11: Hour Quiz II covers through Dijkstra's Algorithm.
Wednesday, July 28 --
Chapter 9, pages 356 - 360, Prim's Algorithm.
Wednesday, August 4: Final Exam
Some topics will be covered that are not in the text. Please get the notes and assignments from other students (or the web, when appropriate) so that you will be prepared for class at all times. Being absent is not an excuse for being unprepared for material covered in the previous class. Nor is being absent an excuse for being unprepared to turn in assignments.