**Teachers**

- Philip Bille, office hours Fridays 12.00-12.30 on Zoom id: 677 3898 7472.
- Inge Li Gørtz.

**Teaching Assistants**

- Peter Revsbech
- Simon Rumle Tarnow
- Christian Mikkelsen Fuglsang
- Katrine Bjørn Pedersen Thoft
- Kasper Sand Kirk
- Alexander Philip Bilton Bråten
- Emil Toftegaard Gæde
- Olav Nørgaard Olsen
- Mathias Jarl Jarby Søndergaard
- Gustav Valdemar Fjorder

**Materials** "Introduction to Algorithms", 3rd edition (CLRS), Cormen, Leierson, Rivest, and Stein + notes.

**CodeJudge** We use CodeJudge for testing code and correcting the implementation part of the mandatory exercise. Access CodeJudge here.

**Gradescope** We use Gradescope for correcting the written part of the mandatory exercise and the final exam. The system significantly improves consistency and quality in grading. Please sign up for Gradescope as follows:

- Go to http://www.gradescope.com.
- Select "Sign up for free".
- Select "Sign up as a student".
- Enter the course entry code
`4PGYJ4`

, your*full name*, your`@student.dtu.dk`

email, and your student-id (of the form`s123456`

). Please follow these instructions precisely so that we can correctly identify you.

**Weekplan** The weekplan below is preliminary and may be updated during the course.

**Online Teaching Plan** Detailed plan for the online activities is here. The plan will be updated weekly.

Week | Topics | Slides | Weekplans | Materials | Screencasts |
---|---|---|---|---|---|

Warmup: Preparation, Programming Prerequisites, and Puzzles. | Warmup | Survival Guide · Programming Prerequisites | |||

Basic Concepts I: Introduction, Algorithms, Data Structures, Peaks. | 1x1 · 4x1 | Introduction | CLRS chap. 1 | Introduction | |

Basic Concepts II: Searching, Sorting. | 1x1 · 4x1 | Searching and Sorting | CLRS chap. 2 | Searching and Sorting 1 · Searching and Sorting 2 | |

Basic Concepts III: Complexity, Asymptotic Notation, Empirical Analysis. | 1x1 · 4x1 | Analysis of Algorithms | CLRS chap. 3 | Analysis | |

Data Structures I: Stack, Queues, Linked Lists, Trees. | 1x1 · 4x1 | Introduction to Data Structures | CLRS intro to part III + chap. 10 | Data Structures 1 · Data Structures 2 · Data Structures 3 | |

Graph Algorithms I: Undirected Graphs, Representation, Searching, Modelling. | 1x1 · 4x1 | Introduction to Graphs | CLRS intro to part VI + chap. 22.1-22.4 + appendix B.4-B.5. | Graphs 1 · Graphs 2 · Graphs 3 | |

Graph Algorithms II: Directed Graph, Topological Sorting, Implicit Graphs. | 1x1 · 4x1 | Directed Graphs | CLRS intro to part VI + chap. 22.1-22.4 + appendix B.4-B.5. | ||

Data Structures II: Priority Queues, Heaps. | 1x1 · 4x1 | Priority Queues and Heaps | CLRS chap. 6 + appendix B.5 | ||

Data Structures III: Union-Find, Dynamic Connected Components. | 1x1 · 4x1 | Union-Find | CLRS chap. 21 except 21.4 + Algorithms, 4ed. chap. 1.5 | ||

Graph Algorithms III: Minimum Spanning Trees, Prims' Algorithm, Kruskal's Algorithm. | 1x1 · 4x1 | Minimum Spanning Trees | CLRS chap. 23. | ||

Graph Algorithms IV: Dijkstra's Algorithm, Shortest Paths in Weighted Graphs, Shortest Paths in DAGs. | 1x1 · 4x1 | Shortests Paths | CLRS chap. 24 except 24.1 and 24.4. | ||

Data Structures IV: Dictionaries, Hashing. | 1x1 · 4x1 | Hashing | CLRS chap. 11 except 11.5. | ||

Data Structures V: Algorithms on Trees, Predecessor Problem, Binary Search Trees. | 1x1 · 4x1 | Binary Search Trees | CLRS chap. 12 except 12.4. |

The course has a single mandatory exercise. The mandatory exercise is done in small groups of 3, 2, or 1 students. The mandatory exercise runs from March 25 to April 18.

**Collaboration policy** The mandatory exercise is subject to the following collaboration policy. The exercise should be done in groups of 3, 2, or 1 students. It is not allowed to collaborate with other groups 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 parts of solutions to the exercises to other people. It is not allowed to use solutions from previous years, solutions from similar courses, or solutions found on the internet or elsewhere.

**What programming and mathematics requirements do I need for the course?** In general, you need an introductory course in programming and mathematics. We use basic programming extensively to implement algorithms and discrete mathematics to analyse algorithms. See the materials on this page to clarify how this applies to your current competencies in programming and mathematics.

**What is the language of the course?** The official language of the course is English. Hence the spoken language in lectures and the exam is in English. There are Danish exercise classes and your are free to hand in the mandatory exercise and the exam in Danish.

**What is the programming language used in the course?** You can use most standard imperative programming languages (including Python, Java, C, and C++). The language must be supported by CodeJudge.

** I need to quickly refresh my programming skills. What do you recommend?** We suggest the book "Introduction to Programming in Java", Sedgewick and Wayne. The book is compact, concise, and focused on the core technical aspects of programming. The books covers essentially all relevant material for the course in chapter 1, which is freely available at the homepage for the book.

**Which supplementary books/materials do you recommend?** We suggest the following:

- "Algorithm Design", Kleinberg and Tardos. Focus on algorithm design. Lacks some of data structures covered in the course.
- "Algorithms", Sedgewick and Wayne. Focus on implementation and many code examples.
- "Algorithms", Jeff Erickson. Excellent freely available online book.
- "Data structures and algorithms in Java", Goodrich and Tamassia.

**When and where is the exam?**
Please see the DTU exam schedule.