if you want to learn about computer science and the Art of programming this course is where to start cs50 is

considered by many to be one of the best computer science courses in the world this is a Harvard University course

taught by Dr David men and we are proud to bring it to the Freo Camp YouTube channel throughout a series of lectures

Dr me will teach you how to think algorithmically and solve problems efficiently and make sure to check the

description for a lot of extra resources that go along with the course [Music]

all right this is cs50 Harvard University's introduction to the intellectual Enterprises of computer

science and the Art of programming back here on campus in beautiful Sanders Theater for the first time in quite a

while so welcome to to the class my name is David May so my name is David man and I took

this class myself some time ago but almost didn't it was it was sophomore fall and I was sitting in on the class

and I was a little curious but H didn't really feel like the field for me I was definitely a computer person but

computer science felt like something altogether and I only got up the Nerf to take the class ultimately because the

professor at the time Brian kernahan allowed me to take the class past fail initially and that is what made all the

difference I quickly found that computer science is not just about programming and working in isolation on your

computer it's really about problem solving more generally and there was something about homework frankly that

was like actually fun for perhaps the first time in what 19 years and there was something about this ability that I

discovered along with all of my classmates to actually create something and bring a computer to life to solve a

problem and and sort of bring to bear something that I've been using every day but didn't really know how to harness

that's been gratifying ever since and definitely challenging and frustrating like to these to this day all these

years later you're going to run up against mistakes otherwise known as bugs in programming that just drive you nuts

and you feel like you've hit a wall but the trick really is to give it enough time to take a step back take a break

when you need to and there's nothing better I dare say than that sense of gratification and pride really when you

get something to work and in a class like this present ultimately a a terms end something like your very own final

project now this isn't to say that I took to it 100% perfectly in fact just this uh this past week I I looked in my

old cs50 binder which I still have from some 25 years ago and took a photo of what was apparently the very first

program that I wrote and submitted and quickly received minus two points on but this is a program that we'll soon see in

the coming days that does something quite simply like print hello cs50 in this case to the screen and to be fair I

technically hadn't really followed the directions which is why I lost those couple of points but if you just look at

this especially if you've never programmed before you might have heard about programming language but you've

never typed something like this out undoubtedly it's going to look cryptic but unlike human languages frankly which

were a lot more sophisticated a lot more vocabulary a lot more grammatical rules programming once you start to wrap your

mind around what it is and how it works and what these various languages are it's so easy you'll see after a few

months of a class like this to start teaching yourself subsequently other languages as they may come in the coming

years as well so what ultimately matters in this particular course is not so much where you end up relative to your

classmates but where you end up relative to yourself when you began and indeed you'll begin today and the only

experience that matters ultimately in this class is your own and so consider where you are today consider perhaps

just how cryptic something like that looked a few seconds ago and take comfort in knowing just some months from

now all of that will be uh within your own grasp and if you're thinking that okay surely the person in front of me to

the left to the right behind me knows more than me that's statistically not the case 2third of cs50 students have

never taken a CS course before which is to say you're in very good company uh throughout this whole term so then what

is computer science I claim that it's problem solving and the upside of that is that problem solving is something we

sort of do all the time but computer science class learning to program I think kind of cleans up your thoughts it

helps you learn how to think more method meally more carefully more correctly more precisely because honestly the

computer's not going to do what you want unless you are correct and precise and methodical and so as such there's these

sort of fringe benefits of just learning to think like a computer scientist and a programmer and it doesn't take all that

much to start doing so this for instance is perhaps the simplest picture of computer science sure but really problem

solving in general problems are all about taking input like the problem you want to solve you want to get the

solution AKA output and so something interesting's got to be happening in in here in here when you're trying to get

from those inputs to outputs now in the world of computers specifically we need to decide in advance how we represent

these inputs and outputs we all just need to decide uh whether it's Macs or PCS or phones or something else that

we're all going to speak some common language irrespective of our human languages as well and you may very well

know that computers tend to speak only what language so to speak assembly one but binary 2 might be

your go-to binary by implying two means that the world of computers has just two digits at its disposal zero and one and

indeed we humans have many more than that certainly not just zeros and ones alone but a computer indeed only has

zeros and ones and yet somehow they can do so much they can crunch numbers and Excel send text messages create images

and and artwork and movies and more and so how do you get from something as simple as a few zeros a few ones to all

of the stuff that we're doing today in our pockets and laptops and desktops well it turns out that we can start

quite simply if a computer were to want to do something as simple as count well what it could it do well in our human

world we might count doing this like 1 2 3 4 5 using so-called unary notation literally the digits on your fingers

where one finger represents one person in the room if I'm for instance taking attendance now we humans would typically

actually count 1 2 3 4 5 six and we'd go past just those five digits and count much higher using zeros through nines

but computers somehow only have these zeros and one so if a computer only somehow speaks

binary zeros and ones how does it even count past the number one well here are three zeros of course and if you

translate this number in binary 0 0 0 to a more familiar number in decimal we would just call this zero enough said if

we were to represent with a computer the number one it would actually be 0 01 which not surprisingly is exactly the

same as we might do in our human world but we might not bother writing out the two zeros at the beginning

but a computer now if it wants to count as high as two it doesn't have the digit two and so it has to use a different

pattern of zeros and ones and that happens to be 0 1 0 so this is not 10 with a zero in front of it it's indeed 0

1 0 in the context of binary and if we want to count higher now than two we're going to have to tweak these zeros and

ones further to get three and then if we want four or five or six or seven we're just kind of toggling these zeros and

ones AKA bits for binary digits that represent via these different patterns different numbers that you and I as

