COMP3600/6466 - Algorithms Semester 2, 2022 Tutorial 3

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Semester 2, 2022

Tutorial 3

COMP3600/6466 - Algorithms

Exercise 1                                       Recurrence Analysis: Recurrence tree

Using a recurrence tree, provide a tight upper bound for the following recurrences:

1. T(n) = 2T() + n2

2. T(n) = 2T(n − 1) + 1


Exercise 2                                       Recurrence Analysis: Master Theorem

Use the Master theorem to find tight asymptotic bounds to prove:

1. T(n) = 10T ( ) + Θ(n) = Θ(n)

2. T(n) = 3T(^n) + log n = Θ(loglog 3 n) by making a change of variables.


Exercise 3                                                       Probability refresher

1. The price of a TV is $1000. Every year it goes up by either $100 or $200 with equal probability. What is the expected final price of the TV after N years?

2. What if the price goes up by 1% or 2% (with equal probability) every year? You can assume the price increase each year is independent of the increase in the other years.

Note:  When X and Y are independent, E(XY) = E(X)E(Y)


3. Given a sequence of N integers, each in the range [1,M], what is the expected number of adjacent pairs of numbers with absolute difference of d?

For Q4–Q5, you assume that the coins used are all fair coins and the result of each coin toss is independent and identically distributed compared to all other tosses.

Hint: You might want to check [CLRS] App. C.4.

4. What is the expected number of coin tosses before you get a heads?

5. What is the expected number of coin tosses before you get two heads?


Exercise 4                                                       Probabilistic Analysis

1. The town AIT (AIT Is a Town) has just finished renovating its one and only museum, called AIT- Museum. To attract tourists, AIT town council created Little Museum collectible program. Each ticket to enter AIT-Museum comes with a free mini replica (made of paper) of one of its permanent displays. Suppose the complete Little Museum consists of mini replica of n different permanent displays. Assuming one can only earn a mini replica by purchasing a ticket to enter AIT-Museum and assuming the probability one receives mini replica of a particular display is equally likely and independent of the other replicas one received, what is the expected number of tickets one needs to purchase to complete the Little Museum?












2022-09-20