HW10

gistfile1.md

{ "metadata": { "name": "", "signature": "sha256:0a73ca15645dd5f416851809ef72de1dc22336999041b334779c06ba497368ff" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "22.3-2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "22.3-3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$(u$ $(v$ $(y$ $(x$ $x)$ $y)$ $v)$ $u)$ $(w$ $(z$ $z)$ $w)$" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "22.4-3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "####Design:\n", "Algorithm($G$):
\n", "  for each vertex $u \in G$.$V$:
\n", "    $u.$color $:=$ WHITE
\n", "    $u$.$\pi := $ NIL
\n", "\n", "  time $:= 0$
\n", "  for each $u \in G$.$V$:
\n", "    if $u.$color == WHITE
\n", "      if MODIFIED-DFS-VISIT($u$) == True:
\n", "        return True
\n", "  return False\n", "\n", "\n", "MODIFIED-DFS-VISIT($u$):
\n", "  time $:=$ time $+ 1$
\n", "  $u$.d $:=$ time
\n", "  $u$.color $:=$ GRAY
\n", "  for each $v \in G$.$Adj[u]$:
\n", "    if $v$.color == WHITE
\n", "      $v$.$\pi := u$
\n", "      if MODIFIED-DFS-VISIT($v$) == True:
\n", "        return True
\n", "    else
\n", "      return True
\n", "\n", "  $u$.color $:=$ BLACK
\n", "  $u$.$f := $ time $:=$ time $+1$
\n", "  return False
\n", "\n", "####Analysis:\n", "1. Our algorithm visits each node in $V$ at most twice when it returns answer.\n", "2. The depth-first tree contains $|V_{\text{DFS}}| - 1$ edges. When our algorithm terminates, it has gone through at most $|V|$ edges.
\n", "Hence, the time complexity is $O(|V|)$." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "22.5-3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If so, the second DFS might cross different SCCs.
\n", "\n", "For example, let $C_1$, $C_2$ be two different SCCs with circular shape, we may assume $C_1$.$V = \{u_1, ... , u_n\}$ and there exists an edge $(u_k, v)$ satisfying $u_k \in C_1$, $v \in C_2$. Assuming that we start the first DFS from $u_{k+2}$ but enter $C_2$ after it visits all nodes in $C_1$.\n", "\n", "Thus, we have two chain-like depth-first trees $T_1$ and $T_2$ which contain all nodes of $C_1$ and $C_2$, respectively. And it does not pass through $(u_k,v)$. Note that the node with smallest finishing time must be $u_{k+1}$, then the second DFS will start from $u_{k+1}$ and turn in $(u_k,v)$ then get exceed $C_1$ after it goes through $u_k$." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "22-2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "####c.\n", "####Design:\n", "Algorithm($G$, $G_\pi$):
\n", "  let $E_r := G$.$E - G_\pi$.$E_\pi$
\n", "  let $G_r := (V, E_r)$
\n", "  let root $:= G_\pi$.$V$
\n", "  root.low $:=$ Visit($G_\pi$, $E_r$, root)
\n", "  if root has at least $2$ children:
\n", "    output root
\n", "\n", "Visit($G_\pi$, $G_r$, $v$):
\n", "  min $:= \infty$
\n", "  for each $u \in G_\pi$.$Adj[v]$ but $u \neq v$.$\pi$:
\n", "    temp $:=$ Visit($u$)
\n", "    if temp $<$ min:
\n", "      min $:=$ temp
\n", "  for each $w \in G_r$.$Adj[v]$:
\n", "    if $w$.$d < $ min:
\n", "      min $:= w$.$d$
\n", "  $v$.low $:= \min${min, $v$.$d$}
\n", "  if $v$.$d \leq v$.low:
\n", "    output $v$
\n", "  return min\n", "\n", "####Analysis:
\n", "1. $G$ is connected. $\implies |V|=O(|E|)$
\n", "2. Our algorithm goes through each node & edge at most twice. $\implies O(|E|)$\n", "\n", "Hence, the time complexity is $O(|E|)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "####d.\n", "As above. Output all nodes $v$ satisfying $v$.$d$ == $v$.low.
\n", "Since $G$ is connected. $\implies$ The complexity is $|V|=O(|E|)$
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "####h.\n", "If node $u$ is contained in a BCC, then $u$.low $\leq u$.$d$ and all other nodes which have the same low value are also contained in this BCC.\n", "\n", "####Design:\n", "Algorithm($G$, $G_\pi$):
\n", "  use c. to evaluate all nodes' low value
\n", "  for each $v \in V$:
\n", "    $v$.bcc := $v$.low
\n", "\n", "####Analysis:\n", "1. The algorithm of c. takes $O(|E|)$ time.
\n", "2. The for-loop takes $O(|V|)$ time.
\n", "Hence, the time complexity is $O(|E|)$." ] } ], "metadata": {} } ] }