Objective:
1. This document is aim to research about the algorithm engineering development lifecycle.
Research Findings:
1. Algorithm Engineering focuses on the design, analysis, implementation, optimization, profiling and experimental evaluation of computer algorithms, bridging the gap between algorithm theory and practical applications of algorithms in software engineering.
2. constant factors of algorithms have such a considerable impact on real-world inputs that sometimes an algorithm with worse asymptotic behavior performs better in practice due to lower constant factors.
3. Implementations of algorithms used for experiments differ in significant ways from code usable in applications. While the former prioritizes fast prototyping, performance and instrumentation for measurements during experiments, the latter requires thorough testing, maintainability, simplicity, and tuning for particular classes of inputs.
4. Empirical algorithmics (sometimes also called experimental algorithmics) is the area within computer science that uses empirical methods to study the behaviour of algorithms. It can be used in the analysis of algorithms.
5. Algorithm design is a specific method to create a mathematical process in solving problems.
6. Techniques for designing and implementing algorithm designs are algorithm design patterns,[1] such as template method pattern and decorator pattern, and uses of data structures, and name and sort lists.
7. Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.
8. Proof by exhaustion, also known as proof by cases, perfect induction, or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases and each type of case is checked to see if the proposition in question holds
9. In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.
10. Brute force search should not be confused with backtracking, where large sets of solutions can be discarded without being explicitly enumerated
11. the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity)
12. Informally, an algorithm can be said to exhibit a growth rate on the order of a mathematical function if beyond a certain input size n, the function f(n) times a positive constant provides an upper bound or limit for the run-time of that algorithm.
14. Algorithm analysis is important in practice because the accidental or unintentional use of an inefficient algorithm can significantly impact system performance. In time-sensitive applications, an algorithm taking too long to run can render its results outdated or useless. An inefficient algorithm can also end up requiring an uneconomical amount of computing power or storage in order to run, again rendering it practically useless.
15.
Steps in development of Algorithms
1. Problem definition
2. Development of a model
3. Specification of Algorithm
4. Designing an Algorithm
5. Checking the correctness of Algorithm
6. Analysis of Algorithm
7. Implementation of Algorithm
8. Program testing
9. Documentation Preparation
Common Algorithm Paradigms:
- Simple recursive algorithms
- Backtracking algorithms
- Divide and conquer algorithms
- Dynamic programming algorithms
- Greedy algorithms
- Branch and bound algorithms
- Brute force algorithms
- Randomized algorithms
Topics:
Algorithm Engineering
Algorithm Theory
Experimental Algorithmic
Algorithm Cycle:
Design
Analysis
Implementation
Experimental Evaluation
Joined by further aspects like Machine Models or Realistic Inputs
Institutes:
Library of Efficient Data types and Algorithms
Algorithms Marketplace
Top Algorithms in 20th Century:
1946: The Metropolis Algorithm for Monte Carlo. Through the use of random processes, this algorithm offers an efficient way to stumble toward answers to problems that are too complicated to solve exactly.
1947: Simplex Method for Linear Programming. An elegant solution to a common problem in planning and decision-making.
1950: Krylov Subspace Iteration Method. A technique for rapidly solving the linear equations that abound in scientific computation.
1951: The Decompositional Approach to Matrix Computations. A suite of techniques for numerical linear algebra.
1957: The Fortran Optimizing Compiler. Turns high-level code into efficient computer-readable code.
1959: QR Algorithm for Computing Eigenvalues. Another crucial matrix operation made swift and practical.
1962: Quicksort Algorithms for Sorting. For the efficient handling of large databases.
1965: Fast Fourier Transform. Perhaps the most ubiquitous algorithm in use today, it breaks down waveforms (like sound) into periodic components.
1977: Integer Relation Detection. A fast method for spotting simple equations satisfied by collections of seemingly unrelated numbers.
1987: Fast Multipole Method. A breakthrough in dealing with the complexity of n-body calculations, applied in problems ranging from celestial mechanics to protein folding.
Feelings:
1. It is like solving math problems.
2. Problems have easy, middle, and hard problems.
3. It is very important to understand the problem; or is the problem describer has described the problem clearly. Many times, they are not. So we have to use questions to find out what exactly the problem the describer has.
4. The only way to achieve this, is by solving more problems, and increase my experience. Just like Machine learning, we have to train ourselves with enough training examples, so we can improve algorithm experience.
5. Algorithm Experience matters.
6. There are many tricks in Algorithm.
7. Also focus on worst case balancing.
8. This is the key source for FLAG Company.
9. Focus on practicing more questions with answers, accumulate tricks and common designs, and then solve the issue myself. There is no single good answer for all the problems.
10. Algorithm is to increate smartness of computer.
11. Algorithm shall go from easy to middle to hard, just like Experience.
12. Algorithm is about solving problems.
14. Shall also try to research about how other people solve this problem with what algorithms first, and then customize it.
15. Leverage other people's algorithms.
References:
https://en.wikipedia.org/wiki/Algorithm_engineering
http://www.algorithmic-solutions.com/leda/index.htm
https://algorithmia.com/tags/machine%20learning
https://en.wikipedia.org/wiki/Empirical_algorithmics
https://en.wikipedia.org/wiki/Algorithm_design
https://en.wikipedia.org/wiki/Proof_by_exhaustion
https://en.wikipedia.org/wiki/Brute-force_search
https://en.wikipedia.org/wiki/Analysis_of_algorithms
https://www.quora.com/What-are-the-top-10-algorithms-of-the-20th-century
