CPS 102: Discrete Mathematics for Computer ScienceDepartment of Computer Science, Duke UniversitySpring 2011Instructor: Bo ZhangOffice: D105 LSRCEmail: [email protected]: Xiaoming XuOffice: N006 North BldgEmail: [email protected] InformationLectures: TuTh 2:50PM – 4:05PM, Languages 109Recitation: F 2:50PM – 4:05PM, Languages 109Textbook◦ Discrete Mathematics and Its Applications, 6th Edition, by KennethH. RosenGradingHomework 30%Midterm Exam 1 20% Friday, 02/18, 2:50PM – 4:05PMMidterm Exam 2 20% Friday, 04/01, 2:50PM – 4:05PMFinal Exam 30% Monday, 05/02, 7:00PM – 10:00PMA-: 90% – 91% A: 92% – 100%B-: 80% – 81% B: 82% – 87%: B+: 88%–89%C-: 70% – 71% C: 72% – 77%: C+: 78%–79%D-: 60% – 61% D: 62% – 67%: D+: 68%–69%F: 0% – 59%Late PolicyPlease turn in your homework at the beginning of the class on the day it isdue. Late homework is not accepted. However, one of your lowest homeworkgrade will be dropped.1Collaboration PolicyHomework assignments are done individually, under Duke’s CommunityStandard. No collaboration of any kind is allowed on standard homeworkassignments.Components of Study◦ Fundamentals- Logic, quantifiers- Sets and functions- Mathematical induction- Algorithms and complexities◦ Number Theory- Modular arithmetic- Euclid’s algorithm- RSA cryptosystem◦ Counting- Permutations and combinations, binomial coefficients- Recurrence relations, and solving techniques◦ Discrete Probablity- Probability distribution, random variable- Bayes’ Theorem- Expected value and variance◦ Graph Theory- Basic concepts- Representation of graph, isomorphism- Connectivity- Euler and Hamilton paths, shortest path problems- Application of tree, tree
View Full Document