Please share your current paper here for help each other.
Stay blessed and Best of Luck for exam.
Remember me in your prayers.
Best Regards,
sana
Tags:
QNo.1 What is heap and what is heap order? (Mark2)
Answer:-
The heap is the section of computer memory where all the variables created or initialized at runtime are stored. The heap order property: in a
(min) heap, for every node X, the key in the parent is smaller than or equal to the key in X.
Ref: Handouts Page no. 40
QNo.2 Quick sort such that sort the array in to non-increasing order? (Mark2)
Answer:-
Quick sorting, an array A[1..n] of n numbers We are to reorder these elements into increasing (or decreasing) order. More generally, A is an array of objects and we sort them based on one of the attributes - the key value. The key value need not be a number. It can be any object from a totally ordered domain. Totally ordered domain means that for any two elements of the domain, x and y, either x < y, x = y or x > y.
Ref: Handouts Page no. 40
QNo.3 Draw the cost table for chain multiplication problem with initial states(Mark3)
Answer:-
(A1)(A2A3A4 . . .An)
or (A1A2)(A3A4 . . .An)
or (A1A2A3)(A4 . . .An)
. . . . . .
or (A1A2A3A4 . . .An−1)(An)
Ref: Handouts Page no. 90
QNo.4 we can avoid unnecessary repetitions for recursive calls? (Mark3)
Answer:-
We can avoid these unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later. This process is called memorization
Ref: Handouts Page no. 49
Worst case for edit distance algorithm? What is the simple change that can change the worst case time ? 5 marks
Answer:-
Analysis of DP edit distance
There are entries in the matrix. Each entry E(i,j) takes time to compute. The total running is Recursion clearly leads to the same repetitive call pattern that we saw in Fibonnaci sequence. To avoid this, we will use the DP approach. We will build the solutionb bottom-up. We will use the base case E(0,j) to fill first row and the base case E(I,0) to fill first column. We will fill the remaining E matrix row by row.
Ref: Handouts Page no. 14
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.
Ref: Handouts Page no. 34
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.
Ref: Handouts Page no. 85
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)
Ref: Handouts Page no. 85
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]
Ref: Handouts Page no. 12, 74
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:
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.
Ref: Handouts Page no. 74 – 77
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.
Ref: Handouts Page no. 41
Write Pseudo code for KNAPSACK algorithm? 5 marks
Solution:
KNAPSACK (n, W)
1 for w=0,W
2 do V[0,w]ß0
3 for i=0,n
4 do V[i,0]ß0
5 for w=0,W
6 do if(wi w& +V[i-1,w- ]>V[i-1,w])
7 then V[I,w]ß +V[i-1,w]
8 else V[i,w]ßV[i-1,w]
The time complexity is clearly O(n,W), it must be cautioned that as n and W get large, both time and space complexity become significant.
Ref: Handouts Page no. 96
Spelling correction in edit distance? 3 marks
A better way to display this editing process is to place the words above the other:
S D I M D M
M A - T H S
A - R T - S
THE FIRST WORD HAS AGAP FOR EVERY INSERTION (1)AND THE SECOND WORD HAS A GAP FOR EVERY DELETION (D). MATHES (M) DO NOT COUNT. THE EDIT TRANSCRIPT IS DEFINED AS A STRING OVER THE ALPHABETM,S,I,d THAT DESCRIBES A TRANSFORMATION OF ONE STRING INTO OTHER. FOR EXAMPLE
S D I M D M
1+1+1+0+1+0+=4
Ref: Handouts Page no. 77
Differentiate b/w Bubble sort, insertion sort and selection sort? 3 marks
SOLUTION:
Bubble sort: scan the array. Whenever two consecutive items are found that are out of order, swap them. Repeat until all consecutive items are in order.
Insertion sort: assume that A[1…i-1] have already been sorted. Insert A[i] into its proper position in this sub array. Create this position by shifting all larger elements to the right.
Selection sort:
Assume that A[1..i-1] contain the i-1 smallest elements in sorted order. Find the smallest in A[i….n] swap it with A[i].
Ref: Handouts Page no. 54
Write down the steps of dynamic programming strategy. (2 marks)
Solution:
Developing a dynamic programming algorithm generally involves two separate steps:
1_formulate problem recursively.
Write down a formula for the whole problem as a simple combination of answers to smaller sub problems.
2_ Build solution to recurrence from bottom up:
Ref: Handouts Page no. 75
Solve the recursion problem. (5marks.)
Solution:
Recursion clearly leads to the same repetitive call pattern that we saw in Fibonnaci sequence. To avoid this, we will use the DP approach. We will build the solutionb bottom-up. We will use the base case E(0,j) to fill first row and the base case E(I,0) to fill first column. We will fill the remaining E matrix row by row.
If we trace through the recursive calls to MemoFib, we find that array F[] gets filled from bottom up…i.e., first F[2], then F[3], and so on, upto F[n]. we can replace recursion with a simple for-loop that just fills up the array F[] in that order.
• We are given an array of n elements of x1 , x2 ,x3 , ,,,,xn,
suggest best sorting algorithm of order On. (5 marks).
Solution:
The main shortcoming of counting sort is that it is useful for small integers, i.e., 1…k where k is small. If this were a million more, the size of the rank array would also be a million. Radix sort provides a nice work around this limitation by sorting numbers one digit at a time.
what is the answer of this question
Suppose we want to multiply of series of matrices. What is the technique called and which one is batter approach rather then straight forward multiplication?
given an unorder list of n numbers x1,x2,x3,........xn and all elemnts are common if there are at least n/5 copies.give a o(nlogn) algorithm
: 5 marks ka qstn tha
: 2. Draw max heap 50,31,45,30,2,7,40,12,28,1 ..marks(5)
3.construct an optimal solution for 0/1 knapsack
4. define with algorithm bubble sort,insertion sort and selection sort
5.how can we make it possible for an array of n elements that every elemnt has equal probability of 1/n to select uing pivot elemnets
6.Plagrism detection with algorithm
mcqs buht mushkil that theory based nhi thay best n worst case algorithm ki timing ko prove krnay walay mcqs thay.koi b past papers mein say nhi tha
CS502 (Fundamental Of Algorithm)
By Safeena Ali
Date 16-05-2012
Q Due to left complete nature of binary tree, the heap can be stored in
• Arrays
• Structures
• Link Lis
• Stack
Q For Chain Matrix Multiplication we can not use divide and conquer approach
because,
We do not know the optimum k
We use divide and conquer for sorting only
We can easily perform it in linear time
Size of data is not given
Q word Algorithm comes from the name of the muslim author
Abu Ja’far Mohammad ibn Musa al-Khowarizmi.
Uzbikistan
Khawarizmi
India
Q What is the total time to heapify?
• O(log n)
• O(n log n)
• O(n2 logn)
• O(log2n)
Q In which order we can sort?
Select correct option:
increasing order only
decreasing order only
increasing order or decreasing order
both at the same time
Q= A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:
heap
binary tree
binary search tree
array
Q= How many elements do we eliminate in each time for the Analysis of Selection
algorithm?
n / 2 elements
(n / 2) + n elements
n / 4 elements
2 n elements
Q= We do sorting to,
keep elements in random positions
keep the algorithm run in linear order
keep the algorithm run in (log n) order
keep elements in increasing or decreasing order
Q= Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
Select correct option:
left-complete
right-complete
tree nodes
tree leaves
Q= Divide-and-conquer as breaking the problem into a small number of
Select correct option:
pivot
Sieve
smaller sub problems
Selection
Q= For the sieve technique we solve the problem,
Select correct option:
recursively
mathematically
precisely
accurately
Q= In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
Select correct option:
T(n)
T(n / 2)
log n
n / 2 + n / 4
Q= Random access machine or RAM is a/an
Q= A symptotic notation is used to calculate
Q= If an algorithm has a complexity of 5n + log_{2} ( log_{2} n ) + 10 for some model of computation (some set of assumptions) and some complexity measures (such as number of comparison operations) we could say that it has complexity
Q= Matrix – Chain – Order is __________ than the exponential time method of enumerating all possible parenthesizations and checking each one
Q= find maximum and minimum heap of height h . Mark 2
Q= a1,a2 a3 in ki values di hoi thi un ka combination banana tha mark 3
Q= knaspack 0/1 problem by using dynamic mark 5
Q= write running time of edit distances Algorithm mark 3
Q=average case quick sort ka sawal tha 2 mark ka
Q= ak table tha jis ko fill krna tha 1 iteration k bad as main kaya changing hon gi
Safina aap ka tu easy thaa paper
CS502 Midterm Examz All Current papers in one thread Spring May 2012
CS502
Current paper 20 May 2012
Note: 30% MCQS were from the past papers and remaining were totally new. Formula based MCQs were also given.
The subjective questions are given below:
Q21. Consider the case of 3 matrices. A1 is 5X4, A2 is 4 X 6 and A3 is 6 X 2.If the multiplication can be carried out this way (A1 (A2A3)) then find out the cast.
Q.22.What is idea behind in calculating sort; to sort the elements without comparisons in linear time?
Q23. How edit distance is used in spelling correction?
Q.24. Modify QUICKSORT algorithm that it sorts array into non-increasing order.
Q.25. In general how can we use the table by the dynamic programming algorithm to tell whether there is more than one optimal subset for the Knapsack problem instance.
Q.25. Carry out radix sort on the following 4-alphabet words in order to sort them in ascending order
Algo Word Xeon Zest Neon Rime Fine Dear Cast Ante
Show the result after the first pass.
CS502 - Fundamentals of Algorithms
Fall Spring 2012
MID TERM Paper
Dated May 11,2012
Time 1 hour
Total Marks 40
Attempt by Umair Saulatsaulat.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)
can any one tell me what is the correct choice
The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required?
Select correct option:
16
10
32
31
The correction answer of this question is 32
The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required?
16
10
31
32
thanks
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