I require assistance with these 2 programming assignments

 

 

IE 332 - Homework #1
Due: Feb 15, 11:59pm Read Carefully. Important!
As outlined in the course syllabus this homework is worth 6% of your final grade. The maximum attainable
mark on this homework is 60. As was also outlined in the syllabus, there is a zero tolerance policy for
any form of academic misconduct. This is an individual assignment.
By electronically uploading this assignment to Blackboard you acknowledge these statements and accept
any repercussions if in any violation of ANY Purdue Academic Misconduct policies. You must upload your
homework on time for it to be graded. No late assignments will be accepted. Only the last uploaded
version of your assignment will be graded. Page i of i IE 332 Homework #1 Due: Feb 15 2016 1. The purpose of this question is to provide insight into how numbers are stored electronically, and how
to translate to/from sequences of bits and the decimal number system.
(a) Converting a binary number to a decimal number is necessary in order for a result obtained from
the CPU to be more easily understand by humans. For binary number B = bn−1 bn−2
. . . b0 , where
Pn−1
i
bi=1,...,n−1 ∈ {0, 1}, the corresponding decimal value is computed according to
i=0 bi 2 . For
0
1
example, if B = 100 then the corresponding decimal value will be computed as 0·2 +0·2 +1·22 = 4.
Convert the following binary numbers to decimal, showing your work.
i. (2 points) 11100000101
ii. (2 points) 110101101
(b) There are different algorithms for converting a decimal number to a binary number. One approach
is based on successively subtracting the largest powers of two until a zero is reached. For each
power, a 1 will appear in the binary notation, otherwise a 0 will appear. For example, consider the
decimal number 44. We know 26 = 64, which means we will need six bits to store the number 44
as a binary number. Then, we proceed as:
1.
2.
3.
4. the
the
the
the largest power of two ≤ 44 is 25 = 32, and subtracting from 44 will be 44 − 32 = 12.
largest power of two ≤ 12 is 23 = 8, and subtracting from 12 will be 4.
largest power of two ≤ 4 is 22 = 4. Subtraction results in 0.
process then terminates with the resulting binary number 101100. Convert the following decimal numbers to binary, and show all of your work.
i. (2 points) 1003
ii. (2 points) 6248
2. (3 points) A common strategy to reduce the execution time of an algorithm is to program it in such a
way that parts of it can be run simultaneously in parallel (i.e., on different CPUs at the same time).
Consider a program that requires 1000 seconds to execute on a single processor CPU where the first 40%
of the code cannot benefit from executing in a parallel. However, the remaining 60% can be parallelized.
What will be the theoretically best total computation time if running on a quad-core CPU?
3. The SIR model is used by epidemiologists to calculate the theoretical number of Susceptible, Infected
and Recovered individuals in a host population during a pandemic. It can be expressed by the following
differential equations due to Kermack and McKendrick in 1927:
dS
dt
dR
dt
dI
dt = −βIS (1) = γI


