Home Bookmarks Papers Blog

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.
    4. Spring 2005 (undergrad)
      hw: 0, 1, 2, 3, 4, 5, 6.
      Exams: midterm, midterm II.
      final.
    5. Fall 2003 (grad)
      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].

Additional Notes

  1. Hashing [16_hash_notes] [PS]
Last modified: Thu Dec 10 11:39:16 CST 2009