good afternoon cs109 and welcome to the first day of fall quarter hey I have not gotten to I was studying abroad in Spring which means I haven't gotten to start a class in person since pre-pandemic and boy does it feel good I am so happy to see you guys oh welcome welcome to cs19 if you didn't expect me to say cs109 this is your time to find that cs103 class or that uh cs121 class that you might be looking for but if you're looking for a cs109 this is a place coming in grab a seat I am Chris and we're going to be learning about probability for computer scientists okay shall we jump in gather around I have such a story to tell you guys today and it's a story that computer scientists know it's a story that mathematicians should know but certainly it's probably also a story that um all people should know to some extent but before I get into that I think I should introduce myself hi I'm Chris I'm a professor here in the computer science department I'm also in the school of education I'm in both places um I teach and I research and I have a good time I have a research lab it's AI for social good we mostly do education and some medical work as well uh I love to teach I teach 109 I teach 106a I'll teach cs398 I'll teach anything uh that I can that I'm equipped to teach um a small detail but um I've been here for a while I actually originally was born in Kenya when I was 12 I moved to Malaysia and then I came here when I was 18. and I liked it so much that I just decided to stay um and because I've been here for so long I was actually here as an undergraduate and after undergraduate I stayed for my PhD after my PhD they're like you want to teach her I'm like yeah that sounds cool so here I am um when I was an undergraduate I actually had the honor of being in the world's very first cs109 class it was a brand new class When I Was An undergraduate I got to take the very first one and look I was so young anyways and I've been teaching for quite a long time wow 2014. it's been a great great run so I love teaching and a lot of my research actually involves teaching because I love it so much one of the things that I did during the pandemic is we taught 20 000 students intro CS around the world and we got the world's the class with the most teachers in the world we got trained 2 000 people up to teach and they taught 20 000 students and it was a good vibe it was just like a little bit of community service and then time pandemic um that also gives me a chance to tell you a little about some of the research I do we taught these 20 000 people how to program but one of the things that I'm intellectually curious about is how can we understand humans who are learning uh and so one of the things we tried to do is said okay students are learning how to code can we look at their code and use some AI to analyze it and give feedback and we had this nice little result for the first time ever for something as complicated as open-ended code we're able to give feedback that students preferred uh to TA feedback it showed up in the New York Times amongst other places problems I'm also really interested in how AI can help teachers teach better and give and how they could improve their craft we tried all this stuff in code in place and we've found ways that we could make teachers even better at what they do and that just scratches the surface of how many cool problems there are in the world um you know I'm into things like measuring how well people can see I'm into things like can we figure out fairness in artificial intelligence the world is so full of things to be curious about and whether the joys of being at Stanford is I get to think about all these wonderful diverse things um outside of academics there's a whole bunch of things I love too I love music I love playing guitar Kenya and Malaysia have some of the best food in the world and I will argue with anybody that our Cuisine is better I'm just joking I love food I love cooking and I just love science the last winter I went into the forest and I found this wood covered with this ice that was in the shape of hairs and like our world is such a beautiful beautiful place um this is kind of a big deal in my life I do a lot of research I do a lot of teaching and then I've got this little baby and so this summer was like research half day teach half day and then like make airplanes out of cardboard uh which is like a total Joy I'll tell you all about her okay that's a little bit about me but I'm just one of the people who's gonna be teaching you cs109 cs1 is an incredible 109 is an incredible course and one of the things that makes it so amazing we have such an awesome team of uh Tas who are going to be helping us through this journey and learning probably are there any here today hey we got a corner of Tas everybody round of applause these guys are the heart and soul of the class thank you guys for what you do [Applause] okay I really want to get into content but I do want to give you the most important pieces of course mechanics but the number one thing to take away from today is we have a course web page it's cs109.stanford.edu all the course mechanics I mentioned you can go find on that course website and you can go look at the Nitty Gritty details for things that you're curious about though we should talk about some of the things one of the things you might be curious about am I in the right place there's a lot of questions about prerequisites and I just want to give you an idea of what we actually are going to be basing cs19 on top of we really really assume that you know cs106b coding we are going to talk about things like recursion hash tables binary trees and also we're just going to assume a certain maturity in coding some people have managed to take cs106b alongside cs109 uh that's fine but it's just a really really important prerequisite a less important prerequisite is cs103 uh we just use some light bits of cs103 and they mostly show up at the beginning of class in fact one day I was curious I there is all this card of data and I was wondering how do people do in cs109 if they've never had cs103 before and how do people do if they hadn't and I found the surprising result that if you didn't have cs103 you did slightly better in cs9 now as we'll talk about causality later in this class but it's certainly not causal it's probably just people who are willing to skip cs103 might be coming from a different population but long story short we really don't rely too much on the material from cs103 we do rely heavily on material for math 51 or CME 100. you know you're going to want to know what a partial derivative is we are going to teach you multivariate integration if you hadn't seen it before you'll see it in cs109 you know a lot of the stuff I'd if you get there and you're Rusty on it we're gonna help you but this is just what we're assuming coming in and certainly just some notation we hope you're a little bit familiar with uh if you just really really want to take cs109 uh come and you don't feel like you completely mastered all the prerequises just come talk to us we're happy to have that conversation so yeah you're in the right place um cs109 is a math course but we discovered a while ago that math can really Bloom when you can create things using math not just solve problem sets but make real things and to that end we are going to use the math that you learn in this class to make stuff and python is going to be the language that you use to make things in cs109 some of you probably seen python before some of you haven't if you haven't seen python that's absolutely fine we're gonna have review sessions to catch up on what you need it's a beautiful language certainly something you should know by the time you graduate worth it come to the review sessions as long as you've seen some programming python is one of the kindest and gentlest programming languages that you could learn okay oh this is a very small thing you know that there is a unit choice in Access there really shouldn't be because there's not really a choice it's a deterministic decision mostly start here are you an undergraduate yes very simple five units if you register for Access for less than five units I get an email per student which is a lot of emails let's say you're not an undergraduate then ooh do you want to take cs109 for Fiora units no guess what five units but if you did want to take cs1i for fewer units I'm here to let you know that you can if you're a graduate student if you take it for three years or four units the workload doesn't change uh it's the same amount of work for fewer units that's just life in grad school uh welcome to adulting anyways the really quick note on units so it's a five unit class uh the way Stanford units works is about three hours per unit so you can imagine uh we're going to be spending about 15 hours per week on cs109 uh and a large large majority of that will be you guys doing your own work so 10 hours for assignments a few hours for lecture and a few hours for section speaking of which what are the components of this wonderful class well as I mentioned one of the biggest components is assignments you guys will make things you'll derive things you'll practice your art form of understanding probability and that will be done uh in your assignments and that's a good chunk of cs109 and a good chunk of your grade we do have exams we have a midterm and a final exam you should show up they're both going to be a good time we put a lot of love to try and make it an educational uplifting experience I'm not really here to judge people I want you guys to grow and improve as and hit your potentials but anyways the final exam we were told by the university do it then and it's very very very very very very very very very very very close impossible to change only if you're like a senior who's graduating this quarter are there does the University make exceptions the midterm we have a lot more leeway on if you can't make this time you just let us know close uh to the date and we'll figure out something for you so anyways we have these exams if you're in a class that's at this exact same time your exam is probably at the exact at the same time and you definitely want to solve that problem now not at the end of the quarter okay and then one of my favorite things about cs109 it's fun to come to lecture you guys should come to lecture we were going to have a good time we're going to do demos we're going to tell jokes we're going to laugh hold hands sing Kumbaya now we're not going to do that last part but we are going to learn a lot of probability um but one of the best parts of the classes then you get to meet in small groups with one of our excellent World expert Tas who will walk you through the concepts so you can practice it before you go off on your own into problem sets uh it's a beautiful lecture than section then do your work I got this question a lot is this class online uh it's recorded these wonderful cameras we have an amazing amazing amazing scpd team that's doing professional recording of these classes uh they'll be released about 24 hours later so there's a few things to say about that I love the recording you get sick you can watch it later you didn't catch something you can watch it later realistically though some people are gonna be like oh man my club really needs me to do XYZ and I'll just catch up on lecture later and we've all Fallen to that trap so I want to talk a little bit about you know the query we did about people who had um who had or hadn't done one of three we can do the same thing based on how people are watching uh lectures and we know that coming to lectures people do about a grade point hires again not causal but come to lecture it's a good time it'll help you stay on top having said that I do think of you guys as adults you're adults of course I think if you as adults um and to that extent you're in charge of making sure you know this material you know find your way it's just coming to lecture we know is one of the best ways to do that um and but I will leave it to your own devices to how you're going to get to the end of the score you probably have questions in fact somebody from right now if you have an electric you just raise your hand and we'll get amongst it there are other ways oh yeah um the grading breakdown and the slide is slightly different than the syllabus which one is like oh definitely the one in solos what did I get wrong here 40. ah yeah I was gonna reveal that on Wednesday no no no no no no that's great that's great um okay well okay the reveal is going to come today so I was thinking about this slide and I was like well I want you guys to make your own decisions I don't want to penalize people I don't want to put in um uh something that to force you to come lecture but I do know that coming to lecture is generally good for you guys learning the material better so I was like how could I incentivize this in a nice and healthy way so what I was going to do is I was going to put like a really chill like you know code on the the board and you can record if you came to class and if you come to most of the classes then I'll just slightly decrease how much your final weighs into your grade and I'll just give you full points for that so just a small way to encourage participation if you don't do it can you still get 100 in the class absolutely like if you never show up to lecture but you show up to all your sections that is important and then you come to the final and you just rock it you're like yeah I can do all this probability you can get 100 in cs109 but uh we know that the more reasonable path to that coming to lecture participating so we're going to incentivize that and I'll give you all a little bit more details about that on Wednesday but very very very good question okay you might have other good questions where are you going to ask your good questions well you guys know q a forms by now we use Ed instead of sending us an email often it's better to post and a lot of people will read that and get back to you as soon as possible one of the great places to go ask questions is in person we do working office hours on cs109 so you don't even have to have a question you just go with your problems and be like I'm gonna work on my problem set and then when you have a question you're already there what a time to be alive so it is working office hours they're going to start on Thursday and we have a lot all of our Tas are doing four office hours we've got so many off stars for you guys because we want you to get the help when you need it so working off star is one of the great places to get help and you can also always email that email address and that goes to me and all the Tas and we can get you any help if you have anything private that comes up that's going to happen to some people you can email me in the head ta will directly and I also have one-on-one office hours as opposed to group office hours so you can come and ask me just questions there okay questions on questions how meta oh this is so cool I first started writing lecture notes for all my classes like okay what did I talk about today and then over time it became an entire reader so now I have an entire reader for you I finally finished it last year but now there's a cs19 reader it goes over a lot of the concepts we talk about in class um but just in a written form if you like there's this thing called an ace companion course it's fantastic if you want to take more units to cover this material and get some more examples you can take the ace class there's a application form and you can learn more about it by following the link it's both in the slides and on the home page of cs19 you guys want to see our homepage it's really not that beautiful but I designed it I'm not a designer and I feel really good about some of the small details it's not that important right now what is important though uh is that link is right over here so if you want to apply to Ace there it is uh and then I didn't go over all the details but for all the details the way you get all this information is on the course website uh under the course there's the syllabus and you can read oh our wonderful Tas and you read all about the details about the course structure and we go into all the nitty gritty anxiety any other questions shall we let's do it I want to tell you guys a story and I would like to tell you the story of modern air and boy has it become interesting in the last year so modern AI has this really interesting story but if I had to give it a subtitle it would be how we learn to combine probability and programming together to do very interesting things but I think I should give some historical context you know people thought AI would be a very easy problem and a I'm going to speak about broadly just computer is doing human level intelligent things we thought this would be simple in the 1950s computers start to do some awesome things we got computers that could beat any human in checkers and then we got computers that could do automatic proofs like you know imagine the sort of proofs you would do in cs103 you had computers that could start to do automatic theorem proving and we're like yeah we're awesome AI gonna be super simple and it led to ridiculousness for example Herbert Simon uh one of the leading AI researchers in 1952 said this ridiculous thing on a grant that he won that was worth the equivalent of like half a billion dollars today he said machines will be capable within 20 years of doing any work a man could do which is ridiculous for two years like or two reasons like 1952 all the work a man can do geez get with the times uh and then the other things like imagine 1972 rookie machines able to do this no they're basically like big calculators by 1972. completely wrong you just thought the world was pretty simple his Grant was like first I will solve language and then once I've solved language then I will solve free thoughts this is ridiculous anyways he didn't get past language he started with translation uh and this was he made this thing a good translate from English to Russian and and one of the funny examples was you could put in something like the spirit is willing but the flesh as we can get translated to Russian I didn't understand Russian so I didn't include it here but then you can take that Russian and put it back to English and see if it did a good job it's like the vodka is good but the meat is rotten which is funny but not at all the input sentence and you know what had happened the world's just too complex what did he try and do he tried to write all the rules of English to Russian he's like I'm just gonna spend this money we're getting a lot of people will write all these rules once you've written all the rules then we'll have a translation system but it turns out the world is so complex and we don't understand it because we have these beautiful probability machines called brains and these beautiful probability machines have so much power and they're so good about thinking about uncertainty that we think uncertain problems are easy but they are not as exemplified uh by Herbert Simon and then we called we got what we call the AI winter and for decades no one would fund anybody not just Herbert Simon uh anybody who said their AI they'd be like but obviously the AI winter is over and something's going on you guys probably know a lot about it a lot of its history started here for example this is a picture of Stanley a car made at Stanford which was one of the very first self-driving cars so in 1997 we started to win at chess in 2005 we got cars that could drive themselves in 2011 we had computers that could play Jeopardy something had started to change and obviously we know that that was just the beginning you know when I was in your seats crazy thing someone told me there's this problem called Speech the problem is you get an audio recording of someone's voice and then you have to write the transcription of what they said that's the problem of speech when I was in your seats someone told me this problem will not be solved in your academic lifetime I was like whoa what a hard problem but of course it has been solved we're very very very good at that in fact my my phone right now can do transcription for my voice into written text something really big can change between when I was in your seats and now you know board games yeah we're done with board games and in fact the people got so good at board games were like let's do something real with this technology and then started protein folding if you don't know what protein folding is is this very hard task of taking the amino acid sequence and then figuring out the 3D structure and if you could do that you could develop drugs faster you could understand our bodies faster it is a very interesting and wild world but it's such a hard problem to figure out how amino acid will become a 3D structure that we thought you know we won't be able to do it but as of a couple years ago not only are we good but we have we've come up with a 3D structure for every single known amino acid sequence in some popular database which I can't remember the name of but you know AI is not just those flashy things AI is also in our day-to-day lives like when you say I want to go from San Francisco to Mexico City and you get this route and it's a little bit of artificial intelligence that's helping you figure out your path and you know translations got a whole bunch better than when Herbert Simon was working on it if you're in Silicon Valley or self-driving cars well actually I have no idea how they're doing they haven't hit me yet okay and you know it's always been an exciting time but then this year everything seemed to change once again this is just kind of like a timeline since May um and all of a sudden we've started to get these huge results in artificial intelligence in a world that people are starting to call large language models but basically they're these like half billion dollar AI systems that people have started to make public for other people to use I was playing with my 18 or not 20 month old daughter uh a little while ago and we opened up one of these AI systems these AI systems can do different things the one we use would take text and when you wrote text it would infer the distribution of that text it would then go figure out what is the probability distribution of all the images that relate to this text conditioned on what was written and then it can sample you a few different images from that probability distribution that's insanity but for my 20 month old daughter it's just like she writes three birdies happy and she gets this picture or she writes you know robot Messiah and she gets this picture out in fact have you guys seen this is anyone who's not seen this live do you guys want to see it I need a prompt though uh let's say a rabbit and a giraffe in an airplane so this is a one AI model called dully it's going to take that sentence it's going to try and sample from the probability distribution of images related to that sentence and this is something that came out about six months ago we can also oh there you go and he constructed these images oh that's so cute look it's got like a little heart there ah okay and these aren't pictures found on the internet you know it just constructed those pictures from scratches thinking about probably distributions over images what a time so much is happening so fast and every problem that's gets solved seems to open up a whole bunch of open new problems oh so hopefully at this point I've convinced you that stuff's happening but you might be curious like Chris what's really going on under the hood well I'm going to start telling you that story now but really cs109 is a class where we're going to understand this story more deeply oh a little bit of suspense this is so fun to have been starting a class in person for so long okay let's focus on one problem uh this is the fun problem called Chihuahua or muffin you may think it's easy but you know originally when I was working on AI this would have seemed like an impossible task uh first of all let's just take a moment to appreciate how smart we are as humans and feel better than the machines for a moment okay just yell it out loud you guys are good a little tricky because the blueberries arranged like eyes and but you're right it is in fact a muffin okay how about now that was very impressive okay humans are getting smarter too you know why is this problem so hard it's like when you're seeing this it's hard to separate the fact that you have billions of neurons which are activating and they're lighting up in response to your retina you're having this experience of Chihuahua but that's a huge amount of processing that leads to the experience of Chihuahua for both your eyes and for computers it starts like this you either have Retina responses or in the case of a computer vision you have pixel values and you have to understand what's in an image just from Pixel values you just look at those raw numbers it is very hard to tell we have this thing called a visual cortex and about 30 of your brain is dedicated to seeing so when you perceive the world you have a huge huge mechanism that is behind that what seems easy to you is actually using one of the world's most powerful computers okay I'm going to show you this example using numbers this is going to be my hard example what digit is this oh no it's supposed to be a zero I really did choose a hard one and how about this one okay it's a little bit easier for I mean instead of Chihuahuas and muffins I'm gonna do uses yours and one's a little bit more straightforward you know you can imagine one of the AI tasks that you can do is to build an algorithm which can detect Chihuahua or muffin Oregon techs are one or a zero that's hand drawn it's a classification algorithm it looks at a picture and it classifies it as either group a or group b or in this group group one or group zero so we're going to make this AI algorithm we wanted to look at a picture and say something like this is a picture of one and look at this picture and say something like this is a picture of a zero that's our goal this particular AI algorithm task is called classification um it's not always perfect AI doesn't have to always be perfect but we want it to be fair and we also want it to be about as accurate as possible Okay so how could we do this we're not going to go down the Herbert Simon approach we're not going to try and write all the rules of what makes for a one or a zero we're not going to try to write all the rules of makes for a Chihuahua or muffin it just turns out this approach doesn't work the world is too complicated so instead let's use some insights I'm going to tell you two great ideas one is artificial intelligence artificial neurons as simple probability machines and then this idea of learning by examples shall we let's do it okay our brains are smart we have neurons so can we make a cartoon model of that here is a cartoon model of how your brain works you've got billions of these things called neurons neurons get inputs those inputs lead to a buildup charge in the nucleus of the neuron and if that charge gets big enough the neuron starts firing those inputs get weighted differently so your brain can decide to pay attention to some neurons more than other neurons uh and and that's kind of your cartoon model we can build a cartoon version of this and in fact we have done that we build these cartoon models they have inputs each input can be weighted and then we're going to start firing or not firing in fact when we build these cartoon models we built probability Theory into it from first principle so we interpret the output as a probability of firing or a probability of not firing this was a great idea and this idea changed the world not because you can get intelligence from one neuron but because you can start to put them together just to walk you through this metaphor really quickly these cartoon neurons that have inputs those are like the inputs to a human neuron and those could have different values every value we're going to wait and then we're going to sum up all the weighted values and once we sum up all the weighted values you know you can imagine it's like this little nice little mathematical Foundation where again then put it through a squashing function that gives an output that looks a little bit like a probability I said a whole bunch but at the end of the day this is a very digestible model if you spend you know 10 minutes looking at you it starts to feel a little bit comfortable you know a little cartoon model inputs get weighted some squashed think of the output as a probability that was our cartoon model of a neuron but the beautiful thing about these is you don't get a lot of intelligence from one neuron you get a lot of intelligence from putting a bunch of neurons together and so people started taking these little probability Lego blocks and putting them on top of each other and you could put a bunch of them together in a computer and you can end up with a bigger probability machine sometimes we'll represent it with layers like you have your input layers and then layers of hidden neurons and then a final layer and people would build these probability machines they would make the inputs equal to the pixel values and then they would try and get neurons in the middle to Fire and not fire and eventually they would have a very final neuron and that very final neuron would end up with a probability output and we would interpret that as a probability of a classification it was a good idea and you know people would make these bigger and bigger and bigger I won't go I won't go into oh let's take a look do you guys want to see one oh yeah blocked okay that's okay the picture captures it uh and yeah so people would build these huge neurons neural networks this is a visualization one where you have hand-drawn digit here and then you just have these layers of those tiny little blago blocks I describe they're tiny little probably uh units stacked on top of each other and they would each be Computing some probability on top of previously computed probabilities at the end we would have a bunch of neurons which would represent either this is a zero or one two three four five six seven eight or nine it was a simple model but you know I've told you about this model I've given you no reason to believe that it's intelligent you can make this model you guys could code it up but where does the intelligence come from the intelligence is embodied in this model where does it live and the answer is it's in these weights you know how you set these weights can make you can construct this whole Lego structure of these probability units and the intelligence will come from having well set weights if you have well set weights you can have good probabilities which have meaning well if you could get perfect weights you'd have intelligence do we hire grad students to go and just like fiddle around with those weights no it'd be great if we could get those weights in a more automatic way which leads to our second great idea learning by example humans have beautiful brains but we also have this experience of learning by trying things you know we're not always just given uh rules on how the world work we go experience the world and we get smarter through experiencing and so there was this great idea in probability in the 90s which was let's learn from example so imagine a single neuron you have these weights if they were the perfect weights it could be a smart neuron if they're random weights it's not a smart neuron and we want to get those weights to be really smart you know what people did they would take examples you know take this zero turn on your neuron have it fire and then if it was wrong like this case it predicts it's a one when really it's a zero what we would do is we would say hey algorithm could you adjust your weights so that you would be a little less wrong and the algorithm is like you know what I can you know why because I'm based on probability Theory because I'm based on probability Theory I can formulate that request mathematically and since I can formulate that that request mathematically as a computer I can do that I can take this input this example and I can change my weight so that I could have been smarter uh and if you do this a little bit over and over again and just get a little smarter every time you see an example eventually these models become intelligent over time and it really starts with this you know the neural network at its end makes a probability claim it says the probability that this is a zero is something like 0.9 and you say um but you know it's actually a one and so we're going to give you some loss uh and and then it says okay how could I have to update myself and it says well that was my probability that's my claim I can understand these from my probability basis and then I can ask how could I change so that I could have been better how could what is my change in weights that would improve or minimize my loss as much as possible and like there you go you can just write it as a formula and some of you guys are looking like what you mean you can just write out the formula that looks incredibly scary here's the beautiful thing about cs109 this looks scary right now this is something every single person in this class is going to master and feel very comfortable with and you will understand that mathematics that is the basis of this huge revolution in Ai and it's not just the basis of this revolution AI is math that will continue to change the world it is math absolutely worth knowing you will walk out of the class knowing what all of this means of course we're not there yet you're not supposed to look at that and be like yeah obviously it's the derivative of loss with respect to each of the weights um that's where we're going to get to in cs109 we're going to get there and not only are you going to be able to derive these we're going to derive all this work and then we're going to use it to start to solve some problems uh we're going to solve some interesting problems like detecting heart disease figuring out what movies people like um and doing some DNA analysis and you know I've told this story through Chihuahuas and muffins but one of the interesting things happening AI right now is we have these tools when you learn how to use these and you learn how to use them appropriately then the next question is what problems do you want to solve and we all have different answers for that but I would love to see these tools in your hands because I bet you guys would think of the coolest most useful things to do with uh with this like for example instead of detecting Chihuahuas versus muffins one of the things that somebody here at Stanford figured out was can we take a photo of somebody's skin and detect is this cancer or not cancer and there's a lot of interesting things to say about this but one of the things I'd like to point out is this is somebody who was just a few years older than most of you guys in this class and this was only a few years ago somebody at Stanford took some of these models that we're going to learn about and did something really worthwhile okay so what's the story so far hey guys going through a huge change and so far in its history not once but twice AI was Revolution advised people who understood their probability Theory really well end of story accept it no sorry too much suspense except it obviously isn't the end of the story it just keeps changing uh and there's not the end of the story for a bunch of reasons we're going to learn core probability theory in cs109 it'll be driven by application it'll be driven by our desire to understand this world but you're going to learn this fundamental theory that explains a lot of natural phenomena and it's gonna be much more useful than just learning there is abundance of important problems and I'm going to just show you one open problem that computers are really not that good at so this is a problem of One-Shot learning I'm going to show you an example of a single symbol and can you recognize which of these is an example another instance of that symbol so that's your single training and I want you to figure out which of these is another example is this it is this it is this it is this it ah fantastic you guys are this part you just you just that it's amazing humans are brilliant in that way but typical machine learning often needs to see millions and millions of examples and this is an example of you know we really have a lot left to do in the world of AI if you learn your probability it's not just good for machine learning if you're really into algorithms you just want to go into 161 you want to understand how all these different algorithms that have allowed us to use computers in such effective ways work you want to understand your probability so many modern algorithms use probabilistic analysis for telling the story of how they work so well and they use probabilistic analysis for great ideas and how to make cool ideas much faster we've all lived outside of the university and had experiences where probability could help us make good decisions there is this other part to cs19 I'll teach you fundamental probability and there's going to be times in your life when you will really appreciate that when somebody gives you a probabilistic claim that you can understand what that means if somebody gives you a probabilistic claim and you get more information you can understand how to incorporate that more information to improve your probabilistic understanding and it just makes us better understand the world around us and if you understand the world around us you can start to build things for that world a couple other cool examples you know some things aren't traditional AI with deep learning but maybe you want to be using some interesting conditional probability like recommender systems are some examples of that uh what a time my god with so much moving we need people to be building useful and important things with technology but we also need people who understand it very well to figure out how it could be used wrong and to be able to figure out when other people are doing things that we don't like uh ethics has become more and more important and it's not just ethics it's the codification of Ethics into things like law there's huge fields and careers to be made if you care about intersections Beyond just you know making the next cool Dolly image generator but are cool too maybe you want to understand how it made this picture of this giraffe and this uh bunny on this airplane sorry this is the image of image generation from like two years ago and this is where it is now it's changed a lot I had to update my slides okay but you know there's a few stories I hope you guys are just excited to learn this for the the pure joy of understanding how the world works the pure joy of learning tools that will allow you to build things that other people can't build but you know there is this practical side too it turns out this is the concept that is one at most demand in industry and also in Academia they did this survey for PhD students coming in they said what do you wish you knew better upon graduation and and the most common answer was a better understanding of probability it's a cool thing to learn it's going to enrich us as people we'll walk out just being a little bit more enlightened into the complexity of this world and we'll be able to do some cool stuff speaking of cool stuff here's just one story to tell you about how we try and incorporate the real world into cs109 ah spring 2017 what innocent days anyways spring 17 people in cs109 came in for their final and there was this problem and the problem says hey you've been learning a lot of probability Theory let's use it to make a really smart eye exam have you guys ever been to the eye doctor and they have you like close one eye and they're like that's an e that's an a they're like that's not an a that's a b what are you talking about you know that one it's not the best exam and so on the on their midterm in Spring 2017 their job was used probability to come up with a better exam I just thought this was a neat problem because I was like trying to write my exam while at the eye doctors I'm like this is boring the story I'm like oh I got a midterm problem this is awesome um and you know when you think about this probabilistically you can take information like what questions people have gotten right or wrong and you can develop a belief distribution over how well somebody can see and that's interesting because if you have a belief distribution over how well somebody can see you can make an intelligent decision under uncertainty for what to show next as a letter and then based on this you can make an algorithm which could dynamically give people different prompts for what they could answer and this is a plot of how long an exam is and this is a plot of how crappy it is you want to be low because crappy is bad that is the exam that you get at the doctors the blue one can be short or long but generally not very good the black one is the research exam so if you want to end up in a paper you have to study people's eyes using that black dot but using the cs109 algorithm we get way more accurate for much much shorter exams which is exciting and we could tell that story in lots of these beautiful probability plots which we'll get into later in the class it started in cs109 it was just a midterm problem and then a guy like published in science and the landsat and you know you have the Stanford Acuity test which started in our class and it just tells the story of all these open problems you might feel like probability assault it is not solved there's so many intersections think about something you love think about something you love that maybe not everybody loves there's a good chance there is a meaty interesting problem in the intersection of probability computer science and that thing that you love we'll try and explore different ones like for example uh on last year's final we did things like you know taking chess.com puzzles and figuring out how people good people are um P hacking supply chain decision making uh algorithmic art like how can you use probably to just make some beautiful images and on exams people made images like this ah so beautiful you're like exams are stressful man and people are not looking for Beauty on exams but that's a philosophy we can get into later okay it's a foundation for your future but not always the most intuitive thing I'm going to tell you honestly when I learned probably in high school I'm like well thank God I'm never going to need this in my life because I want to study the other fields of math and I was completely wrong um I just found it rather unintuitive I didn't understand how much it was going to change the world when I was in high school to give you an example of what I mean when I say probably isn't always intuitive let me give you this canonical example imagine a patient has a positive zika test and this is something that we can probably relate to from the two years of thinking about probability on testing so if somebody has a positive zika test how could you reason about the probability that they actually have zika I'm separating the idea that they had a test that that says they have zika from the underlying truth that they actually have the disease we need some more information to answer this question so I'll give you some more information very few people actually have zikra and then this test is not perfect so if people have zika 90 percent of the time they'll say you have zika and people don't have zika seven percent of the time you'll say you have zika you know how could it say you have zika if you don't have it well we know tests aren't perfect so if you don't have zika there's a chance that it'll still say you have it so now you have enough information to answer this question what's the probability that you have zika you just got a positive test but the right answer turns out to be only nine percent do you guys find that unintuitive you just had a test that says you have zika it's a pretty good test like those aren't bad numbers yet you're probably having zika is still very very low and what's going on here well you know one of certainly influencing factors is the fact that not many people actually have zika but if you want to understand this deeply you'd need to know your probability Theory and certainly the probability Theory would help you get to this answer but the one thing people don't often appreciate is you will then get more information the next day you'll feel a little bit better you'll feel a little bit worse and probably Philly Theory gives you clean way to update beliefs over evidence so the more information you gather you can keep updating your chance of anything you care about inferring in this case whether or not you have a disease do you guys find that on YouTube whoa small number so here we end up with this story probably important and something that needs study it's a something hard to learn on your own if you're not in the classroom so okay here's my view of probability in cs109 I'm going to teach you some beautiful Theory and the Beautiful theory that you need to do the math that most people are not able to do so that you can build and create things that will bring some Wonder into some people's lives gets you through this wonderful Journey it's not just about AI it's also about this uncertainty Theory and understanding probabilistic models that we're going to get to but in order to get there we need to build a foundation first you need to understand your Basics inside and out because when you get to this stuff it will get a little more complicated and so our job is to build this solid foundation upon which you can then improve and 109 is just the start of your journey you're going to take further classes and see us and they're going to build upon this even further so let's really make the sound Foundation Rock Solid how's that sound your future cells are going to love you they're like thank you for making my foundation so rock solid no problem pass me as into that sort of stuff okay so I'm excited you can tell I'm excited um and but at this point it'd be really fun to dive in so I'd like to get us to this point of understanding the Deep philosophy behind things like artificial intelligence and algorithms like making decisions under uncertainty but we got to build that Foundation you want to start right now we don't have to wait we can just do it now let's do it okay I do this thing these classes are long and they're long because it turns out probability Foundation has to be pretty hefty but I want you guys to be able to take things in I've talked about a lot of things what I'm going to do now is going to give you two minute pedagogy Applause I want you to meet the person next to you if you already know them great get to know them a little bit better if you don't know them get to know them a little bit better because we're going to be on this journey together two minute pedagogical pause just talk to somebody then we'll talk about some material let's bring on back okay let's do this let's build ourselves a foundation some people are like foundations are just not that exciting but houses are exciting you know foundations thing a house goes on and you're like I just want to make a house I want to make a tower I want to make a beautiful castle I want to make something exciting have you ever tried to make a house without a foundation not so exciting you got to build it's like it just feels like hole in a ground filled with concrete but like no this is where it all starts this is the Bedrock and the foundation of probability theory is hilariously encounting and you might think like Chris I'm pretty good at counting I've been counting since I was two well today you're going to learn how to really count um probability gets its Genesis from Counting Theory and it turns out when people are trying to understand how probability related to the world of mathematics is through counting that we were able to deeply understand it if you could understand counting it will provide that foundation for you but it also turns out it's a nice intuitive Direction into probability Theory it's a it's an easier space to reason about and it will give you a lot of the same insights that show up in probability Theory counting is also useful as a computer scientist because a lot of times you're trying to decide am I writing an algorithm that will eventually stop and a lot of times that's like how many iterations do I have to do and I actually have to count it and so counting really is that process of counting how many elements there are in probably Theory we have a slight formalization but it's no more complicated than you imagine we think of an experiment so you're going to do something and that doing something can have outcomes and we're going to think about how many unique outcomes there are um so let me give you an example I've got a dice here and I can roll that Dice and you can imagine rolling the rice as the experiment and the outcome is just which side of the dice we see so if we think about it how many outcomes can you get from rolling a single dice well there's six outcomes you get one two three four five six there's these nice discrete outcomes to Rolling a single dice what about how many ways could you roll a dice that where you have only evens well you can imagine my experiment is rolling the dice there's still six outcomes but only three of those outcomes satisfy the the idea that you have an even outcome on your dice this is just a little bit of terminology so counting we're going to think about experiments and we're going to think about counting events and what we're going to think about counting the outcomes that satisfy the idea behind those events so rolling single dice how many ways to get evens there's just three ways two four or six bump this up a notch you know rolling two dice isn't that bumped up but we can really take this uh to very interesting places and if you roll two dice you can imagine thinking about all the different outcomes of rolling two dice you know you can have a one and a one and you have a one and a two and one and a three and you can sit there and go through every possible combination write them all down and eventually get that there's 36 different outcomes and we can write them all out here you know here's the one in the one here's the one and the two the two and the one and so on so forth so here's a little bit of a first rule to start thinking about this you could have counted 36 for the number of outcomes in dice but it turns out we're going to learn our very first rule to make counting a little bit easier this is one of the two core ideas to Counting turns out if you know two ideas in counting how to count with steps and how account with or you could derive all the higher level counting that you could ever want so if you can really Master these two everything falls from them the first idea is if I wanted to count that there's 36 outcomes to these two dice here is one of the rules you can do you can break down this experiment into steps and anytime you can break down experiment into steps you can use one of your major Pathways to Counting called the step rule of counting okay I told you there's a little bit of Reliance on 106 or sorry 103 and this is kind of what it looks like we assume that you've heard of sets before and we've assumed that you've seen notation like this those vertical lines meaning the size of a set but if you've not seen that before study this notation and that's kind of the prerequisite that you would need to know you need to feel comfortable with some of this set notation so we're going to say the outcomes to an experiment if you break it down to steps could be thought of using the step rule of counting so when I say breaking down to steps let's say the outcome of an experiment comes from two steps steps a and step B and step a will have its own set of outcomes and step B will have its own set of outcomes and let's say there's some number of outcomes in Step a and some number of outcomes in Step B the step rule of counting says if it is such that the first step doesn't affect how many options there are in the Second Step so your first choice isn't changing how many choices you have in the step second choice you can just figure out the number of outcomes using multiplication so if you have it so if you have a two-step process where you have step one has a outcomes and step two has B outcomes if after step one there's always the same number of outcomes in step two the total number of steps in your two-step process is just going to be the size of number of outcomes in a times the size of number outcomes in B you know you could have named the number of outcomes in am and you could have named the number of outcomes in b n and then would just be M times n this is a really really fancy way of saying if you can figure out an experiment and break it down into steps you can just use multiplication to do your Counting I love this example there's so many beautiful things to be said about counting why it's interesting just from the single example not too long ago there was this art project they took 12 pixels and they were going to try and generate every possible image that you could with 12 pixels so you can imagine first they start with these pixels then you could slightly tweak this pixel then you can slightly tweak this pixel and they're going to try and generate every single possible image so my question for you is how many Unique Images can you get from 12 pixels and this will give us an idea if you're a computer scientist you might want to care how much work there is in this task but also it's going to be Pro a good practice in this first most important rule of counting the step rule of counting so see if you can use a step roll of counting to answer the question how many Unique Images are there for 12 pixels I'm going to give you an important fact and I can derive it for you later there's this idea of how many colors can each pixel be and it's about 17 million there's 256 options for red 256 options for blue and 256 options for green in how computers represent colors and so if you multiply 256 times 256 times 256 because you think of the process of choosing color as choose your red then choose your green then choose your blue put that together you have a color three steps no step changes how many options you have the other ones 256 times 250 times 256 gets you 17 million there's about 17 Millions at a computer 17 million different colors that a computer can represent for every pixel so if you have 12 how many different Unique Images were they going to generate in this piece of artwork talk to the person next to you get to know them them try and solve this interesting math problem try and talk about it in the terms of the step rule of counting and think about what your steps are I'll give you a moment to think about it oh this is great that is so wonderful just to hear people thinking you we're all going on this journey together we're going to spend you know 10 weeks that we're going to be synchronously trying to learn the beauty of probability together as a team what a beautiful thing and I just this cacophony of people thinking about a problem just really exemplifies that for me thank you thank you for that okay let's do it together though um how did people think about how many Unique Images are how could you break this into steps did somebody come up with a series of steps that they want to share with people right and each of the pixels can be one of 2.6 cubed million just like two six cubed colors and so if each of them were independent and they're not influencing the number of outcomes the other pixels have that what you could do is just multiply the number of outcomes of each pixel where's your steps this is exactly right but I just want to use the language of steps what are the steps how many steps are there and what's your first step right the first step is determining the color of the first pixel so we got pixel one step one choose that color does that change how many colors you're allowed to choose for Pixel 2 no no it doesn't infect at all so step two what's step two you determine the volume of that pixel so and how many steps we have well yeah 12 steps and no choice for anyone so that changes how many choices you have for the other one that's why we can just multiply and how many choices you have for step one you send me 256 cubed that's 17 million so 17 million times how many steps for two two seventy million you're like that's a lot two pixels is all we need uh but no no there are more 70 million times 70 million times 70 million you guys want to see what that looks like I put up a lot of these questions you guys I love programming so I made this thing called the pset app so you guys can do stuff in this like super cool app and I put all the the problems from today's lecture there too so you can try them out get your answer and put them in here this is how many Unique Images can you guys see that number oh okay well that is the number which is how many Unique Images there are from 12 freaking pixels that's 20 you know uh sorry 17 million times by itself 12 different times this is what that looks like uh and you know 12 to the power or sorry 17 million to the power of 12. and why is it 17 million to the power of 12 and not the other way around is because you have 17 million times 70 million times 17 million times itself 12 different times that's how you can get 17 million to the power of 12 as being the number of Unique Images 5.8 times 10 to the power of 77 doesn't look that large you're like that looks pretty large uh and it really looks large when you look at it in terms of just this raw number that is what that that's how many Unique Images you can get from the 12 pixels wow I did want to just review you know I said that there's 17 million it's because every single pixel has a red Channel which has 256 and blue which is 256 and green which is 256 options so you can imagine every single Pixel you think of it as three steps choose your red choose your blue choose a green do you know why 256 step rule of counting again there's actually eight bits to represent the red channel so there's eight different places where you can choose a zero or a one so if you have eight bits and this could be zero one there's two choices here two choices for zero one here two choices two choices two which is two choices two choices if you have eight binary values how many unique numbers can you make to the power of eight equals 256. step rule of counting is just all over uh okay so if 17 million to the power of 12 is how many images you get from picture C how many Unique Images are there from picture B you just yell it out loud 17 million to the power 300 do you know how big that is okay to give you a sense that people have estimated how many atoms there are in the known universe like if you went and counted every items like you need better things to do but if you went and counted every item we think you would get to about 10 to the power of 80. do you remember how big this number was it was 10 to the power of 77. there is almost as many Unique Images in these bloody 12 pixels as there are atoms in the known universe 17 million to the power of 300 isn't more than the number of atoms in the universe it's so much more and if you get to something like 12 million pixels which is like small compared to what your your phone can do it makes the number of atoms in the universe look like an infinitesimally small number in fact you would have to have a whole universe inside of every single atom to even get remotely close to how many Unique Images there are this matters this explains why some things are hard for computers why computations can be hard to compute being able to count and being able to kind of avoid the step rule of counting in some of your algorithms is key to being computer scientist but there's also some deep philosophy here can I just aside for a moment have you guys ever wondered how are we going to as a species keep trying to grow in a world with finite resources like we have a whole society based off of infinite growth but we have a world that only has finite things that seems like a problem right and it is true there are finite atoms and there's finite things in this world but once you get into the world of counting in combinatorics there are so many infinities of combinations of things we live in a world where there might be finite things but there's Infinite combination of those things it's not an infinite but just you know the step rule of counting leads to so many unique combinations so fast that our world of combinations is incredibly large and I just find this like some nice little philosophy uh for your first day of class anyways long story short the answer is 17 million to the power of n where n is the number of unique pixels um and what we think about the number of Unique Images we're now talking about way more than the number of atoms in the known universe how cool is that okay so uh here's your numbers is 72 million to the power of n um oh well slightly off but uh incredibly incredibly large numbers so I told you that the step rule of counting was one of two fundamental rules and if you can Master these two fundamental rules you could derive basically all of the mathematical field of combin torques which is the ancestor of probability Theory what's that other rule then the other rule man I feel almost shy telling it to you but I have to because you have to know its name it's called the sum rule of counting we're going to think about a different way of counting previously we're counting by steps you would take an experiment and try and split it up into Step A or B or 12 different sub steps this other way of crouching is we're going to say we're going to count by ORS we're going to say my outcomes can either come from set a or from set B so if you can have outcomes which are either from A or B and you want to count how many outcomes there are you could use the sum rule of counting if you where there's no element that's in both of these sets then it turns out the total number of outcomes is just going to be the total outcomes in a plus the total outcomes of B you could imagine like Steps leads to multiplication and or leads to addition uh that's a very special case where there's no element that's in both we call these sets mutually exclusive so there is no element that is both in set a and in set B and I want to give you just the intuitive idea to realize how obvious a statement what I made is so we're going to count my daughter's toys and we're going to live in a world where she only has balls or plush animals but oh my God we could talk about like capitalism and how many toys there are for kids it drives me crazy but I wish we only had these toys but we have more anyways that's not important right now what is important right now imagine my daughter only has balls or plush animals what I'm saying is you can think of the number of Toys she has is either coming from set a or set B and there's no toy that's in both sets so you can say um you know there's two toys in this set and there's three Toys in this set so I'm saying the total number of sets you can total number of toys you can just get by adding you're like Chris are you really teaching me this at Stanford in a college level class yes yes I in fact so how many toys are there just you know humor me you're like yes yes there are five they're in fact five because there is two from set a and there's three from set B because they're mutually exclusive you can just add them Good Times okay but like this isn't the end of the story because this um this really relies on a very important rule this is only if there's no element in a and b so they're mutually exclusive all right let's play with this a little bit here's a more interesting problem and this problem is going to make us think a little bit more deeply it's going to think about both counting with or and Counting with steps in the same time you've got these two tools we're going to try and bring them together okay here's my problem for you a six bit string so that's six zeros and ones so for example here is a valid six bit string zero zero one one zero zero it's six bits everything is a one or zero we're gonna send them over the networks but the receiver is only going to recognize as valid bit strings that start with a 0 1 or end with a one zero is this valid or invalid invalid because it neither starts with a zero one nor does it end with a one zero our question is let's just practice our counting and let's count how many valid strings there are and you're like whoa how'd you break this apart well we have two rules we have you can take your problem and try and break things into sets or if you have a problem you can try and break things into steps two mechanisms for taking a big problem and breaking into a smaller pieces there is an or in the question because valid strings either start with zero one or they start with one zero and when I see that or in the question my mind immediately goes to the step rule of counting so we can say why don't we count how my strings start with zero one and how my strings end with one zero we can split that up and we can just do one at a time so with the person next to you can you count how many valid strings are there that start with a zero one talk to the person next to you see if you can use one of these two rules to break that down and figure out how many valid strings start with zero one okay so just to be clear we were given a gargantuan problem and our job you know our strategy is to use these two things to break it into smaller pieces we did the first step together which we're going to split it into counting how many strings start with zero one and Counting how many strings end with uh one zero and then the task I gave you was can you count how many bit strings start with zero one anyone have an idea and really if you could appeal to either the step rule of counting or the or rule of counting that'd be very helpful yes uh at 16 because you know that your first two numbers have to be zero one yeah and then you have four more steps that you need to take yes and so you take your first step it's either one or zero so that's two the two choices for your first step the two choices for your second step and so on until you have four steps okay and you have two choices for the next bit two choices for this one two choices for this one two choices for this one that's fantastic you guys know I like to make things like physical it makes things more interesting for understanding so I've got here Coke Zeros and Coke ones and you're like you should okay okay let's let me just say something that's on my mind this is not a Coke series it's a Diet Coke because I went to the bookstore I was like do you have Coke series like no we have Diet codes I'm like no I need a Coke Zero for my demo and they're like not at all understand they're like it's the same number of calories basically but anyways this is my zero this is my one step one start your string has to be zero one there's only one choice for those first two but then you get four more choices you could either put a zero or one for your next string this step has two options then you have one more choice for the next bit two choices oh sorry a zero or one two choices you have to choose one of them and then we've got one two three four we've got two more steps left you know choose one of these two and then for your very final choice you have two more choices left so if there is one times two times two times two times two to the squared to the third to the fourth sixteen thank you very much that's exactly right so there's two to the fourth strings that start with zero one if you guys want to see them all like maybe you don't believe me there they are there are all the strings that start to zero one and like this is what it looks like to enumerate all of those in fact anytime you find counting hard use your ability to write awesome programs and you could enumerate every single possibility and really convince yourself so you counted right how many strings end with one zero it's the same thing just backwards there still are going to be the same number of steps okay this is one no it has to end in one zero so this is my Coke Zero obviously this is my Coke one so step one is to put them at the end of the string and then there's four places that can either be or zero or a one and there's two choices for each of those four steps so two choices for this one two choice for this one two choice for this one two choices for this one so you can think about it as step one fix these last two to be one zero and then you have four steps left to construct your string you have two choices for this step two choices for this step two choices for this step two choices for this step very importantly when you choose our one or zero here it doesn't change whether or not you can choose a one or zero here right if you chose a one this can still be a one we've chose a zero this can still be a zero so a number of choices in one step doesn't affect the number of choices in another step okay hey we use both of the rules in one problem we use the step rule of counting to figure out how many strings end in zero one and we use a step row of count to figure out how many strings and then one zero now we've got an or of two sets we have set a and set B and our results can come from either of them so we can just add them and you're like 16 plus 16 I'm done and you like take your answer and you go to your pset app your fun little piece of app what a good time and you go over what's 16 plus 16 real fast and you put in your 32 and you hit check answer and it's checking answer and I hope I have internet enough to get to my server oh it's a little optimistic it's like keep trying you're like you jerk just tell me I'm right what did Chris lie I don't lie I try not to lie but like did he lie something's wrong somebody knows they're not yeah there's three PS4s you gotta get rid of that okay the schedule of counting is very useful as long as step a doesn't change how many elements are in Step B we can use it the or rule of counting has this very hard constraint you can't have elements that in both sets this is what that looks like there is this element here and that exact same bit string is right over there we've counted it twice it's not two different unique strings it's just one string but we've counted it twice so if this was a midterm and you guys were like I want to get my my partial credit I want to get the right answer how would you just hack this together really quickly yeah you just like uh subtract four because I double counted them and you get uh 28 and you're like uh 28. so that felt hacky we're just like okay uh we want to subtract off four but it turns out subtracting off four is in fact a very elegant thing to do if you want to count by ORS in the case where this condition doesn't hold there is a very simple fix you just need to count how many elements are in this overlap how many elements are in both if you can count how many elements are in both you just subtract off that number so it leads to this more general rule of counting with or which is if you want to drop this box then the total number of outcomes is going to be the size of elements in set a plus the size of elements in set B but then you have to subtract off all of your double counting and you have to say let's subtract off all the elements that are in both sets can people on that side see this I know it gets a little bit close to the screen okay and that leads to the outcome that is correct and also just the final rule to learn today it has a fancy name it's called inclusion exclusion and it is one of the fundamental ideas of counting in fact it's very close to one of the axioms upon which all of probability theory is based but it's a pretty simple easy to understand idea we can count either by or or by steps and when you count by or you've got this very general rule if your outcomes are either coming from set a or set B you can just use this formula and this is the summary core counting really comes down to Counting with steps or counting with or counting with steps we can just use multiplication as long as this constraint holds that step a doesn't affect step B and when you're counting with or so outcomes either come from A or B you can use this formula and now you've got two great formulas and this counting with or if you subtract off the overlap has no limits you can use it any case you're counting with or okay have a challenge for you guys this is my my little brain teaser to end the day so Boba we all love it uh imagine the letters b-o-b-a that's funny this image is huge but the letters are tiny my question for you is how many unique orderings are there of the letters b o b a and we can start writing them out you know there's one unique ordering you could do b b o a they don't have to be valid words I just want to know how many unique ways could you order all the letters in boba and this is our final challenge for today and you could think if if you can figure out how many unique ways there are of doing Boba and you want to bump it up you can say how many unique ways are there doing Mississippi and I'm going to give you guys some time to talk about that this isn't the answer is it maybe it is the answer I'm gonna give everyone a chance to think about it so think about it how could you figure out how many unique orderings are there of the word Boba uh and we're going to be taking our counting up to the next level if you want an easier one to start with if you're finding this hard thinking about how many unique orderings are there of something where all the letters are unique and that would be a easier problem to solve on your way to the answer talk to talk about this with the person next to you let's see where we can get to okay you guys are awesome I'm so looking forward to the rest of this quarter this is going to be such a good ride okay I don't want to talk about the answer to this harder problem I want to talk about the answer to this easier problem where all the letters are unique and I want to think about orderings for these number of unique letters so how can we think about the number of unique ways of ordering A B C or D I'm going to give you a four-step process step one choose letter one how many choices are there four and let's say you chose a and there's four choices here how about first step two my claim is that your step two is you're going to choose the second letter but are there four choices anymore uh oh is that breaking a rule the step rule says that after you make your first choice it can affect how many choices there are in the second one does your choice in the first step change how many choices you have in the second one oh It's Tricky well if you choose a there's three things left if you choose B there's three things left if you choose C there's three things left if you choose D there's three things left it turns out no matter what you choose for the first letter there's still three things left so that allows us to use a step rule of counting so you know there's three things left and let's say we choose C know what no matter what you chose for the first two letters they're still going to be just two letters left so your third step is to choose that next letter and there's two choices so that could be B and then finally your last one will be determined because you've chosen three of the letters that last one there's not really a choice there's only one option left no matter what you chose your first step changes the options for your second step but your first step doesn't change how many options there are and it's the second thing that needs to be true to use a step rule of counting and since that second thing is true then the total number of ways of organizing a b c d is four times three times two times one that is easier than thinking about the orderings of this why is it easier than think about the orderings of this word the silly bees oh my God make our lives so much they're our new beards so I'm not going to tell you the answer to this I'm going to leave this as a little bit of a tease for you guys to try and think about on your own can you figure out how many orderings are there if you do figure it out what you can do is you can go to the website go find lecture one use these optional problems where I just kind of like write up the things we talked about and you can go try and if you get your right answer you can put it in here and you can see if you got the answer right have a wonderful rest the first day of the quarter come back on Wednesday we'll continue this wonderful journey of cs109 foreign