 www.vustudents.ning.com

We non-commercial site working hard since 2009 to facilitate learning Read More. We can't keep up without your support. Donate.

I though of posting this so that people can easily find matching solution if any questions repeat in the future.

These are the VU solutions from VU teachers.

CS 502 Fundamental of Algorithms

Solution of Assignment # 01

Fall 2012

Total Marks = 20

Assignment Statements:

Question 1:

Consider the searching problem:

• Input: A sequence of n numbers A = ­a1, a2, . . . , an­ and a value v.

• Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.

Observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. Binary search is an algorithm that repeats this procedure, halving the size of the remaining portion of the sequence each time. Write Pseudo code, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is Θ (lg n).

Solution:

Procedure BINARY-SEARCH takes a sorted array A, a value v, and a range [low . . high] of the array, in which we search for the value v. The procedure compares v to the array entry at the midpoint of the range and decides to eliminate half the range from further consideration. We give both iterative and recursive versions, each of which returns either an index i such that A[i ] = v, or NIL if no entry of A[low . . high] contains the value v. The initial call to either version should have the parameters A, v, 1, n.

ITERATIVE-BINARY-SEARCH(A, v, low, high)

while low high

do mid (low+high)/2

if v = A[mid]

then return mid

if v > A[mid]

then low mid +1

else high mid 1

return NIL

RECURSIVE-BINARY-SEARCH(A, v, low, high)

if low > high

then return NIL

mid (low+high)/2

if v = A[mid]

then return mid

if v > A[mid]

then return RECURSIVE-BINARY-SEARCH(A, v, mid +1, high)

else return RECURSIVE-BINARY-SEARCH(A, v, low, mid 1)

Both procedures terminate the search unsuccessfully when the range is empty (i.e., low > high) and terminate it successfully if the value v has been found. Based on the comparison of v to the middle element in the searched range, the search continues with the range halved. The recurrence for these procedures is therefore

T (n) = T (n/2) + Θ (1), whose solution is T (n) = Θ (lg n).

Question 2:

