Algorithms: Design Techniques And Analysis (Revised Edition)
eBook - ePub

Algorithms: Design Techniques And Analysis (Revised Edition)

Design Techniques and Analysis(Revised Edition)

M H Alsuwaiyel

Partager le livre
  1. 572 pages
  2. English
  3. ePUB (adapté aux mobiles)
  4. Disponible sur iOS et Android
eBook - ePub

Algorithms: Design Techniques And Analysis (Revised Edition)

Design Techniques and Analysis(Revised Edition)

M H Alsuwaiyel

DĂ©tails du livre
Aperçu du livre
Table des matiĂšres
Citations

À propos de ce livre

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

Foire aux questions

Comment puis-je résilier mon abonnement ?
Il vous suffit de vous rendre dans la section compte dans paramĂštres et de cliquer sur « RĂ©silier l’abonnement ». C’est aussi simple que cela ! Une fois que vous aurez rĂ©siliĂ© votre abonnement, il restera actif pour le reste de la pĂ©riode pour laquelle vous avez payĂ©. DĂ©couvrez-en plus ici.
Puis-je / comment puis-je télécharger des livres ?
Pour le moment, tous nos livres en format ePub adaptĂ©s aux mobiles peuvent ĂȘtre tĂ©lĂ©chargĂ©s via l’application. La plupart de nos PDF sont Ă©galement disponibles en tĂ©lĂ©chargement et les autres seront tĂ©lĂ©chargeables trĂšs prochainement. DĂ©couvrez-en plus ici.
Quelle est la différence entre les formules tarifaires ?
Les deux abonnements vous donnent un accĂšs complet Ă  la bibliothĂšque et Ă  toutes les fonctionnalitĂ©s de Perlego. Les seules diffĂ©rences sont les tarifs ainsi que la pĂ©riode d’abonnement : avec l’abonnement annuel, vous Ă©conomiserez environ 30 % par rapport Ă  12 mois d’abonnement mensuel.
Qu’est-ce que Perlego ?
Nous sommes un service d’abonnement Ă  des ouvrages universitaires en ligne, oĂč vous pouvez accĂ©der Ă  toute une bibliothĂšque pour un prix infĂ©rieur Ă  celui d’un seul livre par mois. Avec plus d’un million de livres sur plus de 1 000 sujets, nous avons ce qu’il vous faut ! DĂ©couvrez-en plus ici.
Prenez-vous en charge la synthÚse vocale ?
Recherchez le symbole Écouter sur votre prochain livre pour voir si vous pouvez l’écouter. L’outil Écouter lit le texte Ă  haute voix pour vous, en surlignant le passage qui est en cours de lecture. Vous pouvez le mettre sur pause, l’accĂ©lĂ©rer ou le ralentir. DĂ©couvrez-en plus ici.
Est-ce que Algorithms: Design Techniques And Analysis (Revised Edition) est un PDF/ePUB en ligne ?
Oui, vous pouvez accĂ©der Ă  Algorithms: Design Techniques And Analysis (Revised Edition) par M H Alsuwaiyel en format PDF et/ou ePUB ainsi qu’à d’autres livres populaires dans Mathematics et Discrete Mathematics. Nous disposons de plus d’un million d’ouvrages Ă  dĂ©couvrir dans notre catalogue.

Informations

Éditeur
WSPC
Année
2016
ISBN
9789814723664
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...

Table des matiĂšres