humans know of course as the so-called Decimal System 0 through n deck implying 10 10 digits those zeros through nine so

why that particular pattern and why these particular zeros and Ones Will turns out that representing one thing or

the other is just really simple for a computer why at the end of the day they're powered by electricity and it's

a really simple thing to just either store some electricity or don't store some electricity like that's as simple

as the world can get on or off one or zero so to speak so in fact inside of a computer a phone anything these days

that's electronic pretty much is some number of switches otherwise known as transistors and they're tiny you've got

thousands millions of them in your Mac or PC or phone these days and these are just tiny little switches that can get

turned on and off and by turning those things on and off in patterns a computer can count from zero on up to seven and

even higher than that and so these switches really you can think of being as like switches like this let me just

borrow one of our little stage lights here here's a light bulb it's currently off and so I could just think of this as

representing in my laptop a transistor a switch representing zero but if I allow some electricity to flow now I in fact

have a one well how do I count higher than one I of course need another light bulb so let me grab another one here and

if I put it in that same kind of pattern I don't want to just do this that's sort of the old finger counting way of unary

just one two I want to actually take into account the pattern of these things being on and off so if this was one a

moment ago what I think I did earlier was I turned it off and let the next one over be on AKA 01 0 and let me get us a

third bit if you will and that feels like enough here is that same pattern now starting at the beginning with three

so here is 0 0 here is 0 0 1 here is 0 1 0 Z AKA in our human world of decimal two and then we of course keep counting

further this now would be three and dot dot dot if this other bulb now goes on and that switch is turned and all three

stay on this again was what number okay so seven so it's just as simple relatively as that if you will but how

is it that these patterns came to be well these patterns actually follow something very familiar you and I don't

really think about it at this level anymore cuz we've probably been doing math and numbers since grade school or

whatnot but if we consider something in decimal like the number 123 I immediately jump to that this

looks like 123 in decimal but why it's really just three symbols a one a two with a bit of curve a three with a

couple of curves that you and I now instinctively just assign meaning to but if we do rewind a few years that is

123 because you're assigning meaning to each of these columns the three is in the so-called one's place the two is in

the so-called 10's place and the one is in the so-called hundreds place and then the math ensues quickly in your head

this is technically 100 * 1 plus 10 * 2 + 1 * 3 AKA 100 + 20 + 3 and there we get the sort of mathematical notion we

know is 123 well nicely enough in binary it's actually the same thing it's just these

columns mean a little something different if you use three digits in decimal and you have the ones place the

T place and the hundreds place well why was that 10 1 10 and 100 they're technically just powers of 10 so 10 the

0 10 the 1 10 the two why 10 Decimal System deck meaning 10 you have eight and 10 digits zero through nine in the

binary system if you're going to use three digits just change the bases if you're using only zeros and ones so now

it's powers of two 2 to the 0 2 to the 1 2 to the 2 AK a 1 and 2 and four respectively and if you keep going it's

going to be Eight's column 16's column 32 64 and so forth so why did we get these patterns that we did here's your 0

0 0 because it's 4 * 0 2 * 0 1 * Z obviously zero this is why we got the decimal number one in binary this is why

we got the number two in binary because it's 4 * 0 + 2 * 1 + 1 * 0 and now 3 and now 4 four and now five and now six and

now seven and of course if you wanted to count as high as eight to be clear like what do you have to do what does a

computer need to do to count even higher than seven add a bit add another light bulb

another switch and indeed computers have standardized just how many zeros and ones or bits or switches they throw at

these kinds of problems and in fact most computers would typically use at least eight at a time and even if you're only

counting as high as three or seven you would still use eight and have a whole bunch of zeros but but that's okay

because the computers these days certainly have so many more thousands millions of transistors and switches

that that's quite okay all right so if with that said if we can now count as high as seven or frankly as high as we

want that only seems to make computers useful for things like Excel like number crunching but computers of course let

you send text messages write documents and so much more so how would a computer represent something like a letter like

the letter A of the English alphabet if at the end of the day all they have is

switches any thoughts yeah okay so we could represent letters using numbers okay so give me what's a

proposal what number should represent whatting the beginning perfect yeah we just all have

to agree somehow that one number is going to represent one letter so one is a two is B 3 is C uh Z is 26 and so

forth maybe we can even take into account uppercase and lower case we just have to agree and sort of write it down

in some global standard and humans indeed did just that they didn't use one two three turns out they started a

little higher up capital A has been standardized as the number 65 uh and capital B has been standardized as the

number 66 and you can kind of imagine how it goes up from there and that's because whatever you're representing

ultimately can only be stored at the end of the day as zeros and ones and so some humans in a room before decided that

capital A shall be 65 or really this pattern of zeros and ones inside of every computer in the world 0 1 0 0

00001 so if that pattern of zeros and ones ever appears in a computer it might be interpreted then as indeed a capital

letter a eight of those bits at a time but I worry just to be clear we might have now created a problem it might seem

if I play this naively that okay how do I now actually do math with the number 65 if now Excel displays 65 is an a let

alone B's and C's so how might a computer do as you've proposed have this mapping from numbers to letters but

still support numbers it feels like we've given something up yeah AIX by having a

prefixed okay so we could perhaps have some kind of prefix like some pattern of zeros and ones I like this that rep that

indicates to the computer here comes another pattern that represents a letter here comes another pattern that

represents a a number or a letter so not bad I like that other thoughts how might a computer distinguish these two H

yeah indeed and that's spot on nothing wrong with what you suggested but the world generally does just that the

reason we have all of these different file formats in the world like uh JPEG and GIF and pings and Word Documents do

do o c x and Doc Excel files and so forth is because a bunch of humans got in a room and decided Well in the

