Programming Lab 11 : Revisions


CSCI-UA 9102, Data Structures

The notation [W] refers to the book “Data structures and problem solving using Java” by Mark A. Weiss

  • Exercise 11.1. [W] Implement the various hasDuplicates methods, which all return true if there are any duplicates entries in the specified group of elements. 


public static boolean hasDuplicates( int [ ] arr )
public static boolean hasDuplicates( int [ ][ ] arr )
public static boolean hasDuplicates( String [ ] arr )
public static boolean hasDuplicates( ArrayList < String >  arr )

  • Exercise 11.2. [W] Implement the following methods that reverse an array or ArrayList of Strings. 


public static void reverse( String [ ] arr )
public static void reverse( ArrayList < String >  arr )


  • Exercise 11.3. [W] Implement the following methods that return the minimum of the group of items passed as a parameter. In the case of Strings, the minimum is the alphabetically smallest, as determined by compareTo 

    • 
public static int min( int [ ] arr )
public static int min( int [ ][ ] arr )
public static String min( String [ ] arr )
public static String min( ArrayList arr )


  • Exercise 11.4. [W] Write, in as few lines as possible, code that removes all entries in a Map whose values are null.
  • Exercise 11.5. [W] A linked list contains a cycle if, starting from some node p, following a sufficient number of next links brings us back to node p. Node p does not have to be the first node in the list. Assume that you have a linked list that contains N nodes. However, the value of N is unknown

    1. Design a O(N) algorithm to determine whether the list contains a cycle. You may use O(N) extra space
    2. Repeat part (a) but use only O(1) extra space. (Hint: use two iterators that are initially at the start of the list, but advance at different speeds.)

  • Exercise 11.6. Add a method find(x) to the Linked List class that returns the position associated to the element ‘x’
  • Exercise 11.7. Modify the method from Exercise 11.6 so that it returns the last occurence of ‘x’
  • Exercise 11.8. Add a remove(x) method to the linked list class
  • Exercise 11.9. Modify the remove method from Exercise 11.8 to remove all occurences of ‘x’
  • Exercise 11.10. We now consider a sorted linked list. Write routines makeUnion and intersect that return the union and intersection of two sorted linked lists.
  • Exercise 11.11. Write efficient methods (and give their Big-Oh running times) that take a reference to a binary tree root T and compute:
    1. The number of leaves in T
    2. The number of nodes in T that contain one non-null child
    3. The number of nodes in T that contain two non-null children
  • Exercise 11.12. Suppose a binary tree stores integers. Write efficient methods that take a reference to a binary tree root T and compute:
    1. The sum of all the items in the tree
    2. The number of nodes with two children that contain the same value
    3. The length of the longest strictly increasing sequence of numbers
      that follow a path down the tree. The path does not have to
      include the root.