CS502 Midterm Past Paper Spring 2013

Q: Write the STABLE OR IN-PLACE of QUICK, HEAP, COUNTING, MERGE Sorts. [5 MARKS]

Answer: [PAGE 54]

In-place Stable Bubble sort Bubble sort Insertion sort Insertion sort Selection sort Merge sort Quick sort Heap sort Counting sort

Q: Write any 3 applications of Edit distance. [3 MARKS]

Answer: [PAGE 76 and 77]

1. Spelling correction.
2. Plagiarism detection.
3. Computational and molecular biology.
4. Speech recognition.

Q: Define MEMOIZATION? [2 MARKS]

Answer: [PAGE 74]

We can avoid unnecessary repetition by write down the recursive calls and look them when we need.

Q: Define worst case and average case of Quick sort? [2 MARKS]

Answer: [From MDB] Worst case:

We maximize over all possible values of q, means the selection of pivot q which gives the maximum (worst) time for sorting. The worst case running time is O (n2).

Average case:

Average case analysis of quick sort, the average is computed over all possible random choices of the pivot index q. The average case running time for quick sort is ԕ (n log n).

Q-Quick sort such that sort the array in to non-increasing order? [There is no any array in this question]

Answer: Page 47 n 48

Q-We can avoid unnecessary repetitions for recursive calls?( I thnk how can we ... ho ga.) [PAGE 74]

Answer: By using Fibonacci Sequence We can avoid this unnecessary repetition by writing down the results of recursive calls and looking them up again if we need them later. This process is called memoization.

Q-Write a pseudo code Fibonacci With memorization? -- (3)

Answer: [PAGE 74] MemoFIB(n) if(n<2) then return n if (f[n] is undefined) then F[n] <--- MemoFIB(n-1) + MemoFIB(n-2) returnf[n] QSpelling correction in edit distance? 3 marks

Answer: [PAGE 76]

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.

Q-What is Bubble sort?

Answer: [PAGE 39] 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.

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

Answer: Page 49 and 50

Worst case running time is O (n). The simple change which can change the running time of the edit distance algorithm is the number of entries n2.

Q: In edit distance what is the simple change that can change the worst case time?

Answer: [Page 49 and 50]