Computer organisation and architecture
WILLIAM STALLINGS
Computer organisation and architecture - Pearson 2010
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
9788131732458
Computer organisation and architecture - Pearson 2010
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
9788131732458