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 cover graphs, strings, polynomials, and geometry. Furthermore, we 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 Wednesdays in the slot 16:00 -- 18:00.

The tutorial will take place also in lecture hall 002 on Thursdays and Fridays 8:30 -- 10:00. Your are free in the choice of the tutorial.

We strongly recommend that you participate in this course being present in the classroom. However, we also make it possible to take the course remotely, see Information->Virtual Guide.

Prerequisites

The course requires basic knowledge in algorithms and data structures as covered for example by the introductory course "Grundzüge von Algorithmen und Datenstrukturen". 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 Wednesday, November 9.

Exercises

Exercise sheets will be given out typically on Mondays and are due on the following Monday before the lecture. 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).

You may collaborate on solving the exercises, but every student must hand in a write-up in their own words. You are required to state your collaborators and all sources (books, papers, course notes, web pages, etc.) that you use to arrive at your solutions.

The solutions to these exercises are presented in the tutorial. You are free to choose the Thursday or Friday tutorial.

There will be approximately 12 exercise sheets. 6 clearly specified exercise sheets will be graded. You must have achieved at least 50% of the at that time possible points to qualify for an exam.

Mock-up Midterm Exam

On Wednesday, December 21st, we will offer a mock-up midterm exam in the afternoon instead of the usual lecture. The campus will be closed during that week. So you can take the exam at home. It is up to you to simulate the usual on-site exam conditions, in particular that  you refrain from using illicit help or use too much time. The exam will be graded but the results will not count towards the final grade.

 

Exams

Your final grade will be determined solely by your performance on the final exam or the repeat exam. Admittance to the exams requires 50% of the exercise sheet points, as explained above. The dates will be as follows:

Endterm: Friday, Febraruy 10th 2023,  14:15--16:45   lecture hall 002 in building E1 3.

Re-Exam: Friday, March 24th 2023,  14:15--16:45   lecture hall 002 in building E1 3.

 

Tentative List of Topics

 

• greedy algorithms
• dynamic programming
• divide and conquer (e.g. master theorem, integer multiplication, FFT)
• randomized algorithms (e.g. quicksort, randomized search trees, hashing)
• amortization (e.g. Fibonacci heaps, union find)
• strings (e.g. pattern matching, tries)
• graphs (e.g. shortest paths, maxflow, matching)
• (high-dimensional) geometry

 

Literature