- Class participation 10%.
- Homework 30%.
- Midterm 30%. Out on Wednesday, February 27, 2019, 15:00 EST. Due on Thursday, February 28, 2019, 15:00 EST.
- Final 30%. Out on Monday, April 22, 15:00 EST. Due on Tuesday, April 23, 15:00 EST.

- No late homework or exam will be accepted.
- Collaborating with other students in the class on homework problems is fine and encouraged, though we urge you to attempt working out all of the problems by yourself first. In any case, you must write up your solutions, in your own words. Furthermore, if you did collaborate on any problem, you must clearly list all of the collaborators in your submission.
- No collaboration is allowed on the midterm and final exams. You must work on the midterm and final exams on your own.
- For your solutions you can use what we saw in class and what you were supposed to know before taking this class. Anything else must be proved from scratch. In particular, finding solutions to problems on the web, or by asking students not enrolled in the class (or the class staff) is strictly prohibited. No late homework or exam will be accepted.
- You should type your solutions to the homework and exams using LaTeX. LaTeX is a scientific document preparation system; most CS technical publications are prepared using this tool. There are many good, cross-platform, free editors. They include LyX (which I use regularly), TeXstudio, and overleaf (which I also use regularly). To use LyX you don't really have to know anything about LaTeX. If you want to know more about LaTeX The not so short introduction to LateX is a good reference to get you started.

- [E] Algorithms, by J. Erickson
- [CLRS] Introduction to Algorithms, third edition, by T. Cormen, C. Leiserson, R. Rivest, and C. Stein
- [DPV] Algorithms, by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
- [KT] Algorithm Design, by Jon Kleinberg, Éva Tardos

- [V] Algorithms and complexity, by E. Viola

Bubblesort [CLRS, Problem 2-2]

Countingsort [CLRS, 8.2]

Radixsort [CLRS, 8.3]

Mergesort [E, 1.4], [CLRS, 2.3]

Quicksort [E, 1.5], [CLRS, 7]

Oblivious mergesort [V, 2.1]

Median [E, 1.8], [CLRS, 9.3]

Closest pair [CLRS, 33.4]

Karatsuba's integer multiplication [E, 1.9], [KT 5.5]

Strassen's matrix multiplication [CLRS, 4.2]

Fast Walsh-Hadamard transform [V, 2.2]

Polynomials and fast Fourier transform [CLRS, 30], [KT, 5.6]

Coin-change problem

Longest common subsequence [CLRS, 15.4]

Subset sum [E, 3.8]

Dynamic programming in economics [V, 3.1]

Activity selection [E, 4.2], [CLRS, 16.1]

Binary search trees [CLRS 12.1, 12.2] [V 4]

Rotations [CLRS 13.2] [V 4]

AA Trees [V 4]

Hash functions [CLRS 11]

Heaps [CLRS 6]

Graph representations [E 5.4], [CLRS 22.1]

Breadth-first search [E 8.4], [CLRS 22.2]

Bellman-Ford [E 8.7] [CLRS 24.1]

Dijkstra [E 8.6], [CLRS 24.3]

All-pairs shortest-path via matrix multiplication [E 9.7], [CLRS 25.1]

Floyd Warshall [E 9.8], [CLRS 25.2]

Johnson's algorithm [E 9.4], [CLRS 25.3]

3SAT reduces to CLIQUE [CLRS 34.5.1]

CLIQUE to VERTEX-COVER [CLRS 34.5.2]

3SAT reduces to SUBSET-SUM [CLRS 34.5.5]

3SAT reduces to 3COLOR [E 12.10]

Flow networks [E 10.1 - 10.3] [CLRS 26.1] (our notation is closer to edition 2 CLRS)

Ford-Fulkerson [E 10.4] [CLRS 26.2]

Edmonds-Karp [E 10.6] [CLRS 26.3]

Maximum bipartite matching [E 11.3], [CLRS 26.4]

The linear programming problem [CLRS 29.1, 29.2]

The simplex algorithm [CLRS 29.3]

Duality [CLRS 29.4]

2-approximation for VERTEX-COVER [CLRS 35.1]

2-approximation for weighted VERTEX-COVER [KT 11.6]

Vector programs, randomized rounding, and max-cut