Midterm 1 (March 3, 2005)
Names:
Student ID:
Email:
Don’t panic!
Print your name, student id, and email in the box above, and print your name on top of every page.
Please write your answers on the front of the exam pages. Use the back of the page as scratch paper. Let us know if you need more paper.
Read the entire exam before writing anything.
Make sure you understand what the questions are asking.
If you give a beautiful answer to the wrong question,
You’ll get no credit. If any question is unclear, please ask me for clarification.
Don’t spend too much time on any single problem (unless you solved all but one)
If you get stuck, move on to something else and come back later.
Write something down for every problem.
Don’t panic and erase large chunks of work.
It might be worth partial credit.
Don’t panic!
Problem Score
1
2
3
4
5
1. Multiple Choices (some questions may have more than one correct answer, you should try to mark them all) [Each question 4 points: total 12 points]
1. Which of the following equations are true
a.
b.
c.
d.
2. Which of the following subsets of R3 are actually subspaces?
- the plane of vectors with .
- the plane of vectors with .
- the vectors with
- all vectors that satisfy .
3. Which of these rules gives a correct definition of the rank of A.
a.The number of nonzero rows in R, where R is the reduced Echelon
matrix for A
b.The number of columns minus the total number of rows
c.The number of columns minus the number of free columns
d.The number of 1's in the matrix R
Problem 2. [ 13 points] True or False and Justify
Circle T or F for each of the following statements to indicate whether the statement is true or false, respectively. If the statement is correct, briefly state why. If the statement is wrong, explain why or provide a counter example. The more content you provide in your justification, the higher your grade, but be brief. Your justification or explanation is worth more points than the true or false designation. Each statement is typically worth different amount of points depending on its difficulty.
T F [ 1 point for T-F, 2 points for explanation]
The dot product does not always equal ?
T F [ 1 point for T-F, 2 points for explanation]
Assume u and v are two vectors in 5000000 dimensions. Then if u and v are perpendicular to each other, then .
T F [1 point for T-F, 2 points for explanation]
The inverse of an n by n matrix can be computed in steps.
T F [ 1 point for T-F, 3 points for explanation]
In 5 dimensions, there exist two vectors v and w such that
Problem 2: [35 total points] [Computation Problems]
a. [5 points] Give the affine combination of the plane passing through points
b.[5 points] How long is the vector in 2500 dimensions?
c. [10 points] Give the 5 by 5 permutation matrix P such that for any 5 by 5 matrix A, PA permutes the rows of A as: rows 1 to row 3, row 2 to row 4, row 3 to row 5, row 4 to row 2, and row 5 to row 1.
d.[15 points] Compute the Nullspace matrix of
Problem 4. [Math] [20 points]
a. [10 points] Prove the following statement: Suppose B is an m by n matrix and A is a symmetric m by m matrix. Then BT A B is symmetric.
b[10 points] If ||v|| = 7 and ||w|| = 3, what are the smallest and largest values of ||v-w||? Give an example for each case.
Problem 5 [Algorithm]: [20 points]
[One-dimensional 7 nearest neighbor problem]
Design an algorithm for the following problem: The input of the problem is an array of n integers. The desirable output of the problem is: for every number an array that consists of the 7 nearest numbers of .
(a) [8 points] You can earn up to 8 points for giving an algorithm that runs in time. Argue why your algorithm takes time.
(b)[12 points] You can earn up to another 12 points for giving an algorithm that runs in time. Argue why your algorithm takes time
(Hint: you can assume that sorting n numbers can be performed in time.)
In both (a) and (b) you can specify your algorithm in English rather than pseudo-code.