Reference no: EM132819005
1. A Young tableauis an m x n matrix such that: the entries of each row are in sorted order from left to right, and the entries of each column are in sorted order from top to bottom.
Some entries of a Young tableau may be∞, which we treat a nonexistent numbers. Give an algorithm to implement Extract-Min on a non-empty m x n Young tableau thatruns in O(m+n) time. The algorithm should use a recursive subroutine that solves an m x n problem by recursively solving either an (m-1) x nor an m x (n-1) sub-problem¬¬¬.
2. Define T(p), where p=m+n, to be the maximum running time of Extract-Min on any m x n Young tableau. Give and solve a recurrence relation for T(p) that yields the O(m+n) time bound.
3. Using no other sorting method as a subroutine, show how to use an n x n Young tableau to sort n^2 numbers in(n^3) time.
4. Show that mergesort, bubblesort, and insertion sort, if carefully done, are stablesorts. Show why quicksort and selection sort, as usually implemented, are not stable sorts.
5. Give an algorithm that, givennintegers in the range from 0 tok, preprocessesits input and then answers any query about how many of thenintegers fall into a range[a..b] inO(1) time. The algorithm should use Θ(n+k) preprocessing time
6. Consider the following problem: Sort an array of C-strings which may be of different lengths into lexicographical order. C-strings are arrays of characters where thelast character indicates the end of the string and is always the null character (Unicode orASCII 0). Lexicographical ordering is dictionary order: compare the two strings, characterby character, until the first mismatched pair of characters is found, and whichever stringhas the smaller character in that position is the smaller string. If one string is a prefix of another string, then the mismatched characters occur when at the last character of the prefix (0) and at a non-zero character of the other string, so the prefix always comes firstin lexico graphical ordering.
Consider using MSD-Radix sort to sort the strings. In practice, it is very important toswitch to insertion sort for small arrays.How many characters, on average, are examined when sortingNrandomstrings from anR-character alphabet? Hint: How many strings fall in each bucket, on average, and howmuch work is done to sort each bucket? Write and solve a recurrence relation for this.How many characters, in the worst-case, are examined, when sortingNstrings from an Rcharacter alphabet and the average string length isw?
7. Give an efficient algorithm that finds theith largest numbers in a set ofnnumbers. Do not assume that the input is sorted. The output numbers do not have to bein order. What is the running time of your algorithm?