# 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

1. NP completeness
1. Efficiency, reductions, NP completeness [PS]
2. NP Complete Problems] [PS]
Max Clique, Independent set, Vertex cover, and graph coloring.
3. [Even more NPC Problems] [PS]
Hamiltonian Cycle, TSP, Subset Sum, 3 dimensional matchings, Partition, longest path (the song).
2. Dynamic Programming
1. [04_dprog_notes] [PS]
2. [05_dprog_II_notes] [PS]
3. Approximation Algorithms
1. [06_approx_notes] [PS]
2. [07_approx_II] [PS]
3. [08_approx_III] [PS]
4. Sorting networks
[09_sortnet_notes] [PS]
5. Randomized algorithms
1. [10_rand_notes] [PS]
2. [11_rand2_notes] [PS]
3. [Minimum Cut] [PS]
4. Treaps
[13_treaps] [PS]
6. Network flow
1. [14_flow_I] [PS]
2. [15_flow_II] [PS]
7. Lower bounds
[18_lwr_bnd] [PS]
8. Union-Find
[19_uf] [PS]
9. FFT - Fast Fourier Transform
[20_fft] [PS]
10. Computational Geometry>
1. 19_triang [PS]
2. [20_triang_II] [PS]
3. [22_triang_II] [PS]
4. [23_cg_ch_2d] [PS]
5. [24_cg_vor] [PS]
6. [25_cg_arr_notes] [PS]
11. Linear programming
1. Two dimensions - Megiddo's algorithm [PS]
2. Constant dimension] [PS]
3. Simplex by example [PS]
4. Even more on the simplex algorithm [PS]
5. Perceptron algorithm [PS] - linear programming via iterative methods.
12. Matchings
1. Basic tools [PS] - basic properties, and weighted and unweighted matchings for bipartite graphs.
2. General unweighted case [PS]

Homeworks, exams, etc
1. Fall 2009 - 473G
hw: 0, 1, 2, 3, 4, 5, 6, Exams: midterm, final.
2. Fall 2007 - 473G
hw: 0, 1, 2, 3, 4, 5, 6, Exams: midterm, final.
3. Spring 2006 - 473G
hw: 0, 1, 2, 3, 4, Exams: midterm, final.
hw: 0, 1, 2, 3, 4, 5, 6.
Exams: midterm, midterm II.
final.
hw: 0[ps], 1[ps], 2[ps], 3[ps], 4[ps], 5[ps], 6[ps],
Exams: midterm[ps], final[ps].
6. 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].
7. 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].
8. 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].