Question

2.) Consider an input array A of size n in which n − 1 of the
elements have identical values and the remaining one value is
smaller than the n − 1 identical values. What is the running time
of Heapsort with input A?

Answer #1

**2)** The running time of Heapsort with input A
will be **O(n log n).**

Heap sort requires two steps. One is creating the tree and the other one is heapify process. As we already know that, apart from one element other elements are identical to each other. So, the heapification process will run for that element and the complexity will be O(n log n). If all the elements in the array were identical then it will take O(n) times as no heapification will be required. In that case only traversing the tree will be required which will take O(n) time. But, since one element is smaller than all other equal elements, so we will require the heapification. So, it will take O(n log n) time.

**Please comment in case of any doubt.
Please upvote if this helps.**

1) Develop a C++ function that determines the
average value of an array of type double elements
double GetAverage(double array[], int
size)
The function should accept as input an array of double
values
The function should accept as input the number of elements in
the array of double values
The function should return a double value which is the array's
average value
2) Develop a C++ function that determines the
variance of an array of type double elements
double GetVariance(double...

Find the worst-case complexity of the algorithm below. Show your
work.
UFSizeCalc
Input: uf: Union-Find array
of size n
Input: n: size of uf
Output: size array for uf; that is, an
array s such that s[r] equals the number of
elements in the Union-Find tree rooted at r, for every
root r (s may have any value for indexes that are
not roots of uf)
Pseudocode:
For i = 1 to n
uf.Find(i)
size = Array(n)
Initialize size to be...

1. Given an
n-element array A, Algorithm X executes an
O(n)-time computation for each even
number in A and an O(log n)-time computation for
each odd number in A.
What is the best-case running time of Algorithm X?
What is the worst-case running time of Algorithm X?
2. Given an array,
A, of n integers, give an O(n)-time algorithm that finds
the longest subarray of A such that all the numbers in that
subarray are in sorted order. Your algorithm...

C++ program for :
1. Given an array of real numbers and the dimension n (n is
entered from the keyboard). B form an array, each element bi -
arithmetic mean of the array elements and excluding ai.
2. Given an array of integers dimension n. Change the array so that
all the elements of the module which is not equal to the maximum
element of the array, replaced by zero, and equal - unit.
3. Given an array of...

We are given an array A of size n containing n positive and
negative integers (the array is indexed starting from 0).
Our goal is to find two indices i and j such that 0 ≤ i ≤ j ≤ n
and Pk=j k=i A[k] is maximized.
Input sequence: [2, -4, 1, 9, -6, 7, -3]
Output: [1, 9, -6, 7] or i = 2 and j = 5
Input sequence: [1, 2, 3, 4, 5, 6, -3]
Output: [1,...

Consider the following recursive algorithm. Algorithm Test
(T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n =
1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1]
return temp else return T[n − 1] a. What does this algorithm
compute? b. Set up a recurrence relation for the algorithm’s basic
operation count and solve it.

Develop a program that will sort the elements of a single
dimension array. Program Requirements:
1. Declare a single dimension array of size n
2. Input n elements to a single dimension array
3. Sort the elements of an array from highest to lowest and vice
versa
Also, the program will identify and output the highest and
lowest integer.

For questions 1 and 2 declare the array size as name
constant first then use it to declare the array
1. Declare an array named
scores of type double and size
30.
2. Declare an array named
names of string objects and size
15
3. Given the following array definition:
int values[] = {2, 5, 8, 11};
What does each of the following
display?
cout <<
values[1];
B) cout <<
value[3]+values[0];
Define a three element array named letters,
initialize it...

Consider the C code below which reverses the elements in the
array A in place. Both array indexing and pointer versions are
given. Assume that A holds doubleword integers and that size is the
number of elements in the array. Translate to RISC-V using as few
instructions as possible. For your RISC-V code, assume the base
address of A is initially in x10 and that the number of elements in
the array (i.e., size) is initially in x11.
long long...

In heapsort we view an array as a binary tree using the
following mapping: a[0] is the root of the entire tree and for
element a[i], its left child is a[2i+1] and its right child is
a[2i+2]. Answer the following questions for an array of size n. (
Answers in some cases may be in terms of n.)
a) What is the index of the parent a[i] for any i > 0?
b) What is the biggest index for which...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 58 seconds ago

asked 7 minutes ago

asked 44 minutes ago

asked 44 minutes ago

asked 58 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago

asked 3 hours ago