Lehre » Winter 19/20 » Bride Course Algorithms and Data Structures
Bridge Course Algorithms and Data Structures (WS 19/20)
A blended learning bridge course for master students in CSS and for master students in Data Science
This course is intended
- for students of Data Science, and
- for students of Computational Social Systems,
with little background in computer science.
Exam
At the end of the term (February 19, 2020), there will be a written exam of 90 minutes.
-
The exam covers the contents of the 12 video lectures, the corresponding chapters and sections in the
underlying textbook [CLRS], and the recommended problems and exercises (as listed on this web-page).
-
The registration must be done via
RWTHonline.
Click on "Exam Registration - Search", then search for "Algorithms and Data Structures",
and register for the exam where "Wöginger G" is the examiner.
-
You have to register for the exam by December 29, 2019.
(You may cancel your registration lateron without further consequences, but only till the third day before the exam.)
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
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
Book
The underlying text book [CLRS] is the
2nd edition of
"Introduction to Algorithms"
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
Many copies of the book are available in our library (Informatik Bibliothek).
It is also easy to find electronic versions of the book on the web.
Contact
woeginger(at)algo.rwth-aachen.de
Question hour: Friday, 10:30-11:30, room 4024 (E1)