CS2223 PROGRAMMING ASSIGNMENT #4 GAUSS-JORDAN ELIMINATION & DYNAMIC PROGRAMMING solved

$35.00

Category: You will receive a download link of the .ZIP file upon Payment

Description

5/5 - (1 vote)

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.