Bridging Course Algorithms and Data Structures
A blended learning bridge course for M.Sc. students to acquire fundmental basics in design and analysis of algorithms and data structures.
- Only students in MSc. Data Science can get credit for the course.
- No need to register for the lectures -- it is a self-learning course, and there are no corrected exercises.
- Students from study programs other than MSc. Data Science may watch the video lectures and study the text book on their own. However, they can neither register for the exam, nor take the exam, and in particular they cannot receive credit points for this course.
- To register for the exam, Data Science students shall use the standard exam registration in RWTHonline.
- Oral exams at the end of the semester -- contact Prof. Hoefer to schedule your exam.
Material
The course is self paced and consists of 12
[video lectures] from MIT Open CourseWare.
The [course material] has been developed by Prof. Charles Leiserson and Prof. Erik Demaine.
- 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
Recommended Exercises
In addition to the [problems and exercises] posed at the MIT page, we also recommend the following exercises and problems from the book by Cormen et al (2nd edition). Exercises in black color, problems (see final sections of each chapter) are in red color.
- Lecture 1: 1.2-3, 2.1-2, 2.2-2, 2.3-3, 2.3-5; 2-2
- Lecture 2: 3.1-2, 3.2-3; 3-2, 3-4; 4.2-1; 4.3-1; 4-4
- Lecture 3: 28.2-2, 28.2-6
- Lecture 4: 7.1-2, 7.2-1, 7.3-1, 7.4-2
- Lecture 5: 8.1-1, 8.1-3, 8.2-2, 8.3-2, 8.4-2
- Lecture 6: 9.1-1, 9.3-1, 9.3-2, 9.3-8, 9.3-9
- Lecture 7: 11.1-2, 11.2-1, 11.2-5, 11.3-3, 11.3-4
- Lecture 9: 12.1-1, 12.1-2, 12.1-4, 12.2-4, 12.3-3, 12.3-5
- Lecture 15: 15.1-2, 15.1-3, 15.4-1, 15.4-2, 15.4-5
- Lecture 16: 23.1-1, 23.1-3, 23.1-5, 23.2-1, 23.2-4, 23-3
- Lecture 17: 24.3-1, 24.3-2, 24.3-3, 24.3-4, 24.3-8
- Lecture 18: 24.1-1, 24.1-2, 24.1-4, 24.2-4, 24.4-2, 24.4-6
Book
- Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein. "Introduction to Algorithms", 2nd edition, MIT Press.
All references to chapters (and in particular: all numbers of exercises and problems) refer to the 2nd edition of the book; other editions contain essentially the same material but slightly differ in the numbering of chapters and exercises.