Prerequisites: (MATH 125 or INFS 501) and STAT 344
Objectives: mathematical foundations of Computer Science focusing on basic mathematical structures, mathematical logic and probability theory. It is designed to provide students with proficiency in applying these concepts to problem solving and formal reasoning. The course provides students with hands-on practice through the use of computational tools.
Instructor: Dr. Eugene Borovikov, adjunct professor at Computer Science department
Office hours: by appointment, Wednesday 5:30 – 7:00 pm in Nguyen Engineering 5306
Teaching Assistant: Pooja Sunkapur, office hours: Wed 1:30-3:30PM, Fri 2-4PM ENGR 5321
Class: IN 134 (Innovation Bldg, room #134)
Meeting Time: Wednesday 7:20 – 10:00 pm (except when noted in the schedule)
Textbooks:
- Text 1: Foundations of Computer Science by Alfred V. Aho and Jeffrey D. Ullman
- Text 2: Mathematics for Computer Science by E. Lehman, F.T. Leighton, A.R. Meyer
- Text 3: Lecture Notes on Mathematical Logic by Vladimir Lifschitz
- Text 4: Probability course notes by Richard Weber
- Additional material will be provided by the instructor
Grading:
- 6 Homeworks (must be submitted, but are assessed by corresponding quizzes/exams)
- 4 Quizzes: (Quizzes 1,3,4 – 5% each; Extended quiz 2 – 10%)
- Midterm: 30%
- Final: 45%
date | topic | events |
1/20 | Foundations: - sets, relations, functions, composition, inversion - algebra of sets and binary relations | HW1 out |
1/27 | Foundations: - induction and recursion, and recurrence relations - structural inductions, inductive definitions | |
2/3 | Foundations: - recurrence relations and generating functions | HW1 in, HW2 out, Quiz 1 |
2/10 | Foundations: Number Theory | |
2/17 | Foundations: wrap-up Logic: introduction | HW2 in, Extended Quiz 2 |
2/24 | Logic: propositional logic - syntax and semantics - transforming English specification into logical statements and creating proofs - consistence and completeness w/out proofs | HW3 out |
3/2 | Logic: predicate logic w/examples - syntax and semantics - transforming English specification into logical statements - consistence and completeness w/out proofs | |
3/9 | no class | spring break |
3/16 | Logic: practice/problem solving by proving theorems/finding counterexamples - hand vs mechanized proofs, counterexamples - theorem proving vs model checking | HW3 in, HW4 out, Quiz 3 |
3/23 | Logic: practice with computing applications | HW4 in |
3/30 | exam | midterm |
4/6 | Probability: - sample spaces, probability, random variables - continuous sample spaces, probability density - joint, marginal, and conditional probabilities - rules of probability: sum and product rules - Bayes' theorem | HW5 out |
4/13 | Probability: - 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. | |
4/20 | Probability: - Maximum likelihood estimation - Bayesian inference (e.g. for the Gaussian) - examples of applications in Computer Science - Probabilistic reasoning | HW6 out, HW5 in, Quiz 4 |
4/27 | advanced topics, review | HW6 in |
5/4 | exam | final |