General Info
Teacher
Professor Inge Li Gørtz, office 011, building 322, Email: inge@dtu.dk.
When Thursday 8-12.
The course runs in the DTU fall semester.
Structure
The class is structured as follows:
- 8.00-10.00 Group work. Time to work on the exercises you couldn't solve at home. The TAs will be there to help you.
- 10.00-12.00 Lecture
Where
The exercise class from 8-10 is in building 358, room
060a, 039, 040, 065.
Lectures will be in building 358, room 060a.
OBS!! (Covid-19) Due to Covid-19 restrictions,
you will be divided into groups. The group you are in determines which
room you have exercise class in and which weeks you can attend the
lecture in the lecture room. See more on DTU Learn.
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
- Basic algorithm analysis, asymptotic notation.
- Data structures: stacks, queues, linked lists, trees, heaps, priority queues, hash tables, union-find, binary search trees.
- Searching and sorting: binary search, heap sort, insertion sort, merge-sort.
- 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
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.
- You may work in groups consisting of at most two
students.
- For the written exercises collaboration is limited to
discussion of ideas, and you
should write up the solutions entirely on your own. Your collaborator must be listed in your solution.
- In weeks where there is both a written and a programming
exercise, the group you are in has to be the same for both exercises.
- It is not allowed to collaborate with people not in your group, 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.
Programming Competition
The programming
competition is now on.
There will be a prize for the best three
teams. The deadline is November 29th at 20.00. The description can
be found at CodeJudge.
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 |
|
|
|
|
|
Dynamic programming I: Introduction, weighted interval scheduling, segmented least squares |
1x1 · 4x1· full |
DP1
|
X |
X |
|
|
|
Dynamic programming II: Sequence alignment and shortest paths |
1x1 · 4x1 |
DP2 |
X |
|
| Sequence Alignment |
|
Network Flow I: Max-cut min-flow theorem, augmenting paths, Ford-Fulkerson |
1x1 · 4x1 · full |
Flow1 |
X |
X |
| 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 |
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 |
|
- 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 |
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 |
|
| |
|
Randomized algorithms II: selection, quicksort |
1x1 · 4x1 |
Randomized Algorithms II |
|
X |
| |
|
Questions, repetition, prize for programming competition |
|
|
|
|
| |
Old Exam Sets
Here is the exam set from some of the previous years:
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 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.