AL CS Core

AL-A: Fundamental Data Structures and Algorithms

  1. Abstract Data Types (ADTs) including Bag, Collection, Dictionary, List, and Set properties
  2. Arrays: single and multi-dimensional
    1. Linear and Binary Search
  3. Cryptography (e.g. SHA-256, RSA)
  4. Graphs [cross-reference: MF/Graphs and Trees]
    1. (un)directed, (a)cyclic, (un)connected, and (un)weighted
    2. Adjacency List and Matrix representations
  5. Graph Algorithms
    1. Breadth-First Search
      1. Connectivity, Shortest-Path
    2. Depth-First Search
      1. Acyclicity, Connectivity, Transitive Closure, Topological Sort
    3. Hamiltonian Circuit
    4. Minimal Spanning Tree
      1. Prim’s and Kruskal’s algorithms
    5. Shortest-Path
      1. Bellman-Ford,
      2. Dijkstrat’s/Uniform-Cost,
      3. Floyd-Warshall
    6. Transitive Closure: Warshall’s Algorithm
  6. Hash Tables / Maps
    1. Collision resolution: Linear/Quadratic Probing, Chaining, and Rehashing
  7. Linked Lists: single, doubly linked, and circular
  8. Objects
  9. Queues, Priority Queues, and Dequeues
  10. Records/Structs and Tuples
  11. Stacks
  12.  Strings
    1. String Matching: (Boyer-Moore)
  13. Sorting Algorithms:
    1. O(n2) Selection, Insertion
    2. O(n log n) Quicksort, Merge, and Heap
    3. O(n) Fast-Sorting: Bucket and Radix
    4. Lexicographical Ordering
    5. Partial Ordering
    6. Topological Ordering
  14. Trees
    1. Binary, N-ary, Search, Balanced, and Heaps
    2. Depth-First, Bread-First, Best-First, Backtracking search
    3. Balancing approaches (e.g., for AVL, Red-Black, 2-3, or B trees)
    4. Huffman Coding
  15. Differential Privacy
  16. Basic Linear Algebra (e.g., Strassen’s Matrix Multiplication)
  17. Invariants (in: loops, search algorithms, etc.)

AL-B: Algorithmic Strategies

  1. Algorithmic Strategy
  2. Approximation
    1. Polynomial approximation
  3. Backtracking [crosslist: Artificial Intelligence]
  4. Branch and Bound
  5. Brute-Force/Exhaustive Search
    1. Selection Sort, Traveling Salesman, Knapsack
  6. Consensus algorithms
    1. Blockchain
  7. Decrease-and-Conquer
    1. Insertion sort, Depth and Breadth-First search, Topological sort
  8. Divide-and-Conquer
    1. Binary Search, Quicksort, Mergesort, Strassen’s algorithm
  9. Dynamic Programming
    1. Warshall’s algorithm and Floyd’s algorithm
  10. Greedy
    1. Dijkstra’s Kruskal’s algorithms
  11. Heuristic: A*
  12. Iterative
    1. Linear Search
  13. Parallel [crosslist: PD/Parallel Algorithms, Analysis, and Programming]
    1. Parallel Mergesort
  14. Randomized/Stochastic Algorithms
    1. MaxCut, Balls and Bins
  15. Recursive
    1. Depth-First, Breadth-First Search, Factorial
  16. Space and Time Tradeoff
    1. Hashing
  17. Transform-and-Conquer/Reduction
    1. 2-3, AVL, Red-Black trees, Heapsort

AL-C: Complexity Analysis

  1. Algorithmic Analysis
  2. Analysis Framework
    1. Average, Best, and Worst case performance
    2. Empirical and Relative (Order of Growth) Measurements
    3. Input Size and Primitive Operations
    4. Time and Space Efficiency
  3. Asymptotic complexity analysis
    1. Big O, Little O, Big Omega, and Big Theta
    2. Foundational Complexity/Efficiency classes
      1. Constant, Logarithmic, Linear, Log Linear, Quadratic, Cubic, Exponential, and Factorial
  4. Iterative and recursive algorithm analysis
    1. Recurrence Relations
      1. Master Theorem Analysis
      2. Substitution Analysis
  5. Tractability and Intractability
    1. P, NP and NP-C complexity classes
      1. Hamiltonian Circuit, Knapsack, and SAT problems
  6. Time and space trade-off in algorithms

AL-D: Computational Models

  1. Formal Languages and Grammars
    1. Chomsky Hierarchy
    2. Regular, Context-Free, Context-Sensitive, and Recursively Enumerable
    3. Regular expressions
  2. Formal Automata
    1. Finite State, Pushdown, Linear-Bounded, and Turing Machine
    2. Deterministic versus Nondeterministic and equivalencies
    3. Relations among formal automata, languages and grammars
    4. Decidability and limitations
  3. Decidability, Computability, Halting problem
  4. The Church-Turing Thesis
  5. The P, NP, and NPC complexity

AL-E: Algorithms and Society

  1. Context-Aware Computing
  2. Social, Ethical, and Secure Algorithms
  3. Differential Privacy
  4. Algorithmic Fairness
  5. Accountability/Transparency