Advanced algorithms and data structures (Spring 2013)

General information

Course code
ITI8590
Lecturer
James Chapman
Please use the address iti8590-staff@lists.ioc.ee to contact me
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

Session 1
Friday, 2pm -- 4pm, B126, IoC
Session 2
Friday, 4pm -- 6pm, B126, IoC

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

Lectures

Week 1. (01.02.2013)
• Introduction, insertion and merge sort implemented, executed, and analysed. Something to sort: ints.txt. (chapter 2)
• Manipulating summations. (appendix A)
Week 2. (08.02.2013)
• Growth of functions, asymptotic notation + exercises. (chapter 3)
• Solving recurrences + exercises. (chapter 4)
Week 3. (14.02.2013)
• Divide and Conquer algorithms, Strassen's algorithm (chapter 4)
• Homework lab (homework out today!)
Week 4. (22.02.2013)
• Counting and Probability. (appendix C)
• Linear-time sorting. (chapter 8)
Week 5. (29.02.2013)
• Random variables, quicksort + analysis.
• Randomized quicksort, analysis of randomized quicksort.
Week 6. (8.03.2032)
• Order statistics in expected linear time and w-c linear time, analysis.
• Homework lab.
Week 7 (15.03.2013)
• Basic data structures.
• Hashing I.
Week 8 (22.03.2013)
• Hashing II (given by Pavel Grigorenko).
Week 9 (29.03.2012)
• Public holiday.
Week 10 (05.04.2013)
• BSTs/homework feedback (both sessions)
Week 11 (12.04.2013)
• Balanced trees
• homework feedback
Week 12 (19.04.2013)
• Augmenting data structures
• homework lab
Week 13 (26.04.2013)
• Amortized analysis
• Amortized analysis
Week 14 (03.05.2013)
• Dijkstra's algorithm
• homework lab
Week 15 (10.05.2013)
• Dynamic programming by Pavel Grigorenko
Week 16. (17.05.2013)
• Bellman-Ford's algorithm
• Linear Programming

Exercises

Exam

Exam information

2 hours. 4 compulsory questions. Question 1 is multiple choice. To guarantee success you should revise all topics. There are two dates when you can take the exam but you can only take it once this semester.

You can bring 2 double sided hand written A4 pages of notes. No other reference materials (e.g. the textbook) are allowed. Calculators, mobile phones, etc. are not allowed.