Andrew's Exercise Solutions: Algorithms: Design and Analysis: Part 1

Showing posts with label Algorithms: Design and Analysis: Part 1. Show all posts

Wednesday, November 25, 2015

Algorithms: Design and Analysis, Part 1 - Index

Algorithms: Design and Analysis, Part 1 - Exam Question 20

Problem:

Recall the Master Method and its three parameters $ a,b,d $. Which of the following is the best interpretation of $ b^d $, in the context of divide-and-conquer algorithms?

Solution:

I revisited the lecture video for this one, and now I am explaining in my own words.

The current amount of work is $ O(n^d) $.
The problem size become $ \frac{n}{b} $, and then the amount of work (for the merge step, ignoring recursive calls is $ O((\frac{n}{b})^d) $.

Therefore the amount of work is reduced by a factor of $ O(b^d) $, that's why this option is correct.

(Option 1) The rate at which the work-per-subproblem is shrinking (per level of recursion).

Algorithms: Design and Analysis, Part 1 - Exam Question 19

Problem:

Running time of Strassen's matrix multiplication algorithm: Suppose that the running time of an algorithm is governed by the recurrence $ T(n)=7*T(n/2)+n$2 $. What's the overall asymptotic running time (i.e., the value of $ T(n) $)?

Solution:

Applying master theorem, we have the variables $ a = 7, b = 2, d = 2 $, and we have the $ 7 = a > b^d = 4 $ case, therefore the answer is $ \theta(n^{\log_2{7}}) $

Algorithms: Design and Analysis, Part 1 - Exam Question 18

Problem:

Suppose you are given $ k $ sorted arrays, each with $ n $ elements, and you want to combine them into a single array of kn elements. Consider the following approach. Divide the $ k $ arrays into $ k/2 $ pairs of arrays, and use the Merge subroutine taught in the MergeSort lectures to combine each pair. Now you are left with $ k/2 $ sorted arrays, each with $ 2n $ elements. Repeat this approach until you have a single sorted array with kn elements. What is the running time of this procedure, as a function of $ k $ and $ n $?

Solution:

The first iteration deal with $ \frac{k}{2} $ array of length $ n $, so it takes $ \theta(nk) $ time.
The second iteration deal with $ \frac{k}{4} $ array of length $ 2n $, so it also takes $ \theta(nk) $ time.

Therefore the overall execution time is really just $ \theta(nk\log k) $ time.

This is simply and I should have got this correct, I made a careless mistake here, sigh.

Algorithms: Design and Analysis, Part 1 - Exam Question 17

Problem:

Which of the following statements about Dijkstra's shortest-path algorithm are true for input graphs that might have some negative edge lengths?

Solution:

(Option 1) It is guaranteed to terminate.
The algorithm, regardless of correctness, also make progress towards completion by removing a vertex from the unknown set, so it must terminate.

(Option 2) It may or may not correctly compute shortest-path distances (from a given source vertex to all other vertices), depending on the graph.
This is true because the graph may not have any negative edge at all.

(Option 3) It may or may not terminate (depending on the graph).
This is not true given option 1

(Option 4) It is guaranteed to correctly compute shortest-path distances (from a given source vertex to all other vertices).
This is not true, or else we don't really need the restriction.

Algorithms: Design and Analysis, Part 1 - Exam Question 16

Problem:

Which of the following patterns in a computer program suggests that a hash table could provide a significant speed-up (check all that apply)?

Solution:

Hash table are great for lookup but do not good for finding minimum of maximum.

Algorithms: Design and Analysis, Part 1 - Exam Question 15

Problem:

Which of the following patterns in a computer program suggests that a heap data structure could provide a significant speed-up (check all that apply)?

Solution:

Heap is good for finding minimum and maximum but do no good to lookups

Algorithms: Design and Analysis, Part 1 - Exam Question 14

Problem:

Suppose you implement the operations Insert and Extract-Min using a sorted array (from biggest to smallest). What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)

Solution:

This is again a done assignment problem, find the solution below

Algorithms: Design and Analysis, Part 1 - Problem Set 5 - Question 3

Algorithms: Design and Analysis, Part 1 - Exam Question 13

Problem:

