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)

 

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

 

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/

Catch-up and Review

 

HA6 In

 

Dec 14

Final

7:30 PM

 

 

Final