Page 212 - Discrete Mathematics and Its Applications

CH A P TER

3 Algorithms

3.1 Algorithms any problems can be solved by considering them as special cases of general problems.
MFor instance, consider the problem of locating the largest integer in the sequence 101,
3.2 The Growth of 12, 144, 212, 98.This is a specific case of the problem of locating the largest integer in a sequence
Functions
of integers. To solve this general problem we must give an algorithm, which specifies a sequence
3.3 Complexity of of steps used to solve this general problem. We will study algorithms for solving many different
Algorithms types of problems in this book. For example, in this chapter we will introduce algorithms for
two of the most important problems in computer science, searching for an element in a list and
sorting a list so its elements are in some prescribed order, such as increasing, decreasing, or
alphabetic. Later in the book we will develop algorithms that find the greatest common divisor
of two integers, that generate all the orderings of a finite set, that find the shortest path between
nodes in a network, and for solving many other problems.
We will also introduce the notion of an algorithmic paradigm, which provides a general
method for designing algorithms. In particular we will discuss brute-force algorithms, which
find solutions using a straightforward approach without introducing any cleverness. We will also
discuss greedy algorithms, a class of algorithms used to solve optimization problems. Proofs are
important in the study of algorithms. In this chapter we illustrate this by proving that a particular
greedy algorithm always finds an optimal solution.
One important consideration concerning an algorithm is its computational complexity,
which measures the processing time and computer memory required by the algorithm to solve
problems of a particular size. To measure the complexity of algorithms we use big-O and big-
Theta notation, which we develop in this chapter.We will illustrate the analysis of the complexity
of algorithms in this chapter, focusing on the time an algorithm takes to solve a problem. Fur-
thermore, we will discuss what the time complexity of an algorithm means in practical and
theoretical terms.

3.1 Algorithms

Introduction

There are many general classes of problems that arise in discrete mathematics. For instance:
given a sequence of integers, find the largest one; given a set, list all its subsets; given a set
of integers, put them in increasing order; given a network, find the shortest path between two
vertices. When presented with such a problem, the first thing to do is to construct a model that
translates the problem into a mathematical context. Discrete structures used in such models
include sets, sequences, and functions—structures discussed in Chapter 2—as well as such
other structures as permutations, relations, graphs, trees, networks, and finite state machines—
concepts that will be discussed in later chapters.
Setting up the appropriate mathematical model is only part of the solution. To complete the
solution, a method is needed that will solve the general problem using the model. Ideally, what
is required is a procedure that follows a sequence of steps that leads to the desired answer. Such
a sequence of steps is called an algorithm.

DEFINITION 1 An algorithm is a finite sequence of precise instructions for performing a computation or for
solving a problem.

191