Lehre » Winter 21/22 » Algorithms and Data Structures
Bridge Course Algorithms and Data Structures (WS 21/22)
A blended learning bridge course for master students with little background in theoretical computer science.
This course is only open for students of the following Master programs:
- Data Science
- Computational Social Systems
(Students from other programs may of course 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.)
Registration Process
- Data Science students have to use the exam registration in RWTHonline.
- Computational Social Systems students do not need to register for the exam.
It is not necessary to register for the lecture, because this course is a self learning course.
Exam
Due to the rising infection numbers we plan to switch from a written exam in presence to an online oral exam using zoom.
We already did this in the Winter semester 20/21 to protect the health of our students. This means that the exam on the 22.02 will not take place.
You have access to an online system to choose the appointment of your exam
here.
When you click on "Bridge" and "Examination" you can choose the time of your oral examination by clicking on one of the square.
It is possible to remove or change your choice later.
Your first attempt has to take place before the 18.03.
The second attempt has to take place between the 31.03 and the 14.04. You have to choose the appointment of your exam
here.
If you encounter problems, please contact fuchs(at)algo.rwth-aachen.de.
OLD:
At the end of the term, there will be two written exams of 90 minutes.
Here you can find an old exam. The exam is only an example for an exam and does not cover all the topics from the course that could occur in an exam. So please, make sure to learn all the topics from the course to prepeare for the exam.
First exam: 22.02.2022 at 12:30 in the AH VI, Ahornstr. 55(2356)
Second exam: 14.03.2022 at 12:30 in the AH I, Ahornstr. 55(2350)
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
If you encounter problems or have questions regarding some topic of the lecture, you can wirte your question to fuchs(at)algo.rwth-aachen.de
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
Book
The underlying text book is
"Introduction to Algorithms"
by Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein, MIT Press.
All references to chapters (and in particular: all numbers of exercises and problems) concern the
2nd edition
of the book; the other editions contain essentially the same information, but slightly deviate in the numbering
of chapters and exercises.
Contact
fuchs(at)algo.rwth-aachen.de
