# 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

**Exercises:**

**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