2023年11月25日

算法设计代写 | Practice Problem Set 3

本次美国代写是算法设计的一个problem set

Problem 1

Provide a recursive algorithm called Range(A,x,y) that takes as input a heap stored in
A, and numbers x and y. The algorithm prints out all numbers from the heap A that are
between x and y inclusively. Determine the recurrence for the runtime of your algorithm
(in the worst-case) and determine the runtime in big-oh notation.

Problem 2

A heap can be built using 4 children for each node in the tree instead of 2. How would
you represent this heap an array? Describe where to find the children and the parent of
node i. How would you update the bubble-down and bubble-up procedures?

Problem 3 (**not possible for student presentation)

We discussed the both bubble-down and bubble-up in class. Write the pseudocode for
bubble-down(i) for index i where the heap is stored in array A. Assume that A.heapsize
refers to the number of elements in the heap. Repeat for bubble-up(i).

Problem 4

Given a max-heap, suppose we would like to output the minimum element. Describe a
recursive algorithm that solves this problem. Write a recurrence for the worst-case run-
time T(n) and determine it’s big-oh notation. Is your recursive algorithm asymptotically
faster than just a brute-force algorithm?

Problem 5 (**not possible for student presentation)

• Array A contains elements that are sorted in decreasing order. Is this a heap?

• In class we saw two algorithms for building a heap. Describe the runtime of each of
these algorithms when the input array is already sorted in decreasing order.

Problem 6

The rst step of the algorithm Randomized-Select algorithm from class is to partition
the elements about a randomly selected element in the array. Write the pseudo-code
for Partition(A,s,f) which partitions the elements of array A about a randomly selected
pivot, and returns the rank of the pivot. You may assume that you have access to a
function that selects a random number is some range, for example Random(a,b) returns
a random integer between the integers a and b inclusively. You may use additional space
during the execution of your algorithm if needed.

Problem 7

Suppose you are given a magic machine that can find the median of any list of n
numbers in constant time. Assume the magic function is called Median(A,s,f) and that
it returns the index of the median element in the array A between indices s and f.

Describe how you can make use of this function to write a recursive algorithm that finds
the kth largest element in the list. Is this asymptotically better than the Select algorithm
from class?

Problem 8

Suppose we would like an algorithm that takes as input an array of n numbers (where
n is odd), and outputs the 3 numbers that are closest to the median (and including the
median). For example,

4; 3; 5; 2; 6; 1; 7

has median is 4. The algorithm will output the 3 numbers closest to (and including)
the median, which are f4; 3; 5g. You may make use of the Select algorithm from class.
Justify why the runtime of your algorithm is O(n).