## Random Numbers

Our next set of algorithms will be methods for using a computer to generate random numbers. We will find many uses for random numbers later on let's begin by trying to get a better idea of exactly what they are. Often, in conversation, people use the term random when they really mean arbitrary. When one asks for an arbitrary number, one is saying that one doesn't really care what number one gets almost any number will do. By contrast, a random number is a precisely defined mathematical concept...

## D E F

H l l l l l l l l l l l l l 11111111111111 For very large graphs, this computation can be organized so that the operations on bits can be done a computer word at a time, which will lead to significant savings in many environments. (As we've seen, it is not intended that such optimizations be tried with Pascal.) For many applications involving directed graphs, cyclic graphs do arise. If, however, the graph above modeled a manufacturing line, then it would imply, say, that job A must be done...

## For kl to M do inserta[k

This code breaks all the rules of abstract data structures by assuming a particular representation for the priority queue (during each loop, the priority queue resides in a I , , a k-l ), but it is reasonable to do this here because we are implementing a sort, not a priority queue. The priority queue procedures are being used only for descriptive purposes in an actual implementation of the sort, we would simply use the code from the procedures to avoid doing so many unnecessary procedure calls....

## Union Find Algorithms

In some applications we wish to know simply whether a vertex x is connected to a vertex y in a graph the actual path connecting them may not be relevant. This problem has been carefully studied in recent years some efficient algorithms have been developed which are of independent interest because they can also be used for processing sets (collections of objects). Graphs correspond to sets of objects in a natural way, with vertices corresponding to objects and edges have the meaning is in the...

## Passl hnextsorthnext N pass hnextsorthnext N

After these calls, the closest pair of points is found in the global variables cpl and cp2 which are managed by the check find the minimum procedure. The crux of the implementation is the operation of sort when pass 2. Before the recursive calls the points are sorted on x this ordering is used to divide the points in half and to find the x coordinate of the dividing line. After the recursive calls the points are sorted on y and the distance between every pair of points in each half is known to...

## End until iVl end

The running time of this program is dominated by the time spent processing edges in the priority queue. Suppose that the graph consists of two clusters of vertices all connected together by very short edges, and only one edge which is very long connecting the two clusters. Then the longest edge in the graph is in the minimum spanning tree, but it will be the last edge out of the priority queue. This shows that the running time could be proportional to ElogE in the worst case, although we might...

## Preview

To introduce the general approach that we'll be taking to studying algorithms, we'll examine a classic elementary problem Reduce a given fraction to lowest terms. We want to write 2 3, not 4 6, 200 300, or 178468 267702. Solving this problem is equivalent to finding the greatest common divisor gcd of the numerator and the denominator the largest integer which divides them both. A fraction is reduced to lowest terms by dividing both numerator and denominator by their greatest common divisor. A...

## Minimum Spanning Tree Delphi

It is obvious how to represent weighted graphs in the adjacency matrix representation, the matrix can contain edge weights rather than boolean values, and in the adjacency structure representation, each list element which represents an edge can contain a weight. We'll start by assuming that all of the weights are positive. Some of the algorithms can be adapted to handle negative weights, but they become significantly more complicated. In other cases, negative weights change the nature of the...

## Aaaceeegh I Lm

Other search keys are found even more efficiently for example X and A are found in the first step. Interpolation search manages to decrease the number of elements examined to about log log N. This is a very slowly growing function which can be thought of as a constant for practical purposes if N is one billion, lglgiV lt 5. Thus, any record can be found using only a few accesses, a substantial improvement over the conventional binary search method. But this assumes that the keys are rather well...

## Elementary Geometric Methods

Computers are being used more and more to solve large-scale problems I__ which are inherently geometric. Geometric objects such as points, lines and polygons are the basis of a broad variety of important applications and give rise to an interesting set of problems and algorithms. Geometric algorithms are important in design and analysis systems for physical objects ranging from buildings and automobiles to very large-scale integrated circuits. A designer working with a physical object has a...

## Gaussian Elimination

As we found with polynomials, if we wtint to have a program that takes N as input, it is necessary in Pascal to first decide how large a value of N will be legal, and declare the array suitably. Note that the code consists of three nested loops, so that the total running time is essentially proportional to iV3. The third loop goes backwards so as to avoid destroying a , i before it is needed to adjust the values of other elements in the same row. The program in the above paragraph is too...

## Finding the Convex Hull

Often, when we have a large number of points to process, we're interested in the boundaries of the point set. When looking at a diagram of a set of points plotted in the plane, a human has little trouble distinguishing those on the inside of the point set from those which lie on the edge. This distinction is a fundamental property of point sets in this chapter we'll see how it can be precisely characterized by looking at algorithms for separating out the boundary points of a point set. The...

## Elementary Sorting Methods

As our first excursion into the area of sorting algorithms, we'll study _ some elementary methods which are appropriate for small files or files with some special structure. There are several reasons for studying these simple sorting algorithms in some detail. First, they provide a relatively painless way to learn terminology and basic mechanisms for sorting algorithms so that we get an adequate background for studying the more sophisticated algorithms. Second, there are a great many...

## External Sorting

Many important sorting applications involve processing very large files, much too large to fit into the primal y memory of any computer. Methods appropriate for such applications are ca.led external methods, since they involve a large amount of processing external to the central processing unit as opposed to the internal methods that we've been studying . There are two major factors which make external algorithms quite different from those we've seen until now. First, the cost of accessing an...

## External Searching

I I Searching algorithms appropriate for accessing items from very large files are of immense practical importance. Searching is the fundamental operation on large data files, and certainly consumes a very significant fraction of the resources used in many computer installations. We'll be concerned mainly with met hods for searching on large disk files, since disk searching is of the most practical interest. With sequential devices such as tapes, searching quickly degenerates to the trivially...

## Geometric Intersection

II I A natural problem arising frequently in applications involving geometric _ data is Given a set of N objects, do any two intersect The objects involved may be lines, rectangles, circles, polygons, or other types of geometric objects. For example, in a system for designing and processing integrated circuits or printed circuit boards, it is important to know that no two wires intersect to make a short circuit. In an industrial application for designing layouts to be executed by a numerically...

## String Searching

Data to be processed often does not decompose logically into independent records with small identifiable pieces. This type of data is characterized only by the fact that it can be written down as a string a linear typically very long sequence of characters. Strings are obviously central in word processing systems, which provide a variety of capabilities for the manipulation of text. Such systems process text strings, which might be loosely defined as sequences of letters, numbers, and special...

## P

The points are labeled with single letters for reference in explaining the examples. The programs usually have no reason to refer to points by name they are simply stored in an array and are referred to by index. Of course, the order in which the points appear in the array may be important in some of the programs indeed, it is the goal of some geometric algorithms to sort the points into some particular order. The labels that we use are assigned in the order in which the points are assumed to...

## Radix Searching

Several searching methods proceed by examining the search keys one bit at a time rather than using full comparisons between keys at each step . These methods, called radix searching methods, work with the bits of the keys themselves, as opposed to the transformed version of the keys used in hashing. As with radix sorting methods, these methods can be useful when the bits of the search keys are easily accessible and the values of the search keys are well distributed. The principal advantages of...

## Range Searching

I I Given a set of points in the plane, it is natural to ask which of those I_ points fall within some specified area. List all cities within 50 miles of Providence is a question of this type which could reasonably be asked if a set of points corresponding to the cities of the U.S. were available. When the geometric shape is restricted to be a rectangle, the issue readily extends to non-geometric problems. For example, list all those people between 21 and 25 with incomes between 60,000 and...

## The Formulas Are Most Conveniently Expressed In Terms Of The Load Factor Of The Hash Table

This technique uses the same amount of space as linear probing but the average number of items examined for successful search is slightly smaller 32 17 1.882. Still, such a full table is to be avoided as shown by the 9 probes used to insert the last E in this example. Open addressing methods can be inconvenient in a dynamic situation, when an unpredictable number of insertions and deletions might have to be processed. First, how big should the table be Some estimate must be made of how many...

## Quicksort

In this chapter, we'll study the sorting algorithm which is probably more widely used than any other, Quicksort. The basic algorithm was invented in 1960 by C. A. R. Hoare, and it has been studied by many people since that time. Quicksort is popular because it's not difficult to implement, it's a good general-purpose sort works well in a variety of situations , and it consumes less resources than any other sorting method in many situations. The desirable features of the Quicksort algorithm are...

## Radix Sorting

II The keys used to define the order of the records in files for many _ sorting applications can be very complicated. For example, consider the ordering function used in the telephone book or a library catalogue. Because of this, it is reasonable to define sorting methods in terms of the basic operations of comparing two keys and exchanging two records. Most of the methods we have studied can be described in terms of these two fundamental operations. For many applications, however, it is...

## Until Hhiadlnext mergesortheadt next end

This program uses a list header node pointed to by head whose link field points to the file being sorted. Each iteration of the outer repeat loop passes through the file, producing a linked list comprised of sorted subfiles twice as long as for the previous pass. This is done by maintaining two pointers, one to the part of the list not yet seen todo and one to the end of the part of the list for which the subfiles have already been merged c . The inner repeat loop merges the two subfiles of...

## Boyer Moore Algorithm

If backing up is not a problem, then lt i significantly faster string searching method can be developed by scanning ' he pattern from right to left when trying to match it against the text. When searching for our sample pattern 10100111, if we find matches on the eighth, seventh, and sixth character but not on the fifth, then we can immediately slide the pattern seven positions to the right, and check the fifteenth character next, because our partial match found 111, which might appear...

## Delphi Algorithms For Table Interpolation

The interval size is at least halved at each step, so the total number of times through the loop is only about lgN. However, the time required to insert new records is high the array must be kept sorted, so records must be moved to make room for new records. For example, if the new record has a smaller key than any record in the table, then every entry must be moved over one position. A random insertion requires that N 2 records be moved, on the average. Thus, this method should not be used for...

## Cryptology

I I In the previous chapter we looked at methods for encoding strings of _I characters to save space. Of course, there is another very important reason to encode strings of characters to keep them secret. Cryptology, the study of systems for secret communications, consists of two competing fields of study cryptography, the design of secret communications systems, and cryptanalysis, the study of ways to compromise secret communications systems. The main application of cryptology has been in...

## Closest Point Problems

I Geometric problems involving points on the plane usually involve imI_I plicit or explicit treatment of distances between the points. For example, a very natural problem which arises in many applications is the nearest-neighbor problem find the point among a set of given points closest to a given new point. This seems to involve checking the distance from the given point to each point in the set, but we'll see that much better solutions are possible. In this section we'll look at some other...

## For iien[indexa [ downto do writebitscode [index a [ i

This program uses the bits procedure from Chapters 10 and 17 to access single bits. Our sample message is encoded in only 236 bits versus the 300 used for the straightforward encoding, a 21 savings 01110111001 An interesting feature of the Huffman code that the reader undoubtedly has noticed is that delimiters between characters are not stored, even though different characters may be coded with different numbers of bits. How can we determine when one character stops and the next begins to...

## Begin jjl addtailscan end else if ch [dq[iieada[ then

Addtail nextl dq head else if ch dq head ' 'then begin nl nextl dq hefid n2 next2 dq iiead addhead nl if il lt gt n2 then addhead n2 end head head l mod M until J gt N or dq head 0 or head tail if dq head 0 then mntch j l This function takes as its argument the josition j in the text string a at which it should start trying to match. It returns the index of the last character in the match found if any, otherwise it returns j-1 . The following table shows the contents of the deque each time a...

## Directed Graphs

Directed graphs are graphs in which edges connecting nodes are oneway this added structure makes it more difficult to determine various properties. Processing such graphs is akin to traveling around in a city with many one-way streets or to traveling around in a country where airlines rarely run round-trip routes getting from one point to another in such situations can be a challenge indeed. Often the edge direction reflects some type of precedence relationship in the application being...

## Head r redfalse end

This procedure takes care of fixing the colors after a rotation and also restarts x high enough in the tree to ensure that the search doesn't get lost due to all the link changes. The long argument list is included for clarity this procedure should more properly be declared local to rbtreeinsert, with access to its variables. If the root is a 4-node then the split procedure will make the root red, corresponding to transforming it, along with the dummy node above it into a 3-node. Of course,...

## Contents

.... 9 Pascal, Euclid s Algorithm, Recursion, Analysis of Algorithms Implementing Algorithms Polynomials, Matrices, Data Structures 3. Random Applications, Linear Congruential Method, Additive Congruential Method, Testing Randomness, Implementation Notes Evaluation, Interpolation, Multiplication, Divide-and-conquer Recurrences, Matriz Multiplication 5. Gaussian A Simple Example, Outline of the Method, Variations and Extensions 6. Curve Polynomial Interpolation, Spline Interpolation, Method of...

## File Compression

I I For the most part, the algorithms that we have studied have been de- _ signed primarily to use as little time as possible and only secondarily to conserve space. In this section, we ll examine some algorithms with the opposite orientation methods designed primarily to reduce space consumption without using up too much time. Ironically, the techniques that we ll examine to save space are coding methods from information theory which were developed to minimize the amount of information...