2. Consider the following algorithm. Array A[0..n – 1] contains n integers. Algorithm choose (A) { n = A.last for (i = 0 to n-2) { min = i %3D for (j if (A[j] < A[min]) { min = j } } swap (A, i, min) } } = i+1 to n-1) { a) What does this algorithm compute? Describe the strategy of the algorithm. b) Trace the steps of the algorithm on the following array: 71 59 23 30 | 8 28 c) Use the big-Oh notation to express its computational complexity.

2. Consider the following algorithm. Array A[0..n – 1] contains n integers. Algorithm choose (A) { n = A.last for (i = 0 to n-2) { min = i %3D for (j if (A[j] < A[min]) { min = j } } swap (A, i, min) } } = i+1 to n-1) { a) What does this algorithm compute? Describe the strategy of the algorithm. b) Trace the steps of the algorithm on the following array: 71 59 23 30 | 8 28 c) Use the big-Oh notation to express its computational complexity.

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

Consider the following pseudocode below (where A is an array of size N). Identify and explain any problem(s) in the logic of the pseudocode. Fix the problem by re-writing the pseudocode correctly. for i <- 0 to N { If (A[i] > A[i+1]) { Swap (A[i], A [i+1]) } }
analyze the time complexity and space complexity of the following algorithm
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
Determine which properties of algorithms the following algorithms lack (there may be more than one property, but you only have to find one). A. procedure sum (n: integer) { for i =: 1 to n do sum =: sum + 1 return sum } B. procedure increment ( ) { for i =: 1 to n do ai =: ai + 1 return a } C. procedure decrement (a: array of integers) { for i =: 1 to n do ai =: ai − 1 } D. procedure divide (n: integer > 1 ) { i =: 1 while n > 0 do n =: n − 1/i i =: 2 * 1 return n }
Consider the algorithm given below. ALGORITHM MinDistance(A[0..n − 1]) //Input: Array A[0..n − 1] of numbers //Output: Minimum distance between two of its elements dmin←∞ for i ←0 to n − 1 do for j ←0 to n − 1 do if i != j and |A[i]− A[j ]| < dmin dmin ←|A[i]− A[j ]| return dminif n = 20, and the list is sorted in descending order, then the loop " or i ←0 to n − 1 do " will be executed ______ times.
Let A be an array of size n storing positive integers. Write an algorithm(pseudo code) that takes array A and replaced each unique element of A by-1. For example, if A=(5,20,41,5,35,6,6) then after you run the algorithm, A=(5,-1,-1,5,-1,6,6). Compute time complexity of your algorithm.
The algorithm below searches for the maximum in an input array A. Assume A is a random sequence containing n distinguishable real numbers, what is the probability for line #4 to be executed exactly once? (The phrase "random sequence" here means the n numbers can appear in any order with equal chance.) mymax(A, n) { 1: max = A[1]; 2: for i = 2:n 3: if A[i] > max 4: max = A[i); 5: end; 6: end; 7: return max; }
Can someone help me with this algorithm? No coding needed
Given an unsorted array of integers, write a function in Python to find the length of the longest increasing subsequence (LIS) in the array. For example, given the array [10, 9, 2, 5, 3, 7, 101, 18], the LIS is [2, 3, 7, 101], which has a length of 4. Your solution should have a time complexity of O(n log n), where n is the length of the input array. Here's some code to get you started: def longest increasing_subsequence(arr): # TODO: implement function pass # example usage arr = [10, 9, 2, 5, 3, 7, 101, 18] print(longest_increasing_subsequence(arr)) # should print 4
Let M(n) be the minimum number of comparisons needed to sort an array A with exactly n ele- ments. For example, M(1) = 0, M(2) = 1, and M(4) = 4. If n is an even number, clearly explain why M(n) = 2M(n/2) + n/2.
What is the time complexity of the following algorithm? function findLargest(array): largest = array[0] for i = 1 to array.length: if array[i] > largest: largest = array[i] return largest Assume that array.length is n, and that all other operations take constant time. Express your answer in big O notation.