<<O>>  Difference Topic AlgorithmsComplexity (r1.10 - 27 Sep 2007 - Main.nova)
META TOPICPARENT OntologyProject

Algorithms, Computability & Complexity

Changed:
<
<		 Basic algorithmic analysis
>
>

Algorithms

  • Complexity analysis

  • Asymptotic analysis
    • Average case complexity bound
    • Asymptotic analysis: worst case complexity bounds
Line: 18 to 21
  • Recurrrence relations
  • Amortized analysis
  • Other advanced algorithmic analysis
Changed:
<
<

Algorithmic Design strategies

>
>
  • Algorithmic Design strategies

  • Brute-force algorithms
  • Greedy algorithms
  • Divide-and-conquer
Line: 91 to 92
  • Combinatorial optimization
  • Pseudo random number generation
  • Computational Number Theory
Added:
>
>

^^^ Consider http://www.esecurity.ch/Books/cryptography.html for expansion of this section


  • Cryptographic algorithms
Changed:
<
<
    • Private-key cryptography
    • Public-key cryptography
>
>
    • Unkeyed cryptography
      • Parabolic encryption
    • Symmetric cryptography
      • Secret-key encryption
    • Asymmetric cryptography
      • Public-key encryption
    • Steganography

  • Geometric algorithms
    • Line segments: properties, intersections
    • Convex hull finding algorithms
 <<O>>  Difference Topic AlgorithmsComplexity (r1.9 - 26 Apr 2007 - Main.nova)
META TOPICPARENT OntologyProject

Algorithms, Computability & Complexity

Deleted:
<
<


Basic algorithmic analysis
Changed:
<
<
  • Asymptotic analysis: average case complexity bounds
>
>
  • Asymptotic analysis
    • Average case complexity bound

  • Asymptotic analysis: worst case complexity bounds
  • Identifying differences among best, average, and worst case behaviors
  • Big O
Line: 20 to 15
  • Empirical measurements of performance
    • Profiling programs
  • Time and space tradeoffs in algorithms
Changed:
<
<
  • Using recurrence relations to model recursive algorithms
  • Solving recurrrence relations
>
>
  • Recurrrence relations
  • Amortized analysis
  • Other advanced algorithmic analysis

Algorithmic Design strategies
  • Brute-force algorithms
  • Greedy algorithms
Line: 74 to 70
    • Shell sort
    • Linear time sorting: Bucket sort
    • Linear time sorting: Radix sort
Deleted:
<
<
    • Distinction between comparison-based and other sorting

  • Graph and tree algorithms
    • Depth-first Binary Tree traversals (pre, in, post order)
    • Breadth-first Tree traversal (level order)
Line: 87 to 82
    • Minimum spanning tree: Kruskal’s algorithms
    • Topological sort
Deleted:
<
<		 Other algorithms

  • Pattern matching and string/text algorithms
  • Numerical (floating-point numbers) algorithms
    • Matrix algorithms
Line: 128 to 122
  • Context-free grammars
  • Push-down automata
  • Equivalence of CFGs and PDAs
Changed:
<
<
  • Pumping Lemma for Regular Languages
  • Pumping Lemma for Context-Free Languages
>
>
  • Pumping Lemma

  • Cellular automata
Changed:
<
<
  • Advanced automata theory
>
>
  • Other automata theory

Complexity Theory

  • Tractable vs. intractable problems
Line: 166 to 159
  • Turing machines
    • Universal Turing Machine
    • Nondeterministic Turing machines
Changed:
<
<
  • Other models of computable functions (e.g., RAM model, lambda Calculus, partial recursive functions)
>
>
  • RAM model
  • Lambda calculus
  • Partial recursive functions
  • Other models of computable functions
    • RAM model
    • Lambda calculus
    • Partial recursive functions

  • Advanced computability theory
  • Chomsky hierarchy
  • The Church-Turing thesis
Deleted:
<
<		 Advanced algorithmic analysis
  • Amortized analysis
  • Other advanced algorithmic analysis
 <<O>>  Difference Topic AlgorithmsComplexity (r1.8 - 06 Mar 2007 - Main.nova)
META TOPICPARENT OntologyProject

Algorithms, Computability & Complexity

Added:
>
>


Basic algorithmic analysis
  • Asymptotic analysis: average case complexity bounds
  • Asymptotic analysis: worst case complexity bounds
