Reference no: EM131126233
Assignment : Recursions and Complexity
1. Double Tower of Hanoi contains 2n disks of n different sizes, with two disks of each size. You must move all 2n disks from one peg to another, but you may move only one disk at a time, without putting a larger disk over a smaller one. How many moves does it take to transfer a double tower from one peg to another if disks of equal size are indistinguishable from one another? Find a recurrence relation for the number of moves. Then, solve the recurrence relation.
2. Below is pseudocode for a modified merge sort algorithm. This new algorithm partitions the list into four sublists instead of the usual two:
procedure newmergesort.a[1, ..., n].
input:
output:
if n > 1 then
L1 = merge (newmergesort(a[ 1, ..., |n/4J ), newmergesort.(a[ |n/4J + 1, ..., |n/2J ]
L2 = merge (newmergesort(a[ |n/2J + 1, ..., |3n/4 ], newmergesort a[ |3n/4J + 1, ..., n ])
merge(L1, L2)
Complete the following two problems to determine if it is possible to improve the complexity of merge sort by partitioning the list into more than two lists of smaller sizes.
a) Analyze the worst-case runtime of the new merge sort (you may make reasonable as- sumptions about the length of the list).
b) Compare the complexity of the original merge sort with the complexity of the new merge sort.
3. Solve the following recurrences:
a) T (n) = 7T (n - 1) - 10T (n - 2) for n ≥ 2, T (0) = 2 and T (1) = 1.
b) T (n) = 6T (n - 1) - 8T (n - 2) for n ≥ 2, T (0) = 4 and T (1) = 10.
c) T (n) = T (n - 2) for n ≥ 2, T (0) = 5 and T (1) = -1.
d) T (n) = -4T (n - 1) + 5T (n - 2) for n ≥ 2, T (0) = 2 and T (1) = 8.
|
Describe how the following business transactions
: Describe how the following business transactions affect the three elements of the accounting equation.a. Invested cash in business.b. Received cash for services performed.c. Paid for utilities used in the business.d. Purchased supplies for cash.e. Pu..
|
|
Rhetoric and science final paper assignment
: Your final paper will be a 5-8 page analysis of one document from one of the case studies we have covered this semester. The paper is due by the end of the day on Saturday, July 16.
|
|
How plea bargaining affects the criminal justice process
: As you learned in your readings this week, a vast majority of criminal cases are resolved through plea bargaining. Evaluate when plea bargaining can occur, the ethics of plea bargaining, and how plea bargaining affects the criminal justice process..
|
|
Analyze the worst-case runtime of the new merge sort
: Analyze the worst-case runtime of the new merge sort and compare the complexity of the original merge sort with the complexity of the new merge sort.
|
|
How constitutional right is practically applied to protect
: Explain how the constitutional right is practically applied to protect the individual and/or society as a whole. Provide your personal opinion on the relative strength and/or weakness of this constitutional issue moving forward in the 21st century..
|
|
Mba level human resource management online
: The responses should include answering the main discussion questions, fully, including proper cites as well. If you use citaitons I should be able to look it up to use for reference to understand. The professor requires that the questions be res..
|
|
In what phase of the cell cycle is dna replicated
: In what phase of the cell cycle is DNA replicated? Tendons and Ligaments heal with scar tissue and do not repair completely due to
|
|
Coordinator in the human resources department
: Create a training plan for this Customer Service program and include it in your report. Download this Training Plan Template and use it to provide a framework for the development of your Training Plan.
|