We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

# www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + 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 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?

Views: 2172

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

### Replies to This Discussion

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

Attachments:

CS702 Today Paper 9:00 AM Dated: 24-12-2016

1. Write pseudo code of assembly line scheduling dynamic programming for print station. (5marks)
2. Logically equivalence that ~C-->~(B^(B --> C)) (5 marks)
3. Time complexity of binary addition of two binary numbers. (10 Marks)
4. Pseudo Code of Brut Force algorithm closes point in 3-D and its time complexity. (10 Marks)

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
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
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

Attachments:

thanx

.