Spring 2023

Brown University

CSCI 0220 provides a foundation in discrete math and probability theory. Key topics include logic, set theory, number theory, combinatorics, graph theory, and probability. No prior math background assumed. Aims to develop problem solving, communication, and collaboration skills. Introduces new concepts and ways of thinking to enable analyzing problems arising in computer science. Beginner-friendly introduction to core mathematical concepts underlying many aspects of CS.

I don't know about you, but we're feeling 22! This class gives you the tools to explore interesting questions and convince yourself and others of their answers. You'll be introduced to new worlds of ideas and ways of thinking. We'll learn about Set Theory, Logic, Number Theory, Combinatorics, Graph Theory, and Probability. If these topics sound unfamiliar, not to fear: you're in exactly the right place! This course assumes no prior experience with these topics.

Our expectations from you

- No mathematical background is assumed. We’re not doing calculus, statistics, ...
- Approach things with an open mind.
- Try to communicate clearly and concisely.
- Respect your classmates and TAs: we’re in this together.
- Let us know how you’re doing!

CS can feel like a very applied field. Why learn math?

- Problem solving
- Communication
- Collaboration

A key result of this class: you’ll have a vocabulary for discussing certain kinds of problems that appear in many different contexts, and a toolbox of general approaches for solving them.

A vital point of computer science (academic, industry, hobbyist): *communication*.

Mathematics for Computer Science — Lehman, Leighton, Meyer

Reading (and purchasing!) this textbook is not required, though many students in the past have found it helpful in reinforcing what's covered in lecture!

Lecture slides available at Lectures

No videos available

Assignments available at Assignments

Resources available at Resources

Bijection, injection and surjectionBinary relationBinomial theoremConditional probabilityConjunctive normal form (CNF)Disjunctive normal form (DNF)ExpectationFirst-order logicGraph theoryIndependence (probability theory)Mathematical inductionModular arithmeticNumber theoryProbability theoryProof by contradictionPropositional calculus (Propositional logic)Quantifier (logic)RSA (cryptosystem)Random variableRandom walk on graphsRelation (mathematics)Set theoryStatement (logic)The Pigeon Hole PrincipleTree (graph theory)Truth table