CS1050C: Understanding and Constructing Proofs
Spring 2003
MWF 2:05-2:55, Location:
College of Computing, room 17
Instructor
Dr.
Margaret Loper
Electronics
Research Building (ERB)
Office
Hours: By appointment
General Class Information
Textbook:
Discrete Mathematics with Applications, 2nd edition, by Susanna
Epp
Newsgroup:
git.cc.class.cs1050c
Goals and Objectives
This course is primarily
a foundations and logic course. Topics covered are logic of compound
and quantified statements, elementary number theory and proof, sequences
and mathematical induction proofs, sets, functions, and relations.
This course will focus on:
-
Fundamental concepts, notations, and facts in discrete mathematics
-
Fundamental principles, theories, and generalizations
-
Rational thinking, decision-making, and problem-solving
One
goal of this course is to study the mathematical ideas that are used in
various disciplines of computer science. Discrete mathematics is
relevant to many areas in computer science including:
-
Algorithms and Complexity Theory
-
Relational Databases
-
Computer Security, Cryptography
-
Artificial Intelligence
-
Programming language theory, compiler optimizations
-
Hardware verifications
-
Network-related problems
-
Computer graphics
Teaching Assistants
The class is divided into two sections. Each
section has two TAs assigned to it. The TAs will be responsible for
grading homework for their section for the duration of the course.
Each TA will hold office hours for 2 hours each week.
Section Red:
Haile
Seifu
seif@cc.gatech.edu
Office hours: M W 10:00-11:00, Commons/NT Lab
Matthew
Might
treknut@cc.gatech.edu
Office hours: T Th 11:00-12:00, Commons
Section Blue:
Barath
Petit
bpetit@cc.gatech.edu
Office hours: Tuesday Wednesday 11:30 - 12:30 CCB
154
Shomari
Mosi
shomari@cc.gatech.edu
Office hours: T Th 10:00 - 11:00 Commons/NT lab
Homework
There will be seven homework sets assigned.
To do well on the tests, you need to do the homework. When I make
up the exam, I expect that you have done and understood all the homework
problems. If you do not keep up with the homework, you will do poorly
on the tests.
You have one week to complete homework assignments.
It is important to start on the assignments early, starting on the assignment
the night before and running into problems will not get you much support
or sympathy from the instructor or TAs. All assignments must have
your name and e-mail address (from your prism account) written legibly
at the top. If your assignment is multiple pages, it must be stapled
together.
Partial answers to the problems will be given partial
grades, so always submit your best attempt at solving a problem
Each homework submitted must have a collaboration
statement of the form:
?I worked alone
and only with course material?,
or
?I collaborated
on this assignment with (students in class), got help from (people other
than collaborators and course staff), and referred to (citations to texts
and material other than the class texts and notes).?
No homework will be given a grade until it has a
collaboration statement.
Late Policy: I will collect homework at the
beginning of the class period. Any homework not turned in by the
end of class is considered late. Late homework sets should be turned
in to your TA by arrangement with him or her. Homework sets turned
in within 24 hours of the due time will be penalized 10%; those turned
in 24 to 48 hours late will be penalized 20%. Homework sets more
than two days late may not get graded at all. If you are unable to
complete the homework by the date assigned, please talk to the instructor
in
advance.
Re-grade Policy: All re-grade requests must
be made to the instructor in writing.
Collaboration: I do not mind if you work together
on homework sets. Study groups can be an excellent means to master
course material. However, you must write up the solutions on your
own, neither copying solutions nor providing solutions to be copied.
If you do collaborate on homework, you must cite all of your collaborators
in the collaboration statement.
Exams and Grades
Tests and Final
There will be three tests during the semester,
each worth 100 points. My tests always include definitions, examples
of how those definitions apply, proofs, and problems of varying difficulty.
Test
1: February 7th
Test
2: March 14th
Test
3: April 9th
Final
Exam: Thursday, May 1st, 11:30-2:20
Students are expected
to take tests/exam at the scheduled times. No make-ups will be given
except in the case of a real emergency, serious illness, or death in the
immediate family. In such cases, the instructor must be contacted
as soon as possible.
Homework
There will be 7 homework sets, each about equal
weight. Your lowest grade among the 7 will be dropped.
Grades
Grades for the course will be based on the following
weighting:
Tests:
40% (10%, 15%, 15%)
Homework:
20%
Final:
30%
Class
Participation: 10%
Unless
otherwise specified, I will use the following grading scale:
A 90-100%, B 80-89%,
C 70-79%, D 60-69%, F 0-59%
Attendance Policy
Classes and office
hours are what you pay tuition for, so take advantage of them. If
you don?t come to class you will not learn the material with the same emphasis
that I put on it. That will hurt your test scores and detract from
what you learn. I do not deduct points for classes missed, however
you cannot earn class participation points if you do not attend class.
Reading
Assignments and Topics
|
Date
|
Topic
|
Book
Section
|
Homework
|
|
1/6
|
Introduction
and Syllabus
|
|
|
|
1/8
|
Logical
Form and Logical Equivalence
|
1.1
|
|
|
1/10
|
Conditional
Statements
|
1.2
|
|
|
1/13
|
Valid
and Invalid arguments
|
1.3
|
|
|
1/15
|
Valid
and Invalid arguments
|
1.3
|
|
|
1/17
|
Application:
Digital Logic Circuits
|
1.4
|
HW1
due
|
|
1/20
|
NO
CLASS
|
|
|
|
1/22
|
Predicates
and Quantified Statements
|
2.1
|
|
|
1/24
|
Predicates
and Quantified Statements
|
2.2
|
|
|
1/27
|
Predicates
and Quantified Statements
|
2.2
|
|
|
1/29
|
Arguments
with Quantified Statements
|
2.3
|
|
|
1/31
|
Application:
Prolog
|
|
HW2
due
|
|
2/3
|
Direct
Proofs
|
3.1
|
|
|
2/5
|
Direct
Proofs
|
3.2-3.3
|
|
|
2/7
|
TEST 1
|
|
|
|
2/10
|
Test 1 Review
|
|
|
|
2/12
|
Direct
Proofs
|
3.4-3.5
|
|
|
2/14
|
Indirect
Argument Direct Proofs
LAST
DAY TO DROP COURSE
|
3.6
|
|
|
2/17
|
Application:
Algorithms
|
|
|
|
2/19
|
Sequences
|
4.1
|
HW3
due
|
|
2/21
|
Induction
|
4.2
|
|
|
2/24
|
Induction
|
4.3
|
|
|
2/26
|
Strong
Induction
|
4.4
|
|
|
2/28
|
Application:
Correctness of Algorithms
|
|
HW4
due
|
|
3/3
|
NO
CLASS - Spring Break
|
|
|
|
3/5
|
NO
CLASS - Spring Break
|
|
|
|
3/7
|
NO
CLASS - Spring Break
|
|
|
|
3/10
|
Set
Theory Definitions
|
5.1
|
|
|
3/12
|
Properties
of Sets
|
5.2
|
|
|
3/14
|
TEST 2
|
|
|
|
3/17
|
Test
2 Review
|
|
|
|
3/19
|
Empty
Sets, Partitions, Power Sets, and Boolean Algebra
|
5.3
|
|
|
3/21
|
Application:
Formal Languages
|
|
HW5
due
|
|
3/24
|
Functions
Defined on General Sets
|
7.1-7.2
|
|
|
3/26
|
One-to-One
and Onto, Inverse Functions
|
7.3-7.4
|
|
|
3/28
|
Composition
|
7.5
|
|
|
3/31
|
Cardinality
and Countability
|
7.6
|
|
|
4/2
|
Application:
Finite-State Automata
|
|
HW6
due
|
|
4/4
|
Relations
on Sets
|
10.1
|
HW7
|
|
4/7
|
Reflexivity,
Symmetry and Transitivity
|
10.2
|
|
|
4/9
|
Equivalence
Relations
|
10.3
|
|
|
4/11
|
Application:
Relational Databases
|
|
HW7
due
|
|
4/14
|
Test 3
|
|
|
|
4/16
|
Test
3 Review
|
|
|
|
4/18
|
O-notation
|
9.2
|
|
|
4/21
|
Application:
Efficiency of Algorithms
|
|
|
|
4/23
|
Review
for Final Exam
|
|
|
|
4/25
|
NO
CLASS
|
|
|
|
5/1
|
EXAM
11:30-2:20
|
|
|
REVIEW QUESTIONS AND
ANSWERS
SAMPLE QUESTIONS