# Fundamental Algorithms - Winter 10

Jump to navigation
Jump to search

**Term**- Winter 10
**Lecturer**- Dr. Dirk Pflüger
**Time and Place**- Tuesday, 9:00-10:30, lecture hall MI
**02.07.023**; first lecture November 2 **Audience**- Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing
**Tutorials**- -
**Exam**- repeat exam (date: May 02, 2011; 16:30-18:00 in room MI 02.07.023
**Semesterwochenstunden / ECTS Credits**- 2 SWS (2V) / 3 Credits
**TUMonline**- {{{tumonline}}}

## Contents

# Contents

The course will provide an overview of fundamental algorithms and an introduction to the analysis of 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
- Graph Algorithms: Transitive Closure, Shortest Path Problems, Minimum Spanning Trees (if time allows)

# Current News

**Master Thesis? Student project?**We're always looking for you! See Student Projects and/or ask me!- See the updates on corrections.
- Exam details below.

# Lecture Notes and Material

## Slides from the Lecture

- Introduction - Algorithms, Fibonacci example, growth of functions
- Nov 2
- slides (Update loop invariants, 08.11.)
- Sorting Algorithms
- Nov 9, 16, 23
- slides (few typos corrected, 15.11. - update last slide, 24.11. - corrected partitioning algorithm, Python implementations available at [1], [2], call with "Python filename.py", 3.2.)
- Recurrences
- Nov 30
- slides (corrected prerequisites for Master Theorem, 6.12.)
- More Sorting
- Dec 7, 14
- slides
- Selecting
- Dec 14, 21
- slides
- Random Access Machines
- Dec 21
- slides (introduced Vector x, 21.12.) - NEW: RAM Simulator online!
- The PRAM Model
- Jan 11
- slides (Update of three slides, 12.01.)
- Searching
- Jan 18
- slides (update assumptions on slide 4, 18.01.)
- AVL Trees
- Jan 25
- slides
- Hashing
- Feb 1
- slides (update formula multiplication method, numbers on slide 19, 1.2.)

## Worksheets

- Growth of functions
- Nov 9
- worksheet, solution
- Complexity of Algorithms, Sorting on Matrices
- Nov 16
- worksheet, solution
- Recurrences - Complexity of MergeSort and QuickSort
- Nov 23
- worksheet, solution
- CountingSort
- Nov 30
- worksheet, solution (27.1. corrected error in solution 2a, third loop)
- Recurrences
- Dec 07
- worksheet, solution
- Selecting
- Dec 14
- worksheet, solution (27.1. corrected solution for exercise 2: call to larger partition)
- RAM
- Dec 21
- worksheet, solution (31.1. corrected line 16 RAM program: "=" -> ">"; 7.2. corrected resulting line 15, R6-R7 -> R7-R6 (thanks for both comments); 9.2. sorry, changed everything back again: the original version was correct, I included a full list of all RAM states for reference, note the definition of the subtraction!)
- PRAM
- Jan 8
- worksheet, solution (1.2. corrected typeos in ScalarProductPar and MatrixVectorProductEREW)
- Searching
- Jan 18
- worksheet, solution
- AVL trees
- Jan 25
- worksheet (28.1. corrected typeo: first "TreeInsert(5)" should be "TreeDelete(5)", solution
- Hashing
- Feb 1
- worksheet, solution

# Exam

- Date of repeat exam: Moday, May 02, 16:30-18:30 in room MI 02.07.023, see TUMonline
- Helping material: you are allowed to use
**one sheet (size A4) of paper**with**hand-written(!) notes**during the exam. Any further helping material (books, calculators, etc.) is forbidden! - Exam topics are all topics covered during the lectures; see, in particular, the worksheets for this course

# Literature

Recommended:

- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press

For parallel RAM:

- Berman, Paul: Fundamentals of Sequential and Parallel Algorithms

Also helpful:

- Heun: Grundlegende Algorithmen, Vieweg 2000
- Sedgewick: Algorithms, Pearson Education
- Shackleford, Computing and Algorithms, Addison Wesley Longman
- Kleinberg, Tardos: Algorithm Design, Pearson Education