Problem set 5: Writing your own algorithms

This problem set has no tasks, but only problems of increasing complexity. See how far you can get :)

[1]

import math

Factorial

Remember that the factorial of $n$ is

n\cdot(n-1)\cdot(n-2)\cdot...\cdot 1

Problem: Correct the following function so that it returns the factorial of n using functional recursion.

[2]

def factorial(n):
    if n == 1:
        return 1
    else:
        return n # + missing code
    
print(factorial(5))

Answer: see A1.py

Descending bubble sort

Problem: Sort a list of numbers in-place descending (from high to low).

Inputs: List of numbers.

Outputs: None.

Algorithm:

[4]

L = [54, 26, 93, 17, 77, 31, 44, 55, 20] # test list

# write your code here (hint: use the bubble_sort() algorithm from the lectures)
def bubble_sort(L):
    pass

bubble_sort(L)
print('sorted',L)

Answer: see A2.py

Linear search for index

Problem: Consider a number x and a sorted list of numbers L. Assume L[0] <= x < L[-1]. Find the index i such that L[i] <= x < L[i+1] using a linear search.

Inputs: A sorted list of numbers L and a number x.

Outputs: Integer.

[6]

L = [0, 1, 2, 8, 13, 17, 19, 32, 42] # test list

# write your code here (hint: use the linear_seach() algorithm from the lecture)
def linear_search(L,x):
    pass

# test your function
for x in [3,7,13,18,32]:
    i = linear_search(L,x)
    print(f'{x} gives the index {i}')
    assert(x >= L[i] and x < L[i+1]),(x,i,L[i])

Answer: see A3.py

Bisection

Problem: Find an (apporximate) solution to $f(x) = 0$ in the interval $[a,b]$ where $f(a)f(b) < 0$ (i.e. one is positive and the other is negative).

If $f$ is a continuous function then the intermediate value theorem ensures that a solution exists.

Inputs: Function $f$ , float interval $[a,b]$ , float tolerance $\epsilon > 0$ .

Outputs: Float.

Algorithm: bisection()

Set $a_0 = a$ and $b_0 = b$ .
Compute $f(m_0)$ where $m_0 = (a_0 + b_0)/2$ is the midpoint
Determine the next sub-interval $[a_1,b_1]$ :
i. If $f(a_0)f(m_0) < 0$ then $a_1 = a_0$ and $b_1 = m_0$
ii. If $f(m_0)f(b_0) < 0$ then $a_1 = m_0$ and $b_1 = b_0$
Repeat step 2 and step 3 until $|f(m_n)| < \epsilon$

[8]

f = lambda x: (2.1*x-1.7)*(x-3.3) # test function
def bisection(f,a,b,tau):
    pass
    # write your code here
    
result = bisection(f,0,1,1e-8)
print(result)

None

Answer: see A4.py

Find prime numbers (hard)

Goal: Implement a function in Python for the sieve of Eratosthenes.

The sieve of Eratosthenes is a simple algorithm for finding all prime numbers up to a specified integer. It was created by the ancient Greek mathematician Eratosthenes. The algorithm to find all the prime numbers less than or equal to a given integer $n$ .

Algorithm: sieve_()

Create a list of integers from $2$ to $n$ : $2, 3, 4, ..., n$ (all potentially primes)
primes = list(range(2,n+1))
Start with a counter $i$ set to $2$ , i.e. the first prime number
Starting from $i+i$ , count up by $i$ and remove those numbers from the list, i.e. $2i$ , $3i$ , $4i$ etc.
primes.remove(i)
Find the first number of the list following $i$ . This is the next prime number.
Set $i$ to the number found in the previous step.
Repeat steps 3-5 until $i$ is greater than $\sqrt {n}$ .
All the numbers, which are still in the list, are prime numbers.

A more detailed explanation: See this video

[10]

def sieve(n):
    pass # write your code here

print(sieve(100))

None

Answer: see A5.py