Section4: Mid-Quarter Review and Object-Oriented Programming

Section materials curated by our Head TA Trip Master, drawing upon materials from previous quarters. Special thanks to
Nick Bowman and Julie Zelenski for awesome ideas!

This week’s section exercises fall into 2 categories: the first half of the handout will provide review problems for your upcoming assessment, and the latter half will consist of some more complex backtracking examples along with a forray into OOP. If you're working on OOP, you may find this Classes and Objects Syntax Sheet to be helpful.

Remember that every week we will also be releasing a Qt Creator project containing starter code and testing infrastructure for that week's section problems. When a problem name is followed by the name of a .cpp file, that means you can practice writing the code for that problem in the named file of the Qt Creator project. Here is the zip of the section starter code:

📦 Starter code

1) String Processing (strings.cpp)

Write a function

that reverses a string “in-place.” That is, you should take the string to reverse as a reference parameter and modify it so that it ends up holding its reverse. Your function should use only O(1) auxiliary space.

Now, imagine you have a string containing a bunch of words from a sentence. Here’s a nifty little algorithm for reversing the order of the words in the sentence: reverse each individual string in the sentence, then reverse the entire resulting string. (Try it – it works!) Go and code a function

that accomplishes this task and uses only O(1) auxiliary storage space.

void reverseInPlace(string& str) {
    /* We need to make sure to only loop up to halfway though the string
    * or we will end up with the original string! Try it out on
    * paper if this isn't clear.
    */
    for (int i = 0; i < str.length() / 2; i++) {
        char temp = str[i];
        str[i] = str[str.length () - 1 - i]; // Question: Why is the -1 here?
        str[str.length () - 1 - i] = temp;
    }
}

/* Essentially the same function as before, except that we specify our own start
 * and end indices so we can reverse parts of a string rather than the whole
 * string at each point. The end index is presumed to be one past the end of the
 * substring in question.
 */
void reverseInPlace(string& str, int start, int end) {
    for (int i = 0; i < (end - start) / 2; i++) {
        char temp = str[start + i];
        str[start + i] = str[end - 1 - i];
        str[end - 1 - i] = temp;
    }
}
void reverseWordOrderingIn(string& sentence) {
    /* Scan across the sentence looking for words. The start variable holds the
    *  index of the start point of the current word in the sentence. The variable
    *  i holds the index of the character we're currently scanning.
    */
    int start = 0;
    for (int i = 0; i < sentence.length(); i++) {
        if (sentence[i] == ' ') {
            reverseInPlace(sentence, start, i);
            start = i + 1;
        }
    }
 
    /* We need to account for the fact that there might be a word 
    * flush up at the end of the sentence.
    */
    reverseInPlace(sentence, start, sentence.length());
    
    /* Now reverse everything. */
    reverseInPlace(sentence, 0, sentence.length());
}

2) Container Classes (adts.cpp)

Write a function

that, given a Map<string, int> that associates string values with integers, produces a Map<int, Set<string>> that’s essentially the reverse mapping, associating each integer value with the set of strings that map to it. (This is an old job interview question from 2010.)

Then, consider the following problem. A compound word is a word that can be cut into two smaller strings, each of which is itself a word. The words “keyhole” and “headhunter” are examples of compound words, and less obviously so is the word “question” (“quest” and “ion”). Write a function

that takes in a Lexicon of all the words in English and then prints out all the compound words in the English language.

Map<int, Set<string>> reverseMap(Map<string, int>& map) {
    Map<int, Set<string>> result;
    for (string oldKey : map) {
        if (!result.containsKey(map[oldKey])){
            result[map[oldKey]] = {};
        }
        result[map[oldKey]].add(oldKey);
    }
    return result;
}


bool isCompoundWord(string& word, Lexicon& dict) {
    /* Try splitting the word into two possible words for 
    * every possible position where you can make the split.
    */
    
    for (int i = 1; i < word.length(); i++) {
        /* The two words are formed by taking the substring up to the splitting
        * point and the substring starting at the splitting point.
        */
        if (dict.contains(word.substr(0, i)) && dict.contains(word.substr(i))) {
            return true;
        }
    }
    return false;
}
    
void printCompoundWords(Lexicon &dict) {
     for (string word: dict) {
        if (isCompoundWord(word, dict)) cout << word << endl;
     }
}

3) Big O

Below are eight functions. Determine the big-O runtime of each of those pieces of code.

