You are given an mxn grid, in which each entry stores a positive integer. All numbers...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
You are given an mxn grid, in which each entry stores a positive integer. All numbers are distinct. Your task is to find one entry which is larger than all its neighbors. (The neighbors of entry [i, j] are [i - 1, j], [i+1,j], [i, j-1], and [i, j+1]; note that an entry in a corner has 2 neighbors, and an entry on an edge (but not corner) has 3 neighbors.) 1. Suppose that m = 1. Design an algorithm for this task. Your algorithm should run in O(logn) time. (Note that in this case each of two boundary entries has 1 neighbors, while each of the other entries has 2 neighbors.) Prove that your algorithm is correct. 2. Suppose that m=n. Design an algorithm for this task. Your algorithm should run in O(n) time. You are given an mxn grid, in which each entry stores a positive integer. All numbers are distinct. Your task is to find one entry which is larger than all its neighbors. (The neighbors of entry [i, j] are [i - 1, j], [i+1,j], [i, j-1], and [i, j+1]; note that an entry in a corner has 2 neighbors, and an entry on an edge (but not corner) has 3 neighbors.) 1. Suppose that m = 1. Design an algorithm for this task. Your algorithm should run in O(logn) time. (Note that in this case each of two boundary entries has 1 neighbors, while each of the other entries has 2 neighbors.) Prove that your algorithm is correct. 2. Suppose that m=n. Design an algorithm for this task. Your algorithm should run in O(n) time.
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 programming questions
-
In this question assume that p and q are atomic formulae. (a) Compare and contrast path formulae and state formulae in temporal logic. [4 marks] (b) Describe and contrast the meanings of F(G p) and...
-
Developments in Technology Light is incident from air on the end face of a multimode optical fibre at angle of incidence as shown below. n n 1 2 The refractive indices of the core and cladding are...
-
(c) It is known that although variance is a widely used measure of investment risk, variance does not satisfy the concept of subadditivity. This means that a risk measure should reflect the fact that...
-
Refer to Multiple-Concept Example 7 for insight into this problem. During a tennis serve, a racket is given an angular acceleration of magnitude 160 rad/s2. At the top of the serve, the racket has an...
-
Finx, Inc., purchased a truck for $40,000. The truck is expected to be driven 15,000 miles per year over a 5-year period and then sold for approximately $5,000. Determine depreciation for the first...
-
How are internal auditing and independent auditing related?
-
The post-closing trial balance of Violet Corporation at December 31, 2012, contains the following stockholders equity accounts. Preferred Stock (15,000 shares issued)........... $ 750,000 Common...
-
An air-gap parallel plate capacitor of capacitance Co = 20 nF is connected to a battery with voltage V = 12 V. While the capacitor remains connected to the battery, we insert a dielectric (K = 2.6)...
-
The profit as per cost accounts is 1,15,000 the following points are found out on comparison between cost accounts and financial accounts. Particulars a) Opening stock: Materials Work-in-progress...
-
The finance manager of a fastfood restaurant is presented with an opportunity for opening a new location. The company has recently paid a consultant $50,000 for a demographic study about this new...
-
La Fiesta Restaurants issued bonds that have a 6 percent coupon interest rate. Interest is paid annually. The bonds mature in 12 years. If your required rate of return is 8 percent, what is the value...
-
Assume that the expected market return is 12% and volatility is 20%. Assume that the CAPM accurately describes the data we are using. the correlation between IBM and the market is 0.90% and the...
-
What is the yield to maturity on a 6% bond that is currently trading for $1100 and matures in 10 years?
-
What is the current price of a bond that has 8 years until maturity? The face value of the bond is $10,000 and has a coupon rate of 8.61% compounded semi-annually and a yield rate of 8.6% compounded...
-
MedStar Health is expanding into Virginia. The firm must select one location where it can build a clinic to serve patients. The following table lists the expected profits for clinics in three...
-
An environmentalist wants to determine if the median amount of potassium (mg/L) in rainwater in Lincoln County, Nebraska, is different from that in the rainwater in Clarendon County, South Carolina....
-
Professor Gompers suspects that it might be possible to keep just one pointer in each set object, rather than two (head and tail), while keeping the number of pointers in each list element at two....
-
We can define the distance between two points in ways other than euclidean. In the plane, the L m -distance between points p 1 and p 2 is given by the expression (|x 1 x 2 | m + |y 1 y 2 | m ) 1/m...
-
Suppose that in the rod-cutting problem of Section 15.1, we also had limit l i on the number of pieces of length i that we are allowed to produce, for i = 1, 2, . . . ,n. Show that the...
-
Given forecast errors of 3, 2, -2, and 9, what is the tracking signal?
-
Given forecast errors of 10, -2, 25, and 0 when actual values were 120, 145, 275, and 124, what is the mean absolute percent error?
-
Given an actual demand of 34 this period, a predicted value of 45 this period, and an alpha of 0.2, what would be the simple exponential smoothing forecast for the next period?
Study smarter with the SolutionInn App