We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>
+ Link For Assignments, GDBs & Online Quizzes Solution |
+ Link For Past Papers, Solved MCQs, Short Notes & More |
Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion
How to Add New Discussion in Study Group ? Step By Step Guide Click Here.
Please share your Midterm papers and share past papers. Thanks.
Tags:
+ How to Follow the New Added Discussions at Your Mail Address?
+ How to Join Subject Study Groups & Get Helping Material? + How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators? + VU Students Reserves The Right to Delete Your Profile, If?.
+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)
+ Click Here to Search (Looking For something at vustudents.ning.com?) + Click Here To Join (Our facebook study Group)today paper 12 pm 19-12-16
4 question.
1. solve recursion by induction. T(n)= {smthng
2.T(n/2)+n smthng} prove karna tha for nlgn.
2. chain matrix ka tha question to solve A1, A2, A3 question given tha
3. Merge sort algorithm
4. Show that sum of odd integers m = m2(square). by insuction
Bs yahe tha. All the best. Do pray fr me
my paper
q 1. for n belongs to Z and n > 1 then n can be written as product of primes.
q 2 . write pseudo code for merge sort algorithm .
q 3. write pseudo code for o-1 knapsack brute force algorithm.
q 4 . tn - 4tn-1 = (n +3 ) 5n give its general solution
Mahrosh thanks for sharing
dsvsd
CS702 Today Paper 9:00 AM Dated: 24-12-2016
Tariq Mehmood thanks for sharing
Time complexity of binary addition of two binary numbers???????????????
Plz have u solution of this question the send me
thanx
My Exam
Assembly Line Scheduling Algorithm for Dynamic Programming (10 marks)
Solve recursion relation (10 marks)
Pseudo code for o-1 knapsack brute force algorithm (5 marks)
Solve recursion relation (5 marks)
1. If n belong to Z and greater than 1 then it is the product of two primes. (samjkh se bahir hai k prove krna tha)
2. Brute force algo for closest points and its complexity.
3. chain matrix dynamic approach (numerical tha).
4. Mathematical induction example prove krna the.
CS 702 – Mid Term 2015
1. Prove gcd(an,bn)=n.gcd(a,b)
2. Write down pseudo code of longest common subsequence?
3. Write down prim’s algorithm?
4. Write down Shortest Path (dag) algorithm?
5. Why we use dynamic programming? Give limitations.....5 marks
Dynamic programming is a completely other beast. It is applicable to problems with the property that
• it can be partitioned into subproblems (probably in more than one way),
• those subproblems can be solved independently,
• (optimal) solutions of those subproblems can be combined to (optimal) solutions of the original problem and
• subproblems have the same property (or are trivial).
6. Pseudo code for Johnson’s algorithm....5 marks
7. How to print path in BFS algorithm...5 marks.
8. Extend Shortest Path algorithm.5 marks.
9. Pseudo code of n line assembly or Print station n line assembly
There are two assembly lines each with n stations
• The jth station on line i is denoted by Si, j
• The assembly time at that station is ai,j.
• An auto enters factory, goes into line i taking time ei
• After going through the jth station on a line i, the auto goes on to the (j+1)st station on
either line
• There is no transfer cost if it stays on the same line
• It takes time ti,j to transfer to other line after station Si,j
• After exiting the nth station on a line, it takes time xi for the completed auto to exit the
factory.
• Problem is to determine which stations to choose from lines 1 and 2 to minimize total
time through the factory.
10. From asymptotic notation prove theta function.
11. Asymptotic Notations Properties
• Categorize algorithms based on asymptotic growth rate e.g. linear, quadratic,
polynomial, exponential
• Ignore small constant and small inputs
• Estimate upper bound and lower bound on growth rate of time complexity function
• Describe running time of algorithm as n grows to .
• Describes behavior of function within the limit.
Limitations
• not always useful for analysis on fixed-size inputs.
• All results are for sufficiently large inputs.
12. Algorithm of chain matrix multiplication.
Given a sequence of n matrices A1, A2, ... An, and their dimensions p0, p1, p2, ..., pn, where where i = 1, 2, ..., n, matrix Ai has dimension pi − 1 × pi, determine the order of multiplication that minimizes the the number of scalar multiplications.
Note:
1:write algo of 0-1 knapsack problem by brute force.
Knapsack-BF (n, V, W, C)
Compute all subsets, s, of S = {1, 2, 3, 4}
For all s Î S
weight = Compute sum of weights of these items
if weight > C, not feasible
new solution = Compute sum of values of these items
solution = solution È {new solution}
Return maximum of solution
2:write algo knapsack problem by dynammic programming.
Dynamic-0-1-knapsack (v, w, n, W)
FOR w = 0 TO W
DO c[0, w] = 0
FOR i=1 to n
DO c[i, 0] = 0
FOR w=1 TO W
DO IFf wi ≤ w
THEN IF vi + c[i-1, w-wi]
THEN c[i, w] = vi + c[i-1, w-wi]
ELSE c[i, w] = c[i-1, w]
ELSE
c[i, w] = c[i-1, w]
3:algorithm of 2-dimension points.
The distance between two points is calculated like this:
D=((x2 - x1)^2 + (y2 - y1)^2)^(1/2)
4:write algoritm 2-line assembly language.
The closest pair of points can be computed in O(n2) time by performing a brute-force search. To do that, one could compute the distances between all the n(n − 1) / 2 pairs of points, then pick the pair with the smallest distance, as illustrated below.
minDist = infinity
for i = 1 to length(P) - 1
for j = i + 1 to length(P)
let p = P[i], q = P[j]
if dist(p, q) < minDist:
minDist = dist(p, q)
closestPair = (p, q)
return closestPair
5:algorithm n-line assembly language
n-Line Assembly: Dynamic Algorithm
FASTEST-WAY(a, t, e, x, n, m)
1 for i ← 1 to n
2 ƒ[i,1] ←e[i] + a[i,1]
3 for j ← 2 to m
4 for i ← 1 to n
5 ƒ[i, j] ¬ f[1, j-1] + t[1, j-1] + a[i, j]
126
6 L[1, j] = 1
7 for k ¬ 2 to n
8 if f[i,j] > f[k, j-1] + t[2, j-1] + a[i, j]
9 then f[i,j] ¬ f[k, j-1] + t[2, j-1] + a[i, j]
L[i, j] = k
10 end if
11 ƒ* ¬ ƒ[1, m] + x[1]
12 l* = 1
13 for k ¬ 2 to n
14 if f* > f[k, m] + x[k]
15 then ƒ* ¬ ƒ[k, m] + x[k]
16 l* = k
1. 1/2n^2+3n= theta(n^2)
3. Div and con algorithm steps and complexity
Knapsack
if wi <= w // item i can be part of the solution
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
V[i, j] = max(V[i-1, j], vi + V[i-1, j – wi]);
Development of Dynamic Algorithms
1. Characterize the structure of an optimal solution
2. Recursively define the value of an optimal solution
3. Compute the value of an optimal solution in a bottom-up fashion
4. Construct an optimal solution from computed information
Note: Steps 1-3 form the basis of a dynamic programming solution to a problem. Step
4 can be omitted only if the value of an optimal solution is required.
n-Line Assembly: Dynamic Algorithm
FASTEST-WAY(a, t, e, x, n, m)
1 for i ← 1 to n
2 ƒ[i,1] ←e[i] + a[i,1]
3 for j ← 2 to m
4 for i ← 1 to n
5 ƒ[i, j] ¬ f[1, j-1] + t[1, j-1] + a[i, j]
126
6 L[1, j] = 1
7 for k ¬ 2 to n
8 if f[i,j] > f[k, j-1] + t[2, j-1] + a[i, j]
9 then f[i,j] ¬ f[k, j-1] + t[2, j-1] + a[i, j]
L[i, j] = k
10 end if
11 ƒ* ¬ ƒ[1, m] + x[1]
12 l* = 1
13 for k ¬ 2 to n
14 if f* > f[k, m] + x[k]
15 then ƒ* ¬ ƒ[k, m] + x[k]
16 l* = k
Assembly-Line Scheduling Problem
• There are two assembly lines each with n stations
• The jth station on line i is denoted by Si, j
• The assembly time at that station is ai,j.
• An auto enters factory, goes into line i taking time ei
• After going through the jth station on a line i, the auto goes on to the (j+1)st station on
either line
• There is no transfer cost if it stays on the same line
• It takes time ti,j to transfer to other line after station Si,j
• After exiting the nth station on a line, it takes time xi for the completed auto to exit the
factory.
• Problem is to determine which stations to choose from lines 1 and 2 to minimize total
time through the factory.
2-Line Assembly Scheduling Problem
• There are two assembly lines each with n stations
• The jth station on line i is denoted by Si, j
• The assembly time at that station is ai,j.
• An auto enters factory, goes into line i taking time ei
• After going through the jth station on a line i, the auto goes on to the (j+1)st station on
either line
• There is no transfer cost if it stays on the same line
• It takes time ti,j to transfer to other line after station Si,j
• After exiting the nth station on a line, it takes time xi for the completed auto to exit the
factory.
• Problem is to determine which stations to choose from lines 1 and 2 to minimize total
time through the factory.
Word File 2003
thanx
© 2020 Created by + M.Tariq Malik. Powered by
Promote Us | Report an Issue | Privacy Policy | Terms of Service
VU Students reserves the right to delete profile, which does not show any Activity at site nor has not activity more than 01 month.
We are user-generated contents site. All product, videos, pictures & others contents on vustudents.ning.com don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. 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 or Contact us at contact Page 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