### Mathematical Foundations of Computer Science

#### Textbooks

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

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

#### 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