CCS CS 2: Foundations of Computer Science

This course is intended to increase your ability to think and communicate like a mathematician, and to appreciate the value of that skill.

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.

For the first time, this course will have a workload that is comparable to a 5-unit course, which constitutes a 25% increase. This extra load is devoted to 2 ancillary topics: elements of:

Textbook

References

Major Topics Covered in the Course

  1. Logic
    1. Propositional Logic
    2. Propositional Logic Applications
    3. Propositional Equivalences
    4. Predicates & Quantifiers
    5. Nested Quantifiers
    6. Rules of Inference:
      1. Propositional Calculus
      2. Predicate Calculus
    7. Introduction to Proofs
    8. Proof Methods & Strategy
  2. Basic Structures: Sets & Functions
    1. Sets
    2. Set Operations
    3. Functions
  3. Algorithms
    1. Algorithms
    2. The Growth of Functions
    3. Complexity of Algorithms
  4. Number Theory & Cryptography
    1. Divisibility & Modular Arithmetic
  5. Induction & Recursion
    1. Mathematical Induction
    2. Strong Induction & Well Ordering
    3. Recursive Definitions & Structural Induction
    4. Recursive Algorithms
  6. Counting
    1. The Product and Sum Rules of Counting
    2. The Basics of Counting
    3. The Pigeon Hole Principle
    4. Permutations & Combinations
    5. Binomial Coefficients
    6. Generalized Permutations & Combinations
  7. Discrete Probability - covered in PSTAT 120A
  8. Advanced Counting Techniques
    1. Applications of Recurrence Relations
    2. Divide-and-Conquer Algorithms & Recurrence Relations
    3. Inclusion-Exclusion
    4. Applications of Inclusion-Exclusion
  9. Relations
    1. Relations & Their Properties. Some exercises.
    2. Representing Relations.
    3. Equivalence Relations.
    4. Partial Orderings

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.