Suppose that a randomized algorithm succeeds (e.g., correctly computes the minimum cut of a graph) with probability $ p $ (with $ 0 < p < 1$ ). Let $ \epsilon $ be a small positive number (less than 1). How many independent times do you need to run the algorithm to ensure that, with probability at least $ 1 - \epsilon $, at least one trial succeeds?

Solution:

Suppose we run the algorithm for $ n $ times and therefore the probability for all of these independent trials to fail is $ (1 - p)^n $.

The probability to success is therefore $ 1 - (1 - p)^n > 1 -\epsilon $.

$ \begin{eqnarray*} 1 - (1 - p)^n &>& 1 -\epsilon \\ - (1 - p)^n &>& -\epsilon \\ (1 - p)^n &<& \epsilon \\ \log((1 - p)^n) &<& \log \epsilon \\ n\log(1 - p) &<& \log \epsilon \\ n &>& \frac{\log \epsilon}{\log(1 - p)} \end{eqnarray*} $

Note the change of inequality sign in the last line, this is because $ \log(1 - p) < 0 $

Algorithms: Design and Analysis, Part 1 - Exam Question 12

Problem:

When does a directed graph have a unique topological ordering?

Solution:

(Option 1) Whenever it is directed acyclic
This is wrong 1->2, 3 has two topological order

(Option 2) Whenever it has a unique cycle
This is wrong, any graph with a cycle do not have a topological order.

(Option 3) Whenever it is a complete directed graph
A complete directed graph of size > 1 will necessarily have cycle, so no topological order at all.

(Option 4) None of the other options
This is the only possible solution now, and that's correct!

Algorithms: Design and Analysis, Part 1 - Exam Question 11

Problem:

Which of the following statements hold? (As usual n and m denote the number of vertices and edges, respectively, of a graph.) [Check all that apply.]

Solution:

Breadth-first search can be used to compute the connected components of an undirected graph in $ O(m+n) $ time.
Depth-first search can be used to compute the strongly connected components of a directed graph in $ O(m+n) $ time.
Breadth-first search can be used to compute shortest paths in $ O(m+n) $ time (when every edge has unit length).
Depth-first search can be used to compute a topological ordering of a directed acyclic graph in $ O(m+n) $ time.

All of these options are correct and all of them are just standard results.

Algorithms: Design and Analysis, Part 1 - Exam Question 10

Problem:

Let $ 0< \alpha <.5 $ be some constant. Consider running the Partition subroutine on an array with no duplicate elements and with the pivot element chosen uniformly at random (as in QuickSort and RSelect). What is the probability that, after partitioning, both subarrays (elements to the left of the pivot, and elements to the right of the pivot) have size at least $ \alpha $ times that of the original array?

Solution:

It is easiest to look at problem of this sort in term of concrete numbers, it is very easy that way, let say $ \alpha = 0.2 $ and $ n = 10 $. Then the requirement is that we have at least 2 elements in both subarrays. Further suppose the numbers are simply $ 1,2,\cdots, 10 $, then as long as we are not picking 1, 2, 9, 10, we are good to go.

Generalizing, it is easy to see that if we are not picking the $ n\alpha $ largest numbers and $ n\alpha $ smallest numbers, then we satisfy the condition, the probability of that is simply $ 1 - 2\alpha $.

Algorithms: Design and Analysis, Part 1 - Exam Question 9

Problem:

Let f and g be two increasing functions, defined on the natural numbers, with $ f(1) $ , $ g(1) \ge 1 $. Assume that $ f(n)=O(g(n)) $ . Is $ 2^{f(n)}=O(2^{g(n)}) $? (Multiple answers may be correct, check all that apply.)

Solution:

This is simply an assignment problem I have done before, it can be found in the link below.

Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 3

The key idea is just going back to the definition and argue the necessary condition for $ 2^{f(n)}=O(2^{g(n)}) $ is $ f(n) \le g(n) $.

Algorithms: Design and Analysis, Part 1 - Exam Question 8

Problem:

What is the asymptotic running time of Randomized QuickSort on arrays of length $ n $, in expectation (over the choice of random pivots) and in the worst case, respectively?

Solution:

It is again just memorizing standard results:

The expected result is $ \theta(n \log n) $, and the worst case result is $ \theta(n^2) $.

Algorithms: Design and Analysis, Part 1 - Exam Question 7

