Berkeley CS170 Spring 2022

Week 1

01/18/2022

1. Analysis of Fibonacci

   function fib(n)
       if n = 0 then
           return 0
       if n = 1 then
           return 1
       return fib(n-1) + fib(n-2)

   The runtime is exponential. Actually you can calculate the formula: $f(n)=\frac{1}{\sqrt{(}5)}[(\frac{\sqrt{(}5)+1}{2}{)}^n-(\frac{\sqrt{(}5)-1}{2}{)}^n]$

   function fib(n)
       create an array of size n called fibArray
       fibArray[0] = 0
       fibArray[1] = 1
       for i = 2 to n
           fibArray[i] = fibArray[i-1] + fibArray[i-2]
       return fibArray[n]

   The runtime is linear

2. Analysis of arithmetic

   • Addition: x, y are n bit integers, adding them together is an $O(n)$ operation
   • Subtraction: x, y are n bit integers, subtracting them together is an $O(n)$ operation
   • Multiplication: x, y are n bit integers, multiplying them together is an $O(n^2)$ operation
   • The russian peasant algorithm
     • Halve on the first column, double on the second column, repeat this until the item in the first column is 0
     • Remove all rows that have an even item in the first column
     • Add up the remaining items in the second column This algorithm is a a $O(n^2)$ operation

01/20/2022

1. Analysis of multiplication using divide and conquer

   • Problem: x, and y are n bit integers, calculate the multiplication of them using divide and conquer

   • Divide x and y into two halves: $x_L$, $x_R$, $y_L$, $y_R$, where the four terms all have length of n/2, and $x=x_L\ast 2^{n/2}+x_R$, $y=y_L\ast 2^{n/2}+y_R$.Then we have $x\ast y=2^n{x}_L\ast y_L+2^{n/2}\ast (x_L\ast y_R+x_R\ast y_L)+x_R\ast y_R$

     MULT(x, y)
         a1, a2 <- a
         b1, b2 <- b
         p1 <- MULT(a1, b1)    
         p2 <- MULT(a1, b2)    
         p3 <- MULT(a2, b1)    
         p4 <- MULT(a2, b2)
         return 2^n * p1 + 2^{n/2} * (p2 + p3) + p4    

   • This algorithm is a $O(n^2)$ operation, since $T(n)=4\ast T(n/2)+c\ast n$

   • Rule of thumb: sum of an increasing geometric series is $O(lastterm)$

     MULT(x, y)
         a1, a2 <- a
         b1, b2 <- b
         p1 <- MULT(a1, b1)    
         p2 <- MULT(a2, b2)
         p3 <- MULT(a1 + a2, b1 + b2)    
         return 2^n * p1 + 2^{n/2} * (p3 - p1 - p2) + p2    

   • This algorithm is a $O(n^{lo{g}_{2}3})=O(n^{1.6})$ operation, since $T(n)=3\ast T(n/2)+c\ast n$

2. Analysis of matrix multiplication using divide and conquer
   • Problem: given two n * n matrices A, and B, calculate A * B
   • The naive algorithm: $O(n^3)$ since multiplication of two vectors is $O(n)$
   • Use divide and conquer
     • Divide the n * n matrix into four n/2 * n/2 matrices
     • The recurrence relationship is : $T(n)=8\ast T(n/2)+O(n^2)$, so time complexity is $O(n^3)$
     • Improvement