Consider an instance of SAT with $m$ clauses, where every clause has exactly $k$ literals. Give a Las Vegas algorithm (i.e., an algorithm that always gives the correct result) that finds an assignment satisfying at least $m(1-2^{-k})$ clauses, and analyze its expected running time.
A possible Las Vegas algorithm is to randomly assign true/false to every variable, each with probability $1/2$. If the assignment satisfies less than $m(1-2^{-k})$ clauses, rerandomize all variables. Keep doing this until we get an assignment satisfying at least $m(1-2^{-k})$ clauses.
This is a valid Las Vegas algorithm, but I'm not sure it's one that would be expected by the question. Also, to analyze the expected running time, we would need to compute the probability that a random assignment works. This means the random assignment satisfies at least $m(1-2^{-k})$ clauses, and it doesn't seem easy to compute. What would be a better Las Vegas algorithm?