Write a program that reads an integer N and generates a random array of N integers in ascending order. The first number in the array should be 0, and the difference between each pair of consecutive array elements should be a random number from 1 to 10.
Next, the program should generate N new random integers in the range from 0 to 10 · N. The program should count how many of these integers are present in the array, and print this count. Use a binary search for an efficient implementation.
If the input number N is large, what value do you think this program will print, approximately?
Write a program that reads an integer n ≥ 0 and prints the square root of n (if it is an integer), or otherwise 'Not a square'. Do not use any floating-point numbers. Your program should run in O(log n). (Hint: You can solve this problem using a variation of binary search.)
Write a function that takes an array a with N – 1 elements. The array will contain all the integers from 1 .. N in order, except that one integer from that range will be missing. Your function should return the value of the missing integer. It should run in time O(log N) in the worst case.
We know that binary search on an array with N elements runs in a worst-case time of O(log N). Write a program that reads an integer N and outputs the exact maximum number of comparisons that may be performed in a binary search on an array with N elements.
Write a function that takes a list of integers 'a' that is guaranteed to contain a strictly increasing sequence of values followed by a strictly decreasing sequence. For example, the integers might be
4, 8, 10, 20, 37, 50, 52, 48, 7
It's guaranteed that the values will increase at least once and decrease at least once.
Your function should find and return the largest value in the list. It must run in sub-linear time.
Suppose that we have a function f(x) that is defined on all integers and is monotonically non-decreasing, i.e. f(x) ≤ f(y) whenever x < y. (For example, f(x) = x3 is one such function.) Now we are given a value k, and would like to find the smallest value n such that f(n) ≥ k. Write a program that can solve this problem in O(log n) (assuming that f runs in constant time).
Modify our implementation of bubblesort from the lecture so that it will exit immediately if no elements are exchanged on any pass, since in that case there is no more work to be done.
With this improvement, what is the best-case and worst-case running time?
In a selection sort of an array with N elements, what is the maximum number of times that an element might move to a new position?
Suppose that we run a sorting algorithm on an array with N elements that is already sorted. How many array writes will it perform if we use each of the following algorithms?
bubble sort
selection sort
insertion sort
a) Modify our implementation of insertion sort to eliminate the test 'j >= 0' in the inner loop, by first finding the smallest element in the array and moving it into the first position.
b) Perform an experiment to determine whether this change has a signficant effect on the algorithm's worst-case performance.
Suppose that we run an insertion sort on an input array whose values are all 0 or 1. The array contains N values.
a) What array of input values will be the worst case? What will be the worst-case running time?
b) What will be the expected (i.e. average) running time, if the values in the input array are all randomly either 0 or 1?