The Art Of Computer Programming Fundamental Algorithms - Donald E Knuth - 1995

Contents
Foreword vii
A Quick Start . . . ix
I   Background 1
1  Proof Machines 3
1.1   Evolution of the province of human thought  . . . . . . . . . . . . . .      3
1.2   Canonical and normal forms  . . . . . . . . . . . . . . . . . . . . . . .      7
1.3   Polynomial identities  . . . . . . . . . . . . . . . . . . . . . . . . . . .      8
1.4   Proofs by example? . . . . . . . . . . . . . . . . . . . . . . . . . . . .      9
1.5   Trigonometric identities   . . . . . . . . . . . . . . . . . . . . . . . . .    11
1.6   Fibonacci identities . . . . . . . . . . . . . . . . . . . . . . . . . . . .    12
1.7   Symmetric function identities  . . . . . . . . . . . . . . . . . . . . . .    12
1.8   Elliptic function identities  . . . . . . . . . . . . . . . . . . . . . . . .    13
2  Tightening the Target 17
2.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    17
2.2   Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    21
2.3   Human and computer proofs; an example . . . . . . . . . . . . . . . .    23
2.4   A Mathematica session . . . . . . . . . . . . . . . . . . . . . . . . . .    27
2.5   A Maple session . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    29
2.6   Where we are and what happens next . . . . . . . . . . . . . . . . . .    30
2.7   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    31
3  The Hypergeometric Database 33
3.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    33
3.2   Hypergeometric series . . . . . . . . . . . . . . . . . . . . . . . . . . .    34
3.3   How to identify a series as hypergeometric  . . . . . . . . . . . . . . .    35
3.4   Software that identifies hypergeometric series . . . . . . . . . . . . . .    39
3.5   Some entries in the hypergeometric database . . . . . . . . . . . . . .    42
3.6   Using the database  . . . . . . . . . . . . . . . . . . . . . . . . . . . .    44
3.7   Is there really a hypergeometric database?  . . . . . . . . . . . . . . .    48
3.8   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    50
II   The Five Basic Algorithms 53
4  Sister Celine’s Method 55
4.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    55
4.2   Sister Mary Celine Fasenmyer  . . . . . . . . . . . . . . . . . . . . . .    57
4.3   Sister Celine’s general algorithm . . . . . . . . . . . . . . . . . . . . .    58
4.4   The Fundamental Theorem   . . . . . . . . . . . . . . . . . . . . . . .    64
4.5   Multivariate and “q” generalizations   . . . . . . . . . . . . . . . . . .    70
4.6   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    72
5  Gosper’s Algorithm 73
5.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    73
5.2   Hypergeometrics to rationals to polynomials  . . . . . . . . . . . . . .    75
5.3   The full algorithm: Step 2  . . . . . . . . . . . . . . . . . . . . . . . .    79
5.4   The full algorithm: Step 3  . . . . . . . . . . . . . . . . . . . . . . . .    84
5.5   More examples   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    86
5.6   Similarity among hypergeometric terms . . . . . . . . . . . . . . . . .    91
5.7   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    95
6  Zeilberger’s Algorithm 101
6.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   101
6.2   Existence of the telescoped recurrence . . . . . . . . . . . . . . . . . .   104
6.3   How the algorithm works . . . . . . . . . . . . . . . . . . . . . . . . .   106
6.4   Examples  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   109
6.5   Use of the programs   . . . . . . . . . . . . . . . . . . . . . . . . . . .   112
6.6   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   118
7  The WZ Phenomenon 121
7.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   121
7.2   WZ proofs of the hypergeometric database  . . . . . . . . . . . . . . .   126
7.3   Spinoffs from the WZ method  . . . . . . . . . . . . . . . . . . . . . .   127
7.4   Discovering new hypergeometric identities  . . . . . . . . . . . . . . .   135
7.5   Software for the WZ method . . . . . . . . . . . . . . . . . . . . . . .   137
7.6   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   140
8  Algorithm Hyper 141
8.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   141
8.2   The ring of sequences . . . . . . . . . . . . . . . . . . . . . . . . . . .   144
8.3   Polynomial solutions  . . . . . . . . . . . . . . . . . . . . . . . . . . .   148
8.4   Hypergeometric solutions . . . . . . . . . . . . . . . . . . . . . . . . .   151
8.5   A Mathematica session . . . . . . . . . . . . . . . . . . . . . . . . . .   156
8.6   Finding all hypergeometric solutions   . . . . . . . . . . . . . . . . . .   157
8.7   Finding all closed form solutions . . . . . . . . . . . . . . . . . . . . .   158
8.8   Some famous sequences that do not have closed form  . . . . . . . . .   159
8.9   Inhomogeneous recurrences . . . . . . . . . . . . . . . . . . . . . . . .   161
8.10 Factorization of operators   . . . . . . . . . . . . . . . . . . . . . . . .   162
8.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   164
III   Epilogue 169
9  An Operator Algebra Viewpoint 171
9.1   Early history   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   171
9.2   Linear difference operators . . . . . . . . . . . . . . . . . . . . . . . .   172
9.3   Elimination in two variables  . . . . . . . . . . . . . . . . . . . . . . .   177
9.4   Modified elimination problem  . . . . . . . . . . . . . . . . . . . . . .   180
9.5   Discrete holonomic functions . . . . . . . . . . . . . . . . . . . . . . .   184
9.6   Elimination in the ring of operators . . . . . . . . . . . . . . . . . . .   185
9.7   Beyond the holonomic paradigm . . . . . . . . . . . . . . . . . . . . .   185
9.8   Bi-basic equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   187
9.9   Creative anti-symmetrizing . . . . . . . . . . . . . . . . . . . . . . . .   188
9.10 Wavelets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   190
9.11 Abel-type identities . . . . . . . . . . . . . . . . . . . . . . . . . . . .   191
9.12 Another semi-holonomic identity   . . . . . . . . . . . . . . . . . . . .   193
9.13 The art   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   193
9.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   195
A The WWW sites and the software 197
A.1  The Maple packages EKHAD and qEKHAD . . . . . . . . . . . . . . . . .   198
A.2  Mathematica programs . . . . . . . . . . . . . . . . . . . . . . . . . .   199
Bibliography 201
Index 208


Other Algoritm Books
Algorithm - Wikipedia, the free encyclopedia
What is algorithm? - Definition from WhatIs.com
Introduction to Genetic Algorithms 
Practical Genetic Algorithms 
Download

