Algorithms: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
Line 20: | Line 20: | ||
* Map | * Map | ||
* Hash Map | * Hash Map | ||
* Distributed Hash Map | * Distributed Hash Map. Insist on this as is key to systems that scale. | ||
* Trees | * Trees | ||
** Binary Trees. Binary tree height. | ** Binary Trees. Binary tree height. |
Revision as of 20:11, 4 August 2018
External
Internal
Overview
- Arrays.
- Lists (single linked and double linked)
- Stack
- Queue. Difference between list and queue.
- Sorting
- Comparison Sort. Comparison sort algorithm class. Know that comparison sort cannot do better than n ln n. Proof in a separate article.
- Non-comparison Sort
- Sorting algorithms characteristics (in-place, stability)
- Algorithm complexity, Bounds. Understand and document O, Omega and Theta notations. Perform complexity analysis on all the algorithms I examine. Expected running time, worst-case running time. Average case running time.
- Iteration and recursion – fundamentally different approaches.
- Set
- Map
- Hash Map
- Distributed Hash Map. Insist on this as is key to systems that scale.
- Trees
- Binary Trees. Binary tree height.
- Sorting trees. Difference between a binary search tree and a red-black tree.
- BTrees
- Binary Trees. Binary tree height.
- Tree walking algorithms. Difference between depth first and breadth first.
- Graphs
- Graph algorithms
- Dynamic programming and memoization.
- Greedy algorithms.
- Matrix multiplication (NOKB and code).
- lg and ln notation. Link from the Mathematics main page.
- Random variable analysis. Indicator random variable.
Probability Distribution.
- Consider starting upside down, with the bottom (math) sections, and NOKB concepts from them first.
- Mathematics: Understand and document induction.
- Need to understand aggregate analysis Section 17.1
Organizatorium
- A data structure is an arrangement of data in computer's memory or external storage. Data structures include arrays, linked lists, stacks, binary trees, hash tables, etc. Algorithms manipulate the data in these structures in various ways.
- Array
- Directed Acyclic Graph
- Associative Array
- Map
- Tree
- Consistent Hashing
- https://en.wikipedia.org/wiki/Big_O_notation
- https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo
- http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html