Fundamental Algorithms - Winter 09: Difference between revisions

From Sccswiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(21 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{Lecture
{{Lecture
| term = Winter 09
| term = Winter 09
| lecturer = [[Michael Bader|Dr. Michael Bader]]
| lecturer = [[Michael Bader|Jun.-Prof. Dr. Michael Bader]]
| timeplace = Friday, 9-11, lecture hall MI 00.13.009A (first lecture: Oct 30)
| timeplace = Friday, 9-11, lecture hall MI 03.07.023 ('''!room change!''')
| credits = 2 SWS (2V) / 3 Credits
| credits = 2 SWS (2V) / 3 Credits
| audience = Computational Science and Engineering, 1st semester (Module [https://www.in.tum.de/myintum/kurs_verwaltung/cm.html?id=IN2005 IN2005]); 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 (t.b.a.)
| exam = written exam (date: Feb 12, 2010; 10-12 in room MI 02.07.23)
}}
}}


Line 15: Line 15:
* Sorting: Bubble-Sort, Merge-Sort, Quick-Sort, Median-Algorithms, Lower Bounds, etc.: sorting in parallel
* Sorting: Bubble-Sort, Merge-Sort, Quick-Sort, Median-Algorithms, Lower Bounds, etc.: sorting in parallel
* Searching: Hashing, Search Tress, etc.
* Searching: Hashing, Search Tress, etc.
* Artithmetic Problems: parallel prefix computation, parallel matrix and vector operations
* Arithmetic Problems: parallel prefix computation, parallel matrix and vector operations
* Graph Algorithms: Transitive Closure, Shortest Path Problems, Minimum Spanning Trees (if time allows)
* Graph Algorithms: Transitive Closure, Shortest Path Problems, Minimum Spanning Trees (if time allows)
= Lecture Notes and Material =
== Slides from the Lecture ==
; Introduction - Algorithms, Fibonacci example, growth of functions : Oct 30, Nov 6
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg01.pdf slides]
; Sorting Algorithms : Nov 6, Nov 13
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg02.pdf slides]
; More Sorting : Nov 20, Nov 27
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg03.pdf slides]
; Selecting : Dec 04
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg04.pdf slides]
; Random Access Machines : Dec 11
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg05.pdf slides]
; Recurrences : Dec 18
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg_recurrence.pdf slides]
; The PRAM Model : Jan 8
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg06.pdf slides]
; Searching : Jan 15
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg07.pdf slides]
; AVL Trees : Jan 22
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg08.pdf slides]
; Hashing : Jan 29
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/slides/fundalg09.pdf slides]
== Worksheets ==
; Growth of functions : Oct 30
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg2.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg2sol.pdf solution]
; Complexity of Algorithms, Sorting on Matrices : Nov 6
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg3.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg3sol.pdf solution]
; Recurrences - Complexity of MergeSort and QuickSort : Nov 13
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg4.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg4sol.pdf solution]
; CountingSort : Nov 20
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg5.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg5sol.pdf solution]
; Selecting :  Dec 4
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg6.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg6sol.pdf solution]
; RAM :  Dec 11
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg7.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg7sol.pdf solution]
; PRAM :  Jan 8
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg8.pdf worksheet]
; Searching :  Jan 15
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg9.pdf worksheet]; for solution, see [http://www.cse.tum.de/vtc/FundAlg/index.html skript on virtual teaching centre] (sections on searching on binary search trees)
; AVL trees :  Jan 22
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg10.pdf worksheet], [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg10sol.pdf solution]
; Hashing :  Jan 29
: [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 =
* Date of final exam: Friday, Feb 12, 10-12 in room MI 02.07.023
* 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
* Repeat exam: a repeat exam will offered (only for students who failed the regular exam) in April 2010. The exam will be written or oral, depending on the number of participants.
* Possibility to view your exam results will be given on '''March 8, 14-16, in office 02.05.057'''.
== Further Material ==
* [http://www.cse.tum.de/vtc/FundAlg/index.html Lecture notes (on CSE Teaching Centre)]
== Literature ==
* Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press
* Heun: Grundlegende Algorithmen, Vieweg 2000
* Sedgewick: Algorithms, Pearson Education
* Shackleford, Computing and Algorithms, Addison Wesley Longman
* Kleinberg, Tardos: Algorithm Design, Pearson Education

Latest revision as of 11:44, 19 February 2010

Term
Winter 09
Lecturer
Jun.-Prof. Dr. Michael Bader
Time and Place
Friday, 9-11, lecture hall MI 03.07.023 (!room change!)
Audience
Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing
Tutorials
-
Exam
written exam (date: Feb 12, 2010; 10-12 in room MI 02.07.23)
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)

Lecture Notes and Material

Slides from the Lecture

Introduction - Algorithms, Fibonacci example, growth of functions
Oct 30, Nov 6
slides
Sorting Algorithms
Nov 6, Nov 13
slides
More Sorting
Nov 20, Nov 27
slides
Selecting
Dec 04
slides
Random Access Machines
Dec 11
slides
Recurrences
Dec 18
slides
The PRAM Model
Jan 8
slides
Searching
Jan 15
slides
AVL Trees
Jan 22
slides
Hashing
Jan 29
slides

Worksheets

Growth of functions
Oct 30
worksheet, solution
Complexity of Algorithms, Sorting on Matrices
Nov 6
worksheet, solution
Recurrences - Complexity of MergeSort and QuickSort
Nov 13
worksheet, solution
CountingSort
Nov 20
worksheet, solution
Selecting
Dec 4
worksheet, solution
RAM
Dec 11
worksheet, solution
PRAM
Jan 8
worksheet
Searching
Jan 15
worksheet; for solution, see skript on virtual teaching centre (sections on searching on binary search trees)
AVL trees
Jan 22
worksheet, solution
Hashing
Jan 29
worksheet, solution

Exam

  • Date of final exam: Friday, Feb 12, 10-12 in room MI 02.07.023
  • 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
  • Repeat exam: a repeat exam will offered (only for students who failed the regular exam) in April 2010. The exam will be written or oral, depending on the number of participants.
  • Possibility to view your exam results will be given on March 8, 14-16, in office 02.05.057.

Further Material

Literature

  • Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press
  • Heun: Grundlegende Algorithmen, Vieweg 2000
  • Sedgewick: Algorithms, Pearson Education
  • Shackleford, Computing and Algorithms, Addison Wesley Longman
  • Kleinberg, Tardos: Algorithm Design, Pearson Education
Retrieved from "https://www5.in.tum.de/wiki/index.php?title=Fundamental_Algorithms_-_Winter_09&oldid=6108"