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.
Reading and writing definitions
Writing proofs
Working with quantifiers and other logical statements
Probability definitions: sample space, probability measure (including Kolmogorov's axioms), probability space, independence (for events and RVs), conditional probability, random variable, expectation, variance
Know and be able to use basic theorems about probability: Bayes's rule, law of total probability, linearity of expectation, expectation of the product, variance of sums, Markov's inequality, Chebychev's inequality, weak law of large numbers, 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)\).
Be able to apply the above definitions, etc. in concrete examples