Line: 47 to 52
  • Search
    • Sequential search
    • Binary search
Added:
>
>
    • Hash-based retrieval

    • Hashing
      • Hash tables
Added:
>
>
    • collision resolution techniques
      • chaining
      • probing
      • clustering

      • Hash functions
Changed:
<
<
      • Hashing collision resolution: chaining
      • Hashing collission resolution: probing
      • Hash tables, including collision-avoidance strategies
>
>
      • collision-avoidance techniques


  • Sorting
    • Quadratic sorting (e.g., selection and insertion sort)
    • O(n log n) sort: Quicksort
Line: 101 to 114
  • Fibbonacci Heaps
  • Binomial Heaps
  • Union-find data structure
Added:
>
>
    • Disjoint-sets data structure

  • Splay Trees
  • B-Trees
  • Other

Automata and formal language theory

Changed:
<
<
  • Sets, languages, strings, alphabets
>
>
  • Languages, strings, alphabets

  • DFAs (Deterministic Finite Automata)
  • NFAs (Nondeterministic Finite Automata)
  • Regular expressions
 <<O>>  Difference Topic AlgorithmsComplexity (r1.7 - 02 Jun 2006 - Main.nova)
META TOPICPARENT OntologyProject

Algorithms, Computability & Complexity

Deleted:
<
<		 Comparison of algorithm complexities

Basic algorithmic analysis

  • Asymptotic analysis: average case complexity bounds
Line: 17 to 15
  • Empirical measurements of performance
  • Profiling programs
  • Time and space tradeoffs in algorithms
Changed:
<
<
  • How recurrence relations model recursive algorithms
>
>
  • Using recurrence relations to model recursive algorithms

  • Solving recurrrence relations
Algorithmic Design strategies
  • Brute-force algorithms
Line: 27 to 25
  • Branch-and-bound
  • Dynamic programming
Algorithms for different computational environments
Changed:
<
<
  • Distributed algorithms (AL4)
>
>
  • Distributed algorithms

    • Consensus and election
    • Termination detection
    • Fault tolerance
Line: 38 to 36
    • Pointer jumping
    • Brent’s theorem and work efficiency
    • Online and offline algorithms
Added:
>
>
  • Quantum computing algorithms

Methods with different notions of success

  • Approximation algorithms
  • Randomized algorithms
  • Heuristics
Changed:
<
<

Algorithms: Famous instructional examples

>
>		 Algorithms: Important (instructional or practical) particular examples
  • Search

  • Sequential search
  • Binary search
Changed:
<
<
  • Sorting Problem
>
>
    • Hashing
      • Hash tables
      • Hash functions
      • Hashing collision resolution: chaining
      • Hashing collission resolution: probing
      • Hash tables, including collision-avoidance strategies
  • Sorting

  • Quadratic sorting (e.g., selection and insertion sort)
  • O(n log n) sort: Quicksort
  • O(n log n) sort: Heapsort
Line: 57 to 62
  • Linear time sorting: Bucket sort
  • Linear time sorting: Radix sort
  • Distinction between comparison-based and other sorting
Changed:
<
<
  • Notion of hashing
  • Hash tables
  • Hash functions
  • Hashing collision resolution: chaining
  • Hashing collission resolution: probing
  • Hash tables, including collision-avoidance strategies
>
>
  • Graph and tree algorithms

  • Depth-first Binary Tree traversals (pre, in, post order)
  • Breadth-first Tree traversal (level order)
  • Depth-first search of graphs
Line: 74 to 74
  • Minimum spanning tree: Kruskal’s algorithms
  • Topological sort
Changed:
<
<		 Algorithms: Problem Spaces
>
>		 Other algorithms

  • Pattern matching and string/text algorithms
Changed:
<
<
  • Numerical (floating-point numbers) algorithms [Could have separate BIG numerical analysis top-level area]
>
>
  • Numerical (floating-point numbers) algorithms

    • Matrix algorithms
    • Transforms (e.g., FFT)
  • Medians and order statistics
  • Network Flow
  • Combinatorial optimization
Added:
>
>
  • Pseudo random number generation

  • Computational Number Theory
  • Cryptographic algorithms
Changed:
<
<
    • Historical overview of cryptography
    • Private-key cryptography and the key-exchange problem
>
>
    • Private-key cryptography

    • Public-key cryptography
