CS 206 Midterm 2 Preparation: Story Proofs and Probability Skills

CS 206 Spring 2016, Rutgers University

Prof. David Cash

March 27, 2016

General Advice for Exam Preparation

This preparation document is meant to help you prepare for Midterm 2. It does not contain any new problems or topics. Instead, it places everything we've covered in one place, and isolates some specific skills that will be tested in the exam.

Learning math (or, more specifically, learning problem-solving skills in order to do well on an exam) is a highly personal activity. But I can describe how I learn math, in the hope that my opinion will be useful.

To learn basic topics, like how to compute simple conditional probabilities, one can actively work through solved examples, especially the ones from class. While this is an important first step, it only teaches the mechanics of a definition, to ensure that you've correctly parsed the definition or idea. (For example, to learn mutual versus pair-wise independence, I start with a small exercise and walk through it to see what the definition really says.)

Beyond the simple examples, though, the best way to learn these topics is by working fresh problems without looking for solutions until you are completely stuck. By struggling with a problem for a significant amount of time, you'll train your intuition to more quickly find the right approach later. But if you just go find a hint, you won't remember all the wrong ways (and why they are wrong) next time! And since every problem is different, the solution to one won't necessarily help on the next one anyway.

Topics Covered on Midterm 2

Midterm 2 will cover Homework 5 through Homework 8. Below I break down the topics we covered, and also identify specific problem-solving skills that will be on the exam. When possible, I'll point to the homework problems that correspond to those skills.

Story Proofs

Concepts and Definitions

1. Why we use story proofs: to explain identities and avoid induction.
2. The idea behind story proofs: Count the same thing in two different ways.
3. What a story proof looks like, and what's acceptably specific for a solution.

(Page 1)

Problem Solving Skills

1. Finding a simple story proof (without a hint). For example, something like