Module Details

Relevant topics:

• Greedy Algorithms
• Divide and Conquer
• Graphs (No content)
• Dynamic Programming (No content)
• Complexity of Problems (No content)
• Reductions

Module Overview

• Analysis of Algorithms
  • Asymptotic Analysis (big O notation, $\Theta$, $\Omega$ from cs126 or similar)
  • Recursive Analysis
• Many different algorithms!
  • Algorithms for different kinds of data (graphs, numeric etc.)
  • Algorithms of different paradigms (greedy, divide and conquer, DP etc.)
• Computational complexity (and what algorithms can’t do)

The Paradigms & Problems

• Greedy algorithms Intro to Algos: making locally maximising (or minimising) choices
• Graph algorithms Graphs: shortest path, spanning trees
• Divide and Conquer: breaking a big problem into smaller problems (and solving them)
• Dynamic Programming DP: breaking a big problem into overlapping smaller problems
• Reductions
• P vs NP
• NP-completeness, mutual reducibility
• Graph algorithms 2
• Flow network