CIS 621 Algorithms and Complexity

Winter 2008

• crn: 21426
• room: 30 Pacific
• times: Monday and Wednesday, 12:00-1:20pm
• instructor: Chris Wilson
• contact info: room 326 DES, 346-3412, cwilson@cs.uoregon.edu
• office hours: 2:30-4:00 MWF
• text: Algorithm Design, by Kleinberg and Tardos, Addison-Wesley, 2006.

evaluation

This will be based on written homework. There will be no exams, but there will be at the end of the term a take-home test, more or less the same format as the assignments, to be due Tuesday, March 18.

potential topics

• algorithm basics (§1, §2)
• graph traversals (§3)
• greedy method (§4)
• divide & conquer (§5): simple integer multiplication (§5.5), Strassen's method, FFT (§5.6)
• dynamic programming (§6): there's a lot here
• amortization: fibonacci heaps, disjoint sets (not covered in this text)
• NP completeness (§8)
• Beyond NP to PSPACE (§9)
• approximation algorithms (§11)
• this seems like too much to fit into ten weeks

next lectures

• (Jan 7) We'll start out with chapter 1: "Some representative problems"
• (Jan 9) Continuing chapter 1.
• (Jan 14) The stable matching problem and implementation from chapters 1 and 2, then start simple graph algorithms from chapter 3.
• (Jan 16) Depth and breadth first searching of graphs.
• (Jan 21) No class, MLK Day.
• (Jan 23) Finish DFS. Greedy method: interval scheduling, shortest paths.
• (Jan 28) Shortest paths and minimum spanning trees.
• (Jan 30) Minimum spanning trees, Huffman codes.
• (Feb 4) Divide and conquer: master method, inversion, Strassen, integer multiplication.
• (Feb 6) Divide and conquer: polynomial multiplication. APSP.
• (Feb 11) Dynamic programming: Floyd-Warshall, interval scheduling.
• (Feb 13) Dynamic programming: memoization, knapsack, matrix chain product.
• (Feb 18) Dynamic programming: obst, rna secondary structure.
• (Feb 20) Amortized analysis and union-find.
• (Feb 25) Fibonacci heaps. Polynomial reductions.
• (Feb 27) More reductions. Definitions of NP.
• (Mar 3) Satisfiability. 3SAT and 3COL.
• (Mar 5) Cook-Levin Theorem
• (Mar 10) More reductions.
• (Mar 12) Beyond NP: co-NP and PSPACE.

upcoming reading

• §1 and §2.
• §3.
• §4, sections 1, 4-8
• §5, sections 1,2,3,5,6
• §6, sections 1, 2, 4, 5, 8, 9
• §8.

assignments

• Assignment 1, due January 23.
• Assignment 2, due February 6.
• Assignment 3, due February 20.
• Assignment 4, due March 5.
• Assignment 5, due March 12.
• take home final, due March 19.

supplemental readings

• Algorithms, 2nd edition, Cormen, Leiserson, Rivest, and Stein, MIT Press/McGraw-Hill, 2001.
• Algorithms, Dasgupta, Papadimitriou, and Vazirani, McGraw-Hill, 2008.
• The Art of Computer Programming, I & II, Knuth, Addison-Wesley, 1975.
• Computers and Intractability, Garey and Johnson, Freeman 1979
• The Complexity Zoo.

comments and announcements

• Useful for chapter 5 is this description of the master theorem for solving recurrence relations.
• Here is a nice Wikipedia entry for the stable marriage problem.
• Regarding the Jan. 9 possibly confusing class slides:
  • That any proof (like we discussed wrt NP) can be written so that only 10 or 20 bits need to be checked has to do with probabilistically checkable proofs: see here and here.
  • That as one thing becomes provably hard, another thing becomes easier, comes from natural proofs.
  • The blog entry the slides were from is here - see the comments for (some) explanations. There's more
• You are welcome to drop by my office outside official office hours