CPS 102 - Duke University

CPS 102
Discrete Math for Computer Science
Fall 2005

Course Mechanics

What, No Algorithms?

What, No Recitations?

Course Outline & Preparatory Homework

Due Dates

Standard Homework

Teaching Staff and Office Hours

Anonymous Feedback

Web Discussion Forum for this Class

Venues and Dates

  • Lectures: Levine Science Research Center (LSRC) room D106, Tuesdays and Thursdays 10:05-11:20.

  • There is no scheduled recitation session, but please do come to us for help. Please read this explanation.

  • Two in-class exams will be held in D106 during regular class times:
    Exam 1 is on Thursday, October 6.
    Exam 2 is on Tuesday, November 22.

  • The Final Exam  is on Friday, December 16, 2-5 PM in LSRC D106.

Announcements

  • 12/16/05: All grades, including final exam and letter grades for the class, are available on blackboard. They have also been posted to the Registrar's system, and should appear by 6:30 tonight.

  • 12/12/05: All homework grades, grades for exams 1 and 2, and class participation grades are available on blackboard.

  • 12/2/05: I am sorry to say that I will not be able to hold office hours at the regular times on Monday, 12/5, and Wed, 12/7. Please come on Tuesday, or send me mail for a separate appointment.

  • 10/31/05: The date for Exam 2 has changed to Tuesday, November 22. Please let me know as soon as possible if this creates any difficulty.

  • 10/17/05: In homework 3, question 5(a), the phrase "corresponding to Friday the 13th of that month" should be changed to "corresponding to the 13th of that month". Sorry about the typo, which has been fixed in the online version of the assignment.

  • 10/7/05: Exam 1 grades have been posted on blackboard.

  • 9/13/05: The date originally scheduled for in-class Test 1 falls on a religious holiday (Rosh Hashanah). Test 1 is therefore moved to Thursday, October 6th.

  • 9/8/05: The sentence ``If Sergei gets a signing bonus, then he will not receive a higher salary" in homework 1 should read ``If Sergei gets a signing bonus, then he will not receive a high salary.'' Sorry about the typo. I changed the text in the version online.

  • Please read the course mechanics carefully.

Textbook

  • Kenneth H. Rosen. Discrete Mathematics and Its Applications. Fifth Edition. McGraw-Hill, New York, NY, 2003.

 Course Outline, Readings, and Problems for Class Discussion

This course covers basic concepts of discrete mathematics used in computer science. This is not a course ON computer science, but rather a math course FOR computer science. There will be little about algorithms in the modern sense of the world. A separate note explains why.
 

Module

# of Lectures
(Tight Estimate)

Readings

Problems for Class
Introduction 1

---

---

Propositional Logic 1 1.1, 1.2, Note 1 1.1: 2, 10, 12, 16, 22, 30
1.2: 8, 10
Predicate Logic 1 1.3, 1.4, Note 1 1.3: 10, 18, 56
1.4:  6, 20, 28
Inference and Proofs 2 1.5, Note 1, Note 2 1.5: 2, 16, 38
Sets 1 1.6, 1.7 1.6: 8, 10, 18, 26
1.7: 4, 16, 40
Functions 1 1.8 1.8: 2, 12, 16, 18, 22, 34
Integers and Division 1 2.4 2.4: 10abc, 18abc, 28abc, 32, 36

In-Class Exam 1 (Open book, closed notes, problems from Rosen, sections above)

Sequences and Series 1 3.2 3.2: 4, 8, 18, 24, 36
Technical Proof Methods 2 3.1, 3.3 3.1: 2, 16, 24
3.3: 12
Recursion and Trees 2 pp. 256-266 3.4: 4, 8, 22, 48
Basic Counting 1 4.1, 4.2, Note 3 4.1: 8, 16, 22
4.2: 4, 6
Permutations & Combinations 2 4.3, 4.4, 4.5 4.3: 8, 12
4.4: 4, 12
4.5: 2, 12

In-Class Exam 2 (Open book, closed notes, problems from Rosen, sections above not in Exam 1)

Recurrence 2 6.1, 6.2 6.1: 2abc, 8abc
6.2: 2abcd, 4ab
Probability 2 5.1, 5.2, 5.3 5.1: 22, 24, 36
5.2: 2, 26
5.3: 2, 4, 24
Graphs 3 8.1, 8.2, 8.3, 8.4, 8.5 8.1: 10, 18
8.2: 2, 4, 8, 18
8.3: 4, 12, 38, 40
8.4: 2, 12ab, 24
8.5: 4, 32

Final Exam (Open book, closed notes, problems from Rosen, sections above not in Exam 1 or 2)

 

 

Due-Date Calendar (Evolving)

Tuesday Thursday
Aug 30 -- Sep 1 1.1, 1.2
Sep 6 Note 1 (pp1-12) Sep 8 1.3, 1.4, Note 1 (pp12-14)
Sep 13 1.5, Note 2 Sep 15 HW1
Sep 20 1.6, 1.7 Sep 22 1.8
Sep 27

 1.8

Sep 29

HW2, 2.4

Oct 4 2.4, cont'd Oct 6 Test 1
Oct 11 Fall break Oct 13 Welcome back!
Oct 18 3.2 Oct 20 HW3, 3.1, 3.3
Oct 25 3.1, 3.3, cont'd Oct 27 3.3, 3.4
Nov 1 3.3 Nov 3 3.4
Nov 8

HW4, 4.1

Nov 10 4.1
Nov 15 Note 3 Nov 17 4.2, 4.3, 4.4
Nov 22 Test 2 Nov 24 Thanksgiving
Nov 29 5.1, 5.2 Dec 1 5.2, 5.3
Dec 6 5.2, 5.3 Dec 8 HW5, 8.1, 8.2, 8.3
Friday, Dec 16, 2-5PM: Final Exam

 

Standard Homework Assignments

Anonymous Feedback

  • Please give us anonymous feedback on this course here.

Teaching Staff

Carlo Tomasi, Instructor
E-mail address: tomasi@cs.duke.edu
Office Hours: Mon-Thu 1:30-2:00
Office Location: D213 LSRC
Office Phone: (919) 660-6539
FAX: (919) 660-6519

 

Zheng Li, Teaching Assistant
E-mail address: zheng@cs.duke.edu
Office Hours: Tue, Thu, Fri 11:20-12
Office Location: D125 LSRC
Office Phone: (919) 660-6576
FAX: (919) 660-6519