**Teachers**

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

**Teaching Assistants**

- Christian Mikkelsen Fuglsang
- Simon Rumle Tarnow
- Alexander Philip Bilton Bråten
- Olav Nørgaard Olsen
- Christian Møller Mikkelstrup
- Lauge Thode Hermansen
- Hans Henrik Hermansen
- Jonathan Schmidt Højlev
- Karl Meisner-Jensen
- Magnus Kragh Siegumfeldt
- Roar Nind Steffensen

**Schedule**
Find the detailed plan for exercises classes, online walkthroughs, and lectures here. The plan will be updated weekly.

**Materials**

- "Introduction to Algorithms", 3rd edition (CLRS), Cormen, Leierson, Rivest, and Stein
- "Competitive Programmer's Handbook" (CSES), Chap. 11-15, Laaksonen. Links: Java version and Python version. See book homepage for other programming languages.
- "Algorithms, 4th edition", Chap. 1.5, Sedgewick and Wayne. (See materials for Union-Find).
- Miscellaneous Notes.

**CodeJudge** We use CodeJudge for automatic code verification.

**Screencasts** As a supplement we have screencasts available for the material in the lectures. These were recorded during COVID-19 lockdowns.

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

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. + CSES chap. 11-12. | 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 + CSES chap. 11-12. | Directed Graphs 1 · Directed Graphs 2 · Directed Graphs 3 | |

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

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

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

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 + CSES chap. 14. | Shortests Paths | |

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

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

Course Wrap-Up: Questions, Exam, and Algorithms Courses and Projects. |

The course features a number of non-mandatory/voluntary hand-in exercises posted throughout the semester and evaluated by TAs. The guidelines for preparing these exercises are as follows.

- Work together on the exercises with other students if possible. This will help you to come up with better solutions. Pick a single group member that submits on DTU Learn. Do
*not*submit multiple copies for a group. - Be precise and brief in your answer to the questions. Write you algorithms and data structure descriptions in natural language unless otherwise specified. Separate your description of algorithms, analysis, and correctness.
- Use the toolbox of known algorithms and data structures from the course as "black-boxes" in your solutions if applicable. Do not repeat description and/or analysis of known algorithms and data structures.
- Prepare a single pdf-file of your write-up. Write your full names and study IDs on the top of the page. Do not repeat problem statement in your write up. Like this template. The final file should consist of a single page.
- Use Danish or English for your write up depending on which language you are most proficient in.

The exam is a written exam covering the teaching goals of the course (see course description). The format of the exam consists of 3 parts:

- A multiple-choice part. This part is a sequence of questions where the correct answer(s) are to be selected. This part is done using the digital exam platform at DTU.
- A programming part. This part involves programming solutions to problems. This solutions must be uploaded to the CodeJudge platform.
- A written part. This part involves writing solutions to problems. The solutions must be uploaded to digital exam platform at DTU.

**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 exercises and the exam in Danish.

**What is the programming language used in the course?** You can use the following standard imperative programming languages: Python, Java, C, and C++.

** I need to quickly refresh my programming skills. What do you recommend?** We suggest the book "Introduction to Programming in Java", Sedgewick and Wayne (or the Python version "Introduction to Programming in Python"). 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.
- "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.