Comparison of Designs, Sorts, and Search Algorithms: A Graduate-Level Analysis

Design Approaches

1) CompareDesigns: Write 1.5-2 page essay (max 12-point font), comparing and contrasting the Backtracking versus Branch-and-Bound design approaches, using your own words. Discuss how they compare to brute-force approach. In addition, discuss the differences and similarities (implementation and performance) between the solution for knapsack problem using Backtracking (Algorithm 5.7) versus Branch and Bound (Algorithm 6.2). The essay needs to be graduate level depth and breadth and at least 50% original thought. Note that work which is not written in student’s own words will not earn credit. Changing words to their synonyms is not sufficient and often changes the meaning of the context or makes it read as garbage because technical terms are changed incorrectly. 

2) CompareSorts: 

a) Implement the Selection Sort (Algorithm 7.2 pp. 292) and Insertion Sort (Algorithm 7.1 pp. 288-289) in Python programming language. 

b) Program files should have your name at the top in a comment, with short description of what is implemented in that program/file. Make sure your file(s) have appropriate names for this exercise. Program should write output to the Console and have hard coded input in main. 

c) In the video explain each of the algorithms and implementations, run the test program and discuss the output. 

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

Use 3 different data sets: random values, already sorted, and sorted in opposite order of at least 2,000-10,000 elements each data set for each sorting algorithms. 

1.That means run for 5 different number of elements for each data set (e.g. 2000, 4000, 6000, 8000, 10000) to compare the runtime and see a growth trend when you graph it. 

2.That means you will have 3 types of datasets (random, sorted, reverse sorted) times 5 different inputs (number of elements) for a total of 15 runtime results for each algorithm. 

e) Graph the results using line graph (a) comparing the 3 dataset type results for the same algorithm to analyze and discuss the differences/similarities of growth rate trend for different input type and how it compares to time complexity (b) comparing the same dataset type for the different algorithms and again analyze and discuss the differences/similarities of growth rate trend for same input but different sorting algorithm and how it compares to time complexity 

f) Add code to capture comparison of keys and assignment of records: 

Graph these results and compare across datasets and algorithms 

1.Compare to runtime results and comparison of keys and assignments of records. 

2.Document runtime data used, how it was generated, and the results (values and graphs) as well as the comparison of time complexity relative to datasets runtime, comparison of keys, and assignment of records. 

g) Document your conclusions based on your experiment discussing impacts of different data sets on performance, time complexity versus runtime complexity, and performance  relative to comparison of keys and assignment of records. Discuss whether your experiment support the time complexity for best-average-worst cases. 

h) Determine and document which algorithm is more appropriate to find the smallest value when algorithm is sorting for increasing order. Explain why the algorithm you chose is more appropriate. 

i) In the video explain the implementation of each algorithm; show the programs running for one set of data and explain the output; 

j) Submit all sorting code in one zip/rar file and analysis report as PDF or Word document to be checked by TurnItIn 

3) CompareSearch: Describe each algorithm and discuss the advantages of using each of the following instead of the other. The short essay answers need to be graduate level depth and breadth and at least 50% original thought. Note that work which is not written in student’s own words will not earn credit. Changing words to their synonyms is not sufficient and often changes the meaning of the context or makes it read as garbage because technical terms are changed incorrectly. 

a) Binary Search versus Interpolation Search (A8.1) 

b) Binary Search Tree with balancing mechanism versus B-tree 

c) Binary Search Tree versus 3-2 tree 

d) Selection Algorithm 8.5 versus Algorithm 8.6 versus Algorithm 8.7