context of this type of file or really more specifically in the context of this type of program Excel versus Photoshop

versus Google Docs or the like we shall interpret any patterns of zeros and ones as being maybe numbers for Excel maybe

uh letters in like a text messaging program or Google Docs or maybe even colors of the rainbow and something like

Photoshop and more so it's context dependent and we'll see when we ourselves start programming you the

programmer will ultimately provide some hints to the computer that tells the computer interpret it as follows so

similar in spirit to that but not quite as standardized with these prefixes so this system here actually has a name ASI

the American Standard code for information interchange and indeed it began here in the US and that's why it's

actually a little biased toward A's through Z's and a bit of punctuation as well and that quickly became a problem

but if we start simply now in English the mapping itself is fairly straight so if a is 65 B is 66 and dot dot dot

suppose that you received a text message an email from a friend and underneath the hood so to speak if you kind of

looked inside the computer what you technically received in this text or this email happened to be the numbers 72

73 33 or really the underlying pattern of zeros and ones what might your friend have sent you as a message if it's 72 73

33 hey close hi it's indeed High Why well apparently according to this little

cheat sheet H is 72 I is 73 it's not obvious from this chart what the 33 is but indeed this pattern represents high

and anyone want to guess or if you know what 33 is exclamation point and this is frankly not the kind of thing most

people know but it's easily accessible via a nice userfriendly chart like this so this is an asky chart when I said

that we just need to write down this mapping earlier this is what people did they wrote it down in a book in a chart

and for instance here is our 72 for H here is our 73 for I and here is our 7 33 for exclamation point and computers

Macs PCS iPhones Android devices just know this mapping by heart if you will they've been designed to understand

those letters so here I might have received High technically what I've received is these patterns of zeros and

ones but it's important to note that when you get these patterns of zeros and ones in any format be it email or text

or a file they do tend to come in standard lengths with a certain number of zeros and ones alog together and this

happens to be 8 plus 8 plus 8 so just to get the message High exclamation point you would have received at least it

would seem some 24 bits but frankly bits are so tiny literally and mathematically that we don't tend to think or talk

generally in terms of bits you're probably more familiar with bites b t s is a bite is a bite is a bite a bite is

just eight Bits And even those frankly aren't that useful if we do out the math how high can you count if you have eight

bits anyone know say again uh higher than that unless you want to go negative that's

that's fine 256 technically 255 long story short if we actually got into the weeds

of all of these zeros and ones and we figured out what 11 one one one11 mathematically adds up to in decimal it

would indeed be 255 or less if you want to represent negative numbers as well so this is

useful because now we can speak not just in terms of bytes but if the files are bigger kilobytes is thousands of bytes

megabytes is millions of bytes gigabytes is billions of bytes terabytes are trillions of bytes and so forth we have

a vocabulary for these increasingly large uh quantities of uh data the problem is that if you're using

asky and therefore eight bits or one B per character and originally only seven you can only represent 255 characters

and that's actually fine or 256 total characters including zero and that's fine if you're using literally English

in this case plus a bunch of punctuation but there's many humans uh languages in the world that need many more symbols

and therefore many more bits so thankfully the world decided that we'll indeed support not just the US English

keyboard but all of the accented characters that you might want for some languages and Heck if we use enough bits

zeros and ones not only can we represent all human languages in written form as well as some emotions along the way we

can capture the latter with these things called emojis and indeed these are very much invogue these days you probably

send and or receive many of these things any given day these are just characters like letters of an alphabet patterns of

zeros and ones that you're receiving that the world has also standardized for instance there are certain emojis that

were represented with certain patterns of bits and when you receive them your phone your laptop your desktop displays

them as such and this newer standard is called Unicode so it's a superet of what we called ASI and unicode is just a

mapping of many more numbers to many more letters or characters more generally that might use eight bits for

backwards compatibility with the old way of doing things with ASI but they might also use 16 Bits And if you have 16 bits

you can actually represent more than 65,000 possible letters and that's getting up there and heck unic code

might even use 30 two bits to represent letters and numbers and punctuation symbols and emojis and that would give

you up to 4 billion possibilities and I dare say one of the reasons we see so many emojis these days is we have so

much room I mean there's got room for billions more literally so in fact just as a little bit of trivia has anyone

ever received this decimal number or if you prefer binary now has anyone ever received this pattern of zeros and ones

on your phone in a text or an email perhaps this past year here well if you actually look this up this esoteric uh

sequence of zeros and ones happens to represent uh face with medical mask and notice that if you've got an iPhone or

an Android device you might be seeing different things in fact this is the Android version of this most recently

this is the iOS version of it most recently and there's Bunches of other interpretations by other companies as

well so Unicode as a Consortium if you will has standardized the descriptions of what these things are but the

companies themselves manufacturers out there have generally interpreted it as you see fit and this can lead to some

human uh miscommunications in fact for like literally embarrassingly like a year or two I started being in the habit

of using the Emoji that kind of looks like this cuz I thought it was like woo happy face or whatever didn't realize

this is the emoji for hug because whatever device I was using sort of looks like this not like this and that's

because of their interpretation of the data this has happened too when what was a gun became a water pistol in some

manufacturers eyes and so it's an interesting dichotomy between what information we all want to represent and

how we choose ultimately to represent it questions then on these representations of formats be it numbers or letters or

soon more yeah and sorry why is why is what so popular popular

yeah so we'll come back to this in a few weeks in fact there are other ways to represent numbers binary is one decimal

is another unary is another and heximal is yet a fourth that uses 16 total digits literally 0 through 9 plus AB CDE

EF and somehow you can similarly count even higher with those uh we'll see in a few weeks why this is uh compelling but

