Homework Set 3 Solution

Complete each of the following problems to the best of your ability. Remember, you can’t be graded on what you don’t write down so (unless you are just making stu up) something is better than nothing. Discussing problems between each other is ne, but your nal writeup and work must be your own.







Algorithms and Sorting




Suppose you are given a sequence or array of n real numbers (a1; a2; : : : ; an), all distinct. We are interested in sorting this list, and ideally sorting it as e ciently as possible / with minimal e ort.







We can summarize the total ordering information in terms of a permutation of the numbers 1 to n. For instance, given (a1; a2; a3), a total ordering permutation of (3; 1; 2) would tell us that a3 a1 a2 and therefore that the sorted form of the list would be (a3; a1; a2).







How many possible total ordering permutations are there? How many ways can a list of n numbers be ordered?



Argue that if you know or are given the total ordering permutation, then you can sort the list in linear time, without any additional comparisons or tests.



Argue that if you don’t know the total ordering permutation (or only know partial / incomplete information about it) you cannot sort the list without additional comparisons or tests.



Taking this view, argue that any sorting algorithm must do at least enough work to determine the total ordering permutation of the list.



If every element comparison (testing whether ai aj) provides at most one bit of information, argue that you need at least on the order of ln(n!) many tests/comparisons to sort the list.



Argue that for n 1, n! nn.



Argue that for n 2, n! (n=2)n=2.



What can you conclude about the asymptotic growth / order of ln(n!)? What can you conclude about the minimal number of tests/comparisons needed in a universal sorting algorithm?



Based on the prior result, argue that merge sort is, asymptotically, as or more e cient than any other sorting algorithm.



Bonus) What are the tightest (simple) bounds you can achieve and verify on ln(n!)?




Modular Arithmetic and Divisibility Rules




These problems concern divisibility in base-10. Let N be an n-digit base-10 number,




N = DnDn 1 : : : D2D1:
(1)



Argue that N can be checked for divisibility by 2 in constant time. Do you even have to read all the digits in?



Argue that for any integer k 0, the following holds:



10k 1 (mod 3):
(2)



1
Computer Science Department - Rutgers University







Argue from this that if N is divisible by 3, the sum of the digits Dn + Dn 1 + : : : + D2 + D1 must also be divisible by 3, and vice versa.



Use this fact to construct an algorithm for checking divisibility by 3 (in base-10). What are the base cases you have to deal with?



Estimate the big O complexity of summing the digits of an n-digit number. For an n-digit number N, how big can the digit sum be?



Estimate, as tightly as you can, the big O complexity of checking divisibility by 3 according to this algorithm. Can you relate the complexity of running the algorithm to a smaller version of the same problem?



Look up an algorithm for computing division and remainder, and compare the complexity of your algorithm to the complexity of simply dividing N by 3 and checking the resulting remainder. Which one is better? Why?



Show that for any k,



2k (mod 3) 1 if k is even; 2 if k is odd
(3)



and use this to suggest an algorithm for checking divisibility by base 2. Estimate its complexity.




9) What is the complexity of checking for divisibility by 3 in base 3?































































































































2