\documentclass[11pt]{article}\pagestyle{empty}
\usepackage{amsmath,amssymb,amsthm,color,graphicx}
\usepackage{euscript}
\usepackage{mathpazo}

\usepackage[top=1.5in,bottom=1.5in,left=1.25in,right=1.25in]{geometry}
%improve trypography

\usepackage{microtype}
\usepackage{fixltx2e}
\usepackage{fullpage}
\usepackage{xspace}
\usepackage{tikz}
\usepackage{enumitem}


{\catcode`\@=11
\gdef\setft#1#2#3{%
\def\@oddfoot{%
{\setbox0=\hbox{#1}%
\setbox1=\hbox{#3}%
\ifdim\wd0>\wd1%
\dimen0=\wd0%
\box0\hfil#2\hfil\hbox to\dimen0{\hfil\hfil\box1}%
\else \dimen0=\wd1%
\hbox to\dimen0{\box0\hfil}\hfil#2\hfil\box1\fi%
}}}}

{\catcode`\@=11
\gdef\sethd#1#2#3{%
\def\@oddhead{\vbox{\hbox to\hsize{{#1}\hfil{#2}\hfil{#3}}%
\vspace{0.06in}%
\hbox to \hsize{\hrulefill}\vspace*{-0.09in}}}
\def\@evenhead{\@oddhead}
	}
}

\def\reals{\mathbb{R}}
\def\sphere{\mathbb{S}}
\def\xx{\mathbf{x}}
\def\hint#1{(\textbf{Hint:} #1)}

\marginparsep=1pt
\oddsidemargin=0.25in
%
%%%%%% A few macros %%%%%%%%%%%%%%%%
\newtheorem{probm}{Problem}
\newenvironment{prob}{\noindent{\bf Problem \addtocounter{probm}{1}
\hspace{-1mm}\theprobm:\hspace{2mm}}}{\vspace{2mm}}

\def\hint#1{\noindent ({\bf Hint:} {\it #1})}
\def\eps{\varepsilon}
\def\conv{\mathop{\mathrm{conv}}}

\parskip=2mm
\sethd{{\sc Assignment 2}}{}{{\sc Course: COMPSCI531D}}
\setft{{\sc Fall 2021}}{{\sc Introduction to Algorithms}}{{\sc Page \thepage}}

\begin{document}
\vspace*{2mm}

\noindent\textbf{Due Date: September 16, 11:59pm}

\noindent In all problems, prove the correctness of your algorithm and analyze its running time.

\begin{prob}[10pts]
	Given an undirected graph $G = (V,E)$, describe an algorithm to detect whether $G$ has a cycle of odd length. 
\end{prob}

\begin{prob}[10pts]
	Given an undirected graph $G = (V, E)$, for a vertex $v\in V$, $G-v$ is obtained by removing $v$ and its incident edges from $G$. Describe an $O(|V|+|E|)$ time algorithm to find a vertex $v\in V$ such that $G-v$ consists of more than one connected components, or report that no such vertex exists. 
\end{prob}

\begin{prob}[10pts]
	Let $G = (V,E)$ be a directed graph with integral and non-negative edge weights. Suppose we have $s, t\in V$ such that the distance from $s$ to $t$ is $O(|V|)$. Describe an $O(|V|+|E|)$ time algorithm to find the length of the shortest path from $s$ to $t$. 
\end{prob}


\end{document}
