MWF 1000-1050 TECH LG52 (room changed)

Prof. Hai Zhou

haizhou AT northwestern.edu

L461 Tech Institute

(847)491-4155

Office Hours: W 1-3pm or by appointment

Mr. Bach Ha

hqbach AT northwestern.edu

M314 Tech Institute

(847)491-9925

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.

- D. Gries and F. B. Schneider, A Logical Approach to Discrete Math. Springer-Verlag New York, 1993.

- K. H. Rosen, Discrete Mathematics and Its Applications, 6th Ed.. McGraw Hill, 2007.

- N. Wirth, Computing Science Education: The Road not Taken, Opening address at the ITiCSE Conference, Aarhus, 2002.
- A note on voting by Kleinberg.
- 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

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.