Jawaharlal Nehru Technological University Hyderabad B.Tech IV ADVANCED ALGORITHMS Previous Question Paper (July/August - 2022 - R16)

Quick sort is a divide-and-conquer algorithm that picks an element as a pivot and partitions the array around it. The process involves:

1. Pick an element as the pivot from the array.
2. Partitioning: Reorder the array so that all elements with values less than the pivot come before it, and all elements with values greater than the pivot come after it.
3. Recursively apply the above steps to the sub-array of elements with smaller values and the sub-array of elements with greater values.

Example: Consider array [10, 80, 30, 90, 40]. Choosing 40 as the pivot: After partitioning, elements smaller than 40 (10, 30) move to the left, and elements larger (80, 90) move to the right. The array becomes [10, 30, 40, 80, 90]. The process repeats for sub-arrays [10, 30] and [80, 90] until the entire array is sorted.

The Longest Common Subsequence (LCS) problem finds the longest subsequence present in two sequences. Given sequences X of length m and Y of length n, the algorithm uses dynamic programming with a table L[m+1][n+1]:

Algorithm LCS(X, Y, m, n)
for i = 0 to m:
    L[i][0] = 0
for j = 0 to n:
    L[0][j] = 0
for i = 1 to m:
    for j = 1 to n:
        if X[i-1] == Y[j-1]:
            L[i][j] = L[i-1][j-1] + 1
        else:
            L[i][j] = max(L[i-1][j], L[i][j-1])
return L[m][n]

The value L[m][n] contains the length of the LCS. To reconstruct the sequence, one can backtrack from L[m][n] to L[0][0], moving diagonally when characters match and following the direction of the maximum value otherwise.