CMPSC 40: Foundations of Computer Science
This course introduces you to the discrete mathematics needed to successfully complete your computer science degree.
Catalog Description
Propositional and predicate logic, set theory, functions and relations, counting, mathematical induction and recursion.
Prerequisites
Computer Science 10 or 12; and Mathematics 3C.
Why have a lower division course on mathematical foundations?
To prepare computer science students for the mathematical knowledge and maturity required by some upper division courses, such as the courses on algorithms and the course on automata and formal languages.
It also can be argued that any educated person in an information economy should have a basic grasp of logic.
Course Goals
To learn and be able to apply basic knowledge of:
- logic
- sets
- relations
- recursion & induction
- counting.
As an instructor, my goals are to 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 on your own some additional topics that are of interest to you. Self-directed learning, like any skill, takes practice. Persevere. Self-directed learning does not mean that you cannot talk to people. It means that you take personal responsibility for organizing and 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
- Logic & Proofs
- Propositional Logic
- Propositional Equivalences
- Predicates and Quantifiers
- Nested Quantifiers
- Rules of Inference
- Introduction to Proofs
- Proof Methods and Strategy
- Sets and Functions
- Sets
- Set Operations
- Functions
- The Growth of Functions
- Complexity of Algorithms
- Modular Arithmetic
- Relations
- Relations and Their Properties
- n-ary Relations and Their Applications
- Representing Relations
- Equivalence Relations
- Partial Orderings
- Induction and Recursion
- Mathematical Induction
- Strong Induction
- Recursive Definitions and Structural Induction
- Counting
- The Sum and Product Principles
- The Pigeonhole Principle
- Permutations and Combinations
- Binomial Coefficients
- Recurrence Relations
- Divide-and-Conquer Algorithms and Recurrence Relations
- Inclusion-Exclusion
- Applications of Inclusion-Exclusion
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.
Discussions & Lectures
| Lecture | PSYCH 1902 | Monday, Wednesday, Friday | 13:00 - 13:50 |
| Discussion | 932, room 101 | Thursday | 14:00 - 14:50 |
| Discussion | 387, room 104 | Friday | 10:00 - 10:50 |
Please email Peter Cappello comments about what you would like to see in future lectures, so that he can better accommodate your wishes.
Required Text
Discrete Mathematics and Its Applications, 6th edition, Kenneth Rosen, McGraw-Hill, ISBN-13 978-0-07-288008-3, ISBN-10-0-07-288008-2, 2007.
Office Hours
| Pete Cappello | cappello@cs.ucsb.edu | Harold Frank Hall, 2157 |
|
| Yuanyang Zhang | yuanyang@cs.ucsb.edu | Phelps 1413 |
|
| Varsha Parthasarathy | varsha@cs.ucsb.edu | GSL |
|