Week 2: Algorithms and Programming Concepts

So far you’ve been looking
at making web pages. Now, we’re going to switch gears for awhile and we are going to talk
about computational thinking, the type of thinking that enables
you to write computer programs. You’ll be programming in JavaScript so
that, eventually, you can use your programs
to enhance your web pages. In this module, you’ll learn some basic
programming concepts and JavaScript syntax, a process for designing algorithms
or solutions to programming problems, and how to work with some image processing
libraries we’ve developed for this course. So why are you learning programming? What can you do with it? Programming is great for solving problems that have a lot of
computation or repetition in them. For example, what if you wanted to
manipulate the images on your web page? Since images are made up of pixels,
to manipulate the images on your web page, you would need to look at
all the pixels in them. If you had an image that was 100 by
100 pixels, relatively small image, you would still need to
look at 10,000 pixels. This is hard for humans,
but easy for computers. If you tried to look at all 10,000
pixels by hand, you might get bored, you might make mistakes, and
it would definitely take you a long time. A computer could finish looking at all
10,000 pixels in just a few seconds. One common application of image
processing using programming is using green screens to change
the background of an image. If you take a photo in
front of a green screen, you could write a program to change
every green pixel on the image so that you replace the green
screen with another image. This is the example you’ll
focus on in this module. You’ll learn our seven step process for solving Problems, the basics of
JavaScript, and the programming concepts you’ll need to be able to solve
the green screen problem and many more. Now, let’s start by looking at one
important idea behind programming, that everything is a number.

Knowing how to use a computer program without knowing how a computer works is an example of:

Abstraction

Computers only work with

numbers

Welcome back. In this lesson, you’re going to learn an
important principle of computer science, everything is a number, or put a different
way, computers only work with numbers. If we were to delve into the hardware, we
would find that it only deals with bits, 0’s and 1’s. We’re not going to look into
the particulars of the hardware, but the important thing to know is that
computers can only work with numbers, and really, can only do math. In fact, there is nothing that
a computer can do that you cannot do. Computers can just do math really fast,
so they can operate on large sets of data billions of times
more quickly than you or I could by hand. Fortunately, you do not typically need
to think about the details of the bits, due to a wonderful principle
called abstraction. Before we talk more about
how everything is a number, we’ll take a minute to
talk about abstraction. Abstraction is the separation of
the interface, what a thing does, or how you use it from the implementation,
how it does that, or how it works. You can understand abstraction and its usefulness with
a non-computer related example. Think for a moment about driving a car. Abstraction lets someone drive
a car without knowing how it works. I know that if I press down on
the gas pedal, my car will go faster. However, I do not know about the
complicated inner workings of my car that make that happen. Abstraction often comes in layers, and what layer you need to work at
depends on what you need to do. For someone driving a car, the level of
abstraction appropriate to think about is what the controls of the car do. The inner workings under the hood
are hidden and not important. However, for a mechanic, the details under the hood are important
and are what she works with day to day. But even there,
there’s a different level of abstraction. The mechanic is concerned with how
the parts of the engine fit together and work together, but maybe not with the
physics that go into designing the engine. The engineers who designed the car would
have worked at that level of abstraction, applying physics to make
a car that works properly. Of course, there is an even
lower level of abstraction and more theoretical physics that they
did not concern themselves with. We could keep going down until we
reach the most theoretical physics at the boundaries of human knowledge, all things that you do not
need to know to drive a car. These same concepts apply in programming. The level of abstraction that you
need depends on what you are doing. Before this class, you have probably used a computer without
knowing anything about how programs work. Now you will learn how programs work, but
there will be deeper levels of abstraction that you generally will
not need to know about. Now that you know about abstraction,
let us return to the principle that everything is a number,
giving you a bit of a peek under the hood. You may be a bit surprised by this idea,
since you’re used to using your computer working with things that do not
seem like numbers, such as letters. However, these are relatively
easy to encode as numbers. We could go with a = 1,
b = 2, and so forth. What computers actually do
is represent characters, symbols that can be letters,
digits, punctuations, and so on. One way to encode characters is ASCII,
in which, A is 65, a is 97,! is 33, and various other characters
have other numerical values. If you needed to look up
the numerical value of a character, you could find them in an ASCII table. However, you generally do
not need to worry about the particular numerical values,
due to the joys of abstraction. Once we have characters, we can also have strings,
sequences of characters such as “Hello!”. Strings com up quite often
in computer science, as programmers frequently
want to manipulate text. In fact, you’ve seen strings in HTML. Strings are another great
example of abstraction. You can write “Hello!”, and it gets turned into numbers that
your computer can work with. You generally do not have to think
about the numeric representation, but you can manipulate it if your
programming task calls for it. So why is it so important to know
that everything is a number? Well, sometimes you want to do math with
things that do not seem like numbers. Cryptography, the science of
keeping information secure, relies on the ability
to do math on strings. When you visit a website using HTTPS, the
information sent back and forth between your computer and the web server is
encrypted so that nobody else can read it. That process involves
doing math on that data. Another reason that it is important to
understand that everything is a number is because this is why
programming languages have types, which tell it how to
operate on these numbers. Even though everything is a number, programmers want to interpret
those values in different ways. Do the numbers mean letters? Do they mean pictures? Do they actually just mean plain numbers? The type of the data tells what
the numbers mean, and thus, how to operate on them. If we add two strings together,
we might want to concatenate them, put one after the other
to form a longer string. In that case, the string “1” +
the string “1” would be the string “11”. If we have just the number 1 and
we add it to 1, we would get 2. A third reason why the everything is
a number principle is important is that whenever you have data you want to work
with, you need to represent it as numbers. You may be able to use existing types, such as strings, which already represent
information as numbers, to help you out. Such is the joy of abstraction. One other thing that may surprise you is
that programs themselves are numbers. Then again, it may not surprise you, since you just learned that
everything is a number. As you have already seen, you express your algorithms to
the computer by writing text. The code that you type in is a string. Another program takes this string and
figures out how to turn it into numerical instructions that
the computer can execute. The fact that programs are numbers
is actually quite powerful. It means that you can download and
run new programs on your computers. They’re just data, like everything else. The fact that programs
are also just like data is at the heart of many security issues. Hackers give a program input
that have the numeric encodings of instructions they want to execute, and
then trick the program into running it. Of course, as you write programs, you do
not need to worry about the numerical encoding details, all because of
the wonderful ideas of abstraction. So in this lesson,
you learned that everything is a number, an important principle since
computers can only do math. You learned about abstraction, the separation of interface from
implementation, and how that means that you may not always need to think about how
things are numbers to compute with them.

