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.

Instructor

Dr. Dmitri Kaznachey

Adjunct Professor, Computer Science Department

Senior Director, Trading Technology, Freddie Mac

dkaznach@gmu.edu

Office hours: by appointment

Graduate Teaching Assistant

Indranil Banerjee

Office hours: TBD

Class

Art and Design Building, Room 2026

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

Prerequisites

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)

Grading

 Tentative Schedule

Date

Topic

Test

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

Midterm

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

Final