040968 UK Graph Algorithms and Network Flows (2011S)
- Registration is open from Mo 07.02.2011 09:00 to Th 17.02.2011 17:00
- Registration is open from We 23.02.2011 09:00 to Fr 11.03.2011 14:00
- Deregistration possible until Mo 14.03.2011 23:59
Classes (iCal) - next class is marked with N
Aims, contents and method of the course
Assessment and permitted materials
- Presentation of a selected topic (15%)
- Oral exam (60%)At least 60% in total are needed to pass the exam.
Minimum requirements and assessment criteria
b) develop models and algorithms to design, manage and analyse networks.
- Graph Traversal Algorithms. Topological Ordering.
- Dynamic Programming. Shortest Path Algorithms.
- Greedy Algorithms. Minimum Spanning Tree.
- Flow Algorithms.2) Analysis of social networks
- Graph partitioning (strong and week ties, betweenness measures)
- Networks in their surrounding contexts: homophily, affiliation
- Positive and negative relationships: structural balance, weaker form of structural balance, generalization
- Cascading behavior in networks: diffusion, cascades and clusters. Knowledge, threshold and collective action. The cascade capacity.
- Spreading epidemics in networks: branching process, SIR vs. SIS epidemic model. Analysis of branching process.
* Algorithm Design, by Eva Tardos, Jon Kleinberg
* Networks, Crowds, and Markets: Reasoning About a Highly Connected World, by David Easley and