Advanced topics in algorithms

Spring 2012/2013, Tel Aviv University

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

Announcements:

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

·

Presentations

· 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 2 sol1 sol2

· Homework 3 sol1 sol2

· Homework 4 sol1 sol2

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

Bibliography

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

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

· cycle detection and strings