6.1-2

6.1-2 Show that an n-element heap has height $\lfloor lg n \rfloor$. As we know the minimum and maximum no of elements for tree of height h is $2^h$ and $2^{h+1}-1$ $$ 2^h \leq n \leq 2^{h+1}-1 $$ $$ 2^h \leq n \leq 2^{h+1}-1 \lt 2^{h+1} $$ $$ 2^h \leq n \lt 2^{h+1} $$ applying logarithm for in equality $$ h \leq log n \lt h+1 $$ But h is an integer hence the height of the tree is $\lfloor lg n \rfloor$.

6.1-1

What are the minimum and maximum numbers of elements in a heap of height h?
Since a heap is binary tree the idea is to write in the power of 2. The minimum no of nodes for height h tree is (the tree has to have 1 node to left)$$\{1+2+2^2+....+2^{h-1}\}+1$$ The above series in the flower braces can be written as a geometric series Below is the formula for geometric series(see wikipedia): $$1-r^{n+1}/1-r$$ $$ \{1-2^{h-1+1}/1-2\} + 1 $$ $$ \{1-2^{h}/-1\} + 1 $$ $$ \{2{h}-1 \}+ 1 $$ $$ 2{h}$$ The maximum no of nodes for a height h tree is $$1+2+2^2+....+2^{h}$$ Below is the formula for geometric series(see wikipedia): $$1-r^{n+1}/1-r$$ $$ 1-2^{h+1}/1-2 $$ $$ 1-2^{h+1}/-1 $$ $$ 2^{h+1} -1 $$

Harmonic Series Approximation

$$H(n) = 1+1/2+1/3+...1/n$$ This is Area under the curve $\int_1^n 1/x dx $ is $log n - log 1$ (this is an approximation) $$log n - 0$$ $$log n$$ Refer to youtube http://www.youtube.com/watch?v=H5PcgX6i0wY CLRS also has a proof: see apendix A For a monotonically decreasing function $$\int_m^{n+1} f(x) dx \leq \sum\limits_{k=1}^n f(k) \leq \int_{m-1}^n f(x) dx $$ for the lower bound $$\int_m^{n+1} 1/x dx \leq \sum\limits_{k=1}^n 1/k $$ $$ log(n+1) - log 1 \leq \sum\limits_{k=1}^n 1/k $$ $$ log(n+1) \leq \sum\limits_{k=1}^n 1/k $$ for upper bound $$\sum\limits_{k=2}^n 1/k \leq \int_{1}^n 1/n dx $$ $$\sum\limits_{k=2}^n 1/k \leq log n - log 1 $$ $$\sum\limits_{k=2}^n 1/k \leq log n $$

5.4-5

5.4-5 What is the probability that a k-string over a set of size n forms a k-permutation? How does this question relate to the birthday paradox? k-permuation over set n is $_n\mathrm{P}_k$ we can construct k-length over set n of size by $$n.n.n...n = n^k$$ the probability is $_n\mathrm{P}_k/n^k$ $$n(n-1)(n-2)...1/n^k (n-k)!$$ $$(n-1)(n-2)...(n-k+1)/n^{k-1} $$ The above equation looks similar to the probability of distinct birthdays k people in a room can have. Where k is the no of people and n -s no of days in a year.

5.4-3

5.4-3 For the analysis of the birthday paradox, is it important that the birthdays be mutually independent, or is pairwise independence sufficient? Justify your answer.

From appendix: A collection A1,A,.....An of events is said to be pairwise independent if $$Pr{Ai \cap Aj} = Pr{Ai} .Pr{Aj}$$ for all 1 i < j n.
We say that the events of the collection are (mutually) independent if every k-subset Ai1,Ai2, ... ,Aik of the collection, where 2\leq k \leq n and $1 \leq i1 < i2 < < ik \leq n$, satisfies $$Pr{Ai1 \cap Ai2 \cap.... \cap Aikg } = Pr{Ai1}. Pr{Ai2}...Pr{Aik}.$$ we need pairwise independence if we see the analysis of birthday pardox we compare two people birthdays. $$Pr\{b_i = r and b_j =r\} = Pr\{b_i=r\} Pr\{b_j=r\}$$

5.4-2

