My Blog
0%

Berkeley CS170 Spring 2022

Posted on Edited on In
Symbols count in article: 2.1k Reading time ≈ 2 mins.

Week 1

01/18/2022

  1. Analysis of Fibonacci 

    1
    2
    3
    4
    5
    6
    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]\) 
    1
    2
    3
    4
    5
    6
    7
    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 * 2^{n/2} + x_R\), \(y = y_L * 2^{n/2} + y_R\).Then we have \(x * y = 2^{n} {x_L * y_L} + 2^{n/2} * (x_L * y_R + x_R * y_L) + x_R * y_R\) 

      1
      2
      3
      4
      5
      6
      7
      8
      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 * T(n/2) + c * n\)

    • Rule of thumb: sum of an increasing geometric series is \(O(last\;term)\) 

      1
      2
      3
      4
      5
      6
      7
      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^{log_23}) = O(n^{1.6})\) operation, since \(T(n) = 3 * T(n/2) + c * 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 * T(n/2) + O(n^2)\), so time complexity is \(O(n^3)\)
      • Improvement