If you are studying for an exam, or you just want some extra practice with concepts in this class, you might find these practice problems helpful!

## Easy

### Question 1: Fix the Bug

The following snippet of code doesn't work! Figure out what is wrong and fix the bugs.

``````def compare(a, b):
""" Compares if a and b are equal.

>>> compare(4, 2)
'not equal'
>>> compare(4, 4)
'equal'
"""
if a = b:
return 'equal'
return 'not equal'``````

The line `a = b` will cause a `SyntaxError`. Instead, it should be

``if a == b:``

### Question 2: Last square

Implement the function `last_square`, which takes as input a positive integer and returns the largest perfect square less than its argument. A perfect square is any integer multiplied by itself:

Hint: If you're stuck, try writing a function that prints out the first 5 perfect squares using a `while` statement: 1, 4, 9, 16, 25. Then, adapt that `while` statement to this question by changing the header.

``````def last_square(x):
"""Return the largest perfect square less than X, where X>0.

>>> last_square(10)
9
>>> last_square(39)
36
>>> last_square(100)
81
>>> result = last_square(2) # Return, don't print
>>> result
1

>>> cases = [(1, 0), (2, 1), (3, 1), (4, 1), (5, 4), (6, 4),
...          (10, 9), (17, 16), (26, 25), (36, 25), (46, 36)]
>>> [last_square(s) == t for s, t in cases].count(False)
0

"""
k = 0
while k * k < x:
k = k + 1
return (k-1) * (k-1)``````

We iterate over perfect squares until we find the first one larger or equal to the input. The answer is then the square before that one. This solution is inefficient, but an efficient solution requires taking a square root.

### Question 3

An open interval is a range of numbers that does not include its end points. For example, (10, 15) stands for all numbers that are strictly greater than 10 and strictly less than 15. Two intervals overlap if they contain any points in common. For example (10, 15) overlaps (14, 16), but not (1, 5) or (15, 16). The intervals (10, 10) or (10, 9) contain no numbers, since nothing is both greater than and less than 10, or greater than 10 and less than 9. Implement the function `overlaps` to take four numbers as arguments, representing the bounds of two intervals, and return `True` if the intervals overlap and `False` otherwise.

``````def overlaps(low0, high0, low1, high1):
"""Return whether the open intervals (LOW0, HIGH0) and (LOW1, HIGH1)
overlap.

>>> overlaps(10, 15, 14, 16)
True
>>> overlaps(10, 15, 1, 5)
False
>>> overlaps(10, 10, 9, 11)
False
>>> result = overlaps(1, 5, 0, 3)  # Return, don't print
>>> result
True

>>> [overlaps(a0, b0, a1, b1) for a0, b0, a1, b1 in
...       ( (1, 4, 2, 3), (1, 4, 0, 2), (1, 4, 3, 5), (0.1, 0.4, 0.2, 0.3),
...         (2, 3, 1, 4), (0, 2, 1, 4), (3, 5, 1, 4) )].count(False)
0
>>> [overlaps(a0, b0, a1, b1) for a0, b0, a1, b1 in
...       ( (1, 4, -1, 0), (1, 4, 5, 6), (1, 4, 4, 5), (1, 4, 0, 1),
...         (-1, 0, 1, 4), (5, 6, 1, 4), (4, 5, 1, 4), (0, 1, 1, 4),
...         (5, 5, 3, 6), (5, 3, 4, 6), (5, 5, 5, 5),
...         (3, 6, 5, 5), (4, 6, 5, 3), (0.3, 0.6, 0.5, 0.5) )].count(True)
0
"""
return low1 < min(high0, high1) > low0``````

There are many solutions to this problem. One way to look at it is to consider conditions under which the intervals don't overlap. Clearly for two non-empty not to overlap, one has to come entirely before the other. This becomes `high1 <= low0 or high0 <= low1`, which when negated is `high1 > low0 and high1 > low1`. In addition, both lower bounds must be less than their respective upper bounds (or the intervals are empty). The solution given combines these observations.

### Question 4: Triangular numbers

The nth triangular number is defined as the sum of all integers from 1 to n, i.e.

``1 + 2 + ... + n``

The closed-form formula for the nth triangular number is

``(n + 1) * n / 2``

