Write the dynamic programming code to compute c

Assignment Help Basic Computer Science

Reference no: EM131038629

1. For each recurrence relation below, indicate show and justify its theta class:

a. T(1) = 1; T(n) = 2T(n/2)+5

b. T(1) = 1; T(n) = 2T(n/2) + 2n

c. T(1) = 1; T(n) = T(3n/4) + T(n/6) + 5n

d. Solve the following recurrence T(1) = 1; T(n) = 3T(n/3) + 3

e. Let a and b be real numbers such that 0<a<b. Show that na is in O(nb), but nb is not in O(na).

f. Explain why the best case running time of Insertion Sort is O(n) .

Dynamic Programming

2. Assume k is odd and let O(n,k) be the number of ways to write n as the sum of odd positive integers each at most k but not necessarily distinct. Find a recurrence for O(n,k) and explain it.

3. Consider the following recurrence (given a sequence pi) :
with C[i,i] = 0

a. Draw the table dynamic programming would use to implement this.

b. Write the dynamic programming code to compute C.

Greedy Algorithms

4. In the bin-packing problem, you are given a set of objects with sizes s1, s2, ... ,sn where 0<si<1 (si is the fraction of a box that the ith item will fill). You are to determine to put them in a few boxes of size 1 as possible.

a.Give a greedy strategy for this problem.

b. (What order would you have to process the items in order for your solution to be optimal?

5. Consider the following algorithm. T is a binary tree.
fred(T)
{
if (T is null)
return 0
else return (fred(left child of T) + fred(right child of T)
}

a. Give the recurrence relation for the fred function. You do not need to solve the equation, but remember the basis.

b. What does the function fred do?

Mergeable Heaps

6. Why did Binomial heaps NOT require the mark bits and the rules about losing two children?

7. The H be a fibonacci heap with a B4 and a B5 with the min at the root of the B5. Show the structure that would result from ExtractMin(H).

Applying what we have learned

8. Find the most efficient solution for each of the problems below and analyze its running time. In each case, you are given n points in the plane,

Hint, the distance from the origin to the ith point is
a. Find the smallest circle, centered at the origin, containing all of the points in its interior.

b. Determine whether it is possible to draw a circle centered at the origin containing two or more of the points on its boundary.

c. Given k satisfying 0<=k<=n, find a circle, centered at the origin, such that at most k of the points are in the interior of the circle and at most n-k of the points are in the exterior of the circle.

9. Graph Algorithm Details

a. Define the three types of shortest path problems.

b. Give an example where the shortest path tree from Dijkstra's algorithm is not a minimum spanning tree.

c. Show the DFS forest resulting from running DFS on the graph described by this adjacency list. Label each node with its start and finish times.

1: 2, 5,

2: 1, 3, 5

3: 1, 2, 5

4: 2, 3, 6

5: 1, 2, 3

6: 2, 3, 4

Running Shortest Path Algorithms

10. Show the execution of Prim's algorithm starting at node A on the following graph. Redraw the diagram for each edge that is added (yes, you can write neatly on this entire page)

NP-Completeness

11. Prove that this problem is in NP: Given n, a number of dice, there are at least k ways of rolling a given value, y.

12. Explain exactly what you have to do to prove that a problem is NP-Complete

13. Which of the following statements is true for all problems X and Y in NP such that X is reducible to Y in polynomial time? (T or F after each one - yes, that can be outside of a box)

a. If Y is NP-complete, then X is NP-complete

b. If Y is in P, then X is in P

c. If X is NP-complete, then Y is in P

d. If Y is not in P, then X is not in P

14.We said that if we had a polynomial time solution to an NP-complete problem X, we would have a polynomial-time solution to every problem in NP. Explain the polynomial-time solution for an arbitrary problem Y in NP.

15.If you have to solve a problem that is NP-Complete, what options do you have?

Reference no: EM131038629

Questions Cloud

Describe the rationale the target audience : Research and create a training project that will promote understanding of conflicts cause, impact, parties involved, conflict styles, and strategies for conflict management or resolution.

Calculate the gross regular pay : The spreadsheet has five tabs: Employee, Department, Time Sheets, Deductions, and Deduction Types. On a new sixth tab, calculate the payroll information for the first week of January 2012 (ending 1/7/2012). Do not delete any data on the other five..

Identify the common roles in a human resource project : Identify the common roles in a human resource project. Then, analyze these roles to typical human resource functions and Reorganize any two (2) roles at TriHealth that result in shared responsibilities and then state why you chose those two roles.

Online reading of strategic alliances : Consider the online reading of strategic alliances. What are some other advantages and disadvantages that you can think of as it pertains to strategic alliances?

Write the dynamic programming code to compute c : Assume k is odd and let O(n,k) be the number of ways to write n as the sum of odd positive integers each at most k but not necessarily distinct. Find a recurrence for O(n,k) and explain it.

Identify the possible impacts of the electric car technology : Identify and analyze the possible impacts (political, environmental, health, safety, cultural, economic) of the electric car technology on society (including individual, local, regional, or global context)?

Important differences in level effectiveness : Complete scenario 1 (in addition to scenario 4), provide insights on both scenarios and key differences between them in this reflection (e.g., what were some important differences in level effectiveness between scenario 1 and 4).

Formal orientation programmer : Q1) Does the company have an orientation programmer? Q2) If yes how effective is it? Q3) how is formal Orientation programmer conducted? Q4) If you were Navin what would have you done?

Write a review of a professional engineering journal article : Write a review of a professional engineering journal article. The article should come from a scholarly journal such as the American Society of Civil Engineers.

User Account

All Pages