• ES Español
• EN English

2.2. Algorithmic Foundations (AL)

Algorithms and data structures are fundamental to computer science, since every theoretical computation and applied program consists of algorithms that operate on data elements possessing some underlying structure. Selecting appropriate computational solutions to real-world problems benefits from understanding the theoretical and practical capabilities and limitations of available algorithms and paradigms, including their impact on the environment and society. Moreover, this understanding provides insight into the intrinsic nature of computation, computational problems, and computational problem-solving as well as possible solution techniques independent of programming language, programming paradigm, computer hardware, or other implementation aspects.

This knowledge area focuses on the nature of computation including the concepts and skills required to design and analyze algorithms for solving real-world computational problems. It complements the implementation of algorithms and data structures found in the Software Development Foundations (SDF) knowledge area. As algorithms and data structures are essential in all advanced areas of computer science, this area provides the algorithmic foundations that every computer science graduate is expected to know. Exposure to the breadth of these foundational AL topics is designed to provide students with the basis for studying these topics in more depth, for studying additional computation and algorithm topics, and for learning advanced algorithms across a variety of CS knowledge areas and CS+X disciplines.

Knowledge Area (KA)	CS Core	KA Core
2.2.1 Foundational Data Structures	5	3
2.2.2 Foundational Algorithms	4	2
2.2.3 Advanced Algorithms	3	2
2.2.4 Algorithmic Strategies	6
2.2.5 Complexity Analysis Framework	2	1
2.2.6 Asymptotic Notation and Complexity Classes	1	1
2.2.7 Complexity Analysis: Recursion, Amortization, and Tight Bounds	2	1
2.2.8 Computational Complexity Theory	2	1
2.2.9 Formal Languages and Automata	4	10
2.2.10 Computability and Decidability	6	14
2.2.11 Society, Ethics, and the Profession	Elective

2.2.1. AL/Foundational Data Structures  (CS Core: 5 hrs, KA Core: 3 hrs) ↑ Back to top

Topics:
Core

• Abstract Data Type (ADT) and operations on an ADT:
• Dictionary operations (insert, delete, find) enumerate
• Arrays:
• Numeric vs non-numeric, character strings
• Single (vector) vs multidimensional (matrix) enumerate
• Records/Structs/Tuples and Objects
• Linked lists (for historical reasons):
• Single vs Double and Linear vs Circular enumerate
• Stacks
• Queues and deques:
• Heap-based priority queue enumerate
• Hash tables/maps:
• Collision resolution and complexity (e.g., probing, chaining, rehash) enumerate
• Trees:
• Binary, n-ary, and search trees
• Balanced (e.g., AVL, Red-Black, Heap) enumerate
• Sets

Learning Outcomes:
Core:

1. For each ADT/Data-Structure in this unit:
2. Explain its definition, properties, representation(s), and associated ADT operations.
3. Explain step-by-step how the ADT operations associated with the data structure transform it. enumerate [Explain]
4. Explain how collision avoidance and collision resolution is handled in hash tables [Explain]
5. Explain the heap property and the use of heaps as an implementation of a priority queue [Explain]

2.2.2. AL/Foundational Algorithms  (CS Core: 4 hrs, KA Core: 2 hrs) ↑ Back to top

Topics:
Core

