you
all right hi everyone welcome to cs50
test review goal of this afternoon is
going to be an opportunity to talk about
all of the topics that we've really
covered in cs50 over the course of the
first eight weeks or so of the term and
to get an opportunity to ask questions
in preparation for the test so a couple
of logistical notes before we get on to
the actual content of what's going to be
today's test review note that the test
is going to be released later this
evening at 7:30 p.m.
it'll be released on the course website
so if you go to the course website
you'll see a link to the test there
you'll have until Friday this Friday at
11:59 p.m. to turn in the test
there's no timer on the test it's
entirely self-paced so you're welcome to
take as much or as little time within
that time frame to work on the test as
you'd like as long as you meet that
final deadline of turning in the test by
Friday the 8th at 11:59 p.m. and you'll
do so by turning in the test via Skype
in much the same way that you've been
turning in quizzes where you'll upload a
PDF of your responses you'll choose
which pays it pages each of your answers
to each of the questions corresponds to
and that will be how you'll turn in that
test a couple of rules about the honesty
policy for the test the test is entirely
open book which means you're allowed to
reference any of the notes you can go
back and look at the lecture videos you
can look at the lecture notes the slides
any of your own notes that you've taken
you're welcome to use any and all online
resources that you'd like so you're
welcome to Google things look things up
for the purposes of the test the only
thing you cannot do is turn to other
human resources you cannot turn to other
students in the class or other people or
your teaching fellows for questions and
if you need to ask anything pertaining
to the test you should email the course
heads and if you email the course heads
we'll be able to respond to you but that
is just for like clarifying questions
you're expected to for any of the
content part of the test you're expected
to work on that on your own without
turning to other human resources for
help but you're more than welcome to
look things up online or reference any
of the resources on the course website
but would that be lecture resources or
otherwise questions about test logistics
anything about how the test is going to
work yeah
when can you expect results back after
turning in the test usually we'll try
and get the test graded within a couple
of days a week at most other questions
about test logistics yes
if you look something up on google
should you reference that in your test
response yes at the end of every
question and the test will be a
debriefing section which will ask you
which resources you used in order to
answer the question so any resources
that you took advantage of whether
that's a website you looked up online or
a lecture slide just reference that in
your response to that test question just
so we have that information as well
other logistical questions about the
test where oh yes
can you reach them it before the
deadline yes you're welcome to resubmit
as many times as you'd like prior to the
Friday midnight deadline yeah yeah can
you log in and out of the tests across
dates absolutely there's no limit on
when during that range you can access
the test you can access it immediately
Monday at 7:30 in fact I'd encourage you
to as soon as possible
open up the test and at least read
through the questions and then you can
continue to access it up until the
deadline other logistical things yes
there are no tutorials or sections or
office hours during the test question up
there about how long should you expect
the test to take you in general we say
you'll probably be spending half an hour
a little more than half an hour per
question and you can look back at past
year's tests and quizzes and usually
they're in the range of like 8 to 12
questions or so somewhere in that range
all right so a couple of ways in terms
of preparation for the test in terms of
what to do first and foremost I would
recommend reviewing any of the lecture
resources so that includes the lecture
video but also lecture notes any of the
source code examples that David
demonstrated in lecture all of that code
is made available on the course website
so you can download that code or open it
up in the sandbox or inside of cs50 IDE
to read that code understand it
experiment with it and you can find the
slides from all the videos as well from
the lecture ISM all of the past year's
tests and quizzes and the solutions to
those tests and quizzes are also made
available online so that's another thing
definitely worth looking at because the
style of the questions that are asked
are generally similar in terms of the
types of questions that we're asking the
types of things were asking you to be
thinking about so past year's tests
quizzes and their solutions are
available online too and then I'd
recommend taking a look at the problem
sets the problem set specifications are
online in addition to sample staff
solutions that you can take a look at
and those are often helpful resources as
well just to give you a sense for the
types of problems that you were asked to
solve during cs50 so far and therefore
the types of things we you might be
thinking about over the course of the
test and then of course a great thing to
do for the test preparation is what
you're all doing here attending the test
review session a really big goal of this
is for it to be interactive so certainly
as we talk through all the topics from
week zero all the way up until week
seven
feel free to flag any of us and raise
your hand and ask questions because we
want this preparation session to be an
opportunity for you to get your
questions answered about whatever topics
you might have questions about over the
course of the curriculum that we've
covered so far in general let's go as we
think about all the different weeks and
the different topics we've talked about
from weeks to weeks there have been a
number of different themes that have
come up again and again and one of the
big things that we try to emphasize as
we think about preparing for the test is
thinking about those big themes and how
it's connected to a lot of the different
topics that we've covered over the
course of the course so far so the first
of which is this idea of abstraction the
idea that once you've been able to
understand the underlying details of
something you can begin to think about
it as a higher level without needing to
worry about those underlying details so
we saw that way back in scratch week
when we introduced the idea of like
functions and function blocks that
abstract away the details within them or
the idea that once we understand that
electricity can be on or off we can
build abstractions on top of that in the
number system and other systems that we
use for representing information and
then we saw that more recent weeks with
things like data structures where data
structures can often be thought of
abstractions of or lower-level ideas or
even more modern programming languages
like Python that introduced a lot of new
abstractions easier ways of implementing
particular tasks in comparison to a
language like C where you didn't need to
worry about a lot of those underlying
details as you went about designing
those programs algorithms are another
big theme thinking about if you're given
a problem what are these step-by-step
instructions you might use in order to
solve that problem remembering that in
that process you need to be very precise
about telling the computer exactly what
it is you want the computer to be doing
you saw that this past Friday when we
were doing the drawing example where
when you're trying to like draw a figure
on the board you have to be very precise
about the instructions you're using in
order to do that representation is all
about like taking information and
representing it inside the computer so
we saw a lot of different ways to do
this for things like how do you
represent text but also how do you
represent images how do you represent
more complex data how do you store all
that inside of a computer another theme
that has come across a lot during the
course and then security thinking about
with any of the decisions we make
computers are vulnerable and where are
those vulnerabilities we saw a couple of
those vulnerabilities when we were
talking about databases this past week
but we've seen other vulnerabilities
when we consider thing
that might happen when things go wrong
and so we'll be talking about a couple
of those today and definitely feel free
to ask about them as well and then
finally a big theme has been trade offs
the idea that anytime we get something
in computer science it often comes at a
cost that an algorithm that might be
faster might come at the cost of using
more memory or an algorithm they might
allow for certain operations might come
at the cost of being a little bit slower
and so always thinking about with any of
the decisions that we make in computer
science what the trade-offs there are
what are you getting for the choice that
you're making and what is the cost of
the choice that you're making and
thinking about those trade-offs is
another big theme that has come across
time and time again over the course of
cs50 so as we go through all the weeks
of the class we'll go through one week
at a time be thinking about those themes
and how they connect to the topics in
the course because those will be some of
the key takeaways from the class so far
questions about any of the themes and
the big ideas of the class before we go
into we'll start with week zero all
right in that case I'll turn things over
to Emma all right so we are going to
start where you all started with scratch
and computational thinking in the very
first or 0if week of the course and we
begin with trying to think and act like
computers in a certain way so we learned
about binary which is a sequence of bits
of zeros and ones so a bit can be a 0 or
a 1 a sequence of 8 bits would be
considered a byte you can represent
numbers from 0 to 255 in this way
anybody know what this number is in
binary some quick maths it's really easy
if you guessed a number that we would
put on the board 50 exactly so here you
can think of it sort of like a base 2
system so wheat counts typically with
the base 10 system you have your ones
place your tens place your hundreds
place etc and those are the sorts of
operations that we are most familiar
with in regular math but in binary math
instead it's base 2 so the first place
the two to the zeroth place can be
either a 0 or a 1 representing quite
literally a 0 or a 1 and so forth all
the way up to 2 to the seventh for 8
bytes for 8 bits to make one byte
questions about binary
great so moving on from there we have
different representations of numbers
letters things that we would want to
store inside of our computer that we
also want to be aware of how those are
actually represented in memory itself so
in Caesar you learned a lot about ASCII
values but numeric representations of
letters we know that they're different
for uppercase and lowercase letters as
you learned with your to lower and to
upper functions coding and see later in
the course these numbers are also
ultimately represented in binary so this
65 which represents a would be
represented similar to the number 50
that we saw on the previous slide in
binary when it's stored in your
computer's memory and moving forward we
thought about another way of
representing something that we were
interested in in the filter problems
that you had to do with RGB triples and
so RGB values are numbers from 0 to 255
representing the amount of red the
amount of green and the amount of blue
and any given pixel you know that you
are able to manipulate those values
individually you're able to manipulate
them as a series and in your computer
they're stored as the values for the RGB
numerically just like ASCII and then
ultimately again in binary questions
about representations of data yeah
yes and so ultimately the question is
the sum of the RGB values is ultimately
255 and so yes they go all the way up to
that great other questions
cool if we think about how then we use
the letters individually and the numbers
themselves then we think about
algorithms as a black box and so in the
first weeks you were given access to
things like getstring and get integer
where you were able to take a number
from a user you had some text right
after it in order to get those values
that you needed ultimately those things
we didn't need to know how exactly they
were working as long as we were using
them properly and so getstring you knew
that you had to write get underscore
string you had to import the cs50
library then say you know ask for the
name of a person in quotes right
afterwards and then they would type in a
string to the computer which your
computer would then store in whichever
variable you used there the getstring
documentation and the actual code behind
how it works is somewhere in the cs50
library you could find it if you wanted
it but you didn't actually need to know
how it was implementing such a thing in
order to use it correctly a lot of the
power of computer science is reusing
things that other people have written
before and so here we think about a lot
of those sorts of things that you used
in the first weeks of the course as
blackbox algorithms it takes an input in
this case it took a string from the user
and it gives you your desired output a
variable that holds that string
questions about this black box structure
cool so moving forward then in scratch
you were able to see visually what these
sorts of things looked like and so we
learned about all sorts of tools that we
have in computer science such as
functions it takes something like this
the Blubaugh block boxes in scratch and
says move 10 steps 10 is the input that
you give the function if you think of it
sort of like your main function it takes
in any sort of variable it usually
returns void because it doesn't return
anything directly here this takes in an
integer 10 and it moves that direct
number of steps and so if we go to our
thing about our previous slide the input
is time the output is the action of
moving 10 steps variables are something
distinctly that holds a value and so it
can hold a string you can hold an
integer any number of things that you
define in this case it's sets my
variable which is the name of the
variable to be 28 that's the sort of
tool that you would use many other times
in C and Python and beyond conditions
holds boolean statements and so you have
ifs elif's else else's don't hold
anything because they're your ultimate
final thing that's going to happen in
your code however here you know that
your if-then conditions take in
something called a boolean expression it
says either you know if a equals B if a
and B are both true or operators not
operators you would learn about the
syntax truthfully of how would you you
would use those things in C and in
Python later you know that they change a
little bit the double ampersand for and
and see the actual word and in Python
however the idea is always the same and
you know that you are able to compare
any number of things of the same type in
this way loops and a similar vein
represented in scratch with these yellow
blocks it can repeat something or a
certain number of times you learned
about while loops about do-while loops
etc and they are able to repeat actions
any number of times that you defined and
those were all of these sorts of things
that you used and became familiar with
in scratch weeks any questions about
those broad concepts
cool
so then we'll move into week 1 where you
guys the opportunity to start coding in
the cs50 using see your first
programming language and the very first
program that you likely wrote was this
one you included standard IOH
and ant main void he then wrote printf
hello world
int main is of holds void because it
doesn't directly return any values the
function isn't returning anything to be
used anywhere later but rather it's
simply printing this message to you that
you are now a computer scientist you can
print hello world and this was where we
started moving from here we learned
about all sorts of different types of
data so we know that a boolean is
something that returns true or false
hold true or false our boolean values a
character is a single letter a double
and a float are sort of related a float
is an integer is a number that has a
decimal point in it and so it can be
like 1 point 0 is a float whereas 1 as
an integer you can represent things with
more precision using floats then you
could potentially using interference a
double is a float that has 16 bytes of
memory rather than 8 or 8 bytes of
memory rather than the floor and so that
gives you even more ability to be even
more precise with your calculations
using a double rather than a float
similarly with an int and long and int
is four bytes along is 8 so you can hold
more information along is represented
sometimes in different ways in different
coding environments but for the sake of
the IDE it would be 8 bytes and then a
string which is an array of characters
you learned later a little bit more
about what means in terms of memory
directly but for the sake of week 1 we
knew that strengths were arrays of
characters questions about data types
yeah
for other questions so moving forward
once you had all the tools to build
whatever sorts of did then you were able
to use it so here we use functions like
getstring those black box abstractions
that are made available to you through
the cs50 library and you would rate your
variable name string name you declare it
with the correct type and then get
string name then if I typed my name Emma
and when prompted
then name would be a variable that held
the string Emma or the array of
characters Emma and then you could print
using this syntax with the percent s to
hold a space for a string essentially
and then pass in the variable name for
conditionals they would look something
like this
this is very familiar to you as well you
would write if X is less than Y print
this X is greater than Y else etc you
know that if you have an ultimate
condition then you put it in an else
without a boolean expression because
anything else would fall under that
condition automatically by not
satisfying any of the previous ones
questions about any of these things so
far and C syntax you're all experts I
know so then if we move forward into
loops you would write for int I equals 0
I had less than 50 I plus plus how many
times would that print something or do
the action in the middle 50 because
that's how you set it so the constraints
in the middle say the number of times
that you want something to happen and
that's every loop that you define has
that sort of roadmap for how many times
you want something to happen loops also
can be like a while loop so this one
doesn't directly iterate over with I you
can use something like this if you don't
actually need that value of I to
influence the inputs that you're going
through we know that for a lot of our
programs earlier like if you think about
moving through an image you needed that
I value in order to orient yourself
within a picture etc but sometimes you
just want to do an action a certain
number of times then you could have a
while loop or even a do-while loop which
does something as long as another
condition is true something else that
you saw with maybe getting inputs from
the user that notch a certain number of
constraints that you want to set
questions about loops great so then we
learned how to define our own functions
and so you know that sometimes it's
easier for both readability and
repetition within your code in order to
create functions of your own so that you
can call them up in your main function
and do the same thing over and over
again without having to physically write
repetitive code we know that as
programmers we want to be as Lilli as
easy as possible and functions are a
really great way to abstract out some of
your logic and then apply it later in
the future so here we have a function
fork off and that takes in an integer n
and then for I is less than the integer
and weak off that number of times and so
you would be potentially in your main
function you would say something like
get an integer from the user integer n
and then call that number of times maybe
for every single person in this room I
wanted to give you all an opportunity to
cough however many times you would wish
and then it would make a lot of sense to
have this function separated so that I
didn't have to repeat this code every
time I would just have to repeat getting
an integer and from you individually and
then running the cost function with
integer add any questions about
functions yeah
do you you'd like to find it like at the
end but you
so I think the questions about
structuring your codes so that code like
if your main function is above it
understands that the function exists
later and so you can declare functions
earlier on so that you can use them so
you don't get like weird C syntax errors
in order to use things in the order that
you want them while they might be
created later because this would
probably be down lower in your code and
your main function would be above it
what other questions do you have about
functions so then you dealt in your quiz
with floating point imprecision and so
we know that computer memory is
complicated it only gets more
complicated as we get later in the
course but we knew even now when we were
doing programs like cache that your
computer memory doesn't have space to
hold things exactly the way that they
are and so in a function like cache you
had to use the round function because
when you divide two by 10 it does 0.2 0
0 0 0 0 that's all very correct and then
it sort of goes off the wire because if
you think about the way that things are
stored in memory there might you might
run into other blocks of things that
aren't directly related to what you
calculated and so you always have to be
careful about floating point imprecision
in order to be sure that you apply the
round function etc so that you're always
getting back the results that you're
looking for and then a similar memory
error that we saw in the Gandhi problem
of one of the quizzes that you did is
integer overflow so here is a function
that takes an integer I equals 1 and
while true which is essentially the C
equivalent of a forever block in scratch
you would print F I and then multiply by
2 and so this would go on forever and
ever never never never
until the integer I that you defined
originally can't hold it anymore it
would overflow back to the beginning and
so like in the Gandhi problem where you
try to subtract 2 from 0 and you ended
up at the highest possible aggression
rating you have to be careful about
where your values are headed and whether
or not you have enough space to hold
them there questions about integer
overflow floating point imprecision
great so that is all for week 1 that's
when you were able to do your problem
sets the first ones in see Mario hello
and cash and then we moved into week 2
where we talked about arrays and
compiling and so one of the first things
we looked at was using clang here we had
this big bulky line where you took in
the name of the program and libraries
that you had to import all of that was
difficult to remember and difficult to
execute and so then we gave you
something called make which was made
compiling a little bit easier it did
this whole process for you where it took
your original source code say the
program hello dot C it did
pre-processing which is the process of
taking all of the things that you
hashtag include like standard i/o or the
cs50 library and turns those along with
your initial source code into assembly
code in compiling then the assembly then
assembling assembles that assembly code
essentially and then linking links them
all together and so when it's turned
into assembly code the things that you
included in standard i/o and the cs50
library and your source code are all
separate versions of us all separate
assembly code files linking puts them
all together into one big binary file
that your computer can read and execute
correctly and so this is the big scary
process behind the make function which
simplified a lot of it for you what
questions do you have about compiling
great and so once we knew how to compile
and run things and our code got a little
bit more complex there became a need to
be able to debug it when you're taking
the test it'll be important to note that
there won't be office hours or tutorials
as usual for other people to help find
your bugs and so it will ultimately be
up to you to use the tools that we've
given you and your own knowledge of how
things are working in order to debug any
coding aspects of the test itself so you
know that we have the tools help 50 and
debug 50 notes on how to use both of
them are in the notes tab of the lecture
two slides and presentation and then you
always know that you can use printf
statements in order to see where you are
at any given time so if you know that
something is messed up in a for loop you
can print every single variable you use
in that for loop and usually tell by
process of elimination and some clever
printing where you're going wrong yeah
so python is a little bit different in
terms of compiling because you don't
have yeah we'll talk about this a little
more when we get to Python which will be
in a couple of slides but in short this
is the process for seed things look a
little different for Python because
Python is what we wouldn't call an
interpreted language as opposed to a
compiled language like same and so the
way that you run Python programs is a
little bit different but we'll get there
it's a little fuzzier because you don't
impact memory directly and things are a
little bit more abstract ageneral e
helps just add one point there in C
you'll notice that if you have some sort
of syntax errors you can't run the code
because the compiler will catch those
errors and break before your program
actually executes whereas in Python it
just kind of execute line by line until
there's some sort of error and then your
program crashes so you'll notice in
Python files you can have like a half
functioning program that does everything
is expected and then crashes whereas
didn't see you're not allowed to run it
until you fix all the bugs yeah
we will talk about that when we do
pointers in memory accessing but that's
another tool just like this that you
would want to have in your back pocket
for debugging on your own great so
moving on from debugging we'll talk
about a raid so arrays are a super
powerful data structure you're able to
store things in contiguous blocks of
memory and so if you want to be sure
that things are right next to each other
in a way that's easily accessible and
you can use indexing in order to get to
it all then you would want to use an
array so here if we write int value then
we get an actual integer called value
but if we write int values in brackets 5
then we get an array with 5 spaces for
integers and those would all be stored
next to each other we could do any
number of things with them so for
example I swear I didn't make these
slides Brian made them I'm not that vain
but if we have a satiric named Emma that
we know that that's stored as an array
of characters emm a and then a null
character so even though my name was
only 4 letters it needs 5 spaces of
memory that automatically gets stored as
an array if I wanted to say array name
bracket 5 then I could later put the
string like individual characters into
it in order to get the same output what
questions do you have about arrays great
oh so then we talked a lot about
command-line arguments because it's
limiting to only be able to do as we did
in Mario prompt the user for input once
the code has compiled and started
running and then act based on that it's
a lot more powerful if we're able to
take things in directly and act upon
them in our code itself and so here we
have Mario where you made Mario and then
it compiled and then you use those
arguments and then we had a plurality
where you passed in the names of the
candidates themselves to the command
line and so here for plurality we know
that we have in tark see and string Arg
V which is the in tark C is a number of
arguments that you pass in including the
name of the file itself and our V is the
array of the inputs to that file and so
here what would our exede be for this
call to plurality for and your array
would be what
I'll leave talk a little louder
yes until then its directly the things
that you typed in these four distinct
strings of characters and then the
Argosy is a number of things that you
typed in which in this case would be
four great so that's all for week two
what questions you have about
command-line arguments arrays anything
from the past two weeks yes
I think you still consider it to be a
null character but it's not something
that you access so you wouldn't say like
this is none directly do Python the idea
of the string has been obstructed away a
little bit so you don't need to worry
about how exactly that string is stored
in memory it's stored in a more complex
way in Python than it is in scene so you
don't need to worry about the null
terminator when it comes to Python
yes
mm-hmm
yes
yeah so if you had an array if I put
into that array of whatever the one of
values 1 2 3 4 5 5 would be the fourth
technically index of that array there
wouldn't be a null character at the end
look sorry the question was no
characters are only for string arrays
character is yes
so that's correct so there are four
things stored in it but with zero
indexing yes actually I'm pretty sure
that RDC counts from one number of
command-line arguments and so if there
are four command-line arguments and Arc
C is 4 that means the individual
arguments are stored at our v-0 our v1
or v2 and our v3 similar to how if we
you know create the integer array with
space for five things the fifth
character would be at the fourth index
this is something that you can test
yourself as well when you're you know
and the IDE you can just whip up a quick
temp dot C file and just write like
print what's arc see what's art vr like
loop through the elements in art V so
that you can see for yourself and get
this better intuition instead of having
to try to memorize you can actually just
test for yourself and see it
they're stored as an array of characters
yes and so then that's wise in C
programming when you were taking in AI
like in integers in your array then you
had to make like apply the integer
function to them great so now Brian is
going to talk to you about algorithms
all right so weeks what 0 1 2 were
really about building up the
fundamentals of how to write programs in
a programming language like C so Emma
talked about the building blocks of
variables and conditions and loops and
now that we handle it in functions and
now that we have all this capability the
next step is how do we use that in order
to solve problems and so this was what
we three was about week three was all
about algorithms trying to figure out
how do we write code that is able to
take these inputs and solve some sort of
problem in the problem set you use this
in order to implement a variety of
different election algorithms so a
simple Prout plurality election that
counted up like who has the most number
of votes but then looking at more
sophisticated algorithms like a runoff
election or the tied min election method
that run a little more of a complex
algorithm to try and figure out who the
winner of an election is but in lecture
we talked about a couple of strategies
for how to represent information and
then how you use that information inside
of an algorithm and the first key idea
was the idea of a struct and so here
gave us the ability to create our own
types where Emma introduced the basic
types that are already built into the C
programming language types like int and
float and bool and char and long and
double and those sorts of types but if
we needed to represent other types like
we wanted to represent a person for
example as we saw in lecture or in the
problem set you saw the representation
of a candidate as a brand new type in
later problem sets you saw a type 4 RGB
triples for a triple of red green and
blue in order to store a pixel of
information none of those types are
built into the C programming language
but that's ok because we can create our
own types in order to represent that
information and so what we had here was
the definition of a new type called
person where the way the syntax worked
is we use the type DEF keyword to say
let me have a new type with a particular
name
what is that type well the type is a
structure or a struct where you can
think of a struct as a way of
encompassing multiple different pieces
types of information into a single unit
into a single value and so inside of a
person we're going to represent a person
using two pieces of information
every person has a string called name
and everyone every person has a string
called number that represents their
phone number for example and recall that
we used a string instead of an int
because we wanted to be able to
represent maybe hyphens or parentheses
that might have been included inside of
the phone number so a string was a more
reasonable choice for that but we can
choose exactly what we want to be inside
of that structure and so with RGB
triples inside of here we had separate
fields we might call them for some
amount of red some amount of green some
amount of blue for candidates we
included a field in here for a number of
votes but in short we could take
whatever data we wanted a store
encompass it all together inside of a
struct and then call that new type a
person or whatever type we wanted and
that gave us the ability to more
abstractly represent the idea of a
person or a pixel somewhere inside of
our program questions about creating
your own types or structures what
questions do you have about that idea
and how that worked yeah
oh yeah so good question the question is
when why did later on in future weeks we
sometimes had to include the word struct
somewhere inside of this definition that
was used when we needed for our data for
the type that we were creating to be
able to somehow reference itself and so
this came up in particular when we were
talking about linked lists where every
linked list node contains a pointer to
the next node in the linked list Rodrigo
will talk a little bit more about that
later but in short when we need that
recursive data structure we need some
way of referencing itself and so we had
to add an extra keyword here but we'll
see the syntax for that in just a bit -
but very good question that was why we
needed that other questions about types
and structures of data all right so what
did we use those structures of data for
and what was the purpose event well the
first thing that we tried to do was
solve a problem of being able to search
for something inside of an or inside of
an array for example and so there were a
number of different ways that we could
search for something but one way was to
say for example if we have a big list of
unsorted things we could use linear
search to say like start at the very
first element in the array and then look
what element at a time in order to try
to find it and can someone remind me
like in running time what was the Big O
of linear search how efficient is linear
search to search for something yeah Oh F
n yeah linear time to be able to search
for something big o notation recall sort
of encodes the idea of what is the worst
case or the upper bound on how long it
might take for this algorithm to run and
so in the case of linear search it might
take us if we have n elements inside of
the array that we're looking for him it
might take us n steps in order to look
through it and so that was one method of
searching for something and what was a
more efficient way to search for
something inside of an array if we
stipulate for example that the array is
sorted yeah
oh of log N and we used an algorithm for
that called binary search so binary
search another search algorithm only
works when the array is sorted in linear
search it doesn't matter whether the
array is sorted or not but the idea of
binary search is alright let's say we're
looking for the number 50 inside of an
array we first say all right well if
there's nothing in the array return
false we didn't find the number 50 if
the middle item of the array is 50 well
then we found 50
have returned true and what are the only
other possibilities well if 50 is less
than the middle item then we need to
search the left half because the 50 is
less than the middle item then if 50 is
inside of this right it's got to be in
the left half of the array so we'll
search the left half of the rate the
array and otherwise if 50 is greater
than the middle item then we'll search
the right half in order to try and find
that number so this algorithm gives us a
couple of different insights but one of
the big ideas is this idea of recursion
that we're solving a big problem by
solving a smaller problem that if 50 is
less than the middle item then we repeat
this same algorithm just on the left
half of the array and we can keep
repeating this process of solving a
smaller and smaller and smaller problem
until either there's nothing left in the
array in which case we return false
or the middle item is 50 in which case
we found the number we're looking for
and in that case we can just return true
and so if we compare the running times
of these this is where Big O notation
came in this was the more mathematical
side of week 3 thinking about given an
algorithm how long is it going to take
for that algorithm to run and computer
scientists use a notation called Big O
notation to represent that idea where
Big O is all about the upper bound in
the worst case or as an upper bound how
many steps will it take for the
algorithm to run if there are n inputs
so in this case if there are n items in
the list how long might it take to be
able to search for a particular element
and we decided that all right for linear
search the running time is Big O of n if
there are n elements in the list it
might take us n steps to be able to find
the thing we're looking for because in
the worst case it might be all the way
at the end of the array and we have to
make our way through the whole array in
order to be able to find it and then as
someone mentioned binary search is an
improvement on that in the worst case
it's log n if we assume that the yeah if
we're looking through the array it's log
n because we can cut the problem in half
over and over again we can look for the
middle item then choose one half and
then just keep looking to the next half
of the items and we don't need to look
through every single value in the array
we can jump around a little bit in order
to narrow our way down to the one value
that we're looking for so in this sense
o of log n is a faster algorithm in the
worst case binary search was better but
of course it came at the cost of
requiring that the list is sorted to
begin with our array needs to be in
sorted order
in other in order for binary search to
work otherwise it's not going to work so
that's binary search and also as we
introduced as part of binary search big
o-notation listener patient we use for
describing the runtime of algorithms how
long it takes for an algorithm to run
what questions you have about that big
o-notation algorithms runtime all right
we feel okay about that
in that case related to Big O notation
was another notation so while Big O
describes the upper bound on the running
time of any algorithm there was another
notation we used called big Omega which
was all about the lower bound on the run
time of an algorithm so you can think of
that as like in the best case how long
might the algorithm take and for linear
search and binary search what is the big
Omega how long made it take in the best
case if we get lucky for example all
right I heard a couple people say at O
of one in other words constant time in
the best-case meaning just a single step
or some fixed constant number of steps
and why is that well because we might
just get lucky and the first thing we
look at might be the element that we're
searching for we might find 50 at the
very beginning of the list in the case
of linear search we might find 50 at the
exact midpoint of the list in the case
of binary search so depending on the
algorithm we might just get lucky or
depending on the array that we start
with we might get lucky and get the
answer immediately so often in
algorithms you'll find that the big
Omega the lower bound on the running
time of the algorithm can be different
than the Big O of that algorithm what it
might take is an upper bound on time and
knowing the difference between those two
and being able to think about that
algorithm in deciding what is the Big O
of this algorithm what is the big Omega
that can often be a helpful way to frame
an algorithm and think about the
implications of its particular running
time questions about run time Big O a
big Omega how to think more abstract me
about these runtimes another useful
thing to remember is that when it comes
to Big O and big Omega we didn't really
care about the constant factors or the
smaller terms inside of the run time so
it didn't matter if this was like n
steps or two n steps or three n steps
the constant factor didn't really matter
what we cared about is what happens as n
gets very very big
and so we can throw away those constant
terms so to speak and an algorithm that
takes three n steps or four n steps we
can really just consider to be O of n
steps it's the end part that we care
about more so than what the individual
constant factors happened to be all
right so that was searching for
something and we stipulated the binary
search only works if we have a sorted
array first and so one of the next
questions that came up with algorithms
was how do we sort things
what are algorithms we can use for doing
that and we looked at at least three
different algorithms for being able to
sort things and the first of which was
bubble sort here represented in
pseudocode where the big idea of bubble
sort is if we have a big array where the
elements are unsorted we look at the
elements in that array two at a time
look at a pair of elements and in a
sorted array the element on the left
should always be less than or equal to
the element on the right in any pair of
elements and so if we look at any pair
of two elements and the element on the
left is greater than the element on the
right then those two elements are out of
order and we can swap them and that's
what bubble sort is all about it's going
through the entire array pair by pair by
pair and making swaps whenever two
elements are out of order so the
algorithm is we're gonna repeat this n
minus one times and we'll come back to
why n minus one in just a moment but
we're gonna repeat this from I from 0 to
n minus 2 so from the very first element
in the array up until the second-to-last
element in the array recall that if we
have an array that has n elements the
first element is element 0 the last
element is n minus 1 a little bit tricky
because you have to start counting at 0
but for each element I we're gonna look
at element I and I plus 1 and if they're
out of order we're going to swap them
and so we repeat that process again and
again making a swap making the slot
making a swap and at the end of this
inner loop the effect will be that
whatever the largest element in the
array is it will bubble its way so to
speak to the top of the array because
we'll continue to make swaps until the
biggest element gets to the rightmost
position in the array and there's one
element that we have now sorted and
after that we can go back and do the
same thing again and again and again and
we only need to sort n minus 1 elements
into their correct place because
if you have an array of n elements and n
minus 1 of them are in the right place
then the last element must also be in
the right place because there's nowhere
else for it to be and there was a visual
demonstration of this shown in lecture
where actual people were standing up
here and they were switching places in
order to figure out how to get into the
right order so that might be a helpful
thing to go back and look at just to
familiarize yourself with bubble sort
but if you recall from bubble sort there
was an optimization we could make to
make it more efficient and even remember
what that optimization was yeah
merge sort was an entirely different
algorithm but yes it was more efficient
and we'll get to that in a moment but
with bubble sort specifically there was
a way we could make it more efficient
yeah
use a wildly yeah and the idea here was
we don't always need to repeat n minus 1
times because as soon as we go through
the elements pair by pair by pair as
soon as we go through all the elements
and we don't swap anything we can
effectively stop running the algorithm
because if we make it through the entire
array and we never need to make any
swaps then we can just stipulate that
the entire array must now be sorted and
so we were able to make this algorithm
slightly more efficient by repeating
until there were no more swaps left to
make so a slight optimization that might
require running this algorithm fewer
times questions about bubble sort and
how that algorithm works yeah how can
you tell that you're not swapping things
well to do just a bit of a visual
example if we imagine we had four
elements let's say we had three and then
one two and then four what we would do
in bubble sort is we would start with
these first two right say three and one
are they in order or out of order well
three is greater than one so these are
out of order so we would swap them and
so this would be one and then three then
we go to the next pair three and two
well these about are out of order as
well so we can go ahead and swap those
and so now we have two and three then we
look at three and four and say are these
in order or out of order they're in
order and so we don't need to do
anything here so that was one pass
through the array we went pair by pair
by pair making swaps and then we might
check this again
say alright 1 & 2 have we made it do we
need to switch anything well no we don't
they're good 2 & 3 do we need to switch
anything no 3 & 4 do we need to switch
anything no and so we made an entire
pass through the array and we didn't
need to switch anything and so if you're
keeping track of did I actually have to
switch anything and the answer to that
question is no then at the end of that I
can say this array is now sorted I don't
need to go through it again and again
and again trying to see if there are
more slots to make because if I went
through this whole array and didn't make
any swaps then it must already be sorted
otherwise I would have had to make some
swap somewhere other questions about
bubble sort alright so the next
algorithm we took a look at was
selection sort this was a slightly
different algorithm we're instead of
going pair by pair by pair and making
swaps the idea was if we have a whole
array let's figure out what belongs at
the beginning of the array and what
belongs at the beginning of the Ray is
the smallest element so we went through
the array found the smallest element
moved it to the beginning then we did
the same thing for the second element go
through the rest of the array find the
smallest element make that the second
element in the array and repeat the same
process again and again where every time
we're just looking for what is the next
smallest element to put into the array
and so that's the idea here
we're going through the array find the
smallest element between I and the last
item and then swap the smallest element
with item I where I goes from 0 again
all the way up to n minus 1 so that was
two algorithms bubble sort and selection
sort
both of which achieved the same effect
on the same input they take an input of
an array that might be unsorted and the
output is a sorted version of that same
array and anyone remember the runtime of
these algorithms what was the Big O how
long did it take for bubble sort and
selection sort to run yeah and squared
exactly so
we'll talk about merge sort in a second
but in Big O notation N squared was our
bubble sort and selection sort
algorithms and the way to remember that
is you might look at what the loops are
how many times are each of the loops
running well in bubble sort we're
running this inner loop n minus two
times
in terms of Big O really only the N is
going to matter here so about n times
and how many times might this outer loop
repeat
well we repeat until there are no more
swaps and in the worst case we might
need to do that n minus 1 times until
there are no more swaps because all the
elements might be out of order or the
list might be in reverse order for
example and so if you look at the loops
and think about for every loop how many
times is that loop going to run that can
give you a sense for the overall runtime
of the algorithm and whenever you have
nested loops the number of times that
that code is going to run inside the
innermost loop you can think of as
multiplying the number of times the
outer loop is running by the number of
times the inner loop is running if you
have an outer loop that runs 5 times and
an inner loop that runs 4 times the
number of times that in inner block of
code is going to run is going to be 20
right the outer loop is running five
times and for each of those iterations
the inner loop is going to run four
times so you can do the math and figure
out how many times that code is going to
run so more abstractly if you have an
outer loop that runs n times and an
inner loop that also runs about n times
then on the whole your loop is going to
run about n squared number of times for
that innermost block of code questions
about runtime for bubble sort or
selection sort all right so next as a
couple people of alluded to now is the
idea of merge sort
this was our more efficient way of
solving the problem and this was a
recursive way of trying to sort numbers
so if we have a big array of numbers
here's how we're going to sort them we
start with what we'll call a base case
anytime you have a recursive algorithm
that repeats itself that calls upon
itself in order to solve a problem
you'll need some sort of base case some
stopping point to say at some point I
need to just know to not continue to
call myself otherwise the function is
just going to run forever we need some
place to stop and so in merge sort the
place to stop is once we get down to one
item one element in the list and if
there's only one element in the list we
can just return we can say if there's
only one thing in the list then the
array has to be sorted because in a list
of size one is by definition sorted
there's no other order it could be in
but otherwise if there are more elements
in the list here is the recursive
algorithm we start by sorting the left
half then we saw at the right half
and once we have a sorted left and a
sorted right then it's not too difficult
to merge those two sorted house together
by just figuring out one at a time which
order the elements go in because each
half is already in sorted order so that
makes it pretty easy to combine them and
merge them into a single sorted list
so this recursive algorithm is a type of
algorithm that shows up a lot
binary search was like this where we
said binary search the whole array by
binary searching the left or binary
searching the right merge sort now is
like that too we're to merge sort a big
array we first say merge sort the left
half of the array then merge sort the
right half of the array and then combine
those two results to get the answer that
we want and the runtime of that if you
recall was more efficient than N squared
it was n log n which is more efficient
than N squared because log n is smaller
than n at least as n gets very big so
merge sort was our more efficient way of
being able to sort numbers when they're
inside of an array questions about any
of these algorithms and why they have
the runtimes that they do Big O notation
runtime yeah
yeah so the runtime of mergesort in Big
O notation in the worst case is n times
log n and the reason why if you recall
the way that we did this was if I give
myself an example here and we said that
we started with maybe three one two six
eight five seven four the way we would
sort of big array using merge sort is to
start with like the left half three one
two six and how do you sort three one to
six
well we're gonna do that by sorting the
left half of that three and one and how
do you sort that we're going to sort the
left half which is a three and so what
you end up building up is this kind of a
tree like structure where you're first
going to take one in three and say
alright with this list of two items
three and one how do you sort of that
will becomes one and three with two and
six how do you sort that well that's
just two and six that's a normal eight
and five how do you sort that list of
size two well that's going to be five
and eight seven and four how do you sort
that that's going to be four and then
seven and so if you imagine that up here
we had a big array each of size one
three one two two six eight five seven
four you can think of the next step as
being we took these individual arrays of
size one and merge them into sorted
arrays of size two one in three is now
in order to and six is now in order five
and eight is in order four and seven is
in order and now we'll take those lists
of size two and merge those together how
do you merge 1/3 and 2/6 will you get
one and then two and then three and then
six and then likewise here five eight
four and seven how do you merge those
together we'll the smallest one is four
and then it's five and then it's seven
and then it's eight
and then finally now we have two lists
each of size four and the last step is
to merge them all together and we get
one two three four five six seven eight
so this generally speaking is what merge
sort looks like we start with elements
of size one merge them together to get
elements of size to merge those together
to get elements of list of size four and
then one final time in the case of an
array that has eight elements in it and
so if you think about how many steps
this took well this is n elements there
n sort of columns in this image and how
many times did we need to repeat this
process well we needed to repeat that
process as many times as it took us to
take a list divide it in half divided a
half divide it in half until we got down
to just one and we remember from way
back in week zero that the number of
times we can do that the number of times
we can take an array divide it in half
again and again and again is log N and
so we have to do this division in log n
times and with each time there are n
elements that we have to manipulate or
deal with so log n times n gives us and
log n yeah how would you implement merge
sort and see it'll be similar in spirit
to the pseudocode that we took a look at
so merge sort would probably be a
function where that function took his
input some lists that you wanted to sort
it and you would first call merge sort
on the left half then you would call the
merge sort function on the right half
and then you'd have to implement some
logic to merge the sorted halves
together where that logic is probably
going to involve taking each of those
smaller lists and looking one element at
the time starting at the beginning
trying to figure out which one is
smaller in order to merge those together
so it'll be similar to the pseudocode
that you'll need to add some additional
details in order to be a little more
precise about it yeah
will you need to be able to calculate
Big O and big Omega you should be able
to if you are like writing a function or
you're writing describing some code or
an algorithm to do something you should
be able to think about what it is that
that algorithm is doing and think about
what its runtime is ultimately going to
be Omega for merge sort anyone have a
sense for what big Omega for merge sort
is in the best case how might fast might
this algorithm run yeah n log n yeah so
the key idea here is then in the case of
merge sort it there is no way to speed
it up if the numbers are already sorted
if the numbers are already in sorted
order or even in close to sorted order
we're still going to be repeating the
same steps like merge sort doesn't care
how close to sorted the array is we're
still dividing in half dividing and half
dividing in half we're still merging
those sorts together and that's going to
take that same exact amount of time so
even in the big Omega in the best case
the merge sort is still gonna be big
Omega of n log n selection sort
meanwhile still big Omega of N squared
we're repeating that same process the
only one that does get more efficient is
bubble sort that becomes big Omega of n
in the best case as a lower bound as
opposed to N squared as an upper bound
and that was because of that
optimization we made where we said that
in bubble sort we can stop the algorithm
after we reach a point where there are
no more swaps left to go and so maybe we
just get lucky and after the first run
through the entire array there's no more
swaps left to make and we're done yeah
if what happens if there's only one
element how do you analyze Big O or big
Omega in general Big O is all about what
happens as the number of inputs gets
bigger so that's why we represent it
using n where n stands in for the number
of inputs so we're generally not
concerned with the case of what if
there's only one thing we care about
what happens as n gets big and there
become more and more elements that we
have to deal with sorting yeah
what if they're an odd number of
elements and murderer a very good
question in general there you just break
it up into approximately half if they're
nine elements you might do five and then
for a question yes good back here
uh what sort am I using here when I say
sort the left half sort the right half
I'm using merge sort and so this seems a
little bit weird that inside of the
definition of merge sort I'm using the
merge sort algorithm but it's okay
because I'm using merge sort on a
smaller array that I start with an array
of maybe eight elements and I call merge
sort on an array of four elements and as
long as I always call merge sort on a
smaller array eventually I'll get down
to this case where there's only one
element left and then I'm done so this
is a recursive algorithm in the sense
that it uses itself in order to solve a
problem other question
oh so this is back to how exactly do we
do this merging process that if we have
these two lists how do we combine them
in general if I have two lists that are
already in sorted order I know that the
first element of the combined one must
be either the first element of this list
on the left or the first element of this
list on the right it's got to be one or
four because everything later then it is
bigger than the one or bigger than the
four so I look at 1 & 4 and say you know
what 1 is the smallest one so that one
goes first and then I can say alright
well what comes after 1 2 so it's got to
be either the two or the four as the
next thing and you can go step by step
like that looking at the two smallest
elements in each of the smaller arrays
to figure out what the smallest element
in the bigger array should be and that's
the general process and there's some
examples of that in the lecture slides
as well
alright with that let's go ahead and
move on to memory talk a little bit
about pointers and go into a little more
detail there right so you guys were all
pretty comfortable with the explanations
of binary and such from week zero and
week one and another way that we have of
representing numbers is Texa decimal so
hexadecimal is essentially just another
base system to represent numbers whereas
a binary we have base two where
everything is either a 1 or a 0 and so
you have the zeros place the the yeah
the zeroes place the ones place and then
like all the exponents of 2 so you have
2 to the 0 2 to the 1 2 squared and so
on and so forth that's how you construct
your numbers with hexadecimal you have a
similar idea except you're using base 16
instead of base 2 and so you're able to
use 0 through 9 as themselves and then
the letters A through F represent the
values 10 through 15
so this basically just gives you a
different way of representing bigger
numbers and we generally use this in the
context of at least in this class oh you
said in the context of pointer addresses
so if you'll recall pointers especially
if you use debug 50 or printed like the
value of one of your pointer so you
might have noticed that you got some
sort of result
said like 0x you know 1 2 F 3 whatever
it might have been that was hexadecimal
notation but all that you really need to
worry about with hexadecimal is just
understanding that this is another way
of representing numbers that works
similarly to binary except the base is
different and instead of just using ones
and zeros you can use any of these where
0 0 up through F being 15 so back to
pointers which I know is kind of like an
intimidating concept especially when
you're learning it for the first time
and I agree as a student I also found it
intimidating but hopefully we can give
you a little bit more intuition and you
can also check back the lectures for
more intuition of this as well one
analogy that I like to use when I'm
thinking about pointers and non pointer
values is the idea that memory and C is
kind of like a neighborhood and in a
neighborhood you might have apartments
and houses and the like and all of these
have addresses so you might live at you
know one two three neighborhood road or
whatever and so there's that concept of
your house or apartment having an
address it's somewhere and then you can
go inside the house and look for things
so in this case we have int N equals 50
where we can think of this built in type
of an integer is kind of just like a
studio apartment where you walk in and
there's just you know a space you don't
have multiple rooms or whatever so you
walk into the studio apartment that's
this space in memory that we call N and
there's a 50 that lives there whereas in
this case down below where we're
declaring a pointer called P we have
that the integer star P which is the
notation that we use when we're
declaring a pointer we're initializing
it to be the address of n where if you
recall the ampersand symbol is what we
use to get to the actual address of like
a variable for example this integer n
where if we just refer to n by itself we
get its value so if we if we refer to
end it's like we're looking inside the
studio apartment and seeing the 50
whereas if we refer to and percent and
we just care about what's the address of
that studio apartment where is
where is it in the neighborhood and so
in this case right here we have integer
n is set to 50 and the pointer P is set
to the address of n so if you look at
the value of P later on I guess we can
draw this a little bit and is it this
one no this one if we look at the value
of P now we get that this value is
actually going to be the address of n
where initially we declared star P as a
percent and so when we actually refer to
P we get this address where the address
of n might be something like zero x over
wrote this a little bit the address of n
might look something like zero X you
know like 1 2 3 for example and so on
and so forth let's just say 1 2 so
that's actually the address of P whereas
if we then dereference p using the
asterisk that's a start using the
asterisk mechanic that we have this is
actually going inside of the address
where P is holding yeah you know the
address 1 2 it's going to that address
checking inside the apartment and then
it sees that there's a value of 50 so
let's actually go back to this slide now
that is to say then that when your
dereferencing a pointer which is when
you're referring to it with the little
asterisk that means that you're actually
going to the address of that pointer and
checking inside to see what value is
there whereas when you're just referring
to the pointer itself by its variable
name like P it's just giving you the
actual address before I go further are
there questions about this is this our
people confused about addresses versus
the actual values that it contains yeah
I see a hand back here yes so here you
can also think about it as the fact that
we we are setting start or in this case
we're actually declaring it so it's a
little bit misleading but after we
declare it when we're actually wanting
to use P if we say star P that gives you
the value contained at the address to
which P refers so that means if you just
do P it gives you the address of n where
n might live in 0 X 1 2 3 and then if
you do start P it goes to 0 X 1 2 3
checks what's there and it finds a 50
does that answer your question
ok so let's look at this in this case P
lives somewhere in memory when you when
you declare a pointer just like when you
declare a variable you're essentially
like taking up some space in your
computer where this reference to the
pointer is going to exist because
pointers don't magically not take up
space this pointer actually lives at
some position in memory itself and the
value that is contained at that position
memory is the address of a different
variable so in this case P lives up some
address we don't give it a name but what
it contains is the address of n where
here's N and contains the value 50 but
it lives at this address so when you
actually get the value of P you're
getting you know its own address whereas
when you're getting the value of star P
you're getting the address of n when
you're getting the value of n you get 50
and when you get ampersand n which is
how you refer to the
actual address of a non pointer variable
it's how you get the actual address and
I'm kind of using pointer and address a
little bit interchangeably here but that
just goes to show that you can think of
pointers is essentially just containing
addresses so that's a little bit of a
visual there in the context of strengths
to make it a little bit more concrete we
said to you at the beginning of the
course that strings were just array of
characters and we kind of left it at
that and then later on we kind of took
off the there took off the training
wheels and you saw that a string is
essentially just a pointer where here we
define the string called s
that stores Emma a string is just a
pointer that holds the address of the
first character of the string so if the
string is Emma and we store it in a
pointer or in a string variable called s
what's it s really is the value of the
address of e so then you can go to that
address and you get e back and if you
want to refer to the string at position
0 you just have to go to this address
and you see that it's an E if you want
to go to the position or the index 1 of
the string s since strings are just a
race of characters and each character
only takes one byte then underneath the
hood you know that you only have to add
1 to the value of this address to get
the value of the next block of memory
since strings are contiguous memory and
so that's how strings are essentially
operating where you just have a
reference to the first character and
then you can just add you know some
values to it to get the address of
whichever index and the string that you
want to go I don't want to lose anybody
here so definitely raise your hands wave
at me if this is confusing raise up your
hands if this is making sense ok cool
and was there a question here
yeah you have to be careful because the
question is what's the difference
between saying int P equals ampersand n
or int star P equals n % n and you just
have to be careful and this is why
people get confused one of the reasons
why people get confused with pointers is
that when you're declaring a pointer you
have to use the asterisk you have to say
n star P to tell the computer that this
is going to be a pointer so you would
want to say n star P equals and percent
n because if you just said nth P then
you're telling the computer give me a
normal integer and then that integer
would just contain like the value of
that address because it's in hexadecimal
so it's a number and so when you're
actually declaring the pointer you do
want to use this int star P but once the
pointer has been declared from then on
once you reference star P that means
your dereferencing it and which means
you're going inside the house and
checking what's there and seeing what
value is if it's a 50 or if this is a
boolean pointer if it's true or false or
whatever type it is and if you just
refer to P after it's been initialized
that means you want the actual address
okay so o question where yeah
that's a great question the question is
now if we want to change the value of n
do we do so by changing like now N
equals 17 or start P equals 17 the
answer there is that you can do both
because the pointer is essentially a
reference to that location in memory so
if you can follow that or and then
access that location in memory through
the pointer and change the value then
since this is you know and and and here
or in star P R referring to the same
place in memory if you change the value
there than any references to that place
in memory are gonna be changed and you
can also see this if you have two
pointers and you point them at the same
address and you change the value of that
address with one pointer you can then
see that it's changed if you access it
through the other pointer because just
keep in mind that everything that you're
doing like lives in an actual place in
your computer and since pointers are
just references to that address then
they allow you to go there and change
whatever is there and then anything else
that refers to that location will see
that the value has been changed great
question
another one here
so clearing up pointer versus array
versus pointer to an array so you can
think of a pointer in an array as
essentially the same thing where they
both refer to the address of the first
element or an array refers to the
address of its first element as a
pointer so if I say like char array of
size whatever and I set that to Emma or
I asked for you know memory dynamically
to store the size of the string Emma and
I set in star P to be that then we I can
access this all the characters in the
string essentially the same way if I
have an a pointer to an array then
that's essentially like having a two
dimensional array almost where you can
have like if you think of a board you
have one index for like rows and one
index for columns and since arrays and
pointers are kind of the same thing then
if you have in a pointer to an array you
end up with a two dimensional you know
all right
essentially okay these are all great
questions I love them keep them coming
so I referred to asking the computer
dynamically for memory and so we've seen
examples of this especially in speller
when we were dealing with porting over a
file containing words to our own data
structure that we then called the
dictionary and the way that malloc
played into it was that this is a
function that asks the computer for some
dynamic memory and then be at the end of
your yeah at the end of the execution of
your program you need to make sure that
any memory that you've malloc or asked
for dynamically is also freed so that
your program isn't then leaking memory
which is where valgrind comes into play
and I'm going to use this visual to talk
about it a little bit where you can
think of so again the motif here is that
everything that you do on your computer
is essentially like there's somewhere in
your computer that's
presenting that and so your actual code
itself after it's been compiled and
assembled and linked and whatnot you end
up with machine code and so that lives
somewhere in memory you can think of it
as living here then any space that your
global variables and such you're taking
also take up some space in memory and
let's say that that lives here and then
everything else in your program also
takes some space in memory where we use
the stack we refer to the stack as the
place in memory where all local
variables live so if you have like a
function you call it f and then in your
F function you declare some variables
like X Y Z x y&z are all going to live
in the stack as is your function f is
also going to live in the stack the
things that live in the heap are things
that you explicitly ask the computer for
so if you're asking the computer via
malloc or kalloch or those similar
functions hey give me 4 bytes to store
an integer give me 1 byte to store a
character then whatever memory that
you're asking for is coming out of the
heap which is then like if some people
as in speller may have run into like
some sort of memory overflow error or
segmentation faults or the like
especially with these overflow issues
might arise from you're asking for
memory and you're asking for memory but
you're also taking up memory in the
stack and so eventually the heap and the
stack like collide and you're out of
memory and you don't have anything else
this is just how we represent memory and
see and you use valgrind as the question
from before to eval Guren is a program
that you can run on your actual code on
your actual on the execution of your
program to then let you know if you're
leaking memory where leaking memory
means that you've asked for memory
dynamically on the heap but you didn't
give it back and you haven't freed it so
if you don't free that memory then it
can't be used for something else if
you're asking for memory unless you
reset it yourself manually so
see if I if I asked you know Matlock and
I'm not gonna use the exact syntax here
but if I'm a lock for my and at some you
know some spot in the computer's memory
like say these are four bytes right here
I've asked for this and now if I ever
asked for other memory I'm not gonna be
given this because I've already been
given it so if I keep asking for memory
and asking for memory I'm eventually
gonna keep being given memory and given
memory and given memory and if I don't
ever give it back there's gonna reach a
point where if I keep asking for memory
the computer's gonna be like hey I I
gave you all I got there's nothing else
we have a problem
whereas if you're actually freeing
memory once you're done using it then
that same piece of memory can then be
given back to you if you ask for memory
again
and that's essentially what valgrind
does this just checks for whether you're
not giving back memory that you've asked
for and that's what we call leaking
memory and this is kind of like a nice
visual for how you can think about where
things live when you declare them or
when you ask for them with malloc versus
when you just declare them naturally as
local variables and your functions or
when you declare functions themselves
that was kind of like a brief overview
about pointers in memory but I know that
there's usually a lot of questions about
this so definitely let me know what
other questions are there yes
the question is and correct me if I
misheard you whether after you asked for
malloc you have to like free it right
after not technically right after so if
you recall in the speller example you
may locked memory or us from memory via
malloc to store your dictionary words
and then you didn't free it until later
on after you unloaded the dictionary
just as long as before the program
terminates you have freed any memory
that you've asked for then you're good
you don't have to like free it right
after or you know it's good it's good
practice to once you and your program
know that you're done referring to a
piece of memory you've asked for - just
free it but you can technically get away
with just freeing things right before
the program terminates there's another
question back here as well no we're all
good yes
right so the question is when we said in
start P equals ampersand n can we then
use P and ampersand and interchangeably
and I think the answer is yes right yeah
the only thing is that then you just for
readability I guess it doesn't matter as
long as you're you're being consistent
it's better to just use one thing to
refer to something instead of mixing and
matching because then people have to say
wait what is this again it's the safe
answer is just use P since you've
already stored and percent and in a
variable but technically they're the
same so you can use them interchangeably
okey dokey
I'm about to talk about data structures
so stop me now if you have any final
questions so I have to squint because
the lights are like awesome all right
one more question over here yeah so
again the intuition of why pointer is
like an array this is just because of
the way arrays were implemented
underneath the hood where the way that a
Rays work is they are essentially
pointers to the first element of the
array itself so declaring a pointer is
just kind of like explicitly doing that
without worrying about any like
syntactic sugar or whatever where
syntactic sugar is just like syntax that
does something in a little bit of a
nicer way than having to do it
explicitly yeah
right so with files when you're opening
a file you get a pointer to that file
itself and the question is what's the
difference between f get and f read I
would have to check the documentation
but I think F get gets you one bite at a
time correct you want to talk about
there's a number of different functions
for reading and writing from files and
if you check out Nancy is 5000 which is
cs50 programmers manual there's some
descriptions of all of these but F get C
for example is just going to read to you
one character at a time so you call F
get C you'll get one character you call
F get C again you'll get the next
character F read is generally used if
you're reading some a number of bytes at
a time and so in the case of recover for
example you wrote a program to read from
a memory card and the way you likely did
that was not by reading one bite one
bite one bite but you probably read in
like 512 byte blocks where you would
read one block at a time then read the
next block and so F right or F read
rather can read a certain number of
blocks from a file and read it into
somewhere inside of your computer's
memory okay let's talk about data
structures because pointers are still
relevant here who knows what this is
race of hands linked list I'm hearing
murmurings yeah linked lists and this
kind of goes back to the idea of what I
was saying like memories like
neighborhood where now instead of like
when you say int n equals 50 let's say
the N is like a studio now when you're
getting two linked lists for which we
use structs where you can have multiple
types it under one name we can talk
about you know one-bedroom apartments or
two-bedroom or whatever if we want to
extend the analogy where maybe in the
living room is the actual thing that
you're looking for maybe in the living
room is the integer and then in the
bedroom there's like a little clue like
scavenger hunt here's an address of
another house and so if you follow the
address of the other house and you go
check it out you see in the living room
oh here's another integer is the integer
two and then in that bedroom there's
another scavenger hint that says hey
check out this address you're gonna find
something there you check out that
address and you see in the living room
there's a three
and then in the bedroom you don't have
any clues you don't know where to go
from here and this is null which means
that we're not pointing to anything else
this is the end of the linked list and
pictorially we represent it using arrows
so that we don't have to worry about you
know hexadecimal notation and addresses
and whatever it's just overall kind of
nicer but you can just keep it in the
back of your mind that this is actually
what it is right it's just one portion
of the struct contains you know an
integer whatever value you're looking
for it can it doesn't have to be an
integer but for example and then another
portion of the struct contains a pointer
to another struct of the same type
that's going to contain an integer and a
pointer to another struct of the same
type and so on this is essentially what
linked lists are why are linked lists
good why would we bother using a linked
list rather than an array for example
don't be shy yeah
perfect yes with a linked list you have
dynamic memory allocation let's say that
right now your last element here you
decide that you don't want this to be
the end of your list you want to add
something else well you can just use
malloc get a little bit more memory and
set up an address here on this element
to point to that new struct that you've
asked for whereas with an array when you
declare an array you have to tell the
compiler how many they're like how many
elements in that array do you want off
the top you're like up front and then if
you want more elements in that array
later on you're just gonna have to ask
for a new array and it's a whole ordeal
so with linked list you can just
continually grow it and use exactly as
much memory as you need or you want why
might you use an array over a linked
list maybe someone on this side yeah
exactly
erase have random access because when
you ask for an array and you tell it hey
I want an array of 40 elements and if
it's an integer array then that means
that you get you know 40 times yeah
let's say you have an array of
characters then you have to pretend you
get 10 bytes so the 10 bytes are
contiguous and so you know that since
the blocks of memory are all right next
to each other you can access through
pointer arithmetic the last element or
the middle element or so on and so forth
just by adding however many you know
bytes you need to get to that index
whereas with the linked lists since
you're just asking dynamically for
memory this memory can come from
anywhere in the heap it's not gonna be
right next to each other maybe this
house is in one in one corner of the
neighborhood and this one is all the way
at the other end so you just have to
kind of like if you're looking for a
specific element in your linked list you
just have to keep following the
breadcrumbs until you reach the actual
house that contains the element that
you're looking for so there's this
element of trade-offs here and here's
the question about the the answer to the
question about the syntax the reason why
we have struct node here in this
definition of like a node where you'll
recall a node contains just a number and
then a pointer to the next node is that
if we want to refer to the node we need
to be able to call it something and in
the previous
in the previous example of a struct will
you notice that we just had type def
struct and then the fields but there was
no name so there wasn't any way to
reference to a struct and so here when
we give it the name here type def struct
node now we can say oh this type is
struct node so struct node pointer next
and then it's before you also put the
name here just first and taxes sake but
yeah that's just so that you have a
reference to the actual name of the
struct so that you can refer to itself
recursively otherwise if it has no name
there's no way to refer to it okay so
we've seen a race we've seen linked
lists here's a binary search tree which
in a way is really just a linked list
that's been taken to the next level you
can imagine and let me define this real
quick a binary search tree is a tree
that has four where each node has
maximally two children and then each
each child to the left of a node has to
be less than or equal to depending on
the implementation it can be strictly
less than or less than or equal to let's
just say strictly less than each child
to the left of each node is going to be
strictly less than the value of that
node or the value at each child so here
you see we have four to one and you can
imagine a trivial case where let's say
we have the numbers 10 through 1 and
they're all just kind of like less than
the previous one so you just end up with
a linked list right because 10 9 8 and
so on and so forth so really these are
kind of like linked lists except we try
to there's other types of there's like
the height balanced binary search trees
that enforce this kind of like construct
where you have more of a actually
balanced tree instead of just one
trivial linked list but in theory let's
imagine binary search trees that are
balanced on both sides where the height
to the left is at most one more or less
than the height to the right of the tree
what might these be good for spoiler in
the name right
by searching binary search is going to
be very easy industry because it's
inherently sorted you know that if
you're at any particular node anything
to its left is going to be less than
that value and anything to the right is
going to be greater than that value so
this is amazing if you're you know
looking for Mike Smith in the phone book
or you know what have you or if you're
interested in questions such as what are
given some you know structure of
information you're looking at or you're
asking a question like how many things
are less than some specific value or
what things specifically are less than
some specific value then you can go to
that specific value and just grab
everything to its left so there's plenty
of applications for binary search trees
but primarily yeah for searching they're
great they'll run in log in time like
we've discussed with binary search we've
also seen other data structures like
hash tables can anyone explain how a
hash table works you can look at the
diagram yeah see your hand back there
yeah yeah it's it's an array of linked
lists essentially and you can think of
it really as an array of struct pointers
essentially where it's a pointer to a
struct that where we've defined the
struct to also contain a pointer to the
next one and so forth but it's simpler
at its simplest level an array of linked
lists is the way to go and recall that
especially in the examples with speller
when you're looking at dictionaries the
way that we decided where a particular
entry might go in a hash table is by
hashing the value of the element and
then producing an index so if we
remember the hash of the simplistic hash
function that we came up with for a for
let's say dictionary if you look at the
first character of a word it tells you
you know in our alphabet from 0 to 25
ignoring case it'll tell you we're on an
array of size 26 to put a particular
word so Alice might go at index 0 Bob
go ahead index 1 and so on and so forth
up until Zacharias would go at position
25 in the array and then anytime that
you have another word that begins with
the same character that goes at the same
position in the array you can kind of
get over this collision by making a
linked list so that you can then go to
position 25 and access Zacharias and
access whatever other Z names that you
have there this is not necessarily a
great hash function this looking at the
first character can anybody tell me why
why might an array of size 25 not be the
best yeah
yeah precisely like what if you're
looking at a set of names that all begin
with the same character then suddenly
you have one one entry in the array that
has you know 26 nodes and then all the
other ones are empty you're not really
using your memory like very efficiently
or just what if you're looking at a huge
number or a huge list of names and even
if they're spread out fairly evenly
across the different indices of the
array
there's just ends up being like a huge
linked list for each one so this is the
nice thing about hash tables is that you
can kind of like structure or ask for as
much memory as you think you're gonna
need to avoid collisions so you can
instead of using a simplistic hash
function that just looks at the first
character and gives you back a number
between 0 and 25 use a more complex hash
function that does some magic underneath
the hood to a string and then output
some number between whatever 0 or like
20,000 and then suddenly you can have an
array of size 20,000 to store all these
different names in such that you can
theoretically have constant time lookup
assuming that you don't have a lot of
collisions based on how many different
buckets each name can fall into the
trade-off there is then that you're just
taking up way more space to save on time
and there's like different types of hash
tables that will address these types of
things but I'm not going to go into it
for the sake of what we've seen so far
in terms of other data structures we've
seen tries for retrieval and these are
essentially kind of like an inverse of a
hash table one might say where it's a
tree that where each node contains an
array of pointers to other nodes that
contain arrays to pointers to other
nodes and in addition each node also
contains a flag that tells you for
example in the case of dictionaries and
words whether the current node is the
end of a word so a try might look like a
node where you have an array a through Z
or whatever alphabet you're using and if
you
store or looking for the word hello you
would let's say you're looking for it so
it's already here you would check the
index of the character H in the array
see if there's an H there or true or
false or what however you want to do
this a try let's say that if a word is
in the try you just set the index of the
array at that note to be true so right
here where the H is that would be true
and then you go to the next node and you
see if the e and that array is set to
true and then you go to the next node
and you see if the l is set to true and
at each point you're checking is the end
of word flag set to true if you're
looking if you're just checking if
that's a word up until you get to hello
where you see that H ll and o are all in
the try and in addition at this node
that contains the oh there's a flag that
says this is the end of a word so then
you can confirm whether hello is and the
try and in theory the nice thing about
tries is that even though they take up a
huge amount of space they give you
what's essentially constant time lookup
especially for English words where the
longest word that we have is I think
like 45 characters long and so you have
at most Big O of 45 which is really big
o of 1 lookup for words you just have
like an incredible amount of space that
you're taking up so there's these trade
offs again we've also talked about
abstract data structures like
dictionaries in the context of Python if
you'll recall a dictionary you can
access it by its a it's a data structure
that contains key value pairs so if you
have a dictionary D if you store if
you're using it to store students you
might have like a student's name you
might have students hu ID you might have
a student's house and if you access D at
key name it'll give you back like Emma
or Brian or Rodrigo if you access a hu
ID it'll give you back whatever value is
stored there the nice thing about
abstract data structures such as queues
and stacks as well is that since they're
abstract that means that you can
implement them with like say linked
lists or with arrays or whatever actual
tangible data structures that we have so
example like a queue which is just a
data structure where the first thing is
the first thing in it's the first thing
out it's in the name right like a queue
if you're waiting in line for a store or
if you're if you own a restaurant and
you support online orders in theory you
want the people that order first to get
their food first so you might store them
in a queue where the two kind of like
stand out properties of it is that it
has an in Q and a DQ function where n
queue stores or inserts an element into
the queue and DQ takes it out and so in
theory with with a queue you have
if this is your cue you insert elements
here and then they end up coming out
here whereas with a stack you insert
elements here at the top and then they
also come out from the top where a stack
is kind of like a stack of trace you
insert element insert elements and they
start getting kind of buried under all
the new insertions and then when you get
something out you just take the one at
the top whereas with a cue the first
thing that goes in you also want it to
be the first thing that goes out and so
cues we refer to as first in first out
FIFO and stacks are last in first out
leaf o or LIFO however you want to
pronounce it but yeah the main take away
with these abstract data types are that
you can actually construct them with
whatever data types that are tangible
that you want and if you're curious you
know you can now actually implement a
queue using two stacks and you can
implement a stack you can't accuse and
this all kind of all kinds of fun stuff
that you can do there but this is the
main overview of data structures and I
want to stop here to ask what questions
there are before I turn things over to
Brian to talk about week six yeah
oh right what are the two words that
correspond to NQ & DQ four stacks so
four stacks you have push and you have
pop where push means that you're pushing
to the stack or you're inserting into it
and pop means that you're taking out of
the stack where it's I don't know it
push and pop just sounds like you push
it and then you pop it off the top I
don't know why any ink you and DQ are
the corresponding ones for Q's any other
questions you guys see anything I don't
see okay without further ado let me turn
things over to Bryan to talk about week
six all right two weeks left left in the
class to talk about so up until week
five everything was all about see this
lower level language where there was no
magic if you wanted a data structure you
needed to build it for yourself week six
we now introduce Python a higher-level
language where more is given to you
python is an interpreted language where
instead of compiling the code first into
assembly and then into machine code we
run a program called an interpreter that
is just reading our Python file
line-by-line and executing those
instructions and those instructions
ultimately look a little bit different
than the instructions look like in seam
but there are a lot of similarities so
in order to print something out we would
call a function just as we didn't see in
this case the function is called print
and the argument is put in parenthesis
so hello world is what we would call the
argument to that function or the input
to that function if we store the result
of a function like getstring inside of a
variable called answer we can again
print out the value of a variable using
print and the way we do that in this
case with using what we called an F
string a special formatted type of
spring where we could use these curly
braces here to mean plug in the value of
a variable inside of the string at this
position in the string so answer is a
variable and when we put answer inside
of those curly braces we mean take the
value of answer and plug that into the
string and then print out the result so
that we end up saying hello to Emma or
hello to whoever typed in their name
into the program we saw a couple of
other types of syntax here's how you do
a variable in Python I can just say
counter equal zero name a variable
equals a particular value values in
pious
have types so counter in this case is an
INT but unlike in c where you needed to
specify when you declared a variable
what the type of that variable was i
needed to say and c in counter equals 0
in python python is able to infer the
types for you if you say counter equals
0
well python knows that 0 is an integer
so may as well just treat the variable
counter as an integer so it's not that
the types don't exist the types do exist
and you can still use those types
incorrectly it's just the Python figures
out for you what the types are without
you needing to specify what those types
are increasing a variable counter equals
counter plus 1 very similar to C just no
semicolons in any of Python and whereas
in C we would enclose blocks of code
like blocks of code inside of a
condition or inside of a function or
inside of a loop using a pair of curly
braces in Python we do it by having a
colon and then everything inside of the
block of code is indented so the
indentation is mandatory in Python we're
here we're saying if X is less than Y
then execute any of the code that is
indented printing X is less than Y and
as soon as we stop indenting that code
is outside of the if condition so to
speak hopefully this is familiar I we
can also have else conditions so if X is
less than Y and then else where again we
end else with a colon and then followed
by indented all of the information
inside of the else block and we can have
el if a LIF instead of else if as it
wasn't same to add additional branches
there as we have different conditions
each of which might do something a
little bit different loops in Python
very similar to loops in C where again
we can use the wild keyword to repeat
some block of code as long as some
condition is true if the condition is
literally the word true that means this
is going to continue to execute forever
so this will print hello world again and
again and again but that true could be
replaced by any boolean expression
checking if two things are equal to each
other checking if one thing and
something else is true or one thing or
something else is true so a lot of the
same ideas that we saw in seem again
apply in Python as well and then loops
in Python might look a little something
like this for I in range 3 range 3 is
the way in python of getting basically a
sequence of 3
elements 0 1 & 2 so this is going to
repeat 3 times 0 1 2 just printing out
cough so a little bit more succinct than
writing the same idea in C you don't
need the into I equals 0 I is less than
3 I plus plus syntax you probably wrote
a number of times over the course of the
last 7 weeks or so it's a little more
succinct in the world of Python and then
in terms of the types that we have a
requester yeah
so what do you do if you want to
increase I by two every time instead of
by one couple ways you could do that one
is that though we did wasn't shown in
lecture range can actually take
additional arguments so you could
specify not only like count three times
we could say like count from this number
to that number accounting in twos or
counting by threes so you can add
additional arguments to make that work
and you can take a look at pythons
documentation for exactly what the order
of those arguments are alternatively you
could use something like a while loop
where you just have a variable called I
and then inside of the while loop you
say I equals I plus two to increase I by
two every time you run the loop other
questions about Python syntax that we've
taken a look at so far
all right so data types in Python we saw
the some data types that existed in C so
boolean values floating values integer
values and string values these are all
types that are built into Python but
Python also has some types that we
didn't have access to in seed directly
the Python will just give to us and
these are often types that we'll use for
representing sequences of values so a
range for example is for a sequence of
numbers where for example range 3 gave
us a sequence 0 1 2 so we could easily
loop over a range of possible numbers a
list is kind of like an array and see
it's a sequence of values that you can
mutate that you can change and so unlike
an array in C I can add things to the
list I can remove things out of the list
but this is a mutable sequence I can add
to it remove from it change elements
inside of that sequence unlike a tuple
or a tuple which is a sequence of
immutable values for things that aren't
going to change so Python draws a
distinction if you have a sequence of
values and you know that sequence of
values is not going to change you're not
going to need to add anything to it or
remove anything or modify any of the
values if you can use a tuple type
instead in order to represent that data
as well and then finally a couple of
other types you've probably seen over
the course of the past couple weeks a
dict short for a dictionary is a
collection of key value pairs where a
key value pair is anytime I want to map
one piece of information to some other
piece of information so in a phone book
for example I might want to map people's
names to their phone numbers or
an actual dictionary I might want to map
words on to their definitions or in the
case of the DNA problem that you worked
on for problem set six you might have
mapped DNA sequences to the number of
times they repeated inside of a person's
DNA so anytime we have this generic idea
of wanting to map one type of value onto
another type of value a dictionary can
often be helpful for that and then
finally we took a look at sets which are
just four collections of unique values
and so in lecture David demonstrated how
you could write a spell checker by using
a set in order to store all of those
words just a collection of values for
storing information
each of these different data types have
different operations you can do on them
they run in different run times and all
of that information is on pythons
documentation and so definitely a useful
resource to take a look at either now or
during the test if it comes up it's
taking a look at pythons documentation
for these things to get a sense for how
it is that these data structures work
and what their run time ultimately is
like questions about Python in that
syntax all right
so oh and then in the context of Python
we were also able to talk about the idea
of regular expressions so we could use a
library in Python the regular expression
library to look for particular sequences
of characters so if I wanted to check to
see if someone had typed in yes or maybe
we wanted to just accept why or yes we
could use a combination of these regular
expression characters to be able to
express that idea and so a question mark
for example means that something is
optional it isn't me I could include it
or I don't necessarily need to include
it so if I want to check if I'm having
someone type in some input and I want to
check like did they type in Y or did
they type in yes and I want to accept
both of them then one thing that I could
do is say that all right well I want to
I want them to definitely type in Y but
the es is optional for example and so I
might in parentheses say ES and then a
question mark and this was the way in
lecture we said here's how you can
represent the idea of either Y or Y es
the Y needs to be there but the es is
followed by a question mark which means
the es is optional and so you'll often
see regular expressions in the context
of checking to see whether
not an input is valid if you've ever had
to go to a forum and type in an email
address and it rejects it because it's
not a valid email address odds are it's
because there's some regular expression
that's checking like does this actually
look like an email address are there
characters followed by an @ symbol
followed by other characters so you can
use regular expressions to do that type
of input validation as well so questions
about Python or regular expressions or
any of the features of the language that
were talked about in week six alright
one last week to talk about in terms of
content of the course if we looked at PC
then we looked at Python and then this
past week we looked at sequel a language
used for interacting with databases and
there were a number of things we wanted
to do with databases we wanted to be
able to create a table which you can
think of it's like a spreadsheet table
just something with rows and columns for
storing data and then there were
operations that we wanted to perform on
that table in order to add data to it
modify that data update that data in
other ways and so the first thing we
needed to know how to do was how to
create a new table and to do that we
used a create table query where the
query looked like this create table
followed by the name of the table in
this case movies as with the case in the
problem set that you just completed and
then we specify what are the different
columns of that table what are the
fields or properties of every movie that
I want to store along with what type of
information do they represent so here
inside of the movies table every movie
has an ID which is an integer just so I
can uniquely reference every movie every
movie has a title which is of type text
it's just some text-based information
and I can add constraints to particular
fields I can say the title is gonna be
text but it's not null I can't have an
empty title where I have no title every
movie must have a title and not null
enforces that constraint that every
movie needs to have a title every movie
has a year just some numeric value
representing what year the movie was
released and then down here I specified
that the ID column is the primary key
and the primary key just means this is
the main way that I'm going to reference
a movie and it is going to be a unique
way to reference a movie that yeahmaybe
two movies were released in the same
year maybe two movies have the same
title but no two movies will have the
same ID the ID is a unique
way of identifying one particular movie
and so we're calling it the primary key
the main way via which I can uniquely
reference a single movie what questions
do we have about this create table query
how we create a table for these movies
why do I not poet put ID integer not
null I certainly could add I not know a
constraint just to enforce that as well
yes you could do that in general often
what you'll do with an integer ID field
is you'll added a property to it called
Auto increment which means the ID will
automatically increase to the next value
this was the case in the houses problem
that you worked on the table we gave you
had an automatically incrementing ID
field so you didn't need to worry about
the ID and there that way the database
will enforce the property of always
giving a new ID to every new item we add
all right so now how do know that we
have this table how do we add data to
that table to do that here was the query
rent we ran an insert query to insert
data into the table and the way that
query worked is we said insert into what
table the movies table and which columns
am I going to specify values for come
next so in parentheses title comma year
because I'm about to insert a value for
a title and then a value for the year
what values of my inserting well I'm
inserting Toy Story and then 1995 so
then a the title of a movie and then a
year and importantly the order of these
values needs to be in the same order as
the order of the columns that I specify
so here I'm saying Toy Story is the
title 1995 is the year and that is the
row that I would like to insert into my
movies table yeah
yeah so what happens if for example
there's a field that's unique like an ID
field or maybe there's some other unique
field that I've specified that the
database needs to make it unique and I
try and insert something into that
database where the uniqueness constraint
fails you can actually try this but most
databases will reject the insert it will
not let you insert something into the
database if it violates a constraint
like a uniqueness constraint likewise if
I try and insert something into
something where it says not know I might
get a database error that says that if I
didn't specify a value for the field
it's not going to let me insert it into
the database so that's why we add those
constraints so that the database makes
sure that we don't use it incorrectly
all right how do you update data after
you've inserted it into the table let's
imagine the toy story's rating has
changed on IMDb's website and we need to
somehow update this in order to reflect
it we say update followed by the name of
the table we want to update in this case
movies what do we want to change set
rating equal to 8.2 for example whatever
its new rating is and if I just had this
first-line update movie set rating
equals to 8.2 the effect of that would
be that every movie in the database
would now get a rating of 8.2 here I'm
assuming the movies table has a rating
column which wasn't in there before but
it's just imagine for now in order to
specify which movie I wanted to apply to
I might say where title equals Toy Story
to constrain myself down to only a
particular title and for this particular
movie I want to set the rating equal to
a certain number deleting from a table
follows a similar rule if I want to
delete all the movies that are the worst
movies in the database set up a rating
of 0 I can say delete from movies where
rating equals 0 for example and that
will achieve that effect was there a
question here
what do you want to do if you want to
change more than one thing and update
whatever this where Klaus returns that
is the number of rows that are just
going to apply the update to so I could
update multiple different if there are
multiple movies called Toy Story if I
wanted to update all of the movies with
the rating above a particular number or
all the movies released in 2008 you
could do that just by specifying a more
general where query and that would be
able to achieve that effect so if you
wanted to change multiple fields yeah
you can I'm pretty sure you can include
multiple comma-separated ideas there I
forget the exact syntax but it's along
those lines alright so what came up next
was how you deal with like multiple
tables about multiple tables that I
wanted to join together somehow and the
way I can do that here is to say I want
to select maybe the let's imagine now
that instead of having a single table
that has movies and ratings as we saw in
the problem set you separated that data
out into multiple tables a movies table
and a ratings table and the way to join
that information together was to say
select the columns I want the title of
the movie in the rating from the movies
table but I need to now join it with
some other table to be able to access
the information I want so I can join it
with the ratings table and then when I
join two tables together I need to tell
sequel how to join those tables together
so I can say the ID column of the movies
table is equal to the movie ID column of
the ratings table those two columns are
how these two tables line up it's how
the data relates to one another and so I
can join tables like this in order to
combine two tables together to be able
to query across multiple different
tables when there are a couple of ways
that I can query for information across
multiple tables one way is using that
join syntax to join multiple tables
together another thing I can use are
nested queries where I take a sequel
query and put it inside of another query
so if I wanted to figure out all the
people who starred in Toy Story for
example one thing I might do is first
just select the ID for movies where
title equals Toy Story in other words
what is toy story's ID and then for that
particular movie ID let
get all the people that started it so
select all of the person IDs from the
stars table where the movie ID is
whatever toy stories ideas so those
bottom two lines are going to tell me
what toy stories movie ID is and then
that first line uses toy stories movie
ID and looks in the stars table to find
all of the people who starred in that
movie so you can take a sequel query put
it inside of another query and repeat
that process nesting queries inside of
each other in this case I'm assuming
that select ID for movies is only going
to give me back a single ID but if I
wanted the stars of all the Toy Story
movies not just the first one I might do
something like this change the equal
sign to a like I don't want to just look
for Toy Story but any toy story % where
% is a wild card meaning look for any
movie title that begins with the word
Toy Story and then here I changed where
movie ID equals to where a movie ID in
to mean if the movie ID is in any of the
IDS of movies where the title begins
with the word Toy Story then I want to
query for it there as well
questions about that syntax yeah
yeah
equal sign general use for the first or
the only value where there's one value
that I'm looking for in generally when
I'm dealing with the sequence of values
and I want to check for membership in
that sequence then finally just to wrap
up sequel a couple of threats or
concerns you might want to be aware of
the first of which is race conditions
which can happen if multiple people are
trying to do something do something with
the database at the same time so if for
example two people are trying to like an
Instagram post at the same time what
might happen well if the code isn't
written quite carefully enough you might
end up with situations where two
different programs are trying to update
some value in a database at the same
time and they conflict with one another
in order to get potentially dangerous
results so something to be mindful of
there as well and then a particular
danger has to do with what's called
sequel injection which is what happens
if you're not careful and you just
literally plug in values into a sequel
query if you're just plugging an input
into a sequel query you allow for the
possibility that an adversary could plug
in danger a sequel code into your query
in order to get you to run code you're
not intending to run on top of a
database so for example if someone
logged in but in the login name they
added like a n quotation mark and a dash
- where - - and sequel introduces a
comment in sequel so it ignores the rest
of a query then you might imagine that a
login system that is checking someone's
username and password if you literally
just plug in the - - it's gonna comment
out everything after the query which
means it's going to ignore checking the
password which means if the person who's
designing the system has not done so
securely they might end up allowing
someone to log into an account even if
they haven't provided the correct
password by nature of using sequel
injection this security vulnerability
that we can defend against by making
sure to escape our input and that's one
thing that the sequel library does for
us so questions about these threats or
vulnerabilities in sequel yeah question
yeah so they're joins the nested queries
can be used for similar things there are
just some situations that will often
lend themselves better towards one or
the other just in terms of how you might
logically think about it and it's gonna
vary a little bit from problem to
problem but yeah it's a good question
yeah
[Music]
Group buys another piece of syntax we
didn't quite look at just now but it's a
way of taking all things that share the
same value and collectively grouping
them together into a single entry so if
you group things by a person ID you'll
get all of those person IDs grouped
together into a single row all right so
we'll go ahead and wrap up here the test
again is going to be released at 7:30
later this evening you'll have until
Friday in order to work on it we'll
stick around for a little bit to answer
your questions if you do have them but
best of luck with the upcoming test