Scribd
Upload
9 views4 pages

ADA Assignment 3

This document is an assignment for the Analysis and Design of Algorithm course at the East West Institute of Technology, outlining various algorithmic concepts and problems. It includes tasks such as constructing minimum cost spanning trees, applying Dijkstra's algorithm, and solving problems using techniques like backtracking and branch and bound. The assignment aims to assess students' understanding of algorithm analysis, efficiency, and design methods.

Uploaded by

vaishumyakalamaddi
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
9 views4 pages

ADA Assignment 3

This document is an assignment for the Analysis and Design of Algorithm course at the East West Institute of Technology, outlining various algorithmic concepts and problems. It includes tasks such as constructing minimum cost spanning trees, applying Dijkstra's algorithm, and solving problems using techniques like backtracking and branch and bound. The assignment aims to assess students' understanding of algorithm analysis, efficiency, and design methods.

Uploaded by

vaishumyakalamaddi
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

East West Institute of Technology

(Affiliated to Visvesvaraya Technological University, Belagavi)


Department of Artificial Intelligence & Machine Learning

(2024-25 Even Semester)

ASSIGNMENT-3

Course Name :Analysis and Design of Algorithm Course Code :BCS401

Course Outcomes: After Studying this course, students will be able to:
BCS401.1 To learn the methods for analyzing algorithms and evaluating their performance.

BCS401.2 To demonstrate the efficiency of algorithms using asymptotic notations.


To solve problems using various algorithm design methods, including brute force, greedy,
BCS401.3 divide and conquer, decrease and conquer, transform and conquer, dynamic programming,
backtracking, and branch and bound.

Bloom’s
Sl.No Questions CO
Level
Construct minimum cost spanning tree using Kruskals algorithm for the following
graph.

1 CO3 L3

What are Huffman Trees? Construct the Huffman tree for the following data.

2 CO3 L3

Encode DAD-CBE using Huffman Encoding.


Apply Dijkstra’s algorithm to find single source shortest path for the given graph by
considering S as the source vertex.

3 CO3 L3

Explain the following with examples


4 CO3 L3
i) P problem ii) NP Problem iii) NP- Complete problem iv) NP – Hard Problems

What is backtracking? Apply backtracking to solve the below instance of sum of


subset problem S={5,10,12,13,15,18} d=30
5 CO3 L2

Illustrate N queen’s problem using backtracking to solve 4-Queens problem


6 CO3 L3

Using Branch and Bound technique solve the below instance of knapsack problem.

7 CO3 L2

Capacity 5

Apply Greedy method for the following instance of Knapsack problem. Given:
Knapsack capacity (M) = 15.

8 CO3 L3
Apply Prim's algorithm to obtain a minimum cost spanning tree for the given graph.

9 CO3 L2

For the given data, find the optimal job sequence and maximum profit using Greedy
approach.

10 CO3 L2

Solve the given instance of 0/1 Knapsack problem using Branch and Bound
technique. Given: Knapsack Capacity (m) = 15

11

Apply the Branch and Bound algorithm to solve the travelling salesperson problem
for the given graph.

12.

13. Explain: (i) Cook’s theorem (ii) Non-deterministic algorithms.

Define minimum cost spanning tree. Obtain a minimum cost spanning tree for the
given graph using (i) Prim’s Algorithm and (ii) Kruskal’s Algorithm.

14.
Solve the given traveling salesperson problem using Branch and Bound technique.

15.

Faculty Incharge Head of the Department


Prof.Vedashree C R Dr. E V Vidya

You might also like