M1399.000200 Homework 1

Due Sep 27, 2020 @ 11:59PM

Q1. Git/GitHub

No handwritten homework reports are accepted for this course. We work with Git and GitHub. Efficient and abundant use of Git, e.g., frequent and well-documented commits, is an important criterion for grading your homework.

1. Apply for the Student Developer Pack at GitHub using your snu.ac.kr email.

2. A link to join the M1399.000200 Github Classroom and a link to create an individual Github repository for homework is provided in the eTL. First join the classroom, and then create your own homework repo by accepting these two invitations in turn.

3. For each homework, the teaching assistant will make a pull request. Merge each pull request to your homework repo.

4. In this course, you are required to write your homework reports using IJulia. For each homework, you need to submit your Jupyter notebook (e.g, hw1.ipynb), html (e.g., hw1.html), along with all code and data that are necessary to reproduce the results.

5. Provide your answer directly on this notebook. Add your answer right below the question. If the question has subproblems, split the cell at the right location and insert cells for your answer. Do not modify the questions.

6. Maintain two branches master and develop. The develop branch will be your main playground, the place where you develop solution (code) to homework problems and write up report. The master branch will be your presentation area. Submit your homework files (Jupyter notebook file ipynb, html file converted from the notebook, all code and data sets to reproduce results) in master branch.

7. Before each homework's due date, commit your master branch. The teaching assistant and the instructor will check out your committed master branch for grading. Commit time will be used as your submission time. That means if you commit your Homework 1 submission after the deadline, penalty points will be deducted for late submission according to the syllabus.

8. Read the style guide for Julia programming. Following rules in the style guide will be strictly enforced when grading: "Write functions, not just scripts", "Avoid writing overly-specific types", "Handle excess argument diversity in the caller", "Append ! to names of functions that modify their arguments", "Don't use unnecessary static parameters", "Avoid using floats for numeric literals in generic code when possible". Also it is advised to follow "Use naming conventions consistent with Julia base/", "Write functions with argument ordering similar to Julia Base".

Q2. Algorithm

Write a Juila function that accepts the three coefficients of a quadratic polynomial and evaluates one of the roots by means of the quadratic formula, and computes the other root in an appropriate manner. Write the function specification very carefully, but succinctly, by using the ''' comments and other documentation system of Julia. (What do you do if $b^2 < 4ac$? You do not have to provide a solution in this case, i.e., complex roots, but your software part must handle that case.)

Q3. JIT

Consider Julia function

function g(k::Number)
    for i in 1:10
        k = 2k - 1
    end
    k
end

1. Use @code_llvm to find the LLVM bytecode of compiled g(2).
2. Use @code_llvm to find the LLVM bytecode of compiled g(2.0).
3. Compare the bytecode from questions 1 and 2. What do you find?
4. Repeat questions 1-3 with @code_native.

Q4. Floats

Consider the evaluation of $e^x$ using the Taylor series $$e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dotsb$$ in Julia. Write function expTaylor() that takes a double-precision floating point number x and executes the following.

stop = 100
ex = 1.
xi = 1.
ifac = 1.
for i=1:stop
    xi *= x
    ifac *= i
    ex += xi / ifac
end
ex

Now let x=20.0. A correct implementation of expTaylor() should yield 4.8516519540979016e8, which is close enough to 4.851651954097903e8 that the built-in fuction exp() yields.

1. Compare the values of expTaylor(-20.0) and 1 / expTaylor(20.0). Calculate the relative error of the two values, assuming that exp(-20.0) is the true value. Explain what you found.

2. We can think of the algorithm given in the Julia code above as an iterative algorithm in i. At each value of i, there is a difference in the value of ex and the true value ex. (The exact value of this difference is the truncation error.) Modify the code (or use different code) to determine the relative error in ex for each value of i. For x = 20.0, make a plot of the relative error and the number of iterations (that is, of i) for 1 to 100 iterations. Now, repeat this for x = −20.0. Explain what you found.

3. Determine the order of the error for approximating ex with the Taylor series for x = 20 in terms of the number of iterations (that is, the number of terms in the Taylor series).

Q5. Strassen's algorithm

Assume n is a power of 2. Strassen's algorithm for multiplying two n by n matrices A and B is as follows:

function Strassen(A::Matrix, B::Matrix) 
    n = size(A, 1)
    if n == 1
        return A * B
    end
    @views A11 = A[1:n/2, 1:n/2]
    @views A12 = A[1:n/2, n/2+1:n]
    @views A21 = A[n/2+1:n, 1:n/2]
    @views A22 = A[n/2+1:n, n/2+1:n]
    @views B11 = B[1:n/2, 1:n/2]
    @views B12 = B[1:n/2, n/2+1:n]
    @views B21 = B[n/2+1:n, 1:n/2]
    @views B22 = B[n/2+1:n, n/2+1:n]

    P1 = Strassen(A12 - A22, B21 + B22)
    P2 = Strassen(A11 + A22, B11 + B22)
    P3 = Strassen(A11 - A21, B11 + B12)
    P4 = Strassen(A11 + A12, B22)
    P5 = Strassen(A11, B12 - B22)
    P6 = Strassen(A22, B21 - B11)
    P7 = Strassen(A21 + A22, B11)

    C11 = P1 + P2 - P4 + P6
    C12 = P4 + P5
    C21 = P6 + P7
    C22 = P2 - P3 + P5 - P7

    return [C11 C12; C21 C22]
end

1. Show that this algorithm correctly multiplies A and B.
2. Let $T(n)$ by the number of floating point operations (addtion, subtraction, multiplication). Show that $$T(n) = 7 T(n/2) + \frac{9}{2}n^2 .$$
3. Show that $T(n) = O(n^{\log_2 7})$.
4. What is a drawback is Strassen's algorithm?