$18.99
Homework 1: Review of Linear Algebra, Probability & Statistics and Computing solution
1. You can modify any of the C++ code on Compass to solve these problems, if you want. It might help you with honing your programming skills. If these attempts (at using C++ code) is turning out to to be intense, you can use MATLAB just this once.
2. You will submit a PDF-version of your answers on Compass on-or-before mid- night of the due date.
Instructions
1. Linear Algebra: (30 points) Consider the following set of linear equations in- volving six equations in five unknowns x1 , x2 , . . . , x5 .
2 0 0 6 2 x1
1 1 1 4 0 x2
2 2 2 4 0 x3
2 2 0 6 0 x4
4 4 8 4 0 x5
4 0 2 14 4 x6
(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
a
−7a − 7b
− 8/3 a – 7/3 b + 11/3
8/3 a – 7/3 b + 8/3
−7 + 7a + 7b
are solutions to the equation Ax = y identified earlier.
(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
7x4 + x5 = 7
x2 + 2x5 = 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 equation- s/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
x 0 ≤ x ≤ 1
f (x) = 2 − x 1 < x ≤ 2
(3)
0 otherwise.
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)
else
}
return (1 + √2x);
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)
else
return (2 − √1 − 2x);
2
return ( √
}
x − 1);
3. (40 points) General Programming Concepts:
(a) (10 points) 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 generate1 .
# i n c l u d e < i o s t r e a m
# i n c l u d e < c m a t h
u s i n g n a m e s p a c e s t d ;
v o i 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 w l i n e ”
r e t u r n ;
c o u t << c ;
f ( ) ;
}
i n t m a i n ( )
{
f ( ) ;
c o u t << e n d l ;
}
(a) Problem 3a(I)
# i n c l u d e < i o s t r e a m
# i n c l u d e < c m a t h
u s i n g n a m e s p a c e s t d ;
v o i 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 w l i n e ”
r e t u r n ;
f ( ) ;
c o u t << c ;
}
i n t m a i n ( )
{
f ( ) ;
c o u t << e n d l ;
}
(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 and n
k 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 pro- grams.
# i n c l u d e < i o s t r e a m
u s i n g n a m e s p a c e s t d ;
l o n g g c d ( 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 g c d ( m, n−m ) ;
e l s e
}
r e t u r n g c d ( m−n , n ) ;
i n t m a i n ( )
{
c o u t << g c d ( 2 5 9 , 1 1 1 ) << e n d l ;
}
Figure 2: Problem 3b.
# i n c l u d e < i o s t r e a m
u s i n g n a m e s p a c e s t d ;
v o i 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 % 1 0 + ’A ’ ) ;
i f ( num / 1 0 )
p r i n t i n t e g e r ( num / 1 0 ) ;
}
i n t m a i n ( )
{
p r i n t i n t e g e r ( 1 2 3 4 ) ; c o u t << e n d l ;
}
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, inter- mediate 2, destination);
3: Move Using Four Pegs (k − 1, source, intermediate 2, des- tination, 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 Initial State
At no point in the move can a larger disk sit above a smaller disk in a peg
Final State
Peg A Peg B Peg C Peg D
