MAT-72006 Advanced Algorithms and Data Structures, 7 cr

Prof. Tapio Elomaa

Fall 2016, periods I ja II

Lectures:
Exceptions:
Weekly exercises: M.Sc. Juho Lauri Thu 12-14 TB224
Course exam: Fri Dec. 16, 2016 @ 13 - 16

- News

- General Information

- Lectures

The lectures are based on the book

WeekDatesSlidesExercises Chapters in the Book
1 Aug. 29 & 31 1 - 57 Sept. 8 2 Getting Started
2 Sept. 5 & 7 58 - 115 Sept. 15 3 Growth of Functions, 4 Divide-and-Conquer
3 Sept. 12 & 14 116 - 164 Sept. 22 4, 5 Probabilistic Analysis and Randomized Algorithms
4 Sept. 19 & 21 165 - 225 Sept. 29 5, 9 Medians and Order Statistics, 11 Hash Tables
5 Sept. 26 & 28 226 - 271 Oct. 6 11.3 Hash Functions, 14 Augmenting Data Structures
6 Oct. 3 & 5 272 - 327 Oct. 13 14, 15 Dynamic Programming
7 Oct. 10 & 12 328 - 382 Oct. 27 15.4 Longest common subsequence, 15.5 Optimal binary search trees 16.1 An activity selection problem
8 Oct. 24 & 26 383 - 429 n/a 16 Greedy Algorithms, 17 Amortized Analysis
9 Oct. 31 & Nov. 2 430 - 489 Nov. 10 17, 19 Fibonacci Heaps
10 Nov. 7 & 9 490 - 535 Nov. 17 23 Minimum Spanning Trees, 24 Single-Source Shortest Paths
11 Nov. 14 & 16 536 - 582 Nov. 24 24, 25 All-Pairs Shortest Paths
12 Nov. 21 & 23 583 - 636 Dec. 1 31 Number-Theoretic Algorithms, 35 Approximation Algorithms
13 Nov. 28 & 30 637 - 659 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
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
23 Minimum Spanning Trees
24 Single-Source Shortest Paths
25 All-Pairs Shortest Paths
VII Selected Topics
28 Matrix Operations
29 Linear Programming
31 Number-Theoretic Algorithms
35 Approximation Algorithms

- Links


Nov. 28, 2016 http://www.cs.tut.fi/~elomaa/