CS 1155 - Understanding and Constructing Proofs
Summer 1996
The basic concepts covered in the course include: logic (propositional and predicate), set theory, function theory, relations, and 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.
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. Scott McCrickard
If you need to meet with me, come during my office hours or
send me email to arrange an appointment. (MiRC is just south of
the CoC building through the covered walkway.)
Ellen Zegura
Homework 10%
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:
Textbook
The required textbook is by
K. A. Ross and C. R. B. Wright, "Discrete Mathematics (Third
Edition)", Prentice Hall, 1992.
I will also draw material from "Discrete Mathematics and
Its Applications (Third Edition)" by K. Rosen, McGraw Hill,
1995.
Getting Help
There is one teaching assistant for this course. He 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.
Office: CoC 226C, 894-9390
Email: mccricks@cc.gatech.edu
Office hours: Monday, Tuesday 3-4pm, or by appointment
Office: MiRC 131, 894-1403
Email: ewz@cc.gatech.edu
Monday, Wednesday 9:15-10am, 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.
First Midterm 25%
Second Midterm 25%
Final 40%
Schedule (subject to change)
Week | Topic | Reading |
---|---|---|
1 | Introduction | |
Propositional Logic | Sect 2.1, 2.2 | |
2 | Sets | Sect 1.1, 1.2 |
MIDTERM 1 | ||
3 | Functions | Sect 1.3, 1.4 |
4 | Relations | Sect 3.1, 3.2, 3.3 |
5 | Proof methods | Sect 2.3, 2.4 |
MIDTERM 2 | ||
6 | Predicate calculus | Sect 2.1, 2.2 |
Big-Oh notation | Sect 1.6 | |
7 | Special Topics | |
FINAL EXAM | ||
The first exam will be on Friday, August 30.
We will not hold class on Monday,
September 2 (Labor Day).