How to Design Programs An Introduction to Computing and Programming

Matthias Felleisen
Robert Bruce Findler
Matthew Flatt
Shriram Krishnamurthi

Contents
Preface
Why Everyone Should Learn to Program
Design Recipes
The Choice of Scheme and DrScheme
The Parts of the Book
Acknowledgments
I Processing Simple Forms of Data
1 Students, Teachers, and Computers
2 Numbers, Expressions, Simple Programs
2.1 Numbers and Arithmetic
2.2 Variables and Programs
2.3 Word Problems
2.4 Errors
2.5 Designing Programs
6 Compound Data, Part 1: Structures
6.1 Structures
6.2 Extended Exercise: Drawing Simple Pictures
6.3 Structure Definitions
6.4 Data Definitions
6.5 Designing Functions for Compound Data
6.6 Extended Exercise: Moving Circles and Rectangles
6.7 Extended Exercise: Hangman
7 The Varieties of Data
7.1 Mixing and Distinguishing Data
7.2 Designing Functions for Mixed Data
7.3 Composing Functions, Revisited
7.4 Extended Exercise: Moving Shapes
7.5 Input Errors
8 Intermezzo 1: Syntax and Semantics
8.2 The Scheme Vocabulary
8.3 The Scheme Grammar
8.4 The Meaning of Scheme
8.5 Errors
8.6 Boolean Expressions
8.7 Variable Definitions
8.8 Structure Definitions
II Processing Arbitrarily Large Data
9 Compound Data, Part 2: Lists
9.1 Lists
9.2 Data Definitions for Lists of Arbitrary Length
9.3 Processing Lists of Arbitrary Length
9.4 Designing Functions for Self-Referential Data Definitions
9.5 More on Processing Simple Lists
10 More on Processing Lists
10.1 Functions that Produce Lists
10.2 Lists that Contain Structures
10.3 Extended Exercise:
13 Intermezzo 2: List Abbreviations
III More on Processing Arbitrarily Large Data
14 More Self-referential Data Definitions
14.1 Structures in Structures
14.2 Extended Exercise: Binary Search Trees
14.3 Lists in Lists
14.4 Extended Exercise: Evaluating Scheme
15 Mutually Referential Data Definitions
15.1 Lists of Structures, Lists in Structures
15.2 Designing Functions for Mutually Referential Definitions
15.3 Extended Exercise: More on Web Pages
16 Development through Iterative Refinement
16.1 Data Analysis
16.2 Defining Data Classes and Refining Them
16.3 Refining Functions and Programs
17 Processing Two Complex Pieces of Data
17.1 Processing Two Lists Simultaneously: Case 1
17.2 Processing Two Lists Simultaneously: Case 2
17.3 Processing Two Lists Simultaneously: Case 3
17.4 Function Simplification
17.5 Designing Functions that Consume Two Complex Inputs
17.6 Exercises on Processing Two Complex Inputs
17.7 Extended Exercise: Evaluating Scheme, Part 2
17.8 Equality and Testing
18 Intermezzo 3: Local Definitions and Lexical Scope
18.2 Organizing Programs with local
Syntax of local
Semantics of local
20 Functions are Values
20.1 Syntax and Semantics
20.2 Contracts for Abstract and Polymorphic Functions
21 Designing Abstractions from Examples
21.1 Abstracting from Examples
21.2 Finger Exercises with Abstract List Functions
21.3 Abstraction and a Single Point of Control
21.4 Extended Exercise: Moving Pictures, Again
21.5 Note: Designing Abstractions from Templates
22 Designing Abstractions with First-Class Functions
22.1 Functions that Produce Functions
22.2 Designing Abstractions with Functions-as-Values
22.3 A First Look at Graphical User Interface
23 Mathematical Examples
23.1 Sequences and Series
23.2 Arithmetic Sequences and Series
23.3 Geometric Sequences and Series
Taylor Series
23.4 The Area Under a Function
23.5 The Slope of a Function
24 Intermezzo 4: Defining Functions on the Fly
Syntax of lambda
Scope and Semantics of lambda
Pragmatics of lambda
V Generative Recursion
25 A New Form of Recursion
25.1 Modeling a Ball on a Table
25.2 Sorting Quickly
26 Designing Algorithms
26.1 Termination
26.2 Structural versus Generative Recursion
26.3 Making Choices
29 Intermezzo 5: The Cost of Computing and Vectors
29.2 Concrete Time, Abstract Time
29.3 The Definition of ``on the Order of''
29.4 A First Look at Vectors
VI Accumulating Knowledge
30 The Loss of Knowledge
30.1 A Problem with Structural Processing
30.2 A Problem with Generative Recursion
31 Designing Accumulator-Style Functions
31.1 Recognizing the Need for an Accumulator
31.2 Accumulator-Style Functions
31.3 Transforming Functions into Acc
32 More Uses of Accumulation
32.1 Extended Exercise: Accumulators on Trees
32.2 Extended Exercise: Missionaries and Cannibals
32.3 Extended Exercise: Board Solitaire
33 Intermezzo 6: The Nature of Inexact Numbers
33.2 Fixed-size Number Arithmetic
33.3 Overflow
33.4 Underflow
33.5 DrScheme's Numbers
VII Changing the State of Variables
34 Memory for Functions
35 Assignment to Variables
35.1 Simple Assignments at Work
35.2 Sequencing Expression Evaluations
35.3 Assignments and Functions
35.4 A First Useful Example
38 Intermezzo 7: The Final Syntax and Semantics
38.2 The Vocabulary of Advanced Scheme
38.3 The Grammar of Advanced Scheme
38.4 The Meaning of Advanced Scheme
38.5 Errors in Advanced Scheme
VIII Changing Compound Values
39 Encapsulation
39.1 Abstracting with State Variables
39.2 Practice with Encapsulation
40 Mutable Structures
40.1 Structures from Functions
40.2 Mutable Functional Structures
40.3 M

Other Algorithm Books
Other Computing Books
Computing - Wikipedia, the free encyclopedia
Computer programming - Wikipedia, the free encyclopedia
Grid Computing
Data Structures and Algorithms with Object-Oriented Design Patterns in Java
Download

Foundations of Algorithms Using C++ Pseudocode

