for(i = 0; i < n; i = i + 10) for(j = 0; j < n; j = j + 10) System.out.println("Hello");Solution: Fix the value of i at 0. For this value of i, the output statement executes once for each value of j = 0, 10, 20, ..., n - 10. Couting the number of possible values of j, we see that there are n/10 values. So when i = 0, the output statement is executed n/10 times. Similarly, when i = 10, the output statement is executed n/10 times and so on. Just like j, the loop-control variable i also takes on n/10 values. Therefore the output statement gets executed n^2/100 times.
for(i = 0; i < n; i = i + 10) for(j = 0; j < i; j = j + 10) System.out.println("Hello");Solution: When i is equal to 0, the output statement is executed 0 times. For any value of i between 1 and 10 (inclusive of both values), the output statement executes once. For any value of i between 11 and 20 (inclusive of both values), the output statement executes twice and so on. Summing this up over all possible values of i we get that the total number of times the output statement is executed is:
0 + 1 * 10 + 2 * 10 + 3 * 10 +....To figure out where this summation stops, note that the last batch of 10 values that i takes are:
(n-20) + 1, (n-20) + 2, ..., (n-20) + 10For each value of i in this batch, the output statement executes n/10 - 1 times. So the total number of executions of the output statement is:
0 + 1 * 10 + 2 * 10 + 3 * 10 +....+ (n/10 - 1) * 10.Taking 10 common and using the formula for the summation of the first n natural numbers, we obtain that the above summation equals:
5(n/10 - 1) (n/10) = n(n-10)/20.
i = 1; while(i < n) { System.out.println("Hello"); i = 2*i; }Solution: The output statement is executed once for each value of i = 1, 2, 4, 8, ..., 2^k, where 2^k < n, but 2^(k+1) >= n. This is a total of (k+1) times. But, what is k? Solving the inequality, n <= 2^(k+1) < 2n, we get that log_2 (n) <= (k+1) < 1 + log_2 (n). Therefore, the number of times the output statement is executed is the integer between log_2 (n) (inclusive) and log_2 (n) + 1.
for(i = 0; i < n-1; i++) for(j = n-2; j >= i; j--) if(list[j] > list[j+1]) swap(list, j, j+1);
3 1 8 2 4 5In particular, show the array after each swap.
Solution:
3 1 8 2 4 5 3 1 2 8 4 5 1 3 2 8 4 5 1 3 2 4 8 5 1 2 3 4 8 5 1 2 3 4 5 8
Solution: For i=0, the variable j takes on n-1 values and therefore for i = 0, n-1 comparisons are made. For i=1, the variable j takes on n-2 values. For i=2, the variable j takes on n-3 values and so on. The last value that i takes is n-1 and for this value of i, the variable j takes on 0 values. Therefore, the total number of comparisons is
(n-1) + (n-2) + (n-3) + .... + 3 + 2 + 1 = n(n-1)/2.
Solution:
int i = 0; boolean done = false; while(!done) { done = true; for(int j = n-2; j >= i; j--) if(list[j] > list[j+1]) { done = false; swap(list, j, j+1); } i++; }
Solution: The improved bubble sort algorithm makes n - 1 comparisons.
We also discussed two different implementations of this ADT. Implement the above ADT as a java class using an ordered array. Make sure that the search operation is implemented using binary search. Assume that each record consists of three fields. A string field to store a name, a long field to store a social security number, and a double field to store the person's pay. The social security field should be used as a key to delete from the collection and search the collection. Therefore collection of records should be maintained in increasing order of social security number.
Solution: Here is the code that is the solution to this problem.