02110 Algorithms and Data Structures II |
Teacher Professor Inge Li Gørtz, office 011, building 322, Email: inge@dtu.dk.Office hours: Friday 12.15-12.45 on Zoom, Meeting ID: 681 9419 7720.
When Thursday 8-12.
The course runs in the DTU fall semester.
Structure The class is structured as follows. For week x:
Where
The exercise class from 8-10 is in building 116, rooms
H015, H018, H011, H012, and H010.
English speaking students should go to room H018.
Lectures will be in building 116, aud. 81.
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
Programming Exercises We will use CSES for implementation exercises. CSES automatically evaulates your submitted solutions for both correctness and running time.
The weekplan is preliminary. It will be updated during the course.
Week | Topics | Slides | Weekplan | Material | Demos |
---|---|---|---|---|---|
Divide-and-Conquer: Recurrence relations, Mergesort (recap), counting inversions. | 1x1 · 4x1 | DC |
|
||
Dynamic programming I: Introduction, weighted interval scheduling | 1x1 · 4x1· full | DP1 |
|
||
Dynamic programming II: Knapsack and Sequence alignment | 1x1 · 4x1 | DP2 |
| Sequence Alignment ·Recursive subsetsum ·Iterative subsetsum | Network Flow I: Max-cut min-flow theorem, augmenting paths, Ford-Fulkerson | 1x1 · 4x1 · full | Flow1 |
| Ford Fulkerson and min cut |
Network Flow II: scaling, Edmonds-Karp, applications, maximum bipartite matching, disjoint paths |
1x1 · 4x1 · full | Flow2 |
| ||
Data Structures I: Partial Sums and Dynamic Arrays | 1x1 · 4x1 | Partial Sums and Dynamic Arrays |
| ||
Data Structures II: Amortized Analysis | 1x1 · 4x1 · full | Amortised Analysis |
|
||
Randomized Algorithms I: Contention resolution and minimum cut. |
1x1 · 4x1 | Contention resolution and minimum cut |
| ||
Randomized algorithms II: selection, quicksort |
1x1 · 4x1 | Randomized Algorithms II |
| ||
Randomized Data Structures: Hashing |
1x1 · 4x1 | Randomized Data Structures |
| ||
Introduction to NP-completenes | 1x1 · 4x1 | NP |
| ||
Strings I: String matching | 1x1 · 4x1 | Strings |
|
Automata
matching and
construction KMP matching and construction |
|
Questions, repetition |
Collaboration policy The mandatory exercises are subject to the following collaboration policy. The mandatory exercises are individual. It is not allowed to collaborate on the exercises, except for discussing the text of the exercise with teachers and fellow students enrolled on the course in the same semester. Under no circumstances is it allowed to exchange, hand-over or in any other way communicate solutions or part of solutions to the exercises. It is not allowed to use solution from previous years, solutions from similar courses, or solutions found on the internet or elsewhere. It is not allowed to search for solutions or parts of solutions on the internet or to use solutions obtained with the help of AI tools.
How should I write my solutions? 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.