SUNDAR COACHING CENTRE

DESIGN AND ANALYSIS OF ALGORITHMS, SEMESTER-4, 2023

PRE-END SEMESTER REVISION EXAMINATION, May06
------------------------------------------------------------------------------------------------------
This Paper consists of 5 Sections.
Section-A convers Introduction of Algorithms. It spans Q1 and Q2, with mark split-up
as 2+3, totalling 5 MARKS.
Section-B convers Greedy Approach. It spans Q3 to Q9, with mark split-up as
6+5+5+5+5+5+6, totalling 37 MARKS.
Section-C covers Dynamic Programming. It spans Q10 to Q17, with mark split-up as
5+5+5+5+5+5+5+5, totalling 40 MARKS.
Section-D convers Amortized Analysis. It spans Q18 and Q19, with mark split-up as
6+5, totalling 11 MARKS.
Section-E covers NP-Problems. It spans Q20, with mark split-up as 7, totalling 7
MARKS.
Therefore, in total, this paper is of 5+37+40+11+7 = 100 MARKS.
------------------------------------------------------------------------------------------------------
SECTION-A: INTRODUCTION TO ALGORITHMS

Question-1
Using tournament method, find the maximum element of the array {3, 2, 8, 1, 4, 9,
10, 1}.
[2]

Question-2
Find out the time complexity of the following C++ Code Snippet using the Master’s
Theorem. Also calculate the value of foo (6).

[3]
------------------------------------------------------------------------------------------------------
SECTION-B: GREEDY APPROACH

Question-3
Using Kruskal’s algorithm, find the minimal spanning tree and using Prim’s
algorithm, find the maximal spanning tree for the following graph:

[3+3]

Question-4
Using Strassen’s Matrix Multiplication, multiply the following matrices:

[5]

Question-5
Solve the Fractional Knapsack Problem using Greedy Approach. The knapsack
capacity is 15 kg. The weights of the items and their corresponding profits are given
by {10, 5, 8, 2} and {60, 30, 45, 10}.
[5]

Question-6
Consider a text document with the characters {A, B, C, D, E} and their
corresponding frequencies as {10, 15, 12, 3, 4}. Using Huffman coding, encode the
string DCBABED.
[5]
Question-7
Using Dijkstra’s Algorithm, find the shortest distance and corresponding path to
each vertex starting from A:

[5]

Question-8
You are given a set of 10 jobs, each with a specific deadline and profit. Each job
takes one unit of time to complete. You can only work on one job at a time. The
objective is to maximize the total profit by selecting a subset of jobs to complete,
considering their deadlines. The deadlines are given by {2, 1, 2, 3, 1, 4, 2, 3, 1, 4}
and the profits are given by {100, 50, 75, 90, 60, 110, 45, 80, 55, 70}. Using the
Job Sequencing with Deadlines algorithm, determine the maximum profit
achievable and the sequence of jobs to be completed.
[5]

Question-9
Show the steps involved in sorting the array {6, 5, 12, 10, 9, 1} using merge sort
and quick sort (taking last element as pivot).
[3+3]

------------------------------------------------------------------------------------------------------
SECTION-C: DYNAMIC PROGRAMMING

Question-10
Solve the given matrix chain multiplication problem using dynamic programming.
The matrix dimension sequence is given by {2, 4, 4, 5, 2, 6}. Find the optimal order
of multiplication to maximize the number of scalar multiplications required.
[5]
Question-11
Solve the 0/1 Knapsack Problem using dynamic programming. Knapsack capacity
is 15 kg. The weights of the items and their corresponding profits are given by {6, 3,
2, 8, 5, 9} and {10, 7, 4, 12, 8, 15}.
[5]

Question-12
Solve the Longest Common Subsequence problem using dynamic programming for
the following strings: String 1: "AGGTAB" and String 2: "GXTXAYB". Determine the
length of the LCS and provide the actual LCS sequence.
[5]

Question-13
Given a set of keys – {1, 2, 3, 4, 5}. Frequencies of successful searches are given by
{5, 2, 3, 9, 7} and unsuccessful searches are given by {1, 3, 2, 5, 7, 4}. Construct an
optimal BST for this situation to minimize the total number of comparisons.
[5]

Question-14
A salesperson needs to visit a set of cities A, B, C, D, E and return to the starting
city. The salesperson has a list of cities to visit, and the distances between each
pair of cities are given by A to B = 10, A to C = 15, A to D = 20, A to E = 25, B to C =
35, B to D = 40, B to E = 45, C to D = 55, C to E = 60, D to E = 70. Find the longest
possible route that visits each city exactly once, starting and ending at city A.
[5]

Question-15
Apply the Floyd-Warshall Algorithm on the following graph and find the shortest
distance between all possible pairs of vertices:

[5]
Question-16
You are given an array A of n integers (n ≤ 10^5). You need to find the maximum
subarray sum such that no two adjacent elements are included in the subarray. To
solve this problem using linear dynamic programming, you can define a state dp[i]
as the maximum subarray sum ending at index i, where no two adjacent elements
are included. You can then use the recurrence relation: dp[i] = max(dp[i-1], dp[i-2]
+ A[i]). Find the answer for the array: [1, -2, 3, -1, 2].
[5]

Question-17
Solve the given multi-stage graph and find the path which requires the minimum
cost to travel.

[5]
------------------------------------------------------------------------------------------------------
SECTION-D: AMORTIZED ANALYSIS

Question-18
Sort the array {8, 1, 6, 4, 0, 3, 9, 5} using randomized quick sort. After sorting,
using randomized binary search, search the elements: 4 and 7. Write proper steps
and find the time complexities of both operations.
[3+3]

Question-19
What is Amortization? Differentiate between the Las-Vegas and Monte-Carlo type
algorithms. Then, find the min cut of the graph below:
 [2+3]

------------------------------------------------------------------------------------------------------
SECTION-E: NP PROBLEMS

Question-20
Explain in depth about the classification of problems. Explain Cook’s Theorem.
[7]
------------------------------------------------------------------------------------------------------