Лекция 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.
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 email@example.com and 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.