Description

IE531: Algorithms for Data Analytics
Homework 1: Review of Linear Algebra, Probability & Statistics and Computing
Zhenye Na(zna2)

1. Linear Algebra: Consider the following set of linear equations involving six equations in five unknowns x1, x2, . . . , x5 .

(a) Show that there a solution to these equations.

(b) Present a general formula for the set of all solutions that satisfy these equations. The Reduced Row Echelon Form of Matrix (A | y) is as follows:

So the general formula for the solutions will be:

xT = [8-3x+y, y, 1+x, x, -7-y]T
(c) Verify the general formula using MATLAB.
Define x=0 and y=1, using MATLAB to calculate the matrix multiplication of Ax, the result is:

So this is the general formula for this equation.

(d) Show that
are solutions to the equation Ax = y identified earlier.

According to the Reduced Row Echelon Form of A | y, we can extract three equations from it:
𝑥” + 3𝑥% + 𝑥& = 1
𝑥) + 𝑥& = −7
𝑥, − 𝑥% = 1

Applying both of the solutions to Ax=y, and we can get that both (1) and (2) are correct solutions to the matrix multiplication.

(e) Present a cogent argument in support of the claim that even though the solution identified by equations (1) and (2) look different, they are in effect the same.

𝜆” = , 𝜆) = 0
𝑎 = 9, 𝑏 =

(f) Show that if add the constraints
in addition to those already in the requirement that Ax = y as described in problem 1, there can be only one solution to the combined set of equations/constraints.

Because the rank of (A | y) is 5, which is the number of unknown variables. There is only one solution to this equation.

(a) The triangular distribution has a probability density function

In three/four sentences describe how you can generate i.i.d. r.v’s that are distributed according to equation 3.

First, you should find a formula for the quantile function 𝐹45″. Then, you need generate a uniform random number 𝑢. Via Inverse Transform Method, we can return the random number 𝑥 =
𝐹45″(𝑢)
𝑥 (0 ≤ 𝑥 ≤ 1)
2 − 𝑥 (1 ≤ 𝑥 ≤ 2)
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
𝑥)
(0 ≤ 𝑥 ≤ 1)
2
𝐹 𝑥 = 1 − 2 − 𝑥 ) (1 ≤ 𝑥 ≤ 2)
2
0 (𝑥 < 0)
1 (𝑥 > 2)

(b) What is the i.i.d. distribution generated by repeated calls to the code shown below?

1 (𝑥 ≥ 2)
(𝑥 − 1)) (1 ≤ 𝑥 ≤ 2)
𝐹(𝑥) =
1 − 𝑥 − 1 ) 0 ≤ 𝑥 ≤ 1
0 (𝑥 ≤ 0)

(c) What is the i.i.d. distribution generated by repeated calls to the code shown below?

3. General Programming Concepts:

(a) Consider the two versions of the code shown in figure 1. Sup- pose I type the string “kablooey” as input, give me the reasoning behind the output each of the programs generate 1 . This is a straightforward exercise in programming.

Version 1 (LHS):
It will return the same string as input ‘kablooey’. The reason is that even there is recursion in the program. It will output first then re-call the function again. So it will return every character in the input string first, then use the rest of characters to call f() again.

Version 2 (RHS):
It will return the reverse order of the input string – ‘yeoolbak’. This function is different from the LHS one. Because it calls itself first so it will kind of calling a stack to save each character then when it is done, output each character in the stack. So it will return the reverse order of the input string.

The greatest common divisor (GCD) of two positive numbers m and n is the largest number k that divides m and n. That is, m/k and n/k leaves no remainder. Consider the C++ code shown in figure 2. Using the fact that the GCD of two numbers does not change if the smaller number is subtracted from the larger number, show that the recursive funtion gcd(m, n) in the code shown in figure 2 implements the GCD computation.
(Note: Please do not give me an illustrative example as a “proof” of that the code does what it is supposed to do. I am looking for a rigorous attempt at showing the correctness of the code for any pair of numbers.)

Proof:
The case n = m is clear.

