CECS 528 Recordings of Lectures

  1. Monday, April 27th, Randomized Algorithms and Karger's Algorithm
  2. Friday, April 24th, Introduction to Approximation Algorithms
  3. Supplemental Lecture: Inapproximability of TSP, Christofides' Algorithm for Triangle-TSP
  4. Wednesday, April 22nd, Approximation Algorithms contd.
  5. Monday, April 20th, Approximation Algorithms contd.
  6. Supplemental Lecture: Approximation Algorithms for Vertex Cover and k-Clustering
  7. Supplemental Lecture: DHP to UHP, HP to HC, HC to TSP
  8. Friday, April 17th, 3SAT to Subset Sum, 3SAT to Clique, 3SAT to DHP, DHP to UHP Mapping Reductions
  9. Wednesday, April 15th, 3SAT to DHP Mapping Reduction
  10. Monday, April 13th, Review of 3SAT mapping reductions to Clique and Subset Sum
  11. Review of NP-Completeness and Subset Sum is NP-Complete
  12. Wednesday, March 25, More NP Problems, Class co-NP
  13. Vertex Cover to Half Vertex Cover and more on P and NP
  14. Monday, March 23, Introduction to P and NP
  15. Friday, March 20, Finish Mapping Reductions, Introduce P and NP
  16. Wednesday, March 18, Continuation of Mapping Reducibility
  17. Mapping Reduction from Clique to Independent Set
  18. Friday, March 13th
  19. Logic Problems Part 2
  20. Logic Problems Part 1
  21. Friday, March 6th
  22. Dynamic Programming: Finding Distances in Graphs
  23. Dynamic Programming: Optimal BST's and Matrix Chain Multiplication
  24. Friday, February 27th
  25. Wednesday, February 25th
  26. Wednesday, February 18th
  27. Greedy Algorithms Part 2
  28. Greedy Algorithms Part 1
  29. Fast Fourier Transform Part 2
  30. Friday, February 6th
  31. Wednesday, February 4th
  32. Monday, February 2nd
  33. Additional Divide and Conquer Algorithms
  34. Divide and Conquer Algorithms
  35. Recurrences Part 1
  36. Recurrences Part 2
  37. Wednesday, January 21st