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 handson 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)
Prerequisites:
(MATH 125 or
INFS 501) and STAT 344
Textbook(s):
 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/mcsftl.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/probweber.pdf )

Additional material will be provided by instructor
Grading
 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
Date 
Meeting 
Topic 
Homework Out 
Homework In 
Quizes/Exams 
Aug 31 
1 
Foundations 
HA1 Out 


Sep 7 
 
Labor Day – university closed 



Sep 14 
2 
Foundations (cont.) 



Sep 21 
3 
Foundations (cont.) 
HA2 out 
HA1 In 
Quiz 1 
Sep 28 
4 
Foundations (cont.) 



Oct 5 
5 
Foundations (cont.)
+ Start Math Logic 

HA 2 In 
Extended quiz 2 
Oct 12 
 
Columbus Day
– no classes 



Oct 13 (Tue) 
6 
Mathematical Logic 
HA 3 Out 


Oct 19 
7 
Mathematical Logic
(cont.) 



Oct 26 
8 
Mathematical Logic
(cont.) 
HA 4 Out 
HA3 In 
Quiz 3 
Nov 2 
9 
Mathematical Logic
(cont.) 

HA 4 In 

Nov 9 
10 
Midterm 


Midterm 
Nov 16 
11 
Probability Theory 
HA5 Out 


Nov 23 
12 
Probability Theory (cont.) 



Nov 30 
13 
Probability Theory
(cont.) 
HA 6 Out 
HA5 In 
Quiz 4 
Dec 7 
14 
Advanced Topics/ Catchup and Review 

HA6 In 

Dec 14 
Final 
7:30 PM 


Final 