Homework 04 METU CENG310

Homework 04
METU CENG310
Data Structures and Algorithms with Python

1 Finding the Peak
Task-1: In this exercise, you are expected to develop a pseudo code1
that uses recursion for the problem
described below, and determine the complexity of your algorithm. Your algorithm has to be efficient, solutions
with growth rate function other than O(nlogn) will not be accepted.
Suppose you are given a sequence (i.e., array) of size n with each entry holding a distinct number. For some
index value p between 0 and n − 1, the values in the array entries increase up to position p and then decrease
on the remainder of the way until position n − 1.
An example of such array would be [12,17,38,54,55,69,68,44,39,19,14,7] where p and n could be 5 and 12,
respectively.
Develop an algorithm to find the peak entry p without having to read the entire array. The algorithm should
read as few entries of the array as possible. Also note that p could be 0 or n − 1, so your algorithm should be
able to handle these corner cases as well.
Hint: There will two slopes (trends) of the array values: An increasing one followed by another decreasing
one. Each of these trends can be considered as monotonically increasing or decreasing functions. So when we
pick up value in the array, we can easily understand on which trend that value resides by checking whether
the previous and next values are larger or smaller than the picked-up value. Depending on which trend the
picked-up value is on, the direction of the search can be determined: Left or right half of the search input. The
base condition would be met when both previous and next items on the array are smaller than the picked-up
value (i.e., when we picked up the peak value.)
2 Instructions
Pertaining to the answers of this homework, correct typing of superscripts (e.g., n
2
) and subscripts (e.g., n0)
matters. Due to this reason, this homework may be done on paper and returned as a PDF file containing
the answer sheet captures (photos, scanned files). If you would like you can use MS Word or Latex, but your
deliverable has to be a single PDF file. PDF file should be created so that the answers appears in the same
order as the questions shown in the homework assignment document.
A Homework-04 page will be generated soon after the start date of this homework. All deliveries should
be done over METUClass. Please also be aware of the late penalties (Please check the Announcements –
Homework and Assignment Policy in METUClass if you have not already done so.). Should you have any
questions pertaining to homework tasks, please ask them in advance (not on the due date) for your own
convenience.
If the questions that are marked as Bonus are answered, they are accounted as additional score to your
homework grading. So that, by answering these questions, taken into account that all other questions are
answered correctly, you can get scores higher than full score. No matter how much bonus score you get
throughout the semester, the total grade point that you will get from homework assignments cannot exceed
15% of your total grade (please recall that homework assignments comprise 15% of your total grade).
1https://users.csc.calpoly.edu/~jdalbey/SWE/pdl_std.html
1