Scribd
Upload
4 views1 page

CS21003 Algorithms 1 Tutorial Guide

This tutorial covers various topics in algorithms, including finding fallacies in derivations, arranging functions based on their growth rates, and developing recursive definitions for set operations. It also includes exercises to compute asymptotic complexities of given functions and provides examples of functions that do not fit standard growth rate comparisons. The tutorial is designed for students of CS21003 at IIT Kharagpur.

Uploaded by

rupshali
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
4 views1 page

CS21003 Algorithms 1 Tutorial Guide

This tutorial covers various topics in algorithms, including finding fallacies in derivations, arranging functions based on their growth rates, and developing recursive definitions for set operations. It also includes exercises to compute asymptotic complexities of given functions and provides examples of functions that do not fit standard growth rate comparisons. The tutorial is designed for students of CS21003 at IIT Kharagpur.

Uploaded by

rupshali
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

Tutorial 1: CS21003 Algorithms 1

Prof. Partha Pratim Chakrabarti and Palash Dey


Indian Institute of Technology, Kharagpur
January 20, 2022

1. Find fallacy in the following derivation.


Claim 1. n = O(1)

Proof. We will proof by induction on n. For n = 0, the statement is clearly true. Let us assume
that the statement holds for n = n1 . We will now prove it for n = n1 +1. We have the following.

n1 + 1 = O(n1 + 1) = O(n1 ) = O(1)

The third equality follows from induction hypothesis.

2. Arrange the following functions


√ √n 1 n
√
 
ln n 2 ln n n 1000 1.0001 .999 100000
n, 10, n , ln ln n, (ln n) ,2 , n!, n ln n, n ,n ln n, n , , n
n 2

in a sequence such that if f1 (n) appears in the left of f2 (n), then f1 (n) = O(f2 (n)).
3. Develop recursive definitions to solve the following problems and refine them for final algo-
rithms and data structures.

(a) Given two unordered sets U and V, find their union, intersection and set difference.
(b) Given two ordered sets X and Y of integers, find their union, intersection and set difference.
4. Compute asymptotic complexity of T (n, n) in terms of Θ where


x if y 6 50
T (x, y) = y if x 6 50

 y
x + y + T 2x

,
3 2 otherwise

5. Compute asymptotic complexity of T (n) in terms of Θ where



3T (dn/2e) + n log2 n if n > 50
(a) T (n) =
1 otherwise

T (dn/5e) + 9n if n > 50
(b) T (n) =
1 otherwise

T d n2 e + 7 + b n2 c + 11 if n > 50
 
(c) T (n) =
1 otherwise
 √
T (d ne) + 13 lg n if n > 50
(d) T (n) =
1 otherwise

6. Give an example of two functions f, g : N −→ N \ {0} such that we have neither f = O(g) nor
f = Ω(g).

You might also like