Department of Computer Science and Engineering, IIT Kanpur

CS210: Data Structures

Dr. R. K. Ghosh

Home | Notice Board | Instructor | TAs | Students | Assignments | Schedule | Lectures | Resources
Assignment 5
Deadline for submission: Tuesday, 03 Sep., 2002, Midnight.

This assignment contains two parts. Part I is yours basic assignment while Part II is a bonus, and for more enthusiastic students.

PART I

Q1. Give an example of a positive function f(n) such that f(n) is neither O(n) nor Ω(n) ?

Q2. Consider any two positive functions f, and g. Prove that

O(f(n)) + O(g(n)) = O(f(n) + g(n)) = O(max(f(n),g(n))) = max(O(f(n),O(g(n))

Q3. Prove that f(n)+o(f(n)) = Θ(f(n)).

Q4. Show that

n
Σ
 k=1 
 1/(2k-1)  =  ln(Sqrt n) + O(1)
by manipulating the harmonic series.

Q5. Show that

¥
Σ
 k=0 
 k-1/2k  =  0

Q6. Evaluate the sum

¥
Σ
 k=1 
 (2k+1)x2k

Q7. Prove that lg(n!) = Θ (nlg n) and that n! = O(nn).

Q8. Is the function ⌈lg n⌉! polynomially bounded ? Is the function ⌈lg lg n⌉! polynomially bounded ?

Q9. Prove that if f(n) < g(n) that is f(n) is O(g(n)) but not Ω(g(n)), then there exists a function h(n) between them, i.e. f(n) < h(n) < g(n)

Q10. Deduce the complexity of the following algorithms.

  1. Merge Sort
  2. Insertion Sort
  3. Bubble Sort

Q11. Rank the following function by their order of growth.

(lg n)! n! n 2 (sqrt 2)lg n 2lg*n lg(lg*n) ln n nlglg n lnln n (n+1)! 4lgn
n1/lg n 22n lg(n!) lg2n n3 (3/2)n en lg*(lg n) 2n nlg n 22n+1

Note lg*n = min {i>=0: lgi n <= 1}.

PART II


Correct attempt of this part will be awarded by seven bonus marks and consequently the corresponding grades.Five marks are for Question 1 and two are for Question 2. Any downloading from Internet will be caught and you will lose your marks as a punishment and matter will be reported to SSAC.

Q1. Given are two sorted arrays A and B, each containing n integer valued elements. Give an algorithm to find the median (nth smallest) of the 2n elements in union(A,B). Your algorithm should require no more than O(log n) comparisons.

Q2. Consider a computational model in which one comparison takes one time unit. Let T(n) be the worst case time of the median-of-3 algorithm for finding the kth smallest of n elements.

  • Deduce a recurrence for T(n).
  • Draw the recursion tree.
  • Use it to derive a "Θ" Expression for T(n).


How To Submit

You have to submit the solutions on paper to the respective TAs of M. Tech CSE(Ist yr.) students. However the students who attempted the PART II and are sure upto a good extent that their solutions are correct, are required to submit their assignment to Mr.Manish Agarwal either by keeping it on his table in the CSE(MTP)lab or by slipping it under the door of room  #53 MANAS Hostel.

Please make sure:

  1. your name and roll No. appears on the top right corner of your paper.
  2. all the sheets are neatly pinned.
  3. the top of your paper marked "Attempted PART II", if you attempted it.

Home | Notice Board | Instructor | TAs | Students | Assignments | Schedule | Lectures | Resources
Page last updated 20 Aug, 2002 by Manish Agarwal