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

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme