Fundamental Algorithms - Winter 11: Difference between revisions
Jump to navigation
Jump to search
mNo edit summary |
No edit summary |
||
| Line 22: | Line 22: | ||
== Slides from the Lecture == | == Slides from the Lecture == | ||
; Introduction - Algorithms, Fibonacci example (Oct 25) | ; Introduction - Algorithms, Fibonacci example (Oct 25) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg01.pdf slides] | ||
; Sorting (Nov 8, Nov 15, Nov 22) | ; Sorting (Nov 8, Nov 15, Nov 22) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg02.pdf slides] (lecture on Nov 15 from 9.00 to 9.45, because of Student General Assembly) | ||
; Recurrences (Nov 22, Nov 29) | ; Recurrences (Nov 22, Nov 29) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg02b.pdf slides] | ||
; More Sorting (Nov 29) | ; More Sorting (Nov 29) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg03.pdf slides] | ||
; Parallel Algorithms and PRAM (Dec 6) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg04.pdf slides] | |||
== Worksheets == | == Worksheets == | ||
; O-notation, etc. (Nov 8) | ; O-notation, etc. (Nov 8) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg1.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg1sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg1.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg1sol.pdf solution] | ||
; Complexity and Sorting (Nov 15) | ; Complexity and Sorting (Nov 15) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg2.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg2sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/WS11/fundalg2.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg2sol.pdf solution] | ||
; MergeSort and Recurrences (Nov 22) | ; MergeSort and Recurrences (Nov 22) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg3.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg3sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/WS11/fundalg3.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg3sol.pdf solution] | ||
; (no worksheet on Nov 29) | ; (no worksheet on Nov 29) | ||
Revision as of 13:06, 1 December 2011
- Term
- Winter 11
- Lecturer
- Prof. Dr. Michael Bader
- Time and Place
- Tuesday, 9:00-10:30, (MI 02.07.023); first lecture: Oct 25
- Audience
- Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing (elective)
- Tutorials
- t.b.a. (no compulsory tutorials; there might be a few extra lessons on a voluntary basis)
- 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
- Foundations of parallel algorithms and simple models of parallel computation
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
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
- (no worksheet on Nov 29)
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