Description
IE531: Algorithms for Data Analytics
1. Linear Algebra: (30 points) Consider the following set of linear equations involving six equations in five unknowns x1, x2, . . . , x5.
2 0 0 6 2
1 −1 −1 4 0
2 −2 2 4 0
2 −2 0 6 0
−4 4 −8 −4 0
4 0 −2 14 4
| {z }
A
x1
x2
x3
x4
x5
| {z }
x
=
2
7
18
16
−40
2
| {z }
y
(a) (2 points) Show that there a solution to these equations.
(b) (10 points) Present a general formula for the set of all solutions that satisfy
these equations.
(c) (3 points) Verify the general formula using MATLAB.
(d) (5 points) Show that
−7λ1 − 4λ2 + 8
−7λ1 − 7λ2
1 − λ2
−λ2
−7 + 7λ1 + 7λ2
(1)
and
a
−7a − 7b
−
8
3
a −
7
3
b +
11
3
−
8
3
a −
7
3
b +
8
3
−7 + 7a + 7b
. (2)
are solutions to the equation Ax = y identified earlier.
1
(e) (5 points) 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.
(f) (5 points) Show that if add the constraints
7×4 + x5 = 7
x2 + 2×5 = 7,
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.
2. (30 points) Generating RVs using the Inverse Transform Technique: You
may want to use the various C++ code samples on Compass (along with some
graphing/plotting software) to verify/experiment-with things before you put your
answers down for this problem.
(a) (10 points) The triangular distribution has a probability density function
f(x) =
x 0 ≤ x ≤ 1
2 − x 1 < x ≤ 2
0 otherwise.
(3)
In three/four sentences describe how you can generate i.i.d. r.v’s that are
distributed according to equation 3.
(b) (10 points) What is the i.i.d. distribution generated by repeated calls to the
code shown below?
double blah1( )
{
(double) x = get uniform();
if (x <= 0.5)
return (1 +
√
2x);
else
return (1 −
√
2 − 2x);
}
(c) (10 points) What is the i.i.d. distribution generated by repeated calls to the
code shown below?
double blah2( )
{
(double) x = get uniform();
if (x <= 0.5)
return (2 −
√
1 − 2x);
else
return ( √
2x − 1);
}
2
3. (40 points) General Programming Concepts:
(a) (10 points) Consider the two versions of the code shown in figure 1. Suppose I type the string “kablooey” as input, give me the reasoning behind
the output each of the programs generate1
.
# i n c l u d e
# i n c l u d e
u s i n g name s pace s t d ;
v oi d f ( )
{
c h a r c ;
c i n . g e t ( c ) ;
/ / t h i s l i n e r e a d s c h a r a c t e r ” c ”
i f ( ’ \ n ’ == c )
/ / ’\ n ’ i s ” r e t u r n / n e wli n e ”
r e t u r n ;
c o ut << c ;
f ( ) ;
}
i n t main ( )
{
f ( ) ;
c o ut << e n dl ;
}
(a) Problem 3a(I)
# i n c l u d e
# i n c l u d e
u s i n g name s pace s t d ;
v oi d f ( )
{
c h a r c ;
c i n . g e t ( c ) ;
/ / t h i s l i n e r e a d s c h a r a c t e r ” c ”
i f ( ’ \ n ’ == c )
/ / ’\ n ’ i s ” r e t u r n / n e wli n e ”
r e t u r n ;
f ( ) ;
c o ut << c ;
}
i n t main ( )
{
f ( ) ;
c o ut << e n dl ;
}
(b) Problem 3a(II)
Figure 1: (Two versions of the) Code for problem 3a.
(b) (10 points) 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.)
(c) (10 points) What is the output of the C++ code shown in figure 3. Make
sure you give me your reasoning for your answer.
1
I am looking for an answer that justifies why we get to see the output generated by each of these programs.
3
# i n c l u d e
u s i n g name s pace s t d ;
l o n g gcd ( l o n g m, l o n g n )
{
i f (m == n )
r e t u r n n ;
e l s e i f (m < n )
r e t u r n gcd (m, n−m ) ;
e l s e
r e t u r n gcd (m−n , n ) ;
}
i n t main ( )
{
c o ut << gcd ( 2 5 9 , 1 1 1 ) << e n dl ;
}
Figure 2: Problem 3b.
# i n c l u d e
u s i n g name s pace s t d ;
v oi d p r i n t i n t e g e r ( i n t num )
{
p u t c h a r ( num % 10 + ’A ’ ) ;
i f ( num / 1 0 )
p r i n t i n t e g e r ( num / 1 0 ) ;
}
i n t main ( )
{
p r i n t i n t e g e r ( 1 2 3 4 ) ; c o ut << e n dl ;
}
Figure 3: Problem 3c.
What is the output of the above program? What is the reasoning behind the
output that this program generates?
(d) (10 points) 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.
Alternate Solution to 4-Peg Tower of Hanoi Problem
1: int k = b
√
2 ∗ nc;
2: Move Using Four Pegs (n − k, source, intermediate 1, intermediate 2, destination);
4
3: Move Using Four Pegs (k − 1, source, intermediate 2, destination, intermediate 1);
4: cout << ”Move the top disk from peg ” << source << ” to
peg ” << destination << endl;
5: Move Using Four Pegs (k − 1, intermediate 2, destination,
intermediate 1, source);
6: Move Using Four Pegs (n − k, intermediate 1, destination,
intermediate 2, source);
Comment on the correctness of this algorithm. Will this work? (You
might want to spend a little time thinking about this problem before
you wrote down your answer)
Peg A Peg B Peg C Peg D
Peg A Peg B Peg C Peg D
Initial State
Final State
At no point in the move can a
larger disk sit above a smaller
disk in a peg
5
