Week 8: Optional Exercises

1. Condition Count

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).

2. Array Reduce

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[0] + a[1) + a[2]) + …

3. Queue Using Stacks

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?

4. Swap Count

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?

5. Quicksort Depth

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?

6. Iterative Euclid

In class we saw a recursive implementation of Euclid’s algorithm. Rewrite it iteratively.

7. Rational Type

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.