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 )
```

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

- Design a O(N) algorithm to determine whether the list contains a cycle. You may use O(N) extra space
- 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.)

- The number of leaves in T
- The number of nodes in T that contain one non-null child
- The number of nodes in T that contain two non-null children

- The sum of all the items in the tree
- The number of nodes with two children that contain the same value
- 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.