CS 170

Efficient Algorithms and Intractable Problems

I will post my notes, code, resources, etc. here as the semester progresses.

Notes/Code

  • def mss_dac(a):
        if not a: return None
        n = len(a)
        if n == 1: 
            return a[0]
        mid = n // 2
        # divide 
        l = mss_dac(a[:mid])
        r = mss_dac(a[mid:])
        # boundary condition
        b_l = b_r = -float('inf')
        s_l = s_r = 0
        for i in range(mid, -1, -1):
            s_l += a[i]
            b_l = max(b_l, s_l)
        for i in range(mid + 1, n):
            s_r += a[i]
            b_r = max(b_r, s_r)
        b = b_l + b_r
        # conquer
        return max(l, r, b)
  • from random import choice
    def quickselect(a, l):
      if not a: return None
      v = choice(a) # pivot selection
      a_l, a_v, a_r = [], [], []
      for e in a: 
        if e < v: 
          a_l.append(e)
        elif e == v:
          a_v.append(e)
        else:
          a_r.append(e)
      if len(a_l) >= l:
        return quickselect(a_l, l)
      elif len(a_l) + len(a_v) >= l:
        return v
      else:
        return quickselect(a_r, l - len(a_l) - len(a_v))
  • def quantiles(a, k):
      if not a: return None
      assert(k >= 2 and (not k & (k-1))) # check if k is power of two
      mid = len(a) // 2
      med = quickselect(a, mid)
      print(a, med)
      if k == 2: return [med]
      # less efficient method of getting left and right arrays
      # could perform this in quickselect step
      l = [e for e in a if e <= med][:mid]
      r = [e for e in a if e >= med][-mid:]
      q_l = quantiles(l, k // 2)
      q_r = quantiles(r, k // 2)
      return q_l + [med] + q_r