# Fundamental Algorithms - Winter 11

Jump to navigation
Jump to search

**Term**- Winter 11
**Lecturer**- Prof. Dr. Michael Bader
**Time and Place**- Tuesday, 9:30-11:00 (MI 02.07.023); first lecture: Oct 25
**Audience**- Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing (elective)
**Tutorials**- ---
**Exam**- written exam, Thu, Feb 23, 2012 at 14.00 in room MW 0350; repeat exam (written) on Thu, Apr 12, 2012, at 13.00 in room MI 02.07.02
**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
- Foundations of parallel algorithms and simple models of parallel computation
- Algorithms on (weighted) graphs: traversals, shortest paths, etc.

# Announcements

**Exam Review**: on**Mon, Mar 19, 2012**from 15.30-17.00, you can look into your exam (for corrections and grading, e.g.); further opportunities for exam review will be offered, if there is respective demand.**Change of time**: Lecture was moved from 9.00-10.30 to 9.30-11.00 (starting on Dec 20)

## Repeat Exam

- the repeat exam will be on
**Thu, Apr 12, 2012**at**13.00**in room**MI 02.07.023**; the repeat exam will again be a written exam - Working time will be 90 minutes.
- 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! - Please use only blue or black ink during the exam.
- Exam topics are all topics covered during the lectures except Chapter 9 (Weighted Graphs); see, in particular, the worksheets for this course

# Lecture Notes and Material

## Slides from the Lecture

- Introduction - Algorithms, Fibonacci example (Oct 25)
- slides
- Sorting (Nov 8, Nov 15, Nov 22)
- slides (lecture on Nov 15 from 9.00 to 9.45, because of Student General Assembly)
- Recurrences (Nov 22, Nov 29)
- slides
- More Sorting (Nov 29)
- slides
- Parallel Algorithms and PRAM (Dec 6)
- slides
- Parallel Sorting, Odd-Even MergeSort (Dec 13)
- slides
- Searching (Dec 20)
- slides
- AVL trees(Jan 10)
- slides
- Hash Tables (Jan 17)
- slides
- Graphs (Jan 24)
- slides
- Weighted Graphs (Jan 31)
- slides (as the lecture on Feb 7 was cancelled, this module will not be part of the exam)

## Worksheets

- O-notation, etc. (Nov 8)
- worksheet and solution
- Complexity and Sorting (Nov 15)
- worksheet and solution
- MergeSort and Recurrences (Nov 22)
- worksheet and solution
- Parallel Scalar Product and Matrix-Vector Multiplication (Dec 6)
- worksheet and solution
- Sequential and Binary Search (Dec 20)
- worksheet and solution
- AVL trees (Jan 10)
- worksheet and solution
- Hashing (Jan 17)
- worksheet and solution
- Graphs (Jan 31)
- worksheet and solution

## Literature

- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms; MIT Press
- Berman, Paul: Algorithms: Sequential, Parallel, and Distributed; Cengage Learning Emea 2004
- Heun: Grundlegende Algorithmen; Vieweg 2000
- Sedgewick: Algorithms; Pearson Education
- Shackleford, Computing and Algorithms; Addison Wesley Longman
- Kleinberg, Tardos: Algorithm Design; Pearson Education