PYTHON: Runtime Analysis & BST

Assignment 2

Note: Submitting wrong files or in the wrong format or corrupted files or missing files will

not give you permission to re-submit. It is your responsibility to submit all the correct files

on time.

1. Compare: Write 2 page essay, in your own words, comparing and contrasting insertion,

selection, quicksort, mergesort algorithms that we went over in class (max 12-point font).

Diagrams or tables are not included in the length and your comparison must be in the form of

essay. Submit essay as PDF or Word document to be checked by TurnItIn (NOT inside of a

zip/rar file). Note that work which is not written in student’s own words will not earn credit.

Changing words to their synonyms (or running through translation program) is not sufficient

and often changes the meaning of the context or makes it read as garbage because technical

terms are changed incorrectly. Essay that makes no sense and cannot be understood will not

earn credit. The submitted work must be graduate level quality and will be graded as such.

2. Analysis:

a) Write Python code to generate input data for sorting algorithms as follows

 Number of elements: 2000, 4000, 6000, 8000, 10000, 12000

 Types of data: sorted, reverse sorted, random

b) Capture runtime (how long it took to sort):

 Run your input data sets that you generated (18 inputs) through each of the

sorting algorithms provided for this assignment

 Be careful you do not pass the sorted input to the next sort for reverse and

random!!!

 Put all your results in a table

c) In your program graph the runtime results using line graph as follows:

 3 dataset type results for the same algorithm (2 graphs)

 same dataset type for the different algorithms (3 graphs)

 you should have at minimum five graphs

d) Write an analysis report which includes:

 runtime results in a table

 time complexity analysis of each sorting algorithm (code) for best and worst

time complexity

 analysis of the data relative to growth rate (are the results linear, quadratic,

etc.)

 each generated graph and discussion of each graph to include the differences

in performance as shown in the graph and differences in rate of growth

 summary comparing the algorithms and their results relative to the different

data sets based on the individual graph discussion and the worst versus best

case scenarios

 final conclusion of the analysis to include which algorithm seems more

efficient relative to different data set types and why and whether the runtime

results support the time complexity of the algorithms

e) Submit code in one zip/rar file; and analysis report as PDF or Word document to be

checked by TurnItIn (NOT in zip/rar);

3. BST: 1. Using the bst code given for assignment 2 add the following operations:

a) Implement get_by_type bst operation which take as parameter type value and returns a Python list with all the art objects that match that type. The operation

must be self-contained - you cannot add class attributes

b) Implement insertM operation which takes as a parameter a Python list with art objects and inserts the objects into the bst

2. Add test cases to bst-test to demonstrate that the new operations work correctly 3. Write report analyzing the time and space complexity of each of the new operations

for best and worst complexity. Make sure you explain in writing your analysis and

give all the calculations as well as the final rate of growth. A guess of the final rate of

growth time or space complexity (without calculations and explanation) will not earn

any credit

4. Submit all code in a single zip/rar file and time/space complexity analysis in separate pdf/word file to be checked by TurnItIn (not in zip/rar)

Grading Rubric

Points Criteria

20 Compare: The compare and contrast is written in student’s own words in essay format

with introduction/body/conclusion format, represents graduate level depth and

breath, has at least 50% original thought, uses appropriate examples to support

discussion, and does not plagiarize any of the materials

40 Analysis: Correctly implements datasets, experiment, and plotting code

Analysis is submitted as PDF or Word file (not in zip/rar so can be run by

TurnitIn)

Correctly analyzes time complexity of each algorithm

Correctly analyzes the runtime performance of the sort methods for each

graph and discusses how they compare to each other and to best-worst in the

written report

Each graph is analyzes individually and then summarized relative to algorithm

and each data type category

Provides final conclusions in the written report to include whether runtime

results support the time complexities

40 BST: Correctly implements new operations adding to the given bst code

Correctly implements new test cases adding to the given test code

Correctly analyzes in writing the time and space complexity of the external

operations giving details and the final rate of growth value