Advanced Algorithms
Advanced algorithm work has changed in two ways that reach this course: implementations are now routinely drafted by AI coding agents, so empirical verification of machine-produced code and its asserted complexity bounds becomes an assessed skill rather than an assumed one, and AI infrastructure has become one significant consumer of advanced algorithms, alongside scheduling, networks, and large-scale data processing, through vector and nearest neighbor search, sketching and streaming, and heuristic search. The course therefore keeps its design, analysis, and intractability core and adds those developments as application context and as a verification discipline rather than as its organizing frame.
Current description → proposed description
This is an advanced course in current trends in Problem Solving and Algorithms that builds on our undergraduate courses data structure (CSC 4400) and CS Theory (CSC 4200). This course will look at emerging algorithms across the grand ideas of computer science. As new technologies emerge, new algorithms must be explored to support them.
This is an advanced course in current trends in problem solving and algorithms that builds on undergraduate data structures and theoretical computer science. The course examines emerging algorithms across the grand ideas of computer science on the premise that as new technologies emerge, new algorithms must be explored to support them. Students analyze advanced data structures together with randomized, amortized, and approximation methods, and they study computational intractability, reductions between problems, and the graph and dynamic-programming techniques that yield tractable solutions to hard problems. Design and analysis of search and optimization algorithms, including branch and bound, A* with admissible heuristics, beam search, evolutionary and other metaheuristic methods, and Monte Carlo tree search, occupy a central place. These methods are exercised across application domains including scheduling and logistics, network and graph workloads, large-scale data processing through sketching and streaming, and the approximate nearest neighbor and vector indexing structures that serve AI retrieval systems, where recall, latency, memory, and cost must be traded against one another. Because implementations are now routinely drafted by AI coding agents, the course treats specification, adversarial and worst-case testing, profiling, and the verification of machine-asserted complexity claims as core professional skills, and it examines the accountability an engineer retains for approximation and prioritization rules that distribute benefit and burden unevenly among the people a system serves.
What changes
- Computational intractability and reductions made explicit
- Search and optimization algorithm families named and analyzed
- Sketching, streaming, and vector indexing added as application context
- Verification of agent-generated implementations and complexity claims
- Accountability for approximation and prioritization choices in deployment
6 proposed outcomes, mapped to 5 program outcomes
Each outcome below is written to be observable and assessable, and each is mapped to the program learning outcomes for which it produces evidence.
Students will be able to analyze the correctness and asymptotic cost of advanced algorithms and data structures, including randomized, amortized, and approximation methods and the search and optimization algorithms designed in the course, justifying the bound obtained for a chosen design under explicitly stated assumptions.
PLO 3.1: the outcome names search algorithms among the foundational theory to be applied, and this CLO requires proving completeness, optimality, or a cost bound for the search and optimization algorithms the course designs, which is a distinct analytical performance from the construction CLO 2 assesses.
Students will be able to design search and optimization algorithms, including branch and bound, A* with admissible heuristics, beam search, evolutionary and other metaheuristic methods, and Monte Carlo tree search, implementing and tuning them for planning problems operating under a fixed computational budget.
PLO 3.1: the outcome explicitly names search algorithms and evolutionary computation, and this CLO requires students to build and tune exactly those families, including evolutionary metaheuristics and Monte Carlo tree search, rather than merely describe them.
Students will be able to evaluate approximate nearest neighbor, sketching, and streaming algorithms serving an embedding-based retrieval component of an AI system, measuring recall, latency, memory, and cost against exact baselines and refining index and sketch parameters from the resulting diagnostic evidence.
PLO 6.2: the artifact evaluated is a retrieval component of an AI system, recall and error against an exact baseline are the appropriate evaluation metrics for it, and the required parameter refinement from diagnostic results is the iterative refinement the outcome describes.
Students will be able to critique implementations and complexity claims produced by AI coding agents, constructing adversarial and worst-case inputs, profiling observed running time and memory against the asserted bound, documenting which claims were confirmed and which were not, and revising or re-specifying the implementation where a claim fails.
PLO 6.2: profiling an agent's output against its asserted bound is a direct assessment of an AI model's performance and limitations using appropriate metrics, and the required revision or re-specification where a claim fails is the iterative refinement from diagnostic results the outcome names.
Students will be able to justify the approximation, tie-breaking, and prioritization rules embedded in a deployed algorithm, assessing how those choices distribute benefit and burden among the people the system serves and stating the accountability the engineer retains for machine-generated components.
PLO 1.1 and PLO 3.2: the workbook states this same outcome twice, once under Christian Faith and once under Integrated Disciplinary Knowledge, and the CLO earns it in both places because assessing how ranking, scheduling, and cutoff rules distribute benefit and burden is the fairness and potential-harm analysis it names, while stating the engineer's retained responsibility for machine-generated components is its accountability requirement.
Students will be able to communicate an algorithm selection decision for an AI system component, with its complexity, cost, risk, and fairness tradeoffs, to both technical reviewers and non-technical stakeholders, grounding the recommendation in measured evidence rather than asserted performance.
PLO 5.1: the CLO requires an AI system component's results and its fairness tradeoffs to be made intelligible both to technical reviewers and to non-technical stakeholders, which is the outcome's communication of AI concepts, results, and ethical considerations to both audiences with clarity and responsibility.
Program outcomes this course reaches
Filled cells are program learning outcomes with at least one supporting course learning outcome in this course. Sparse coverage is expected — no single course carries all twelve.