Introduction to Algorithms and Data Structures

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.

 

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.

 

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: date tba
• Re-Exam: date tba

 

Tentative Schedule

Date	Topic	Comment
Oct 17	Introduction
Oct 24	Basic Sorting Algorithms
Oct 31	HeapSort and non-comparison-based sorting
Nov 7	Introduction to randomized algorithms
Nov 14	Basic data structures
Nov 21	Binary Search Trees
Nov 28	Hashing
Dec 5	Divide and Conquer
Dec12	Greedy and Dynamic Programming
Dec 19	More Dynamic Programming
Dec 26	---	lecture-free period
Jan 2	---	lecture-free period
Jan 9	Graphs: Representation and Traversal
Jan 16	Graphs II: Shortest Paths
Jan 23	Graphs III: Minimum Spanning Trees
Jan 30	??
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)