Post your solutions to the Feb 6 In-Class Exercise to this thread. Chris

-- Feb 6 In-Class Exercise Thread

''How many distinct strings of head and tails of length @BT@\ceil{\log n}@BT@ are there?'' @BT@@BT@ '''Solution:''' With 2 options for each position, there are @BT@2^{\ceil{\log n}} \approx n@BT@ possibilities. ---- ''Upper bound the number of coin tosses you would need to make to expect to see them all.'' @BT@@BT@ '''Solution:''' Considering this as a coupon collector problem, an upper bound given @BT@n@BT@ possibilities, the expected number of tosses necessary to "hit" all the @BT@n@BT@ possibilities would be would be @BT@O(n(\ln n + O(1))@BT@. ---- General solution without approximation @BT@2^\ceil{\log n} \approx n@BT@, * Distinct strings of heads and tails: @BT@2^\ceil{\log n}@BT@ possibilities * Upper Bound: @BT@O(2^\ceil{\log n}(\ln (2^\ceil{\log n}) + O(1))@BT@

-- Feb 6 In-Class Exercise Thread

1) 2 ^ (ceiling of logn) 2) upper boundry is O( 2^(ceiling of logn) * (ln(2^(ceiling of logn)) + O(1))) per Coupon collector problem where b = 2^(ceiling of logn)

-- Feb 6 In-Class Exercise Thread

- How many distinct strings of head and tails of length upper(log n) are there? For a string of length log n there are 2^(logn) number of distinct strings. - Upper bound the number of coin tosses you would need to make to expect to see them all. O(n (ln (n) + O(1)))

-- Feb 6 In-Class Exercise Thread

2^[logn] distinct string

-- Feb 6 In-Class Exercise Thread

 How many distinct strings of head and tails of length ⌈logn⌉ are there?

 There are 2^log(n) distinct strings of length log(n).

 Upper bound the number of coin tosses you would need to make to expect to see them all.

 The upper bound is b(ln(b)+O(1)) where b = 2^log(n) from the coupon collector bound.

How many distinct strings of head and tails of length ⌈logn⌉ are there? There are 2^log(n) distinct strings of length log(n). Upper bound the number of coin tosses you would need to make to expect to see them all. The upper bound is b(ln(b)+O(1)) where b = 2^log(n) from the coupon collector bound.

-- Feb 6 In-Class Exercise Thread

How many distinct strings of head and tails of length ⌈logn⌉ are there? 2^(logn)

-- Feb 6 In-Class Exercise Thread

How many distinct strings of head and tails of length are there? 2^(logn) Upper bound the number of coin tosses you would need to make to expect to see them all. O(n (ln (n) + O(1)))

-- Feb 6 In-Class Exercise Thread

Number of distinct strings: 2^(ceil(logn)) Upper bound on coin tosses to see all distinct strings: Use the coupon collector problem and view each distinct string as a bin to get 2^(ceil(logn))(ln(2^(ceil(logn)) + O(1))

-- Feb 6 In-Class Exercise Thread

'''How many distinct strings of head and tails of length ⌈logn⌉ are there?''' Each coin toss has 2 results and is mutually independent, so there are 2^⌈logn⌉ possibilities. ---- '''Upper bound the number of coin tosses you would need to make to expect to see them all?''' Using the coupon collector's problem, the upper bound on tosses would be b(ln(b)+O(1)) where b = 2^⌈logn⌉