heximal long story short uses four bits per digit and so four bits if you have two digits in HEX that gives you eight

and it's just a very convenient unit of measure and it's also human convention in the world of like files and other

things but we'll come back to that soon other questions the lights on the stage supposedly do the lights on the stage

supposedly say anything well if we had thought in advance to use maybe 64 light bulbs that would seem to give us uh

eight total bites on stage eight times uh eight giving us just that maybe good question other questions on zeros and

ones it's a little bright in here no oh

yes where everyone's pointing somewhere specific there we go sorry very bright in this

corner oh sure and we'll come back to this in some form in the coming days too at at a slower Pace too we have with

eight bits two possible values for the first and then two for the next two for the next and so so forth so that's 2 * 2

* 2 that's 2 to 8th power total which means you can have 256 total possible patterns of Zer and ones but as we'll

seen soon computer scientists programmers software often starts counting at zero by convention and if

you use one of those patterns 0 00 0 000000 0 to represent the decimal number we know is zero you only have 255 other

patterns left to count as high as therefore 255 that's all good question

question all right so what then might we have besides uh these emojis and letters and numbers well we of course have

things like colors and programs like Photoshop and pictures and photos well let me ask the question again how might

a computer do you think knowing what you know now represent something like a color like what are our options if all

we've got are zeros and ones and switches yeah RGB when RGB indeed is This Acronym

that represents some amount of red and some amount of green green and blue and indeed computers can represent Colors by

just doing that remembering for instance this dot this yellow dot on the screen that might be part of any of those

emojis these days well that's some amount of red some amount of green some amount of blue and if you sort of mix

those colors together you can indeed get a very specific one and we'll see in just a moment just that so indeed

earlier on did uh humans only use seven bits total and it was only once they decided oh let's add an eighth bit that

they got extended asy and that was initially in part A solution to the same problem of not having enough room if you

will in those patterns of zeros and ones to represent all of the characters that you might want but even that wasn't

enough and that's why we've now gone up to 16 and 32 and long past 7even so if we come back now to this one particular

color RGB was proposed as a scheme but how might this work well consider for instance this if we do indeed decide as

a group to represent any color of the rainbow with some mixture of some red some green and some blue we have to

decide how to represent the amount of red and green and blue well it turns out if all we have are zeros and ones airgo

numbers let's do just that for instance suppose a computer we using these three numbers 72 73 33 no longer in the

context of an email or a text message but now in the context of something like Photoshop a program for editing and

creating graphical files maybe this first number could be interpreted as representing some amount of red green

and blue respectively and that's exactly what happens you can think of the first digit as red second as green third as

blue and so ultimately when you combine that amount of red that amount of green that amount of blue it turns out it's

going to resemble this shade of yellow and indeed you can come up with numbers between 0 and 255 for each of those

colors to mix any other color that you might want and you can actually see this in practice even though our screens

admittedly are getting really good on our phones and laptops such that you barely see the dots they are there you

might have heard the term pixel before pixel is just a DOT on the screen and you've got thousands millions of them

these days horizontally and vertically and if I take even this Emoji which again happens to be one company's

interpretation of a face with medical mask and zoom in a bit maybe zoom in a bit more you can actually start to see

these pixels things get pixelated because what you're seeing is each of the individual dots that compose this

particular image and apparently each of these individual dots are probably using 24 bits eight bits for red eight bits

for green eight bits for blue in some pattern and this program or some other like Photoshop is interpreting one

pattern it's white or yellow or black or some brown in between and so if you look sort of awkwardly but up close to your

phone or your laptop or maybe your TV you can see exactly this too all right well what about things that we also

watch every day on YouTube or the like things like video how would a computer knowing what we

know now represent something like a video how might you represent a video using only zeros and ones

yeah yeah exactly and to summarize what video really adds is just some notion of time it's not just one image it's not

just one letter or number it's presumably some kind of sequence because time is passing and so with a whole

bunch of images maybe 24 maybe 30 per second if you fly them by the human's eyes we can interpret them using our

eyes and brain that there is now movement and therefore video and similarly with audio or music if we just

came up with some convention for representing those same notes on a musical instrument could we have the

computer synthesize them too and this might be actually pretty familiar let me pull up a quick video here which uh

happens to be an old school version of the same idea you might remember from [Music]

childhood so granted that particular video is an actual video of a paper based animation but indeed that's really

all you need is some sequence of these uh these images which themselves of course are just zeros and ones because

they're just this grid of these pixels or dots now something like musical notes like these those of you who are musicans

might just naturally play these on physical devices but computers can certainly represent those sounds too and

for instance a popular format for audio is called midi and midi might just represent each note that you saw a

moment ago essentially as a a sequence of numbers but more generally you might think about music as having notes for

instance a through G maybe some flats and some Sharps uh you might have the duration like how long is the note being

heard or played on a piano or some other device and then just the volume like how hard does a human in the real world

press down on that key and therefore how loud is that sound it would seem that just remembering little details like

that quantitatively we can then represent really all of these these otherwise analog uh human realities so

that then is really a laundry list of ways that we can just represent information again computers or digital

have all of these different formats but at the end of the day and as fancy as those devices in yours are it's just

zeros and ones tiny little switches or light bulbs if you will represented in some way and it's up to the software

that you and I and others write to use those zeros and ones in ways we want to get the computers to do something more

powerfully questions then on this representation of information which I dare say is ultimately what problem

solving is all about taking in information and producing new via some process in

between any questions out there yeah yeah in back yeah we so a really good question there are

many other file formats out there you allude to MP4 for video and more generally the are these things called

codecs and containers it's not quite as simple when using larger files for instance in more modern formats that a

