$(10$ points$)$

Before you work on this problem, go to the $C++$ Resources page and read the two files:

Arrays vs$.$ Vectors in C$++.$docx

Reminders on reading from a data file.docx

Consider the following problem. You have an array A$[0],$ A$[1],..,$ A$[$n $-1]$ of distinct integers that

has the following property: The values in the array increase up to index p for some $p,0pn-1,$

and then decrease for all indices beyond $p$ through position $n-1.$ You want to find the $p$ index at

which the peak value occurs and what the peak value is$.$

Example: In the $6-$element array illustrated below, the p index is $3,$ and the peak value is $4.$

Describe $[$write an English paragraph, not code$]$ a divide$-$and$-$conquer algorithm that can solve this

problem. $($Hint: the solution is a bit like the binary search algorithm.$)$ Do a formal analysis $($for

which you can assume that $n$ is a power of $2)-$ this means formulate and solve a recurrence relation

to prove that your algorithm does $(lgn)$ work units, where the work unit is comparison of array

values. Turn your algorithm description and analysis in on Canvas as a pdf file $($for the TA$).$

Implement your algorithm in a C$++$ program called peak.cpp$.$ Recall your program will be run on

Visual Studio $2022,$ and you need to test it there before turning it in$.$ If you use Visual Studio to

create your program, be sure that you choose Empty Project. I expect that, on all coding

assignments, you will follow good coding practice $-$ reasonable identifier names, modularization

using functions, clear comments, etc.

Read the input values $($i$.$e$.,$ the array values$)$ as a series of integers, one per line, from a text file

called peak.txt $-$ make up your own file for testing your program. You can assume a maximum

array size of $32.$ Or you can implement using a vector instead of an array.

Turn in only peak.cpp $($not all your project files or data files$)$ via Canvas Assignments.