Consider the pseudo-code below: ALGORITHM MaxElement(A[0..n - 1]) //Determines the value of the largest element in a given array //Input: An array A[0..n - 1] of real numbers //Output: The value of the largest element in A maxval - A[0] for i 1 to n - 1 do if A[i] > maxval maxval ← A[i] return maxval a. What is the basic operation of this algorithm? b. Give the best-case and worst-case time complexities of this algorithm in asymptotic notation. Consider the algorithm below and give its best-case and worst-case time complexities in asymptotic notation. ALGORITHM UniqueElements (A[0..n-1]) //Determines whether all the elements in a given array are distinct //Input: An array A[0..n - 1] //Output: Returns "true" if all the elements in A are distinct // and "false" otherwise for i 0 to n - 2 do for ji+ 1 to n - 1 do if A[i] = A[j] return False return True

Consider the pseudo-code below: ALGORITHM MaxElement(A[0..n - 1]) //Determines the value of the largest element in a given array //Input: An array A[0..n - 1] of real numbers //Output: The value of the largest element in A maxval - A[0] for i 1 to n - 1 do if A[i] > maxval maxval ← A[i] return maxval a. What is the basic operation of this algorithm? b. Give the best-case and worst-case time complexities of this algorithm in asymptotic notation. Consider the algorithm below and give its best-case and worst-case time complexities in asymptotic notation. ALGORITHM UniqueElements (A[0..n-1]) //Determines whether all the elements in a given array are distinct //Input: An array A[0..n - 1] //Output: Returns "true" if all the elements in A are distinct // and "false" otherwise for i 0 to n - 2 do for ji+ 1 to n - 1 do if A[i] = A[j] return False return True

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Rank SortWrite an efficient parallel program that reads n integers from any input file and implements rank sort using p processors (p << n). Assume n is divisible by p.Given n integers stored in an array, rank sort computes rank of every a[j] as follows: Rank a[j] = no. of array elements that are ≤ a[j] for k = 0, 1, 2 … j-1 + no. of array elements that are < a[j] for k = j+1, j+2, j+3,… n – 1 Note: Every a[j] is compared with all array elements.
Implement the algorithm in C++. Algorithm: substring (s, p, len) Initialize i = p and count =0 Use an array „dest‟ to hold the required substring Repeat steps 4 ,5 and 6 while count <len dest[count] =s[i] count = count+1 i = i +1 Insert string terminator at end of dest Exit
Write the code of MergeSort algorithm using JAVA programming language. Assume your array continues 8 unsorted numbers. Hint: Array[] = 56, 4 , 44, 6, 5, 32, 60, 2 Change the array as you want.
In a sequence, numbers decrease up to a point and then increase. Example: A=[10,9,8,7,6,5,13,14,15] Write an algorithm with O(logn) time complexity that finds the smallest element in such an array. (can be pseudocode.)
Suppose B is a one dimension array with (20) elements. This code sorts B so that its elements are decreasing. For I=1 To 19 1-......... 2-....... D=B(1) B(I)=B(J) B(J)=D 3-....... 4-....... O ***** 1-For J = 1+1 To 20 2-lf B(J) > B( 1 ) Then 3-Endlf 4-Next I, J 1-For J = 1+1 To 20 2-lf B(J) B( 1 ) Then 3- Endlf 4-Next J, I 1-For J = 1+1 To 20 2-lf B(J) > B(1) Then 3-Next J, I 4-End If 1-For J = 1+1 To 20 2-lf B(J) > B(1) Then 3-Endlf 4-Next J, I
What does the following pseudo-code do to the array A[1: n, 1: n], whichis already provided as input to the code?B = 5for i = 1 to n for j = 1 to n temp = A[i,j] – B A[i, j] = A[j, i] A[j, i] = temp + B endend
Given the following algorithm. ALGORITHM BubbleSort(A[0..n – 1]) //Sorts a given array by bubble sort //Input: An array A[0..n - 1] of orderable elements //Output: Array A[0..n-1] sorted in nondecreasing order for i +0 to n– 2 do for j+0 to n – 2 - i do if A[j +1] < A[j] swap A[j]and A[j +1] - a) Demonstrate the steps based on the algorithm above for the following lists: List 1: 3, 7, 8, 9, 10
Write the algorithm which finds the second maximum value of the array. Then find the complexity of the algorithm as Big O notation
Consider the Insertion Sort Function below:public static void insertionSort(int array[]){ int n = array.length; for (int j = 1; j < n; j++) { int key = array[j]; int i = j-1; while ( (i > -1) && ( array [i] > key ) ) { array [i+1] = array [i]; i--; } array[i+1] = key;} }Discuss when is its best case, and worst case performance.
15. Consider the problem of finding the first position in which an array b occurs as a subsequence of an array a. Write two nested loops: let result undefined for (let i = 0; i < a.length - b.length; i++) { for (let j = 0; j < b.length; j++) { if (a[i+j] = b[j]) . . . } } Complete with labeled break and continue statements.
Question # 02: Let’s assume we want to find the largest number in a non-empty array A. A sample solution can be following: def max(A): answer = A[0] for j in range(1,len(A)): // in pseudo-code: for i=1,...,len(A)-1 if (A[j]>answer): answer = A[j] return answer Perform the code correction check including the loop invariance. Question # 03: illustrate the operation of merge sort on the array A = {3; 41; 52; 26; 38; 57; 9; 49}. Question # 04: Answer the following short questions: a) Is 2n+1 = O(2n)? b) Is 22n = O(2n)? c) f(n)=O(g(n)) implies g(n)=O(f(n)) d) f(n) = O((f(n))2)