Question

Give pseudocode for a Theta(n)-time algorithm that returns the 50 largest values in an array. You may assume the array has at least 50 values.

Answer #1

**/*If you have any query do comment in the comment
section else like the solution*/**

**Pseudo Code:**

function FiftyLargest(arr, size) {

PriorityQueue pq = createMaxHeap(arr, size);

for i = 0 to 49

print(pq.top())

pq.pop()

}

function createMaxHeap(arr, n) {

PriorityQueue pq

for i = 0 to n

pq.add(arr[i])

return pq;

}

Time taken to create maxHeap = O(n) //where n is size of array

Time taken to pick 50 largest element = O(k log n) // where is k is 50

Overall time complexity = O(n + klogn)

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...

Give pseudocode for a memoized algorithm that computes n
factorial. You will want to think about the implementation of an
appropriate data structure as well as a sentinel value for this
problem.
Note: a memoized factorial algorithm is not
considered dynamic programming, as factorial does not encounter
repeated subproblems while recursing. However, memoizing this
algorithm is the same process as memoizing a dynamic programming
algorithm.

2. Design a deterministic algorithm to solve the following
problem.
input: An array A[1...n] of n integers.
output: Two different indices i and j such that
A[i] = A[j], if such indices exist.
Otherwise, return NONE.
Your algorithm must take O(n log(n)) time. You must describe your
algorithm in plain English (no pseudocode) and you must explain why
the running time of your algorithm is O(n log(n)).

Assume evaluating a function f(n) in the pseudocode below takes
theta(n) time.
i = 1;
sum = 0;
while (i <= n)
do if (f(i) > k)
then sum += f(i);
i = 2*i;
What is the

Given an unsorted integer array A of size n, develop a
python version pseudocode with time complexity as low as possible
to find two indexes i and j such that A[i] + A[j] = 100. Indexes i
and j may or may not be the same value.

Write a function that returns the largest element of an array?
Your function should accept a 1-D array as an input and return the
largest number. You may assume all numbers are integers. CODE IN
C++ PLEASE

Assume that we have a sorted array a[n]with n non-negative
numbers.
a. Develop an algorithm using divide-and-conquer to search for
an element x in this sorted array a[n]. This algorithm will take an
input of a sorted array a[n], and return the index of element x is
an element of a[n], or return -1if xis NOT an element of this
array.
b. Analyze the time complexity of this algorithm.

Given a sorted array A with distinct values which has been
rotated r times to the left. Find r in least possible time. Provide
python source code, time complexity, and pseudocode.
Input: The sorted array ? that has been rotated r times to the
left.
Output: The value and ?.

Write pseudocode for a simple algorithm for addition of two
n-digit numbers (one of
them could be < n digits with 0's appended to the
left) in base-10, as follows. Assume
the digits are stored in arrays A and B, with A[1] and B[1] being
the rightmost digits and
A[n] and B[n] being the leftmost digits. Use a for loop to go from
right to left adding the
digits and keeping track of the carry. Now, here's the real
task:...

In this programming exercise you will create an algorithm for
solving the following version of the m Smallest Numbers
problem. Instead of just returning the m
smallest values as in homework 1, you want to return a list of the
positions where the m smallest values are located
without changing the original array.
Your algorithm should meet the following specifications:
mSmallest( L[1..n], m )
Pre: L is a list of distinct integer values. n is the
number of elements in...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 6 minutes ago

asked 8 minutes ago

asked 8 minutes ago

asked 23 minutes ago

asked 23 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago