CS 502 Fundamental of Algorithms
Assignment # 01
Spring 2012
Total Marks = 10+10 = 20
Deadline
Your assignment must be uploaded / submitted before or on April 23, 2012
Upload Instructions
Please view the assignment submission process document provided to you by the
Virtual University.
Rules for Marking
Please note that your assignment will not be graded if:
• It is submitted after due date
• The file you uploaded does not open
• The file you uploaded is copied from someone else or from internet
• It is in some format other than .doc
Note: Material that is an exact copy from handouts or internet would be graded
Zero marks. Your solution should consist of the material found through different sources and written in your own words.
Assignment Statements:
Question 1:
Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n - 1 elements of A. Write pseudo code for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n - 1 element, rather than for all n elements? Give the best-case and worst-case running times of selection sort in Θ-notation.
Question 2:
We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n, m), we denote by O(g(n, m)) the set of functions
O(g(n, m)) = {f(n, m): there exist positive constants c, n0, and m0 such that 0 ≤ f(n, m) ≤ cg(n, m) for all n ≥ n0 and m ≥ m0}.
Give corresponding definitions for Ω(g(n, m)) and Θ(g(n, m)).
Tags:
Please Discuss here about this assignment.Thanks
2nd question solve karny k qabil hai kia? ya ye mazaq kia hai sir ne
yar mujy tu ye solution mila ha kahin se bt i dont know that it is right or wrong.......
i hav shared here so take idea and try to solve it because us book ki tu smaj hi nahi aa rahi yar.............ab bhi ni pta kesy kerna ha..hahahahahahahaha
Solution file is not opening
second question to thek bt first question ka pta nae
solution of cs502 assignment no1 # just and 70% idea.
good luck
CS502 FUNDAMENTAL OF ALGORITHMS
Umair sid
Question 1:
Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n - 1 elements of A. Write pseudo code for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n - 1 element, rather than for all n elements? Give the best-case and worst-case running times of selection sort in Θ-notation.
Answer of no#1:
The Selection-sort (A)
For i ← 1 to length [A]
Do min-value ← A [i]
Min-index = i
For j = i +1to length [A]
Do if A[j] ≤ min-value
Min-value = A [j]
Min-index = j
A[i] ←→ A [min-index]
In this session the worst –case running time of SELECTION-Sort is Ө (n2)
Question 2:
We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n, m), we denote by O(g(n, m)) the set of functions
O(g(n, m)) = {f(n, m): there exist positive constants c, n0, and m0 such that 0 ≤ f(n, m) ≤ cg(n, m) for all n ≥ n_{0} and m ≥ m_{0}}.
Give corresponding definitions for Ω(g(n, m)) and Θ(g(n, m)).
Answer of no#2:
Ω(g(n,m)) = { f (n,m) : there exist positive constants c, n_{0} , and m_{0} such that 0 ≤ cg(n,m) ≤ f (n,m) for all n ≥ n_{0} and m ≥ m_{0} }.
Ө(g(n,m)) ={ ƒ(n,m) : there exist positive constants c1,c2 n, and m_{0} such that c1g(n,m) ≤ ƒ(n.m) ≤ c2g(n,m) for all n≥ n_{0} and m ≥ m_{0} }.
Solved by.
umair sid
umair sid gud keep it up
How to Get This Badge at Your Profile DP
------------------------------------
Management: Admins ::: Moderators
© 2021 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. 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