UNIVERSITY AT BUFFALO - STATE UNIVERSITY OF NEW YORK
The Department of Computer Science & Engineering

CSE 191: DISCRETE STRUCTURES Spring 2008

SYLLABUS

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

   ---

2. PREREQUISITES:

   CSE 113 or 115 or permission of the instructor.

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

   ---

3. STAFF:
   Professor:
   Dr. William J. Rapaport, 214 Bell Hall, 645-3180 x 112, rapaport@cse.buffalo.edu
   Office Hours: Mondays, 2:00-2:50 p.m.; Tuesdays, 2:00-2:50 p.m.; and by appointment.

   Teaching Assistants:

   • Ms. Yu Liu (prounounced "yoo leeOO"), Trailer B, Seat 09, 645-3772 or 645-6164 x 151, yl73@buffalo.edu
     Office Hours: Mondays, 1:00-1:50 p.m.; Tuesdays, 4:00-4:50 p.m.; and by appointment.

   • Mr. Muzammil (pronounced "mooZAMmil") Hussain Syed, Trailer B, Seat 23, 645-3772, mh69@cse.buffalo.edu
     Office Hours: Wednesdays, 1:00-1:50 p.m.; Thursdays, 2:00-2:50 p.m.; and by appointment.

   ---

4. CLASS MEETINGS:

   CLASS	INSTR.	REG. #	DAYS	HOURS	LOCN
   Lecture	Rapaport	189244	MWF	9:00-9:50 a.m.	Knox 110
   Recitation R1	Yu Liu	244811	T	8:00-8:50 a.m.	Park 146
   Recitation R2	Muzammil Hussein	086739	W	12:00 noon - 12:50 p.m.	Baldy 117
   Recitation R3	Muzammil Hussein	300070	Th	3:00-3:50 p.m.	Park 146

   Recitations will begin meeting the week of January 22.

   Complete Meeting & Office-Hour Schedule

   
   

   ---

5. TEXTS:
   1. Required:
      • Rosen, Kenneth H. (2007), Discrete Mathematics and Its Applications, 6th Edition (New York: McGraw-Hill)

        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.

   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:
   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	§ in Rosen	HW
   M	Jan	14	What is discrete math?	pp. xx-xxii	HW #1 assigned
   W		16	What is discrete math? (concluded); Propositional Logic	1.1
   F		18	Propositional Logic (cont'd)	1.1 (cont'd)
   M		21	No class: Martin Luther King Day
   T		22	1st meeting of Recitation R1
   W		23	Propositional Equivalences 1st meeting of Recitation R2	1.2	HW #1 due HW #2 assigned
   Th		24	1st meeting of Recitation R3
   F		25	Propositional Equivalences (concluded); Predicates & Quantifiers Last drop/add day	1.2 (concluded); 1.3
   M		28	Predicates & Quantifiers (cont'd)	1.3 (cont'd)
   W		30	Predicates & Quantifiers (concluded)	1.3
   F	Feb	1	Nested Quantifiers	1.4	HW #2 due HW #3 assigned
   M		4	Nested Quantifiers (continued)	1.4 (continued)
   W		6	Nested Quantifiers (concluded); Rules of Inference	1.4 (concluded); 1.5
   F		8	Rules of Inference (cont'd)	1.5 (cont'd)	HW #3 due HW #4 assigned
   M		11	Rules of Inference (concluded); Proofs	1.5 (concluded); 1.6
   W		13	Proofs (cont'd)	1.6 (cont'd)
   F		15	Proofs (cont'd)	1.6 (cont'd)	HW #4 due HW #5 assigned
   M		18	Proofs (cont'd)	1.6 (cont'd); 1.7
   W		20	Proofs (concluded!); Sets	1.7 (concluded!); 2.1
   F		22	Sets (concluded); Set operations	2.1 (concluded); 2.2	HW #5 due; Virtual HW #6 assigned
   M		25	Set operations (cont'd)	2.2 (cont'd)
   W		27	Set operations (concluded); Review for Mid-Term Exam	2.2 (concluded)
   F		29!	Review for Mid-Term Exam (concluded)		HW #6 answers will be posted
   M	Mar	3	MID-TERM EXAM (covers §§1.1-2.2)
   W		5	Review of MT Exam
   F		7	Functions	2.3	HW #7 assigned
   M-F		10-14	Spring Break
   M		17	Functions (concluded); Sequences (& Series [Summations])	2.3-2.4 (concluded)
   W		19	Mathematical Induction	4.1
   F		21	Recursive Definitions	4.3	HW #7 due; HW #8 assigned
   M		24	Recursive Definitions (cont'd)	4.3 (cont'd)
   W		26	Recursive Definitions (cont'd)	4.3 (cont'd)
   F		28	Recursive Definitions (concluded); Structural Induction; Last R Day	4.3 (concluded)	HW #8 due; HW #9 assigned
   M		31	Recursive Algorithms	4.4
   W	Apr	2	Recurrence Relations	7.1-7.2
   F		4	Recurrence Relations (concluded)	7.1-7.2 (concluded)	HW #9 due; HW #10 assigned
   M		7	Relations	8.1
   W		9	Relations (concluded)	8.1 (concluded)
   F		11	n-ry Relations; Representing Relations; Closures of Relations	8.2-8.4	HW #10 due; HW #11 assigned
   M		14	Closures (continued)	8.4
   W		16	Closures of Relations (concluded); Equivalence Relations; Partial Orderings	8.4-8.6
   F		18	Graphs	9.1-9.2	HW #11 due; HW #12 assigned
   M		21	Graphs (concluded)	p.627, Ex.11; §9.5 to p.640; §9.6, esp. pp.653-655; §9.7 to p.663; §9.8
   W		23	Trees	10.1-10.2
   F		25	Tree Traversals	10.3
   M		28	Last Class: Summary & Review
   T-W		29-30	Reading Days
   F	May	2	FINAL EXAM: 8-11 a.m. Hochstetter 114

   ---

