Comparing and Contrasting Backtracking and Branch-and-Bound Design Approaches and Sort Algorithms

Backtracking versus Branch-and-Bound design approaches

1) CompareDesigns: Write an essay on 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 your selected 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) Conduct and document the runtime analysis of both algorithms using different data sets (at least 500 elements for each data set; already sorted, sorted in opposite order, and random) and collect at least 5 values of different size for each type of data set

d) Run 3 times each combination and graph the average (using line graph) runtime results for both algorithm and data sets

e) Add code to capture comparison of keys and assignment of records and compare the algorithms’ results. Graph those results.

f) Analyze and document the time complexity for each algorithm. Compare to runtime results and comparison of keys and assignments of records.

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

h) Draw and document 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 case.

i) 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.

j) In the video explain the solution and implementation of each algorithm; show the programs running for one set of data and explain the output; Discuss the conclusions of the experiment and analysis

Note 1: If a program is not in approved programming language (or in different language than previous assignment) or has any syntax error, no points will be awarded for that exercise

Note 2: Submitting wrong files or in the wrong format or corrupted files will not be accepted nor will any re-submission be allowed for any such mistake.

3) CompareSearch: Compare and contrast, in your own words based on what you learned in the class materials, the below algorithms. In your answers make sure to discuss how each of the algorithms work, what are they best used for - in what applications/systems, and how they are similar and/or different from each 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 versus Binary Search Tree with balancing feature

c) Binary Search Tree with balancing feature versus B-tree d) Selection Algorithm 8.5 versus Algorithm 8.6 versus Algorithm 8.7

4) DesignAproaches: For each of the below problem/solution descriptions, indicate which of the five design approaches (Divide and Conquer, Dynamic Programming, Greedy Approach, Backtracking, or Branch-and-Bound) should be used and why. You need to submit a document with the answers and explanation.

a) The problem is non optimization problem that has overlapping sub problems and the sub-problems can be solved recursively.

b) The problem can be divided into smaller unrelated instances and the smaller instances can be solved recursively.

c) The problem is a very large instance for non-optimization problem where we want all possible solutions and it needs to select a sequence of objects from a set to satisfy a criterion.

d) The problem is an optimization problem that can be divided into smaller instances, the smaller instances can be solved recursively, and the smaller instances are related.

e) The optimization problem is a very large instance and it needs to select a sequence of objects from a set to satisfy a criterion.

f) The problem is scheduling problem to determine the best use of resources to make the greatest profit.