 |
| Detailed information |
| Original study plan |
Bachelor's programme Electronics and Information Technology 2020W |
| Objectives |
Algorithms are the basis of software development. They bridge computer science theory and programming.
In this lecture students learn about the important core characteristics and classes of algorithms with a focus on their practical use to implement software systems and solve concrete problems.
|
| Subject |
- Algorithms: definition, algorithms vs. programs, representing algorithms, abstraction layers and characteristics of algorithms
- Specifications: objectives, Interface descriptions, requirements, representing specifications
- Step-wise refinement: "divide & conquer", systematic problem solving, examples
- Algorithms with a memory: term and definition, ways to implement algorithms with a memory
- Complexity: terms and definitions, runtime analysis, runtime measurements, asymptotic complexity, minimal complexity of problems
- Dynamic data structures: classes and references, linear lists, unsorted lists, sorted lists, ring lists, double-connected lists, stacks, queues, sets
- Recursion: term and definition, classification, termination, applications, transforming recursive into iterative algorithms
- Sorting: selection sort, insertion sort, shell sort, quick sort, merge sort, sorting lists, heap sort, topological sort, complexity of sorting algorithms
- Trees: term and definition, binary search trees, balanced trees, topdown-234-trees, black-red-trees, B-trees
- Graphs: term and definition, depth-first-search, breadth-first-search, smallest spanning tree, shortest path, transitive hull, serialization of graphs
- Exhaustion: n-queens problem, schema to search a solution, using exhaustion to find a solution, optimization, representing solution vectors, approximation, non-deterministic algorithms
- Classification of algorithms
|
| Criteria for evaluation |
Written exam at the end of the semester
|
| Methods |
The lecture mostly is based on algorithms in pseudo code. This allows learning algorithms independent of a concrete programming language.
Some parts of the lecture are supported by demo videos. Some algorithms are constructed on the blackboard or whiteboard step by step.
|
| Language |
German |
| Study material |
- Aho A.V., Hopcroft J.E., Ullman J.D.: Data Structures and Algorithms. Addison-Wesley 1983.
- Goodrich, M. T., Tamassia, R., and Goldwasser, M. H.: Data structures and algorithms in Java. John Wiley & Sons. 2014.
- Knuth D.E.: The Art of Computer Programming. Addison-Wesley 1973.
Band 1: Fundamental Algorithms.
Band 2: Seminumerical Algorithms.
Band 3: Sorting and Searching.
- Wirth, N.: Algorithms + Data Structures = Programs. Prentice-Hall. 1976.
|
| Changing subject? |
No |
| Further information |
The lecture is mainly based on slides. Slides and additional material will be made available for download in PDF format.
|
| Corresponding lecture |
(*)MEBPFVOPIN1: VL Praktische Informatik 1 (3 ECTS)
|
|
