In­tro­duc­tion to Al­gorithms

Der Kurs gibt eine Einführung in Entwurf und Analyse von Algorithmen.
The course gives an introduction into the design and analysis of algorithms.

Sortieralgorithmen, Grundlegende Datenstrukturen, Graphen und Graphenalgorithmen, Entwurf und Analyse von Algorithmen (Problemkomplexität, Laufzeit und Speicherplatzkomplexität von Algorithmen, exakte und heuristische Lösungen, probabilistische Ansätze)

Sorting algorithms, basic data structures, graphs and graph algorithms, design and analysis of algorithms (problem complexity, run time and storage complexity of algorithms, exact vs. heuristic solu-tions, probabilistic approaches)

Fachkompetenz / Domain competence:

Die Studierenden sind nach dem Besuch der Lehrveranstaltung in der Lage,

• grundlegende Algorithmen und Datenstrukturen zu beschreiben und zu erklären,
• die behandelten Verfahren selbständig auf neue Beispiele anzuwenden,
• die gefundenen Lösungen bezüglich Laufzeit zu analysieren und zu bewerten,
• die entwickelten Algorithmen zu in einer modernen objektorientierten Programmiersprache zu implementieren.

After attending the course, the students will be able

• to describe and explain basic algorithms and data structures,
• to apply them to new problems,
• to analyze and evaluate the developed solutions with respect to run time,
• to implement the developed algorithms in a modern object oriented programming language.

Fachübergreifende Kompetenzen / Key qualifications:

Die Studierenden können

• die trainierten Problemlösungsstrategien disziplinübergreifend einsetzen
• Lösungen im Team erarbeiten und umsetzen
• die erworbenen Kompetenzen im Selbststudium vertiefen.

The students

• are able to apply the practiced strategies for problem solving across varying disciplines,
• have experience in developing solutions and implementing them together in cooperation with their fellow students,
• know how to improve their competences by private study.

• Vorlesung mit Übung (teilweise am Rechner)
• Programmierprojekt

• Lecture combined with lab course (partly with hands-on programming exercises)
• Programming project

Mathematische Grundlagen (z.B. asymptotisches Verhalten von Funktionen, Wahrscheinlichkeiten)
Mathematical basics (e.g. asymptotic behavior of functions, probabilities)

Grundlage für weiterführende Veranstaltungen im Zweig „Signal and Information Processing“
Basis for advanced courses in specialization “Signal and Information Processing”

Mündliche Prüfung oder Klausur
Oral or written exam

Englisch / English

• T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. 2nd Edition, MIT Press, 2002.
• E. Horowitz, B. Sahni, B. Rajabkaran: Computer Algorithms – C++, 2nd Edition, Computer Science Press, 1998
• V. Aho, J. E. Hopcroft, and J. Ullman, Data Structures and Algorithms. 1st Edition Addison-Wesley, 1983
• R. Sedgewick: Algorithms in C++, Addison-Wesley, 2001.
• M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co Ltd., 1979
• Kopien der Vorlesungfolien / Handouts of Lecture Slides