000			09230nam a22001697a 4500
999			_c40137 _d40137
003			OSt
020			_a9788173716126
100			_aHorowitz, Ellis
245			_aFundamentals of Computer Algorithms
250			_a2nd
260			_aNew Delhi _bUniversity Press _c2007
300			_a773p.
500			_a1 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 n2 Processors 13.4.2 Finding the Maximum Using n Processors 13.4.3 Maximal Selection Among Integers 13.4.4 General Selection Using n2 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
856			_uhttps://books.google.co.in/books?id=qzoqLM8899MC&printsec=frontcover&dq=fundamentals+of+computer+algorithms&hl=en&sa=X&ved=0ahUKEwjvksv--bLgAhUGFHIKHR8HCJIQ6AEIKDAA#v=onepage&q=fundamentals%20of%20computer%20algorithms&f=false
901			_a27937
942			_2ddc _cBK