Analysis of Algorithms I, CSW4231

Summer 1999

Grading

• homeworks (30%)
• a midterm (30%)
• a final (40%).

This Summer, the midterm will be held on July 8 and the final will be held on August 6.

There will be two small changes from when the course was taught in Fall. I am listing them here to avoid confusion if either fact is discussed on video. The two changes are:

• Each student's homework grade will be the average of their best 5 assignments (not the best 4, as was the case in Fall).
• The final exam still consists of the same 4 questions as last Fall, but each will be worth 25 and the maximum score will be 100 (last Fall, each question was worth 35, and there was a maximum cutoff of 120).

Problem Sets

• Problem set 1 was due Oct 5, now due June 15.
  • Problem set 1 solutions.
• Problem set 2 was due Oct 19, now due June 24.
  • Problem set 2 solutions.
• Practice midterm not to be handed in.
  • Practice midterm solutions.
• Midterm given July 8.
  • Midterm solutions.
• Problem set 3 was due Nov 16, now due July 13.
  • Problem set 3 solutions.
• Problem set 4 was due Nov 30, now due July 22.
  • Problem set 4 solutions.
• Problem set 5 was due Dec 14, now due July 30.
  • Problem set 5 solutions.
• Problem set 6 was due Dec 21 (during final), now due with final exam.

Contents of Lectures (with original dates and suggested Summer dates):

• Sep 14/June 1 - Administrativia. Introduction: analysis of algorithms, asymptotic analysis, models of computations, the master theorem for solving recurrences.
  References: CLR Sections 1.1, 1.2, 1.3, 4.3, 4.4.
  [Slides] [Notes]
• Sep 21/June 4 - Techniques for algorithm design. Divide and conquer: binary search, maximum and minimum, polynomial multiplication, matrix multiplication. Dynamic programming: subset sum, knapsack.
  References: CLR Sections 10.1, 31.1, 31.2, 16.2.
  [Slides] [Notes]
• Sep 28/June 10 - Techniques for algorithm design. Dynamic programming: matrix chain multiplication, edit distance, longest common subsequence. Greedy: file storing, fractional knapsack.
  References: CLR Sections 16.1, 16.3, 17.2. (See also Notes from previous lecture).
  [Slides]
• Oct 5/June 15 - Greedy: Huffman algorithms. Sorting in linear time.
  References: CLR Sections 17.3, 9.2, 9.3, 9.4.
  [Slides] [Notes]
• Oct 12/June 18 - Median in linear time. Hash tables.
  References: CLR Sections 10.2, 10.3, 12.1, 12.2.
  [Slides]
• Oct 19/June 24 - Hashing and Binary Search Trees.
  References: CLR Sections 12.3, 13.1, 13.2, 13.3
  [Slides]
• Oct 26/June 29 - Balanced Search Trees.
  References: CLR Sections 14.1, 14.2, 14.3, 14.4, 19.1, 19.2, 20.1, 20.2.
  [Slides]
• Nov 9/July 8 - MIDTERM
  
• Nov 16/July 13 - Graph Algorithms: Definitions, BFS, DFS, Strong Connectivity
  References: CLR Sections 23.1, 23.2, 23.3, 23.5.
  [Slides]
• Nov 23/July 16 - Graph Algorithms: Topological sort, Shortest paths, Minimum Spanning Tree.
  References: CLR Sections 23.4, 24.1, 24.2, 25.1, 25.2, 25.3, 26.2.
  [Slides]
• Nov 30/July 22 - Graph Algorithms: Random walks for s-t connectivity, Maximum Flow, Minimum Cut, Minimum Global Cut, Maximum Matching in Bipartite Graphs.
  References: CLR Sections 27.1, 27.2, 27.3.
  [Slides]
• Dec 7/July 27 - NP-completeness: Definitions; NP-completeness of Circuit SAT, CNF SAT and 3CNF SAT.
  References: CLR Sections 36.1, 36.2, 36.3, 36.4.
  [Slides]
• Dec 14/July 30 - NP-completeness: Independent Set, Vertex Cover, Clique, Subset Sum, Partition, Bin Packing, Hamiltonian Circuit, TSP. Approximation Algorithms: Vertex Cover, Bin Packing, TSP, Max SAT, Max CUT
  References: CLR Sections 36.5, 37.1, 37.2.
  [Slides]