Transcript
(1)5. Design an algorithm to find all the common elements in two sorted lists of numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output should be 2, 5, 5.What is the maximum number of comparisons your algorithm makes if the lengths of the two given lists are m and n, respectively?
(2)5. Describe the standard algorithm for finding the binary representation of a positive decimal integer
a. in English.
b. in pseudocode.
(3)1. Consider the algorithm for the sorting problem that sorts an array by counting,
for each of its elements, the number of smaller elements and then uses this
information to put the element in its appropriate position in the sorted array:
ALGORITHM ComparisonCountingSort(A[0..n ? 1])
//Sorts an array by comparison counting
//Input: Array A[0..n ? 1] of orderable values
//Output: Array S[0..n ? 1] of A’s elements sorted
// in nondecreasing order
for i ? 0 to n ? 1 do
Count[i]? 0
for i ? 0 to n ? 2 do
for j ? i + 1 to n ? 1 do
if A[i] < A[j ]
Count[j ]? Count[j ] + 1
else Count[i]? Count[i] + 1
for i ? 0 to n ? 1 do
S[Count[i]]? A[i]
return S
a. Apply this algorithm to sorting the list 60, 35, 81, 98, 14, 47.
b. Is this algorithm stable?
c. Is it in-place?
(4)2. If you have to solve the searching problem for a list of n numbers, how can you take advantage of the fact that the list is known to be sorted? Give separate answers for a. lists represented as arrays. b. lists represented as linked lists.
(4)10. Anagram checking Design an algorithm for checking whether two given words are anagrams, i.e., whether one word can be obtained by permuting the letters of the other. For example, the words tea and eat are anagrams.
(5)8. For each of the following functions, indicate how much the function’s value will change if its argument is increased fourfold. a. log2 n b. ?n c. n d. n2 e. n3 f. 2n
(5)9. For each of the following pairs of functions, indicate whether the first function of each of the following pairs has a lower, same, or higher order of growth (to within a constant multiple) than the second function. a. n(n + 1) and 2000n2 b. 100n2 and 0.01n3 c. log2 n and ln n d. log2 2 n and log2 n2 e. 2n?1 and 2n f. (n ? 1)! and n!
(6)5. List the following functions according to their order of growth from the lowest to the highest: (n ? 2)!, 5 lg(n + 100) 10, 22n, 0.001n4 + 3n3 + 1, ln2 n, ?3 n, 3n.
(6)10. The range of a finite nonempty set of n real numbers S is defined as the difference between the largest and smallest elements of S. For each representation of S given below, describe in English an algorithm to compute the range. Indicate the time efficiency classes of these algorithms using the most appropriate notation (O, , or ). a. An unsorted array b. A sorted array c. A sorted singly linked list d. A binary search tree
int sizem , sizen ; sizem=arr1.size(); sizen=arr2.size(); int m=0 , n=0 , element1, element2, index=0; if(sizemelement1) break; else if(element1>element2) continue; } } return arr3 ;
