Compsci 100, Fall 2006, Written List

This assignment is worth 25 points. You should work on your own, but you can use books/notes. You should not use the web as a resource for solving problems. Please do NOT compile and do not run your solutions. Please write your solutions by hand, using pencil/pen etc. Do NOT use Eclipse or a computer. We want you to practice thinking, writing by hand. Hopefully you'll rewrite to make things neat. If we can't read your writing, we'll think it's wrong.

Do NOT worry about perfect syntactic correctness, your grade is based on the algorithms you use/invent, not on whether the code compiles. However, you must write something close to correct in Java.

You'll submit a README electronically using Eclipse, but you'll turn in your written work: stapled, your name on every page. Your README file should indcate how long you spent on these problems and with whom you consulted.

Submit the README using Eclipse (assignment name linkedlist)

Again, do not run and debug. Instead, think. This is good practice for thinking, for test-taking, and for programming which should include time not spent at the machine.

In all these problems assume that the inner class Node exists as shown below. You'll write static methods in a class LinkProblems for your solutions. You cannot use instance variables, all variables must be local to the static methods you write. public class LinkProblems { public static class Node { String info; Node next; Node(String s, Node link) { info = s; next = link; } } // your methods here }

  1. Fruit Salad

    2. Write the method fruitCounter whose header follows. Method fruitCounter returns a count of the number of nodes whose info field has a value for which a static method isFruit (see below) returns true. public static boolean isFruit(String s){ // code not shown } For example, assuming that "apple", "orange", and "pear" are fruits (isFruit returns true) and "bear", "coyote", and "fox" are not fruits, and list is represented by: 
       ("apple", "bear", "apple", "orange", "coyote", "fox", "orange", "pear")
    the call fruitCounter(list) should evaluate to 5 since there are five fruits.

    Write two versions, one iterative and one recursive. 

    /**
  * @return the number of nodes whose info field is a fruit
  * as determined by method isFruit
  */
public static int fruitCounter(Node list)

  2. Reversi

    3. Write the function makeNrev whose header follows. The function returns a list in which for each number k in the range [1..n], there are k nodes containing k, and the nodes are in reverse order: n, n-1, ..., 3, 2, 1

    When creating nodes, use a string like "3" for the number 3, so nodes still contain strings.

    For example:

    picture

    /** * Create a list whose first node contains a String representing * n, whose nodes are in reverse order, and in which for all * k in [1..n] there are k occurrences of a node containing k. * @param n is the number used to control creation of the list * @return the first node of the list created */ public static Node makeNrev(int n)

  3. Occurs Check

    1. Write a method hasDuplicates whose header follows. The method returns true if parameter list has any duplicates (words occurring more than once) and false otherwise. For example, for the list 
       ( "apple", "guava", "cherry")
      hasDuplicates should return false, but it would return true for the list below since "guava" appears twice. 
       ( "apple", "guava", "cherry", "guava")
      In writing hasDuplicates you must call the method countOccurrences shown below and your method must be either a recursive function with no loop or a function with one loop. Either version can include calls to countOccurrences. You cannot use any ArrayList, Set, etc. objects in your code. /** * @return the number of occurrences of s in list */ public static int countOccurrences(Node list, String s) { if (list == null) return 0; int count = 0; if (list.info.equals(s)) count = 1; return count + countOcurrences(list.next,s); } /** * @return true if and only if list has duplicates * */ public static boolean hasDuplicates(Node list) { }

    2. What is the complexity (using big-Oh) of the solution you wrote to hasDuplicates and why?
    3. Describe how to write a more efficient solution to the hasDuplicates method using, for example, a TreeSet or a HashSet instead of calling countOccurrences. Be sure to indicate what the complexity of your solution is and why.

    Doubly linked lists are implemented using the declaration below.

    public static class DoubleNode { string info; DoubleNode next; // next node DoubleNode prev; // previous node DoubleNode(String s, DoubleNode before, DoubleNode after) { info = s; prev = before; next = after; } }

  4. Double Trouble

    5. Write an iterative function iremove that removes all nodes with a specific value from a doubly-linked list with no header node.

    For example, if list is 

        ("aardvark", "cat", "dog", "cat")
    then the statement 
        list = iremove(list, "cat");
    should make list be ("aardvark", "dog"). 
       /**
     * @return list with all copies of target removed
     */

   public static DoubleNode iremove(DoubleNode list, String target)
    Be sure to change all links appropriately.

  5. Move to the Back

    6. Write the method moveAfter which moves each node whose info field satisfies a criteria to the end of the list. The nodes are doubly-linked. The relative order of the unmoved nodes doesn't change, and the relative order of the moved nodes doesn't change (from the original order in the list). A pointer to the modified list is returned.

    Note that it's possible that the original first node is moved and that no nodes are moved. You should not create any new nodes, just move pointers/references.

    In the example here, assume the criteria is "being a citrus fruit" (orange and lemon are citrus). In general, assume there's an interface IIsMoveable and that an IIsMoveable object is passed to the method you write.

    public interface IIsMoveable { public boolean isMoveable(String s); } In the picture below only links in one direction are shown, but you're writing code to manipulate a doubly-linked list.

    *move*

    For full credit your code must run in O(n) time for an n-node list.

    /** * Move all nodes satisfying a criteria to the back of a list, * leaving relative order of nodes unchanged. * @param list is the list to be altered * @param moveable is used to indicate whether some node * should be moved * @return the potentially altered list */ public static DoubleNode moveAfter(DoubleNode list, IIsMoveable moveable)

  6. Lickety Split

    7. Write a method listSplit that will split a circular list containing an even number, say 2k, of nodes into two circular lists each of which contains k nodes. The method should have return one of the lists with k nodes and make the parameter list point to the other list of k nodes. For example, if list points to a circular list with 20 nodes the call 
        Node half = listSplit(list);
    will make list point to a circular list of 10 nodes and return a circular list containing the other 10 nodes of the original list.

    In writing listSplit, new nodes are not created, but are redistributed evenly between the two half-as-big lists. It doesn't matter how you divide the nodes between the two lists. Assume the list parameter contains at least 2 nodes, and that the number of nodes is even.

    The prototype for the function is:

    public static Node listSplit(Node list) (you should write documentation for the method)

  7. PolyCrackerNomial

    8. The following problems use the class TermNode below to represent a single term of a polynomial. For example 3x100 can be represented by TermNode(3,100,null); and 7x50 + 2x5 + 8 is represented by 
      TermNode poly = new TermNode(7,50, new TermNode(2,5, new TermNode(8,0,null)));
    Here's the class definition. public static class TermNode { int coeff; int power; TermNode next; TermNode(int co, int po, TermNode follow) { coeff = co; power = po; next = follow; } }
    1. Write a method makePolyNomial that takes a polynomial expressed in array form in which every term is explicitly stored (including those with zero-coefficients) and returns a polynomial expressed in linked list form (list of TermNodes) in which just terms with non-zero coefficients are stored. For example, given a array of [3, 0, 0, 2, 5], your function should return the list ( (3, 4), (2, 1), (5,0) ) since both represent 
      3x4 + 2x + 5

      Here we assume the 5 in the array has index 0 and the 3 has index 4, so the array is shown with the zero-index on the right (but your method doesn't have a right or a left, just an array with a length and int coefficients).

      /** * Returns a list of TermNodes representingy poly, * the elements in poly are in sorted order by power/exponent * with largest exponent first, no zero-coefficent terms in list returned. */ public static TermNode makePolyNomial(int[] poly)
    2. Write a method addPolyNomial that takes two polynomials expressed as lists of TermNodes, and returns a new polynomial representing the sum of the two parameters. The parameters should not be altered as a result of calling addPolynomial, a new polynomial is created and returned.

      For example, (3x4 + 2x + 4) + (2x2 - 4x -9) = (3x4 +2x2 - 2x - 5)

      ((3,4),(2,1),(4,0)) + ((2,2),(-4,1),(-9,0)) = ( (3,4),(2,2),(-2,1),(-5,0) )

      // pre: elements in p1 and p2 are sorted by power, largest to smallest // (standard form for this problem) // post: returns polynomial/list of TermNodes // representing the sum of p1 and p2 /** * Return polynomial in standard form of two standard form polynomials. * @param p1 is sorted by power, large to small, standard form * @param p2 is sorted by power, large to small, standard form * @return polynomial representing sum of p1 and p2 */ public static TermNode addPolyNomial(TermNode p1, TermNode p2)
    Owen L. Astrachan
    Last modified: Thu Sep 28 13:46:16 EDT 2006