Skip to main content
CBE Nexus · Undergraduate Computer Science

Chapter 15: Advanced Algorithms and Computational Theory

Advanced computer science notes on greedy algorithms, dynamic programming, graph algorithms, complexity classes, reductions, computability, automata, formal languages and computational limits.

Back to Computer Science course guide

Chapter overview and learning outcomes

This chapter develops the theory and practical foundations of advanced algorithms and computational theory, linking core concepts to the design, evaluation and responsible operation of computing systems.

1. Algorithm analysis and asymptotic notation

Algorithm analysis estimates resource use as input size grows. Time complexity counts operations under a defined model; space complexity considers memory requirements. Big-O gives an asymptotic upper bound, Big-Omega a lower bound and Big-Theta a tight bound. Best, average and worst cases answer different questions. Constants and hardware matter in practice, but asymptotic analysis helps compare scalability. State assumptions about input representation and the operation being counted.

Applied study: Work through a realistic scenario from the domain. Identify the assumptions, constraints, relevant stakeholders and expected outcome. Explain the reasoning behind a proposed method, compare it with at least one alternative, and discuss reliability, security, performance, ethical implications and limitations.

Learning activity: Prepare a labelled model or worked example, define how you would test it, and write a short reflection on what evidence would change your conclusion.

2. Divide-and-conquer algorithms

Divide-and-conquer breaks a problem into smaller subproblems, solves them recursively and combines their results. Binary search repeatedly halves a sorted search interval. Merge sort divides an array, sorts each half and merges them, achieving O(n log n) time in standard implementations. Recurrence relations model recursive costs and can be solved using expansion, recursion trees or the Master Theorem where its conditions apply. Recursion depth and auxiliary memory must also be considered.

Applied study: Work through a realistic scenario from the domain. Identify the assumptions, constraints, relevant stakeholders and expected outcome. Explain the reasoning behind a proposed method, compare it with at least one alternative, and discuss reliability, security, performance, ethical implications and limitations.

Learning activity: Prepare a labelled model or worked example, define how you would test it, and write a short reflection on what evidence would change your conclusion.

3. Greedy algorithms and proof of correctness

A greedy algorithm makes a locally optimal choice at each step. Greedy strategies are efficient for problems with suitable structure, but local choices are not always globally optimal. Correctness may be established using an exchange argument, cut property or stays-ahead proof. Examples include minimum spanning tree algorithms and Huffman coding. Before using a greedy method, identify the choice rule, prove that an optimal solution can contain that choice, and establish that the remaining problem has the same structure.

Applied study: Work through a realistic scenario from the domain. Identify the assumptions, constraints, relevant stakeholders and expected outcome. Explain the reasoning behind a proposed method, compare it with at least one alternative, and discuss reliability, security, performance, ethical implications and limitations.

Learning activity: Prepare a labelled model or worked example, define how you would test it, and write a short reflection on what evidence would change your conclusion.

4. Dynamic programming and optimal substructure

Dynamic programming solves problems with overlapping subproblems and optimal substructure. It stores solutions to smaller states using memoisation (top-down) or tabulation (bottom-up). A design requires defining the state, recurrence, base cases, evaluation order and reconstruction method. Examples include Fibonacci computation, weighted interval scheduling, knapsack and edit distance. Complexity depends on the number of states and transitions, not merely on the recursive description.

Applied study: Work through a realistic scenario from the domain. Identify the assumptions, constraints, relevant stakeholders and expected outcome. Explain the reasoning behind a proposed method, compare it with at least one alternative, and discuss reliability, security, performance, ethical implications and limitations.

Learning activity: Prepare a labelled model or worked example, define how you would test it, and write a short reflection on what evidence would change your conclusion.

5. Graph representations and traversal

A graph consists of vertices and edges, which may be directed, undirected, weighted or labelled. Adjacency lists are space-efficient for sparse graphs; adjacency matrices support constant-time edge checks at higher space cost. Breadth-first search finds shortest paths in unweighted graphs; depth-first search supports cycle detection, connected components and topological reasoning. Graph algorithms should specify how they handle disconnected vertices, repeated edges and invalid input.

Applied study: Work through a realistic scenario from the domain. Identify the assumptions, constraints, relevant stakeholders and expected outcome. Explain the reasoning behind a proposed method, compare it with at least one alternative, and discuss reliability, security, performance, ethical implications and limitations.