Third Edition
by Richard Neapolitan and Kumarss Naimipour ISBN:0763723878
Jones and Bartlett Publishers © 2004 (618 pages)
This text offers a well-balanced presentation on designing algorithms, complexity analysis of algorithms, and computational complexity that is accessible to mainstream computer science students.




Table of Contents
Foundations of Algorithms Using C++ Pseudocode, Third Edition
Preface
Chapter 1 - Algorithms—Efficiency, Analysis, and Order
Chapter 2 - Divide-and-Conquer
Chapter 3 - Dynamic Programming
Chapter 4 - The Greedy Approach
Chapter 5 - Backtracking
Chapter 6 - Branch-and-Bound
Chapter 7 - Introduction to Computational Complexity—The Sorting Problem
Chapter 8 - More Computational Complexity—The Searching Problem
Chapter 9 - Computational Complexity and Interactability—An Introduction to the Theory of NP
Chapter 10 - Number-Theoretic Algorithms
Chapter 11 - Introduction to Parallel Algorithms
Appendix A - Review of Necessary Mathematics
Appendix B - Solving Recurrence Equations—With Applications to Analysis of Recursive Algorithms
Appendix C - Data Structures for Disjoint Sets
References
Index
List of Figures
List of Tables
List of Algorithms, Examples, and Theorems
List of Sidebars


Algorithm - Wikipedia, the free encyclopedia
Algorithms
Dictionary of Algorithms and Data Structures
Data Structures and Algorithms with Object-Oriented Design Patterns in Java
Practical Genetic Algorithms
Other Algorithm Books
Download

Data Compression-The Complete Reference-Appendixes & Solution

Contents
A. The ASCII Code 823
1 ASCII Features 823
B. Basics of Probability 827
1 Joint and Union of Events 830
2 Conditional Probability 831
3 Probability Distributions 834
C. Curves That Fill Space 841
1 The Hilbert Curve 841
2 The Sierpi´nski Curve 842
3 Traversing the Hilbert Curve 848
4 Traversing the Peano Curve 850
D. Data Structures 853
1 Arrays 854
2 Stacks and Queues 855
3 Lists 855
4 Trees 856
5 Graphs 860
6 Hashing 861
7 Hash Functions 862
8 Collision Handling 863
E. Error Correcting Codes 867
1 First Principles 867
2 Voting Codes 869
3 Check Bits 870
4 Parity Bits 871
5 Hamming Distance and Error Detecting 872
6 Hamming Codes 874
7 The SEC-DED Code 876
8 Generating Polynomials 877

F. Finite State Automata 879
G. Gallery of Images 883
H. Human Visual System 887
1 Color and the Eye 887
2 The HLS Color Model 889
3 The HSV Color Model 890
4 The RGB Color Model 890
5 Additive and Subtractive Colors 892
6 Complementary Colors 895
7 Human Vision 895
8 Luminance and Chrominance 897
9 Spectral Density 901
10 The CIE Standard 904
11 Halftoning 906
12 Dithering 908
I. Introductory Mathematics 919
1 Useful Sums 919
2 Matrices 920
3 Trigonometric Identities 923
4 Vector Algebra 925
5 Complex Numbers 928
6 Convolution 930
7 Voronoi Diagrams 934
8 L Systems 935
9 The Greek Alphabet 940
10 Interpolating Polynomials 940
Glossary 947
Answers to Exercises 975
Index 1049

Other Algorithm Books
Download

Data Compression The Complete Reference (2004), 3Ed

Contents
Preface to the Third Edition vii
Preface to the Second Edition xi
Preface to the First Edition xv
Introduction 1
1 Basic Techniques 15
1.1 Intuitive Compression 15
1.2 Run-Length Encoding 20
1.3 RLE Text Compression 21
1.4 RLE Image Compression 25
1.5 Move-to-Front Coding 35
1.6 Scalar Quantization 39
2 Statistical Methods 43
2.1 Information Theory Concepts 44
2.2 Variable-Size Codes 50
2.3 Prefix Codes 51
2.4 The Golomb Code 57
2.5 The Kraft-MacMillan Inequality 65
2.6 The Counting Argument 66
2.7 Shannon-Fano Coding 66
2.8 Huffman Coding 68
2.9 Adaptive Huffman Coding 84
2.10 MNP5 90
2.11 MNP7 95
2.12 Reliability 96
2.13 Facsimile Compression 99
2.14 Arithmetic Coding 106
2.15 Adaptive Arithmetic Coding 120
2.16 The QM Coder 124
2.17 Text Compression 133
2.18 PPM 134
2.19 Context-Tree Weighting 156
3 Dictionary Methods 165
3.1 String Compression 167
3.2 Simple Dictionary Compression 168
3.3 LZ77 (Sliding Window) 169
3.4 LZSS 173
3.5 Repetition Times 176
3.6 QIC-122 178
3.7 LZX 180
3.8 File Differencing: VCDIFF 183
3.9 LZ78 185
3.10 LZFG 188
3.11 LZRW1 191
3.12 LZRW4 194
3.13 LZW 195
3.14 LZMW 206
3.15 LZAP 208
3.16 LZY 209
3.17 LZP 211
3.18 Repetition Finder 218
3.19 UNIX Compression 221
3.20 GIF Images 222
3.21 The V.42bis Protocol 223
3.22 Various LZ Applications 223
3.23 Deflate: Zip and Gzip 224
3.24 PNG 236
3.25 XML Compression: XMill 240
3.26 EXE Compressors 242
3.27 CRC 243
3.28 Summary 246
3.29 Data Compression Patents 246
3.30 A Unification 248
4 Image Compression 251
4.1 Introduction 253
4.2 Approaches to Image Compression 259
4.3 Intuitive Methods 273
4.4 Image Transforms 274
4.5 Orthogonal Transforms 279
4.6 The Discrete Cosine Transform 289
4.7 Test Images 325
4.8 JPEG 329
4.9 JPEG-LS 346
4.10 Progressive Image Compression 352
4.11 JBIG 360
4.12 JBIG2 369
4.13 Simple Images: EIDAC 380
4.14 Vector Quantization 382
4.15 Adaptive Vector Quantization 390
4.16 Block Matching 395
4.17 Block Truncation Coding 399
4.18 Context-Based Methods 405
4.19 FELICS 408
4.20 Progressive FELICS 411
4.21 MLP 415
4.22 Adaptive Golomb 423
4.23 PPPM 424
4.24 CALIC 426
4.25 Differential Lossless Compression 429
4.26 DPCM 431
4.27 Context-Tree Weighting 436
4.28 Block Decomposition 437
4.29 Binary Tree Predictive Coding 441
4.30 Quadtrees 448
4.31 Quadrisection 465
4.32 Space-Filling Curves 473
4.33 Hilbert Scan and VQ 474
4.34 Finite Automata Methods 477
4.35 Iterated Function Systems 494
4.36 Cell Encoding 511
5 Wavelet Methods 513
5.1 Fourier Transform 513
5.2 The Frequency Domain 514
5.3 The Uncertainty Principle 518
5.4 Fourier Image Compression 521
5.5 The CWT and Its Inverse 524
5.6 The Haar Transform 530
5.7 Filter Banks 549
5.8 The DWT 559
5.9 Multiresolution Decomposition 572
5.10 Various Image Decompositions 573
5.11 The Lifting Scheme 580
5.12 The IWT 591
5.13 The Laplacian Pyramid 593
5.14 SPIHT 597
5.15 CREW 609
5.16 EZW 609
5.17 DjVu 613
5.18 WSQ, Fingerprint Compression 616
5.19 JPEG 2000 622
6 Video Compression 637
6.1 Analog Video 637
6.2 Composite and Components Video 643
6.3 Digital Video 645
6.4 Video Compression 649
6.5 MPEG 661
6.6 MPEG-4 683
6.7 H.261 688
7 Audio Compression 691
7.1 Sound 692
7.2 Digital Audio 695
7.3 The Human Auditory System 698
7.4 µ-Law and A-Law Companding 704
7.5 ADPCM Audio Compression 710
7.6 MLP Audio 712
7.7 Speech Compression 717
7.8 Shorten 725
7.9 MPEG-1 Audio Layers 729
8 Other Methods 755
8.1 The Burrows-Wheeler Method 756
8.2 Symbol Ranking 761
8.3 ACB 765
8.4 Sort-Based Context Similarity 772
8.5 Sparse Strings 777
8.6 Word-Based Text Compression 789
8.7 Textual Image Compression 793
8.8 Dynamic Markov Coding 799
8.9 FHM Curve Compression 808
8.10 Sequitur 811
8.11 Triangle Mesh Compression: Edgebreaker 816
8.12 SCSU: Unicode Compression 827
Bibliography 835
Glossary 855
Joining the Data Compression Community 877
Index 879

