MAT-72006 Advanced Algorithms and Data Structures, 7 cr

Prof. Tapio Elomaa

Fall 2015, periods I ja II

Lectures:
Exception:
Weekly exercises: M.Sc. Juho Lauri and M.Sc. Teemu Heinimäki Mon 10-12 TC315 TB215
Course exam: Fri Dec. 18, 2015

- News

- General Information

-Programming Assignment

Settlers of Catan

You are free to use any programming language as far as it is easy to obtain a suitable testing environment (without monetary expences). Using C++, Lua, or Python is suggested.

The deadline for the submissions is October 15, 2015 (inclusive). If it seems that you cannot make it, you can ask more time _beforehand_, but being late costs you points.

You should submit your solution to the e-mail address a@b, in which "a" is replaced by "teemu.heinimaki" and "b" is replaced by "tut.fi". The subject of the mail should be "AADS programming assignment X", in which "X" should be replaced by your student number.

As an attachment there should be a .zip packet, named X.zip, in which "X" should again be replaced by your student number. The packet should contain (1) the source codes and (2) a short pdf document. The document should briefly explain how your solution works and give the instructions of using the program (for instance, the required command line input format). If your solution contains especially clever tricks, it is a good idea to mention them also within the documentation.

Your work will be evaluated based on the ability to follow the instructions, correctness of the solution, efficiency, algorithmic inventions, documentation, and the coding style. (You are not required to adhere to any specific coding guidelines, but it is expected, for instance, that you comment your code adequately.) The maximum number of additional points you can gain for the course grading is 3.

If there are any questions, feel free to ask (using the address mentioned).

- Lectures

The lectures are based on the book

WeekDatesSlidesExercises Chapters in the Book
1 Aug. 25 & 27 1 - 71 n/a 2 Getting Started
2 Sept. 1 & 3 72 - 127 Sept. 7 3 Growth of Functions, 4 Divide-and-Conquer
3 Sept. 8 & 10 128 - 180 Sept. 14 4, 5 Probabilistic Analysis and Randomized Algorithms
4 Sept. 15 & 17 181 - 239 Sept. 21 5, 9 Medians and Order Statistics, 11 Hash Tables
5 Sept. 22 & 24 240 - 296 Sept. 28 11.3 Hash Functions, 14 Augmenting Data Structures
6 Sept. 29 & Oct. 1 297 - 352 Oct. 5 14, 15 Dynamic Programming
7 Oct. 6 & 8 353 - 392 Oct. 19 15.4 Longest common subsequence, 15.5 Optimal binary search trees
8 Oct. 20 & 22 393 - 422 Oct. 26 Guest Lecture by Timo Aho, 16 Greedy Algorithms
9 Oct. 27 & 29 423 - 478 Nov. 2 17 Amortized Analysis
10 Nov. 3 & 5 479 - 542 Nov. 9 18 B-Trees, 19 Fibonacci Heaps
11 Nov. 10 & 12 543 - 580 Nov. 16 23 Minimum Spanning Trees
12 Nov. 17 & 19 581 - 633 Nov. 23 24 Single-Source Shortest Paths, 31 Number-Theoretic Algorithms
13 Nov. 24 & 26 634 - 678 Nov. 30 31, 35 Approximation Algorithms
14 Dec. 1 679 - 690 35

- 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
VII Selected Topics
28 Matrix Operations
29 Linear Programming
31 Number-Theoretic Algorithms
35 Approximation Algorithms

- Links


Dec. 1, 2015 http://www.cs.tut.fi/~elomaa/