Introduction to Discrete Structures & Probability

CS22 meets Mondays, Wednesdays, and Fridays from 1:00 - 1:50 pm in MacMillan Hall 117.

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

All assignments after Homework 2 must be completed in LaTeX. Read about LaTeX here.

NAME

RECITATION

RELEASED

DUE

SOLUTIONS

NAME

RECITATION

RELEASED

DUE

SOLUTIONS

NAME

RECITATION

RELEASED

DUE

SOLUTIONS

NAME

RECITATION

RELEASED

DUE

SOLUTIONS

NAME

RECITATION

RELEASED

DUE

SOLUTIONS

NAME

RECITATION

RELEASED

DUE

SOLUTIONS

NAME

RECITATION

RELEASED

DUE

SOLUTIONS

NAME

RECITATION

RELEASED

DUE

SOLUTIONS

NAME

RECITATION

RELEASED

DUE

SOLUTIONS

EXAM

REVIEW SESSION

EXAM DATE

SOLUTIONS

EXAM

REVIEW SESSION

EXAM DATE

SOLUTIONS

EXAM

REVIEW SESSION

EXAM DATE

SOLUTIONS

Refer to the calendar below for the most up-to-date TA hours. Professor Littman's office hours TBA.

Recitations will be held twice weekly, times and locations TBA.

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

DATE

TOPICS

BOOK

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

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.

- Proof Virtues — PDF

- Bidirectional
- Bijective Proof Sketch
- More Bijective Proof Sketches
- Bijective Strategies
- Cases
- Contradiction
- Contraposition
- Counterexample
- Induction
- More Induction
- Set Equivalence
- Strong Induction

LaTeX (pronounced *la-tek*) is a program that you will be using to make your homework solutions look
beautiful. The sample proofs above were written in LaTeX to give you an idea of what documents written in
LaTeX look like. 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.

- LaTeX Workshops at Brown's Science Center
- A Not So Short Introduction to LaTeX
- LaTeX Symbols Guide
- Essential LaTeX
- Art of Problem Solving: LaTeX
- LaTeX Intro Wikibook
- LaTeX on Brown CS Systems

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!

Below is a template you can use as a starting point for your homeworks.

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):

mlittman

he/him/his

I've been at Brown for 7.5 years. Before that, I was a professor at Rutgers University in NJ. Also, Dunkin' Munchkins were originally marketed as the dough from the hole of the other donuts. But, that's a lie.

jmcclel1

she/her/hers

Hellomst! I'm Julia, a junior from Concord, Massachusetts, the birthplace of the American Revolution. If I'm not in the CIT, I'm probably on a run (come join Running Club at 4:15 outside the Nelson!). Also, my town of 17,000 people has 4 Dunkin' Donuts.

jwang73

she/her/hers

Greetings, traveler! I'm a junior studying Computer Science, spiritually from Beijing and legally from Toronto. If you can't find me, I'm most likely hiding in a cardboard box; I also sometimes eat pancakes. Also, did you know that Krispy Kreme is older than most cats?

tdefrosc

he/him/his

Hi 22ers! I'm a senior studying Math-CS from Maine. This is my third time TA'ing 22! My favorite cs22 topic is Number Theory. My favorite local donut shop is PVDonuts (try the cruller). ALSO, yeast doughnuts and cake doughnuts contain most of the same ingredients, however, their structural differences arise from the type of flour and leavening agent used. In cake doughnuts, cake flour is used, and the resulting doughnut is denser because cake flour has a relatively low gluten content of about 7 to 8 percent.

ahabib3

apikieln

asingh79

he/him/his

Largest donut made is 1.7 ton

cxiao2

she/her/hers

Hi! I'm a senior studying Computer Science-Economics from northern Virginia. I'm a dancer and foodie with a show binging problem. I usually avoid the CIT at all costs. Also, the world's most expensive doughnut sells for $100 a piece. The ingredients include golden flakes, edible diamonds, and aged chocolate balsamic vinegar.

drozenb1

she/her/hers

Hi! I'm a sophmore from North Andover, Massachusetts studying CS (and maybe APMA or Econ). Some things I enjoy outside of CS are flowers, rock climbing and airheads extreme bites. Also, there are 10 people living in America with the last name 'Doughnut' or 'Donut'

cli135

he/him/his

Hi, I am a freshman from Beijing, China. I am not much into writing mathematical proofs, but I enjoy reading them and spotting the parts where they are not rigorous. Also, a donut is a torus!

eavril

she/her/hers

Hi! I'm a senior from Philadelphia interested in cryptography and tech policy. I like knitting, baking, and taking care of my many plants. Talk to me about books, musicals, or which piano in Steinert is the best! Also, I like donuts.

galon1

she/her/hers

Hi! I'm a sophmore studying APMA and Computer Science from Newton, Massachusetts. Btw I have a twin sister if you see her around! Also, my favorite type of doughnut is chocolate glazed!

ihasan2

jciabato

he/him/his

