Classify a Permutation as Even/Odd

Loading...

From the course by University of California San Diego

Mathematical Thinking in Computer Science

201 оценки

University of California San Diego

Mathematical Thinking in Computer Science

201 оценки

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

Solving a 15-Puzzle

In this module, we consider a well known 15-puzzle where one needs to restore order among 15 square pieces in a square box. It turns out that the behavior of this puzzle is determined by mathematics: it is solvable if and only if the corresponding permutation is even. We will learn the basic properties of even and odd permutations. The task is to write a program that determines whether a permutation is even or odd. There is also a more difficult bonus task: to write a program that actually computes a solution (sequence of moves) for a given position assuming that this position is solvable.

The Rules of 15-Puzzle3:10

Permutations9:07

Proof: The Difficult Part8:38

Mission Impossible2:27

Classify a Permutation as Even/Odd5:11

Bonus Track: Fast Classification1:54

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

Now we come to a programming assignment,

which is just to classify a given permutation.

So, how it looks on the programmer's viewpoint.

Permutation can be instead of letters,

it's easier to deal with numbers.

So immediately, we have n numbers--1, 2, 3,

4, n--and they are in some array in arbitrary order. They are permuted.

And the question is whether this permutation's even or

odd and you should try in 0 and 1 for example.

Zero is an even number so it's more neutral to use

even permutations. How will you do this?

One of the possible approaches,

not actually the most effective one,

but still easy and rather effective.

Probably you have taken a programming course,

and maybe you have seen

a problem when the permutation was obtained by a sequence of transposition.

Do you remember something like this?

Sorting is the answer.

So when you want to sort an array,

initially the array is in some random order and we need to bring it to the normal order,

and many sorting algorithm use permutation for that.

Not all, there are some more advanced algorithm like node-sort

or whatever but many of them use transpositions,

exchanges, where at each step you exchange two elements of the array.

If the sorting algorithm use exchanges,

it can be used to find better permutations algorithm,

just count the number exchanges to see whether it's odd or even.

And we even have a piece of code.

But let me tell you that there is an intentional error.

So you should be careful to understand

where the error is but let me explain what has happening.

So this is the array given to us.

We want to sort it,

and this is an additional variable which is not in the original sorting algorithm.

It's just a number of those position with 0 or 1.

It flips back and forth.

So that is a simple algorithm of sorting.

We put first elements in the right place from left to right.

So we put first the minimal element in the first place,

and the second element on the second place and so on.

So here's how you write this algorithm.

So there some variable S,

which counts how many elements are at the right place,

and usually there are none of them.

And at the end,

we want to have n elements.

So while S is less than n we continue doing things.

So we can even show S elements are already okay.

And this is the rest.

So you start with S + 1,

you put u here and also t here.

And now a of t is minimal element among the rest- not among the rest,

but among this part between s + 1 and u because it's only one element.

And then the idea is you move u, you increase u,

and always you keep a of t minimal among this element.

So you increase u,

and there is a new element.

The last one, which is not checked.

And if this last one is smaller than the current minimum,

then we need to move the current minimum in a different place.

And after u is equal to n,

here u is equal to n,

so a of t is minimal among all the rest.

And then, what remains to do is to exchange this minimal element somewhere.

Here is the minimal element t and you exchange it with

u and get one more element in the right place.

Here is additional operation.

We keep track of whether we'll making even or odd number of exchanges.

So it looks very convincing but do you see the error? There isn't.

Now, maybe there are some unintentional error but there is

one intentional error in this program.

Can you see it?

Okay, you can try it for some examples and then you will see the problem.

Actually, you will see that the answer doesn't depend on the error for some reason.

And then you can think what is the reason and how to correct the thing.

What is wrong with this code?

You should find and you should find out how to correct it.

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

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

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

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

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

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