Algorithmic Mathematics

Exercise 6.9. Prove that the algorithm InsertSort is correct. This algorithm was introduced at page 76 in connection with the algorithm Echelonize.) Exercise 6.10. Write an algorithm to the following specifications Algorithm Echelon INPUT: W, a finite sequence of n-dimensional vectors, over the same field. OUTPUT: TRUE, if W is in echelon form, FALSE otherwise. Explain what you are doing. Use the notation W = (W1,W2,...), and W. = (W2,1,W2.2, ...), and the operator # to access input data. Assume that the algorithm ldindx and ldterm are available. Decide how ldterm behaves for the zero vector, and design the algorithm accordingly. Exercise 6.11. Write an algorithm to the following specifications Algorithm Subspace INPUT: V, W, where V and W are finite sequences of n-dimensional vectors over the same field. OUTPUT: TRUE, if (V) S (W), FALSE otherwise. Exercise 6.12. Prove that theorem 28 holds also for the algorithm Sift2. Exercise 6.9. Prove that the algorithm InsertSort is correct. This algorithm was introduced at page 76 in connection with the algorithm Echelonize.) Exercise 6.10. Write an algorithm to the following specifications Algorithm Echelon INPUT: W, a finite sequence of n-dimensional vectors, over the same field. OUTPUT: TRUE, if W is in echelon form, FALSE otherwise. Explain what you are doing. Use the notation W = (W1,W2,...), and W. = (W2,1,W2.2, ...), and the operator # to access input data. Assume that the algorithm ldindx and ldterm are available. Decide how ldterm behaves for the zero vector, and design the algorithm accordingly. Exercise 6.11. Write an algorithm to the following specifications Algorithm Subspace INPUT: V, W, where V and W are finite sequences of n-dimensional vectors over the same field. OUTPUT: TRUE, if (V) S (W), FALSE otherwise. Exercise 6.12. Prove that theorem 28 holds also for the algorithm Sift2