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 8

Details

  1. (5+2+2+3+2 pts) The Taylor Polynomial of degree n for computing en is given on page 412 (formula 11.6).
    1. Use it to approximate the value of e0.25≈1.28402541669... using a fifth-degree Taylor Polynomial (i.e. ex≈1+x+...+x5/5! )
    2. What is the absolute error of this approximation, to at least 10 decimal places?
    3. What is the relative error of this approximation?
    4. According to formula 11.8 on page 413, what is the maximum value of the expected absolute error?
    5. Is the actual error greater than or less than the expected error? Explain why your answer makes sense.
  2. (10 pts) Apply backtracking to solve the following instance of the subset sum problem: A={2,3,4,7}, d=13
    Clearly show the state-space tree labelled appropriately along with any other relevant work.
  3. (10 pts) Solve the following instance of the knapsack problem using the branch-and-bound algorithm. Make sure to show the state-space tree, including all of the appropriate details in each node, and any other necessary work. You can use either the bound from the book or the one we discussed in class, but clearly state what bound you are using. Clearly state the solution and its value.

    W=15
    ItemWeight Value
    1 7 53
    2 6 49
    3 3 19
    4 8 60
    5 2 14