CIS 2210 Discrete Structures

Basic Information and Requirements

• Instructor: Prof. Neng-Fa Zhou
• Class hours: 6:30-9:00PM Thursday (room New Ingersoll 238)
• Office hours: 5:00-6:00 Thursday (room Ingersoll 1161)
• Textbook: Discrete Mathematics, 5th ed., by - K. Ross & C. Wright, Prentice-Hall.
• Lecture notes by Prof. Ziegler
• Homework
  • There will be one homework assignment each week. Selected homework questions will be reviewed in class and sample solutions will be given.
• Exams
  • There will be two tests, one midterm exam, and one final exam, all closed-book. Each test counts for 15%, the midterm 30%, and the final exam 40%.
• How to do well in this class?
  • Read the message "To the Student Especially" in the textbook. In short, to do well you need to read ahead, attend classes and participate in class discussions, review notes after class, and study for tests.

B-Prolog Examples

• Set operations

Course Outline and Homework Assignments

1. Weeks 1 & 2: Sets, Sequences, and Functions (Set Operations; Functions; Inverses of Functions; Sequences)
   • H.W. - Chapter 1: Answers to \# 8 questions
     • 1.3 - 1, 3, 5, 8, 9, 11, 13 (Special Sets)
     • 1.4 - 1, 3, 5, 7, 8, 11, 13 (Set Operations)
     • 1.5 - 1, 3, 5, 7, 8, 13 (Functions)
     • 1.6 - 1, 3, 5, 7, 8, 9 (Sequences)
     • 1.7 - 1, 3, 5, 7, 8, 11 (Properties of Functions)
2. Weeks 3 & 4: Elementary Logic (Propositional Calculus; Methods of Proof; Analysis of Arguments)
   • H.W. - Chapter 2:
     • 2.1 - 1, 8, 9, 15 (Introduction)
     • 2.2 - 1, 3, 5, 7, 8, 9, 19 (Propositional Calculus)
     • 2.3 - 5, 7, 8, 9, 13 ((Proofs)
     • 2.4 - 1, 3 8 (Methods of Proofs)
     • 2.5 - 1, 3, 7, 8, 9, 17 (Logic in Proofs)
     • 2.6 - 1, 5, 8, 9a,c, 13 (Analysis of Arguments)
3. Test #1:
4. Weeks 5 & 6: Relations (Relations; Digraphs and Graphs; Matrices; Equivalence Relations and Partitions)
   • H.W. - Chapter 3:
     • 3.1 - 1, 3, 8, 9, 11, 13 (Relations)
     • 3.2 - 1, 3, 8, 9, 10, 11, 15 (Digraohs and Graphs)
     • 3.3 - 3, 5, 8, 11, 15 (Matrices)
     • 3.4 - 1, 5, 7, 8, 13, 15 (Equivalence Relations and Partitions)
     • 3.5 - 1, 3, 5, 8, 15 (The Division Algorithm and integers Mod p)
5. Weeks 7 & 8: Induction and Recursion (Loop Invariants; Mathematical Induction; Recursive Definitions; Recurrence Relations)
   • H.W. - Chapter 4:
     • 4.1 - 8, 9, 11, 17, 19, 21 (Loop Invariants)
     • 4.2 - 1, 5, 7, 8, 13, 17, 19 (Mathematical Induction)
     • 4.4 - 1, 3, 7, 8, 9, 17 (Recursive Definitions)
     • 4.5 - 1, 3, 7, 8, 11, 15 (Recurrence Relations)
     • 4.6 - 1, 7, 8, 11, 13 (More Induction)
6. Weeks 9 & 10: Counting (Basic Counting Techniques; Elementary Probability; Inclusion-Exclusion Principle; Binomial Methods; Counting and Partitions; Independence; Bayes Formula)
   • H.W. - Chapter 5
     • 5.1 - 1, 3, 7, 8, 9, 11, 15 (Basic Counting Techniques)
     • 5.2 - 1, 3, 5, 7, 8, 9, 15, 19 (Elementary Probability)
     • 5.3 - 1, 3, 7, 8, 9, 15, 17 (Inclusion-Exclusion and Binomial Methods)
     • 5.4 - 1, 3, 5, 8, 9, 11 (Counting and Partitions)
     • 9.1 - 1, 3, 7, 8, 9, 13, 17, 19 (Independence in Probability and Bayes Formula)
7. Test #2:
8. Weeks 11 & 12: Boolean Algebra (Boolean Algebras; Boolean Expressions; Logic Networks; Karnaugh Maps: Isomorphism)
   • H.W. - Chapter 10:
     • 10.1 - 5, 7, 8 (Boolean Algebra)
     • 10.2 - 1, 3, 7, 8 (Boolean Expressions)
     • 10.3 - 1, 3, 8 (Logic Networks)
     • 10.4 - 1, 5, 7, 8, 9 (Karnaugh Maps)
     • 10.5 - 1, 3, 5, 8 (Isomorphism)
9. Weeks 13 & 14: Introduction to Graphs and Trees (Graphs; Edge Traversal Problems; Trees; Rooted Trees; Vertex Traversal Problems; Minimum Spanning Trees)
10. Final Examination: May 26, Thursday, 6-8.