4ezk3C1M

1\documentclass{hw121}              % make sure that hw121.cls is in the same directory
2\usepackage{amsmath}
3\usepackage{amssymb}
4\usepackage{amsthm}
5\usepackage{commath}
6\usepackage{listings}
7\usepackage{mathtools}
8
9\usepackage{hyperref}
10
11\hwauthor{Marcos Carballal}{mcarball@seas.upenn.edu}
12\hwcourse{CIS 320}
13\hwrecitation{001}
14\hwno{3}
15\hwpartner{}
16\hwpartner{}
17% \date{}  % uncomment this line to suppress the current date in the title
18% \date{Due: Never}  % or uncomment this line to manually add a date
19% \hwonelateday                   % uncomment either this line or the next to
20% \hwtwolatedays                  % indicate that you are using an extension
21
22\begin{document}
23\maketitle
24\hwproblem
25WTS: Any randomly chosen hash function h from H will have the property that Pr(h(x)=h(y)) $\leq \frac{1}{n}$	for all x $\neq$ y in our universe.\\
26Proof: Let us arbitrarily pick distinct and fixed x and y and determine the probability that h(x)=h(y). Since they are distinct, there must exist an index i s.t. x[i] $\neq$ y[i]. Without loss of generality let x[i] = 1 and y[i] = 0. Because of how matrix multiplication works, the following is true for all the rows in the resulting column vectors. Let the result of our hash from key x be the column vector $C_x$[1..n]. For the first column, $C_x$[1] = A[1][1]*x[1]+ ... + A[1][i]*x[i] + ... +A[1][n]*x[n]. Likewise, $C_y$[1] = A[1][1]*y[1]+ ... + A[1][i]*y[i] + ... +A[1][n]*y[n]. We know that A[1][i]*x[i] = 0 because x[i] = 0 but the result of A[1][i]*y[i] = A[1][i] because y[i] =1. Because we are dealing in boolean algebra and A is randomly generated, we know that for every entry in the column vector, the probability that $C_y[row] = C_x[row]$ is $\frac{1}{2}$  and the probability that $C_y[row] \neq C_x[row]$ is $\frac{1}{2}$ for all rows. Therefore, Pr[$C_y$=$C_x]\leq$($\frac{1}{2^b})$ where b is the number of rows in the resulting column vector. Conveniently, $2^b$ is also the size of our hashtable so we can substitute it in n = $2^b$ to yield Pr[$C_y$=$C_x]\leq$($\frac{1}{n})$
27\hwproblem
28\hwsubproblem
29$B_1:1,B_2:0,B_3:1,B_4:0,B_5:2,B_6:0,B_7:5$
30\hwsubproblem
31For two non-empty binary trees to be distinct one of the following must be true: Their left sub-trees are distinct from each other, their right sub-trees are distinct from each other, or both their right and left sub-trees are distinct from the others right and left sub-trees. For any given tree with n nodes (including root), we can allocate - without loss of generality - k nodes to the left sub tree and n-1-k nodes to the right sub-tree. We can recursively find the amount of distinct left sub-trees and distinct right sub-trees for a given k and take their product to represent the number of combinations given we choose to allocate k nodes to the left sub-tree. If we vary k from 1 to n then we can account for all possible configurations of the new tree. For example $B_3$ is given by $B_0B_2 + B_1B_1+B_0B_2$ = 1  Therefore, the recurrence relation for $B_n$ is given by
32\begin{equation}
33  B_n=\begin{cases}
34    \sum\limits_{k=1}^{n-1} B_{n-k-1}B_k, & \text{if n = 2k+1 for some } k$\in \mathbb{N}$.\\
35    0, & if n = 2k \text{ for some } k$\in \mathbb{N}$. \\
36    1, & if n = 1
37  \end{cases}
38\end{equation}
39\hwsubproblem
40For this sub-problem we don't have to worry about even values so this alters our recurrence relation to be
41\begin{equation}
42  B_{2k+1}=\begin{cases}
43    1, & if k = 0 \\
44    \sum\limits_{i=0}^{k} B_{2k-2i+1}B_{2i+1}, & otherwise
45  \end{cases}
46\end{equation}
47As a consequence of the above recurrence,\\
48$B_{2k+1}$ = $B_{2k-1}B_1 + B_{2k-3}B_3 + ... + B_3B_{2k-3} + B_1B_{2k-1}$. $B_1$ is just 1, so we can make the inequality $B_{2k+1}\geq 2B_{2k-1}$.\\
49I.H: $B_k\geq 2^{k-1} \forall k\in\mathbb{N}$ (Strong induction)\\
50B.C $W.T.S: B_1 \geq 2^{0}$. Trivially true.\\
51I.S:$B_{2(k+1)-1} = B_{2k+1} = B_{2k-1}B_1 + B_{2k-3}B_3 + .. + B_3B_{2k-3} + B_1B_{2k-1}$\\
52We know from our above inequality that $B_{2k+1}\geq 2B_{2k-1}$. Invoking our induction hypothesis gives us\\
53$B_{2k+1}\geq 2*2^{(2k+1) - 1)}$\\
54$B_{2k+1}\geq 2^{2k+1} \geq 2^{2k}$. Induction Hypothesis holds.\\
55Taking the log of both sides yields\\
56$log(B_{2k+1}) \geq 2k$. \\
57Therefore, $log(B_{2k+1}) \in \Omega(k)$ 
58\hwproblem
59\hwsubproblem
60Clearly, looking at all subsets of size m from the initial set of n and multiplying all of the probabilities of successes and failures for every subset would be algorithmically inefficient because $\binom{n}{m}\in O(n^m)$ . Therefore, we will approach the problem using recursion. The main idea behind the recurrence is that to get i heads  after the last flip we must either already have i heads and get a tails on the last flip or we must have i-1 heads and get a heads on the last flip.\\
61
62\begin{equation}
63  P(i,j)=\begin{cases}
64    0, & i > j  \\
65     \prod\limits_{i=0}^n (1 - p_i) & i = 0 \\
66     P(i,j-1)(1-p_j) + P(i-1,j-1)(p_j) & otherwise
67  \end{cases}
68\end{equation}
69\hwsubproblem
70\textbf{Pseudo-Code:}\\
71P(i,j):\\
72If $i>j$, return 0.\\
73If k = 0, return $\prod\limits_{i=0}^n (1 - p_i$) \\
74Else, return $P(i,j-1)(1-p_j) + P(i-1,j-1)(p_j) $\\
75\hwproblem
76\textbf{Algorithm:} We will start our algorithm by initializing an array T[1..n] with all values initialized to false. T[i] will become true if and only if s[1...i] is a valid sequence of words. It will remain false otherwise. We want to find T[n]. We want to start with the smallest value so that we can later rely on our true/false table to determine larger values. With this in mind, we can generate the following recurrence:\\
77\begin{equation}
78  T[i]=\begin{cases}
79    false & \text{if } i  \leq  0\\
80    OR_{1\leq j \leq i} (T[j]\land DICT(s[j+1..i])) & otherwise  
81  \end{cases}
82\end{equation}
83where OR simple takes logical or operation of all the boolean values given  by $(T[j]\land DICT(s[j+1..i])) $ at all values of j between 1 and i. To solve this recurrence we have to solve it in the order of T[1],T[2],...,T[n].\\ \\ \\ \\ 
84SENTENCE(s):\\
85Initialize all values in T[1..n] to false and T[0] = true\\
86for i = 1 ... n\\
87\text{\hspace{10mm}} T[i] = false \\
88\text{\hspace{10mm}} for j =0 ... i -1 \\
89\text{\hspace{20mm}} if $(T[j] \land DICT(s[j+1..i])$\\ 
90\text{\hspace{30mm}} T[i] = true \\
91\text{return T[n]}\\
92\textbf{Proof Of Correctness:} The lemma under which the algorithm operates, that is, s[1...i] is a valid sequence of words if there exists a j between 1 and i s.t. s[1..j] is a valid sequence of words and s[j..i] is a word. We can prove this through induction. Let s be a valid string of k words.\\
93I.H: SENTENCE(s) will always return true on this input of k words. \\
94B.C: k=1.\\
95Let the length of this word be n. The algorithm may find sub-strings which are also words (Ex: "and" where "a" and "an" are sub-strings that are also words) but regardless of what the values the array takes on our statement of  $T[0]\land DICT(s[1...n])$ will be true and therefore T[n] will be set to true.\\
96I.S. Let s be a word  w comprised of k+1 words. Let us represent s as u$\cdot$ v where u is the string of the first k words and v is the last word. By induction hypothesis, after we have done $|u|$ loops we will have T[$|u|$ ] = true. The algorithm will then have to loop $|v|-1$ more times without finding any words until the final iteration where we make the comparison T[$|u|$ ]$\land DICT(s[|u|+1..|u|+|v|])   $ . Since $s[|u|+1..|u|+|v|]$ is a word, as per our definition, this statement will be evaluated to true and therefore $T[|u|+|v|] = true$ Since s = u$\cdot$v, this means $T[|s|] = true$ and the algorithm will return true.\\
97\textbf{Run-time Analysis:}  We can see that i varies from 1 to n and j varies from 0 to i-1 with only O(1) operations occurring under the j for loop. Therefore, complexity is given by $\sum\limits_{i=1}^{n} \sum\limits_{j=0}^{i-1}$O(1). Inner loop is O(n) as it will run the comparisons up to n times. Outer loop is trivially O(n). Therefore, the whole algorithm is $O(n^2)$
98\hwproblem
99The main idea behind the recursion is that we have a choice of j-i options of where to draw our diagonal to create two sub-problems of triangulation whose cost is given to us because it is recursively defined.
100\hwsubproblem
101\begin{equation}
102  C(i,j)=\begin{cases}
103  0 & i=j \\
104   min_{i\leq k \leq j}\{C(i,j) + C(k,j) + dist(i,k) + dist(k,j)\} & otherwise
105  \end{cases}
106\end{equation}
107\hwsubproblem
108Min-Triangulation($p_1,p_2,..,p_n)$:\\
109Initialize 2 dimensional n x n array A.\\
110for i =1 .. n\\
111\text{\hspace{10mm}} A[i][i]=0\\
112for s=1..n-1\\
113\text{\hspace{10mm}} for =1..n-s\\
114\text{\hspace{20mm}} j = i + s\\
115\text{\hspace{20mm}} A[i,j] = $min_{i\leq k \leq j}\{A[i,k] + A[k,j] + dist(i,k) + dist(k,j)$\}\\
116return A[1..n]\\
117Using an upper bound of n on j-i, we can see that the program actually has 3 loops (the min clause would execute as a loop) and since each loop is O(n) this yields the running time of $O(n^3)$
118
119\hwproblem
120\textbf{Algorithm:}\\
121Our algorithm, IsSubsequence(A,B) will do the following on input A = $(a_1,a_2,...a_m)$ and B = $(b_1,b_2,...b_n)$\\
122Initialize i = 1. Let us use a for loop with j being initialized to 1, running the loop while $j < n$ and increment j by one each loop. In each iteration of the loop check if $a_i = b_j$. If so, increment i by one and check if $i > m$. If it is, we have found a match for all of the elements in the shorter sequence and we return true.\\
123\textbf{Proof Of Correctness:} We can see that i is only incremented in the case that $a_i$ = $b_j$ but j is incremented over every loop. That makes it impossible for $a_{i+1}$ to be compared to any $b_k$ where $a_i = b_j$ and $b_k \leq b_j$. This maintains the direction of the sequence. In order to exit the loop and return true, we must have found a match in sequence for every element in A and have successfully determined that A is a sub-sequence of B. Otherwise, if we reach the end of B and have yet to find a match for one or more elements in A, we know that A can not be a sub-sequence of B and return false.\\
124\textbf{Run-time Analysis:}
125It is fairly trivial to see that the loop runs at most n-1 times. We only do two O(1) comparisons within the loop. Therefore, the algorithm is O(n) run-time.
126\end{document}