MAT-72006 Advanced Algorithms and Data Structures, 7 cr

Prof. Tapio Elomaa

Fall 2013, periods I ja II

Lectures:
Weekly exercises: M.Sc. Teemu Heinimäki, Wed 8 - 10 TD308
Course exam: Fri Dec. 13, 2013

- News

- General Information

- Lectures

The lectures are based on the book

WeekDatesSlidesExercises Chapters in the Book
1 Aug. 27 & 29 1 - 47 n/a 2 Getting Started
2 Sept. 3 & 5 48 - 99 Sept. 11 3 Growth of Functions, 4 Divide-and-Conquer
3 Sept. 10 & 12 100 - 156 Sept. 18 4, 5 Probabilistic Analysis and Randomized Algorithms
4 Sept. 17 & 19 157 - 217 Sept. 25 5, 6 Heapsort, 7 Quicksort
5 Sept. 24 & 26 218 - 265 Oct. 2 7, 8 Sorting in Linear Time
6 Oct. 1 & 3 266 - 321 Oct. 9 10 Elementary Data Structures, 11 Hash Tables
7 Oct. 8 & 10 322 - 367 Oct. 23 11, 12 Binary Search Trees, 13 Red-Black Trees
8 Oct. 22 & 24 368 - 414 Oct. 30 13, 15 Dynamic Programming
9 Oct. 29 & 31 415 - 460 Nov. 6 15
10 Nov. 5 & 7 461 - 515 Nov. 13 15, 16 Greedy Algorithms, 17 Amortized Analysis
11 Nov. 12 & 14 516 - 558 Nov. 20 17
12 Nov. 21 559 - 581 Nov. 27 18 B-Trees
13 Nov. 26 & 28 582 - 628 n/a 18, 19 Fibonacci Heaps
14 Dec. 3 629 - 667 n/a 35 Approximation Algorithms

- Contents

We intend to selectively cover the following parts of the textbook:

I Foundations
2 Getting Started
3 Growth of Functions
4 Divide-and-Conquer
5 Probabilistic Analysis and Randomized Algorithms
II Sorting and Order Statistics
6 Heapsort
7 Quicksort
8 Sorting in Linear Time
III Data Structures
10 Elementary Data Structures
11 Hash Tables
12 Binary Search Trees
13 Red-Black Trees
IV Advanced Design and Analysis Techniques
15 Dynamic Programming
16 Greedy Algorithms
17 Amortized Analysis
V Advanced Data Structures
18 B-Trees
19 Fibonacci Heaps
VI Graph Algorithms
These are covered in MAT-41196 Graph Theory
VII Selected Topics
35 Approximation Algorithms

- Links


Feb. 13, 2014 http://www.cs.tut.fi/~elomaa/