UCSB CMPSC40 — Foundations of Computer Science — Winter 2021



Archived content. Lecture material left here for whomever may find it useful.

Course Overview

Introduction to the theoretical underpinnings of computer science.
CS 40 introduces the essential mathematical background necessary for computer science, from logical reasoning to a number of basic constructs of discrete mathematics required to succeed in more advanced courses in the curriculum. It is a 5 unit course instead of the usual 4, and as such requires more study time and commitment.

Prereqs: 16 and Math 4A
Prereq for: 130A, 138, 178

Books: “Discrete Mathematics and Its Applications” by Kenneth H. Rosen, 6th edition or newer.

Topics covered in CS40

  • Propositional and first-order predicate classical logic
  • Proof techniques
  • Mathematical datatypes: Sets, function, relations
  • Set cardinality and countability
  • Induction and recursion, strong induction, structural induction
  • Recursively defined structures
  • Divide-and-conquer type recurrences
  • Combinatorics: Elementary counting
  • Combinatorics: Permutations, combinations, binomial coefficients
  • Modular arithmetic and elementary cryptography
  • The principle of inclusion-exclusion

Lectures and Reading Assignments

Lecture   Topics covered
Week 1 Chapters 1.1-1.3 (propositional logic)
Week 2 Chapters 1.4-1.8 (predicate logic and proof methods)
Week 3 Chapters 2.1-2.3 (sets and functions)
Week 4 Chapters 2.3-2.4 (functions, sequences and summation), additional notes on sequences and summation; chapters 4.1-4.3 (number theory)
Week 5 Lecture notes (Representation of negative integers, Fermat’s little theorem and RSA encryption); chapters 4.4-4.5 (solving congruences and applications)
Week 6 Lecture notes (cardinality and countability)
Week 7 Lecture notes (computability and density); chapters 9.1, 9.5, 9.6 (partial orderings, well orderings and equivalence relations)
Week 8 Chapters 5.1-5.3 (mathematical induction, strong induction, structural induction and recursive structures)
Week 9 & 10 Lecture notes (combinatorics); chapters 6.1-6.5 (combinatorics: counting, combinations and permutations, binomial coefficients and binomial theorem, generalized combinations and permutations)