Algorithms: Design Techniques And Analysis (Revised Edition)

Design Techniques and Analysis(Revised Edition)

M H Alsuwaiyel

• Publisher: WSPC
• Year: 2016
• ISBN:
  9789814723664
• Topic: Mathematics
• Subtopic: Discrete Mathematics
• Index: Mathematics

Problem solving is an essential part of every scientific discipline. It has two components: (1) problem identification and formulation, and (2) the solution to the formulated problem. One can solve a problem on its own using ad hoc techniques or by following techniques that have produced efficient solutions to similar problems. This requires the understanding of various algorithm design techniques, how and when to use them to formulate solutions, and the context appropriate for each of them.

Algorithms: Design Techniques and Analysis advocates the study of algorithm design by presenting the most useful techniques and illustrating them with numerous examples — emphasizing on design techniques in problem solving rather than algorithms topics like searching and sorting. Algorithmic analysis in connection with example algorithms are explored in detail. Each technique or strategy is covered in its own chapter through numerous examples of problems and their algorithms.

Readers will be equipped with problem solving tools needed in advanced courses or research in science and engineering.

Problem solving is an essential part of every scientific discipline. It has two components: (1) problem identification and formulation, and (2) the solution to the formulated problem. One can solve a problem on its own using ad hoc techniques or by following techniques that have produced efficient solutions to similar problems. This requires the understanding of various algorithm design techniques, how and when to use them to formulate solutions, and the context appropriate for each of them.

Algorithms: Design Techniques and Analysis advocates the study of algorithm design by presenting the most useful techniques and illustrating them with numerous examples — emphasizing on design techniques in problem solving rather than algorithms topics like searching and sorting. Algorithmic analysis in connection with example algorithms are explored in detail. Each technique or strategy is covered in its own chapter through numerous examples of problems and their algorithms.

Readers will be equipped with problem solving tools needed in advanced courses or research in science and engineering.

Readership: Senior undergraduates, graduate students and professionals in software development. Readers in advanced courses or research in science and engineering.
Key Features:

• It covers many topics that are not in any other book on algorithms
• It covers a wide range of design techniques each in its own chapter

PART 1

Basic Concepts and Introduction to Algorithms

This part of the book is concerned with the study of the basic tools and prerequisites for the design and analysis of algorithms.

Chapter 1 is intended to set the stage for the rest of the book. In this chapter, we will discuss examples of simple algorithms for solving some of the fundamental problems encountered in almost all applications of computer science. These problems include searching, merging and sorting. Using these example algorithms as a reference, we then investigate the mathematical aspects underlying the analysis of algorithms. Specifically, we will study in detail the analysis of the running time and space required by a given algorithm.

Chapter 2 reviews some of the basic data structures usually employed in the design of algorithms. This chapter is not intended to be comprehensive and detailed. For a more thorough treatment, the reader is referred to standard books on data structures.

In Chapter 3, we investigate in more detail two fundamental data structures that are used for maintaining priority queues and disjoint sets. These two data structures, namely the heap and disjoint set data structures, are used as a building block in the design of many efficient algorithms, especially graph algorithms. In this book, heaps will be used in the design of an efficient sorting algorithm, namely heapsort. We will also make use of heaps in Chapter 7 for designing efficient algorithms for the single-source shortest path problem, the problem of computing minimum cost spanning trees and the problem of finding variable-length code for data compression. Heaps are also used in branch-and-bound algorithms, which is the subject of Sec. 12.5. The disjoint set data structure will be used in Sec. 7.3 in Algorithm KRUSKAL for finding a minimum cost spanning tree of an undirected graph. Both data structures are used extensively in the literature for the design of more complex algorithms.

Chapter 1

Basic Concepts in Algorithmic Analysis

1.1 Introduction

The most general intuitive idea of an algorithm is a procedure that consists of a finite set of instructions which, given an input, enables us to obtain an output if such an output exists or else obtain nothing at all if there is no output for that particular input through a systematic execution of the instructions. The set of possible inputs consists of all inputs to which the algorithm gives an output. If there is an output for a particular input, then we say that the algorithm can be applied to this input and process it to give the corresponding output. We require that an algorithm halts on every input, which implies that each instruction requires a finite amount of time, and each input has a finite length. We also require that the output of a legal input to be unique, that is, the algorithm is deterministic in the sense that the same set of instructions are executed when the algorithm is initiated on a particular input more than once. In Chapter 13, we will relax this condition when we study randomized algorithms.

The design and analysis of algorithms are of fundamental importance in the field of computer science. As Donald E. Knuth stated “Computer science is the study of algorithms.” This should not be surprising, as every area in computer science depends heavily on the design of efficient algorithms. As simple examples, compilers and operating systems are nothing but direct implementations of special purpose algorithms.

The objective of this chapter is twofold. First, it introduces some simple algorithms, particularly related to searching and sorting. Second, it covers the basic concepts used in the design and analysis of algorithms. We will cover in depth the notion of “running time” of an algorithm, as it is of fundamental importance to the design of efficient algorithms. After all, time is the most precious measure of an algorithm’s efficiency. We will also discuss the other important resource measure, namely the space required by an algorithm.

Although simple, the algorithms presented will serve as the basis for many of the examples in illus...