CMSC 451 UMCP Recursive Function Sum Project

Description

2 attachmentsSlide 1 of 2attachment_1attachment_1attachment_2attachment_2

Unformatted Attachment Preview

CMSC 451 Homework 2
1. Given the following two functions:


f(n) = 3n2 + 5
g(n) = 53n + 9
Use L’Hopital’s rule and limits to prove or disprove each of the following:


f  (g)
g  (f)
2. Rank the following functions from lowest asymptotic order to highest. List any two or
more that are of the same order on the same line.










2𝑛
𝑛3 + 5𝑛
log 2 𝑛
𝑛3 + 2𝑛2 + 1
3n
log 3 𝑛
𝑛2 + 5𝑛 + 10
𝑛 log 2 𝑛
10𝑛 + 7
√𝑛
3. Draw the recursion tree when n = 8, where n represents the length of the array, for the
following recursive method:
int sum(int[] array, int first, int last)
{
if (first == last)
return array[first];
int mid = (first + last) / 2;
return sum(array, first, mid) + sum(array, mid + 1, last);
}

Determine a formula that counts the numbers of nodes in the recursion tree.

What is the Big- for execution time?

Determine a formula that expresses the height of the tree.

What is the Big- for memory?

Write an iterative solution for this same problem and compare its efficiency with this
recursive solution.
4. Using the recursive method in problem 3 and assuming n is the length of the array.

Modify the recursion tree from the previous problem to show the amount of work on
each activation and the row sums.

Determine the initial conditions and recurrence equation.

Determine the critical exponent.

Apply the Little Master Theorem to solve that equation.

Explain whether this algorithm optimal.
Grading Rubric
Problem
Problem 1
Problem 2
Meets
10 points
Does Not Meet
0 points
Used L’Hopital’s rule to correctly
determine limits (2)
Did not use L’Hopital’s rule to correctly
determine limits (0)
Provided correct proof or disproof of
Big-Theta relationship (4)
Did not provide correct proof or
disproof of Big-Theta relationship (0)
Provided correct proof or disproof of
Big-Omega relationship (4)
Did not provide correct proof or
disproof of Big-Omega relationship (0)
10 points
0 points
Positioned exponential functions
correctly (2)
Did not position exponential functions
correctly (0)
Positioned polynomial functions
correctly (2)
Did not position polynomial functions
correctly (0)
Positioned constant functions correctly
(2)
Did not position constant functions
correctly (0)
Positioned logarithmic functions
correctly (2)
Did not position logarithmic functions
correctly (0)
Positioned root functions correctly (2)
Did not position root functions
correctly (0)
10 points
Correctly drew recursion tree (2)
0 points
Did not correctly draw recursion tree
(0)
Provided correct formula for number of Did not provide correct formula for
nodes (2)
number of nodes (0)
Problem 3
Provided correct Big-Theta for
execution time (1)
Did not provide correct Big-Theta for
execution time (0)
Provided correct formula for tree
heights (2)
Did not provide correct formula for
tree heights (0)
Provided correct Big-Theta for memory
(1)
Did not provide correct Big-Theta for
memory (0)
Wrote correct iterative solution (1)
Did not write correct iterative solution
(0)
Provided correct comparison of
efficiency of recursive and iterative
solutions (1)
Did not provide correct comparison of
efficiency of recursive and iterative
solutions (0)
10 points
Problem 4
0 points
Correctly drew modified recursion tree
(2)
Did not correctly draw modified
recursion tree (0)
Provided correct initial condition (1)
Did not provide correct initial condition
(0)
Provided correct recurrence equation
(2)
Did not provide correct recurrence
equation (0)
Provided correct critical exponent (1)
Did not provide correct critical
exponent (0)
Correctly applied Little Master
Theorem to correctly solve recurrence
equation (3)
Provided correct explanation of
whether algorithm is optimal (1)
Did not correctly apply Little Master
Theorem to correctly solve recurrence
equation (0)
Did not provide correct explanation of
whether algorithm is optimal (0)

Purchase answer to see full
attachment

Tags:
programming language

asymptotic order

Recursive Function Sum

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.

Reviews, comments, and love from our customers and community:

Article Writing

Keep doing what you do, I am really impressed by the work done.

Alexender

Researcher

PowerPoint Presentation

I am speechless…WoW! Thank you so much!

Stacy V.

Part-time student

Dissertation & Thesis

This was a very well-written paper. Great work fast.

M.H.H. Tony

Student

Annotated Bibliography

I love working with this company. You always go above and beyond and exceed my expectations every time.

Francisca N.

Student

Book Report / Review

I received my order wayyyyyyy sooner than I expected. Couldn’t ask for more.

Mary J.

Student

Essay (Any Type)

On time, perfect paper

Prof. Kate (Ph.D)

Student

Case Study

Awesome! Great papers, and early!

Kaylin Green

Student

Proofreading & Editing

Thank you Dr. Rebecca for editing my essays! She completed my task literally in 3 hours. For sure will work with her again, she is great and follows all instructions

Rebecca L.

Researcher

Critical Thinking / Review

Extremely thorough summary, understanding and examples found for social science readings, with edits made as needed and on time. Transparent

Arnold W.

Customer

Coursework

Perfect!

Joshua W.

Student

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>