dS dR
= −
+
dt
dt (2)
(3) where S, I, R represent proportions of individuals in a population of size N , β is the rate at which an
infected person infects a susceptible person, and γ is the rate at which people recover from the disease.
An assumption of this model is that after recovery from the disease the host cannot become susceptible
again. Assume that γ = 0.1, β = 0.6 and that the initial number of infected individuals is ten from a
population size of five million.
You must ONLY use the R programming language for this question. You cannot use any
R simulation or differential equation solver libraries. (a) (6 points) In lecture we discussed the forward Euler method for approximating the solution to the
above system. However, an improvement to that algorithm (given below) typically yields a better
result. Specifically, the calculation is
yˆi+1 = yi + ∆tf (ti , yi )
∆t
(f (ti , yi ) + f (ti+1 , yˆi+1 ))
yi+1 = yi +
2 (4)
(5) Provide an approximation to the system given in Equations (1)-(3) using this alternative approach.
Run the approximation for 100 simulated days in step increments of 1 day by setting ∆t = 1 (i.e.,
t = 0, 1, 2, . . . , 100). Note, each S, I, R value will need to be independently solved (see last semester
A1 for a hint).
(b) (8 points) The SIR model stated above does not consider randomness, which is not realistic. In
this question you will create a Monte Carlo simulation of the the SIR model that accounts for some
real-world randomness. That is, we want to estimate the number of S, I, R at each time point using
a Monte Carlo simulation instead of the numerical method approach used in part (a). In doing
so, each simulation of this model can be thought of as representing a potential outcome that could
happen in the real world (of course only one actually will). By including this stochastic component
it is possible to gain more insight into the variability of disease spread.
At each time point a randomly selected susceptible person remains uninfected if they either avoid
contact with an infected individual or if contact was made then no disease transmission occurred:
if ρ is the probability of contact, then these calculation will be (1 − ρ) and ρ(1 − β), respectively.
Assuming that contacts occur independently of each other, the probability of a susceptible individual
remains uninfected at time t + 1 will be P[not infected] = (1 − ρ + ρ(1 − β))T [t] .
A susceptible individual will either become infected on a given day or not. Hence, the number of
susceptible individuals S(t) that remain susceptible at S(t + 1) will equal the number of individuals
who did not become infected, which can be modeled using a Binomial distribution (useful for
modeling the number of successes in a sequence of “success or fail” events) having parameters S[t]
and 1 − P[not infected], respectively. Similarly, the number of newly recovered individuals from I(t)
to R(t + 1) can also be modeled using a Binomial distribution, where a “success” is equivalent to
a “recovery” and occurs with probability γ.
Create a Monte Carlo simulation according to the above description with ρ ∈ [0.00000015, 0.00000035]
according to a uniform distribution. The code should be wrapped within a function (HINT: let
the function return a matrix with 3 columns corresponding to S, I, R values and each row being
a different time point. You will need to use the rbinom function. The function should not require
more than 15 lines of code.):
MCsir <- function(beta, gamma, rho, initS, initI, timePoints) {
YOUR CODE HERE
}
(c) (3 points) You will create three plots, one for each of S, I, R curves as a function of time. Within
each plot you will show the results from (a) and (b). Specifically, curves from part a (each having
width 3) that correspond to S, I, R will be colored blue, red and green, respectively. You will
also run 10 replications of your simulation from (b), yielding ten realizations of S, I and R values
that will be added to the corresponding plots (each having width of 1 and color gray). Therefore,
each of the three plots should have 11 curves (one from (a) and ten from (b)). Be sure to include
appropriate legend and axes labels. IE 332 Homework #1 Page 2 of 3 4. It is common practice for banks to record account transactions in the chronological order that they were
made. However, it is also common for people to prefer to order their transactions by check number,
versus chronological order. This is essentially a problem of sorting a list initially ordered chronologically
into one sorted by check number, where it is highly likely that the chronologically ordered list is almost
already sorted by check number.
Consider the following sorting algorithm where A is the already chronologically sorted list of transactions:
1:
2:
3:
4:
5:
6:
7:
8:
9: for i = 2 to length(A) do
v = A[i].checknumber
j =i−1
while j > 0 and A[j].checknumber > v do
A[j + 1] = A[j]
j =j−1
end while
A[j + 1] = A[i]
end for (a) (8 points) Using a loop invariant prove that the sorting algorithm is correct.
(b) (2 points) What is the worst-case? Briefly explain.
(c) (4 points) What is a tight bound for the worst-case runtime?
(d) (2 points) What is the best-case? Briefly explain.
(e) (4 points) What is a tight bound for the best-case runtime?
(f) (2 points) Recall the MERGESORT algorithm discussed in lecture. Explain, between MERGESORT and the above sorting algorithm, which you would recommend to perform the reordering
from chronological to check number?
5. Technology influences our lives in many ways; a trend that will surely continue at a staggering pace.
In this Ted Talk from 2011, Kevin Slavin highlights some algorithms that shaped our world. While
watching keep in mind that this talk was given in 2011 and there have been five years of significant
advances. Answer the following questions in the context of this talk:
www.ted.com/talks/kevin slavin how algorithms shape our world
(a) (1 point) Who was he seated next two on his flight?
(b) (1 point) What did they think when a radar detected a flock of birds alongside electronic communications?
(c) (1 point) Approximately how many physicists are on Wall Street?
(d) (1 point) What percentage of United States stock market is algorithm-based?
(e) (1 point) What happened during the flash crash of 2:45?
(f) (1 point) What was the initial and highest price on Amazon of the book “The making of a fly”?
(g) (1 point) What is the name of the most recent (at that time at least) Netflix algorithm?
(h) (1 point) Approximately what percent of movies that are rated is a result of the Netflix algorithm?
(i) (1 point) What is the main quality that algorithms on Wall Street depend on?
(j) (1 point) How many microseconds does it take to click a mouse? IE 332 Homework #1 Page 3 of 3