02110 Algorithms and Data Structures II

Weekplan

The weekplan is preliminary. It will be updated during the course.

Topics	Slides	Weekplan	Material	Demos
Divide-and-Conquer: Recurrence relations, Mergesort (recap), integer multiplication	1x1 · 4x1· full	DC	KT 4.1, 4.2, 4.5 (KT 5.1, 5.2, 5.5 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: Implementation of flow		Flow2	No reading material this week
Network Flow III: scaling, Edmonds-Karp, applications, maximum bipartite matching, disjoint paths	1x1 · 4x1 · full	Flow3	KT 7.3, 7.5, 7.6 Extra: KT 7.7, 7.8, 7.9, 7.10, 7.11
Data Structures I: Amortized Analysis	1x1 · 4x1 · full	Amortised Analysis	Chapter 17 in Algorithms from Cormen, Leiserson, Rivest, Stein (can be found on DTU Learn).
Data Structures II: Partial Sums and Dynamic Arrays	1x1 · 4x1	Partial Sums and Dynamic Arrays	Notes on Partial Sums and Dynamic Arrays, chapter 1 (minus section 1.4) and chapter 2. Extra: A New Data Structure for Cumulative Frequency Tables, P.M. Fenwick, Softw. Pract. Exp. 1994. Extra: Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences, M.T. Goodrich and J.G. Kloss, WADS 1999
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 and Hashing	1x1 · 4x1	Randomized Algorithms II	KT 12.3 and 12.6 Ekstra: High Speed Hashing for Integers and Strings, Mikkel Thorup
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 mandatory exercises that counts in the final grade. 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. 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, 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.

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:

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.