040968 UK Graph Algorithms and Network Flows (MA) (2020S)

4.00 ECTS (2.00 SWS), SPL 4 - Wirtschaftswissenschaften

Prüfungsimmanente Lehrveranstaltung

Moodle

An/Abmeldung

Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").

Anmeldung von Mo 10.02.2020 09:00 bis Mi 19.02.2020 12:00
Anmeldung von Di 25.02.2020 09:00 bis Mi 26.02.2020 12:00
Abmeldung bis Do 30.04.2020 23:59

Details

max. 30 Teilnehmer*innen

Sprache: Englisch

Lehrende

Mario Ruthmair

Termine (iCal) - nächster Termin ist mit N markiert

Actions due to the current situation:
- Lectures will be recorded and uploaded in Moodle.
- Course material (slides, descriptions, etc.) will be anyway in Moodle.
- Solutions to homework and programming exercises have to be uploaded to Moodle until the corresponding deadlines.
- The final exam will be online in Moodle on June 23, 13-15h:
* at start time the exam can be downloaded as PDF
* you can solve the exercises electronically or on paper, using any resources (open book)
* you upload your solutions as single PDF (including electronic documents, scans, photos) until the end time

    
    Dienstag
    03.03.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    10.03.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Montag
    16.03.
    13:15 - 14:45
    Hörsaal 4  Oskar-Morgenstern-Platz 1  Erdgeschoß
    
    Dienstag
    17.03.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Donnerstag
    19.03.
    09:45 - 11:15
    Hörsaal 6  Oskar-Morgenstern-Platz 1  1.Stock
    
    Donnerstag
    19.03.
    15:00 - 16:30
    Hörsaal 6  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    24.03.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    31.03.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    21.04.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    28.04.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    05.05.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    12.05.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    19.05.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    26.05.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    09.06.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    16.06.
    13:15 - 14:45
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    23.06.
    16:45 - 18:15
    Hörsaal 13  Oskar-Morgenstern-Platz 1  2.Stock

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

Networks are apparent in our daily lives. Typical examples are: electrical and power networks, data networks, traffic networks (streets, rails, airline routes), manufacturing and distribution networks, and (online) social networks.
Graphs are used to model these networks in an abstract way and allow to efficiently solve problems on networks by using standardized graph algorithms.
In detail we discuss:
- matchings (stable marriage problem)
- computational complexity
- graph connectivity and search algorithms
- maximum flows
- shortest paths
Furthermore, we consider tools and algorithms for (social) network analysis:
- community detection
- partitioning and clustering
- strong and weak ties
- positive and negative relationships

The goals of this course are to:
- understand the fundamental concepts of networks
- understand basic graph algorithms
- be able to apply algorithms to network based problems
- be able to analyze networks based on different measures

The methods for knowledge transfer and gain are:
- lectures
- joint discussions of exercises and according solutions
- practical implementation of algorithms

Art der Leistungskontrolle und erlaubte Hilfsmittel

Students collect points with the following actions:
- homework exercises: students prepare solutions to given exercises and upload them in Moodle (max. 20 points)
- programming exercise: students implement a selected algorithm (max. 30 points)
- online open book exam in Moodle (max. 50 points)

Mindestanforderungen und Beurteilungsmaßstab

- Attendance at the lecture / exercise units is NOT required, except for the FIRST lecture on March 3.
- The grade is determined by the total number of points collected:
1: 89 - 100
2: 76 - 88
3: 63 - 75
4: 50 - 62
5: 0 - 49
- There is NO minimal required number of points for each action.

Prüfungsstoff

For the final exam you have to know:
- the contents of the lecture slides
- the solutions to the homework exercises

Literatur

- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, 1990
- D. Jungnickel: Graphen, Netzwerke und Algorithmen, BI Wissenschaftsverlag, 3. Auflage, 1994
- J. Bang-Jensen, G. Gutin: Digraphs: Theory, Algorithms and Applications, Springer, 2001
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993
- D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010
- E. Tardos, J. Kleinberg, Algorithm Design, Addison Wesley, 2005

Zuordnung im Vorlesungsverzeichnis

Letzte Änderung: Mo 07.09.2020 15:20