HW11 part II

gistfile1.md

{ "metadata": { "name": "", "signature": "sha256:fb32189c9859a01bc9371cdf5d176b0b5b95394ff9c9490038f0f3226c5ed4b2" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "SUBSET SUM" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Algorithm($S[1 ... m]$, $N$):
\n", "  if $N$ == $0$:
\n", "    return Yes
\n", "\n", "  if $N < 0$ or $S$ is empty:
\n", "    return No
\n", "\n", "  for $i$ from $1$ to $m$:
\n", "    if Algorithm($S[1 ... m] - S[i]$, $N - S[i]$) returns Yes:
\n", "      output $S[i]$
\n", "      return Yes
\n", "\n", "  return No
\n", "\n", "Algorithm($S[1 ... n]$, $B$)" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "HAMILTONIAN PATH" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Algorithm($G$):
\n", "choose any vertex $v \in G.V$ as start
\n", "return Hamilton-Visit($G$, $v$)
\n", "\n", "Hamilton-Visit($G$, $v$):
\n", "  if count($V$.visited) == $|V|$:
\n", "    return Yes
\n", "  for each $u \in Adj[v]$ and $u.visited$ == False:
\n", "    $u$.visited $:=$ True
\n", "    if Hamilton-Visit($G$, $u$) returns Yes:
\n", "      return Yes
\n", "  return No
\n" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "DOMINATING SET" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Algorithm($G$, $K$, $S$):
\n", "  if Check-Dominating($G$, $K$, $S$):
\n", "    return Yes
\n", "  for each $v \in (G.V - S)$:
\n", "    if Algorithm($G$, $K$, $S \cup \{ v \}$) returns Yes:
\n", "      return Yes
\n", "  return No\n", "\n", "Check-Dominating($G$, $K$, $S$):
\n", "  if $|S| > K$:
\n", "    return False
\n", "\n", "  for each $v \in (G.V - S)$:
\n", "    flag $:=$ False
\n", "    for each $s \in S$:
\n", "      if $v \in Adj[s]$:
\n", "        flag $:=$ True
\n", "        break
\n", "    if flag is False:
\n", "      return False
\n", "  return True\n", "\n", "Algorithm($G$, $K$, $\phi$)
" ] } ], "metadata": {} } ] }