Fundamental Algorithms - Winter 10: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (15 intermediate revisions by the same user not shown) | |||
| Line 6: | Line 6: | ||
| audience = Computational Science and Engineering, 1st semester (Module [http://drehscheibe.in.tum.de/myintum/kurs_verwaltung/cm.html?id=IN2157 IN2157]); Biomedical Computing | | audience = Computational Science and Engineering, 1st semester (Module [http://drehscheibe.in.tum.de/myintum/kurs_verwaltung/cm.html?id=IN2157 IN2157]); Biomedical Computing | ||
| tutorials = - | | tutorials = - | ||
| exam = written exam (date: Feb 11, 2011; 16:30-18:30 in room MW(!) 1050) | | exam = <!--written exam (date: Feb 11, 2011; 16:30-18:30 in room MW(!) 1050)-->repeat exam (date: May 02, 2011; 16:30-18:00 in room MI 02.07.023 | ||
}} | }} | ||
| Line 19: | Line 19: | ||
= Current News = | = Current News = | ||
* | * '''Master Thesis? Student project?''' We're always looking for you! See [[Student Projects]] and/or ask me! | ||
* See the updates on corrections. | |||
* Exam details below. | |||
= Lecture Notes and Material = | = Lecture Notes and Material = | ||
| Line 27: | Line 29: | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg01.pdf slides] (Update loop invariants, 08.11.) | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg01.pdf slides] (Update loop invariants, 08.11.) | ||
; Sorting Algorithms : Nov 9, 16, 23 | ; Sorting Algorithms : Nov 9, 16, 23 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg02.pdf slides] (few typos corrected, 15.11. | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg02.pdf slides] (few typos corrected, 15.11. - update last slide, 24.11. - corrected partitioning algorithm, Python implementations available at [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/QuickSort.py], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/Partition.py], call with "Python filename.py", 3.2.) | ||
; Recurrences : Nov 30 | ; Recurrences : Nov 30 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg02b.pdf slides] (corrected prerequisites for Master Theorem, 6.12.) | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg02b.pdf slides] (corrected prerequisites for Master Theorem, 6.12.) | ||
| Line 35: | Line 37: | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg04.pdf slides] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg04.pdf slides] | ||
; Random Access Machines : Dec 21 | ; Random Access Machines : Dec 21 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg05.pdf slides] (introduced Vector x, 21.12.) | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg05.pdf slides] (introduced Vector x, 21.12.) - NEW: [http://www5.in.tum.de/cgi-bin/FundAlg/RAMsimulator.py RAM Simulator online!] | ||
; The PRAM Model : Jan 11 | ; The PRAM Model : Jan 11 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg06.pdf slides] (Update of three slides, 12.01.) | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg06.pdf slides] (Update of three slides, 12.01.) | ||
| Line 42: | Line 44: | ||
; AVL Trees : Jan 25 | ; AVL Trees : Jan 25 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg08.pdf slides] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg08.pdf slides] | ||
; Hashing : Feb | ; Hashing : Feb 1 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg09.pdf slides] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg09.pdf slides] (update formula multiplication method, numbers on slide 19, 1.2.) | ||
== Worksheets == | == Worksheets == | ||
| Line 60: | Line 61: | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg6.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg6sol.pdf solution] (27.1. corrected solution for exercise 2: call to larger partition) | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg6.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg6sol.pdf solution] (27.1. corrected solution for exercise 2: call to larger partition) | ||
; RAM : Dec 21 | ; RAM : Dec 21 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg7.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg7sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg7.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg7sol.pdf solution] (31.1. corrected line 16 RAM program: "=" -> ">"; 7.2. corrected resulting line 15, R6-R7 -> R7-R6 (thanks for both comments); 9.2. sorry, changed everything back again: the original version was correct, I included a full list of all RAM states for reference, note the definition of the subtraction!) | ||
; PRAM : Jan 8 | ; PRAM : Jan 8 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg8.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg8sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg8.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg8sol.pdf solution] (1.2. corrected typeos in ScalarProductPar and MatrixVectorProductEREW) | ||
; Searching : Jan 18 | ; Searching : Jan 18 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg9.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg9sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg9.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg9sol.pdf solution] | ||
; AVL trees : Jan 25 | ; AVL trees : Jan 25 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg10.pdf worksheet] (28.1. corrected typeo: first "TreeInsert(5)" should be "TreeDelete(5)" | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg10.pdf worksheet] (28.1. corrected typeo: first "TreeInsert(5)" should be "TreeDelete(5)", [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg10sol.pdf solution] | ||
; Hashing : Feb 1 | |||
, [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg10sol.pdf solution] | |||
; Hashing : | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg11.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg11sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg11.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg11sol.pdf solution] | ||
= Exam = | = Exam = | ||
<!-- | |||
* Date of final exam: Friday, Feb 11, 16:30-18:30 in room '''MW(!)''' 1050, see TUMonline | * Date of final exam: Friday, Feb 11, 16:30-18:30 in room '''MW(!)''' 1050, see TUMonline | ||
--> | |||
* Date of repeat exam: Moday, May 02, 16:30-18:30 in room MI 02.07.023, see TUMonline | |||
* 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! | * 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! | ||
* Exam topics are all topics covered during the lectures; see, in particular, the worksheets for this course | * Exam topics are all topics covered during the lectures; see, in particular, the worksheets for this course | ||
<!-- | |||
* Repeat exam: a repeat exam will offered (only for students who failed the regular exam) in April 2011. The exam will be written. | * Repeat exam: a repeat exam will offered (only for students who failed the regular exam) in April 2011. The exam will be written. | ||
* Possibility to view your exam results will be given on '''Feb 22, 09:30-11:30, in room 02.05.011'''. | * Possibility to view your exam results will be given on '''Feb 22, 09:30-11:30, in room 02.05.011'''. | ||
--> | |||
<!-- | <!-- | ||
| Line 91: | Line 91: | ||
--> | --> | ||
= Literature = | |||
Recommended: | Recommended: | ||
Latest revision as of 15:43, 1 March 2011
- Term
- Winter 10
- Lecturer
- Dr. 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
- repeat exam (date: May 02, 2011; 16:30-18:00 in room MI 02.07.023
- 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
- Master Thesis? Student project? We're always looking for you! See Student Projects and/or ask me!
- See the updates on corrections.
- Exam details below.
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. - corrected partitioning algorithm, Python implementations available at [1], [2], call with "Python filename.py", 3.2.)
- Recurrences
- Nov 30
- slides (corrected prerequisites for Master Theorem, 6.12.)
- More Sorting
- Dec 7, 14
- slides
- Selecting
- Dec 14, 21
- slides
- Random Access Machines
- Dec 21
- slides (introduced Vector x, 21.12.) - NEW: RAM Simulator online!
- The PRAM Model
- Jan 11
- slides (Update of three slides, 12.01.)
- Searching
- Jan 18
- slides (update assumptions on slide 4, 18.01.)
- AVL Trees
- Jan 25
- slides
- Hashing
- Feb 1
- slides (update formula multiplication method, numbers on slide 19, 1.2.)
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, solution (27.1. corrected error in solution 2a, third loop)
- Recurrences
- Dec 07
- worksheet, solution
- Selecting
- Dec 14
- worksheet, solution (27.1. corrected solution for exercise 2: call to larger partition)
- RAM
- Dec 21
- worksheet, solution (31.1. corrected line 16 RAM program: "=" -> ">"; 7.2. corrected resulting line 15, R6-R7 -> R7-R6 (thanks for both comments); 9.2. sorry, changed everything back again: the original version was correct, I included a full list of all RAM states for reference, note the definition of the subtraction!)
- PRAM
- Jan 8
- worksheet, solution (1.2. corrected typeos in ScalarProductPar and MatrixVectorProductEREW)
- Searching
- Jan 18
- worksheet, solution
- AVL trees
- Jan 25
- worksheet (28.1. corrected typeo: first "TreeInsert(5)" should be "TreeDelete(5)", solution
- Hashing
- Feb 1
- worksheet, solution
Exam
- Date of repeat exam: Moday, May 02, 16:30-18:30 in room MI 02.07.023, see TUMonline
- 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!
- Exam topics are all topics covered during the lectures; see, in particular, the worksheets for this course
Literature
Recommended:
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press
For parallel RAM:
- Berman, Paul: Fundamentals of Sequential and Parallel Algorithms
Also helpful:
- Heun: Grundlegende Algorithmen, Vieweg 2000
- Sedgewick: Algorithms, Pearson Education
- Shackleford, Computing and Algorithms, Addison Wesley Longman
- Kleinberg, Tardos: Algorithm Design, Pearson Education