Universities Press

Fundamentals of Computer Algorithms

Ellis Horowitz;Sartaj Sahni;Sanguthevar Rajasekaran

ISBN: 9788173716126 | Year: 2008 | Paperback | Pages: 808 | Language : English

Book Size: 158 x 240 mm | Territorial Rights: Restricted

Price: 950.00

About the Book

This is the of the programming language-independent text that helped establish computer algorithms as a discipline of computer science. The text incorporates the latest research and state-of-the-art applications, bringing this classic to the forefront of modern computer science education. A major strength of this text is its focus on design techniques rather than on individual algorithms. This book is appropriate as a core text for upper-and graduate-level courses in algorithms.

The second edition of Fundamentals of Computer Algorithms emphasizes:
• Design techniques: Divide and conquer, the greedy method, dynamic programming, backtracking and branch and bound are illustrated with several examples. Each algorithm is completely analyzed.
• Examples: A wide range of examples provides students with the actual implementation of correct design.
• The latest research: A thorough treatment of probabilistic and parallel algorithms is included.
• Full integration of randomized algorithms: Performance with nonrandomized algorithms is thoroughly compared.

Contributors (Author(s), Editor(s), Translator(s), Illustrator(s) etc.)

Ellis Horowitz is Professor of Computer Science and Electrical Engineering at the University of Southern California. Dr Horowitz is the author of ten books and numerous journal articles and refereed conference proceedings.

Sartaj Sahni is a Distinguished Professor and Chair of Computer and Information Sciences and Engineering at the University of Florida. Dr Sahni has published over 300 research papers and written 15 textbooks.

Sanguthevar Rajasekaran is the UTC Chair Professor of Computer Science and Engineering at the University of Connecticut. He has published over 150 articles in journals and conferences, co-authored two textbooks and co-edited four books.

Table of Content

1 INTRODUCTION
1.1 WHAT IS AN ALGORITHM?
1.2 ALGORITHM SPECIFICATION
	1.2.1 Pseudocode Conventions
	1.2.2 Recursive Algorithms
1.3 PERFORMANCE ANALYSIS
	1.3.1 Space Complexity
	1.3.2 Time Complexity
	1.3.3 Amortized Complexity
	1.3.4 Asymptotic Notation (Ο, Ω, Θ)
	1.3.5 Practical Complexities
	1.3.6 Performance Measurement
1.4 RANDOMIZED ALGORITHMS
	1.4.1 Basics of Probability Theory
	1.4.2 Randomized Algorithms: An Informal Description
	1.4.3 Identifying the Repeated Element
	1.4.4 Primality Testing
	1.4.5 Advantages and Disadvantages
1.5 REFERENCES AND READINGS

2 ELEMENTARY DATA STRUCTURES
2.1 STACKS AND QUEUES
2.2 TREES
	2.2.1 Terminology
	2.2.2 Binary Trees
2.3 DICTIONARIES
	2.3.1 Binary Search Trees
2.4 PRIORITY QUEUES
	2.4.1 Heaps
	2.4.2 Heap Sort
2.5 SETS AND DISJOINT SET UNION
	2.5.1 Introduction
	2.5.2 Union and Find Operations
2.6 GRAPHS
	2.6.1 Introduction
	2.6.2 Definitions
	2.6.3 Graph Representations
2.7 REFERENCES AND READINGS

3. DIVIDE AND CONQUER
3.1 GENERAL METHOD
3.2 DEFECTIVE CHESSBOARD
3.3 BINARY SEARCH
3.4 FINDING THE MAXIMUM AND MINIMUM
3.5 MERGE SORT
3.6 QUICK SORT
	3.6.1 Performance Measurement
	3.6.2 Randomized Sorting Algorithms
3.7 SELECTION
	3.6.2 Evaluating Postfix Expressions
3.7 Multiple Stacks and Queues
3.7 Additional Exercises
	3.7.1 A Worst-Case Optimal Algorithm
	3.7.2 Implementation of Select2
3.8 STRASSEN´S MATRIX MULTIPLICATION
3.9 CONVEX HULL
	3.9.1 Some Geometric Primitives
	3.9.2 The QuickHullAlgorithm
	3.9.3 Graham´s Scan
	3.9.4 An Ο (n log n) Divide-and-Conquer Algorithm
3.10 REFERENCES AND READINGS
3.11 ADDITIONAL EXERCISES

4 THE GREEDY METHOD
4.1 THE GENERAL METHOD
4.2 CONTAINER LOADING
4.3 KNAPSACK PROBLEM
4.4 TREE VERTEX SPLITTING
4.5 JOB SEQUENCING WITH DEADLINES
4.6 MINIMUM-COST SPANNING TREES
	4.6.1 Prim´s Algorithm
	4.6.2 Kruskal´s Algorithm
	4.6.3 An Optimal Randomized Algorithm (∗)
4.7 OPTIMAL STORAGE ON TAPES
4.8 OPTIMAL MERGE PATTERNS
4.9 SINGLE-SOURCE SHORTEST PATHS
4.10 REFERENCES AND READINGS
4.11 ADDITIONAL EXERCISES

