2018-01-19.ipynb

Kernel: Python 3 (Ubuntu Linux)

Math 157: Intro to Mathematical Software

UC San Diego, winter 2018

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.

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

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.

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 = []  #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)))

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 = [] #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.

# Your code snippet goes here l[i][0] l[i][1]

Problem 3: Flow control

Grading criterion: 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.

# Your code goes here

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

Moot
Fizz
Buzz
Fizz
Moot
FizzBuzz
Moot

Problem 4: Better and worse

Grading criterion: 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):
    # your code goes here

def fib2(N):
    # your code goes here

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.

Your identity: (fill in here)

# Your test code goes here

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.

Problem 5: Dictionaries

Grading criterion: 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".)

5b. Give a list l1 of four Python objects that can't be the keys of a Python dictionary, and a list l2 of four objects that can be keys of a Python dictionary. Then check that each object consists of four 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.)

# Define lists l1, l2 here

# Check correctness of your answer here

Problem 6: List comprehensions

Grading criterion: 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\}$