7. READING:

   "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 "The more you read, the more intelligent you are. It's really that simple." — Ethan Hawke

   1. There are a lot of topics to cover, and not nearly as many lectures as there are topics. 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.

   2. Moreover, not all material in the text will be covered in lecture: 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.

   3. No matter how far we stray from the tentative schedule, if you do the readings at the assigned times, you will be able to finish everything by the end of the semester.

   4. I will expect you to have read each section before the first day of my lecture on it.

   5. I strongly recommend that you re-read each section after my lectures on it.

   6. Mathematics is an active discipline; you learn it best by doing. 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. (However, DO NOT CHEAT!— see below.)

   7. For advice on how to read writings in mathematics in particular, and any academic discipline in general, see "How to Read (a Computer Science Text)".

   ---

8. HOW TO STUDY:

   • For general advice on how to study for any course, see my web page, "How to Study".

   ---

9. ATTENDANCE, EXAMS, HOMEWORKS, LISTSERV:
   1. You will be expected to attend all lectures and recitations, and to complete all readings and assignments on time.

   2. There will be weekly homework assignments, a mid-term exam, and a final exam. Taking both exams is a logically necessary condition for passing the course. No programming will be required.

   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 will be announced in lecture when the HW is assigned.
         HWs will be collected at the start of lecture on the due date.

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

      4. Put your:
         • full name
         • date
         • recitation (R1, R2, R3)

         at the top right-hand side of each page.

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

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

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

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

      9. Your graded HW will be returned in recitation.

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

   5. 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, whoever 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 email Listserv.

   6. Email Listserv:

      You will automatically be placed on an email list (a "Listserv") for the course. If you do not normally read email at the email address that UB has as your official address, please either do so for this course, or else have your mail forwarded. 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.

      You may send questions and comments that are of general interest to the entire class using the Listserv: Just send them to:

      cse191-sp08-list@listserv.buffalo.edu

      You can also send email just to me, at:

      rapaport@cse.buffalo.edu

      In any case, 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 it's spam.

      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.

      The emails will be archived at the listserv website, and I will also archive them at http://www.cse.buffalo.edu/~rapaport/191/S08/EMAIL/.

      For more information, read the Listserv Information webpage.

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

   ---

10. GRADING:
    • All graded work will receive a letter grade:
      • A, A— ("high distinction")
      • B+, B, B— ("superior")
      • C+, C, C— ("average")
      • D+, D ("minimum passing grade")
      • F ("failure").

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

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

    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 Fall 2008 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!

    ---

11. ACADEMIC INTEGRITY:

    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 webpages

    "Academic Integrity: Policies and Procedures",

    which spells out all the details of this, and related, policies, and

    "Academic Integrity" (from the Undergraduate Catalog).

    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 in the PDF document "Obstruction or Disruption in the Classroom".