Warning! The directory is not yet complete and will be amended until the beginning of the term.
040968 UK Graph Algorithms and Network Flows (MA) (2019S)
Continuous assessment of course work
Labels
Details
max. 30 participants
Language: English
Lecturers
Classes (iCal) - next class is marked with N
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.
Tuesday
05.03.
11:30 - 13:00
Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
Tuesday
05.03.
13:15 - 14:45
Seminarraum 1 Oskar-Morgenstern-Platz 1 Erdgeschoß
Tuesday
19.03.
11:30 - 13:00
Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
Tuesday
19.03.
13:15 - 14:45
Seminarraum 1 Oskar-Morgenstern-Platz 1 Erdgeschoß
Tuesday
26.03.
11:30 - 13:00
Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
Tuesday
26.03.
13:15 - 14:45
Seminarraum 1 Oskar-Morgenstern-Platz 1 Erdgeschoß
Tuesday
02.04.
11:30 - 13:00
Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
Tuesday
02.04.
13:15 - 14:45
Seminarraum 1 Oskar-Morgenstern-Platz 1 Erdgeschoß
Tuesday
09.04.
11:30 - 13:00
Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
Tuesday
09.04.
13:15 - 14:45
Seminarraum 1 Oskar-Morgenstern-Platz 1 Erdgeschoß
Tuesday
30.04.
11:30 - 13:00
Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
Tuesday
30.04.
13:15 - 14:45
Seminarraum 1 Oskar-Morgenstern-Platz 1 Erdgeschoß
Tuesday
07.05.
11:30 - 13:00
Seminarraum 1 Oskar-Morgenstern-Platz 1 Erdgeschoß
Tuesday
14.05.
11:30 - 13:00
Seminarraum 1 Oskar-Morgenstern-Platz 1 Erdgeschoß
Tuesday
14.05.
13:15 - 14:45
Seminarraum 1 Oskar-Morgenstern-Platz 1 Erdgeschoß
Tuesday
21.05.
11:30 - 13:00
Hörsaal 1 Oskar-Morgenstern-Platz 1 Erdgeschoß
Information
Aims, contents and method of the course
Assessment and permitted materials
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)
- 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)
Minimum requirements and assessment criteria
- 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.
- 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.
Examination topics
For the final written exam you have to know:
- the contents of the lecture slides
- the solutions to the blackboard exercises
- the contents of the lecture slides
- the solutions to the blackboard 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
- 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: We 12.06.2019 12:47
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 relationshipsThe 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 measuresThe methods for knowledge transfer and gain are:
- lectures
- student presentations of selected topics
- joint discussions of exercises and according solutions
- practical implementation of algorithms