CSCI 385 Spring 2023
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook
Homework

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

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).