Other Algorithm Books
Download

Ant Colony Optimization

Contents
Preface ix
Acknowledgments xiii
1 From Real to Artificial Ants 1
1.1 Ants’ Foraging Behavior and Optimization 1
1.2 Toward Artificial Ants 7
1.3 Artificial Ants and Minimum Cost Paths 9
1.4 Bibliographical Remarks 21
1.5 Things to Remember 22
1.6 Thought and Computer Exercises 23
2 The Ant Colony Optimization Metaheuristic 25
2.1 Combinatorial Optimization 25
2.2 The ACO Metaheuristic 33
2.3 How Do I Apply ACO? 38
2.4 Other Metaheuristics 46
2.5 Bibliographical Remarks 60
2.6 Things to Remember 61
2.7 Thought and Computer Exercises 63
3 Ant Colony Optimization Algorithms for the Traveling Salesman
Problem 65
3.1 The Traveling Salesman Problem 65
3.2 ACO Algorithms for the TSP 67
3.3 Ant System and Its Direct Successors 69
3.4 Extensions of Ant System 76
3.5 Parallel Implementations 82
3.6 Experimental Evaluation 84
3.7 ACO Plus Local Search 92
3.8 Implementing ACO Algorithms 99
3.9 Bibliographical Remarks 114
3.10 Things to Remember 117
3.11 Computer Exercises 117
4 Ant Colony Optimization Theory 121
4.1 Theoretical Considerations on ACO 121
4.2 The Problem and the Algorithm 123
4.3 Convergence Proofs 127
4.4 ACO and Model-Based Search 138
4.5 Bibliographical Remarks 149
4.6 Things to Remember 150
4.7 Thought and Computer Exercises 151
5 Ant Colony Optimization for NP -Hard Problems 153
5.1 Routing Problems 153
5.2 Assignment Problems 159
5.3 Scheduling Problems 167
5.4 Subset Problems 181
5.5 Application of ACO to Other NP -Hard Problems 190
5.6 Machine Learning Problems 204
5.7 Application Principles of ACO 211
5.8 Bibliographical Remarks 219
5.9 Things to Remember 220
5.10 Computer Exercises 221
6 AntNet: An ACO Algorithm for Data Network Routing 223
6.1 The Routing Problem 223
6.2 The AntNet Algorithm 228
6.3 The Experimental Settings 238
6.4 Results 243
6.5 AntNet and Stigmergy 252
6.6 AntNet, Monte Carlo Simulation, and Reinforcement Learning 254
6.7 Bibliographical Remarks 257
6.8 Things to Remember 258
6.9 Computer Exercises 259
7 Conclusions and Prospects for the Future 261
7.1 What Do We Know about ACO? 261
7.2 Current Trends in ACO 263
7.3 Ant Algorithms 271
Appendix: Sources of Information about the ACO Field 275
References 277
Index 301

Another Algorithm Books
Download

Algorithms and Complexity

CONTENTS
Chapter 0: What This Book Is About
0.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.2 Hard vs. easy problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.3 A preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Chapter 1: Mathematical Preliminaries
1.1 Orders of magnitude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Positional number systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Manipulations with series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Recurrence relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Chapter 2: Recursive Algorithms
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3 Recursive graph algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4 Fast matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.5 The discrete Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.6 Applications of the FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.7 A review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Chapter 3: The Network Flow Problem
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2 Algorithms for the network flow problem . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3 The algorithm of Ford and Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.4 The max-flow min-cut theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.5 The complexity of the Ford-Fulkerson algorithm . . . . . . . . . . . . . . . . . . . . . 70
3.6 Layered networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.7 The MPM Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.8 Applications of network flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Chapter 4: Algorithms in the Theory of Numbers
4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.2 The greatest common divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.3 The extended Euclidean algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.4 Primality testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.5 Interlude: the ring of integers modulo n . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.6 Pseudoprimality tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.7 Proof of goodness of the strong pseudoprimality test . . . . . . . . . . . . . . . . . . . . 94
4.8 Factoring and cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.9 Factoring large integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.10 Proving primality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Chapter 5: NP-completeness
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.2 Turing machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.3 Cook’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.4 Some other NP-complete problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.5 Half a loaf ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.6 Backtracking (I): independent sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.7 Backtracking (II): graph coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.8 Approximate algorithms for hard problems . . . . . . . . . . . . . . . . . . . . . . . . 128

