Scribd
Upload
23 views1 page

Daa Mid2 QP Mca

The document outlines the II-MCA I-SEM II-MID Examinations for the Design and Analysis of Algorithms course at Satya Institute of Technology and Management. It includes four questions focused on algorithmic problems such as the 0/1 Knapsack problem, subset sum, the Travelling Salesman Problem, and concepts of P, NP, NP-HARD, and NP-COMPLETE. Each question carries equal marks and aims to assess students' understanding of various algorithmic approaches and complexity theory.

Uploaded by

SwethaRouthu
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
23 views1 page

Daa Mid2 QP Mca

The document outlines the II-MCA I-SEM II-MID Examinations for the Design and Analysis of Algorithms course at Satya Institute of Technology and Management. It includes four questions focused on algorithmic problems such as the 0/1 Knapsack problem, subset sum, the Travelling Salesman Problem, and concepts of P, NP, NP-HARD, and NP-COMPLETE. Each question carries equal marks and aims to assess students' understanding of various algorithmic approaches and complexity theory.

Uploaded by

SwethaRouthu
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/ 1

SATYA INSTITUTE OF TECHNOLOGY AND MANAGEMENT

NAAC Accredited, Approved by A.I.C.T.E &Permanently Affiliated to JNTUK-Kakinada


Gajularega, Vizianagaram, Andhra Pradesh -535002
DEPARTMENT OF MASTER OF COMPUTER APPLICATIONS
II -MCA I- SEM (R20) II-MID EXAMINATIONS JUNE-2025
Design and Analysis of Algorithms
Course & Sem: II MCA & I SEM Subject Code: MCA2105
Date: 25-06-2025 Time: 10:30 AM – 12:30 AM

Max.Marks:40M R SWETHA
All questions carry equal marks Answer all questions.

(Q1) Solve the following instance of 0/1 KNAPSACK problem using Dynamic programming n = 3, (W1,
W2, W3) = (2, 3, 4), (P1, P2, P3) = (1, 2, 5), and m = 6. [10M]
Course Outcome -04 Program outcome-03
Solve problems using divide and conquer, greedy, Design solutions for complex engineering
dynamic programming, backtracking and branch and problems and design system components or
bound algorithmic approaches processes that meet the specified needs.

(Q2) Find all possible subsets of w that sum to m. Let w={5,7,10,12,15,18,20}and m=35 and draw the
portion of the state space tree that is generated using backtracking with an algorithm. [10 M]

Course Outcome-04 Program outcome-03


Solve problems using divide and conquer, greedy, Design solutions for complex engineering problems
dynamic programming, backtracking and branch and design system components or processes that
and bound algorithmic approaches meet the specified needs

(Q3) DiscussTravelling Salesman Problem using Branch and Bound Algorithm with an example. [10 M]
Course Outcome-03 Program outcome-03
Solve problems using divide and conquer, greedy, Design solutions for complex engineering problems
dynamic programming, backtracking and branch and and design system components or processes that meet
bound algorithmic approaches the specified needs.

(Q4) Explain what is P , NP, NP-HARD and NP-COMPLETE with diagrams. [10 M]
Course Outcome-05 Program outcome-02
Demonstrate an understanding of NP- Completeness Identify, formulate, and analyze complex engineering
theory and lower bound theory problems reaching substantiated conclusions using the
first principles of engineering sciences.

You might also like