ALG 1B 011218

[animatedsilicon]

0:01:38 Fibonacci numbers recap.
0:03:20 You are expected to be able to prove a theorem by induction, and identify the growth of a function.
0:08:40 You can avoid the characteristic equation of the Fibonacci sequence with linear algebra.
0:17:30 Computing the Fibonacci number with the new approach reframes the nth term as the nth power of the matrix, allowing us to use repeated squaring fast exponentiation.
0:22:20 How long will the product of two matrices take?
0:27:50 Finding the product more efficiently, fewer multiplications.
0:35:00 Generalising the method for larger matrices.
0:46:20 What if the size of matrix can't be halved? As mathematicians, we don't need to care about the implementation details. The answer is that it can be done, but you have to find the specific implementation on your own.
0:49:25 What is the run time of this? How long is it going to take?
0:59:40 The answer. Core idea—analysing growth gives us an objective way of comparing algorithms, by seeing how the time it takes to compute scales with the size of input.
1:03:35 Growth analysis of merge sort.
1:13:45 Order notation.

[mitalighotgalkar]

Amazing explanation. Your videos are awesome. Thank you for sharing this.