Fundamental Algorithms - Winter 11: Difference between revisions

From Sccswiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 37: Line 37:
; Parallel Sorting, Odd-Even MergeSort (Dec 13)
; Parallel Sorting, Odd-Even MergeSort (Dec 13)
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg03.pdf slides]  
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg03.pdf slides]  
; Searching (Dec 20)
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg05.pdf slides]


== Worksheets ==
== Worksheets ==
Line 48: Line 50:
; Parallel Scalar Product and Matrix-Vector Multiplication (Dec 6)
; Parallel Scalar Product and Matrix-Vector Multiplication (Dec 6)
: [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/WS11/worksheets/fundalg4.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg4sol.pdf solution]
; Sequential and Binary Search (Dec 20)
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg5.pdf worksheet]


== Literature ==
== Literature ==

Revision as of 08:18, 20 December 2011

Term
Winter 11
Lecturer
Prof. Dr. Michael Bader
Time and Place
Tuesday, 9:30-11:00 (MI 02.07.023); first lecture: Oct 25
Audience
Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing (elective)
Tutorials
t.b.a. (no compulsory tutorials; there might be a few extra lessons on a voluntary basis)
Exam
written exam
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
  • Foundations of parallel algorithms and simple models of parallel computation

Announcements

  • Change of time: Lecture was moved from 9.00-10.30 to 9.30-11.00 (starting on Dec 20)
  • Exam: the final exam will be on Thu, Feb 23, 2012 (14.00-16.00)

Lecture Notes and Material

Slides from the Lecture

Introduction - Algorithms, Fibonacci example (Oct 25)
slides
Sorting (Nov 8, Nov 15, Nov 22)
slides (lecture on Nov 15 from 9.00 to 9.45, because of Student General Assembly)
Recurrences (Nov 22, Nov 29)
slides
More Sorting (Nov 29)
slides
Parallel Algorithms and PRAM (Dec 6)
slides
Parallel Sorting, Odd-Even MergeSort (Dec 13)
slides
Searching (Dec 20)
slides

Worksheets

O-notation, etc. (Nov 8)
worksheet and solution
Complexity and Sorting (Nov 15)
worksheet and solution
MergeSort and Recurrences (Nov 22)
worksheet and solution
(no worksheet on Nov 29)
Parallel Scalar Product and Matrix-Vector Multiplication (Dec 6)
worksheet and solution
Sequential and Binary Search (Dec 20)
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