How to study algorithms

Algorithms and data structures

Lecture, summer semester 2006

To the exercise page

Current information

Organizational matters

  • Date: Monday, 2-4 p.m., F135
  • Exercise: 2 hours, in groups


Please be sure to read the information about the practice and the exam.

General

classification

- Bachelor Applied Computer Science: Computer Science, compulsory 2nd subject semester
- Bachelor of Business Informatics: Computer Science, compulsory elective area
- Diploma in business informatics: basics of informatics, compulsory area

requirements

Knowledge of the lectures "Introduction to Computer Science" (including associated Java internship) by Prof. Wirtz, "Mathematics for Computer Scientists" (including computer exercises) by Prof. Mendler and business mathematics by Dr. Dobbener.

Please also note the lecture "Application-Oriented Probability Calculation", which we strongly recommend attending parallel to "Algorithms and Data Structures"!

content

The lecture introduces the basic techniques of efficient algorithm design and their implementation through data structures. The aim of the lecture is to impart theoretical knowledge (what distinguishes efficient processes? What algorithms and data structures are behind them? How can the effort be expressed in terms of complexity? How is an algorithm analyzed?) And practical skills (how do you analyze a problem? How do you map it to efficient algorithms and data structures? How do you implement the algorithm and data structures using an executable program? Java in the exercises! How do you test the code and its efficiency?)

The lecture begins with the basics of the analysis of algorithms. Mathematical basics are dealt with, such as estimates, exact and abstract runtime, asymptotic notations, estimates for the worst case and the average case, estimates for typical procedures such as recursion, especially the master theorem. In addition, the basic data structures fields, stacks, queues, lists and ski lists as well as graphs and trees are dealt with. Further topics are internal sorting processes through comparisons (bubble sort, mergesort, quicksort, heapsort), lower bounds for internal sorting processes, sorting in linear time, external sorting, selection, management of dynamic quantities using hash processes and search trees, in particular height-balanced trees (AVL trees). Finally, basic algorithms on graphs are dealt with, e.g. for shortest paths (Dijkstra) or minimal spanning trees.

Lecture slides

are made available here to accompany the lecture.

Chapter 1:

Chapter 2:

Chapter 3:

Chapter 4:

Chapter 5:

Chapter 6: Design Methods for Algorithms

Lecture slides only form a framework. They are not a substitute for attending a lecture or reading the literature and are not sufficient on their own for a good understanding of the material and the ability to use it.

literature

The lecture is partly based on

  • Christel Baier: Script for the lecture "Computer Science IV - Algorithms and Data Structures", University of Bonn, SS2004. [PDF]

Recommended books

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, 2nd edition, 2001.
  • Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete Mathematics - A Foundation for Computer Science, Addison-Wesley, 2nd edition, 1994.
  • Ralf Hartmut Güting, Stefan Dieker: Data structures and algorithms, Teubner, 3rd edition, 2004.
  • Cornelia Heinisch, Frank Müller, Joachim Goll: Java as the first programming language, Teubner, 4th edition, 2005.
  • Jon Kleinberg, Eva Tardos: Algorithm Design, Addison-Wesley, 2005.
  • Donald E. Knuth: The Art of Computer Programming, Volume I-III, Addison-Wesley, 1969-1973.
  • Peter Pepper: Programming with Java, Springer, 2004.
  • Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstruktur, dpunkt, 3rd revised edition, 2006.
  • Robert Sedgewick: Algorithmen in Java, Pearson Studium, 3rd edition, 2003.

Java books on the net

Useful references