Design and Analysis of Computer Algorithms

This work has four parts that deal with four areas of algorithmic research. The first part, algorithms on strings, has a number of specific problems for which improved algorithms will need new algorithmic techniques. In the second part, the study of cryptographic protocols, concerns new protocols, and exploring tradeoffs of security and communication for useful tasks. The third part, problems in distributed computing, includes developing precise models and improved algorithms. The fourth part, problems in dynamic graphs, involves the development of algorithmic techniques for graph problems whose underlying graphs may change. This research develops new general tools and techniques as well as attacking the specific problems of special interest. It includes the design of sequential, parallel, and distributed algorithms and protocols. Theoretical considerations as well as practical ones are taken into account.