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.

从本节课中

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.