Deleted:
<
<
    • Digital signatures
    • Security protocols
    • Applications (e.g., zero-knowledge proofs, authentication)

  • Geometric algorithms
    • Line segments: properties, intersections
    • Convex hull finding algorithms
    • Other
Changed:
<
<
  • Routing and layout
>
>
  • Routing and layout (of e.g., VLSI)

  • Scheduling
Added:
>
>

Advanced Data Structures
  • Balanced Binary trees (e.g., Red-black)
  • Threaded Binary Trees
Line: 100 to 98
  • Balanced Binary trees (e.g., Red-black)
  • Threaded Binary Trees
  • Tries
Changed:
<
<
  • Fibbornacci Heaps
>
>
  • Fibbonacci Heaps

  • Binomial Heaps
  • Union-find data structure
  • Splay Trees
Line: 120 to 118
  • Pumping Lemma for Context-Free Languages
  • Cellular automata
  • Advanced automata theory
Added:
>
>

Complexity Theory
  • Tractable vs. intractable problems
Added:
>
>
  • Theory of P, NP, etc.

  • Complexity Class P
  • Complexity Class NP
Added:
>
>
    • NP Completeness
    • The P =? NP problem
    • Famous NP-complete problems (e.g., 3SAT, Traveling Salesperson, Vertex Cover, Integer Programming)

  • Other complexity classes
  • Reductions
    • Poly-time reductions
    • Log space reductions
  • Complete problems for a complexity class
Deleted:
<
<
  • NP Completeness
  • The P =? NP problem
  • Famous NP-complete problems (e.g., 3SAT, Traveling Salesperson, Vertex Cover, Integer Programming)

  • Other time-based complexity classses
  • Space complexity classes
  • Relations among complexity classes
Changed:
<
<
  • Complexity classes based on mode of computing (e.g., alternating, randomized)
>
>
  • Complexity classes based on mode of computing

    • Alternating
    • Randomized
    • Online
Line: 153 to 152
  • Turing machines
    • Universal Turing Machine
  • Nondeterministic Turing machines
Changed:
<
<
  • Other models of computable functions (e.g., RAM model, lambda Calculas, partial recursive functions)
>
>
  • Other models of computable functions (e.g., RAM model, lambda Calculus, partial recursive functions)

  • Advanced computability theory
  • Chomsky hierarchy
  • The Church-Turing thesis
 <<O>>  Difference Topic AlgorithmsComplexity (r1.6 - 11 Feb 2006 - Main.nova)
META TOPICPARENT OntologyProject

Algorithms, Computability & Complexity

Deleted:
<
<		 Add Real History of Computing
  • Alan Turing lives here
  • Euclid's GCD history lives here


Comparison of algorithm complexities
Line: 18 to 12
  • Big O
  • Big Omega
  • Big Theta
Changed:
<
<
  • Little o assymptotic notation
>
>
  • Little o asymptotic notation

  • Little omega asymptotic notation
Deleted:
<
<

  • Empirical measurements of performance
  • Profiling programs
  • Time and space tradeoffs in algorithms
Line: 33 to 26
  • Backtracking
  • Branch-and-bound
  • Dynamic programming
Changed:
<
<		 Algorithms for different computational envioronments
>
>		 Algorithms for different computational environments

  • Distributed algorithms (AL4)
    • Consensus and election
    • Termination detection
Line: 86 to 76

Algorithms: Problem Spaces

  • Pattern matching and string/text algorithms
Changed:
<
<
  • Numerical (floating-point numbers) algorithms (Could have separate BIG numerical analysis top-level area)
>
>
  • Numerical (floating-point numbers) algorithms [Could have separate BIG numerical analysis top-level area]

*Matrix algorithms *Transforms (e.g., FFT)
  • Medians and order statistics
 <<O>>  Difference Topic AlgorithmsComplexity (r1.5 - 11 Nov 2005 - Main.nova)
META TOPICPARENT OntologyProject
Changed:
<
<		 AL. Algorithms, Computability & Complexity
>
>

Algorithms, Computability & Complexity


Add Real History of Computing

  • Alan Turing lives here
 <<O>>  Difference Topic AlgorithmsComplexity (r1.4 - 22 Jul 2005 - Main.nova)
META TOPICPARENT OntologyProject
AL. Algorithms, Computability & Complexity
Line: 7 to 7
  • Euclid's GCD history lives here
Deleted:
<
<		 Contrast complexities of different algorithmic strategies

Added:
>
>		 Comparison of algorithm complexities

