Narrowing the Search

Loading...

Del curso dictado por University of California San Diego

Mathematical Thinking in Computer Science

406 calificaciones

University of California San Diego

Mathematical Thinking in Computer Science

406 calificaciones

Curso 1 de 5 en SpecializationIntroduction to Discrete Mathematics for Computer Science

Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In the course, we use a try-this-before-we-explain-everything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself. Prerequisites: 1. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.

De la lección

How to Find an Example?

How can we be certain that an object with certain requirements exist? One way to show this, is to go through all objects and check whether at least one of them meets the requirements. However, in many cases, the search space is enormous. A computer may help, but some reasoning that narrows the search space is important both for computer search and for "bare hands" work. In this module, we will learn various techniques for showing that an object exists and that an object is optimal among all other objects. As usual, we'll practice solving many interactive puzzles. We'll show also some computer programs that help us to construct an example.

Magic Squares3:26

Narrowing the Search6:47

Multiplicative Magic Squares5:16

More Puzzles9:21

Integer Linear Combinations5:15

Paths In a Graph4:35

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

Now, we learn how to narrow the search.

Actually there are many combinations,

but some clever tricks can condense,

delete most of them and restrict our search to some small set.

So, let's see how it's done.

We're looking for 3×3 magic square.

In fact, the truth is that they exist for all and starting from three,

three, four, five and so on.

It's not so easy to prove actually.But we are now interested only in 3×3 magic square,

and what is called brute force search this mean that we should check

all the possible positions of this nine numbers,

and actually we know how many of them we have.

If you don't know, you will know after the combinatorics course,

part of this our course.

But, there are nine possibilities for

the first cell and for each possibility for the first cell there are

eight possibility for the second one and so on.

And if you multiply all those number you get 300,000.

It's not much for a computer,

but still still for us it's completely impossible.

So, let's try to think how we can narrow the search.

The first observation is we can know in

advance what this... We know that the sum is in all the rows and columns are the same,

but what is the sum?

We can find it in a very easy way.

So we know that in all the square together we have 45,

and this 45 is made of three rows or of three columns.

So, each column should have sum one third of 45 so it's 15.

Why it's important?

Let me show you before going farther.

So, now, if for example,

we know what is here, then the rest is the term to include.

So, we can make a search only for all possibilities to fill this square.

And this is much smaller actually,

we have only nine, eight, seven, six.

So I think it's 120 times smaller.

Still it's a large number anyway,

so we need more tricks and this is one of the tricks which I showed too early.

And the trick is that we can predict what is in the center.

So look, we have sum up four lines.

This is the one line,

this is the second line,

third line and fourth line.

First we know that if we sum all these numbers along these lines,

we get four times the constant,

this s, which is the sum of each line and each diagonal.

So we have 4S. On the other hand,

we can see that everything is counted exactly once,

except for the center which is count for four lines,

it's count four times.

So the center, there is additional to 3×center.

So 4S is the total sum which we know is 3S and 3×center.

So the center is one third,

so this four and three,

so the difference is S. And the center is one third of the sum on every line.

In our case is five.

So, here is the equation and here is the solution in general,

and in our case it's five.

Good. So we know that we have five here.

And this is again,

our search space become smaller and smaller.

And the next step is to think where we should place one.

There is a minimal number one and it should be somewhere.

And there are essentially two possibilities,

either it's in the corner or it's in the middle of the side.

So, this is our question, corner or middle?

Now we should consider make a case analysis.

So let's imagine one is in the corner, what happens then?

Then we know that if this one is six,

we have nine here.

What do we know about other things?

So there is three lines which should have key 15.

This line, this line, and this line.

So this is 14.

So this should be 14 and this should be 14.

But then let's look how we can get 14.

14 is 5+9 is this one.

And there are other possibilities;

this for example, you can get 6+8.

You don't have number bigger than nine,

so the only thing you can decrease this nine and then you get six here.

And the next step is get 7+7,

but this is not possible because we cannot use 7 twice.

So actually there are only two ways to get 14; 5+9 and 6+8.

And we have three positions when the 14 is needed.

So we get a contradiction,

one cannot be in the corner.

This case is closed.

Okay. Then, it should be in the middle.

Let's put it in the middle for example,

in the bottom line.

Now, actually there is also symmetry,

like we can turn it over this line.

So we can assume for example,

then on this line we should have 14,

and this 14 we know that the only possibility is 8+6.

But the question is whether eight here and six here or vice versa.

But it's symmetric, so we consider one case.

Now everything is determined.

If we know we can compute all of the things.

So if we have 13,

we have 2 and in this lines 11,

4 and there is 12, 3 and 2+8+7.

And what is very important which can be predicted,

that we have correct sums everywhere, you can check this.

And also, all the numbers are different.

We can also check this easily by looking in the picture.

So, we are lucky and indeed we get a major square 3×3.

So we know that our existential statement with

the magic square of size 3×3 exists is proven,

we have an example it's enough.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play