## 02110 Algorithms and Data Structures II

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

### 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 358, room H-071 (English), H-063, and H-067.
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 308, auditorium 12.

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. Sign up here.

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 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:
• pass at least 3 mandatory assignments from the week plans (more info below).
• implement (and pass the tests of) two of the implementation exercises on CodeJudge.
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.
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

The programming competition is now on. There will be a prize for the best three teams. Participation in the programming competition counts as both a mandatory exercise and a mandatory CodeJudge exercise if you pass a certain set of the test cases.The deadline is November 26th 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 · full 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 · full Week 2
• Section 15 + 16.5-16.6 in notes by Jeff Erickson (can also be found on CampusNet)
• (CLRS chapter 17)
Splay Trees
Splay Trees Deletions
Dynamic programming I: Rod cutting and longest common subsequence 1x1 · 4x1· full Week 3
• CLRS 15.0-15.1, (15.3), 15.4
Dynamic programming II: Sequence alignment and All Pairs Shortest Paths 1x1 · 4x1 · full 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 · full Week 5
• CLRS 26.1, 26.2
Ford Fulkerson and min cut
Network Flow II: Edmonds-Karp, maximum bipartite matching 1x1 · 4x1 · full Week 6
• CLRS 26.2, 26.3
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)
• Alternative reading: Algorithm Design by Kleinberg and Tardos, section 13.5 (on CampusNet).
Line Segnment Intersection and Programming Competition Week 8
• CLRS 33.1
Strings I: String matching 1x1 · 4x1 Week 9
• CLRS 32.0, 32.3, 32.4
Automata matching and construction
KMP matching and construction
Strings II: Suffix trees 1x1 · 4x1 Week 10
• 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)
Computational Geometry: Closest Pair of Points in the Plane 1x1 · 4x1 Week 11
• CLRS 33.4.
• Algorithm Design by Kleinberg and Tardos, section 5.4 and 13.7 (on CampusNet).
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 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.