|
|
|
<
< |
Algorithms, Computability & Complexity
|
>
> |
ALGORITHMS AND THEORY
|
|
|
|
<
< |
Algorithms
|
>
> |
Algorithms
|
|
- Complexity analysis
- Asymptotic analysis
- Average case complexity bound
|
|
-
- Backtracking
- Branch-and-bound
- Dynamic programming
|
|
<
< |
Algorithms for different computational environments
|
>
> |
- Algorithms for different computational environments
|
|
- Distributed algorithms
- Consensus and election
- Termination detection
|
|
-
- Brent’s theorem and work efficiency
- Online and offline algorithms
- Quantum computing algorithms
|
|
<
< |
Methods with different notions of success
|
>
> |
- Methods with different notions of success
|
|
- Approximation algorithms
- Randomized algorithms
- Heuristics
|
|
<
< |
Algorithms: Important (instructional or practical) particular examples
|
>
> |
- Algorithms: Important (ISAructional or practical) particular examples
|
|
- Search
- Sequential search
- Binary search
|
|
>
> |
-
-
- Interpolation search
- Jump Search
|
|
|
|
>
> |
|
|
|
|
>
> |
-
-
- Open Hashing
- Bucket Hashing
|
|
-
- collision resolution techniques
|
|
-
-
- Hash functions
- collision-avoidance techniques
|
|
<
< |
|
|
|
|
<
< |
-
- Quadratic sorting (e.g., selection and insertion sort)
- O(n log n) sort: Quicksort
- O(n log n) sort: Heapsort
- O(n log n) sort: Merge sort
|
>
> |
-
-
- Comparison-based sorts
- Quadratic sorts (eg.selection sort,insertion sort)
- n log n sort
- Quicksort
- Heapsort
- Merge sort
|
|
|
|
<
< |
-
- Linear time sorting: Bucket sort
- Linear time sorting: Radix sort
|
>
> |
* Non-Comparison-based sorts
-
-
-
- Bucket sort
- Radix sort
* Sorting Networks
|
|
- Graph and tree algorithms
- Depth-first Binary Tree traversals (pre, in, post order)
- Breadth-first Tree traversal (level order)
- Depth-first search of graphs
- Breadth-first search of graphs
|
|
<
< |
-
- Dijkstra’s shortest path algorithm
|
>
> |
-
-
- Single-source shortest paths
|
|
|
|
<
< |
-
- Transitive closure (Floyd’s algorithm)
- Minimum spanning tree: Prim’s algorithms
- Minimum spanning tree: Kruskal’s algorithms
|
>
> |
-
-
-
- Transitive closure
- Floyd’s algorithm
- Dijkstras alogrithm
- Minimum-cost spanning tree
- Kruskal’s algorithm
- Prim's algorithm
|
|
|
|
<
< |
|
|
- Pattern matching and string/text algorithms
- Numerical (floating-point numbers) algorithms
|
|
- Combinatorial optimization
- Pseudo random number generation
- Computational Number Theory
|
|
<
< |
^^^ Consider http://www.esecurity.ch/Books/cryptography.html for expansion of this section
|
|
|
|
-
- Line segments: properties, intersections
- Convex hull finding algorithms
- Other
|
|
<
< |
- Routing and layout (of e.g., VLSI)
|
>
> |
|
|
|
|
<
< |
Advanced Data Structures
- Balanced Binary trees (e.g., Red-black)
|
>
> |
- Advanced Data Structures
- Search Trees
- Red-black trees
|
|
- Threaded Binary Trees
- Tries
|
|
<
< |
|
>
> |
|
|
- Binomial Heaps
- Union-find data structure
|
|
<
< |
-
- Disjoint-sets data structure
- Splay Trees
|
|
|
|
>
> |
-
-
- 2-3 Trees
- 2-3-4 Trees
- B+ Trees
- B* Trees
- Spatial Data Structures
- R-Trees
- Region representations
- Point representations
- Rectangle Representations
- Line representations
|
|
|
|
<
< |
Automata and formal language theory
|
>
> |
Theory
- Automata and formal language theory
|
|
- Languages, strings, alphabets
- DFAs (Deterministic Finite Automata)
- NFAs (Nondeterministic Finite Automata)
|
|
- Pumping Lemma
- Cellular automata
- Other automata theory
|
|
<
< |
Complexity Theory
|
>
> |
|
|
- Tractable vs. intractable problems
- Theory of P, NP, etc.
|
|
-
- Circuits and circuit complexity
|
|
<
< |
Computability Theory
|
>
> |
|
|
- Notion of decision problem
- Recursive (decidable) problems
- Recursively enumerable problems
|
|
- Turing machines
- Universal Turing Machine
- Nondeterministic Turing machines
|
|
<
< |
- RAM model
- Lambda calculus
- Partial recursive functions
|
|
- Other models of computable functions
- RAM model
- Lambda calculus
|