CS130 N

DATA STRUCTURES

Work Sheet 3

1.

Given a generalized list, write functions to (a) Replace all occurences of an atomic item, x, in the list, L, with y.

(b) List all the atomic elements that occur in L.

2.

Show how to represent a multi-variate polynomial using generalized lists. Write a program to multiply two multi-variate polynomials.

3.

Let A and B be two sparse matrices. Write an algorithm to obtain C= A * B. Can this multiplication be achieved in $O(\min \{ p r_A , n r_B \} )$steps where A is an $n \times m$ matrix with r_A entries and B is an $m \times p$ matrix with r_B entries.

4.

A lunch counter in the university contains 23 seats in a row. Customers enter either alone or in pairs and are seated by the hostess. Prove that all customers can be seated without splitting provided no lone customer is assigned the seats 2,5,8...,20 and there are never more than 16 customers.

5.

Show how to represent strings in an editor so as to allow for the following operations:

(i) Deletion of a character.

(ii) Replacement of a character by a string.

(iii) Determining if a given pattern exists in the string