Advanced algorithms and data structures (Spring 2012)

General information

Course code
ITI8590
Lecturers
James Chapman
Pavel Grigorenko

Please use the address iti8590-staff@lists.ioc.ee to contact us
ECP
6.0
Textbook
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd edition). MIT Press, 2009.

When and where

ODD WEEKS
Session 1
Tuedsday, 2pm -- 4pm, B126, IoC
Session 2
Tuesday, 4pm -- 6pm, B126, IoC

EVEN WEEKS
Session 1
Tuedsday, 12pm -- 2pm, B126, IoC
Session 2
Tuesday, 2pm -- 4pm, B126, IoC

How the time is used in the two sessions will vary from week to week.

Lectures

Week 1. (31.01.2012) - James
• Introduction, insertion and merge sort implemented, executed, and analysed.
• Manipulating summations.
Week 2. (07.02.2012) - James
• Growth of functions, asymptotic notation + exercises.
• Solving recurrences + exercises.
Week 3. (14.02.2012) - Pavel
• Divide and Conquer algorithms.
• Strassen's matrix multiplication. Sets and relations.
Week 4. (21.02.2012) - Pavel
• Relations and functions.
• Quicksort, analysis of quicksort.
Week 5. (28.02.2012) - Pavel
• Counting theory, probability, indicator random variables.
• Randomized quicksort, analysis of randomized quicksort.
Week 6. (06.03.2012) - James
• Linear-time sorting.
• Exercises 1 feedback.
Week 7. (13.03.2012) - James
• Order statistics in expected linear time and w-c linear time, analysis.
• Exercise lab.
Week 8. (20.03.2012) - Pavel
• Hashing. Collision resolution by Chaining. Division and Multiplication methods. Analysis.
• Handling collisions by Open Addressing. Linear probing and Double hashing.
Week 9. (27.03.2012) - Pavel
• Universal Hashing, analysis.
• Perfect Hashing, analysis.
Week 10. (03.04.2012) - James
• BSTs, randomly built BSTs, analysis.
• No lab.
Week 11. (10.04.2012) - James
• Red-black trees.
• Exercise lab.
Week 12. (17.04.2012) - Pavel
• Dynamic programming. Rod cutting problem.
• Longest Common Subsequence.
Week 13. (24.04.2012) - Pavel
• Graphs recap.
• Greedy algorithms. Minimum Spanning Trees.
Week 14. (01.05.2012)
• Holiday.
Week 15. (07.05.2012) - James
• Dijkstra's algorithm.
• Exercise lab.
Week 16. (15.05.2012) - James
• Bellman-Ford's algorithm + Exercises 2 feedback.
• Exercise lab.

Exercises

Exam