## Cloud Computing, Homeworks for the course CS 5354/CS 4365, Spring 2015

1. (Due January 29) Prepare a proposal for a class project.

2. (Due January 29) Solve the following constraint optimization problem: minimize the expression (x − 1)2 + (y − 1)2 under the constraint x2 + y2 =1.

3. (Due February 3) Write a program that, given two arrays x = (x1, ..., xn) and y = (y1, ..., yn), uses the Least Squares method that estimates m and b for which yi ~ m * xi + b for all i. Test your program, first by using the exact values yi = m * xi + b, and then by adding a small random noise to the values yi. Submit a printout of the program and the printout of the testing results.

Reminder: The Least Squares method leads to the following formula for estimating m: m = (x * yx * y) / (x2 - (x)2), where:

• x = (x1 + ... + xn) / n,
• y = (y1 + ... + yn) / n,
• x * y = (x1 * y1+ ... + xn * yn) / n, and
• x2 = ((x1)2 + ... + (xn)2) / n.
Once we found m, we can estimate b as b = y − m * x.

4. (Due February 5) Write two programs that, given two arrays x = (x1, ..., xn) and y = (y1, ..., yn), estimates the parameters of, correspondingly, the exponential law y = A * exp(k * x) and power law y = A * xα (by reducing the estimation problem to the case of a linear dependence).

By February 12: please test your programs to make sure that it is correct, and deliver the testing results. To test your program, you need to first pick some A and k (or, for power law, A and α), pick any xi, generate corresponding yi, then apply your mail program and check that you get the same values A and k (or A and α) back:

• First, do it for the values yi which describe exactly the related model. In this case, you should get the exact values A and k (or A and α).
• Second, add small random noise to the values yi. In this case, you should get values close to the original ones.

5. (Due February 12) Write a program that, given three integers m, e, and n, computes me mod n, by using the corresponding part of the RSA algorithm.

6. (Due February 17) Write a program that, given two numbers a and b, computes their greatest common divisor.

7. (Due February 17) Write a program that, given two numbers φ(n) and e for which gcd(e, φ(n)) = 1, returns the value d for which d * e = 1 mod φ(n).

8. (Due February 17) Show, step by step, how you can parallelize multiplication of two 2 x 2 matrices if you have enough processors.

9. (Due February 19) Combine your RSA-related programs into a single package consisting of three methods:

• the first method, given two prime numbers p and q, should return n, e, and d; to find e, use a while loop, namely, generate random values e from 0 to φ(n) until you find e for which gcd(e, φ(n)) = 1;
• the second method should use the public code (i.e., n and e) to encode a given message;
• the third method should use the encoded message and the value n and d to decode this message.
Check your package by showing, on some non-trivial example (use larger prime numbers than 3 and 7) that you get the original message back.

10. (Due February 26; extra credit if turned in by February 24) Write a program that uses fuzzy methodology that we discussed in class -- based on the handout. This program should, given a difference in temperatures Δt, compute the appropriate control value u. Make this program modular: use separate methods

• for computing the values of the membership function N(x) corresponding to negligible,
• for computing the values of the membership function SP(x) corresponding to small positive,
• for computing the values of the membership function SN(x) corresponding to small negative,
• for an and-operation,
• for an or-operation, and
• for computing the degree R(u, Δt) to which the control value u is reasonable for a given value of the temperature difference Δt.

11. (Due March 19; extra credit if turned in by March 17) Write a program that simulates a simple 3-layer back-propagation neural network and how this network can learn.

• In the first layer, we have K non-linear neurons. Each neuron k (k = 1, 2, ..., K) transforms the input signals x1, ..., xn into a signal
yk = s0(wk1 * x1 + ... + wkn * xn − wk0),
where s0(z) = 1 / (1 + exp(−z)).
• The last linear neuron then transform these signals yk into a single output
y = W1 * y1 + ... + WK * yK − W0.
For each pattern with the known desired output Y, once the NN computed the input y, you can find the error Δy = y − Y. Based on this error, you can compute the changes to all the weights as follows:
• ΔW0 = α * Δ y, for some small number α > 0;
• ΔWk = − yk * ΔW0;
• Δwk0 = − ΔWk * Wk * (1 − yk);
• Δwki = − xi * Δwk0.

12. (Due March 31) Report on the progress of your project.

13. (Due March 31) Sign for amazon.com cloud, learn how to use it.

14. (Due April 9) Estimate the costs and decide whether it is beneficial to sign a contract for T = 3 years. The cost of buying a unit of computations on a year-by-year basis is c0 = 1, the contract offer a discount price c1 = 0.89, the discount rate is q = 0.91, the price of computing decreases yearly by a factor of v = 0.85.

15. (Due April 9) Suppose that a company uses between m = 100 and M = 500 computations. All values between 100 and 500 are equally probable p(x) = const, and computing in the cloud is 4 times more expensive than computing in-house: c0 = 1 and c1 = 4.

• How much computing power x0 should be purchase for in-house computations?
• What is the resulting expected cost?
• Compute the expected costs when we do all the computations in-house and when we do all the computations exceeding m in the cloud, and show that the optimal arrangement indeed saves money.

16. (Due April 14) Let us now assume that every day, the company uses at least m = 500 computations, and the probabilities of different numbers of computations x is described by the power law p(x) = A * x−α, with α = 2.5. Assume that the cost of a unit in-house computation is c0 = 10 money units per computation unit and the cost of computing in the cloud is c1 = 22.5 money units per computation unit.

• How much computing power x0 should be purchase for in-house computations?
• What is the resulting expected cost?
• Compute the expected costs when we do all the computations exceeding m in the cloud, and show that the optimal arrangement indeed saves money.

In these computations, you can use the formulas that we derived in class for the power law case:

• the optimal amount of computing power to purchase is x0 = m * (c1 / c0)1 / (α − 1);
• the resulting expected cost is equal to ((α − 1) / (α − 2)) * c0(α − 2) / (α − 1) * c11 / (α − 1) * m;
• if we do all the computations exceeding m in the cloud, then the resulting cost is m * (c0 + c1 / (α − 2)).

17. (Due April 21) Use some functionality of the Amazon cloud and submit an explanation and a proof (e.g., a screen shot) of what you did.

18. (Due April 21) Follow the general procedure of solving multi-objective optimization problems on a simple example.

• The general procedure is that, if we want to minimize several functions f1(x) --> min, ..., fn(x) --> min, then we select some non-negative weights w1, ..., wn whose sum is 1, and minimize the weighted combination w1 * f1(x) + ... + wn * fn(x).
• The example that we started in class is as follows. We have a CEO with salary s1, and a student with much smaller salary s2. The CEO pays taxes t, and these taxes become a stipend for the student. As a result, the CEO's income is x1 = s1 − t, and the student's income is x2 = s2 + t. We want to minimize inequality, i.e., minimize f1(t) = (x1 − x2)2. We also want to minimize taxes, i.e., minimize f2(t) = t2. Write a general formula for the optimal value of t (and for the resulting incomes x1 and x2) and show how this formula will look like when we assign equal weights to both criteria, i.e., when w1 = w1 = 0.5.