Week 11: Exercises

1. Recursive Mergesort

Write a procedure mergesort(var p: pnode) that sorts a linked list using mergesort.

2. Number of Moves

Suppose that we sort an array of distinct integers of length N, and that initially the largest integer is at the beginning of the array. How many times will this integer move to a new array position during

1. a bubble sort?

2. an insertion sort?

3. a mergesort?

4. a quicksort, using the Hoare partitioning scheme we discussed in the lecture?

3. Ancestor Check

Write a function isAncestor(p, q: pnode): boolean that takes pointers to two nodes p and q in a binary tree and returns true if p is an ancestor of q.

4. Array to Tree

Write a function that takes an array containing a sorted list of integers and returns a binary search tree containing all the values in the array. The tree should be as balanced as possible, i.e. it should have the minimum possible height.

5. Vertex Reachability

Write a function that takes a graph and two vertex ids v and w, and returns true if there is any path from v to w. Use a recursive depth-first search. If the search discovers w, return true immediately.

6. Shortest Path

Write a function that takes a graph and two vertex ids v and w, and prints a sequence of vertex ids indicating the shortest path from v to w.

7. Overlapping Segments

Write a program that reads four real numbers a, b, c, and d, with a < b and c < d. The program should write 'overlap' if the line segments [a, b] and [c, d] touch or overlap, or 'disjoint' otherwise.

Input:

3 10 8 15

Output:

overlap