Home Page > > Details

Problem 1 [10 points]: In Lecture 10 (file lect 10.pdf) we argued that the Earliest-Finish-Time-First

greedy algorithm does not always work when weights are > 1. Give an example to show that the approach

of selecting the job/interval of least duration from among those that are compatible with previously selected

jobs/jobs does not work either.

Problem 2 [20 points]: Demonstrate how to use the MatrixChain algorithm presented in Lecture 10

(file lect 10b.pdf) to:

• [10 points] Fill table m for a matrix–chain product whose sequence of dimensions is 5, 10, 3, 12, 5, 50, 6.

• [10 points] Demonstrate how to retrieve the optimal parenthesization using table s.

Problem 3 [30 points]: Problem 15-3 (Bitonic Euclidean TSP) in your textbook. For full marks:

• Summarize the problem you are solving

• Describe the algorithm in English and, if helpful, pseudo–code

• Provide at least one worked example or diagram to show more precisely how your algorithm works.

• Prove (or indicate) the correctness of your algorithm.

Problem 4 [40 points]: Suppose you are working in a packaging business, and that you are given n

marbles, and an (arbitrary) number of packages. Your boss has asked you to maximize the total value of

all packages containing at least one marble, minus the cost of packaging, which is i for a package containing

i marbles. You may assume that array A[1 . . . n] is given, such that each entry A[i] ≥ i is the value of a

package containing exactly i marbles.

• [20 points] Describe an efficient algorithm that uses the principle of dynamic programming to package

marbles for a maximum profit.

• [10 points] Argue why your algorithm is correct.

• [10 points] Give a tight (asymptotic) upper bound for the running time of your algorithm and prove

that it is an upper bound for your solution.

1

In the euclidean traveling-salesman problem, we are given a set of n points in the plane, and we wish to find the

shortest closed tour that connects all n points. Figure 15.11(a) shows the solution to a 7-point problem. The general

problem is NP-hard, and its solution is therefore believed to require more than polynomial

time (see Chapter 34).

J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonic tours, that is, tours

that start at the leftmost point, go strictly rightward to the rightmost point, and then go strictly leftward back to the

starting point. Figure 15.11(b) shows the shortest bitonic tour of the same 7 points. In this case, a polynomial-time

algorithm is possible.

Describe an O.n2/-time algorithm for determining an optimal bitonic tour. You may assume that no two points

have the same x-coordinate and that all operations on real numbers take unit time. (Hint: Scan left to right,

maintaining optimal possibilities for the two parts of the tour.)

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Help With Program,Help With Python Pro... 2024-02-19
- Help With Cs2910,Help With C/C++ Progr... 2024-02-19
- Help With Cs 532,Matlab Programminghel... 2024-02-19
- Data Programminghelp With ,Help With P... 2024-02-18
- Programhelp With ,Help With Java/Pytho... 2024-02-18
- Help With Program Programming,Help Wit... 2024-02-18
- Help With Econ 323,C/C++，Java Program... 2024-02-17
- B31se Programminghelp With ,Java，C++ ... 2024-02-17
- Help With Program,Help With Java/Pytho... 2024-02-16
- Help With Ece438,Help With C/C++ Progr... 2024-02-16
- Help With Program,Python Programminghe... 2024-02-16
- Data Programminghelp With ,Python/Java... 2024-02-16
- Help With Cs9053,Help With Java Progra... 2024-02-15
- Help With Comp26020,Help With Java，C+... 2024-02-15
- Help With Csci3280,Python Programmingh... 2024-02-14
- Help With Program,Help With Python/Jav... 2024-02-14
- Help With Ems5730,Help With Python Pro... 2024-02-14
- Help With Cs 211 Programming,Help With... 2024-02-13
- Programhelp With ,Help With Java，C++ ... 2024-02-13
- Prog10065help With ,Help With C++ Prog... 2024-02-13

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2021 www.asgnhelp.com

Programming Assignment Help！