CS 217-002 Discrete Information Structures
Fall 2004
TR 4:00 - 5:15 pm, PHY 145
Instructor: Christine Cheng
EMS 1045 x5170
Office hours: TR 3-4 PM or by appointment.
Syllabus of the course.
Schedule
- 9/2/04: Logic (Sec. 1.1)
- 9/7/04: Propositional Equivalences (Sec. 1.2), Truth Tables and SAT problems.
- 9/9/04: Rules of Inference (Sec. 1.5), Intro to Predicates (Sec.
1.3). HW 1 (due 9/23, Th, in class).
- 9/14/04: Predicates and Quantifiers (Sec. 1.3, 1.4). Intro to
Rules of Inference for Predicates (Sec. 1.5).
- 9/16/04: Rules of Inference for Predicates (Sec. 1.5). Sets (Sec.
1.6). HW 2 (due 9/23, Th, in class)
- 9/21/04: Set Operations (Sec. 1.7).
- 9/23/04: Functions (Sec. 1.8). HW 3 (due
10/7, Th, in class)
- 9/28/04: Functions cont'd. Intro to Relations (Sec. 7.1).
- 9/30/04: Equivalence Classes (Sec. 7.5), Different proof techniques
(Sec. 1.5). HW 4 (due 10/7, Th, in class)
- 10/05/04: Intro to Induction (Sec. 3.3)
- 10/07/04: Induction cont'd. Summation and sequences (Sec. 3.2.) HW 5 (due 10/19, Tu, in class) Note that you only have 1.5 weeks to work on this problem set.
- Solution on class exercises on induction is here.
- 10/12/04: Summations cont'd. Intro to Counting: sum and product rules (Sec.4.1).
- 10/14/04: Review for Midterms.
- MIDTERM 1 on October 19 . Sample Exam . Coverage .
- 10/21/04: Counting continued.
- 10/26/04: Permutations and Combinations. (Sec. 4.3). Intro to Binomial Theorem. (Sec.4.4)
- 10/28/04: Binomial Theorem cont'd. Generalized Permutations and Combinations (Sec. 4.5). HW 6 (due 11/11, Th, in class)
- 11/02/04: Counting with indistinguishable objects. Pigeonhole Principle. Intro to Discrete probability (Sec. 5.1).
- 11/04/04: Discrete probability continued, Intro to general probability theory (Sec. 5.2). HW 7 (due 11/11, Th, in class)
- 11/09/04: Independent events, the Birthday Problem and the Monty Hall Problem. Random Variables and their expected values.
- 11/11/04: Expectation and Variance of Random Variables. HW 8 (due 11/23, Tuesday, in class)
- FINALS is on December 16, Tuesday from 3-5PM. Same room.
- 11/16/04: Intro to graphs. (Sec. 8.1, 8.2 ,8.3).
- 11/18/04: Graph Isomorphism cont'd. Eulerian and Hamiltonian Paths. Reminder: HW 8 is due on Tuesday. HW 9 (due 12/02, Thursday, in class).
- 11/23/04: Hamiltonian Paths cont'd. Applications of Hamiltonian Paths: knight's tour, de Bruijn cycles.
- MIDTERM 2 on December 7 . Sample Exam . Coverage.
- 11/30/04: Graph Coloring. Discussion on old hw.
- 12/2/04: Review of sample exam.
- 12/7/04: Exam II.
- 12/9/04: Exam 2 discussed. Sample Final Exam .
- 12/23/04: Final grades have been posted on PAWS.