Another Algorithm Books
Download

Algorithm Analysis And Computational Complexity

Book excerpts:

These lecture notes are almost exact copies of the overhead projector transparencies used by the author in his course of Algorithm Analysis and Complexity Theory at the University of North Texas. The material comes from:
- textbooks on algorithm design and analysis,
- textbooks on other subjects,
- research monographs,
- papers in research journals and conference.

Since this is not a textbook, readers probably already aware that to get the best use of this note they need to attend the course itself. Not to worry though, the note itself is readable, neatly summarized and contains 219 sophisticated graphics. It makes a good reference.

Then again, readers are expected to able to program in some procedural programming language such as C or C++, and to be able to deal with discrete mathematics. Some familiarity with basic data structures and algorithm analysis techniques is also assumed.


Another Algorithm Books
Download

A Primer on Integral Equations of the First Kind: The Problem of Deconvolution and Unfolding

A Primer on Integral Equations of the First Kind: The Problem of Deconvolution and Unfolding
Society for Industrial Mathematics | January 1, 1987 | ISBN-10: 0898712637 | 149 pages | File type: PDF

This book is designed to offer applied mathematicians, physicists, chemists, engineers, geophysicists, and other scientists an elementary level explanation of integral equations of the first kind. It maintains a casual, conversational approach. The book emphasizes understanding, while deliberately avoiding special methods of highly limited application.


Table of Contents

Front Matter FREE [ PDF ]

1. An Introduction to the Basic Problem [ PDF ]

2. Some Examples [ PDF ]

3. A Bit of Functional Analysis [ PDF ]

4. Integral Operators with Separable Kernels [ PDF ]

5. Integral Operators with General Kernels [ PDF ]

6. Some Methods of Resolving Integral Equations of the First Kind [ PDF ]

7. Some Impoant Miscellany [ PDF ]

8. Epilogue [ PDF ]

Appendix A: The Domain of K(x, y) [ PDF ]

Appendix B: Remarks about Complex Functions, Vectors, and Operators [ PDF ]

Appendix C: Modes of Convergence [ PDF ]


Another Algorithm Books
Download

A Concise Introduction To Data Compression

Contents
Preface vii
Part I: Basic Concepts 1
Introduction 5
1 Approaches to Compression 21
1.1 Variable-Length Codes 25
1.2 Run-Length Encoding 41
Intermezzo: Space-Filling Curves 46
1.3 Dictionary-Based Methods 47
1.4 Transforms 50
1.5 Quantization 51
Chapter Summary 58
2 Huffman Coding 61
2.1 Huffman Encoding 63
2.2 Huffman Decoding 67
2.3 Adaptive Huffman Coding 76
Intermezzo: History of Fax 83
2.4 Facsimile Compression 85
Chapter Summary 90
3 Dictionary Methods 93
3.1 LZ78 95
Intermezzo: The LZW Trio 98
3.2 LZW 98
3.3 Deflate: Zip and Gzip 108
Chapter Summary 119
Part II: Advanced Techniques 121
4 Arithmetic Coding 123
4.1 The Basic Idea 124
4.2 Implementation Details 130
4.3 Underflow 133
4.4 Final Remarks 134
Intermezzo: The Real Numbers 135
4.5 Adaptive Arithmetic Coding 137
4.6 Range Encoding 140
Chapter Summary 141
5 Image Compression 143
5.1 Introduction 144
5.2 Approaches to Image Compression 146
Intermezzo: History of Gray Codes 151
5.3 Image Transforms 152
5.4 Orthogonal Transforms 156
5.5 The Discrete Cosine Transform 160
Intermezzo: Statistical Distributions 178
5.6 JPEG 179
Intermezzo: Human Vision and Color 184
5.7 The Wavelet Transform 198
5.8 Filter Banks 216
5.9 WSQ, Fingerprint Compression 218
Chapter Summary 225
6 Audio Compression 227
6.1 Companding 230
6.2 The Human Auditory System 231
Intermezzo: Heinrich Georg Barkhausen 234
6.3 Linear Prediction 235
6.4 µ -Law and A-Law Companding 238
6.5 Shorten 244
Chapter Summary 245
7 Other Methods 247
7.1 The Burrows–Wheeler Method 248
Intermezzo: Fibonacci Codes 253
7.2 Symbol Ranking 254
7.3 SCSU: Unicode Compression 258
Chapter Summary 263
Bibliography 265
Glossary 271
Solutions to Puzzles 281
Answers to Exercises 283
Index 305

Another Algorithm Books
Download

Mathematics for Algorithm and Systems Analysis

