 |
Algorithms and Data Structures, Fall 2011Taught by Rasmus Pagh. This page contains the publicly available materials for the course. |
We will be using the Algorithms, 4th edition, textbook by Sedgewick and Wayne (SW). Literature in parenthesis is not in the curriculum (and should not contain essential new things), but we recommend that you review it since this is assumed knowledge for the rest of the course.
| Date | Topic | Literature | Exercises |
| 29/8 | Introduction (slides) | (SW 1.1), SW 1.4 | handout, SW 1.4.4, 1.4.5, 1.4.6, 1.4.8, 1.4.10, 1.4.12, 1.4.15, 1.4.24 (hints) |
| 5/9 | Stacks and queues (slides, code) | (SW 1.2), SW 1.3 | handout, data, SW 1.3.2, 1.3.5, 1.3.6, 1.3.19, 1.3.20, 1.3.27, 1.3.28, 1.3.32, 1.3.47 |
| 12/9 | Recursion and sorting (slides, code) | SW 2.1, 2.2, 2.3 | handout, SW 2.1.6, 2.1.7, 2.1.15, 2.2.4, 2.3.5, 2.3.8, 2.3.15 |
| 19/9 | Trees and search trees (slides) | SW 3.1, 3.2 | work on hand-in and past exercises |
| 26/9 | No activities | ||
| 3/10 | Balanced trees; hashing (slides, code) | SW 3.3, 3.4, PR04 until sec. 2.1 | handout, SW 3.2.6, 3.3.1, 3.3.4, 3.3.9, 3.3.16, 3.4.4, 3.4.10, 3.4.13. |
| 10/10 | Case studies on sorting and searching (slides) | SW 2.5, 3.5 | work on hand-in and past exercises |
| 17/10 | Autumn break | ||
| 24/10 | Priority queues (slides) | SW 2.4, BFJ02 sec. 1.0, 2 | handout, SW 2.4.2, 2.4.3, 2.4.4, 2.4.9, 2.4.12, 2.4.13, 2.4.16 |
| 31/10 | Basic graph search (slides) | SW 4.1, 4.2 until p. 583 | handout, SW 4.1.1, 4.1.16, 4.1.23, 4.2.22, 4.2.30 |
| 7/11 | Shortest paths (slides) | SW 4.4 | slash maze, last problem from this old exam, SW 4.4.1, 4.4.14, 4.4.15, 4.4.23, 4.4.25, 4.4.28 |
| 14/11 | Case studies on graphs (slides) | multiple-choice part of June 2010 exam (page 5-6); work on hand-in | |
| 21/11 | Radix sorting and digital search (slides, code) | SW 5.1, 5.2 | January 2011 exam |
| 28/11 | Trial exam | ||
| 5/12 | Guest lecture by Jesper Larsson: Data compression (slides) | SW 5.5 |