Advanced Signs Switching

Loading...

From the course by University of California San Diego

What is a Proof?

175 ratings

University of California San Diego

What is a Proof?

175 ratings

Course 1 of 5 in the Specialization Introduction 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.

From the lesson

Invariants

"There are things that never change". Apart from being just a philosophical statement, this phrase turns out to be an important idea that can actually help. In this module we will see how it can help in problem solving. Things that do not change are called invariants in mathematics. They form an important tool of proving with numerous applications, including estimating running time of programs and algorithms. We will get some intuition of what they are, see how they can look like, and get some practice in using them.

Even and Odd Numbers4:36

Summing up Digits4:36

Switching Signs3:19

Advanced Signs Switching8:30

Meet the Instructors

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

[SOUND] Let us consider now a more advanced illustration

of the previous program.

Again we are given a table of four by four.

Again, there are plus and minus signs on the table,

but now all four corners have minus signs, and

all other cells have plus signs.

Again, now we switched this position to all signs by switching signs in rows and

columns several times repeatedly.

Okay, let's consider this problem.

We can try to do it, and if we try to do it,

we will see that this problem looks way more tricky.

It still doesn't work somehow, if we try we will not succeed.

On the other hand, the previous argument doesn't work.

In the previous argument we use the number of minuses initially odd,

and then if we want it to be even, and it is in variance, so we can do it.

But here the number of minuses is also even in the beginning, so

we say it doesn't work.

So it doesn't forbid disrupting or

plus positions, so what can you do instead?

If you know already about residues modulo 4,

we will learn them later in the later courses.

You can try to use them, but they also doesn't help.

Still, if you try to use this variant it doesn't help.

Data satisfied in the end and data satisfied in the beginning.

So still yet, there is a very simple solution to this problem.

And if you don't know it, I suggest you to think bit more before we can server.

This way you will get more from this lesson, and besides that you enjoy

the solution more if you thought about problem in the beginning,

especially it applies to simple solutions.

So now I will proceed to the solution.

Okay so, we have this table and then here the solution is very simple.

Lets look at the smaller problem,

lets look at the small part of the current problem.

And that's a very basic and natural here, and

somehow it works very good in this situation.

More precisely let's do the following, let's consider a sub table of this

table at two by two corner to top left corner.

And let's observe the following, if you switch a column or row in the large table,

if we also switch a column or a row in the small table, or do nothing.

So if you switch one of the two top rows in this table,

then we switch a row in the small table as well, in the small sub table we consider.

If we switch one of the first two columns,

again, we switch columns in our small sub problem we are considering now,

we are ignoring everything else.

If we switch last two rows or last two columns,

we just do nothing with our small sub problem.

So if we can move in a large table,

we either make the same in a small table, or we do nothing in a small table.

So what does it mean?

It means that if we want to solve the large problem,

if we want to make all signs to be pluses in large problem, at the same time

we will make all signs to be pluses in the small sub problem we're considering.

And to apply exactly the same position we will switch rows and

columns in this small sub table.

Okay, but now this two by two problem is unsolvable by the old argument.

It has odd number of minuses.

And if we switch row and or a columns here, the number of minuses stay odd.

So we cannot solve the small problem.

And from it, we get that we cannot solve the large problem as well.

If we could solve the large problem,

we could have solved the small problem as well.

And this is impossible by our old argument.

Okay, now let's get a glimpse beyond what we are considering.

So we note that we have found a very powerful obstacle.

We note that if we are given such a table with pluses and

minuses, and for it to be possible to switch to all signs to pluses.

There should be even number of minuses in all two by two squares in this table.

And this is a very powerful obstacle.

For many tables, this is not satisfied and

then we can immediately say this stable is not possible

to switch all sides of the table to get pluses.

Okay, and it turns out that these are the only obstacles.

So we have found a lot of obstacles and they are very powerful,

and this is a complete set of obstacles.

That is if our table satisfies all these restrictions,

if for all two by two squares if a number of minuses is even,

then it is always possible to switch all signs to plus.

You can think about this problem yourself.

We will not discuss it, but you can think it about yourself.

It's not complicated on the same level of complexity.

I will give a hint on next slides, so if you would like to think about it yourself,

please stop now.

So I'm switching to the hint.

Let's consider a table, and let's assume that our invariant is satisfied.

So all 2 x 2 squares has even number of minuses.

And let's do the following, the first step, switch the first row and

the first column to all pluses.

This is always possible, it's not hard to do, so you can perform this.

So you can perform switches of rows and

columns in such a way that you obtain this position.

And you do not know what is in the blank cells.

And the second step, use this invariant to show that if you achieve this position,

then all the rest cells also contain pluses.

So now we're done with this problem and

let's summarize what we have learned on this week.

We have studied invariants and we observed it very important, and

they can help a lot in different problems in a wide range of problems.

And they can help to prove impossibility of something,

they can also prove to count something.

And also another important application is to show

the process terminates or even recontrol them in variance.

We can show bounds on the running time of some algorithms, and

this is important especially for computer science.

This is a very important application of invariance.

Invariance can take many forms.

It can be numbers.

It can be properties of the number to be even or odd.

It can be some equation.

It can be some of the commodity.

There are a lot of form of invariance.

The important thing is, if there's something that doesn't change or

changes in the right way.

So double counting can be viewed as a special case of an invariant.

And this is not all.

There are other forms of invariants we haven't discussed.

For example, the residues.

And we will discuss some of them in the future in the next courses.

[SOUND]

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play