Basic Concepts in Algorithms

The following sections are included:

• Dedication
• Contents
• List of Background Concepts
• List of Algorithms
• Preface

The following sections are included:

• Minimum and maximum
• Mergesort
• Multiplying large numbers
• Lower bounds
• Exercises

The following sections are included:

• Binomial coefficients
• Edit distance
• Matrix chain multiplication
• Exercises

The following sections are included:

• Graphs
• The Minimum Spanning Tree problem
• Kruskal’s algorithm
• Borůvka’s algorithm
• Yao’s algorithm
• Prim’s algorithm
• Exercises

This chapter deals with one of the fundamental graph problems for which the translation of a real-life situation to an abstract description in mathematical terms seems most natural. Given is a map (a graph G = (V, E)) with locations (vertices V) and paths or roads (edges E) connecting them, and we wish to find a path from some source location, a special vertex we call s, to a target vertex t, in the fastest, or cheapest, or shortest, of the possible ways. Though the formulation of these optimization problems might look different at first sight, depending on the units in which the cost or weight w(a, b) of an edge (a, b) ∈ E is expressed, be it minutes, dollars or kilometers, the reader will realize that all these problems are essentially equivalent. We shall adopt the language of shortest or cheapest paths, but these should be understood in a broader sense encompassing also similar challenges…

The following sections are included:

• Probabilistic algorithms
• Primality testing
  • Rabin’s algorithm
  • Space complexity
  • Time complexity
  • Euclid’s GCD algorithm
• Probabilistic string matching
  • Karp and Rabin’s algorithm
  • Error probability
• Probabilistic Quicksort
• Exercises

Computing devices have been invented to facilitate the monotonic and quite boring task of performing many high-precision calculations. Doing it faultlessly requires advanced skills and an ability to focus on details, but humans tend to relax their concentration in the long run, which ultimately leads to errors. Machines are preferable in this regard, providing more accurate results and, furthermore, achieving them much faster…

The string matching problem, which is a special case of the more general pattern matching problem, is tackled differently depending on the sizes of its input parameters. It may be defined generically for a text T = T[0]T[1] ⋯ T[n − 1] of length n and a string S = S[0]S[1] ⋯ S[m − 1] of length m characters, all belonging to some pre-defined alphabet ∑. We are interested in finding the starting index of the first location of S in T, if it appears there at all, or to get appropriate notice, if not. In the example of Figure 7.1, the string S = OT-TO is indeed found in T, starting at position 10…

The following sections are included:

• Extended Pattern Matching
• Multiplying polynomials
• The Fourier transform
• The inverse Fourier transform
• Concluding remarks
  • Summary of fast polynomial multiplication
  • Using approximations
  • Summary of extended pattern matching
• Exercises

This chapter deals with yet another transformation of an input text, in addition to the data compression methods seen in Chapter 6. Actually, the technical goal of Cryptography, the subject of the current chapter, is also to remove as much redundancy as possible, but the motivation is different, as already mentioned. While compression strives to reduce redundancy in order to minimize the required space, the objective of encrypting is to hide information from whoever it is not intended for…

A book on algorithms is expected to present various methods and techniques on how to tackle computational problems. The contents of the present chapter will thus be rather surprising, because it deals more with challenges we are unable to solve than with those we can. And yet, there are good reasons to investigate these topics, as is also done in many other textbooks on algorithmics…

The previous chapter may have left us with the rather depressing impression that many, if not most, of the interesting problems we are confronted with are probably not solvable in reasonable time. Nonetheless, these and similar challenges need to be tackled as a matter of routine, and this chapter deals with possible ways to cope with such hard problems…

This section contains solutions to selected exercises found at the end of each chapter.

The following sections are included:

• References
• Index