Difference between revisions of "Fundamental Algorithms - Winter 13"

From Sccswiki
Jump to navigation Jump to search
Line 81: Line 81:
  
 
* the exam will be on '''Mon, Feb 3, 2013''' at '''18.30''' in lecture hall '''MW 0350''' (Department of Mechanical Engineering, Boltzmannstr. 15)
 
* 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 announcement 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!

Revision as of 09:18, 27 January 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
written exam: Mon, Feb 3, 2014 (18.30, lecture hall MW 0350)
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
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

  • 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 announcement 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