video is just a sequence of images for instance why if you stored that many images for like a Hollywood movie like

24 or 30 of them per second that's a huge number of images and if you've ever taken phone uh photos on your phone you

might know how many megabytes or larger even individual photographs might be so humans have developed over the years uh

fancier software that uses much more math to represent the same information more minimally just using somehow

shorter patterns of zeros and ones that are most simplistic representation here and they use what might be called

compression if you've ever used a zip file or something else somehow your computer is using fewer zeros and ones

to represent the same amount of information ideally without losing any information and in the world of

multimedia which we'll touch on a little bit in a few weeks there are both lossy and lossless formats out there lossless

means you lose no information whatsoever but more commonly as you're alluding to one is ly compression L OSS Y where

you're actually throwing away some amount of quality you're getting a some amount of pixelation that might not look

perfect to the human but heck it's a lot cheaper and a lot easier to distribute and in the world of multimedia you have

containers like Quicktime and other uh M containers that can combine different formats of video different formats of

audio in one file but there too do designers have discretion so more in a few few weeks too other questions then

on information here as well yeah know Compu used to be very big taking up like a whole room andu is the reason they've

gotten smaller because information what exactly I mean back in

the day you might have heard of the expression a vacuum tube which is like some physically large device um that

might have only stored some zero or one um yes it is the miniaturization of Hardware these days that has allowed us

to store as many and many more zeros and ones much more closely together and as we've built more fancy machines that can

sort of Design This Hardware at an even smaller scale we're just packing more and more into these devices but there

too is a trade-off for instance you might know by using your phone uh or your laptop for quite a while maybe on

your lap starts to get warm and so there are these literal physical side effects of this where now some of our devices

run hot and this is why like a data center in the real world might need more air conditioning than a typical place

because there are these physical AR facts as well and in fact if you'd like to see one of the earliest computers

from decades ago across the river here in now Alon in the new engineering building is the Harvard mark1 computer

uh that will give you a much big a better mental model of just that well if we come back now to this first picture

being computer science or really problem solving I dare say we have more than enough ways now to represent information

input and output so long as we all just agree on something and thankfully those before us have given us things like asky

and unicode not to mention MP4s Word documents and the like but what's inside of this proverbial black box into which

these inputs are going and the outputs are coming well that's where we get this term you might have heard too an

algorithm which is just step-by-step instructions for solving some problem incarnated in the world of computers by

software when you write software AKA programs you are implementing one or more algorithms one or more step uh sets

of instructions for solving some problem and maybe you're using this language or that but at the end of the day no matter

the language you use the computer is going to represent what you type using just zeros and ones so what might be a

representative algorithm nowadays you might use uh your phone quite a bit to make calls or send texts or emails and

therefore you have a whole bunch of contacts in your address book nowadays of course this is very digital but

whether on iOS or Android or the like you might have a whole bunch of names a first name and or last as well as

numbers and emails and the like and you might be in the habit of like scrolling through on your phone all of those names

to find the person you uh want to call uh it's probably sorted alphabetically by first name or last name a through z

or some other symbol and this is frankly quite the same as we used to do you know back in in my day cs50 when we just used

a physical book and this physical book might be a whole bunch of names alphabetically sorted from left to right

corresponding to a whole bunch of numbers so suppose that in this Old Harvard phone book we want want to

search for John Harvard we might of course start quite simply at the beginning here looking at one page at a

time and this is an algorithm this is like literally step by steps uh looking for the solution to this problem in that

sense if John Harvard's in the phone book is this algorithm Page by Page correct would you

say yes like if uh John Harvard's in the phone book obviously I'm eventually going to get to him so that's what we

mean by correct is it efficient is it well-designed would you say no I mean this is going to take forever even just

to get to the J's or the H's depending how this thing sorted all right well let me go a little faster I'll start like

two pages at a time 2 4 6 8 10 12 and so forth sounds faster is faster is it correct okay why is it not correct

yeah exactly if I start an odd number of pages and I'm going two at a time I miss pages in between and if I therefore

conclude when I get to the back of the book there was no John Harvard I might have just aired this would be again one

of these bugs but if I try a little harder I feel like there's a solution we don't have to completely throw out this

algorithm I think we can probably go roughly twice as fast still but what should we do instead to fix this yeah

I'm back nice so I think what many of us most of us if we even use this technology

anymore these days we might go roughly to the middle of the phone book just to kind of get us started and now I'm

looking down I'm looking for Jay assuming first name Jay Harvard and it looks like I'm in the M section so just

to be clear what should I do next okay and presumably it is John Harvard would be to the left of this so

here's an opportunity to figuratively enl literally tear this particular problem in half throw half of the

problem away it's it's actually pretty easy if you just do it that way the hard way is this way but I've now just uh

decreased the size of this problem really in half so if I started with like a thousand pages of phone numbers and

names now I'm down to 500 and already we haven't found John Harvard but that's a big bite out of this problem and I do

think it's correct because if J is to the left of M of course he's definitely not going to be over there and I think

if I repeat this is again dividing and conquering if you will here I might have gone a little too far now I'm in like

the E section so let me tear the problem in half again throw another 250 Pages away and again repeat dividing and

dividing and conquering until finally presumably I end up with just one page of a phone book on which John Harvard's

name either is or is not but because of the algorithm you proposed step by step I know that he's not in anything I

discarded so dramatic as that might have been um uh been made out to be it's actually

just harnessing pretty good human intuition indeed this is what programming is all about too it's not

about learning a completely new world but really just how to harness intuition and ideas that you might already have

and take naturally but learning how to express them now more succinctly more precisely and using things called

programming languages why is an algorithm like that if I found John Harvard better than ultimately just

