Fundamental Algorithms - Winter 14: Difference between revisions
Jump to navigation
Jump to search
m (→Worksheets) |
m (→Worksheets) |
||
| Line 61: | Line 61: | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg1.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg1sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg1.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg1sol.pdf solution] | ||
; Complexity and Sorting (Oct 20) | ; Complexity and Sorting (Oct 20) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg2.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg2.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg2sol.pdf solution] (corrected Ex. 1) | ||
; MergeSort (Oct 27) | ; MergeSort (Oct 27) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg3.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg3.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg3sol.pdf solution] | ||
<!-- | <!-- | ||
; Recurrences(Nov 11) | ; Recurrences(Nov 11) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg4.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg4sol.pdf solution] (with slightly updated solution for Exercise 1) | ||
; PRAM - Linear Algebra and Prefix Problem (Nov 18) | ; PRAM - Linear Algebra and Prefix Problem (Nov 18) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg5.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg5sol.pdf solution] (slightly updated; leaves Ex. 3 for next week) | ||
; PRAM - Prefix Problem and BucketSort (Nov 25) | ; PRAM - Prefix Problem and BucketSort (Nov 25) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg6.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg6sol.pdf solution] (includes Ex. 3 from previous week) | ||
; Sequential and Binary Search (Dec 2) | ; Sequential and Binary Search (Dec 2) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg7.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg7sol.pdf solution] | ||
; AVL trees (Dec 9) | ; AVL trees (Dec 9) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg8.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg8sol.pdf solution] | ||
; Hashing (Dec 16) | ; Hashing (Dec 16) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg9.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg9sol.pdf solution] | ||
; Graphs (Jan 13) | ; Graphs (Jan 13) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg10.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg10sol.pdf solution] | ||
; Hypergraphs and Bipartite Graphs (Jan 20) | ; Hypergraphs and Bipartite Graphs (Jan 20) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg11.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/worksheets/fundalg11sol.pdf solution] | ||
--> | --> | ||
Revision as of 08:47, 31 October 2014
- Term
- Winter 14
- Lecturer
- Prof. Dr. Michael Bader
- Time and Place
- Mon 8.30-10.00, lecture hall MI HS 3 (first lecture on Oct 13, 8.30)
- Audience
- Computational Science and Engineering; Biomedical Computing (elective)
- Tutorials
- ---
- Exam
- written exam at end of semester
- Semesterwochenstunden / ECTS Credits
- 2 SWS (2V) / 3 ECTS
- TUMonline
- https://campus.tum.de/tumonline/lv.detail?clvnr=950160214 (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.
Lecture Notes and Material
will be made available during the course.
Lecture Slides
- Introduction - Algorithms, Fibonacci example, Asymptotics (Oct 13, 20)
- slides
- Sorting - InsertSort, MergeSort, QuickSort, BucketSort (Oct 20, 27; Nov 3)
- slides
- Recurrences (Nov 3)
- slides
Worksheets
- O-notation, etc. (Oct 13)
- worksheet and solution
- Complexity and Sorting (Oct 20)
- worksheet and solution (corrected Ex. 1)
- MergeSort (Oct 27)
- 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