Please answer the following questions.

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

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)
```

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

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]:

In [4]:

```
multiplyAll([4, 0, 2])
```

Out[4]:

In [5]:

```
multiplyAll([1, 1, 1, 1, 1])
```

Out[5]:

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]:

In [8]:

```
isSorted([1, 2, 3, 5, 4])
```

Out[8]:

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]:

In [11]:

```
sort11([1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 10])
```

Out[11]:

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]:

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]:

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]:

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.

`n`

¶`n`

`n`

`n`

C. n^3

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)]
```

In [40]:

```
print [ test_solve(n)/float(n**3) for n in range(1,30)]
```

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