doing the first one or even the second maybe doubling back to check those even Pages well let's just look at a little

charts here again we don't have to get into the the nuances of numbers but if we've got like a chart here XY plot on

the x-axis here I claim is the size of the problem so measured in the P numbers of pages in the phone book so the

farther you go out here the more pages are in the phone book and here we have time to solve on the y- axis so the

higher you go up the more time it's going to be taking to solve that particular problem so let's just

arbitrarily say that the first algorithm involving like n Pages might be represented graphically like this no

matter the slope it's a straight line because there's presumably a onetoone relationship between numbers of pages

and number of seconds or number of page turns why if the phone company adds another page next year because some new

people move to town that's going to require one additional page for me one to one if though we use the second

algorithm flawed though it was unless we double back a little bit to fix someone being in between that's two going to be

a straight line but it's going to be a different slope because now there's a two: one or a one: two relationship

because I'm going two pages at a time so if the phone company adds another page that's going to take me only or another

two pages that's still only just one more step and you can see the difference if I kind of dra draw this if this is

the phone book in question this number of pages it might take this many seconds on the yellow line to represent or to

solve uh to find someone like John Harvard but of course on the first algorithm the red line

it's literally going to take twice as many steps and what do the ends here Meet n is the go-to variable for

computer scientist or programmer just generically representing a number so if the number of pages in the phone book is

in the number of steps the second algorithm would have taken would be in the worst case n/ two half as many

because you're going twice as fast but the third algorithm actually if you recall your your logarithms looks a

little something like this there's a fundamentally different relationship between the size of the problem and the

amount of time required to solve it that technically is log based two event but it's really the shape that's different

and the implication there is that if for inston Cambridge and Austin two different towns here in Massachusetts

merge next year and there's just one phone book that's twice as big no big deal for that third and final algorithm

why you just tear the problem one more time in half taking one more bite that's it not another thousand bytes just to

get to the solution and put another way you can walk out way way way out here to a much bigger phone book and ultimately

that green line is barely going to have budged so this then is just a way of now formalizing and thinking about what the

performance or quality of these algorithms might be and before we now make one more formalization of the

algorithm itself any questions then on this notion of efficiency or now performance of

ideas yeah many um a lot of phone books over the years and if you or your parents have

any more still somewhere we could definitely use them because they're hard to find other questions but thanks other

questions here too no oh was that a murmur yes over here sorry say

again oh yeah hopefully and then we could uh then we'd have a little something more to use here so now if we

want to formalize further what it is we just did we can go ahead and introduce this a form of code AKA pseudo code

pseudo code is not a specific language it's not like something we're about to start coding in it's just a way of

expressing yourself in English or any human language succinctly correctly toward an end of getting your idea for

an algorithm across so for instance here might be how we could formalize the code the pseudo code for that same algorithm

step one was pick up the phone book as I did step two might be open to the middle of the phone book as you proposed that

we do first step three was probably to look down at the pages I did and step four gets a little more interesting

because I had to quickly make a decision and ask myself a question if person is on page then I should probably just go

ahead and call that person but that probably wasn't the case at least for John Harvard and I opened the M section

and so there's this other question I should now ask else if the person is earlier in the book then I should tear

the problem in half as I did but go left so to speak and then not just open to the middle of the left half of the book

but really just go back to step three repeat myself why because I can just repeat what I just did but with a

smaller problem having taken this big bite but if the person was later in the book as might have happened with a

different person than John Harvard then I should open to the middle of the right half of the book again go back to line

three but again I'm not going to get stuck doing something forever like this cuz I keep shrinking the size of the

problem lastly the only possible scenario that's left if John Harvard is not on the page and

he's not to the left and he's not to the right what should our conclusion be he's not there he's not listed and so

we need to quit in some other form now as an aside it's kind of deliberate that I buried that last question at the end

because this is H what happens all too often in programming whether you're new at it or professional just not

considering all possible cases Corner cases if you will that might not happen that often but if you don't anticipate

them in your own code code pseudo code or otherwise this is when and why programs might crash or you might see

stupid little spinning beach balls or hourglasses or your computer might reboot why it's doing something sort of

unpredictable if a human maybe myself didn't anticipate this like what does this program do if John Harvard's not in

the phone book If I Had omitted lines 12 and 13 I don't know maybe it would behave differently on a Mac or PC

because it's sort of undefined behavior and these are the kinds of omissions that frankly you're invariably going to

make bugs you're going to introduce mistakes you're going to make early on and me too 25 years later but you'll get

better at thinking about those Corner cases and handling anything that can possibly go wrong and as a result your

code will be all the better for it now the problem ultimately with learning how to program especially if you've never

had experience or even if you do but you learned a one language only is that they all look a little cryptic at first

glance but they do share certain alties and in fact we'll use this pseudo code to define those first highlighted in

yellow here are what henceforth we're going to start calling functions lots of different programming languages exist

but most of them have what we might call functions which are actions or verbs that solve some smaller problem that is

to say you might use a whole bunch of functions to solve a bigger problem because each functions tend to do each

function tends to do something very specific or precise these then in English might be translated in code

actual computer code to these things called functions highlighted in yellow now are what we might call conditionals

conditionals are things that you do conditionally based on the answer to some question you can think of them kind

of like Forks in the road do go left or go right or some other direction based on the answer to some question well what

are those questions highlighted now in yellow are what we would call Boolean Expressions named after mathematician

last name bull that simply have yes no answers or if you prefer true or false answers or Heck if you prefer one or

zero answers we just need to distinguish one scenario from another the last thing manifest in this pseudo code is what I

might highlight now and call Loops some kind of cycle some kind of directive that tells us to do something again and

