2018-01-19-solutions.ipynb

Kernel: Python 3 (Ubuntu Linux)

Math 157: Intro to Mathematical Software

UC San Diego, winter 2018; materials by Kiran S. Kedlaya

Homework 1: due January 19, 2018

Please enter all answers within this notebook unless otherwise specified.

Each problem's statement includes the criteria by which it will be graded. Correctness means in particular that all code that is supposed to execute must actually do so without errors! In addition, you may be marked off for not setting cells to the appropriate format (Code or Markdown), or for not answering textual questions in complete, grammatical English sentences with proper spelling and punctuation.

Note: homework assignments may consist of variable numbers of problems, but the maximum possible scores will be renormalized to a common value for the computation of grades.

Problem 1: Comparison of programming languages

Grading criterion: correctness.

1a. Explain the difference between 0-based arrays and 1-based arrays.

In a 0-based array, the initial object is assigned the index 0. In a 1-based array, the initial object is assigned the index 1.

1b. Explain the difference between "pass by reference" and "pass by value".

When a parameter is passed by value to a function, a copy is made. Any changes made to the parameter within the function are only made to that copy, so the original parameter is unchanged. When a parameter is passed by reference to a function, no copy is made. Any changes made to the parameter within the function are therefore also made outside that function.

1c. Classify the following programming languages according to the criteria in parts a and b: Python, MATLAB, R, Javascript, Julia. For examples of the languages other than Python, see the Sage worksheet "comparison.sagews" in this folder.

Python and Javascript are 0-based; MATLAB, R, and Julia are 1-based. Python, MATLAB, and R are pass by value; Javascript and Julia are pass by reference. To see this for MATLAB using the Sage worksheet "comparison.sagews", we note that to change the initial element of the array b we input "b(1)=5". We conclude that MATLAB is 1-based. We note that when b is changed, a is not changed, so we conclude that MATLAB is pass by value.

References: https://en.wikipedia.org/wiki/Zero-based_numbering

https://stackoverflow.com/questions/373419/whats-the-difference-between-passing-by-reference-vs-passing-by-value

Problem 2: Truth values

Grading criterion: correctness and thoroughness.

An expression e will be called truthy if bool(e) is True (i.e., if if e: stuff executes stuff); otherwise e is falsy.

1a. Create a list l consisting of 10 different Python objects that are falsy. For correctness, your list must have the property that a is b evaluates to False whenever a and b are entries of the list in different positions. For thoroughness, the entries should look as different as possible. (Hint: [] is an example.)

l = [None, False, 0, 0.0, 0j, [], {}, (), '', set()]  #insert ten objects here

# Use this code to test correctness of your answer!
print(len(l) == 10)
print(all(not l[i] for i in range(10)))
print(all(not (l[i] is l[j]) for i in range(10) for j in range(i+1,10)))

True
True
True

1b. In Python, "is" means "identical objects", whereas "==" can be much more subtle. Create a list l consisting of 5 tuples (a,b) for each of which a==b evaluates to True but a is b evaluates to False.

l = [([],[]),({},{}),(1,1.0),(1,2/2),(1,True)] #insert five objects here

1c. By analogy with the code snippet given in 1a, write a code snippet to verify correctness of your answer to 1b. That is, the code snippet should print one or more True/False values, all of which are True if and only if the answer is correct.

print(len(l) == 5)
print(all((l[i][0]==l[i][1]) for i in range(5)))
print(all(not (l[i][0] is l[i][1]) for i in range(5)))

True
True
True

References: https://stackoverflow.com/questions/39983695/what-is-truthy-and-falsy-in-python-how-is-it-different-from-true-and-false

https://dbader.org/blog/difference-between-is-and-equals-in-python

Problem 3: Flow control

Grading criteria: correctness of output.

Write a function named fizz_buzz that accepts an integer N and for each integer m from 1 to N, prints 'Fizz' if m is divisible by 2 but not 3, prints 'Buzz' if m is divisible by 3 but not 2, prints 'FizzBuzz' if m is divisible by 2 and 3, and prints 'Moot' if none of the above.

def fizz_buzz(N):
    for m in range(1,N+1): # Go through the integers from 1 to N one by one
        if m%2 == 0 and m%3 != 0: # Check the various divisibility conditions using %
            print('Fizz')
        elif m%2 != 0 and m%3 == 0: # Use elif to make sure that for each integer, only one thing is printed 
            print('Buzz')
        elif m%2 == 0 and m%3 == 0:
            print('FizzBuzz')
        else:
            print('Moot')
            

# Test your answer against the output below
fizz_buzz(7)

Moot
Fizz
Buzz
Fizz
Moot
FizzBuzz
Moot

Moot
Fizz
Buzz
Fizz
Moot
FizzBuzz
Moot

Problem 4: Better and worse

Grading criteria: correctness (of the code) and thoroughness (of the explanation).

4a. Read about recursion in Python. Then write two different functions that, on an input N, return the Nth Fibonacci number: one using recursion, and one not.

def fib1(n): # Version with recursion
    if n<1: # Check that the input is a positive integer
        return "Need n positive"
    elif n in [1,2]: # Base case
        return 1
    else: # Recursively call the function inside itself
        return fib1(n-1)+fib1(n-2)

