CS 1155 - Understanding and Constructing Proofs

Fall 1996

Homework Assignments

Syllabus

Course Summary
Teaching Philosophy
Teaching/Learning Goals
Textbooks
Getting Help
Grading
Schedule

Course Summary

CS 1155 (Understanding and Constructing Proofs) is the first course in the computer science department on the formal mathematical foundation of computer science. The material in this course is required and further developed in courses such as CS 3156 (Introduction to Automata Theory) and CS 3158 (Design and Analysis of Algorithms). While intended to be taken in the freshman year, many students put off this course until the sophomore and junior year, thereby denying themselves the benefit of early introduction to the useful tools of mathematical rigor and proof techniques.

The basic concepts covered in the course include: logic (propositional and predicate), set theory, function theory, relations, and proof methods (including induction). The primary goal of the course is for students to develop skill in the technique of proofs, including the ability to write correct (even elegant!) proofs and recognize whether an argument is a valid proof. This skill is invaluable in computer science and elsewhere. Secondary goals include an introduction to concepts that can be difficult and will recur throughout the undergraduate curriculum, including big-Oh notation and recurrence/induction.

Students may find this material dry and seemingly irrelevant to the nuts and bolts of computer science. Quite the contrary; abstraction and logical reasoning are central to computer science. Examples will be used throughout the course that attempt to connect these concepts with familiar domains including programming and games.

Teaching Philosophy

As described above, the primary purpose of this course is for you to develop skill in the technique of proving things. Like any skill, development takes practice --- lots of practice. I will present many examples of proofs in class; these should serve as useful models, but are no substitute for working out problems yourself. The homework assignments will give you the opportunity to practice your technique. You should try to work out the homework problems on your own, seeking help from the TA's or myself after you have given the problem some thought.

I encourage (and expect) you to participate actively in the learning process. In particular, I welcome your comments and questions as we cover material in class. One-way lectures quickly becoming boring, both for you and for me. By asking lots of questions, your understanding of the material will be deepened signficantly, and the course will be much more fun!

Teaching/Learning Goals

My primary goals for this course are for you to develop the following abilities:

To take an informal problem statement and express it using unambiguous and rigorous mathematics.
To correctly use mathematical definitions, and to recognize that the precision of definitions complements (and sometimes contradicts) intuition.
To apply understanding of proofs and proof techniques to write correct proofs, starting with the hypothesis and known facts and ending with the conclusion.
To understand what constitutes a proof, and be able to recognize flaws in candidate proofs.
To select an appropriate proof method.
To understand the relationship between mathematical foundations and the rest of computer science.
To appreciate a part of the history of mathematics and computer science.

Textbook

The required textbook is by K. Rosen, "Discrete Mathematics and Its Applications (Third Edition)", McGraw Hill, 1995.

Several other books cover proofs and proof techniques with a more "conversational" tone. These books should be available at the library. None are required, but they are all fun to read and are likely to reinforce the notion of what constitutes an elegant proof and how proofs can be useful in a variety of contexts.

D. Velleman, "How to Prove It: A Structured Approach", Cambridge University, 1994.
G. Polya, "How to Solve It: A New Aspect of Mathematical Method", Princeton University Press, 1945.
D. Solow, "How to Read and Do Proofs: An Introduction to Mathematical Thought Processes", John Wiley and Sons, 1990.

Getting Help

There are two teaching assistants for this course. They will do all grading of homework assignments, and should be your first point of contact when you need help with homework or have a question about grading.

David Cardoze
Office: CoC 123
Email: cardoze@cc.gatech.edu
Office hours: Tu 2-3, Fr 2-3

Vergilia Chin
Office: CoC 153
Email: vchin@cc.gatech.edu
Office hours: M 2-3, Tu 3-4

If you need to meet with me, come during my office hours or send me email to arrange an appointment.

Ellen Zegura
Office: GCATT 216; 894-1403
Shared CoC Office: CoC 217
Email: ewz@cc.gatech.edu
Monday, Wednesday 10-11am, or by appointment

Grading

The grading allocation is given below. Note that the homework carries relatively low weight. This is not a reflection on the importance of doing the homework; you should do the homework to develop skills which you will demonstrate during the exams. Solutions to the homework will be handed out on the day that it is due; {\it late homeworks will not be accepted.} A note about academic honesty: I expect you to work alone on the homework assignments and (obviously) on the exams. Seek help from the TA or me if you are having difficulty with the homework.

Homework 10%
First Midterm 25%
Second Midterm 25%
Final 40%

Schedule (subject to change)

Week	Topic	Reading
1	Introduction
2	Propositional Logic	Sect 1.1, 1.2
3	Predicate Calculus	Sect 1.3
4	Proof methods	Sect 3.1
	Examples using number theory
5	MIDTERM 1
	Sets	Sect 1.4, 1.5
6	Functions	Sect 1.6
7	Big-Oh	Sect 1.7, 2.1, 2.2
8	Relations	Sect 6.1, 6.3, 6.5
	MIDTERM 2
9	Induction	Sect 3.2, 3.3
	FINAL EXAM