02110 Algorithms and Data Structures II


General Info | Mandatory Exercises | Weekplan | Programming Competition | Exam sets | FAQ

General Info

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.

Weekplan

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
  • KT 4.1, 4.2, 4.3
  • (KT 5.1, 5.2, 5.3 in the American edition)
Dynamic programming I: Introduction, weighted interval scheduling 1x1 · 4x1· full DP1
  • KT 6.1, 6.2
Dynamic programming II: Knapsack and Sequence alignment 1x1 · 4x1 DP2
  • KT 6.4, 6.6
Sequence Alignment ·Recursive subsetsum ·Iterative subsetsum
Network Flow I: Max-cut min-flow theorem, augmenting paths, Ford-Fulkerson 1x1 · 4x1 · full Flow1
  • KT 7.1, 7.2
Ford Fulkerson and min cut
Network Flow II: scaling, Edmonds-Karp, applications, maximum bipartite matching, disjoint paths
1x1 · 4x1 · full Flow2
  • KT 7.3, 7.5, 7.6
  • Extra: KT 7.7, 7.8, 7.9, 7.10, 7.11
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
  • Chapter 17 in Algorithms from Cormen, Leiserson, Rivest, Stein (can be found on DTU Learn).
Randomized Algorithms I: Contention resolution and minimum cut.
1x1 · 4x1 Contention resolution and minimum cut
  • KT 12, 12.1, 12.2, 12.12 (In the American edition it is chapter 13)
Randomized algorithms II: selection, quicksort
1x1 · 4x1 Randomized Algorithms II
  • KT 12.3, 12.5
Randomized Data Structures: Hashing
1x1 · 4x1
Introduction to NP-completenes 1x1 · 4x1 NP
  • KT 8.0, 8.1
  • KT 8.3 (except the proof of 8.10)
  • KT 8.4 (only introduction and the subsection A General Strategy for Proving New Problems NP-Complete)
Strings I: String matching 1x1 · 4x1 Strings
  • CLRS 32.0, 32.3, 32.4 (on DTU Learn)
Automata matching and construction
KMP matching and construction
Questions, repetition

Mandatory assignments

The course has a mandatory exercise that counts in the final grade. This is a multiple choice test that will be available on DTU Learn approximately a week before the deadline. The deadline is November 20. The deadline for handing in the assignment must be respected.

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.

Old Exam Sets

Here is the exam set from some of the previous years: ExamE21 ( solution (very brief)), ExamE20 ( solution (brief)), ExamE19 ( solution (very brief)), ExamE18, ExamE17 ( solution (very brief)), ExamE16, ExamE15, ExamE14 and a solution to E14.
And an example exam: ExampleExam.

Solutions to selected exercises

Here are solutions to a couple of exam like exercises, such that you can see how a well written solution could be: Example solutions.

Frequently Asked Questions

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.