CSCI 385 Spring 2023Advanced Data Structures and Algorithms Archived Class

# Homework 2

## Details

1. Do problem 6.2.5 on page 216. Assume A' is upper-triangular and has been augmented with b' as its final column, and that it is indexed in the expected way (e.g. A'[i,j] is the entry in row i and column j). The solution should be placed in a vector x (e.g. x[1] will store the value of x1, etc.)

Hint: Pay careful attention to how you solved systems with 3 or 4 variables. Which variable did you solve for first? How did you find each of the remaining variables? You should realize that the process you followed can be captured by a simple formula.

Do not forget to analyze your algorithm. (Hint: You will need to express it using one or more sums which you will then need to simplify.)

2. Solve problem 6.6.11b on page 249 by reducing to a graph problem. Please do this problem on your own! I know that it is easy to find solutions for this one online, but you won't learn much by using one of those and you risk failing the assignment (unless you give credit, in which case the 1/2-credit policy applies).