Scribd
Upload
6 views6 pages

Daa Ia1

The document outlines algorithms for finding the Longest Common Subsequence (LCS) using recursion and dynamic programming, as well as sorting algorithms including Insertion Sort, Quick Sort (with Lomuto and Hoare's partitioning methods), and Merge Sort. It also describes the Matrix Chain Multiplication problem and provides a dynamic programming solution for optimal matrix multiplication order. Each algorithm is presented with its respective pseudocode.

Uploaded by

BotGamer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views6 pages

Daa Ia1

The document outlines algorithms for finding the Longest Common Subsequence (LCS) using recursion and dynamic programming, as well as sorting algorithms including Insertion Sort, Quick Sort (with Lomuto and Hoare's partitioning methods), and Merge Sort. It also describes the Matrix Chain Multiplication problem and provides a dynamic programming solution for optimal matrix multiplication order. Each algorithm is presented with its respective pseudocode.

Uploaded by

BotGamer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

LCS

Checks for every subsequence of sequence 1 whether it is also a subsequence in sequence


2. Sequence S1 and S2 with length n and m respectively. So, the LCS of S1 and S2 is the
maximum of LCS( S1[1…m-1],S2[1….n]),LCS(S1[1…m],S2[1…..n-1])).

Recursion
int LCS(string X, string Y, int i, int j) {
if (i == 0 || j == 0)
return 0;
if (X[i - 1] == Y[j - 1])
return LCS(X, Y, i - 1, j - 1) + 1;
return max(LCS(X, Y, i, j - 1), LCS(X, Y, i - 1, j));
}

DP
function LCS(X, Y):
m = length(X)
n = length(Y)
let dp[m + 1][n + 1] be a 2D array

// Initialize base cases


for i = 0 to m:
dp[i][0] = 0
for j = 0 to n:
dp[0][j] = 0

// Fill the dp table using the recurrence relation


for i = 1 to m:
for j = 1 to n:
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

// Length of LCS is stored in dp[m][n]


return dp[m][n]
Insertion sort
Algorithm InsertionSort(A, n)
for i = 1 to n - 1 do
key = A[i]
j=i-1
while j ≥ 0 and A[j] > key do
A[j + 1] = A[j]
j=j-1
end while
A[j + 1] = key
end for
end Algorithm
Quick Sort
Algorithm QuickSort(A, low, high)
if low < high then
pivotIndex = Partition(A, low, high)
QuickSort(A, low, pivotIndex)
QuickSort(A, pivotIndex + 1, high)
end if
end Algorithm

Lomuto
Algorithm Partition(A, low, high)
pivot = A[high]
i = low
for j = low to high - 1 do
if A[j] ≤ pivot then
swap(A[i], A[j])
i=i+1
swap(A[i], A[high])
return i
end Algorithm

Hoare’s
int partition(int arr[], int low, int high) {
int p = arr[low];
int i = low;
int j = high;
while (i < j) {
while (arr[i] <= p && i <= high - 1)
i++;
while (arr[j] > p && j >= low + 1)
j--;

if (i < j)
swap(&arr[i], &arr[j]);
}
swap(&arr[low], &arr[j]);
return j;
}
Merge Sort

Chain Matrix
function MatrixChainOrder(p):
n = length(p) - 1
let dp[n][n] be a 2D array
for i = 1 to n:
dp[i][i] = 0

for length = 2 to n: // length of the subchain


for i = 1 to n - length + 1:
j = i + length - 1
dp[i][j] = ∞
for k = i to j - 1:
cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
if cost < dp[i][j]:
dp[i][j] = cost

return dp[1][n]

You might also like