CSCE221- Homework 1 Solved

. (10 points) 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.

(5 points) 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.
(10 points) 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.

(5 points) Tabulate the number of comparisons to find the target in each range.
(5 points) Plot the number of comparisons to find a target where the vector size n = 2k, k = 1,2, . . . ,11 in each increasing/decreasing case. You can use any graphical package (including a spreadsheet).
Just to clarify, I got the same number of comparisons on both cases. One graph is plotted on top of the other one. This is due to the fact that I am using two different binary search algorithms that are executed whenever I have a decreasing or increasing vector.

(a) (5 points) 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.

(5 points) 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 2k −1, k = 1,2,3, . . . ,11.
operator to find the value faster.

(5 points) Use Big-O asymptotic notation to classify this algorithm and justify your answer.
(10 points) (R-4.7 p. 185) The number of operations executed by algorithms A and B is 8nlogn and 2n2, respectively. Determine n0 such that A is better than B for n ≥ n0.
(10 points) (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?
.

(10 points) (R-4.39 p. 188) Al and Bob are arguing about their algorithms.Al claims his O(nlogn)time method is always faster than Bob’s O( n2)-time method. To settle the issue, they perform a set of experiments. To Al’s dismay, they find that if n < 100, the O(n2)-time algorithm runs faster, and only when n ≥100 then the O(nlogn)-time one is better. Explain how this is possible.
(20 points) 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.