Given an 8-element array: A = {x1, x2, X3, X4, X5, X6, 27, x8}, we would like to find its 3rd smallest element. It is known that x₁ and xs are the two extreme elements: max and min, but we do not know which one is the max and which one is the min. It is also known that x4 and 5 are the two medians: left-median and right-median. What is the minimum number of comparisons you need to find the 3rd smallest element of the original array?

Given an 8-element array: A = {x1, x2, X3, X4, X5, X6, 27, x8}, we would like to find its 3rd smallest element. It is known that x₁ and xs are the two extreme elements: max and min, but we do not know which one is the max and which one is the min. It is also known that x4 and 5 are the two medians: left-median and right-median. What is the minimum number of comparisons you need to find the 3rd smallest element of the original array?

Programming Logic & Design Comprehensive

9th Edition

ISBN:9781337669405

Author:FARRELL

Publisher:FARRELL

Chapter6: Arrays

Section: Chapter Questions

Problem 17RQ

See similar textbooks

Similar questions

You are given an array A[1 : n] which includes the scores of n players in a game. You are additionally given an array B[1 : m] with the score of m new players. Design and analyze an algorithm that given both arrays A and B, can find the rank of each player B inside the array A, i.e., for each B[i], determines what would be the rank of B[i] in the array consisting of all elements of A plus B[i]. Your algorithm should run in O((n + m) ·log n) time.
You are given an array J[1 : n] which includes the scores of n players in a game. You are additionally given an array P[1 : m] with the score of m new players. Design and analyze an algorithm that given both arrays J and P, can find the rank of each player P inside the array J, i.e., for each P[i], determines what would be the rank of P[i] in the array consisting of all elements of J plus P[i]. Your algorithm should run in O((n + m) ·log n) time.
A minimax or saddle point in a two-dimensional array is an element that is the minimum of its row and the maximum of its column, or vice verse. For example, in the following array11 22 33 33 99 55 66 77 77 44 99 22the element 33 is a minimax because it is the maximum of row 0 and the minimum of column 2. The element 55 is another minimax because it is the minimum of row 1 and the maximum of column 1.Write a program that reads a 4-by-3 matrix, and then prints the location and value of each minimax in the matrix. For example, it would printa[0][2] = 33 is a minimax a[1][1] = 55 is a minimaxfor the matrix shown above.
This question requires C++ and Edipse or Replit IDE works. PART ONE======- Write a program that stores these values into a 2-Darray Rows represent months, and columns represent sales regions. The cells represent sales figures: 6545 6420 6541 4568 9280 9874 1258 6000 3214 8452 5050 7412 3650 8544 8523 2140 5222 9632 3250 9512 1478 3659 4500 2589 4521 3200 3698 6900 3205 8451 2630 4722 9362 5024 8744 3568 Then proces this 2-D array and outout thetofalannua sale by months e sum the rows) Yor outout should resemble
The number of poles lying on right side of S-Plane for the following R-H array are= S5 1 b a S4 -3 f S3 -12 s? 6 f so -4 4 3. 2.
A unimodal array is an array that has a sequence of monotonically increasing integers followed by a sequence of monotonically decreasing integers, assuming all elements in the array are unique. Example: |- A= {4, 5, 8, 9, 10, 11, 7, 3, 2, 1}: A is a unimodal array because there is an increasing sequence followed by a decreasing sequence and the maximum element is 11. B= {11, 9, 8, 7, 5, 4, 3, 2, 1}: B is not a unimodal array because there is no increasing sequence It is simply a decreasing sequence and the maximum element is 11. C= {1, 2, 3, 4, 5, 7, 8, 9, 11: C is not a unimodal array because There is an increasing sequence, but there is no decreasing sequence and the maximum element is 11. a) Design an efficient algorithm with the lowest possible complexity to state whether a given array is unimodal or not, and explain why your algorithm is efficient. b) Analyze the complexity of your algorithm.
Suppose an array A contains 8 elements as follows: 77,33,X,11,88,Y,6, 15 Where: element X = last two digits of your roll number (e.g., if your roll number is 19106018, then X is 18; if your roll number is 19106001, then X is 1) element Y = last two digits of the number obtained by squaring X (c.g., squarc of X = 18 is 324,50 Y is 24; squarc of X =1 is I,s0 Y is 1). Write an algorithm for insertion sort and step by step ap algorithm on the above example array A.
This code segment determine an average of even elements of Array T(50). s=0:c=0 For I = 1 To 50 1-..... 2-..... 3-........ 4-... 5-..... 6-........ 1-If T(1) mod 2=0 then 2-s = s + T(1) 3- c=c+1 4-A = s/ 50 5-End if 6-Next 1-If T(1) mod 2=0 then 2-s = s + T(1) 3- c=c+1 4-Next 5-End if 6-A = S/C 1-If T(1) mod 2=0 then 2-s = s + T(1) 3- c=c+1 4-End if 5-Next 6-A = s / 50 1-If T(1) mod 2=0 then 2-s = s + T(1) 3- c=c+1 4-End if 5-Next 6-A = s/c III
You have been given an array A of size N and an integer K. This array consists of N integers ranging from 1 to 10^7. Each element in this array is said to have a Special Weight. The special weight of an element a[i] is a[i]%K. You now need to sort this array in Non-Increasing order of the weight of each element, i.e the element with the highest weight should appear first, then the element with the second highest weight and so on. In case two elements have the same weight, the one with the lower value should appear in the output first. Input Format: The first line consists of two space separated integers N and K. The next line consists of N space separated integers denoting the elements of array A. Output Format: Print N space separated integers denoting the elements of the array in the order in which they are required. Constraints: 1≤N≤10^5 1≤A[i]≤10^7 1≤K≤10^7 Note: You need to print the value of each element and not their weight. SAMPLE INPUT 5 21 2 3 4 5 SAMPLE OUTPUT 1 3 5 2 4…
Given an array of integers, print a sum triangle from it such that the first level has all array elements. From then, at each level number of elements is one less than the previous level and elements at the level is be the Sum of consecutive two elements in the previous level. Input The single line of input contains an array of integers, each of it is separated by space Output Triangle form that has been created from the input array Sample Input1 12345 Sample Output1 48 20 28 8 12 16 3579 12345
Using r create a 4×3×4 array where for each of the 3 students, a 4×3 matrix holds their six scores and six averages (i.e., two averages by scores, three averages by subject, and the grand average). The last (i.e., 21st) matrix should hold the elementwise averages of the previous 20 matrices. Do not use a loop. Ini A1 A2 B1 B2 C1 C2 RE 81.9 75.1 78.3 69.2 79.6 74.4 ON 82.7 72.6 85.3 78.9 78.3 75.7 KS 83.8 63.4 73.4 73.5 80.4 66.2 Ini is the student's initials, A1 is subject 1 first, A2 is subject 1 second, etc.
To check if COVID Social Distancing is applied or not in a classroom, a 2-D array of characters can be used to represent seating in a classroom as in the following example table. The valne "X in an element of the classroom array means that the seat is not occupied and any other value in an array element means that the seat is occupied. +For example consider the following seating table A X H X X I X e K b X X J X E in the above tahle the element that violate the social distancing rule are H,n,q, I, e, K, E Write a C function named covid sd that checks if COVID Social Distancing is applied or not in a classroom. Your function must o accept exactly three parameters named: classroom, num rows, and Ist. The classroom parameter is a 2-D array of characters with 6 columns. This array represents the classroom seating. num rows is the number of rows in the 2D array, Ist is a 1-D array of characters. The size of Ist is 6 * num rows. o store the values of each seat that violates the COVID Social…