\documentclass{exam}
 
 \usepackage{graphicx}
 \usepackage{float}
 \usepackage{amsmath}
 \usepackage{mdframed}
 \usepackage{xcolor}
 
% First, we setup the header and footer
\pagestyle{headandfoot}
\runningheadrule
\runningfootrule
\header{COL702: Advanced Data Structures and Algorithms (CSE, IITD, Semester-I-2024-25)}{}{Homework-6}
\footer{}{\thepage  \, of \numpages}{}
 
% We want the points for each question displayed on the left
%\pointname{points}
%\pointsinmargin
 
% Automatically total the points - make sure to compile TWICE
\addpoints
 
\begin{document}
 
\begin{center} 
\fbox{\parbox{5.5in}{
\vspace{-0.1in}
\begin{itemize}
\item \small{The instructions are the same as in Homework 1--5.}
\end{itemize}
\vspace{-0.1in}
}}
\end{center}

\vspace{0.1in}


\vspace{0.1in}
% Some general text together with several questions and total points possible
There are \numquestions\, questions for a total of \numpoints\, points.
\vspace{0.1in}
\hrule
 \vspace{0.2in}
\begin{questions}
 
\question Solve the following two problems:
\begin{parts}
\part[10] An edge in a network flow graph is called {\em downwards critical} if decreasing the capacity of this edge decreases the maximum flow in the network. Design an algorithm to find a downwards critical edge in a network. Give pseudocode, discuss running time and give proof of correctness.



\part[15] An edge in a network flow graph is called {\em upwards critical} if increasing the capacity of this edge increases the maximum flow in the network. Design an algorithm to find an upwards critical edge in a network in case there exists one.
Give pseudocode, discuss running time and give proof of correctness.
\end{parts}


\vspace{0.3in}


\question[25] Design an algorithm that outputs a minimum vertex cover of a given bipartite graph $G = (L, R, E)$. Give pseudocode, discuss running time and give proof of correctness.
 
 
 \vspace{0.3in}
 
\question[25] You are given $n$ pairs of integers $(d_1, d_1'), ..., (d_n, d_n')$ such that $\forall i, d_i, d_i' \geq 0$. 
You have to design an algorithm that determines if there exists a directed  graph $G=(\{1,...,n\}, E)$ such that the in-degree of vertex $i$ is $d_i$ and the out-degree of vertex $i$ is $d_i'$. 
Your algorithm should also output a graph with the given degree sequence, in case there exists one. 
Give pseudocode, discuss running time and give proof of correctness.


\end{questions}
\end{document}