Algo HW11 I

gistfile1.md

{ "metadata": { "name": "", "signature": "sha256:74b6438947f049e10e34b827393cc06ea98a28fd298f7aef5097912ce9be36a5" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "23.1-2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "Consider the above example from the lecture note. If we partition the orginal graph into $\{ a, b, c, d, e, f, h, i \}, \{ g \}$, then it's clear that $(g, f)$ is a safe edge but $(g, h)$ is the only light edge." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "23.2-4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1. We can apply counting sort on sorting edges by weight. Then by analysis in lecture note, total time consumption is almost linear, $O(|E| \alpha(|V|))$.\n", "2. Similarly, $O(W + |E| \alpha(|V|))$." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "23.2-5" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1. We don't need heap structure anymore. Instead, we can use an adjacency list which contains |V| linked-lists for storing adjacent nodes. For instance, the $n$-th linked-list contains all nodes which are adjacent to the MST with edge weight $n$. Then, by analysis in lecutre note, total time consumption is $O(|V|) + O(|E|) = O(|E|)$.\n", "2. Similarly, $O(W) + O(|E|) = O(W + |E|)$." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "23-3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "####a.\n", "Let $T$ be a minimum spanning tree of graph $G$. Assume that $T$ is not a bottleneck spanning tree. Thus, for the largest weight edge of $T$, written $(u, v)$, there exists another spanning tree $T'$ of $G$ which contains no edge with weight $\geq (u,v)$. If $(u, v)$ is removed from $T$, then it consequently cut $T$ into $2$ parts. But since $T'$ is also a spanning tree, we can find another edge $(u', v')$ from $T'$ to connect these $2$ parts and construct a new spanning tree $T''$ with $w(T) > w(T'')$. That implies $T$ is not a minimum spanning tree and leading a contradiction." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "####b.\n", "It's not difficult to see the time complexity is $O(|E|)$.\n", "\n", "CHECK-BST($G$, $b$):
\n", "  for each edge $e \in G.E$:
\n", "    if $w(e) > b$:
\n", "      discard $e$ from $G$
\n", "  if $G$ is connected (by DFS):
\n", "    return True
\n", "  else:
\n", "    return False
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "####c.\n", "####Design:\n", "BOTTLENECK-SPANNING-TREE($G$)
\n", "  $M :=$ largest weight in $G.E$
\n", "  $m :=$ smallest weight in $G.E$
\n", "  $b := \lfloor \frac{M + m}{2} \rfloor$
\n", "  $T := \phi$
\n", "\n", "  while $|G.V| > 1$:
\n", "    if CHECK-BST($G$, $b$):
\n", "      $M := b$
\n", "      $b := \lfloor \frac{M + m}{2} \rfloor$
\n", "    else:
\n", "      $m := b$
\n", "      $b := \lfloor \frac{M + m}{2} \rfloor$
\n", "\n", "    $G, T := $MST-REDUCE($G$,$T$)
\n", "\n", "  if CHECK-BST($G$, $b$):
\n", "    return $b$ and $T$
\n", "  else:
\n", "    return $(b+1)$ and $T$
\n", "\n", "####Analysis:\n", "1. Expect the while-loop, all operations takes $O(|E|)$ time.\n", "2. Since at least a half nodes merges into others in each iteration of the while-loop, it makes $|E|$ shrink at least a half also (it seems true for connected graph, but I have no idea to explain). Therefore, the while-loop consumes $O(|E|) + O(|E| / 2) + O(|E| / 8) + ... \leq O(2 |E|) = O(|E|)$ time.\n", "\n", "Hence, the time complexity is $O(|E|)$." ] } ], "metadata": {} } ] }