248 lines
8.7 KiB
TeX
248 lines
8.7 KiB
TeX
% vim: set ts=2 sw=2 tw=80 et:
|
|
\documentclass[12pt]{article}
|
|
|
|
\usepackage[margin=3cm]{geometry}
|
|
\usepackage{xcolor}
|
|
\usepackage{lmodern}
|
|
\usepackage{listings}
|
|
\usepackage{hyperref}
|
|
|
|
\title{Graded Assignment 4 -- DSA}
|
|
\author{Claudio Maggioni}
|
|
\setlength{\parindent}{0cm}
|
|
|
|
% listings configuration
|
|
\lstset{
|
|
basicstyle=\small\ttfamily,
|
|
frame=shadowbox,
|
|
xleftmargin=10mm, % Move everything 10mm to the right
|
|
framexleftmargin=10mm, % Make the frame 10mm wider to the left
|
|
numbers=left, % Add numbers to the left of the code
|
|
rulesepcolor=\color{black},
|
|
columns=fullflexible,
|
|
commentstyle=\color{gray},
|
|
keywordstyle=\bfseries,
|
|
keywords={,NIL,while,if,elif,else,continue,FUNCTION,return,for,from,to,TRUE,FALSE,not,},
|
|
mathescape=true,
|
|
aboveskip=2em,
|
|
captionpos=b,
|
|
abovecaptionskip=1em,
|
|
belowcaptionskip=1em,
|
|
}
|
|
|
|
\begin{document}
|
|
|
|
\maketitle
|
|
\tableofcontents
|
|
\lstlistoflistings
|
|
{\color{white}{Will these be the right solutions? I have the answer: \url{https://imgur.com/a/yk9RPFs}}}
|
|
\newpage
|
|
|
|
\section{Exercise 1}
|
|
|
|
\begin{lstlisting}[caption=Solution for exercise 1, label={lst:ex1}]
|
|
FUNCTION BEST-PATH(G=(V,E), v, w):
|
|
P[V(G)[0]] = NIL
|
|
|
|
for each vertex u $\in$ V(G):
|
|
prev_start[u] = NIL
|
|
prev_end[u] = NIL
|
|
|
|
prev_start[v] = START $(\textit{non-NIL})$
|
|
prev_end[w] = END $(\textit{non-NIL})$
|
|
|
|
HELP-SETUP(G, P, Adj[V(G)[0]], V(G)[0])
|
|
|
|
s = v
|
|
e = w
|
|
|
|
while prev_end[s] is NIL and prev_start[e] is NIL:
|
|
if P[s] is not NIL:
|
|
prev_start[P[s]] = s
|
|
s = P[s]
|
|
if P[e] is not NIL:
|
|
prev_end[P[e]] = e
|
|
e = P[e]
|
|
|
|
if prev_end[s] is not NIL:
|
|
n = s
|
|
else:
|
|
n = e
|
|
|
|
while s is not v:
|
|
s = prev_start[s]
|
|
prev_end[s] = P[s]
|
|
|
|
s = v
|
|
while s != w:
|
|
print(s)
|
|
s = prev_end[s]
|
|
if v != w:
|
|
print(w)
|
|
|
|
FUNCTION HELP-SETUP(G=(V,E), P, S, v):
|
|
for each vertex u $\in$ S:
|
|
P[u] = v
|
|
HELP-SETUP(G, P, Adj[u] \ {v}, u)
|
|
|
|
\end{lstlisting}
|
|
|
|
The $O(n)$ setup happens between line 2 and line 14. This is mainly needed to initialize some help arrays and define an
|
|
arbitrary root (and consequent parent relation) on the tree.
|
|
|
|
The rest of the algorithm walks the tree from the start to the root and from the end to the root concurrently, keeping track of the
|
|
path taken and stopping when an edge was traversed by both walks. Then, the path memory to the start is reversed and inserted in the
|
|
path memory for the end in order to obtain a mapping to the next node in the path from $v$ to $w$. This mapping is then printed.
|
|
The complexity of this step is $O(dist(v,w))$, since the number of traversed edges is at most two times the
|
|
distance from $v$ to $w$, and the reversing operation
|
|
at the end requires at most $dist(v,w)$ steps, as the printing operation.
|
|
|
|
\section{Exercise 2}
|
|
|
|
\begin{lstlisting}[caption=Solution for exercise 2, label={lst:ex2}]
|
|
FUNCTION CONNECTED-COMPONENTS(G=(V,E)):
|
|
for each vertex u $\in$ V(G):
|
|
color[u] = WHITE
|
|
|
|
c = 0
|
|
|
|
for each vertex s $\in$ V(G):
|
|
if color[u] $\neq$ WHITE:
|
|
continue
|
|
|
|
color[s] = GRAY
|
|
Q = $\emptyset$
|
|
c = c + 1
|
|
ENQUEUE(Q, s)
|
|
|
|
while Q $\neq \emptyset$:
|
|
u = DEQUEUE(Q)
|
|
for each v $\in$ Adj[u]:
|
|
if color[v] == WHITE:
|
|
color[v] = GRAY
|
|
ENQUEUE(Q, v)
|
|
color[u] = BLACK
|
|
|
|
return c
|
|
\end{lstlisting}
|
|
|
|
The algorithm is simply a modified color-only version of BFS with an extra iteration: using every vertex in the graph as a starting
|
|
node. If the node was already visited, the color makes this iteration over all vertexes skip to the next vertex. The complexity of
|
|
this algorithm is $O(|V| + |E|)$ like BFS, since the iterative application to BFS over every connected component will cover every edge
|
|
and node of the graph exactly once, and the extra check for nodes being which is just another $O(|V|)$ cost, which can be ignored.
|
|
|
|
\section{Exercise 3}
|
|
|
|
Assume data is provided in Graph-like form $G=(V,E)$ where $V$ is the set of butterflies, $E$ is the set of edges, and a relation
|
|
$o : E \to \textsc{true, false}$ where \textsc{false} means ``same'' and \textsc{true} means ``different'' to determine the the type
|
|
of observation. Ambiguous observations are not included in $E(G)$ in the
|
|
first place, so $o$ does not have to be defined for this case.
|
|
|
|
\begin{lstlisting}[caption=Solution for exercise 3, label={lst:ex3}]
|
|
FUNCTION OBSERVATION-HOLDS(G=(V,E), o):
|
|
for each vertex u $\in$ V(G):
|
|
color[u] = WHITE
|
|
species[u] = NIL
|
|
|
|
for each vertex u $\in$ V(G):
|
|
if color[u] $\neq$ WHITE:
|
|
continue
|
|
species[u] = FALSE
|
|
if not DFS-CHECK-OBSERVATION(species, o, v):
|
|
return FALSE
|
|
|
|
return TRUE
|
|
|
|
FUNCTION DFS-CHECK-OBSERVATION(species, o, v):
|
|
color[u] = GREY
|
|
|
|
for each vertex v $\in$ Adj[u]:
|
|
if color[v] == WHITE:
|
|
species[v] = species[u] XOR o($\textit{edge}$ (u, v))
|
|
if not DFS-CHECK-OBSERVATION(species, o, v):
|
|
return FALSE
|
|
else:
|
|
if species[u] $\neq$ species[v] XOR o($\textit{edge}$ (v, u)) $\lor$
|
|
species[v] $\neq$ species[u] XOR o($\textit{edge}$ (u, v)):
|
|
return FALSE
|
|
|
|
color[u] = BLACK
|
|
return TRUE
|
|
\end{lstlisting}
|
|
|
|
The code given traverses $G$ using a modified DFS by first assigning an arbitrary species (\texttt{FALSE}) to the first
|
|
vertex encountered, then by computing the species of the subsequent nodes encountered using the observation mapping $o : E \to
|
|
\textsc{true, false}$. A XOR is used to assign the opposite species (flip the species[\ldots] bit) to the newly discovered node
|
|
if $o(\textsc{current node, new node})$ is ``different'', and to assign the same species if the observation is ``same''
|
|
\footnote{\textsc{true, false} mean ``different'' and ``same'' when they are result of $o(\ldots)$. When assigning to
|
|
\texttt{species[\ldots]}, they represent an arbitrary assignment of the two species of butterfly.}.
|
|
|
|
Paths between already visited vertexes (non-white vertexes) are checked in order to find inconsistencies. Both edge traversal
|
|
directions are checked in order to handle cases where observation are directed (i.e. $o(\textit{edge} (v, u)) \neq
|
|
o(\textit{edge} (v, u)))$. If an inconsistency is found, we return \texttt{FALSE}, otherwise we return true.
|
|
|
|
Note that if the observation graph $G$ is composed by more than one connected component assigning an arbitrary species to the first
|
|
vertex encountered in each connected component does not compromise the solutions, since we are not asked to find the correct species
|
|
assignment but we are just asked to find inconsistencies.
|
|
|
|
\section{Exercise 4}
|
|
|
|
\subsection{Point 1}
|
|
|
|
We assume the minimum spanning tree $T$ is represented as an adjacency-mapped graph. \textit{weight} is the weight mapping for every
|
|
edge in the minimal spanning tree. The other parameters must be given as described in the assignment.
|
|
|
|
\begin{lstlisting}[caption=Solution for exercise 4 point 1, label={lst:ex4p1}]
|
|
FUNCTION IS-MST-MINIMAL(T=(V,E), weight, v, w, c):
|
|
P[w] = NIL
|
|
DEFINE-PARENT(T, P, Adj[w], w)
|
|
s = v
|
|
while s $\neq$ w:
|
|
edge_w = weight($\textit{edge}$ (s, P[s]))
|
|
if edge_w > c:
|
|
return FALSE
|
|
s = P[s]
|
|
|
|
return TRUE
|
|
|
|
FUNCTION DEFINE-PARENT(G=(V,E), P, S, v):
|
|
for each vertex u $\in$ S:
|
|
P[u] = v
|
|
DEFINE-PARENT(G, P, Adj[u] \ {v}, u)
|
|
\end{lstlisting}
|
|
|
|
The algorithm works by walking the entire tree with \texttt{DEFINE-PARENT} in order to define a parent relation considering $w$ as
|
|
the root. Then, this relation is used to define the path between $v$ and $w$, and the weights of every edge in the path from $v$ to
|
|
$w$ are memorized in \texttt{edge\_w} and compared and checked against the weight of $(v, w)$. If we find an edge in the path with
|
|
weight bigger than $(v, w)$ we can then replace that edge with $(v, w)$, so we return \texttt{FLASE}\textit{ (sic)}
|
|
\footnote{\url{https://medium.com/@DanielC7/dbf8773df767}} since we the old MST is not minimal anymore.
|
|
The complexity of this is $O(|V|)$ since the total number of edges in a tree is linearly dependent to the number
|
|
of vertices (i.e.: $|E_T| = |V| - 1$).
|
|
|
|
\subsection{Point 2}
|
|
|
|
\begin{lstlisting}[caption=Solution for exercise 4 point 2, label={lst:ex4p1}]
|
|
FUNCTION MAKE-MST-MINIMAL(T=(V,E), weight, v, w, c):
|
|
P[w] = NIL
|
|
DEFINE-PARENT(T, P, Adj[w], w)
|
|
s = P[s]
|
|
s_max = s
|
|
max = weight($\textit{edge}$ (s, P[s]))
|
|
while s $\neq$ w:
|
|
edge_w = weight($\textit{edge}$ (s, P[s]))
|
|
if edge_w > max:
|
|
max = edge_w
|
|
s_max = s
|
|
s = P[s]
|
|
|
|
if max < c:
|
|
return
|
|
else:
|
|
$\textit{remove edge (max\_s, P[max\_s]) from T}$ // O(|V|) cost operation
|
|
$\textit{add (v, w) to T}$ // constant cost
|
|
\end{lstlisting}
|
|
|
|
For what said before, this algorithm updates $T$ to a valid MST and runs in $O(|V_T|)$ which is always $< O(|E|)$. In order to find
|
|
the new MST, we need to find remove the edge with highest weight in the path from $v$ to $w$ and add $(v, w)$ to the MST.
|
|
|
|
\end{document} |