# Revision Exercise - 1

## Exercise 1 - Frog Hopping Simulation

The question involves reasoning about a simulation of a frog hopping in a straight line. The frog attempts to hop to a goal within a specified number of hops.

The simulation is to be encapsulated in a `FrogSimulation` class. You will write two of the methods in this class.

```cpp
class FrogSimulation {
private:
    // Distance, in inches, from the starting position to the goal 
    int goalDistance;
    // Maximum number of hops allowed to reach the goal
    int maxHops;
    
public: 
    // Constructs a `FrogSimulation` where `dist` is the distance, in inches, from
    // the starting position to the goal, and `numHops` is the maximum number of
    // hops allowed to reach the goal. 
    FrogSimulation(int dist, int numHops): goalDistance(dist), maxHops(numHops) {};
    
    // Returns a random integer between 1-10 representing the distance, in inches, 
    // to be moved when the frog hops 
    int hopDistance() {
        return (rand() % 20) - 10; 
    }
    
    // Simulates a frog attempting to reach the goal as described in part (a)
    // Returns `true` if the frog successfully reached or passed the goal during
    // the simulation, `false` otherwise. 
    bool simulate() {
        // To be implemented in part 1
    }
    
    // Runs `num` simulations and returns the proportion of simulations in which
    // the frog successfully reached or passed the goal. 
    double runSimulations(int num) {
        // To be implemented in part 2
    }
}
```

### Part 1&#x20;

Write the `simulate` method, which simulates the frog attempting to hop in a straight line to a goal from an initial position of 0 within a maximum number of hops.&#x20;

The method returns `true` if the frog successfully reached the goal within the maximum number of hops, and returns `false` otherwise.

The `FrogSimulation` class provides a method called `hopDistance` that returns a random integer between -10 and 10, representing the distance to be moved when the frog hops. A negative distance represents the frog hopping *away* from the goal. The value returned will vary from call to call.&#x20;

The frog hops until one of the following conditions becomes true:

* The frog has reached or passed the goal&#x20;
* The frog has reached a negative position
* The frog has taken the maximum number of hops without reaching the goal

#### Example&#x20;

The following example shows a declaration of a `FrogSimulation` object with a goal distance of 24 inches and maximum number of hops of 5. The table shows some possible outcomes when the `simulate` method is invoked.&#x20;

| Example | Values returned by `hopDistance` | Final position of the frog | Return value of `simulate` |
| ------- | -------------------------------- | -------------------------- | -------------------------- |
| 1       | 5, 7, -2, 8, 6                   | 24                         | true                       |
| 2       | 6, 7, 6, 6                       | 25                         | true                       |
| 3       | 6, -6, 31                        | 31                         | true                       |
| 4       | 4, 2, -8                         | -2                         | false                      |
| 5       | 5, 4, 2, 4, 3                    | 18                         | false                      |

### Part 2&#x20;

Write the `runSimulations` method, which performs a given number of simulations and returns the proportion of simulations in which the frog successfully reached or passed the goal. For example, if the parameter passed to `runSimulations` is 400, and 100 of the 400 `simulate` method calls returned `true`, then the `runSimulations` method should return 0.25.&#x20;

## Exercise 2 - Word Pairs&#x20;

This question involves reasoning about pairs of words that are to be represented by the following `WordPair` class.&#x20;

```cpp
class WordPair {
public: 
    // Constructs a WordPair object
    WordPair(std::string first, std::string, second); 
    // Returns the first string of this WordPair object 
    std::string getFirst();
    // Returns the second string of this WordPair object
    std::string getSecond();
}
```

### Part 0&#x20;

Fully implement the `WordPair` class - its constructor and the `getFirst` and `getSecond` methods.&#x20;

### Part 1&#x20;

You will implement the constructor and another method for the following `WordPairList` class:

```cpp
class WordPairList 
{
private:
    // The list of all word pairs
    std::vector<WordPair> allPairs;
    
public:
    // Construfts a WordPairList object as described in Part 1
    WordPairList(std::vector<std::string> words) {
    }
    
    // Returns the number of matches as described in Part 2
    int numMatches() {
    }
}
```

Write the constructor for the `WordPairList` class. The constructor takes a vector of strings, `words`, as a parameter and populates the `allPairs` member variable as a vector of `WordPair` objects.

A `WordPair` object consists of a word from the array paired with a word that appears later in the array. The `allPairs` vector should contain every possible pair of words from `words`, with each pair occurring only once.&#x20;

#### Example 1

```cpp
std::vector<std::string> words = {"one", "two", "three"};
WordPairList wpl_one = WordPairList(words);
```

