UCSB CMPSC40 — Foundations of Computer Science — Winter 2021

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

Lectures are held on Tuesday and Thursday 14:00-15:15 online via Zoom.
Recorded lectures will be posted on Piazza.

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)

Office Hours

Mine: After lectures TR 15:20-16:00, same Zoom link as lecture.
TAs: See Piazza.


Homework assignments will be posted weekly.
You may work in pairs by collaborating with another student on the homework, however each submission must be yours and written by you only (read the conduct section below). If you elect to work in pairs, please write the name of the collaborator on your homework.
Please note: No late submissions, no make-up exams!

Assignment Due date
Homework 1   pdf source    Monday 11st January 24:00
Homework 2   pdf source    Monday 18th January 24:00
Homework 3   pdf source    Monday 25th January 24:00
Homework 4   pdf source    Monday 1st February 24:00
Homework 5   pdf source    Monday 8st February 24:00
Homework 6   pdf source    Monday 15st February 24:00
Homework 7   pdf source    Monday 22st February 24:00
Homework 8   pdf source    Monday 1st March 24:00
Homework 9   pdf source    Tuesday 9th March 24:00


You may only use the book (chapters we covered), lectures, lecture notes, homework assignments and their solutions.
No other resources and no collaboration of any kind, individual work only.
No late submissions

Final pdfFinal source
Due on Tuesday 16th March 12:00 (noon)

Practice worksheet


The final class grade will consist of the weighted average: 70% Homework + 30% Final Exam. All homework assignments will be given equal weight.
Letter grades: A ≥ 90, 90 > B ≥ 80, 80 > C ≥ 70, 70 > D ≥ 60, 60 > F.


You are required to work on the homework assigments on your own. Please check the policies for expected student conduct of the UCSB catalogue. Note that in particular “It is expected that students attending the University of California understand and subscribe to the ideal of academic integrity, and are willing to bear individual responsibility for their work. Any work (written or otherwise) submitted to fulfill an academic requirement must represent a student’s original work. Any act of academic dishonesty such as cheating or plagiarism, will subject a person to University disciplinary action. Using or attempting to use materials, information, study aids, or commercial “research” services not authorized bythe instructor of the course constitutes cheating. Representing the words, ideas, or concepts of another person without appropriate attribution is plagiarism. Whenever another person’s written work is utilized, whether it be single phrase or longer, quotation marks must be used and sources cited. Paraphrasing another’s work, i.e., borrowing the ideas or concepts and putting them into one’s “own” words, must also be acknowledged. Although a person’s state of mind and intention will be considered in determining the University response to an act of academic dishonesty, this in now way lessens the responsibility of the student."