02110 Algorithms and Data Structures II |
Teacher Associate Professor Inge Li Gørtz, office 018, building 322, Email: inge@dtu.dk. Office hours: Monday 12.15-13 and Friday 12.15-13.00.
When Thursday 8-12.
The course runs in the DTU fall semester.
Structure The class is structured as follows:
Where
The exercise class from 8-10 is in building 358, room
060a and 042. English speaking students should go to room 042.
Lectures will be in building 358, room 060a.
Textbook
"Algorithm Design" by Kleinberg and Tardos. (KT)
Prerequisites The course builds on 02105 Algorithms and Data Structures I. You are expected to know the curriculum for 02105, which includes
CodeJudge Exercises marked with [CJ] are implementation exercises and can be tested in CodeJudge (CodeJudge). For each of these exercises, a detailed specification of the input/output can be found on CodeJudge.
Written assignments These are algorithmic challenges that must be answered in writing. These must be handed through DTU Learn for correction by the TA's. Each written exercise is scored depending on the quality of your solution and your writing. It is a requirement for participation in the exam that you score at least 50 points in total in these exercises.
Implementation assignments These are programming challenges that must be implemented and handed in through CodeJudge for automatic evaluation and scoring. It is a requirement for participation in the exam that you score at least 50 points in total in these exercises.
The exercises do not count in the final grade for the course. There are 10 written assignments and 5 implentation assignments. Each can give up to 20 points.Collaboration policy All mandatory exercises are subject to the following collaboration policy.
The weekplan is preliminary. It will be updated during the course.
Week | Topics | Slides | Weekplan | Deadline Mandatory Written |
Deadline Mandatory Programming |
Material | Demos |
---|---|---|---|---|---|---|---|
Warmup | Warmup | ||||||
Divide-and-Conquer: Recurrence relations, Mergesort (recap), integer multiplication | 1x1 · 4x1 | DC |
|
||||
Dynamic programming I: Introduction, weighted interval scheduling, segmented least squares | 1x1 · 4x1· full | DP1 | X | X |
|
||
Dynamic programming II: Sequence alignment and shortest paths | 1x1 · 4x1 | DP2 | X |
| Sequence Alignment | Network Flow I: Max-cut min-flow theorem, augmenting paths, Ford-Fulkerson | 1x1 · 4x1 · full | Flow1 | X | X |
| Ford Fulkerson and min cut |
Network Flow II: scaling, Edmonds-Karp, applications, maximum bipartite matching, disjoint paths |
1x1 · 4x1 · full | Flow2 | X |
| |||
Introduction to NP-completenes | 1x1 · 4x1 | NP | X | X |
| ||
Data Structures I: Red-Black trees and 2-3-4 trees | 1x1 · 4x1 · full | Balanced Search Trees | X |
|
|||
Data Structures II: Partial Sums and Dynamic Arrays | 1x1 · 4x1 | Data Structures II | X |
| |||
Data Structures III: Amortized Analysis + splay trees. | 1x1 · 4x1 · full | Amortised Analysis | X | X |
|
Splay
0211 Trees Splay Trees Deletions |
|
String matching | 1x1 · 4x1 | Strings | X |
| Automata
matching and
construction KMP matching and construction |
||
Randomized Algorithms I: Contention resolution, Minimum cut. |
1x1 · 4x1 | Randomized Algorithms I | X |
| |||
Randomized algorithms II: selection, quicksort |
1x1 · 4x1 | Randomized Algorithms II | X |
| |||
Questions, repetition, prize for programming competition |
How should I write my mandatory exercises? Here is a few tips:
Can I write my assignments in Danish? Ja. Du er meget velkommen til at aflevere på dansk. Det samme gælder til eksamen.
What do I do if I want to do a MSc/BSc thesis or project in Algorithms? Great! Algorithms is an excellent topic to work on :-) and Algorithms for Massive Data Sets is designed to prepare you to write a strong thesis. Some basic tips and points.