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

4.00 ECTS (2.00 SWS), SPL 4 - Wirtschaftswissenschaften

Continuous assessment of course work

REMOTE

Moodle

Registration/Deregistration

Note: The time of your registration within the registration period has no effect on the allocation of places (no first come, first served).

Registration is open from Th 11.02.2021 09:00 to Mo 22.02.2021 12:00
Registration is open from Th 25.02.2021 09:00 to Fr 26.02.2021 12:00
Deregistration possible until We 31.03.2021 23:59

Details

max. 30 participants

Language: English

Lecturers

Michael Kahr

Classes (iCal) - next class is marked with N

Exam: Tue 29.06.2021, 13:30-15:30, online, moodle

    
    Tuesday
    02.03.
    13:15 - 14:45
    Digital
    
    Tuesday
    09.03.
    13:15 - 14:45
    Digital
    
    Tuesday
    16.03.
    13:15 - 14:45
    Digital
    
    Tuesday
    23.03.
    13:15 - 14:45
    Digital
    
    Tuesday
    13.04.
    13:15 - 14:45
    Digital
    
    Tuesday
    20.04.
    13:15 - 14:45
    Digital
    
    Tuesday
    27.04.
    13:15 - 14:45
    Digital
    
    Tuesday
    04.05.
    13:15 - 14:45
    Digital
    
    Tuesday
    11.05.
    13:15 - 14:45
    Digital
    
    Tuesday
    18.05.
    13:15 - 14:45
    Digital
    
    Tuesday
    01.06.
    13:15 - 14:45
    Digital
    
    Tuesday
    08.06.
    13:15 - 14:45
    Digital
    
    Tuesday
    15.06.
    13:15 - 14:45
    Digital
    
    Tuesday
    22.06.
    13:15 - 14:45
    Digital
    
    Tuesday
    29.06.
    13:15 - 14:45
    Digital

Information

Aims, contents and method of the course

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

Assessment and permitted materials

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 or written exam (max. 50 points)

Minimum requirements and assessment criteria

- Attendance at the lecture / exercise units is NOT required, except for the FIRST lecture on March 2.
- 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.

Examination topics

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

Reading list

- 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

Association in the course directory

Last modified: Fr 12.05.2023 00:13