[Solved] CSCE221-Homework 1

Write a C++ program to implement the Binary Search algorithm for searching a target element in a sorted vector. Your program should keep track of the number of comparisons used to find the target.

• To ensure the correctness of the algorithm the input data should be sorted in ascendingor descending order. An exception should be thrown when an input vector is unsorted.
• Test your program using vectors populated with consecutive (increasing or decreasing) integers in the ranges from 1 to powers of 2, that is, to these numbers:

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048.

Select the target as the last integer in the vector.

• Tabulate the number of comparisons to find the target in each range.

I get the same number of comparisons for the increasing or decreasing values because I created two different binary search algorithms for the increasing or decreasing case.

• Plot the number of comparisons to find a target where the vector size n = 2^k, k = 1,2, . . . ,11 in each increasing/decreasing case. You can use any graphical package (including a spreadsheet).

.

(a) Provide a mathematical formula/function which takes n as an argument, where n is the vector size and returns as its value the number of comparisons.Does your formula match the computed output for a given input? Justify your answer.How can you modify your formula/function if the largest number in a vector is not anexact power of two? Test your program using input in ranges from 1 to 2^k 1, k = 1,2,3, . . . ,11.

• Use Big-O asymptotic notation to classify this algorithm and justify your answer.
• Submit to CSNet an electronic copy of your code and results of all your experiments for grading.

2. (R-4.7 p. 185) The number of operations executed by algorithms A and B is 8nlogn and 2n², respectively. Determine n₀ such that A is better than B for n n₀.
3. (R-4.21 p. 186) Bill has an algorithm, find2D, to find an element x in an n narray A. The algorithm find2D iterates over the rows of A, and calls the algorithm arrayFind, of code fragment 4.5, on each row, until x is found or it has searched all rows of A. What is the worst-case running time of find2D in terms of n? What is the worst-case running time of find2D in terms of N, where N is the total size of A? Would it be correct to say thatfind2D is a linear-time algorithm? Why or why not?

2. (R-4.39 p. 188) Al and Bob are arguing about their algorithms.Al claims his O(nlogn)time method is always faster than Bobs O( n²)-time method. To settle the issue, they perform a set of experiments. To Als dismay, they find that if n < 100, the O(n²)-time algorithm runs faster, and only when n 100 then the O(nlogn)-time one is better. Explain how this is possible.

1. Find the running time functions for the algorithms below and write their classification using Big-O asymptotic notation. The running time function should provide a formula on the number of operations performed on the variable s.