Unit CL: Basic Counting and Listing
Section 1: Lists with Repetitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .CL-1
set, list, multiset, sequence, word, permutation, k-set, k-list, k-multiset, k-lists
with repetition, rule of product, Cartesian product, lexicographic order (lex order),
dictionary order, rule of sum, composition of a positive integer
Section 2: Lists Without Repetition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CL-9
k-lists without repetition, Stirling’s formula for approximating n!, circular arrange-
ments, words from a collection of letters
Section 3: Sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .CL-13
set intersection, set union, set difference, set complement, symmetric difference, set
product (Cartesian product), binomial coefficients, generating functions, binomial
theorem, full house (card hand), two pairs (card hand), rearranging words, multino-
mial coefficients, card hands and multinomial coefficients, recursions, set partitions,
Stirling numbers of the second kind (S(n, k)), straight (card hand), Bell numbers
B n
Section 4: Probability and Basic Counting. . . . . . . . . . . . . . . . . . . . . . . . . .CL-28
sample space, selections done uniformly at random, event, probability function,
combining events, Venn diagrams, odds, hypergeometric probabilities, fair dice,
geometric probability, principle of inclusion exclusion, birthday problem
Multiple Choice Questions for Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CL-41
Unit Fn: Functions
Section 1: Some Basic Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fn-1
direct product, intersection, union, symmetric difference, domain, range, codomain,
one-line notation, surjection, onto, injection, one-to-one, bijection, permutation,
relation, functional relation, two-line notation
Section 2: Permutations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Fn-7
composition, cycle, cycle form of permutation, involution, permutation matrices,
derangements
Section 3: Other Combinatorial Aspects of Functions. . . . . . . . . . . . . .Fn-14
image, inverse image, coimage, image size and Stirling numbers, strictly increasing,
strictly decreasing, weakly increasing, weakly decreasing, monotone, multisets, lists
without repetition, restricted growth functions and partitions
Section 4: Functions and Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fn-21
random variable, probability function, event, probability distribution function, ex-
pectation, covariance, variance, standard deviation, correlation, independent events,
independent random variables, product spaces, generating random permutations,
joint distribution function, marginal distributions, binomial distribution, Poisson
distribution, normal distribution, standard normal distribution, cumulative distri-
bution, central limit theorem, normal approximation to binomial, Poisson approx-
imation to binomial, Tchebycheff’s inequality
Multiple Choice Questions for Review. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Fn-41
Unit DT: Decision Trees and Recursion
Section 1: Basic Concepts of Decision Trees. . . . . . . . . . . . . . . . . . . . . . . . . DT-1
decision trees, vertices, root, edges, degree of vertex, down degree, child, parent,
leaves, internal vertex, height of leaf, path to vertex, traversals of decision tree,
depth first vertices, depth first edges, breadth first, preorder, postorder, length-
first lex order, dictionary order, permutations in lex order, partial permutation,
rank of leaf, direct insertion order for permutations, backtracking, Latin squares,
domino coverings, strictly decreasing functions, unlabeled balls into boxes, isomorph
rejection
Section 2: Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DT-15
recursive algorithm, simplest case reduction, recursive algorithm for 0-1 sequences,
sorting by recursive merging, recursive approach, recursive solutions, local descrip-
tion for permutations in lex order, recursive description of Towers of Hanoi, decision
tree for Towers of Hanoi, recursion and stacks, configuration analysis of Towers of
Hanoi, abandoned leaves and RANK, characteristic functions and subsets, Gray
code for subsets, decision tree for Gray code for subsets, local description of Gray
code, Towers of Hanoi with four poles
Section 3: Decision Trees and Conditional Probability . . . . . . . . . . . . DT-27
conditional probability, independent events, Venn diagrams, probabilities of leaves,
probabilities of edges, probabilistic decision trees, decision trees and Bayesian meth-
ods, Bayes’ theorem, multiplication theorem for conditional probabilities, sequen-
tial sampling, the SAT problem, first moment method, tournaments, gambler’s ruin
problem
Section 4: Inductive Proofs and Recursive Equations . . . . . . . . . . . . . DT-40
induction, recursive equations, induction hypothesis, inductive step, base case,
prime factorization, sum of first n integers, local description, recurrence relation,
binomial coefficients C(n, k), Stirling numbers S(n, k), guessing solutions to recur-
rences, linear two term recurrence, constant coefficients, characteristic equation,
two real roots, one real root, complex roots, recursion for derangements, Fibonacci
recurrence relation, recurrence relation for derangements
Multiple Choice Questions for Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DT-52
Unit GT: Basic Concepts in Graph Theory
Section 1: What is a Graph?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . GT-1
computer network example, simple graph, graph, vertices, edges, set theoretic de-
scription of graph, pictorial description of a graph, incidence function, vertices
joined by an edge, adjacent vertices, edge incident on a vertex, simple graphs are
graphs, form of a graph, equivalence relations, equivalence classes, blocks, binary
relations, reflexive, symmetric, transitive, equivalent forms, isomorphism of graphs,
graph isomorphism as an equivalence relation, degree of a vertex, loops, parallel
edges, isolated vertices, degree sequences and isomorphism, random graphs
Section 2: Digraphs, Paths, and Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . GT-13
flow of commodities, directed graph, digraph, simple digraph, simple graphs as
simple digraphs, directed loops, digraphs and binary relations, symmetric binary
relations and simple graphs with loops, complete simple graphs, path, trail, walk,
vertex sequence, walk implies path, restrictions of incidence functions, subgraphs,
subgraph induced by edges, subgraph induced by vertices, cycles, connected graphs,
connected components and equivalence classes, connectivity in digraphs, Eulerian
trail, Eulerian circuit, Hamiltonian cycle, Hamiltonian graph, bicomponents of
graphs, bipartite graphs, oriented simple graphs, antisymmetry, order relations,
Hasse diagrams, covering relations, counting trees
Section 3: Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . GT-24
tree, alternative definitions of a tree, rooted graph, rooted tree, parent, child,
sibling, leaf, internal vertices, unique paths in trees, rooted plane tree, RP-tree,
traversing RP-trees, depth first sequences, breadth first sequences, spanning trees,
minimum spanning trees, greedy algorithms, Prim’s algorithm, Kruskal’s algorithm,
lineal or depth-first spanning trees, algorithm for depth-first spanning trees, bipar-
tite graphs and depth first spanning trees, degree sequences of trees, binary trees,
full binary trees, height and leaf restrictions in binary trees
Section 4: Rates of Growth and Analysis of Algorithms . . . . . . . . . . GT-37
comparing algorithms, machine independence, example of finding the maximum, Θ
notation, O notation, properties of Θ and O, Θ as an equivalence relation, suffi-
ciently large, eventually positive, asymptotic, “little oh” notation, using Θ to com-
pare polynomial evaluation algorithms, average running time, tractable, intractable,
graph coloring problem, traveling salesman problem, clique problem, NP-complete
problems, NP-hard, NP-easy, chromatic number of a graph, almost good algo-
rithms, almost correct algorithms, close algorithms, polynomial time, exponential
time, Θ and series, Θ and logs
Multiple Choice Questions for Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . GT-51
Solutions to Exerciseshttp://www.blogger.com/img/blank.gif
Notation Index
Subject Index

Another Algorithms Books
Another The Core of CS Books
Download

Algorithms

