Runs this cell first!

In [ ]:

```
%config InteractiveShell.ast_node_interactivity="none"
def f(globals, locals):
import base64
code="ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ=="
exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f
def check(fn, *input, expected):
result = fn(*input)
if expected != result:
print(
f"{fn.__name__}({", ".join(input)}) should be {expected}, not {result}.")
else:
print(f"Test case passed!")
```

Imagine you are the boss who runs the `JamCoders Premier League`

. You have the following teams competing for the top prize in the league: "Manchester United", "Arsenal", "Chelsea", "Liverpool", "Manchester City", "Tottenham Hotspur", "Everton".

The clubs have the following points in the league:

Club Name | Points |
---|---|

Manchester United | 66 |

Arsenal | 67 |

Chelsea | 71 |

Liverpool | 94 |

Manchester City | 95 |

Tottenham Hotspur | 70 |

Everton | 53 |

Create a list called `club_points_list`

that contains 5 integers.

In [ ]:

```
# Write your solution here
```

Print every element in that list (`club_points_list`

) using a `for`

loop.

In [ ]:

```
#Write your answer here
```

The function `minimum(L)`

finds the minimum element in a list `L`

:

```
def minimum(L):
min_so_far = L[0]
for element in L:
if element < min_so_far :
min_so_far = element
return min_so_far
```

Write a non recursive function `maximum(L)`

that takes a list of integers `L`

and returns the largest integer in that list.

In [ ]:

```
def maximum(L):
#Write your solution here
return
```

In [ ]:

```
# TEST_CASE
L = [23, 45, 56, 88, 19, 10]
check(maximum(L), 88)
L = [0, 12, 44, 5, 6, 7]
check(maximum(L), 44)
```

Let's write a **recursive** function `recursive_max(L)`

that takes a list of integers `L`

and returns the largest integer in that list.

In [ ]:

```
def recursive_max(L):
# Write your solution here
return
```

In [ ]:

```
# TEST_CASE
L = [23, 45, 56, 88, 19, 10]
check(recursive_max(L), 88)
L = [0, 12, 44, 5, 6, 7]
check(recursive_max(L), 44)
```

Logarithms are the opposite (inverse) of exponents. For any two numbers $a > 0$ and $z$, the $a$-ary logarithm of $z$ is a number such that $$a^x = z.$$ Just like with exponents, we have mathematical notation to denote the logarithm: $x=\log_{a}(z)$.

Some examples:

- Since $2^{5} = 32$ then $\log_2(32) = 5$.
- Since $2^{0} = 1$ then $\log_2(1) = 0$. Actually, for any number $a \neq 0$ it holds that $\log_a(1) = 0$...

As you may remember, there are some nice tricks (sometimes called rules) for working with expressions involving exponents. Specifically, for any three numbers $x, y$

- $$a^x \cdot a^y = a^{x + y}$$
- $${\left(a^x\right)}^y = a^{x \cdot y}$$

