Introduction to Algorithms and Data Structures

Prof. Karl Bringmann
This course is also known as "Fundamentals of Data Structures and Algorithms" and "Grundzüge von Algorithmen und Datenstrukturen"

News

Exercise Sheet 7 Task 3.a

Written on 10.12.24 (last change on 10.12.24) by Niko Hastrich

Dear all,

we have noticed that the intended solution for subtask 3.a on exercise sheet 7 was not correct, and decided that every student should get full credits for this subtask.

The problem lies in the fact that n in this task refers to the number of elements currently present in the data… Read more

Dear all,

we have noticed that the intended solution for subtask 3.a on exercise sheet 7 was not correct, and decided that every student should get full credits for this subtask.

The problem lies in the fact that n in this task refers to the number of elements currently present in the data structure. If we do not allow deletions, then we need at most (1 + log n)-many arrays to hold all elements. However, if we allow deletions (which were intended to just pop the last element of some list), this is no longer the case as there are sequences of operations such that afterward we have n lists with one element each. This breaks the running time of the intended solution. Rather, the running times should have referred to the number of insert operations N, that have already taken place.

We deeply apologize for any inconvenience that were caused by this error.

Best regards,
Niko

Anonymous Feedback and Workload

Written on 05.12.24 (last change on 05.12.24) by Niko Hastrich

Dear all,

in the past, you could submit anonymous feedback directly to the teaching team in the CMS. Due to some disrespectful comments, we have disabled this line of feedback. Still, we value your feedback, so you can from now on submit feedback anonymously at … Read more

Dear all,

in the past, you could submit anonymous feedback directly to the teaching team in the CMS. Due to some disrespectful comments, we have disabled this line of feedback. Still, we value your feedback, so you can from now on submit feedback anonymously at https://forms.office.com/e/kS2CmxvShW. Here, a person not involved with the lecture will read your feedback. If it is respectful, they will pass it on to us verbatim. Otherwise, they will summarize your critique and pass it on this way.

A few exercise sheets ago, we asked you to state how many hours you are working for this lecture. This question was sparked by anonymous feedback. The mean workload among the students who answered is 7.8 hours, while the median workload is 8 hours. This roughly corresponds to our expectations, and we do not see a need for changes.
We know that there are some students who are investing more time than intended. However, the tutors reported to us that, typically, students spending too much time do not submit in groups of 3. So, if you are affected and do not submit in a group of 3, talk to your tutor and ask them whether there is some other group with whom they can pair you up.

Best regards,
Niko

PS: You can find a chart of the workload distribution here.

Relocation of Tutorials

Written on 14.11.24 by Niko Hastrich

Dear all,
next week, the beamer in E1.3, SR015 will be replaced. Therefore, all tutorials taking place in this room are moved as follows:
Mo 10-12 (Lars) takes place in E1.1, 407
Mo 12-14 (Mahmoud) takes place in E1.3, HS003
Thu 8-10 (Johannes) takes place in E1.3, HS003
Thu 10-12 (Jashman) takes… Read more

Dear all,
next week, the beamer in E1.3, SR015 will be replaced. Therefore, all tutorials taking place in this room are moved as follows:
Mo 10-12 (Lars) takes place in E1.1, 407
Mo 12-14 (Mahmoud) takes place in E1.3, HS003
Thu 8-10 (Johannes) takes place in E1.3, HS003
Thu 10-12 (Jashman) takes place in E1.1, 3.06
Best,
Niko

Exam Dates

Written on 12.11.24 by Karl Bringmann

Dear students,

The exam dates have been fixed as follows:

Final Exam: 13.02. 16:00-18:30

Re-Exam: 25.3. 14:00-16:30

Tutorial Assignment, Exercise Sheet 2, Sample Solutions

Written on 24.10.24 by Niko Hastrich

Dear all,

as some of you already noticed, you were assigned to a tutorial now. If there are any dealbreakers with your assignments, please don't hesitate to contact me.
Exercise sheet #2 is published now and as always you have one week to solve it (deadline is October 31st 12:00). Additionally, we… Read more

Dear all,

as some of you already noticed, you were assigned to a tutorial now. If there are any dealbreakers with your assignments, please don't hesitate to contact me.
Exercise sheet #2 is published now and as always you have one week to solve it (deadline is October 31st 12:00). Additionally, we published a sample solution to the first exercise sheet.

Best,
Niko

One Submission per Team

Written on 24.10.24 by Niko Hastrich

Dear all,

