Description

3 attachmentsSlide 1 of 3attachment_1attachment_1attachment_2attachment_2attachment_3attachment_3

Unformatted Attachment Preview

CMSC 451 Project 2

Project 2 involves writing an analysis of the results that you obtained in first project. You are to

submit a paper that discusses the results of your analysis. Your paper should include the

following items:

A brief introduction of the sorting algorithm that you have selected and how the two

versions of the algorithm compare including:

o High-level pseudocode for the sorting algorithms

o A Big-Θ analysis of the two versions of the algorithm

o An explanation of your approach to avoiding the problems associated with JVM

warm-up

o A discussion of the critical operation that you chose to count with an explanation

of why you selected it

An analysis of the results of your study, which should include:

o graph of critical operations for both algorithms and one for the execution times

o a comparison of the performance of the two versions of the algorithm

o a comparison of the critical operation results and the actual execution time

measurements

o a discussion of the significance of the coefficient of variance results and how it

reflects the data sensitivity of your algorithm

o how your results compare to your Big-Θ analysis

A conclusion that summarizes the important observations of your study

If for any reason, it was necessary to revise the program you submitted in project 1, the revised

source code should also be included along with the paper.

Grading Rubric

Criteria

Introduction

Meets

100 points

Does Not Meet

0 points

35 points

0 points

Contains a brief description of the

sorting algorithm together with highlevel pseudocode for the algorithm

(10)

Does not contain a brief description of

the sorting algorithm together with

high-level pseudocode for the

algorithm (0)

Contains a correct Big-Θ analysis of

the algorithm (10)

Does not contain a correct Big-Θ

analysis of the algorithm (0)

Contains an explanation of your

approach to avoiding the problems

associated with JVM warm-up (10)

Does not contain an explanation of

your approach to avoiding the

problems associated with JVM warmup (0)

Analysis

Conclusion

Contains a discussion of the critical

operation that you chose to count

with an explanation of why you

selected it (5)

Does not contain a discussion of the

critical operation that you chose to

count with an explanation of why you

selected it (0)

50 points

0 points

Contains a graph of critical

operations and one for the execution

times (20)

Does not contain a graph of critical

operations and one for the execution

times (10)

Contains a comparison of the

performance of the two versions of

the algorithm (5)

Does not contain a comparison of the

performance of the two versions of the

algorithm (0)

Contains a comparison of the critical

operation results and the actual

execution time measurements (10)

Does not contain a comparison of the

critical operation results and the actual

execution time measurements (0)

Contains a discussion of the

significance of the coefficient of

variation results and how it reflects

the data sensitivity of your algorithm

(5)

Contains a discussion of how your

results compare to your Big-Θ

analysis (10)

Does not contain a discussion of the

significance of the coefficient of

variation results and how it reflects the

data sensitivity of your algorithm (0)

15 points

0 points

Contains a conclusion that

summarizes the important

observations of your study (20)

Does not contain a discussion of how

your results compare to your Big-Θ

analysis (0)

Does not contain a conclusion that

summarizes the important

observations of your study (0)

The traveling salesperson problem is a harder problem than Dijkstra’s

single-source shortest path problem. In other words, the typical Greedy

algorithm approach does not work for this problem. It is even harder

than the all-points shortest path algorithm implemented with Floyd’s

algorithm. Give an example of a graph that shows that the path that

would be chosen by relying on shortest-path information by choosing

the closest vertex each time isn’t sufficient to find the shortest circuit.

What makes this problem harder? Why are the straight forward

approaches to this problem exponential?

Purchase answer to see full

attachment

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