book

Mastering Algorithms with Perl

by Jarkko Hietaniemi, Jon Orwant, John Macdonald

August 1999

Intermediate to advanced

701 pages

19h 7m

English

O'Reilly Media, Inc.

Read now

Unlock full access

A Note Regarding Supplemental Files
Preface
About This BookTheory or Practice?Organization of This BookConventions Used in This BookWhat You Should Know Before Reading This BookWhat You Should Have Before Reading This BookOnline Information About This BookAcknowledgmentsComments and Questions
1. Introduction
What Is an Algorithm? A Sample Algorithm: Binary Search What do all those funny symbols mean?ReferencesAdapting AlgorithmsGeneralityEfficiencySpace Versus TimeBenchmarkingFloating-Point NumbersTemporary Variables Caching Evaluating Algorithms: O(N) NotationDon’t cheatRecurrent Themes in AlgorithmsRecursionDivide and ConquerDynamic ProgrammingChoosing the Right Representation
2. Basic Data Structures
Perl’s Built-in Data Structures Build Your Own Data Structure A Simple Example Lols and Lohs and Hols and Hohs Objects Using a Constructed Datatype Shortcuts Perl Arrays: Many Data Structures in One Queues Stacks Deques Still More Perl Arrays
3. Advanced Data Structures
Linked Lists Linked List Implementations Tracking Both Ends of Linked Lists Additional Linked List Operations Circular Linked Lists Garbage Collection in Perl Doubly-Linked Lists Infinite Lists The Cost of Traversal Binary Trees Keeping Trees BalancedUser-visible routinesMergingThe actual balancing Heaps Binary Heaps Janus Heap The Heap Modules Future CPAN Modules
4. Sorting
An Introduction to SortingPerl’s sort FunctionASCII OrderNumeric OrderReverse Order: From Highest To Lowest Sort::Fields Sort::Versions Dictionary OrderSorting EfficiencyThe Schwartzian TransformLong duration cachingDeficiency: missing internationalization (locales) Sort::ArbBiLex See for yourself: use the Benchmark moduleSorting Hashes Is Not What You Might ThinkAll Sorts of SortsQuadratic Sorting AlgorithmsSelection sortMinima and maximaBubble sortInsertion sortShellsortLog-Linear Sorting AlgorithmsMergesortHeapsortQuicksortRemoving recursion from quicksortMedian, quartile, percentileBeating O(N log N)Radix sortsCounting sortHybrid sortsBucket sortQuickbubblesortExternal SortingSorting Algorithms SummaryO(N2) SortsSelection sortBubble sort and insertion sortShellsortO(N log N) SortsMergesortQuicksortHow Well Did We Do?
5. Searching
Hash Search and Other Non-Searches Lookup Searches Ransack Search Linear Search Binary Search in a List Proportional Search Binary Search in a Tree Should You Use a List or a Tree for Binary Searching? Bushier Trees Lists of Lists B-Trees Hybrid Searches Lookup Search Recommendations Generative Searches Game Interface Exhaustive Search Alternatives to Exhaustive Search in Games Minimax Pruning Alpha-beta pruning Killer moveTranspose tables Advanced pruning strategies Other strategies Nongame Dynamic Searches Greedy algorithms Branch and bound The A* algorithm Dynamic programming
6. Sets
Venn Diagrams Creating Sets Creating Sets Using Hashes Creating Sets Using Bit Vectors Set Union and Intersection Union Intersection Set Universe Complement Set Null Set Set Union and Intersection Using Hashes Union and Intersection Using Bit Vectors Set Differences Set Difference Set Symmetric Difference Set Differences Using Hashes Set Differences Using Bit Vectors Counting Set Elements Set Relations Set Relations Using Hashes Set Relations Using Bit Vectors The Set Modules of CPAN Set::Scalar Set::Object Set::IntSpan Bit::Vector Set::IntRange Sets of Sets Power Sets Power Sets Using Hashes Multivalued SetsMultivalued LogicFuzzy SetsBagsSets Summary
7. Matrices
Creating MatricesManipulating Individual ElementsFinding the Dimensions of a MatrixDisplaying MatricesAdding or Multiplying ConstantsAdding a Constant to a MatrixAdding a Matrix to a MatrixTransposing a MatrixMultiplying MatricesExtracting a SubmatrixCombining MatricesInverting a MatrixComputing the DeterminantGaussian EliminationEigenvalues and EigenvectorsComputing EigenvaluesUsing PDL to calculate eigenvalues and eigenvectorsCalculating easy eigenvalues directlyThe Matrix Chain ProductDelving Deeper
8. Graphs
Vertices and Edges Edge Direction Vertex Degree and Vertex Classes Derived Graphs Graph TransposeComplete GraphComplement Graph Density Graph Attributes Graph Representation in Computers Our Graph Representation Creating graphs, dealing with vertices Testing for and adding edges Returning edges Density, degrees, and vertex classes Deleting edges and vertices Graph attributes Displaying graphs Graph Traversal Depth-First Search Topological Sortmake as a topological sort Breadth-First Search Implementing Graph TraversalImplementing depth-first traversalImplementing breadth-first traversal Paths and Bridges The Seven Bridges of Königsberg Graph Biology: Trees, Forests, DAGS, Ancestors, and Descendants Parents and ChildrenEdge and Graph Classes Edge Classes Graph Classes: Connectivity BiconnectivityStrongly Connected Graphs Minimum Spanning Trees Kruskal’s minimum spanning tree Prim’s minimum spanning tree Shortest Paths Single-source shortest paths Dijkstra’s single-source shortest pathsBellman-Ford single-source shortest pathsDAG single-source shortest paths All-pairs shortest paths Transitive Closure Flow Networks Ford-Fulkerson Edmonds-Karp Traveling Salesman Problem CPAN Graph Modules