(If you haven't seen these before, try to convince yourself of why they are true. You can try out some small examples, such as $2^3 \cdot 2^2 = 2^5$; write down the exponents as repeated multiplication.)

Because logarithm is an opposite (inverse) of exponent, each of the rules above have a corresponding rule for working with logarithms.

- $$ \log_a(x \cdot y) = \log_a(x) + \log_a(y)$$
- $$ \log_a(x^y) = y \cdot \log_a(x)$$

It's not terribly important that we remeber all these rules now. But it's nice to think about them as a way to get comfortable with logarithms. Can you convince yourself of the two logarithm rules based on the corresponding exponent rule?

In [ ]:

```
# Optional: Your thoughts here.
```

The **integer (binary) logarithm** of a number $x$ is the smallest integer $y$ such that $$2^{y+1} > x.$$

It's just like the logarithm, except rounded down to the nearest integer.

Write a function the computes the integer (binary) logarithm.

(Hint: You can refer back to the code for the **integer square root** function `isqrt()`

in day 5 lecture 12.)

In [ ]:

```
def ilog_binary(x):
"""Finds the smallest integer y for which 2 ** (y+1) > x.
Arguments: x (int)
Returns: (int)
"""
# Your code here
```

Out[ ]:

In [ ]:

```
check(ilog_binary, 2, 1)
check(ilog_binary, 1, 0)
check(ilog_binary, 4, 2)
check(ilog_binary, 8, 3)
check(ilog_binary, 10, 3)
check(ilog_binary, 100, )
```

The reason why we called our function the **binary** integer logarithm is because it works for **base 2**; the base is the base of the exponent in the condition $\mathbf{2}^{y+1} > x$ (notice the bold 2).

But we can define the logarithm for *any* base. For example, the *decimal* integer logarithm of $x$ is the smallest integer $y$ such that $10^{y+1} > x$.

In general, for any positive integer $a$, the **$a$-ary** integer logairithm of $x$ is the smallest integer $y$ such that $$a^{y+1} > x.$$

Next, we'll define this function.

In [ ]:

```
def ilog(x, a):
"""Finds the smallest integer y for which a ** (y+1) > x.
Arguments: x (int), a (positive integer)
Returns: (int)
"""
# Your code here
check(ilog, 2, 2, 1)
check(ilog, 1, 2, 0)
check(ilog, 4, 2, 2)
check(ilog, 8, 2, 3)
check(ilog, 10, 2, 3)
check(ilog, 100, 2, 6)
check(ilog, 10, 10, 1)
check(ilog, 1, 10, 0)
check(ilog, 9, 10 , 0)
check(ilog, 100, 10, 2)
check(ilog, 215, 10, 2)
check(ilog, 3, 3, 1)
check(ilog, 4, 3, 1)
check(ilog, 9, 3, 2)
check(ilog, 10, 3, 2)
```

Let us introduce a "very fun" game called *Guess The Number*. There are two players: the *Host* and the *Seeker*. The game goes as follows:

- The Host chooses a range of integers $[a,b]$ and a target integer $x$ in that range.
- The Host tells the Seeker about the range $[a,b]$. The Seeker's goal is to find $x$.
- In each turn, the Seeker chooses a number $y$. If $y = x$, the Seeker wins and the game is over. Else, the the Host tells the seeker whether $y$ is greater than $x$ or less than $x$.

Try playing the game by running the code below using different inputs.

In [ ]:

```
def seek(x, a, b):
"""Plays Guess The Number.
Arguments: x (int), a (int), b (int)
Returns: The number of rounds played (int).
Effects: Prints dialogue between the Host and the Seeker.
"""
if x > b or x < a:
print("Invalid number!")
return -1
mid = (a + b) // 2
print("Seeker: I choose", mid)
if mid == x:
print("Host: Exactly!")
return 1
if mid > x:
print("Host: Too big!")
return 1 + seek(x, a, mid-1)
if mid < x:
print("Host: Too small!")
return 1 + seek(x, mid+1, b)
```

Let's play!

In [ ]:

```
x, a, b = 56, 1, 100
print(f"Host: Let's play! The range is [{a}, {b}].")
print(f"Seeker wins in {seek(x, a, b)} rounds.")
```

What are the **left** and **right** values for each of the 4 guesses made in `guess(56,1,100)`

?

In [ ]:

```
# Your answer here
```

That was so fun! Let's play again!

In [ ]:

```
x, a, b = 1, 1, 100
print(f"Host: Let's play! The range is [{a}, {b}].")
print(f"Seeker wins in {seek(x, a, b)} rounds.")
```

What are the **left** and **right** values for each of the guesses made in `guess(1,1,100)`

?

In [ ]:

```
# Your answer here
```

Here is an implementation of binary search using a `while`

loop. Run this cell before continuing:

In [ ]:

```
def binarySearch(lst, x):
"""Finds x in a sorted list lst.
Arguments: lst (list of ints), x (int)
Returns: index of x in lst (int)
Effects: Prints the number of iterations taken to find x.
"""
cnt = 0
left = 0
right = len(a) - 1
while left <= right:
# print(f"left={left}, right={right}") # Question 3.2
cnt += 1
mid = (left+right)//2
# print(f"Looking at {lst[mid]}") # Question 3.1
if lst[mid] == x:
break
if lst[mid] > x:
right = mid - 1
else:
left = mid + 1
print("Number of iterations:", cnt)
return mid
binarySearch([1, 2, 4, 6, 7, 10], 4)
```

What values of the array are looked at when searching for `10`

in the list `[âˆ’1,3,6,10,15]`

? You may uncomment a line in the above code to see if you are right (just be sure to re-run that cell).

In [ ]:

```
# Your answer here
```

In [ ]:

```
binarySearch([âˆ’1, 3, 6, 10, 15], 10) # If you would like to check your answer.
```

What values do `left`

and `right`

take when searching for `5`

in the list `[-1, 0, 1, 3, 5, 7]`

? You may uncomment a line in the above code to see if you are right (just be sure to re-run that cell).

In [ ]:

```
# Your answer here
```

What will happen if we run `binarySearch([1, 9, 8, -1, 4, 11], 4)`

? Why does this not work? How would you fix it?

`isqrt()`

-- bigger, better, faster, binary-search-ier!¶The integer square root of $x$ is the smallest integer $y$ such that $$ (y+1)^2 > x.$$

Here is an implementation of the integer square root function, similar to the one we saw in week 1.

In [ ]:

```
def isqrt(x):
"""Computes the smallest integer y such that (y + 1) ** 2 > x.
Arguments: x (int)
Returns: (int)
"""
for y in range(x):
if (y + 1) ** 2 > x:
return y
```

Let's try to use our function to find the square root of a big number. Run the following cell.

In [ ]:

```
big_number = 14472334024676221 # 14,472,334,024,676,221
# isqrt(4)
isqrt(big_number)
```

While the cell is running, take a moment to reflect on this poem by Dick King-Smith:

Patience is a virtue,

Virtue is a grace.

Grace is a little girl

Who would not wash her face.

Whew, that was pretty awful! Luckily, we can speed things up using *binary search*.

You can think of computing the integer square root of $x$ as a search problem on the array $[0, 1, 2, ..., x]$. Our old implementation of `isqrt()`

is doing *linear search*. However, since this array is sorted, we know that we can use binary search!

Wait a minute... Usually, we're used to using binary search to find a given (already-known) number; for example, find the index of $71$ in the array $[-3, 21, 35, 71, 101]$. But we don't know what the integer square root is yet! So we'll do things a bit differently.

Here is the pseudo-code for `fast_isqrt(x)`

:

- Initialize variables
`low = 0`

and`high = x`

. - While
`low + 1 < high`

: - Let
`mid = (low + high) // 2`

. - If
`(mid + 1) ** 2 <= x`

:- Set
`low = mid`

.

- Set
- Else:
- Set
`high = mid`

.

- Set
- Return
`low`

.

In [ ]:

```
def fast_isqrt(x):
"""Computes the smallest integer y such that (y + 1) ** 2 > x.
Arguments: x (int)
Returns: (int)
"""
# Your code here
```

Now let's try again.

In [ ]:

```
fast_isqrt(big_number)
```

Much better! Let's celebrate with a tiny poem for our tiny runtime; this one is by Ogden Nash, and is title *Fleas*.

Adam

Had'em

Use binary-search to speed up our implementation of `ilog(x, a)`

. Here is the pseudo-code.

- Initialize variables
`low = 0`

and`high = x`

. - While
`low + 1 < high`

: - Let
`mid = (low + high) // 2`

. - If
`2 ** (mid + 1) <= x`

:- Set
`low = mid`

.

- Set
- Else:
- Set
`high = mid`

.

- Set
- Return
`low`

.

In [ ]:

```
def fast_ilog_binary(x):
"""Finds the smallest integer y for which 2 ** (y+1) > x.
Arguments: x (int), a (positive integer)
Returns: (int)
"""
```

In [ ]:

```
check(fast_ilog_binary, 2, 2, 1)
check(fast_ilog_binary, 1, 2, 0)
check(fast_ilog_binary, 4, 2, 2)
check(fast_ilog_binary, 8, 2, 3)
check(fast_ilog_binary, 10, 2, 3)
check(fast_ilog_binary, 100, 2, 6)
```

So you have a faster implementation of the binary integer logarithm. Fantastic! But does it matter? That is, can you find a number $x$ for which `ilog_binary(x)`

takes a while (say, 30 seconds) to run, but `fast_ilog_binary(x)`

is quick (say, under 1 second)?

In [ ]:

```
big_number = # Choose a big number
%timeit -r1 -n1 ilog_binary(big_number)
%timeit -r1 -n1 fast_ilog_binary(big_number)
```

If you're punching in big numbers, then you'll probably notice that `ilog_binary()`

(not the fast version) returns in under one second even for very large inputs.

Why do you think that is? Hint / answer: the number of iterations in `ilog_binary()`

is proportional to the *output*. For example, since `ilog_binary(2 ** 265)`

outputs `265`

, then only $\log_2(2^{265}) = 265$ iterations will be run in the function -- despite the fact that $2^{265}$ is more than the number of atoms in the universe!

Since the output is the integer logarithm of the input, we see that the logarithm of even really big numbers is still very small!

In [ ]:

```
# Your thoughts here
```