Algorithms Answers

Search the Value 125 from the following array using Binary Search algorithm. Show
the values of BEG, END and MID at each step.
11 22 30 33 40 44 55 60 66 77 80 88 99 125 150 200

Consider a 420 x 680 matrix array SCORE. Suppose Base (SCORE) = 1001 and there
are 2 words per memory cell. Assume that the first element of the array is SCORE
[1,1]. Find the address of SCORE [100, 260] when the array is stored in
i. row major order
ii. column major order.

Consider the linear array BBB[100] where lower bound is -10.
Suppose Base (BBB) = 300 and w = 4 words per memory cell for BBB. Find the
address of BBB [-10], BBB [0] and BBB [15].

White algorithm for bubble sort

public void ppp( Object [ ] data ){
int i,j;
for (j = 0; i < data.length-1; i++)
for (j = data.length-1; j>i;--j)
If (((comparable)data[ jj ]).compareTo (data[j-1]) < 0 )
Swap(data,j,j-1);
}

What is the above java code segment intended to do?
Select one or more:
A. selection sort algorithm
B. quick sort algorithm
C. insertion sort algorithm
D. bubble sort algorithm
E. radix sort algorithm

implemented a linked list to keep record of his savings during the last 10 months. He decided to have 10 nodes each recording a months saving. In his search algorithm, he accidently lost the reference to the first/head node but luckily a reference to the fourth node was retained.

b) Consider the following array values and apply quick sort on it. Only dry run is required but you have to show all steps:
10 3 8 5 12 2 15 4 1

int myFunc(int A[], int n)
{
int i, j, max = 0;
int msis[n];

for ( i = 0; i < n; i++ )
msis[i] = A[i];

for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if (A[i] > A[j] &&
msis[i] < msis[j] + A[i])
msis[i] = msis[j] + A[i];

for ( i = 0; i < n; i++ )
if ( max < msis[i] )
max = msis[i];

return max;
}
a) What is the time complexity of the algorithm

1. Compute the minimum number of multiplications required for the matrix chain A 1 × 5, B 5 × 10,
C 10 × 15, D 15 × 20, E 20 × 5. Show the contents of the dynamic programming table along with the
calculations considered. Also give the recurrence?
2. Compute the Longest Common Subsequence for the strings X = [ABCDABCAB] and Y = [BCBCB].
Show the contents of the dynamic programming table. Also give the recurrence?

ADVANCED DESIGN AND ANALYSIS OF ALGORITHMS - ASSIGNMENT 3 [20 points]
Assignment Date: 30 November 2020
Due Date: 04 December 2020 Midnight
INSTRUCTIONS:
A. Please do your own work.
B. Submit your work well before time.
C. Plagiarized work shall earn zero credit for the submission.
TASKS:
1. Compute the minimum number of multiplications required for the matrix chain A 1 × 5, B 5 × 10,
C 10 × 15, D 15 × 20, E 20 × 5. Show the contents of the dynamic programming table along with the
calculations considered. Also give the recurrence?
2. Compute the Longest Common Subsequence for the strings X = [ABCDABCAB] and Y = [BCBCB].
Show the contents of the dynamic programming table. Also give the recurrence?