E7 MAR 2018

Reg. No.
Amrita Vishwa Vidyapeetham
Amrita School of Engineering, Bengaluru
Depart1ment of CSE
Periodical Test - 2, March 2018
15CSE211 Design and Analysis of Algorithms Max.: 50 Marks
Sem /Branch: IV CSE A and B Sections Duration: 2 Hrs.
Answer all the questions.
Part A 5 x3 =15 Marks
1
In the single-processor scheduling problem, we are given aset of njobs. Each job i has adeadline
di.Afeasibie schedule is apermutation of the jobs such that when the jobs are performed in that
order, every job is finished before its deadline. The greedy algorithm for single-processor
scheduling selects the job with the earliest deadline first. Show that if a feasible schedule exists,
then the schedule produced by this greedy algorithm is feasible. What is the optimal solution?
Job Deadline in Profit per
Profit
Minutes Minute
A 19 2 19
B 27 1 27
25 25
D 30 30

2. Write the binary encoding of the messages using the table: i) BCDA i) BADBB
A BC D

0 1 11 10 *UK REFERENCE ONLY

Check whether the given encoding scheme leads to unambiguous decoding or not for any arbitrary
message. Justify.

3. Compare and Contrast Divide &Conquer method, Dynamic Programming and Greedy method.
Mention the suitable examples for each method.
4. Suggest a technique which could be the best to solve for each of the following problems and
justify your answer.
i) Given a set of non-negative integers, and a value sum, determine if there is a subset of the
given set with sum equal to given sum. Examples: set [ ]= {3, 34, 4, 12, 5. 2}, sum = 9
Output: True, There is a subset (4,5) with sum 9.
i) Given the capacity of Compact Disc as 650 MB and a bunch of songs of varying sizes
(anown sizes), store maximum songs on the Compact Disc until it is full.
ii) Hunt the way out for thegiven maze. If noway out possible then report that as an error.
S. Complete the Sudoku 4x4 and show the application of backtracking in the solution.
3

1
2

Page 1 of 2

035
(35 M a r k s )

Part B
(10M)
6
Consider the codes shown below:
D E
Character B
1 0 ||10
001011
000
Encoding 16 18
10 23
Frequency in Thousands 25 the cost.
form. Find
binary tree
101100010002

i) Arrange the given codes for characters in a decode the string

new code will havc
How do you
ii) Do these codes have the prefix-property? so that the characters as
ii) Modify the above code (keeping the prefix
property)
frequencies of
the given in
document with
the cost.
minimum storage requirement for a compute the
the new code and
the above table. Showthe binary tree for moulding and
processes: painting.
main
through 2 and painting (m; and p,
7. There are Ntoys. Each toy needs to passpainting. The time for moulding moulding

Obviously, moulding must be done before

Now we only have 1
such that
machin,
toy may be different. a suitable order the total
respectively for i toy) for every the Ntoys
produce
in
complete thetasks in order)
and I painting machine. How should we optimal time required to
production time is minimized? What is
the (8 M)
p. (mins)
m, (mins)
Toy i
5
2

2 2
4

4 7
3
5 4

6
a set ots
should take from
deciding which subset
of items you
problem inyolves the size of the items. or th:
8. Knapsack perhaps the worth of the items, an item or
optimize some value: we can either take lea
if you want to In this problem, we will assume that a fixed size. and o:
worth to size. knapsack has
ratio of
fractional part of an
item). Our
hold at most 25 units of spa:
it (we cannot take a the selected items. Our knapsack can items and o
optimize the worth of worth. Show the steps for the selection of
and their
Here is the list of items (8 M
on the given problem.
Size Worth
Item
22 12
Laptop
10 9
Play Station
Textbook 9
Basketball 6
distinct
a) A chain of 6 matrices A through F is to be multiplied. Find the number of
9.
parenthesized.
ways by which the matrices can be fully
required to multiply the following char
b) Find the number of scalar multiplications
Show the best order of muti
matrices along with the solution for the sub-problems.
them.