After the constructor has executed, the `allPairs` member variable of `wpl_one` should contain the following `WordPair` objects:

```cpp
("one", "two"), ("one", "three"), ("two, three")
```

#### Example 2&#x20;

```cpp
std::vector<std::string> words = {"the", "more", "the", "merrier"};
WordPairList wpl_two = WordPairList(words);
```

After the constructor has executed, the `allPairs` member variable of `wpl_two` should contain the following `WordPair` objects:

```cpp
("the", "more"), ("the", "the"), ("the", "merrier"), 
("more", "the"), ("more", "merrier"), ("the", "merrier")
```

### Part 2&#x20;

Write the `WordPairList` method `numMatches`. This method returns the number of `WordPair` objects in `allPairs` for which its first and second strings match.&#x20;

#### Example&#x20;

```cpp
std::vector<std::string> words = {"the", "red", "fox", "the"};
WordPairList wpl_three = WordPairList(words);
```

After the constructor has executed, the `allPairs` member variable of `wpl_three` should contain the following `WordPair` objects:

```cpp
("the", "red"),
("the", "fox"),
("the", "the"),  // MATCHES
("red", "fox"),
("red", "the"),
("fox", "the")
```

The call to `wpl_three.numMatches()` should therefore return 1.&#x20;

## Example 3 - Array Reasoning&#x20;

This question involves reasoning about one-dimensional and two-dimensional arrays of integers. The first method returns the sum of the values of a one-dimensional array; the second method returns an array that represents the sum of the rows of a two-dimensional array; and the third method analyses the row sums.&#x20;

### Part 1&#x20;

Write a method `arraySum` that calculates and returns the sum of the elements in a one-dimensional array.&#x20;

```cpp
int arraySum(int* arr, int length) {
   // to be implemented 
}
```

### Part 2&#x20;

Write a method `rowSums` that calculates the sums of each row in a given two-dimensional array and returns these sums in a one-dimensional array.&#x20;

The method has three parameters, a two-dimension array, `int** arr2D` of integer values, the number of rows, `int rows`, and the number of columns, `int cols`.&#x20;

The method returns a one-dimensional array with one element for each row of `arr2D` such that each element is the sum of the corresponding row in `arr2D`.&#x20;

```cpp
int* rowSums(int** arr2D, int rows, int cols) {
    // to be implemented
}
```

#### Example&#x20;

For example, if the below is the two-dimensional array represented by `arr2D`:

```cpp
{
    {1, 3, 2, 7, 3},
    {10, 10, 4, 6, 2},
    {5, 3, 5, 9, 6},
    {7, 8, 4, 2, 1},
}
```

Then the call `rowSums(arr2D, 4, 5)` should return a pointer to the array `{16, 32, 28, 20}`.

The length of the array to be returned can be determined by the number of rows in `arr2D`, which is information that the function caller should already have.&#x20;

### Part 3&#x20;

A two-dimensional array is **diverse** if no two of its rows sum to the same value:

```cpp
{
    {1, 3, 2, 7, 3},   // 16
    {10, 10, 4, 6, 2}, // 32
    {5, 3, 5, 9, 6},   // 28
    {7, 8, 4, 2, 1},   // 20 
}
```

The above two-dimensional array is **diverse** because each row sums to a different value.&#x20;

```cpp
{
    {1, 1, 5, 3, 4},   // 14
    {12, 7, 6, 1, 9},  // 35
    {8, 11, 10, 2, 5}, // 36
    {3, 2, 3, 0, 6},   // 14 
}
```

The above two-dimensional array is **not diverse** because rows 0 and 3 sum to the same value 14.

Write a method `isDiverse` that determines whether a given two-dimensional array is diverse. The method has three parameters much like the `rowSums` method: a two-dimension array, `int** arr2D` of integer values, the number of rows, `int rows`, and the number of columns, `int cols`.&#x20;

The method should return `true` if all row sums are unique; otherwise it should return `false`.&#x20;

## Example 4 - Sparse Arrays&#x20;

A two-dimensional array of integers in which most elements are zero is called a **sparse array**. Sparse in this context meaning thinly dispersed, or scattered.&#x20;

Imagine a image of the night sky, with a resolution of 1000x1000 pixels. Such an image would have 1 million pixels. Let's assume that this is represented by a two-dimensional boolean array, where a value of `true` indicates that the pixel is white (a star), and a value of `false` indicates that the pixel is black (the sky).&#x20;

If the image only has a handful of stars, we are using 1 million bytes to store information on those handful of stars. We can leverage the **sparse** characteristic of this problem and store instead the non-zero values in the sparse array.&#x20;

