Algorithms: Difference between revisions
Jump to navigation
Jump to search
Line 46: | Line 46: | ||
=Organizatorium= | =Organizatorium= | ||
* [[Array]] | * [[Array]] | ||
* [[Directed Acyclic Graph]] | * [[Directed Acyclic Graph]] |
Revision as of 00:45, 5 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.
- Collision resistant hash function.
- 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
- 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