English English

ECTS: 4
RWTHonline: here
Course dates Contact person
Winter term 2018/19 Gerhard Woeginger


Bridge Course Algorithms and Data Structures
A blended learning bridge course for master students in Data Science

This course is intended for Data Science students with little background in computer science, in particular for students with a bachelor's degree in Mathematics, Physics or Electrical Engineering.


Videos

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


Book

The underlying text book is "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein.


Recommended exercises

On top of 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 are shown in black, and problems (listed in the final section of every chapter) are shown 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


Exam

At the end of the term, there will be a written exam of 90 minutes.


Contact

woeginger(at)algo.rwth-aachen.de
Question hour: Friday, 11:00-12:00, room 4024 (E1)