Summing up Digits

Loading...

En provenance du cours de University of California San Diego

Mathematical Thinking in Computer Science

305 notes

University of California San Diego

Mathematical Thinking in Computer Science

305 notes

Cours 1 sur 5 dans 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.

À partir de la leçon

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

Rencontrer les enseignants

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

Consider the following problem.

Is it possible to place signs,

plus and minus, before numbers one, two,three and so on until nine

and some of the resulting numbers up in such a way that

as a result we obtain the sum 100?

The second question, can we obtain the sum two, as a result?

Let us start with 100.

Note that the sum of these numbers is maximal if we place signs, plus, everywhere.

Let us do it and see what is the resulting sum in this case.

Let us place the plus signs here and the result is 45.

We can do the calculations and see that it is 45.

So, this is the maximal possible number we can obtain.

So, if we place some other signs there the sum will be even smaller.

So, 45 is the maximum and we cannot obtain 100 as a result.

Let us now proceed to the second question.

Can we get two as the sum of these sequence?

Here is the place where we would need to consider

properties of the numbers to be odd and even.

Is it possible to get two?

And the main observation here is that in the sequence,

there are five even numbers and five odd numbers and as a result,

no matter how we place signs there,

the sum will always be odd.

Because the sum of two odd numbers is even,

the sum of an even and an odd number is odd and the sum of two even numbers is even.

So, if you sum up five even numbers and five odd numbers,

it can be seen easily that the result will be always odd not matter how we put

the signs here and so, the sum two is impossible.

Let us also consider the more general question.

What are the possible sums we can get here?

Can we list all possible sums we can obtain

by placing the signs in this sequence?

We have two constrains, two obstacles.

We have shown that the sum is always odd,

we cannot obtain an even number as a sum

and we have also shown that the sum is at most 45.

The maximum possible sum is 45.

Symmetrically, if we place all signs to be minus, we obtain minus 45.

These are the constraints that we have and it turns

out that this is all constraints that are present here.

So all other sums are possible.

If some numbers satisfy both of the restrictions we have found then it is

possible to obtain it to place the signs in the right way such that

the sum is equal to this number.

We will not discuss it in

details but you can try to do it yourself.

It is not very complicated and to do it, you can consider the following greedy algorithm.

Let us consider this sequence of numbers,

one, two, three and so on until nine and

let's go from right to left and let's place signs gradually.

You have your current goal number and you have your current sum.

Initially the current sum was zero and then you place some sign before the number,

you add it or subtract it from your current sum.

If your current sum is less than the goal, you increased your current sum,

you place the sign plus and if the current sum

is greater than the goal or equal to the goal, let us place the sign minus.

It turns out that

this greedy algorithm always gives you the right sequence of signs,

plus and minus, and it can be shown

using some other invariant that we have not considered for this problem yet,

so you can try to think about it yourself.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play