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:
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:
Tags:
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.
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 = {a_{1}, a_{2}, . . . , a_{n}} of activities, where a_{i} = [s_{i} , f_{i} ), 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 = {a_{1}ˊ, a_{2}ˊ, …, a_{n}ˊ}, where a_{i}ˊ= [ f_{i} , s_{i} ). That is, a_{i}ˊ is a_{i} in reverse. Clearly, a subset of {a_{i}_{1} , a_{i}_{2} , . . . , a_{ik}} ⊆ S is mutually compatible if and only if the corresponding subset { a_{i1}ˊ, a_{i2}ˊ, …, a_{ik}ˊ} ⊆ 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).
Solution of Question 1:
Part a:
Part b:
Question 2: Marks 5
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
© 2022 Created by + M.Tariq Malik. Powered by
Promote Us | Report an Issue | Privacy Policy | Terms of Service
We are user-generated contents & non-commercial site since 2009. All product, videos, pictures & others contents on site don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. All Contents on site are for personal & non-commercial use.We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Awards Badges List | Moderators Group
All Members | Featured Members | Top Reputation Members | Angels Members | Intellectual Members | Criteria for Selection
Become a Team Member | Safety Guidelines for New | Site FAQ & Rules | Safety Matters | Online Safety | Rules For Blog Post