Welcome to Algorithms:
We illustrate our basic approach to developing and analyzing algorithms by considering the dynamic connectivity problem. We introduce the union−find data type and consider several implementations (quick find, quick union, weighted quick union, and weighted quick union with path compression). Finally, we apply the union−find data type to the percolation problem from physical chemistry.
• Apply the union-find data type to solve problems in science, engineering, and industry.
• Define the union-find (or disjoint sets) data type.
• Compare the performance of different algorithms for the union-find data type.
• Design different algorithms (quick find, quick union, weighted quick union, path compression) for the union-find data type.
• Develop Java implementations of different algorithms for the union-find data type.
• Use the parent-link representation to represent tree data structures.
The basis of our approach for analyzing the performance of algorithms is the scientific method. We begin by performing computational experiments to measure the running times of our programs. We use these measurements to develop hypotheses about performance. Next, we create mathematical models to explain their behavior. Finally, we consider analyzing the memory usage of our Java programs.
• Define tilde and order-of-growth notations.
• Determine the order of growth of the running time of a program as a function of the input size.
• Formulate a hypothesis for the running time of a program as a function of the input size by performing computational experiments.
• Calculate the amount of memory that a Java program uses a function of the input size.
• Describe the binary search algorithm.
• Analyze the running time of binary search.
