Recall the MAX$-3-$SAT problem: given a set of clauses $C_1,C_2,$dots,$C_k,$ each a disjunction of $3$ terms over a set of variables $x=\{x_1,x_2,$dots,$x_n\},$ find a truth assignment of the variables that satisfies as many of the $k$ clauses as possible.

$($a$)(3$ points$)$ In class we saw a very simple, polynomial$-$time, randomized algorithm for achieving a $\frac{7}{8}$ approximation $($in expectation$)$ to the optimal solution of MAX$-3-$SAT. What was the algorithm? Give either a description of it in English or provide some brief pseudocode for it$.$

$($b$)(2$ points$)$ We noted that an immediate consequence of this result in part $($a$)$ is the following fact: For every instance of $3-$SAT, there exists an assignment of the boolean variables that satisfies at least a $\frac{7}{8}$ fraction of all the clauses. That is$,$ if $k$ is the number of clauses, there is an assignment that satisfies at least $7\frac{k}{8}$ of them.

What does the above fact imply about instances of $3-$SAT that have $k7$ clauses?

$($Hint to get you going here: suppose we have an instance of $3-$SAT with $k=8$ clauses. For such an instance, according to this fact, at least how many of the clauses can be satisfied? Now what if $k=7?$