Notes - DAA HT23, All the algorithms

Created: January 26, 2023

A list of all the algorithms that have come up in the course.

  • Insertion sort
  • Merge sort
  • A divide-and-conquer algorithm for finding the largest and smallest among $n$ integers using at most $3n/2$ comparisons (problem sheet 1, question 7)
  • A “ternary” search algorithm which splits the list into three rather than two (problem sheet 1, question 8).
  • Finding the midpoint of the union of two arrays in $O(\log n)$ time (problem sheet 1, question 9).
  • $O(n \log n)$ algorithm for finding $i, j$ in an array such that $A[i] + A[j]$ equals some number (problem sheet 1, question 11).
  • Counting the number of inversions in an array in $O(n \log n)$ time.
  • Strassen’s algorithm for matrix muliplication
  • The fast fourier transform for polynomial multiplication
  • Counting sort
  • Removing an arbitrary element from a heap
  • Heapsort
  • Knapsack problem
  • Edit distance


Related posts