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 realnumber 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 discretemathematical 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 discretemathematical 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 firstorder 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 setmembership relation [∈] between them); so, we will study set theory.
Then we'll use the language of logic and the set datatype 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 highlevel programminglanguage algorithmic techniques, structures, and terminology from an introductory computerscience or programming course.
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 
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: McGrawHill); 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 :)
DAY  MONTH  DATE  TOPICS  SUBTOPICS  § 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:

1.1  
F  3 
Propositional Logic (cont'd):
Recitations begin next week! 
1.1–1.2  
M  6  No class: Labor Day  
T  7  1st meeting of Recitation A1  
W  8 
Propositional Logic (cont'd)
1st meeting of Recitation A2 
1.1–1.2  
Th  9  No Classes: Rosh Hashanah  
F  10 
Propositional Logic (cont'd)
Last drop/add day 
1.2 
HW #1 due HW #2 assigned 

M  13 
HOW TO STUDY MATH; Logical Equivalence (cont'd) 
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. A5 
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)
Announce MidTerm Exam! 
1.6  
W  13  Proof Strategies (cont'd)  1.6–1.7  
F  15  Review for MidTerm Exam  
M  Oct  18 
MIDTERM EXAM will cover §§1.1–1.6 clock digital clock 

W  20 
Review of MidTerm Exam
+ midsemester 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)
Last R Day 
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):

§8.5
§8.3, pp. 541–542 

F  3 
Graphs:
Rel'ns: rep'n via digraphs 
§8.3, pp. 541–542; 9.1 
HW #11 due;
Virtual HW #12 assigned 

M  6 
Graphs (cont'd):
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
"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… "The more you read, the more intelligent you are. It's really that simple." — Ethan Hawke 

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,
plus
occasionally material that is not in the text.
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,
checking each other's answers.
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 righthand 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 timeconsuming, so please consider your other commitments, and plan your time accordingly.
Therefore, be
sure to get a classmate's phone number or email address
(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.
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,
beginning with
"CSE 191",
so that my mailer doesn't think that it's spam.
Clerical errors by the TAs or me on HWs,
and incorrect
or "unfair" grades on exams,
can be adjusted at any time.
Recitation Assignments (including attendance, HWs, quizzes) 
40% 
MidTerm Exam  20% 
Final Exam  40% 
Total  100% 

For information on my philosophy of grading, see my web document on "How I Grade"
Any incompletes that I might give,
in a lapse of judgment :), will have to be made up by the end of the
(I will not be here during the Fall 2011 semester.) 

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,
see your TA or Prof. Rapaport.
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".