void function1(int n) {
    for (int i = 0; i < n; i++) {
        cout << '*' << endl;
    }
}

void function2(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << '*' << endl;
        }
    }
}

void function3(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            cout << '*' << endl;
        }
    }
}

void function4(int n) {
    for (int i = 1; i <= n; i *= 2) {
        cout << '*' << endl;
    }
}

void function5(int n) {
    if (n == 0) return;
    function5(n - 1);
}

void function6(int n) {
    if (n == 0) return;
    function6(n - 1);
    function6(n - 1);
}

void function7(int n) {
    if (n == 0) return;
    function7(n / 2);
}

void function8(int n) {
    if (n == 0) return;
    for (int i = 0; i < n; i++) {
        cout << '*' << endl;
    }
    function8(n / 2);
    function8(n / 2);
}

Finally, what is the big-O runtime of this function in terms of n, the number of elements in v?

int squigglebah(Vector<int>& v) {
    int result = 0;
    for (int i = 0; i < v.size(); i++) {
        Vector<int> values = v.subList(0, i);
        for (int j = 0; j < values.size(); j++) {
            result += values[j];
        }
    }
    return result;
}

int squigglebah(Vector<int>& v) {
    int result = 0;
    for (int i = 0; i < v.size(); i++) {
        Vector<int> values = v.subList(0, i);
        do O(i) work;
    }
    return result;
}

int squigglebah(Vector<int>& v) {
    int result = 0;
    for (int i = 0; i < v.size(); i++) {
        do O(i) work;
        do O(i) work;
    }
    return result;
}

int squigglebah(Vector<int>& v) {
    int result = 0;
    for (int i = 0; i < v.size(); i++) {
        do O(i) work;
    }
    return result;
}

4) Recursion (recursion.cpp)

Imagine you have a 2 × n grid that you’d like to cover using 2 × 1 dominoes. The dominoes need to be completely contained within the grid (so they can’t hang over the sides), can’t overlap, and have to be at 90° angles (so you can’t have diagonal or tilted tiles). There’s exactly one way to tile a 2 × 1 grid this way, exactly two ways to tile a 2 × 2 grid this way, and exactly three ways to tile a 2 × 3 grid this way (can you see what they are?) Write a recursive function

that, given a number n, returns the number of ways you can tile a 2 × n grid with 2 × 1 dominoes.

int numWaysToTile(int n) {
    /* There's one way to tile a 2 x 0 grid: put down no dominoes. */
    if (n == 0) return 1;

    /* There's one way to tile a 2 x 1 grid: put down a vertical domino. */
    if (n == 1) return 1;
    
    /* Recursive case: Use the above insight. */
    return numWaysToTile(n - 1) + numWaysToTile(n - 2);
}

🛑Note:🛑 The material beyond this point moves to the current week's material: more recursive backtracking and OOP.

5) Splitting the bill (bill.cpp)

You’ve gone out for coffees with a bunch of your friends and the waiter has just brought back the bill. How should you pay for it? One option would be to draw straws and have the loser pay for the whole thing. Another option would be to have everyone pay evenly. A third option would be to have everyone pay for just what they ordered. And then there are a ton of other options that we haven’t even listed here!

Your task is to write a function

void listPossiblePayments(int total, Set<string>& people)

that takes as input a total amount of money to pay (in dollars) and a set of all the people who ordered something, then lists off every possible way you could split the bill, assuming everyone pays a whole number of dollars. For example, if the bill was $4 and there were three people at the lunch (call them A, B, and C), your function might list off these options:

A: $4, B: $0, C: $0
A: $3, B: $1, C: $0
A: $3, B: $0, C: $1
A: $2, B: $2, C: $0
A: $2, B: $1, C: $1
A: $2, B: $0, C: $1
…
A: $0, B: $1, C: $3
A: $0, B: $0, C: $4

Some notes on this problem:

• The total amount owed will always be nonnegative. If the total owed is negative, you should use the error() function to report an error.
• There is always at least one person in the set of people. If not, you should report an error.
• You can list off the possible payment options in any order that you’d like. Just don’t list the same option twice.
• The output you produce should indicate which person pays which amount, but aside from that it doesn’t have to exactly match the format listed above. Anything that correctly reports the payment amounts will get the job done.

