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, {});
}