Difference between revisions of "Fundamental Algorithms - Winter 13"

From Sccswiki
Jump to navigation Jump to search
Line 64: Line 64:
 
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg4.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg4sol.pdf solution]
 
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg4.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg4sol.pdf solution]
 
; PRAM Linear Algebra and Prefix Problem (Nov 18)
 
; PRAM Linear Algebra and Prefix Problem (Nov 18)
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg4.pdf worksheet] <!--and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg4sol.pdf solution]-->
+
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg5.pdf worksheet] <!--and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/worksheets/fundalg5sol.pdf solution]-->
 
<!--
 
<!--
 
; Sequential and Binary Search (Dec 20)
 
; Sequential and Binary Search (Dec 20)

Revision as of 17:07, 15 November 2013

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
written exam: Mon, Feb 3, 2014 (further details t.b.a.)
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

will be made available here throughout the lecture ...

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

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
PRAM Linear Algebra and Prefix Problem (Nov 18)
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