Learning activity: Prepare a labelled model or worked example, define how you would test it, and write a short reflection on what evidence would change your conclusion.

6. Shortest paths, spanning trees and network optimisation

Dijkstra's algorithm finds shortest paths from a source when edge weights are non-negative. Bellman-Ford supports negative edge weights and can detect reachable negative cycles. Floyd-Warshall computes all-pairs shortest paths through dynamic programming. Minimum spanning tree algorithms such as Kruskal and Prim connect all vertices at minimum total edge weight in a connected weighted undirected graph. Select an algorithm based on graph size, density, weights and required output.

Applied study: Work through a realistic scenario from the domain. Identify the assumptions, constraints, relevant stakeholders and expected outcome. Explain the reasoning behind a proposed method, compare it with at least one alternative, and discuss reliability, security, performance, ethical implications and limitations.

Learning activity: Prepare a labelled model or worked example, define how you would test it, and write a short reflection on what evidence would change your conclusion.

7. Complexity classes P, NP and NP-completeness

P contains decision problems solvable in polynomial time by a deterministic algorithm. NP contains decision problems whose proposed solutions can be verified in polynomial time. NP-hard problems are at least as hard as every problem in NP under the chosen reduction; NP-complete problems are both in NP and NP-hard. Whether P equals NP remains unresolved. Practical algorithms often use approximation, heuristics, parameterised methods or restricted problem instances.

Applied study: Work through a realistic scenario from the domain. Identify the assumptions, constraints, relevant stakeholders and expected outcome. Explain the reasoning behind a proposed method, compare it with at least one alternative, and discuss reliability, security, performance, ethical implications and limitations.

Learning activity: Prepare a labelled model or worked example, define how you would test it, and write a short reflection on what evidence would change your conclusion.

8. Reductions, approximation and intractability

A polynomial-time reduction transforms instances of one problem into another while preserving the answer in a defined way. Reductions establish relative difficulty and are central to NP-completeness proofs. For optimisation problems, approximation algorithms provide solutions with a provable bound on quality relative to optimum. Heuristics may work well empirically without a formal guarantee. Distinguish proof of worst-case difficulty from evidence about typical workloads and practical solvability.

Applied study: Work through a realistic scenario from the domain. Identify the assumptions, constraints, relevant stakeholders and expected outcome. Explain the reasoning behind a proposed method, compare it with at least one alternative, and discuss reliability, security, performance, ethical implications and limitations.

Learning activity: Prepare a labelled model or worked example, define how you would test it, and write a short reflection on what evidence would change your conclusion.

9. Automata and regular languages

Finite automata recognise regular languages. A deterministic finite automaton has one transition for each state and input symbol; a nondeterministic automaton may have multiple possible transitions and can be converted to an equivalent deterministic form. Regular expressions describe regular languages, and finite automata can implement lexical analysis and pattern recognition. Pumping lemmas can prove that certain languages are not regular, but cannot by themselves prove regularity.

Applied study: Work through a realistic scenario from the domain. Identify the assumptions, constraints, relevant stakeholders and expected outcome. Explain the reasoning behind a proposed method, compare it with at least one alternative, and discuss reliability, security, performance, ethical implications and limitations.

Learning activity: Prepare a labelled model or worked example, define how you would test it, and write a short reflection on what evidence would change your conclusion.

10. Context-free grammars, pushdown automata and parsing

A context-free grammar consists of terminals, nonterminals, production rules and a start symbol. It describes hierarchical structures such as balanced parentheses and many programming-language constructs. Pushdown automata extend finite-state machines with a stack. Parsing determines whether an input conforms to a grammar and may construct a syntax tree. Ambiguous grammars allow multiple parse trees for a string; language design and parser construction require explicit precedence and associativity rules.

Applied study: Work through a realistic scenario from the domain. Identify the assumptions, constraints, relevant stakeholders and expected outcome. Explain the reasoning behind a proposed method, compare it with at least one alternative, and discuss reliability, security, performance, ethical implications and limitations.

Learning activity: Prepare a labelled model or worked example, define how you would test it, and write a short reflection on what evidence would change your conclusion.

11. Turing machines, computability and limits

A Turing machine is an abstract model of computation with a finite control, tape and read-write head. Computability theory distinguishes problems for which an algorithm exists from undecidable problems. The halting problem demonstrates that no general algorithm can correctly decide for every program and input whether execution eventually halts. Complexity theory studies resource bounds for computable problems. These theories clarify fundamental limits, not merely limitations of current hardware.

