Algorithms and Data Structures

Algorithms and Data Structures

The course will cover some basic and advanced data structures & algorithms along with their performance analysis. Examples of data structures are cuckoo hashing, splay trees, randomized search trees, and union-find structures. In terms of problem domains, we will cover polynomials, graphs, strings, and geometry. Furthermore, we will discuss algorithm analysis techniques such as amortization and randomization, and general algorithm design principles.

Time & Date & Format

Lectures:

• Mondays:   E2.5 Math lecture hall 1                 from 16:00 -- 18:00 (c.t.)
• Thursdays: E2.2 Günther-Hotz lecture hall     from 16:00 -- 18:00 (c.t.)

Tutorials:

• Online Wednesday: See  Materials                   from 14:00 -- 16:00 (c.t.)
• Offline Wednesday: E1.4 MPI-Inf Room 024   from 16:00 -- 18:00 (c.t.)
• Offline Fridays:         E1.3 Room SR016             from 10:00 -- 12:00 (c.t.)
• Offline Fridays:         E1.3 Room SR016             from 14:00 -- 16:00 (c.t.)

Prerequisites

The course requires basic knowledge in algorithms and data structures as covered, for example, by the introductory course "Introduction to Algorithms and Data Structures". In particular, you should be familiar with correctness proofs of algorithms. Specific concepts that you should have basic familiarity with and should be able to apply include:

• pseudocode notation
• O-notation, running time analysis
• binary search
• basic sorting algorithms (e.g., mergesort)
• arrays, linked lists
• stacks, queues
• heaps/priority queues
• binary search trees, balanced binary search trees (e.g., AVL trees)
• definition of a graph
• graph traversal (e.g., depth-first search/breadth-first search)

Registration

For participation in this course, you must also register on this website, and this must happen by Monday, May 4th.

Assignment Sheets

We will distribute an assignment sheet each Monday. Each assignment consists of graded exercises and ungraded exercises.

The graded exercises are further divided into solo exercises and group exercises. Please complete the solo exercises independently, without help from others. You are allowed to solve the group exercises in groups of up to three students. However, make sure that each member of your group understands the solution to each exercise. Turning in copied solutions is to nobody's gain. After all, in the end, to pass the course, you will need to write an exam without your friends or tools from the internet helping you.

Your solutions are to be uploaded as a PDF to this course website. The submission deadline is Monday before the lecture. Each person has to upload one file for their solo exercise solutions, and each group has to upload a separate file for their group exercise solutions (please upload a group submission even if your group only has a single member, i.e., you are doing the group exercises on your own). Do not upload any solution for the ungraded exercises. Instead, you should ask about them during the tutorial session.

For submission, you can produce a PDF by writing in LaTeX, writing in a common word processor like Word, or by taking a scan or a photo of your handwritten solution (if you take a photo, take special care that the PDF is readable).

The solutions to these exercises are presented in the tutorial. To be more specific, we will discuss the solution to the ungraded exercises before the submission deadline and the solution to the graded exercises after the submission deadline.

To be admitted to the (re)-exam, you need at least 50% of the total number of graded points (excluding bonus points).

AI and LLM policy

(Borrowed from https://cms.sic.saarland/ti2526/)

First of all, we need to differentiate between

1. Using ChatGPT to study and understand the concepts and
2. Using ChatGPT to solve the exercises given to you

Case 1 is obviously allowed and does not require any special indication. It is a perfectly valid way to learn, not much different from doing regular research on the internet. Therefore, in what follows, we will mainly concern ourselves with case 2.

Case 2 means that you have used an external source for (a part of) a solution. You should clearly indicate what source you used for what part of the solution on the same submission (same PDF file) as the task.

If you do not state your source, it will count as plagiarism.

If you state your source, it will not be plagiarism. We will grade the solution, but upon the first (no matter how small) mistake, we will stop the grading and award that particular exercise 0 points. We will also not put in extra effort to give detailed feedback (why would we be giving feedback to ChatGPT?)

Note that while we were mostly mentioning ChatGPT, the same holds for other external sources as well.

In addition:

• Copying any part of a solution of another group always counts as plagiarism.
• Copying any part of a solution for solo exercises always counts as plagiarism.

Exams and Grades

Your final grade will be determined solely by your performance on the final exam or the repeat exam. The better grade of both exams determines your final grade. The dates will be as follows:

Endterm: Thursday, July 23rd 2026,  14:00 -- 17:00 

Re-Exam: Thursday, September 24th 2026,  14:00 -- 17:00

List of Topics

Note that this list is preliminary and may change. Also, additional references may be added shortly before or after the lecture.

Literature