C-ID Descriptor
Discrete Structures

Descriptor Details

  • Discrete Structures
  • Not Identified
  • 152
  • Not Identified
  • 3.0
  • Not Identified
  • Uploaded: 10/12/2017 04:44:03 PM PDT

This course is an introduction to the discrete structures used in Computer Science with an emphasis on their applications. Topics covered include: Functions, Relations and Sets; Basic Logic; Proof Techniques; Basics of Counting; Graphs and Trees; and Discrete Probability.

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)

  • No
  • Not Identified

  • Not Identified

  • Fifth course in a sequence of courses that is compliant with the standards of the Association for Computing Machinery (ACM).

  • Not Identified

  • Not Identified