Fundamental Algorithms - Winter 14

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

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