Exponents

We'll start the course by talking about exponents. The definition we'll use is

$a^b = a \times a \times a \times ... \times a$ ($b$ times)

For instance, $2^4 = 2 \times 2 \times 2 \times 2 = 16$

In python, doing an exponential is quite simple; we just say a ** b. For instance

2**4

16

Now let's dive right into an application of exponents to computer science. We'll start by asking how many different binary strings (strings that only use 1's and 0's) there are with $N$ digits. For instance, there are 8 binary strings with 3 digits: $000, 001, 010, 011, 100, 101, 110, 111$. There's a very nice way to organize these into a binary tree structure to find a general formula. Let's have a look below for our example with $N = 3$:

We start with one node at the top of the tree, and then for every digit, we branch out both to the left (which we consider to be a 0) and to the right (which we consider to be a 1). Then, for each of those branches, we can continue to recursively branch in this way to get to the next digit. In this way, a binary string can be obtained by following some path down from the root of the tree to a leaf. For instance, the string 101 can be obtained by going RIGHT, LEFT, RIGHT. So we just have to count the number of leaves there are to count the number of unique binary numbers. We notice that the number of nodes doubles at each step we go down the tree, so the total number of nodes is $2 \times 2 \times ... \times 2$ N times, or simply $2^N$!

Subset Sum And Exponential Algorithms

Let's now look at a computational problem and an algorithm to solve it that takes "exponential time" as a function of the size of the input $N$.

The subset sum problem asks if we start with an array of numbers $X$ and a target number $T$, is it possible to pick some subset of numbers in $X$ that sum to $T$?

---

Ex) As an example, consider $X = [1, 5, 2, 6, 3, 1, 2]$ and $T = 7$. Then there are a few different ways to satisfy this problem. For instance, we can take

$X[1] + X[2] = 5 + 2 = 7$

$X[3] + X[5] = 6 + 1 = 7$

$X[0] + X[3] = 1 + 6 = 7$

$X[0] + X[2] + X[4] + X[5] = 1 + 2 + 3 + 1 = 7$

---

A brute force algorithm would try all possible subsets of numbers and check to see if they sum to the target. But how long will this algorithm take? To see this, we can come up with a binary string that corresponds to each possible subset. The table below shows how

	0	1	2	3	4	5	6
X[1]+X[2]	0	1	1	0	0	0	0
X[3]+X[5]	0	0	0	1	0	1	0
X[0]+X[3]	1	0	0	1	0	0	0
X[0] + X[2] + X[4] + X[5]	1	0	1	0	1	1	0

In other words, we put a $1$ in the $i^{\text{th}}$ place if the number at index $i$ is a part of the sum, and a $0$ otherwise. Since there is a one to one correspondence between binary digits and subsets, we see that there must be $2^N$ possible subsets, since we know there are $2^N$ possible binary strings with $N$ digits. Therefore, the naive algorithm has to loop through $2^N$ possibilities. We refer to such an algorithm as an exponential algorithm. But how bad is this really? To see this, let's plot $2^N$ as a function of $N$ for the first 20 integers

import numpy as np
import matplotlib.pyplot as plt

N = np.arange(1, 21)
plt.plot(N, 2**N)
plt.xticks(N);
plt.xlabel("N");
plt.ylabel("Number of binary strings with $N$ digits")

Text(0, 0.5, 'Number of binary strings with $N$ digits')

We can see that for $N = 20$, we have just over a million subsets to try

2**20

1048576

Moreover, this seems to be growing very quickly as $N$ gets bigger. But how quickly? Suppose, for example, that subset-sum takes a microsecond (1e-6 seconds) to run on 20 elements. Then how long will it take to run on 100 elements? Well, by our reasoning above, we'll have to multiply by 80 additional factors of 2

(1e-6)*(2**80)

1.208925819614629e+18

That's a lot of seconds! Let's convert it to years to get a better idea for how bad this is. There are 3600 seconds in an hour, 24 hours and a day, and generally 365 days in a year. So that brings us to

(1e-6)*(2**80)/(3600*24*365)

38334786263.782

Or nearly 40 billion years!! But 100 isn't that much larger than 20, which only took a microsecond. And herein lies the problem with exponential algorithms. Even though they may run alright on inputs of small size, they blow up in computation time very quickly. So we generally do not consider exponential time algorithms to be good enough in practice, because they start to degrade and become impractical very quickly with just the addition of a few inputs, even if they seem alright at first.

Interestingly, when the numbers are real (floating point) numbers, the naive algorithm that tries all possibilities is roughly the best we can do. But we'll see in the recursion unit a way to do this more efficiently if all of the numbers are integers, as in the above example