# Fundamental Algorithms - Winter 14

Jump to navigation
Jump to search

**Term**- Winter 14
**Lecturer**- Prof. Dr. Michael Bader
**Time and Place**- Mon 8.30-10.00, lecture hall MI HS 3 (first lecture on Oct 13, 8.30)
**Audience**- Computational Science and Engineering; Biomedical Computing (elective)
**Tutorials**- ---
**Exam**- written exam, repeat on
**Wed, Apr 15, 2015**at**16.30**in lecture room**MI 02.07.23**(see details below) **Semesterwochenstunden / ECTS Credits**- 2 SWS (2V) / 3 ECTS
**TUMonline**- https://campus.tum.de/tumonline/lv.detail?clvnr=950160214 (lecture),

https://campus.tum.de/tumonline/WBMODHB.wbShowMHBReadOnly?pKnotenNr=458187&pOrgNr=14189 (module description)

## Contents

# Contents

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.

# Lecture Notes and Material

## Lecture Slides

- Introduction - Algorithms, Fibonacci example, Asymptotics (Oct 13, 20)
- slides
- Sorting - InsertSort, MergeSort, QuickSort, BucketSort (Oct 20, 27; Nov 3)
- slides
- (corrected partitioning algorithm, now fully according to Hoare's algorithm; the previous partitioning algorithm only worked, if all elements of A have distinct size)
- Recurrences (Nov 3)
- slides
- Searching (Nov 10, 17)
- slides
- AVL trees(Nov 10, 17)
- slides
- Hash Tables (Nov 24)
- slides
- Parallel Algorithms and PRAM (Dec 1, 8)
- slides
- Parallel Sorting, Odd-Even MergeSort (Dec 8, 15)
- slides
- Graphs (Dec 15, Jan 12)
- slides
- Weighted Graphs (Jan 12, Jan 19)
- slides
- Exam (Jan 26)
- Due to the exam on Jan 26, there will be no lecture on that day

## Worksheets

- O-notation, etc. (Oct 13)
- worksheet and solution
- Complexity and Sorting (Oct 20)
- worksheet and solution (corrected Ex. 1)
- MergeSort (Oct 27)
- worksheet and solution
- Recurrences(Nov 3)
- worksheet and solution
- Sequential and Binary Search (Nov 10)
- worksheet and solution
- AVL trees (Nov 17)
- worksheet and solution
- Hashing (Nov 24)
- worksheet and solution
- PRAM - Linear Algebra and Prefix Problem (Dec 1)
- worksheet and solution
- PRAM - Prefix Problem and BucketSort (Dec 8)
- worksheet and solution
- Graphs (Dec 15)
- worksheet and solution
- Hypergraphs and Bipartite Graphs (Jan 19, optional)
- worksheet and solution

## Exam

- a
**repeat exam**will be offered on**Wed, Apr 15, 16.30 (MI 02.07.023)**- the exam will be written
- all rules (helping material, etc.) are identical to the first exam

- please by at the lecture hall in time (16.15) - the exam will start precisely at 16.30 and there will be announcements before starting
- Working time will be 90 minutes.
- Helping material: you are allowed to use
**one sheet (size A4) of paper**with**hand-written(!) notes**(on both sides) 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; see, in particular, the worksheets for this course
- Dijkstra and Prim Algorithm from Chapter 9 (Weighted Graphs) are excluded from the exam

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