Prelim 1 study guide

Everything covered in lecture or homework on or before Wednesday, September 20 is in scope. Material that was covered on the homework will receive a heavier emphasis. Material covered after Wednesday may be used as examples, but any defintions will be given to you.

update: - You are not required to know the new definitions from this week: hash function, "good" hash function, injective/surjective/etc. However, you should understand what they mean, as they are good uses of quantified statements, random variables, independence, etc. In other words, if I ask questions using these concepts, I will give you the relevant definitions.

Here are some collected questions from past prelims and finals (solutions) There is always variation between semesters on the exact topics covered and the extent to which they are emphasized, so take the sample prelims with a grain of salt. I would expect most of these questions to take 10-15 minutes.

Topics include, but are not limited to:

• Basic definitions: set, function, partial function, domain, codomain, power set, cartesian product, set of functions, union, intersection, set difference, empty set, etc.

• Be able to state and prove basic facts about probability, including the above results, as well as simple facts like $$Pr(S \setminus E) = 1 - Pr(E)$$.