Hey, Drew. I remember in the last lesson, you taught us that everything in
the computer was presented with numbers. >> Sure, Robert. This is a very important principle
in computer science as computers can only compute on numbers. >> I remember and it was really cool you
showed us that we could represent letters and logic with numbers but I have so
much more on the computer than just words. For example, look at all of these images. Surely they’re not just numbers. >> Actually, Robert, if we were to
zoom in on one of these images, we would see that it’s made of
many tiny little dots call pixels. Each pixel is a single color and
is numerically represented by a red component,
a green component and a blue component. Each of these values ranges from 0 to
255 where 0 means none of that color and 255 means as much of
that color is possible. Once we’ve represented each pixel as
a number we can represent the entire image with thousands or millions of pixels
meaning thousands or millions of numbers. >> Wow! That’s really cool. But if they’re just numbers,
we could do math on them. If I had magenta and I had green,
could I add them together? >> Sure. Let’s see how. We can do math on colors
because they’re just numbers. To answer Robert’s question, if we took
magenta which has a red value of 255, a green value of 0, and
a blue value of 255 and added it to green which has a red
value of 0, a green value of 255, and a blue value of 0,
we would get a red value of 255, a green value of 255 and
a blue value of 255 which would be white. In fact, we can solve a lot of
useful problems by doing math on the pixels that make up images. We can make an image lighter, darker,
redder or bluer or we could compress an image so that it takes less time
to transfer across the Internet. We’re still looking the same to
the human eye, for example a jpeg file. If you’ve ever heard of a movie codec,
this is software that encodes and decodes video doing a lot
of math to determine the images that make up
each frame of the video. >> That’s really mean. So do you think that I can write
an algorithm that would replace all of one color in an image? With a completely different image? >> Sure, in fact that’s what’s
happening to us right now since we’re standing in
front of a green screen. The video software is iterating over
all of the pixels in our images and replacing green ones
with a different image. We could, if we wanted to,
give this lesson in front of dinosaurs or even in outer space. >> [SOUND] That’s really amazing. I’m going to go write the green screen
algorithm for practice right now. >> Produced by Duke University,
online at duke.edu.

