Fundamental Algorithms - Winter 10: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 41: | Line 41: | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg3.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg3sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg3.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg3sol.pdf solution] | ||
; Recurrences - Complexity of MergeSort and QuickSort : Nov 23 | ; Recurrences - Complexity of MergeSort and QuickSort : Nov 23 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg4.pdf worksheet] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg4.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg4sol.pdf solution] | ||
; CountingSort : Nov 30 | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg5.pdf worksheet] | |||
<!-- | <!-- | ||
| Line 61: | Line 63: | ||
== Worksheets == | == Worksheets == | ||
, [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg5sol.pdf solution] | |||
; Selecting : Dec 4 | ; Selecting : Dec 4 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg6.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg6sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg6.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg6sol.pdf solution] | ||
Revision as of 22:30, 29 November 2010
- Term
- Winter 10
- Lecturer
- Dr. rer. nat. 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
- written exam
- 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
In the hope that the file system problems will eventually be resolved, a few announcements:
- On Tuesday, Nov. 16, we will have only 45 minutes lecture due to SVV (Studentische Vollversammlung [1] in MW2001)
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.2011)
- Recurrences
- Nov 30
- slides
- More Sorting
- Nov 30
- slides
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
Literature
Recommended:
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press
Also helpful:
- Heun: Grundlegende Algorithmen, Vieweg 2000
- Sedgewick: Algorithms, Pearson Education
- Shackleford, Computing and Algorithms, Addison Wesley Longman
- Kleinberg, Tardos: Algorithm Design, Pearson Education