CSE - Honours
22CS951 ADVANCED GRAPH ALGORITHMS
Hours Per Week :
L T P C
3 0 2 4
PREREQUISITE KNOWLEDGE: Basic Logical Thinking and Problem Solving Ability.
Source: https://
COURSE DESCRIPTION AND OBJECTIVES: towardsdatascience.
com/10-graph-
The course will cover some traditional discrete approaches to various graph problems, especially flow algorithms-visually-
problems, and then contrast these approaches with modern, asymptotically faster methods based on explained-e57faa1336f3
combining convex optimization with spectral and combinatorial graph theory.
MODULE-1
UNIT-1 12L+0T+8P=20 Hours
INTRODUCTION
Introduction to Optimization, Convex Geometry, Linear Algebra, Convexity and Second Derivatives,
Gradient Descent and Acceleration.
UNIT-2 12L+0T+8P=20 Hours
SPECTRAL GRAPH THEORY
Introduction to Spectral Graph Theory, Effective Resistance, Gaussian Elimination as Optimization,
Additive Perspective on Gaussian Elimination.
PRACTICES:
●● Implement the gradient descent optimization algorithm with Nesterov Momentum.
●● Assume that S is subset of R^n is a convex set and that the function f : S->R is convex. Suppose
that x1, …, xn belongs to S and theta_1,…,theta_n >= 0 with theta_1,…,theta_n = 1. Prove
that f(theta_1x1 + _ _ _ + theta_nxn) <= theta_1f(x1) + …. + theta_nf(xn)
MODULE-2
UNIT-1 12L+0T+8P=20 Hours
RANDOM MATRIX CONCENTRATION
Introduction to Random Matrix Concentration, Spectral Graph Sparsification, Laplacian Linear Equations,
Classical Algorithms for Maximum Flow
UNIT-2 12L+0T+8P=20 Hours
SEPARATING HYPERPLANE THEOREM
Separating Hyperplane Theorem, Langrange Multipliers, and Convex Duality, Karush-Kuhn-Tucker
Conditions, Fenchel Conjugates, Newton’s Method.
VFSTR 175
CSE - Honours
SKILLS: PRACTICES:
99 Develop ●● Show that the Ford-Fulkerson algorithm may not terminate; moreover, it may converge a value
a deeper
understanding
not equal to the value of the maximum flow.
of fundamental ●● An electric company is setting up a power plant in a foreign country and it has to plan its capacity.
phenomena in The peak period demand for power is given by p1 = 400 − q1 and the off-peak is given by p2
optimization.
= 380 − q2. The variable cost to is 20 per unit (paid in both markets) and capacity costs 10 per
99 Deep dive unit which is only paid once and is used in both periods.
into modern
approaches to ●● Write down the lagrangian and Kuhn-Tucker conditions for this problem
graph algorithms ●● Find the optimal outputs and capacity for this problem.
using convex
optimization
●● How much of the capacity is paid for by each market (i.e. what are the values of λ1 and λ2)?
techniques. ●● Now suppose capacity cost is 30 per unit (paid only once). Find quantities, capacity and
99 Central how much of the capacity is paid for by each market (i.e. λ1 and λ2)?
techniques in the
development of COURSE OUTCOMES:
graph algorithms Upon successful completion of this course, students will have the ability to:
including graph
decomposition
techniques, CO Blooms Module Mapping
Course Outcomes
oblivious routing No. Level No. with POs
etc.
Analyze key concepts in optimization such as first
and second-order optimization, convex duality,
1 multiplicative weights and dual-based methods, Analyze 1 1, 2, 9, 10, 12
acceleration, preconditioning, and non-Euclidean
optimization.
Design convex optimization through the lens of
2 Create 1 1,2,3,9
graph algorithms
Apply the central techniques in the development
of graph algorithms including graph decomposition
3 Apply 2 1, 2, 9, 10, 12
techniques, sparsification, oblivious routing, and
spectral and combinatorial preconditioning.
TEXT BOOKS:
1. Boyd, Stephen, Stephen P. Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge
university press, 2004.
2. Cartan, Henri. Differential calculus. Hermann, 1983.
REFERENCES:
1. Tarjan, Robert Endre. Data structures and network algorithms. Society for industrial and Applied
Mathematics, 1983.
2. Cook, William J., et al. “Combinatorial optimization.” Oberwolfach Reports 5.4 (2009): 2875-
2942.
3. Rockafellar, R. Tyrrell. Convex analysis. Vol. 18. Princeton university press, 1970.
VFSTR 176