Продвинутые алгоритмы (Advanced Algorithms) курс Harvard University COMPSCI 224 лекция 1 — 25

Продвинутые алгоритмы, Advanced Algorithms курс Harvard University COMPSCI 224 лекция 1 — 25

• Лекция 1. Logistics, course topics, word RAM, predecessor, van Emde Boas, y-fast tries.
• Лекция 2.Fusion trees, word-level parallelism, most significant set bit in constant time.
• Лекция 3.Hashing: load balancing, k-wise independence, chaining, linear probing.
• Лекция 4.Symmetrization, hashing: linear probing (5-wise indep.), bloom filters, cuckoo hashing, bloomier filters.
• Лекция 5.Hashing: cuckoo hashing analysis, power of two choices.
• Лекция 6.Amortized analysis, binomial heaps, Fibonacci heaps.
• Лекция 7. Splay trees.
• Лекция 8.Online algorithms, competitive analysis, move-to-front, paging.
• Лекция 9.Randomized paging, packing/covering linear programs, weak duality, approximate complementary slackness, primal/dual online algorithms (2-competitive deterministic ski rental).
• Лекция 10.Online primal/dual: e/(e-1) ski rental, set cover; approximation algorithms via dual fitting: set cover.
• Лекция 11.Approximation algorithms via dual fitting (wrap-up), LP integrality gaps, definitions of PTAS/FPTAS/FPRAS, PTAS for knapsack.
• Лекция 12.FPTAS (knapsack), FPRAS (DNF counting), semidefinite programming, Goemans-Williamson MAXCUT algorithm.
• Лекция 13.Guest lecture: Rong Ge.
• Лекция 14.linear programming: standard form, vertices, bases, simplex.
• Лекция 15.Simplex wrap-up, strong duality, complementary slackness, ellipsoid, intro to interior point.
• Лекция 16.Path-following interior point, first order methods (gradient descent).
• Лекция 17.Second order methods (Newton’s method), path-following interior point wrap-up.
• Лекция 18.Learning from experts, multiplicative weights.
• Лекция 19.Linear programming via multiplicative weights, flows, augmenting paths.
• Лекция 20.Scaling for max flow, blocking flow.
• Лекция 21.Preferred path decomposition, link-cut trees.
• Лекция 22.Heavy-light decomposition, O(log2n) amortized analysis of link-cut trees, min cost max flow, min cost circulation, shortest augmenting paths.
• Лекция 23.More efficient exponential-time algorithms: exponential divide-and-conquer (TSP), pruned brute force (3-SAT), Schöning’s algorithm (3-SAT), inclusion-exclusion (k-colorability).
• Лекция 24.Zeta transform, Möbius inversion, streaming algorithms, necessity of randomization and approximation, distinct elements.
• Лекция 25.Power of random signs: ℓ2 norm estimation, subspace embeddings (regression), Johnson-Lindenstrauss, deterministic point query.

Policies

• No late days. No extensions.
• Each student will have their lowest problem set score dropped.
• Each problem set contributes the same amount to your final grade (other than the one that’s dropped).
• The answers must be typeset in LaTeX; here is a template to start with.
• Each problem set will have an associated page limit which submissions must fit into. Anything beyond the page limit will not be read. Use at least 10 pt font and 1 inch margins.
• Submissions must be via email to cs224-f14-assignments@seas.harvard.eduand include a compiled PDF attachment. The file name should follow the pattern: [first-initial][last-name]-ps[number].pdf; for example, a solution to the 3rd assignment from John Doe should be named jdoe-ps3.pdf.
• Solutions do not need to include all calculations, trivial details etc. Just prove to us that you found the solution, and that you understand it well.
• Homework is always due at 11:59pm on the due date.
• Collaboration to solve homework problems is allowed, but students must then write up the solutions on their own and list names of all collaborators at the beginning of the first page.
• You may read papers to help find solutions to problems, but they must be properly cited, and you must explain the solution in a way that demonstrates your understanding (a homework submission simply stating «this problem is solved in paper X» would receive no credit, for example). Bibliographies do not count toward page limits.

Assignments

1. Due Monday, Sept. 15: [PDF][TeX]
2. Due Wednesday, Sept. 24: [PDF][TeX]
3. Due Monday, Oct. 6: [PDF][TeX]
4. Due Wednesday, Oct. 15: [PDF][TeX]
5. Due Monday, Oct. 27: [PDF][TeX]
6. Due Wednesday, Nov. 5: [PDF][TeX]
7. Due Monday, Nov. 17: [PDF][TeX]
8. Due Wednesday, Nov. 26: [PDF][TeX]