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.
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
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.
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
|VI||4||Fundamental Algorithms (CSE) (IN2157)||
Assistants: Osep, A.
Tue, 10:00–12:00, virtuell
Thu, 16:00–18:00, virtuell
Learning and Teaching Methods
- 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.
Description of exams and course work
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.
The exam may be repeated at the end of the semester.