CS 4820: Design and analysis of algorithms

Announcements

Schedule

All readings are from the text unless otherwise indicated.

Topic Date Reading Lecture
7/1 §1.2 introduction
Greedy algorithms 7/2 §1.1 stable matching
7/3 §4.1, §4.2interval scheduling, minimizing lateness
7/4 notes no class (happy independence day!)
  7/5 §4.5 minimum spanning trees
7/8 Kruskal's algorithm
Divide and conquer 7/9 §5.1, §5.2mergesort, solving recurrences, master theorem
7/10 §5.5, §6.1, §6.2 large integer multiplication
Dynamic programming fibonacci, memoization, weighted interval scheduling
7/11 §6.6 sequence alignment
7/12 §6.8 Bellman-Ford
Flow 7/15 browse chapter 7 network flow, a cornucopia of problems
7/16 review
7/17 prelim I
  7/18 §7.1 Ford-Fulkerson
7/19 §7.2 max-flow min-cut theorem
7/22 §7.3 delta-scaling, circulation
7/23 §7.7 circulation with lower bounds
NP completeness §8.1 polynomial time reductions
7/24 §8.3, § 8.4 definitions of P, NP, NP-hard, NP-complete,
§8.2 vertex cover and independent set
7/25 §8.2 fun with SAT
7/26 §8.5 Hamiltonian paths
7/29 §8.1, §8.5 traveling salesman problem, set cover
7/30 §8.6, §8.7, §8.8 3-coloring, 3d matching, subset sum
§8.10 taxonomy of NP-complete problems
Undecidability 7/31 notes, §1, §2 Turing machines
8/1 notes, §5.2 proving Cook-Levin, nondeterministic Turing machines
8/2 notes, §3 universal turing machines
8/5 notes, §4.1–§4.4 undecidability, the halting problem
8/6 notes, §4.5 Rice's theorem

Course staff

Dates and times

Lecture:

Mike's office hours

Workshop/Office hours

Prelim I

Prelim II

Final

Grading

The course grade will be based on the homeworks (roughly 20%), the exams (roughly 20% prelim I, 20% prelim II, 25% final exam), and class participation (roughly 15%, including mini problem sets that I will give for discussion).

Academic Integrity

Academic integrity is important for two reasons. The first is that the course is designed to help you learn the material. If you don't do the work you won't learn the material. The second is that we grade you; this would be meaningless if the work we grade is not yours.

You are encouraged to work together to figure out solutions to the problem sets. However, the work you submit should be your own; copying others' papers is forbidden. My strategy is to write rough notes while working with others and then try to write up my submission without referencing them. This ensures both that I learn the material, and that I comply with the requirements of integrity.