Every time, n-m (or m-n) can be written like n-qm. Assume that at least one of n and m is nonzero. Now gcd(n, m) divides n, m and n − qm, hence
gcd(n, m) ≤ gcd(m, n − qm).
On the other hand, gcd(m, n − qm) divides m, n − qm and n = (n − qm) + qm. so
gcd(m, n − qm) ≤ gcd(n, m).
So, in every recursion, it will give the right answer because gcd(m, n − qm) = gcd(n, m) at the end.

What is the output of the C++ code shown in figure 3. Make sure you give me your reasoning for your answer.

What is the output of the above program? What is the reasoning behind the output that this program generates?

Output: ‘EDCB’

Reason:
It recursively call the function print_integer() and every time it is devided by 10. So argument in print_integer() function is devided by 10 every time and leaves the digit behind point.
num % 10 + ‘A’ means that extract the last digit in num and add it to the ASCII number of character ‘A’ so we will get B, C, D, E, F and G etc..

My review of computing contains the Frame-Stewart solution to the k-peg version of the Tower of Hanoi problem. Consider the following solution to the 4-peg version of the problem.

Comment on the correctness of this algorithm. Will this work?

Code performance result as below:

no_of_disks = 3
Move the top disk from pegA to pegB
Move the top disk from pegA to pegC
Move the top disk from pegA to pegD
Move the top disk from pegC to pegD
Move the top disk from pegB to pegD

no_of_disks = 4
Move the top disk from pegA to pegD
Move the top disk from pegA to pegB
Move the top disk from pegD to pegB
Move the top disk from pegA to pegC
Move the top disk from pegA to pegD
Move the top disk from pegC to pegD
Move the top disk from pegB to pegA
Move the top disk from pegB to pegD
Move the top disk from pegA to pegD -> illegal here

no_of_disks = 5
Move the top disk from pegA to pegD
Move the top disk from pegA to pegB
Move the top disk from pegD to pegB
Move the top disk from pegA to pegB
Move the top disk from pegA to pegC
Move the top disk from pegB to pegC
Move the top disk from pegA to pegD
Move the top disk from pegC to pegA

Move the top disk from pegC to pegD Move the top disk from pegA to pegD
Move the top disk from pegB to pegA
Move the top disk from pegB to pegD
Move the top disk from pegA to pegD

no_of_disks = 6 Move the top disk from pegA to pegC Move the top disk from pegA to pegD
Move the top disk from pegA to pegB
Move the top disk from pegD to pegB Move the top disk from pegC to pegB
Move the top disk from pegA to pegB
Move the top disk from pegA to pegC Move the top disk from pegB to pegC
Move the top disk from pegA to pegD
Move the top disk from pegC to pegA
Move the top disk from pegC to pegD Move the top disk from pegA to pegD Move the top disk from pegB to pegC
Move the top disk from pegB to pegA
Move the top disk from pegB to pegD Move the top disk from pegA to pegD
Move the top disk from pegC to pegD

no_of_disks = 7 Move the top disk from pegA to pegB
Move the top disk from pegA to pegC Move the top disk from pegB to pegC
Move the top disk from pegA to pegD
Move the top disk from pegA to pegB
Move the top disk from pegD to pegB
Move the top disk from pegC to pegA Move the top disk from pegC to pegB
Move the top disk from pegA to pegB
Move the top disk from pegA to pegB
Move the top disk from pegA to pegC Move the top disk from pegB to pegC
Move the top disk from pegA to pegD
Move the top disk from pegC to pegA
Move the top disk from pegC to pegD Move the top disk from pegA to pegD Move the top disk from pegB to pegD
Move the top disk from pegB to pegC Move the top disk from pegD to pegC
Move the top disk from pegB to pegA
Move the top disk from pegB to pegD Move the top disk from pegA to pegD Move the top disk from pegC to pegB
Move the top disk from pegC to pegD
Move the top disk from pegB to pegD

