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.
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 monotonic, 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?