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

# CS502 Assignment No 1 Solution & Discussion Due Date: 23-04-2012

CS 502 Fundamental of Algorithms
Assignment # 01
Spring 2012
Total Marks = 10+10 = 20
Your assignment must be uploaded / submitted before or on April 23, 2012

Please view the assignment submission process document provided to you by the
Virtual University.

Rules for Marking
• 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)).

+ 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: 1471

.

+ 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

help plzzzzzzzzzz

share plez

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

Attachments:

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

Attachments:

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.

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 nn0 and mm0}.

Give corresponding definitions for Ω(g(n, m)) and Θ(g(n, m)).

Ω(g(n,m)) = { f (n,m) : there exist positive constants c, n0 , and m0 such that 0 ≤ cg(n,m) ≤ f (n,m) for all n ≥ n0 and m ≥ m0 }.

Ө(g(n,m)) ={ ƒ(n,m) : there exist positive constants c1,c2 n, and m0 such that c1g(n,m) ≤ ƒ(n.m) ≤ c2g(n,m) for all n≥ n0 and m ≥ m0 }.

Solved by.

umair sid

umair sid  gud keep it up

koi to correct solution upload kro

## Latest Activity

8 minutes ago
14 minutes ago
Tayyaba Ahmad. joined + M.Tariq Malik's group

### ENG502 Introduction to Linguistics

25 minutes ago
28 minutes ago
Tayyaba Ahmad. joined + M.Tariq Malik's group

33 minutes ago

42 minutes ago
46 minutes ago
47 minutes ago
47 minutes ago
52 minutes ago
52 minutes ago
52 minutes ago

1

2

3