Fundamental Algorithms - Winter 10

From Sccswiki
Jump to navigation Jump to search
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

Also helpful:

  • Heun: Grundlegende Algorithmen, Vieweg 2000
  • Sedgewick: Algorithms, Pearson Education
  • Shackleford, Computing and Algorithms, Addison Wesley Longman
  • Kleinberg, Tardos: Algorithm Design, Pearson Education