1 Tracing CodePredict the output of the following programs. Some of the lines may generatecompiler or runtime error; if so, indicate it on your answer and treat the rest ofthe program as if that line did not exist.public class AString {public String body;public AString(String text) { body = text; }public String toString() { return body;}public static void main(String[] argv){AString a = new AString("Blessed are the poor in spirit,");AString b = new WeirdString(a.toString());AString c = new WeirdString(new AString(a.toString()));System.out.println(b == a); // 1System.out.println(b.equals(a)); // 2System.out.println(b.toString() == a.toString()); // 3System.out.println(b.toString().equals(a.toString())); // 4System.out.println(c.toString() == b.toString()); // 5System.out.println(c.toString().equals(b.toString())); // 6a.body = "For theirs is the kingdom of heaven";System.out.println(b); // 7System.out.println(c); // 8}}class WeirdString extends AString {public String body;public WeirdString(String text){super(text);body = text;}public String toString() { return body;}}Output:1. ___________ 2. _____________13. ___________ 4. _____________5. ___________ 6. _____________7. ________________________________8. ________________________________2 SortingModify merge sort so that it behaves exactly like an insertion sort. And by“behaving exactly the same”, I mean that you cannot distinguish the two sortsby only looking at how the array changes through the sort. What’s the worstcase running time of this new merge sort?void mergeSort(int[] arr, int lo, int hi) {if (lo == hi)return;mergeSort(arr, _______________, _________________);mergeSort(arr, _______________, _________________);// FILL IN}Now, modify quick sort so it behaves exactly like selection sort. What’s theworst cas e running time of this new quick sort?void quickSort(int[] arr, int hi, int lo) {if (lo == hi)return ;2// SET-UP PIVOT HERE:Integer pivot = _______________;// PREPARE FOR RECURSIVE CALL HERE:quickSort(arr, _____________________);quickSort(arr, _____________________);}3 ArrayListIn ArrayList, every single insertion is fast except for the ones that expands thearray since they need to copy the entire contents of the old array to a newone. Min observed this and claims that we can make ArrayList insertion moreefficient by squaring the size of the array when expanding instead of doubling.His rationale is that we would not have to expand the array nearly as often thisway. Describe to him why squaring the size offers no faster running time overjust doubling the size. Is his scheme slower? Explain.4 GenericsAssume that “Number” is a Java interface that Integer, Double, Long, etc,implements and that Number has a isPositive method that tests for whetherthe number is positive. We would like to declare a method that scans througha list of Numbers and return the numb er of positive elements. We would likeour method to accept as many input types as possible.First, explain why the following declaration won’t work:int countPositive(List<Number> ls) { ... }3Now, fill in the correct declaration:___________________ int countPositive(_____________________________ ls) { ...
View Full Document