Scribd
Upload
59 views

ICS 211, Design & Analysis of Algorithms, Assignment 1

This document contains 14 questions regarding algorithms analysis and design. It provides recurrences and functions to analyze asymptotic runtime complexity using techniques like recursion trees, the master method, and Big O notation. Students are asked to determine asymptotic bounds, arrange functions by growth rate, solve recurrences, and analyze algorithms for problems like finding local minimums in binary trees.

Uploaded by

Pratik Raj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
59 views

ICS 211, Design & Analysis of Algorithms, Assignment 1

This document contains 14 questions regarding algorithms analysis and design. It provides recurrences and functions to analyze asymptotic runtime complexity using techniques like recursion trees, the master method, and Big O notation. Students are asked to determine asymptotic bounds, arrange functions by growth rate, solve recurrences, and analyze algorithms for problems like finding local minimums in binary trees.

Uploaded by

Pratik Raj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

ICS 211, Design & Analysis of Algorithms, Assignment 1

Sem III (Odd 2021)

Deadline: Submit on or before November 25, 2021

Question 1.

Suppose you have algorithms with the five running times listed below. (Assume these are the exact running
times.) How much slower do each of these algorithms get when you (a) double the input size, or (b) increase
the input size by one?

1. n2
2. n3
3. 100n2
4. n log n
5. 2n

Question 2.

Take the following list of functions and arrange them in ascending order of growth rate. That is, if function
g(n) immediately follows function f (n) in your list, then it should be the case that f (n) is O(g(n)).

1. f1 (n) = n2.5
√
2. f2 (n) = 2n
3. f3 (n) = n + 10
4. f4 (n) = 10n
5. f5 (n) = 100n
6. f6 (n) = n2 log n

Question 3.

Is 2n+1 = O(2n )? Is 22n = O(2n )?

Question 4.

Show that if f (n) and g(n) are monotonically increasing functions, then so are the functions f (n) + g(n) and
f (g(n)), and if f (n) and g(n) are in addition non-negative, then f (n).g(n) is monotonically increasing.

Question 5.

Let f (n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures.

1
ICS 211, Design & Analysis of Algorithms, Sem III (Odd 2021) Assignment 1

1. f (n) = O(g(n)) implies g(n) = O(f (n)).


2. f (n) = O(g(n)) implies 2f (n) = O(2g(n) ).
3. f (n) = O((f (n))2 ).
4. f (n) = O(g(n)) implies g(n) = Ω(f (n)).
5. f (n) = Θ(f ( n2 ))

Question 6.

Show that the solution of T (n) = T (n − 1) + n is O(n2 ).

Question 7.

Show that the solution of T (n) = T (d n2 e) + 1 is O(log n).

Question 8.

Show that the solution of T (n) = 2T (b n2 c + 17) + n is O(n log n).

Question 9.

Using the master method, you can show that the solution to the recurrence T (n) = 4T ( n2 )+n is T (n) = Θ(n2 ).
Show that a substitution proof with the assumption T (n) ≤ cn2 fails. Then show how to subtract off a lower-
order term to make a substitution proof work.

Question 10.

Use a recursion tree to give an asymptotically tight solution to the recurrence T (n) = T (n − a) + T (a) + cn,
where a ≥ 1 and c > 0 are constants.

Question 11.

Use the master method to show that the solution to the binary-search recurrence T (n) = T ( n2 ) + Θ(1) is
T (n) = Θ(log n).

Question 12.

Give asymptotic upper and lower bounds for T (n) in each of the following recurrences. Assume that T (n)
is constant for n ≤ 2. Make your bounds as tight as possible, and justify your answers.

1. T (n) = 2T ( n2 ) + n4 .
2. T (n) = T ( 7n
10 ) + n.

3. T (n) = 16T ( n4 ) + n2 .
4. T (n) = 7T ( n2 ) + n2 .
5. T (n) = 7T ( n3 ) + n2 .

2
ICS 211, Design & Analysis of Algorithms, Sem III (Odd 2021) Assignment 1

Question 13.

Consider an n-node complete binary tree T , where n = 2d − 1 for some d. Each node v of T is labeled with
a real number xv . You may assume that the real numbers labeling the nodes are all distinct. A node v of T
is a local minimum if the label xv is less than the label xw for all nodes w that are joined to v by an edge.
You are given such a complete binary tree T , but the labeling is only specified in the following implicit way:
for each node v, you can determine the value xv by probing the node v. Show how to find a local minimum
of T using only O(log n) probes to the nodes of T .

Question 14.

Solve the following recurrences with Master Theorem. Indicate reason if the Master Theorem is not appli-
cable.

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

4. T (n) = 2n T ( n2 ) + nn .
5. T (n) = 16T ( n4 ) + n.
6. T (n) = 2T ( n2 ) + nlogn.
7. T (n) = 16T ( n4 ) + n!.

8. T (n) = 6T ( n3 ) + n2 logn.
9. T (n) = T ( n2 ) + n(2 − cosn).
10. T (n) = 7T ( n3 ) + n2 .

...

Sources:

1. Cormen, Thomas H, and Thomas H. Cormen. Introduction to Algorithms. Cambridge,


Mass: MIT Press, 2001.

2. Kleinberg, J., Tardos, E. (2006). Algorithm Design. Addison-Wesley.

You might also like