for each team, exactly one team member should submit your solution (either digitally or physically). This helps the tutors to only grade each exercise sheet once.
Even though we decided against using the teams feature of the CMS, all of you will get the respective points for the exercise… Read more

Dear all,

for each team, exactly one team member should submit your solution (either digitally or physically). This helps the tutors to only grade each exercise sheet once.
Even though we decided against using the teams feature of the CMS, all of you will get the respective points for the exercise sheet. To be able to do that, you must write the names of all your team members on your solution.

Best,
Niko

Corrected Deadline for First Exercise Sheet

Written on 17.10.24 by Niko Hastrich

Please note that we put the wrong Deadline on the first exercise sheet. The correct deadline is next Thursday, October 24. We have corrected the uploaded version. As mentioned in the lecture, this gives you one week to work on the exercises.

Best,
Niko

Update Your Tutorial Choice

Written on 16.10.24 by Niko Hastrich

Dear all,

up until now, you were only able to assign preferences for the time of your tutorial. For the time slots where there is an English and a German tutorial simultaneously, this did not allow you to choose the tutorial language. We have updated the tutorial choices for you to be able to give… Read more

Dear all,

up until now, you were only able to assign preferences for the time of your tutorial. For the time slots where there is an English and a German tutorial simultaneously, this did not allow you to choose the tutorial language. We have updated the tutorial choices for you to be able to give preferences to each tutorial individually, allowing you to specify the language of the tutorial you prefer.

This erased all preferences. So, please update your preferences by next Wednesday, October 23rd.

Best,
Niko
Show all

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 17. The lectures will be held in English.

We will try to make recordings of the lecture available on this website, but there can always be technical difficulties, so we recommend attending in person.

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. 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 first page of your solutions must list your name and your tutorial slot.

You can work in groups of up to 3 students on the exercises. 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. Each group must write their own solution and must not copy the solution of another group!

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 28. We offer the following tutorial slots:

Time Tutor Room Tutorial Language Submission Language
Monday 8-10 Jonas E1.3, SR014 English English or German
Monday 10-12 Jan E1.3, SR014 English English or German
Monday 10-12 Lars E1.3, SR015 German English or German
Monday 12-14 Thorben E1.3, SR014 English English or German
Monday 12-14 Mahmod E1.3, SR015 German English or German
Monday 14-16 Samuel E1.3, SR014 German English or German
Monday 16-18 Florian E1.3, SR014 German English or German
Thursday 8-10 Johannes E1.3, SR015 German English or German
Thursday 10-12 Jashmanpreet E1.3, SR015 English English or German

 

When registering on this website, you are asked to give your preferences for tutorial slots. You can submit your preferences until October 23. We will then create a tutorial assignment on October 24.

 

Office Hours

We offer Office Hours, where you can ask tutors about the course material or exercises:

  • Tuesdays 13:00-14:00, room 401 E1 3
  • Wednesdays 11:00-12:00, room 401 E1 3

 

Algodat++

If you feel confident with the core concepts of the lecture and would like to explore more advanced topics, we offer an extra tutorial which is:

  • solving additional, difficult exercises
  • presenting additional material related to the lecture, e.g. more efficient algorithms

  • discussing unexpected applications of the lecture material

This happens Tuesdays 14:15-16:00 in room 024 building E1 4 (MPI-Inf), starting on October 29. It is organized by Evangelos Kipouridis. Participation is voluntary.

 

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: 13.02. 16:00-18:30
  • Re-Exam: 25.03. 14:00-16:30

 

Tentative Schedule

Date Topic Comment
Oct 17
Introduction (machine model, O-notation, correctness proofs)
  
Oct 24
Basic Sorting Algorithms and Lower Bound
  
Oct 31
Non-comparison-based Sorting + Basic Data Structures
  
Nov 7
More Basic Data Structures + Binary Search Trees
  
Nov 14
Balanced Binary Search Trees
  
Nov 21
Divide and Conquer
 replacement lecturer: Evangelos Kipouridis
Nov 28
Priority Queues
  
Dec 5
Introduction to Randomized Algorithms
 replacement lecturer: Evangelos Kipouridis
Dec12
Graphs: Representation and Traversal
 replacement lecturer: Evangelos Kipouridis
Dec 19
Hashing
  
Dec 26 --- lecture-free period
Jan 2 --- lecture-free period
Jan 9
Graphs II: Shortest Paths
  
Jan 16
Graphs III: Minimum Spanning Trees
  
Jan 23
Greedy and Dynamic Programming
  
Jan 30 More Dynamic Programming  
Feb 6
Outlook
  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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)
Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.