Contents
Introduction . . . . . . . . . . . . . . . . . . . . . .
Algorithms, Outline of Topics
1. Preview. . . . . . . . . . . . . . . . . . . . . . .
Pascal, Euclid’s Algorithm, Recursion, Analysis of Algorithms
Implementing Algorithms
MATHEMATICAL ALGORITHMS
2. Arithmetic . . . . . . . . . . . . . . . . . . . . .
Polynomials, Matrices, Data Structures
3. Random Numbers . . . . . . . . . . . . . . . . . . .
Applications, Linear Congruential Method, Additive
Congruential Method, Testing Randomness, Implementation Notes
4. Polynomials . . . . . . . . . . . . . . . . . . . . . .
Evaluation, Interpolation, Multiplication, Divide-and-conquer
Recurrences, Matriz Multiplication
5. Gaussian Elimination . . . . . . . . . . . . . . . . . .
A Simple Example, Outline of the Method, Variations and Extensions
6. Curve Fitting . . . . . . . . . . . . . . . . . . . . .
Polynomaal Interpolation, Spline Interpolation, Method of Least Squares
7. Integration . . . . . . . . . . . . . . . . . . . . . .
Symbolac Integration, Simple Quadrature Methods, Compound Methods,
Adaptive Quadrature
SORTING
8. Elementary Sorting Methods . . . . . . . . . . . . . .
Rules of the Game, Selection Sort, Insertion Sort, Shellsort,
Bubble Sort, Distribution Counting, Non-Random Files
9. Quicksort . . . . . . . . . . . . . . , , . , . . . . .
The Baszc Algorithm, Removing Recursion, Small Subfiles,
Median-of- Three Partitioning
10. Radix Sorting . . . . . . . . . . . , . . . . . . . . .
Radiz Ezchange Sort, Straight Radix Sort, A Linear Sort
11. Priority Queues . . . . . . . . . . . . . . . . . . . .
Elementary Implementations, Heap Data Structure, Algorithms
on Heaps, Heapsort, Indirect Heaps, Advanced Implementations
12. Selection and Merging . . . . . . . . . . . . . . . . .
Selection, Mergang, Recursion Revisited
13. External Sorting . . . . . . . . . . . . . . . . . . . .
Sort-Merge, Balanced Multiway Merging, Replacement Selectzon,
Practical Considerations, Polyphase Merging, An Easier Way
SEARCHING
14. Elementary Searching Methods . . . . . . . . . . . . . . . . 171
Sequential Searching, Sequential List Searchang, Binary Search,
Binary ‘Pree Search, Indirect Binary Search Trees
15. Balanced Trees . . . . . . . . . . . . . . . . . . . . . . 187
Top-Down 2-9-4 Trees, Red-Black Trees, Other Algorithms
16. Hashing . . . . . . . . . . . . . . . . . , . . . . . . . 201
Hash Functions, Separate Chaining, Open Addresszng, Analytic Results
17. Radix Searching . . . . . . . . . . . . . . . . . . . . . . 213
Digital Search Trees, Radix Search Wes, M&iway Radar Searching,
Patricia
18. External Searching . . . . . . . . ,, . . . . . . . . . . . . . 225
Indexed Sequential Access, B- nees, Extendible Hashing, Virtual Memory
STRING PROCESSING
19. String Searching . . . . . . . . . . . . . . . . . . . . . . 241
A Short History, Brute-Force Algorithm, Knuth-Morris-Pratt Algorzthm,
Bayer-Moore Algorithm, Rabin-Karp Algorithm, Multiple Searches
20. Pattern Matching . . . . . . . . . . . . . . . . . . . . . 257
Describing Patterns, Pattern Matching Machznes, Representzng
the Machine, Simulating the Machine
21. Parsing , . . . . . . . . . . . . . . . . . . . . . . . . . 269
Conteti-Free Grammars, Top-Down Parsing, Bottom-Up Parsing,
Compilers, Compiler-Compilers
22. File Compression . . . . . . . . . . . . . . . . . . . . . . 283
Run-Length Encoding, Variable-Length Encoding
23. Cryptology . . . . . . . . . . . . . . . . . . . . . . . . . 295
Rules of the Game, Simple Methods, Encrypt:!on/Decryption
Machines, Publzc-Key Cryptosystems
GEOMETRIC ALGORITHMS
24. Elementary Geometric Methods . . . . . . . . . . . . . . . . 307
Poznts, Lines, and Polygons, Line Intersection, Simple
Closed Path, Inclusaon in 4 Polygon, Perspective
25. Finding the Convex Hull . . . . . . . . . . . . . . . . . . . 321
Rules of the Game, Package Wrapping, The Graham Scan,
Hull Selection, Performance Issues
26. Range Searching . . . . . . . . . . . . . . . . . . . . . . . 335
Elementary Methods, Grad Method, 2D Trees,
Multidimensaonal Range Searching
27. Geometric Intersection . , . . . . . . . . . . . . . . . . . . 349
Horizontal and Vertical Lines, General Line Intersection
28. Closest Point Problems . . . . . . . . . . . . . . . . . . . 361
Closest Paar, Voronoi Diagrams
GRAPH ALGORITHMS
29. Elementary Graph Algorithms . . . . . . . . . . . . . . .
Glossary, Representation, Depth-First Search, Mazes, Perspectzve
30. Connectivity . . . . . . . . . . . . . . . . . . . . .
Biconnectivity, Graph Traversal Algorzthms, Union-Find Algorithms
31. Weighted Graphs . . . . . . . . . . . . . . . . . . .
Mmimum Spanning Tree, Shortest Path, Dense Graphs, Geometrzc Problems
32. Directed Graphs . . . . . . . . . . . . . . . . . . . .
Depth-Farst Search, Transitwe Closure, Topological Sorting,
Strongly Connected Components
33. Network Flow . . . . . . . . . . . . . . . . . . .
The Network Flow Problem, Ford-Adkerson Method, Network Searching
34. Matching . . . . . . . . . . . . . . . . . . , . . . . .
Bapartite Graphs, Stable Marriage Problem, Advanced Algorathms
ADVANCED TOPICS
35. Algorithm Machines . . . . . . . . . . . . . . . . . . .
General Approaches> Perfect ShujIes, Systolic Arrays
36. The Fast Fourier Transform . . . . . . . . . . . . . . .
Evaluate, Multiply, Interpolate, Complez Roots of Unity, Evaluation
at the Roots of Unity, Interpolatzon at the Roots of Unity, Implementation
37. Dynamic Programming . . . . . . . . . . . . . . . . . .
Knapsack Problem, Matriz Chain Product, Optimal Binary Search Trees,
Shortest Paths, Time and Space Requirements
38. Linear Programming . . . . . . . . . . . . . . . . . .
Lznear Programs, Geometric Interpretation, The Simplex Method,
Implementation
39. Exhaustive Search . . . . . . . . . . . . . . . . . . .
Exhaustive Search in Graphs, Backtrackzng, Permutation Generation,
Approximation Algorithms
40. NP-complete Problems . . . . . . . . . . . http://www.blogger.com/img/blank.gif . . . . .http://www.blogger.com/img/blank.gif
Deterministic and Nondeterministic Polynomial- Time Algorzthms,http://www.blogger.com/img/blank.gif
NP-Completeness, Cook’s Theorem, Some NP-Complete Problems

