Home | Bookmarks | Papers | Blog |

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.

- 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].

- Hashing [16_hash_notes] [PS]

Last modified: Thu Dec 10 11:39:16 CST 2009