COMP3011 Assignment 1
MA Mingyu (Derek) | Sep 16, 2017
derek.ma | derek.ma@connect.polyu.hk
Question 1
a) \(T(n)=4T(n/2)+n\)
Use master method: \(n^{log_24}\) vs. \(n\)
\(log_24 - \epsilon = 1\) for some constant \(\epsilon = 1\), use case 1 in master method. Then \(T(n)=\Theta(n^2)\)
b) \(T(n) = T(\sqrt{n})+1\)
This case can't use master method. Then use substitution method. Guess: \(T(n) = \Theta(lg^{lgn})\).
Assume \(m=lgn\), then
\[
\begin{align}
T(n) = T(\sqrt{n})+1
\end{align}
\]
\[
\begin{align}
T(2^m) &= T(2^{m/2}) + 1
\end{align}
\]
Assume \(S(m) = T(2^m)\), then
\[
\begin{align}
S(m)=S(m/2) + 1
\end{align}
\]
According to master method, for function (3), \(log_12 = 0\), use case 2, then
\[
S(m) = \Theta(lgm)
\].
Change back to \(T(n)\):
\[
\begin{align}
T(n) = T(2^m) = S(m)= \Theta(lgm) = \Theta(lg^{lgn})
\end{align}
\]
C) \(T(n) = T(n/3) + T(n/4) + T(n/5) + n\)
Use substitution method. Guess: \(T(n)=\Theta(n)\).
Upper bound
From the recurrence, \(T(n)<=T(n/3)+T(n/4)+T(n/5)+cn\) for some constant \(c>0\).
Guess: \(T(n) = O(n)\)
Assume \(T(n) <= dn\) for some constant \(d>0\) holds for all positive \(m<n\).
So, in particular, for \(m=n/3 < n\): \(T(n/3) \leqslant d\frac{n}{3}\);
for \(m=n/4 < n\): \(T(n/4) \leqslant d\frac{n}{4}\);
for \(m=n/5 < n\): \(T(n/5) \leqslant d\frac{n}{5}\).
\[
\begin{align}
T(n) &\leqslant T(n/3)+T(n/4)+T(n/5)+cn \\
&\leqslant \frac{dn}{3} +\frac{dn}{4}+\frac{dn}{5}+cn \\
&= \frac{47}{60}dn + cn \\
&\leqslant dn
\end{align}
\]
by taking \(d >= \frac{60}{13}c\).
Thus, \(T(n)=O(nlgn)\)
Lower bound
From the recurrence, \(T(n)>=T(n/3)+T(n/4)+T(n/5)+cn\) for some constant \(c>0\).
Guess: \(T(n) = O(n)\)
Assume \(T(n) >= dn\) for some constant \(d>0\) holds for all positive \(m<n\).
So, in particular, for \(m=n/3 < n\): \(T(n/3) \geqslant d\frac{n}{3}\);
for \(m=n/4 < n\): \(T(n/4) \geqslant d\frac{n}{4}\);
for \(m=n/5 < n\): \(T(n/5) \geqslant d\frac{n}{5}\).
\[
\begin{align}
T(n) &\geqslant T(n/3)+T(n/4)+T(n/5)+cn \\
&\geqslant \frac{dn}{3} +\frac{dn}{4}+\frac{dn}{5}+cn \\
&= \frac{47}{60}dn + cn \geqslant dn
\end{align}
\]
by taking \(d \leqslant \frac{60}{13}c\).
Thus, \(T(n)=\Omega(nlgn)\)
By theorem 3.1, \(T(n)=\Theta(nlgn)\).
Question 2
Each term gives a different equivalence class, where the > symbol means \(\omega\)
\[
n^{\frac{n}{lgn}} > (5/3)^n > (lgn)^{lgn} > n^{99}
\], that is:
\[
f_3(n) > f_2{n} > f_4{n} > f_1{n}
\]. To prove it, just take log for each item and compare.
Question 3
a)
There are 2 squares in string ALFALFA. They are
- When i=1 and k=3, the substring
ALFALF; - When i=2 and k=3, the substring
LFALFA.
b)
DETECT-SQUARE(string, head, tail)
1 middle = floor((head + tail) / 2)
2 a = DETECT-SQUARE(string, head, middle)
3 b = DETECT-SQUARE(string, middle, tail)
4 c = ACROSS(string[head, middle], string[middle, tail])
5 if (a, b or c is 'yes')
6 return 'yes'
7 else
8 return 'no'
//Initial Call:
DETECT-SQUARE(string, 0, length(string))
Calculate the time complexity:
| Line # | Time Complexity |
|---|---|
| 1 | \(O(1)\) |
| 2 | \(T(m/2)\) |
| 3 | \(T(m/2)\) |
| 4 | \(O(m)\) |
| 5 | \(O(1)\) |
| 6 | \(O(1)\) |
| 7 | \(O(1)\) |
| 8 | \(O(1)\) |
According to the table:
\(T(m) = 2T(m/2) + O(m)\), according to master method, \(m^{log_22} = m\), use case 2:
\[
T(m) = \Theta(n^{log_22}lgn) = \Theta(nlogn)
\]
Question 4
In my algorithm, for every iteration, select one node with least undirected edges and add directions to the undirected edges connected to the node. All the new directions are outgoing from that selected node. Then do next iteration.
Algorithm pseudocode
DIRECTGRAPH(nodes, undirected_edges)
1 var node = the node with least undirected edges
2 var undirected_edges_of_node = all undirected edges of node
3 assign all directions of undirected_edges_of_node from node to others
4 var other_nodes = nodes.remove(node)
5 var other_edges = edges.remove(edge)
6 DIRECTGRAPH(other_nodes, other_edges)
// Initial call
DIRECTGRAPH(all_nodes, all_edges)
A demonstration
Proof of correctness
1 - Proof of directed graph has no cycles
Proof by induction:
1.1 Claim
In any iteration, the directed graph generated so far has no cycle.
1.2 Base case
For the case with only one node, all directed edges so far are outgoing from the selected node. It's impossible to form a cycle.
1.3 General case
Suppose the claim is true at the beginning of iteration k. Let's say the directed graph generated so far is \(G_{k-1}\), and the graph after this iteration is \(G_{k}\). Assume that there is no cycle in \(G_{k-1}\).
Now let's select a new node \(node_k\) and set directions for all undirected edges of \(node_k\) to outgoing from \(node_k\). So the only difference between \(G_{k-1}\) and \(G_{k}\) is only the node \(node_k\) and new directed edges around \(node_k\).
Now let's raise a assumption:
Assumption: there is a cycle in \(G_{k}\)
There are two cases under this assumption:
1.3.1 If \(node_k\) is in not in the cycle
If the cycle doesn't contains \(node_k\), then all the edges in the cycle already exist in the graph \(G_{k-1}\). But according to the assumption of this induction proof, there is no cycle in \(G_{k-1}\). There is a contradiction here. So this situation is impossible.
1.3.2 If \(node_k\) is in the cycle
If the cycle contains \(node_k\). Then let's see the cycle. Assume \(node_j\) is the earliest node of this cycle's node(i.e. the first node appear among all nodes of the cycle). To form a cycle, there must be at least one incoming edges to \(node_j\), which must from a node \(node_v\) which is also on the cycle. Because the edge from \(node_v\) to \(node_j\) is incoming to \(node_j\), then we can know \(node_v\) exists before \(node_j\). But \(node_j\) is the earliest node on the cycle. There is a contradiction. This situation is impossible.
Now we can know, all these two situations are impossible, then the assumption is wrong. So that, there is no cycle in \(G_{k}\)
2 - Proof of maximum number of outgoing edges from any vertex is as small as possible
After a greedy choice in a iteration, say the following variables:
\(maxout_g\): the value of max outgoing edges in the graph using greedy choices;
\(maxout_o\): the optimal value of the max outgoing edges in the graph after this iteration;
\(node_i\): a node in the graph generated by greedy algorithm so far with outgoing degree \(maxout_g\).
There two possible cases are shown as follows:
Case 2.1: \(maxout_g = maxout_o\)
They we can find that the greedy choice is one of the optimal solution. This algorithm works for this problem.
Case 2.2: \(maxout_g \ne maxout_o\)
In this case, we can get that:
\[
maxout_g = maxout_o + c (c>0)
\]. Because the outgoing degree of \(node_i\) is \(maxout_g\), there are at least \(maxout_g\) nodes around the \(node_i\). Outgoing edges from \(node_i\) can be pointed to these nodes around it. Let's say the nodes around the \(node_i\) which connect with it by outgoing edges from \(node_i\) is \(nodes_{around-i}\).
According to the algorithm, the algorithm select \(node_i\) rather than any node among \(nodes_{around-i}\). This means that all nodes in \(nodes_{around-i}\) must have more than \(maxout_g\) undirected edges. So that the algorithm will chooce \(node_i\) because it has less undirected edges than any node in \(nodes_{around-i}\) before this particular iteration starts.
But \(maxout_o < maxout_g\), the maximum outgoing degree is only \(maxout_o\). We can know among \(maxout_g\) edges around \(node_i\), there must by at least one edges is incoming rather than outgoing from \(node_i\). The same situation happen to all \(nodes_{around-i}\), which means their outgoing "children" also need to have at least one incoming edges rather than outgoing from all nodes of \(nodes_{around-i}\). So we can know that all nodes in the graph have incoming and outgoing edges. But there are limited number of nodes in the graph, which means there must be cycles in the graph.
According to the proof above, there is no cycles in the graph. Then there is a contradiction here. Now we can know that the case 2.2 is impossible.
According to the analysis of case 2.1 and 2.2, we know that only case 2.1 is possible. Thus we can prove that maximum number of outgoing edges from any vertex is as small as possible.
Proof of correctness(alternative approach)
Proof by induction that this algorithm works correctly:
Claim
The directed graph with n node constructed by this algorithm so far:
- has no cycles;
- the maximum number of outgoing edges from any vertex is the smallest.
Base case
1.Proof of no cycles
There is no edge for only one node in the graph. So definitely, there is no cycle.
2.Proof of number of the outgoing edges is smallest
There is no edge for only one node in the graph, the number of the outgoing edges is 0, which is definitely smallest.
General case
Suppose the claim is true with k nodes in the graph, then let's consider the graph with k+1 nodes. Say the graph with k+1 nodes is \(G_{k+1}\).
Select the node in \(G_{k+1}\) with least degree(i.e. the first one chosen by the first iteration of the algorithm) and name it \(node_i\).
Because the claim is true for the graph with k node, we can say: the directed graph generated by this algorithm with k node has no cycle, and the max number of outgoing edges from any nodes are optimized to the smallest value.
1.Proof of no cycles
All the directed edges between \(node_i\) and other nodes and their connections are outgoing from the \(node_i\). Assume there is a cycle in the graph. There are two sub-situations under this assumption:
1.1 situation
If the cycle doesn't contains \(node_i\), then all the edges in the cycle already exist in the graph with k nodes. But according to the claim, there is no cycle in this sub-graph. There is a contradiction here. So this situation is impossible.
1.2 situation
If the cycle contains \(node_i\). Then let's see the cycle. Assume \(node_j\) is the earliest node of this cycle's node(i.e. the first node appear among all nodes of the cycle). To form a cycle, there must be at least one incoming edges to \(node_j\), which must from a node \(node_v\) which is also on the cycle. Because the edge from \(node_v\) to \(node_j\) is incoming to \(node_j\), then we can know \(node_v\) exists before \(node_j\). But \(node_j\) is the earliest node on the cycle. There is a contradiction. This situation is impossible.
According to above, none of the two situations holds. So there is no cycle in the graph \(G_{k+1}\). So the first property in the claim holds for the graph with k+1 nodes.
2.Proof of smallest value of max outgoing edges in the graph
Consider \(node_i\) and other nodes and their connections:
Consider all undirected edges connecting to \(node_i\), all of these undirected edges connect with some nodes in the k nodes. For the directions of these undirected edges, according to this algorithm, will be outgoing from \(node_i\). Consider these directions, if some of these directions are not outgoing from \(node_i\):
Then some nodes in k nodes will have more outgoing edges, which may lead to more max outgoing degree. Then there will be a contradiction on the max value of the outgoing edges among k nodes. Current value is already smallest according to the claim, but if some of the directions are not outgoing from \(node_i\) in terms of the edges connecting from \(node_i\) to nodes in k nodes, then the max value of outgoing edges will increase, which is not possible.
Among the k nodes and their connections, there is a smallest value for maximum count of outgoing edges. But since \(node_i\) is the least degree node in the k+1 value, so it will not increase the smallest value in the graph with k nodes.
So we can know, \(G_{k+1}\) has smallest max value of outgoing edges generated by the algorithm.
According to the proof above, we can imply that the claim is true and the algorithm works for this kind of task.
Reference
Asahiro, Y., Jansson, J., Miyano, E., & Ono, H. (2016). Degree-constrained graph orientation: Maximum satisfaction and minimum violation. Theory of Computing Systems, 58(1), 60-93.
https://carlstrom.com/stanford/cs161/ps1sol.pdf