This is a second course in algorithms. Topics regarding combinatorial algorithms involving graphs are studied in this course.
Brief listing of topics, which are liable to change as the course proceeds.
1. Network flows
Max-flow problem and the Ford-Fulkerson algorithm, Design and analysis.
max-flow min-cut theorem statement,proof and analysis
Improvements: Preflow-push, Edmonds, Dinics, MPM, with analysis.
2. Application of Network Flows.
Bipartite Matching, Circulation with demands, Survey Design,Airline Scheduling, Image Segmentation
2. Coloring
Brooks theorem, Erdos' result on chromatic number, Vertex coloring and hardness, list coloring, planar graphs,
3. Geometric structures using graphs:
Interval trees Segment Trees, Range trees, Hilbert Trees.
4. Graph Algorithms
Spanning trees, Biconnected Components, SSP-Shortest path(Dijkstra), APSP-shortest path (Bellman-Ford), Hall's Theorem, Matching in general graphs (Edmonds blossom shrinking) with full analysis. Stable Matching with fairness study, Tuttes' condition for matching and application, Max-weighted bipartite matching,
4. Discharging Technique for studying properties of planar graphs.
- Instructor: Swathyprabhu Maharaj
Fundamentals of Linux Programming
Basics in understanding configuration of system services.
Hands-on using mysql.
Bird's view of networking
- Teacher: Swathyprabhu Maharaj