Question
Suppose you are given a matrix (a 2-dimensional array) A[1..m][1..n] of numbers. An element A[i][ j] is called good if each of its neighbors A[i1][
Suppose you are given a matrix (a 2-dimensional array) A[1..m][1..n] of numbers. An element A[i][ j] is called good if each of its neighbors A[i1][ j], A[i+1][ j], A[i][ j1], and A[i][ j + 1] are at most A[i][ j]. For simplicity, assume elements beyond the boundaries of A are equal to . In other words, A[0][] = A[n + 1][] = A[][0] = A[][n + 1] = .
(a) Suppose m = 1 so we only have the array A[1][1..n]. Design and analyze in psuedocode with a proof an algorithm to find a good element of A in O(log n) time.
(b) Now suppose m = n. Design and analyze (with psuedocode and proof) an algorithm to find a good element of A in O(n log n) time. Hint: Suppose you know the maximum element of a column A[][ j], but it is not itself good. What can you say about the maximum elements of neighboring columns?
(c) Extra credit: Design and analyze an algorithm to find a good element of A in O(n) time.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started