Analysis and Design of Algorithms Theory Assignment 3150703

Assignment - 1
CO 1 Introduction Set 2

# Question BT
1 Explain linear inequality and equations. R/U
2 2
2 Find upper bound of function f(n)= lg(n ) + n lg n A
3 Explain Asymptotic notation. Arrange the growth rate of 2 n, n2, 1, log n, nlogn, 3 n and n in U/E
increasing order of growth.
4 What is the smallest value of n such that an algorithm whose running time is 100n2 runs E
faster than an algorithm whose running time is 2n on the same machine?

CO 1 Sorting Algorithms Set 2

# Question BT
1 Which are the basic steps of counting sort? Write the counting sort algorithm. U
2 Sort following with the Radix Sort Method. : 78, 17, 39, 26, 72, 94, 21, 12, 23, 68 E

Assignment - 2
CO 2 Recurrence Set 2

# Question BT
1 Solve the following recurrence using recursion tree method: E
- T(n) = 3T(n/3) + n^3
2 Solve following recurrence using master method E
- T(n) = 9T(n/3) +n

CO 2 Divide and Conquer Set 2

# Question BT

BT Level
R: Remembrance; U: Understanding; A: Application, N: Analyze, E: Evaluate and C: Create (Revised
Bloom’s Taxonomy)
 Analysis and Design of Algorithms Theory Assignment 3150703

1 Explain the Binary search using the divide and conquer method and compute its worst-case U
running time.
2 Sort the following using Quick sort algorithm : 50, 40, 20, 60, 80, 100, 45, 70, 105, 30, 90, 75 E
3 Find multiplication (A x B) of A = 2341 and B = 6780 using divide and conquer E
methodology.

Assignment - 3
CO 3 Dynamic Programming Set 2

# Question BT
1 Explain the common characteristics of dynamic programming. R
2 Discuss and derive an equation for solving the 0/1 Knapsack problem using a dynamic U/N
programming method. Design and analyze the algorithm for the same.
3 Find anyone Longest Common Subsequence of given two strings using Dynamic E
Programming.
- S1=abbacdcba
- S2=bcdbbcaac

CO 3 Greedy Algorithms Set 2

# Question BT
1 Explain in brief the characteristics of greedy algorithms. R
2 Give and Explain the Kruskal’s Algorithm to find out Minimum Spanning Tree with an U/N
illustration. Give its time complexity.
3 Using the greedy algorithm find an optimal solution for knapsack instance E
- n=7, M = 15
- (P1,P2,P3,P4,P5,P6,P7)=(10, 5, 15, 7, 6, 18, 3) and
- (w1,w2,w3,w4,w5,w6,w7) = (2, 3, 5, 7, 1, 4, 1)

CO 3 Backtracking and Branch Set 2

# Questions BT
1 Explain Backtracking Method. What is the N-Queens Problem? U

BT Level
R: Remembrance; U: Understanding; A: Application, N: Analyze, E: Evaluate and C: Create (Revised
Bloom’s Taxonomy)
 Analysis and Design of Algorithms Theory Assignment 3150703

BT Level
R: Remembrance; U: Understanding; A: Application, N: Analyze, E: Evaluate and C: Create (Revised
Bloom’s Taxonomy)
 Analysis and Design of Algorithms Theory Assignment 3150703

Assignment - 4
CO 4 String Matching Set 2

# Questions BT
1 Explain the Rabin-Karp method for string matching and also give the algorithm and its time U
complexity.
2 Write pseudo-code for Naïve-String-Matching algorithm. U

Assignment - 5
CO 5 P-NP Theory Set 2

# Questions BT
1 Compare NP-Hard with NP-Complete problems. N
2 Explain Minimax principle. U

Assignment - 6
CO 6 Graph Algorithms Set 2

# Questions BT
1 Define: Directed Acyclic Graph, Dense graph, Sparse graph, Preconditioning, Articulation R
Point, Graph, Tree, Complete graph, Connected Graph
2 Differentiate BFS and DFS. N
3 Write an algorithm to find out the articulation points of an undirected graph. Find out E
articulation points for the following graph. Consider vertex A as the starting point.

BT Level
R: Remembrance; U: Understanding; A: Application, N: Analyze, E: Evaluate and C: Create (Revised
Bloom’s Taxonomy)
 Analysis and Design of Algorithms Theory Assignment 3150703

BT Level
R: Remembrance; U: Understanding; A: Application, N: Analyze, E: Evaluate and C: Create (Revised
Bloom’s Taxonomy)