## Description

1. (4 Points) Explain why the ForwardElimination algorithm on page 210 of Levitin fails to provide a solution for:

x1 + x2 + x3 = 6

x1 + x2 + 2×3 = 9

x1 + 2×2 + 3×3 = 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?

2. (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 + 2×3 = 9

2×1 + 2×2 + 3×3 = 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

3. (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 coefficients1

, 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 + 2×2 + x3 + x4 + x5 + x6 + 2×7 + x8 = 0

x1 + x2 + 3×3 + x4 + x5 + 3×6 + x7 + x8 = 0

x1 + x2 + x3 + 4×4 + 4×5 + x6 + x7 + x8 = 0

11×1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 = 20

x1 + x2 + x3 + x4 − x5 − x6 − x7 − x8 = 34

x1 + 2×2 + 3×3 + 4×4 + 5×5 + 6×6 + 7×7 + 8×8 = −51

x1 − x2 + x3 − x4 + x5 − x6 + x7 − x8 = −6

1Note: We may revisit this algorithm later, but for now you can assume that an 8 × 9 array

of reals (or doubles!) will suffice.

4. (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

Row 8 89 70 73 83 90 22 44 92

Row 7 46 23 99 77 10 42 1 72

Row 6 85 52 27 5 94 91 82 62

Row 5 22 93 68 11 56 63 49 35

Row 4 13 78 48 19 78 11 90 94

Row 3 31 5 63 10 32 40 14 13

Row 2 73 38 24 49 18 6 40 74

Row 1 79 71 18 20 34 51 93 65

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:

(a) Bilbo’s starting square,

(b) a representation of his path,

(c) the total number of gems collected on the way, and

(d) the number of the vault wherein the King has secreted the Arkenstone.