Fundamental Algorithms (CSE)
- Lecturer: Prof. Dr. Harald Räcke
- Module: IN2157, TUMOnline
- Time and Place:
Monday, 08:30–10:00, 00.06.011, MI Hörsaal 3 - Audience:
CSE graduate students - Recommended for:
CSE graduate students
Announcements
Content
The course will provide an overview on the analysis of fundamental algorithms. Topics will be:
- Fundamentals: Models of Computation, Complexity Measures
- Sorting: Bubble-Sort, Merge-Sort, Quick-Sort, Median-Algorithms, Lower Bounds, etc.: sorting in parallel
- Searching: Hashing, Search Tress, etc.
- Arithmetic Problems: parallel prefix computation, parallel matrix and vector operations
- Foundations of parallel algorithms and simple models of parallel computation
- Algorithms on (weighted) graphs: traversals, shortest paths, etc.
Material
Lectures:- Introduction – Algorithms, Fibonacci Example, Asymptotic Notation: pdf
- Sorting: pdf
- Recurrences: pdf
- Searching: pdf
- AVL-Trees: pdf
- Hashing: pdf
- PRAM, Introduction to Parallel Algorithms: pdf
- Parallel Sorting: pdf
- Graphs: pdf, pptx
- Weighted Graphs: pdf pdf
- Asymptotic Notation: pdf and solution
Asymptotic Notation has not been covered in the lecture yet, but should be prior knowledge. Please make sure that you are up to date with this topic. - Complexity and
Sorting: pdf and solution
- Mergesort: pdf and solution
- Recurrences: pdf and solution
- Searching: pdf and solution
- AVL-trees: pdf and solution
- Hashing: pdf and solution
- Parallel Algorithms: pdf and solution
- Parallel Sorting: pdf and solution
- Graphs: pdf and solution
- Weighted Graphs: pdf
and solution
Exam
- The exam will take place on Friday, 26th Feb, in room 5101.EG.501.
- You are allowed to bring a cheat sheet, which must adhere to the following
requirements:
- size DIN A4 or smaller
- it must be hand-written, on one side only (copies are not allowed)
- it must carry your name and your student ID number in legible(!) writing
- no further materials (book, calculate etc.) is allowed