Quiz 2 - Solutions

Please answer the following questions.

Problem 1

Write a function hasSolution1(a, b) which returns True if ax = b has a unique solution for x, and otherwise returns False

In [1]:
def hasSolution1(a,b):
    return a!=0

Problem 2

Describe what is wrong with the following code? Also change the code below by replacing # HERE with something else to make it work. The code you add there should not use + at all.

In [ ]:
# returns the sum x+y, where x and y are both greater than or equal to 0
def add(x, y):
    if y==0:
        return x
    return 1 + add(x, y-1)

What was wrong?:

There was no base case for the recursion so the function never stopped.

Problem 3

Use recursion to implement a function multiplyAll which takes as input a list L of integers and returns the product of all elements of L.

In [2]:
def multiplyAll(L):
    if len(L)==0:
        return 1
    return L[0]*multiplyAll(L[1:])

Examples:

In [3]:
multiplyAll([1,2,3])
Out[3]:
6
In [4]:
multiplyAll([4, 0, 2])
Out[4]:
0
In [5]:
multiplyAll([1, 1, 1, 1, 1])
Out[5]:
1

Problem 4

Write a function isSorted which takes as input a list L of integers and returns True if L is sorted and False if it is not sorted.

In [6]:
def isSorted(L):
    for i in range(len(L)-1):
        if L[i]>L[i+1]:
            return False
    return True

Examples:

In [7]:
isSorted([1,2,3,4,5])
Out[7]:
True
In [8]:
isSorted([1, 2, 3, 5, 4])
Out[8]:
False

Problem 5

Suppose you are given an implementation of sort10 as below, which sorts an input list of 10 numbers. Use it to implement sort11, which sorts a list of 11 numbers. Use the selection sort algorithm. Your code should not use the built-in sorted() function in sort11.

In [9]:
def sort10(L):
    return sorted(L)

def sort11(L):
    current_min = L[0]
    current_idx = 0
    for i in range(1,11):
        if current_min > L[i]:
            current_min = L[i]
            current_idx = i
    L[current_idx],L[0] = L[0],L[current_idx]
    return [L[0]]+sort10(L[1:])

Examples