9. Strings
Perl Builtins Exact Matching Regular Expressions Quick tips for regular expressions: readability Quick tips for regular expressions: efficiency study() String-Matching Algorithms Naïve Matching Matching sequences Rabin-Karp Rabin-Karp is a checksum algorithm Handling huge checksums Implementing Rabin-Karp Further checksum experimentation Knuth-Morris-Pratt Boyer-Moore Shift-Op Baeza-Yates-Gonnet Shift-OR Exact Matching Approximate Matching Baeza-Yates-Gonnet Shift-Add Wu-Manber k-differences Longest Common Subsequences Summary of String Matching Algorithms String::Approx Phonetic Algorithms Text::Soundex Text::Metaphone Stemming and Inflection Modules for Stemming and Inflection Text::Stem Text::German Lingua::EN::Inflect Lingua::PT::Conjugate Parsing Finite Automata Grammars Context-free grammars Parsing Up and Down Top-down parsing Bottom-up parsing Interpreters and Compilers Modules for Lexing and Parsing Parse::Lex Parse::RecDescent Text::Abbrev Text::ParseWords Text::DelimMatch String::ShellQuote Text::Balanced Special-purpose parsers Compression Run-Length Encoding Huffman Encoding compress, GNU gzip, pkzip
10. Geometric Algorithms
Distance Euclidean Distance Manhattan Distance Maximum Distance Spherical Distance Area, Perimeter, and Volume Triangle Polygon Area Polygon Perimeter Direction Intersection Line Intersection Line intersection: the general case Line intersection: the horizontal-vertical case Inclusion Point in Polygon Point in Triangle Point in Quadrangle Boundaries Bounding Box Convex Hull Closest Pair of Points Geometric Algorithms SummaryCPAN Graphics Modules2-D ImagesPerl-GimpGDImage::SizePerlMagickPGPLOTCharts a.k.a. Business Graphics3-D ModelingOpenGLRendermanVRMLWidget/GUI ToolkitsPerl/TkOther windowing toolkits
11. Number Systems
Integers and Reals Constants Pure Integer Arithmetic Precision Rounding Numbers Rounding up or down to an integer Rounding to the nearest integer Rounding to a particular decimal point Very Big, Very Small, and Very Precise Numbers Fractions Strange Systems Bits and Bases Bit Vectors Complex Numbers Polar Coordinates Dates and Times Roman Numerals Trigonometry Significant Series Arithmetic and Geometric Progressions The Fibonacci Sequence Harmonic Series The Riemann Zeta Function and Bernoulli Numbers
12. Number Theory
Basic Number Theory Linear Combination Theorem Greatest Common Divisor GCD: Linear Combination Least Common Multiple Prime Numbers Caching: Another Example Noninfinite Arithmetic Modular Arithmetic Chinese Remainder Theorem Modular Division Chinese Remainder Theorem Revisited Treating Chinese remainders as integers Integer Exponentiation Modular Exponentiation Miller-Rabin: Prime Generation Revisited Unsolved Problems Is the Collatz Conjecture False? Is There an Odd Perfect Number? Is the Goldbach Conjecture False?
13. Cryptography
Legal Issues Authorizing People with Passwords Password Hazards Authorization of Data: Checksums and More Obscuring Data: Encryption Perfect Encryption: The One-Time Pad Shared-Secret Encryptions Analysis of Shared-Secret Encryption Encrypting with SSLeay Public Key Encryption RSA Public Key Encryption El Gamal Public Key Encryption Choosing Between Public Key and Private Key Hiding Data: Steganography Winnowing and Chaffing Encrypted Perl Code Other Issues
14. Probability
Random Numbers Don’t Forget to Seed Your Generator Better Randomness Events Will the Blue Jays Win, and Will the Stock Market Go Up? Will Neither the Blue Jays Win nor the Stock Market Go Up? Will the Blue Jays Win or the Stock Market Go Up? Permutations and Combinations Permutations Combinations Probability Distributions Expected Value Rolling Dice: Uniform Distributions Measuring Time: Uniform Continuous Distributions Choosing an Element from an Array Picking Random BigInts Rolling Dice Revisited: Combining Events Loaded Dice and Candy Colors: Nonuniform Discrete Distributions Flipping a Coin: The Binomial Distribution The Binomial Distribution in Poker If the Blue Jays Score Six Runs: Conditional Probability The Vaunted Monty Hall Problem Flipping Coins Over and Over: Infinite Discrete Distributions How Much Snow? Continuous Distributions Many More Distributions The Bernoulli Distribution The Beta Distribution The Binomial Distribution The Cauchy Distribution The Chi Square Distribution The Erlang Distribution The Exponential Distribution The Gamma Distribution The Gaussian (Normal) Distribution The Geometric Distribution The Hypergeometric Distribution The Laplace Distribution The Log Normal Distribution The Maxwell Distribution The Pascal Distribution The Poisson Distribution The Rayleigh Distribution The Uniform Distribution
15. Statistics
Statistical MeasuresThe MeanThe MedianThe ModeStandard Deviation The Standard Score The Variance and Standard Deviation of DistributionsSignificance TestsHow Sure Is Sure?The Sign TestThe z-testThe t-testThe Chi-square testANOVA and the F-testCorrelationComputing the CovarianceComputing the Correlation Coefficient Fitting a Line to Your Data
16. Numerical Analysis
Computing Derivatives and IntegralsComputing the Derivative at a Particular PointComputing the JacobianComputing Definite IntegralsSolving EquationsSimple Roots: Quadratics and CubicsThe quadratic formulaCubic equationsApproximating RootsMultiple Nonlinear EquationsInterpolation, Extrapolation, and Curve FittingFitting a Polynomial to a Set of PointsSplinesCubic splinesData Smoothing
A. Further Reading
General References for Algorithms Graphs, Graphics, and Geometry String Processing and Parsing Numerical Methods General Mathematics Probability and Statistics Other References
B. ASCII Character Set
Index
About the Authors
Colophon
Copyright

