Inhalt

### [ 289SEECNESV20 ] VL Algorithms and Data Structures

Versionsauswahl
(*) Unfortunately this information is not available in english.
Workload Education level Study areas Responsible person Hours per week Coordinating university
3 ECTS B1 - Bachelor's programme 1. year (*)Informationselektronik Rick Rabiser 2 hpw Johannes Kepler University Linz
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