What are the main principles of scan algorithms? That is, what characteristics do they share?
Solution. A scan algorithm makes a single scan over the input. At each point, it remembers the answer for the list scanned so far, plus any additional information needed to update when another list members is looked at. (Sometimes, the answer alone is not enough.)
Describe the main ideas behind greedy algorithms.
Solution. A greedy algorithm concentrates on optimizing locally. It makes decisions without looking ahead, and commits to them.
What problem does Kruskall's algorithm solve?
Solution. Kruskall's algorithm finds a minimal spanning tree of a graph.
Show the Knuth/Morris/Pratt pattern matching machine for pattern aabaabcab.
Solution. Instead of drawing the maching, I will give the failure function (called the prefix function in the book).
| n | F(n) |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 0 |
| 4 | 1 |
| 5 | 2 |
| 6 | 3 |
| 7 | 0 |
| 8 | 1 |
| 9 | 0 |
The period of a string x1...xn is the smallest k > 0 such that x1...xn-k+1 = xk...xn. That is, removing the first k characters yields the same string as removing the last k characters. For example, the period of string abcabcab is 3, since you get abcab both by removing the first 3 characters and by removing the last three characters. (A string with period k is a prefix of a longer string that consists of the same k-character string repeated over and over.) Every string has a period. For example, the period of abc is 3, since you get the same string (the empty string) by removing the first 3 characters and by removing the last 3 characters.
Describe an algorithm to compute the period of a length n
string that runs in time O(n).
Solution:
Suppose that x is a string of length n. To find the period
of x, compute the KMP failure function of x. The period
of x is n - F(n). This is because a periodic
string with period k matches itself when shifted forward
k characters.
Consider a problem where the input is a list of n points in the plane plus one more point called Q. Describe an algorithm to sort the points in clockwise order from Q. If your list of points after sorting is p1,...,pn, and you draw a line segment from Q to each point, then as you go from x1 to x2, ..., to xn, you should see the line segments sweep in a clockwise direction.
Your algorithm should run in time O(n log(n)), assuming arithmetic operations take constant time.
Solution: Any fast comparison algorithm can be used to sort. For example, use mergesort. The only issue is how to compare values. Given points A and B, consider the angle QAB from Q to A then to B. If this is a left turn then B is to the left (counterclockwise) of A, so say that B < A. If the turn is to the right, then say that B > A. If there is no turn then say that A = B: the order does not matter.
This will work as long as you do not consider only one half of the plane at a time. So break the points into those to the right of Q and those to the left of Q. Sort each half separately. Then combine the two sorted lists.
Turn directions can be determined from cross products, as shown in class.
Say that point (u,v) dominates point (x,y) if u > x and v > y. Given a set S of points, you would like to find the largest subset A of S such that no member of A dominates any other member of A. Describe how to use a scan algorithm to solve this problem, provided a preprocessing step is used that sorts the points in S from left to right or from right to left.
Solution: One solution is a scan algorithm that scans the points from left to right. It works like the Graham scan. The algorithm keeps, at each point, a list of the points that do not dominate one another in a stack. To add another point p, just pop all points from the top of the stack that p dominates, and then push p onto the stack.
An alternative algorithm scans from right to left. I have given one algorithm. I will let you think about how the right-to-left scan will work. What should you remember and how should you update what you are remembering when you encounter the next point. Be careful; this algorithm is significantly different from the preceding one because of the asymmetry in the definition of domination.
A heap can be used as a representation of a set of values. One operation on that set is to remove the largest member. If the heap has n members, how long does it take to remove the largest member, and to restore the heap, so that the set is still represented as a heap?
Solution: Performing one update on the heap costs time O(lg(n)) if there are n things in the heap.