22C:31 Algorithms

Lincoln Lourens		Office hours: Friday 1:30-2:30		Office: B20J, MLH 	Phone: 515 975 4539 (cell) 	E-mail: lincoln-lourens@uiowa.edu
              			      Wed 3:30-4:30

Clifton J. (CJ) Palmer	Office hours: Mon: 1:30-2:30		Office: B20J, MLH 	Phone: 				E-mail: clifton-palmer@uiowa.edu
              			      Tues: 2:15-3:15

• Week 13: 4/19-4/23 How can knapsack and subset sum have dynamic programming solutions even when they are said to be intractable? Introduction to pseudo-polynomial time algorithms. Final example of dynamic programming: The Bellman-Ford Algorithm. Introduction to NP-completeness.

• Week 12: 4/12-4/16 Finished up the longest common subsequence problem. The knapsack problem and the subset sum problem. Dynamic programming solution to the subset sum problem.

• Week 11: 4/5-4/9 Two more examples of 1-dimensional dynamic programming algorithms: finding a longest path in an ordered graph, pretty printing. Examples of 2-dimensional dynamic programming: matrix-chain multiplication and longest common subsequence.

• Week 10: 3/29-4/2 Finding a local minima via divide-and-conquer. Introduction to dynamic programming. Why recursion can be costly. Memoization as a solution. The example of computing Fibonacci numbers. Our first example: weighted interval scheduling.

• Week 9: 3/22-3/26 More examples of the divide-and-conquer paradigm. Closest point pair problem, Strassen matrix multiplication algorithm, and computing the local minima in a matrix.
  Reading: Sections 5.4 and 6.1

• Week 8: 3/8-3/12 Solving recurrence relations using the recursion tree method and by use the substitution method. Proof that merge sort runs in O(n log n) time. A divide-and-conquer algorithm for counting inversions. A divide-and-conquer algorithm for closest point pair.
  Reading: Sections 5.3 and 5.4.

• Week 7: 3/1-3/5 The Union-Find data structure. An implementation that has good average running time. Efficient implementation of Kruskal's algorithm using the Union-Find data structure. The divide-and-conquer paradigm. MergeSort as a first example of a divide-and-conquer algorithm.
  Reading: Sections 5.1 and 5.2.

• Week 6: 2/22-2/26 Exam 1 review; homework 2 review. Greedy algorithms for minimum spanning tree. Cut Theorem. Correctness of Prim's and Kruskal's algorithm derived from the Cut Theorem.
  Reading: Sections 4.4 and 4.5.

• Week 5: 2/15-2/19 Greedy algorithm for the problem of scheduling to minimize lateness. Proof via the "exchange argument." The shortest path problem and the minimum spanning tree problem. Dijkstra's algorithm for the shortest path problem. Proof of correctness and running time analysis.
  Reading: Sections 4.4 and 4.5.

• Week 4: 2/8-2/12 The interval scheduling problem. Proof that greedy "stays ahead." The interval coloring problem. Proof that greedy matches lower bound.
  Reading: Sections 4.1 and 4.2.

• Week 3: 2/1-2/5 More examples of the use of asymptotic notation. Logarithmic functions vs Polynomial functions vs Exponential functions. Common running times of algorithms. Introduction to greedy algorithms. The interval scheduling problem.
  Reading: All of Chapter 2 and Section 4.1.

• Week 2: 1/25-1/29 Analyzing the running time of algorithms: basic operations, worst case analysis. Example 1: showing that InsertionSort runs in quadratic time. Example 2: showing that BinarySearch runs in logarithmic time. Asymptotic notation: Big Oh, Big Omega, and Big Theta.
  Reading: Sections 2.1, 2.2, and 2.4.

• Week 1: 1/18-1/22 Five representative problems: interval scheduling, weighted interval scheduling, closest point pair, traveling salesperson problem, maximum independent set Constructing counterexamples for greedy algorithms.
  Reading: All of Chapter 1, including the material on the Stable Marriage problem.

• None yet.