Time: Thursdays, 16-19

Place: Dan David 110

Announcements:

Links to solutions of homework are available below.

The exam is with closed material on this Friday. I will post soon a question
or two as examples. You will have to choose 3 out of 4 open questions. **Good luck!**

Tentative topics:

·
Splay trees.

·
Dynamic trees

·
Maximum flow

·
Minimum cost flow

·
Dynamic connectivity

·
Online cycle detection

·

Presentations

Max-flow: The algorithm of Goldberg and Rao

Minimum cost flow (the cost scaling technique)

Pattern matching with
mismatches

Lecture notes by Barak Itkin (which were not proof read by me)

List
of homework

·
Homework 1 (due March 20) sol1
sol2

·
Homework 2 (due April 25) sol1
sol2

·
Homework 3 (due May 18) sol1
sol2 sol3