Fundamental Algorithms - Winter 13: Difference between revisions
Jump to navigation
Jump to search
mNo edit summary |
|||
| Line 6: | Line 6: | ||
| audience = Computational Science and Engineering; Biomedical Computing (elective) | | audience = Computational Science and Engineering; Biomedical Computing (elective) | ||
| tutorials = --- | | tutorials = --- | ||
| exam = written exam | | exam = written exam: Mon, Feb 3, 2014 (further details t.b.a.) | ||
| tumonline = https://campus.tum.de/tumonline/lv.detail?clvnr=950121698 (lecture),<br> https://campus.tum.de/tumonline/wbStpModHB.detailPage?&pKnotenNr=458187 (module description) | | tumonline = https://campus.tum.de/tumonline/lv.detail?clvnr=950121698 (lecture),<br> https://campus.tum.de/tumonline/wbStpModHB.detailPage?&pKnotenNr=458187 (module description) | ||
}} | }} | ||
| Line 62: | Line 62: | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg3.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg3sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg3.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg3sol.pdf solution] | ||
; Recurrences(Nov 11) | ; Recurrences(Nov 11) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg4.pdf worksheet] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg4.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg4sol.pdf solution] | ||
<!-- | <!-- | ||
; Parallel Scalar Product and Matrix-Vector Multiplication (Dec 6) | ; Parallel Scalar Product and Matrix-Vector Multiplication (Dec 6) | ||
Revision as of 14:55, 15 November 2013
- Term
- Winter 13
- Lecturer
- Prof. Dr. Michael Bader
- Time and Place
- Mon 8.30-10.00, lecture hall MI HS 3 (first lecture on Oct 21, 8.30)
- Audience
- Computational Science and Engineering; Biomedical Computing (elective)
- Tutorials
- ---
- Exam
- written exam: Mon, Feb 3, 2014 (further details t.b.a.)
- Semesterwochenstunden / ECTS Credits
- 2 SWS (2V) / 3 ECTS
- TUMonline
- https://campus.tum.de/tumonline/lv.detail?clvnr=950121698 (lecture),
https://campus.tum.de/tumonline/wbStpModHB.detailPage?&pKnotenNr=458187 (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.
Announcements
- in the slot on Dec 23, we will do a short (40min) test exam, with discussion of solutions afterwards;
participation is entirely optional (questions and solutions will be made available towards the end of the Christmas holidays) - the lectures will start on Monday, Oct 21 (no lecture on Oct 14, due to semester opening)
Lecture Notes and Material
will be made available here throughout the lecture ...
Lecture Slides
- Introduction - Algorithms, Fibonacci example, Asymptotics (Oct 21, Oct 28)
- slides
- Sorting - InsertSort, MergeSort, QuickSort (Oct 28, Nov 4, Nov 11)
- slides (with corrected proof for InsertionSort)
- Recurrences (Nov 11)
- slides
Worksheets
- O-notation, etc. (Oct 21)
- worksheet and solution
- Complexity and Sorting (Oct 28)
- worksheet and solution
- MergeSort (Nov 4)
- worksheet and solution
- Recurrences(Nov 11)
- worksheet and solution
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