605.621 Foundations of Algorithms Spring 2023 Programming Assignment #2
Assigned with Module 3, Due at the end of Module 7
The goals of Programming Assignment 2 are: (1) to have you express your understanding of recursion trees through a program, and (2) to exercise the algorithm analysis techniques you studied in Modules 1 and 2.
This assignment requires you to “construct an algorithm”. There are, of course, many algorithms solving this problem. Some algorithms are asymptotically more efficient than others. Your objectives are to (a) complete the assignment, and (b) submit an asymptotically efficient algorithm.
In this course, critical thinking and problem analysis results in discovering appropriate and better, the best, algorithm for a problem; defining the algorithm in pseudocode; demonstrating (we don’t usually prove) that the algorithm is correct; and determining the asymptotic runtime for the algorithm using one or more of the tools for asymptotic analysis you have studied this semester.
This programming problem is not a collaborative assignment. You are required to follow the Programming Assignment Guidelines and Pseudocode Restrictions (Canvas page Pseudocode Restrictions & Programming Guidelines ) when preparing your solutions to these problems.
Exercising the algorithm you design using one or more example data set(s) removes any doubt from the grader that the algorithm is structurally correct and all computations are correct. When a problem supplies data you are expected to use it to demonstrate that your algorithm is correct.
You are permitted to use Internet resources while solving problems, however complete references must be provided. Please follow the Sheridan Libraries’ citation guidance at “Citing Other Things – HOW DO YOU CITE AN INTERVIEW, A TWEET, OR A PUBLIC WEB PAGE?” and continue to the APA Academic Writer Sample References. Additional example citations are provided at the Purdue University, Purdue Online Writing Lab (OWL), College of Liberal Arts Reference List: Electronic Sources. You can also use training provided by Victoria University Library, Melbourne Australia on Harvard Referencing: Internet/websites
1. Algorithm Requirements
Design an algorithm that generates a recursion tree based on Definition 3.5 Recursion tree rules, contained in the ImprovedRecursionTreeMethod.pdf in Module 2’s Content and included on the PA2 page. In this assignment you will substantially extend the algorithm defined by Definition 3.5.
Definition 3.5 is an algorithm (a step-by-step procedure for solving a specific problem with defined resources) but it is not written the style of our text and is not yet in compliance with the Pseudocode Restrictions. The figures in the ImprovedRecursionTreeMethod.pdf provide a guide to applying this algorithm.
You will augment that algorithm, as necessary, to accept as input the following recurrence function forms: Divide-and-Conquer: T (n) = aT (n/b) + f (n), where constants
– a isanintegersuchthata≥1
– b>1,andbisarationalnumber
– Note you are not being asked to accept T (n) = aT (n/b) + gT (n/h) + f (n) recurrence relations
Chip-and-Be-Conquered: T (n) = aT (n − b) + f (n), where constants – a isanintegersuchthata≥1
– b>0,andbisaninteger
Your algorithm that must accept the following f (n) forms:
polynomial – cnd where
– 0
[20 points] Attributes of your code:
(a) [ 5 points] Code follows a reasonable, consistent style with reasonable documentation, with appropriate use of structures, modularity, error checking
(b) [ 5 points] Trace runs documenting that your program executes correctly.
(c) [10 points] Instrumentation and tests to measure the asymptotic behavior of your program.
[10 points] Analysis comparing your algorithm’s worst-case big-O asymptotic running time to the asymptotic behavior of your program. In this assignment, you must probe your code’s worst-case big-O asymptotic running time not by increasingly larger input length n but by varying the parameters of your recurrence functions and f (n) forms.
(end of the assignment)
程序代写 CS代考 加微信: cstutorcs