Algorithms: Difference between revisions
Jump to navigation
Jump to search
Line 14: | Line 14: | ||
** Comparison Sort | ** Comparison Sort | ||
** Non-comparison Sort | ** Non-comparison Sort | ||
** Sorting algorithms characteristics (in- | ** 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. | * 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. | ||
* Set | * Set | ||
* Map | * Map | ||
Line 28: | Line 28: | ||
* Graph algorithms | * Graph algorithms | ||
* Matrix multiplication (NOKB and code). | * Matrix multiplication (NOKB and code). | ||
* lg and ln notation. Link from the [[Mathematics]] main page. | * lg and ln notation. Link from the [[Mathematics]] main page. | ||
• | • | ||
• Binary tree height. | • Binary tree height. | ||
• Stable sort. | • Stable sort. |
Revision as of 01:52, 4 August 2018
External
Internal
Overview
- Arrays.
- Lists (single linked and double linked)
- Stack
- Queue
- Sorting
- Comparison Sort
- 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.
- Set
- Map
- Hash Map
- Distributed Hash Map
- Trees
- Binary Trees
- Sorting trees.
- BTrees
- Binary Trees
- Tree walking algorithms. Difference between depth first and breadth first.
- Graphs
- Graph algorithms
- Matrix multiplication (NOKB and code).
- lg and ln notation. Link from the Mathematics main page.
• • Binary tree height. • Stable sort. • Comparison sort algorithm class. Know that comparison sort cannot do better than n ln n. Proof in a separate article. • Random variable analysis. Indicator random variable. • Consider starting upside down, with the bottom sections, and NOKB concepts from them first. • Difference between a binary search tree and a red-black tree. • Difference between list and queue. • Iteration and recursion – fundamentally different approaches. • Probability Distribution. • 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