Problem:

On adding one extra edge to a directed graph G, the number of strongly connected components...?

Solution:

Anything could happen!

Suppose the graph is a direct chain, adding an edge to make it a cycle can make it reduce a lot of strongly connected components.

1 -> 2 -> 3 -> 4 (4 strongly connected components)

Adding 4 -> 1 will result in just 1 strongly connected components.

On the other hand adding one more edge, say 1 -> 3, does not decrease it any more.

So the answer is this choice:

...might or might not remain the same (depending on the graph).

Algorithms: Design and Analysis, Part 1 - Exam Question 6

Problem:

What is the asymptotic running time of the Insert and Extract-Min operations, respectively, for a heap with $ n $ objects?

Solution:

This is just memorizing the standard results.

Insert takes $ O(\log n) $ time.
Extract-Min takes $ O(\log n) $ time.

Note that the problem is a little sloppy here, it requires an answer in $ \Theta $, however, in the best case both operation takes just $ O(1) $ time, and the problem do not explicitly ask for the worst case time.

Algorithms: Design and Analysis, Part 1 - Exam Question 5

Problem:

What is the running time of depth - first search, as a function of n and m, if the input graph $ G = (V,E) $ is represented by an adjacency matrix (i.e., NOT an adjacency list), where as usual $ n=|V| $ and $ m=|E| $ ?

Solution:

Each node need to be gone through. And for each of them it need to look at all other nodes for a possible edge, so the time is $ \theta(n^2) $.

Algorithms: Design and Analysis, Part 1 - Exam Question 4

Problem:

Consider a directed graph $ G = (V,E) $ with non-negative edge lengths and two distinct vertices $ s $ and $ t $ of $ V $. Let $ P $ denote a shortest path from $ s $ to $ t $ in $ G $. If we add 10 to the length of every edge in the graph, then:

Solution:

Let consider this graph:

s -1-> a
a -1-> t
s -3-> t

The current shortest path is s -1-> a -1-> t has cost 2.

Suppose we add 10 to each edges, the path is no longer optimal, the optimal path will become

s -13-> t

The general transformation of path cost is path cost + number of edges times 10, therefore, path with less number of edge will be proportionally shorten than the one with larger number of edges, the construction of the example above is based on this.

Therefore we can consider the choices now:

(Option 1) $ P $ definitely remains a shortest $ s - t $ path.
This is obviously wrong given the example above.

(Option 2) $ P $ might or might not remain a shortest $ s − t $path (depending on the graph).
This is true, the example above shown this could be not the shortest path. It could be the shortest path, for example, in case there is only one path.

(Option 3) $ P $ definitely does not remain a shortest $ s - t $ path.
This is obviously wrong given the above.

(Option 4) If $ P $ has only one edge, then $ P $ definitely remains a shortest $ s − t $ path.
This is true, but it is non-obvious. This can be proved by looking at the cost transformation.

Suppose the contrary that there exists another path $ Q $ after the transformation is shorter than $ P $, then

New Cost of Q < New Cost of P
Old Cost of Q + num edges in Q times 10 < Old Cost of P + 10

Now num edges in Q must be at least 1, so we have

Old Cost of Q + 10 < Old Cost of P + 10
Old Cost of Q < Old Cost of P

But that is impossible! $ P $ was the shortest path!

Therefore we proved option 4 is true.

Algorithms: Design and Analysis, Part 1 - Exam Question 3

Problem:

What is the asymptotic worst-case running time of MergeSort, as a function of the input array length $ n $?

Solution:

Actually all recursion levels will take $ \theta(n) $ time to create the merged arrays, so the time is obviously $ \theta(n \log n) $ time.

Algorithms: Design and Analysis, Part 1 - Exam Question 2

Problem:

Here is an array of ten integers: 5 3 8 9 1 7 0 2 6 4

Suppose we run MergeSort on this array. What is the number in the 7th position of the partially sorted array after the outermost two recursive calls have completed (i.e., just before the very last Merge step)? (When we say "7th" position, we're counting positions starting at 1; for example, the input array has a "0" in its 7th position.)

Solution:

Just before the last merge, the left half and the right half must be sorted, so it should be

1 3 5 8 9 0 2 4 6 7

Therefore the solution is 2.