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, 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

The lectures will take place in lecture hall 002 in building E1 3 Mondays and Thursdays in the slot 16:00 -- 18:00.

The tutorial will take place also in lecture hall 002 on Wednesdays in the same slot 16:00 -- 18:00.

The lectures and tutorials will not be streamed. We strongly recommend that you participate in this course being present in the classroom.

Prerequisites

The course requires basic knowledge in algorithms and data structures as covered for example by the introductory course "Fundamentals of 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 register also on this website, and this must happen until Friday, November 15.

Problem Sets

We will hand out problem sets about every other week.  Although solutions of problem sets will not count towards your grade we strongly recommend that you work on the problems and cleanly write up and turn in some of your solutions. Feel free to discuss the problems with your friends, but avoid looking up solutions somewhere too early.

Turning in copied solutions is to nobody's gain. Even if you collaborate with friends and together you find a solution you should try to generate a clean writeup of this solution on your own, with your own words, your own notation. After all, In the end for passing 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. 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.

Mock-up Midterm Exam

On Monday, December 9th, we will offer a mock-up midterm exam in class instead of the usual lecture. The exam will be graded but the results will not count towards the final grade.

 

Exams and Grades

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

Endterm: Friday, Febraruy 14th 2025,  13:15--15:45   lecture hall 002 in building E1 3.

Re-Exam: Friday, April 4th 2025,  13:15--15:45   lecture hall 002 in building E1 3.

 

Tentative List of Topics

 

• greedy algorithms
• dynamic programming
• divide and conquer (e.g. Akra-Bazzi-Theorem, polynomial arithmetic, FFT)
• randomized algorithms (e.g. quicksort, randomized search trees, hashing)
• amortization (e.g. hollow heaps, union find)
• strings (e.g. pattern matching, tries)
• graphs (e.g. shortest paths, maxflow, matching)
• computational geometry

 

Literature