x
Contents
5.5 ORDER OF MAGNITUDE
412
Function Growth
412
More on Analysis of Algorithms
415
The Master Theorem
417
Proof of the Master Theorem
419
SECTiOn 5.5 Review
421
ExErCiSES 5.5
421
5.6 THE MIGHTY MOD FUNCTION
423
Hashing
424
Computer Security
427
Cryptography
427
Hashing for Password
Encryption
433
Miscellaneous Applications
435
Identification Codes
435
Generating and Decomposing
Integers
437
Modular Arithmetic Designs 438
SECTiOn 5.6 Review
440
ExErCiSES 5.6
440
5.7 MATRICES
446
Terminology
446
Matrix Operations
448
Gaussian Elimination
453
Boolean Matrices
458
special interest page
Solve Millions of Equations, Faster than Gauss
460
SECTiOn 5.7 Review
461
ExErCiSES 5.7
461
Chapter 5 Review
470
On the Computer
472
CHAPTEr 6
Graphs and Trees
475
6.1 GRAPHS AND THEIR
REPRESENTATIONS
476
Definitions of a Graph
476
Applications of Graphs
479
Graph Terminology
481
Isomorphic Graphs
484
Planar Graphs
487
Computer Representation
of Graphs
492
Adjacency Matrix
492
Adjacency List
494
special interest page
isomorphic Protein Graphs
497
SECTiOn 6.1 Review
498
ExErCiSES 6.1
498
6.2 TREES AND THEIR
REPRESENTATIONS
509
Tree Terminology
509
Applications of Trees
511
Binary Tree Representation
513
Tree Traversal Algorithms
514
Results about Trees
519
SECTiOn 6.2 Review
521
ExErCiSES 6.2
521
6.3 DECISION TREES
529
Searching
529
Lower Bounds on Searching 532
Binary Tree Search
533
Sorting
535
SECTiOn 6.3 Review
536
ExErCiSES 6.3
536
6.4 HUFFMAN CODES
539
Problem and Trial Solution
539
Huffman Encoding Algorithm
542
Justification
544
Application of Huffman Codes
546
SECTiOn 6.4 Review
547
ExErCiSES 6.4
548
Chapter 6 Review
551
On the Computer
552
CHAPTEr 7
Graph Algorithms
553
7.1 DIRECTED GRAPHS AND BINARY
RELATIONS; WARSHALL’S
ALGORITHM
554
Directed Graphs and
Binary Relations
555
Reachability
557
Warshall’s Algorithm
562