Technische Universität Braunschweig
  • Study & Teaching
    • Beginning your Studies
      • Prospective Students
      • Degree Programmes
      • Application
      • Fit4TU
      • Why Braunschweig?
    • During your Studies
      • Fresher's Hub
      • Term Dates
      • Courses
      • Practical Information
      • Beratungsnavi
      • Additional Qualifications
      • Financing and Costs
      • Special Circumstances
      • Health and Well-being
      • Campus life
    • At the End of your Studies
      • Discontinuation and Credentials Certification
      • After graduation
      • Alumni*ae
    • For Teaching Staff
      • Strategy, Offers and Information
      • Learning Management System Stud.IP
    • Contact
      • Study Service Centre
      • Academic Advice Service
      • Student Office
      • Career Service
  • Research
    • Research Profile
      • Core Research Areas
      • Clusters of Excellence at TU Braunschweig
      • Research Projects
      • Research Centres
      • Professors‘ Research Profiles
    • Early Career Researchers
      • Support in the early stages of an academic career
      • PhD-Students
      • Postdocs
      • Junior research group leaders
      • Junior Professorship and Tenure-Track
      • Habilitation
      • Service Offers for Scientists
    • Research Data & Transparency
      • Transparency in Research
      • Research Data
      • Open Access Strategy
      • Digital Research Announcement
    • Research Funding
      • Research Funding Network
      • Research funding
    • Contact
      • Research Services
      • Academy for Graduates
  • International
    • International Students
      • Why Braunschweig?
      • Degree seeking students
      • Exchange Studies
      • TU Braunschweig Summer School
      • Refugees
      • International Student Support
    • Going Abroad
      • Studying abroad
      • Internships abroad
      • Teaching and research abroad
      • Working abroad
    • International Researchers
      • Welcome Support
      • PhD Studies
      • Service for host institutes
    • Language and intercultural competence training
      • Learning German
      • Learning Foreign Languages
      • Intercultural Communication
    • International Profile
      • Internationalisation
      • International Cooperations
      • Strategic Partnerships
      • International networks
    • International House
      • About us
      • Contact & Office Hours
      • News and Events
      • International Days
      • 5th Student Conference: Internationalisation of Higher Education
      • Newsletter, Podcast & Videos
      • Job Advertisements
  • TU Braunschweig
    • Our Profile
      • Aims & Values
      • Regulations and Guidelines
      • Alliances & Partners
      • The University Development Initiative 2030
      • Foundation University
      • Facts & Figures
      • Our History
    • Career
      • Working at TU Braunschweig
      • Vacancies
    • Economy & Business
      • Entrepreneurship
      • Friends & Supporters
    • General Public
      • Check-in for Students
      • The Student House
      • Access to the University Library
    • Media Services
      • Communications and Press Service
      • Services for media
      • Film and photo permits
      • Advices for scientists
      • Topics and stories
    • Contact
      • General Contact
      • Getting here
  • Organisation
    • Presidency & Administration
      • Executive Board
      • Designated Offices
      • Administration
      • Committees
    • Faculties
      • Carl-Friedrich-Gauß-Fakultät
      • Faculty of Life Sciences
      • Faculty of Architecture, Civil Engineering and Environmental Sciences
      • Faculty of Mechanical Engineering
      • Faculty of Electrical Engineering, Information Technology, Physics
      • Faculty of Humanities and Education
    • Institutes
      • Institutes from A to Z
    • Facilities
      • University Library
      • Gauß-IT-Zentrum
      • Professional and Personnel Development
      • International House
      • The Project House of the TU Braunschweig
      • Transfer Service
      • University Sports Center
      • Facilities from A to Z
    • Equal Opportunity Office
      • Equal Opportunity Office
      • Family
      • Diversity for Students
  • Search
  • Quicklinks
    • People Search
    • Webmail
    • cloud.TU Braunschweig
    • Messenger
    • Cafeteria
    • Courses
    • Stud.IP
    • Library Catalogue
    • IT Services
    • Information Portal (employees)
    • Link Collection
    • DE
    • EN
    • IBR YouTube
    • Facebook
    • Instagram
    • YouTube
    • LinkedIn
    • Mastodon
