Compsci 100, Recitation, October 2

recitation code submitted


Name: _____________________  Netid: _________________


Name: _____________________  Netid: _________________
 

Name: _____________________  Netid: _________________


In all these problems assume that the inner class Node exists as shown below. You'll write methods in a class LinkStuff for your solutions. You'll snarf a skeleton version of the code to write solutions in a group and then view them during recitation. You cannot use instance variables, all variables must be local to the methods you write. public class LinkStuff { public static class Node { String info; Node next; Node(String s, Node link) { info = s; next = link; } } // your methods here }

  1. I'm Special
  2. Write the method specialCount whose header follows. The method specialCount returns a count of the number of nodes whose info field has a value which is special as determined by the method isSpecial. public static boolean isSpecial(String s){ // code not shown } For example, assuming that "apple", "orange", and "pear" are special (isSpecial returns true) and "bear", "coyote", and "fox" are not special, and list is represented by:
       ("apple", "bear", "apple", "orange", "coyote", "fox", "orange", "pear")
    
    the call specialCount(list) should evaluate to 5 since there are five special strings.

    /** * @return the number of nodes whose info field is special. */ public int specialCount(Node list)

  3. Reversi
  4. Write the function makeReversed 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 Node makeReversed(int n)

  5. 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 frequency 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 frequency. You cannot use any ArrayList, Set, etc. objects in your code. /** * @return the frequency of occurrences of s in list */ public int frequency(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 boolean hasDuplicates(Node list) { }

    2. What is the complexity (using big-Oh) of the solution you wrote to hasDuplicates and why?
      
      
      
      
      
      
      
      
      
      
      
      
      
      

    Doubly linked lists are implemented using the declaration below.

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

  6. Double Trouble
  7. Write the method remove that removes all nodes with a specific value from a doubly-linked list with no header node. It's much easier to write this recursively.

    double linked

    For example, if list is

        ("aardvark", "cat", "dog", "cat")
    
    then the statement
        list = remove(list, "cat");
    
    should make list be ("aardvark", "dog").
       /**
         * @return list with all copies of target removed
         */
    
       public static DNode remove(DNode list, String target)
    
    
    
    
    
    Be sure to change all links appropriately.


  8. Move to the Back
  9. Write the method moveToBack which moves each node whose info field is equal to target to the end of the list. The nodes are doubly-linked. The relative order of the unmoved 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.

    For full credit your code must run in O(n) time for an n-node list. You might want to create a pointer to a list containing the moved nodes, update that list, then link the entire moved-node list to the end.

    /** * Move all nodes with target values to end of list, * leaving relative order of nodes unchanged. * @param list is the list to be altered * @return the potentially altered list */ public static DNode moveAfter(DoubleNode list, String target)