11-22-2011, 11:14 PM
[B]Fundamentals of Algorithms
CS502-Fall 2011
ASSIGNMENT #2
.
Fundamentals of Algorithms
CS502-Fall 2011
ASSIGNMENT #2
Deadline
Your assignment must be uploaded/submitted at or before 21stNov. 2011
Uploading instructions
Please view the assignment submission process document provided to you by
the Virtual University to upload the assignment.
Rules for Marking
It should be clear that your assignment will not get any credit if:
oThe assignment is submitted after due date.
oThe submitted assignment does not open or run.
oThe assignment is copied.
Objectives
This assignment will help you to understand the concept of recurrence relations and way
to solve then and writing asymptotic notation after analyzing and solving recurrences
.The other main focus is to learn dynamic programming applications and edit distance
problem solution using dynamic programming technique which will be ultimately
enhance your vision and logics to think critically and analytically.
Some basic information for solving assignment question 1 is given below.
Growth Rate of Function:
If some function f1(n)>f2(n) for positive values of x then the function f1(x) is said to have
greater growth rate then f2(x). For example f1(n)=n100 and f2(n)= n99 it is obvious that
f1(x) has greater growth rate ( 2100 > 299).This concept relate to complexity of algorithm
,an algorithm having greater growth rate function means the algorithm has greater
complexity here f1(x) is more complex then f2(x).
Books to read for solution
Cormen, Leiserson, Rivest, and Stein (CLRS) 2001, Introduction to Algorithms, (2nd ed.)
McGraw Hill.
Estimated Time 3.5 hours
Your concepts and logics will take actual measure of time ;however first question
should not take more than 2 hour and for question 2 you may solve in 1.5 hours It
all depends upon your sheer concentration.
Question# 1 (10)
Arrange the following in the Least to Most complexity order. Here “n “is the input size
for the some complexity function and j< k and j & k are numbers greater than 2.Every
function is separated by “comma” and note these are 20 functions to arrange.
7 2
2 4 9
11 3
n/10000, 10n6k/2, n12j/4, nlgn, nn , 1000000000, 2n , n lgn, n!, (2nn n )/ n ,
n!/ n , 2nnlogn/ n , n!/logn, 1000000, n / n,n(logn) n,
n / n, n(logn) n, kn , jn
Question# 2 (10)
Carry out the radix sort on the following five digits numbers and also develop
complexities function and then write worst case Theta Θ notation for the radix sort algorithm.
45141,16545,11478,12196,12133,21322,31422,31511,11262,27210[/B]
CS502-Fall 2011
ASSIGNMENT #2
.
Fundamentals of Algorithms
CS502-Fall 2011
ASSIGNMENT #2
Deadline
Your assignment must be uploaded/submitted at or before 21stNov. 2011
Uploading instructions
Please view the assignment submission process document provided to you by
the Virtual University to upload the assignment.
Rules for Marking
It should be clear that your assignment will not get any credit if:
oThe assignment is submitted after due date.
oThe submitted assignment does not open or run.
oThe assignment is copied.
Objectives
This assignment will help you to understand the concept of recurrence relations and way
to solve then and writing asymptotic notation after analyzing and solving recurrences
.The other main focus is to learn dynamic programming applications and edit distance
problem solution using dynamic programming technique which will be ultimately
enhance your vision and logics to think critically and analytically.
Some basic information for solving assignment question 1 is given below.
Growth Rate of Function:
If some function f1(n)>f2(n) for positive values of x then the function f1(x) is said to have
greater growth rate then f2(x). For example f1(n)=n100 and f2(n)= n99 it is obvious that
f1(x) has greater growth rate ( 2100 > 299).This concept relate to complexity of algorithm
,an algorithm having greater growth rate function means the algorithm has greater
complexity here f1(x) is more complex then f2(x).
Books to read for solution
Cormen, Leiserson, Rivest, and Stein (CLRS) 2001, Introduction to Algorithms, (2nd ed.)
McGraw Hill.
Estimated Time 3.5 hours
Your concepts and logics will take actual measure of time ;however first question
should not take more than 2 hour and for question 2 you may solve in 1.5 hours It
all depends upon your sheer concentration.
Question# 1 (10)
Arrange the following in the Least to Most complexity order. Here “n “is the input size
for the some complexity function and j< k and j & k are numbers greater than 2.Every
function is separated by “comma” and note these are 20 functions to arrange.
7 2
2 4 9
11 3
n/10000, 10n6k/2, n12j/4, nlgn, nn , 1000000000, 2n , n lgn, n!, (2nn n )/ n ,
n!/ n , 2nnlogn/ n , n!/logn, 1000000, n / n,n(logn) n,
n / n, n(logn) n, kn , jn
Question# 2 (10)
Carry out the radix sort on the following five digits numbers and also develop
complexities function and then write worst case Theta Θ notation for the radix sort algorithm.
45141,16545,11478,12196,12133,21322,31422,31511,11262,27210[/B]
0300-9520262
Get solution in 24 hour |cpmputer & internet
mileys81:[SIZE="4"][SIZE="3"]....[/SIZE][/SIZE]