Fundamental Algorithms - Winter 10

Term

Winter 10

Lecturer

Dr. Dirk Pflüger

Time and Place

Tuesday, 9:00-10:30, lecture hall MI 02.07.023; first lecture November 2

Audience

Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing

Tutorials

-

Exam

written exam (date: Feb 11, 2011; 16:30-18:30 in room MW(!) 1050)

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
• Graph Algorithms: Transitive Closure, Shortest Path Problems, Minimum Spanning Trees (if time allows)

Current News

• Master Thesis? Student project? We're always looking for you! See Student Projects and/or ask me!

Lecture Notes and Material

Slides from the Lecture

Introduction - Algorithms, Fibonacci example, growth of functions

Nov 2

slides (Update loop invariants, 08.11.)

Sorting Algorithms

Nov 9, 16, 23

slides (few typos corrected, 15.11. - update last slide, 24.11. - corrected partitioning algorithm, Python implementations available at [1], [2], call with "Python filename.py", 3.2.)

Recurrences

Nov 30

slides (corrected prerequisites for Master Theorem, 6.12.)

More Sorting

Dec 7, 14

slides

Selecting

Dec 14, 21

slides

Random Access Machines

Dec 21

slides (introduced Vector x, 21.12.)

The PRAM Model

Jan 11

slides (Update of three slides, 12.01.)

Searching

Jan 18

slides (update assumptions on slide 4, 18.01.)

AVL Trees

Jan 25

slides

Hashing

Feb 1

slides (update formula multiplication method, numbers on slide 19, 1.2.)

Worksheets

Growth of functions

Nov 9

worksheet, solution

Complexity of Algorithms, Sorting on Matrices

Nov 16

worksheet, solution

Recurrences - Complexity of MergeSort and QuickSort

Nov 23

worksheet, solution

CountingSort

Nov 30

worksheet, solution (27.1. corrected error in solution 2a, third loop)

Recurrences

Dec 07

worksheet, solution

Selecting

Dec 14

worksheet, solution (27.1. corrected solution for exercise 2: call to larger partition)

RAM

Dec 21

worksheet, solution (31.1. corrected line 16 RAM program: "=" -> ">"; 7.2. corrected resulting line 15, R6-R7 -> R7-R6; 9.2. sorry, changed everything back again: the original version was correct; included full list of all RAM states)

PRAM

Jan 8

worksheet, solution (1.2. corrected typeos in ScalarProductPar and MatrixVectorProductEREW)

Searching

Jan 18

worksheet, solution

AVL trees

Jan 25

worksheet (28.1. corrected typeo: first "TreeInsert(5)" should be "TreeDelete(5)", solution

Hashing

Feb 1

worksheet, solution

Exam

• Date of final exam: Friday, Feb 11, 16:30-18:30 in room MW(!) 1050, see TUMonline
• Helping material: you are allowed to use one sheet (size A4) of paper with hand-written(!) notes during the exam. Any further helping material (books, calculators, etc.) is forbidden!
• Exam topics are all topics covered during the lectures; see, in particular, the worksheets for this course
• Repeat exam: a repeat exam will offered (only for students who failed the regular exam) in April 2011. The exam will be written.
• Possibility to view your exam results will be given on Feb 22, 09:30-11:30, in room 02.05.011.

Literature

Recommended:

• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press

For parallel RAM:

• Berman, Paul: Fundamentals of Sequential and Parallel Algorithms

Also helpful:

• Heun: Grundlegende Algorithmen, Vieweg 2000
• Sedgewick: Algorithms, Pearson Education
• Shackleford, Computing and Algorithms, Addison Wesley Longman
• Kleinberg, Tardos: Algorithm Design, Pearson Education