MAT-72006 Advanced Algorithms and Data Structures, 7 cr

Prof. Tapio Elomaa

Fall 2014, periods I ja II

Lectures:
Weekly exercises: M.Sc. Teemu Heinimäki Tue 10 - 12 TC429 (PI), TD308 (PII)
Course exam: Tue Dec. 9, 2014

- News

- General Information

- Lectures

The lectures are based on the book

WeekDatesSlidesExercises Chapters in the Book
1 Aug. 26 & 28 1 - 66 n/a 2 Getting Started
2 Sept. 2 & 4 67 - 113 Sept. 9 3 Growth of Functions, 4 Divide-and-Conquer
3 Sept. 9 & 11 114 - 178 4, 5 Probabilistic Analysis and Randomized Algorithms
4 Sept. 18 179-185, 275-294 5, 9 Medians and Order Statistics
5 Sept. 23 & 25 295-304, 323-366 9, 11 Hash Tables
6 Sept. 30 & Oct. 2 367-374, 422-471 11, 14 Augmenting Data Structures, 15 Dynamic Programming
7 Oct. 7 & 9 472 - 515 15.2 Matrix-chain multiplication, 15.4 Longest common subsequence
8 Oct. 21 & 23 516 - 565 15.4 Optimal binary search trees, 16 Greedy Algorithms
9 Oct. 28 & 30 566 - 621 17 Amortized Analysis
10 Nov. 4 & 6 622 - 691 18 B-Tree, 19 Fibonacci Heaps
11 Nov. 11 & 13 692 - 735 28 Matrix Operations
12 Nov. 18 & 20 736 - 785 29 Linear Programming
13 Nov. 25 & 27 786 - 836 35 Approximation Algorithms
14 Dec. 2 & 4 837 - 860 31 Number-Theoretic 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
9 Medians and Order Statistics
III Data Structures
10 Elementary Data Structures
11 Hash Tables
12 Binary Search Trees
13 Red-Black Trees
14 Augmenting Data Structures
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
28 Matrix Operations
29 Linear Programming
31 Number-Theoretic Algorithms
35 Approximation Algorithms

- Links


Dec. 3, 2014 http://www.cs.tut.fi/~elomaa/