The Department of Computer Science & Engineering
 CSE 191: DISCRETE STRUCTURES Fall 2010

## SYLLABUS

This is a living document; the latest version will always be available on the Web at:
`http://www.cse.buffalo.edu/~rapaport/191/F10/syl.html`

 Last Update: 20 August 2010 Note: or material is highlighted

 Index: Other Relevant Links: Course Description CSE 191 homepage Prerequisites Directory of Documents Staff Email Archive Class Meetings UB Learns for CSE 191 Texts Important Dates & Tentative Schedule Reading How to Study "Rules of the Road": Attendance, Exams, Homeworks, Email Grading Incompletes Academic Integrity Classroom Disruptions

1. COURSE DESCRIPTION:

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.

2. PREREQUISITES:

CSE 113 or 115 or permission of the instructor.

No programming will be required, but you will be expected to understand various high-level programming-language algorithmic techniques, structures, and terminology from an introductory computer-science or programming course.

3. STAFF:

4. CLASS MEETINGS:

5. TEXTS:

1. Required:

2. Recommended:

1. Lipschutz, Seymour; & Lipson, Marc Lars (2007), Schaum's Outline of Theory and Problems of Discrete Mathematics, 3rd Edition (New York: McGraw-Hill); ISBN=0071470387.

2. Lipschutz, Seymour; & Lipson, Marc Lars (1992), Schaum's 2000 Solved Problems in Discrete Mathematics (New York: McGraw-Hill); ISBN=0070380317.

6. IMPORTANT DATES & TENTATIVE SCHEDULE:

Note: As the semester progresses, I will adjust some of the dates below to reflect what we actually do in class, rather than on what I hope to do :-)

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
1.1
F   3   Propositional Logic (cont'd):
• syntax & semantics
• truth tables

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)
• truth tables;
• translation
Propositional Equivalences

1st meeting of Recitation A2

