Fundamentals of computer algorithms (Record no. 2167)
[ view plain ]
000 -LEADER | |
---|---|
fixed length control field | 09563nam a2200205Ia 4500 |
003 - CONTROL NUMBER IDENTIFIER | |
control field | OSt |
005 - DATE AND TIME OF LATEST TRANSACTION | |
control field | 20191026020004.0 |
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
fixed length control field | 140801s2011 xx 000 0 und d |
020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
International Standard Book Number | 8175152575 |
082 ## - DEWEY DECIMAL CLASSIFICATION NUMBER | |
Classification number | 003-1 HOR-F |
100 ## - MAIN ENTRY--PERSONAL NAME | |
Personal name | HOROWITZ E |
245 ## - TITLE STATEMENT | |
Title | Fundamentals of computer algorithms |
260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
Name of publisher, distributor, etc | GALGOTIA PUB. |
Date of publication, distribution, etc | 2011 |
300 ## - PHYSICAL DESCRIPTION | |
Extent | 769p. |
500 ## - GENERAL NOTE | |
General note | 1. INTRODUCTION<br/>1.1 What is an algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1<br/>1.2 Writing algorithms in SPARKS . . . . . . . . . . . . . . . . . . . . . . . . .. . . 4<br/>1.3 Writing structured programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14<br/>1.4 Analyzing algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24<br/>References and selected readings , . . . . . . . . . . . . . . . . . . . . . . . . . 40<br/>Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41<br/>2. ELEMENTARY DATA STRUCTURES<br/>2.1 Stacks and queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48<br/>2.2 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53<br/>2.3 Heaps and heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61<br/>2.4 Sets and disjoint set union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70<br/>2.5 Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79<br/>2.6 Hashing................................................ 82<br/>References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . 93<br/>Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94<br/>3. DIVIDE-AND-CONQUER<br/>3 .1 The general method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98<br/>3.2 Binary search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100<br/>3.3 Finding the maximum and minimum. . . . . . . . . . . . . . . . . . . . . . . . 108<br/>3.4 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113<br/>3.5 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121<br/>3.6 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127<br/>3. 7 Strassen's matrix multiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . 137<br/>References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . . 140<br/>Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141<br/>xi <br/>xii Contents<br/>4. THE GREEDY METHOD<br/>4.1 The general method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152<br/>4.2 Optimal storage on tapes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153<br/>4.3 Knapsack problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157<br/>4.4 Job sequencing with deadlines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161<br/>4.5 Optimal merge patterns................................... 169<br/>4.6 Minimum spanning trees.................................. 174<br/>4. 7 Single source shortest paths. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183<br/>References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . . 188<br/>Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191<br/>5. DYNAMIC PROGRAMMING<br/>5.1<br/>5.2<br/>5.3<br/>5.4<br/>5.5<br/>5.6<br/>5.7<br/>5.8<br/>The general method ..................................... .<br/>Multistage graphs ....................................... .<br/>All pairs shortest paths .................................. .<br/>Optimal binary search trees ............................... .<br/>0/1 knapsack .......................................... .<br/>Reliability design ....................................... .<br/>The traveling salesperson problem ......................... .<br/>Flow shop scheduling .................. ·t" ............ .. References and selected readings.......... . .............. .<br/>Exercises .............................................. .<br/>6. BASIC SEARCH AND TRAVERSAL TECHNIQUES<br/>198<br/>203<br/>208<br/>211<br/>219<br/>228<br/>231<br/>234<br/>238<br/>240<br/>6.1 The techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248<br/>6.2 Code optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270<br/>6.3 AND/OR graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286<br/>6.4 Game trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290<br/>6.5 Biconnected components and depth first search . . . . . . . . . . . . . . . 302<br/>References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . . 309<br/>Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311<br/>7. BACKTRACKING<br/>7 .1 The general method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323<br/>7.2 The 8-queens problem.................................... 337<br/>7.3 Sum of subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339<br/>7 .4 Graph coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343<br/>7. 5 Hamiltonian cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348<br/>7.6 Knapsack problem....................................... 350 <br/>Contents xiii<br/>References and selected readings. . . . . . . . . . . . . . . . . . . . . . . . . . . 359<br/>Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363<br/>8. BRANCH-AND-BOUND<br/>8.1 The method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370<br/>8.2 011 knapsack problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390<br/>8.3 Traveling salesperson.................................. . . . 403<br/>8.4 Efficiency considerations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412<br/>References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . . 415<br/>Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417<br/>9. ALGEBRAIC SIMPLIFICATION AND<br/>TRANSFORMATIONS<br/>9.1 The general method...................................... 422<br/>9.2 Evaluation and interpolation..... . . . . . . . . . . . . . . . . . . . . . . . . . . 424<br/>9.3 The fast Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431<br/>9.4 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440<br/>9.5 Even faster evaluation and interpolation . . . . . . . . . . . . . . . . . . . . . 447<br/>References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . . 455<br/>Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457<br/>10. LOWER BOUND THEORY<br/>10 .1 Comparison trees for sorting and searching. . . . . . . . . . . . . . . . . 461<br/>10.2 Oracles and Adversary Arguments . . . . . . . . . . . . . . . . . . . . . . . . 469<br/>10.3 Techniques for algebraic problems.... . . . . . . . . . . . . . . . . . . . . . 478<br/>10.4 Some lower bounds on parallel computation . . . . . . . . . . . . . . . . . 488<br/>References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . 494<br/>Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497<br/>11. NP-HARD AND NP-COMPLETE PROBLEMS<br/>11.1 Basic concepts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501<br/>11.2 Cook's theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513<br/>11.3 NP-Hard graph problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522<br/>11.4 NP-Hard scheduling problems............................ 532<br/>11.5 NP-Hard code generation problems.. . . . . . . . . . . . . . . . . . . . . . . 538<br/>11.6 Some simplified NP-Hard problems. . . . . . . . . . . . . . . . . . . . . . . . 545<br/>References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . 548<br/>Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552 <br/>xiv Contents<br/>12. APPROXIMATION ALGORITHMS FOR NP-HARD<br/>PROBLEMS<br/>12.1 Introduction........................................... 559<br/>12.2 Absolute approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562<br/>12.3 E-approximations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567<br/>12.4 Polynomial time approximation schemes................... 578<br/>12.5 Fully polynomial time approximation schemes . . . . . . . . . . . . . . 585<br/>12.6 Probabilistically good algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 596<br/>References and selected readings. . . . . . . . . . . . . . . . . . . . . . . . . . 599<br/>Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604<br/>APPENDIX A. SPARKS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614<br/>INDEX .................................. |
650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | AIIT |
700 ## - ADDED ENTRY--PERSONAL NAME | |
Personal name | HOROWITZ E |
856 ## - ELECTRONIC LOCATION AND ACCESS | |
Uniform Resource Identifier | <a href="https://nehardblog.files.wordpress.com/2016/03/fundamentals-of-computer-algorithms-by-ellis-horowitz.pdf">https://nehardblog.files.wordpress.com/2016/03/fundamentals-of-computer-algorithms-by-ellis-horowitz.pdf</a> |
942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
Source of classification or shelving scheme | Dewey Decimal Classification |
Koha item type | Books |
Koha issues (borrowed), all copies | 4 |
Withdrawn status | Lost status | Source of classification or shelving scheme | Damaged status | Not for loan | Home library | Current library | Shelving location | Date acquired | Cost, normal purchase price | Total Checkouts | Barcode | Date last seen | Date checked out | Price effective from | Koha item type |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Dewey Decimal Classification | Amity Central Library | Amity Central Library | ASET CSE | 26/05/2011 | 410.00 | 2 | 14042 | 07/12/2018 | 27/11/2018 | 26/05/2011 | Books | ||||
Dewey Decimal Classification | Amity Central Library | Amity Central Library | ASET CSE | 26/05/2011 | 410.00 | 3 | 14043 | 04/12/2019 | 25/10/2019 | 26/05/2011 | Books | ||||
Dewey Decimal Classification | Amity Central Library | Amity Central Library | ASET CSE | 26/05/2011 | 410.00 | 1 | 14044 | 27/11/2019 | 27/08/2019 | 26/05/2011 | Books | ||||
Dewey Decimal Classification | Amity Central Library | Amity Central Library | ASET CSE | 26/05/2011 | 410.00 | 2 | 14045 | 26/08/2019 | 22/07/2019 | 26/05/2011 | Books |