Fundamental Algorithms - Winter 11: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (13 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
| credits = 2 SWS (2V) / 3 Credits | | credits = 2 SWS (2V) / 3 Credits | ||
| audience = Computational Science and Engineering, 1st semester (Module [http://drehscheibe.in.tum.de/myintum/kurs_verwaltung/cm.html?id=IN2157 IN2157]); Biomedical Computing (elective) | | audience = Computational Science and Engineering, 1st semester (Module [http://drehscheibe.in.tum.de/myintum/kurs_verwaltung/cm.html?id=IN2157 IN2157]); Biomedical Computing (elective) | ||
| tutorials = | | tutorials = --- | ||
| exam = written exam | | exam = written exam, Thu, Feb 23, 2012 at 14.00 in room MW 0350; repeat exam (written) on Thu, Apr 12, 2012, at 13.00 in room MI 02.07.02 | ||
}} | }} | ||
| Line 17: | Line 17: | ||
* Arithmetic Problems: parallel prefix computation, parallel matrix and vector operations | * Arithmetic Problems: parallel prefix computation, parallel matrix and vector operations | ||
* Foundations of parallel algorithms and simple models of parallel computation | * Foundations of parallel algorithms and simple models of parallel computation | ||
* Algorithms on (weighted) graphs: traversals, shortest paths, etc. | |||
= Announcements = | = Announcements = | ||
* '''Exam Review''': on '''Mon, Mar 19, 2012''' from 15.30-17.00, you can look into your exam (for corrections and grading, e.g.); further opportunities for exam review will be offered, if there is respective demand. | |||
* '''Change of time''': Lecture was moved from 9.00-10.30 to 9.30-11.00 (starting on Dec 20) | * '''Change of time''': Lecture was moved from 9.00-10.30 to 9.30-11.00 (starting on Dec 20) | ||
* ''' | |||
== Repeat Exam == | |||
* the repeat exam will be on '''Thu, Apr 12, 2012''' at '''13.00''' in room '''MI 02.07.023'''; the repeat exam will again be a written exam | |||
* Working time will be 90 minutes. | |||
* Helping material: you are allowed to use '''one sheet (size A4) of paper''' with '''hand-written(!) notes''' during the exam. Any further helping material (books, calculators, etc.) is forbidden! | |||
* Please use only blue or black ink during the exam. | |||
* Exam topics are all topics covered during the lectures except Chapter 9 (Weighted Graphs); see, in particular, the worksheets for this course | |||
= Lecture Notes and Material = | = Lecture Notes and Material = | ||
| Line 37: | Line 46: | ||
; Parallel Sorting, Odd-Even MergeSort (Dec 13) | ; Parallel Sorting, Odd-Even MergeSort (Dec 13) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg03.pdf slides] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg03.pdf slides] | ||
; Searching (Dec 20) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg05.pdf slides] | |||
; AVL trees(Jan 10) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg06.pdf slides] | |||
; Hash Tables (Jan 17) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg07.pdf slides] | |||
; Graphs (Jan 24) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg08.pdf slides] | |||
; Weighted Graphs (Jan 31) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg09.pdf slides] (as the lecture on Feb 7 was cancelled, this module will not be part of the exam) | |||
== Worksheets == | == Worksheets == | ||
| Line 45: | Line 64: | ||
; MergeSort and Recurrences (Nov 22) | ; MergeSort and Recurrences (Nov 22) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg3.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg3sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg3.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg3sol.pdf solution] | ||
; Parallel Scalar Product and Matrix-Vector Multiplication (Dec 6) | ; Parallel Scalar Product and Matrix-Vector Multiplication (Dec 6) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg4.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg4sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg4.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg4sol.pdf solution] | ||
; Sequential and Binary Search (Dec 20) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg5.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg5sol.pdf solution] | |||
; AVL trees (Jan 10) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg6.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg6sol.pdf solution] | |||
; Hashing (Jan 17) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg7.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg7sol.pdf solution] | |||
; Graphs (Jan 31) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg8.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg8sol.pdf solution] | |||
== Literature == | == Literature == | ||
Latest revision as of 08:15, 6 March 2012
- Term
- Winter 11
- Lecturer
- Prof. Dr. Michael Bader
- Time and Place
- Tuesday, 9:30-11:00 (MI 02.07.023); first lecture: Oct 25
- Audience
- Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing (elective)
- Tutorials
- ---
- Exam
- written exam, Thu, Feb 23, 2012 at 14.00 in room MW 0350; repeat exam (written) on Thu, Apr 12, 2012, at 13.00 in room MI 02.07.02
- 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
- Algorithms on (weighted) graphs: traversals, shortest paths, etc.
Announcements
- Exam Review: on Mon, Mar 19, 2012 from 15.30-17.00, you can look into your exam (for corrections and grading, e.g.); further opportunities for exam review will be offered, if there is respective demand.
- Change of time: Lecture was moved from 9.00-10.30 to 9.30-11.00 (starting on Dec 20)
Repeat Exam
- the repeat exam will be on Thu, Apr 12, 2012 at 13.00 in room MI 02.07.023; the repeat exam will again be a written exam
- Working time will be 90 minutes.
- Helping material: you are allowed to use one sheet (size A4) of paper with hand-written(!) notes during the exam. Any further helping material (books, calculators, etc.) is forbidden!
- Please use only blue or black ink during the exam.
- Exam topics are all topics covered during the lectures except Chapter 9 (Weighted Graphs); see, in particular, the worksheets for this course
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
- Parallel Sorting, Odd-Even MergeSort (Dec 13)
- slides
- Searching (Dec 20)
- slides
- AVL trees(Jan 10)
- slides
- Hash Tables (Jan 17)
- slides
- Graphs (Jan 24)
- slides
- Weighted Graphs (Jan 31)
- slides (as the lecture on Feb 7 was cancelled, this module will not be part of the exam)
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
- Parallel Scalar Product and Matrix-Vector Multiplication (Dec 6)
- worksheet and solution
- Sequential and Binary Search (Dec 20)
- worksheet and solution
- AVL trees (Jan 10)
- worksheet and solution
- Hashing (Jan 17)
- worksheet and solution
- Graphs (Jan 31)
- 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