CS 530 – Mathematical Foundations of Computer Science

Prof. A. Brodsky – Fall 2015

Course Objectives:

This course teaches 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.  To achieve this, the course provides students with significant hands-on practice including through the use of computational tools.


Instructor: Prof. Alex Brodsky, Computer Science department

Office hours: Thursday, 3:30 – 5:00 pm

Special hour for CS 530 solutions: Thursday, 2:30 – 3:30 pm (location TBD)


Graduate Teaching Assistant: Nate Craun

GTAŐs Office Hours: TBD


Class: East Building, Room 122

Meeting Time: Monday 7:20 – 10:00 pm (see exceptions on detailed schedule below)



(MATH 125 or INFS 501) and STAT 344



-           Text 1: Foundations of Computer Science by Alfred V. Aho and Jeffrey D. Ullman (http://infolab.stanford.edu/~ullman/focs.html )

-           Text 2: Mathematics for Computer Science by E. Lehman, F.T. Leighton and A.R. Meyer ( http://courses.csail.mit.edu/6.042/fall10/mcs-ftl.pdf )

-           Text 3: Lecture Notes on Mathematical Logic by Vladimir Lifschitz (https://www.cs.utexas.edu/users/vl/teaching/388Lnotes.pdf)

-           Text 4: Probability course notes by Richard Weber (http://www.statslab.cam.ac.uk/~rrw1/prob/prob-weber.pdf )

-           Additional material will be provided by instructor



-           6 Homeworks (must be submitted, but are assessed by corresponding quizzes/exams)

-           4 Quizes: (Quizzes 1,3,4 – 5% each; Extended quiz 2 – 10%)

-           Midterm: 30%

-           Final: 45%


Course Content


-           Foundations  (~ 5 weeks):

o    Set Theory: Sets, relations and functions, composition, inversion

o    Algebra of sets and Boolean relations

o    Induction and recursion, and recurrence relations

o    Structural inductions, inductive definitions

o    Recurrence Relations and Generating Functions

o    Number Theory

-           Mathematical Logic (~ 4 weeks):

o    Propositional logic (syntax and semantics; transforming English specification into logical statements and creating proofs; consistence and completeness w/out proofs)

o    Predicate logic w/examples (syntax and semantics; transforming English specification into logical statements; consistence and completeness w/out proofs)

o    Practice/problem solving by proving theorems/finding counterexamples; hand vs. mechanized proofs and counterexamples; theorem proving vs. model checking

o    Practice with computing applications

-           Probability Theory (~ 3 weeks):

o    Sample spaces, probability, random variables (discrete)

o    Continuous sample spaces. Probability density.

o    Joint, marginal, and conditional probabilities

o    The rules of probability: Sum and product rules

o    Bayes' theorem

o    Independence of random variables

o    Expectations. Mean, Variance, and Covariance

o    Biased and unbiased estimators

o    Univariate and multivariate Gaussian distributions

o    Other important distributions: Poisson, Exponential, Bernoulli, Binomial, Multinomial; Exponential family of distributions.

o    Maximum likelihood estimation

o    Bayesian inference (e.g. for the Gaussian)

o    Examples of applications in Computer Science

o    Probabilistic reasoning



Tentative Teaching Schedule




Homework Out

Homework In


Aug 31



HA1 Out



Sep 7


Labor Day –

university closed




Sep 14


Foundations (cont.)




Sep 21


Foundations (cont.)

HA2 out

HA1 In

Quiz 1

Sep 28


Foundations (cont.)




Oct 5


Foundations (cont.) +

Start Math Logic


HA 2 In

Extended quiz 2

Oct 12


Columbus Day – no classes




Oct 13 (Tue)


Mathematical Logic

HA 3 Out



Oct 19


Mathematical Logic (cont.)




Oct 26


Mathematical Logic (cont.)


HA 4 Out

HA3 In

Quiz 3

Nov 2


Mathematical Logic (cont.)



HA 4 In


Nov 9







Nov 16


Probability Theory

HA5 Out



Nov 23


  Probability Theory (cont.)





Nov 30


Probability Theory (cont.)


HA 6 Out

HA5 In

Quiz 4

Dec 7


Advanced Topics/

Catch-up and Review


HA6 In


Dec 14


7:30 PM