/*
 * Lists off all ways that the set of people can pay a certain total, assuming
 * that some number of people have already committed to a given set of payments.
 *
 * @param total The total amount to pay.
 * @param people Who needs to pay.
 * @param payments The payments that have been set up so far.
 */
void listPossiblePaymentsRec(int total, Set<string>& people, 
                Map<string, int>& payments) {
    /* Base case: if one person left, they have to pay the whole bill.*/
    if (people.size() == 1) {
        Map<string, int> finalPayments = payments;
        finalPayments[people.first()] = total;
        cout << finalPayments << endl;
    }
    /* Recursive case: The first person has to pay some amount between 0 and 
    * the total amount. Try all of those possibilities.
    */
    else {
        for (int payment = 0; payment <= total; payment++) {
            /* Create a new assignment of people to payments in which 
            * this first person pays this amount. 
            */
            Map<string, int> updatedPayments = payments;
            updatedPayments[people.first()] = payment;
            Set<string> remainingPeople = people - people.first();
            listPossiblePaymentsRec(total - payment, remainingPeople,
                        updatedPayments);
        }
    }
}
void listPossiblePayments(int total, Set<string>& people) {
    /* Edge cases: we can't pay a negative total, and there must 
    *  be at least one person.
    */
    if (total < 0) error("Guess you're an employee?");
    if (people.isEmpty()) error("Dine and dash?");
    Map<string, int> payments;
    listPossiblePaymentsRec(total, people, payments);
}

6) Longest Common Subsequence (lcs.cpp)

Write a recursive function named longestCommonSubsequence that returns the longest common subsequence of two strings passed as arguments. Some example function calls and return values are shown below.

Recall that if a string is a subsequence of another, each of its letters occurs in the longer string in the same order, but not necessarily consecutively.

Hint: In the recursive case, compare the first character of each string. What one recursive call can you make if they are the same? What two recursive calls do you try if they are different?

longestCommonSubsequence("cs106a", "cs106b") --> "cs106" 
longestCommonSubsequence("nick", "julie") --> "i" 
longestCommonSubsequence("karel", "c++") --> "" 
longestCommonSubsequence("she sells", "seashells") --> "sesells"

string longestCommonSubsequence(string s1, string s2) {
    if (s1.length() == 0 || s2.length() == 0) {
        return "";
    } else if (s1[0] == s2[0]) {
        return s1[0] + longestCommonSubsequence(s1.substr(1), 
                            s2.substr(1));
    } else {
        string choice1 = longestCommonSubsequence(s1, s2.substr(1));
        string choice2 = longestCommonSubsequence(s1.substr(1), s2);
        if (choice1.length() >= choice2.length()) {
            return choice1;
        } else {
            return choice2;
        }
    }
}

7) Circle of Life (Circle.h/.cpp)

Topics: Classes

Write a class named Circle that stores information about a circle. Your class must implement the following public interface:

class Circle {
	// constructs a new circle with the given radius
	Circle(double r); 
	// returns the area occupied by the circle
	double area() const;
	// returns the distance around the circle 
	double circumference() const;

	// returns the radius as a real number
	double getRadius() const;
	// returns a string representation such as "Circle{radius=2.5}"
	string toString() const;
};

You are free to add any private member variables or methods that you think are necessary. It might help you to know that there is a global constant PI storing the approximate value of π, roughly 3.14159.

// .h file starts
#pragma once

class Circle {
public:
	Circle(double radius);

	double area() const;
	double circumference() const;
	double getRadius() const;
	string toString() const;
private:
	double r;
}

// .h file ends


// .cpp file starts 
#include "Circle.h"

using namespace std;

Circle::Circle(double radius) {
	r = radius;
}

double Circle::area() const{
	return PI * r * r;
}

double Circle::circumference() const{
	return 2 * PI * r;
}

double Circle::getRadius() const{
	return r;
}

string Circle::toString() const{
	return string("Circle{radius=") + realToString(r) + string("}");
}
// .cpp file ends

8) The Notorious RBQ (Ring Buffer Queue) (RingBufferQueue.h/.cpp)

Topics: Classes, dynamic arrays

Think back to week 2 when we studied collections. We learned about Queues, a "first-in, first-out" data structure. Today in section, we're going to implement a special type of queue called a Ring Buffer Queue. A Ring Buffer Queue, or RBQ, is implemented by using an underlying array. In our implementation, the capacity is capped; once the array is full, additional elements cannot be added until something is dequeued. Another "interesting" thing about RBQs is that we don't want to shift elements when an element is enqueued or dequeued. Instead, we want to keep track of the front and tail of the Queue. For example, say our queue can hold 5 elements and we enqueue 3 elements: 1, 2, 3. Our queue would look like this:

