Compsci 100e, Fall 2009, Linear Structure Questions

Collaborators:

Palindrome

1. You want to determine whether a sequence of characters represents a Watson-Crick complemented palindrome: the {A, C, T, G}-sequence equals its reverse when you replace each base with its complement: A-T, C-G). Palindromes in DNA have many important biological roles. For example, tumor cells frequently amplify their genes by forming DNA palindromes.
   1. What data structure is most appropriate here: a stack, queue, or deque?

   2. Write a method isPalindrome in WatsonCrick.java that uses the appropriate structure to determine whether two Strings are are Watson-Crick palindromes. Your program should also include test cases. Print your code and submit it with the rest of the answers.

   Adding to Lists

   The first two data series come from ListMaker in which values are added to the front and back of two kinds of lists. Both the data and a graph are shown. The first graph shows the timings from add to a LinkedList from the front, adding to a LinkedList from the back, and adding to an ArrayList from the back. The second graph adds the timings for adding to an ArrayList from the front. the front, the second are from adding to the back.

   

   

    double ltime = maker.addFront(linked,k);
    double atime = maker.addFront(array,k);
   
   10000   0.027   0.063
   20000   0.049   0.241
   30000   0.051   0.48
   40000   0.047   0.876
   50000   0.072   1.31
   60000   0.068   1.919
   70000   0.114   2.549
   80000   0.097   3.332
   90000   0.098   4.211
   100000  0.103   5.34
   110000  0.126   6.451
   120000  0.125   7.46
   130000  0.125   8.823
   140000  0.13    10.334
   

    double ltime = maker.addBack(linked,k);
    double atime = maker.addBack(array,k);
   
   
   10000   0.025   0.0090
   20000   0.048   0.035
   30000   0.052   0.02
   40000   0.047   0.06
   50000   0.071   0.033
   60000   0.067   0.079
   70000   0.111   0.044
   80000   0.096   0.053
   90000   0.096   0.059
   100000  0.102   0.131
   110000  0.124   0.073
   120000  0.124   0.083
   130000  0.123   0.148
   140000  0.128   0.188
   
   

2. Explain why addBack and addFront can be called with arguments that are linked-lists and array-lists.

3. Develop an explanation for the timings above. In particular, predict the time to create lists of size 200,000 by adding to the front and back of LinkedList and ArrayList lists (that's four predicted values).

   ---

   Finding and Removing

   Here are times from ListSplicer.java. First, times for removing the first element.

   

   	
    double ltime = splicer.removeFirst(splicer.create(linked,k));
    double atime = splicer.removeFirst(splicer.create(array,k));
   
   10000   0.0050  0.053
   20000   0.0010  0.205
   30000   0.0020  0.459
   40000   0.0030  0.814
   50000   0.0030  1.271
   60000   0.0030  1.84
   70000   0.0040  2.511
   80000   0.0050  3.26
   
   

4. Why are the times different? Explain.

   ---

   Here are times for removing the middle element by its index.

   

   	
    double ltime = splicer.removeMiddleIndex(splicer.create(linked,k));
    double atime = splicer.removeMiddleIndex(splicer.create(array,k));
   
   10000   0.222   0.029
   20000   0.843   0.104
   30000   2.268   0.233
   40000   4.921   0.411
   50000   8.078   0.645
   60000   11.649  0.926
   70000   18.179  1.251
   80000   23.796  1.636
   
   
   

5. Explain the differences here.

   ---

   Here are times for removing the middle element by finding it using indexOf, then removing it by index. The second set of data removes the middle element via iteration, see the code for details.

   

    double ltime = splicer.removeMiddleValue(splicer.create(linked,k));
    double atime = splicer.removeMiddleValue(splicer.create(array,k));
    (remove first and one-past found/middle)
   
   10000   0.335   0.211
   20000   1.388   0.829
   30000   3.931   1.859
   40000   7.512   3.319
   50000   12.053  5.237
   60000   17.334  7.63
   70000   24.288  10.496
   80000   30.983  13.783
   
   
   

    double ltime = splicer.removeMiddleValue(splicer.create(linked,k));
    double atime = splicer.removeMiddleValue(splicer.create(array,k));
    remove first and one past iterated found middle
   
   10000   0.445   0.612
   20000   1.963   2.726
   30000   4.425   6.153
   40000   8.028   11.187
   50000   12.708  17.348
   60000   18.67   25.033
   70000   25.643  34.015
   80000   33.164  44.39
   
   

6. Explain these timings