ADA TUTS

ADA

MANAV RACHNA UNIVERSITY


TUTORIAL-0

                  Course: B.Tech. CSE                                          Semester:  III                                   

 Session: May 2020                       Subject:  Analysis and Design of Algorithms(CSH326B) T & P

  Blooms Taxonomy Level: BT1, BT2

Objective: Students will be able to solve the data structure problems.

1.     Write the algorithm for the following

a.      To calculate the Factorial of a number using

i.                 Iteration

ii.               Recursion

b.     To find Fibonacci series using

i.                 Iteration

ii.               Recursion

c.      To push and pop in a stack

2.     Suppose each data structure is stored in a circular array with N memory cells:

a.      Find the number NUMB of elements in a queue in terms of FRONT &  REAR.

b.     When will the array be filled?

3.     Write preorder, postorder and inorder traversal for the given binary tree.

TUTORIAL-1

 

Objective: Students will learn about GROWTH OF FUNCTION.

Blooms Taxonomy Level: BT2, BT3, BT4

 

1. Show that f(x)=x2 + 2x + 1 is O(x2).

2. Show that f(x)=7x2 is O(x3).

3. Show that n2 is not O(n)

4. Is it true that x3 is O(7x2).

 

	x2 + 2x + 1	x2
X=1	4	1
X=4	25	16
X=6	47	36

ADA Assignment -1

Note:-  All questions are for 10 marks.

1.      Explain all the asymptotic notations with function and graphs

2.      Analyse bubble sort and insertion sort and state the difference between then using pseudo code

3.      State the difference between Big-O and Small-O. Is Big-O a subset of Small-O. Explain using f(n) = 2n^2 + n + n/2+5

4.      What do you understand by divide and conquer. Can you write a pseudo code for an algorithm based on this technique? Indicate the best, average and worst time complexity for the pseudo code that you will write. Also state if this pseudo code is stable or not

5.   What are disjoint sets? How do you write disjoint sets? Give some examples of disjoint sets and non-disjoint sets?

ADA ASSIGNMENT 1 SOLVED