Questions

I ask A LOT of questions when I learn something. (Huge thanks to all of my instructors for not getting annoyed ^ ^)I’m going to keep track of the questions I’ve asked that I may want to revisit in the future.

• [Probability] Poisson distribution & normal distribution?
• Question: We use Poisson distribution to approximate Binomial distribution, which means it’s approximately a summation of Bernoulli random variables. Since the underlying assumption for Poisson distribution is n goes go infinity, why wouldn’t Poisson distribution look like normal distribution according to CLT?
• Answer: (Prof. Adhikari; rephrased) If we fix $p$, the sum of Bernoulli random variables will be approximately normally distribution. However, for Poisson approximation, $p$ goes smaller when $n$ goes larger.
• [Probability] Why do we use square brackets for expectations?
• Question: I notice that we write E[X] or E(X) but I’ve never seen Var[X]. Why do we sometimes use square brackets for expectations?
• Answer: (Dibya) In algebra, linear functionals are denoted by f[x] instead of f(x). A functional of a vector space is a linear map f:VR. On the vector space of random variables, the expectation operator is a linear functional, and so often denoted as E[X]. The variance is not a linear functional, and so not written using square brackets.
• [Probability] A urn contains $w$ white balls and $b$ black balls. After a ball is drawn, it is replaced along with $d$ more balls of the same color. Show that $P$(second ball drawn is white) = $\frac{w}{w+b}$.
• Question: What is the intuition behind $P$(second ball drawn is white) doesn’t depend on $d$?
• Answer: (Prof. Ibser) Consider the extreme cases: d=0 and d very large. If d=0, then the draws are independent and P(white on second draw) is same as P(white on first).  If d is very large, P(white on second|white on first) is close to 1, and P(white on second|black on first) is close to 0, so P(W 2nd) = P(W 1st)P(W 2nd|W 1st) + P(B 1st)P(W 2nd|B 1st) which gets us back to P(W 1st). Hopefully thinking about the extreme cases helps with the intuition.
• [Propositional logic] $\forall x ((\exists y Q(x,y)) \implies P(x))$ is not equivalent to $\forall x \exists y (Q(x,y) \implies P(x))$
• Question: Since P(x) doesn’t depend on y, what’s special about this expression that alters the expression when we move $\exists y$?
• Answer: (Hung) The main difference is between “If there exists y such that …, then …” versus “There exists y such that if …, then …” . The first statement is true when that y does not exist, but the second statement would be false.
• [Misc. ] Markov Chain Monte Carlo
• Question: Where does this name come from? Why Monte Carlo?
• Answer: (Jason) Monte Carlo algorithms use random sampling to compute deterministic quantities such as integrals or probability distributions.

In the 1940s, when Stanislaw Ulam and John von Neumann were testing nuclear bombs, Ulam needed a method to estimate how much energy neutrons would give off. A deterministic model would have been too complex, so Ulam came up with the modern version of the Monte Carlo Method. Nicholas Metropolis came up with the codename for this method, naming it after the Monte Carlo Casino in Monaco.

CS70 CSM

Here are some supplementary notes for CS70 to help students build a larger picture of the material. Each document is based on the official lecture notes and/or CSM worksheet for the corresponding week. Hope you’ll find them helpful, and have a great time studying CS70!

(Thank you Hung Vu for proofreading!)

Week0

Week1

Week2

Week3 Good luck on the midterm!

Week4

Week5

Week6

Week7

Week8

Week9

Week10

Week11

Week12

Week13

Wow, look at all those things you’ve learned in one semester! Finishing 70 is already an accomplishment. Hope you can spend some time during dead week to truly appreciate the concepts you learned, and best of luck on the final!

CS61A: Scheme Problems

Below is a compilation of scheme problems from recent semesters. Good luck and have fun!

• Tail Recursion: implement a helper function with an extra parameter storing the result / things you want to remember; return the result of calling call the helper function with base case returned value
• Stream: kind of like linked list – rest is either nil or another stream (recursive call).

Practice:

• [Tail Recursion] Spring 17 Q8 Solution

• [Stream + tail recursion] Fall 16 5(b) Solution

• [Tail Recursion] Fall 2015 Q6 Solution

• [Tail Recursion] Summer 15 7(a) Solution

• [Tail Recursion] Fall 14 4(c) Solution

• [Tail Recursion] Summer 17 8(b) Solution

• Summer 17 Q9 Solution

CS61A: repr and str

• str returns a human-readable string
• repr returns a Python interpretable expression that evaluates to an equal object.
• repr(object) -> String
• For most object types, eval(repr(object)) == object
• The result of calling repr on the value of expression is what Python prints in an interactive session

• In summary,
• >>> print(a) is print(str(a))
• >>> a is print(repr(a))
• repr is called if str isn’t defined in the class.
• .format calls __repr__ on input arguments.

CS61A: Iterable, Iterator and Generator

• Iterables have __iter__ method, which returns a iterator.
• Iterators have __iter__method (returns themselves, since they’re iterators), and __next__  method.
• Generators functions (functions with yield statement) return a iterator after being called. You can write __iter__ in iterables as a generator function.

• Practice: Spring 2017 Final Q9 Solution

*list takes an iterable and return a list whose items are the same and in the same order as iterable’s items.

CS61A: Nonlocal

• Modify a variable in parent frame (*cannot be global frame!)
• Nothing fancy 😛 Mostly environment diagrams – do more practice!
• Okay. Enough environment diagrams / Q2’s! Again, get more practice! ( <– the key to 61A)