02110 Algorithms and Data Structures II


General Info | Mandatory Exercises | Weekplan | Programming Competition | Exam sets | FAQ | Fall 15 | Fall 16 | Fall 17

General Info

Teacher Associate Professor Inge Li Gørtz, office 018, building 322, Email: inge@dtu.dk. Office hours: Monday 12.15-13 and Friday 12.15-12.45.

When Thursday 8-12. The course runs in the DTU fall semester.

Exercise class Thursday 8-10 in building 450, room 006a, 006b, 106a. English speaking students should go to room 106a.

Lectures Thursday 10-12 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 978-0-262-53305-8 (CLRS)

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 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: 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 hand-in 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, 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.

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: Red-Black trees and 2-3-4 trees 1x1 · 4x1 · full Warmup
Balanced Search Trees
  • Algorithms in Java by Sedgewick, page 572--585 (on Campusnet)
  • (Supplementary reading: CLRS chapter 13)
  • Survival guide
Data Structures II: Amortized Analysis + splay trees. 1x1 · 4x1 · full Amortised Analysis
  • Section 15 + 16.5-16.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
  • KT 6.1, 6.2, 6.3
Dynamic programming II: Sequence alignment and shortest paths 1x1 · 4x1 DP2
  • KT 6.6, 6.8.
Sequence Alignment
Network Flow I: Max-cut min-flow theorem, augmenting paths, Ford-Fulkerson 1x1 · 4x1 · full Flow1
  • KT 7.1, 7.2
  • (CLRS 26.1, 26.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
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
  • KT 5.4, 13.7
Introduction to NP-completenes 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:

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.