Algorithms and Complexity (AL)
Algorithms are fundamental to computer science and software engineering. The real-world performance of any software system depends on: (1) the algorithms chosen and (2) the suitability and efficiency of the various layers of implementation. Good algorithm design is therefore crucial for the performance of all software systems. Moreover, the study of algorithms provides insight into the intrinsic nature of the problem as well as possible solution techniques independent of programming language, programming paradigm, computer hardware, or any other implementation aspect.
An important part of computing is the ability to select algorithms appropriate to particular purposes and to apply them, recognizing the possibility that no suitable algorithm may exist. This facility relies on understanding the range of algorithms that address an important set of well-defined problems, recognizing their strengths and weaknesses, and their suitability in particular contexts. Efficiency is a pervasive theme throughout this area.
This knowledge area defines the central concepts and skills required to design, implement, and analyze algorithms for solving problems. Algorithms are essential in all advanced areas of computer science: artificial intelligence, databases, distributed computing, graphics, networking, operating systems, programming languages, security, and so on. Algorithms that have specific utility in each of these are listed in the relevant knowledge areas. Cryptography, for example, appears in the new knowledge area on Information Assurance and Security, while parallel and distributed algorithms appear in PD-Parallel and Distributed Computing.
As with all knowledge areas, the order of topics and their groupings do not necessarily correlate to a specific order of presentation. Different programs will teach the topics in different courses and should do so in the order they believe is most appropriate for their students.
AL. Algorithms and Complexity (19 Core-Tier1 hours, 9 Core-Tier2 hours)
| Core-Tier1 hours | Core-Tier2 hours | Includes Electives | |
| AL/Basic Analysis | 2 | 2 | N |
| AL/Algorithmic Strategies | 5 | 1 | N |
| AL/Fundamental Data Structures and Algorithms | 9 | 3 | N |
| AL/Basic Automata, Computability and Complexity | 3 | 3 | N |
| AL/Advanced Computational Complexity | Y | ||
| AL/Advanced Automata Theory and Computability | Y | ||
| AL/Advanced Data Structures, Algorithms, and Analysis | Y |
AL/Basic Analysis
[2 Core-Tier1 hours, 2 Core-Tier2 hours]
Topics:
[Core-Tier1]
- Differences among best, expected, and worst case behaviors of an algorithm
- Asymptotic analysis of upper and expected complexity bounds
- Big O notation: formal definition
- Complexity classes, such as constant, logarithmic, linear, quadratic, and exponential
- Empirical measurements of performance
- Time and space trade-offs in algorithms
[Core-Tier2]
- Big O notation: use
- Little o, big omega and big theta notation
- Recurrence relations
- Analysis of iterative and recursive algorithms
- Some version of a Master Theorem
Learning Outcomes:
[Core-Tier1]
- Explain what is meant by “best”, “expected”, and “worst” case behavior of an algorithm. [Familiarity]
- In the context of specific algorithms, identify the characteristics of data and/or other conditions or assumptions that lead to different behaviors. [Assessment]
- Determine informally the time and space complexity of simple algorithms. [Usage]
- State the formal definition of big O. [Familiarity]
- List and contrast standard complexity classes. [Familiarity]
- Perform empirical studies to validate hypotheses about runtime stemming from mathematical analysis. Run algorithms on input of various sizes and compare performance. [Assessment]
- Give examples that illustrate time-space trade-offs of algorithms. [Familiarity]
[Core-Tier2]
- Use big O notation formally to give asymptotic upper bounds on time and space complexity of algorithms. [Usage]
- Use big O notation formally to give expected case bounds on time complexity of algorithms. [Usage]
- Explain the use of big omega, big theta, and little o notation to describe the amount of work done by an algorithm. [Familiarity]
- Use recurrence relations to determine the time complexity of recursively defined algorithms. [Usage]
- Solve elementary recurrence relations, e.g., using some form of a Master Theorem. [Usage]
AL/Algorithmic Strategies
[5 Core-Tier1 hours, 1 Core-Tier2 hours]
An instructor might choose to cover these algorithmic strategies in the context of the algorithms presented in “Fundamental Data Structures and Algorithms” below. While the total number of hours for the two knowledge units (18) could be divided differently between them, our sense is that the 1:2 ratio is reasonable.
Topics:
[Core-Tier1]
- Brute-force algorithms
- Greedy algorithms
- Divide-and-conquer (cross-reference SDF/Algorithms and Design/Problem-solving strategies)
- Recursive backtracking
- Dynamic Programming
[Core-Tier2]
- Branch-and-bound
- Heuristics
- Reduction: transform-and-conquer
Learning Outcomes:
[Core-Tier1]
- For each of the strategies (brute-force, greedy, divide-and-conquer, recursive backtracking, and dynamic programming), identify a practical example to which it would apply. [Familiarity]
- Use a greedy approach to solve an appropriate problem and determine if the greedy rule chosen leads to an optimal solution. [Assessment]
- Use a divide-and-conquer algorithm to solve an appropriate problem. [Usage]
- Use recursive backtracking to solve a problem such as navigating a maze. [Usage]
- Use dynamic programming to solve an appropriate problem. [Usage]
- Determine an appropriate algorithmic approach to a problem. [Assessment]
[Core-Tier2]
- Describe various heuristic problem-solving methods. [Familiarity]
- Use a heuristic approach to solve an appropriate problem. [Usage]
- Describe the trade-offs between brute force and heuristic strategies. [Assessment]
- Describe how a branch-and-bound approach may be used to improve the performance of a heuristic method. [Familiarity]
AL/Fundamental Data Structures and Algorithms
[9 Core-Tier1 hours, 3 Core-Tier2 hours]
This knowledge unit builds directly on the foundation provided by Software Development Fundamentals (SDF), particularly the material in SDF/Fundamental Data Structures and SDF/Algorithms and Design.
Topics:
[Core-Tier1]
- Simple numerical algorithms, such as computing the average of a list of numbers, finding the min, max, and mode in a list, approximating the square root of a number, or finding the greatest common divisor
- Sequential and binary search algorithms
- Worst case quadratic sorting algorithms (selection, insertion)
- Worst or average case O(N log N) sorting algorithms (quicksort, heapsort, mergesort)
- Hash tables, including strategies for avoiding and resolving collisions
- Binary search trees
- Common operations on binary search trees such as select min, max, insert, delete, iterate over tree
- Graphs and graph algorithms
- Representations of graphs (e.g., adjacency list, adjacency matrix)
- Depth- and breadth-first traversals
[Core-Tier2]
- Heaps
- Graphs and graph algorithms
- Shortest-path algorithms (Dijkstra’s and Floyd’s algorithms)
- Minimum spanning tree (Prim’s and Kruskal’s algorithms)
- Pattern matching and string/text algorithms (e.g., substring matching, regular expression matching, longest common subsequence algorithms)
Learning Outcomes:
[Core-Tier1]
- Implement basic numerical algorithms. [Usage]
- Implement simple search algorithms and explain the differences in their time complexities. [Assessment]
- Be able to implement common quadratic and O(N log N) sorting algorithms. [Usage]
- Describe the implementation of hash tables, including collision avoidance and resolution. [Familiarity]
- Discuss the runtime and memory efficiency of principal algorithms for sorting, searching, and hashing. [Familiarity]
- Discuss factors other than computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data. [Familiarity]
- Explain how tree balance affects the efficiency of various binary search tree operations. [Familiarity]
- Solve problems using fundamental graph algorithms, including depth-first and breadth-first search. [Usage]
- Demonstrate the ability to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in a particular context. [Assessment]
[Core-Tier2]
- Describe the heap property and the use of heaps as an implementation of priority queues. [Familiarity]
- Solve problems using graph algorithms, including single-source and all-pairs shortest paths, and at least one minimum spanning tree algorithm. [Usage]
- Trace and/or implement a string-matching algorithm. [Usage]
AL/Basic Automata Computability and Complexity
[3 Core-Tier1 hours, 3 Core-Tier2 hours]
Topics:
[Core-Tier1]
- Finite-state machines
- Regular expressions
- The halting problem
[Core-Tier2]
- Context-free grammars (cross-reference PL/Syntax Analysis)
- Introduction to the P and NP classes and the P vs NP problem
- Introduction to the NP-complete class and exemplary NP-complete problems (e.g., SAT, Knapsack)
Learning Outcomes:
[Core-Tier1]
- Discuss the concept of finite state machines. [Familiarity]
- Design a deterministic finite state machine to accept a specified language. [Usage]
- Generate a regular expression to represent a specified language. [Usage]
- Explain why the halting problem has no algorithmic solution. [Familiarity]
[Core-Tier2]
- Design a context-free grammar to represent a specified language. [Usage]
- Define the classes P and NP. [Familiarity]
- Explain the significance of NP-completeness. [Familiarity]
AL/Advanced Computational Complexity
[Elective]
Topics:
- Review of the classes P and NP; introduce P-space and EXP
- Polynomial hierarchy
- NP-completeness (Cook’s theorem)
- Classic NP-complete problems
- Reduction Techniques
Learning Outcomes:
- Define the classes P and NP. (Also appears in AL/Basic Automata, Computability, and Complexity). [Familiarity]
- Define the P-space class and its relation to the EXP class. [Familiarity]
- Explain the significance of NP-completeness. (Also appears in AL/Basic Automata, Computability, and Complexity). [Familiarity]
- Provide examples of classic NP-complete problems. [Familiarity]
- Prove that a problem is NP-complete by reducing a classic known NP-complete problem to it. [Usage]
AL/Advanced Automata Theory and Computability
[Elective]
Topics:
- Sets and languages
- Regular languages
- Review of deterministic finite automata (DFAs)
- Nondeterministic finite automata (NFAs)
- Equivalence of DFAs and NFAs
- Review of regular expressions; their equivalence to finite automata
- Closure properties
- Proving languages non-regular, via the pumping lemma or alternative means
- Context-free languages
- Push-down automata (PDAs)
- Relationship of PDAs and context-free grammars
- Properties of context-free languages
- Turing machines, or an equivalent formal model of universal computation
- Nondeterministic Turing machines
- Chomsky hierarchy
- The Church-Turing thesis
- Computability
- Rice’s Theorem
- Examples of uncomputable functions
- Implications of uncomputability
Learning Outcomes:
- Determine a language’s place in the Chomsky hierarchy (regular, context-free, recursively enumerable). [Assessment]
- Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs. [Usage]
- Explain the Church-Turing thesis and its significance. [Familiarity]
- Explain Rice’s Theorem and its significance. [Familiarity]
- Provide examples of uncomputable functions. [Familiarity]
- Prove that a problem is uncomputable by reducing a classic known uncomputable problem to it. [Usage]
AL/Advanced Data Structures Algorithms and Analysis
[Elective]
Many programs will want their students to have exposure to more advanced algorithms or methods of analysis. Below is a selection of possible advanced topics that are current and timely but by no means exhaustive.
Topics:
- Balanced trees (e.g., AVL trees, red-black trees, splay trees, treaps)
- Graphs (e.g., topological sort, finding strongly connected components, matching)
- Advanced data structures (e.g., B-trees, Fibonacci heaps)
- String-based data structures and algorithms (e.g., suffix arrays, suffix trees, tries)
- Network flows (e.g., max flow. [Ford-Fulkerson algorithm], max flow – min cut, maximum bipartite matching)
- Linear Programming (e.g., duality, simplex method, interior point algorithms)
- Number-theoretic algorithms (e.g., modular arithmetic, primality testing, integer factorization)
- Geometric algorithms (e.g., points, line segments, polygons. [properties, intersections], finding convex hull, spatial decomposition, collision detection, geometric search/proximity)
- Randomized algorithms
- Stochastic algorithms
- Approximation algorithms
- Amortized analysis
- Probabilistic analysis
- Online algorithms and competitive analysis
Learning Outcomes:
- Understand the mapping of real-world problems to algorithmic solutions (e.g., as graph problems, linear programs, etc.). [Assessment]
- Select and apply advanced algorithmic techniques (e.g., randomization, approximation) to solve real problems. [Assessment]
- Select and apply advanced analysis techniques (e.g., amortized, probabilistic, etc.) to algorithms. [Assessment]