Given a Sequence S of n integers not necessarily positive, MAXIMUM SUM CONSECUTIVE SUBSEQUENCE PROBLEM asks to find a consecutive subsequence of S whose summation is maximized.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

  Advanced Data Structure and Algorithms

1. [30 pt]. In dynamic programming, we derive a recurrence relation for the solution to one subproblem in terms of solutions to other subproblems. To turn this relation into a bottom-up dynamic programming algorithm, we need an order to fill in the solution cells in a table, such that all needed subproblems are solved before solving a subproblem. For each of the following relations, give such a valid traversal order (Describe how the table is filled, in what orders), or if no traversal order is possible for the given relation, briefly justify

(1). A(i, j) = F( A(i, j-1), A(i-1, j-1), A(i-1, j+1) ) [10 pt].

 

(2). A(i, j) = F( A(min{i, j}-1, min{i, j}-1), A(max{i, j}-1, max{i, j}-1) ) [10 pt]. (3). A(i, j) = F( A(i-2, j-2), A(i+2, j+2) ) [10 pt].

 

 

2. [30 pt]. Given a Sequence S of n integers (not necessarily positive), MAXIMUM SUM CONSECUTIVE SUBSEQUENCE PROBLEM asks to find a consecutive subsequence of S whose summation is maximized. For example, for S=<-6, 12, -7, 0, 14, -7, -3>, the maximum sum of 19 is achieved for the subsequence <12, -7, 0, 14>. Note that it is straight-forward to use brute-force to design a O(n3)-time algorithm for this problem by computing the sum for all possible consecutive subsequences. However, your goal is to design a dynamic programming algorithm with better running

• Write and describe a recurrence to structure a dynamic programming algorithm for solving the MAXIMUM SUM CONSECUTIVE SUBSEQUENCE PROBLEM. [15 pt].

 

• Describe and analyze your algorithm based on the recurrence you constructed in (a). [15 pt].

[Note: While there is a solution with Θ(n) running time, Θ(n2) time solution is also worth full credit.]

 

 

3. [30 pt]. You are driving from New York to San Francisco, using one or more rental cars for the trip. Along the way, you will visit cities c1, c2,…cn in order (here, c1 is New York and cn is San Francisco). You have a fee schedule f(i, j) that gives the cost of a rental car that is picked up in city ci and dropped off in city cj, j>i. Note that these costs are arbitrary and possibly non-monotonic; for example, it may cost $200 for a rental from c1 to c2 but only $100 for a rental from c1 to c3. Your goal is to choose a set of rentals that minimize the total cost of your trip. Note that you can rent only one car at a time, and that you can never be without a car. Hence, a solution is a set of non-overlapping rentals that span all

• Give an algorithm to solve the problem. Particularly, write and describe a recurrence to structure a dynamic programming algorithm to solve it. [15 pt].
• Describe and analyze your algorithm based on the recurrence you constructed in (a). [15 pt].

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of