Bridging Course - Algorithms and Data Structures
Overview
The Bridging Course "Algorithms and Data Structures" is a blended learning course intended for students of the Master programme "Computational Social Systems" who need to catch up on their background in theoretical computer science. It is given as an additional requirement ("Auflage") with admission for those students. The course (and the exam) were previously organized by the Computer Science Department but since 2022 are being coordinated and held by iTec.
Organization
The course consist of lecture and exercise material for self-learning and ends with an exam usually held early in the lecture free period of a semester. The exam will be conducted as an oral exam. The exam will be graded as pass/fail only, so no mark will be given. Registration is not necessary for the lecture, but it is mandatory for sitting the exam and it should be done via RWTH Online.
Content
The course is based on the MIT Open CourseWare course "Introduction to Algorithms" by Prof. Charles Leiserson and Prof. Erik Demaine.
Lectures
The lectures can be attended self-paced with the video lectures provided from the MIT course. We encourage you to take a look at the lecture notes provided in the "Related Resources" section for every lecture as well. We will be covering a subset of those lectures only, namely the following twelve items:
- Lecture 1: Introduction; Analysis of Algorithms, Insertion Sort, Mergesort
- Lecture 2: Asymptotic Notation; Recurrences; Substitution, Master Method
- Lecture 3: Divide-and-Conquer: Strassen, Fibonacci, complete binary trees
- Lecture 4: Quicksort, Randomized Algorithms
- Lecture 5: Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort
- Lecture 6: Order Statistics, Median
- Lecture 7: Hashing, Hash Functions
- Lecture 9: Binary search trees
- Lecture 15: Dynamic Programming, Longest Common Subsequence
- Lecture 16: Greedy Algorithms, Minimum Spanning Trees
- Lecture 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search
- Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints
Assignments
In addition to the lecture videos we strongly recommend also looking at the assignments given in the MIT course.
Book
The course is using the text book "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein, MIT Press. The references to chapters, exercises and problems made in the course material are referring to the 2nd edition of the book. Other editions contain the same information, but might deviate in the numbering.
Contact