Scribd
Upload
10 views2 pages

B.Tech CSE IV Sem Algorithm Assignment

This document outlines the Theory Assignment -2 for the B.Tech CSE program, detailing submission instructions, evaluation criteria, and a list of questions related to algorithms. The assignment is to be submitted individually and contributes 10% to the internal evaluation, with a total of 120 students enrolled. Questions cover various topics including sorting algorithms, dynamic programming, and optimization techniques.

Uploaded by

spandan1106
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
10 views2 pages

B.Tech CSE IV Sem Algorithm Assignment

This document outlines the Theory Assignment -2 for the B.Tech CSE program, detailing submission instructions, evaluation criteria, and a list of questions related to algorithms. The assignment is to be submitted individually and contributes 10% to the internal evaluation, with a total of 120 students enrolled. Questions cover various topics including sorting algorithms, dynamic programming, and optimization techniques.

Uploaded by

spandan1106
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

School of Engineering & Technology

Department: CSE Session: Even

Programme: [Link] CSE Section Semester: IV


A,B

Course Code: ENCS202 Number of students:120

Course Name: Analysis & Design Faculty: Dr. Swati Gupta


of Algorithms

Theory Assignment -2
Instructions:

 Assignment needs to be submitted by given date


 Assignment must be submitted on ([Link]
 Use of ChatGPT and similar tools is strictly prohibited.
 Assignment must be written on dedicated assignment copy for ADA subject.
 All assignments must be prepared as per the format shared in classes
 Assignment needs to be submitted by each individual.
 Total marks:10
 This assignment contributes to total 10% of internal evaluation
 Assignments will be evaluated on the basis of the following metrics.
 Originality
 Correctness
 Completeness

S. No. Questions CO’s

1. Discuss Quick Sort Algorithm and Explain it with example. Derive Worst CO1
case and Average Case Complexity.
2. Assume that we have a knapsack with max weight capacity, W = [Link] CO2
objective is to fill the knapsack with items such that the benefit (value or
profit) is maximum. Consider the following items and their associated weight
and value
ITEM WEIGHT VALUE

i1 6 6

i2 10 2

i3 3 1
i4 5 8

i5 1 3

i6 3 5

3. Compare Greedy and DYNAMIC Programming Techniques CO1

4 Devise a “binary search” algorithm that splits the set not into two sets of CO1
(almost) equal sizes but into two sets, one of which is twice the size of the
other. How does this algorithm compare with binary search?
5 State the condition when a problem exhibits optimal substructure, while CO3
preparing an optimal substructure , in designing a solution to the problem
using dynamic programming.
6. Consider a variant of the matrix-chain multiplication problem in which the CO2
goal is to parenthesize the sequence of matrices so as to maximize, rather than
minimize, the number of scalar multiplications. Does this problem exhibit
optimal substructure?
7 Find LCS-LENGTH on the sequences X= {A B C B D A B } and Y ={B D CO2
C A B A}. explain why The running time of the procedure is ɵ (mn)
8 Determine an LCS of {1 0 0 1 0 1 0 1} and {0 1 0 1 1 0 1 1 0}. CO1

9 Write the asymptotic notations used for best case ,average case and worst CO1
case analysis of algorithms and Write an algorithm for finding maximum
element of an array perform best , worst and average case complexity with
appropriate order notation

10 How the operations performed in Strassen’s Matrix multiplication CO3

11. What is the largest number of key comparisons made by binary search in CO1
searching for a key in the following array? 3,14, 27, 31, 39, 42, 55, 70, 74,
81, 85, 93, 98

12. Elaborate how backtracking technique can be used to solve the n-queens CO2
problem. Explain with an example.

13. Apply the branch and bound algorithm to solve the traveling salesman CO2
problem for the following graph

You might also like