% Note: This file is intended to serve as a template that can be used
% as a starter file for preparing your (student) solutions to
% CSE 373 Assignment 3 in Winter 2016.
% We are leaving in the Latex source text for the questions so that you
% can rework it to express your answers. However, you do not need to
% include the questions themselves in the solutions you turn in.
% We assume that if you choose to use Latex for preparing your solutions,
% that you either have prior experience with it, or you are pretty good
% at picking up how to use software tools like Latex using online
% resources. We will be happy to try to answer some questions if you
% get stuck on Latex. However, this is not the main purpose of
% Assignment 3, and if you are not comfortable working with Latex,
% then it would probably be better for you to use another tool or
% to simply handwrite your answers clearly on paper and turn in
% a PDF based on clear photos and/or scans of those pages.
\def\Line{\hbox to \hsize}
\def\handout#1{
\Line{University of Washington\hfil}
\Line{Department of Computer Science and Engineering\hfil}
\Line{CSE 373, Winter 2016\hfil}
\vskip45pt
\centerline{\vbox{\hbox{#1}\vskip2pt\hrule}}}
\def\problem[#1]#2{\goodbreak\bigskip\noindent{\bf Problem #1 (#2 points):}\par\smallskip}
\def\extra#1{\goodbreak\bigskip\noindent{\bf Extra Credit #1:}\par\smallskip}
\def\solution{\goodbreak\medskip\noindent{\bf Solution:}\par\smallskip}
\def\note{\goodbreak\smallskip\noindent{\bf Note:}\par\smallskip}
\def\margin#1{\hbox to 0pt{\hss #1\quad}}
\def\endpage{\vfill\eject}
\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{mathtools}
\usepackage{enumitem}
\usepackage{hyperref}
\hypersetup{colorlinks=true, urlcolor=magenta}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\parindent=0pt
\pagestyle{empty}
\begin{document}
\bigskip
\handout{My Answers for Assignment 3, by Jonny James, with student number 1700001 (put your name and student number here)}
\bigskip
\bigskip
\raggedright
For each of the problems below, show your work, unless otherwise specified.\linebreak
\\
{\bf For the inductive proofs, please format into the following four parts, or points may be deducted: Basis, Induction Hypothesis, Induction Step, Conclusion.}\linebreak
\problem[1]{15}
In a tree, a {\it sibling} is any node that shares its parent with another node. Prove by induction that the number of leaves $L$ in a binary tree $T$ and the number of siblings $S$ in the tree obey the following relationship, provided there is at least one node in the tree:
$$L = (S + 2)/2$$
\begin{enumerate}[label=(\alph*)]
\item {\bf Basis} (3 points). Show that the relationship holds in the case of a one-node tree.
\item {\bf Induction Hypothesis} (3 points). We will do induction over the number of nodes in the tree. What is the induction hypothesis?
\item {\bf Induction Step} (6 points). Show that if the relationship is true for any tree with $n$ nodes, then it is also true for any tree with $n+1$ nodes. There are two cases, depending on whether the new node is a sibling or not.
\item {\bf Conclusion} (3 points). What is the conclusion?
\end{enumerate}
\newpage
\problem[2]{15}
Let \(S\) be a finite set. We define the \textit{power set} of \(S\), denoted \(\mathcal{P}(S)\), to be the set of all subsets of \(S\). For example, \(\mathcal{P}(\{a,b\}) = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}\). Also, the number of elements in \(S\), called the {\it cardinality} of \(S\), is often denoted \(|S|\). For example, here if \(S = \{a,b\}\), then \(|S| = 2\), and \(|\mathcal{P}(S)|=4\).
\begin{enumerate}[label=(\alph*)]
\item What is \(\mathcal{P}(\{1,2,3\})\)?
\item Prove that \(|\mathcal{P}(S)| = 2^{|S|}\), for a finite set \(S\), as follows:
\begin{enumerate}[label=(\roman*)]
\item Let \(n = |S|\). How many subsets of size k (where \(0 \leq k \leq n\)) are there? (Remember that sets are unordered.)
\item The total number of subsets of \(S\) is the sum of the number of subsets of size \(k\) for each \(0 \leq k \leq n\). Prove that the closed form expression of this sum is \(2^{n}\). (\textit{Hint:} use the Binomial Theorem: \((x + y)^{n} = \sum_{k=0}^{n} \binom{n}{k}x^{k}y^{n-k}\), and consider the case when \(x = y = 1\).)
\end{enumerate}
\item Here, give an alternative combinatorial derivation of (b) along the following lines: since \(S\) is finite, number its elements, say \(S = \{s_{1},\dots,s_{n}\}\) (\(n = |S|\)). Let \(T \subseteq S\) be any subset and associate to each \(s_{i}\) a binary value: 1 if \(s_{i} \in T\) and \(0\) otherwise. Using this scheme, how can you represent subsets of \(S\)? From this, how can you deduce (b)?
\end{enumerate}
\problem[3]{8}
Use induction to prove that $n! \leq n^n$, for all $n \geq 1$. Remember to show the four parts of an induction proof.
\newpage
\problem[4]{10}
You've asked a colleague to write a fast search method to determine whether a string
occurs in a given set of strings. You've told the colleague that the set could be large,
and that the method should run efficiently. He's come up with a technique he calls
Septenary Search. His method assumes that the input consists of a list L of strings
(in sorted order) and a given string s. His method works by calling a HELPER function which is recursive.\linebreak
The pseudocode for Septenary Search and HELPER is given below.
\begin{verbatim}
septenarySearch(L, s):
HELPER(L, 0, L.length-1, s)
HELPER(L, Lo, Hi, s):
if Hi - Lo > 7:
basic_group_size = floor((Hi - Lo) / 7)
number_of_larger_groups = (Hi - Lo) % 7
for i in 0 .. 7:
group_size = basic_group_size
if i < number_of_larger_groups:
group_size = group_size + 1
first_element_of_group = i*group_size
last_element_of_group = (i+1)*group_size - 1
if L[first_element_of_group] <= s <= L[last_element_of_group]:
return HELPER(L, first_element_of_group, last_element_of_group, s)
else:
for string in L:
if s == string:
return true
return false
\end{verbatim}
Prove that the worst case running time of Septenary Search is in $\Theta(\log n)$ by
writing a recurrence equation for its running time and solving it. Hint: Note that the number
of elements considered in the recursive call to HELPER is at least 1/7 of those in the range (between
Lo and Hi) passed in, and the number is no more than 1/4 of them.
\problem[5]{10}
For each of the three groups of functions below, arrange the functions from slowest growth rate to fastest growth rate, using asymptotic analysis.
If any of the functions grow at the same rate, be sure to indicate this. For example, if both $f(n) \in \Theta(n^{13})$ and
$g(n) \in \Theta(n^{13})$, then they grow at the same rate.
\linebreak
a)\linebreak
\hspace*{5mm}(i) $100n^3$\linebreak
\hspace*{5mm}(ii) $n^3 + n$\linebreak
\hspace*{5mm}(iii) $n(\log{n})^{1000}$\linebreak
\hspace*{5mm}(iv) $\frac{(n+5)!}{(n+4)!}$\linebreak
b)\linebreak
\hspace*{5mm}(i) $\ceil{\log{n}}$\linebreak
\hspace*{5mm}(ii) $\frac{5}{n}$\linebreak
\hspace*{5mm}(iii) $n\log{(n^2)}$\linebreak
c)\linebreak
\hspace*{5mm}(i) $n^{1.5}$ \linebreak
\hspace*{5mm}(ii) $2^{n\log{n}}$\linebreak
\hspace*{5mm}(iii) $2^{(\log{n})^{.9}}$\linebreak
\textit{Hint}: In some cases taking the log of each of a pair of functions may help to compare them.\linebreak
\problem[6]{10}
Recall that a geometric series can be represented by the general form:
$$ \sum\limits_{i=0}^{n-1} ar^{i} = a + ar + ar^2 + ar^3 + \ldots + ar^{n-1} $$
where $a$ is a real constant and $r$ is the common ratio. \linebreak
The sum of a finite geometric series is given by:
$$ \sum\limits_{i=0}^{n-1} ar^{i} = a(\frac{1-r^n}{1-r})$$
If the series is infinite and $\left| r\right| < 1$, then the geometric series converges to $\frac{a}{1-r}$.\linebreak
If the series is infinite and $\left| r\right| \geq 1$, then the geometric series diverges. \linebreak
Determine the sum of the following geometric series. If it is infinite and converges, specify the value it converges to. If it converges for only some values of the parameter $k$, specify the domain for which it converges. (Simplify as much as possible, and round decimals to two places or leave in fractional form.) You may use a graphing calculator or \href{http://www.wolframalpha.com/}{WolframAlpha}\footnote{http://www.wolframalpha.com/} for this problem.
a) $\sum\limits_{i=0}^{\infty} 7(-\frac{2}{15})^{i}$ \linebreak
b) $\sum\limits_{i=0}^{\infty} (\frac{10k^2}{2^{k-5}})^{i}$ \linebreak
c) $\sum\limits_{i=0}^{9} \frac{1}{20}(\frac{3}{2})^{i}$ \linebreak
\problem[7]{12}
\begin{enumerate}[label=(\alph*)]
\item Write $2.5757\overline{57}$ as a fraction in lowest terms. (For example $0.7575\overline{75} = \frac{75}{99}$ and in lowest terms is $\frac{25}{33}$.)
\item Compute the value of the expression:
$$9.9^2 - \floor{9.9} \cdot \ceil{9.9}$$
\item List all permutations of the sequence [a, b, c].
\item List all combinations of elements of the set $\{a, b, c\}$ taken 2 at a time. (There should only be 3 of them.)
\item How many different combinations are there of 3 elements at a time, taken from the set $\{V, W, X, Y, Z\}$?
\item List all substrings of {\tt abcde}. You should have 16 of them.
\item List all subsequences of {\tt abcd}. You should also have 16 of these.
\end{enumerate}
\problem[8]{10}
Let the running time for the following four snippets of code be given by $f_1(n)$, $f_2(n)$, $f_3(n)$, and $f_4(n)$. \linebreak
For each one, either find a corresponding function $g_1(n)$, $g_2(n)$, $g_3(n)$, or $g_4(n)$, such that $f(n)$ is $\Theta(g(n))$ and $g$ is a ``simple'' function, or show that no such function exists. ``Simple'' means it should have no unneeded constants or low-order terms. (E.g., $n^5\log{n}$ and $x^{17}$ are simple, but $3n^3$ and $x^2 + x$ are not.)
\begin{enumerate}[label=(\alph*)]
\item
\begin{verbatim}
sum = 0
len = n
while len > 0:
for i in range(0, len):
sum += 1
len = floor(len / 2)
\end{verbatim}
\item
\begin{verbatim}
sum = 0
for i in range(0, n):
for j in range(0, i * n):
sum += 1
\end{verbatim}
\item
\begin{verbatim}
sum = 0
for i in range(0, n):
for j in range(0, i):
sum += 1
for k in range(0, 20000):
sum += 1
\end{verbatim}
\item
\begin{verbatim}
sum = 0
for i in range(0, n):
for j in range(0, i**2):
for k in range(0, 10):
sum += 1
\end{verbatim}
\problem[9]{10}
For $h = 0, 1, 2, 3$, and 4,
draw an AVL tree having height $h$ that has as few nodes as possible,
and such that whenever two siblings are roots of trees with unequal heights, it is
the left subtree that has greater height. (5 points).
Write down the numbers of nodes $F(h)$ in your trees as a function of $h$ for the
five trees you have drawn. (3 points).
Give a recurrence equation for $F(h)$ that will let you determine these numbers for
trees of greater height without having to first draw the trees and then count their nodes.
(2 points)
\problem[EC]{10}
\textit{Extra Credit} A graph is a set of vertices/nodes \(V\) and a set of pairs of vertices \(E\) called edges. For our purposes, we assume \begin{enumerate}
\item[(i)] there are no self-loops (edges that go from one node to itself)
\item[(ii)] the edges are undirected (the edges are unordered pairs of vertices)
\item[(iii)] there are no duplicate edges (between any two vertices, there is at most 1 edge connecting them)
\end{enumerate}
Graphs are very useful because they can model many structures such as social networks (people are vertices, and 'friend' relationships are edges) and communication networks (routers and gateways are vertices, and connections are edges). In this problem, you will look at a special type of graph. We call a graph \(G = (V,E)\) \textit{fully connected} if for every pair of vertices, there exists an edge between them.
\begin{enumerate}
\item What does a fully connected graph with 1 vertex look like? 3 vertices? 5 vertices? How many edges are present in each of these graphs? (please draw and write the number next to the corresponding graph)
\item Show that in a fully connected graph, we have
\begin{align*}
|E| = \frac{n(n - 1)}{2}
\end{align*}
(\textit{Hint:} Try using induction. You've proven the base case where \(n = 1\) in (a). What happens when you add another vertex to an already fully connected graph? How many edges will you then need to add to this new graph to make it fully connected again?)
\item Find a purely combinatorial way to prove (b).
\end{enumerate}
\end{enumerate}
\eject
\end{document}