### Part 0 (Nothing to do here)

The following `SparseArrayEntry` class is used to represent a non-zero element in a sparse array.&#x20;

```cpp
struct SparseArrayEntry {
    const int row;
    const int col; 
    const int value;
    
    SparseArrayEntry(int r, int c, int v): row(r), col(c), value(v) {}
}
```

Because of the `const` qualifiers on its member variables, a `SparseArrayEntry` cannot be modified once it is constructed.&#x20;

### Part 1&#x20;

The `SparseArray` class represents a sparse array. It contains a vector of `SparseArrayEntry` objects, each representing one of the non-zero elements in the sparse array.&#x20;

The elements representing the non-zero elements are stored in this vector in no particular order.

Each non-zero element is represented in this vector exactly once.&#x20;

```cpp
class SparseArray {
private:
    // Number of rows and columns in the sparse array
    int numRows;
    int numCols; 
    // The list of entries representing the non-zero elements of the 
    // sparse array. Entries are stored in the list in no particular
    // order.
    std::vector<SparseArrayEntry*> entries;

public:
    // Constructs an empty SparseArray of a given size
    SparseArray(int rows, int cols): numRows(rows), numCols(cols) {}
    
    // Adds an entry to the sparse array with the value `value` at 
    // row and column `row`, `col` respectively.
    int addEntry(int row, int col, int value) {
        // Implemented in Part 2
    }
    
    // Returns the number of rows in the sparse array
    int getRows() {
        return numRows;
    }
    
    // Returns the number of columns in the sparse array
    int getCols() {
        return numCols;
    }
    
    // Returns the value of the element at index `row` and column 
    // index `col` in the sparse array 
    int getValueAt(int row, int col) {
        // Implemented in Part 3
    }
    
    // Removes the column `col` from the sparse array 
    void removeColumn(int col) {
        // Implemented in Part 4
    }
    
    ~SparseArray() {
        // Implemented in Part 5
    }
}
```

### Part 2&#x20;

Write the `addEntry` method for `SparseArray`. This method should take 3 parameters, which correspond to the parameters for the constructor of a `SparseArrayEntry`.&#x20;

This method should add a new entry to the `entries` member variable.&#x20;

Bear in mind that the `entries` member variable is an array of `SparseArrayEntry*` (pointers), so each `SparseArrayEntry` object is to be created dynamically.&#x20;

### Part 3&#x20;

Write the `getValueAt` method for `SparseArray`. The method returns the value of the sparse array element at a given row and column in the sparse array.&#x20;

If the vector `entries` contains an entry with the specified `row` and `column`, the value associated with the entry is returned. If there is no entry in `entries` corresponding to the specified row and column, `0` is returned.&#x20;

### Part 4&#x20;

Write the `removeColumn` method for `SparseArray`. After removing a specified column from the sparse array:

* All entries in the list `entries` with column indices matching `col` are removed from the list&#x20;
* All entries in the list `entries` with column indices greater than `col` (to the right of the column being removed) are replaced with entries with column indices that are decremented by one (moved one column to the left)
* The number of columns in the sparse array, `numCols`, is adjusted to reflect the column removed

#### Example

Given the following sparse array:&#x20;

![](https://4122513583-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MSrqC8yBLK9rXNyJ6ol%2F-MZ7DBU3wowO8vaQbZyF%2F-MZ7MQbpt38JBHRxfKmg%2Fimage.png?alt=media\&token=144f4901-b6c7-417e-8973-f7d878808059)

A sample two-dimensional sparse array is shown above. Empty cells in the table indices zero values. The column to be removed here is the column 1 (shaded).&#x20;

The shaded entries in `entries` correspond to the ones in the shaded column above:

![](https://4122513583-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MSrqC8yBLK9rXNyJ6ol%2F-MZ7DBU3wowO8vaQbZyF%2F-MZ7MlXK4y77mTggXIzy%2Fimage.png?alt=media\&token=e3f4f1b7-f1c3-4911-b559-fdcb71e708f8)

When `removeColumn(1)` is called, below should be the new state of the `SparseArray`. The shaded properties below show the changes:

![](https://4122513583-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MSrqC8yBLK9rXNyJ6ol%2F-MZ7DBU3wowO8vaQbZyF%2F-MZ7MzmqN9A9j6huoJ7q%2Fimage.png?alt=media\&token=af0ac534-1639-49b3-a03f-c00a5de690d6)

As observed, the entries corresponding to values `-9` and `5` have been removed. And the entry corresponding to the value `4` has its `col` decremented by one.&#x20;
