Part One: Design and Analysis of Algorithms.

• Week 1
  • Bubble Sort
    • Time Complexity: O(n^2)
    • Space Complexity: O(1)
    • Could be optimized by early cutting off and ignoring already sorted part
  • Insertion Sort
    • Time Complexity: O(n^2)
    • Space Complexity: O(1)
    • Could be optimized by ignoring already sorted part
  • Selection Sort
    • Time Complexity: O(n^2)
    • Space Complexity: O(1)
  • Merge Sort
    • Time Complexity: O(nlogn)
    • Space Complexity: O(n)
  • Count Inversions
    • Time Complexity: O(nlogn)
    • Space Complexity: O(n)
    • Based on TopDown Merge Sort.
  • Karatsuba Multiplication
    • Not going to implement this one.
  • Strassen
    • Naive matrix multiplication
    • Divide-and-Conquer matrix multiplication
      • Time Complexity: O(n^3)
      • Space Complexity: O(n^2)
    • Strassen
      • Time Complexity: O(n^2.8)
      • Space Complexity: O(n^2)
  • Closest Pair 2D
  • Question 1
    • Used Count Inversions program.
• Week 2
  • Quick Sort
  • Question 1
  • Question 2
  • Question 3