512 Midterm Practice

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

  1. See solutions

  2. We have $T(n) = n T(n-1) + 1 $ and we can prove $ n!\le{T(n)}\le{2n!-1}$ by induction:

    • For $n=1$, it works.

    • For $n\ge{2}$,

    So, $T(n)=\Theta{(n!)}$

  3. 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)$

  4. a).

    b). Try Master Theorm first:
    $f(n)=\frac{n}{\lg{n}}$

    so $f(n)=o(n)$, $T(n)=\Theta(n)$
    c). As the link shows,

    and

    and

    For $n \ge 8$, we have that $\log(x)\le2(\log(x)-1)$, thus

    Combining $(1)$ though $(4)$, we get that

    and we have

    So

    Combining $(5)$ and $(7)$ we have

  5. BWTRPUZ

  6. Can’t understand, Mergesort doesn’t compare indices.

  7. See solutions

  8. 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).

    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.

  9. a).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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.

  10. See solutions

  11. See solutions

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    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]).