Description
- (4 Points) Explain why the ForwardElimination algorithm on page 210 of Levitin fails to provide a solution for:
| x1 | + | x2 | + | x3 | = | 6 |
| x1 | + | x2 | + | 2x3 | = | 9 |
| x1 | + | 2x2 | + | 3x3 | = | 14 |
despite the fact that x = (1,2,3) or x1 = 1, x2 = 2, x3 = 3 can be easily verified as a solution to the system.
How does the BetterForwardElimination algorithm on page 211 of Levitin remedy this?
- (6 Points) Explain in some detail why the BetterForwardElimination algorithm on page 211 of Levitin fails to provide a solution for:
| x1 | + | x2 | + | x3 | = | 6 |
| x1 | + | x2 | + | 2x3 | = | 9 |
| 2x1 | + | 2x2 | + | 3x3 | = | 15 |
despite the fact that x = (1,2,3) or x1 = 1, x2 = 2, x3 = 3 can be easily verified as a solution to the system.
What can be done to remedy this shortcoming in the algorithm?
1
- (20 Points) The Gauss-Jordan elimination method differs from Gaussian elimination in that the elements above the main diagonal of the coefficient matrix are made zero at the same time and by the same use of a pivot row as the elements below the main diagonal. Thus, the coefficient matrix is transformed into a diagonal matrix rather than an upper-triangular matrix. Furthermore, if each pivot row is “divided by” its pivot (leading entry) prior to its use as a pivot row, the coefficient matrix is transformed into the identity matrix, and the back substitution step may be dispensed with entirely. That is, the solution x is simply the last column of the (transformed) augmented system matrix.
Modify the BetterForwardElimination algorithm to perform Gauss-Jordan elimination to solve a system of n linear equations in n unknowns with the form Ax = b, where A is an n × n matrix of real coefficients[1], and b is a column vector with n real entries.
Use your algorithm to find the unique solution to the system:
x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 = 0 x1 + 2x2 + x3 + x4 + x5 + x6 + 2x7 + x8 = 0 x1 + x2 + 3x3 + x4 + x5 + 3x6 + x7 + x8 = 0 x1 + x2 + x3 + 4x4 + 4x5 + x6 + x7 + x8 = 0 11x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 = 20 x1 + x2 + x3 + x4 − x5 − x6 − x7 − x8 = 34 x1 + 2x2 + 3x3 + 4x4 + 5x5 + 6x6 + 7x7 + 8x8 = −51 x1 − x2 + x3 − x4 + x5 − x6 + x7 − x8 = −6
- (30 Points) The Dwarf King has locked the Heart of the Mountain, the jewel known as the Arkenstone, in one of the vaults in the deepest treasure room under the Lonely Mountain. The square floor of the room consists of 64 smaller squares, alternating gold and silver. (It is believed that ancient Persians, having discovered the chamber long after the age of Dwarves, were inspired by its beauty to create games played on such a surface.) Upon each square the King has arrayed a varying number of the most wondrous gemstones: emeralds, rubies, sapphires, diamonds, and more, as shown here:
| Vault 1 | Vault 2 | Vault 3 | Vault 4 | Vault 5 | Vault 6 | Vault 7 | Vault 8 |
| 89 | 70 | 73 | 83 | 90 | 22 | 44 | 92 |
| 46 | 23 | 99 | 77 | 10 | 42 | 1 | 72 |
| 85 | 52 | 27 | 5 | 94 | 91 | 82 | 62 |
| 22 | 93 | 68 | 11 | 56 | 63 | 49 | 35 |
| 13 | 78 | 48 | 19 | 78 | 11 | 90 | 94 |
| 31 | 5 | 63 | 10 | 32 | 40 | 14 | 13 |
| 73 | 38 | 24 | 49 | 18 | 6 | 40 | 74 |
| 79 | 71 | 18 | 20 | 34 | 51 | 93 | 65 |
Row 8
Row 7
Row 6
Row 5
Row 4
Row 3
Row 2
Row 1
The vault containing the Arkenstone is sealed with powerful magic which can only be broken by someone who has walked the Most Precious Path. Bilbo Baggins, the Hobbit burglar, having once possessed the Arkenstone, wishes to behold it once again. Devise and implement in C++ a dynamic programming algorithm which will allow Mr. Baggins to collect the greatest number of gemstones given that he:
- begins by collecting the gems on the square of his choice in Row 1, and then moves to
- the square directly ahead of the one he currently occupies, or
- the square (diagonally) ahead and to the left of the one he currently occupies, provided that he is not already against the left wall of the treasure room, or
- the square (diagonally) ahead and to the right of the one he currently occupies, provided that he is not already against the right wall of the treasure room;
- collects the gems from the newly-visited square, and
- repeats this process until,
- he collects gems from a square on Row 8, whereupon the spell sealing the corresponding door will be broken and the vault will yield its treasure if and only if Bilbo has walked the Most Precious Path.
Your output should include:
- Bilbo’s starting square,
- a representation of his path,
- the total number of gems collected on the way, and
- the number of the vault wherein the King has secreted the Arkenstone.
[1] Note: We may revisit this algorithm later, but for now you can assume that an 8 × 9 array of reals (or doubles!) will suffice.
