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 nn is

n(n1)(n2)...1n\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))
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)=0f(x) = 0 in the interval [a,b][a,b] where f(a)f(b)<0f(a)f(b) < 0 (i.e. one is positive and the other is negative).

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

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

Outputs: Float.

Algorithm: bisection()

  1. Set a0=aa_0 = a and b0=bb_0 = b.

  2. Compute f(m0)f(m_0) where m0=(a0+b0)/2m_0 = (a_0 + b_0)/2 is the midpoint

  3. Determine the next sub-interval [a1,b1][a_1,b_1]:

    i. If f(a0)f(m0)<0f(a_0)f(m_0) < 0 then a1=a0a_1 = a_0 and b1=m0b_1 = m_0

    ii. If f(m0)f(b0)<0f(m_0)f(b_0) < 0 then a1=m0a_1 = m_0 and b1=b0b_1 = b_0

  4. Repeat step 2 and step 3 until f(mn)<ϵ|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 nn.

Algorithm: sieve_()

  1. Create a list of integers from 22 to nn: 2,3,4,...,n2, 3, 4, ..., n (all potentially primes)

    primes = list(range(2,n+1))

  2. Start with a counter ii set to 22, i.e. the first prime number

  3. Starting from i+ii+i, count up by ii and remove those numbers from the list, i.e. 2i2i, 3i3i, 4i4i etc.

    primes.remove(i)

  4. Find the first number of the list following ii. This is the next prime number.

  5. Set ii to the number found in the previous step.

  6. Repeat steps 3-5 until ii is greater than n\sqrt {n}.

  7. 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

More Problems