CS 530 - Mathematical Foundations in Computer Science

Fall 2016

Course Description

This course covers 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.


Dr. Dmitri Kaznachey

Adjunct Professor, Computer Science Department

Senior Director, Trading Technology, Freddie Mac


Office hours: by appointment

Graduate Teaching Assistant

Indranil Banerjee

Office hours: TBD


Art and Design Building, Room 2026

Monday, 7:20 PM - 10:00 PM (see exceptions below)


Text Books

  1. Foundations of Computer Science by Alfred V. Aho and Jeffrey D. Ullman (http://infolab.stanford.edu/~ullman/focs.html)
  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)
  3. Lecture Notes on Mathematical Logic by Vladimir Lifschitz (https://www.cs.utexas.edu/users/vl/teaching/388Lnotes.pdf)
  4. Probability course notes by Richard Weber (http://www.statslab.cam.ac.uk/~rrw1/prob/prob-weber.pdf)


 Tentative Schedule




Aug 29

Foundations 1. Set theory - sets, relations and functions, composition, inversion.  Algebra of sets and Boolean relations. Text 1; sections 1 (preface), 7.2, 7.3, 7.7

Sep 5

Labor Day - no class

Sep 12

Foundations 2. Iteration, induction, and recursion

Sep 19

Foundations 3. Graphs

Quizz 1

Sep 26

Foundations 4. Recursive definitions, grammars

Oct 3

Foundations 5. Number Theory

Quizz 2

Oct 10

Columbus Day - no class

Oct 17

Mathematical Logic 1. Propositional Logic

Oct 24

Mathematical Logic 2. Propositional logic - formal proofs

Quizz 3

Oct 31

Mathematical Logic 3. Predicate logic

Quizz 4

Nov 7

Mathematical Logic 4. Practice with computing applications

Nov 14

Midterm Exam


Nov 21

Probability Theory 1.  Sample spaces

Nov 28

Probability Theory 2. Conditional probability

Quizz 5

Dec 5

Probability Theory 3. Continuous sample spaces

Quizz 6

Dec 12

Advance Topics / Review

Dec 19

Final Exam - 7:30 PM