Write a function count that can count how many values in an array of integers satisfy an arbitrary condition (for example, how many are odd, or how many are negative).
Write a function reduce that can combine all the elements of an array of integers given a function f that combines two elements. For example, if f adds two numbers, then reduce will add all the elements in the array If f multiplies two numbers, then reduce will multiply all the elements in the array. The function should combine the numbers from left to right. For example, if f is the addition function, then it will compute ((a + a[1) + a) + …
In class we saw two queue implementations: one using a linked list, the other using an array. Build a third queue implementation that implements a queue using two stacks. It should work independently of the underlying stack implementation. Assuming that the underlying stack has push and pop functions that run in constant time, what are the average and worst-case running times of your enqueue and dequeue operations?
Suppose that an array of N integers is sorted in reverse order. Assume that N is even. Exactly how many swaps will occur if we sort the array using bubble sort? Using quicksort?
For an input array of N elements, what is the worst-case stack depth of the quicksort implementation we saw in class as a function of N? Assuming that the compiler implements tail recursion, can you modify the implementation to have an asymptotically smaller maximum stack depth?
In class we saw a recursive implementation of Euclid’s algorithm. Rewrite it iteratively.
Write a type rational representing rational numbers, implementing this interface:
type rational = …
function rat(n, d: integer): rational; // make a rational number
function add(q, r: rational): rational; // add
function sub(q, r: rational): rational; // subtract
function mul(q, r: rational): rational; // multiply
function toString(r: rational): string;
The toString function should convert a rational number to a string in simplified form. For example, it should never generate the string “4/6”; instead, “2/3” would be the string form of this rational value.