Problem Set 7

Recursive Correctness

Note. These problems (in a slightly modified form) appeared in the final exam when I taught the course in the past. They are on the harder side for exam problems.

1 Modular Exponentiation

In lecture we studied algorithms for multiplication. In this problem, we’ll explore another common mathematical operation - exponentiation! To make things a little more interesting/manageable we’ll study modular exponentiation.

Input. \(b, e, p \in \mathbb{N}\)

Precondition. \(b, e, p \in \mathbb{N}\), with \(0 \leq b < p\).

Postcondition. Returns \(b^e \mod{p}\)

You may assume the following lemma:

Lemma. Let \(a, b, p \in \mathbb{N}\). Then \((a \mod{p}) \cdot (b \mod{p}) \mod{p} = (a \cdot b) \mod{p}\).

Also assume the following:

For any number \(a \in \mathbb{N}\), number of digits used to represent \(a\) is \(\Theta(\log(a))\).
It takes time \(\Theta(n\cdot m )\) to multiply/divide a \(n\) digit number with a \(m\) digit number. In particular, for any two numbers \(x, y\), then it takes time \(\Theta(\log(x) \cdot \log(y))\) to compute \(x \cdot y\), and \(x \mod y\).
\(\log^2(p)\) is shorthand for \((\log(p))^2\).

1.1

Let’s start with the naive algorithm.

def ExpNaive(b, e, p):
    a = 1
    for _ in range(e):
        a = a * b
    return a % p

Show that worst case asymptotic runtime of ExpNaive in terms of \(e\) and \(p\) is at least \(\Omega(e^2\log^2(p))\).

Solution

Pick \(b = p-1\). At iteration \(e/2+1\), you’re computing \(b^{e/2} \cdot b\) which takes time \(\Omega(\log(b^{e/2}) \log(b)) = \Omega(e \log^2(b))\). Summing over the last \(e/2\) iterations (which each take at least the time of iteration \(e/2 + 1\)), we get that the total runtime of the algorithm is at least \(e/2 \cdot \Omega(e \log^2(b)) = \Omega(e^2\log^2(p))\).

1.2

Here’s a slightly better algorithm.

def ExpModFirst(b, e, p):
        if e == 0:
                return 1
        else:
                return b * ExpModFirst(b, e - 1, p) % p

Prove ExpModFirst is correct.

Solution

Let \(P(e):\) For all \(b, p \in \mathbb{N}\) with \(0 \leq b < p\), ExpModFirst returns \(b^e \mod p\) on input \(b, e, p\). We’ll show \(\forall e \in \mathbb{N}\), \(P(e)\) holds.

By induction on \(e\).

Base Case. When \(e = 0\), we return \(1\), and \(b^0 = 1\), so we are good.

Inductive Step. Let \(k \in \mathbb{N}\) with \(k > 0\), and suppose \(P(0),...,P(k-1)\). We’ll show \(P(k)\). We return \(b \cdot \text{ExpModFirst}(b, k-1, p) \mod p\). By the IH, we know that \(\text{ExpModFirst}(b, k-1, p)\) returns \(b^{k-1} \mod p\). Thus, we return \(b \cdot (b^{k-1} \mod p) \mod p\), which is equal to \(b^k \mod p\) by the lemma.

1.3

Prove that the worst case asymptotic runtime of ExpModFirst is asymptotically faster than ExpNaive in terms of \(e\) and \(p\).

Solution

Note that \(b\), the result of the recursive call, and \(p\) are all at most \(p\). Hence, the non-recursive work is at most \(O(\log^2(p))\), since we do one multiplication and one modulo operation.

Additionally, there are at most \(e\) recursive calls, so the total runtime is \(O(e\log^2(p))\). Which is better than the naive algorithm, which has a runtime of \(\Omega(e^2\log^2(p))\).

1.4

Here’s mysterious algorithm, ExpRec.

