Normal view MARC view ISBD view

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
Source of classification or shelving scheme	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