### Mathematical Foundations of Computer Science

#### Textbooks

In preparation for the examination, you may wish to review the following textbooks.

1. Mathematics for Computer Science by E. Lehman, F.T. Leighton and A.R. Meyer (https://courses.csail.mit.edu/6.042/spring15/mcs.pdf)
2. Lecture Notes on Mathematical Logic by Vladimir Lifschitz (https://www.cs.utexas.edu/users/vl/teaching/388Lnotes.pdf)
3. Probability course notes by Richard Weber (http://www.statslab.cam.ac.uk/~rrw1/prob/prob-weber.pdf)

#### Course Content

Foundations:

• Set Theory: Sets, relations and functions, composition, inversion
• Algebra of sets and Boolean relations
• Induction and recursion, and recurrence relations
• Structural inductions, inductive definitions
• Recurrence Relations and Generating Functions
• Number Theory

Mathematical Logic:

• Propositional logic (syntax and semantics; transforming English specification into logical statements and creating proofs; consistence and completeness w/out proofs)
• Predicate logic w/examples (syntax and semantics; transforming English specification into logical statements; consistence and completeness w/out proofs)
• Practice/problem solving by proving theorems/finding counterexamples; hand vs. mechanized proofs and counterexamples; theorem proving vs. model checking
• Practice with computing applications

Probability Theory:

• Sample spaces, probability, random variables (discrete)
• Continuous sample spaces. Probability density.
• Joint, marginal, and conditional probabilities
• The rules of probability: Sum and product rules
• Bayes' theorem
• Independence of random variables
• Expectations. Mean, Variance, and Covariance
• Biased and unbiased estimators
• Univariate and multivariate Gaussian distributions
• Other important distributions: Poisson, Exponential, Bernoulli, Binomial, Multinomial; Exponential family of distributions.
• Maximum likelihood estimation
• Bayesian inference (e.g. for the Gaussian)
•  Examples of applications in Computer Science
• Probabilistic reasoning