CS 217-002 Discrete Information Structures

Fall 2004
TR 4:00 - 5:15 pm, PHY 145
Instructor: Christine Cheng
EMS 1045 x5170

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.