no_of_disks = 8 Move the top disk from pegA to pegB
Move the top disk from pegA to pegC Move the top disk from pegB to pegC
Move the top disk from pegA to pegD
Move the top disk from pegA to pegB
Move the top disk from pegD to pegB
Move the top disk from pegC to pegA Move the top disk from pegC to pegB
Move the top disk from pegA to pegB Move the top disk from pegA to pegD
Move the top disk from pegA to pegB
Move the top disk from pegA to pegC Move the top disk from pegB to pegC
Move the top disk from pegD to pegC Move the top disk from pegA to pegD Move the top disk from pegC to pegB
Move the top disk from pegC to pegA
Move the top disk from pegC to pegD Move the top disk from pegA to pegD
Move the top disk from pegB to pegD
Move the top disk from pegB to pegD Move the top disk from pegB to pegC
Move the top disk from pegD to pegC
Move the top disk from pegB to pegA
Move the top disk from pegB to pegD Move the top disk from pegA to pegD Move the top disk from pegC to pegB
Move the top disk from pegC to pegD
Move the top disk from pegB to pegD

no_of_disks = 9 Move the top disk from pegA to pegB Move the top disk from pegA to pegC Move the top disk from pegB to pegC
Move the top disk from pegA to pegC Move the top disk from pegA to pegD Move the top disk from pegC to pegD Move the top disk from pegA to pegB Move the top disk from pegD to pegA
Move the top disk from pegD to pegB
Move the top disk from pegA to pegB Move the top disk from pegC to pegA
Move the top disk from pegC to pegB
Move the top disk from pegA to pegB Move the top disk from pegA to pegD
Move the top disk from pegA to pegB
Move the top disk from pegA to pegC Move the top disk from pegB to pegC
Move the top disk from pegD to pegC Move the top disk from pegA to pegD Move the top disk from pegC to pegB
Move the top disk from pegC to pegA
Move the top disk from pegC to pegD Move the top disk from pegA to pegD
Move the top disk from pegB to pegD
Move the top disk from pegB to pegD Move the top disk from pegB to pegC Move the top disk from pegD to pegC Move the top disk from pegB to pegC
Move the top disk from pegB to pegA
Move the top disk from pegC to pegA
Move the top disk from pegB to pegD
Move the top disk from pegA to pegB Move the top disk from pegA to pegD Move the top disk from pegB to pegD Move the top disk from pegC to pegB
Move the top disk from pegC to pegD
Move the top disk from pegB to pegD

no_of_disks = 10 Move the top disk from pegA to pegD
Move the top disk from pegA to pegB
Move the top disk from pegA to pegC Move the top disk from pegB to pegC
Move the top disk from pegD to pegC
Move the top disk from pegA to pegC Move the top disk from pegA to pegD Move the top disk from pegC to pegD Move the top disk from pegA to pegB Move the top disk from pegD to pegA
Move the top disk from pegD to pegB
Move the top disk from pegA to pegB Move the top disk from pegC to pegD Move the top disk from pegC to pegA Move the top disk from pegC to pegB
Move the top disk from pegA to pegB
Move the top disk from pegD to pegB Move the top disk from pegA to pegD
Move the top disk from pegA to pegB
Move the top disk from pegA to pegC Move the top disk from pegB to pegC
Move the top disk from pegD to pegC
Move the top disk from pegA to pegD
Move the top disk from pegC to pegB
Move the top disk from pegC to pegA
Move the top disk from pegC to pegD
Move the top disk from pegA to pegD
Move the top disk from pegB to pegD
Move the top disk from pegB to pegA
Move the top disk from pegB to pegD Move the top disk from pegB to pegC
Move the top disk from pegD to pegC
Move the top disk from pegA to pegC Move the top disk from pegB to pegC
Move the top disk from pegB to pegA
Move the top disk from pegC to pegA
Move the top disk from pegB to pegD
Move the top disk from pegA to pegB
Move the top disk from pegA to pegD
Move the top disk from pegB to pegD
Move the top disk from pegC to pegA Move the top disk from pegC to pegB
Move the top disk from pegC to pegD
Move the top disk from pegB to pegD
Move the top disk from pegA to pegD

There exists some illegal move from peg to peg (large disk on small disk), so this solution is not correct.