473 Algorithms
The following is my class notes for CS 473 (algorithms). Those class
notes are all written by me, but a large fraction of them (content
wise) are based on the class
notes by Jeff Erickson. Note that although some of those notes
were used in combined courses with undergrads/grads, they are mainly
targeted at grad students.
In any case, some of this class notes were updated in my 473G class
notes, available here .
Class notes
NP completeness
Efficiency, reductions, NP
completeness
[PS ]
NP Complete Problems ]
[PS ] Max Clique, Independent
set, Vertex cover, and graph coloring.
[Even more NPC Problems ]
[PS ]
Hamiltonian Cycle, TSP, Subset Sum, 3 dimensional matchings,
Partition, longest path (the song).
Dynamic Programming
[04_dprog_notes ]
[PS ]
[05_dprog_II_notes ]
[PS ]
Approximation Algorithms
[06_approx_notes ]
[PS ]
[07_approx_II ]
[PS ]
[08_approx_III ]
[PS ]
Sorting networks
[09_sortnet_notes ]
[PS ]
Randomized algorithms
[10_rand_notes ]
[PS ]
[11_rand2_notes ]
[PS ]
[Minimum Cut ]
[PS ]
Treaps
[13_treaps ]
[PS ]
Network flow
[14_flow_I ]
[PS ]
[15_flow_II ]
[PS ]
Lower bounds
[18_lwr_bnd ]
[PS ]
Union-Find
[19_uf ]
[PS ]
FFT - Fast Fourier Transform
[20_fft ]
[PS ]
Computational Geometry>
19_triang
[PS ]
[20_triang_II ]
[PS ]
[22_triang_II ]
[PS ]
[23_cg_ch_2d ]
[PS ]
[24_cg_vor ]
[PS ]
[25_cg_arr_notes ]
[PS ]
Linear programming
Two dimensions - Megiddo's algorithm
[PS ]
Constant dimension ]
[PS ]
Simplex by example
[PS ]
Even more on the simplex algorithm
[PS ]
Perceptron algorithm
[PS ] - linear programming via
iterative methods.
Matchings
Basic tools
[PS ] - basic properties,
and weighted and unweighted matchings for bipartite graphs.
General unweighted case
[PS ]
Homeworks, exams, etc
Fall 2009 - 473G
hw:
0 ,
1 ,
2 ,
3 ,
4 ,
5 ,
6 ,
Exams:
midterm ,
final .
Fall 2007 - 473G
hw:
0 ,
1 ,
2 ,
3 ,
4 ,
5 ,
6 ,
Exams:
midterm ,
final .
Spring 2006 - 473G
hw:
0 ,
1 ,
2 ,
3 ,
4 ,
Exams:
midterm ,
final .
Spring 2005 (undergrad)
hw:
0 ,
1 ,
2 ,
3 ,
4 ,
5 ,
6 .
Exams:
midterm ,
midterm II .
final .
Fall 2003 (grad)
hw:
0 [ps ] ,
1 [ps ] ,
2 [ps ] ,
3 [ps ] ,
4 [ps ] ,
5 [ps ] ,
6 [ps ] ,
Exams: midterm [ps ] ,
final [ps ] .
Spring 2003
hw:
0 [ps ] ,
1 [ps ] ,
2 [ps ] ,
3 [ps ] ,
4 [ps ] ,
5 [ps ] ,
6 [ps ] ,
7 [ps ] ,
8 [ps ] .
Exams: midterm 1 [ps ] ,
midterm 2 [ps ] .
final [ps ] .
Spring 2002
hw:
0 [ps ] ,
1 [ps ] ,
2 [ps ] ,
3 [ps ] ,
4 [ps ] ,
5 [ps ] ,
6 [ps ] ,
7 [ps ] ,
8 [ps ] .
Exams: midterm 1 [ps ] ,
midterm 2 [ps ] .
final [ps ] .
Fall 2001
hw:
0 [ps ] ,
1 [ps ] ,
2 [ps ] ,
3 [ps ] ,
4 [ps ] ,
5 [ps ] ,
6 [ps ] ,
7 [ps ] ,
8 [ps ] .
Exams: midterm 1 [ps ] ,
midterm 2 [ps ] .
final [ps ] .
Additional Notes
Hashing
[16_hash_notes ]
[PS ]
Last modified: Thu Dec 10 11:39:16 CST 2009