# Fundamental Algorithms - Winter 10

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

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