again so that I don't need a thousand line program to search a thousand page phone book I can get away with a 13 line

program but sort of repeat myself inherently in order to solve some problem

until I get to that last step so this then is what we might call pseudo code and indeed there are other

characteristics of programs that we'll touch on before long things like arguments and return values variables

and more but unfortunately in most languages including some we will very deliberately use in this class and that

everyone in the world world these days still uses these programs tend to look like this this for instance is a

distillation of that very first program I wrote in 19 96 in cs50 itself just to print something on the screen and in

fact this version here just tries to print quote unquote hello world which is dare say the most canonical first thing

that most any programmer ever gets a computer to say just because but look at this mess I mean there's a hash symbol

these angled brackets parentheses words like int curly braces quotes parentheses semicolons and backslashes I mean

there's more overhead and more syntax and clutter than there is an actual idea now that not to say that you won't be

able to understand this before long because honestly there's not that many patterns inde programming languages have

typically a much smaller vocabulary than any actual human language but at first it might indeed look quite cryptic but

you can perhaps infer I have no idea what these other lines do yet but hello world is presumably quote unquote what

will be printed on the screen but what we'll do today after a short break and set the stage for next week is introduce

these exact same ideas and just a bit using scratch something that you yourselves might have used when you're

quite younger but without the same vocabulary applied to those ideas and the upside of what we'll soon do using

scratch this graphical programming language from our friends down the road at MIT it'll let us today start to drag

and drop things that look like puzzle pieces that interlock together if it makes logical sense to do so but without

the distraction of hashes parentheses curly braces angled brackets semicolons and things that are quite beside the

point but for now let's go ahead and take a 10-minute break here and when we resume we will start programming so this

on the screen is a language called C something that we'll dive into next week and thankfully this now on the screen is

another language called python that we'll also take a look at in a few weeks before long along with other languages

along the way today though and for this first week week zero so to speak we use scratch because again it'll allow us to

explore some of those programming fundamentals that will be in C and in Python and in JavaScript and other

languages too but in a way where we don't have to worry about the distractions of syntax so the world of

scratch looks like this it's a web-based or downloadable programming environment that has this layout here by default on

the left here we'll soon see is a pet of puzzle pieces programming blocks that represent all of those ideas we just

discussed and by dragging and dropping these puzzle pieces or blocks over this to Big area and connecting them together

if it makes logical sense to do so will start programming in this environment the environment allows you to have

multiple Sprites so to speak multiple characters things like a cat or anything else and those Sprites exist in this

rectangular World up here that you can full screen to make bigger and this here by default is scratch who can move up

down left right and do many more things too and within it scratches world you can think of it as perhaps a familiar uh

coordinate system with x's and y's which is helpful only when it comes time to like position things on the screen right

now scratch is at the default 0 comma 0 where x equals 0 and Y equals 0 if you were to move the cat way up to the top X

would stay zero y would be positive 180 if you move the cat all the way to the bottom X would stay zero but y would now

be negative 180 and if you went left X would become -240 but y would stay zero or to the right X would be 240 and Y

would stay zero so those numbers generally don't so much matter because you can just move relative ly in this

world up down left right but when it comes time to like uh precisely position some of these Sprites or other imagery

it'll be helpful just to have that mental model of up down left and right well let's go ahead and make perhaps the

simplest of programs here I'm going to switch over to the same programming environment now for a tour of the left

hand side so by default selected here are the category in blue motion which has a whole bunch of puzzle pieces or

blocks that relate to motion and whereas scratch as a graphical language categorizes things by the type of things

that these pieces do we'll see that throughout this whole pet we'll have functions and variables and conditionals

and Boolean expressions and more each in a different color and shape so for instance moving 10 steps or turning one

way or the other would be functions categorized here as things like motion under looks in purple you might have

speech bubbles uh that you can create by dragging and dropping these that might say hello or whatever for some number of

seconds or you could switch costumes change the cat to look like a dog or a bird or anything else in between sounds

too you can play sounds like meow or anything you might import or uh record yourself and then there's these things

scratch calls events and the most important of these is the first when green flag clicked because if we look

over to the right of scratch's world here this rectangular region has this green flag and red stop sign up above

one of which is for play one of which is for stop and so that's going to allow us to start and stop our actual programs

when that green flag is initially clicked but you can listen for other types of events when the space bar is

pressed or something else when this Sprite is clicked or something else and here you already see like a programmer's

incarnation of things you and I take for granted like every day now on our phones anytime you tap an icon or drag your

finger or hit a button on the side these are what a programmer would call events things that happen and are often

triggered by us humans and things that a program be it in scratch or python or C or anything else can listen for and

respond to indeed that's why when you tap the phone icon on your phone the phone application starts up because

someone wrote software that's listening for a finger press on that particular icon and so scratch has these same

things too under control in Orange you can see that we can wait for one second or repeat something some number of times

10 by default but we can change anything in these white circles to anything else there's another puzzle piece here

forever which implies some kind of loop where we can do something again and again and even though it's seems a

little tight there's not much room to fit something there scratch is going to have these things grow and Shrink

however we want to fill similarly shaped pieces and here's those conditionals if something is true or false then do this

this next thing and that's how we can put in this little trapezoid like shape some form of Boolean expression a

question with a yes no true false or one zero answer and decide whether to do something or not you can mess uh combine

these things too if something is true do this else do this other thing and you can even tuck one inside of the other if

you want to ask three or four or more questions sensing too is going to be a thing you can ask questions AKA Boolean

expressions like is the Sprite touching the mouse pointer the arrow on the screen so that you can start to interact

