Programming Lab 4 : Fundamental Data Structures, Arrays, Encryption

and Linked Lists

CSCI-UA 9102, Data Structures

Exercise 1: Playing with arrays and generics

Exercise 2: Encryption

- Exercise 1.1. Let A be an array of size n>=2 containing integers from 1 to n-1 inclusive one of which is repeated. Provide an algorithm for finding the integer in A that is repeated

- Exercise 1.2. Implement the method whose specification is provided below and which tests whether an array has four consecutive numbers with the same value. Write a test program that prompts the user to enter a series of integers and displays it if the series contains four consecutive numbers with the same value. Your program should first prompt the user to enter input size (i.e. the number of values in the series)

```
public static boolean isConsecutiveFour(int[] values)
```

- Exercise 1.3.

In computational geometry, often you need to find the rightmost lowest point in a series of points. Implement the method ‘getRightmostLowestPoint’ given below that should return the rightmost lowest point from a set of points. Write a test program that prompts the user to enter coordinates of six points and then displays the rightmost lowest point.

```
public static double getRightmostLowestPoint(double[][] points)
```

- Exercise 1.4.

Let B be an array of size n>=6 containing integers from 1 to n-5 inclusive, five of which are repeated. Provide an algorithm for finding the five integers in B that are repeated.

- Exercise 1.5.

Write a Java method that takes two three dimensional integer arrays and adds them componentwise

- Exercise 1.6.

Write a generic method to exchange the positions of two different elements in an array.

- Exercise 1.7.

Consider the generic ‘Pair’ class below. Add a method swap to the Pair class that swaps the first and second elements of the pair

```
public class Pair < T, S >
{
public Pair(T firstElement, S secondElement)
{
first = firstElement;
second = secondElement;
}
public T getFirst() { return first; }
public S getSecond() { return second; }
private T first;
private S second;
}
```

- Exercise 1.8.
Write a generic method to exchange the positions of two different elements in an array

- Exercise 1.9.

Consider the interface comparable that is given below. This interface only requires its implementations to provide a comparison between objects. Given this interface we can define a generic Method which returns the maximum entry in a give list. The signature of such a method is provided below. Give an implementation of this method. Then write a program that prompts the user to enter 10 integers, invoke this method to find the max and display the maximum number.

```
public static < E extends Comparable < E > > E max(E[] list)
```

```
// Interface for comparing objects defined in java.lang
package java.lang
public interface Comparable < E > {
public int compareTo(E o);
}
```

- Exercise 1.10.

Extend your solution from Exercise 1.7 and provide an implementation for a Comparable method that returns the maximum element from a two dimensional array.

```
public static < E extends Comparable < E > > E max(E[][] list)
```

- Exercise 1.11.

Provide an implementation for the generic method ‘sort’ whose signature is provided below. The ArrayList Specification can be found on the oracle website

```
public static < E extends Comparable < E > > void sort(ArrayList< E > list)
```

Exercise 2: Encryption

- Exercise 2.1. Write a Java program that can perform the Caesar cipher for English messages that include both upper and lower case letters

- Exercise 2.2. Write a Java program that can decipher a Caesar cipher code without having access to the decoder

- Exercise 2.3. We consider a new encryption scheme which we name SubstitutionCipher. This new scheme will be represented by a constructor which takes as argument a string with the 26 uppercase letters in an arbitrary order and uses that as the encoder (that is A is mapped to the first character of the string, B is mapped to the second, and so on). You should derive the decoder from the encoder.

- Exercise 2.4. Design a random cipher class as a subclass of the SubstitutionCipher so that each instance of the class relies on a random permutation of letters for its encoder.

Exercise 3: Linked Lists

- Exercise 3.1.

Give an algorithm for finding the second to last node in a singly linked list in which the last node is indicated by a null reference

- Exercise 3.2.

Give an algorithm for concatenating two singly linked lists L and M, into a singly linked list L’ that contains all the nodes of L followed by the all the nodes of M

- Exercise 3.3.

Consider the class given below: