Next: About this document ...
Data Structures (CS130N) Minor I Feb 6, 2001
Name: Entry: Grp:
Note:
Maximum marks : 60 (a mark a minute). Answer only in the space provided.
3 pages in all.
- 1.
- An ordered binary tree of size n is a tree of n nodes labelled
that has as inorder traversal. Set up
a recurrence to count the number of distinct ordered binary trees
of size n (that is, the number of structurally different
binary trees of n nodes). [10 marks]
- 2.
- Show that two univariate sparse polynomials of sizes m and n,
, in their sorted (according to exponents) list representations (discussed in class) can be multiplied
in time . [15 marks]
- 3.
- (a)
- Write a recursive algorithm to draw markings on a ruler. Given a
parameter n signifying a resolution of 1/2n, you have
to put a mark at every integral point between and 2n,
endpoints not included. The middle mark should be n units high, the
marks in the middle of the left and right halves should be
n-1 units high, and so on.
Assume that a procedure called mark(x,h)
is available which puts a mark of height h at location x.
What is the time complexity? [10 marks]
- (b)
- Remove recursion from the above procedure using a stack.
[10 marks]
- 4.
- Let M be a set of n men and
W be a set of n women. Each man ranks the women from
1 to n and each woman ranks the men from 1 to n.
A pairing is a one-one correspondence of men to women.
A pairing is unstable if there
exists a man and a woman who prefer each other to their actual
marriage partners, otherwise it is stable.
Now consider the following (non-backtracking) strategy for finding
a stable marriage solution (called "man proposes, woman disposes").
Order the men arbitrarily. In each step, the least numbered unengaged
man proposes to the woman he likes most among those who haven't
rejected him so far. The woman accepts the proposal if either she
is unengaged or the new proposal is better than the current one.
Thus, after each step, either a woman is unproposed or is engaged
with exactly one man. This step is repeated until all women are
engaged.
- (a)
- Show that the above algorithm always converges. (Then the
engagements can be converted to marriages!)
[5 marks]
- (b)
- Show that the above always converges to a stable
marriage solution.
[5 marks]
- (c)
- Estimate the number of steps required.
[5 marks]
Next: About this document ...
Subhashis Banerjee
2/15/2001