1.1–1.2
Th   9   No Classes: Rosh Hashanah
F   10   Propositional Equivalences (cont'd)

1.2 HW #1 due
HW #2 assigned
M   13   HOW TO STUDY MATH;

Propositional Equivs (cont'd);

1.2–1.3
W   15   Preds & Qfrs 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)
Nested Qfrs
1.3;
1.4;

W   22   Nested Qfrs (cont'd)
Peano's axioms
1.4;
p. A-5

F   24   Peano's Axioms (cont'd);
Rules of Inf.
1.5–1.6 HW #3 due;
HW #4 assigned
M   27   Rules of Inf. (cont'd);
Proofs
1.5–1.6
W   29   Rules & Pfs (cont'd) 1.5–1.6
F Oct. 1   Pfs (cont'd) 1.6–1.7 HW #4 due;
HW #5 assigned
M   4   Pfs (cont'd) 1.7
W   6   Pfs (cont'd) 1.7
F   8   Pfs (cont'd) 1.7 HW #5 due;
Virtual HW #6 assigned
M   11   Pfs (cont'd)

Announce Mid-Term Exam!

1.7
W   13   Pfs (cont'd) 1.7
F   15   Review for Mid-Term Exam
M Oct 18   MID-TERM EXAM
(will probably cover §§1.1–1.7)
clock

W   20   Review of Mid-Term Exam
+ mid-semester course evaluation
HW #7 assigned
F   22 SET THEORY Sets 2.1
M   25   Sets (cont'd);
Set operations
2.1–2.2
W   27   Set opns (cont'd) 2.2
F   29   Set opns (cont'd) 2.2 HW #7 due;
HW #8 assigned
M Nov. 1 FUNCTIONS Functions 2.3
W   3   Functions (cont'd) 2.3
F   5   Functions (cont'd) 2.3 HW #8 due;
HW #9 assigned
M   8
RECURSION
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 HW #9 due;
HW #10 assigned
M   15   Math. Ind'n (cont'd);
Recursive Definitions
4.1;
4.3;

W   17   Rec. Defs (cont'd);
4.3
F   19   Recurrence Relations 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.3, pp. 541–542
W Dec. 1

GRAPHS
Rel'ns (cont'd):
equivalence rel'ns;
rep'g rel'ns w/ digraphs

§8.5
§8.3, pp. 541–542

F   3   Rel'ns: rep'n via digraphs (cont'd) §8.3, pp. 541–542 HW #11 due;
Virtual HW #12 assigned
M   6   Graphs:
basic defs;
Euler paths & circuits;
Traveling Salesman Problem

§9.1
§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

M–M   13–20   Exam Week:

ASSUME THE WORST,
NAMELY,
THAT OUR EXAM
WILL BE ON
THE LAST DAY

"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

But…

"To read critically is to read skeptically. The reader [should] ask…not only, ‘Do I understand what this means?’ but ‘Do I buy it?’ " — Kenneth S. Goodman

8. HOW TO STUDY:

1. Attendance:

2. Assignments:

1. There will be weekly homework assignments, a mid-term exam, and a final exam.

2. Taking both exams is a logically necessary condition for passing the course.

3. No programming will be required.

4. PLEASE KEEP ALL OF YOUR WORK TILL THE END OF THE SEMESTER!

3. Homeworks (HW):

1. HW assignments will be of the "paper-and-pencil" variety,
to be done outside of class.

2. The purposes of HW are:

1. to give you practice in applying the concepts covered in the course
2. to give you a chance to assess the level of your understanding

3. Due dates & late HWs:

1. Due dates will be announced in lecture when the HW is assigned.

2. HWs will be collected at the start of lecture on the due date.

3. If you try to hand yours in after they have been collected
(e.g., at the end of lecture, in my mailbox, in the TA's mailbox, etc.),
it will not be accepted.

4. To repeat:

NO LATE HOMEWORKS WILL BE ACCEPTED

This is so that the HW can be discussed in the class period when it is due.

5. If you know now that you will regularly be late, see me to make alternative arrangements for turning in your work.

4. HW Format:

1. Put your:

• full name
• date
• recitation (A1, A2, A3, A4)

at the top right-hand side of each page.

2. Secure all pages with a staple (not a paper clip, etc.) in the top left-hand corner.

3. Each HW problem solution should consist of:

• a restatement of the entire problem (you may copy it word for word),
• followed by a complete solution with all intermediate steps shown.

5. The lowest HW grade will be dropped.
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.

2. If you have a question about the HW,
you may ask your TA or me at any time during the semester,
preferably during recitation or office hours.

3. If you think that a HW grade is incorrect or "unfair",
you must let your TA or me know within 1 week of the date that the HW is returned to you.

7. Just as you cannot expect to learn how to drive a car by reading about it or by watching other people do it, the same holds true for doing mathematics.

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.

8. All homeworks and other important information will be announced in lecture.

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.

4. Email:

1. You will automatically be placed on the UB Learns email list for the course.
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.

3. You may send questions and comments that are of general interest to the entire class using the UB Learns email list. You can also send email just to me, at:

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.

4. If you send email just to me that I deem to be of general interest, I will feel free to remail it to the email list along with my reply unless you explicitly tell me that you want to remain anonymous, in which case I may choose to remail it to the email list preserving your anonymity.

5. The emails will be archived at:
http://www.cse.buffalo.edu/~rapaport/191/F10/EMAIL/.

5. Students with Disabilities:
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).

• A, A– ("high distinction")
• B+, B, B– ("superior")
• C+, C, C– ("average")
• D+, D ("minimum passing grade")
• F ("failure").

2. If you think that a HW grade is incorrect or "unfair",
you must let your TA or me know within 1 week of the date that the HW is returned to you.

Clerical errors by the TAs or me on HWs,
and incorrect or "unfair" grades on exams,
can be adjusted at any time.

3. Your final course grade will be calculated as a weighted average of all letter grades according to the following weights:

Total 100% Recitation Assignments(including attendance, HWs, quizzes) 40% Mid-Term Exam 20% Final Exam 40%

For information on my philosophy of grading, see my web document on "How I Grade"

#### 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
semester.

(I will not be here during the Fall 2011 semester.)

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.

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".

12. CLASSROOM DISRUPTIONS: In large classes (but surely not ours :-), students have been known to be disruptive, either to the instructor or to fellow students. The university's policies on this topic, both how the instructor should respond and how students should behave, may be found at: "Obstruction or Disruption in the Classroom".