Describe an efficient algorithm to find the median of a set of 106 integers; it is known that there are fewer than 100 distinct integers in the set
Solution:-
Step1:Start
Step2:Find the 100 distinct numbers among 10^6 integers.
Step3:Sort the 100 distinct numbers
Step4:Count the distinct numbers
Step5: if count is odd,middle number is the median
Step6:if count is even,add the middle two numbers then divide by 2,the result is the median Step5:End
number.
What is the formula for generating Catalan numbers?
Solution
Equation (22) is a recurrence relation.
C_(n+1) = C_n * [2(2n+1)] / (n+2)
we have the values of n in one column and the values of C_n in another, then to put this formula in Excel, on the (n+1)-th row just replace C_n and n with the appropriate cells from the previous row.
What are Catalan numbers? Give the formula.
Catalan numbers form a sequence of natural numbers that occur in variouscounting problems, often involving recursively defined objects
Formula is C(n) = 2n Cn / (n+1)
Q-Write a pseudo code Fibonacci With memorization? -- (3)
Sol
MEMOFIB(n)
1 if (n < 2)
2 then return n
3 if (F[n] is undefined)
4 then F[n] MEMOFIB(n − 1) + MEMOFIB(n − 2)
5 return F[n]
Q – Write Down the steps of Dynamic programming (5)Dynamic programming is essentially recursion without repetition. Developing a dynamic programming
algorithm generally involves two separate steps:
· Formulate problem recursively. Write down a formula for the whole problem as a simple
combination of answers to smaller sub problems.· Build solution to recurrence from bottom up. Write an algorithm that starts with base cases and works its way up to the final solution.
Dynamic programming algorithms need to store the results of intermediate sub problems. This is often but not always done with some kind of table. We will now cover a number of examples of problems in which the solution is based on dynamic programming strategy.
How we build heap
We build a max heap out of the given array of numbers A[1..n]. We repeatedly extract the maximum item from the heap. Once the max item is removed, we are left with a hole at the root.
On Sun, May 13, 2012 at 11:33 PM, zain <zain2123@gmail.com> wrote:
salaam can u send me answer of current paper cs502? and also solved mid term subjctive notes plzOn Sat, May 12, 2012 at 2:39 AM, Umair Saulat <saulat.umair@googlemail.com> wrote:
--CS502 - Fundamentals of Algorithms
Fall Spring 2012
MID TERM Paper
Dated May 11,2012
Time 1 hour
Total Marks 40
Attempt by Umair Saulat saulat.umair@gmail.com May 11, 2012 at 7.30AM,
Campus North Nazimabad Karachi
Total Question 26
MCQs 20 80% MCQs are New.
Short Question 2 x 2
Short Question 2 x 2
Short Question 2 x 3
Short Question 2 x 5
80% MCQS are New.
QNo.1 What is heap and what is heap order? (Mark2)
QNo.2 Quick sort such that sort the array in to non-increasing order? (Mark2)
QNo.3 Draw the cost table for chain multiplication problem with initial states(Mark3)
QNo.4 we can avoid unnecessary repetitions for recursive calls? (Mark3)
QNo.5 Matrix multiplication is an associative with commutative operation, explain? (Mark5)
QNo.6 Statement (Mark5)
--
Zindagi mein 2 Logo ka buhat khayal rahkoooo
Ist woh jiss ney tumhari jeet ke Liye buhat kuch hara hoo (Father)
2nd woh jiss ko tum ney har dukh me pukaara hoo (Mother)Regards,Umair Saulat
--
Please visit www.vuzs.net For Current & Old Papers, Quizzes, Assignments and study material.
To post a new message on this group, send email to vuZs@googlegroups.com
Message Posting Rules: http://vuzs.net/faq/4795-vuzs-google-groups-basic-rules-for-posting-messages.html
--
To unsubscribe from this group, send email to vuZs+unsubscribe@googlegroups.com
--
To join this group Send blank email to vuZs+subscribe@googlegroups.com
or visit
http://groups.google.com/group/vuZs/subscribe
--
--
Please visit www.vuzs.net For Current & Old Papers, Quizzes, Assignments and study material.
To post a new message on this group, send email to vuZs@googlegroups.com
Message Posting Rules: http://vuzs.net/faq/4795-vuzs-google-groups-basic-rules-for-posting-messages.html
--
To unsubscribe from this group, send email to vuZs+unsubscribe@googlegroups.com
--
To join this group Send blank email to vuZs+subscribe@googlegroups.com
or visit
http://groups.google.com/group/vuZs/subscribe
--
Zindagi mein 2 Logo ka buhat khayal rahkooooIst woh jiss ney tumhari jeet ke Liye buhat kuch hara hoo (Father)
2nd woh jiss ko tum ney har dukh me pukaara hoo (Mother)Regards,Umair Saulat
--
--
Please visit www.vuzs.net For Current & Old Papers, Quizzes, Assignments and study material.
To post a new message on this group, send email to vuZs@googlegroups.com
Message Posting Rules: http://vuzs.net/faq/4795-vuzs-google-groups-basic-rules-for-posting-messages.html
--
To unsubscribe from this group, send email to vuZs+unsubscribe@googlegroups.com
--
To join this group Send blank email to vuZs+subscribe@googlegroups.com
or visit
http://groups.google.com/group/vuZs/subscribe
--
--
Please visit www.vuzs.net For Current & Old Papers, Quizzes, Assignments and study material.
To post a new message on this group, send email to vuZs@googlegroups.com
Message Posting Rules: http://vuzs.net/faq/4795-vuzs-google-groups-basic-rules-for-posting-messages.html
--
To unsubscribe from this group, send email to vuZs+unsubscribe@googlegroups.com
--
To join this group Send blank email to vuZs+subscribe@googlegroups.com
or visit
http://groups.google.com/group/vuZs/subscribe
No comments:
Post a Comment