Learn more about our help with Assignments: Algorithms
Search & Filtering
Algorithms
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
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
Algorithms
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.
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.
Algorithms
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].
Suppose Base (BBB) = 300 and w = 4 words per memory cell for BBB. Find the
address of BBB [-10], BBB [0] and BBB [15].
Algorithms
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
10 3 8 5 12 2 15 4 1
Algorithms
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
{
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
Algorithms
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?
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?
Algorithms
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?
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?
Algorithms
1. Show that 3-SAT problem is in NP appealing to the definition of the NP class .
2. Finding a vertex cover of a graph, is a problem of finding a set of vertices of minimum size such that each edge in the graph is covered with at least one vertex. Formulate a decision version of the vertex cover problem.
3. Suppose A and B are two different decision problems and furthermore assume that problem A is polynomial-time reducible to problem B. If problem B is NP-complete, is problem A NP-complete ? Justify your answer.
Algorithms
Write a structured algorithm to prompt the user to enter the length of a square. Calculate the output and area of the square
Algorithms
Write a structured algorithm to prompt the user to input the ages of four friends. The algorithm should allow the user to input the ages, find and print the average.
"assignmentexpert.com" is professional group of people in Math subjects! They did assignments in very high level of mathematical modelling in the best quality. Thanks a lot
#339914 on Dec 2023
#339914 on Dec 2023