Midterm 2 Review Session Solutions

1. Classes

(1a)

class CuteQ {
public:
CuteQ(int capacity); // Constructor
~CuteQ(); // Destructor
int size() const; // Returns the number of students in the CuteQ
void enqueue(std::string student); // Adds a student to back of the CuteQ
string dequeue(); // Removes and returns the student at index 0
private:
// Swap strings at index1 and index 2 within internal array
void swapElements(int index1, int index2);

int _size;
int _capacity;
string* _elements;

(1b)

CuteQ::CuteQ(int capacity) {
    _size = 0;
    _capacity = capacity;
    _elements = new string[_capacity];
}

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

int CuteQ::size() const {
    return _size;
}

void CuteQ::enqueue(string student) {
    _elements[_size] = student;
    _size++;
}

string CuteQ::dequeue() {
    if (_size == 0) error("Can't dequeue from an empty CuteQ!");
    string res = _elements[0];
    for (int i = 1; i < _size; i++) {
        swapElements(i, i - 1);
    }
    _size--;
    return res;
}

2. Binary Heaps

(2a)

(2b)

3. Memory Diagram

(3a) Here is what the diagram should look like after part (a). The print statement should print out: “Today I have consumed 65 mg of caffeine.”

(3b) We should replace the line

Beverage* coffee = new Beverage;

with

Beverage tokyoLatte;
Beverage* coffee = &tokyoLatte;

4. Backtracking

bool canGuardHelper(Vector<pirateT> crew, Map<string, Map<string, bool>>& rivals, int timeRemaining, Vector<pirateT> shiftsSoFar) {
    if (timeRemaining <= 0) {
        return true;
    }

    pirateT prevPirate;
    if (!shiftsSoFar.isEmpty()) {
        prevPirate = shiftsSoFar[shiftsSoFar.size() - 1];
    }

    for (int i = 0; i < crew.size(); i++) {
        pirateT nextPirate = crew[i];
        if (shiftsSoFar.isEmpty() || rivals[prevPirate.pirateName][nextPirate.pirateName]) {
            crew.remove(i);
            if (canGuardHelper(crew, rivals, timeRemaining - min(nextPirate.timeOwed, 60), shiftsSoFar + nextPirate)) {
                return true;
            }
            crew.insert(nextPirate, i);
        }
    }

    return false;
}

bool canGuard(Vector<pirateT> crew, Map<string, Map<string, bool>>& rivals) {
    return canGuardHelper(crew, rivals, 480, {});
}