Achtung! Das Lehrangebot ist noch nicht vollständig und wird bis Semesterbeginn laufend ergänzt.
040968 UK Graph Algorithms and Network Flows (MA) (2021S)
Prüfungsimmanente Lehrveranstaltung
Labels
DIGITAL
An/Abmeldung
Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").
- Anmeldung von Do 11.02.2021 09:00 bis Mo 22.02.2021 12:00
- Anmeldung von Do 25.02.2021 09:00 bis Fr 26.02.2021 12:00
- Abmeldung bis Mi 31.03.2021 23:59
Details
max. 30 Teilnehmer*innen
Sprache: Englisch
Lehrende
Termine (iCal) - nächster Termin ist mit N markiert
Exam: Tue 29.06.2021, 13:30-15:30, online, moodle
- Dienstag 02.03. 13:15 - 14:45 Digital
- Dienstag 09.03. 13:15 - 14:45 Digital
- Dienstag 16.03. 13:15 - 14:45 Digital
- Dienstag 23.03. 13:15 - 14:45 Digital
- Dienstag 13.04. 13:15 - 14:45 Digital
- Dienstag 20.04. 13:15 - 14:45 Digital
- Dienstag 27.04. 13:15 - 14:45 Digital
- Dienstag 04.05. 13:15 - 14:45 Digital
- Dienstag 11.05. 13:15 - 14:45 Digital
- Dienstag 18.05. 13:15 - 14:45 Digital
- Dienstag 01.06. 13:15 - 14:45 Digital
- Dienstag 08.06. 13:15 - 14:45 Digital
- Dienstag 15.06. 13:15 - 14:45 Digital
- Dienstag 22.06. 13:15 - 14:45 Digital
- Dienstag 29.06. 13:15 - 14:45 Digital
Information
Ziele, Inhalte und Methode der Lehrveranstaltung
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 or written exam (max. 50 points)
- 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)
Mindestanforderungen und Beurteilungsmaßstab
- 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.
- 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
- 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
- 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: Fr 12.05.2023 00:13
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 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
- joint discussions of exercises and according solutions
- practical implementation of algorithms