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 |