Sorting Searching Trees Graphs Java Python
The course gives an introduction to algorithms and data structures as well as basic principles of algorithm design and complexity analysis. Assignments are carried out by implementing the algorithms either in Java, (with Eclipse IDE) or in Python (with Jupyter Notebook / Google Colab / Spyder).
We will discuss the following topics
- Algorithm design (recursion, divide-and-conquer, greedy strategy)
- Complexity analysis (RAM-Model, Measures of complexity, worst/average/best-case, Big-O-Notation)
- Sorting algorithms: SelectionSort, InsertionSort, QuickSort, MergeSort
- Abstract data types, linked lists, stacks, queues, hashing
- Trees, binary trees, balanced trees
- Graph algorithms (breadth-first search, depth-first search, minimal spanning tree, algorithms of Kruskal and Prim, shortest path problems, algorithms of Djikstra and Bellmann-Ford
Students receive an introduction to basic concepts of algorithms and data structures, with practical applications in engineering. During lab, students learn to develop algorithms creatively. On completion of this course you should be able to:
- use design principles for algorithms and apply them in practical applications
- estimate complexity of algorithms (runtime and memory)
- use dynamical data structures such as linked lists, stacks, queues, hash tables and trees and understand the effect of the correct choice of datastructure on the overall performance of the algorithm
- implement and use common algorithms for efficient sorting, storage and search
Here a selection of recommended readings.
- Sedgewick, R.; Wayne, K.: Algorithms; Addison Wesley
- Cormen, T.H.; et. al.: Introduction to Algorithms, The MIT Press
- Ottmann, T.; Widmayer, P.: Algorithmen und Datenstrukturen; Springer
- Saake, G.; Sattler, K.U.: Algorithmen und Datenstrukturen: Eine Einführung mit Java; Dpunkt
As software, we use Eclipse IDE for Java Developers and yED Graph Editor for UML diagrams. Other integrated development environments such as IntelliJ IDEA or NetBeans are also used occasionally.
Eclipse is one of the leading tools for Java developers, including a Java IDE, a Git client, XML Editor, Maven integration and many plugins that extend its already powerful functionality: project templates and automatic code generation for interfaces and classes, syntax highlighting, configuration through perspectives and views, refactoring capabilities. The extended version, Eclipse IDE for Enterprise Java Developers, is used for developing web applications based on JavaServer Pages and Faces, Web Services, and JPA-components for accessing databases.
For Python programming, a current Python installation from the Python website python.org must first be downloaded and installed. For the development of larger programs and data science projects, the package management platform Anaconda containing Spyder and Jupyter Notebook should also be set up, which provides extensive functionality for package management, software development and presentation.
- yED Graph Editor
With yED, we develop ER and UML-diagrams.
The following apps created with Python / Jupyter Notebook / Google Colab can be used for learning about algorithms and data visualization. Some of the apps are work in progress, to be finished as project work by students.
This Jupyter Notebook features the implementation in Python of the SelectionSort algorithm, which finds the smallest element in the list and swaps it for the first element, then repeats this for the unsorted part of the sequence until it is completely sorted. SelectionSort is stable, in-place, and slow: the algorithm's complexity is O(N^2) in average and worst case. You can modify the code, extend it, add additional tests.
This Jupyter Notebook features the implementation in Python of the MergeSort algorithm, which recursively divides a list in two halves, then merges two already sorted halves. MergeSort needs an additional helper array and is efficient: the algorithm's complexity is O(N log(N)) in in average and worst case.
This Jupyter Notebook features the interactive visualization of binary search trees using Jupyter Notebook Widgets and the graphviz-package. The nodes of a binary search tree are created using the class TreeNode. Binary search trees are created using the methods of the class BST.