We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>
+ Link For Assignments, GDBs & Online Quizzes Solution
+ 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
How to Add New Discussion in Study Group ? Step By Step Guide Click Here.
CS502 All Current Mid Term Papers Spring 2013 (25 May 2013 ~ 06 June 2013) at One Place
From 25 May 22, 2013 to 06 June 2013 Spring 2013
Current Mid Term Papers Spring 2013 Papers, May 2013 Mid Term Papers, Solved Mid Term Papers, Solved Papers, Solved Past Papers, Solved MCQs
.+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)
+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)+ Click Here to Search (Looking For something at vustudents.ning.com?) + Click Here To Join (Our facebook study Group)
Prepared By Rao Usman Aims Lahore Subjective cs502 Midterm parers 2013 Quick sort such that sort the array into non increasing order? we are given an array A[1..n] of n numbers We are to reorder these elements into increasing (or decreasing) order. Q we can avoid unnecessary repetitions for recursive calls? We can avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later. This process is called memoization. Here is the algorithm with memoization. Q-Write a pseudo code Fibonacci With memorization? -- (3) 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] Spelling correction in edit distance? 3 marks If a text contains a word that is not in the dictionary, a ‘close’ word, i.e. one with a small edit distance ,may be suggested as a correction. Most word processing applications, such as Microsoft Word, have spelling checking and correction facility. When Word, for example, finds an incorrectly spelled word, it makes suggestions of possible replacements. 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. What is the worst case running time for the Quick sort? What simple change is required in the algorithm to preserve its linear expected running time and makes it worst case time Θ(n log n) ADIT DISTANCE KI 3 APPLICATION K NAME BTANEY THE 3 MARKS Spelling Correction Plagiarism Detection Computational Molecular Biology MEMOIZATION KI DIFINATION THI 2 MARKS
We can avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later. This process is called memoization. Worst CASE OR AVERAGE CASE DEFINE KRNE THE 2 MARKS Worst-case time is the maximum running time over all (legal) inputs of size n. Let I denote an input instance, let |I| denote its length, and let T(I) denote the running time of the algorithm on input Average-case time is the average running time over all inputs of size n. Let p(I) denote the probability of seeing this input. The average-case time is the weighted sum of running times with weights EK 3 NUMBER WALA QUESTION THA US KA YAD NH Write Essential constraint of Counting sort. What are total numbers of entries in matrix for edit distance? There are Θ (n2) entries in the matrix. Each entry E(i, j) takes Θ (1) time to compute. The total running time is theata(n2). WHAT IS the necessary assumption for average case analysis quick sort? We will now show that in the average case, quicksort runs in Θ (n log n) time. Recall that when we talked about average case we said that it depends on some assumption about the distribution of inputs. However, in the case of quicksort, the analysis does not depend on the distribution of input at all. It only depends upon the random choices of pivots Θ Suggest & describe modifications of the implementation of "Quick sort" that will improve its performance? There are Total 26 Questions 20 MCQs and 6 Subjective questions. Mostly MCQs are from this file Q1 : How we Heapify? There is one principal operation for maintaining the heap property. It is called Heapify. Q2 : Describe Heap sort algorithm? We build a max heap out of the given array of numbers A[1..n]. We repeatedly extract the the maximum item from the heap. Once the max item is removed, we are left with a hole at the root. To fix this, we will replace it with the last leaf in tree. But now the heap order will very likely be
destroyed. We will apply a heapify procedure to the root to restore the heap. Figure 4.2 shows an array being sorted. Q3 : How many elements are in matrix of edit distance? repeat Q4 : Cost table was given with initial states and we have to find the next iteration after initial state and we have to mark it with "?" mark Q5 : Three matrix are given A1=5 x 4 , A2= 4 x 6, A3= 6x2 (Sorry values mujay yaad nai) we have to asked that which one is the better in performance wise justify your answer 1) A1(A2A3) 2) (A1A2)(A3) Sorry sahih yaad nai yah wala question magar kuch istarah ka tha Q6 : suggest and describe one modification of implementing quick sort? 5marks Page no 51 in handouts ----------- 1. Differentiate between structure and unstructured . 2. Types of Organizational Structure 3. Defines the logical and physical model in system design? Edit Distance in Speech Recognition Algorithms similar to those for the edit-distance problem are used in some speech recognition systems. Find a close match between a new utterance and one in a library of classified utterances. What is sorting? describe slow running sorting algorithms. 5 marks Sorting is well studied problem from the analysis point of view. Sorting is one of the few problems where provable lower bounds exist on how fast we can sort. In sorting, we are given an array A[1..n] of n numbers We are to reorder these elements into increasing (or decreasing) order. Slow Sorting Algorithms There are a number of well-known slow O(n2) sorting algorithms. These include the following: 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 element in A[i..n] Swap it with A[i]. These algorithms are easy to implement. But they run in _(n2) time in the worst case. 3 matrix given with their order. 2 multiplication orders were given.. calculate and tell which order of multiplication is better. 5 marks Catalan Numbers and their formula 3 marks This is related to a famous function in combinatorics called the Catalan numbers. Catalan numbers are related the number of different binary trees on n nodes. Catalan number is given by the formula: C(n)=1/n+1 2n n one array given.. apply quick sort for one iteration and reason your answer.. 3 marks one question of marks 2 forgotten.. page no 31 in handouts MCQ was from whole 1 - 20 almost . which seems difficult , that were from mathmaticle analysis ( 5 - 6 were of that type ) Q1.Heap Sort , Counting Sort , Quick Sort ,Merge Sort , in ,table ,And required to tell , which is inplace Algorithm and stable ? Marks 5 Q2 . Suggest that , how can make better improvement in Quick Sort algorithm .Marks The best we have seen so far is O(n log n) algorithms for sorting. Is it possible to do better than O(n log n)? If a sorting algorithm is solely based on comparison of keys in the array then it is impossible to sort more efficiently than Ω (n log n) time. Q3. Consider three numbers with comparison based sortig algorithim and write possible combination in a1,a2,a3 .Marks 3 (a1, a2, a3), (a1, a3, a2) , (a3, a2, a1) (a3, a1, a2), (a2, a1, a3) , (a2, a3, a1) Q4. What is better aproach of multiplication rather than straight form of Multiplication . Named that . Marks 3 Q5. ((A3A2)A1 . Question was of this type . but input change from handout .(Marks 2) Q6.worst case and average case algorithim of Quick Sort .Marks 2
1)difine heap and heap oerder A heap is a left-complete binary tree that conforms to the heap order. 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. In other words, the parent node has key smaller than or equal to both of its children nodes.
CS502 today paper
1st june 2013
MCQs from handouts and just few MCqs from past paper
1.which sort is stable and which is in place (table bna tha yes or no btyana tha)
2.What is sorting?Name slow sorting algorithms.
3.If A1,A2,A3 then how many combinations they have(issi type ka tha.)
4.Draw a max heap and show every node has large value then sub trees?
5.Draw the cost table for chain matrix multiplication problem with initial state?
6 Question tha ky multiply matrix main forwade sy better kia hai uss ka name kia hai.(bhool gi sorry iss type ka tha question.)
What is matrix multiplication?
Answer: You can multiply two matrices if, and only if, the number of columns in the first matrix equals the number of rows in the second matrix.
Otherwise, the product of two matrices is undefined.
The product matrix's dimensions are
→(rows of first matrix) × (columns of the second matrix )
In the picture on the left, the matrices can be multiplied since the number of columns in the 1st one, matrix A, equals the number of rows in the 2nd, matrix B.
The Dimensions of the product matrix
Rows of 1st matrix × Columns of 2nd
4 × 3
If we multiply a 2×3 matrix with a 3×1 matrix, the product matrix is 2×1
Here is how we get M11 and M12 in the product.
M11 = r11× t11 + r12× t21 + r13×t31
M12 = r21× t11 + r22× t21 + r23×t31
Two Matrices that can not be multiplied
Matrix C and D below cannot be multiplied together because the number of columns in C does not equal the number of rows in D. In this case, the multiplication of these two matrices is not defined.
plzzzz give these answers
What is the worst case running time for the Quick sort? What simple change is
required in the algorithm to preserve its linear expected running time and makes it
suggest and describe one modification of implementing quick sort?
Suggest that , how can make better improvement in Quick Sort algorithm
Plzzz answer these questions