Algorithms

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).

Contents

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

Learning goals

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

Literature

Here a selection of recommended readings.

  • [1] Cormen, Thomas H.; Leiserson, Charles Eric; Rivest, Ronald Linn; Stein, Clifford (2022): Introduction to algorithms. Fourth edition. Cambridge, Massachusett, London: The MIT Press.
    Fundamental textbook. Our implementations (Java or Python) rely mostly on pseudocode from Cormen's.
  • [2] Sedgewick, R.; Wayne, K.: Algorithms; Addison Wesley
    Sedgewick's textbook comes with its own Java algorithms, that we use for comparison.
  • [3] Ottmann, T.; Widmayer, P.: Algorithmen und Datenstrukturen; Springer
  • [4] Saake, G.; Sattler, K.U.: Algorithmen und Datenstrukturen: Eine Einführung mit Java; Dpunkt

Software

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
    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.
  • Python and Anaconda
    Python is well-suited for learning the basic algorithms, as it offers easy ways for visualization. For Python programming, a current Python installation from the Python website python.org must first be downloaded and installed. Additionally, the package management platform Anaconda containing Jupyter Notebook and Spyder should be set up.
  • yED Graph Editor
    yED Graph Editor is used to create Entity-Relationship- and UML-diagrams.

Learning Apps

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.

  • SelectionSort   Algorithms Sorting Python

    This 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.

    Start the SelectionSortLearner 
  • Sorting Algorithms   Algorithms Sorting Python

    This Notebook shows the implementation of the SelectionSort vs InsertionSort algorithm in Python, with their respective time complexity.

    Start the Notebook "SortingAlgorithms"  
  • MergeSort   Algorithms Sorting Python

    This 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.

    Start the MergeSortLearner 
  • BSTLearner   Algorithms Binary Search Trees Python

    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.

    Start the BSTLearner