Advanced Data Structure and Algorithms

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

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

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

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

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

7COM1028 Secure Systems Programming Referral Coursework: Secure

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

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

Get Free Quote!

261 Experts Online