\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{fullpage}
\usepackage{tikz}
\usetikzlibrary{positioning}
\begin{document}
\noindent
CS 161 \hfill \textbf{Problem Set 5} \newline
{Spring 2017} \hfill \textbf{Due:} May 19, 2017, 3pm
\noindent
\rule{\linewidth}{0.4pt}
\noindent
Please answer each of the following problems. Refer to the course webpage for
the \textbf{collaboration policy,} as well as for \textbf{helpful advice} for
how to write up your solutions.
\\\\
\textbf{Note:} For all problems, if you include pseudocode in your solution,
please also include a brief English description of what the pseudocode does.
\\\\
\textbf{Drawing graphs:} You might try \texttt{http://madebyevan.com/fsm/} which
allows you to draw graphs with your mouse and convert it into \LaTeX \,code:
\begin{center}
%%%%%%% GENERATED AUTOMATICALLY BY madebyevan.com/fsm/
\begin{tikzpicture}[scale=0.1]
\tikzstyle{every node}+=[inner sep=0pt]
\draw [black] (26.7,-13.3) circle (3);
\draw (26.7,-13.3) node {C};
\draw [black] (45.6,-14.7) circle (3);
\draw (45.6,-14.7) node {$1$};
\draw [black] (33.8,-17.5) circle (3);
\draw (33.8,-17.5) node {S};
\draw [black] (54.5,-17.5) circle (3);
\draw (54.5,-17.5) node {$6$};
\draw [black] (62.2,-13.3) circle (3);
\draw (62.2,-13.3) node {$1$};
\draw [black] (42.68,-15.39) -- (36.72,-16.81);
\fill [black] (36.72,-16.81) -- (37.61,-17.11) -- (37.38,-16.14);
\draw [black] (31.22,-15.97) -- (29.28,-14.83);
\fill [black] (29.28,-14.83) -- (29.72,-15.67) -- (30.23,-14.8);
\draw [black] (48.46,-15.6) -- (51.64,-16.6);
\fill [black] (51.64,-16.6) -- (51.03,-15.88) -- (50.73,-16.84);
\draw [black] (57.13,-16.06) -- (59.57,-14.74);
\fill [black] (59.57,-14.74) -- (58.62,-14.68) -- (59.1,-15.56);
\draw [black] (28.907,-11.271) arc (129.11449:50.88551:24.638);
\fill [black] (59.99,-11.27) -- (59.69,-10.38) -- (59.06,-11.15);
\draw [black] (65.108,-12.614) arc (131.00538:-156.99462:2.25);
\fill [black] (64.51,-15.19) -- (64.66,-16.12) -- (65.42,-15.47);
\end{tikzpicture}
\end{center}
\rule{\linewidth}{0.4pt}
\begin{enumerate}
\item \textbf{(Examples.)} (4 points) Give one example of a directed graph on
four vertices, A, B, C, and D, so that both depth-first search and breadth-first
search discover the vertices in the same order when started at A. Give one
example of an directed graph where BFS and DFS discover the vertices in a
different order when started at A. Above, \em discover \em means the time that
the algorithm first reaches the vertex. Assume that both DFS and BFS iterate
over outgoing neighbors in alphabetical order.
\textbf{[We are expecting: a drawing of your graphs and an ordered list of
vertices discovered by BFS and DFS.]}
%%%%%%%%%%%% PROBLEM 2
\vspace{1cm}
\item \textbf{(In-order traversal)} (6 points)
In class, we stated the fact that Depth-First Search can be used to do in-order
traversal of a binary search tree. That is, given a binary search tree $T$
containing $n$ distinct elements $a_1 < a_2 < \cdots < a_n$, DFS can be used to
return an array $[a_1,a_2,\ldots,a_n]$ containing these elements in sorted
order. Call this algorithm \texttt{inOrderTraversal}. Work out the details for
this algorithm, and answer the following questions:
\begin{enumerate}
\item(3 pts) Give pseudocode for \texttt{inOrderTraversal}. For your
pseudocode, assume that each node in $T$ has a key value (one of the $a_i$) and
pointers to its left and right children, and that if a vertex has no child this
is represented as a \texttt{NIL} child.
\item(2 pts) What is the asymptotic running time of \texttt{inOrderTraversal},
in terms of $n$? We're looking for a statement of the form ``the running time
is $\Theta(\_\_\_)$.''
\item(1 pt) Does the algorithm need to look at the values $a_1,\ldots,a_n$
(other than to return the values)?
\end{enumerate}
\textbf{[We are expecting: just the answers to these questions, no justification
needed.]}
%%%%%% PROBLEM 3
\vspace{1cm}
\item \textbf{(Too good to be true)} (6 points)
Your friend claims to have built a new kind of binary search tree with $O(1)$
(deterministic) insertion time (better than the $O(\log(n))$ of red-black
trees), which can handle arbitrary comparable objects. How do you know they are
wrong?
\textbf{[We are expecting: a short but formal proof that your friend is wrong.]}
\newpage
%%%%%%%%%%%% PROBLEM 4
\item \textbf{(Dijkstra and negative edge weights)} (15 points)
Let $G = (V,E)$ be a weighted directed graph. For the rest of this problem,
assume that $s,t \in V$ and that \textbf{there is a directed path from $s$ to
$t$}. The weights on $G$ could be anything: \textbf{negative, zero, or
positive.}
For the rest of this problem, refer to the implementation of Dijkstra's
algorithm given by the pseudocode below.
\begin{verbatim}
Dijkstra_st_path(G, s, t):
for all v in V, set d[v] = Infinity
for all v in V, set p[v] = None
// we will use the information p[v] to reconstruct the path at the end.
d[s] = 0
F = V
D = []
while F isn't empty:
x = a vertex v in F so that d[v] is minimized
for y in x.outgoing_neighbors:
d[y] = min( d[y], d[x] + weight(x,y) )
if d[y] was changed in the previous line, set p[y] = x
F.remove(x)
D.add(x)
// use the information in p to reconstruct the shortest path:
path = [t]
current = t
while current != s:
current = p[current]
add current to the front of the path
return path, d[t]
\end{verbatim}
Notice that the pseudocode above differs from the pseudocode in the notes: first
it runs Dijkstra's algorithm (as presented in the notes), and then it uses this
to compute the shortest path from s to t. It returns the shortest path and the
cost of that path.
\begin{enumerate}
\item (2 points) Step through \texttt{Dijkstra\_st\_path}$(G,s,t)$ on the
graph $G$ shown below.
Complete the table below to show what the arrays \texttt{d} and
\texttt{p} are at each step of the algorithm, and indicate what path is returned
and what its cost is.
\begin{center}
\begin{tikzpicture}[scale=0.15]
\tikzstyle{every node}+=[inner sep=0pt]
\draw [black] (20.7,-26.5) circle (3);
\draw (20.7,-26.5) node {$s$};
\draw [black] (34.4,-26.5) circle (3);
\draw (34.4,-26.5) node {$u$};
\draw [black] (49.4,-19.9) circle (3);
\draw (49.4,-19.9) node {$v$};
\draw [black] (49.4,-33.1) circle (3);
\draw (49.4,-33.1) node {$t$};
\draw [black] (23.7,-26.5) -- (31.4,-26.5);
\fill [black] (31.4,-26.5) -- (30.6,-26) -- (30.6,-27);
\draw (27.55,-27) node [below] {$3$};
\draw [black] (37.15,-25.29) -- (46.65,-21.11);
\fill [black] (46.65,-21.11) -- (45.72,-20.97) -- (46.12,-21.89);
\draw (42.88,-23.71) node [below] {$2$};
\draw [black] (49.4,-22.9) -- (49.4,-30.1);
\fill [black] (49.4,-30.1) -- (49.9,-29.3) -- (48.9,-29.3);
\draw (48.9,-26.5) node [left] {$1$};
\draw [black] (37.15,-27.71) -- (46.65,-31.89);
\fill [black] (46.65,-31.89) -- (46.12,-31.11) -- (45.72,-32.03);
\draw (40.92,-30.31) node [below] {$4$};
\node at (10,-30) {$G$};
\end{tikzpicture}
\end{center}
\textbf{[We are expecting: the table below filled out, as well as the final
shortest path and its cost. No further justification is required.]}
%%%%%%%%%%%%%%%%%%% TABLE: Fill in your answers between the & symbols below if
%you wish to take this LaTeX code for your solution.
\begin{center}
\def\arraystretch{1.5}
\newcommand{\td}{\texttt{d}}
\newcommand{\tp}{\texttt{p}}
\begin{tabular}{|p{6cm}||c|c|c|c||c|c|c|c|}
\hline
& \td[$s$] & \td[$u$] & \td[$v$] & \td[$t$] & \tp[$s$] & \tp[$u$] & \tp[$v$] &
\tp[$t$] \\
\hline
When entering the first while loop for the first time, the state is:&
0 & $\infty$ & $\infty$ & $\infty$ & None & None & None & None \\
\hline
Immediately after the first element of $D$ is added, the state is: &
0 & $3$ & $\infty$ & $\infty$ & None & s & None & None \\
\hline
Immediately after the second element of $D$ is added, the state is: &
& & & & & & & \\
\hline
Immediately after the third element of $D$ is added, the state is: &
& & & & & & & \\
\hline
Immediately after the fourth element of $D$ is added, the state is: &
& & & & & & & \\
\hline
\end{tabular}
\end{center}
%%%%%%%%%% END TABLE %%%%%%%%%%%%%
\item (3 points) \textbf{Prove or disprove}: In every such graph $G$, the
shortest path from $s$ to $t$ exists. Here, a \em path \em from $s$ to $t$ is
formally defined as a sequence of edges
\[ (u_0,u_1), (u_1, u_2), (u_2,u_3), \ldots, (u_{M-1}, u_M)\]
so that $u_0 = s$, $u_M = t$, and $(u_i, u_{i+1}) \in E$ for all
$i=0,\ldots,M-1$. A \em shortest path \em is a path
$((u_0,u_1),\ldots,(u_{M-1},u_M))$ so that
\[ \sum_{i=0}^{M-1} \mathrm{weight}(u_i,u_{i+1}) \leq \sum_{i=0}^{M'-1}
\mathrm{weight}(u'_i, u_{i+1}')\]
for all paths $((u'_0, u'_1),\ldots, (u'_{M'-1}, u'_{M'}))$.
\item (3 points) \textbf{Prove or disprove}: In every such graph $G$ in
which the shortest path from $s$ to $t$ exists, \texttt{Dijkstra\_st\_path}$(G,
s,t)$ returns a shortest path between $s$ and $t$ in $G$.
\item (3 points) \textbf{Prove or disprove}: In every such graph $G$ in
which there is a negative-weight edge, and for all $s$ and $t$,
\texttt{Dijkstra\_st\_path}$(G, s,t)$ does not return a shortest path between
$s$ and $t$ in $G$.
\item (4 points) Your friend offers the following way to patch up
Dijkstra's algorithm to deal with negative edge weights. Let $G$ be a weighted
graph, and let $w^*$ be the smallest weight that appears in $G$. (Notice that
$w^*$ may be negative). Consider a graph $G' = (V,E')$ with the same vertices,
and so that $E'$ is as follows: for every edge $e \in E$ with weight $w$, there
is an edge $e' \in E'$ with weight $w - w^*$. Now all of the weights in $G'$
are non-negative, so we can apply Dijkstra's algorithm to that:
\begin{verbatim}
modifiedDijkstra(G,s,t):
Construct G' from G as above.
return Dijkstra_st_path(G',s,t)
\end{verbatim}
\textbf{Prove or disprove}: Your friend's approach will always correctly
return a shortest path between $s$ and $t$ if it exists.
\end{enumerate}
\textbf{[We are expecting: for each ``prove or disprove," either a proof or
a (small) counterexample. In the previous sentence, ``(small)" means no more
than 5 vertices.]}
\newpage
\item \textbf{(Social engineering)} (13 points)
Suppose we have a community of $n$ people. We can create a directed graph from
this community as follows: the vertices are people, and there is a directed edge
from person $A$ to person $B$ if $A$ would forward a rumor to $B$. Assume that
if there is an edge from $A$ to $B$, then $A$ will always forward any rumor they
hear to $B$.
Notice that this relationship isn't symmetric: $A$ might gossip to $B$ but not
vice versa.
Suppose there are $m$ directed edges total, so $G = (V,E)$ is a graph with $n$
vertices and $m$ edges.
Define a person $P$ to be \em influential \em if for all other people $A$ in the
community, there is a directed path from $P$ to $A$ in $G$. Thus, if you tell a
rumor to an influential person $P$, eventually the rumor will reach everybody.
You have a rumor that you'd like to spread, but you don't have time to tell more
than one person, so you'd like to find an influential person to tell the rumor
to.
In the following questions, assume that $G$ is the directed graph representing
the community, and that you have access to $G$ as an array of adjacency lists:
for each vertex $v$, in $O(1)$ time you can get a pointer to the head of the
linked lists $v$\texttt{.outgoing\_neighbors} and
$v$\texttt{.incoming\_neighbors}. Notice that $G$ is not necessarily acyclic.
In your answers, you may appeal to any statements we have seen in class, in the
notes, or in CLRS.
\begin{enumerate}
\item(2 pts) Show that all influential people in $G$ are in the same
strongly connected component, and that everyone in this strongly connected
component is influential.
\textbf{[We are expecting: a short but formal proof.]}
\item(8 pts)
Suppose that an influential person exists.
Give an algorithm that, given $G$, finds an influential person in time $O(n
+ m)$.
\textbf{[We are expecting: pseudocode, a proof of correctness, and a short
argument about the runtime.]}
\item(3 pts)
Suppose that you don't know whether or not an influential person exists.
Use your algorithm from part (b) to give an algorithm that, given $G$, either
finds an influential person in time $O(n + m)$ if there is one, or else returns
``no influential person.''
\textbf{[We are expecting: pseudocode, and a short argument for both
correctness and runtime. You do not need to re-write your algorithm from part
(b), you can just call it.]}
\end{enumerate}
%%%%%% END PROBLEMS.
\end{enumerate}
\end{document}