Analysis of Algorithm
- How long will my program take?
- Why does my program run out of memory?
The very same approach that scientists use to understand the natural world is effective for studying the running time of programs:
- Observe some feature of the natural world, generally with precise measurements.
- Hypothesize a model that is consistent with the observations.
- Predict events using the hypothesis.
- Verify the predictions by making further observations.
- Validate by repeating until the hypothesis and observations agree.
Essence of Math
The art of doing mathematics is finding that special case that contains all germs of generality.
Analyzing Running Time
- Develop an input model, including a definition of the problem size.
- Identify the inner loop.
- Define a cost model that includes operations in the inner loop.
- Determine the frequency of execution of those operations for the given input.
Analyzing Memory Usage
Developing an Efficient Algorithm
- Decide on a complete and specific problem statement, including identifying fundamental abstract operations that are intrinsic to the problem and an API.
- Carefully develop a succinct implementation for a straightforward algorithm, using a well-thought-out development client and realistic input data.
- Know when an implementation could not possibly be used to solve problems on the scale contemplated and must be improved or abandoned.
- Develop improved implementations through process of stepwise refinement, validating the efficacy of ideas for improvement through empirical analysis, mathematical analysis, or both.
- Find high-level abstract representations of data structures or algorithms in operation that enable effective high-level design of improved versions.
- Strive for worst-case performance guarantees when possible, but accept good performance on typical data when available.
- Know when to leave further improvements for detailed in-depth study to skilled researchers and move on to the next problem.
Important and Useful Algorithms
- Bags, Queues, and Stacks
- Implementations using resizing arrays and linked lists.
- Elementary Sorts: Selection Sort, Insertion Sort, Bubble Sort and Shellsort
- Priority Queues: One of implementations using binary heap.
- Symbol Tables: Key is original value.
- Binary Search
- Binary Search Tree
- Balanced Search Tree
- Hash Tables: Transform key with hash function.
- Undirected Graphs
- Directed Graphs
- Depth First Search
- Breadth First Search
- Minimum Spanning Trees
- Shortest Paths
- String Sorts
- Key-indexed counting
- LSD: Least-significant-digit string sorts, right-to-left order.
- MSD: Most-significant-digit string sorts, left-to-right order.
- Three-way string quicksort
- Tries：R-way tries and ternary search tries for implementing symbol tables with string keys.
- Substring Search
- Brute-force substring search
- Knuth-Morris-Pratt substring search
- Boyer-Moore substring search
- Rabin-Karp fingerprint search
- Regular Expressions
- DFA: Deterministic finite-state automation
- NFA: Nondeterministic finite-state automata
- 编译原理概述 - 前端 - 词法分析
- Data Compression
- Run-length encoding
- Huffman compression: Maintain a table of variable-length codewords for fixed-length patterns in the input.
- LZW compression: Maintain a table of fixed-length codewords for variable-length patterns in the input.
- String Sorts
- Event-driven simulation
- Suffix arrays
- Network-flow algorithms