Introduction to the Design and Analysis of Algorithms
(Textbook. Click for information.)
 CS 3343/3341
 Analysis of Algorithms
 Spring 2012
 Recitation 3
 Linked Lists, Etc.
    Week 3: Jan 31-Feb 2
 Due (on time): 2012-02-06  23:59:59
 Due (late):        2012-02-10  23:59:59

Recitation 3 should be submitted following directions at: submissions with deadlines
  • 2012-02-06  23:59:59 (that's Monday, 06 February 2012, 11:59:59 pm) for full credit.
  • 2012-02-10  23:59:59 (that's Friday, 10 February 2012, 11:59:59 pm) for 75% credit.

Fibonacci Search Topic.

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

Fake Coin Topic.

  1. 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) log3(n) steps.

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

Quicksort.

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

  1. 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 
  
 2    9   19   13    5   12    8    7    4    21    2    6    11 
  
                [rows 3 to 10 to be filled in]
  
 e    9    5    8    7    4    2    6   11    21   13   19    12

  2. 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 >

  3. Same question for the array:

    < 15, 15, 15, 15, 15, 15, 15, 11 >

Linked List Used as a Stack and a Queue.

  1. 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:

What you should submit: Refer to the submissions directions and to deadlines at the top of this page. The text file that you submit should first have Your Name, the Course Number, and the Recitation Number. The rest of the file should have the following in it, in the order below, and clearly labeled, including at the beginning the appropriate item numbers: 1, 2, 3, etc.

 Contents of email submission for Recitation 3:

Your last name, Your first name; CS 3343; Recitation 3.

Solutions to problems 1 through 7 above. For part 7, you should submit a complete listing in either Java or in C, including all the additions that you made to the six incomplete functions, labeled (a) through (f). Your submission should also include a run. For submissions that include separate files, you should still concatenate these together, perferably with some line of characters such as ////////////////// between files.

If you are having trouble getting this to work, consult with me or with the TA, or send me an email question. You should submit whatever you have for the deadline, even if it is not working.

(Remember, just a single .txt file, with the parts concatenated together.)

Key goals:

Revision date: 2012-01-02. (Please use ISO 8601, the International Standard.)