Review Problems for Prelim I

CS 482 - Spring 2005

Our first prelim takes place on Thursday, Feb 24, from 7:30 to 9:00pm. The exam takes place in two rooms: Olin 155 and Olin 165. Check the course website as we get closer to the exam to see which room to report to.

The exam includes material from lecture and from assigned reading up through Monday, Feb 21.  See the Schedule for the sections of the text assigned for reading (this includes most of Chapters 1 through 6).  Topics include Stable Matching, Basics of Algorithms Analysis, Graphs, Greedy Algorithms, Divide & Conquer, and Dynamic Programming.

The questions below are meant to help you study for the prelim. They will not be collected and they will not be graded. The lecture on Wednesday, Feb 23, is meant to be a review session; this would be a good time to ask about any of these review questions. You are also welcome to ask about these questions during any of the course office hours. The text has many more questions (some easier, some harder) that you are also welcome to ask about.

  1. Problems 1 and 2 of Chapter 1: True or False. If true give a short explanation. If false, give a counter-example.
    1. In every instance of the stable matching problem, there a stable matching containing a pair (m, w) such that m is ranked first in the preference list of w and w is ranked first in the preference list of m.
    2. Consider an instance of the stable matching problem in which there exists a man m and woman w such that m is ranked first on the preference list of w, and w is ranked first on the preference list of m. Then in every stable matching S for this instance, the pair (m, w) belongs to S.
  2. Problem 3 in Chapter 2: Take the following list of functions and arrange them in order of ascending growth rate. That is, if function g(n) immediately follows f(n) in your list then it should be the case that f(n) is O(g(n)).
    n2.5, sqrt(2n), n+10, 10n, 100n, n2 log n
  3. Problem 5 of Chapter 3: A binary tree is a rooted tree in which each node has at most two children. Show by induction that in any binary tree, the number of nodes with two children is exactly one less than the number of leaves.
  4. Problem 2 of Chapter 4: For each of the two statements below, decide whether it is true or false. If it is true, give a short explanation. If it is false, give a counter-example.
    1. Suppose we are given an instance of the MST problem on a graph G, with edge costs that are all positive and distinct.  Let T be the MST for this instance. Now suppose we replace each edge cost c by its square c2, thereby creating a new instance of the problem with the same graph, but different costs.  True or false? --- T must still be an MST for this instance.
    2. Same idea, but now we're solving a shortest s-t path problem on the graph G. Let P be the shortest s-t path on the original graph. True or false? --- P must still be a minimum-cost s-t path for the graph with modified costs.
  5. Problem 6 of Chapter 5: Consider an n-node binary tree T, where n = 2d - 1 for some d...
  6. Problem 1 of Chapter 6: Let G = (V, E) be an undirected graph with n nodes. Recall that a subset of the nodes is called an independent set if ...