Maths ( especially discrete mathematics ) and computer science go very much hand in hand.
Though it is possible for you to be a decent programmer without acing mathematics, having a sound knowledge of discrete mathematics can be a great facilitator when it comes to learning new algorithms.
Teaching everything that discrete mathematics has to offer is well beyond the scope of this course and the technical interviews. So, for now, we will stick to learning some of the most used mathematics concepts.
This is another very important concept in computer science. Particularly because of how data is represented within machines.
Taking up bit arithmetic as a topic separately, let us initiate with understanding what those terms even mean.
In our customary base-ten system, we have digits for the numbers zero through nine. We do not have a single-digit numeral for “ten”. Yes, we write “10”, but its two digits; we have no single solitary digit that stands for “ten”.
There are 10 digits using which we represent all the numbers. Hence the base 10 system.
Similarily, binary number system or base 2 number system has only 2 digits
0, 1. Hex number system or
base 16 number system has 16 digits (
0, 1, 2 .. 9, A, B, .. F ). In general a N base number system has N digits,
0, 1, ... N-1 ( The digits usually after 9 are represented as A, B and so on ).
Base systems like binary and hexadecimal seem a bit strange at first. The key is understanding how different systems “tick over” like an odometer when they are full.
Base 10, our decimal system, “ticks over” when it gets 10 items, creating a new digit. We wait 60 seconds before “ticking over” to a new minute. Hexadecimal and binary are similar, but tick over every 16 and 2 items, respectively.
In computers, numbers are internally represented in binary number system.
We explore more in next slides.
Way back in the day, we didn’t have base systems! It was uphill both ways, through the snow and blazing heat. When you wanted to count one, you’d write:
When you wanted 5, you’d write
And clearly, 1 + 5 = 6
| + ||||| = ||||||
This is the simplest way of counting.
The value of any number = number of
Unary, where we just write
1, 11, 111… just goes on forever. Binary, with two options (1 and 0) looks like this:
1: 1 2: 10 (we’re full – tick over) 3: 11 4: 100 (we’re full again – tick over) 5: 101 6: 110 7: 111 8: 1000 (tick over again)
and so on …
Now, how do we convert an arbitrary binary number to its decimal equivalent? Obviously counting and matching is not an option.
Let us first look at the value of
10000...n times (
1 followed by n 0s ):
This number will only come after we have tried all possible n digit numbers in the binary system which has:
2 * 2 * 2 * .. n times possibilities ( every position can either have 0 or 1 ) = 2^n possibility which covers numbers from 0 to 2^n - 1.
So, the value of 1000..n times = 2n.
Now any number like
1010110 can be expressed as
1000000 + 10000 + 100 + 10 = 2^6 + 2^4 + 2^2 + 2^1.
Hence, if the binary representation is
An An-1 An-2 ... A1 A0, then the corresponding value is
A0 * 2^0 + A1 * 2^1 + A2 * 2^2 + .... + An * 2^n
Now look at the reverse process. Which is given a decimal number N, how do we convert it to binary.
To do this conversion, we need to divide repeatedly by 2, keeping track of the remainders as we go. Watch below:
Let us say our number is 357.
Thus the number converts to 101100101
Walkthrough Example :
A base N number system has N digits. The process of conversion of N based number to decimal and vice versa is very similar to the binary number system process we just saw.
The only thing that changes is that 2 is replaced by N.
So, if the N based number system representation is
An An-1 ... A2 A1 A0, then the corresponding decimal value is
A0 * N^0 + A1 * N^1 + A2 * N^2 + ...
The reverse process is also exactly similar. We keep dividing by N, keeping track of the remainders as we go.
Let us say our number is
N = 7.
1 R0 --------- 7 | 7 R2 --------- 7 | 51 R0 --------- 7 | 357
Thus the number converts to
1020 in base 7.
|Grid Unique Paths||375||