Menu
  • Organisation
  • Faculties
  • Carl-Friedrich-Gauß-Fakultät
  • Institutes
  • Institute of Operating Systems and Computer Networks
  • Courses
  • Summer 2021 Courses
Logo IBR
IBR Login
  • Institute of Operating Systems and Computer Networks
    • News
    • About us
      • Whole Team
      • Directions
      • Floor Plan
      • Projects
      • Publications
      • Software
      • News Archive
    • Connected and Mobile Systems
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
      • Software
      • Datasets
    • Reliable System Software
      • Overview
      • Team
      • Teaching
      • Theses & Jobs
      • Research
      • Publications
    • Algorithms
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
    • Microprocessor Lab
    • Education
      • Summer 2025
      • Winter 2024/2025
      • Theses
    • Services
      • Library
      • Mailinglists
      • Webmail
      • Knowledge Base
      • Wiki
      • Account Management
      • Services Status
    • Spin-Offs
      • Docoloc
      • bliq (formerly AIPARK)
      • Confidential Technologies
    • Research Cooperations
      • IST.hub

Netzwerkalgorithmen

Semester
Summer 2021
Summer 2023Summer 2022Summer 2020
ProgrammesBusiness Information Systems Bachelor, Computer and Communication Systems Engineering Bachelor, Computer Science Bachelor
IBR GroupALG (Prof. Fekete)
TypeLecture & Exercise
Lecturer
Photo
Dr. Arne Schmidt
Wissenschaftlicher Mitarbeiter
aschmidt[[at]]ibr.cs.tu-bs.de
+49 531 3913115
Room 333
Assistant
Photo
Dr. Christian Rieck
Ehemaliger Wissenschaftlicher Mitarbeiter
rieck[[at]]ibr.cs.tu-bs.de
Credits5
Hours2+1+1
Time & Place Lecture: Tuesdays, 11:30 AM - 01:00 PM
Exercises: Thursdays, 11:30 AM - 01:00 PM (roughly biweekly, see schedule)
Small Tutorials: Fridays, 11:30 AM - 01:00 PM (roughly biweekly, see schedule)

You can find the (preliminary) schedule here (updated at 04/08/2021). We will publish changes in the schedule via the mailing list and on this page.
Start Lecture: 04/20/2021
Exercises: 04/22/2021
Small Tutorials: 05/07/2021
Prerequisites keine. (Empfohlen: Algorithmen und Datenstrukturen, Basiswissen NWA)
Certificates

Studienleistung: 50% der Hausaufgabenpunkte
Prüfungsleistung: Erfolgreiche Teilnahme an der Online-Klausur

Registration
Die Anmeldung für die Übungsgruppen ist abgelaufen. Falls Du Dich dennoch für die Übungsgruppen anmelden möchtest, schreibe eine kurze Mail an Dr. Arne Schmidt oder Dr. Christian Rieck mit vollem Namen, Matrikelnummer, Studiengang und Fachsemester
Please login to get more information here as a mitarb member.
Content Die Veranstaltung untersucht Algorithmen und Eigenschaften auf Graphen. Themenbereiche die in der Vorlesung behandelt werden sind:
  • Kostenminimale aufspannende Bäume
  • Kürzeste Wege
  • Maximale Flüsse
  • Maximum Matchings
In der großen Übung werden weitere Themen besprochen, die die Themen der Vorlesung ergänzen und einen Ausblick auf teils schwerere Probleme geben sollen.
References
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: Introduction to Algorithms, MIT Press, 2001.
  • Bernhard Korte, Jens Vygen: Combinatorial Optimization, Springer, 2006. Zugriff der deutschen Version über die UB: [Link]
  • William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver: Combinatorial Optimization, John Wiley & Sons, 2011.

Aktuelles

  • Die letzte Vorlesung (am 20.07.21) findet nicht über YouTube, sondern über BigBluButton (s.u.) statt und wird nicht aufgezeichnet.
  • Aufgrund der Covid-19 Pandemie, findet die Veranstaltung im Sommersemester 2021 online statt.
  • Die Mailingliste steht jetzt zur Anmeldung zur Verfügung (siehe unten!). Bitte meldet euch dort an, weil wir auch dort kurzfristig Informationen zur Veranstaltung (wie zum Beispiel Veranstaltungsbeginn und -art) verteilen.
  • Zur selbständigen Vorbereitung haben wir ein Dokument mit (vorausgesetztem) Basiswissen erstellt.

Vorlesung

Die Vorlesung findet voraussichtlich über YouTube (Playlist) statt. Fragen können beispielsweise über TU-Messenger oder alternativ Discord gestellt werden.

  • VL 1, 20.04.21 - Einführung: [slides], [Satz 2.5], [YouTube], [IBR]
  • VL 2, 27.04.21 - Kruskals Algorithmus: [slides], [Satz 2.9], [Lemma 2.12], [YouTube], [IBR]
  • VL 3, 04.05.21 - Prims Algorithmus: [slides], [Lemma 2.14], [Satz 2.15],[YouTube], [IBR]
  • VL 4, 11.05.21 - Dijkstras Algorithmus: [slides], [Satz 3.8], [YouTube], [IBR]
  • VL 5, 18.05.21 - Algorithmus von Moore, Bellman und Ford: [slides], [Satz 3.10], [YouTube], [IBR]
  • VL 6, 01.06.21 - Algorithmen von Floyd-Warshall und Johnson: [slides], [YouTube], [IBR]
  • VL 7, 08.06.21 - Algorithmus von Ford-Fulkerson: [slides], [YouTube], [IBR]
  • VL 8, 15.06.21 - Algorithmus von Edmonds-Karp: [slides], [Lemma 4.12], [Satz 4.16],[YouTube], [IBR]
  • VL 9, 22.06.21 - Algorithmus von Stoer-Wagner: [slides], [YouTube], [IBR]
  • VL 10, 29.06.21 - Algorithmus von Hopcroft-Karp: [slides], [YouTube], [IBR]
  • VL 11, 06.07.21 - Blossom-Algorithmus: [slides], [YouTube], [IBR]
  • VL 12, 13.07.21 - Ungarische Methode: [slides],[YouTube], [IBR]
  • VL 13, 20.07.21 - Zusammenfassung: [slides]

Die Ergebnisse der Quizze: [MST], [SP], [MaxFlow], [Mat]

Große Übung

Die große Übung findet an den folgenden Donnerstagen jeweils um 11:30 Uhr über BigBlueButton statt.

  • GÜ 0, 22.04.2021. Organisation, Einführung, Rückblick und Ausblick. [slides]
  • GÜ 1, 06.05.2021. Pfadkompression, Bottleneck Spannbaum, Steinerbaum Problem, Komplexität. [notizen]
  • GÜ 2, 20.05.2021. Längste Pfade, Wurmlöcher, Starker Zusammenhang, Abbiegungen. [slides], [notizen], [abbiegungen]
  • GÜ 3, 17.06.2021. Zirkulationen, Flüsse mit unteren Schranken, Matrix-Rounding, Gomory-Hu Bäume. [slides], [Multi-Terminal Network Flows]
  • GÜ 4, 01.07.2021. Metrisches Traveling Salesman Problem. [notizen], [christofides], [slightly improved heuristic]
  • GÜ 5, 15.07.2021. Stabile Matchings, 3D-Matching. [slides], [notizen]

Hausaufgaben

