2018-03-16-part1.ipynb

Kernel: SageMath 8.1

Math 157: Intro to Mathematical Software

UC San Diego, winter 2018

March 9, 2018: discussion of part 1 of the final project

I have added some comments in boldface to the original problem statements.

Problem 1: Symbolic sums

Grading criteria: correctness of code.

Demonstrate that Sage is able to evaluate the following infinite sums (without manually encoding known mathematical formulas).

1. Compute $\sum_{n=1}^{\infty} \frac{(-1)^n}{n}$ symbolically.

2. Compute $\sum_{n=1}^{\infty} \frac{1}{n^2}$ symbolically.

3. Compute $\sum_{n=1}^{\infty} \frac{1}{n^3}$ both symbolically (in terms of the Riemann Zeta function) and numerically.

4. Compute $\sum_{n=1}^{\infty} \frac{1}{n^4}$ symbolically.

Problem 2: Determinants

Grading criteria: correctness of code and explanations.

2a. Implement a function called my_det that calculates the determinant of a matrix recursively using expansion by cofactors. The Matrix methods delete_columns and delete_rows may come in handy. You can assume that your input is a square matrix.

2b. Check that your function agrees with Sage's built-in function on a random 5 by 5 matrix over $\mathbb{Z}$.

2c. Do some timings for random $n \times n$ matrices over $\mathbb{Z}$ for $n=5, \dots, 10$ comparing your function and Sage's built-in function. Make a single plot containing both sets of results. ** The timing for $n=10$ may take a long time (>30 minutes). **

2d. Explain the results of 2c in terms of the asymptotic complexity of the two methods.

Problem 3: Back to the poker table

Grading criteria: correctness of code.

In a previous exercise, you constructed a "deck" of 52 playing cards consisting of the Cartesian product of "ranks" and "suits", and wrote a function to classify a set of 5 (distinct) cards as a poker hand. You may wish to reuse your answer to that problem here.

3a. Write a function which, given two poker hands h1 and h2, returns 1 if h1 is the higher-ranking hand, -1 if h2 is the higher-ranking hand, and 0 if the two hands are equally ranked. Note that poker hands are primarily sorted by their type, but there are rules to break some ties even among hands of the same type. (For example, a pair of queens outranks a pair of jacks.)

3b. Define a Python class called "Hand" with the following property: if s1 and s2 are two poker hands, then

h1 = Hand(s1)
h2 = Hand(s2)
print(h1 < h2)

will print True if and only if s2 is (strictly) higher in ranking than s1. Your class should implement the method __lt__ to achieve operator overloading. (Do not implement __cmp__; this works in Python 2 but will fail in Python 3.)

class Hand:
    # rest of the definition goes here

# Assume that s1 and s2 are two lists of five distinct cards each.
h1 = Hand(s1)
h2 = Hand(s2)
print(h1 < h2)

Problem 4: Texas Hold 'Em

Grading criteria: correctness of code, to be judged as if your solution to problem 3 is completely correct.

Texas Hold 'Em is the variety of poker most often shown on television. Each player is initially dealt two cards (kept hidden), and eventually five more cards are dealt (face up) on the table. Each player's holding is ranked according to the best hand that can be made from their two cards plus the five common cards. (The bidding aspect of the game is not relevant for this problem.)

4a. Write a function which, given a set of seven distinct cards, identifies the highest-ranking hand which can be made using some five of the cards. In case of a tie, you may return any hand which ties for the highest ranking.

4b. Write a function which, given two pairs of cards, computes the probability that for a random set of five common cards (where all nine cards in question are distinct), the first pair will outrank the second pair. For full credit, you should do this by exhausting over all possibilities for the common cards, rather than doing a random sample. ** This was a bit too optimistic in my part. Instead, do a random sample on at least $10^4$ sample points. **

4c. Write a function, given one pair of distinct cards, computes the probability that if one chooses another pair and five common cards at random from the remaining cards (so again all nine cards in question are distinct), the given pair will outrank the other pair. For this problem, instead of exhaustion, use $10^6$ random samples. ** Again, it is sufficient if you use at least $10^4$ sample points. **

4d. Determine the values of the function you wrote in 3c for all possible pairs of distinct cards. Note that this probability should depend only on the values of the two cards and (if the values are distinct) whether the two cards are of the same or different suits. ** You may want to exploit the fact that the exact suits of the initial 2 cards do not matter, only whether they are the same or different. **

Problem 5: Adjacent states

Grading criteria: correctness of code.

Throughout this problem, by "US states" we mean the 50 US states plus the District of Columbia.

5a. The following string, adapted from this source, represents the adjacencies among US states, as represented by their standard postal abbreviations.

