$1.$ Prove that if f: X $->$ Y and g:Y $->$ Z are $1-1$ functions then g$$f : X $->$ Z is also $1-1.$

$2.$ Give an example of a function that is:

$($a$)1-1,$ not onto $($include domain and codomain$)$

$($b$)1-1$ and onto $($ include domain and codomain$)$

$($c$)$ Neither $1-1$ nor onto $($ include domain and codomain$)$

$($d$)$ Has asymptotic complexity more that n but less than n$2$

$3.$ A population has exponential growth; t years from now its population will be y $=5000$ e$0\mathrm{.}02$t$.$

$($a$)$ When will the population reach $6000?($show work$)$

$($b$)$ How long does it take the population to double $?($show work$)$

$4.$ Write pseudocode for a program that will take an unordered list of distinct integers A$(1)-$

A$($n$),$ and output a new list B$(1)-$B$($n$)$ such that;

B$(1)$ is the largest number in list A$,$ B$(2)$ is the smallest number in A

B$(3)$ is the second largest number in A$,$ B$(4)$ is the second smallest number in A

B$(5)$ is the third largest, etc.

$5.$ The following gives pseudocode for a $$binary search$.$ We have a list of n integers A$(1)-$A$($n$),$

in order starting with the lowest. We are given a value $$x$$ to search for in the list. If $$x$$ is in

the list, we Return its position. If $$x$$ is not in the list, Return $-1.$ You may assume n is even,

and start by giving out Bubblesort code from class to order the numbers first, if you wish.

$($a$)$ Trace the program using n$=7,$ A value $1,3,4,7,8,10,12,$ and x$-$value $10.$ Give me the

values of low, hi and mid each time the mid value is calculated $($by mid:$=($low$+$hi$)/2),$

and give the final output Returned.

$($b$)$ Same as $($a$),$ but now use x$-$value $2.$

Program Binary Search

Input: positive integer n$,$ list of n integers A$(1)$ A$($n$),$ number x

Output: location of x if it is in the list, otherwise $-1.$

hi:$=$ n

low :$=1$

while hi $>=$ low do

mid:$=|\_($low$+$hi$)/2\_|$

if A$($mid$)=$ x$,$ Return mid

else if A$($mid$)<$ x$,$ low:$=$ mid$+1$

else hi:$=$ mid$-1$

end$-$if

end$-$while

Return $-1$