These comments assume you've read the solutions posted on the website,
or at least that you have them available.

#1. You all did terribly on this problem! 4 of you got 0/10, which means
you basically completely ignored the possibility that the runtime can
be exponential, instead pretending the problem is as easy as showing L
⊆ P. 7 points were allocated for giving an algorithm that handles the
possibly-exponential runtime using polynomially-many arbitrary-precision
arithmetic operations. 1 point for observing the issue that the computed
probabilities can have exponential precision, and 2 points for dealing
with that issue.

#2. I allocated 7 points for modifying the base case appropriately, and 3
points for the inductive step. Only one of you got the 3 points. Perhaps
I should have made the split closer to 5 and 5.

#3 and #4. Good job on these.

Dustin