Fundamentals of Algorithms and Data Structures
Module IN0007
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
IN0007 is a semester module in German language at Bachelor’s level which is offered in summer semester.
Total workload | Contact hours | Credits (ECTS) |
---|---|---|
180 h | 75 h | 6 CP |
Content, Learning Outcome and Preconditions
Content
First, the module studies the basics of efficiency and complexity analyses. Basic terminology, complexity measures, the Landau symbols and different machine models are introduced. Then, fundamental data structures and algorithmic problems are studied.
- Data structures for sequences: Dynamic arrays, lists, stacks and queues are investigated. The complexity of each operation is analyzed.
- Hashing: Hashing with chaining, universal hashing as well as various probing methods are examined. Perfect hashing and hash-based algorithms, e.g. for set intersection problems, may also be explored.
- Sorting: First, simple algorithms such as InsertionSort, SelectionSort and BubbleSort are reviewed. Then, advanced algorithms such as MergeSort, HeapSort and QuickSort are investigated. Furthermore, sorting-based algorithms, the lower bound for comparison-based sorting, selection, RadixSort and external sorting may be covered.
- Priority queues: Binary heaps and binomial heaps are presented in the module.
- Search trees: Binary search trees, AVL trees and (a,b)-trees are investigated.
- Graph algorithms: Various graph representations, traversal techniques using DFS/BFS, the computation of 2-connected components and strongly connected components, topological sorting, the computation of the shortest paths and minimum spanning trees are covered. Approaches for solving the Traveling Salesman Problem (TSP) may be studied.
The module may also cover data compression schemes (Huffman, Lempel-Ziv) and simple pattern matching algorithms.
- Data structures for sequences: Dynamic arrays, lists, stacks and queues are investigated. The complexity of each operation is analyzed.
- Hashing: Hashing with chaining, universal hashing as well as various probing methods are examined. Perfect hashing and hash-based algorithms, e.g. for set intersection problems, may also be explored.
- Sorting: First, simple algorithms such as InsertionSort, SelectionSort and BubbleSort are reviewed. Then, advanced algorithms such as MergeSort, HeapSort and QuickSort are investigated. Furthermore, sorting-based algorithms, the lower bound for comparison-based sorting, selection, RadixSort and external sorting may be covered.
- Priority queues: Binary heaps and binomial heaps are presented in the module.
- Search trees: Binary search trees, AVL trees and (a,b)-trees are investigated.
- Graph algorithms: Various graph representations, traversal techniques using DFS/BFS, the computation of 2-connected components and strongly connected components, topological sorting, the computation of the shortest paths and minimum spanning trees are covered. Approaches for solving the Traveling Salesman Problem (TSP) may be studied.
The module may also cover data compression schemes (Huffman, Lempel-Ziv) and simple pattern matching algorithms.
Learning Outcome
The participants master the basic algorithms and data structures mentioned above. They are able to independently analyze their complexity and apply the corresponding analysis concepts to related algorithmic problems. Furthermore, the participants are able to use the algorithms and data structures handled, if necessary to modify them and to compare different solutions in their quality.
Preconditions
IN0001 Introduction to Informatics 1, IN0015 Discrete Structures
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
Type | SWS | Title | Lecturer(s) | Dates | Links |
---|---|---|---|---|---|
VO | 3 | Fundamentals of Algorithms and Data Structures (IN0007) |
Thürey, N.
Winchenbach, R.
Assistants: Franz, E.Kohl, G. |
eLearning documents |
|
UE | 2 | Fundamentals of Algorithms and Data Structures, Exercise Session (IN0007), Fr | Franz, E. Kohl, G. Thürey, N. |
eLearning |
|
UE | 2 | Fundamentals of Algorithms and Data Structures, Exercise Session (IN0007), We, Th |
Franz, E.
Kohl, G.
Responsible/Coordination: Thürey, N. |
eLearning |
|
UE | 2 | Fundamentals of Algorithms and Data Structures, Exercise Session (IN0007), Mo, Tu |
Franz, E.
Kohl, G.
Responsible/Coordination: Thürey, N. |
eLearning |
Learning and Teaching Methods
The module consists of lectures and exercises. The content of the lectures is conveyed in presentations of the scientific material. By solving homework assignments, the students are encouraged to work intensively on the respective topics. The solutions of the assignments are discussed in the exercises. The homework assignments are graded so that students get an individual feedback on their learning success.
Media
Slides, whiteboard, homework assignments
Literature
Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures - The Basic Toolbox. Springer, 2008.
Complementing material for the module is contained in the following books.
- Volker Heun: Grundlegende Algorithmen - Einführung in den Entwurf und die Analyse effizienter Algorithmen. 2. Edition, Vieweg, 2003.
- Michael T. Goodrich, Roberto Tamassia. Algorithm Design - Foundations, Analysis, and Internet Examples. John Wiley & Sons, 2002.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd edition, MIT Press, 2009. German translation: Algorithmen - Eine Einführung. 3. Auflage, Oldenbourg Verlag, 2010.
- Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2005.
- Uwe Schöning. Algorithmik. Spektrum Akademischer Verlag, 2001.
- Robert Sedgewick, Kevin Wayne: Algorithms. 4th edition, Addison-Wesley, 2011.
- Robert Sedgewick. Algorithms in Java, Parts 1-4. 3rd edition, Addison-Wesley, 2002. German translation: Algorithmen in Java, Teil 1-4. 3. Auflage, Pearson Education, 2003.
Complementing material for the module is contained in the following books.
- Volker Heun: Grundlegende Algorithmen - Einführung in den Entwurf und die Analyse effizienter Algorithmen. 2. Edition, Vieweg, 2003.
- Michael T. Goodrich, Roberto Tamassia. Algorithm Design - Foundations, Analysis, and Internet Examples. John Wiley & Sons, 2002.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd edition, MIT Press, 2009. German translation: Algorithmen - Eine Einführung. 3. Auflage, Oldenbourg Verlag, 2010.
- Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2005.
- Uwe Schöning. Algorithmik. Spektrum Akademischer Verlag, 2001.
- Robert Sedgewick, Kevin Wayne: Algorithms. 4th edition, Addison-Wesley, 2011.
- Robert Sedgewick. Algorithms in Java, Parts 1-4. 3rd edition, Addison-Wesley, 2002. German translation: Algorithmen in Java, Teil 1-4. 3. Auflage, Pearson Education, 2003.
Module Exam
Description of exams and course work
The exam takes the form of a 90 minutes written test. In the written exam, based on the questions posed, the students are intended to demonstrate that they have fundamental knowledge in the area of algorithms and data structures. They are able to apply their knowledge successfully in order to solve given problems. In addition, by answering the questions, the students are expected to show that they have profound knowledge of the fundamental algorithmic methods and data structures covered in the module. The students prove that they are able to recognize and analyze basic algorithmic problems and to find efficient solutions within a limited scope of time.
Exam Repetition
The exam may be repeated at the end of the semester.
Current exam dates
Currently TUMonline lists the following exam dates. In addition to the general information above please refer to the current information given during the course.
Title | |||
---|---|---|---|
Time | Location | Info | Registration |
Fundamentals of Algorithms and Data Structures | |||
2001 0001 1550 2501 2502 |