Developing an Algorithm

Loading...

Из курса от партнера Duke University

Programming Foundations with JavaScript, HTML and CSS

4418 оценки

Duke University

Programming Foundations with JavaScript, HTML and CSS

4418 оценки

Курс 1 из 5 — Specialization Java Programming and Software Engineering Fundamentals

Learn foundational programming concepts (e.g., functions, for loops, conditional statements) and how to solve problems like a programmer. In addition, learn basic web development as you build web pages using HTML, CSS, JavaScript. By the end of the course, will create a web page where others can upload their images and apply image filters that you create. After completing this course, you will be able to: 1. Think critically about how to solve a problem using programming; 2. Write JavaScript programs using functions, for loops, and conditional statements; 3. Use HTML to construct a web page with paragraphs, divs, images, links, and lists; 4. Add styles to a web page with CSS IDs and classes; and 5. Make a web page interactive with JavaScript commands like alert, onClick, onChange, adding input features like an image canvas, button, and slider.

Из урока

Algorithms and Programming Concepts

Introduction2:05

Everything Is a Number6:41

How Is That a Number?2:55

Developing an Algorithm6:02

A Seven Step Approach to Solving Programming Problems7:02

Познакомьтесь с преподавателями

Susan H. Rodger
Professor of the Practice
Computer Science
Robert Duvall
Lecturer
Computer Science
Owen Astrachan
Professor of the Practice
Computer Science
Andrew D. Hilton
Associate Professor of the Practice
Electrical and Computer Engineering

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

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play