Assignment-2 for IV Sem B CSE students "Design and Analysis of Algorithms"

Write an algorithm to find maximum and minimum from given list of array elements a[1-n] using divide and conquer approach. Find its time efficiency.

Write merge sort algorithm. Find its time efficiency.

Apply merge sort algorithm for given list of numbers 8  3 2 9 7 1 5 4

Apply merge sort algorithm for the characters M E R G E S O R T

Write quicksort algorithm.

Apply quicksort algorithm for 5 3 1 9 8 2 4 7. Draw its recursive call tree.

Apply quicksort algorithm for the letters E X A M P L E.

Apply quicksort algorithm for the letters Q U I C K S O R T

Write differences between brute force approach and Strassen's method to find multiplication of two matrices of size 2 by 2.

Apply Strassen's method to find multiplication of following 2 matrices.

  A               B

2   5           1   0
5   2           0   1

Apply Strassen's method to find multiplication of following 2 matrices.

  A                               B

2  4  6  3                1   1  1   1
1  2  2  1                1   1  1   2
3  1  1  3                2   1   1  2
1  1  1  1                3   1   1  3

Discuss 3 categories of decrease and conquer technique with examples.

What is topological sort? Give example for both DFS based and source removal algorithms.

Module 3 :

Discuss Greedy Technique with its general plan to find optimal solution for the given problem.

Discuss Coin Change Problem with its algorithm.

Discuss Knapsack Problem with example. Write GrredyKnapsack algorithm.

What is the difference between spanning tree and minimum spanning tree?

Discuss Prim's and Kruskal's algorithm with example.