512 Midterm Practice

Just for practice, if you find something wrong, feel free to contact me.

See solutions
We have $T(n) = n T(n-1) + 1 $ and we can prove $ n!$ by induction:
- For $n=1$, it works.
- For $n\ge{2}$, \[ n! = n((n-1)!) \le T(n) = n(T(n-1)+1) + 1 \le n(2(n-1)!-1)+1=2n!-n+1 \le 2n!-1 \]
So, $T(n)=\Theta{(n!)}$
a). $n^3 = \omega(\lg^2n)$

b). $\lg(n^2) = 2\lg(n)$, $\lg{2^{\sqrt{2\lg{n}}}}=\sqrt{2\lg{n}}\lg{2}$, so $\lg{n^2}=\omega{(\lg{2^{\sqrt{2\lg{n}}}})}$, thus ${n^2}=\omega{({2^{\sqrt{2\lg{n}}}})}$

c). $\Theta$

d). $(3/2)^n=o(2^n)$
a). \[ \begin{align*} T(n) &= T(n-2)+n^2\\ &= \frac{n}{2}T(0) + \sum_{i=0}^{\lfloor{\frac{n}{2}}\rfloor}{(n-2i)^2}\\ &= \Theta(n) + \Theta(n^3)\\ &= \Theta(n^3) \end{align*} \] b). Try Master Theorm first: $f(n)=\frac{n}{\lg{n}}$ \[ \lim_{n->\infty}{\frac{f(n)}{n}} = \lim_{n->\infty}{\frac{1}{\lg{n}}} = 0 \] so $f(n)=o(n)$, $T(n)=\Theta(n)$ c). As the link shows, \[ T(n)=\left\{\begin{array}{}T(0)+\sum_{k=1}^{n/2}\frac{1}{\log(2k)}&\text{if }n\text{ is even}\\T(1)+\sum_{k=1}^{(n-1)/2}\frac{1}{\log(2k+1)}&\text{if }n\text{ is odd}\end{array}\right.\tag{1} \] and \[ \begin{align} \sum_{k=1}^{(n-1)/2}\frac{1}{\log(2k+1)} &\le\frac{1}{\log(3)}+\int_1^{(n-1)/2}\frac{\mathrm{d}x}{\log(2x+1)}\\ &={\frac{1}{\log(3)}+\frac12\int_3^8\frac{\mathrm{d}x}{\log(x)}}+\frac12\int_8^n\frac{\mathrm{d}x}{\log(x)}\tag{2} \end{align} \] and \[ \begin{align} \sum_{k=1}^{n/2}\frac{1}{\log(2k)} &\le\frac{1}{\log(2)}+\int_1^{n/2}\frac{\mathrm{d}x}{\log(2x)}\\ &={\frac{1}{\log(2)}+\frac12\int_2^8\frac{\mathrm{d}x}{\log(x)}}+\frac12\int_8^n\frac{\mathrm{d}x}{\log(x)}\tag{3} \end{align} \] For $n \ge 8$, we have that $\log(x)\le2(\log(x)-1)$, thus \[ \begin{align} \frac12\int_8^n\frac{\mathrm{d}x}{\log(x)} &\le\int_8^n\frac{(\log(x)-1)\mathrm{d}x}{\log(x)^2}\\ &=\frac{n}{\log(n)}{-\frac{8}{\log(8)}}\tag{4} \end{align} \] Combining $(1)$ though $(4)$, we get that \[ T(n)\le{C}+\frac{n}{\log(n)}=O\left(\frac{n}{\log(n)}\right)\tag{5} \] and we have \[ T(n) = \sum{\frac{1}{\log{i}}} \ge \sum{\frac{1}{\log{n}}} = \lfloor\frac{n}{2}\rfloor \frac{1}{\log{n}} \tag{6} \] So \[ T(n) = \Omega(\frac{n}{\log{n}}) \tag{7} \] Combining $(5)$ and $(7)$ we have \[ T(n) = \Theta(\frac{n}{\log{n}}) \]
BWTRPUZ
Can't understand, Mergesort doesn't compare indices.
See solutions
a).
1
2
3
4
5
6
7
8
kthSmallest(a, k):
if len(a) == 1 and k<=1:
return a[0]
p = partition(a) // p <= len(a) * 0.6
if k <= p:
return kthSmallest(a[:p], k)
else:
return kthSmallest(a[p:], k-p)
a[:p] means a[0], a[1], a[2], ... , a[p-1],

a[p:] means a[p], a[p+1], ... , a[len(a)-1]

b). $T(n) = T(\frac{n}{5/3}) + n$

c). \[ n^{\log_{5/3}{1}} = 1 \] so $f(n)=\Omega(1)$,

in order to find $0<c<1$ s.t. $f(\frac{n}{5/3})\le{cf(n)}$, $\frac{n}{5/3}\le{cn}$, just let $c=\frac{3}{5}$

so $T(n)=\Theta(f(n))=\Theta(n)$, is leaner as well.

a).

isSemiconnected(G):
  V, E = G
  meta_G = compute_SCC_meta(G)  // which costs O(|V|+|E|)
  Vm, Em = meta_G
  if not connected(meta_G):  // which costs O(|Vm|+|Em|)
    return Flase
  Vt = topo_sort(meta_G)  // which costs O(|Vm|+|Em|)
  flag = True
  for i in range(len(Vt)-1):  // which costs O(|Vm|)
    v, u = Vt[i], Vt[i+1]
    flag &= check whether edge (v, u) exists // which costs O(1) when edges are store in matrix
  return flag

b). Since Vm<=V, Em<=E, as the comments on the right, we have $T=O(|V|+|E|)$

c). If a graph is semiconnected, its meta graph of SCC must be a link(only one single path), otherwise the subtrees of the branching node cannot visit each other.

See solutions
See solutions

We can use something like Segment Tree to do this. a).

MaxSum(1, n):
  pre_sum[0] = 0
  for i = 1 to n:  // O(n)
    pre_sum[i] = pre_sum[i-1] + a[i]
  return Query(1, n)[1]

MyMax(x, y):  // O(1)  
  if x[0] > y[0]:
    return x
  return y

Sum(l, r):  // O(1)
  return pre_sum[r] - pre_sum[l-1]

Query(l, r):
  if r < l: return (-inf, -1, -1), (-inf, -1, -1), (-inf, -1, -1)
  if l == r: return (a[l], l, l), (a[l], l, l), (a[l], l, l) 
  mid = (l + r) // 2
  left_pre, left_max, left_suf = Query(l, mid - 1)
  right_pre, right_max, right_suf = Query(mid, r)
  if Sum(l, mid - 1) + right_pre[0] > left_pre[0]:
    self_pre = (Sum(l, mid - 1) + right_pre[0], l, right_pre[2])
  else:
    self_pre = left_pre
  if left_suf[0] + Sum(mid, r) > right_suf[0]:
    self_suf = (left_suf[0] + Sum(mid, r), left_suf[1], r)
  else:
    self_suf = right_suf
  self_max = MyMax(left_max, right_max)
  self_max = MyMax(self_max, (left_suf[0]+right_pre[0], left_suf[1], right_pre[2]))
  self_max = MyMax(self_max, MyMax(left_pre, right_suf))
  return self_pre, self_max, self_suf

b). $T(n)=2T(n/2)+C$, so $T(n)=\Theta(n)$

c). If using dynamic programming, we can get another $O(n)$ algorithm, transmission formula is dp[i] = max(a[i], dp[i-1] + a[i]).