Define `triangular_sum`, which takes an integer `n` and returns the sum of the first `n` triangular numbers, while printing each of the triangular numbers between 1 and the `n`th triangular number.

``````def triangular_sum(n):
"""
>>> t_sum = triangular_sum(5):
1
3
6
10
15
>>> t_sum
35
"""
count = 1
t_sum = 0
while count <= n:
t_number = count * (count + 1) // 2
print(t_number)
t_sum += t_number
count += 1
return t_sum``````

## Medium

### Question 5: Same hailstone

Implement `same_hailstone`, which returns whether positive integer arguments `a` and `b` are part of the same hailstone sequence. A hailstone sequence is defined in Homework 1 as the following:

1. Pick a positive integer `n` as the start.
2. If `n` is even, divide it by 2.
3. If `n` is odd, multiply it by 3 and add 1.
4. Continue this process until `n` is 1.
``````def same_hailstone(a, b):
"""Return whether a and b are both members of the same hailstone
sequence.

>>> same_hailstone(10, 16) # 10, 5, 16, 8, 4, 2, 1
True
>>> same_hailstone(16, 10) # order doesn't matter
True
>>> result = same_hailstone(3, 19) # return, don't print
>>> result
False

Extra tests:

>>> same_hailstone(19, 3)
False
>>> same_hailstone(4858, 61)
True
>>> same_hailstone(7, 6)
False
"""
return in_hailstone(a, b) or in_hailstone(b, a)

def in_hailstone(a, b):
"""Return whether b is in hailstone sequence of a."""
while a > 1:
if a == b:
return True
elif a % 2 == 0:
a = a // 2
else:
a = a * 3 + 1
return False``````

### Question 6

Implement the function `nearest_two`, which takes as input a positive number `x` and returns the power of two (..., 1/8, 1/4, 1/2, 1, 2, 4, 8, ...) that is nearest to `x`. If `x` is exactly between two powers of two, return the larger.

You may change the starter implementation if you wish.

``````def nearest_two(x):
"""Return the power of two that is nearest to x.

>>> nearest_two(8)    # 2 * 2 * 2 is 8
8.0
>>> nearest_two(11.5) # 11.5 is closer to 8 than 16
8.0
>>> nearest_two(14)   # 14 is closer to 16 than 8
16.0
>>> nearest_two(2015)
2048.0
>>> nearest_two(.1)
0.125
>>> nearest_two(0.75) # Tie between 1/2 and 1
1.0
>>> nearest_two(1.5)  # Tie between 1 and 2
2.0

>>> nearest_two(3)
4.0
>>> nearest_two(.01)
0.0078125
"""
power_of_two = 1.0
if x < 1:
factor = 0.5
else:
factor = 2
while abs(power_of_two * factor - x) < abs(power_of_two - x):
power_of_two = power_of_two * factor
if abs(power_of_two * 2 - x) == abs(power_of_two - x):
power_of_two = power_of_two * 2    return power_of_two``````

This implementation repeatedly doubles or halves the number `power_of_two` until reaching the closest number to `x`. The last three lines enforce the tie-breaking policy when `x` is exactly betweeen two powers of two.

### Question 7

Complete the implementation of `pi_fraction`, which takes a positive number `gap` and prints the fraction that is no more than `gap` away from `pi` and has the smallest possible positive integer denominator. See the doctests for the format of the printed output.

Hint: If you want to find the nearest integer to a number, use the built-in `round` function. It's possible to solve this problem without using `round`.

You may change the starter implementation if you wish.

``````from math import pi

def pi_fraction(gap):
"""Print the fraction within gap of pi that has the smallest denominator.

>>> pi_fraction(0.01)
22 / 7 = 3.142857142857143
>>> pi_fraction(1)
3 / 1 = 3.0
>>> pi_fraction(1/8)
13 / 4 = 3.25
>>> pi_fraction(1e-6)
355 / 113 = 3.1415929203539825

>>> pi_fraction(1e-3)
201 / 64 = 3.140625
>>> pi_fraction(1/32)
19 / 6 = 3.1666666666666665
"""
numerator, denominator = 3, 1
This implementation repeatedly increases `denominator` until the nearest fraction to `pi` is within `gap`.