$1.$ Describe an algorithm for locating the last occurrence of the largest number in a list of integers and determine the worst$-$case time complexity of your algorithm.

$2.$ Give a big$-$O estimate for $($x$^2+$ x$($log x$)^3)(2^$x $+$ x$3).$

$3.$ Find an example that shows that scheduling jobs in order of increasing time required does not always yield a schedule with the smallest possible maximum lateness.

$4.$ Given n points in space $($defined by their coordinates x$,$ y$)$ belonging to a class a$,$ and m points in space belonging to a class b$,$ write an algorithm that classifies a new point $($x$\text{'},$ y$\text{'})$ as either class a or class b$.$ You may use any criteria for your classification, but you have to argue why your criteria is a good idea.

$5.$ Let P$($n$)$ be the statement that $1^2+2^2++$ n$^2=$ n$($n$+1)(2$n $+1)6$ for the positive integer n$.$

a$)$ What is the statement P$(1)?$

b$)$ Show that P$(1)$ is true, completing the basis step of a proof that P$($n$)$ is true for all positive integers n$.$

c$)$ What is the inductive hypothesis of a proof that P$($n$)$ is true for all positive integers n$?$

d$)$ What do you need to prove in the inductive step of a proof that P$($n$)$ is true for all positive integers n$?$

e$)$ Complete the inductive step of a proof that P$($n$)$ is true for all positive integers n$,$ identifying where you use the inductive hypothesis.

f$)$ Explain why these steps show that this formula is true whenever n is a positive integer.

$6.$ Prove that $2^$n $>$ n$^2$ if n is an integer greater than $4.$