The Australian National University Research School of Computer Science
COMP3600/6466 – Algorithms
This tutorial is compiled by:
Cormac Kikkert, William Cashman, and Hanna Kurniawati
Exercise 1 Recurrence Analysis: Substitution
Use the substitution method to prove the following: 1. T(n)=T(⌈n⌉)+1=O(logn)
2
2. T(n)=2T(⌊n⌋+17)+n=O(nlogn) 2
Semester 2, 2020 Tutorial 3
Exercise 2
Recurrence Analysis: Recurrence tree
Using a recurrence tree, provide a tight upper bound for the following recurrences: 1. T(n)=2T(n)+n2
2
2. T(n) = 2T(n−1)+1
Exercise 3 Recurrence Analysis: Master Theorem
Use the Master theorem to find tight asymptotic bounds to prove: 1. T(n)=10T n +Θ(n)=Θ(n)
100
2. T (n) = 3T (√n) + log n = Θ(loglog 3 n) by making a change of variables.
Exercise 4 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.
4. What is the expected number of coin tosses before you get a head?
5. What is the expected number of coin tosses before you get two heads?
Exercise 5 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?