Fundamental Algorithms - Winter 14: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| (36 intermediate revisions by the same user not shown) | |||
| 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 at | | exam = written exam, repeat on '''Wed, Apr 15, 2015''' at '''16.30''' in lecture room '''MI 02.07.23''' (see details below) | ||
| tumonline = https://campus.tum.de/tumonline/lv.detail?clvnr=950160214 (lecture),<br> https://campus.tum.de/tumonline/ | | tumonline = https://campus.tum.de/tumonline/lv.detail?clvnr=950160214 (lecture),<br> https://campus.tum.de/tumonline/WBMODHB.wbShowMHBReadOnly?pKnotenNr=458187&pOrgNr=14189 (module description) | ||
}} | }} | ||
| Line 27: | Line 27: | ||
= Lecture Notes and Material = | = Lecture Notes and Material = | ||
will be made available during the course. | <!-- will be made available during the course. --> | ||
== Lecture Slides == | == Lecture Slides == | ||
| Line 34: | Line 34: | ||
; Sorting - InsertSort, MergeSort, QuickSort, BucketSort (Oct 20, 27; Nov 3) | ; Sorting - InsertSort, MergeSort, QuickSort, BucketSort (Oct 20, 27; Nov 3) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg02.pdf slides] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg02.pdf slides] | ||
: (corrected partitioning algorithm, now fully according to Hoare's algorithm; the previous partitioning algorithm only worked, if all elements of A have distinct size) | |||
; Recurrences (Nov 3) | ; Recurrences (Nov 3) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg02b.pdf slides] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg02b.pdf slides] | ||
; Searching (Nov 10, 17) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg05.pdf slides] | |||
; AVL trees(Nov 10, 17) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg06.pdf slides] | |||
; Hash Tables (Nov 24) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg07.pdf slides] | |||
; Parallel Algorithms and PRAM (Dec 1, 8) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg03.pdf slides] | |||
; Parallel Sorting, Odd-Even MergeSort (Dec 8, 15) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg04.pdf slides] | |||
; Graphs (Dec 15, Jan 12) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg08.pdf slides] | |||
; Weighted Graphs (Jan 12, Jan 19) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg09.pdf slides] <!-- (Dijkstra and Prim Algorithm are excluded for the exam) --> | |||
; Exam (Jan 26) | |||
: Due to the exam on Jan 26, there will be no lecture on that day | |||
<!-- | <!-- | ||
; MidTerm Test (Dec 23) | ; MidTerm Test (Dec 23) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/midterm.pdf exercises] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/midterm_solution.pdf solutions] | ||
--> | --> | ||
| Line 61: | Line 62: | ||
: [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 3) | |||
; Recurrences(Nov | : [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] | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | ; Sequential and Binary Search (Nov 10) | ||
; | : [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] | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | ; AVL trees (Nov 17) | ||
; | : [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] | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | ; Hashing (Nov 24) | ||
; | : [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] | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | ; PRAM - Linear Algebra and Prefix Problem (Dec 1) | ||
; | : [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] | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | ; PRAM - Prefix Problem and BucketSort (Dec 8) | ||
; | : [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] | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | ; Graphs (Dec 15) | ||
; Graphs ( | : [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] | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | ; Hypergraphs and Bipartite Graphs (Jan 19, optional) | ||
; Hypergraphs and Bipartite Graphs (Jan | : [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] | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | |||
== Exam == | == Exam == | ||
* a '''repeat exam ''' will be offered on ''' | * a '''repeat exam ''' will be offered on '''Wed, Apr 15, 16.30 (MI 02.07.023)''' | ||
** the exam will be written | ** the exam will be written | ||
** all rules (helping material, etc.) are identical to the first exam | ** all rules (helping material, etc.) are identical to the first exam | ||
* the '''exam review''' (i.e., opportunity to take a look at your graded exam) will be on '''Friday, Feb | <!-- | ||
* the exam will be on '''Mon, | * the '''exam review''' (i.e., opportunity to take a look at your graded exam) will be on '''Monday, Feb 23''', 15.00-16.30 and on '''Friday, Feb 27''', 10.00-11.30, in room (E.2.044, office of Prof. Bader, LRZ, Boltzmannstr. 1) | ||
* please by at the lecture hall in time ( | * the exam will be on '''Mon, Jan 26, 2015''' at '''18.30''' in lecture hall '''Interim 2''' (black lecture-hall building in front of Mathematics/Informatics) | ||
--> | |||
* please by at the lecture hall in time (16.15) - the exam will start precisely at 16.30 and there will be announcements before starting | |||
* Working time will be 90 minutes. | * Working time will be 90 minutes. | ||
* Helping material: you are allowed to use '''one sheet (size A4) of paper''' with '''hand-written(!) notes''' (on both sides) 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''' (on both sides) during the exam. Any further helping material (books, calculators, etc.) is forbidden! | ||
| Line 97: | Line 97: | ||
* 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 | ||
** Dijkstra and Prim Algorithm from Chapter 9 (Weighted Graphs) are excluded from the exam | ** Dijkstra and Prim Algorithm from Chapter 9 (Weighted Graphs) are excluded from the exam | ||
== Literature == | == Literature == | ||
Latest revision as of 17:15, 2 March 2015
- 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, repeat on Wed, Apr 15, 2015 at 16.30 in lecture room MI 02.07.23 (see details below)
- Semesterwochenstunden / ECTS Credits
- 2 SWS (2V) / 3 ECTS
- TUMonline
- https://campus.tum.de/tumonline/lv.detail?clvnr=950160214 (lecture),
https://campus.tum.de/tumonline/WBMODHB.wbShowMHBReadOnly?pKnotenNr=458187&pOrgNr=14189 (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
Lecture Slides
- Introduction - Algorithms, Fibonacci example, Asymptotics (Oct 13, 20)
- slides
- Sorting - InsertSort, MergeSort, QuickSort, BucketSort (Oct 20, 27; Nov 3)
- slides
- (corrected partitioning algorithm, now fully according to Hoare's algorithm; the previous partitioning algorithm only worked, if all elements of A have distinct size)
- Recurrences (Nov 3)
- slides
- Searching (Nov 10, 17)
- slides
- AVL trees(Nov 10, 17)
- slides
- Hash Tables (Nov 24)
- slides
- Parallel Algorithms and PRAM (Dec 1, 8)
- slides
- Parallel Sorting, Odd-Even MergeSort (Dec 8, 15)
- slides
- Graphs (Dec 15, Jan 12)
- slides
- Weighted Graphs (Jan 12, Jan 19)
- slides
- Exam (Jan 26)
- Due to the exam on Jan 26, there will be no lecture on that day
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
- Recurrences(Nov 3)
- worksheet and solution
- Sequential and Binary Search (Nov 10)
- worksheet and solution
- AVL trees (Nov 17)
- worksheet and solution
- Hashing (Nov 24)
- worksheet and solution
- PRAM - Linear Algebra and Prefix Problem (Dec 1)
- worksheet and solution
- PRAM - Prefix Problem and BucketSort (Dec 8)
- worksheet and solution
- Graphs (Dec 15)
- worksheet and solution
- Hypergraphs and Bipartite Graphs (Jan 19, optional)
- worksheet and solution
Exam
- a repeat exam will be offered on Wed, Apr 15, 16.30 (MI 02.07.023)
- the exam will be written
- all rules (helping material, etc.) are identical to the first exam
- please by at the lecture hall in time (16.15) - the exam will start precisely at 16.30 and there will be announcements before starting
- Working time will be 90 minutes.
- Helping material: you are allowed to use one sheet (size A4) of paper with hand-written(!) notes (on both sides) 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; see, in particular, the worksheets for this course
- Dijkstra and Prim Algorithm from Chapter 9 (Weighted Graphs) are excluded from the exam
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