You can access the SID$\_$NameSurname.rar file for the Lab Exam from the attachment. Your exam duration is $90$ minutes.

The content of the file includes the question paper and a file that you will use for each question. $($such as Q$1.$cpp$,$ Q$2.$cpp and Q$3.$h$).$ If there is a template you need to use in addition to these, you can use it from the lab documents. If you have an explanation about any question, you can write it in the form of comment lines at the bottom of the relevant question document.

When sharing the file back, re$-$rar and send it in the appropriate format, including your own student number and name and surname $($SID$\_$NameSurname$).$

You only need to solve $2$ questions. Scoring will vary depending on the questions selected. Scoring is available at the top of the exam paper. #include

#include

#include

#include

#define N $10$

#define M $10$

using namespace std;

$//$ Function to create a sorted matrix.

$//$ You don't need to modify or understand this $($just don't waste time$)$

std::vector$$ vector $>$ createSortedMatrix$()$

$\{$

std::vector$$ vector $>$ matrix$($N$)$;

std::vector row$($M$)$;

int i$,$j$,$n;

srand$($time$($NULL$))$;

for $($i$=0$;i $>$ m$)$

$\{$

for $($int i$=0$;i $($write your answer HERE!$)$

$*/$

bool searchNum$($vector$$ vector $>$ m$,$ int e$)$

$\{$

$//*********$

$//$ Write your solution here for Question $1.$

$//*********$

$\}$

$//$ You don't need to change the main function.

int main$()$

$\{$

std::vector$$ vector $>$ matrix$($N$)$;

int e;

matrix $=$ createSortedMatrix$()$;

printSortedMatrix$($matrix$)$;

std::cout $$ "Element to search for : $"$;

std:cin $>>$ e;

bool result $=$ searchNum$($matrix$,$e$)$;

if $($result$)$

cout $$ e is found in the matrix!";

else

cout $$ e is NOT found";

return $0$;

$\}$Q$1)$ Sorted Matrix $($definition$)$: in a sorted matrix of size $NxM,$ elements in each row is

sorted in ascending order and the first number of each row is greater than the last

number of the previous row.

You are required to implement an efficient algorithm to search a given number, $k,$ in

a sorted matrix. We already know that the common method of searching for an

element in a matrix involves scanning the entire matrix, and thus, this approach has

a time complexity of $O(NM).$ The algorithm you will develop should offer a better

solution than this $($Do NOT code the classical matrix search algorithm$).$

$($Hint: think about the well$-$known efficient method for searching an item in a sorted

array. Using this algorithm, you should first locate the correct row; then look for the

element in that row of the sorted matrix$).$

You are given the empty function body and a driver program $($Q$1.$cpp$),$ which a

sample sorted matrix $($of type vector $$ vector $$ int $>>)$ is already created and printed

for you.

a$)$ Implement your proposed search algorithm within the body of the given function.

b$)$ Analyze your code and determine time complexity with respect to $N$ and $M($write

your answer right above the function$)$