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.

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

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.

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.

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

  • The frog has reached or passed the goal

  • The frog has reached a negative position

  • The frog has taken the maximum number of hops without reaching the goal

Example

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.

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

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.

Exercise 2 - Word Pairs

This question involves reasoning about pairs of words that are to be represented by the following WordPair class. 

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

Fully implement the WordPair class - its constructor and the getFirst and getSecond methods.

Part 1

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

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.

Example 1

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:

("one", "two"), ("one", "three"), ("two, three")

Example 2 

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:

("the", "more"), ("the", "the"), ("the", "merrier"), 
("more", "the"), ("more", "merrier"), ("the", "merrier")

Part 2

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

Example 

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:

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

The call to wpl_three.numMatches() should therefore return 1.

Example 3 - Array Reasoning

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.

Part 1

Write a method arraySum that calculates and returns the sum of the elements in a one-dimensional array. 

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

Part 2

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.

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.

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. 

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

Example

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

{
    {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.

Part 3

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

{
    {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. 

{
    {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.

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

Example 4 - Sparse Arrays

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.

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

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.

Part 0 (Nothing to do here)

The following SparseArrayEntry class is used to represent a non-zero element in a sparse array. 

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.

Part 1

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.

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. 

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

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

This method should add a new entry to the entries member variable.

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

Part 3

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.

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.

Part 4

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

  • 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:

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

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

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

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.

PreviousPractice ResourcesNextRevision Exercise - 2

Last updated

Was this helpful?