# Quiz 2 - Solutions¶

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

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

"""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$