Your All-in-One AI-Powered Toolkit for Academic Success.

Available 24*7 on WhatsApp / Email

Unlock your academic potential

© 2024 | Zucol Services PVT LTD | All rights reserved.

Added on 2019/09/18

|6

|491

|172

Homework Assignment

AI Summary

This homework assignment is for CS 4120/5120 Spring 2017, and it consists of 11 problems related to recursion, sorting, and heap operations. Problems include drawing a recursion tree for a given recurrence relation, guessing and solving the recurrence using substitution and master methods, implementing Merge-Sort algorithm, designing a 3-way merge sort algorithm, providing a recurrence relation and solving it using the Master Method, showing a given input array as a 'heap' in binary tree form, converting the heap into a maximum-heap, and performing Heapsort on the final maximum-heap.

Your contribution can guide someone’s learning journey. Share your
documents today.

CS 4120/5120 Spring 2017 Homework 2

_______ / 50 points

DUE MONDAY FEBRUARY 13, 2017 7:30PM

Turn in both an electronic copy on Canvas and a printed copy in lecture.

Name ______________________________________

ID ______________________________________

1. [5 pts] Draw the recursion tree (see Fig 2.5, page 38 in the book for an example) for the recurrence:

T(n) = θ(1) if n = 1

= 2T(n/2) + n2 if n > 1

1

_______ / 50 points

DUE MONDAY FEBRUARY 13, 2017 7:30PM

Turn in both an electronic copy on Canvas and a printed copy in lecture.

Name ______________________________________

ID ______________________________________

1. [5 pts] Draw the recursion tree (see Fig 2.5, page 38 in the book for an example) for the recurrence:

T(n) = θ(1) if n = 1

= 2T(n/2) + n2 if n > 1

1

Need help grading? Try our AI Grader for instant feedback on your assignments.

CS 4120/5120 Spring 2017 Homework 2

2. [2 pts] Use the tree from Problem 1 to guess a solution to the recurrence.

3. [5 pts] Use the substitution method to solve the recurrence based on your guess in Problem 2.

4. [5 pts] Use the Master Method to solve the recurrence in Problem 1.

2

2. [2 pts] Use the tree from Problem 1 to guess a solution to the recurrence.

3. [5 pts] Use the substitution method to solve the recurrence based on your guess in Problem 2.

4. [5 pts] Use the Master Method to solve the recurrence in Problem 1.

2

CS 4120/5120 Spring 2017 Homework 2

5. [5 pts] Use MERGE-SORT algorithm (available on Page 34 in textbook) to sort the following list:

5 8 2 1 6 6 4 2 3

Show the steps (One example is illustrated in Fig 2.4 on Page 35 in the textbook).

3

5. [5 pts] Use MERGE-SORT algorithm (available on Page 34 in textbook) to sort the following list:

5 8 2 1 6 6 4 2 3

Show the steps (One example is illustrated in Fig 2.4 on Page 35 in the textbook).

3

CS 4120/5120 Spring 2017 Homework 2

6. [7 pts] Design a 3-way merge sort algorithm, which divides the given array into three equal parts,

recursively sorts each part, then merges the results. In the main MergeSort3(A,p,r) algorithm,

you may assume the existence of an appropriate Merge3(A,p,q1,q2,r) linear-time ((n))

algorithm. Provide the pseudocode for the main algorithm (but not for the Merge3 helper). Don't forget

to properly handle the base case!

MergeSort3(A,p,r)

7. [3 pts] Give a recurrence relation T(n) for your solution to Problem 6.

8. [3 pts] Use the Master Method to solve the recurrence you gave in Problem 7.

4

6. [7 pts] Design a 3-way merge sort algorithm, which divides the given array into three equal parts,

recursively sorts each part, then merges the results. In the main MergeSort3(A,p,r) algorithm,

you may assume the existence of an appropriate Merge3(A,p,q1,q2,r) linear-time ((n))

algorithm. Provide the pseudocode for the main algorithm (but not for the Merge3 helper). Don't forget

to properly handle the base case!

MergeSort3(A,p,r)

7. [3 pts] Give a recurrence relation T(n) for your solution to Problem 6.

8. [3 pts] Use the Master Method to solve the recurrence you gave in Problem 7.

4

Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser

CS 4120/5120 Spring 2017 Homework 2

9. [3 pts] Given the following input array [40, 10, 30, 80, 5, 60] show as a “heap” (in binary tree form).

Note that this initial “heap” may not satisfy the max-heap property.

10. [5 pts] Convert the heap in Problem 9 into a maximum-heap. Show each step of BUILD-MAX-HEAP

(including marking the node i in each step, similar to Figure 6.3, page 158).

5

9. [3 pts] Given the following input array [40, 10, 30, 80, 5, 60] show as a “heap” (in binary tree form).

Note that this initial “heap” may not satisfy the max-heap property.

10. [5 pts] Convert the heap in Problem 9 into a maximum-heap. Show each step of BUILD-MAX-HEAP

(including marking the node i in each step, similar to Figure 6.3, page 158).

5

CS 4120/5120 Spring 2017 Homework 2

11. [7 pts] Show HEAPSORT on the final maximum-heap from Problem 9 (i.e., skip line 1 of the algorithm

that calls BUILD-MAX-HEAP). Show each step (including marking the node i in each step, similar to

Figure 6.4, page 161).

6

11. [7 pts] Show HEAPSORT on the final maximum-heap from Problem 9 (i.e., skip line 1 of the algorithm

that calls BUILD-MAX-HEAP). Show each step (including marking the node i in each step, similar to

Figure 6.4, page 161).

6

1 out of 6