Hey! I'm a sophomore from Naples, Florida, and I'm studying Computer Science-Economics and Mathematics. My favorite dining hall is Andrews (try the granola bowl) and I'm still not used to the cold Northeast winter weather. Also, researchers have noted that the size of the hole in a doughnut correlates with the quality of the economy. So, the worse the economy, the bigger the doughnut hole.

jxiong3

he/him/his

Hello! I am a senior from Mahwah, New Jersey studying APMA-CS. I literally do not do anything else. Also, within the United States, the Providence metropolitan area was cited as having the most doughnut shops per capita (25.3 doughnut shops per 100,000 people) as of January 13, 2010.

jhuddle1

he/him/his

Hi! I'm a junior from Eastern MA studying Computer Science. When not in the CIT, I can usually be found outside (even in the winter) or in the Ratty. Also, donuts were invented in 1847 on a lime trading ship

jsinger2

jzagorsk

he/him/his

Hi! I'm a senior from Long Island, New York. I study APMA-CS. Outside of the CIT, you can find me either watching The Office or Impractical Jokers, at a baseball game, or playing any sport that ends in "ball". Also, a donut is neither a "do" nor a "nut".

kkawamu1

he/him/his

Hi! I am a sophmore from Tokyo, Japan studying computer science. I love to sleep. Also, there are more Mister Donut stores in Japan than in US since most of them in the US bacame Dunkin' Donuts.

kjiang18

he/him/his

Hi, I am a second year master student studying computer science. I like playing tennis. Also, I am not familiar with donuts.

ktsuji

she/her/hers

Hello! I'm a junior from Japan studying Computer Science and Engineering. I love to eat, and occasionally read, play hockey, or play the harp. Also, Dunkin' Donuts used to offer a donut called "The Dunkin' Donut", which came with a handle that you could hold onto to dunk the donut in your coffee.

lyang39

mheller6

he/him/his

Hi! I'm a sophomore from Albany, NY (not its suburbs) studying CS. I once consumed almost 20 donuts in a day! Also, Donuts used to be called 'olykoeks', meaning 'oily cakes' in Dutch.

nmahaja1

he/him/his

I'm a sophomore from Indiana studying CS. I am also a Meiklejohn and a Pacers fan. Also, You can get kimchi donuts at a Dunkin Donuts in South Korea.

rmani1

he/him/his

Hey everyone! I'm a junior studying CS-Econ. I'm from the D.C. area and am, unfortunately, a huge D.C. sports fan. I also like dogs. Also, a donut a day keeps the doctor away.

zlagumdz

he/him/his

Howdy! I'm a tall Bosnian engaging in existential contemplation every other month and studying CS with hopes of solving my existential dread through distraction. If you ever wanna talk about problem solving strategies or about intuition behind the material in class, pop by my office hours. Also, donuts have a longer wikipedia page than you'd expect

sdsouza1

she/her/hers

Hi! I'm a junior from Hong Kong studying Computational Biology. When not in the CIT, I'm usually at a café or binging a Netflix show. Also, there are approximately over 10 billion doughnuts made in the United States each year.

swang75

smeng4

she/her/hers

Hello, I'm a senior from California studying CS and Visual Arts. I love bread and bread-related products. Also, doughnuts can be doughy... and/or nutty...

spark108

tdelvecc

he/him/his

Heyo! I'm a sophomore from Maryland studying (Pure) Math-CS. I like to run when I'm not injured, play video games when I'm not busy, and read when I'm not tired. My favorite word is "whom'st'd've". Also, the dictionary-approved spelling for the ring-shaped cake made of dough and fried in fat is doughnut. The shortened donut has been around since the late 1800s, but it wasn’t popularized until the late 20th century, when the successful American doughnut chain Dunkin’ Donuts made it ubiquitous.

tjenkin3

he/him/his

I am Junior from the suburbs of Chicago. I am studying computer science and physics, and I am a guitarist for Mariachi de Brown. Also, in Austin Texas, there exists the "Boss Hog" donut, which has pulled pork, potato salad, and honey bbq sauce piled on top

tottaway

he/him/his

Hi! I'm a sophmore from Albany NY studying APMA-CS. I like juggling, unicycling, and rock climbing. Also, many Jewish people eat donuts on Channukka since it is fried in oil.

vlin2

she/her/hers

Hello..! I'm a senior from New Jersey studying CS/APMA/Econ. I am a big fan of knitting and also the indie game Hollow Knight. Also, national donut day is June 5th this year! Mark your calendars n get those DEALS

wyang29

he/him/his

Hi! I'm a sophomore from New Jersey studying APMA-CS. When not in the SciLi or CIT, I'm probably watching the NBA, procrastinating on YouTube, or trekking to the Nelson. Also, Joey Chestnut ate 257 donuts in 6 minutes in celebration of National Doughnut Day in 2018.

zmothner

he/him/his

Hi! I'm a sophomore from New York City studying Computer Science and Visual Art. Outside of class, I'm a BRYTE tutor, and I'm constantly drinking coffee. I love meeting new people so come talk to me! Also, according to the Oxford Dictionary while "doughnut" is used internationally, the spelling "donut" is American.