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.
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>
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)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 !!
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=4^{k} or k=log n
T(n)= 4^{k}(n/4^{k})+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.
© 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