Download PDF
Algorithms for integer multiplication
Algorithms for integer division, modulus and remainders
Calculating natural number square roots
Identifying primes
Factorising natural numbers
Arrays
Reversing arrays
Reductions on arrays
Sorted arrays and bubble sort
Selection sort
Insertion sort
Searching sorted and unsorted arrays
Filtering and slicing arrays
Concatenating arrays
Merging sorted arrays
Decision problems
Correctness of algorithms
Measuring algorithmic complexity with big-O notation
P (PTIME), EXPTIME, DTIME and simulation by Turing-equivalent machines in polynomial time
Hardness of problems and completeness of problems in a given complexity class
L (LSPACE), PSPACE, EXPSPACE, DSPACE
The relationships between P, L and PSPACE
Search problems and reducing them to decision problems
Optimisation problems and reducing them to decision problems
Counting problems and their complexity classes (including \#P)
Function problems and their complexity classes (including FP)
Polynomial-time reductions
Log-space reductions
Simple lossless compression
different to factorising. We don’t care what the actual factors are, just see if it’s prime
From Fermat’s little theorem we know
\(a^{n-1}=1 mod(n)\)
Where \(a\) is an integer and \(n\) is prime.