Starting from s, construct a graph whose vertices are labeled by the postal abbreviations, with an edge between two vertices if and only if they correspond to adjacent states.

s = """
AK
AL,MS,TN,GA,FL
AR,MO,TN,MS,LA,TX,OK
AZ,CA,NV,UT,NM
CA,OR,NV,AZ
CO,WY,NE,KS,OK,NM,UT
CT,NY,MA,RI
DC,MD,VA
DE,MD,PA,NJ
FL,AL,GA
GA,FL,AL,TN,NC,SC
HI
IA,MN,WI,IL,MO,NE,SD
ID,MT,WY,UT,NV,OR,WA
IL,IN,KY,MO,IA,WI
IN,MI,OH,KY,IL
KS,NE,MO,OK,CO
KY,IN,OH,WV,VA,TN,MO,IL
LA,TX,AR,MS
MA,RI,CT,NY,NH,VT
MD,VA,WV,PA,DC,DE
ME,NH
MI,WI,IN,OH
MN,WI,IA,SD,ND
MO,IA,IL,KY,TN,AR,OK,KS,NE
MS,LA,AR,TN,AL
MT,ND,SD,WY,ID
NC,VA,TN,GA,SC
ND,MN,SD,MT
NE,SD,IA,MO,KS,CO,WY
NH,VT,ME,MA
NJ,DE,PA,NY
NM,AZ,CO,OK,TX
NV,ID,UT,AZ,CA,OR
NY,NJ,PA,VT,MA,CT
OH,PA,WV,KY,IN,MI
OK,KS,MO,AR,TX,NM,CO
OR,CA,NV,ID,WA
PA,NY,NJ,DE,MD,WV,OH
RI,CT,MA
SC,GA,NC
SD,ND,MN,IA,NE,WY,MT
TN,KY,VA,NC,GA,AL,MS,AR,MO
TX,NM,OK,AR,LA
UT,ID,WY,CO,AZ,NV
VA,NC,TN,KY,WV,MD,DC
VT,NY,NH,MA
WA,ID,OR
WI,MI,MN,IA,IL
WV,OH,PA,MD,VA,KY
WY,MT,SD,NE,CO,UT,ID
"""

5b. Compute a maximum flow and a minimum cut for this graph, using California as the source and the District of Columbia as the sink. ** For the maximum flow, you should also find a set of edge-disjoint paths realizing the maximum. **

Problem 6: Cholesky dempositions

Grading criteria: correctness of explanations and code. ** For this problem, you are not expected to implement the Cholesky decomposition yourself; it is sufficient to use the predefined functions in the various systems. **

6a. In your words, explain what the Cholesky decomposition of a matrix is, for which matrices it is defined, and why it is useful in numerical linear algebra.

6b. Use Sage's cholesky function to compute the Cholesky decomposition of the matrix $$M = \left(\begin{array}{rrrrr} 3 & -1 & -1 & -3 & -2 \\ -1 & 6 & 5 & 1 & 2 \\ -1 & 5 & 6 & 1 & 3 \\ -3 & 1 & 1 & 5 & 1 \\ -2 & 2 & 3 & 1 & 6 \end{array}\right).$$

6c. Repeat the computation using numpy.

6d. Repeat the computation using Octave. You may either switch to the Octave kernel or call Octave directly from Sage.

6e. Repeat the computation using Julia. You will need to switch to the Julia kernel for this.

Problem 7: Face completion

Grading criteria: correctness of code and answers.

Special note: in this problem, you will be running code in another notebook. However, you will only be credited for answers entered in this notebook.

Go to the scikit-learn example of face completion; download the script as a Jupyter notebook; upload it into this folder in your project; and run all cells using the Python 3 (Ubuntu Linux) kernel. Then answer the following questions.

7a. What fraction of the data was used for testing? And what code can be used to determine this?

7b. Suppose we want to predict the top half of the face from the bottom. Which lines of code need to be changed, and to what?

# List all the lines of code that you are changing here...

# ... and their replacements here.

7c. Suppose we want to use a Multilayer perceptron regressor in addition to the four other estimators used in the sample. What lines of code need to be added, and where? (In each location where one or more lines is to be added, include one existing line before and after your addition.)

# List added code here, with one line of context on each side.

Problem 8: Finding (discrete logarithms using) Nemo

Grading criteria: correctness of code.

For this problem, use the Julia kernel. ** The use of Nemo for this problem is permitted but not required; you may use Julia native functionality instead if you prefer. **

8a. Demonstrate the (usual, not elliptic) Diffie-Hellman key exchange in Julia using the prime p=2171645417 and the primitive root g=3. That is, Alice and Bob choose random secrets and use them to establish a common key.

using Nemo

8b. Implement the baby-step-giant-step algorithm in Julia using the same p and g, including a test for correctness.