Fundamental Algorithms - Winter 14: Difference between revisions

From Sccswiki
Jump to navigation Jump to search
Line 44: Line 44:
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg07.pdf slides]  
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg07.pdf slides]  
; Parallel Algorithms and PRAM (Dec 1)
; Parallel Algorithms and PRAM (Dec 1)
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/fundalg03.pdf slides]  
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg03.pdf slides]  
<!--
<!--
; Parallel Sorting, Odd-Even MergeSort (Nov 25, Dec 2)
; Parallel Sorting, Odd-Even MergeSort (Nov 25, Dec 2)
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/fundalg04.pdf slides]  
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg04.pdf slides]  
; MidTerm Test (Dec 23)
; MidTerm Test (Dec 23)
: [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]
: [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]
; Graphs (Jan 13, Jan 20)
; Graphs (Jan 13, Jan 20)
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/fundalg08.pdf slides] (DF/BF traversals updated)
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS14/fundalg08.pdf slides] (DF/BF traversals updated)
; Weighted Graphs (Jan 20, Jan 27)
; Weighted Graphs (Jan 20, Jan 27)
: [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/WS14/fundalg09.pdf slides] (Dijkstra and Prim Algorithm are excluded for the exam)
; Exam (Feb 3)
; Exam (Feb 3)
: Due to the exam on Feb 3, there will be no lecture on that day
: Due to the exam on Feb 3, there will be no lecture on that day

Revision as of 18:25, 30 November 2014

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 at end of semester
Semesterwochenstunden / ECTS Credits
2 SWS (2V) / 3 ECTS
TUMonline
https://campus.tum.de/tumonline/lv.detail?clvnr=950160214 (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.

Lecture Notes and Material

will be made available during the course.

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)
slides

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


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