5 DYNAMIC PROGRAMMING
5.1 THE GENERAL METHOD
5.2 MULTISTAGE GRAPHS
5.3 ALL-PAIRS SHORTEST PATHS
5.4 SINGLE-SOURCE SHORTEST PATHS: GENERAL WEIGHTS
5.5 OPTIMAL BINARY SEARCH TREES (∗)
5.6 STRING EDITING
5.7 0/1 KNAPSACK
5.8 RELIABILITY DESIGN
5.9 THE TRAVELING SALESPERSON PROBLEM
5.10 FLOW SHOP SCHEDULING
5.11 REFERENCES AND READINGS
5.12 ADDITIONAL EXERCISES

6 BASIC TRAVERSAL AND SEARCH TECHNIQUES
6.1 TECHNIQUES FOR BINARY TREES
6.2 TECHNIQUES FOR GRAPHS
	6.2.1 Breadth First Search and Traversal
	6.2.2 Depth First Search and Traversal
6.3 CONNECTED COMPONENTS AND SPANNING TREES
6.4 BICONNECTED COMPONENTS AND DFS
6.5 REFERENCES AND READINGS CONTENTS

7 BACKTRACKING
7.1 THE GENERAL METHOD
7.2 THE 8-QUEENS PROBLEM
7.3 SUM OF SUBSETS
7.4 GRAPH COLORING
7.5 HAMILTONIAN CYCLES
7.6 KNAPSACK PROBLEM
7.7 REFERENCES AND READINGS
7.8 ADDITIONAL EXERCISES

8 BRANCH AND BOUND
8.1 THE METHOD
	8.1.1 Least Cost (LC) Search
	8.1.2 The 15-puzzle: An Example
	8.1.3 Control Abstractions for LC-Search
	8.1.4 Bounding
	8.1.5 FIFO Branch-and-Bound
	8.1.6 LC Branch-and-Bound
8.2 0/1 KNAPSACK PROBLEM
	8.2.1 LC Branch-and-Bound Solution
	8.2.2 FIFO Branch-and-Bound Solution
8.3 TRAVELING SALESPERSON (∗)
8.4 EFFICIENCY CONSIDERATIONS
8.5 REFERENCES AND READINGS

9 ALGEBRAIC PROBLEMS
9.1 THE GENERAL METHOD
9.2 EVALUATION AND INTERPOLATION
9.3 THE FAST FOURIER TRANSFORM
	9.3.1 An In-place Version of the FFT
	9.3.2 Some Remaining Points
9.4 MODULAR ARITHMETIC
9.5 EVEN FASTER EVALUATION AND INTERPOLATION
9.6 REFERENCES AND READINGS

10 LOWER BOUND THEORY
10.1 COMPARISON TREES
	10.1.1 Ordered Searching
	10.1.2 Sorting
	10.1.3 Selection
10.2 ORACLES AND ADVERSARY ARGUMENTS
	10.2.1 Merging
	10.2.2 Largest and Second Largest
	10.2.3 State Space Method
	10.2.4 Selection
10.3 LOWER BOUNDS THROUGH REDUCTIONS
	10.3.1 Finding the Convex Hull
	10.3.2 Disjoint Sets Problem
	10.3.3 On-line Median Finding
	10.3.4 Multiplying Triangular Matrices
	10.3.5 Inverting a Lower Triangular Matrix
	10.3.6 Computing the Transitive Closure
10.4 TECHNIQUES FOR ALGEBRAIC PROBLEMS (∗)
10.5 REFERENCES AND READINGS

11 NP-HARD AND NP-COMPLETE PROBLEMS
11.1 BASIC CONCEPTS
	11.1.1 Nondeterministic Algorithms
	11.1.2 The Classes NP-hard and NP-complete
11.2 COOK´S THEOREM (∗)
11.3 NP-HARD GRAPH PROBLEMS
	11.3.1 Clique Decision Problem (CDP)
	11.3.2 Node Cover Decision Problem (NCDP)
	11.3.3 Chromatic Number Decision Problem (CNDP)
	11.3.4 Directed Hamiltonian Cycle (DHC) (∗)
	11.3.5 Traveling Salesperson Decision Problem (TSP)
	11.3.6 AND/OR Graph Decision Problem (AOG)
11.4 NP-HARD SCHEDULING PROBLEMS
	11.4.1 Scheduling Identical Processors
	11.4.2 Flow Shop Scheduling
	11.4.3 Job Shop Scheduling
11.5 NP-HARD CODE GENERATION PROBLEMS
	11.5.1 Code Generation with Common Subexpressions
	11.5.2 Implementing Parallel Assignment Instructions
11.6 SOME SIMPLIFIED NP-HARD PROBLEMS
11.7 REFERENCES AND READINGS
11.8 ADDITIONAL EXERCISES

