Scribd Logo
Upload

Welcome to Scribd!

  • 344 views

    Tutorial 05

    Uploaded by

    Tussank Gupta
    The document provides instructions and problems for a tutorial on design and analysis of algorithms using dynamic programming. Students are asked to: 1. Find optimal salesman tours and costs for a directed graph. 2. Determine the longest common subsequence of two strings using dynamic programming. 3. Solve an instance of matrix chain multiplication. 4. Prove a formula for the number of different binary trees with n nodes. It also provides additional problems involving algorithms for palindrome subsequences, minimizing gas storage costs, modifying rod cutting to allow fixed cut costs, and computing the nth Fibonacci number using dynamic programming.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Tutorial 05

    Uploaded by

    Tussank Gupta
    344 views2 pages
    The document provides instructions and problems for a tutorial on design and analysis of algorithms using dynamic programming. Students are asked to: 1. Find optimal salesman tours and costs for a directed graph. 2. Determine the longest common subsequence of two strings using dynamic programming. 3. Solve an instance of matrix chain multiplication. 4. Prove a formula for the number of different binary trees with n nodes. It also provides additional problems involving algorithms for palindrome subsequences, minimizing gas storage costs, modifying rod cutting to allow fixed cut costs, and computing the nth Fibonacci number using dynamic programming.

    Original Description:

    tutorial sheet

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides instructions and problems for a tutorial on design and analysis of algorithms using dynamic programming. Students are asked to: 1. Find optimal salesman tours and costs for a directed graph. 2. Determine the longest common subsequence of two strings using dynamic programming. 3. Solve an instance of matrix chain multiplication. 4. Prove a formula for the number of different binary trees with n nodes. It also provides additional problems involving algorithms for palindrome subsequences, minimizing gas storage costs, modifying rod cutting to allow fixed cut costs, and computing the nth Fibonacci number using dynamic programming.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    344 views2 pages

    Tutorial 05

    Uploaded by

    Tussank Gupta
    The document provides instructions and problems for a tutorial on design and analysis of algorithms using dynamic programming. Students are asked to: 1. Find optimal salesman tours and costs for a directed graph. 2. Determine the longest common subsequence of two strings using dynamic programming. 3. Solve an instance of matrix chain multiplication. 4. Prove a formula for the number of different binary trees with n nodes. It also provides additional problems involving algorithms for palindrome subsequences, minimizing gas storage costs, modifying rod cutting to allow fixed cut costs, and computing the nth Fibonacci number using dynamic programming.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Tutorial 5, Design and Analysis of Algorithms, 2020

    Use Dynamic Programming to design the algorithms. Study section 15.1 (Rod
    Cutting) from the textbook to answer questions 7–10.

    1. Find all possible shortest salseman tours and cost for the following instance of the
    Traveling Salseman Problem for a directed K4 graph having the following adjacency
    matrix:  
    0 8 3 6
    2 0 1 5
    4 7 0 9 .
     

    8 2 5 0

    2. Determine a Longest Common Subsequence of < 1, 0, 0, 1, 0, 1, 0, 1, 1, 0 > and <


    0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0 > using the Dynamic Programming Algorithm.

    3. Solve the following instance of the Matrix Chain Multiplication Problem:


    < A1×2 , B2×3 , C3×4 , D4×5 , E5×6 , F6×7 >.

    4. Prove that the number of different binary trees with n nodes is


     
    1 2n
    .
    n+1 n

    5. A palindrome is a nonempty string over some alphabet that reads the same forward
    and backward. Examples of palindromes are all strings of length 1, civic, racecar,
    and aibohphobia (fear of palindromes). Give an efficient algorithm to find the
    longest palindrome that is a subsequence of a given input string. For example, given
    the input character, your algorithm should return carac. What is the running time
    of your algorithm? Show the working of your algorithm on input character.

    6. The owners of an independently operated gas station are faced with the following
    situation. They have a large underground tank in which they store gas; the tank can
    hold up to L gallons at one time. Ordering gas is quite expensive, so they want to
    order relatively rarely. For each order, they need to pay a fixed price P for delivery
    in addition to the cost of the gas ordered. However, it costs c to store a gallon of
    gas for an extra day (l gallons remaining at the end of a day will give extra cost of
    lc), so ordering too much ahead increases the storage cost. They are planning to
    close for a week in the winter, and they want their tank to be empty by the time
    they close. Luckily, based on years of experience, they have accurate projections for
    how much gas they will need each day until this point in time. Assume that there
    are n days left until they close, and they need gi (gi ≤ L) gallons of gas for each of
    the days i = 1, . . . , n. Assume that the tank is empty at the end of day 0. Design
    an efficient algorithm to decide on which days they should place orders, and how
    much to order so as to minimize their total cost. Also find the time complexity of
    the algorithm.

    7. Show, by means of a counterexample, that the following “greedy” strategy does not
    always determine an optimal way to cut rods. Define the density of a rod of length
    i to be pii , that is, its value per inch. The greedy strategy for a rod of length n
    cuts off a first piece of length i, where 1 ≤ i ≤ n, having maximum density. It then
    continues by applying the greedy strategy to the remaining piece of length n − i.

    8. Consider a modification of the rod-cutting problem in which, in addition to a price


    pi for each rod, each cut incurs a fixed cost of c. The revenue associated with a
    solution is now the sum of the prices of the pieces minus the costs of making the
    cuts. Give a dynamic-programming algorithm to solve this modified problem.

    1
    9. Modify MEMOIZED-CUT-ROD to return not only the value but the actual solu-
    tion, too.

    10. The Fibonacci numbers are defined by the following recurrence:



    0,
     for n = 0;
    Fn = 1, for n = 1;

    Fn−1 + Fn−2 , for n ≥ 2.

    Give an O(n)-time dynamic-programming algorithm to compute the n’th Fibonacci


    number. Draw the subproblem graph. How many vertices and edges are in the
    graph?

    You might also like