From ResearchWiki

Contents 1 History 2 What is an algorithm 3 NP Completeness 4 Basic Paradigms 5 Approximations 6 Randomization 7 Heuristics 8 Lower Bounds 9 Quantum Algorithms 10 Lectures 11 References 12 Homeworks 12.1 Zero

History

• 1964: Cobham proposes that P represent the class of efficient computations, as it is invariant under machine transformations.
• 1965: Edmonds discusses the meaning of 'efficient algorithm' and proposes polynomial time as the definition of 'efficient'
• Michael Sipser's paper on P vs NP from STOC 1992 (and a perspective on worst-case analysis)
• Bob Tarjan's Turing Award Lecture (why ignore constants in worst-case analysis)

Thus, the state of algorithm design in the late 1960s was not very satisfactory. \[...\] the typical content of a paper on a combinatorial algorithm was a description of the algorithm, a computer program, some timings of the program on sample data, and conclusions based on these timings. Since changes in programming details can affect the running time of a computer program by an order of magnitude, such conclusions were not necessarily justified.

• Scott Aaronson's article on P vs NP.

What is an algorithm

• Knuth defn
• A problem is not an algorithm

NP Completeness

• P vs NP
• reductions
• show how problems can be sensitive to the choice of model used.

Basic Paradigms

• Greedy Algorithms
• Dynamic programming
• Prune and search
• Max flow
• FFT ?
• Recurrence relations (George Lueker's paper)

Approximations

• Basic setup
• vertex cover
• set cover
• LP-based methods
• Knapsack

Randomization

• Tail bounds
• Min cut
• Closest pair
• Hashing
• approximate counting

Heuristics

• Local search methods
• Metropolis, EM/k-means

Lower Bounds

• decision trees
• 3SUM
• minimax

Quantum Algorithms

Lectures

1. 08/20: History of algorithms: what is an algorithm ? polynomial time. algorithm vs problem. HW0
2. 08/22: NP-hardness: P vs NP: reductions, Cook-levin: 3SAT
3. 08/27: NP-hardness; Examples of different kinds of reductions.HW0 DUE
4. 08/29: Recurrences and Analysis
5. 09/05: Divide and Conquer/Recursion I: Mergesort, Closest Pair
6. 09/10: Divide and Conquer/Recursion II: MIS, 3SAT, FFT (might need another lec)/ HW1
7. 09/12: Dynamic Programming I: Interval scheduling, knapsack
8. 09/17: Dynamic Programming II: BLAST (sequence alignment)
9. 09/19: Greedy algorithms I: Principle of switching/staying ahead to prove optimality. Caching
10. 09/24: G II: MST HW2
11. 09/26: G III: Matroids
12. Approximations I: Definitions, Load Balancing, Vertex Cover
13. Approximations II: Interval scheduling, Set Cover
14. Approximations III: Dynamic Programming to get PTASs
15. Approximations IV: Linear programming and Vertex Cover
16. Flows I: definition of flow, ford-fulkerson algorithm HW3
17. Flows II: max flows and min cut.
18. Randomness III
19. Randomness IV
20. Flows IHW4
21. Flows II
22. Flows III
23. Linear Programming I
24. Simplex HW5
25. LP-based Approximations: (Randomized) Rounding
26. LP-based approximations: Primal-Dual.
27. Heuristic Methods
28. Parallel Algorithms HW6
29. Quantum Algorithms
30. A Case Study: sorting with reversals

References

• Algorithm Design (Kleinberg/Tardos)
• UIUC Algorithms, Spring 2007.

Homeworks

Zero

• checkers problem (graphs)
• O() ordering
• Twelfth day of christmas problem (how many gifts do you get) (analysis)
• KT 3.4 (butterfly classification)
• KT 13.1 (3coloring a graph so 2/3 of all edges are properly colored)