News
Lecture starts at 12:10Written on 23.10.25 by Karl Bringmann Dear students, This is a reminder that from now on the lecture will always start at 12:10, as we decided in the first lecture. |
Check your Tutorial PreferencesWritten on 14.10.25 by Niko Hastrich Dear all, we updated the available tutorials in the CMS. This might have erased your preferences. Please check and, if needed, re-enter your selection. If you need an English-speaking tutorial, pick a time slot where one is available and then go to that tutorial, even if you were assigned the… Read more Dear all, we updated the available tutorials in the CMS. This might have erased your preferences. Please check and, if needed, re-enter your selection. If you need an English-speaking tutorial, pick a time slot where one is available and then go to that tutorial, even if you were assigned the German-speaking one. Best, |
Introduction to Algorithms and Data Structures
This lecture gives an introduction to the design of efficient algorithms and data structures, as well as analyzing their correctness and running time. We will cover sorting algorithms, basic data structures (linked lists, stacks, priority queues, balanced binary search trees, hashing), and basic graph algorithms (traversal, shortest path, minimum spanning tree). We will discuss algorithm design techniques such as divide and conquer, exhaustive search, greedy and dynamic programming as well as randomized algorithms and amortized analysis of algorithms.
Lecture Format
Lecture: Thursdays 12:15-14:00 (E2 2 HS 001, Günter-Hotz-Hörsaal)
The first lecture will take place on October 16. The lectures will be held in English.
Recordings of the lecture will be made available, in cases of technical difficulties recordings from previous years will be used.
Prerequisites: It is recommended to have taken Programming 1+2 and Mathematics for Computer Scientists 1+2 before this course.
Exercise Sheets & Tutorials
Exercise sheets will be handed out on Thursday and are due on the next Thursday before the lecture. You can work in groups of up to 3 students on the exercises. You do not need to be assigned the same tutorial as your group members. Each group must submit exactly one solution (for digital solutions this means that exactly one group member should submit the solutions via this website). The first page of your solutions must list all group members and their respective tutors. Each group must write their own solution and must not copy the solution of another group! Your solutions should be submitted either physically in the lecture hall or digitally via this website. Physical solutions are handwritten or printed sheets of paper. Digital solutions are submitted as a PDF by writing in LaTeX, writing in a common word processor like Word, or as a high quality scan/photo of a handwritten submission.
The exercises sheets will be written in English, but you can choose to write your solutions in English or German depending on the tutorial you choose (i.e. check the submission language in the table below).
Solutions to the exercises will be presented in the weekly tutorials. Tutorials start on October 29. We offer the following tutorial slots:
| Time | Tutor | Room | Tutorial Language | Submission Language |
|---|---|---|---|---|
| Wed 08-10 | Maryna | E13 SR014 | English | English |
| Wed 10-12 | Thorben | E13 SR014 | English | Deutsch/English |
| Wed 12-14 | Benjamin | E13 SR014 | Deutsch | Deutsch/English |
| Wed 14-16 | Jonas | E13 SR014 | English | Deutsch/English |
| Wed 16-18 | Xijang | E13 SR014 | English | English |
| Wed 08-10 | Florian | E13 SR015 | Deutsch | Deutsch/English |
| Wed 10-12 | Jan | E13 SR015 | Deutsch | Deutsch/English |
| Wed 12-14 | Marius | E13 SR015 | Deutsch | Deutsch/English |
| Wed 14-16 | Mahmoud | E13 SR015 | Deutsch | Deutsch/English |
| Wed 16-18 | Lars | E13 SR015 | Deutsch | Deutsch/English |
When registering on this website, you are asked to give your preferences for tutorial slots. You can submit your preferences until October 22. We will then create a tutorial assignment on October 23.
Office Hours
We offer Office Hours, where you can ask tutors about the course material or exercises:
- Tuesday 12:00-13:00 (Room: E1-3 401)
- Friday 10:00-11:00 (Room: E1-3 401)
The office hours start in the week of the 20th of October.
Grading and Exams
To be able to obtain a certificate you must register in the LSF system. If you are unable to register in LSF, please contact Niko.
To be admitted to the final exam and the re-exam, you need to score at least 50% of the points on the exercise sheets. For the exams you are allowed to bring a single handwritten DinA4-sheet (which can be written on both sides); photocopies and printouts are not allowed. Your final grade will be the better of your grade in the final exam and your grade in the re-exam.
- Final Exam: 17.02.26, 09.00-12.00
- Re-Exam: 24.03.26, 14.00-18.00
Tentative Schedule
| Date | Topic | Comment |
|---|---|---|
| Oct 16 |
Introduction (machine model, O-notation, correctness proofs)
|
|
| Oct 23 |
Basic Sorting Algorithms and Lower Bound
|
|
| Oct 30 |
Non-comparison-based Sorting + Basic Data Structures
|
|
| Nov 6 |
More Basic Data Structures + Binary Search Trees
|
|
| Nov 13 |
Balanced Binary Search Trees
|
|
| Nov 20 |
Priority Queues
|
|
| Nov 27 |
Divide and Conquer
|
|
| Dec 4 |
Introduction to Randomized Algorithms
|
|
| Dec 11 |
Hashing
|
|
| Dec 18 |
Graphs I: Representation and Traversal
|
|
| Dec 25 | --- | lecture-free period |
| Jan 1 | --- | lecture-free period |
| Jan 8 |
Graphs II: Shortest Paths
|
|
| Jan 15 |
Graphs III: Minimum Spanning Trees
|
|
| Jan 22 |
Greedy and Dynamic Programming
|
|
| Jan 29 | More Dynamic Programming | |
| Feb 5 |
Outlook, Q&A
|
Literature
There are many good books and lecture scripts on the topic, here is a selection:
- [Blä] M. Bläser, Introduction to Algorithms and Data Structures, 2015 (Script)
- [MS] K. Mehlhorn, P. Sanders, Algorithms and Data Structures - The Basic Toolbox, Springer, 2008 (ISBN: 9783540779773)
- [CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms - Fourth Edition, MIT Press, 2022 (ISBN: 9780262046305)
- [Eri] J. Erickson, Algorithms, 2019 (Free electronic version)