General Info
Teacher
Associate Professor Inge Li Gørtz, office 018, building 322, Email: inge@dtu.dk. Office hours: Monday 12.1513 and Friday 12.1512.45.
When Thursday 812.
The course runs in the DTU fall semester.
Exercise class Thursday 810 in building 450, room 006a, 006b, 106a. English speaking students should go to room 106a.
Lectures Thursday 1012 in Building 421, auditorium 72.
Textbook
"Algorithm Design" by Kleinberg and Tardos. (KT)
Supplementary: "Introduction to Algorithms", Cormen, Leierson, Rivest and Stein. 3rd edition. ISBN 9780262533058 (CLRS)
Prerequisites The course builds on 02105 Algorithms and Data Structures I. You are expected to know the curriculum for 02105, which includes
 Basic algorithm analysis, asymptotic notation.
 Data structures: stacks, queues, linked lists, trees, heaps, priority queues, hash tables, unionfind, binary search trees.
 Searching and sorting: binary search, heap sort, insertion sort, mergesort.
 Graph algorithms: single source shortest paths (Dijkstra and SSSP in DAGs), Minimum spanning trees, topological sorting, Breadth first search, Depth first search, representation of graphs.
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 and a java template can be found on CodeJudge.
Mandatory assignments
In order to be allowed to participate in the written exam it is a requirement that you:
 get at least 40 point in the mandatory assignments from the week plans (more info below).
 implement (and pass the tests of) two of the implementation exercises on CodeJudge.
Each week from week 1 to 10 you will be asked to do written exercises
and hand them in through DTU Learn. These exercises will be corrected by the teaching assistants. It is a
requirement for participation in the exam that you get at least 40 points in the exercises. Each weekly exercise can give up to 20 points. 20 points is given for a perfect solution, and you can get anything between 0 and 20 points for a handin depending on the quality of your solution and your writing. The exercises do not count in the final grade for the course, but you have to get at least 40 points in order to be allowed to participate in the exam.
The deadline for handing in the mandatory assignment on weekplan x is Sunday in week x+1 at 20:00 in
DTU Learn.
The deadline for handing in the home work must be respected.
The mandatory exercise to be handed in in week 1 is on the weekplan "Warmup".
The deadline for passing the implementation exercises is Thursday in week 11.
Collaboration policy All mandatory exercises are subject to the following collaboration policy. The 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.
Programming Competition
There will be a prize for the best three
teams. Participation in the programming competition counts as
a
mandatory CodeJudge exercise if you pass a certain set of the test cases.
Weekplan
The weekplan is preliminary. It will be updated during the course.
Week 
Topics 
Slides 
Weekplan 
Material 
Demos 

Data Structures I: RedBlack trees and 234 trees 
1x1 · 4x1 · full 
Warmup
Balanced Search Trees 
 Algorithms in Java by Sedgewick, page 572585 (on Campusnet)
 (Supplementary reading: CLRS chapter 13)
 Survival guide



Data Structures II: Amortized Analysis + splay trees. 
1x1 · 4x1 · full 
Amortised Analysis 
 Section 15 + 16.516.6 in notes by Jeff Erickson (can also be found on CampusNet)
 (CLRS chapter 17)

Splay
0211 Trees
Splay Trees
Deletions


Dynamic programming I: Introduction, weighted interval scheduling, segmented least squares 
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 
 KT 7.1, 7.2
 (CLRS 26.1, 26.2)
 Ford
Fulkerson and min cut 

Network Flow II: scaling, EdmondsKarp, applications, maximum bipartite matching, disjoint paths 
1x1 · 4x1 · full 
Flow2 
 

Network Flow III: Circulations and applications
Programming Competition 


 KT 7.7, 7.8, 7.9, 7.10, 7.11, 7.12



Strings I: String matching 
1x1 · 4x1 

 CLRS 32.0, 32.3, 32.4 (on Campusnet)
 Automata
matching and
construction
KMP matching and
construction 

Strings II: Suffix trees 
1x1 · 4x1 

 Notes on Tries and Suffix Trees.
 Alternative reading: Data Structures & Algorithms in Java by Goodrich and
Tamassia, section 12.3 (on CampusNet)
 trie search (old version)
and
trie construction (old version) 

Randomized Algorithms: Introduction, quicksort, selection. 
1x1 · 4x1 

 KT 13.1, 13.2, 13.3, 13.5.
 notes by Paul Fischer on randomized algorithms section 1, 2 (except 2.4 and 2.5)
 

Computational Geometry: Closest Pair of Points in the Plane 
1x1 · 4x1 

 

Introduction to NPcompletenes 
1x1 · 4x1 

 KT 8.0, 8.1
 Notes by Paul Fischer Appendix C
 

Questions, repetition, prize for programming competition 
1x1 · 4x1 

 
Old Exam Sets
Here is the exam set from the two previous years:
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 mandatory
exercises?Here is a few tips:
 Write things directly: Cut to the chase and avoid anything that is not essential. Test your own writing by answering the following question: “Is this the shortest, clearest, and most direct exposition of my ideas/analysis/etc.?”
 Add structure: Don’t mix up description and analysis unless you know exactly what you are doing. For a data structure explain following things separately: The contents of the data structure, how to build it, how to query/update it, correctness, analysis of space, analysis of query/update time, and analysis of preprocessing time. For an algorithm explain separately what it does, correctness, analysis of time complexity, and analysis of space complexity.
 Be concise: Convoluted explanations, excessively long sentences, fancy wording, etc. have no in place scientific writing. Do not repeat the problem statement.
 Try to avoid pseudocode: Generally, aim for human readable
description of algorithms that can easily and unambiguously be
translated into code.
The only exception for this is dynamic programming algorithms, where
pseudo code is often the best choice.
 Examples for support: Use figures and examples to illustrate key points of your algorithms and data structures.
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.
 Let us know well in advance: Identifying an interesting problem in algorithms that matches your interest can take time. With enough time to go over the related litterature and study up on relevant topics your project will likely be more succesful. It may also be a good idea to do an initial “warm up” project before a large thesis to test ideas or survey an area.
 Join the community: It is very good idea to enter the local algorithms community at DTU and the Copenhagen area to get a feel for what kind of stuff you could work on for your thesis and what thesis work algorithms is about. Talk to other students doing thesis work in algorithms. Go to algorithms talks and thesis defenses in algorithms.
 Collaborate: We strongly encourage you to do your thesis in pairs. We think that having a collaborator to discuss with greatly helps in many aspects of thesis work in algorithms. Our experience confirms this.
 No strings attached. Choosing a topic for your thesis is important. You are welcome to discuss master thesis topics with us without pressure to actually write your thesis in algorithms. We encourage you to carefully select your topic.