Content preview from Mastering Algorithms with Perl

Appendix B. ASCII Character Set

Decimal value	Hexadecimal value	Octal value	Character
0	0x00	000	null
1	0x01	001	start of heading
2	0x02	002	start of text
3	0x03	003	end of text
4	0x04	004	end of transmission
5	0x05	005	enquiry
6	0x06	006	acknowledge
7	0x07	007	bell
8	0x08	010	backspace
9	0x09	011	horizontal tab
10	0x0a	012	NL line feed, newline
11	0x0b	013	vertical tab
12	0x0c	014	NP form feed, new page
13	0x0d	015	carriage return
14	0x0e	016	shift out
15	0x0f	017	shift in
16	0x10	020	data link escape
17	0x11	021	device control 1
18	0x12	022	device control 2
19	0x13	023	device control 3
20	0x14	024	device control 4
21	0x15	025	negative acknowledge
22	0x16	026	synchronous idle
23	0x17	027	end of transmission block
24	0x18	030	cancel
25	0x19	031	end of medium
26	0x1a	032	substitute
27	0x1b	033	escape
28	0x1c	034	file separator
29	0x1d	035	group separator
30	0x1e	036	record separator
31	0x1f	037	unit separator
32	0x20	040	space
33	0x21	041	!
34	0x22	042	"
35	0x23	043	#
36	0x24	044	$
37	0x25	045	%
38	0x26	046	&
39	0x27	047	'
40	0x28	050	(
41	0x29	051	)
42	0x2a	052	*
43	0x2b	053	+
44	0x2c	054	,
45	0x2d	055	-
46	0x2e	056	.
47	0x2f	057	/
48	0x30	060	0
49	0x31	061	1
50	0x32	062	2
51	0x33	063	3
52	0x34	064	4
53	0x35	065	5
54	0x36	066	6
55	0x37	067	7
56	0x38 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 1565923987Errata Page

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Mastering Algorithms with Perl

by Jarkko Hietaniemi, Jon Orwant, John Macdonald

Appendix B. ASCII Character Set

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.