Show how to find the entry p by reading at most o entries

Assignment Help Computer Engineering

Reference no: EM132206608

WRITE-UP ONLY, NO NEED FOR A CODE!!

Suppose you are given an array A with n entries, with each entry holding a distinct number.

You are told that the sequence of values A[1], A[2], . . . , A[n] is unimodal, that is - For some index p between 1 and n, the values in the array entries increase up to position p in A and then decrease the remainder of the way until position n.

(So if you were to draw a plot with the array position j on the x-axis and the value of the entry A[j] on the y-axis, the plotted points would rise until x-value p, where they'd achieve their maximum, and then fall from there on.)

You'd like to find the "peak entry" p without having to read the entire array-in fact, by reading as few entries of A as possible.

Show how to find the entry p by reading at most O(log n) entries of A.

Describe this in your README. Prove that your algorithm works in O(logn). No need to provide code.

Reference no: EM132206608

Questions Cloud

Informal communication has little impact on the organization : Informal communication has little impact on the organization. The grapevine is a type of chain communication.

Discuss the validity of the statement : In order to succeed in today's globalized world a multinational business needs to "think global & act local". Discuss the validity of the above statement.

What is the role of a constructor : Write the necessary code including: import statement, instantiation, and other needed statements to read an integer value from the keyboard.

The era of expertise was largely concerned with : The era of expertise was largely concerned with __________. Almost always included as important leadership traits are

Show how to find the entry p by reading at most o entries : You'd like to find the "peak entry" p without having to read the entire array-in fact, by reading as few entries of A as possible.

How much will be paid out each year to the winners : Prof. Gilkinson has pledged a scholarship program called the ˜Lowest GPA Award' for WVU-Tech that will pay a fixed amount starting at the end of 11th year.

How to present and speak about the brand : Brand voice management: it is a written document that outlines the name, logo, visual style of the brand and communicates concise parameters.

Write a pep machine language instruction : Write a Pep/7 machine language instruction that puts the value 1111111100000001 into the A register.

Describe checkpoint firewall and its features : Write a paragraph that describe checkpoint firewall and its features.

User Account

All Pages