\documentclass[]{article}
% Required packages.
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{color}
\usepackage{tikz}
\usepackage[utf8]{inputenc}
\usepackage{dsfont}
\usepackage{enumerate}
\usepackage{ifthen}
\let\mathbb\mathds
% Some setup.
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\setcounter{secnumdepth}{0}
\usetikzlibrary{calc}
% Input data macros for \maketitle.
\title{CS 4810: Homework 9}
\author{due 11/26 11:59pm}
\date{(your name + netid)} % TODO: Fill in your own name and netID here.
\sloppy
% The actual document technically begins here.
\begin{document}
\maketitle
Collaborators: (names and netids) % TODO: List the names and netIDs of everyone who collaborated with you on this homework here.
Each problem is worth 33 points.
\section{Problem 1}
Construct a family of directed graphs such that the random-walk algorithm takes exponential time in expectation to solve the \textsc{path} problem on these instances.
%\paragraph{Solution}
\section{Problem 2}
A directed graph is called \emph{strongly connected} if for every pair of vertices, there exists a directed paths between them (in both directions).
Show that the \textsc{path} problem reduces in logarithmic space to the problem of deciding strong connectivity.
%\paragraph{Solution}
\section{Problem 3}
Show that there exists a polynomial-space algorithm for the following problem (from the previous homework)
$$
L = \{ \varphi \mid \forall x. \exists y. \varphi(x,y)=1 \}.
$$
(Here, $\varphi$ is a Boolean formula in variables $x_1,x_2,\ldots$ and $y_1,y_2,\ldots$.)
%\paragraph{Solution}
\end{document}