Advanced topics in algorithms

Spring 2013/2014, Tel Aviv University

Lecturer: Haim Kaplan
Time: Thursdays, 16-19
Place: Dan David 110


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





Splay trees (+hidden slides)

Max flow: Dinicís algorithm

Dynamic trees

Max-flow: The algorithm of Goldberg and Rao

Minimum cost flow (the cost scaling technique)

Dynamic connectivity

Order maintenance

Cycle detection

Distance Oracles

Suffix trees

Lowest common ancestors

Suffix arrays

The Burrows-Wheeler transform

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

       Homework 4 (due June 10)†††† sol1 sol2

Exam questions