Fundamental Algorithms
Module IN2157
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 workload | Contact hours | Credits (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.
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
WS 2022/3
WS 2021/2
WS 2020/1
WS 2019/20
WS 2018/9
WS 2017/8
WS 2016/7
WS 2015/6
WS 2014/5
WS 2013/4
WS 2012/3
Type | SWS | Title | Lecturer(s) | Dates | Links |
---|---|---|---|---|---|
VO | 2 | Fundamental Algorithms (CSE) (IN2157) | Azeem Muqsit, -. Evangelidis, A. Ghoshdastidar, D. Grover, K. |
Tue, 10:00–12:00, MI 00.13.009A and singular or moved dates |
documents |
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.
- 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.
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.