Midterm 2 Review Session Problems
1. Classes
Daniel Chao, one of our awesome SLs, chose to work on a queue for his capstone project in the CS major. He calls it the CuteQ, and it’s meant to be used for office hours signups. It functions just as the Stanford Queue does, allowing for enqueue and dequeue and following a First In First Out (FIFO) ordering. We can think of the class interface for the CuteQ as follows:
class CuteQ {
public:
CuteQ(int capacity);
~CuteQ();
int size() const;
void enqueue(string student);
string dequeue();
private:
void swapElements(int index1, int index2);
};
Your task is to write the complete CuteQ class, including the declaration of the private member variables and the implementation of the constructor, destructor, and member functions.
Design: A CuteQ holds string values representing students. The required internal representation is a dynamic array of string. We require that the oldest element (which will be removed upon the next call to dequeue) should sit at index 0 within the array.
Constructor: In the constructor, you are to:
- Create an empty CuteQ with the inputted capacity as the capacity of the internal array. The array should be initialized to hold empty strings.
- Initialize all private instance variables and allocate any necessary dynamic memory.
- Note: you may assume that the inputted capacity is sufficiently large such that you will never need to resize your internal array.
Destructor: The destructor performs any needed cleanup and deallocation.
Enqueue a string: enqueue(student) adds a student to the CuteQ. This student should be appended to the end of the dynamic array.
- Again, you can assume that we will never need to expand the size of the internal array. Dequeue a string: dequeue() removes the first student in the CuteQ.
- If the client attempts to dequeue and the CuteQ is empty, you should raise an error.
- You should remove the element at the 0th index, since it was enqueued furthest ago.
- Once the 0th element has been removed, you should shift all elements to the right of that over by one. What was previously at index 1 should move to index 0, what was previously at index 2 should move to index 1, etc.
- You should include the necessary safeguards to ensure you’re not accessing invalid memory.
- We’ve provided a swapElements function that you can use and assume works correctly. It takes in two indices and swaps the string values stored there within your internal array.
Below is a sample client use of CuteQ. The comments show the contents of the internal array after each line of code executes.
CuteQ cq(5); // [ "", "", "", "", "" ]
cout << cq.size() << endl; // prints 0
cq.enqueue("Chris"); // [ "Chris", "", "", "", "" ]
cq.enqueue("Clinton"); // [ "Chris", "Clinton", "", "", "" ]
cq.enqueue("Daniel"); // [ "Chris", "Clinton", "Daniel", "", ""]
cout << cq.size() << endl; // prints 3
cout << cq.dequeue() << endl; // prints "Chris"
// [ "Clinton", "Daniel", "", "", "" ]
cout << cq.dequeue() << endl; // prints "Clinton"
// [ "Daniel", "", "", "", ""]
(1a) Complete the CuteQ class implementation by declaring the private member variables.
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);
// TODO: declare private member variables
}
(1b) Write the full implementation of the CuteQ class.
CuteQ::CuteQ(int capacity) {
}
CuteQ::~CuteQ() {
}
int CuteQ::size() const {
}
void CuteQ::enqueue(string student) {
}
string CuteQ::dequeue() {
}
2. Binary Heaps!
Imagine that we have changed our implementation of the Priority Queue ADT so that it uses a binary max-heap (largest number has the highest priority).
(2a) Draw a diagram of the tree shape of the heap after enqueuing the following priorities in the order given: 15, 3, 2, 20, 1, 5 (for this priority queue we don’t have a separate value, just the priority). Your diagram should be a tree shape with circles for nodes (containing the int key for that node).
(2b) Continuing from the final heap in part (a), draw a diagram of the tree shape of the heap after calling dequeue twice.
3. Memory Diagram
(3a) Draw out a stack/heap memory diagram for the following snippet of code!
struct Beverage {
string name;
int mgCaffeine;
};
struct SectionLeader {
string name;
Beverage* favBeverage;
int numQuartersSLing;
};
SectionLeader* SLs = new SectionLeader[3];
SLs[0].name = "Anushka";
SLs[1].name = "Tommy";
SLs[2].name = "Lucas";
SLs[0].numQuartersSLing = 2;
SLs[1].numQuartersSLing = 7;
SLs[2].numQuartersSLing = 3;
Beverage* matcha = new Beverage;
matcha->name = "matcha latte";
matcha->mgCaffeine = 65;
Beverage* coffee = new Beverage;
coffee->name = "Tokyo latte"
SLs[0].favBeverage = matcha;
SLs[1].favBeverage = coffee;
SLs[2].favBeverage = matcha;
coffee->mgCaffeine = 2 * (SLs[2].numQuartersSLing) + 3 * (matcha->mgCaffeine);
int* caffeine = &((SLs[0].favBeverage)->mgCaffeine);
// What does this print?
cout << "Today I have consumed " << *caffeine << " mg of caffeine." << endl;
// DRAW THE MEMORY AS IT LOOKS HERE!
(3b) If we changed our diagram from having the Tokyo latte Beverage box be moved from the heap side to the stack side, what changes in our code would we have to make to reflect that?
4. Backtracking
In this problem, you will be given a vector of pirateT structs. The struct definition is as follows:
struct pirateT
{
string pirateName; // All names are guaranteed to be unique.
int timeOwed; // timeOwed is given in minutes.
};
Each pirate in the vector is indebted to Captain Bianca Trost and is a member of her crew. Their debts are measured in time owed (in minutes) performing favors for the captain. The captain is curious whether, given a particular vector of pirates (all of whom have timeOwed > 0), she could call in their favors to create a rotation where some subset of them would take turns standing watch throughout the night over a valuable treasure she has recently brought aboard her ship. She has some stipulations for the watch rotation, though:
- The treasure must be under continuous watch through the night, which lasts for 480 minutes (8 hours).
- There should be only one pirate on watch at a time, so as not to double-dip into the debts they owe her.
- No pirate can spend more time on watch than what they owe to the captain.
- No pirate can spend more than 60 minutes on watch regardless of how much time they owe the captain, as she’s worried about them dozing off if required to stand watch for too long.
- No pirate can serve more than one shift on watch. So, there is no benefit to us having a pirate spend less than the maximum time they are able to spend on their watch.
- Not all of the pirates are on good terms, and Captain Trost intends to use this to her advantage. No pirate can immediately follow another pirate in the watch rotation if those two pirates are on decent terms; they must instead be rivals. Captain Trost often does that to ensure that a changing of the guard has less of a chance of leading to a friendly conversation where two pirates might end up starting to plot a mutiny against her.
- Luckily for her, the pirates on her ship are a dastardly group and have many bitter and deep-seated rivalries. She maintains a rivals map of type Map<string, Map<string, bool». In this map, rivals[name1][name2] is true if the two pirates are rivals. Otherwise, the value is false.
- So, if our watch rotation is {A, B, C, D, E, F, G, H}, then A and B must be rivals, and B and C must be rivals, but it doesn’t matter whether A and C are rivals or not.
- We don’t necessarily have to use all the pirates in the vector. It might be possible to accomplish this task with a subset of them.
Write a recursive backtracking function that takes a vector of pirates and determines if it’s possible to set up a 480-minute watch that satisfies the conditions above. Return true if so, false otherwise.
In solving this problem, you must abide by the following guidelines and restrictions:
- Your algorithm must be recursive and must use backtracking techniques to generate its results.
- You can use a vector to keep track of the pirate watch rotation you are building, if you wish. Beyond that, you must not create any auxiliary data structures.
- You can never modify the contents of a pirateT struct. You may add and remove structs from the crew vector, but you cannot change the contents of an individual struct. You also cannot modify copies of any of these structs.
- You should only explore sequences that could potentially lead to valid results. As soon as it becomes clear that a sequence you have generated cannot lead to any valid results, stop exploring that dead-end path.
- You should not iterate over the rivals map. Use it to determine whether two given pirates are rivals – not to get a list of rivals for a given pirate.
bool canGuard(Vector<pirateT> crew, Map<string, Map<string, bool>>& rivals) {
}