Matrix Name A1 A2 A3 A4
Order 2X5 5 X33X6 6X4

036
31 MAY 2024

Reg. No:
Amrita V:slhwa Vidyapeetham
Anrita School of Computing,
B.Tech. Semester Examinaticn -Bengaluru
May 2024
Fourtii & Fifth Semester
Common to CSE & AIE
21AIE212/19CSE302 Design and Analysis of Algorithms
ation Three hours Maximum: 100 Marks

CO Course Outcomes
Evaluate the correctness and analyze
Col complexity offalgorithms solve classical
Understand and implement varicus techniques and
CO2 problems
algorithmic design
for real world problems by identifying, applying and implementing
Design solutions
CO3 appropriate designtechniques.
solutions for real world
CO4 Design problem by napping to classical problemscomplexity
the
COS Ånalyze impact of various implementation choices on the algorithm

Answer all the questions

[Col] [4]
Professor Xuses the following algorithn for merging ksorted lists, each havi3
second list [BTLA]
u/k elements. The algorithm takes the first list and merges it with the
1sing a linear-time algorithm. Then, it merges the resulting list of 2n/k elements
with the fourth
with the third list, merges the list of 3n/k elements that results
eleients. Analyze
ist. and so forth, until it ends up with a single sorted list ofall
algorithm in terras cf n and k.
the wors:-case running time of the Professor's COS)
strategy to solve each of the following [BTL4]
8 Qutline a suitable algorithmic design
problems. Give the reason for your choice. [21
size "2 x 1", count the number of ways to
i Given a "2 xn" board and tiles of placed
tile the given board using the
2 x 1 tiles. A tile can either be
vertically i.e, as 2x1tile.
horizontally i.e., as a l x2 tile or of rooms 2]
hotel manager of XYZ hotel has to process Nadvance bookirgs
ii. The Bookings contain an arrival
date
hotel has Krooms.
for the next season. XYZ whether there are
date. The manager wants to find out
and a departure

enough rooms inthe hotel

to satisfy the demand. [2]
graph can be
undirected graph and a number m, determine if the
ii. Given an that no two adjacent vertices of
the graph
most m colors such
colored with at graph means the
the same color. Here coloring of a
are colored with
assignment of colors to all
vertices. [Co1] [4]
5T("/A)+n using
recursive tree
recurrence relation T(n) = [BTL3]
C Solve the
approach.
white, or blue. [CO3) [8]
n elenents, each of which is ed, BTL5]
consists of whites.
Suppose an array A come before all the
so that all the reds
We seek to sort
the elements
operation permitted on
the keys are
the blues. The ory
which come before all Page 1 of 4
Iramine(A,) - report the color of the helement of A
Swap(A,ij) -swap the element of Awith the element.
rma acorrect and efficient algorithm for red-white-blue sorting and make sure
that your proposed algorithm works in linear time.
3.
Mail Express, an overnight mail service delivers mail to customers throughout |C04)
the United States, Canada, and Mexico, Fortunately, Mail Express has [BTL3}
additional capacity on one of its cargo planes. To maximize profits, Mail
Express takes shipments from local manufacturing plants to warehouses for
other companies. Currently, there is room for another 6tons. Table 1shows the
items that can be shipped, their weights. the expected profit for each (in dolaS),
and the number of available parts. How many units of each item do you suggeS
that Mail Express ship?
Table 1
Item Weight (Tons) Profit/Unit Number Available
3 6
2 2
3
2
2 2

4 Given a single sequence of numbers, design an algorithm to find the longest [C04]
monotonically increasing subsequence. For example, in the sequence 23143758 BTL3]
the longest monotonically increasing subsequence is 23458. What is the running
time of your algorithm? Show the working of the algorithm for this example.

