
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
 Stepwise 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, doubleconnected 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, topdown234trees, blackredtrees, Btrees
 Graphs: term and definition, depthfirstsearch, breadthfirstsearch, smallest spanning tree, shortest path, transitive hull, serialization of graphs
 Exhaustion: nqueens problem, schema to search a solution, using exhaustion to find a solution, optimization, representing solution vectors, approximation, nondeterministic 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. AddisonWesley 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. AddisonWesley 1973.
Band 1: Fundamental Algorithms.
Band 2: Seminumerical Algorithms.
Band 3: Sorting and Searching.
 Wirth, N.: Algorithms + Data Structures = Programs. PrenticeHall. 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)

