   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]   