Coin Problem

Loading...

From the course by University of California San Diego

What is a Proof?

171 оценки

University of California San Diego

What is a Proof?

171 оценки

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

Recursion and Induction

We'll discover two powerful methods of defining objects, proving concepts, and implementing programs — recursion and induction. These two methods are heavily used, in particular, in algorithms — for analysing correctness and running time of algorithms as well as for implementing efficient solutions. You will see that induction is as simple as falling dominos, but allows to make convincing arguments for arbitrarily large and complex problems by decomposing them and moving step by step. You will learn how famous Gauss unexpectedly solved his teacher's problem intended to keep him busy the whole lesson in just two minutes, and in the end you will be able to prove his formula using induction. You will be able to generalize scary arithmetic exercises and then solve them easily using induction.

Coin Problem4:45

Hanoi Towers7:25

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, consider the following coin problem.

So our goal is to prove that any integer amount starting from 8 can

be paid using coins of denominations 3 and 5.

Okay?

So this is our problem, and let's try to investigate.

So first of all, let's check whether 8 and 9 and 10 and 11 can be indeed paid.

So this looks reasonable because 8 is 3 + 5,

9 is 3 + 3 + 3, 10 is 5 + 5,

11 is 3 + 3 + 5, so it seems to be possible.

However, it is still not at all clear whether it is possible for all values.

It is also not at all clear

why are we talking about this problem in the lesson called recursion.

Because recursion was about programs or about definitions.

At the same time, what we are going to do

is to prove that this is possible using recursion.

And in fact, we are going to implement the program that is going

to change any such amount into coins of denominations 3 and 5.

So for this, as usual, let's think about these problems.

So we know already that we can pay 8.

But this immediately that we can also pay 11, right?

Because 11 is just 8 + 3.

So in a sense, we reduce the problem of change in 11

into coins to the problem of changing 8 into coins.

But for 8, we that this is possible which means that for 8, for 11,

it is also possible.

Moreover, if you know how to change 8 then by adding just one single coin,

you had a change for 11, right?

And also 11 in terms, gives 14 then 17 then 20 and then so on.

So an infinite number of amounts can be changed into points 3 and

5 just because 8 can be changed into 3 and 5, right?

Then we would do the same trick with 9.

So it seems we know how to change 9 then we know how to change 12,

15, 21 and so on.

And 10 gives us 13, 16, 19, 22 and so on.

Right?

So this gives us the possibility to implement the following

recursive procedure.

We call the change, and it is given an amount that we need to change.

And the first thing to do,

we check whether the given amount is indeed greater than 8, right?

Then if it is equal to 8 then we just return the representation of 8,

the sum of 3 and 5.

So we just return a list of two points.

If it is equal to 9, we return three coins, 3, 3 and 3.

If it is equal to 10, we return two coins, 5 and 5.

On the other hand, if it is greater, then we do the following.

We first subtract 3 from the amount.

Then we make a recursive call which returns us the set of

points needed to change the amount- 3, right?

So we make a recursive call.

We solve the same permutational problem.

So with this point, we have some subset of coins,

some list of coins that sum up to amount- 3.

So if we add just one single coin with denomination 3

then we have a change for the whole amount, right?

And this is exactly what we do here.

We append 3 to coins, and we return the result in.

Okay, so this is a recursive program, which changes any amount.

And the fact that it changes any amount is guaranteed by the fact that if you get any

number, which is greater than 8.

And you start and you keep subtracting 3 from it,

then at some point, you will reach either 8 or 9 or 10, right?

So for this reason, this algorithm actually proves, this problem proves

that any amount can be changed using coins with denominations 3 and 5.

And it actually proves this constructively.

Meaning that it not only proves that it is possible,

it actually produces the answer for each possible amount.

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

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

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

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

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

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