Course Description

Current Catalog description

Mathematical foundations of computer science: Introduction to propositional and predicate logic, set theory, functions and relations, mathematical induction and recursion, and an introduction to combinatorics.

Textbook

Discrete Mathematics and Its Applications, 6th Edition, Kenneth H. Rosen, McGraw-Hill, 2007.

References

Applied Combinatorics, 5th Edition,  Alan Tucker, John Wiley, 2007.

Extending the Frontiers of Mathematics, inquiries into proof and argumentation, Edward B. Burger, Key College Publishing (Springer), 2007.

Major Topics Covered in the Course

  1. Logic
    1. Propositional Logic
    2. Propositional Equivalences
    3. Predicates & Quantifiers
    4. Nested Quantifiers
    5. Rules of Inference:
      1. Propositional Calculus
      2. Predicate Calculus
    6. Introduction to Proofs
    7. Proof Methods & Strategy
  2. Set & Set Operations
  3. Relations
    1. Relations & Their Properties - Rosen 8.1 exercises 10, 20, 30, 40, 50.
    2. Representing Relations - Rosen 8.3 exercises 10, 20, 30.
    3. Closures of Relations - Rosen 8.4 exercises 10, 20, 30.
    4. Functions
    5. Equivalence Relations - Rosen 8.5 exercises  10, 20, 30, 40, 50.
    6. Partial Orderings
  4. Algorithms - Rosen 3.1 exercises 10, 20, 32, 40, 50, 60.
  5. The Growth of Functions - Rosen 3.2 exercises 10, 20, 30, 40, 44.
  6. Complexity of Algorithms - Rosen 3.3 exercises 10, 20.
  7. Induction & Recursion
    1. Mathematical Induction
    2. Recursive Definitions and Structural Induction - Rosen 4.3 exercises 10, 20, 30, 40, 50.
  8. General Counting Methods for Arrangements & Selections
    1. 2 Basic Counting Principles - Tucker 5.1 exercises 1, 5, 11, 15, 20, 25, 30, 34, 40, 45, [optional: 46, 47, 49].
    2. Simple Arrangements & Selections - Tucker 5.2
    3. Arrangements & Selections with Repetitions - Tucker 5.3
    4. Distributions - Tucker 5.4
    5. Binomial Identities - Tucker 5.5
  9. An Introduction to Generating Functions
    1. Generating Function Models - Tucker 6.1
    2. Calculating Coefficients of Generating Functions - Tucker 6.2
  10. Recurrence Relations
    1. Recurrence Relation Models - Tucker 7.1
    2. Divide-and-Conquer Relations - Tucker 7.2
  11. Inclusion-Exclusion
    1. Counting with Venn Diagrams - Tucker 8.1
    2. Inclusion-Exclusion Formula - Tucker 8.2

Oral & Written Communications

Students present their solutions to problems to the class. The presentation combines both oral and written communication. Precision and clarity are the coin of this communication realm.

Problem Analysis

The essence of this course is to develop mathematical problem-solving skills that you can apply in a variety of intellectual pursuits.