Princeton University
Computer Science Department

Computer Science 226
Algorithms and Data Structures

Rob Schapire

Spring 2005
Directory
General Information | Schedule & Readings | Assignments | Whiteboard

Schedule and readings

Numbers in brackets [] under "readings" refer to required core chapters or sections of Sedgewick, or occasional readings from other sources.  Numbers in braces {} refer to other chapters or sections or readings which may be read optionally for further enrichment, background or review.  Readings preceded by the letter "C" (as in "{C8.1}") refer to the optional Cormen, Leiserson, Rivest & Stein text.  Readings marked with an asterisk have been scanned from the second edition of Sedgewick.  Material and readings for lectures that have not yet taken place are tentative and subject to change.

#

Date

Topic

Readings
1 M 1/31 General introduction.  Union-find. [1]
{2-5}
2 W 2/2 Elementary sorting algorithms; loop invariants [6.0-6.6]
{6.7-6.10}
{C2.1}
3 M 2/7 Mergesort; begin quicksort [8]
4 W 2/9 Quicksort; lower bound for comparison-based sorting; begin priority queues [7]
{C8.1}
5 M 2/14 Priority queues and heapsort; begin symbol tables [9.0-9.5]
{9.6-9.7}
6 W 2/16 Hashing [12.0-12.4] {12.5}
[14]
7 M 2/21 Finish hashing.  Binary search trees. [12.6-12.9]
8 W 2/23 Balanced trees [13 except 13.5] {13.5}
9 M 2/28 Red-black trees; begin radix search [15 except 15.1] {15.1}
10 W 3/2 Radix search  
11 M 3/7 Radix sort; data compression [10.0-10.3; 10.6] {rest of 10}
[Sections 4.1-4.5; 4.8; 6.1-6.3; 6.5-6.6 of Coding and Information Theory (2nd ed.) by R. W. Hamming]
12 W 3/9 Finish data compression.  Begin dynamic programming. [5.3] {C15}
13 M 3/21 Finish dynamic programming.  Begin graph algorithms. [17.0-17.4] {17.5-17.6}
14 W 3/23 MIDTERM  
15 M 3/28 Graph search [17.7-17.8]
[18.0-18.2; 18.7-18.8]
{rest of 18}
16 W 3/30 Minimum spanning trees [20.0; 20.2-20.4] {rest of 20}
17 M 4/4 Directed graphs and DAG's [19.0-19.1; 19.3; 19.5-19.6; 19.8] {rest of 19}
18 W 4/6 Shortest path problems [21.0-21.2; 21.4-21.5; 21.7] {rest of 21}
19 M 4/11 Finish shortest paths; begin network flow  
20 W 4/13 Network flow [22.0-22.2; 22.4] {rest of 22}
21 M 4/18 Geometric algorithms: convex hull; finding the closest pair of points [24*, 25*] [C33.4]
22 W 4/20 Geometric algorithms: range searching; geometric intersection [26*, 27*]
23 M 4/25 Linear programming [C29.0, C29.1, C29.3, C29.4]
{old Scientific American article}
24 W 4/27 NP-completeness {C34}
  Tu 5/17
9am-12		 FINAL EXAM
McCosh 28