Mathematical Foundations of Computer Science
Textbooks
In preparation for the examination, you may wish to review the following textbooks.
- Mathematics for Computer Science by E. Lehman, F.T. Leighton and A.R. Meyer (https://courses.csail.mit.edu/6.042/spring15/mcs.pdf)
- Lecture Notes on Mathematical Logic by Vladimir Lifschitz (https://www.cs.utexas.edu/users/vl/teaching/388Lnotes.pdf)
- 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