mucho gusto me llamo David Malan hablo
poca español but this will be in English
if that's okay as this morning but so
nice to see some familiar faces and some
new ones as well as Jose said we thought
we'd give you an introduction to
computer science the goal of which is to
empower you to have more technical
conversations perhaps with those
students who are taking Jose's class
right now or those of you who are first
years who might like to take Jose's
class next semester or beyond please
feel free to join us in cs50 and in CAI
so computer science is something that's
unfamiliar to a lot of people for
instance what is computer science anyone
who's not in Jose's class what is
computer science yeah I see no one's put
up the very few people have put up their
name tags in this one that's okay
chaos loud informatica anyone at all
anyone at all
so all right someone how about this from
Jose's class what is computer science
yes please ok ok ok good I really like
that so it's the study it's getting
computers to do what we want them to do
and more generally it's the study of
information and like the processes
around information that allow you to
actually solve problems and frankly this
did not this was not clear to me when I
first was able to study computer science
way back in high school even in la
escuela second Nadia I did not study
computer science because I thought it
was only about programming and it seemed
very antisocial and everyone's heads
were down in the computer lab and they
seemed very focused only on the keyboard
but really it wasn't until college when
I took a course called cs50 that I
discovered that it really is more
generally about problem solving and
what's exciting about computer science
is that it's not just useful within the
domain of computer science and press'll
analyzing data and information but it
really is something that you can bring
back
your own world whether that's in the
physical sciences Natural Sciences arts
humanities business or the like because
it's really all about teaching you
computational thinking it cleans up your
thinking process it helps you think more
logically it helps you express yourself
more precisely more correctly and as
such it just makes you a much better
communicator and ultimately decision
maker and so with that said let's start
really at the beginning what does it
mean to think computationally what means
to think methodically more carefully or
as we'll see more algorithmically so to
speak and what does it mean to solve a
problem
well I'd propose that it really is just
this any problem in the world just has
some input the problem that you want to
solve and you want some solutions so
we'll call that the output and in
between here is some kind of process
some kind of problem-solving mechanism
that actually gets the job done
but it's pretty fair to say that this is
computer science at least at a very high
level but before we can discuss inputs
and outputs we like a computer
scientists need to decide how to
represent information after all at the
end of the day our computers our phones
only have say electricity so we really
all need to agree in advance how we
somehow use electricity to represent
inputs and outputs and it's kind of
funny that I just counted the two
ingredients to this problem how might we
represent information if we're just
counting information the number of
people in the room well 1 2 3 4 5 or I
could count higher certainly if I used
hash marks 1 2 3 4 5 6 and so forth and
so that actually that process has a name
it's called unary notation uno implying
1 and that's just because you have one
single mark or one type of digit of
finger via which you can count people so
just a casual warm-up exercise because
there's a lot of folks who obviously
don't know much about computer science
we would call you back home those less
comfortable and that's totally fine
that's the largest demographic of
students taking cs50 back home how high
can I count on one hand I hear 5 6 ok 6
is not right but it is not 5 it's not 5
you're all wrong somehow well why is
that well odds are if you'd like me you
start counting pretty reasonably like 1
two three four five okay now we're out
of fingers unless we start using the
second hand so five would seem to be the
highest but that's because I didn't
really think very hard about this
problem and represent the information as
efficiently as optimally as I might be
able to write I'm just putting my
fingers up or down but I'm really taking
note into it not intake I'm not even
taking into account the order in which
I'm raising or lowering my fingers what
if instead this still represents zero
I've not counted anyone yet but what if
I do this is one and then maybe this is
two and then this is three and then if
we keep counting it's slightly offensive
in some cultures this is four this is
then five this is then six this is now
seven so even if you didn't quite follow
the exact pattern I was doing it was
obviously not as simple as one two three
four five I was instead kind of
permuting them in different ways by
raising and lowering them thereby making
a pattern out of them and so in that
case it actually is significant is my if
my finger is up or it's down that is
there's two states my finger can be in
it's not just that there's a hash mark
there or not my finger is either up or
down proactively and that's called
binary notation by implying two and
that's because each of my fingers can
either be down or up or we might call
this off or on or zero or one but more
on that in just a moment so in other
words I can actually count much higher
than five with five fingers does anyone
know or want to do the math how high can
I count yeah it's 31 it's very painful
to count the 31 on your five human
fingers because I don't think I can
arrange my fingers it's quite cleanly
enough to do that but there are indeed
32 total patterns of fingers up and down
on just one hand if I start at zero and
I go up to all five there's 32 total but
if this is zero and this is all up then
if I've got 32 possibilities I can count
from 0 to 31 it turns out but more on
that in just a little bit so that's a
lot and that suggests that with a little
bit more thought and a little bit more
cleverness as to how a computer
scientist represents information you can
pack a lot more information into very
limited space so how do we get though
from unary to binary to computers well
at the end of the day
you probably all know or have heard that
computers only understand binary zeros
and ones so what does that really mean
well it turns out the computers even
though they might seem pretty
sophisticated they're pretty dumb
devices right the only first of all do
what we tell them to do and that's the
power is priscila notes of getting a
computer to do something for you but
moreover they only take one simple input
they take like electricity from the wall
or maybe from your battery and even if
you've not studied electricity it's you
know electrons flowing in or out of the
device somehow powering the device
that's the only physical input and so
how perfect is it that there's a way to
represent information by either putting
a finger down or up or off or on that is
two different states because you can
represent two states really easily for
instance my laptop right now is on and
thankfully it has battery now it would
be potentially off because it's not
plugged in on electricity is flowing or
off so why is this germane well a
computer it turns out can represent
information just by storing or not
storing electricity and that's powerful
because you can somehow use electricity
either on or off or on or off and
represent it turns out different numbers
but what are those numbers going to be
well consider this even if you've never
well let me ask you a question first how
many of you can speak binary or
understand binary
all right Priscilla and a few other
people okay so most people not but it
turns out give me like two minutes and
everyone in this room will be able to
why well first let's start where we all
started as kids if you saw this on the
board this is of course what number yeah
123 right it's all very intuitive to us
but why really all I did was draw three
symbols on the board I kind of went like
this and then this kind of curvy stroke
and then a slightly more curvy stroke
and drew these symbols on the board but
you all sort of instinctively assigned
meaning to each of these symbols and
quickly mathematically got to 123 but
why is that well if you're like me in
the US I grew up learning that this is
kind of the ones place or the ones
column this is the tens place or the
tens column this is the hundreds place
or the hundreds column and then so forth
you keep multiplying by ten and so the
reason that one two three is 123 is
because this is technically a hundred
times
one and this is 10 times 2 and this is 1
times 3 that of course is a hundred plus
20 plus 3 and this of course is 123 now
this might seem like circular logic
because I've literally written down the
same thing but now we've ascribed
meaning to do local positions of each of
those symbols on the board now what are
these places really representing not to
get too technical but they're just
powers of 10 right the ones place is
technically 10 to the 0 because 10 to
the 0 is 1 the next place is actually 10
to the 1 and 10 to the 1 is 10 this is
of course 10 squared or 10 to the 2 and
that gives you 100 and so 10 to the 3 10
to the 4 10 to the 5 these are just
powers of 10 so a computer and most of
you a moment ago claimed not to speak
binary a computer is fundamentally
really the same exact thing except each
of the places is not a power of 10 it's
probably a power of 2 instead right we
humans sort of Nadd naturally these days
speak decimal Dec meaning 10 and that's
0 1 2 3 4 5 6 7 8 9 computer turns out
speaks binary and by convention a
computer only understands 0 & 1
and that might seem very limiting at
first glance but if this is the ones
place now this is the twos place this is
the fours place than 8 16 32 we can
represent the exact same numbers just
with different patterns but now the
symbols I can draw are not 0 through 9
they're 0 through one so a little more
limiting but that's ok because the
columns will allow me to do the same
kind of math so for instance given this
logic if the only two things I can write
with this chalk is a 0 or a 1 how do we
represent in binary that is zeros and
ones only the number we humans know as
zero yeah yeah so 0 0 0 it's kind of
trivial why well just 4 times 0 plus 2
times 0 plus 1 times 0 is still 0 so
that's ones not that interesting how
would we represent the number we'd
humans know in decimal as 1 0 0 1 yeah
so 0 0 1 and this is where it might get
a little tricky for a moment how about 2
yeah zero one zero and this is where now
we see the connection to how what I was
doing with my fingers I didn't go what 0
1 2 the second time I went 0 1 2 thereby
changing my finger from like a 1 to a
zero and a zero to one to give me this
pattern and of course if you want to
represent 3 it's gonna be yeah 0 1 1 and
now how about 7 yeah 1 1 1 right because
that's 4 times 1 plus 2 times 1 plus 1
times 1 so 4 plus 2 plus 1 is 7 and then
maybe it's your question how do I
represent 8 yeah we need another
placeholder and that's fine you know if
we were on a piece of paper or a board I
can of course just write a 1 here and
then these of course now need to become
zeros because implicit to the left here
was going to be the eights place even
though I don't need to write it from the
get-go but there's now a limitation
computers of course are physical devices
and even if you have the fanciest of
Mac's or pcs like you only have so much
room in that computer you only have so
much memory so much hardware so it's
certainly finite and so let's actually
dive down into what's inside of a
computer such that you can actually
represent the number 7 or 8 or anything
in between using an actual computer well
it turns out that inside of a computer
or in simple form just like lots of tiny
little light bulbs or more specifically
little switches that can be turned on
and off and those switches when turned
on and off either allow you to store a
little bit of electricity that came from
the wall or the battery or allow it to
dissipate and go away so those switches
are called transistors if you've heard
the term transistors just a tiny little
microscopic switch and CPUs these days
central processing units the brains
inside of a computer the Intel Inside
Hardware has millions of these tiny
little switches but for the moment I
only have three of these switches and so
I claim that the number I'm currently
representing with these three light
bulbs is what number if they're all off
zero so if you shrunk these back these
light bulbs down put them into your
phone or computer that's effectively
that was very dramatic with all the
chalk that's effectively how your
computer would store 0 and if you want
to distort the number one well you might
just
turn one of the transistors on store a
little bit of electricity so now the
computer recognizes this pattern of
electricity if I want to represent to do
I want to just do this no so this should
go off because this is the ones column
twos column fours column so this is to
this of course is 3/4 is you through
this one here so for this goes off off
that's 4 5 all the way over here ok 6
middle yep and finally 7 and now you see
the physical problem what if you want to
represent 8 while all of us would have
just carried the 1 so to speak just as I
did on the board so ok that's a zero
that's a zero that's a zero and damn
like we're now out of space and less of
course thankfully the team brought
another light bulb and now you have more
memory right and so herein lies kind of
the origins of why you run out of
memories sometimes and what it means to
run out of memory just means you can't
count as high or you can't store for
instance as many files in your
computer's memory at once or you can't
load as many programs at once because at
some point you do run out of physical
space but it really just boils down to
these very simple primitives so
literally everything inside of your
computer ultimately boils down to zeros
and ones tiny little switches if you
will those transistors that just or
patterns of electricity thereby
representing values and without getting
ahead of ourselves if you were to study
a hardware class in computer science and
really become an electrical electrical
engineer you would also explore the
reality that when you have an intel cpu
intel is inside not only does that cpu
know how to store information it also
has no it also knows how to perform
certain operations addition subtraction
moving values from this location in
memory over here or vice versa and
that's what a cpu really does it just
manipulates these zeros and ones moves
them around adds them together and so
forth but for now let's leverage a
principle in computer science that's
known as abstraction an abstraction is
just this general technique whereby you
take a very simple if like boring idea
and we just all agree ok I get it I
understand that the computers can count
to seven
or to aid or to hire but I don't really
care here on out how they do it right
certainly in the business world it's
rare that you're going to need to you
know make any arguments in binary but
that's fine we can abstract on top of
this and just stipulate computers can
count as high as they want so long as
they have enough memory there's a way of
doing that but how do we represent other
pieces of information right computers
don't just do math they don't just run
Excel and calculators they have word
processing programs they have
spreadsheets PowerPoint tools so there's
words and letters so does anyone want to
wager a guess at how a computer can
represent not numbers but rather letters
of the alphabet
let's ascii table okay so that's a
that's a loaded answer what do you mean
by ASCII table
okay and let me focus on part of the
answer before we introduce what this
term is ASCII I like your idea of just
like a chart so if we want to represent
the letter A but at the end of the day
all computers can represent is you know
numbers zeros and ones or really decimal
numbers by turning switches on and off
well why don't we all just agree that
you know what anytime you want to
represent the letter A thank you with
Microsoft Word or Google Docs why don't
we just have the computer store I don't
know like the number one and any time
the computer wants to store the letter B
store the number two and C can be the
number three and so forth in other words
if we all just agree as humans using
these computers to use the same patterns
of bits and bit if you've ever wondered
is just binary digit it's a conjunction
of the two bit binary digit it's a zero
or one if we just agree that all of
these can be represented yes in switches
in transistors as zeros and ones well
let's just agree that anytime you're
writing an email or a document and you
type the letter A but the computer is
just going to store the number one with
some sequence of transistors and be the
number two and so forth now it turns out
that's all a computer does indeed to
store text but for whatever reason
humans did not choose simple numbers
like 1 2 3 it turns out that decades ago
humans decided but the letter A shall be
65 B shall be 66 c shall be 67 and so
forth and there's other numbers for
things like punctuation and for
lowercase letters and a few other
symbols you would see on a typical
keyboard and that indeed is as high made
notes is a system called ASCII happens
to be the American Standard Code for
information interchange and the American
in the acronym there is actually germane
because we were a little selfish we
didn't really leave room for things like
accented characters or Tilda's or any
number of Asian characters that you
might need ascii only used 7 bits so a
pattern of 7 light bulbs and it turns
out with 7 light bulbs you can only
count as high as 128 it turns out if you
do out the math so that means you can
have a total of 128 characters in your
alphabet which means there were no
accented A's or ease or Tilda's on ends
let alone very
Asian characters it was by design very
American centric so this was ASCII but
there's something newer that has
actually addressed that problem does
anyone know what that is there's another
term that describes same idea it's just
a different chart but more inclusive it
Felix yeah so Unicode if you've ever
heard the expression it's sort of you
know one code for everyone uses either
seven or really eight bits as needed or
sometimes sixteen bits or sometimes 24
bits or even sometimes 32 bits that is a
lot of light bulbs to represent letters
and frankly if you have 32 light bulbs
each of which can be on or off does
anyone want to guess how many possible
patterns of light bulbs there are if you
have 32 of them total how high can you
count in other words then I heard
billions so it's actually roughly 4
billion so if I had 32 light bulbs here
which doesn't seem like a crazy amount I
could actually permute those switches on
and off in different patterns in 4
billion different ways which is to say
Unicode has a lot of room for any and
all characters so what are the
implications of this well let's just see
how this might map so if black capital a
is 65 let's see how we might actually
look at an actual word in ASCII so
here's a quick cheat sheet that's a
little longer than the one I drew here a
is 65 I is 73 and so forth suppose that
you received a text message or an email
and if you really looked underneath the
hood of the computer like what pattern
of bits is it storing when you got that
text message or that email suppose that
the pattern of bits you received happen
to be a bunch of zeros and ones that if
you do out the math like we did over
here works out to be the number 72 then
the number 73 yeah so you literally just
got a text message or an email that says
H I or hi and that's why so you're come
phone or your computer might have gotten
what 8 or 16 total bits that were on and
off in the right patterns to represent
the decimal number 72 or 73 and your
phone because it's context-sensitive or
your laptop because it knows you have
the text messaging program open
or you have your email program open it's
not gonna show you zeros and ones it's
not going to show you decimal numbers
like in a calculator or spreadsheet it's
gonna show you the corresponding ASCII
or Unicode letters which is H I question
No
so what if you got like one more
character this one you would have to
guess but suppose that the pattern were
72 73 33 anyone want to guess what
message you just got high with a
exclamation point so like hi this would
be in a more excited one and you
wouldn't know this other than by looking
it up and indeed you can Google ASCII
chart or Unicode chart and you can see
the hundreds or thousands of pairings of
letters and numbers but yes 33 happens
to be the number that some Americans
years ago decided shall represent in
exclamation points so that's all nice
and good but of course in the world we
have other letters that we want to
represent not just with these patterns
of say H I in an exclamation point what
if we want to abstract further on that
and actually get more familiar symbols
that are all the more common in the
language like Spanish like these where
you want accented characters well that's
where you need Unicode because it turns
out you can't cram all of those possible
letters into just seven bits of patterns
so we need unicode and it turns out that
one of the reasons for this trend these
days that I'm sure you have down here
are these things called emojis right
these look like pictures but they're not
technically pictures these are
characters these are characters like a
and B and C it's just that they happen
to be more graphical why well partly
because once you have four billion
possible values for every letter in your
alphabet that frankly just leaves a lot
of free room to like be creative and so
humans every year lately have been
adding more and more symbols to Unicode
to represent human emotions and Smiley's
like this and characters and so forth
but they literally are just characters
that maybe in the future you could type
a smiley face on your computer because
it's an actual key so as an aside when
we talk about Unicode this is a face
with tears of joy it's apparently
according to Apple at least the most
popular emoji right now does anyone want
to guess
what number is used to represent face
with tears of joy
65 66 67 are already taken so it's some
other number any guesses between beat
could be between 33 and 64 formally
because those are the only ones we
haven't looked at yet baby
emojis didn't come out early enough to
fit in that range so they're actually
much bigger values yeah maybe 500 but
you'd have to go even further because
there's a lot of darn emojis these days
yeah that was strangely precise but yes
perhaps and indeed if we actually do
this in decimal if you receive a text
message with a face with tears of joy
today your phone or a laptop has just
received literally a pattern of bits
that represents the number 120 8514 why
just because that one was available and
all of those other variants of Smiley's
are a little bigger than this number and
a little smaller which just means you
get a pattern of bits that your phone or
your laptop interprets as that smiley
face because of the context if you're in
the text messaging program or in your
email program they're displayed as
pictures and not as numbers as they
might be if that same pattern of zeros
and ones were received in like an excel
file or some calculator type format it
just depends on the context so any
questions then on Unicode or how this
how computers do this mapping and again
the goal at hand is how do we represent
information inputs and outputs we did
zeros and ones we did decimal we did
letters and emojis yeah
really good question so computers have
generally standardized how many bits it
uses at a time to represent information
even if some of those bits are wasted so
in our human world I stopped I didn't I
could have written not just one two
three I could have written 0 1 2 3 or 0
0 1 2 3 or 0 0 0 1 2 3 those are all the
same mathematically but I just don't cuz
it's stupid right why write numbers that
you don't need to but computers to avoid
the ambiguity that you identify always
use or almost always use 8 bits at a
time or 16 or 24 or 32 they use some
multiple of 8 typically and that means
that you can distinguish one characters
ending from the next character start by
looking at those boundaries really good
question other systems if you're
familiar with Morse code do not have
this feature and so you can get
ambiguous words out of Morse code
because sometimes a dot and a dash might
actually be a dash and a dot in
different contexts depending on where
you separate them really good quiet good
question all right so we have zeros in
well actually at the lowest level we
have like electricity literally coming
out of the wall or the floor then we
have zeros and ones that we can
represent by just turning switches on
and off from zeros and ones we get
decimal and from decimal we can get to
ASCII so again these are sort of levels
of abstractions sort of conceptually
we're working our way up so we never
again have to think about binary let
alone electricity but what about more
interesting aspects of a computers not
just text but build about something like
colors if you even if you've never
thought about it you've probably seen
this acronym like red green blue is what
it denotes in English and that just
refers to a convention just like ASCII
or Unicode whereby humans use patterns
of bits zeros and ones to represent
colors as well and they do so by mixing
some amount of red some amount of green
some amount of blue together and
depending on how you mix those three
colors you can get any color of the
rainbow you just need to specify how
much red or green or blue you actually
want so it turns out that computers
typically use eight bits which again is
a multiple of eight as I noted to
represent how much red how much green
how much blue
which is to say eight plus eight plus
eight 24 bits or typically used total to
represent colors on a screen so if the
smallest number you can represent with
eight bits is of course zero right all
the light bulbs are off the largest
number you can represent with eight bits
happens to be 255 if we did out the math
that just implies that if you want no
red this should be zero but if you want
a lot of red this should be 255 and same
for green and blue so in that context if
you were to look inside of your computer
and discover that your computer is
storing 72 amount of red 73 amount of
green and 33 amount of blue recall that
those same numbers or bad urns in the
context of a text message or an email
might ever actually represent hi
exclamation point but if you were to
open Photoshop or some graphical program
that is interpreted posed to show colors
not letters any guesses as to what you
get by combining like a medium amount of
red a medium amount of green and just a
little bit of blue and again the range
is from 0 to 255 anyone want to guess
what you get when you combine those
colors for saw yeah it's a shade of
yellow that looks quite like this here
why well that's just what happens when
you combine those wavelengths of light
essentially so what does this mean well
if you've ever looked really close on
your computer screen or even a
flat-screen TV you might have seen
actual dots like things get kind of
splotchy the closer your human eyes get
what are those things called that you're
looking at the dots yeah they're called
pixels and they literally are just dots
on the screen your TV your phone your
laptop is just thousands of tiny little
dots little squares each of those
squares typically in a computer is
represented with a pattern of 24 bits 8
showing how much red eight showing how
much green eight showing how much blue
and so if you think of those three
colors red green blue just overlapping
you get a single dot like this that
represents 24 bits so if you've ever
looked or cared how big your photographs
are when you're storing them on your
laptop or your phone or any of your file
sizes those file sizes are measured not
in bits but what units of measure yeah
so megabytes maybe or kilobytes or
gigabytes if it's a
videofile well a bite be y te is just
eight bits why
well one bit is generally pretty useless
you can only count as high as one so
units of eight we're common there too so
eight bits is one byte one megabyte is 1
million bytes which is to say that if
you have a lot of these little dots each
of which takes up eight plus eight plus
eight or three bytes you can literally
do out the math and figure out how big
your photograph might be because if you
know it's this many pixels wide and this
many pixels tall and each of those dots
takes up three bytes eight bits plus
eight bits plus 8 bits for red green
blue you can literally do out the math
and say oh this photographs going to be
three megabytes because of that simple
math so even though these file sizes
might seem completely arbitrary they can
be mapped directly to this kind of math
now as a side computers are smart these
days they compress files to save space
so it's not quite as simple as that
but it's an upper bound it indeed is and
we can see this even in this emoji right
if we start zooming in digitally on this
we can start to see these pixels and if
we go really close to his eyes you'll
see these squares which are indeed just
dots and so there's different colors
here like each of these yellow dots is
storing represented with one pattern
this shade of black is store or
represented with one other pattern and
the shades of gray are slightly
different patterns but that's all they
are is bit and in the context of a
graphics program like Photoshop your
computer will show you them as such
alright so we've got electricity zeros
and ones decimal ASCII or Unicode now
colors now images because an image is
just a whole bunch of colors left to
right top to bottom what comes next
yeah so what's a video what's a movie
file yeah it's a representation of
multiple pictures right that just fly
across the screen really fast creating
the illusion or tricking our human
brains into thinking there's actual
motion if you grew up with one of those
little paper flip books little cartoons
and you flip them really fast it looks
like some cartoon is being animated but
no your brain is just kind of
interpolating so to speak it's
interpreting all that most of those
changes as movement even though every
picture is actually stationary so if
you've ever heard that a Hollywood movie
is
24 frames per second or 30 frames per
second which are common units of measure
that just means you are being shown by
some producer 24 pictures per second or
30 pictures per second which are
probably slightly different from each
other
thereby creating the illusion of
movement so now we're all the way at the
top of the sort of abstraction layer
here whereby now we have videos and we
started with like the most mundane of
details and that really is what computer
science is about - not just representing
information but sort of solving a
problem at this level using it as the
input to another problem using that as
the input to another problem so now
we're having kind of a cool conversation
about video files when at the end of the
day we just started with like
electricity coming out of the wall so
that principle of abstraction is
inherent in computer science and this is
kind of the thing you learn when taking
a class like that and these an emoji z'
that you have if you have an iPhone for
instance silly little video files that
track your face these days they're just
sequences of images being shown to you
pretty quickly looping no less and
that's all an image or video file like
this might be alright so that's two out
of our three topics inputs and outputs
we just need this thing in the middle
but before we forge ahead any questions
or confusions yeah Carlos yes so sound
is also similar where you'll typically
measure like the the frequency of a
sound wave so how quickly it's going up
and down and also the wavelength both of
which can really be encoded as numbers
as well as ones and zeros indeed indeed
and back was there question
no Daniel how does the computer know
that a pixel is a square technically it
doesn't it's just hardware devices have
decided that pixels shall be squares and
so therefore when you store an image you
should assume that every dot is same
height as it is with yeah
yes good question okay so some of that I
can answer the rest we'll have to wait
and see so for those unfamiliar bit is
kind of a cute word that refers to a bit
in quantum computing quantum computing
or qubits essentially refers to an
envisioned technology on which research
is being done where technically you can
have in a device like a like a light
bulb that's in both the on and the off
state at the same time in some weird way
it really derives from physics and so
with qubits you have the ability at
first glance to store more than just a
single bit of information you can store
a qubit which is more in the sense that
it can be in two states at once this is
dangerous
theoretically because a lot of the
world's security these days relies on
cryptography the art of encrypting or
scrambling information and a lot of
encryption relies on the perceived
difficulty of solving certain
mathematical problems quickly for
instance it is really hard to take a
really big number and factor it that is
break it down into two smaller numbers
that have multiplied together give you
that big number but with quantum
computing in qubits if you have the
ability to essentially be in multiple
states at a time and therefore do
multiple types of work simultaneously
the presumption is that that is bad for
things like cryptography because you
could solve problems much more quickly
now how soon that's going to happen or
if it's gonna happen that I don't know
for that take you're in Kies course on
quantum computing perhaps but that's a
whole field of research unto itself
so let's look now into this this black
box literally so in between your inputs
and outputs is like the real
intellectual property the secret sauce
bio which you want to solve problems and
those are generally called algorithms an
algorithm is just step by step
instructions for solving a problem it's
kind of a nice fancy word but it really
is just that it's like a list of
commands or instructions that you feed
to a human or to a robot or to a
computer so what's one such algorithm
well back in the day um we like you use
these this technology here phone books
in which you have lots of names and
numbers and the names are hopefully
sorted from A to Z and the numbers then
line up with the individuals names and
so if I wanted to look up a friend or
colleagues phone number I could just
look up that number and then call them
so I don't know why I'm explaining how a
phonebook works but it's very similar to
this technology now in fact even though
we don't really use these devices
anymore it's the same problem right you
probably have an icon on your phone
iPhone or an Android that is your
contacts and they're just sorted
alphabetically top to bottom but if you
type searching at the top and you start
typing like da for David or a Jo for
Jose you'd like to think that it jumps
right to that result that's the same
problem it's just the software is
jumping to Jose or to David's name very
quickly but how is your phone doing that
or how would we humans do it back in the
day well this is a problem to be solved
and the input is this physical book and
so maybe I'll start at the beginning and
look at one page and I look down and
maybe I'm looking for my friend Mike
Smith last name s M ith so Smith so if I
just look at each page I'm not seeing
him yet but this is an algorithm for
each page look down and if Mike's there
call him otherwise move to the next page
and we wouldn't even think about it you
would just do it is this algorithm the
step by step process correct yeah I mean
if Mike is here we'll find him but
what's the catch
it's gonna take forever I mean this is a
stupid algorithm but it's correct right
if Mike is in this phone book I will
eventually find him probably way back
here so what would be slightly smarter
well let me just do 2 4 6 8 10 12 it's
hard to do physically but it does sound
like it's going twice as fast is that
algorithm correct okay why yeah yeah so
I could get unlucky and maybe I you know
he gets sandwiched in between two pages
and I just miss him all together and I
conclude no there's no Mike Smith here
now I could fix that bug that mistake
and it for instance if I hit the T
section the name starting with T or s n
instead of SM I could maybe double back
a page or two and that's not very
expensive it doesn't take me a huge
amount of time and I can fix that bug
but it would be roughly twice as fast
but no one's gonna do that either what's
most and
human gonna do yeah heard open to like
the middle all right I look down I'm in
the M section so Smith is is this way so
what do I do next
so I repeat but I could more
dramatically like tear the problem in
half throw half of the problem away and
now I'm left with same problem where's
Mike Smith but it's half as big so I
hope that's socially acceptable the Tara
phone books in Costa Rica because we do
this all the time in the US but these
are hard to find too though
so Mike Smith is somewhere in this phone
book where is he well let me just go
roughly to like the middle and I look
down oh I went a little too far T
section now but now I know that Mike is
not in this half of the phone book and
so I can tear that half of the problem
away and what's compelling here is where
as that first algorithm was very lazily
going one two three or maybe two four
six if I started with like a thousand
pages in this pretty thick phonebook I
just went from a thousand to 500 to 250
I'm really taking big bites out of this
problem and if I just repeat that same
algorithm again and again I'll probably
be left ultimately with just one page
that Mike is either on or not so just as
an aside suppose that phone book did
have like a thousand pages how many
times might I have to turn it to find
Mike Smith the first way one page at a
time
yeah like 700 you know worst case a
thousand but like you know 700 because
it's you know it's more than halfway
through what about the third algorithm
where I divided and conquered so to
speak splitting it in half every time
yeah eight or nine even fewer a little
more it's probably eight or nine maybe
ten depending on how we round but yeah
if you start with a thousand pages and
do the math you go from a thousand to
500 to 250 to 125 and so forth you can
only have a thousand roughly ten times
depending on how you round so that's
pretty powerful it might take me seven
hundred steps to find Mike Smith in the
first algorithm but my god like ten
steps in the third algorithm with the
same inputs and outputs so computer
science too is all about just kind of
harnessing frankly our human intuition
and expressing ourselves
more carefully putting a little more
thought into the problem and then
getting much much faster or more
efficient results and so how might we
then quantify this difference we don't
have to even talk numbers very
specifically but if this is just a chart
and here is the size of the problem so
this is like number of pages so a lot of
pages over here few pages over here
right to left vertical access time to
solve so maybe zero seconds and a lot of
seconds could be our unit of measure the
first algorithm is really just a
straight line why because if the phone
company adds one more page to the
phonebook next year that just means it's
going to take me one more page turn or
one more unit of time so it's a slope of
one if you will the second algorithm is
going to be same shape it's a straight
line but it's lower because if the phone
book has this many pages the first
algorithm might take me this many steps
but the other algorithm where I'm going
to pages at a time takes half as many
steps so the line is the same shape but
it's just lower on the chart
the third algorithm though is
fundamentally better and it's a
logarithmic curve if you will and even
if a little rusty on what a logarithm is
it's a curve that looks like this it's
always increasing but it increases more
slowly and slowly and slowly the
implication is that suppose that the
phone company next year like double the
number of pages in the phone book well
how many more steps with the first
algorithm take if you went from a
thousand pages to two thousand like
another two thousand steps right like
Mike might be fourteen hundred pages in
twice as far in if the phone book is
twice as big but no big deal for the
third algorithm if the phone company
doubles the size of the phone book
because maybe two towns combined phone
books how many more steps we'll find
next year take to find Mike Smith next
year just one write no big deal tear it
in half one more time and so algorithms
when you think about the efficiency and
when in software engineers sort of
compare the efficiency of their code and
try to claim that our product is better
our product is faster you can absolutely
just measure it by counting seconds on a
clock but you can also make more
theoretically sound arguments and say
well our algorithm is fundamentally
better than yours because look as n gets
large where n is just the number of
pages in the phone book it barely
takes us anymore time and so it's the
Facebook's of the world and the googles
of the world that really care about
getting algorithms not just correct but
efficient so as to leverage that those
kinds of implications an Oracle in any
database company is similarly trying to
invent algorithms like that any
questions there all right well let's
formalize that all of us just kind of
intuitive that a moment ago but let's
introduce one language today and for
more languages you can take cs50 a
tenkai with Jose and hi Mei and team
next term and beyond but pseudocode is
not an actual language it's like a
language like syntax most people write
it in English you can write it in any
spoken language though and it's just
meant to be short succinct instructions
that get your idea across to another
human before you write actual code and
here is how we might write the
pseudocode for that algorithm to find
Mike Smith where I divided and conquered
step zero was pick up the phone book
step one open to the middle of the phone
book step two or look at the names and
then I make a decision if Smith isn't
among the names that I'm looking at then
I'm gonna go ahead and call Mike but
that's not the only possibility it might
be the case that excuse me Smith is
earlier in the book in which case I
should open to the middle of the left
half of the book and then frankly just
go back to step two because I already
have the same logic ready to go else if
Mike is later in the book open to the
middle of the right half of the book and
then also go back to step two else quit
because Mike presumably is not in the
book if he's not there or to the left or
to the right it must be he's just not in
the phone book so what are the
characteristics of this program well in
languages like Java and C++ and others
you see commonalities so this is just
pseudocode but everything I've
highlighted in yellow here in a proper
programming language like Python is
going to be called and a function and a
function is just like a verb an action
that the program or the robot or the
human can take here we have conditions
or decisions that the computer can make
if this go that direction eltz maybe go
this way it's like a fork in the road
and you have to decide which branch to
go down these things a little more
technically are called boolean
expressions after a mathematician named
bull and a boolean expression is just a
question
that has a yes or no answer or a true or
false answer or more simply a one or
zero answer ones and zeroes are just
really nice when you want to represent
two opposing ideas true and false yes or
no or some other idea so a boolean
expression is just gonna say yes or no
so Smith is later in the book it's a
question or Smith earlier in the book
also a question and then lastly we have
this how might you describe this yellow
feature now yeah it's some kind of loop
or cycle now this seems a little
dangerous because if I keep going back
to step two this would just seem to go
forever but that's not going to be the
case because according to the third
algorithm what did I also do every time
I repeated myself yeah I looked at only
half of the problem right I literally
split the problem in half so it was this
big then this big then this big so it's
fine if I keep doing the same thing
again and again because eventually I'm
gonna end up with one page and then
Mike's either gonna be among the names
there or he's not at which point I can
quit so doing that's that's what's
called recursion doing something again
and again but making the problem smaller
each and every time so we thought then
we'd conclude with a final demonstration
that is sort of a pop quois of sorts
here especially for those of you who
came into today less comfortable we
thought we'd make an algorithm together
could we get perhaps two volunteers to
come on up two volunteers two volunteers
let me just give folks a moment to get
comfortable with the idea of coming on
down to volunteers you can maybe nudge
the person next to you or you start wait
you made eye contact can I call on you
what's your name
Carla okay Carla come on down you made
eye contact Carlos you want to come on
down too and I think I saw Jose's hand
if Jose would like to come up to come on
down
Jose why don't you hop in the middle
here Carla and Carlos nice to meet you
both so thanks to the the team here we
brought some food for at least three of
us
all right here we go and you'll see that
we have a knife for each of these
participants and a very common algorithm
back home is the act of making a
sandwich and in fact the one of the
first things I learned in fifth grade so
really young as a kid was how to or
really how not to make a peanut butter
and jelly sandwich but of course all of
you have done this or some similar
sandwich that you might like here
locally
peanut butter and jelly is very common
in in Cambridge but we have all of the
ingredients for this so the challenge at
hand is quite simply going to be to
program all three of you to make us a
correct peanut butter and jelly sandwich
so if you're thinking boy this is easy
that's great because it's going to be
all of you dictating the instructions so
here we have the last ingredients all
right
so shall we begin who would like to
offer step zero so to speak our very
first step to make a peanut butter and
jelly sandwich and for those unfamiliar
with this tradition in the US it's a
piece of bread a piece of bread jelly
and peanut butter together in Sandwich
form that's not an algorithm though okay
right here in the middle pick up bread
all right Priscilla step neck open the
bread
Thank You Carla all right nice
all right next step now humble sit open
the bread so I think that's ambiguous is
the real takeaway here okay
step three take one slice of bread Carla
out there here okay getting ahead of us
okay
okay next step I think I hear something
here put the bread on the dish
Thank You Carlos next step someone over
here it's Javier open the peanut butter
[Laughter]
interpret as you will take covering off
I heard I think that was Carla's
inclination here too good so we're
getting a little better at what it means
to open sore grab a knife that sounds
safe okay by the handle I heard thank
you next step yeah put knife into the
jar okay next it and scoop whatever you
want okay
on the bread okay
all right next step next step yeah over
here spread the peanut butter using your
right hand it seems evenly on the bread
did I see a hand here next step yeah
over here put the bread on the dish take
another piece of bread no no okay open
the jelly next step remove the security
seal if any and now let's go somewhere
else next step next step I oh I heard
right here what do you what would you
like them to do put the knife into the
jelly okay
okay next step almost there yeah maybe
if it's a jar okay okay if it's a jar
scoop it on thank you on the bread very
nice condition as we called it other
steps almost there
spread I heard spread the jelly with
also the right hand again it seems on
the bread pick up bread okay and we're
almost there
combine bread and okay grab another
slice of bread and combine it put it
over the other one and I think a big
round of applause for our volunteers
there we go
so that then is computational thinking
if you're not graduating quite soon
allow me to encourage you to take Jose
and hi mais class cs50 a tenkai it's
been a pleasure being here and I'm happy
to stick around 101 for questions thank
you all so much
[Applause]