UCSB CS40 Winter 2021

CS 40 Foundations of Computer Science

Course Description: 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)
Week 5
Week 6
Week 7
Week 8
Week 9
Week 10

Office Hours

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


Homeworks 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!

Assigment 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 Monday 1st February 24:00
Homework 5 Monday 8st February 24:00
Homework 6 Monday 15st February 24:00
Homework 7 Monday 22st February 24:00
Homework 8 Monday 1st March 24:00


The final class grade will consist of the weighted average: 70% Homework + 30% Final Exam. All homeworks 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.“