If we enqueued two more elements, our queue would then be full:

At this point, we cannot add any additional elements until we dequeue at least one element. Dequeuing will remove the element at head, and head will move onto the next element. If we dequeue 2 elements, our queue will look like this:

Now there's room to add more elements! Since we still don't want to shift any elements, adding an additional element will wrap around. So, if we enqueue an element, our queue will look like this:

Notice that the tail's index is less than the head's index!

Your job is to implement a RingBufferQueue class. Your class should have the following public methods:

You are welcome to add any private methods or fields that are necessary.

It can be hard to know where to start when writing an entire class, so we've given you this breakdown:

1. Start by identifying the private fields you will need, then write the constructor and destructor to initialize the fields and do any cleanup, if necessary. Questions to think about:
   • Is it easier to keep track of head and tail (as pictured in the diagrams above)? Or would it be better to track head and size?
2. Write isEmpty(), isFull(), size(), and peek(). Questions to think about:
   • Which of these methods can be const? In general, how do you know when a method can be const?
3. Write enqueue() and dequeue(). Remember to handle error conditions! Questions to think about:
   • Can you call the methods from part 2 to reduce redundancy?
   • Would using modular math help with wrapping around?
   • Should either of these methods be const?
4. Finally, deal with ostream insertion!

If you want more practice with writing classes, think about how you could modify this class to implement a double ended queue. (A double ended queue, or deque, is one where you can enqueue and dequeue from either the front or the back).

#pragma once 

#include <iostream>
class RBQueue {
public:
	/* Constructs a new empty queue. */
	RBQueue();
	
	~RBQueue();
 	
 	/* Returns true if the queue contains no elements. */
 	bool isEmpty() const;
	
	/* Returns true if no additional elements can be enqueued. */
	bool isFull() const;

	/* Returns number of elements in queue. */
	int size() const;

	/* Adds the given element to back of queue. */
	void enqueue(int elem);

	/*
	* Removes and returns the front element from the queue
	* Throws a string exception if the queue is empty.
	*/
	int dequeue();

	/*
	* Returns the front element from the queue without removing it.
	* Throws a string exception if the queue is empty.
	*/
	int peek() const;

private:
	// member variables (instance variables / fields)
	int* _elements;
	int _capacity;
	int _numUsed;
	int _head;
	
	// by listing this here as a "friend", it can access the private member variables
	friend std::ostream& operator <<(std::ostream& out, const RBQueue& queue);
};

#include "RingBufferQueue.h"

static int kDefaultCapacity = 10;

using namespace std;

RBQueue::RBQueue() {
	_capacity = kDefaultCapacity;
	_elements = new int[_capacity];
	_head = 0;
	_numUsed = 0;
}

RBQueue::~RBQueue() {
	delete[] _elements;
}

bool RBQueue::isEmpty() const {
	return _numUsed == 0;
}

bool RBQueue::isFull() const {
	return _numUsed == _capacity;
}

int RBQueue::size() const {
	return _numUsed;
}

int RBQueue::peek() const {
	if (isEmpty()) {
 		throw "Can't peek from an empty queue!";
	}
 	
 	return _elements[_head];
}

int RBQueue::dequeue() {
	if (isEmpty()) {
		throw "Can't dequeue from an empty queue!";
	}
	
	int front = _elements[_head];
	_head = (_head + 1) % _capacity;
	_numUsed--;
	return front;
}

void RBQueue::enqueue(int elem) {
	if (isFull()) {
		throw "Can't enqueue to already full queue!";
	}

	int tail = (_head + _numUsed) % _capacity;
	_elements[tail] = elem;
	_numUsed++;
}

ostream& operator <<(ostream& out, const RBQueue& queue) {
	out << "{";
 
	if (!queue.isEmpty()) {
		// we can access the inner '_elements' member variable because
		// this operator is declared as a 'friend' of the queue class
		out << queue._elements[queue._head];

		for (int i = 1; i < queue._numUsed; i++) {
			int index = (queue._head + i) % queue._capacity;
			out << ", " << queue._elements[index];
		}
	}
 
	out << "}";
	return out;
}