Die Hausaufgabenblätter findet ihr ab dem jeweiligen Datum hier. Hausaufgabenblatt 0 dient der persönlichen Vorbereitung und ist nicht relevant für die Studienleistung. Bitte beachtet den Hinweiszettel und die Merkzettel zu Beweisen, Laufzeiten und Pseudocode.

  • Hausaufgabenblatt 0 vom 19.04.2021.
  • Hausaufgabenblatt 1 vom 03.05.2021. Abgabe bis Sonntag, den 16. Mai 2021.
  • Hausaufgabenblatt 2 vom 17.05.2021. Abgabe bis Sonntag, den 06. Juni 2021.
  • Hausaufgabenblatt 3 vom 07.06.2021. Abgabe bis Sonntag, den 20. Juni 2021.
  • Hausaufgabenblatt 4 vom 21.06.2021. Abgabe bis Sonntag, den 04. Juli 2021.
    (Es wurde eine Index-Regel für verschmolzene Knoten hinzugefügt. Stand: 28.06.21)
  • Hausaufgabenblatt 5 vom 05.07.2021. Abgabe bis Sonntag, den 18. Juli 2021.

Die kleinen Übungen finden ab dem 07.05.21 jede zweite Vorlesungswoche über BigBlueButton statt. Der Link zu den jeweiligen Räumen und die Gruppeneinteilung können der nachstehenden Tabelle entnommen werden.

Gruppe Tutor Zeit Raum Teilnehmer
1 Marlin Melansek Fr., 11:30 - 13:00 BigBlueButton Raum 1 Nachnamen: A bis K
2 Tobias Wallner Fr., 11:30 - 13:00 BigBlueButton Raum 2 Nachnamen: L bis Z

Klausur

Die Klausur findet am Montag, den 16.08.2021 zwischen 08:15 Uhr und 10:15 Uhr über EvaExam statt. Die Informationen zur NWA-Klausur sind analog zu der von AuD (siehe Beitragsseite von AuD).

  • Die Klausur startet um 08:15 Uhr und endet um 10:15 Uhr.
  • Sie haben 2 Stunden Zeit für die Bearbeitung
  • Eine TAN zur Teilnahme wird etwa 30 Minuten vor Beginn der Klausur per Mail an Ihre tubs-Adresse versandt.
  • Für Fragen steht ein BigBlueButton Raum zur Verfügung
  • Bei Internetproblemen melden Sie sich per Telefon bei Arne Schmidt (0531 391 3115) oder Christian Rieck (0531 391 3114).
  • Nach der Prüfung muss ein Scan der Selbständigkeitserklärung (siehe Cloudstorage) in unsere Nextcloud hochgeladen werden: https://nextcloud.ibr.cs.tu-bs.de/s/NNcANwpjBHbssAE (Format für den Dateinamen: Nachname_Name_Matrikelnummer)

Wiederholungsprüfung

Die Wiederholungsprüfung wird als mündliche Prüfung geplant. Sobald die Anmeldungen zur Prüfung beim Prüfungsamt abgeschlossen ist, melden wir uns per Mail.

Mailingliste

Es gibt eine Mailingliste zu dieser Vorlesung. Bitte meldet euch an, denn wir werden sie nutzen, um kurzfristig Informationen zu verteilen. Um Spam und Probleme zu vermeiden, können nur Mailadressen der TU Braunschweig freigegeben werden. Solltet ihr technische Schwierigkeiten bei der Anmeldung haben, meldet euch bitte direkt per Mail bei Christian.


last changed 2022-04-19, 16:21 (dynamic content) by Dr. Christian Rieck

For All Visitors

Vacancies of TU Braunschweig
Career Service' Job Exchange 
Merchandising

For Students

Term Dates
Courses
Degree Programmes
Information for Freshman
TUCard

Internal Tools

Glossary (GER-EN)
Change your Personal Data

Contact

Technische Universität Braunschweig
Universitätsplatz 2
38106 Braunschweig

P. O. Box: 38092 Braunschweig
GERMANY

Phone: +49 (0) 531 391-0

Getting here

© Technische Universität Braunschweig
Imprint Privacy Accessibility