Assignment 3

 

Assignment 3

1)Sort the following numbers with counting sort algorithm.  5, 3, 1, 2, 1, 4, 1, 3, 2, 5.

2)Explain quick sort algorithm. Sort the following numbers using quick sort.

26, 5, 37, 1, 61, 11, 59, 15, 48, 19

3)Find longest common sub - sequence of X and Y.

X =<A, B, C, B, D, A>

Y=<B, D, C, A, B, A>

4) Explain max & min heap sort with example.

5) Explain Strassen’s multiplication algorithm.

6) Explain algorithm to construct Huffman code.

obtain a set of optimal codes for the messages (m1 , m2 , m3 , m4 , m5 , m6 , m7 ) with relative frequencies (2, 6, 8,  10, 12,16, 20)

7) Find optimal solution to the Knapsack instances n=7 m=15

 (P1, P2, ---------P7) = (20, 15, 5, 8, 6, 18,

 (w1, w2 ------- w7) = (3, 4, 2, 5, 1, 4, 1)

8) Explain insertion sort. Apply insertion sort on following numbers.

 85, 24, 63, 45, 17, 31, 96, 50,

9) State Cook’s theorem. Give its significance

10) Define 4 queen’s problem. Draw state space tree to Find solution for 4 queen’s problem using backtracking

11) Explain any sorting method that uses Divide and conquer strategy. Also discuss its best case and worst-case time complexity

12) Find an optimal solution to knapsack problem instance n = 7, m = 15, p= (10, 5, 15, 7, 6, 18, 3) and w = (2, 3, 5, 7, 1, 4, 1).

13) What is the difference between dynamic programming and greedy algorithms?

14) Draw the binary decision tree for the following set

     (3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 47)

15) Explain about spanning tree and write Kruskal’s algorithm

16) Write algorithm and explain binary search

17) Explain Travelling salesman problem

18) What is all pair shortest path problem?

19) Explain stresses matrix multiplication Formula’s

20) Discuss about various asymptotic notation

 

SHARE

Milan Tomic

Hi. I’m Designer of Blog Magic. I’m CEO/Founder of ThemeXpose. I’m Creative Art Director, Web Designer, UI/UX Designer, Interaction Designer, Industrial Designer, Web Developer, Business Enthusiast, StartUp Enthusiast, Speaker, Writer and Photographer. Inspired to make things looks better.

• 
• 
• 
• 
•