The Department of Computer Science & Engineering |
CSE 191:
DISCRETE STRUCTURES Fall 2010 |
http://www.cse.buffalo.edu/~rapaport/191/F10/syl.html
Last Update: 8 December 2010
Note: or material is highlighted |
This course covers various topics in "discrete" (as opposed to "continuous") mathematics:
The differential and integral
calculus that you study in MTH 141–142 covers "continuous"
mathematical topics in the sense that it analyzes data whose values can
be real numbers.
The real-number line
has no gaps in it.
On the other hand, this course covers "discrete" mathematical topics in the sense that it analyzes data whose values are "separated", like the integers. The integer number line has gaps.
(Compare an analog clock—one with hands—with a digital clock: With the former, every point on the circle that is the "face" of the clock represents a time that one of the clock's hands can point to—there are no gaps. With the latter, not every time between any two times is represented (e.g., there's no time between 11:50 and 11:51). Analog clocks are "continuous"; digital clocks are "discrete".)
This course provides some of the mathematical foundations and skills that you will need in your further study of computer science and engineering. The central concept of computer science is that of an algorithm. Algorithms are discrete-mathematical objects. To understand an algorithm, you need to appreciate that it is a formal mathematical entity, not a program in a particular language; it is based on the discrete-mathematical notion of recursion. To design an algorithm, you need to know logic, set theory, relations, functions, graph theory, and other discrete structures. To verify that an algorithm works correctly, you need mathematical rigor and good proof techniques—in particular, mathematical induction. These are the areas covered by this course.
We will begin with a study of logic (propositional and first-order predicate logics), a subject that is at the foundation of mathematics and computer science. Logic can be considered as what AI researchers call a language for knowledge representation and reasoning. As a language, it enables us to talk precisely about anything in mathematics, just as a programming language enables us to talk precisely about computational procedures.
But we need objects to talk about. We will see that we can represent any mathematical or computational object in terms of a single data type: sets (along with their members and the set-membership relation [∈] between them); so, we will study set theory.
Then we'll use the language of logic and the set data-type to investigate relations among objects, including recursive relations (which are at the heart of computer science), as well as investigating functions (which are a special kind of relation)—and computable functions are what computer science is all about.
Finally, as time permits, we'll use logic, set theory, and relations to discuss graphs and trees, yet another very general and useful data type.
CSE 113 or CSE 115.
No programming is
required, but it would be helpful if you understand various high-level
programming-language algorithmic
techniques,
structures, and terminology from an introductory computer-science or
programming course.
Office Hours:
Mondays & Tuesdays, 2:00–2:50 P.M.
and by appointment.
Office Hours:
Tuesdays,
12:00 NOON–12:50 P.M.,
and by appointment.
Office Hours:
Fridays, 3:00–3:50 P.M.,
and by appointment.
Office Hours:
Thursdays, 1:00–2:50 P.M.,
and by appointment.
Recitations will begin meeting the week of September 6.
which is supposed to be packaged together with:
Grossman, Jerrold (2007),
Student Solutions Guide to Accompany Discrete Mathematics and
Its Applications, 6th Edition
(New York: McGraw-Hill);
combined ISBN=0073503177.
Note:
I have adjusted some of the dates and assignments below to reflect what
we actually did in class, rather than on what I had planned or hoped to
do :-)
Recitations begin next week!
1st meeting of Recitation A2
Last drop/add day
Logical Equivalence (cont'd)
Announce Mid-Term Exam!
Last R Day
"You can lead a horse to water, but you can't make him drink."
— American Proverb
"You can lead a horse to water, but you must convince him it is water
before there is any chance he will drink." — Albert Goldfain
"Education is not filling a bucket, but lighting a fire"
— William Butler Yeats
"Reading is to the mind what exercise is to the body."
— Sir Richard Steele
Therefore…
Consequently, in lectures, I will only be able to
skim the surface of the issues.
But I will assign a lot of reading,
which I will expect you all to do.
In
lecture, we shall only cover interesting or difficult material, You are
responsible for all material in the text and in the
lectures.
Therefore, you should try all exercises whose answers are given in the
text. And there are 3 supplementary texts with extra exercises. You
might want to consider forming study groups to practice solving
problems, (However, DO NOT
CHEAT!—see below.)
If you can't answer
that question, then ask for help.
This is so that the HW can be discussed in the class period when
it is due.
at the top right-hand side of each page.
Do your work on time—this is one course you simply cannot
cram for at the last minute, so don't even try! I cannot stress this
strongly enough. Remember that the homeworks may be fairly
time-consuming, so please consider your other commitments, and
plan your time accordingly.
Therefore, be
sure to get a classmate's phone number or email address
Announcements may also be posted to the course website or the class
email list.
Be sure to send your mail from your buffalo.edu account and
to fill in the subject line,
Clerical errors by the TAs or me on HWs,
For information on my philosophy of grading, see my web document on "How I Grade"
For more information on Incomplete policies, see the Undergraduate
Catalog
"Explanation of Grades" (scroll down to "Incomplete
Grades"). Note that my policy on when a grade of Incomplete must be
completed differs from the University policy!
Although it is acceptable to discuss general
approaches with your fellow students, the work you turn in must be your
own.
It is the policy of this department that any violation of
academic integrity will
result in an F for the course, that all departmental
financial support including teaching
assistantships, research assistantships, or scholarships
be
terminated, that notification of this
action be placed in the student's confidential
departmental record, and that the student be
permanently ineligible for future departmental financial
support.
If you need help doing the assignments,
Please be sure to read the
UB webpage
and the
CSE webpages
which spells out all the
details of this, and related, policies.
For some hints on how to avoid
plagiarism when writing essays for courses, see my website
"Plagiarism".
CLASS
INSTR.
REG. #
DAYS
HOURS
LOCN
Lecture
Rapaport
031018
MWF
12:00 NOON–12:50
P.M.
NSC 215
Recitation A1
Hsieh
417490
T
1:00–1:50 P.M.
Knox 109
Recitation A2
Yao
056153
W
11:00–11:50 A.M.
Baldy 108
Recitation A3
Yao
162436
Th
8:00–8:50 A.M.
Bell 138
Recitation A4
Xu
426093
Th
4:00–4:50 P.M.
Capen 260
DAY
MONTH
DATE
TOPICS
SUB-TOPICS
§ in Rosen
HW
M
Aug
30
DISCRETE MATH
Intro. to course;
What is discrete math?
pp. xx–xxii
HW #1 assigned
W
Sep.
1
LOGIC
What is discrete math? (cont'd);
Propositional Logic:
As a formal language
Lecture Notes
1.1
F
3
Propositional Logic (cont'd):
Lecture Notes
1.1–1.2
M
6
No class: Labor Day
T
7
1st meeting of Recitation A1
W
8
Propositional Logic (cont'd)
Lecture Notes
1.1–1.2
Th
9
No Classes: Rosh Hashanah
F
10
Propositional Logic (cont'd)
Logical Equivalence
1.2
HW #1 due
HW #2 assigned
M
13
HOW TO STUDY MATH;
1.2–1.3
W
15
Logical Equivalence (cont'd);
Propositional Equivalences;
Predicates & Quantifiers
1.3
Th
16
1st meetings of Recitations A3 & A4
F
17
Preds & Qfrs (cont'd)
1.3
HW #2 due
HW #3 assigned
M
20
Preds & Qfrs (cont'd)
1.3
W
22
Preds & Qfrs (cont'd)
1.3–1.4
F
24
Translation (cont'd);
Nested Qfrs
1.4–1.5
p. A-5
HW #3 due;
HW #4 assigned
M
27
Nested Qfrs (cont'd);
Peano's Axioms
1.5–1.6
W
29
Rules of Inference
Proofs
1.6
F
Oct.
1
Rules & Pfs (cont'd)
1.6
HW #4 due;
HW #5 assigned
M
4
Rules & Pfs (cont'd)
1.6
W
6
Rules & Pfs (cont'd)
1.6
F
8
Proof Strategies
1.6
HW #5 due;
Virtual HW #6 assigned
M
11
Proof Strategies (cont'd)
1.6
W
13
Proof Strategies (cont'd)
1.6–1.7
F
15
Review for Mid-Term Exam
M
Oct
18
MID-TERM EXAM
will cover §§1.1–1.6
clock
digital clock
W
20
Review of Mid-Term Exam
+ mid-semester course evaluation
F
22
Proof Strategies (cont'd)
1.7–2.1
HW #7 assigned
M
25
SET THEORY
Sets
2.1–2.2
W
27
Sets (cont'd);
Set operations
2.2
F
29
Set opns (cont'd)
2.2–2.3
HW #7 due;
HW #8 assigned
M
Nov.
1
FUNCTIONS
Set opns (cont'd);
Functions
2.3
W
3
 
Functions (cont'd)
2.3
F
5
Functions (cont'd)
2.3–2.4;
4.1
HW #8 due;
HW #9 assigned
M
8
RECURSION
Functions (cont'd);
Sequences;
Mathematical Induction
2.4;
4.1
W
10
Math. Ind'n (cont'd)
4.1
F
12
Math. Ind'n (cont'd)
4.1;
4.3
HW #9 due;
HW #10 assigned
M
15
Recursive Definitions
4.3
W
17
Rec. Defs (cont'd);
Recurrence Relations
4.3;
7.1
F
19
Recurrence Rel'ns (cont'd)
7.1–7.2
HW #10 due;
HW #11 assigned
M
22
Recurrence Rel'ns (cont'd)
7.1–7.2
W–Sun
24–28
No class: Thankgiving
M
29
RELATIONS
Relations: General definitions
8.1, 8.5
W
Dec.
1
GRAPHS
Rel'ns (cont'd):
equivalence rel'ns
§8.5
§8.3, pp. 541–542
F
3
Graphs:
basic defs;
Rel'ns: rep'n via digraphs
§8.3, pp. 541–542;
9.1
HW #11 due;
Virtual HW #12 assignedM
6
Graphs (cont'd):
Euler paths & circuits;
Traveling Salesman Problem
§9.5 to p. 640
§9.6, esp. pp. 653–655
W
8
Traveling Salesman Problem (cont'd);
4 Color Thm;
Rooted Trees
§9.6, esp. pp. 653–655;
§9.8, esp. p. 668;
§4.3, esp. p. 302
§10.1, esp. p. 685–686
F
10
Last Class:
Summary &
Review
T
14
FINAL EXAM:
8:00–11:00 A.M.
Cooke 121
"Teachers open the door, but you must enter by yourself."
— Chinese Proverb
plus
occasionally material that is not in the text.
if you do the readings at the
assigned times,
you will be able to finish everything by the end of the
semester.
checking each other's answers.
After reading each sentence
and before reading the next,
ask yourself "Why?".
and to
complete all readings and assignments on time.
(click on the link to find out why)
to be done outside of class.
(e.g., at the end of lecture, in my mailbox, in the
TA's mailbox, etc.),
it will not be accepted.
NO LATE HOMEWORKS WILL BE ACCEPTED
You should assume that you
will fail to turn in one HW (oversleep, get stuck in traffic,
etc.)—that's the one that will be dropped.
you may ask your TA or me at any
time during the semester,
preferably during recitation or office hours.
you must let
your TA or me know within 1 week of the date that the HW is returned to
you.
(for instance, 1
or 2
people sitting next to you in class, whomever they are!)
so that you will not miss
announcements in the unlikely event that you miss a class.
I will use this list as my main means of
communicating with you out of class.
And you can use it to communicate with the rest of us.
please either do so for this course, or
else have your mail forwarded.
beginning with
"CSE 191",
so that my mailer doesn't think that it's spam.
http://www.cse.buffalo.edu/~rapaport/191/F10/EMAIL/.
Students should notify
Prof. Rapaport
within the first
two weeks of class if they have a disability which would make it
difficult
to carry out course work as outlined (requiring note-takers, readers,
extended
test time).
you must let
your TA or me know within 1 week of the date that the HW is returned to
you.
and incorrect
or "unfair" grades on exams,
can be adjusted at any time.
Recitation Assignments
(including attendance, HWs, quizzes)40% Mid-Term Exam 20% Final Exam 40% Total 100% Incompletes:
It is University policy that a grade of Incomplete
is to be given only when a small amount of work or a single exam is
missed due to circumstances beyond the student's control, and that
student is otherwise doing passing work. I will follow this policy
strictly! Thus, you should assume that I will not give
incompletes :-)
Any incompletes that I might give,
in a lapse of judgment :-),
will have to be made up by the end of the
Spring 2011
(I will not be here during the Fall 2011 semester.)
see your TA or Prof. Rapaport.