In [10]:
sort11([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
Out[10]:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
In [11]:
sort11([1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 10])
Out[11]:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12]

Problem 6

Suppose you are given implementations of sort10 and merge_lists as below. sort10 sorts an input list of 10 numbers. merge_lists takes two sorted lists L and R as input and outputs the merged sorted list containing all the elements of both L and R. Use sort10 and merge_lists to implement sort20, which sorts a list of 20 numbers. Use the merge sort algorithm. Your code should not use the built-in sorted() function in sort20.

In [15]:
def sort10(L):
    return sorted(L)

def merge_lists(L, R):
    return sorted(L + R)

def sort20(L):
    L1 = sort10(L[0:10])
    L2= sort10(L[10:20])
    return merge_lists(L1,L2)
    # write your code here, using sort10 and merge_lists

Examples

In [16]:
sort20([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
Out[16]:
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]
In [17]:
sort20([1, 2, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6, 7, 8, 7, 8, 9, 10, 10, 9])
Out[17]:
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]

Problem 7

You are given the function positive_solve4(eqs) which solves systems of 4 equations with 4 variables, but only if all the coefficients of the variables are nonnegative. On input a list eqs of 4 equations (each of which is a list of 5 coefficients), positive_solve4(eqs) will return the same value as solve(eqs) (i.e., a list of length 4 of the solutions) if all coefficients of variables are non-negative and return None otherwise. (It's OK if the constant coefficients are negative.)

You need to implement the function solve2(a,b,c,d,e,d) which will solve 2 equations with 2 variables (with potentially negative coefficients) of the form $ax+by+c=0,cx+dy+e=0$ using a call to positive_solve4(eqs).

In [18]:
## Helper function: positive_solve4
from __future__ import division
import numpy as np

def positive_solve4(eqs):
    for eq in eqs:
        if eq[0]<0 or eq[1]<0 or eq[2]<0 or eq[3]<0:
                return None
    A = np.ndarray([4,4])
    for i in range(4):
        for j in range(4):
            A[i,j] = eqs[i][j]
    b = np.ndarray([4,1])
    for i in range(4):
        b[i,0] = -eqs[i][4]
    C = np.linalg.inv(A)
    sol = np.dot(C,b)
    return [round(sol[i,0],3) for i in range(4)]
In [20]:
#helper function, can also not use it but then code is a little longer
def pair(a):
    if a>=0:
        return [a,0]
    return [0,-a]

def solve2(a,b,c,d,e,f): # solve ax + by + c = 0 , dx + ey + f = 0
    eqs = [ [1,1,0,0,0], [0,0,1,1,0]] # create equations x+w =0, y+z=0 so now w=-x, z=-y
    eqs.append(pair(a)+pair(b)+[c]) # Use either ax or -aw depending on whether a>=0, etc..
    eqs.append(pair(d)+pair(e)+[f])
    res = positive_solve4(eqs)
    return [res[0], res[2]]

Examples

In [21]:
solve2(1,1,-10,1,-1,-4)
Out[21]:
[7.0, 3.0]

Problem 8

Suppose n is about one billion (1,000,000,000). Which of these numbers is closest to the number of steps that solve will make on a system of n equations with n variables? Also please explain your solution. We have included the code for solve below for your convenience.

A. n

B. n2

C. n3

D. n4

Answer:

C. n^3

Justification for answer:

We are given $n$ equations in $n$ variables, and so making the first coefficient nonzero and then zeroing out all these equations involves going over all these equations and takes about $n^2$ steps.

Then we make a recursive call and take $(n-1)^2$ steps, and then $(n-2)^2$ etc..

The total amount of work is about $n^2 + (n-1)^2 + (n-2)^2 + .... + 1$ which is $1^2 + 2^2 + ... + n^2$ which is about $n^3$ (or $n^3/3$ to be more precise).

This was a theoretical question which you didn't need to use a computer for, but just to see it, here is a version of solve that counts the number of steps.

In [36]:
from __future__ import division
import sys

step_counter = 0

def inc_step():
    global step_counter
    step_counter += 1

def make_first_coeff_nonzero_general(eqs):
    for i in range(len(eqs)):
        inc_step()
        if eqs[i][0]:
            eqs[0], eqs[i] = eqs[i], eqs[0]
            return
    sys.exit("oops:  all first coefficients are zero")
    return 

### Helper functions
def multiply_equation(eq,num):
    """Multiply all coefficients of equation eq by number num. 
       Return result"""
    res = []
    for x in eq:
        inc_step()
        res += [x*num]
    return res

def add_equations(eq1,eq2):
    """Add eq1 and eq2. Return result"""
    res = []
    for i in range(len(eq1)):
        inc_step()
        res.append(eq1[i]+eq2[i])
    return res

def solve(eqs):
    n = len(eqs)
    if n==0:
        return []
    
    make_first_coeff_nonzero_general(eqs)  # make 1st coef of 1st equation nonzero
    # takes n+1 steps
    
    
    eqs[0] = multiply_equation(eqs[0],1/eqs[0][0]) 
    # make 1st coef of 1st  equation equal 1
    # takes n+1 steps
    
    for i in range(1,n-1):
        eqs[i] = add_equations(eqs[i],multiply_equation(eqs[0],-eqs[i][0])) # zero out first coefficient in eqs 1,2
        # make 1st coef of 2nd .. n-th equation equal zero
        # takes about 3(n+1) steps.
        
    rest_equations = []
    for i in range(1,n):
        rest_equations.append(eqs[i][1:n+1])
        inc_step()
    
    
    solutions = solve(rest_equations)
    # solve remainder of  equations for remainder of  variables 

    x =  - eqs[0][n]
    for i in range(1,n):
        x -= eqs[0][i]*solutions[i-1]
        inc_step()
    # solve 1st variable using solution for 2nd and 3rd variable
    return [x] + solutions
In [30]:
import random

def generate_equations(n):
    solutions = range(n)
    equations = []
    for i in range(n):
        constant_term = 0
        eq = []
        for j in range(n):
            x =  random.randint(-100,+100)
            eq.append(x)
            constant_term -= x*solutions[j]
        eq.append(constant_term)
        equations.append(eq)
    return equations

def test_solve(n):
    global step_counter
    step_counter = 0
    solve(generate_equations(n))
    return step_counter
In [39]:
print [ test_solve(n) for n in range(1,30)]
[3, 9, 26, 58, 109, 183, 284, 416, 583, 789, 1038, 1334, 1681, 2083, 2544, 3068, 3659, 4321, 5058, 5874, 6773, 7759, 8836, 10008, 11279, 12653, 14134, 15726, 17433]
In [40]:
print [ test_solve(n)/float(n**3) for n in range(1,30)]
[3.0, 1.125, 1.0, 0.90625, 0.872, 0.8472222222222222, 0.8279883381924198, 0.8125, 0.7997256515775034, 0.789, 0.7798647633358378, 0.7719907407407407, 0.7651342740100137, 0.7591107871720116, 0.7537777777777778, 0.7490234375, 0.7447588031752493, 0.7409122085048011, 0.7374252806531565, 0.73425, 0.731346506856711, 0.7286814425244177, 0.7262266787211309, 0.7239583333333334, 0.721856, 0.7199021392808375, 0.718081593253061, 0.716381195335277, 0.7147894542621673]

We see that the number of steps converges to about $0.7 n^3$