CS 317 Discrete Information Structures
Fall 2011
TR 12:00-12:50 pm
Instructor: Christine Cheng
EMS 1011 x5170
Office hours: Tuesdays 1-2 pm or by appointment.
Schedule
- 09/06/11: Logic (Sec. 1.1). Propositional equivalences via truth tables and identities (Sec. 1.3).
Handout 1.
- 09/08/11: Propositional equivalences cont'd. Predicates and quantifiers (Sec. 1.4). Handout 2.
Homework 1, due 9/15.
- 09/13/11: Predicates and quantifiers cont'd. Nested quantifiers (Sec. 1.5). Intro to rules of inference (Sec. 1.6). Handout 3.
- 09/15/11: Rules of inference.
Homework 2, due 9/22.
- 09/20/11: Rules of inference cont'd. Proofs (Sec. 1.7, 1.8). Handout 4.
- 09/22/11: Proofs cont'd.
Homework 3, due 9/29.
- 09/27/11: Just a couple more proofs. Stable matchings.
- 09/29/11: Sets (Sec. 2.1, 2.2). Handout 5.
Homework 4, due 10/06.
- 10/04/11: Sets cont'd.
- 10/06/11: Functions (Sec. 2.3). Handout 6.
Homework 5, due 10/13.
- 10/11/11: Functions cont'd. Some tricks.
- 10/13/11: Sample exam discussed.
- First exam is scheduled for October 18. The coverage. A sample exam. You are allowed to have one sheet of regular-sized paper as a "cheat sheet".
- 10/20/11: Mathematical Induction (Sec. 5.1). Handout 7.
Homework 6, due 10/27.
- 10/25/11: Mathematical induction cont'd. Intro to counting (Sec. 6.1). Handout 8.
- 10/27/11: Counting cont'd. Permutations and Combinations. (Sec. 6.3).
Homework 7, due 11/03.
- 11/01/11: Combinations cont'd. Generalized Permutations and Combinations. (Sec. 6.5).
- 11/03/11: Generalized Permutations and Combinations cont'd. Circular arrangements.
Homework 8, due 11/10.
- 11/8/11: Intro to Probability (Sec. 7.1, 7.2). Handout 9.
- 11/10/11: Conditional probability, independence.
Homework 9, due 11/17. Solutions.
- 11/15/11: Random variables and Expectations. (Sec. 7.4). Handout 10.
- 11/17/11: Expectation and variance.
No homework for next week. Here are some exercises for the topics discussed this week.
- 11/22/11: Exercises on expectation discussed.
- Second exam is scheduled for November 29 (Tu). The coverage. A sample exam. Once again, you are allowed to have one sheet of regular-sized paper as a "cheat sheet". I strongly encourage that you work on the exam first before you take a look at the solutions. And if you do make a mistake, figure out why it's wrong. Remember, you can learn a lot from your mistakes!
- 12/1/11: Intro to graphs (Sec. 10.1, 10.2, 10.3). Handout 11.
Homework 10, due 12/13 (Tuesday). Please note the due date!
- 12/6/11: Graph Isomorphism. Connectivity. Euler trails and circuits (Sec. 10.4, 10.5). Handout 12.
- 12/8/11: Euler trails and circuits cont'd.
- 12/13/11: Sample Final discussed.
- Final exam is scheduled for Dec. 16 (Fri) from 12:30-2:30 PM, same room. The exam is comprehensive -- all topics from the first two exams together with graphs are included. You are allowed to bring one cheat sheet during the exam.