Explore
For Enterprise
Join for Free
Log In

Parcourir
Rechercher
For Enterprise
Connexion
Inscrivez-vous gratuitement

Summing up Digits

Loading...

Mathematical Thinking in Computer Science

Université de Californie à San Diego

4.5 (641 évaluations) | 34K étudiants inscrits

Cours 1 de 5 dans Introduction to Discrete Mathematics for Computer Science Spécialisation

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

Visualiser le programme de cours

Compétences que vous apprendrez

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

Avis

4.5 (641 évaluations)

5 stars
420 ratings
4 stars
145 ratings
3 stars
52 ratings
2 stars
11 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!

À 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

Enseigné par

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

Transcription

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.

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

Disponible sur Google Play

Coursera
À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government
Pour le campus

Communauté
Learners
Partners
Developers
Beta Testers
Translators

Se connecter
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Blog Tech

Plus
Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales