Final

Hi all -- nice job on the final! The average was 84%, which is quite good.

I think you all were a particularly strong class this year! Thanks for your hard work.

best,
Ryan

Final info

The final exam is now finalized. As a hint, I can tell you it is pretty heavily focused the post-midterm material.

Don't forget, I have an office hour tonight from 5pm to 6pm.

HW12 graded scripts and solutions

I will hand these out during my OH this week.
Also, I have a few uncollected assignments and midterms.
Please come and collect these.

-Anshul

Practice final exam

I have posted 14 15 practice problems for the final exam. It's still not exhaustive with respect to all the topics, but I think if you get through these it will be a good start!

Course Evaluations!

Please take the time to fill in the course evaluations! It's super-important for making the class better in the future. Go to this link:

https://my.cmu.edu/site/main/page.academics

and look for and click on "University Course Assessment" on the left side. It's due in 3 days, so please fill it out as soon as you can.


Please also take the time to fill in the evaluations for Anshul! Here again is the link.

Office hours

I will have different office hours next week. I believe Anshul will have the same-as-usual office hour, Tuesday 4pm - 5pm.

I will be available my office, GHC 7121:
Tuesday 5pm - 7pm,
Wednesday 5pm - 6pm.

We can discuss any of the practice final problems, or old homework problems, or anything else from the class.

Final exam info

The final exam will take place in GHC 4215 on Thursday, December 10, from 8:30am to 11:00am. Pretty early, I know. I'll try to bring some coffee.

You are responsible for all topics from the course and homeworks. That said, there will be more of a focus on the post-midterm material.

The midterm will consist of 5 parts. As with the midterm, the first part will be "short answer", and the remaining parts will be "problems". (I reserve the right to deviate from this format, though.) My intention is to make the difficulty level comparable to that of the midterm. In particular, I will be designing it as though you have 100 minutes, although in fact you will have 150 minutes. As on the midterm, the problems will be "multi-part", and you can solve later parts by relying on earlier parts, even if you couldn't solve the earlier parts.

As on the midterm, you may bring one standard 3" x 5" index card with prepared material on it. Both sides may be written on. If you do not have an index card, you can download and print this one. The index card must be handwritten (not typed) and prepared by you yourself. No other aids (calculator, computer, magnifying glass, etc.) are allowed.

I will endeavor to post practice problems for the final on this blog by Saturday.

Lecture 26 -- Random variable generation

The notes on random variable generation are posted.

More homework commentary and name-checks

Practice Midterm #2: In 1938, Claude Shannon was the first person to apply Boolean algebra to logical networks. (It was his Master's thesis at MIT.) Rather than circuits, he worked with the "contact networks" described in the problem. Much later, in 1956, he and Edward Moore (not the Moore's Law guy; rather, the guy that invented a lot of automata theory) used ideas like those on the problem to show that even if you have relays that fail with high probability ("crummy" relays, they called them), you can still build reliable contact networks. Contact networks are also studied by statistical physicists, who use them to model percolation of liquids. This has in turn reinspired computer scientists.

Practice Midterm #7: Raimund is Raimund Seidel, who invented the technique of "backwards analysis" used in the problem. This technique is used heavily in computational geometry.

Practice Midterm #10: Michael is Michael Rabin; this data structure of his was one of the first demonstrations of the power of probability in computing. Read more about it here.

Homework 8, #6: Keith refers to Keith Hastings, who generalized the Metropolis algorithm

Homework 9, #6: Georges refers to Georges-Louis Leclerc, Comte de Buffon, an 18th century French guy. He is most famous for the Buffon's Needle result, the result of problem 6f. He actually suggested it as a way to estimate $\pi$: find a floor with long parallel lines and sit around dropping needles, or nails, on it, with length equal to the distance between lines. The fraction that cross a line gives you an estimate of $2/\pi$. This can be considered an early instance of the algorithms technique known as the Monte Carlo Method. (Also a good album with a good cover by Nothing Painted Blue.) Famously, an Italian mathematician called Lazzarini did this experiment in 1901 and obtained $\pi \approx 3.1415929$, which is extremely close. However, he cheated. It is possible to solve the Buffon Needle problem with a boring and slightly painful integral. But instead on the homework, we saw the ingenious way of solving it using Linearity of Expectation. This method is called, no joke, Buffon's Noodle.

Homework 10, #4: This problem illustrates the so-called Inspection Paradox.

Homework 10, #5: As mentioned, the expected length of the MST in a random-length graph approaches 1.202... as $n \to \infty$. More precisely, it approaches

$\zeta(3) = \sum_{i=1}^\infty \frac{1}{i^3}$,

which I find pretty amazing! This fact was proved in 1985 by CMU Math professor Alan Frieze. Please give him a high-five for this amazing result next time you see him.


Updates for Homework 12 to appear soon. And yes, the Anupam of #6 is CMU CSD professor Anupam Gupta.

Lecture 25 -- Entropy and compression

Here are the lecture notes on entropy and compression.

TA evaluation form

Hi all,

Here is the link for the TA evaluation form.

The link will be active till December 11.
Please make sure you fill it out !

-Anshul

Homework extension

I am extending the deadline for Homework 12. It will now be due on Thursday, at the beginning of (our last) class.