Advanced topics in algorithms

Spring 2012/2013, Tel Aviv University

Lecturer: Haim Kaplan
Time: Tuesdays, 16-19
Place: Dan David 001


1.      The exam is on July 11 at 14. We have moed B scheduled for August 15 at 9.

2.      The exam is with open material.

3.      If you know in advance that you will not attend the exam on July 11 please let me know!

4.      Solutions to the homework and the test from last year are attached

Tentative topics:

         Splay trees.

         Dynamic trees

         Maximum flow

         Minimum cost flow

         Dynamic connectivity

         Online cycle detection





         Splay trees (+hidden slides)

         Dynamic trees

         Max flow: Dinicís algorithm

         Max flow: Preflow push

         Minimum cost flow (the cost scaling technique)

         Max flow: The Algorithm of Goldberg and Rao

         Dynamic connectivity

         Order maintenance

         Cycle detection

         Suffix trees and algorithms on strings

         Suffix arrays


List of homework

         Homework 1 sol1 sol2

         Homework 2sol1 sol2

         Homework 3sol1 sol2

         Homework 4sol1 sol2

         The final test from last year (questions 2 and 4 are not relevant)



         splay trees, dynamic trees, maximum flow, minimum cost flow

         Goldberg-Rao maximum flow algorithm, dynamic connectivity, order maintenance

         cycle detection and strings