Next: About this document ...

# CS130N Problem set 3: Some Data structures + Algorithms

Sparse polynomials:
A polynomial is called dense if almost all the coefficients are non-zero. If the number of nonzero coefficients is much smaller than the largest degree then the polynomial is sparse. The most natural representation of a sparse polynomial is as a sorted list of pairs (ai,ji) of nonzero coefficients and the corresponding powers of x. While algorithms for addition and multiplication of dense polynomials can be similar to those for big numbers, sparse polynomials need to be handled differently (why?). Develop algorithms for computing addition, multiplication and division (reciprocal) of sparse polynomials.
Sparse matrices:
A matrix is sparse if most elements of the matrix are zero. We might store a large sparse matrix (to save space) as a list of triples (i,j,value) where (i,j) is a position and value is a non-zero value. We may represent the list in an array A[t,3], where t is an upper bound on the number of non-zero elements. Further, we may maintain the list sorted so that the row numbers are increasing and within a row the column numbers are increasing. Design algorithms to i) transpose a sparse matrix ii) add two sparse matrices and iii) multiply two sparse matrices.
Knight's tour:
Consider a chess board with a knight placed on a square of initial position (x0,y0). Develop an algorithm to determine a covering of the entire board, if there exists one, i.e., to compute a tour of n2 - 1 moves such that every field of the board is visited exactly once.
Stable marriage:
Consider a set A of men and a set B of women. Each man and each woman has stated distinct preferences for their partners. If n couples are chosen such that there exists a man and woman who would both prefer each other to their actual marriage partners then the pairing is said to be unstable (for obvious reasons). If no such pair exists, then the pairing is stable. Develop an algorithm to compute all stable marriage assignments.
FFT multiplication:
Study the Fast Fourier Transform algorithm (tutors please help) and figure out how it can be used for efficient multiplication of big numbers.

Next: About this document ...
Subhashis Banerjee
1/23/2001