\documentclass[12pt,oneside]{article}

\usepackage{amsmath}
\usepackage{booktabs}
%\usepackage[onlytext]{MinionPro}
\usepackage[letterpaper, margin=1in]{geometry}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{fancyvrb}

\def\compare{ {\mathrm{compare}} }
\def\swap{ {\mathrm{swap}} }
\def\sort{ {\mathrm{sort}} }
\def\true{ {\mathrm{true}} }
\def\false{ {\mathrm{false}} }
\def\MergeSort{\mathrm{MergeSort}}
\def\QuickSort{\mathrm{QuickSort}}
\def\InsertionSort{\mathrm{InsertionSort}}
\def\RadixSort{\mathrm{RadixSort}}


%% \setlength{\topmargin}{-0.75in}
%% \addtolength{\textheight}{2.00in}
%% \setlength{\parindent}{0in}
\pagestyle{empty}

\begin{document}

\begin{center}
  {\Large Homework 03}\hfill\emph{COSC 311: Algorithms}, Fall 2022\\
  \hrule
\end{center}

\vspace{0.5em}

\noindent\textbf{Due:} Friday, 10/21/2022 at 11:59 pm

\vspace{2em}

\noindent\textbf{Exercise 1.} Suppose you are given an unsorted array $a$ of size $n-1$ where $n = 2^B$ that contains all of the numbers $0$ through $n-1$ (in an arbitrary order) except for a single missing value $m$. The numbers are each represented in binary with $B$ bits, so that $a[i]$ stores the $i$th number, and $a[i][j]$ is the $j$th bit of $a[i]$. Use the divide and conquer strategy to devise an algorithm that finds the missing value $m$ using $O(n)$ bit comparison and swap operations. Use the Master Theorem to justify the running time of your procedure.

\emph{Hint.} Note the similarity with the setup of RadixSort. While RadixSort uses $O(B n)$ bit comparisons and swap operations, your algorithm must use only $O(n)$ such operations.

\vspace{1em}

\noindent\textbf{Exercise 2.} In class, we saw Dijkstra's algorithm for the single-source shortest path problem:

\begin{Verbatim}[numbers=left]
  Dijkstra(V, E, u):
  1. initialize d[u] = 0 and [v] = infinity for all v != u
  2. maintain set S of finalized nodes, initially empty
  3. while S != V do:
       find node v in V - S with minimal d[v]
       add v to S
       for each neighbor x of v
         update d[x] <- min(d[x], d[v] + w(v, x))
       endfor
     endwhile
  4. return d  
\end{Verbatim}

For simplicity, we assumed that $V = \{1, 2, 3,\ldots,n\}$ so that $d $ is an array where $d[x]$ stores the (weighted) distance from $u $ to $x $. This array, however, does not give the actual path from $u $ to $x $, but just the *length* of the shortest such path. Given a shortest path from $u $ to $x $, $P = u e_1 v_1 e_2 v_2 \ldots v_{k-1} e_k x$, we say that $v_{k-1}$ is $x $'s \textbf{parent}. That is, $x $'s parent is the next vertex from $x $ along the shortest path from $x $ to $u $. Observe that $x $'s parent $v $ is $x $'s neighbor satisfying $d[x] = d[v] + w(v, x)$.

\begin{enumerate}
\item Write a modified version of \texttt{Dijkstra} called \texttt{DijkstraPath} that returns an array $p $ such that for each vertex $x $, $p[x]$ stores $x $'s parent. Your algorithm should only differ from \texttt{Dijkstra} in a few lines of (pseudo)code.
\item Write a method \texttt{GetPath(p, u, x)} that given the array $p $ returned by \texttt{DijkstraPath}, \texttt{GetPath(p, u, x)} returns the shortest path from $u$ to $x$. That is, \texttt{GetPath(p, u, x)} should return an array \texttt{path} of length $k + 1$ where \texttt{path[1] = u}, \texttt{path[k + 1] = x}, and $k $ is the number of hops on the shortest (weighted) path from $u $ to $x $ in $G $. The running time of \texttt{GetPath(p, u, x)} should be $O(k)$.
\end{enumerate}

\end{document}
