02110 Algorithms and Data Structures II


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

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-13.00.

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

Structure The class is structured as follows:

Where The exercise class from 8-10 is in building 358, room 060a and 042. English speaking students should go to room 042.
Lectures will be in building 358, room 060a.

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.

Mandatory assignments

The course has mandatory exercises that must be passed inorder to attend the final exam. The mandatory exercises consist of written and implementation exercises:

Written assignments These are algorithmic challenges that must be answered in writing. These must be handed through DTU Learn for correction by the TA's. Each written exercise is scored depending on the quality of your solution and your writing. It is a requirement for participation in the exam that you score at least 50 points in total in these exercises.

Implementation assignments These are programming challenges that must be implemented and handed in through CodeJudge for automatic evaluation and scoring. It is a requirement for participation in the exam that you score at least 50 points in total in these exercises.

The exercises do not count in the final grade for the course. There are 10 written assignments and 5 implentation assignments. Each can give up to 20 points.

The deadline for handing in the home work must be respected.

Collaboration policy All mandatory exercises are subject to the following collaboration policy.

Programming Competition

We will have a programming competition with a prize for the best three teams. More info follows later.

Weekplan

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

Week Topics Slides Weekplan Deadline
Mandatory
Written
Deadline
Mandatory
Programming
Material Demos
Warmup Warmup
Divide-and-Conquer: Recurrence relations, Mergesort (recap), integer multiplication 1x1 · 4x1 DC
  • KT 5.1, 5.2, 5.5
Dynamic programming I: Introduction, weighted interval scheduling, segmented least squares 1x1 · 4x1· full DP1 X X
  • KT 6.1, 6.2, 6.3
Dynamic programming II: Sequence alignment and shortest paths 1x1 · 4x1 DP2 X
  • KT 6.6, 6.8.
Sequence Alignment
Network Flow I: Max-cut min-flow theorem, augmenting paths, Ford-Fulkerson 1x1 · 4x1 · full Flow1 X X
  • 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 X
  • KT 7.3, 7.5, 7.6
  • KT 7.7, 7.8, 7.9, 7.10, 7.11
Introduction to NP-completenes 1x1 · 4x1 NP X X
  • 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)
Data Structures I: Red-Black trees and 2-3-4 trees 1x1 · 4x1 · full Balanced Search Trees X
  • Algorithms in Java by Sedgewick, page 572--585 (on Campusnet)
  • (Supplementary reading: CLRS chapter 13)
Data Structures II: Partial Sums and Dynamic Arrays 1x1 · 4x1 Data Structures II X
Data Structures III: Amortized Analysis + splay trees. 1x1 · 4x1 · full Amortised Analysis X X
  • Section 15 + 16.5-16.6 in notes by Jeff Erickson (can also be found on CampusNet)
  • Chapter 17 in Algorithms from Cormen, Leiserson, Rivest, Stein (can be found on Campusnet).
Splay 0211 Trees
Splay Trees Deletions
String matching 1x1 · 4x1 Strings X
  • CLRS 32.0, 32.3, 32.4 (on Campusnet)
Automata matching and construction
KMP matching and construction
Randomized Algorithms I: Contention resolution, Minimum cut.
1x1 · 4x1 Randomized Algorithms I X
  • KT 13, 13.1, 13.2, 13.12
Randomized algorithms II: selection, quicksort
1x1 · 4x1 Randomized Algorithms II X
  • KT 13.3, 13.5
Questions, repetition, prize for programming competition

Old Exam Sets

Here is the exam set from some of the 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.