EECS 310 Mathematical Foundations of Computer Science

(or Introduction to Constructive Mathematics)

Time & Place

MWF 1000-1050 TECH LG52 (room changed)

Instructor

Prof. Hai Zhou
haizhou AT northwestern.edu
L461 Tech Institute
(847)491-4155
Office Hours: W 1-3pm or by appointment

TA

Mr. Bach Ha
hqbach AT northwestern.edu
M314 Tech Institute
(847)491-9925
Office Hours: F 1-4pm

Overview

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.

Prerequisites

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

Required Text

Reference Book

Notes

  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.

Policies

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

Homeworks

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 (www.ece.northwestern.edu/~haizhou/310) for updates and course material down-loading.