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


Looking For Something at vustudents.ning.com? Click Here to Search

Assignment No. 01
Semester: Spring 2016
CS502: Fundamentals of Algorithms
Total Marks: 20

Due Date:19/05/2016

Instructions
Please read the following instructions carefully before submitting assignment:

It should be clear that your assignment will not get any credit (zero marks) if:
o The assignment is submitted after due date.
o The submitted assignment is other than .doc file.
o The submitted assignment does NOT open or file is corrupted.
o The assignment is copied (from other student or ditto copy from any other source).

Objective

The objective of this assignment is to:

 Learn and practice Algorithm running time analysis
 Solve recurrences using iteration method

Submission

You are required to submit your solution through LMS as MS Word document.

For any query about the assignment, contact at CS502@vu.edu.pk
GOOD LUCK

Question 1:
Analyze the running time complexity of the following piece of code. Show your working step by step.

SumOddEven(A,n) //A is array and n is size of array
{
int count, sum;
for(int i = 1; i<=n; i++) { sum_even=0; sum_odd=0; for(int j = i; j<=n; j++) { if (A[j] Mod 2 == 0) //check if number is even sum_even=sum_even+A[j] //Sum even numbers else sum_odd=sum_odd+A[j] //Sum odd numbers } cout/p>

+ Click Here To Join also Our facebook study Group.

..How to Join Subject Study Groups & Get Helping Material?..


See Your Saved Posts Timeline

Views: 12636

.

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

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

Attachments:

Replies to This Discussion

Running time complexity means ?? like we are to comment how could we shorten the runing time of this pesudo code or we got to right the new algo with better running time iam blunt !!

Guys please start discussion here!!!!

Khadija sis ap he koe idea to do

or aj lgta hy kise ko nae ateee

but........ aj seniors kahan gaeb hen

If n is assumed to be a power 4 (4­­k=n)

T(n)=4T(n/4)+1 }
       =16T(n/16)+1+1
       =64T(n/256)+1+1+1
 if n is  a power of 4 then let n=4k or k=log n

T(n)= 4k(n/4k)+kn
       =4(log n) T(n/ 4(log N)) + (log n) n
       =4(log n) T(n/n) + (log n) n
       =nT(1) + n log n
       =n + n log n

Khadija sis ap he koe idea to do

or aj lgta hy kise ko nae ateee

but........ aj seniors kahan gaeb hen

bor koe idea to btao yaar aj extended dayhy 

Q No.1 will solve in this way????

PARTITION( array A, int p, int r)
1 x ← A[p]
2 q ← p
3 for s ← p + 1 to r
4 do if (A[s] < x)
5 then q ← q + 1
6 swap A[q] with A[s]
7 swap A[p] with A[q]
8 return q

Je janab a gae last date bhe ub zra kholen book.....

 Book......

Dear Admin sb ap bhe.........

please koe idea to bta den

Analysis of Heapsort

Heapsort calls BuildHeap once. This takes Θ(n). Heapsort then extracts roughly n maximum elements
from the heap. Each extract requires a constant amount of work (swap) and O(log n) heapify. Heapsort
is thus O(n log n).

Is HeapSort Θ(n log n)? The answer is yes. In fact, later we will show that comparison based sorting
algorithms can not run faster than Ω(n log n). Heapsort is such an algorithm and so is Mergesort that we
saw ealier.

idea nhin ha es liye asking to discuss

RSS

Latest Activity

+ M.Tariq Malik replied to + M.Tariq Malik's discussion MCM514 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material in the group MCM514 Feature & Column Writing
6 seconds ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion MCM611 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material in the group MCM611 Seminar on Contemporary Issues in Media
18 seconds ago
+ M.Tariq Malik's 50 discussions were featured
22 seconds ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion MCM610 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material in the group MCM610 Mass Communication Law & Ethics
24 seconds ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion MCM604 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material in the group MCM604 International Communication
29 seconds ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion MCM531 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material in the group MCM531 Community Journalism
33 seconds ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion MCM601 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material in the group MCM601 Media Management
35 seconds ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion MCM532 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material in the group MCM532 Magazine Journalism
38 seconds ago

Today Top Members 

© 2019   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service