Describe a Θ (n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.

Solution:

The following algorithm solves the problem:

1. 1.    Sort the elements in S.
2. 2.    Form the set Sˊ = {z : z = x − y for some y S}.
3. 3.    Sort the elements in Sˊ.
4. 4.    If any value in S appears more than once, remove all but     one instance. Do the same for Sˊ.
5. 5.    Merge the two sorted sets S and Sˊ.
6. 6.    There exist two elements in S whose sum is exactly x if and    only if the same value appears in consecutive positions in    the merged output.

To justify the claim in step 4, first observe that if any value appears twice in the merged output, it must appear in consecutive positions. Thus, we can restate the condition in step 5 as there exist two elements in S whose sum is exactly x if and only if the same value appears twice in the merged output.

Suppose that some value w appears twice. Then w appeared once in S and once in Sˊ. Because w appeared in Sˊ, there exists some y S such that w = x − y, or x = w + y. Since w S, the elements w and y are in S and sum to x.

Conversely, suppose that there are values w, y S such that w + y = x. Then, since x − y = w, the value w appears in Sˊ. Thus, w is in both S and Sˊ, and so it will appear twice in the merged output.

Steps 1 and 3 require O(n lg n) steps. Steps 2, 4, 5, and 6 require O(n) steps. Thus the overall running time is O(n lg n).

Best of Luck:

Views: 447

Attachments:

Replies to This Discussion

CS 502 Fundamental of Algorithms

Assignment # 02

Fall 2012

Total Marks = 20

Assignment Statements:

Question 1:

Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is Ω (lg n).

(Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a path from the root down to a leaf.)

Solution:

If you put a value at the root that is less than every value in the left and right sub trees, then MAX-HEAPIFY will be called recursively until a leaf is reached. To make the recursive calls traverse the longest path to a leaf, choose values that make MAX-HEAPIFY always recourse on the left child. It follows the left branch when the left child is the right child, so putting 0 at the root and 1 at all the other nodes, for example, will accomplish that. With such values, MAX-HEAPIFY will be called h times (where h is the heap height, which is the number of edges in the longest path from the root to a leaf), so its running time will be Θ (h) (since each call does Θ (1) work), which is Θ (lg n). Since we have a case in which MAX-HEAPIFY.s running time is Θ (lg n), its worst-case running time is Ω (lg n).

Question 2:

Suppose that the splits at every level of quicksort are in the proportion 1 - α to α, where 0 /b> α which is ≤ 1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately - lg n/ lg α and the maximum depth is approximately -lg n/ lg(1 - α). (Don't worry about integer round-off.)

Solution:

The minimum depth follows a path that always takes the smaller part of the partition i.e. that multiplies the number of elements by α. One iteration reduces the number of elements from n to α n, and i iterations reduces the number of elements to α in. At leaf, there is just one remaining element, and so at a minimum depth leaf of depth m, we have α m n = 1. Thus, α m = 1/n. Taking logs, we get m lg α = lg n, or m = lg n /  lg α.

Similarly, maximum depth corresponds to always taking the larger part of the partition, i.e., keeping a fraction 1 α of the elements each time. The maximum depth M is reached when there is one element left, that is, when (1 α) M n = 1.

Thus, M = lg n/ lg (1 α).

All these equations are approximate because we are ignoring floors and ceilings.

Attachments:

CS 502 Fundamental of Algorithms

Assignment # 03

Fall 2012

Total Marks = 20

Assignment Statements:

Question 1:

After reviewing the activity scheduling with greedy approach, suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is greedy algorithm and prove that it yields an optimal solution.

Solution:

The proposed approach-selecting the last activity to start that is compatible with all previously selected activities- is really the greedy algorithm but starting from the end rather than the beginning.

Another way to look at it is as follows. We are given a set S = {a1, a2,  . . . , an} of activities, where ai = [si , fi ), and we propose to find an optimal solution by selecting the last activity to start that is compatible with all previously selected activities. Instead, let us create a set S = {a1ˊ, a2ˊ, …, anˊ}, where aiˊ= [ fi , si ). That is, aiˊ is ai in reverse. Clearly, a subset of {ai1 , ai2 , . . . , aik} S is mutually compatible if and only if the corresponding subset { ai1ˊ, ai2ˊ, …, aikˊ} Sˊ is also mutually compatible. Thus, an optimal solution for S maps directly to an optimal solution for Sˊ and vice versa.

The proposed approach of selecting the last activity to start that is compatible with all previously selected activities, when run on S, gives the same answer as the greedy algorithm from the text-selecting the first activity to finish that is compatible with all previously selected activities-when run on S. The solution that the proposed approach finds for S corresponds to the solution that the text’s greedy algorithm finds for Sˊ, and so it is optimal.

Question 2:

Mr. Mohsin drives a car from Lahore to Rahim Yar Khan along National Highway, His car’s gas tank, when full, holds enough gas travel n miles, and his map gives the distance between gas station on his route. Mohsin wishes to make as few gas stops as possible along the way. Give an efficient method by which Mohsin can determine at which gas stations he should stop , and prove that your strategy yields an optimal solution.

Solution:

The optimal strategy is the obvious greedy one. Starting will a full tank of gas, Mr Mohsin should go to the farthest gas station he can get to within n miles of Newark. Fill up there. Then go to the farthest gas station he can get to within n miles of where he filled up, and fill up there, and so on.

Looked at another way, at each gas station, Mr Mohsin should check whether he can make it to the next gas station without stopping at this one. If he can, skip this one. If he cannot, then fill up. Mr Mohsin does not need to know how much gas he has or how far the next station is to implement this approach, since at each fill up; he can determine which is the next station at which he will need to stop.

This problem has optimal substructure. Suppose there are m possible gas stations. Consider an optimal solution with s stations and whose first stop is at the kth gas station. Then the rest of the optimal solution must be an optimal solution to the sub problem of the remaining m k stations. Otherwise, if there were a better solution to the sub problem, i.e., one with fewer than s 1 stops, we could use it to come up with a solution with fewer than s stops for the full problem, contradicting our supposition of optimality.

This problem also has the greedy-choice property. Suppose there are k gas stations beyond the start that are within n miles of the start. The greedy solution chooses the kth station as its first stop. No station beyond the kth works as a first stop, since Mr Mohsin runs out of gas first. If a solution chooses a station j < k as its first stop, then Mr Mohsin could choose the kth station instead, having at least as much gas when he leaves the kth station as if he had chosen the jth station.

Therefore, he would get at least as far without filling up again if he had chosen the kth station.

If there are m gas stations on the map, Mohsin needs to inspect each one just once. The running time is O(m).

Attachments:

Solution of Question 1:

Part a:

1. Suppose (u, v) is a back edge or a forward edge in a BFS of an undirected graph. Then one of u and v, say u, is a proper ancestor of the other (v) in the breadth-first tree. Since we explore all edges of u before exploring any edges of any of u’s descendants, we must explore the edge (u, v) at the time we explore u. But then (u, v) must be a tree edge.

1. In BFS, an edge (u, v) is a tree edge when we set π[v] ← u. But we only do so when we set d[v] ← d[u] + 1. Since neither d[u] nor d[v] ever changes thereafter, we have d[v] = d[u] + 1 when BFS completes.

1. Consider a cross edge (u, v) where, without loss of generality, u is visited before v. At the time we visit u, vertex v must already be on the queue, for otherwise (u, v) would be a tree edge. Because v is on the queue, we have d[v] ≤ d[u] + 1 by Lemma 22.3 of the recommended book. By Corollary 22.4 of the recommended book, we have d[v] ≥ d[u]. Thus, either d[v] = d[u] or d[v] = d[u] + 1.

Part b:

1. Suppose (u, v) is a forward edge. Then we would have explored it while visiting u, and it would have been a tree edge.

1. Same as for undirected graphs.

1. For any edge (u, v), whether or not it is a cross edge, we cannot have d[v] > d[u] + 1, since we visit v at the latest when we explore edge (u, v). Thus, d[v] ≤ d[u] + 1.

1. Clearly, d[v] ≥ 0 for all vertices v. For a back edge (u, v), v is an ancestor of u in the breadth-first tree, which means that d[v] ≤ d[u]. (Note that since self-loops are considered to be back edges, we could have u = v.)

Question 2:                                                                                                                               Marks 5 Question 3:                                                                                                                               Marks 5 Attachments:

Note: (This is Featured Discussion)

For Important Helping Material related to this subject (Solved MCQs, Short Notes, Solved past Papers, E-Books, FAQ,Short Questions Answers & more). You must view all the featured Discussion in this subject group.

For how you can view all the Featured discussions click on the Back to Subject Name Discussions link below the title of this Discussion & then under featured Discussion corner click on the view all link.

thanks

thanx alot broo ........it would help us alot