Fundamentals of Computer Algorithms (Record no. 6244)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 09972nam a22002177a 4500 |
| 003 - CONTROL NUMBER IDENTIFIER | |
| control field | OSt |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20230914020008.0 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 221021b ||||| |||| 00| 0 eng d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9788173716126 |
| 082 ## - DEWEY DECIMAL CLASSIFICATION NUMBER | |
| Classification number | 519.4 |
| Item number | HOR |
| 100 ## - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Horowitz, Ellis |
| 245 ## - TITLE STATEMENT | |
| Title | Fundamentals of Computer Algorithms |
| 250 ## - EDITION STATEMENT | |
| Edition statement | 2nd |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Place of publication, distribution, etc. | Hyderabad |
| Name of publisher, distributor, etc. | Universities Press |
| Date of publication, distribution, etc. | 2022 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Page No. | xx, 773, i-11p |
| 500 ## - GENERAL NOTE | |
| General note | 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.<br/><br/>The second edition of Fundamentals of Computer Algorithms emphasizes:<br/>• 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.<br/>• Examples: A wide range of examples provides students with the actual implementation of correct design.<br/>• The latest research: A thorough treatment of probabilistic and parallel algorithms is included.<br/>• Full integration of randomized algorithms: Performance with nonrandomized algorithms is thoroughly compared. |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc. | Table of Content<br/>1 INTRODUCTION<br/>1.1 WHAT IS AN ALGORITHM?<br/>1.2 ALGORITHM SPECIFICATION<br/> 1.2.1 Pseudocode Conventions<br/> 1.2.2 Recursive Algorithms<br/>1.3 PERFORMANCE ANALYSIS<br/> 1.3.1 Space Complexity<br/> 1.3.2 Time Complexity<br/> 1.3.3 Amortized Complexity<br/> 1.3.4 Asymptotic Notation (Ο, Ω, Θ)<br/> 1.3.5 Practical Complexities<br/> 1.3.6 Performance Measurement<br/>1.4 RANDOMIZED ALGORITHMS<br/> 1.4.1 Basics of Probability Theory<br/> 1.4.2 Randomized Algorithms: An Informal Description<br/> 1.4.3 Identifying the Repeated Element<br/> 1.4.4 Primality Testing<br/> 1.4.5 Advantages and Disadvantages<br/>1.5 REFERENCES AND READINGS<br/> <br/>2 ELEMENTARY DATA STRUCTURES<br/>2.1 STACKS AND QUEUES<br/>2.2 TREES<br/> 2.2.1 Terminology<br/> 2.2.2 Binary Trees<br/>2.3 DICTIONARIES<br/> 2.3.1 Binary Search Trees<br/>2.4 PRIORITY QUEUES<br/> 2.4.1 Heaps<br/> 2.4.2 Heap Sort<br/>2.5 SETS AND DISJOINT SET UNION<br/> 2.5.1 Introduction<br/> 2.5.2 Union and Find Operations<br/>2.6 GRAPHS<br/> 2.6.1 Introduction<br/> 2.6.2 Definitions<br/> 2.6.3 Graph Representations<br/>2.7 REFERENCES AND READINGS<br/> <br/>3. DIVIDE AND CONQUER<br/>3.1 GENERAL METHOD<br/>3.2 DEFECTIVE CHESSBOARD<br/>3.3 BINARY SEARCH<br/>3.4 FINDING THE MAXIMUM AND MINIMUM<br/>3.5 MERGE SORT<br/>3.6 QUICK SORT<br/> 3.6.1 Performance Measurement<br/> 3.6.2 Randomized Sorting Algorithms<br/>3.7 SELECTION<br/> 3.6.2 Evaluating Postfix Expressions<br/>3.7 Multiple Stacks and Queues<br/>3.7 Additional Exercises<br/> 3.7.1 A Worst-Case Optimal Algorithm<br/> 3.7.2 Implementation of Select2<br/>3.8 STRASSEN´S MATRIX MULTIPLICATION<br/>3.9 CONVEX HULL<br/> 3.9.1 Some Geometric Primitives<br/> 3.9.2 The QuickHullAlgorithm<br/> 3.9.3 Graham´s Scan<br/> 3.9.4 An Ο (n log n) Divide-and-Conquer Algorithm<br/>3.10 REFERENCES AND READINGS<br/>3.11 ADDITIONAL EXERCISES<br/> <br/>4 THE GREEDY METHOD<br/>4.1 THE GENERAL METHOD<br/>4.2 CONTAINER LOADING<br/>4.3 KNAPSACK PROBLEM<br/>4.4 TREE VERTEX SPLITTING<br/>4.5 JOB SEQUENCING WITH DEADLINES<br/>4.6 MINIMUM-COST SPANNING TREES<br/> 4.6.1 Prim´s Algorithm<br/> 4.6.2 Kruskal´s Algorithm<br/> 4.6.3 An Optimal Randomized Algorithm (∗)<br/>4.7 OPTIMAL STORAGE ON TAPES<br/>4.8 OPTIMAL MERGE PATTERNS<br/>4.9 SINGLE-SOURCE SHORTEST PATHS<br/>4.10 REFERENCES AND READINGS<br/>4.11 ADDITIONAL EXERCISES<br/> <br/>5 DYNAMIC PROGRAMMING<br/>5.1 THE GENERAL METHOD<br/>5.2 MULTISTAGE GRAPHS<br/>5.3 ALL-PAIRS SHORTEST PATHS<br/>5.4 SINGLE-SOURCE SHORTEST PATHS: GENERAL WEIGHTS<br/>5.5 OPTIMAL BINARY SEARCH TREES (∗)<br/>5.6 STRING EDITING<br/>5.7 0/1 KNAPSACK<br/>5.8 RELIABILITY DESIGN<br/>5.9 THE TRAVELING SALESPERSON PROBLEM<br/>5.10 FLOW SHOP SCHEDULING<br/>5.11 REFERENCES AND READINGS<br/>5.12 ADDITIONAL EXERCISES<br/> <br/>6 BASIC TRAVERSAL AND SEARCH TECHNIQUES<br/>6.1 TECHNIQUES FOR BINARY TREES<br/>6.2 TECHNIQUES FOR GRAPHS<br/> 6.2.1 Breadth First Search and Traversal<br/> 6.2.2 Depth First Search and Traversal<br/>6.3 CONNECTED COMPONENTS AND SPANNING TREES<br/>6.4 BICONNECTED COMPONENTS AND DFS<br/>6.5 REFERENCES AND READINGS CONTENTS<br/> <br/>7 BACKTRACKING<br/>7.1 THE GENERAL METHOD<br/>7.2 THE 8-QUEENS PROBLEM<br/>7.3 SUM OF SUBSETS<br/>7.4 GRAPH COLORING<br/>7.5 HAMILTONIAN CYCLES<br/>7.6 KNAPSACK PROBLEM<br/>7.7 REFERENCES AND READINGS<br/>7.8 ADDITIONAL EXERCISES<br/> <br/>8 BRANCH AND BOUND<br/>8.1 THE METHOD<br/> 8.1.1 Least Cost (LC) Search<br/> 8.1.2 The 15-puzzle: An Example<br/> 8.1.3 Control Abstractions for LC-Search<br/> 8.1.4 Bounding<br/> 8.1.5 FIFO Branch-and-Bound<br/> 8.1.6 LC Branch-and-Bound<br/>8.2 0/1 KNAPSACK PROBLEM<br/> 8.2.1 LC Branch-and-Bound Solution<br/> 8.2.2 FIFO Branch-and-Bound Solution<br/>8.3 TRAVELING SALESPERSON (∗)<br/>8.4 EFFICIENCY CONSIDERATIONS<br/>8.5 REFERENCES AND READINGS<br/> <br/>9 ALGEBRAIC PROBLEMS<br/>9.1 THE GENERAL METHOD<br/>9.2 EVALUATION AND INTERPOLATION<br/>9.3 THE FAST FOURIER TRANSFORM<br/> 9.3.1 An In-place Version of the FFT<br/> 9.3.2 Some Remaining Points<br/>9.4 MODULAR ARITHMETIC<br/>9.5 EVEN FASTER EVALUATION AND INTERPOLATION<br/>9.6 REFERENCES AND READINGS<br/> <br/>10 LOWER BOUND THEORY<br/>10.1 COMPARISON TREES<br/> 10.1.1 Ordered Searching<br/> 10.1.2 Sorting<br/> 10.1.3 Selection<br/>10.2 ORACLES AND ADVERSARY ARGUMENTS<br/> 10.2.1 Merging<br/> 10.2.2 Largest and Second Largest<br/> 10.2.3 State Space Method<br/> 10.2.4 Selection<br/>10.3 LOWER BOUNDS THROUGH REDUCTIONS<br/> 10.3.1 Finding the Convex Hull<br/> 10.3.2 Disjoint Sets Problem<br/> 10.3.3 On-line Median Finding<br/> 10.3.4 Multiplying Triangular Matrices<br/> 10.3.5 Inverting a Lower Triangular Matrix<br/> 10.3.6 Computing the Transitive Closure<br/>10.4 TECHNIQUES FOR ALGEBRAIC PROBLEMS (∗)<br/>10.5 REFERENCES AND READINGS<br/> <br/>11 NP-HARD AND NP-COMPLETE PROBLEMS<br/>11.1 BASIC CONCEPTS<br/> 11.1.1 Nondeterministic Algorithms<br/> 11.1.2 The Classes NP-hard and NP-complete<br/>11.2 COOK´S THEOREM (∗)<br/>11.3 NP-HARD GRAPH PROBLEMS<br/> 11.3.1 Clique Decision Problem (CDP)<br/> 11.3.2 Node Cover Decision Problem (NCDP)<br/> 11.3.3 Chromatic Number Decision Problem (CNDP)<br/> 11.3.4 Directed Hamiltonian Cycle (DHC) (∗)<br/> 11.3.5 Traveling Salesperson Decision Problem (TSP)<br/> 11.3.6 AND/OR Graph Decision Problem (AOG)<br/>11.4 NP-HARD SCHEDULING PROBLEMS<br/> 11.4.1 Scheduling Identical Processors<br/> 11.4.2 Flow Shop Scheduling<br/> 11.4.3 Job Shop Scheduling<br/>11.5 NP-HARD CODE GENERATION PROBLEMS<br/> 11.5.1 Code Generation with Common Subexpressions<br/> 11.5.2 Implementing Parallel Assignment Instructions<br/>11.6 SOME SIMPLIFIED NP-HARD PROBLEMS<br/>11.7 REFERENCES AND READINGS<br/>11.8 ADDITIONAL EXERCISES<br/> <br/>12 APPROXIMATION ALGORITHMS<br/>12.1 INTRODUCTION.<br/>12.2 ABSOLUTE APPROXIMATIONS.<br/> 12.2.1 Planar Graph Coloring<br/> 12.2.2 Maximum Programs Stored Problem<br/> 12.2.3 NP-hard Absolute Approximations<br/>12.3 ∊-APPROXIMATIONS<br/> 12.3.1 Scheduling Independent Tasks<br/> 12.3.2 Bin Packing<br/> 12.3.3 NP-hard ∊-approximation Problems<br/>12.4 POLYNOMIAL TIME APPROXIMATION SCHEMES<br/> 12.4.1 Scheduling Independent Tasks<br/> 12.4.2 0/1 Knapsack<br/>12.5 FULLY POLYNOMIAL TIME APPROXIMATION SCHEMES<br/> 12.5.1 Rounding<br/> 12.5.2 Interval Partitioning<br/> 12.5.3 Separation<br/>12.6 PROBABILISTICALLY GOOD ALGORITHMS (∗)<br/>12.7 REFERENCES AND READINGS<br/>12.8 ADDITIONAL EXERCISES<br/> <br/>13 PRAM ALGORITHMS<br/>13.1 INTRODUCTION<br/>13.2 COMPUTATIONAL MODEL<br/>13.3 FUNDAMENTAL TECHNIQUES AND ALGORITHMS<br/> 13.3.1 Prefix Computation<br/> 13.3.2 List Ranking<br/>13.4 SELECTION<br/> 13.4.1 Maximal Selection with n2 Processors<br/> 13.4.2 Finding the Maximum Using n Processors<br/> 13.4.3 Maximal Selection Among Integers<br/> 13.4.4 General Selection Using n2 Processors<br/> 13.4.5 A Work-Optimal Randomized Algorithm (∗)<br/>13.5 MERGING<br/> 13.5.1 A Logarithmic Time Algorithm<br/> 13.5.2 Odd-Even Merge<br/> 13.5.3 A Work-Optimal Algorithm<br/> 13.5.4 An O (log log m)-Time Algorithm<br/>13.6 SORTING<br/> 13.6.1 Odd-Even Merge Sort<br/> 13.6.2 An Alternative Randomized Algorithm<br/> 13.6.3 Preparata´s Algorithm<br/> 13.6.4 Reischuk´s Randomized Algorithm (∗)<br/>13.7 GRAPH PROBLEMS<br/> 13.7.1 An Alternative Algorithm for Transitive Closure<br/> 13.7.2 All-Pairs Shortest Paths<br/>13.8 COMPUTING THE CONVEX HULL<br/>13.9 LOWER BOUNDS<br/> 13.9.1 A lower bound on average-case sorting<br/> 13.9.2 Finding the maximum<br/>13.10REFERENCES AND READINGS<br/>13.11ADDITIONAL EXERCISES<br/> <br/>14 MESH ALGORITHMS<br/>14.1 COMPUTATIONAL MODEL<br/>14.2 PACKET ROUTING<br/> 14.2.1 Packet Routing on a Linear Array<br/> 14.2.2 A Greedy Algorithm for PPR on a Mesh<br/> 14.2.3 A Randomized Algorithm with Small Queues<br/>14.3 FUNDAMENTAL ALGORITHMS<br/> 14.3.1 Broadcasting<br/> 14.3.2 Prefix Computation<br/> 14.3.3 Data Concentration<br/> 14.3.4 Sparse Enumeration Sort<br/>14.4 SELECTION<br/> 14.4.1 A Randomized Algorithm for n = p (∗)<br/> 14.4.2 Randomized Selection for n > p (∗)<br/> 14.4.3 A Deterministic Algorithm For n > p<br/>14.5 MERGING<br/> 14.5.1 Rank Merge on a Linear Array<br/> 14.5.2 Odd-Even Merge on a Linear Array<br/> 14.5.3 Odd-Even Merge on a Mesh<br/>14.6 SORTING<br/> 14.6.1 Sorting on a Linear Array<br/> 14.6.2 Sorting on a Mesh<br/>14.7 GRAPH PROBLEMS<br/> 14.7.1 An n × n Mesh Algorithm for Transitive Closure<br/> 14.7.2 All-Pairs Shortest Paths<br/>14.8 COMPUTING THE CONVEX HULL<br/>14.9 REFERENCES AND READINGS<br/>14.10 ADDITIONAL EXERCISES<br/> <br/>15 HYPERCUBE ALGORITHMS<br/>15.1 COMPUTATIONAL MODEL<br/> 15.1.1 The Hypercube<br/> 15.1.2 The Butterfly Network<br/> 15.1.3 Embedding of Other Networks<br/>15.2 PPR ROUTING<br/> 15.2.1 A Greedy Algorithm<br/> 15.2.2 A Randomized Algorithm<br/>15.3 FUNDAMENTAL ALGORITHMS<br/> 15.3.1 Broadcasting<br/> 15.3.2 Prefix Computation<br/> 15.3.3 Data Concentration<br/> 15.3.4 Sparse Enumeration Sort<br/>15.4 SELECTION<br/> 1.5.4.1 A Randomized Algorithm for n = p (∗)<br/> 15.4.2 Randomized Selection for n > p (∗)<br/> 15.4.3 A Deterministic Algorithm for n > p<br/>15.5 MERGING<br/> 15.5.1 Odd-Even Merge<br/> 15.5.2 Bitonic Merge<br/>15.6 SORTING<br/> 15.6.1 Odd-Even Merge Sort<br/> 15.6.2 Bitonic Sort<br/>15.7 GRAPH PROBLEMS<br/>15.8 COMPUTING THE CONVEX HULL<br/>15.9 REFERENCES AND READINGS<br/>15.10 ADDITIONAL EXERCISES |
| 700 ## - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Sahni, Sartaj |
| 700 ## - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Rajasekaran, Sanguthevar |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Source of classification or shelving scheme | Dewey Decimal Classification |
| Koha item type | General Books |
| Koha issues (borrowed), all copies | 6 |
| Withdrawn status | Lost status | Source of classification or shelving scheme | Damaged status | Not for loan | Collection code | Home library | Current library | Date acquired | Cost, normal purchase price | Full call number | Barcode | Date last seen | Bill Date | Koha item type | Bill Number | Total Checkouts | Date last checked out |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Dewey Decimal Classification | AIML (Artificial Intelligence and Machine Learning) | Raj Kumar Goel Institute of Technology | Raj Kumar Goel Institute of Technology | 21/10/2022 | 795.00 | 519.4 HOR | 90010 | 21/10/2022 | Reference | 22-23/CRB/286 | |||||||
| Dewey Decimal Classification | AIML (Artificial Intelligence and Machine Learning) | Raj Kumar Goel Institute of Technology | Raj Kumar Goel Institute of Technology | 21/10/2022 | 795.00 | 519.4 HOR | 90011 | 21/10/2022 | Reference | 22-23/CRB/286 | |||||||
| Dewey Decimal Classification | AIML (Artificial Intelligence and Machine Learning) | Raj Kumar Goel Institute of Technology | Raj Kumar Goel Institute of Technology | 21/10/2022 | 795.00 | 519.4 HOR | 90012 | 21/10/2022 | General Books | 22-23/CRB/286 | |||||||
| Dewey Decimal Classification | AIML (Artificial Intelligence and Machine Learning) | Raj Kumar Goel Institute of Technology | Raj Kumar Goel Institute of Technology | 21/10/2022 | 795.00 | 519.4 HOR | 90013 | 21/10/2022 | General Books | 22-23/CRB/286 | |||||||
| Dewey Decimal Classification | AIML (Artificial Intelligence and Machine Learning) | Raj Kumar Goel Institute of Technology | Raj Kumar Goel Institute of Technology | 21/10/2022 | 795.00 | 519.4 HOR | 90014 | 27/09/2023 | General Books | 22-23/CRB/286 | 1 | 13/09/2023 | |||||
| Dewey Decimal Classification | IOT (Internet of Things) | Raj Kumar Goel Institute of Technology | Raj Kumar Goel Institute of Technology | 21/10/2022 | 795.00 | 519.4 HOR | 90261 | 21/10/2022 | General Books | 22-23/CRB/287 | |||||||
| Dewey Decimal Classification | IOT (Internet of Things) | Raj Kumar Goel Institute of Technology | Raj Kumar Goel Institute of Technology | 21/10/2022 | 795.00 | 519.4 HOR | 90262 | 21/10/2022 | General Books | 22-23/CRB/287 | |||||||
| Dewey Decimal Classification | IOT (Internet of Things) | Raj Kumar Goel Institute of Technology | Raj Kumar Goel Institute of Technology | 21/10/2022 | 795.00 | 519.4 HOR | 90263 | 27/09/2023 | General Books | 22-23/CRB/287 | 5 | 13/09/2023 | |||||
| Dewey Decimal Classification | IOT (Internet of Things) | Raj Kumar Goel Institute of Technology | Raj Kumar Goel Institute of Technology | 21/10/2022 | 795.00 | 519.4 HOR | 90264 | 21/10/2022 | General Books | 22-23/CRB/287 | |||||||
| Dewey Decimal Classification | IOT (Internet of Things) | Raj Kumar Goel Institute of Technology | Raj Kumar Goel Institute of Technology | 21/10/2022 | 795.00 | 519.4 HOR | 90265 | 21/10/2022 | General Books | 22-23/CRB/287 |