EECS 310 Mathematical Foundations of Computer Science

(or Introduction to Constructive Mathematics)

Time & Place

MWF 1000-1050 TECH LG52 (room changed)


Prof. Hai Zhou
haizhou AT
L461 Tech Institute
Office Hours: W 1-3pm or by appointment


Mr. Bach Ha
hqbach AT
M314 Tech Institute
Office Hours: F 1-4pm


This course will introduce the mathematical foundations of computer science. Topics include mathematical logic, set theory, programs and correctness proofs, relations and functions, recurrence relations, finite automata, and simple graph theory. Besides an understanding of basic mathematical concepts and structures, another main goal of this course is to help the studuents to establish rigorous mathematical thinking and reasoning habit and problem solving skills.


EECS 110 or EECS 111, and Math 214-3.

Required Text

Reference Book


  1. N. Wirth, Computing Science Education: The Road not Taken, Opening address at the ITiCSE Conference, Aarhus, 2002.
  2. A note on voting by Kleinberg.
  3. L. Lamport, How to Write a Proof. American Mathematical Monthly 102, 7 (August-September 1993) 600-608. Also appeared in Global Analysis in Modern Mathematics, Karen Uhlenbeck, editor. Publish or Perish Press, Houston. Also appeared as SRC Research Report 94.


Grading: 40% Homework     30% Midterm exam     30% Final exam
Late policy: -40% per day


Homework 0 (out:9/26 due:9/28): bio and background
Homework 1 (out:10/1 due:10/8): Boolean expression and propositional calculus
Homework 2 (out:10/8 due:10/15): Proof styles and techniques
Homework 3 (out:10/15 due:10/22): Predicate calculus and programs
Homework 4 (out:10/22 due:10/29): Math induction and programs
Homework 5 (out:10/29 due:11/9): Set theory and relations
Midterm review (out:11/5): review exercises
Homework 6 (out:11/12 due:11/19): Relations and integers
Homework 7 (out:11/19 due:11/26): Integers
Homework 8 (out:11/26 due:12/3): Combinatorial analysis
Homework 9 (out:12/3 as exercise): Recurrence relations

Lecture schedule

Final exam is 9-11am on Wed 12/12

Week 1: Boolean expressions and propositional calculus READING: chapters 1,2,3, Notes 1,2

Week 2: Proofs: styles and techniques. READING: chapters 4,5,6, Note 3

Week 3: Predicate calculus. READING: chapters 7,8,9

Week 4: Programs and mathematical induction. READING: chapters 10,12

Weeks 5,6: Theories of sets, sequences, and relations. READING: chapters 11,13,14

Week 7: Theory of integers and combinatorial analysis. READING: chapters 15,16

Week 8: Recurrence relations. READING: chapter 17

Week 9: Graph theory. READING: chapter 19

Week 10: Models of computation. READING: chapter 20 and handouts

Please check back often to this page ( for updates and course material down-loading.