# 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

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 |

### Grading

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.

### Conduct

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.“