5 Given a one-dimensional array that contain both positive and negative integers,
find the sum of contiguous subarray of numbers which has the largest sum based
on the following approaches.
The problem described above when solved using divide andconquer approach [C02
has a complexity of O(nlogn). Find the maximum sum using this mentioned BTL3]
approach for the aray (-2, -3, 4, -1, -2, 1, 5, -3}.
b. Avariation of the algorithm proposed by Kadane (given below) claims that the [COs]
above problem can be solved using dynamic programming approach with a BTL4]
worst-case complexity of 0(2). Verify the algorithm to get the result obtained
in the subdivision (a). Kadane's algorithm is as follows:
Initialize:
max so far =0
max _ending here =0
Loop for each element of the array
Step 1 max ending here = max ending here +t ali)
Step 2if(max_ending here <0)
max_ending here =0
Step 3 if(max so far < max_ending
here)
max so far = max ending here
return max so far

S
Çolve thesudok1, given in Figure l using backtracking approach. Show the [CO1

space tree. |BTL3)

complete,state
34

Figure l
(3)
Rabin- -Karp algor1thm find the number of valid and spurious hits while
[CO2]

(BTL3]
Using the pattern P
matching
"MIPS" in the text
OREMPSUMDOLORSITAMET»

Use ASCII values. [Note: A-65].

modulo as 19.
A s S u m
the
e
[1!
the
Worst-Case
complexity of this algorithm?
What is
better
than the naive approach?
Isit
b

[COs] (3]
whether
the following are true or false. Justify your answer. (BTL4J

are given an instance of the Minimum Spanning Tree Problem on

State
we
minimum
Suppose

with edge costs that are all positive and distinct. Let Tbe ai
G,
graph
tree for this instance. Now Suppose we replace each edge
cost C by its
newinstance of the problem with the same graph
spanning

Ce, thereby creating a

costs. As perthis Construction, T will be a minimum spanning tre. [CO2]
square,

different
but depth-first
the order of the vertices encountered ona breadth-first and (BTL3]
Report
picking the vertices
starting from vertex A in Figure 2. Break all ties by
thus
searches
typeof edges
order, Draw the resultant trees highlighting the
alphabetical

in
o b t a i n e d .

34

24
22
35

25 19
16 39

65
23

4
12

30

Figure 2 [CO2]
components. Identify the
connected
example graph
which has two reason for your chninn
C Give an from your graph. State the
separation edges and vertices [5
[CO2]
gure 3.
the graph Ggiven in
[BTL3]
topological sorting for
Perform

Figure 3
Page 3 cf 4

16
163
The initial Dmatris and the computed D'matrix for a4-noded digraph is pivcn (Cy.
in Figure 4. Using these matrices, compute the final ' using Floyd-Warshail's (i
algorithm. How many entrics change when compared with D?
3 0 0 3 15
12 5 D ' |l6 0 12
DO
4 7 0
l2 -4 4

Figre 4

10. Figure 5 shows the lengths, in miles, of roadsconnecting 10 towns. [CO21

i. Use Kruskal's algorithm, showing the order in which, you select the edges, (BTL31
to find the minimum spanning tree for the network. Draw your minimum
spanning tree and state its length.
ii. Use Dijkstra's algorithm to find the shortest distance from A to J. State the
route corresponding to this minimum distance.
iii. A new road is built connecting F to I. The length of this road is x miles,
where x is an integer. A shorter route from A to J than that found in
subdivision (ii) is now available. Find the maximum value of x.

12

Figure 5

11. Define the follo wing class of problems and give one example for each category. [CO1]
P, NP, NP Complete [BTLI|

Course Outcome /Bloonm's Taxonomy Level (ETL) Mark Distribution Table

CO Marks BTL Marks

CO1 14 BTLI 06
C02 46 BTL2 04
CO3 14 BTL3 62
16 BTL4 20
COs BTL5 8
BTL6 0

S
Page 4 of4
170