The Green Screen problem
also called a chromo key problem because it is keyed
to the colors chromo or hue, like removing the red from eyes
in a picture with a flash. Is common in videography as it allows
actors to be recorded in a studio, and placed in front of a background or
made from an image or video taken in another setting. This algorithm is what let Dru and
I talk in outer space with dinosaurs. Now, we’re going to walk
through solving this problem as an example of how to approach
programming problems in general. The first thing we need to do
before we solve a program problem is to figure out exactly how to
solve that problem ourselves. You cannot write a program, explain to the computer what it needs
to do until you completely understand yourself how to do the task in
a precise step by step fashion. In fact, this is often
the hardest part of programming. Now, trying to do this particular
example of the Green Screen proplem will be too difficult because these images
have 2 million pixels each approximately. Trying to operate on them by hand
would take an impossibly long time. Instead, it is a good idea to work
on a smaller instance of the problem by hand to gain a deep understanding
of how to solve the problem. In this case, we are going to look
at a 2 pixel by 2 pixel image. We will start by picking a 2 by
2 image to be the foreground. The image that will go on top, and we’ll
pick a 2 by 2 image to be the background. Also, we will need an image called
the final result or output. This should also be 2 by 2. Now that the examples are chosen,
let’s go through and figure out what color to make
each pixel of the output image. Great! Now, we have solved an instance
of a problem by hand. The next step is to write down exactly
what we did in a step by step fashion. I started with the foreground image
I wanted, I’ll call this fgImage and with the background image
I’ll call it bgImage. I then made a blank image of
the same size, I’ll call it output. I looked at the first pixel in fgImage and
it was red. So I set the output’s corresponding
pixel to be red as well. I looked at the second pixel in fgImage,
it was green, so I looked at the same position in bgImage and set output’s
corresponding pixel to bgImage’s pixel. I looked at the third pixel in fgimage,
it was green. So, I looked at the corresponding
pixel in bgimage. It’s blue so
I set the output to be that same color. I then looked at the fourth
pixel in fgimage and it’s blue, so I set the corresponding
pixel to br blue in the output. Great! Now, we have a step by step set
of instructions to describe exactly how we solve the problem for
this particular pair of images. But to write a program, we want to
be able to solve this problem for any image of any size. Now, if you look at these steps closely, you’ll see that there
is a lot of similarity. We’re doing almost but not quite the same
thing for each pixel in the image. When the fgImage’s pixel is green,
we use the the bgImage’s pixel. And when the fgImage’s pixel is not green,
we use the fgImage’s pixel directly. Going back to our step
by step instructions, we will rewrite each step to
be a little bit more general, taking into account this conditional
behavior we just observed. You can do this for each pixel’s step. And now each step is more general and
more similar. They would work for any 2 by 2 images,
but only for 2 by 2 images. Here we’ve improved the step-by-step
instructions to express the repetition over each pixel. Now, the steps are general enough
to work on any sized image. In fact, what we have done, is devise an
algorithm, that we’re going to implement. An algorithm is a clear step by step
set of an instructions to solve any instance of the problem
you want to solve. You can express an algorithm in
English as we have done here or in code as we’ll need to do
to let the computer run it. Everyone makes mistakes. When devising an algorithm there are many
different ways to make mistakes. For example, you may not have
seen the pattern correctly, or you may not generalize
each step correctly. To try to protect against
these types of mistakes, let’s try our algorithm out on a different
example to see if it works as expected. If it does, we’ll be more
confident that we did it right. If not, we’ve caught our mistakes
early before we went to write code. Of course, once we write code,
we will want to test them more thoroughly. But we’ll talk about that later. As you walk through your algorithm, you’ll
want to keep track of what step you’re on. For us, we’re going to draw a green arrow
to show where we are in the algorithm. You then want to go through each
step exactly as it is written. Here, I’ve picked the 3 by 1
image to be the foreground. And this 3 by 1 image
to be the background. And the 3 by 1 image to be the output. Here, I will keep track of
which pixel is the currentPixel where the blue arrow in the drawing above. This first pixel is green. So the algorithm says to look at
the same pixel in the background image which is yellow. And make the same pixel and
the output image also yellow. Those are all the steps for that pixel, so now the algorithm says to go to
the next one and repeat the process. We will continue to follow
these steps as they are written exactly as they are written
until we finish all of them. At this point, we want to see if
the image came out as expected. In this case, the output was right
since our algorithm appears to work, it’s time to write the code

Which of the following is the correct sequence for the seven step approach?

1) Work example by hand. 2) Write down what you did. 3) Find patterns. 4) Check by hand. 5) Translate to code. 6) Run test cases. 7) Debug failed test cases.

