Computer Science 3650
Summer 2002
Practice Questions for Exam 2

This is a closed book exam, but you may use one page of prepared notes. Answer all of the questions.

  1. What are the main principles of scan algorithms? That is, what characteristics do they share?

  2. Describe the main ideas behind greedy algorithms.

  3. What problem does Kruskall's algorithm solve?

  4. Show the Knuth/Morris/Pratt pattern matching machine for pattern aabaabcab.

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

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

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

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

    Hint: Use the ability to compute turn directions. How can you compare two points to decide in which order to put them?