TY  - BOOK
AU  - WILLIAM STALLINGS
AU  - William Stallings
TI  - Computer organisation and architecture
SN  - 9788131732458
PY  - 2010///
PB  - Pearson
N1  - 1 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
UR  - https://books.google.co.in/books?id=Gjx84LGSLA0C&printsec=frontcover&dq=computer+organization+and+architecture+designing+for+performance&hl=en&sa=X&ved=0ahUKEwjZkPP8pKzgAhXQdt4KHZn2CaQQ6AEINTAC#v=onepage&q=computer%20organization%20and%20architecture%20designing%20for%20performance&f=false
ER  -