Applied study: Work through a realistic scenario from the domain. Identify the assumptions, constraints, relevant stakeholders and expected outcome. Explain the reasoning behind a proposed method, compare it with at least one alternative, and discuss reliability, security, performance, ethical implications and limitations.

Learning activity: Prepare a labelled model or worked example, define how you would test it, and write a short reflection on what evidence would change your conclusion.

Figure 1. Algorithm design strategy
Define input and output→Choose data structure→Select algorithmic paradigm→Prove correctness→Analyse time and space

Conceptual diagram for learning and revision.

Figure 2. Dynamic programming structure
Define state and recurrence→Set base cases→Compute subproblem solutions→Reconstruct final answer

Conceptual diagram for learning and revision.

Figure 3. Formal language hierarchy
Regular languages: finite automata→Context-free: pushdown automata→Turing-recognisable languages: Turing machines

Conceptual diagram for learning and revision.

Practical laboratory or project activity

  1. Choose a bounded problem relevant to this chapter and state its purpose.
  2. Identify inputs, outputs, constraints, assumptions and potential failure cases.
  3. Develop a small model, prototype, experiment or worked analysis.
  4. Use appropriate tools and authorised datasets or test environments.
  5. Test normal, boundary and failure conditions; record reproducible observations.
  6. Write a report explaining method, evidence, limitations and recommendations.

Follow institutional rules, protect private information and obtain permission before testing systems or collecting data.

Worked reasoning and self-assessment

Start by translating the question into a precise problem statement. Define variables and assumptions before calculating or implementing. Work through a small example manually, then verify it with an appropriate tool. Explain why the selected approach is suitable, identify an alternative, and discuss its trade-offs. For empirical claims, describe the data and method needed to support them; for system claims, specify observable tests and expected outcomes.

Examination and revision questions

Answer using precise definitions, diagrams, calculations and examples where appropriate.

  1. What does Big-O describe?

    Show answer guidance

    An asymptotic upper bound on growth of resource use.

  2. What is divide-and-conquer?

    Show answer guidance

    Breaking a problem into smaller subproblems, solving them and combining their results.

  3. What is a greedy algorithm?

    Show answer guidance

    An algorithm that repeatedly makes a locally preferred choice.

  4. When is dynamic programming useful?

    Show answer guidance

    When subproblems overlap and the problem has optimal substructure.

  5. What does breadth-first search find in an unweighted graph?

    Show answer guidance

    A shortest path in number of edges from the source to reachable vertices.

  6. What is a minimum spanning tree?

    Show answer guidance

    A minimum-total-weight set of edges connecting all vertices of a connected weighted undirected graph.

  7. What is the class P?

    Show answer guidance

    Decision problems solvable in polynomial time by a deterministic algorithm.

  8. What is the class NP?

    Show answer guidance

    Decision problems whose proposed solutions can be verified in polynomial time.

  9. What is an NP-complete problem?

    Show answer guidance

    A problem in NP to which every problem in NP can be polynomial-time reduced.

  10. What is a polynomial-time reduction?

    Show answer guidance

    A transformation computable in polynomial time that preserves the relevant yes/no answer.

  11. What is a finite automaton?

    Show answer guidance

    A finite-state machine that recognises regular languages.

  12. What is a context-free grammar?

    Show answer guidance

    A grammar whose production rules replace a single nonterminal with a string of terminals and nonterminals.

  13. What is a Turing machine?

    Show answer guidance

    An abstract computational model with finite control, a tape and a read-write head.

  14. State the halting problem.

    Show answer guidance

    There is no general algorithm that decides for every program and input whether it eventually halts.

  15. Why use approximation algorithms?

    Show answer guidance

    They provide tractable solutions with a known bound on quality for difficult optimisation problems.

Revision checklist

Further study and academic references

Consult current university textbooks, peer-reviewed conference and journal papers, official standards and authoritative technical documentation. Verify versions and publication details before citing sources. Use the citation style required by your institution, cite data and software as well as written sources, and distinguish published evidence from your own analysis. Do not invent references, measurements or experimental outcomes.

Academic and responsible-use note: These notes support undergraduate study and do not replace your institution's course outline, laboratory rules or supervisor guidance. Respect privacy, intellectual property, licences, research ethics and applicable law.

Return to the full Computer Science course guide

Official Education References

Use these official organisations for curriculum guidance, examinations and further learning information.