Algorithms and Data Structures
Module BV440007
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.
Module version of SS 2011
There are historic module descriptions of this module. A module description is valid until replaced by a newer one.
Whether the module’s courses are offered during a specific semester is listed in the section Courses, Learning and Teaching Methods and Literature below.
| available module versions | |
|---|---|
| WS 2011/2 | SS 2011 |
Basic Information
BV440007 is a semester module in English language at Master’s level which is offered in summer semester.
This Module is included in the following catalogues within the study programs in physics.
- Catalogue of non-physics elective courses
| Total workload | Contact hours | Credits (ECTS) |
|---|---|---|
| 90 h | 28 h | 3 CP |
Content, Learning Outcome and Preconditions
Content
• Foundations of programming concepts
• Recursive algorithms
• Introduction into the complexity analysis of algorithms
• Data structures (arrays, trees, linked lists)
• Sorting algorithms (sequential approaches, divide-and-conquer approach)
• Search algorithms (sequential and recursive approaches, balancing, hashing)
• Foundations of graph theory and graph applications (minimal-spanning trees, shortest-path-search, maximum network flow)
• Code optimisation and cache-blocking algorithms
• Recursive algorithms
• Introduction into the complexity analysis of algorithms
• Data structures (arrays, trees, linked lists)
• Sorting algorithms (sequential approaches, divide-and-conquer approach)
• Search algorithms (sequential and recursive approaches, balancing, hashing)
• Foundations of graph theory and graph applications (minimal-spanning trees, shortest-path-search, maximum network flow)
• Code optimisation and cache-blocking algorithms
Learning Outcome
After successful participation students are able to
• develop algorithms and, thus, to formulate rules using programming concepts in order to solve problems with the help of computers,
• understand recursive approaches and to apply them on own problems,
• analyse and classify algorithms concerning runtime and memory usage via a complexity evaluation,
• know different data structures and according to their strong and weak aspects to chose appropriate structures for specific problem classes,
• known, understand, and apply different sorting and searching algorithms together with their respective runtime and memory complexity,
• understand the foundations of graph theory and to apply graph-based algorithms for questions regarding minimal-spanning trees, shortest-path-search, and maximum network flow,
• know and understand methods for code optimisation (such as cache-blocking) and to apply them on own problems.
• develop algorithms and, thus, to formulate rules using programming concepts in order to solve problems with the help of computers,
• understand recursive approaches and to apply them on own problems,
• analyse and classify algorithms concerning runtime and memory usage via a complexity evaluation,
• know different data structures and according to their strong and weak aspects to chose appropriate structures for specific problem classes,
• known, understand, and apply different sorting and searching algorithms together with their respective runtime and memory complexity,
• understand the foundations of graph theory and to apply graph-based algorithms for questions regarding minimal-spanning trees, shortest-path-search, and maximum network flow,
• know and understand methods for code optimisation (such as cache-blocking) and to apply them on own problems.
Preconditions
Knowledge of any programming language (for instance C/C++ or Fortran)
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
| Type | SWS | Title | Lecturer(s) | Dates | Links |
|---|---|---|---|---|---|
| VO | 2 | Algorithms and Data Structures | Mundani, R. |
Fri, 09:45–11:15, 2601 |
eLearning |
Learning and Teaching Methods
The module is provided as lecture and its contents will be communicated with descriptive and practical examples as well as discussions with students. The lecture should further motivate students to own researches and lecture studies concerning the topics. Exercise sheets (and solutions) that reflect the respective lecture contents will be provided, thus students can use those for their own control when studying and applying the learned methodologies and concepts.
Media
Main lecture media are PowerPoint slides complemented by the usage of black and white boards. PowerPoint slides are online available for download.
Literature
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, 2nd ed., The MIT Press, 2001
- R. Sedgewick: Algorithms, 2nd ed., Addison-Wesley, 1988
- V. Heun: Grundlegende Algorithmen, Vieweg, 2003
- R. Sedgewick: Algorithms, 2nd ed., Addison-Wesley, 1988
- V. Heun: Grundlegende Algorithmen, Vieweg, 2003
Module Exam
Description of exams and course work
Learning success will be verified via a 90 minute written examination, in order to show students’ familiarity with the discussed topics as well as their ability to apply learned methods and concepts to develop and analyse algorithms for specific problems from the field of recursive approaches, sorting and searching as well as graphs. Therefore, short problems have to be solved and code fragments have to be implemented on paper. Additional resources that are allowed throughout the examination are printed lecture slides and hand-written notes.