Home Work Number 1, Intro to Algorithms, Fall 2014
Due on Thursday September 4
Please submit your answers in a plain paper (write your name and section number)
Do the following problems from the text book (DG - Dasgupta et al, CLRS - Cormen et al's book)
Exercise 0.1 (page 18 from DG or page 8 of DG in 2008 edition)
Exercise 0.3 a and b (page 18 from DG or page 8 of DG in 2008 edition)
Explain whether the following statements are true or false and why
Is 2 n+1 = Big-Oh(2 n )?
Is 2 2n = Big-Oh(2 n )?
Is n log(n) = Big-Oh(2 n )?
What will be the value of sum in the following program as a function of n and what is the running time of the program (using Big-Oh notation)?
sum = 0;
for (i = 1; i <= n; i++)
{
for ( j = 1; j <= i ; j++ )
{
for (k = 1; k <= j; k++)
{
sum++;
}
}
}
Hint: First do the problem with a single loop - then with two loops and then with three loops.
Write a program (pseudo code will suffice) to compute 2 2 n in linear time. Assume
multiplication of arbitrary size integers takes unit time.
Hint: 2 2 n-1 2 2 n-1 = 2 2 n
(because exponents add up)