• Graphs (e.g., [un]directed, [a]cyclic, [un]connected, and [un]weighted):
• Graph representation: adjacency list vs matrix enumerate
• Search algorithms:
• \(O(n)\) complexity (e.g., linear/sequential array/list search)
• \(O(\log_2 n)\) complexity (e.g., binary search)
• \(O(\log_b n)\) complexity (e.g., uninformed depth/breadth-first tree search) enumerate
• Sorting algorithms (e.g., stable, unstable):
• \(O(n^2)\) complexity (e.g., insertion, selection)
• \(O(n \log n)\) complexity (e.g., quicksort, merge, timsort) enumerate
• Graph algorithms:
• Shortest path (e.g., Dijkstra's, Floyd's)
• Minimal spanning tree (e.g., Prim's, Kruskal's) enumerate
• Sorting algorithms:
• \(O(n \log n)\) complexity heapsort
• Pseudo \(O(n)\) complexity (e.g., bucket, counting, radix) enumerate
• Graph algorithms:
• Transitive closure (e.g., Warshall's)
• Topological sort enumerate
• Matching:
• Efficient string matching (e.g., Boyer-Moore, Knuth-Morris-Pratt)
• Longest common subsequence matching
• Regular expression matching enumerate

Learning Outcomes:
Core:

1. For each algorithm in this unit explain step-by-step how the algorithm operates [Explain]
2. For each algorithmic approach (e.g., sorting) in this unit apply a prototypical example of the approach (e.g., merge sort) [Apply]
3. Given requirements for a problem, develop multiple solutions using various data structures and algorithms. Subsequently, evaluate the suitability, strengths, and weaknesses selecting an approach that best satisfies the requirements [Create]
4. Explain factors beyond computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data [Explain]
5. For each of the algorithms and algorithmic approaches in the KA Core topics:
6. Explain a prototypical example of the algorithm, and
7. Explain step-by-step how the algorithm operates. enumerate [Explain]

2.2.3. AL/Advanced Algorithms  (CS Core: 3 hrs, KA Core: 2 hrs) ↑ Back to top

Topics:
Non Core

• Cryptography algorithms (e.g., SHA-256)
• Parallel algorithms
• Consensus algorithms (e.g., Blockchain):
• Proof of work vs proof of stake enumerate
• Quantum computing algorithms:
• Oracle-based (e.g., Deutsch-Jozsa, Bernstein-Vazirani, Simon)
• Superpolynomial speed-up via QFT (e.g., Shor's)
• Polynomial speed-up via amplitude amplification (e.g., Grover's) enumerate
• Fast-Fourier Transform (FFT) algorithm
• Differential evolution algorithm

Learning Outcomes:
NonCore:

1. An appreciation of quantum computation and its application to certain problems [Explain]

2.2.4. AL/Algorithmic Strategies  (CS Core: 6 hrs) ↑ Back to top

Topics:
Core

• Paradigms:
• Brute-Force (e.g., linear search, selection sort, traveling salesperson, knapsack)
• Decrease-and-Conquer:
• By a Constant (e.g., insertion sort, topological sort)
• By a Constant Factor (e.g., binary search)
• By a Variable Size (e.g., Euclid's) enumerate
• Divide-and-Conquer (e.g., binary search, quicksort, mergesort, Strassen's)
• Greedy (e.g., Dijkstra's, Kruskal's, Knapsack)
• Transform-and-Conquer:
• Instance simplification (e.g., find duplicates via list presort)
• Representation change (e.g., heapsort)
• Problem reduction (e.g., least-common-multiple, linear programming)
• Dynamic programming (e.g., Floyd's, Marshall, Bellman-Ford) enumerate
• Space vs time tradeoffs (e.g., hashing) enumerate
• Handling exponential growth (e.g., heuristic A*, branch-and-bound, backtracking)
• Iteration vs recursion (e.g., factorial, tree search)
• Paradigms:
• Approximation algorithms
• Iterative improvement (e.g., Ford-Fulkerson, simplex)
• Randomized/Stochastic algorithms (e.g., max-cut, balls and bins) enumerate

Non Core

• Quantum computing

Learning Outcomes:
Core:

1. For each of the paradigms in this unit:
2. Explain its definitional characteristics
3. Explain an example that demonstrates the paradigm including how this example satisfies the paradigm's characteristics. enumerate [Explain]
4. For each of the algorithms in the Foundational Data Structures , Foundational Algorithms , Advanced Algorithms unit, explain the paradigm used by the algorithm and how it exemplifies this paradigm [Explain]
5. Given an algorithm, explain the paradigm used by the algorithm and how it exemplifies this paradigm [Explain]
6. Give a real-world problem, evaluate appropriate algorithmic paradigms and algorithms from these paradigms that address the problem including evaluating the tradeoffs among the paradigms and algorithms selected [Evaluate]
7. Give examples of iterative and recursive algorithms that solve the same problem, explain the benefits and disadvantages of each approach [Explain]
8. Evaluate whether a greedy approach leads to an optimal solution [Evaluate]
9. Explain various approaches for addressing computational problems whose algorithmic solutions are exponential [Explain]

2.2.5. AL/Complexity Analysis Framework  (CS Core: 2 hrs, KA Core: 1 hr) ↑ Back to top

Topics:
Core

• Complexity Analysis Framework:
• Best, average, and worst-case performance of an algorithm
• Empirical and relative (Order of Growth) measurements
• Input size and primitive operations
• Time and space efficiency enumerate
• Empirical measurements of performance
• Time and space tradeoffs in algorithms

Learning Outcomes:
Core:

1. Prepare a presentation that explains to first year students the basic concepts of algorithmic complexity including best, average, and worst-case algorithm behavior, Big-O, Omega, and Theta notations, complexity classes, time and space tradeoffs, empirical measurement, and impact on practical problems [Explain]
2. For each algorithm in the Foundational Data Structures , Foundational Algorithms , Advanced Algorithms unit, explain its runtime complexity class and why it belongs to this class [Explain]
3. Informally evaluate the foundational complexity class of simple algorithms [Evaluate]
4. Develop empirical studies to determine and validate hypotheses about the runtime complexity of various algorithms by running algorithms on input of various sizes and comparing actual performance to the theoretical analysis [Create]
5. Explain examples that illustrate time-space tradeoffs of algorithms [Explain]
6. Explain how tree balance affects the efficiency of binary search tree operations [Explain]

2.2.6. AL/Asymptotic Notation and Complexity Classes  (CS Core: 1 hr, KA Core: 1 hr) ↑ Back to top

Topics:
Core

• Asymptotic complexity analysis (average and worst-case bounds):
• Big-O, Big-Omega, and Big-Theta formal notations
• Foundational Complexity Classes and Representative Examples/Problems:
• \(O(1)\) Constant (e.g., array access)
• \(O(\log_2 n)\) Logarithmic (e.g., binary search)
• \(O(n)\) Linear (e.g., linear search)
• \(O(n \log_2 n)\) Log Linear (e.g., mergesort)
• \(O(n^2)\) Quadratic (e.g., selection sort)
• \(O(n^c)\) Polynomial (e.g., \(O(n^3)\) Gaussian elimination)
• \(O(2^n)\) Exponential (e.g., Knapsack, Satisfiability (SAT), Traveling Sales-Person (TSP), all subsets)
• \(O(n!)\) Factorial (e.g., Hamiltonian circuit, all permutations) enumerate enumerate

Learning Outcomes:
Core:

1. Using examples, explain each of the foundational complexity classes in this unit [Explain]
2. For each foundational complexity class in this unit, explain an algorithm that demonstrates the associated runtime complexity [Explain]
3. Explain to a non-technical audience the significance of tractable versus intractable algorithms using an intuitive explanation of Big-O complexity [Explain]
4. Apply Big-O notation to give upper case bounds on time/space complexity of algorithms [Apply]

2.2.7. AL/Complexity Analysis: Recursion, Amortization, and Tight Bounds  (CS Core: 2 hrs, KA Core: 1 hr) ↑ Back to top

Topics:
Core

• Little-o, Little-Omega, and Little Theta notations
• Formal recursive analysis
• Amortized analysis

Learning Outcomes:
Core:

1. Given a problem to program for which there may be several algorithmic approaches, evaluate them and determine which are feasible, and select one that is optimal in implementation and run-time behavior [Evaluate]
2. Use recurrence relations to evaluate the time complexity of recursively defined algorithms [Apply]
3. Apply elementary recurrence relations using a form of the Master Theorem [Apply]

2.2.8. AL/Computational Complexity Theory  (CS Core: 2 hrs, KA Core: 1 hr) ↑ Back to top

Topics:
Core

• Tractability and intractability:
• P, NP, and NP-Complete Complexity Classes
• NP-Complete Problems (e.g., SAT, Knapsack, TSP)
• Reductions enumerate
• Turing Machine-based models of complexity:
• Time complexity:
• P, NP, NP-C, and EXP classes
• Cook-Levin theorem enumerate
• Space Complexity:
• NSpace and PSpace
• Savitch's theorem enumerate enumerate

Learning Outcomes:
Core:

1. Explain the significance of NP-Completeness [Explain]
2. Explain how NP-Hard is a lower bound and NP is an upper bound for NP-Completeness [Explain]
3. Explain examples of NP-complete problems [Explain]
4. Explain the Cook-Levin Theorem and the NP-Completeness of SAT [Explain]
5. Explain the classes P and NP [Explain]
6. Prove that a problem is NP-Complete by reducing a classic known NP-C problem to it (e.g., 3SAT and Clique) [Create]
7. Explain the P-space class and its relation to the EXP class [Explain]

2.2.9. AL/Formal Languages and Automata  (CS Core: 4 hrs, KA Core: 10 hrs) ↑ Back to top

Topics:
Core

• Formal automata:
• Finite State
• Pushdown
• Linear Bounded
• Turing Machine enumerate
• Formal languages, grammars and Chomsky Hierarchy:
• Regular (Type-3):
• Regular Expressions enumerate
• Context-Free (Type-2)
• Context-Sensitive (Type-1)
• Recursively Enumerable (Type-0) enumerate
• Relations among formal automata, languages, and grammars
• Deterministic and nondeterministic automata
• Pumping Lemma proofs:
• Proof of Finite State/Regular-Language limitation
• Pushdown Automata/Context-Free-Language limitation enumerate
• Equivalent models of algorithmic computation:
• Turing Machines and Variations (e.g., multi-tape, non-deterministic)
• Lambda Calculus
• Mu-Recursive Functions enumerate

Learning Outcomes:
Core:

1. For each formal automaton in this unit:
2. Explain its definition comparing its characteristics with this unit's other automata
3. Using an example, explain step-by-step how the automaton operates on input including whether it accepts the associated input
4. Explain an example of inputs that can and cannot be accepted by the automaton. enumerate [Explain]
5. Given a problem, develop an appropriate automaton that addresses the problem [Create]
6. Develop a regular expression for a given regular language expressed in natural language [Create]
7. Explain the difference between regular expressions (Type-3 acceptors) and the regular expressions (Type-2 acceptors) used in programming languages [Explain]
8. For each formal model in this unit:
9. Explain its definition comparing its characteristics with the others in this unit
10. Explain example inputs that are and cannot be accepted by the language/grammar. enumerate [Explain]
11. For each formal automaton in this unit explain (compare/contrast) its deterministic and nondeterministic capabilities [Explain]
12. Apply pumping lemmas, or alternative means, to prove the limitations of Finite State and Pushdown automata [Apply]
13. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs [Apply]

2.2.10. AL/Computability and Decidability  (CS Core: 6 hrs, KA Core: 14 hrs) ↑ Back to top

Topics:
Core

• Decidability, (un)computability, and halting
• The Church-Turing thesis
• Algorithmic correctness:
• Invariants (e.g., in iteration, recursion, tree search) enumerate
• Decidability:
• Arithmetization and diagonalization enumerate
• Reducibility and reductions
• Time complexity based on Turing Machine
• Space complexity (e.g., Pspace, Savitch's Theorem)

Non Core

• Quantum computation:
• Postulates of quantum mechanics:
• State space
• State evolution
• State composition
• State measurement enumerate
• Column vector representations of qubits
• Matrix representations of quantum operations
• Simple quantum gates (e.g., XNOT, CNOT) enumerate

Learning Outcomes:
Core:

1. Explain a universal Turing Machine and its operation [Explain]
2. Present to an audience of co-workers and managers the impossibility of providing them a program that checks all other programs, including some seemingly simple ones, for infinite loops including an explanation of the Halting problem, why it has no algorithmic solution, and its significance for real-world algorithmic computation [Explain]
3. Explain examples of classic uncomputable problems [Explain]
4. Explain the Church-Turing Thesis and its significance for algorithmic computation [Explain]
5. Explain how (loop) invariants can be used to prove the correctness of an algorithm [Explain]
6. Apply arithmetization and diagonalization to prove the Halting Problem for Turing Machines is Undecidability [Apply]
7. Given a known undecidable language, apply a mapping reduction or computational history to prove that another language is undecidable [Apply]
8. Explain Rice's theorem and its significance [Explain]
9. Explain an example proof of a problem that is uncomputable by reducing a classic known uncomputable problem to it [Explain]
10. Explain the Primitive and General Recursive functions (zero, successor, selection, primitive recursion, composition, and Mu), their significance, and Turing Machine implementations [Explain]
11. Explain how computation is performed in Lambda Calculus (e.g., Alpha conversion and Beta reduction) [Explain]

NonCore:

1. For a quantum system give examples that explain the following postulates:
2. State Space - system state represented as a unit vector in Hilbert space
3. State Evolution - the use of unitary operators to evolve system state
4. State Composition - the use of tensor product to compose systems states
5. State Measurement - the probabilistic output of measuring a system state. enumerate [Explain]
6. Explain the operation of a quantum XNOT or CNOT gate on a quantum bit represented as a matrix and column vector, respectively [Explain]

2.2.11. AL/Society, Ethics, and the Profession ↑ Back to top

Topics:
Core

• Social, ethical, and secure algorithms
• Algorithmic fairness
• Anonymity (e.g., Differential Privacy)
• Accountability/Transparency
• Responsible algorithms
• Economic and other impacts of inefficient algorithms
• Sustainability
• Context aware computing

Learning Outcomes:
Core:

1. Develop algorithmic solutions to real-world societal problems, such as routing an ambulance to a hospital [Create]
2. Explain the impact that an algorithm may have on the environment and society when used to solve a real-world problem while considering its sustainability and that it can affect different societal groups in different ways [Explain]
3. Prepare a presentation that justifies the selection of appropriate data structures and/or algorithms to solve a given real-world problem [Explain]
4. Explain an example that articulates how differential privacy protects knowledge of an individual's data [Explain]
5. Explain the environmental impacts of design choices that relate to algorithm design [Explain]
6. Explain the tradeoffs involved in proof-of-work and proof-of-stake algorithms [Explain]