Explore
For Enterprise
Join for Free
Log In

Обзор
Поиск
Для организаций
Войти
Присоединиться бесплатно

Classify a Permutation as Even/Odd

Loading...

Mathematical Thinking in Computer Science

Калифорнийский университет в Сан-Диего

4.5 (оценок: 652) | Зарегистрировано учащихся: 35K

Курс 1 из 5 — 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. Do you have technical problems? Write to us: coursera@hse.ru

Просмотреть программу курса

Получаемые навыки

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

Рецензии

4.5 (оценок: 652)

5 stars
427 ratings
4 stars
148 ratings
3 stars
52 ratings
2 stars
12 ratings
1 star
13 ratings

KL

Nov 29, 2018

The course is excellent and most stuff is being taught in a nicely presented way. The main disappointment is 15-puzzle, because it's too difficult to understand without proper material.

DG

Jun 30, 2018

Love the quality of thought that goes into each lesson. The professors speak with acute clarity and really demonstrate and empathy for the student to truly understand the topics!

Из урока

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

Преподаватели

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Vladimir Podolskii
Associate Professor

Текст видео

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

О проекте
Руководство
Карьера
Каталог
Сертификаты
Сертификаты MasterTrack™
Степени
Для организаций
Для правительственных организаций
Для стационара

Сообщество

Учащиеся
Партнеры
Разработчики
Бета-тестировщики
Переводчики
Блог
Технический блог

Еще

Условия
Конфиденциальность
Помощь
Доступность
Пресса
Контакты
Справочник
Филиалы

Учитесь, где угодно

Подпишитесь на нас

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