SIR C R REDDY COLLEGE OF ENGINEERING, ELURU
Approved by AICTE & Affiliated to JNTUK, Kakinada
Accredited by NBA
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
III / IV [Link] (R20), SEMESTER – I, A.Y. 2024-25
ASSIGNMENT – II
Subject: Design and Analysis of Algorithms (R2031052)
Section: A, B & C Marks:5
ANSWER ALL QUESTIONS
S. No QUESTIONS Marks CO Level
Describe the Travelling sales person problem and discuss
1. with an example how to solve it using dynamic 1M CO3 L2
Programming?
Define: (i) State Space tree (ii) E – Node (iii) Dead Node. Give
the statement of sum of subsets problem. Apply sum of subsets
2. technique for n=4, (w1, w2, w3, w4) = (11, 13, 24, 7) and 1M CO4 L3
M=31. Draw the portion of the state space tree using fixed –
tuple sized approach.
Explain how to find Hamiltonian path and cycle using
3. 1M CO4 L2
backtracking algorithm with an example.
Explain about P and NP problems. and write the relationship
4. 1M CO5 L2
between P, NP, NP-hard, NP-Complete.
Write a short note on Cook’s theorem. Explain non
5. 1M CO5 L2
deterministic algorithms. Give some examples.
CO. COURSE OUTCOMES DESCRIPTION
NO.
CO1 Understand fundamentals of algorithms and analyze efficiency of algorithms.
CO2 Apply Divide & Conquer and greedy methods to design an algorithm for a problem.
CO3 Apply Dynamic Programming technique to design an algorithm for a problem.
CO4 Analyze algorithms for problems using various algorithmic methods such as backtracking.
CO5 Apply NP completeness theory to design an algorithm for problem
KNOWLEDGE LEVELS
L1 L2 L3 L4 L5 L6
Remember Understand Apply Analyze Evaluate Create