def fib2(n): # Version without recursion
    if n<1: # Check that the input is a positive integer
        return "Need n positive"
    elif n in [1,2]: # Base case
        return 1
    num0=1 # We need to be able to store three values at a time,
    num1=1 # the two numbers that we'll be adding
    num2=1 # and their sum
    for _ in range(n-2): # Computing F_n requires n-2 additions
        num0=num1 # Move the two largest known Fibonacci numbers down 
        num1=num2 
        num2=num0+num1 # Compute their sum to get a larger number
    return num2

4b. State an identity of Fibonacci numbers other than the defining recurrence $F_n = F_{n-1} + F_{n-2}$; use TeX symbols to format this correctly. Then write some code that tests this identity using your two functions.

Sample identity: $F_n^2-F_{n+1}F_{n-1}=(-1)^{n-1}$

Other identities can be found here: https://en.wikipedia.org/wiki/Fibonacci_number#Combinatorial_identities

def fib_check(n):
    if n<2:
        return "Need n at least 2"
    if (fib1(n)**2-fib1(n+1)*fib1(n-1))==(-1)**(n-1): # Check first program
        fib1_works=True
    else:
        fib1_works=False
    if fib2(n)**2-fib2(n+1)*fib2(n-1)==(-1)**(n-1): # Check second program
        fib2_works=True
    else:
        fib2_works=False
    if fib1_works and fib2_works: # If both programs worked, return True
        return True
    else:
        return False
        
print(all(fib_check(n) for n in range(2,12)))
    

True

4c. Give as detailed an explanation of possible of why your non-recursive function is "better" than the recursive one. You may wish to do some online research for this, in which case please cite your sources.

When computing $F_n$, the recursive function does a separate computation for each of the smaller Fibonacci numbers $F_{n-1},F_{n-2},\dots,F_1$. The non-recursive function uses the Fibonacci numbers it has already computed to compute the next value. The recursive function will therefore take exponentially time to run, wile the non-recursive function will run in linear time. For small values of $n$ the difference will be minor, but for large values the non-recursive function will be much faster.

Reference: https://cs.stackexchange.com/questions/14733/complexity-of-recursive-fibonacci-algorithm

Problem 5: Dictionaries

Grading criteria: correctness and thoroughness.

5a. Search online and find as many names as you can for data structures that are like a Python "dictionary", but in other programming languages. (For example, in Javascript the analogue of a Python dictionary is called a "Map".)

An extremely extensive list is given here: https://en.wikipedia.org/wiki/Comparison_of_programming_languages_(associative_array)

Some examples are maps in C++ and Java, dictionaries in Julia, alists in Lisp, associations in Mathematica, and hashes in Perl.

5b. Give a list l1 of five Python objects that can't be the keys of a Python dictionary, and a list l2 of five objects that can be keys of a Python dictionary. Then check that each object consists of five objects of different types; that is, [type(obj) for obj in l1] should contain no repeated entries, and similarly for l2. (The check should be in the form of a code snippet that prints True if the check passes and False if it fails.)

l1=[[1],{5:3},([1],1),set([1]),bytearray([0x00, 0x00])]
l2=[1, 'a', 1.1, True, (1,2)]

print(all(not (l1[i] is l1[j]) for i in range(5) for j in range(i+1,5)))
print(all(not (l2[i] is l2[j]) for i in range(5) for j in range(i+1,5)))

True
True

Python objects can be the keys of a Python dictionary only when they are immutable. Immutable objects cannot be modified. If you try to change an immutable object, Python will just create a new object. More details can be found here: https://codehabitude.com/2013/12/24/python-objects-mutable-vs-immutable/

Problem 6: List comprehensions

Grading criteria: correctness.

Translate each of the following mathematical definitions of sets into a Python list comprehension:

• $\{x: 0 < x < 100, x \not\equiv 0 \pmod{3} \}$

• $\{x: 10 < x < 50, x^2 \equiv 1 \pmod{5}\}$

• $\{(x,y): 0 < x < 1000, 0 < y < 1000, x^2 - y^3 = 1\}$

• $\{(x,y): -10 < x < 10, -10 < y < 10, |x^2-y^2-y| < 3\}$

[x for x in range(1,100) if not x%3==0]

[1,
 2,
 4,
 5,
 7,
 8,
 10,
 11,
 13,
 14,
 16,
 17,
 19,
 20,
 22,
 23,
 25,
 26,
 28,
 29,
 31,
 32,
 34,
 35,
 37,
 38,
 40,
 41,
 43,
 44,
 46,
 47,
 49,
 50,
 52,
 53,
 55,
 56,
 58,
 59,
 61,
 62,
 64,
 65,
 67,
 68,
 70,
 71,
 73,
 74,
 76,
 77,
 79,
 80,
 82,
 83,
 85,
 86,
 88,
 89,
 91,
 92,
 94,
 95,
 97,
 98]

[x for x in range(10,50) if x**2%5==1]

[11, 14, 16, 19, 21, 24, 26, 29, 31, 34, 36, 39, 41, 44, 46, 49]

[(x,y) for x in range(1,1000) for y in range(1,1000) if x**2-y**3==1]

[(3, 2)]

[(x,y) for x in range(-10,10) for y in range(-10,10) if abs(x**2-y**2-y)<3]

[(-2, -3),
 (-2, -2),
 (-2, 1),
 (-2, 2),
 (-1, -2),
 (-1, -1),
 (-1, 0),
 (-1, 1),
 (0, -2),
 (0, -1),
 (0, 0),
 (0, 1),
 (1, -2),
 (1, -1),
 (1, 0),
 (1, 1),
 (2, -3),
 (2, -2),
 (2, 1),
 (2, 2)]