02110 Algorithms and Data Structures II 
Teacher Professor Inge Li Gørtz, office 011, building 322, Email: inge@dtu.dk.Office hours: Friday 12.0012.45 on Zoom, Meeting ID: 681 9419 7720.
When Thursday 812.
The course runs in the DTU fall semester.
Structure The class is structured as follows:
Where
The exercise class from 810 is in building 116, room
012, 015, 016, 018, 019.
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
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.
The weekplan is preliminary. It will be updated during the course.
Week  Topics  Slides  Weekplan  Material  Demos 

Warmup  Warmup  
DivideandConquer: Recurrence relations, Mergesort (recap), integer multiplication  1x1 · 4x1  DC 


Dynamic programming I: Introduction, weighted interval scheduling, Knapsack  1x1 · 4x1· full  DP1 


Dynamic programming II: Sequence alignment and shortest paths  1x1 · 4x1  DP2 
 Sequence Alignment  
Network Flow I: Maxcut minflow theorem, augmenting paths, FordFulkerson  1x1 · 4x1 · full  Flow1 
 Ford Fulkerson and min cut  
Network Flow II: scaling, EdmondsKarp, applications, maximum bipartite matching, disjoint paths 
1x1 · 4x1 · full  Flow2 
 
Data Structures I: RedBlack trees and 234 trees  1x1 · 4x1  Balanced Search Trees 


Data Structures II: Amortized Analysis + splay trees.  1x1 · 4x1 · full  Amortised Analysis 

Splay
0211 Trees Splay Trees Deletions 

Data Structures III: Partial Sums and Dynamic Arrays  1x1 · 4x1  Partial Sums and Dynamic Arrays 
 
String matching  1x1 · 4x1  Strings 
 Automata
matching and
construction KMP matching and construction 

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 
 
Introduction to NPcompletenes  1x1 · 4x1  NP 
 
Questions, repetition, prize for programming competition 
Written assignments These are algorithmic challenges that must be answered in writing. These must be handed through DTU Learn. Each written exercise is scored depending on the quality of your solution and your writing.
Implementation assignments These are programming challenges that must be implemented and handed in through CodeJudge for automatic evaluation and scoring.
The deadline for handing in the assignments 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, handover 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.
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.