Fundamental Algorithms - Winter 09: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 6: | Line 6: | ||
| audience = Computational Science and Engineering, 1st semester (Module [http://drehscheibe.in.tum.de/myintum/kurs_verwaltung/cm.html?id=IN2157 IN2157]); Biomedical Computing | | audience = Computational Science and Engineering, 1st semester (Module [http://drehscheibe.in.tum.de/myintum/kurs_verwaltung/cm.html?id=IN2157 IN2157]); Biomedical Computing | ||
| tutorials = - | | tutorials = - | ||
| exam = written exam ( | | exam = written exam (preliminary date: Feb 15, 2010) | ||
}} | }} | ||
| Line 15: | Line 15: | ||
* Sorting: Bubble-Sort, Merge-Sort, Quick-Sort, Median-Algorithms, Lower Bounds, etc.: sorting in parallel | * Sorting: Bubble-Sort, Merge-Sort, Quick-Sort, Median-Algorithms, Lower Bounds, etc.: sorting in parallel | ||
* Searching: Hashing, Search Tress, etc. | * 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) | * Graph Algorithms: Transitive Closure, Shortest Path Problems, Minimum Spanning Trees (if time allows) | ||
| Line 28: | Line 28: | ||
; More Sorting : Nov 20, Nov 27 | ; More Sorting : Nov 20, Nov 27 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg03.pdf slides] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg03.pdf slides] | ||
; Selecting : Dec 04 | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg04.pdf slides] | |||
== Worksheets == | == Worksheets == | ||
| Line 39: | Line 41: | ||
; CountingSort : Nov 20 | ; CountingSort : Nov 20 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg5.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg5sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg5.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg5sol.pdf solution] | ||
; | ; Selecting : Nov 27 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg6.pdf worksheet] | |||
== Further Material == | == Further Material == | ||
Revision as of 12:23, 4 December 2009
- Term
- Winter 09
- Lecturer
- Dr. Michael Bader
- Time and Place
- Friday, 9-11, lecture hall MI 03.07.023 (!room change!)
- Audience
- Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing
- Tutorials
- -
- Exam
- written exam (preliminary date: Feb 15, 2010)
- 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)
Lecture Notes and Material
Slides from the Lecture
- Introduction - Algorithms, Fibonacci example, growth of functions
- Oct 30, Nov 6
- slides
- Sorting Algorithms
- Nov 6, Nov 13
- slides
- More Sorting
- Nov 20, Nov 27
- slides
- Selecting
- Dec 04
- slides
Worksheets
- Growth of functions
- Oct 30
- worksheet, solution
- Complexity of Algorithms, Sorting on Matrices
- Nov 6
- worksheet, solution
- Recurrences - Complexity of MergeSort and QuickSort
- Nov 13
- worksheet, solution
- CountingSort
- Nov 20
- worksheet, solution
- Selecting
- Nov 27
- worksheet
Further Material
Literature
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press
- Heun: Grundlegende Algorithmen, Vieweg 2000
- Sedgewick: Algorithms, Pearson Education
- Shackleford, Computing and Algorithms, Addison Wesley Longman
- Kleinberg, Tardos: Algorithm Design, Pearson Education