Algorithms

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 in Java, our integrated development environment of choice is Eclipse.

Contents

Topics include

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

  • 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

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, NetBeans, BlueJ 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.
  • yED Graph Editor
    With yED, we develop ER and UML-diagrams.