12 APPROXIMATION ALGORITHMS
12.1 INTRODUCTION.
12.2 ABSOLUTE APPROXIMATIONS.
	12.2.1 Planar Graph Coloring
	12.2.2 Maximum Programs Stored Problem
	12.2.3 NP-hard Absolute Approximations
12.3 ∊-APPROXIMATIONS
	12.3.1 Scheduling Independent Tasks
	12.3.2 Bin Packing
	12.3.3 NP-hard ∊-approximation Problems
12.4 POLYNOMIAL TIME APPROXIMATION SCHEMES
	12.4.1 Scheduling Independent Tasks
	12.4.2 0/1 Knapsack
12.5 FULLY POLYNOMIAL TIME APPROXIMATION SCHEMES
	12.5.1 Rounding
	12.5.2 Interval Partitioning
	12.5.3 Separation
12.6 PROBABILISTICALLY GOOD ALGORITHMS (∗)
12.7 REFERENCES AND READINGS
12.8 ADDITIONAL EXERCISES

13 PRAM ALGORITHMS
13.1 INTRODUCTION
13.2 COMPUTATIONAL MODEL
13.3 FUNDAMENTAL TECHNIQUES AND ALGORITHMS
	13.3.1 Prefix Computation
	13.3.2 List Ranking
13.4 SELECTION
	13.4.1 Maximal Selection with n² Processors
	13.4.2 Finding the Maximum Using n Processors
	13.4.3 Maximal Selection Among Integers
	13.4.4 General Selection Using n² Processors
	13.4.5 A Work-Optimal Randomized Algorithm (∗)
13.5 MERGING
	13.5.1 A Logarithmic Time Algorithm
	13.5.2 Odd-Even Merge
	13.5.3 A Work-Optimal Algorithm
	13.5.4 An O (log log m)-Time Algorithm
13.6 SORTING
	13.6.1 Odd-Even Merge Sort
	13.6.2 An Alternative Randomized Algorithm
	13.6.3 Preparata´s Algorithm
	13.6.4 Reischuk´s Randomized Algorithm (∗)
13.7 GRAPH PROBLEMS
	13.7.1 An Alternative Algorithm for Transitive Closure
	13.7.2 All-Pairs Shortest Paths
13.8 COMPUTING THE CONVEX HULL
13.9 LOWER BOUNDS
	13.9.1 A lower bound on average-case sorting
	13.9.2 Finding the maximum
13.10REFERENCES AND READINGS
13.11ADDITIONAL EXERCISES

14 MESH ALGORITHMS
14.1 COMPUTATIONAL MODEL
14.2 PACKET ROUTING
	14.2.1 Packet Routing on a Linear Array
	14.2.2 A Greedy Algorithm for PPR on a Mesh
	14.2.3 A Randomized Algorithm with Small Queues
14.3 FUNDAMENTAL ALGORITHMS
	14.3.1 Broadcasting
	14.3.2 Prefix Computation
	14.3.3 Data Concentration
	14.3.4 Sparse Enumeration Sort
14.4 SELECTION
	14.4.1 A Randomized Algorithm for n = p (∗)
	14.4.2 Randomized Selection for n > p (∗)
	14.4.3 A Deterministic Algorithm For n > p
14.5 MERGING
	14.5.1 Rank Merge on a Linear Array
	14.5.2 Odd-Even Merge on a Linear Array
	14.5.3 Odd-Even Merge on a Mesh
14.6 SORTING
	14.6.1 Sorting on a Linear Array
	14.6.2 Sorting on a Mesh
14.7 GRAPH PROBLEMS
	14.7.1 An n × n Mesh Algorithm for Transitive Closure
	14.7.2 All-Pairs Shortest Paths
14.8 COMPUTING THE CONVEX HULL
14.9 REFERENCES AND READINGS
14.10 ADDITIONAL EXERCISES

15 HYPERCUBE ALGORITHMS
15.1 COMPUTATIONAL MODEL
	15.1.1 The Hypercube
	15.1.2 The Butterfly Network
	15.1.3 Embedding of Other Networks
15.2 PPR ROUTING
	15.2.1 A Greedy Algorithm
	15.2.2 A Randomized Algorithm
15.3 FUNDAMENTAL ALGORITHMS
	15.3.1 Broadcasting
	15.3.2 Prefix Computation
	15.3.3 Data Concentration
	15.3.4 Sparse Enumeration Sort
15.4 SELECTION
	1.5.4.1 A Randomized Algorithm for n = p (∗)
	15.4.2 Randomized Selection for n > p (∗)
	15.4.3 A Deterministic Algorithm for n > p
15.5 MERGING
	15.5.1 Odd-Even Merge
	15.5.2 Bitonic Merge
15.6 SORTING
	15.6.1 Odd-Even Merge Sort
	15.6.2 Bitonic Sort
15.7 GRAPH PROBLEMS
15.8 COMPUTING THE CONVEX HULL
15.9 REFERENCES AND READINGS
15.10 ADDITIONAL EXERCISES

Resources

https://www.universitiespress.com/hrwitzsahnirajaskrn/fca?isbn=9788173716126