In­tro­duc­ti­on to Al­go­rithms

Modul
Module

Introduction to Algorithms

Veranstaltungsnummer /
Course ID

L.048.90501

Koordinator /
Coordinator

Hellebrand, Sybille, Prof. Dr. rer. nat.

Lehr- und Forschungseinheit /
Teaching Unit

Fachgebiet Datentechnik
Computer Engineering Group

Typ /
Type

2 V / 2 Ü 
2 L / 2 E

Arbeitspensum / 
Workload

Präsenzphasen / Time of attendance:  45h
Selbststudium / Self-study:  135h
Ges. Arbeitspensum / Total workload:  180h

Leistungspunkte / 
Credits

6

Modulseite /
Module Homepage

http://www.date.uni-paderborn.de

Zeitmodus /
Semester

Wintersemester
winter semester

Kurzbeschreibung / Short Description

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

Inhalt / Contents

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)

Lernergebnisse und Kompetenzen / Learning outcomes and competences

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.

Methodische Umsetzung / Implementation

  • Vorlesung mit Übung (teilweise am Rechner)
  • Programmierprojekt
  • Lecture combined with lab course (partly with hands-on programming exercises)
  • Programming project

Inhaltliche Voraussetzungen / Prerequisites

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

Kombinationshinweise - Überschneidungen / Overlapping modules

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

Prüfungsmodalitäten / Assessments

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

Unterrichtssprache / Teaching Language

Englisch / English

Lernmaterialien, Literaturangaben / Teaching Material, Literature

  • 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