\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx}
\usepackage{enumerate}
\newcommand{\st}{~\mid~}
\newcommand{\ind}{$~~~$}
\name{}
\class{CSE 101 Fall 2018}
\assignment{Homework 3}
\duedate{Due: Tuesday, October 23, 2018 at 11:59pm}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
This homework assignment may be completed in groups of size 1-4. The solutions must be {\bf typed} (using a computer.) Figures and graphs can be hand drawn. For algorithm descriptions we require a high-level English description AND an implementation description. If you find it necessary to also include a pseudo code to help understand your description then feel free to include it.
\newline\newline
Please refer to the course page for requirements in writing up answers for algorithm questions.
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\begin{enumerate}
%FIRST PROBLEM
\item
For each type of graph, give a time analysis for Dijkstra's algorithm using an array for the priority queue and using a binary heap for the priority queue. Which one is more efficient in each case?\\
(6.25 points each.)
\begin{enumerate}
\item
A complete graph on $n$ vertices
\item
A complete bipartite graph on two sets each with $n/2$ vertices.
\item
A $\sqrt{n}\times\sqrt{n}$ grid.
\item
The hypercube of size $n=2^k$. (A hypercube of size $2^k$ is a graph where vertices are binary strings of length $k$ and there is an edge from $b_1$ to $b_2$ if they differ by one bit.)
\end{enumerate}
\bigskip
%SECOND PROBLEM
\item
Say you have $k$ sorted lists, each with $n/k$ elements. Show how to use a heap to merge
all of these lists into a single sorted list in $O(n \log k)$ time. \\
(11 points correct algorithm, 7 points for proof of correctness, 7 points for time analysis and efficiency.)
%THIRD PROBLEM
\item
The following statements may or may not be correct. In each case, either prove it (if it is correct) or give a counterexample (if it is not correct). Always assume that the graph $G=(V,E)$ is undirected, connected and the edge weights are positive. (5 points each)
\begin{enumerate}
\item
If a graph $G$ has more than $|V|-1$ edges, and there is a unique heaviest edge, then this edge cannot be part of a MST.
\item
If $G$ has a cycle with a unique heaviest edge $e$, then $e$ cannot be part of an MST.
\item
Let $e$ be any edge of minimum weight in $G$. Then $e$ must be part of some MST.
\item
If the lightest edge in a graph is unique, then it must be part of every MST.
\item
The shortest path tree computed by Dijkstra's is necessarily an MST.
\end{enumerate}
\bigskip
% FOURTH PROBLEM
\item
Often there are multiple shortest paths between two nodes of a graph. Give a linear-time algorithm for the following task.
\begin{quote}
\emph{Input:} Undirected graph $G=(V,E)$ with unit edge lengths; nodes $u,v\in V$.\\
\emph{Output:} The number of distinct shortest paths from $u$ to $v$.
\end{quote}
(13 points for algorithm description, 6 points proof of correctness 6 points time analysis, space analysis and efficiency.)
\end{enumerate}
\end{document}