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 x^{2} +
y^{2} =1.

3. (Due February 3) Write a program that, given two arrays
x = (x_{1}, ..., x_{n}) and
y = (y_{1}, ..., y_{n}), uses the Least Squares
method that estimates m and b for which y_{i} ~
m * x_{i} + b for all i. Test your program, first by using
the exact values y_{i} =
m * x_{i} + b, and then by adding a small random noise to
the values y_{i}. 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 * y
− x *
y) /
(x^{2} -
(x)^{2}), where:

- x = (x
_{1}+ ... + x_{n}) / n, - y = (y
_{1}+ ... + y_{n}) / n, - x * y = (x
_{1}* y_{1}+ ... + x_{n}* y_{n}) / n, and - x
^{2}= ((x_{1})^{2}+ ... + (x_{n})^{2}) / n.

4. (Due February 5) Write two programs that, given two arrays
x = (x_{1}, ..., x_{n}) and
y = (y_{1}, ..., y_{n}), 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 x_{i}, generate corresponding y_{i}, 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 y
_{i}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 y
_{i}. 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 m^{e} 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.

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 x
_{1}, ..., x_{n}into a signal

y_{k}= s_{0}(w_{k1}* x_{1}+ ... + w_{kn}* x_{n}− w_{k0}),

where s_{0}(z) = 1 / (1 + exp(−z)). - The last linear neuron then transform these
signals y
_{k}into a single output

y = W_{1}* y_{1}+ ... + W_{K}* y_{K}− W_{0}.

- ΔW
_{0}= α * Δ y, for some small number α > 0; -
ΔW
_{k}= − y_{k}* ΔW_{0}; - Δw
_{k0}= − ΔW_{k}* W_{k}* (1 − y_{k}); - Δw
_{ki}= − x_{i}* Δw_{k0}.

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 c_{0} = 1, the contract
offer a discount price c_{1} = 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: c_{0} = 1 and c_{1} = 4.

- How
much computing power x
_{0}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 c_{0} = 10 money
units per
computation unit and the cost of computing in the cloud is
c_{1} = 22.5 money units per computation unit.

- How
much computing power x
_{0}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
x
_{0}= m * (c_{1}/ c_{0})^{1 / (α − 1)}; - the resulting expected cost is equal to
((α − 1) / (α − 2)) *
c
_{0}^{(α − 2) / (α − 1)}* c_{1}^{1 / (α − 1)}* m; - if we do all the computations exceeding m in the cloud, then
the resulting cost is m * (c
_{0}+ c_{1}/ (α − 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 f
_{1}(x) --> min, ..., f_{n}(x) --> min, then we select some non-negative weights w_{1}, ..., w_{n}whose sum is 1, and minimize the weighted combination w_{1}* f_{1}(x) + ... + w_{n}* f_{n}(x). - The example that we started in class is as follows. We have a CEO
with salary s
_{1}, and a student with much smaller salary s_{2}. The CEO pays taxes t, and these taxes become a stipend for the student. As a result, the CEO's income is x_{1}= s_{1}− t, and the student's income is x_{2}= s_{2}+ t. We want to minimize inequality, i.e., minimize f_{1}(t) = (x_{1}− x_{2})^{2}. We also want to minimize taxes, i.e., minimize f_{2}(t) = t^{2}. Write a general formula for the optimal value of t (and for the resulting incomes x_{1}and x_{2}) and show how this formula will look like when we assign equal weights to both criteria, i.e., when w_{1}= w_{1}= 0.5.