02110 Algorithms and Data Structures II |
General Info
| Mandatory Exercises
| Weekplan
| Programming Competition
| Exam sets
| FAQ
General Info
Teacher
Associate Professor Inge Li Gørtz, office 018, building 322, Email: inge@dtu.dk. Office hours: Tuesday 12.15-13.
When Thursday 8-12.
The course runs in the DTU fall semester.
Exercise class Thursday 8-10.30 in building 210.
Class |
Room |
Teaching assistant |
1 |
building 210, room 002 |
Frederik Rye Skjoldjensen (fskj@dtu.dk) |
2 (English) |
building 210, room 008 |
Christian Gießen (cgie@dtu.dk) |
3 |
building 210, room 112 |
Mikko Berggren Ettienne (miet@dtu.dk) |
4 |
building 210, room 118 |
Lasse Kokholm (s134836@student.dtu.dk) |
The exercise classes will work as follows:
-
8.00-9.00 Group work. Time to work on the exercises you couldn't solve at home. The TAs will be there to help you.
- 9.00-10.30 Walk-through of solutions to the exercises. Together with the TA you will go through the solutions to the exercises in class. You are expected to have already solved the exercises and you should be prepared to present your solutions to the rest of the class.
Lectures Thursday 10.30-12 in Building 208, auditorium 51.
Textbook
CLRS: "Introduction to Algorithms", Cormen, Leierson, Rivest and Stein. 3rd edition. ISBN 978-0-262-53305-8
Piazza The course uses Piazza as onlineforum for discussion of material.
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 (https://dtu.codejudge.net/02110-e15). For each of these exercises, a detailed specification of the input/output and a java template can be found on CodeJudge.
Mandatory assignments
Each week from week 1 to 9 you will be asked to do written exercises and hand them in during the group work. These exercises will be corrected by the teaching assistants. It is a requirement for participation in the exam that you get 3 of the 9 exercises approved. The exercises do not count in the final grade for the course, but you have to pass at least 3 of them in order to be allowed to participate in the exam.
The deadline for handing in the mandatory assignment on weekplan x is Thursday in week x+1 at 9:00.
The deadline for handing in the home work must be respected.
You are welcome to hand in more than 3 - the TAs will correct all the home work you hand in.
Programming Competition
The programming
competition is now on. There will be a prize for the best three
teams. Participation in the programming competition counts as a
mandatory exercise if you pass a certain set of the test cases.The
deadline is November 25th 23.59. The
rules and the description of the programming competition is here.
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 |
Week 1 |
- Algorithms in Java by Sedgewick, page 572--585 (on Campusnet)
- CLRS chapter 13
- Survival guide
| |
|
Data Structures II: Amortized Analysis + splay trees. |
1x1 · 4x1 |
Week 2 |
- CLRS 17
- Section 16.5-16.6 in notes by Jeff Erickson (can also be found on CampusNet)
|
Splay
Trees
Splay Trees
Deletions
|
|
Dynamic programming I: Rod cutting and longest common subsequence |
1x1 · 4x1 |
Week 3 |
- CLRS 15.0-15.1, (15.3), 15.4
| |
|
Dynamic programming II: Sequence alignment and All Pairs Shortest Paths |
1x1 · 4x1 |
Week 4 |
- CLRS 25.0, 25.1
- Algorithm Design by Kleinberg and Tardos, section 6.6 (on CampusNet).
| Sequence Alignment |
|
Network Flow I: Max-cut min-flow theorem, augmenting paths, Ford-Fulkerson |
1x1 · 4x1 |
Week 5 |
| Ford
Fulkerson and min cut |
|
Network Flow II: Edmonds-Karp, maximum bipartite matching |
1x1 · 4x1 |
Week 6 |
| |
|
Randomized Algorithms: Introduction, quicksort, selection. |
1x1 · 4x1 |
Week 7 |
- CLRS chapter 7, 9.2
- notes by Paul Fischer on randomized algorithms section 1, 2 (except 2.4 and 2.5)
| |
|
Strings I: String matching |
1x1 · 4x1 |
Week 8 |
| Automata
matching and
construction
KMP matching and
construction |
|
Strings II: Suffix trees |
1x1 · 4x1 |
Week 9 |
- Data Structures & Algorithms in Java by Goodrich and
Tamassia, section 12.3 (on CampusNet)
| trie search and
trie construction |
|
Computational Geometry I: Convex hull |
1x1 · 4x1 |
Week 10 |
- CLRS 33.0, 33.1, 33.3
- Alternative reading: notes by Jeff Erickson
| Graham's scan and Jarvis's march |
|
Computational Geometry II: Closest pair of points |
1x1 · 4x1 |
Week 11 |
- CLRS 33.4
- Algorithm Design by Kleinberg and Tardos, section 13.7 (on CampusNet)
| Randomized algorithm |
|
Introduction to NP-completenes |
1x1 · 4x1 |
Week 12 |
- Notes by Paul Fischer Appendix C
- CLRS 34.0-34.2 + 34.3 until page 1069 (page 1048-1069)
| |
|
Questions, repetition, prize for programming competition |
1x1 · 4x1 |
Week 13 |
| |
Old Exam Sets
Here is the exam set from last year: ExamF14 and a solution.
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.