40,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
A friendly introduction to the most useful algorithms written in simple, intuitive English The revised and updated second edition of Essential Algorithms, offers an accessible introduction to computer algorithms. The book contains a description of important classical algorithms and explains when each is appropriate. The author shows how to analyze algorithms in order to understand their behavior and teaches techniques that the can be used to create new algorithms to meet future needs. The text includes useful algorithms such as: methods for manipulating common data structures, advanced data structures, network algorithms, and numerical algorithms. It also offers a variety of general problem-solving techniques. In addition to describing algorithms and approaches, the author offers details on how to analyze the performance of algorithms. The book is filled with exercises that can be used to explore ways to modify the algorithms in order to apply them to new situations. This updated edition of Essential Algorithms: * Contains explanations of algorithms in simple terms, rather than complicated math * Steps through powerful algorithms that can be used to solve difficult programming problems * Helps prepare for programming job interviews that typically include algorithmic questions * Offers methods can be applied to any programming language * Includes exercises and solutions useful to both professionals and students * Provides code examples updated and written in Python and C# Essential Algorithms has been updated and revised and offers professionals and students a hands-on guide to analyzing algorithms as well as the techniques and applications. The book also includes a collection of questions that may appear in a job interview. The book's website will include reference implementations in Python and C# (which can be easily applied to Java and C++).
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 1314
Veröffentlichungsjahr: 2019
Ähnliche
Table of Contents
Cover
Introduction
Why You Should Study Algorithms
Algorithm Selection
Who This Book Is For
Getting the Most Out of This Book
This Book's Websites
How This Book Is Structured
What You Need to Use This Book
Conventions
How to Contact the Author
CHAPTER 1: Algorithm Basics
Approach
Algorithms and Data Structures
Pseudocode
Algorithm Features
Practical Considerations
Summary
Exercises
CHAPTER 2: Numerical Algorithms
Randomizing Data
Finding Greatest Common Divisors
Performing Exponentiation
Working with Prime Numbers
Performing Numerical Integration
Finding Zeros
Gaussian Elimination
Least Squares Fits
Summary
Exercises
CHAPTER 3: Linked Lists
Basic Concepts
Singly Linked Lists
Doubly Linked Lists
Sorted Linked Lists
Self-Organizing Linked Lists
Linked-List Algorithms
Multithreaded Linked Lists
Linked Lists with Loops
Summary
Exercises
CHAPTER 4: Arrays
Basic Concepts
One-Dimensional Arrays
Nonzero Lower Bounds
Triangular Arrays
Sparse Arrays
Matrices
Summary
Exercises
CHAPTER 5: Stacks and Queues
Stacks
Queues
Binomial Heaps
Summary
Exercises
CHAPTER 6: Sorting
Algorithms
Algorithms
Sub
Algorithms
Summary
Exercises
CHAPTER 7: Searching
Linear Search
Binary Search
Interpolation Search
Majority Voting
Summary
Exercises
CHAPTER 8: Hash Tables
Hash Table Fundamentals
Chaining
Open Addressing
Summary
Exercises
CHAPTER 9: Recursion
Basic Algorithms
Graphical Algorithms
Backtracking Algorithms
Selections and Permutations
Recursion Removal
Summary
Exercises
CHAPTER 10: Trees
Tree Terminology
Binary Tree Properties
Tree Representations
Tree Traversal
Sorted Trees
Lowest Common Ancestors
Threaded Trees
Specialized Tree Algorithms
Interval Trees
Summary
Exercises
CHAPTER 11: Balanced Trees
AVL Trees
2-3 Trees
B-Trees
Balanced Tree Variations
Summary
Exercises
CHAPTER 12: Decision Trees
Searching Game Trees
Searching General Decision Trees
Swarm Intelligence
Summary
Exercises
CHAPTER 13: Basic Network Algorithms
Network Terminology
Network Representations
Traversals
Strongly Connected Components
Finding Paths
Transitivity
Shortest Path Modifications
Summary
Exercises
CHAPTER 14: More Network Algorithms
Topological Sorting
Cycle Detection
Map Coloring
Maximal Flow
Network Cloning
Cliques
Community Detection
Eulerian Paths and Cycles
Summary
Exercises
CHAPTER 15: String Algorithms
Matching Parentheses
Pattern Matching
String Searching
Calculating Edit Distance
Phonetic Algorithms
Summary
Exercises
CHAPTER 16: Cryptography
Terminology
Transposition Ciphers
Substitution Ciphers
Block Ciphers
Public-Key Encryption and RSA
Other Uses for Cryptography
Summary
Exercises
CHAPTER 17: Complexity Theory
Notation
Complexity Classes
Reductions
NP-Hardness
Detection, Reporting, and Optimization Problems
NP-Complete Problems
Summary
Exercises
CHAPTER 18: Distributed Algorithms
Types of Parallelism
Distributed Algorithms
Summary
Exercises
CHAPTER 19: Interview Puzzles
Asking Interview Puzzle Questions
Answering Interview Puzzle Questions
Summary
Exercises
APPENDIX A: Summary of Algorithmic Concepts
Chapter 1: Algorithm Basics
Chapter 2: Numeric Algorithms
Chapter 3: Linked Lists
Chapter 4: Arrays
Chapter 5: Stacks and Queues
Chapter 6: Sorting
Chapter 7: Searching
Chapter 8: Hash Tables
Chapter 9: Recursion
Chapter 10: Trees
Chapter 11: Balanced Trees
Chapter 12: Decision Trees
Chapter 13: Basic Network Algorithms
Chapter 14: More Network Algorithms
Chapter 15: String Algorithms
Chapter 16: Cryptography
Chapter 17: Complexity Theory
Chapter 18: Distributed Algorithms
Chapter 19: Interview Puzzles
APPENDIX B: Solutions to Exercises
Chapter 1: Algorithm Basics
Chapter 2: Numerical Algorithms
Chapter 3: Linked Lists
Chapter 4: Arrays
Chapter 5: Stacks and Queues
Chapter 6: Sorting
Chapter 7: Searching
Chapter 8: Hash Tables
Chapter 9: Recursion
Chapter 10: Trees
Chapter 11: Balanced Trees
Chapter 12: Decision Trees
Chapter 13: Basic Network Algorithms
Chapter 14: More Network Algorithms
Chapter 15: String Algorithms
Chapter 16: Encryption
Chapter 17: Complexity Theory
Chapter 18: Distributed Algorithms
Chapter 19: Interview Puzzles
Glossary
Index
End User License Agreement
List of Tables
Chapter 1
Table 1.1: Function Values for Various Inputs
Chapter 2
Table 2.1: PRNG Values and Results Mapped with a Modulus
Table 2.2: Values Used to Calculate GCD(4851, 3003)
Chapter 4
Table 4.1: Entries in Triangular Arrays
Chapter 6
Table 6.1: Algorithm Characteristics
Chapter 7
Table 7.1: Algorithm Characteristics
Chapter 9
Table 9.1: Run Times for the Tower of Hanoi Puzzle
Chapter 10
Table 10.1: Summary of Tree Terminology
Table 10.2: The Animal Game Trying to Guess Snake
Table 10.3: The Animal Game Trying to Guess Giraffe
Table 10.4: Keys and Values for the Example Trie
Chapter 13
Table 13.1: Summary of Network Terminology
Table 13.2: An Acyclic Network's Reachabilities
Chapter 14
Table 14.1: Kitchen Remodeling Task Dependencies
Table 14.2: Shortest Paths
Chapter 15
Table 15.1: A State Transition Table for
Table 15.2: Soundex Letter Codes
Table 15.3: Refined Soundex Letter Codes
Table 15.4: Soundex Encodings for Example Names
Chapter 16
Table 16.1: Number of Occurrences of the Letters in the Example Ciphertext
Chapter 18
Table 18.1: Run Times with Different Numbers of Processors
Appendix B
Table B.1: Maximum Problem Sizes That Run in Various Times
Table B.2: Cubes for Different Values of N
Table B.3: A State Transition Table for
Table B.4: A State Transition Table for
List of Illustrations
Chapter 1
Figure 1.1: Searching a full binary tree takes O(log N) steps.
Figure 1.2: The log, sqrt, linear, and even polynomial functions grow at a reas...
Figure 1.3: This algorithm generates values for cubes on a cube's “ske...
Figure 1.4: This algorithm adds one more level to the shape as N increases.
Chapter 2
Figure 2.1: Even slightly different seeds lead to very different random trees.
Figure 2.2: This program generates random walks on a square grid.
Figure 2.3: These random directions produce a walk on a triangular lattice.
Figure 2.4: A self-avoiding random walk moves randomly but does not visit any n...
Figure 2.5: A complete self-avoiding random walk visits every node in the latti...
Figure 2.6: The RectangleRule sample program uses the rectangle rule to approxi...
Figure 2.7: The TrapezoidRule sample program uses the trapezoid rule to make a ...
Figure 2.8: The AdaptiveMidpointIntegration program uses an adaptive trapezoid ...
Figure 2.9: The AdaptiveGridIntegration program uses adaptive integration to es...
Figure 2.10: Points inside the shaded region are black, and points outside the ...
Figure 2.11: Newton's method follows a function's tangent lines to zero in on t...
Figure 2.12: The NewtonsMethod sample program demonstrates Newton's method to f...
Figure 2.13: A least squares fit minimizes the sum of the squares of the distan...
Figure 2.14: A high-degree polynomial may match a set of data values very close...
Figure 2.15: You should use lowest-degree polynomial that fits the data reasona...
Chapter 3
Figure 3.1: These linked lists hold the numbers 31, 72, 47, and 9.
Figure 3.2: To add an item at the top of a linked list, make the new cel...
Figure 3.3: To add an item at the end of a linked list, find the last cell and ...
Figure 3.4: Inserting a cell after a given cell takes
time.
Figure 3.5: To remove a cell from a linked list, set the previous cell's...
Figure 3.6: Doubly linked lists often have top and bottom sentinels.
Figure 3.7: When updating a doubly linked list, a program must update both the
Figure 3.8: Self-arranging lists are much faster than fixed lists.
Figure 3.9: Visualizing all the threads through a multithreaded linked list can...
Figure 3.10: Circular linked lists let a program easily loop through a sequence...
Figure 3.11: This list contains a loop that doesn't include all of the list's c...
Figure 3.12: An algorithm can detect a loop by reversing the links in a linked ...
Figure 3.13: T is the distance the tortoise travels to get to the loop, and H i...
Figure 3.14: This program compares the performance of insertionsort and selecti...
Chapter 4
Figure 4.1: You can think of one-, two-, and three-dimensional arrays as arrang...
Figure 4.2: A program can map array entries to memory locations in either row-m...
Figure 4.3: The first step in mapping an item to the
values
array is determinin...
Figure 4.4: In a lower-triangular array, values above the diagonal have a defau...
Figure 4.5: To find the index of an entry, you must figure out how many entries...
Figure 4.6: Adding and removing cells is easier if each linked list begins with...
Figure 4.7: If the target row is missing, the
SetValue
method inserts a new
Arr
...
Figure 4.8: To remove a target entry, the algorithm sets the preceding en...
Chapter 5
Figure 5.1: A stack is similar to a stack of plates at a cafeteria.
Figure 5.2: It's easy to build a stack with a linked list.
Figure 5.3: It's easy to build a stack with an array.
Figure 5.4: Two stacks can share an array if their combined size is limited.
Figure 5.5: You can use stacks to model a train yard sorting a train's cars.
Figure 5.6: You can sort this train in eight moves by using two holding tracks ...
Figure 5.7: The goal in the Tower of Hanoi puzzle is to restack disks from one ...
Figure 5.8: You can model the Tower of Hanoi puzzle with three stacks.
Figure 5.9: As you enqueue and dequeue items in an array-based queue, the occup...
Figure 5.10: In a circular queue, you treat the array's last item as if it come...
Figure 5.11: A binomial tree of order k contains binomial subtrees of order
Figure 5.12: If you make the root of an order 2 tree (in the left dashed circle...
Figure 5.13: Merge two trees with the same order by making one tree's root beco...
Figure 5.14: The goal is to merge these two heaps.
Figure 5.15: This list contains the heaps' merged tree lists.
Figure 5.16: Some of these trees have the same order, so they must be merged.
Figure 5.17: The list now contains three trees in a row that have order 2.
Figure 5.18: At this point, the list ready to be used by a binomial heap.
Figure 5.19: In a bank queue, customers stand in a single line and then are hel...
Chapter 6
Figure 6.1: Insertionsort inserts items into the sorted part of the array.
Figure 6.2: Selectionsort moves the smallest unsorted item to the end of the so...
Figure 6.3: In bubblesort, items that are farther down than they should be slow...
Figure 6.4: Improvements make bubblesort faster, but it still has
performance...
Figure 6.5: In a complete binary tree, every level is full, except possibly the...
Figure 6.6: You can easily store a complete binary tree in an array.
Figure 6.7: In a heap, the value of every node is at least as large as the valu...
Figure 6.8: To add a new value to a heap, place the value at the end of the tre...
Figure 6.9: When the value moves up to a node that already satisfies the heap p...
Figure 6.10: When the value moves up to a node that already satisfies the heap ...
Figure 6.11: If the divider item divides the array into equal halves, the algor...
Figure 6.12: Bucketsort moves items into buckets, sorts the buckets, and then c...
Chapter 7
Figure 7.1: A linear search examines every item in the array until it finds the...
Figure 7.2: A binary search repeatedly divides the part of the array that might...
Figure 7.3: Interpolation search uses the target item's value to calculate wher...
Chapter 8
Figure 8.1: In a hash table with chaining, each bucket is the top of a linked l...
Figure 8.2: In linear probing, the algorithm adds a constant amount to location...
Figure 8.3: Hash tables that use linear probing are subject to primary clusteri...
Figure 8.4: Quadratic probing reduces primary clustering.
Figure 8.5: The average probe sequence length is shorter with quadratic probing...
Figure 8.6: This interface lets you build and test hash tables.
Chapter 9
Figure 9.1: The Fibonacci algorithm's call tree is filled with duplicated calcu...
Figure 9.2: Calls to the
RecursiveFindOptimalCuts
algorithm come in pairs.
Figure 9.3: In the Tower of Hanoi puzzle, the goal is to move disks from one pe...
Figure 9.4: To move n disks, recursively move the upper
disks to the tempor...
Figure 9.5: This sequence of steps transfers three disks from the first peg to ...
Figure 9.6: This initiator (top) and generator (bottom) create the Koch curve.
Figure 9.7: The Koch curve with levels of recursion 0 through 5 produces these ...
Figure 9.8: Three connected Koch curves form a Koch snowflake.
Figure 9.9: High-level Hilbert curves are made up of four connected lower-level...
Figure 9.10: A Sierpiński curve is made up of four smaller Sierpińsk...
Figure 9.11: The level 1 Sierpiński curve is made up of pieces that go ri...
Figure 9.12: The level 2 Right piece is made up of pieces that go right, down, ...
Figure 9.13: To create a Sierpiński gasket, divide a triangle into four p...
Figure 9.14: To create a Sierpiński carpet, divide a square into nine pie...
Figure 9.15: The skyline problem produces an outline similar to the outline of ...
Figure 9.16: The light and dark skylines on the right correspond to the light a...
Figure 9.17: In the eight queens problem, you must position eight queens on a ch...
Figure 9.18: In chess, a knight can move to eight places if none of them lies o...
Figure 9.19: In the polygon method, horizontal lines represent matches in a tou...
Figure 9.20: For N teams, you rotate the lines 360 / N degrees between rounds.
Figure 9.21: You can use a wrapped array to model the polygon method.
Figure 9.22: After each round, move the teams down one position in the array, w...
Figure 9.23: Giving the Koch snowflake's generator 80-degree turns creates a s...
Chapter 10
Figure 10.1: Tree data structures usually are drawn with the root at the top.
Figure 10.2: In a complete binary tree, every level is completely full, except ...
Figure 10.3: Full, complete, and perfect binary trees contain an increasing num...
Figure 10.4: These are two representations of the same tree.
Figure 10.5: You can store a heap, or any complete binary tree, conveniently in...
Figure 10.6: Traversals process a tree's nodes in different orders.
Figure 10.7: In a sorted tree, a node's value lies between the values of its le...
Figure 10.8: How you delete a node from a sorted binary tree depends on the nod...
Figure 10.9: If you remove a leaf node from a sorted binary tree, it remains a ...
Figure 10.10: To remove an internal node that has one child, replace it with it...
Figure 10.11: To remove a target node with two children and whose left child ha...
Figure 10.12: Removing a target node with two children whose left child has a r...
Figure 10.13: You can search a sorted tree from the top down to find lowest com...
Figure 10.14: This tree's Euler tour visits the nodes in the order 0, 1, 3, 6, ...
Figure 10.15: A threaded tree contains references that let you move through the...
Figure 10.16: When you insert a node as a left child, its left thread points wh...
Figure 10.17: When you insert a node as a right child, its right thread points ...
Figure 10.18: This knowledge tree can differentiate among dog, cat, fish, snake...
Figure 10.19: This knowledge tree can now differentiate between cat and giraffe...
Figure 10.20: You can use trees to evaluate mathematical expressions.
Figure 10.21: Horizontal lines represent intervals. Vertical lines show which i...
Figure 10.22: Interval tree nodes contain lists of overlapping intervals sorted...
Figure 10.23: The algorithm only needs to check the left overlap list until it ...
Figure 10.24: If each leaf node can hold 100 items and the items are evenly dis...
Figure 10.25: Each box shows a quadtree node's area.
Figure 10.26: A path through a trie defines a string.
Figure 10.27: To add a key that is longer than the corresponding path through t...
Figure 10.28: If a trie already contains nodes to represent a key, simply add a...
Figure 10.29: Instead of storing an internal node's letter in the node, you can...
Figure 10.30: For Exercises 7 through 10, find this tree's traversals.
Figure 10.31: A preorder traversal can generate a textual display of a tree si...
Figure 10.32: To draw a tree, a program must first position it.
Figure 10.33: In an ordered binary tree, you can leave space to indicate missin...
Figure 10.34: This program builds and displays threaded sorted trees.
Chapter 11
Figure 11.1: In the left-left case, the left child's left subtree contains the ...
Figure 11.2: A right rotation rebalances the tree shown in Figure 11.1.
Figure 11.3: A left rotation rebalances the tree if the new node is in the righ...
Figure 11.4: A left rotation followed by a right rotation rebalances the tree i...
Figure 11.5: A left rotation rebalances the tree after node 1 is removed.
Figure 11.6: In a 2-3 tree, every internal node has either two or three childre...
Figure 11.7: Adding a new value to a full leaf node forces a node split.
Figure 11.8: Adding a new value to a full leaf node forces a node split
Figure 11.9: When you delete a value from a node in a 2-3 tree, sometimes a nod...
Figure 11.10: Sometimes when you delete a value from a 2-3 tree, you need to me...
Figure 11.11: In a B-tree, internal nodes hold several values with branches bet...
Figure 11.12: Sometimes when you add a value to a full B-tree node, you can red...
Figure 11.13: Sometimes when you add a value to a full B-tree node, you must sp...
Figure 11.14: Sometimes when you delete a value from a B-tree node, you can red...
Figure 11.15: Sometimes when you delete a value from a B-tree node, you must me...
Figure 11.16: In a B+tree, values are linked to the corresponding data, shown h...
Figure 11.17: Remove value 33 from this AVL tree and rebalance it.
Figure 11.18: Add value 24 to this 2-3 tree and rebalance it.
Figure 11.19: Add value 56 to this B-tree and rebalance it.
Chapter 12
Figure 12.1: To pick a move, the program must assign values to board positions.
Figure 12.2: The value of a tic-tac-toe square is the number of ways you can us...
Figure 12.3: You use a decision tree to model the partition problem.
Figure 12.4: If you don't allow rotation, some solutions are impossible.
Figure 12.5: A boid can see neighbors only within a certain distance and within...
Figure 12.6: Use a swarm of bugs to minimize this strange function.
Figure 12.7: Display the bugs, their best positions, and the global best positi...
Chapter 13
Figure 13.1: In a directed network, arrows show the directions of links.
Figure 13.2: This network contains four links—two connecting node A to nodes B ...
Figure 13.3: In a depth-first traversal, some nodes far from the start node are...
Figure 13.4: In a breadth-first traversal, nodes close to the starting node are...
Figure 13.5: A spanning tree connects all of the nodes in a network.
Figure 13.6: At each step, you add to the spanning tree the least-cost link tha...
Figure 13.7: An EMST is the cheapest way to connect a set of points.
Figure 13.8: You can use a random spanning tree to generate a maze.
Figure 13.9: A network's strongly connected components partition the net...
Figure 13.10: Kosaraju's algorithm traverses the network's links forward and th...
Figure 13.11: A path that follows a spanning tree from one node to another may ...
Figure 13.12: At each step, you add to the shortest path tree the link that giv...
Figure 13.13: A shortest path tree gives the shortest paths from the root node ...
Figure 13.14: A path through a shortest path tree gives the shortest path from ...
Figure 13.15: In a label-correcting algorithm, some nodes' distances may be cor...
Figure 13.16: The shortest paths between all pairs of nodes in a network can be...
Figure 13.17: To find the path from
start_node
to
end_node
with intermediate po...
Figure 13.18: In a network's transitive closure, each node is only one link awa...
Figure 13.19: An acyclic network's transitive reduction is unique.
Figure 13.20: A cyclic network's transitive reduction may not be unique.
Figure 13.21: Curved streets require many points that don't really matter to th...
Figure 13.22: You can expand a node to represent turn penalties.
Figure 13.23: Now the algorithm cannot take a shortcut through an intersection ...
Figure 13.24: You can use an interchange network to represent a network's turn ...
Figure 13.25: The sample program NetworkMaker lets you build, save, and load te...
Figure 13.26: Draw the
Distance
and
Via
arrays for this network.
Chapter 14
Figure 14.1: You can represent a series of partially-ordered tasks as a network...
Figure 14.2: Some maps can be colored with only two colors.
Figure 14.3: If you draw a closed curve without lifting the pencil and without ...
Figure 14.4: You can simplify this network to a single node with one use of Rul...
Figure 14.5: This network is five-colored.
Figure 14.6: This network is not planar, but it can be three-colored.
Figure 14.7: In the maximal flow problem, the goal is to maximize the flow from...
Figure 14.8: A residual capacity network shows the residual capacity of a netwo...
Figure 14.9: The maximal flow through a work assignment network gives optimal a...
Figure 14.10: Try to find the best links to remove from this network to separat...
Figure 14.11: This network shows a solution to the min-flow-cut problem for the...
Figure 14.12: A clique is a subset of mutually connected nodes.
Figure 14.13: You can use the Bron–Kerbosch algorithm to find this network's ma...
Figure 14.14: Links with high edge betweenness connect communities.
Figure 14.15: This picture shows edge betweenness.
Figure 14.16: Fleury's algorithm follows links, preferring nonbridge links.
Figure 14.17: Hierholzer's algorithm merges loops.
Figure 14.18: Use a residual capacity network to find an augmenting path for th...
Figure 14.19: This program uses the Bron–Kerbosch algorithm to find maximal cli...
Chapter 15
Figure 15.1: Lines connect matching pairs of parentheses.
Figure 15.2: You can use parse trees to represent expressions such as
.
Figure 15.3: This network represents the state transitions for a DFA that recog...
Figure 15.4: This network represents the state transitions for a DFA that recog...
Figure 15.5: This transition diagram represents the simple regular expression B...
Figure 15.6: The transition diagram on the right represents the regular express...
Figure 15.7: The transition diagram on the right represents the regular express...
Figure 15.8: The transition diagram on the right represents the regular express...
Figure 15.9: These transition diagrams represent the regular expression
.
Figure 15.10: Using an NFA and null transitions makes combining subexpressions ...
Figure 15.11: Searching
A man a plan a canal Panama
for
Roosevelt
requires only...
Figure 15.12: Searching abba daba abadabracadabra for cadabra requires 18 compa...
Figure 15.13: This edit graph represents possible ways to convert
assent
to
des
...
Figure 15.14: This program, GraphExpression, builds a parse tree for an expres...
Figure 15.15: By following the path through the edit graph, you can show exact...
Chapter 16
Figure 16.1: In a row/column transposition cipher, you write the plaintext into...
Figure 16.2: Decrypting with an
array is equivalent to encrypting with a
...
Figure 16.3: In a column transposition cipher, you write the plaintext into an ...
Figure 16.4: In a route cipher, you write the plaintext into an array by rows a...
Figure 16.5: In a Vigenère cipher, repeat the keyword as many times as ne...
Figure 16.6: This table makes it easier to shift letters in a Vigenère c...
Figure 16.7: In a substitution-permutation network cipher, substitution stages ...
Chapter 17
Figure 17.1: In a bipartite graph, the nodes are divided into two sets, and lin...
Figure 17.2: Detection, reporting, and optimization have the same complexity.
Chapter 18
Figure 18.1: A systolic array of four cells can sort four numbers in 14 ticks.
Figure 18.2: A loyal lieutenant cannot tell the difference between a traitor ge...
Figure 18.3: Three lieutenants can agree on a common decision no matter who the...
Appendix B
Figure B.1: The Fibonacci function increases more quickly than but less...
Figure B.2: Relatively small numbers of trials sometimes result in significant...
Figure B.3: The GcdTimes example program graphs number of GCD steps versus num...
Figure B.4: The MidpointRectangleRule example program reduces error by using...
Figure B.5: To delete a cell from a doubly linked list, change the next and...
Figure B.6: Sorted chaining gives shorter average probe sequence lengths than...
Figure B.7: Double hashing has shorter average probe sequence lengths, but...
Figure B.8: Not all full complete trees are perfect.
Figure B.9: The expression trees on the right represent the expressions on...
Figure B.10: The expression trees on the right represent the expressions on...
Figure B.11: This trie represents the strings APPLE, APP, BEAR, ANT, BAT, a...
Figure B.12: You can rebalance an AVL tree in the right-left case by using a...
Figure B.13: An AVL tree remains balanced even if you add values in sorted or...
Figure B.14: To rebalance the tree at the top, you need to replace value 33...
Figure B.15: When you add the value 24 to the tree on the left, the leaf cont...
Figure B.16: If you remove a value from a 2-3 tree node and the node contain...
Figure B.17: Sometimes bucket splits cascade to the root of a B-tree and the...
Figure B.18: Sometimes when you remove a value, no rebalancing is required.
Figure B.19: Adding 11 values to an empty B-tree of order 2 makes the root n...
Figure B.20: These numbers show how many possible games begin with X taking...
Figure B.21: Because the graph of the logarithm of nodes visited versus numb...
Figure B.22: A shortest path tree is a spanning tree but not necessarily a mi...
Figure B.23: The
Via
and
Distance
arrays give the...
Figure B.24: A fully expanded node with turn penalties contains 20 links.
Figure B.25: The augmenting path in the residual capacity network on the left...
Figure B.26: At most four jobs can be assigned in this work assignment network.
Figure B.27: This DFA state transition diagram matches the regular expression...
Figure B.28: This NFA state transition diagram matches a pattern anywhere wit...
Figure B.29: The parse tree (left) and corresponding NFA network (right) for...
Figure B.30: This DFA state transition diagram matches the same values as the...
Figure B.31: The network on the left contains a Hamiltonian path but no Hamil...
Figure B.32: The bold Hamiltonian path in the network on the right correspond...
Figure B.33: A systolic array of four cells can sort two lists containing fo...
Figure B.34: In the Chandy/Misra solution with synchronized philosophers, ph...
Guide
Cover
Table of Contents
Begin Reading
Pages
iii
xxix
xxx
xxxi
xxxii
xxxiii
xxxiv
xxxv
xxxvi
xxxvii
xxxviii
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
595
596
597
598
599
600
601
602
603
604
605
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
iv
v
vii
ix
xi
xiii
763
Essential Algorithms
A Practical Approach to Computer Algorithms Using Python® and C#
Rod Stephens
CHAPTER 1Algorithm Basics
Before you jump into the study of algorithms, you need a little background. To begin with, you need to know that, simply stated, an algorithm is a recipe for getting something done. It defines the steps for performing a task in a certain way.
