CSE as AND gate University of Washington Department of Computer Science & Engineering
 CSEP 521 - Reading - Spring 2003
  CSE Home   About Us    Search    Contact Info 

Suggested reading will be given from time to time during the course. It is highly recommended that students become familiar with chapters 1-13 in "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein (CLRS). Additional resources are "The Algorithm Design Manual " by Steven S. Skiena, and the papers/surveys below (to be updated along the quarter). 

 

Lecture 9: 

Scheduling Algorithms.

Survey  by Karger, Stein, and Wein.

Lecture 8: 

Greedy Algorithms

CLRS: chapter 17 (1st  ed.) or 16 (2nd edition)

Lecture 7: 

Dynamic Programming:

CLRS: chapter 16 (1st  ed.) or 15 (2nd edition)

Skiena: section 3.1

Linear Programming

CLRS, Chapter29 (2nd ed. Only)

Skiena: Section 8.2.6

Lecture 6:

Coping with NP-hardness: Approximation Algorithms.

CLRS: chapter 37 (1st  ed.) or 35 (2nd edition)

Skiena: section 6.8

Lecture 5:

NP-Completeness Theory:

CLRS: chapter 36 (1st  ed.) or 34 (2nd edition)
Skiena: section 6
Online Resources: Compendium of NP-complete problems
                            The Complexity zoo (just to get an impression of how many different complexity classes are there)
 
Lecture 4: 
Network Flow:
CLRS: chapter 27 (1st  ed.) or 26 (2nd edition)
Skiena: section 8.4.9 (very brief) 
If you want to read about more advanced Network Flow algorithms (min-cost max-flow, and more), here is a survey by Michel Goemans from MIT.
 
Lecture 3: 
Minimum Spanning Tree:
CLRS: chapter 24 (1st  ed.) or 23 (2nd edition)
Skiena: section 4.7
 
Graph Coloring:
Skiena: section 4.5.3 (very brief)
About the history of the map-coloring problem and a brief description of the latest algorithm for map four-coloring.
(just for fun, to give you an idea how complex is this problem that looks so simple).
 
Lecture 2:
DFS, BFS:
CLRS: chapter 22 (1st and 2nd editions).
Skiena: chapter 4.4
 
Shortest Path Problems:
CLRS: chapter 25 (1st  ed.) or 24 (2nd edition).
Skiena: chapter 4.8
 
Lecture 1:
Big-Oh and the other complexity notations:
CLRS: chapter 2 (1st  ed.) or 3 (2nd edition)
Skiena: chapters 1.4 and 1.5 

CSE logo Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to tami@cs.washington.edu]

</body </html