Changed:
<
<		 Basic algorithmic analysis (4)
>
>

Basic algorithmic analysis


  • Asymptotic analysis: average case complexity bounds
  • Asymptotic analysis: worst case complexity bounds
  • Identifying differences among best, average, and worst case behaviors
Line: 25 to 26
  • Time and space tradeoffs in algorithms
  • How recurrence relations model recursive algorithms
  • Solving recurrrence relations
Changed:
<
<		 Algorithmic Design strategies (6)
>
>		 Algorithmic Design strategies

  • Brute-force algorithms
  • Greedy algorithms
  • Divide-and-conquer
Line: 38 to 39
    • Termination detection
    • Fault tolerance
    • Stabilization
Changed:
<
<
  • Algorithms for parallel architectures (AL 11)
>
>
  • Algorithms for parallel architectures

    • PRAM model
    • Exclusive versus concurrent reads and writes
    • Pointer jumping
 <<O>>  Difference Topic AlgorithmsComplexity (r1.3 - 15 Jun 2005 - Main.nova)
META TOPICPARENT OntologyProject
AL. Algorithms, Computability & Complexity
 <<O>>  Difference Topic AlgorithmsComplexity (r1.2 - 14 Jun 2005 - Main.nova)
META TOPICPARENT OntologyProject
Changed:
<
<		 AL. Algorithms and Complexity
>
>		 AL. Algorithms, Computability & Complexity

Add Real History of Computing
Added:
>
>		 *Alan Turing lives here *Euclid's GCD history lives here

Changed:
<
<
  • Contrast complexities of different algorithmic strategies
>
>		 Contrast complexities of different algorithmic strategies

Basic algorithmic analysis (4)

Line: 67 to 70
  • Hash tables, including collision-avoidance strategies
Changed:
<
<
  • Depth-first Binary Tree traversl (pre, in, post order)
>
>
  • 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
Line: 81 to 84

Algorithms: Problem Spaces

  • Pattern matching and string/text algorithms
Changed:
<
<
  • Numerical (floating-point numbers) algorithms
>
>
  • Numerical (floating-point numbers) algorithms (Could have separate BIG numerical analysis top-level area) *Matrix algorithms *Transforms (e.g., FFT)

  • Medians and order statistics
  • Network Flow
  • Combinatorial optimization
Line: 97 to 102
    • Line segments: properties, intersections
    • Convex hull finding algorithms
    • Other
Changed:
<
<
>
>		 *Routing and layout *Scheduling

Advanced Data Structures
  • Balanced Binary trees (e.g., Red-black)
  • Threaded Binary Trees
Line: 109 to 115
  • B-Trees
  • Other
Changed:
<
<		 Automata and formal languate theory
>
>		 Automata and formal language theory

  • Sets, languages, strings, alphabets
  • DFAs (Deterministic Finite Automata)
  • NFAs (Nondeterministic Finite Automata)
Line: 120 to 126
  • Equivalence of CFGs and PDAs
  • Pumping Lemma for Regular Languages
  • Pumping Lemma for Context-Free Languages
Added:
>
>		 *Cellular automata

  • Advanced automata theory
Complexity Theory
  • Tractable vs. intractable problems
  • Complexity Class P
  • Complexity Class NP
Changed:
<
<
  • Poly-time and/or log space reductions
>
>		 *Other complexity classes *Reductions *Poly-time reductions *Log space reductions *Complete problems for a complexity class

  • NP Completeness
  • The P =? NP problem
  • Famous NP-complete problems (e.g., 3SAT, Traveling Salesperson, Vertex Cover, Integer Programming)
Line: 133 to 144
  • Space complexity classes
  • Relations among complexity classes
  • Complexity classes based on mode of computing (e.g., alternating, randomized)
Added:
>
>		 *Alternating *Randomized *Online *Parallel *Interactive

*Circuits and circuit complexity


Computability Theory
  • Notion of decision problem
  • Recursive (decidable) problems
 <<O>>  Difference Topic AlgorithmsComplexity (r1.1 - 27 May 2005 - Main.nova)
Line: 1 to 1
Added:
>
>
META TOPICPARENT OntologyProject
AL. Algorithms and Complexity Add Real History of Computing

  • Contrast complexities of different algorithmic strategies