Another Algorithm Books
Another The Core of CS Books
Download

Algorithm Design

Table of Contents

Algorithm Design
Jon Kleinberg and Eva Tardos

Table of Contents

1 Introduction: Some Representative Problems

1.1 A First Problem: Stable Matching

1.2 Five Representative Problems
Solved Exercises
Excercises
Notes and Further Reading





2 Basics of Algorithms Analysis

2.1 Computational Tractability

2.2 Asymptotic Order of Growth Notation

2.3 Implementing the Stable Matching Algorithm using Lists and Arrays

2.4 A Survey of Common Running Times

2.5 A More Complex Data Structure: Priority Queues

Solved Exercises
Exercises
Notes and Further Reading





3 Graphs

3.1 Basic Definitions and Applications

3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal using Queues and Stacks
3.4 Testing Bipartiteness: An Application of Breadth-First Search
3.5 Connectivity in Directed Graphs
3.6 Directed Acyclic Graphs and Topological Ordering
Solved Exercises
Exercises
Notes and Further Reading





4 Greedy Algorithms
4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead
4.2 Scheduling to Minimize Lateness: An Exchange Argument
4.3 Optimal Caching: A More Complex Exchange Argument
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem
4.6 Implementing Kruskal's Algorithm: The Union-Find Data Structure
4.7 Clustering
4.8 Huffman Codes and the Problem of Data Compression
*4.9 Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm
Solved Exercises
Excercises
Notes and Further Reading




5 Divide and Conquer
5.1 A First Recurrence: The Mergesort Algorithm
5.2 Further Recurrence Relations
5.3 Counting Inversions
5.4 Finding the Closest Pair of Points
5.5 Integer Multiplication
5.6 Convolutions and The Fast Fourier Transform
Solved Exercises
Exercises
Notes and Further Reading





6 Dynamic Programming
6.1 Weighted Interval Scheduling: A Recursive Procedure
6.2 Weighted Interval Scheduling: Iterating over Sub-Problems
6.3 Segmented Least Squares: Multi-way Choices
6.4 Subset Sums and Knapsacks: Adding a Variable
6.5 RNA Secondary Structure: Dynamic Programming Over Intervals
6.6 Sequence Alignment
6.7 Sequence Alignment in Linear Space
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols
*6.10 Negative Cycles in a Graph

Solved Exercises
Exercises
Notes and Further Reading





7 Network Flow
7.1 The Maximum Flow Problem and the Ford-Fulkerson Algorithm
7.2 Maximum Flows and Minimum Cuts in a Network
7.3 Choosing Good Augmenting Paths
*7.4 The Preflow-Push Maximum Flow Algorithm
7.5 A First Application: The Bipartite Matching Problem
7.6 Disjoint Paths in Directed and Undirected Graphs
7.7 Extensions to the Maximum Flow Problem
7.8 Survey Design
7.9 Airline Scheduling
7.10 Image Segmentation
7.11 Project Selection
7.12 Baseball Elimination
*7.13 A Further Direction: Adding Costs to the Matching Problem
Solved Exercises
Exercises
Notes and Further Reading




8 NP and Computational Intractability
8.1 Polynomial-Time Reductions

8.2 Reductions via "Gadgets": The Satisfiability Problem
8.3 Efficient Certification and the Definition of NP
8.4 NP-Complete Problems
8.5 Sequencing Problems
8.6 Partitioning Problems
8.7 Graph Coloring
8.8 Numerical Problems
8.9 Co-NP and the Asymmetry of NP
8.10 A Partial Taxonomy of Hard Problems
Solved Exercises
Exercises
Notes and Further Reading





9 PSPACE: A Class of Problems Beyond NP
9.1 PSPACE
9.2 Some Hard Problems in PSPACE
9.3 Solving Quantified Problems and Games in Polynomial Space
9.4 Solving the Planning Problem in Polynomial Space
9.5 Proving Problems PSPACE-Complete
Solved Exercises
Exercises
Notes and Further Reading




10 Extending the Limits of Tractability
10.1 Finding Small Vertex Covers
10.2 Solving NP-Hard Problem on Trees
10.3 Coloring a Set of Circular Arcs
*10.4 Tree Decompositions of Graphs
*10.5 Constructing a Tree Decomposition
Solved Exercises
Exercises
Notes and Further Reading





11 Approximation Algorithms
11.1 Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem
11.2 The Center Selection Problem
11.3 Set Cover: A General Greedy Heuristic
11.4 The Pricing Method: Vertex Cover
11.5 Maximization via the Pricing method: The Disjoint Paths Problem
11.6 Linear Programming and Rounding: An Application to Vertex Cover
*11.7 Load Balancing Revisited: A More Advanced LP Application
11.8 Arbitrarily Good Approximations: the Knapsack Problem
Solved Exercises
Exercises
Notes and Further Reading


12 Local Search
12.1 The Landscape of an Optimization Problem
12.2 The Metropolis Algorithm and Simulated Annealing
12.3 An Application of Local Search to Hopfield Neural Networks
12.4 Maximum Cut Approximation via Local Search
12.5 Choosing a Neighbor Relation
*12.6 Classification via Local Search
12.7 Best-Response Dynamics and Nash Equilibria
Solved Exercises
Exercises
Notes and Further Reading





13 Randomized Algorithms
13.1 A First Application: Contention Resolution
13.2 Finding the Global Minimum Cut
13.3 Random Variables and their Expectations
13.4 A Randomized Approximation Algorithm for MAX 3-SAT
13.5 Randomized Divide-and-Conquer: Median-Finding and Quicksort
13.6 Hashing: A Randomized Implementation of Dictionaries
13.7 Finding the Closest Pair of Points: A Randomized Approach
13.8 Randomized Caching
13.9 Chernoff Bounds
13.10 Load Balancing
*13.11 Packet Routing
13.12 Background: Some Basic Probability Definitions
Solved Exercises
Exercises
Notes and Further Reading




Epilogue: Algorithms that Run Forever

References

Index


Another The Core of CS Books
Another Algorithm Books
Download