Scribd
Upload
18 views

CSE303 ADA Assignment (Module3+4+5)

Uploaded by

girdharilals762
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views

CSE303 ADA Assignment (Module3+4+5)

Uploaded by

girdharilals762
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Analysis and Design of Algorithm (CS-303)

Assignment [Module 3]
[Deadline submission: 25 Oct, 2024]

Q.1 (a) Consider two strings 𝑋 = (2,2,1,1,2,1,2,1) and 𝑌 = (2,1,1,2,2,1,1,2,1). Let 𝑙 be the length
of the longest common subsequence between X and Y and n be the number of such common
subsequences between X and Y. Then find the value of (𝑙 + 10𝑛).
(b) Determine LCS for the sequence

𝑋 =< 𝐸, 𝑋, 𝑃, 𝑂, 𝑁, 𝐸, 𝑁, 𝑇, 𝐼, 𝐴, 𝐿 > and 𝑌 =< 𝑃, 𝑂, 𝐿, 𝑌, 𝑁, 𝑂, 𝑀, 𝐼, 𝐴, 𝐿 >

Q.2 What is “principle of optimality”? Write a pseudo code for finding all pair shortest path
using Floyed algorithm. Apply this algorithm for the following graph. Analyze its time-
complexity also.

Q.3 (a) Given a Chain of n-matrices 𝑀1 , 𝑀2 , … . . , 𝑀𝑛 with their dimensions


(𝑝0 × 𝑝1 ), (𝑝1 , 𝑝2 ), … (𝑝𝑛−1 × 𝑝𝑛 ). Write a general formula to find the total number of ways
to parenthesize the given n-matrices.
(b) Given a chain of 6-matrices 𝑀1 , 𝑀2 , 𝑀3 , 𝑀4 , 𝑀5 , 𝑎𝑛𝑑 𝑀6 with dimension vector
𝑑 = [30,35,15,5,10,20,25]. Find an optimal way (minimum No. of scalar multiplications) to
calculate the product 𝑀 = 𝑀1 × 𝑀2 × 𝑀3 × 𝑀4 × 𝑀5 × 𝑀6

Q.4 Solve the following instance of 0/1 knapsack problem using dynamic programming:
Number of objects n=5, Knapsack capacity M=10,
Profit P = (1,6,18,22,28) and weight W = (1,2,5,6,7)

Q.5 Explain how TSP problem is solved using dynamic programming? Find the solution of the
following TSP problem where adjacency matrix is given as:

0 2 2 4
3 0 6 2
[ ]
2 5 0 4
5 4 3 0

*************************************

1
Assignment 4
[Deadline submission: 25 Oct, 2024]

Graph Searching and Traversal

Q1. Differentiate between DFS and BFS with respect to Time and space complexity (b is a branching
factor and m is the depth of the sallowest goal node).
Q2. Given the following graph where A is the starting node and K is the goal node.

Trace Graph-Search algorithm using BFS and DFS strategies. In each case, show the order in which
nodes are added to the fringe as well as the generated tree and the solution path. Leftmost nodes are
added before rightmost ones. Indicate if found solutions are optimal.

Q3. Design an algorithm that uses DFS to find all strongly connected components of a directed graph.

Backtracking

Q4. Let n=6 and w[1:6]=[5,10,15,20,25,12] and m=35. Find all possible subsets of w such that sum
will be equals to m. Draw the state space tree also.

Q5. Consider three items <I1, I2, I3,I4> with the respective weights and values as <W1=2, W2=3,
W3=4,W4=5> and <V1=3, V2=5, V3=6,V4=10>. The knapsack capacity is W=8. Apply backtracking
approach to obtain optimal solution.

Q6. For which values of n does the n queen problem have no solutions? Draw a state space tree for 4
queen’s problem (avoid same row, same column, and diagonal) using backtracking. Write two possible
solutions of 8 Queen’s problem.

2
Branch & Bound

Q.7: Solve the following instance of 0/1 Knapsack problem using Branch and bound.
Knapsack Capacity W=16.

Items Weight Value (in $)


I1 9 10
I2 6 6
I3 7 5
I4 3 1
Q8. Given a set of cities and distance between every pair of cities, the problem is to find the shortest
possible tour that visits every city exactly once and returns to the starting point. Find the LC branch
and bound solution for this travelling salesperson problem.

Module5 (Assignment)
[Deadline submission: 25 Oct, 2024]

Q.1 Differentiate between P, NP, NP-C and NP-Hard Problems with a suitable diagram.
Q.2 State Cook-Levin Theorem.
Q.3 Consider a well-known NP-Hard problem SAT. If 𝐿 ∈ 𝑁𝑃 𝑎𝑛𝑑 𝑆𝐴𝑇 ≼𝑃 𝐿 then what we can say
about class of problem L?
Q.4 Show that the following problem is NP-Complete (Any two of the following)
(i) CLIQUE problem (ii) Vertex cover problem (VCP)
(iii) Hamiltonian cycle problem (iv) TSP

(Multiple choice questions)


Q.5 Let L be an NP-complete problem and Q and R be two other problems not known to be in NP. Q
is polynomial time reducible to L and L is polynomial-time reducible to R. Which one of the following
statements is true?
A. Q is NP-Complete B. Q is NP-Hard C. R is NP-Complete D. R is NP-Hard
Q.6 Consider two decision problems A1, A2 such that A1 reduces in polynomial time to 3-SAT and
3-SAT reduces in polynomial time to A2. Then which one of the following is consistent with the above
statement?
A. A1 is in NP, A2 is NP hard B. A2 is in NP, A1 is NP hard
C. Both A1 and A2 are in NP D. Both A1 and A2 are in NP hard
3

You might also like