MATH 1P67: Mathematics for Computer Science Spring 2016

Assignment 3: Recursions and Complexity Due: Wednesday, June 29, at 19:00 (7:00 pm)

1. Double Tower of Hanoi contains 2n disks of n dierent 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 modied merge sort algorithm. This new algorithm partitions the list into four sublists instead of the usual two: procedure newmergesorta[1,...,n] input: output: if n > 1 then L1 = mergenewmergesorta[ 1,...,bn/4c ], newmergesorta[ bn/4c+ 1,...,bn/2c ] L1 = mergenewmergesorta[ bn/2c+ 1,...,b3n/4c ], newmergesorta[ b3n/4c+ 1,...,n ] mergeL1,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 assumptions 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.

 

 

MATH 1P67: Mathematics for Computer Science Spring 2016 Assignment 3: Recursions and Complexity
Due: Wednesday, June 29, at 19:00 (7:00 pm)
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, ..., bn/4c ] , newmergesort a[ bn/4c + 1, ..., bn/2c ]





L1 = merge newmergesort a[ bn/2c + 1, ..., b3n/4c ] , newmergesort a[ b3n/4c + 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 assumptions 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.

• 1492851153-Assignment3.pdf

ComputerScienceExpert

(11)

Status NEW Posted 22 Apr 2017 08:04 AM My Price 9.00

-----------

Attachments

file 1498443018-MATH 1P67 Mathematics.docx preview (527 words )

1-----------)Th-----------e o-----------bje-----------cti-----------ve -----------is -----------to -----------mov-----------e a----------- do-----------ubl-----------e t-----------owe-----------r o-----------f H-----------ano-----------i t-----------hat----------- ha-----------s -----------2n -----------dis-----------ks ----------- Le-----------t u-----------s c-----------ons-----------ide-----------r t-----------hat----------- th-----------e d-----------isk-----------s o-----------f s-----------ame----------- si-----------zes----------- ar-----------e i-----------ndi-----------sti-----------ngu-----------ish-----------abl-----------e. -----------Let----------- An----------- be----------- th-----------e m-----------ini-----------mum----------- nu-----------mbe-----------r o-----------f s-----------tep-----------s r-----------equ-----------ire-----------d t-----------o m-----------ove----------- to-----------wer----------- of----------- Ha-----------noi----------- to----------- t-----------hir-----------d p-----------eg.----------- Le-----------t B-----------n d-----------eno-----------te -----------the----------- mi-----------nim-----------um -----------num-----------ber----------- of----------- st-----------eps----------- re-----------qui-----------red----------- to----------- mo-----------ve -----------the----------- do-----------ubl-----------e t-----------owe-----------r o-----------f H-----------ano-----------i. -----------The-----------n, -----------by -----------rec-----------urr-----------enc-----------e r-----------ela-----------tio-----------n w-----------e h-----------ave----------- B-----------n â-----------‰¤ -----------A2n----------- = -----------22n----------- âˆ-----------’ 1-----------. -----------Als-----------o w-----------e s-----------ee -----------tha-----------t i-----------f w-----------e w-----------ant----------- to----------- mo-----------ve -----------the----------- bi-----------gge-----------st -----------dis-----------ks,----------- th-----------en

Not Rated(0)

• Buy Answer