Fundamental Algorithms - Winter 13: Difference between revisions
Jump to navigation
Jump to search
m (→Worksheets) |
No edit summary |
||
| (25 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 = | | exam = repeat exam: Tue, Apr 8, 2014 (17.00, MI 02.07.023, written exam) | ||
| tumonline = https://campus.tum.de/tumonline/lv.detail?clvnr=950121698 (lecture),<br> https://campus.tum.de/tumonline/wbStpModHB.detailPage?&pKnotenNr=458187 (module description) | | tumonline = https://campus.tum.de/tumonline/lv.detail?clvnr=950121698 (lecture),<br> https://campus.tum.de/tumonline/wbStpModHB.detailPage?&pKnotenNr=458187 (module description) | ||
}} | }} | ||
| Line 25: | Line 25: | ||
= Lecture Notes and Material = | = Lecture Notes and Material = | ||
== Lecture Slides == | == Lecture Slides == | ||
| Line 46: | Line 44: | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/fundalg07.pdf slides] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/fundalg07.pdf slides] | ||
; MidTerm Test (Dec 23) | ; MidTerm Test (Dec 23) | ||
: exercises and solutions | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/midterm.pdf exercises] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/midterm_solution.pdf solutions] | ||
; Graphs (Jan 13, Jan 20) | |||
; Graphs (Jan | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/fundalg08.pdf slides] (DF/BF traversals updated) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | ; Weighted Graphs (Jan 20, Jan 27) | ||
; Weighted Graphs (Jan | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/fundalg09.pdf slides] (Dijkstra and Prim Algorithm are excluded for the exam) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/ | ; Exam (Feb 3) | ||
: Due to the exam on Feb 3, there will be no lecture on that day | |||
== Worksheets == | == Worksheets == | ||
| Line 72: | Line 70: | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg8.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg8sol.pdf solution] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg8.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg8sol.pdf solution] | ||
; Hashing (Dec 16) | ; Hashing (Dec 16) | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg9.pdf worksheet] ( | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg9.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg9sol.pdf solution] | ||
; Graphs (Jan 13) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg10.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg10sol.pdf solution] | |||
; Hypergraphs and Bipartite Graphs (Jan 20) | |||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg11.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg11sol.pdf solution] | |||
== Exam == | |||
* a '''repeat exam ''' will be offered on '''Tue, Apr 8, 17.00 (MI 02.07.023)''' | |||
** the exam will be written | |||
** 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 28''' from 10.00 in room (E.2.044, office of Prof. Bader, LRZ, Boltzmannstr. 1) | |||
* the exam will be on '''Mon, Feb 3, 2013''' at '''18.30''' in lecture hall '''MW 0350''' (Department of Mechanical Engineering, Boltzmannstr. 15) | |||
* please by at the lecture hall in time (18.15) - the exam will start precisely at 18.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 == | == Literature == | ||
Latest revision as of 17:21, 24 March 2014
- Term
- Winter 13
- Lecturer
- Prof. Dr. Michael Bader
- Time and Place
- Mon 8.30-10.00, lecture hall MI HS 3 (first lecture on Oct 21, 8.30)
- Audience
- Computational Science and Engineering; Biomedical Computing (elective)
- Tutorials
- ---
- Exam
- repeat exam: Tue, Apr 8, 2014 (17.00, MI 02.07.023, written exam)
- Semesterwochenstunden / ECTS Credits
- 2 SWS (2V) / 3 ECTS
- TUMonline
- https://campus.tum.de/tumonline/lv.detail?clvnr=950121698 (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.
Announcements
- in the slot on Dec 23, we will do a short (40min) test exam, with discussion of solutions afterwards;
participation is entirely optional (questions and solutions will be made available towards the end of the Christmas holidays) - the lectures will start on Monday, Oct 21 (no lecture on Oct 14, due to semester opening)
Lecture Notes and Material
Lecture Slides
- Introduction - Algorithms, Fibonacci example, Asymptotics (Oct 21, Oct 28)
- slides
- Sorting - InsertSort, MergeSort, QuickSort (Oct 28, Nov 4, Nov 11)
- slides (with corrected proof for InsertionSort)
- Recurrences (Nov 11)
- slides
- Parallel Algorithms and PRAM (Nov 18, Nov 25)
- slides
- Parallel Sorting, Odd-Even MergeSort (Nov 25, Dec 2)
- slides
- Searching (Dec 2, Dec 9)
- slides
- AVL trees(Dec 9, Dec 16)
- slides
- Hash Tables (Dec 16, Jan 13)
- slides
- MidTerm Test (Dec 23)
- exercises and solutions
- Graphs (Jan 13, Jan 20)
- slides (DF/BF traversals updated)
- Weighted Graphs (Jan 20, Jan 27)
- slides (Dijkstra and Prim Algorithm are excluded for the exam)
- Exam (Feb 3)
- Due to the exam on Feb 3, there will be no lecture on that day
Worksheets
- O-notation, etc. (Oct 21)
- worksheet and solution
- Complexity and Sorting (Oct 28)
- worksheet and solution
- MergeSort (Nov 4)
- worksheet and solution
- Recurrences(Nov 11)
- worksheet and solution (with slightly updated solution for Exercise 1)
- PRAM - Linear Algebra and Prefix Problem (Nov 18)
- worksheet and solution (slightly updated; leaves Ex. 3 for next week)
- PRAM - Prefix Problem and BucketSort (Nov 25)
- worksheet and solution (includes Ex. 3 from previous week)
- Sequential and Binary Search (Dec 2)
- worksheet and solution
- AVL trees (Dec 9)
- worksheet and solution
- Hashing (Dec 16)
- worksheet and solution
- Graphs (Jan 13)
- worksheet and solution
- Hypergraphs and Bipartite Graphs (Jan 20)
- worksheet and solution
Exam
- a repeat exam will be offered on Tue, Apr 8, 17.00 (MI 02.07.023)
- the exam will be written
- all rules (helping material, etc.) are identical to the first exam
- 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