5.4-2 Suppose that we toss balls into b bins until some bin contains two balls. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses?
To solve this lets take an example where we have 4 bins:
[] [] [] []
A bin can contain two balls only after two throws. Let $X_i$ be the variable when a bin contains two throws. Let X be a variable that counts no of bins that have two balls. So lets start at 2 throws It doesn't matter if the first throw hits any of the three boxes but the second throw has to hit the same box if a bin has to contain two balls.
Probability for bin to have two balls after two throws is 1 (first throw). 1/4(second throw the probability of hitting the first bin that has ball)
First throw can land in any of the 4 bins:
[B] [] [] []
[] [B] [] []
[] [] [B] []
[] [] [] [B]
the second throw has to land on any of the above 4 bins.
the final probability: 1 .1/4 (since the above events are independent)
for 3 throws:
First throw can land in any of the 4 bins:
[B] [] [] []
[] [B] [] []
[] [] [B] []
[] [] [] [B]
the second throw has to land on any of the above 3 bins other than the one containing the ball.
[B] [B] [] [] Or
[] [B] [B] [] Or
[] [B] [B] [] Or
[] [] [B] [B]
The probability is for second throw is 3/4.
The third throw has to land in any of two bins containing balls hence 1/2 (2 out of 4 bins)
The final probability: 1.3/4.1/2
for four throws:
for second throw the probability is: 3/4
for third throw we have two empty bins the probability is: 1/2
for fourth throw it has to fall in either of three bins containing a ball : 3/4
The final probability: 1.3/4.1/2.3/4
for five throws:(This is the final case since even 4 throws make it to distinct bins the fifth has to make one of the four to make the count to 2)
for second throw the probability is: 3/4
for third throw we have two empty bins the probability is: 1/2
for fourth throw it has to fall final empty bin : 1/4
for fifth throw it can fall in any bin to make the no of balls in a bin to 2 : 1
The final probability: 1.3/4.1/2.1/4 $$E[X] = 2 * 1 .1/4 + 3 * 1.3/4.1/2 + 4 * 1.3/4.1/2.3/4+ 5 * 1.3/4.1/2.1/4.1 $$ The above equation is of the form $$E[X] = \sum_{k=2}^b+1 k (k-1) b.(b-1)...(b-k+1)/b^k $$ The above sum is the no of throws in which we can get two balls in a bin.

5.4-1

5.4-1 How many people must there be in a room before the probability that someone
has the same birthday as you do is at least 1/2? How many people must there be
before the probability that at least two people have a birthday on July 4 is greater than 1/2?

The probability that someone has same birthday as me = 1 -(probability every person in the room has a different birthday as me) (every person can have birthday on other 364 days and it doesn't matter if they have birthday on same hence the 364 ) $$= 1 - (364/365)(364/365)...(364/365)$$ $$ = 1 - (364/365)^n = 1/2$$ $$ 1 - (364/365)^n \geq 1/2 $$ $$ (364/365)^n \leq 1/2 $$ applying logarithm on both sides $$ n lg(364/365) \leq lg(1/2) $$ $$ n lg(364/365) \leq - lg(2) $$ $$ n lg(365/364) \geq lg(2) $$ $$ n \geq lg(364/365) lg(2) $$ $$ n \geq 253 $$ (using a calculator ) For the second part the probability of at least two people have a birthday on July 4 is greater than 1/2 = 1 - probability of exactly one person born on july4 - probability that no one in the room is born on july 4 let probability of exactly one person born on july4 we can use binomial theorem here $$ {n \choose k} p^k (1-p)^{ n-k} $$ Let k be the no of people in the room(n=k) since we want exactly one person born on july 4(k =1). The probability of person born on a day in a year is 1/365(p =1/365) $$ {k \choose 1} (1/365)^k (1-1/365)^{ k-1} $$ $$ {k \choose 1} (1/365)^k (364/365)^{ k-1} $$ $$ {k \choose 1} (1/365)^k (364/365)^{ k-1} $$ probability that no one in the room is born on july 4: $$ (364/365)^k $$(from first part of analysis) probability of at least two people have a birthday on July 4 = $$1 - {k \choose 1} (1/365)^k (364/365)^{ k-1} - (364/365)^k $$ $$1 - {k \choose 1} (1/365)^k (364/365)^{ k-1} - (364/365)^k /geq 1/2 $$ If $k geq 613 $ the above equation is satisfied.