Basic algorithmic analysis (4)

  • Asymptotic analysis: average case complexity bounds
  • Asymptotic analysis: worst case complexity bounds
  • Identifying differences among best, average, and worst case behaviors
  • Big O
  • Big Omega
  • Big Theta
  • Little o assymptotic notation
  • Little omega asymptotic notation

  • Empirical measurements of performance
  • Profiling programs
  • Time and space tradeoffs in algorithms
  • How recurrence relations model recursive algorithms
  • Solving recurrrence relations
Algorithmic Design strategies (6)
  • Brute-force algorithms
  • Greedy algorithms
  • Divide-and-conquer
  • Backtracking
  • Branch-and-bound
  • Dynamic programming
Algorithms for different computational envioronments
  • Distributed algorithms (AL4)
    • Consensus and election
    • Termination detection
    • Fault tolerance
    • Stabilization
  • Algorithms for parallel architectures (AL 11)
    • PRAM model
    • Exclusive versus concurrent reads and writes
    • Pointer jumping
    • Brent’s theorem and work efficiency
    • Online and offline algorithms

Methods with different notions of success

  • Approximation algorithms
  • Randomized algorithms
  • Heuristics

Algorithms: Famous instructional examples

  • Sequential search
  • Binary search
  • Sorting Problem
  • 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
  • Shell sort
  • Linear time sorting: Bucket sort
  • Linear time sorting: Radix sort
  • Distinction between comparison-based and other sorting
  • Notion of hashing
  • Hash tables
  • Hash functions
  • Hashing collision resolution: chaining
  • Hashing collission resolution: probing
  • Hash tables, including collision-avoidance strategies

  • Depth-first Binary Tree traversl (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
  • All-pairs shortest paths
  • Transitive closure (Floyd’s algorithm)
  • Minimum spanning tree: Prim’s algorithms
  • Minimum spanning tree: Kruskal’s algorithms
  • Topological sort

Algorithms: Problem Spaces

  • Pattern matching and string/text algorithms
  • Numerical (floating-point numbers) algorithms
  • Medians and order statistics
  • Network Flow
  • Combinatorial optimization
  • Computational Number Theory
  • Cryptographic algorithms
    • Historical overview of cryptography
    • Private-key cryptography and the key-exchange problem
    • Public-key cryptography
    • Digital signatures
    • Security protocols
    • Applications (e.g., zero-knowledge proofs, authentication)
  • Geometric algorithms
    • Line segments: properties, intersections
    • Convex hull finding algorithms
    • Other

Advanced Data Structures

  • Balanced Binary trees (e.g., Red-black)
  • Threaded Binary Trees
  • Tries
  • Fibbornacci Heaps
  • Binomial Heaps
  • Union-find data structure
  • Splay Trees
  • B-Trees
  • Other

Automata and formal languate theory

  • Sets, languages, strings, alphabets
  • DFAs (Deterministic Finite Automata)
  • NFAs (Nondeterministic Finite Automata)
  • Regular expressions
  • Equivalence of DFA, NFA, and Regular Expressions
  • Context-free grammars
  • Push-down automata
  • Equivalence of CFGs and PDAs
  • Pumping Lemma for Regular Languages
  • Pumping Lemma for Context-Free Languages
  • Advanced automata theory
Complexity Theory
  • Tractable vs. intractable problems
  • Complexity Class P
  • Complexity Class NP
  • Poly-time and/or log space reductions
  • NP Completeness
  • The P =? NP problem
  • Famous NP-complete problems (e.g., 3SAT, Traveling Salesperson, Vertex Cover, Integer Programming)
  • Other time-based complexity classses
  • Space complexity classes
  • Relations among complexity classes
  • Complexity classes based on mode of computing (e.g., alternating, randomized)
Computability Theory
  • Notion of decision problem
  • Recursive (decidable) problems
  • Recursively enumerable problems
  • Undecidable problems
  • Halting problem
  • Turing machines * Universal Turing Machine
  • Nondeterministic Turing machines
  • Other models of computable functions (e.g., RAM model, lambda Calculas, partial recursive functions)
  • Advanced computability theory
  • Chomsky hierarchy
  • The Church-Turing thesis
Advanced algorithmic analysis
  • Amortized analysis
  • Other advanced algorithmic analysis
View topic | Diffs | r1.10 | > | r1.9 | > | r1.8 | More
Revision r1.1 - 27 May 2005 - 17:21 - Main.nova
Revision r1.10 - 27 Sep 2007 - 15:28 - Main.nova