Summary
An algorithm represents a process that takes input, processes it in some procedure, and finally returns an output, which can be used in many fields, including computer science, mathematics, physics, economics, and psychology. An algorithm can also be a procedure that clearly defines the steps or method of solving a certain problem.
Algorithms are closely related to mathematics. Mathematics allows us to formalize abstract problems and transform them into concrete problems, which can then be formalized into algorithms. This would specifically be the design of search algorithms, for example, using set theory and logic in discrete mathematics.
Such a mathematical approach is used not only in the development of algorithms, but also in the evaluation of algorithms. Algorithms are evaluated in terms of correctness, efficiency, and generality: a correct algorithm should return the correct output for all inputs; an efficient algorithm should be fast, requiring less processing time and resources; a general-purpose algorithm should be able to process different inputs in the same designed to process different inputs in the same procedure. All of these evaluations have a mathematical representation.
Algorithms are particularly important in computer programming, where many programs operate by executing algorithms designed to solve a particular problem. In programming, designing an algorithm is one of the most fundamental and important steps in the design of a computer program.
This section describes various algorithms and their application methods based on the world-standard MIT textbook series “Introduction to Algorithms, 3rd Edition“.
In this issue, I will describe my reading notes.
Algorithm Introduction
The original work is a comprehensive textbook on computer algorithm theory written by four world-renowned experts in the fundamental field of computer science for teaching at MIT. The previous editions have already established themselves as world-standard textbooks on algorithms and data structures, but the book has been extensively revised once again, including the addition of new chapters and sections based on a complete review of the descriptions to improve the textbook.
The book not only explains algorithms in an easy-to-understand manner, but also explains in scientific detail what concepts are necessary and how they are backed up by analysis before the final algorithm is designed.
The book also contains 957 exercises at the end of each section and 158 problems at the end of each chapter at various levels, making it a textbook for undergraduate and graduate courses, a handbook for technical specialists, and an encyclopedia of algorithms.
This book is a complete and comprehensive translation of Chapters 1-35 and Appendices A-D of the original book. The index at the end of the book is also very impressive, and the Japanese-English-English (Japanese) structure makes the book very useful as a “dictionary of mathematical terms.
Part I. Basics
Introduction
1 Role of Algorithms in Computation
1.1 Algorithms
1.2 Algorithms as a scientific technique
2 Let’s get started
2.1 Insertion Sort
2.2 Analysis of Algorithms
2.3 Designing an Algorithm
3 Incrementing Functions
3.1 Asymptotic Notation
3.2 Standard Notation and General Functions
4 Divide-and-conquer
4.1 Maximum sub-array problem
4.2 Strassen’s algorithm for matrix products
4.3 Substitution methods for solving reduction formulas
4.4 Recurrence tree method for solving reduction formulas
4.5 Master’s method for solving reduction formulas
4.6 Proof of the master theorem
5 Probabilistic Analysis and Random Choice Algorithm
5.1 Employment Problems
5.2 Index Probability Functions
5.3 Random Choice Algorithm
5.4 Further Use of Probabilistic Analysis and Indicator Probability Variables
Part II Sorting and Ordinal Statistics
Introduction
6 Heap Sorting
6.1 Heap
6.2 Maintaining Heap Conditions
6.3 Heap construction
6.4 Heap Sort Algorithm
6.5 Prioritized Queues
7 Quick Sort
7.1 Quick Sort Description
7.2 Quick Sort Performance
7.3 Random Selection Version of Quick Sort
7.4 Analysis of Quick Sort
8 Linear Time Sort
8.1 Lower Bound for Sorting
8.2 Count Sort
8.3 Cardinality Sort
8.4 Bucket Sort
9 Median and Ordinal Statistics
9.1 Maximum and Minimum Values
9.2 Linear Expected Time Selection Algorithm
9.3 Linear Worst-Case Time Selection Algorithm
part iii data structures
Introduction
10 Basic Data Structures
10.1 Stacks and Queues
10.2 Coupled Lists
10.3 Pointers and Object Realizations
10.4 Rooted tree representation
11 Hash Tables
11.1 Direct Address Tables
11.2 Hash Tables
11.3 Hash functions
11.4 Open addressing methods
11.5 Complete Hash Method
12 Bicubic Search Tree
12.1 Bicubic Search Trees
12.2 Questions about binary search trees
12.3 Insertion and deletion
12.4 Randomly Constructed Binary Search Trees
13 2-Color Trees
13.1 Properties of 2-Color Trees
13.2 Rotation
13.3 Insertion
13.4 Deletions
14 Data Structure Augmentation
14.1 Dynamic Order Statistics
14.2 Data Structure Augmentation Methods
14.3 Interval Trees
Part IV Advanced Design and Analysis Methods
Introduction
15 Dynamic Programming Methods
15.1 Rod Cutout
15.2 Chain Matrix Product
15.3 Basic Elements of Dynamic Programming
15.4 Longest common subsequence
15.5 Optimal binary search tree
16 Greedy Algorithms
16.1 Activity Selection Problem
16.2 Basic elements of greedy strategies
16.3 Huffman codes
16.4 Matroids and Greedy Methods
16.5 Task Scheduling as a Matroid
17 Normalization Analysis
17.1 Aggregation method
17.2 The Deliverance Method
17.3 Potential method
17.4 Dynamic Tables
Part V. Advanced Data Structures
Introduction
18 B-trees
18.1 Definition of a B-tree
18.2 Basic operations on a B-tree
18.3 Deleting Keys from a B-Tree
19 The Finnabotch Heap
19.1 Structure of the Finnabotch Heap
19.2 Mergeable Heap Operations
19.3 Downward Correction of Key Values and Node Deletion
19.4 Increasing the Maximum Degree
20 van Emde Boas Trees
20.1 Preliminary Design Principles
20.2 Recursive Structure
20.3 van Emde Boas trees
21 Data structures for mutually prime set families
21.1 Operations on mutually prime set families
21.2 Representing mutually prime set families by linked lists
21.3 Forests of mutually prime set families
21.4 Analysis of mergers by ranks using path compression
Part VI Graph Algorithms
Introduction
22 Basic Graph Algorithms
22.1 Representation of graphs
22.3 Breadth-first search
22.4 Depth-First Search
22.4 Topological Sorting
22.5 Strongly Connected Components
23 Minimum Global Tree
23.1 Generating Minimum Global Tree by Growth Method
23.2 Kruski and Prim’s Algorithm
24 Single Starting Point Shortest Problem
24.1 Bellman-Ford Algorithm
24.2 Single Starting Point Shortest Paths in Directed Acyclic Graphs
24.3 Dijkstra’s algorithm
24.4 Difference Constraints and Shortest Paths
24.5 Proof of the shortest path property
25 All-point vs. shortest paths
25.1 Shortest paths and matrix products
25.2 Floyd-Warshall algorithm
25.3 Johnson’s algorithm for sparse graphs
26 Maximum Flow
26.1 Flow networks
26.3 Ford-Fukerson method
26.3 Maximum matching for bipartite graphs
26.4 Push relabeling algorithm
26.5 Re-label front running algorithm
Part VII Selected Topics
Introduction
27 Multithreading Algorithms
27.1 Fundamentals of dynamic multithreading
27.2 Multithreaded Algorithms for Matrix Operations
27.3 Multithreading for Merge Sorting
28. matrix operations
28.1 Solving linear simultaneous equations
28.2 Inverse matrix computation
28.3 Symmetric positive definite matrices and least-squares approximation
29. linear programming
29.1 Standard form and slack form
29.2 Formulating the Problem as Linear Programming
29.3 Simplex Algorithm
29.4 Duality
29.5 Initial feasible basis solutions
30.1 Polynomials and FFT
30.1 Representation of polynomials
30.2 DFT and FFT
30.3 Efficient FFT representation
31. Integer Theoretic Algorithms
31.1 Basic concepts of integer theory
31.2 Greatest common divisor
31.3 Surplus operations
31.4 Solving first-order congruences
31.5 Chinese Surplus Theorem
31.6 Beki power of an element
31.7 RSA public-key cryptosystem
31.8 Element determination
31.9 Integer prime factorization
32.1 String matching
32.1 Rustic String Query Algorithm
32.2 Rabin-Krap algorithm
32.3 String Matching Using Finite Automata
32.4 Knuth-Morris-Pratt algorithm
33. computational geometry
33.1 Line segment properties
33.2 Line intersection determination
33.3 Convex hull construction
33.4 Finding nearest neighbor pairs
34. NP-completeness
34.1 Polynomial Time
34.2 Polynomial-Time Verification
34.3 NP-completeness and reversibility
34.4 Proving NP-completeness
34.5 NP-complete problems
35. Approximation Algorithms
35.1 Trillion point covering problem
35.2 Traveling salesman problem
25.3 Set covering problem
35.4 Random selection
35.5 Partial sum problem
Appendix Mathematical Foundations
A. Sums
A.1 Formulas and properties of sums
A.2 Upper and lower bounds for sums
B Sets, etc.
B.1 Sets
B.2 Relations
B.3 Functions
B.4 Graphs
B.5 Trees
C Counting and Probability
C1 Counting
C2 Probability
C3 Discrete random variables
C4 Geometric and Binomial Distributions
C5 Hem of binomial distribution
D. Matrices
D1 Matrices and Matrix Operations
D2 Basic properties of matrices
コメント