Friday, May 11, 2012

Challenge 067’s Solution

In Part I of Challenge 67, option A best describes the method. The program starts by assigning the int variable n as the length of the String list items. The int variable m is created, equaling n − 1. Then, a for statement is used to make m equal to the element number of the greatest value of items. After that, a String variable named temp is used to switch the values of elements m and n − 1. This process is repeated with the value of n decreased by 1 until n = 1, resulting in the list being sorted in alphabetical order. Because this process best describes Sequential Search, option A is correct.

In Part II of Challenge 67, after two iterations of the while loop, the order of names will be: {“Boris”, “Alice”, “Claire”, “Dan”, “Evan”}. This is because of names’s original order: {“Dan”, “Alice”, “Claire”, “Evan”, “Boris”}. The first iteration of the while statement will compare element 4 (“Boris”) with the others and switch it with the largest of the elements before it: element 3 (“Evan”). The second iteration of the while statement will compare element 3 (“Boris”) with the others and again switch it with the largest of the elements before it: element 0 (“Dan”). This will result in the order of names being: {“Boris”, “Alice”, “Claire”, “Dan”, “Evan”}.

−Phoenix

Monday, May 7, 2012

Challenge 066’s Solution

Of the five options, the most efficient would be option B: to use a Selection Sort that terminates after 5 iterations. Option A offers to use a complete Selection Sort. A Selection Sort starts by getting an array list of size n. It searches each element in this list, and places the largest at position n, then repeats for an array list of size n − 1 until the array has a size of 1. If performed, all 2,000 cows would be ordered. Since we only need the 5 heaviest cows, option A isn’t the most efficient. Option B offers to use Selection Sort, but only for five executions. If performed, the top 5 heaviest cows would be ordered, while the remaining cows would not. Since there is no unnecessary sorting, option B is the most efficient. Option C offers to use a complete Insertion Sort. An Insertion Sort starts by getting an array list and an int variable n of size 1. The value of the element n + 1 is saved separately. Then, among the first n elements of the array, the saved value is inserted in numeric order, and values greater than it are pushed one element right. This repeats with n + 1 until n is the size of the array. If performed, all 2,000 cows would be ordered. Since we only need the 5 heaviest cows, option C isn’t the most efficient. Option D offers to use Insertion Sort, but only for five executions. If performed, only the first 5 cows who were weighed would be ordered, while the remaining cows would not. Since the first 5 cows ordered may not necessarily be the 5 heaviest, option D is inefficient. Finally, option E offers to use a complete Mergesort. A Mergesort starts by splitting the array into two equal halves. Each half is sorted separately, then combined into one sorted whole. If performed, all 2,000 cows would be ordered. Since we only need the 5 heaviest cows, option E isn’t the most efficient.
 
−Phoenix

Thursday, May 3, 2012

Challenge 065’s Solution

A binary search of 1,000 elements would be, on average, 50× faster than a sequential search. A sequential search checks each element of an array list until a matching element is found. The process can be represented with the equation S(n) = n ∕ 2, where n represents the number of elements in the array list and S(n) represents the average number of sequential comparisons it will take. Thus, an array of 1,000 elements would take, on average, 500 comparisons to target. A binary search sorts the array list in ascending order, then checks the median value of the list. If the value of the element being searched for is less than the median, then the procedure is repeated with the left half of the array; else, the procedure is repeated with the right half of the array. This process can be represented with the equation B(n) = log₂(n), where n represents the number of elements in the array list and B(n) represents the average number of binary comparisons it will take. Thus, an array of 1,000 elements would take, on average, about 10 comparisons to target. Therefore, a binary search of 1,000 elements would be, on average, 50× faster than a sequential search.
 
−Phoenix

Tuesday, May 1, 2012

Challenge 064’s Solution

An input of “la-la-la!” will produce an output of “ala-a” in the Terminal window. The original variable str has a value of “la-la-la!” with a length of 9. First, it checks if its length is greater than or equal to 3. Next, the substring method gets the length and divides it by 3, which is 3. Thus, all elements of str that are after element 0 (inclusive) up to the third element are run through the method again via recursion. This second str has a value of “la-” and a length of 3. Running this str through the first substring method creates an str with a length less than 3, so its recursion doesn’t matter. Next, the second str is run through a substring that gets all elements after element 1 (inclusive) up to the second element and prints them on the screen. This produces an output of “a”. After this, str has its first 2 elements removed and runs again through the method; however, this str’s length is less than 3, so nothing happens. The original str, with a length of 9, now ascends to the next line of code. This str is run through a substring that gets all elements after element 3 (inclusive) up to the sixth element and prints them on the screen. This produces an output of “la-”. After this, the original str has its first 6 elements removed and runs again through the method. This third str has a value of “la!” and a length of 3. Like the second str, running this str through the first substring method creates an str with a length less than 3, so its recursion doesn’t matter. The third str is run through a substring method that gets all elements after element 1 (inclusive) up to the second element and prints them on the screen. This produces an output of “a”. Finally, str has its first 2 elements removed and runs again through the method; however, this str’s length is less than 3, so nothing happens. In total, this creates an output of “ala-a”.
 
−Phoenix