with these programs uh what is the distance between a Sprite and a mouse pointer you can do simple calculations

just to figure out maybe if the the enemy is getting close to the cat under operators some lower level stuff like

math but also the ability to pick random numbers which for a game is great because then you can kind of vary the

difficulty or what's happening in a game without the same game playing the same way every time and you can combine ideas

something and something must be true in order to make that kind of decisions before or we can even join two wors

together says apple and banana by default but you can type in or drag and drop whatever you want there to combine

multiple words into full larger sentences and then lastly down here there's in Orange things called

variables in math we've obviously got X and Y and whatnot in programming we'll have have the same ability to sort of

store in these named symbols X or Y values that we care about numbers or letters or words or colors or anything

ultimately but in programming you'll see that it's much more conventional not to just use Simple letters like X and Y and

Z but to actually give variables full words or word uh singular or plural words to describe what they are and then

lastly if this isn't enough colors of blocks for you you can create your own blocks and indeed this is going to be a

programming principle will apply today and with the first problem set whereby once you start to assemble these puzzle

pieces and you realize oh would have been nice if those several pieces could have just been replaced by one had MIT

fought to give me that one puzzle piece you yourself can make your own blocks by connecting these all together giving

them a name and boom a new puzzle piece will exist so let's do the simplest most canonical programs here starting up with

control and I'm going to click and drag and drop this thing here when green flag clicked and then I'm going to grab one

more for instance under looks and under looks I'm going to go ahead and just say something like initially not just hello

but the more canonical hello comma world now you might guess that in this programming environment I can go over

here now and click the green flag and voila hello comma world so that's my first program and obviously much more

userfriendly than typing out the much more cryptic text that we saw on the screen that you too will type out next

week but for now we'll just focus on these ideas and in this case a function so what is it just that just happened

this purple block here is say that's the function and it seems to take some form of input in the white oval specifically

hello comma World well this actually fits the Paradigm that we looked at earlier of just inputs and outputs so if

I may if you consider what this puzzle piece is doing it actually fits this model the input in this case is going to

be hello comma World in white the algorithm is going to be implemented as a function by m called say and the

output of that is going to be some kind of side effect like the cat and the speech bubble are saying hello world so

already even that simple drag and drop mimics exactly this relatively simple mental model so let's take things

further let's go ahead now and make the program a little more interactive so that it says something like hello David

or hello Carter or hello to you specifically and for this I'm going to go under sensing and you might have to

poke around to find these things the first time around but I've done this a few times so I kind of know where things

are and what color there's this function here ask what's your name but that's in white so we can change the question to

anything we want and it's going to wait for the human to type in their answer and this function called ask is a little

different from the say block which just had this side effect of printing a speech bubble to the screen the ask

function is even more powerful in that after it asks the human to type something in this function is going to

hand you back what they typed in in the form of what's called a return value which is stored ultim timately in by

default this thing called answer this little blue oval here called answer is again one of these variables that in

math would be called just X or Y but in programming we we're saying what it does so I'm going to go ahead and do this let

me go ahead and drag and drop this block and I want to ask the question before saying anything but you'll notice that

scratch is smart and it's going to realize I want to insert something in between and it's just going to move

things up and down I'm going to let go and ask the default question what's your name and now if I want to go ahead and

say hello David or Carter let's just do hello comma cuz I obviously don't know when I'm writing the program who's going

to use it so let me now grab another looks block up here uh say something again and now let me go back to sensing

and now grab the return value represented by this other puzzle piece and let me just drag and drop it here

and notice it's the same shape even if it's not quite the same size things will grow or Shrink as needed all right so

let's now zoom out let me go and stop the old versions because I don't want to say hello world anymore let me hit the

green flag and what's my name all right David enter huh all right maybe I just wasn't

paying close enough attention let me try it again green flag da a enter this seems like a

bug what's the bug or mistake might you think uh yeah yeah we kind of want to combine

them in the same text box and it's you know it's technically a bug because this just looks kind of stupid it's just

saying David after I W for my name I'd like it to say maybe hello then David but it's just blowing past the hello and

printing David but let's put our finger on why this is happening you're right for the solution but what's the actual

fundamental problem and back perfect I mean computers are really darn fast these days it is saying hello

all of us are just too slow in this room to even see it because it's then saying David on the screen so fast as well so

there's a coup of solutions here and yours is spot on but just to poke around you'll see the first example of how many

ways in programming be it scratch or C or python or anything else that there are going to be to solve problems and

we'll teach you over the course of the weeks Sometimes some ways are better relatively than others but rarely is

there a Best Way necessarily because again reasonable people will disagree and what we'll try to teach you over the

coming weeks is how to kind of think through those nuances and it's not going to be obvious at first glance but the

more programs you write the more feedback you get the more bugs that you introduce the more you'll get your

footing with exactly this kind of problem solving so let me try this in a couple of ways up here would be one

solution to the problem MIT anticipated this kind of issue especially with first-time programmers and I could just

use puzzle piece that says say the following for two seconds or one second or whatever then do the same with the

next word and it might be kind of a bit of a pause hello 1 second 2 seconds David 1 second 2 seconds but at least it

would look a little more GR atically correct but I can do it a little more elegantly as you propos let me go ahead

and throw away one of these blocks and you can just drag and let go and it'll delete itself let me go down to

operators because this join block here is the right shape and so even if you're not sure what goes where just focus on

the shapes first let me drag this over here and it grew to fill that let me go ahead and say hello comma space and now

it could just say by default hello banana but let me go back to let me go back to S

drag answer and that's going to drag and drop there and so now notice we're sort of stacking or nesting one block on

another so that the output of one becomes the input to another but that's okay here let me go ahead and zoom out