Fundamentals of computer algorithms (Record no. 2167)

MARC details
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
Holdings
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
Web Counter

Powered by Koha