Fundamental Algorithms - Winter 11

From Sccswiki
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

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