CMPSC 40: Foundations of Computer Science

This course introduces you to the discrete mathematics needed to successfully complete your computer science degree. Learning to produce & write mathematical proofs is a central course theme.

Catalog Description

Propositional & predicate logic, set theory, functions & relations, counting, mathematical induction & recursion.

Prerequisites

Computer Science 16 with a grade of C or better & Mathematics 4A with a grade of C or better.

Why have a lower division course on mathematical foundations?

To prepare computer science students for the mathematical knowledge & maturity required by some upper division courses, such as the courses on algorithms & the course on automata & formal languages.

It also can be argued that any educated person in an information economy should have a basic grasp of logic & sets.

Course Goals

To learn & be able to apply basic knowledge of:

The principal application of this knowledge is the ability to comprehend and develop proofs for mathematical statements and to communicate proofs in a clear, precise written form.

As an instructor, I also encourage you to become a more self-directed learner. I believe that the future belongs to those who enjoy learning things for themselves. I consequently hope that you explore some additional topics that are of personal interest. Self-directed learning, like any skill, takes practice. Persevere. Being self-directed does not mean that you cannot talk to people. It means that you take personal responsibility for organizing & executing—in a word, directing—your own learning plan. I would love to discuss any plans you may have or wish to formulate for self-directed learning.

Topics

The slides linked to below are not a substitute for attending lecture. They merely organize the discussion that takes place in class.

  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 & 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-&-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

Written Communication

Students present their solutions to problems in writing on both homework & examinations. Precision & clarity are the coin of this communication realm.

Problem Analysis

This course's essence: Develop mathematical problem-solving skills that you can apply in a variety of intellectual pursuits.

Workload

This is a 4-credit course at UCSB. You are expected to finish this course in 10 weeks, working intelligently for an average of 10 hours/week.

Please email Peter Cappello comments about what you would like to see in future lectures, so that he can better accommodate your wishes.

Office Hours

Pete Cappello cappello@cs.ucsb.edu Harold Frank Hall, 2157
  • TBD
  • By appointment

 cappello@cs.ucsb.edu © Copyright Peter Cappello                                           2018.08.28