def ExpRec(b, e, p):
    if e == 0:
        return 1
    if e % 2 == 0:
        return ExpRec(b * b % p, e // 2, p)
    else:
        return b * ExpRec(b * b % p, (e - 1) // 2, p) % p

Prove ExpRec is correct.

Solution

Note: This is called the “repeated squaring” algorithm for exponentiation in case you want to look it up.

Define \(P(e):\) For all \(b, p \in \mathbb{N}\) with \(0 \leq b < p\), ExpRec returns \(b^e \mod p\) on input \(b, e, p\). We will show \(\forall e \in \mathbb{N}, P(e)\) holds.

By induction on \(e\).

Base Case. Note that when \(e = 0\), we return \(1\), and \(b^0 = 1\), so we are good.

Inductive Step. Let \(k \in \mathbb{N}\) with \(k > 0\), and suppose \(P(0),...,P(k-1)\). We’ll show \(P(k)\). If \(k\) is even, then we return ExpRec called with the \(e\) parameter being \(k/2\). Since \(k\) is even and \(k>0\), \(k\geq2\), and \(0 \leq k/2 \leq k-1\). Thus, the IH applies. Therefore, we return \[(b^2 \mod p)^{k/2} \mod p = b^{2k/2} \mod p = b^k \mod p\] as expected. Note that we used the Lemma here.

The calculation is similar in the other case. If \(k\) is odd, then \(0 \leq (k-1)/2 < k\), so again, the IH applies. In this case, we return

\[b \cdot (b^2 \mod p)^{(k-1)/2} \mod p = b \cdot b^{2(k-1)/2} \mod p = b^k \mod p\] as required.

1.5

Find a bound on the worst case asymptotic runtime of ExpRec in terms of \(e\) and \(p\).

Give informal reasoning for the runtime and show that it is asymptotically faster than ExpModFirst.

Solution

The analysis is the same as before except that for this algorithm, we reach the base case after at most \(\log_2(e)\) recursive calls (instead of \(e\) calls). Thus, the overall runtime is \(O(\log_2(e) \cdot \log^2(p))\).

2 Middle First Search

In this problem, we study the problem of determining whether two vertices are connected by a path. You may have heard of Depth First Search or Breadth First Search. Either of these algorithms would work for this task. We’ll study a different algorithm called Middle First Search.

Input: \(G=(V, E), s, t, k\)

Precondition:

\(G = (V, E)\) is a directed graph
\(s, t \in V\)
\(k \in \mathbb{N}\).

Postcondition: Returns True if there exists a (directed) path from \(s\) to \(t\) in \(G\), of length at most \(k\), and False otherwise.

As a reminder, a path in a graph \(G = (V, E)\) is a sequence of vertices \((v_0,...,v_k)\), where each of \((v_i, v_{i+1}) \in E\), and the length is the number of edges in the path. As an edge case, a path consisting of a single vertex \(v\) is a path from \(v\) to \(v\) with length \(0\).

def MiddleFirstSearch(G, s, t, k):
    if k == 0:
        return s == t
    elif k == 1:
        return (s, t) in E or s == t
    else:
        for u in V:
                if MiddleFirstSearch(G, s, u, floor(k/2)) and MiddleFirstSearch(G, u, t, ceil(k/2)):
                        return True
        return False

Prove MiddleFirstSearch is correct by induction on \(k\).

You may assume that the for loop starting at line 5 just iterates over every vertex of \(V\), runs the two recursive calls, and returns True if both calls return true. I.e., you do not need to prove correctness of the for loop.

Solution

Note: This is called “Savitch’s algorithm” in case you want to look it up. It’s not particularly time efficient, but it very significant in complexity theory. Take CSC463 if you want to learn more about it!

Let \(P(k)\) be the following predicate. For any graph, \(G = (V, E), s, t\), MiddleFirstSearch is correct on input \(G, s, t, k\).

Base Case. \(P(0), P(1)\)

There is a path from \(s\) to \(t\) of length \(0\) iff \(s = t\).
There is a path from \(s\) to \(t\) of length \(1\) iff \((s,t) \in E\).

When \(k = 0\), the algorithm returns \(s == t\), and when \(k = 1\), the algorithm returns \((s, t) \in E\) OR \(s == t\).

Inductive Step. Let \(k \in \mathbb{N}\), with \(k > 1\), and suppose \(P(k')\) for each \(k' < k\), we’ll show \(P(k)\).

Let \(G=(V, E), s, t\) be any graph satisfying the precondition. Since \(k > 1\), we reach the else case of the algorithm. First of all, note that \(\left\lfloor k/2 \right\rfloor \leq \left\lceil k/2 \right\rceil < k\) since \(k \geq 2\), so the IH captures each of the recursive calls.

Suppose there exists a path from \(s\) to \(t\) in \(G\) with length at most \(k\), then there exists a path \(P = (v_0 = s,v_1,...,v_{j}=t)\) in \(G\) such that \(j \leq k\). If \(j > \left\lfloor k/2 \right\rfloor\), then \((v_0, v_1,...,v_{\left\lfloor k/2 \right\rfloor})\) is a path of length \(\left\lfloor k/2 \right\rfloor\) to \(v_{\left\lfloor k/2 \right\rfloor}\), and \((v_{\left\lfloor k/2 \right\rfloor},v_{\left\lfloor k/2 \right\rfloor+1},...,v_{j})\) is a path of length \(j - \left\lfloor k/2 \right\rfloor\leq \left\lceil k/2 \right\rceil\) from \(v_{\left\lfloor k/2 \right\rfloor}\) to \(t\). Thus, when the algorithm tries \(u = v_{\left\lfloor k/2 \right\rfloor}\), both recursive calls will return True, and the MiddleFirstSearch returns true as required. If \(j \leq \left\lfloor k/2 \right\rfloor\), when the algorithm tries \(u = t\), both recursive calls will return True: the first since \(P\) is a path of length at most \(\left\lfloor k/2 \right\rfloor\) from \(s\) to \(t\), and the second since there is a path of length 0 for \(t\) to \(t\).

Similarly, if MiddleFirstSearch returns True, that means there exists some vertex \(u\) such that there is a path of length at most \(\left\lfloor k/2 \right\rfloor\) from \(s\) to \(u\), and another path of length at most \(\left\lceil k/2 \right\rceil\) from \(u\) to \(t\). Composing these two paths, we get a path of length at most \(k\) from \(s\) to \(t\).

Thus, MiddleFirstSearch returns True iff there is a path of length at most \(k\) from \(s\) to \(t\) in \(G\) as required.

2.1

Fix a graph \(G=(V, E)\) with \(2^{10} = 1024\) vertices, and let \(s, t \in V\). Let \(T(k)\) be the runtime of MiddleFirstSearch on input \(G(V, E), s, t, k\). Write a recurrence relation for \(T(k)\). You can ignore floors and ceilings.

Solution

\(T(k) = 2^{10}\cdot T(k/2) + 2^{10}\cdot T(k/2) + 2^{10} = T(k) = 2^{11}\cdot T(k/2) + 1\)

2.2

Solve the recurrence from the previous problem.

Solution

This is a standard form recurrence with \(a = 2^{11}, b = 2, f(k) = 1\). The leaf work is \(k^{\log_2(2^{11})} = k^{11}\). The root work is \(1 = k^0\). \(k^0 = O(k^{10}) = O(k^{11 - \epsilon})\) for \(\epsilon =1\). Thus, we are in the leaf-heavy case of The Master Theorem, and \(T(k) = k^{ 11 }\).

2.3

Let \(T(n)\) be the runtime of MiddleFirstSearch on input \(G(V, E), s, t, n\) where \(n = |V|\).

Find the best upper bound on \(T(n)\) that you can. Provide some justification for your bound.

Solution

The recurrence is \(T(n) = 2n \cdot T(n/2) + n\).

Note: the Master Theorem is not applicable here since \(a\), the braching factor, is not constant (it depends on \(n\)). However, it happens to give the right answer in this particular case.

The leaf work is \(n^{\log_2(2n)}\), the root work is \(n\). The leaf work clearly dominates the root work, so the runtime is \(T(n) = \Theta(n^{\log_2(2n)}) = \Theta(n^{\log(n) + 1})\).

Since the Master Theorem doesn’t actually apply here, we can directly analyse the recursion tree. The height of the recursion tree is \(\log_2(n)\), at level \(h\), there are \((2n)^h\) nodes, each doing work \(n/2^h\). The work being done at level \(h\) is then \(n^{h+1}\).

\[ \sum_{h=0}^{\log_2(n)} n^{h+1} = n \cdot \frac{n^{\log_2(n)+1} - 1}{n - 1} = O(n^{\log_2(n) + 1}). \]

Note we used the formula for the sum of a geometric series.

Anything around \(n^{\log(n)} = 2^{\log^2(n)}\) with justification is fine.