Given a non-negative integer array A[1..n] (that is, A contains numbers from the set {0, 1,...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Given a non-negative integer array A[1..n] (that is, A contains numbers from the set {0, 1, 2, 3, 4, ...}), the next smaller value of A (NSVA) is an integer array of length n, where NSVA[i], 1 ≤ i ≤n, is defined as follows: 1. if A[i]=0 then NSVA[i] = 0 2. otherwise, NSVA[i] = j, where (a) for every h E [1..j-1], A[i] ≤ A[i+h], and (b) either i + j= n+1 or A[i] > A[i + j]. In short, NSV[i] shows how far one should trace forward from A[i] to reach a smaller value than A[i]. Write an algorithm to compute the NSV array in O(n) time, using the stack data structure. Below is an example of an NSV array. [6 marks] i A 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 01 3 3 7 7 15 5 0 NSVA 0 8 4 3 2 1 3 2 1 0 2 2 6 6 0 4 4 4 3 2 1 0 2 1 Given a non-negative integer array A[1..n] (that is, A contains numbers from the set {0, 1, 2, 3, 4, ...}), the next smaller value of A (NSVA) is an integer array of length n, where NSVA[i], 1 ≤ i ≤n, is defined as follows: 1. if A[i]=0 then NSVA[i] = 0 2. otherwise, NSVA[i] = j, where (a) for every h E [1..j-1], A[i] ≤ A[i+h], and (b) either i + j= n+1 or A[i] > A[i + j]. In short, NSV[i] shows how far one should trace forward from A[i] to reach a smaller value than A[i]. Write an algorithm to compute the NSV array in O(n) time, using the stack data structure. Below is an example of an NSV array. [6 marks] i A 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 01 3 3 7 7 15 5 0 NSVA 0 8 4 3 2 1 3 2 1 0 2 2 6 6 0 4 4 4 3 2 1 0 2 1
Expert Answer:
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these computer network questions
-
The Janobi Company has three product lines of beer mugs-A, B, and C-with contribution margins of $5, $4, and $2, respectively. The president foresees sales of 231,000 units in the coming period,...
-
List three specific parts of the Case Guide, Objectives and Strategy Section (See below) that you had the most difficulty understanding. Describe your current understanding of these parts. Provide...
-
A compare-exchange operation on two array elements A[i] and A[j], where i < j, has the form COMPARE-EXCHANGE (A, i, j) 1 If A[i] > A[j] 2 exchange A[i] with A[j] After the compare-exchange operation,...
-
QUESTION ONE Matrix X sells computer hardware and software components as well as other ancillary items to customers all over South Africa. Matrix X also provides installation of hardware and software...
-
What two things can be done to increase the amount of flow in a water pipe? Similarly, what two things can be done to increase the current in an electric circuit?
-
Presented next are the balance sheet accounts of Bergen Corporation as of December 31, 2017 and 2016. Additional Information: On January 2, 2017, Bergen sold all of its marketable investment...
-
Fleetwood Homebuilders issued S200,000 of \(6 \%, 10\)-year bonds at par on August 31. Fleetwood pars semiannual interest on February 28 and August 31. Journalize for Fleetwood: a. Issuance of the...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
The company currently has outstanding a bond with a 5.5 percent coupon rate and another bond with a 3.5 percent coupon rate. The firm has been informed by its investment banker that bonds of equal...
-
GRANT MANAGEMENT CONSULTANTS Comparative Balance Sheets January 1 and December 31, 2014 Jan. 1 Dec. 31 20,000 55,000 40,000 37,000 60,000 92,000 30,000 32,000 20,000 20,000 10,000 40,000 60,000...
-
Wendy, a 4-year-old girl, decides to gift her father a teddy bear on his birthday, because Wendy likes teddy bears. She asks her elder brother to help her wrap the gift. She does not consider the...
-
Explain how a change in interest rates in the economy would be expected to affect each component of the weighted average cost of capital.
-
List the five possible procedures for dealing with real options.
-
Briefly describe the tax depreciation system under MACRS.
-
How widely used is real option analysis?
-
Explain how growth options are like call options.
-
Identify all the expenses above as being either Fixed or Variable. For expenses labeled Shipping, Amortization and Electricity, explain why you chose either fixed or variable. Using your cost...
-
State whether each statement is true or false. If false, give a reason. {purple, green, yellow} = {green, pink, yellow}
-
Define lcm (a 1 , a 2 , . . . ,a n ) to be the least common multiple of the n integers a 1 , a 2 , . . . ,a n , that is, the smallest nonnegative integer that is a multiple of each a i . Show how to...
-
How would you modify Strassens algorithm to multiply n n matrices in which n is not an exact power of 2? Show that the resulting algorithm runs in time (n lg 7 ).
-
A probability distribution function P(x) for a random variable X is defined by P(x) = Pr {X x}. Suppose that we draw a list of n random variables X 1 , X 2 , . . . ,X n from a continuous probability...
-
A pipe branches symmetrically into two legs of length \(L\), and the whole system rotates with angular speed \(\omega\) around its axis of symmetry. Each branch is inclined at angle \(\alpha\) to the...
-
For the rotating sprinkler of Example 4.13, what value of \(\alpha\) will produce the maximum rotational speed? What angle will provide the maximum area of coverage by the spray? Draw a velocity...
-
Compressed air is stored in a pressure bottle with a volume of \(100 \mathrm{~L}\), at \(500 \mathrm{kPa}\) absolute and \(20^{\circ} \mathrm{C}\). At a certain instant, a valve is opened and mass...
Study smarter with the SolutionInn App