Generalizing Closest Point

Loading...

From the course by Duke University

Programming Fundamentals

168 оценки

Duke University

Programming Fundamentals

168 оценки

Course 1 of 4 in the Specialization Introduction to Programming in C

Programming is an increasingly important skill, whether you aspire to a career in software development, or in other fields. This course is the first in the specialization Introduction to Programming in C, but its lessons extend to any language you might want to learn. This is because programming is fundamentally about figuring out how to solve a class of problems and writing the algorithm, a clear set of steps to solve any problem in its class. This course will introduce you to a powerful problem-solving process—the Seven Steps—which you can use to solve any programming problem. In this course, you will learn how to develop an algorithm, then progress to reading code and understanding how programming concepts relate to algorithms.

From the lesson

Introduction

This module introduces a powerful process for solving any programming problem—the Seven Steps. You will learn how to approach a programming problem methodically, so you can formulate an algorithm that is specific and correct. You will work through examples with sequences of numbers and graphical patterns to develop the skill of algorithm development.

A Pattern of Squares4:46

Testing a Pattern of Squares2:21

Drawing a Rectangle4:07

Closest Point5:07

Generalizing Closest Point5:07

Meet the Instructors

Andrew D. Hilton
Assistant Professor of the Practice
Electrical and Computer Engineering
Genevieve M. Lipp
Adjunct Professor
Electrical and Computer Engineering/Mechanical Engineering
Anne Bracy
Senior Lecturer
Computer Science, Cornell University

In the previous video, we carefully wrote down the steps we followed in working

a specific case by hand.

In this video, we generalize the steps to finding the closest point.

Looking at our steps, some of them are similar, but

we need to make them match up.

Each of these colored boxes contain similar steps.

First a computation, then a comparison.

We also have some steps we only do sometimes, and

we need to figure out under what conditions we do them.

We also have some steps we only do at the start and the end, and

we're going to need to generalize the numbers in those.

So the first thing let's do is make these similar stuffs match up.

Why are computing 9 squared plus 6 squared here,

7 squared plus -1 squared next and so on.

If we look at our picture, the 9 comes from delta x and the 6 comes from delta y.

The difference between the point the point 10, 5 in set S and 1, -1, the point p.

The same is true for all of these other numbers, the differences in x and

y between points s and p.

So we might rewrite all of these steps to have the points S1,

S2, etc., up to S6.

We'll call the first point s0 when we get to the starting step.

Programmers often like to start counting from 0.

The first substitution gives us s1's x- P's x quantity squared + s1's

y- P's y quantity squared, then the square root of the whole thing.

Now, the result of this computation won't always be 10.82 or 7.07,

so we should give these a name, such as current distance.

But when we do this, we're going to have to keep track of

each time we use this number and update them, too.

That is if we change the first occurrence of 10.82 to currentDistance,

then we need to make this line compare current distance to 8.06.

But some of these numbers are used in other ways, so

these are going to need a different name.

Here, we've replaced the value for each computation with currentDistance.

Notice that the only times we update the best choice

are when current distance is smaller.

That means we must have been keeping track of the best distance so

far, which we now need to update, as well.

Now, we update the best distance when the current distance is smaller, and

we can use the value of best distance for comparison with future computations.

Let's look at the first 8.06 we compute and consider the other places it occurs.

The computation can be achieved like the others using S0.

Since this is our first computation, it might as well be the best so far,

then we can replace the other instance with bestDistance, making the steps match.

To continue generalizing, let's look at the point for

best choice 2,7,8,-2, and -3,-5.

Each of these is the particular point we're looking at so

we can replace those with S0, S2, and S4.

Recall that we only updated the best choice when the current distance

was smaller.

We can make each of these steps the same by including instructions to compare

current distance and best distance each time, but

only update best distance if current distance is smaller.

Now we do the same steps for each of the points.

Each colored box is the same as the others, except for

what point we're looking at, S1, S2, through S6.

That means we an express this as a repetition

where we count from 1 to the number of points in S exclusive.

We'll call each number that we count i,

and we'll compute the distance from the ieth point in S to P.

If current distance is smaller than best distance,

then we'll update best choice to SI and best distance to current distance.

We haven't changed our steps for the start or end, but

we should generalize the point we give as our answer.

The answer is not always going to be -3, -5.

Why did we say that?

The answer was the best choice when we finished counting, so in general,

we'll give an answer of best choice.

The only other thing we need to do is consider a corner case.

What if S has 0 points in it?

In that case, we give an answer of no answer exists.

This corner case was not revealed by the example we just worked, but

it would have come up through testing.

Working an example with 0 points,

we would have had a problem doing the first step of our computation.

So we report no answer exists and skip all of these other steps.

So here is our algorithm.

You can test it yourself.

Later on, we'll learn how to translate this into code.

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

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

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

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

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

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