SJTU – MA280, Spring 2018 Computer Programming and Data Structures
Homework Assignment #6 (due Wednesday, April 25)
1. Write a C/C++ computer program to sort an array of strings (student names) by the
merge-sorting algorithm. A list of student names will be provided in a separate file,
named “sortStudentNames.c”. Please print out the sorted strings.
2. Please write a C/C++ computer program to play the Hanoi game. In your program,
please print out the state after each move for the case that the number of disks is four.
3. Generate a symmetric (square) matrix A = (ai,j)n×n ∈ Rn×n with specified dimensions
n × n (say, n = 8) so that all off-diagonal entries of the matrix are non-positive (i.e.,
ai,j ≤ 0) and randomly distributed on the interval [−1,0] and each diagonal entry ai,i is
positive and equal to one plus the sum of the absolute values of all off-diagonal entries on
the same row, i.e.,
ai,i = 1 +
summationdisplay
1≤j≤n
jnegationslash=i
|ai,j|.
Generate a random vector w ∈ Rn whose entries are randomly distributed on the interval
[−1, 1]. Compute the matrix vector product Aw of A with w and save the resulting vector
as b = (b1, b2, ··· , bn)T ∈ Rn, i.e.,
bi =nsummationdisplay
j=1
ai,jwj for i = 1, 2, ··· , n.
Write a computer program to solve the linear system
Au = b
for the unknown vector u ∈ Rn with the QR method, which is described in the attached
file “QR-method.pdf”. Compute the error of the vectors u and w in the maximum norm,
e = bardblu−wbardbl∞ = max1≤i≤n|ui − wi|.
4. Given a positive integer n > 0 (say, n = 8), let A ∈ Rn×n be a random matrix generated
in the previous exercise. Let u0 ∈ Rn a non-zero vector, whose entries are randomly
distributed on the interval [−1, 1]. For k = 0, 1, 2, ···, repeatedly solve the linear system
Awk = uk,
and normalize the solution
uk+1 = wk/bardblwkbardbl∞
until bardbluk+1 −ukbardbl is less than a pre-specified tolerance ǫ = 10−6. Verify that the vector
uk upon termination is an approximate eigenvector of the matrix A (as a matter of fact,
bardblwkbardbl∞ is an approximation to the minimum eigenvalue of A).