(Textbook. Click for information.)

CS 3343/3341  Analysis of Algorithms  Spring 2012  Recitation 3  Linked Lists, Etc.     Partial Answers

Here is a trace of Fibonacci search in an array with array values stored using indexes from 1 to 12.

Search for value 23
Index: 0    1    2    3    4    5    6    7    8    9   10   11   12   13
-------------------------------------------------------------------------
Values:     3    7    9   11   18   23   27   36   39   44   48   59
Pivot:                                        36
Since 23 < 36
Limit to:   3    7    9   11   18   23   27
Pivot:                         18
Since 23 > 18
Limit to:                           23   27
Pivot:                                   27
Since 23 < 36
Limit to:                           23
Found!!  

1. Do the same kind of trace for the array below, with values stored for indexes from 1 to 20:

   Search for value 19 Ind: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 --------------------------------------------------------------------- Values: 3 6 7 9 10 12 14 16 17 19 23 24 32 36 38 41 42 45 51 57 Pivot: 32 Limit: 3 6 7 9 10 12 14 16 17 19 23 24 Pivot at:8 16 Limit to: 17 19 23 24 Pivot at:8+3 23 Limit to: 17 19 Pivot at:8+2 19 Done

2. With the Fake Coin Problem say exactly how to handle any number n of coins using 3 piles. (As in the write-up one coin is lighter than the others and you use a balance scale.) Your algorithm should still take (roughly) log₃(n) steps. As long as two piles are of equal size, the third pile can be any size at all, and the system works. It works the most quickly if the size of the third pile is as close to the sizes of the other as you can arrange. Suppose n = n₁ * 3 + n₂, where n₂ = n mod 3, that is, 0, 1, or 2. So make the piles:

   Value of n2	1st pile	2nd pile	3rd pile
   n2==0	n1	n1	n1
   n2==1	n1	n1	n1 + 1
   n2==2	n1 + 1	n2 + 1	n2

   For n sufficiently large, these piles are as close as you like to n/3, and the algorithm would take roughly log₃(n) steps.

3. If n a power of two and we use 2 piles at each stage, it takes log₂(n) steps. For n a power of three and using 3 piles at each stage, it takes log₃(n) steps. Give the value of a constant c such that log₃(n) = c * log₂(n). Give c as an exact symbolic value and an approximate numeric value.

   c = log₃(n) / log₂(n), and
   log₃(n) = log₂(n) / log₂(3), so
   c = 1 / log₂(3) = 1 / 1.58496 25007 = 0.63092 97535.

In these questions you must use your book's version of quicksort, which was also the only one presented in class.

4. Use one call of Partition on the array
   < 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 >

   Show the results step-by-step, as with the book's Figure 7.1, which is online here. The table below shows these results for the starting position, marked s, for the ending position, marked e, and for rows with the result at the end of each loop iteration for j = 0, 1, 2. Fill in the rows for 3 <= j <= 10. For all 13 rows, insert 2 or 3 vertical lines ("|") as shown in Figure 7.1. (This shows an array based on 0, but this makes no difference to the quicksort algorithm.)

   j A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11] ----------------------------------------------------------------- s 13 19 9 5 12 8 7 4 21 2 6 11 0 | 13 19 9 5 12 8 7 4 21 2 6 11 1 13 | 19 9 5 12 8 7 4 21 2 6 11 x(0,2) 2 9 | 19 | 13 5 12 8 7 4 21 2 6 11 x(1,3) 3 9 5 | 13 | 19 12 8 7 4 21 2 6 11 4 9 5 | 13 19 | 12 8 7 4 21 2 6 11 x(2,5) 5 9 5 8 | 19 12 | 13 7 4 21 2 6 11 x(3,6) 6 9 5 8 7 | 12 13 | 19 4 21 2 6 11 x(4,7) 7 9 5 8 7 | 4 13 19 | 12 21 2 6 11 8 9 5 8 7 4 | 13 19 12 | 21 2 6 11 x(5,9) 9 9 5 8 7 4 2 | 19 12 21 | 13 6 11 x(6,10) 10 9 5 8 7 4 2 6 | 12 21 13 | 19 11 x(7,11) e 9 5 8 7 4 2 6 | 11 | 21 13 19 12

5. What is the result of one Partition acting on the following array, and how many exchanges are carried out during this partition? How many of the exchanges are of an element with itself (that is, the element at a single index is exchanged with itself -- NOT two element of the same value exchanged)? (Just give the final result, not step-by-step.)
   < 8, 8, 8, 8, 8, 8, 8, 8, 8, 11 >

   j A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] ----------------------------------------------------------------- | 8 8 8 8 8 8 8 8 8 11 | i=-1,x(0,0) 0 | 8 8 8 8 8 8 8 8 8 11 | i=0,x(1,1) 1 | 8 8 8 8 8 8 8 8 8 11 | i=1,x(2,2) 2 | 8 8 8 8 8 8 8 8 8 11 | i=2,x(3,3) 3 | 8 8 8 8 8 8 8 8 8 11 | i=3,x(4,4) 4 | 8 8 8 8 8 8 8 8 8 11 | i=4,x(5,5) 5 | 8 8 8 8 8 8 8 8 8 11 | i=5,x(6,6) 6 | 8 8 8 8 8 8 8 8 8 11 | i=6,x(7,7) 7 | 8 8 8 8 8 8 8 8 8 11 | i=7,x(8,8) 8 | 8 8 8 8 8 8 8 8 8 11 | i=8,x(9,9) | 8 8 8 8 8 8 8 8 8 11 | i=8

   Exchanges: 10 times element with itself

6. Same question for the array:
   < 15, 15, 15, 15, 15, 15, 15, 11 >

   j A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] --|------------------------------------------------ | 15 15 15 15 15 15 15 11 | i=-1 0 | 15 15 15 15 15 15 15 11 | i=-1 1 | 15 15 15 15 15 15 15 11 | i=-1 2 | 15 15 15 15 15 15 15 11 | i=-1 3 | 15 15 15 15 15 15 15 11 | i=-1 4 | 15 15 15 15 15 15 15 11 | i=-1 5 | 15 15 15 15 15 15 15 11 | i=-1 6 | 15 15 15 15 15 15 15 11 | i=-1 x(0,7) | 11 15 15 15 15 15 15 15 | i=-1

   Exchanges: 1 time element with another.

7. I am supplying incomplete code for a linked list structure that is used to create a stack and a queue. For this recitation you are to fill in the missing parts, labeled (a) through (f). A version is supplied in Java and in C. The Java version is sort of OK (though of course it should be generic), but the C version, translated from the Java code, allows only one stack or one queue, but not both, to be used. This approach wouldn't be reasonable in C, but it still works as a recitation. Please look at the incomplete code for a linked list below:
   • Java Version Answers.
   • C Version Answers.