C-ID Descriptor
Discrete Structures

COMP 122

None

1. Functions, Relations and Sets
   1. Functions (surjections, injections, inverses, composition)
   2. Relations (reflexivity, symmetry, transitivity, equivalence relations)
   3. Sets (Venn diagrams, complements, Cartesian products, power sets)
   4. Pigeonhole principles
   5. Cardinality and countability
2. Basic Logic
   1. Propositional logic
   2. Logical connectives
   3. Truth tables
   4. Normal forms (conjunctive and disjunctive)
   5. Validity
   6. Predicate logic
   7. Universal and existential quantification
   8. Modus ponens and modus tollens
   9. Limitations of predicate logic
3. Proof Techniques
   1. Notions of implication, converse, inverse, contrapositive, negation, and contradiction
   2. The structure of mathematical proofs
   3. Direct proofs
   4. Proof by counterexample
   5. Proof by contradiction
   6. Mathematical induction
   7. Strong induction
   8. Recursive mathematical definitions
   9. Well orderings
4. Basics of Counting
   1. Counting arguments
   2. Sum and product rule
   3. Inclusion-exclusion principle
   4. Arithmetic and geometric progressions
   5. Fibonacci numbers
   6. The pigeonhole principle
   7. Permutations and combinations
   8. Basic definitions
   9. Pascal’s identity
   10. The binomial theorem
   11. Solving recurrence relations
   12. Common examples
   13. The Master theorem
5. Graphs and Trees
   1. Trees
   2. Undirected graphs
   3. Directed graphs
   4. Spanning trees/forests
   5. Traversal strategies
6. Discrete Probability
   1. Finite probability space, probability measure, events
   2. Conditional probability, independence, Bayes’ theorem
   3. Integer random variables, expectation
   4. Law of large numbers

At the conclusion of this course, the student should be able to:

1. Describe how formal tools of symbolic logic are used to model real-life situations, including those arising in computing contexts such as program correctness, database queries, and algorithms.
2. Relate the ideas of mathematical induction to recursion and recursively defined structures.
3. Analyze a problem to create relevant recurrence equations.
4. Demonstrate different traversal methods for trees and graphs.
5. Apply the binomial theorem to independent events and Bayes’ theorem to dependent events

Exams
Quizzes
Programming Projects
Discussions
Class Presentations

Rosen (2006). Discrete Mathematics and its Applications (6th ed.). McGraw-Hill. [ISBN: 0071244743]

Descrete Mathematics. Richard Johnsonbaugh

Sipser (2005). Introduction to the Theory of Computation (2nd ed.). Course Technology. [ISBN: 0534950973]

Lipschutz and Lipson (2007). Schaum's Outline Discrete Mathematics (3rd ed.). McGraw-Hill. [ISBN: 0071470387]

Gaddis, Walters, and Muganda, Starting out with C++: Early Objects, 7th edition (ISBN-13: 978-0-13-607774-9)