CSCI 0220
Discrete Structures and Probability
CSCI 0220 meets Mondays, Wednesdays, and Fridays from 2:00 - 2:50 pm.
I don't know about you, but we're feeling 22!
This class, offered both semesters at Brown University, 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 Logic, Set Theory, Number Theory, Combinatorics, 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.
Important info before the semester starts:
- Exams are in-person, and there will be a total of 3 in-class (non-final) exams and one final exam.
- Lectures will be streamed and recorded; attendance is strongly encouraged.
- Attendance at weekly recitation sections is required.
For the Spring 2026 semester, this class will be taught by professor Robert Lewis. If needed, you can contact him at robert_lewis@brown.edu.
Assignments
Times listed are in EST. Assignments are typically released on Thursdays, and are due 11:59pm on Wednesdays. Clicking on the Overleaf Template link will open a new Overleaf project, so you can write your homework solutions in LaTeX.
| Homework | Template | Released | Due | Solutions |
|---|---|---|---|---|
| HW0 | - | Jan 21 | Jan 28 | - |
| HW1 | Overleaf Template | Jan 29 | Feb 4 | - |
| HW2 | - | Feb 5 | Feb 11 | - |
| HW3 | - | Feb 12 | Feb 20 | - |
| HW4 | - | Feb 19 | Feb 25 | - |
| HW5 | - | Feb 26 | Mar 6 | - |
| HW6 | - | Mar 5 | Mar 11 | - |
| HW7 | - | Mar 12 | Mar 18 | - |
| HW8 | - | Mar 19 | Apr 3 | - |
| HW9 | - | Apr 9 | Apr 15 | - |
| HW10 | - | Apr 16 | Apr 24 | - |
Recitation sections are held on Thursdays and Fridays. Also, if you need to miss a recitation and need to request an absence, fill out the form here.
| Recitation | Template | Released | Solution |
|---|---|---|---|
| Recitation 1 | Overleaf Template | Jan 27 | - |
| Recitation 2 | - | Feb 5 | - |
| Recitation 3 | - | Feb 12 | - |
| Recitation 4 | - | Feb 19 | - |
| Recitation 5 | - | Feb 26 | - |
| Recitation 6 | - | Mar 5 | - |
| Recitation 7 | - | Mar 12 | - |
| Recitation 8 | - | Apr 2 | - |
| Recitation 9 | - | Apr 9 | - |
| Recitation 10 | - | Apr 16 | - |
Lectures
| Lecture | Date | Topic | Recording |
|---|---|---|---|
| 1 | Jan 21 | Intro | Video |
| 2 | Jan 23 | Statements, Proofs, and Contradictions | Video |
| 3 | Jan 26 | Language of Propositional Logic | Video |
| 4 | Jan 28 | Formal Proofs in Propositional Logic | Video |
| 5 | Jan 30 | Propositional Proofs and Validity | Video |
| 6 | Feb 2 | Language of First Order Logic | Video |
| 7 | Feb 4 | Formal Proofs in First Order Logic | Video |
| 8 | Feb 6 | Language of Set Theory | Video |
| 9 | Feb 9 | Proof about Sets | Video |
| 10 | Feb 11 | Binary Relations | Video |
| 11 | Feb 13 | Injectivity, Surjectivity, Bijectivity | Video |
| - | Feb 16 | Long Weekend - NO CLASS | - |
| 12 | Feb 18 | More Properties of Relations | Video |
| 13 | Feb 20 | Induction | Video |
| 14 | Feb 23 | Variants of Induction | Video |
| 15 | Feb 25 | Number Theory -- Division | Video |
| 16 | Feb 27 | Division Algorithm | Video |
| - | Mar 2 | EXAM 1 (Logic & Set Theory) | - |
| 17 | Mar 4 | Modular Arithmetic | Video |
| 18 | Mar 6 | Multiplicative Inverses | Video |
| 19 | Mar 9 | Number Theory in Lean | Video |
| 20 | Mar 11 | Message Passing, RSA | Video |
| 21 | Mar 13 | Encryption and Ethics | Video |
| 22 | Mar 16 | Intro to Counting | Video |
| 23 | Mar 18 | Division Rule | Video |
| 24 | Mar 20 | Binomial Theorem, Inclusion-Exclusion | Video |
| - | Mar 23 | Spring Recess - NO CLASS | - |
| - | Mar 25 | Spring Recess - NO CLASS | - |
| - | Mar 27 | Spring Recess - NO CLASS | - |
| 25 | Mar 30 | Pigeonhole Principle | Video |
| 26 | Apr 1 | Counting Trees | Video |
| 27 | Apr 3 | Intro to Probability | Video |
| 28 | Apr 6 | Probability and Independence | Video |
| - | Apr 8 | EXAM 2 (Number Theory & Combinatorics) | - |
| 29 | Apr 10 | Random Variables, Expectation | Video |
| 30 | Apr 13 | Conditional Expectation | Video |
| 31 | Apr 15 | Linearity of Expectation | Video |
| 32 | Apr 17 | Bayes' Rule | Video |
| 33 | Apr 20 | Induction and Proofs on Data | Video |
| - | Apr 22 | EXAM 3 (Probability + Redo 1) | - |
Calendar
How do hours work?
CS22 hours are collaborative spaces for students to work together on problems, facilitated by TAs. Hours will be primarily in-person. More details about hours can be found in the Course Missive.
Here is a link to the course calendar (same as below).
Resources
Course Textbook
Discrete Mathematics and Its Applications — Kenneth Rosen
Reading this textbook is not required, though many students in the past have found it helpful in reinforcing what's covered in lecture!
Course Documentation
Important Links
- EdStem
- Gradescope
- Anonymous Feedback Form
- Extension Request Form
- Recitation Absence Form
- Lecture Recordings/Livestream
Homework Resources
For many of you, this is your first time writing proofs, and even for those who have written proofs before, what we consider a good proof in CS22 likely differs from what made a good proof wherever you were writing them before! Check out the proof virtues document below to acquaint yourself with what we consider a good proof in CS22. Your proofs will be graded with respect to this document, so be sure to read it carefully, and come to hours with any questions.
Lean Resources
Math Resources
Sample Proofs
- Bidirectional
- Bijective Proof Sketch
- More Bijective Proof Sketches
- Bijective Strategies
- Cases
- Contradiction
- Contraposition
- Counterexample
- Equivalence Relations
- Induction
- More Induction
- Strong Induction
- Probability
- Set Equivalence
The LaTeX files to all the above resources can be found here.
LaTeX Resources
LaTeX (pronounced *la-tek*) is a program that you will be using to make your homework solutions look beautiful. LaTeX allows you to incorporate mathematical notation into your proofs, and because this class involves a healthy dose of mathematical notation, LaTeX is going to be very useful! Using LaTeX is required after the 2nd homework.
We don't expect you've ever done this whole LaTeX business before, and that's why we're giving you some time to learn it! To get started, we recommend creating an account on Overleaf, an online program for writing and compiling LaTeX. After you do that, here are some links to check out: Honestly, please use Overleaf. It's so much easier than installing anything on your computer. Trust me.
- CS22 LaTeX Cheat Sheet (start here!)
- A Not So Short Introduction to LaTeX
- LaTeX Symbols Guide
- Art of Problem Solving: LaTeX
- LaTeX Intro Wikibook
- LaTeX on Brown CS Systems
- LaTeX Gearup Template
- LaTeX Gearup Completed Handout
In general, a really good resource for learning LaTeX is the web. When you have a question, google it, and you'll likely find someone who had the very same question!
If you'd like to download LaTeX on your computer, here are some resources to do that:
If you're using LaTeX and you just don't know what the code for some symbol is, here is a helpful list to start:
Alternatively, this is a neat site which will return the LaTeX code based on handwritten input (although searching your question on the web is likely more efficient):
Staff
Instructors
Robert Y. Lewis
Instructor | Brookline, MA
he/him
Call me Rob! I'm 50% computer scientist, 40% mathematician, and 10% philosopher, so this course is pretty much my dream.
Favorite Bagel: Marble, drenched in butter
Head TAs
Ilija Ivanov
HTA | Podgorica, Montenegro
he/him
Hi! I'm a junior from Podgorica, Montenegro studying CS. Looking forward to a great semester with you all!
Favorite Bagel: Everything Bagel
Amy Qiao
HTA | Madison, WI
she/her
Hi beautiful people! I'm a senior from Madison, WI studying CS & Math. I love cs22 and will not shut up about it. In my free time, I love figure skating and overthinking everything. Talk to me about sports analytics and the Carolina Panthers :)
Favorite Bagel: Cinnamon Crunch
Alyssa Sun
HTA | Wilsonville, OR
she/her
I <3 Bagels
Favorite Bagel: Everything!!!!!
UTA-STAs
Zach Quitkin
UTA-STA | Stratham, New Hampshire
he/him
Hi, I'm Zach! I'm a junior studying CS and enjoy basketball, trying new food, and playing Wii Sports Resort.
Favorite Bagel: French Toast
UTAs
Nathan Phan
UTA | Manning, SC
he/him
Hey! I'm Nathan, and I am a junior concentrating in Math-CS. My favorite things are music, spicy food, and basketball nicknames.
Favorite Bagel: Plain bagel with cream cheese
John Rathgeber
UTA | Cottage Grove, WI
he/him
Hi! I'm a junior studying Math-CS and Music. One fun fact about me is that I have 93K trophies on Brawl Stars 😬
Favorite Bagel: Everything Bagel
Lukas Strelecky
UTA | Bridgewater, NJ
he/him
Hi! I'm a senior from New Jersey studying CS and biology. In my free time, I enjoy weightlifting, distance running, and cooking.
Favorite Bagel: Everything
Grace Wang
UTA | Bellevue, WA
she/her
Hi! My name is Grace, and I'm a junior concentrating in APMA-CS. Excited for the semester!
Favorite Bagel: Cinnamon Raisin
Moses Yang
UTA | Parsippany, NJ
he/him
Hi! Thanks for scrolling all the way down! I'm a junior studying CS, and I also fence at Brown. Fun fact: I went to Chipotle 23 times the past summer...
Favorite Bagel: New York Everything Bagel with Scallion Cream Cheese, Tomatoes, and White Onion, Untoasted