Now we’re going to talk a little bit
more about solving programming problems. In the last lesson, we worked through the
example of doing the green screen problem. We took a specific problem we
wanted to solve, taking images and applying the green screen
technique to them. And worked through step-by-step how
to go from that problem statement to a working piece of code. Now, what we’re going to do in
this lesson is we’re going to take a closer look at solving
programming problems. We’re going to teach you the seven step
approach that you’re going to use to solve programming problems through
the rest of this course and the rest of this specialization. As well as a tool that you can use to
solve programming problems in general, whenever they come up in
the rest of your life. In general, solving a programming
problem starts with a problem statement. I want to be able to take a foreground
image and a background image and combine them using the green screen technique or
anything else you might want to do. And ends when you have working
code that solves your problem. Now, doing this is a big leap. It takes a lot of work to go
from a problem statement to a working piece of code. And you may not be able to just
do this in your head all at once. Sometimes, when a problem becomes easy for you as you become more skilled,
you’ll be able to just do this and it will happen naturally and
you won’t need to worry about it. However, the seven step approach we’re
going to teach you is always going to be a good way to approach any problem where
you can’t just see the answer right away. So these are the seven steps
that you’re going to use to solve programming problems. And we’re going to look at each
of them and see how they work. You’ve seen this already with
the green screen example. We just didn’t talk about the details
of each step, we just did the process. The first thing to do is to
solve a small instance by hand. If you remember from the green
screen lesson that we just did, we took a four-pixel image. We didn’t want to start with the millions
of pixels that are in a real image, we just worked through for
a very small instance. Something manageable. If you have trouble with this step,
maybe the problem is unclear. The problem statement doesn’t
actually tell you how to do things. In which case, you need to find out what you’re
supposed to do before you can proceed. In a classroom situation,
this may involve asking your teacher or teaching assistant for clarification. In the real world, this may involve talking to your
technical lead, your customer, or refining the problem yourself to figure
out exactly what it is you need to do. The other possibility
if step 1 is difficult, is that you might need domain knowledge. If you’re trying to solve a programming
problem related to physics but you don’t know the physics
equations involved, then no amount of programming
expertise will help you. You need to consult a physics textbook,
a Wikipedia article on physics, or a physics professor to
understand the physics before you can try to solve
your programming problem. Once you’ve completed step 1,
you’re ready to proceed to step 2. In step 2, you’re going to write down
the exact steps of what you did in step 1. That is, you’re going to give directions
to someone to solve just that instance of the problem. Not to solve the more general case. Not to do it for any image. But just how you came
up with your answer for that the particular four-pixel image or
whatever your problem might be. The tricky part here is
that there are a lot of things that we as humans do without
consciously thinking about them. We just kind of naturally do them, and we have to think really carefully because
the computer doesn’t have common sense. We need to be very precise. If we’re a little sloppy
with our steps here, it’s going to make things
more difficult for us later on because we’re going to be
missing crucial parts of our algorithm. In step 3, we need to find patterns. We want to write an algorithm for any instance of the problem, not just
the particular instance that we worked. And so what we’re going to do is look at
the steps that we wrote down in step 2, and we’re going to find patterns. We’re going to think about repetition. What things are we doing over and
over again? How many times are we doing them? These will lead to looping constructs. Conditions, sometimes we do something,
sometimes we don’t do it. Under what conditions does this happen? This will lead us to conditional
constructs, like if else, and well have values. Maybe we used a particular number
because it was part of our input, or related to our input. We need to think about why we
used that particular number. If we have difficulties in this step,
we need to go back to steps 1 and 2 and do them again for different inputs. If we do these over and over again, we’ll
come up with more information to look for patterns from. We’ll have different sets of steps that we
come up with for step 2 that tell us how we work multiple instances of the problem
and be able to find patterns more easily. Once we finish step 3,
we want to check our algorithm by hand. We just came up with what we
think is a general algorithm, but we may have made a mistake. We may not have realized that something
happened in a particular case. Or we may have left a value that was
particular to the parameters that we chose. If we did one of these mistakes, we’d like to find this now before we
translate our algorithm into code. So we’re going to check this with one or
more different inputs which are again, going to be of sizes that
are manageable to do by hand. We’re not going to try it
on a million pixels but we might try it on a very small other
image or some other small input. Once we’re confident in our algorithm,
we’re ready to translate it into code. This is where the particular programming
language that we’re working in is going to come into play. So far, we’ve been looking at JavaScript. So we would take our algorithm and
express it in the syntax of JavaScript. Once we’ve written this down,
we want to run test cases. That is,
we want to execute our program and see, did we get the right answer
with our program based on what we expect the right answer to be, knowing
what problem we’re trying to solve? Every time we run a test case,
if it passes, that is we get the right answer,
we’re more confident in our program. If it fails, we know something
is wrong with our program and we move on to step 7,
debugging failed test cases. For this,
we’re going to use the scientific method, which we’re going to talk about
a lot in the next lesson. And this is going to help us
understand what the problem is and give us guidance on what we
need to do to fix the problem. Ultimately, what’s going to happen is
if we have an algorithmic problem, we’re going to return to Step 3 and
fix our algorithm. And if we have an implementation problem,
we’re going to return to Step 5 and correct our translation
of our algorithm to code. So these are the seven steps that you can
use to solve any programming problem, and we’re going to use them throughout our
examples in the rest of this course and specialization.