de | en

Fundamental Algorithms

Module IN2157

This Module is offered by TUM Department of Informatics.

This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.

Basic Information

IN2157 is a semester module in English language at Master’s level which is offered in winter semester.

This Module is included in the following catalogues within the study programs in physics.

  • Focus Area Imaging in M.Sc. Biomedical Engineering and Medical Physics
Total workloadContact hoursCredits (ECTS)
150 h 60 h 5 CP

Content, Learning Outcome and Preconditions

Content

The module provides an overview of fundamental sequential and parallel algorithms, as well as an introduction to the analysis of algorithms. Typical topics include:
Fundamentals: models of computation, complexity measures, loop invariants and induction techniques to prove the correctness of algorithms
Sorting: Bubble-Sort, Merge-Sort, Quick-Sort, median algorithms, lower bounds for sorting, sorting in parallel
Searching: linear and binary search, search trees (AVL Trees), hashing, etc.
Arithmetic problems: parallel prefix computation, parallel matrix and vector operations
Graph algorithms: graph traversal, transitive closure, shortest paths, minimum spanning trees
These algorithms are used as examples to present and exercise the application of models of computation, complexity measures and techniques for analysis and proofs.

Learning Outcome

Participants understand fundamental algorithms (incl. simple parallel algorithms) and are able to apply them. They can analyze the complexity and the parallelism properties of moderately complex algorithms. For algorithms that are discussed in the module, they are able to prove such properties using the discussed techniques. Participants are also able to assess the appropriateness of these algorithms for specific problems.

Preconditions

IN0001 Einführung in die Informatik 1

Courses, Learning and Teaching Methods and Literature

Courses and Schedule

Learning and Teaching Methods

This module comprises lectures and accompanying tutorials. The contents of the lectures will be taught by talks and presentations. Students will be encouraged to study literature and to get involved with the topic in depth. In the tutorials, concrete problems will be solved (partially in teamwork) and selected examples will be discussed.

Media

Slides, blackboard

Literature

- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. 2. Auflage, MIT Press, Cambridge, MA, 2001.
- Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, Boston, MA, 2005.
- Russell L. Shackelford , Introduction to Computing and Algorithms. Addison Wesley, 1997.
- Robert Sedgewick, Kevin Wayne. Algorithms. 4th Edition, Pearson Education, 2011.

Module Exam

Description of exams and course work

The examination consists of a written exam of 90 minutes. In the exam, students prove in the given exercises that they have command of the fundamentals of the algorithms and data structures discussed in the module. They are able to apply their knowledge and solve respective algorithmic problems within limited time. Exercise may include:
determining the complexity of sorting, arithmetic or graph algorithms using the discussed complexity models;
determining non-functional properties (correctness, level of parallelism, etc.) of these algorithms;
discussion of the appropriateness of certain algorithms to meet additional requirements.
Answers require own formulations and computations.

Exam Repetition

The exam may be repeated at the end of the semester.

Top of page