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

4.00 ECTS (2.00 SWS), SPL 4 - Wirtschaftswissenschaften

Prüfungsimmanente Lehrveranstaltung

Moodle

Details

max. 30 Teilnehmer*innen

Sprache: Englisch

Lehrende

Mario Ruthmair

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

The course is slightly blocked which means that from March to May we will do four units in a row (instead of two units), while in June we have no units at all.
Note that the four units on one day will usually take place in two different rooms.

    
    Dienstag
    05.03.
    11:30 - 13:00
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    05.03.
    13:15 - 14:45
    Seminarraum 1 Oskar-Morgenstern-Platz 1  Erdgeschoß
    
    Dienstag
    19.03.
    11:30 - 13:00
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    19.03.
    13:15 - 14:45
    Seminarraum 1 Oskar-Morgenstern-Platz 1  Erdgeschoß
    
    Dienstag
    26.03.
    11:30 - 13:00
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    26.03.
    13:15 - 14:45
    Seminarraum 1 Oskar-Morgenstern-Platz 1  Erdgeschoß
    
    Dienstag
    02.04.
    11:30 - 13:00
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    02.04.
    13:15 - 14:45
    Seminarraum 1 Oskar-Morgenstern-Platz 1  Erdgeschoß
    
    Dienstag
    09.04.
    11:30 - 13:00
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    09.04.
    13:15 - 14:45
    Seminarraum 1 Oskar-Morgenstern-Platz 1  Erdgeschoß
    
    Dienstag
    30.04.
    11:30 - 13:00
    Seminarraum 3  Oskar-Morgenstern-Platz 1  1.Stock
    
    Dienstag
    30.04.
    13:15 - 14:45
    Seminarraum 1 Oskar-Morgenstern-Platz 1  Erdgeschoß
    
    Dienstag
    07.05.
    11:30 - 13:00
    Seminarraum 1 Oskar-Morgenstern-Platz 1  Erdgeschoß
    
    Dienstag
    14.05.
    11:30 - 13:00
    Seminarraum 1 Oskar-Morgenstern-Platz 1  Erdgeschoß
    
    Dienstag
    14.05.
    13:15 - 14:45
    Seminarraum 1 Oskar-Morgenstern-Platz 1  Erdgeschoß
    
    Dienstag
    21.05.
    11:30 - 13:00
    Hörsaal 1  Oskar-Morgenstern-Platz 1  Erdgeschoß

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
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
- student presentations of selected topics
- joint discussions of exercises and according solutions
- practical implementation of algorithms

Art der Leistungskontrolle und erlaubte Hilfsmittel

Students collect points with the following actions:
- exercise presentations: students present their solutions to given exercises on the blackboard (max. 10 points)
- topic presentations: students present a selected topic in front of the class (max. 20 points)
- programming exercise: students implement a selected algorithm (max. 20 points)
- written exam: no supporting material allowed (max. 60 points)

Mindestanforderungen und Beurteilungsmaßstab

- Attendance at the lecture / exercise / presentation units is NOT required.
- The grade is determined by the total number of points collected:
1: 89+
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 written exam you have to know:
- the contents of the lecture slides
- the solutions to the blackboard 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: Mi 12.06.2019 12:47