Section8: Review
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 will be a collection of review problems from the last half of the class. We hope that you find these problems to be a good reflection on the many new skills you have developed over the course of the quarter. You've come a long way in 8 weeks! This handout is somewhat short to leave room for you to ask lots of questions to your wonderful Section Leader!
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) Recursive Enumeration and Backtracking (backtracking.cpp)
Given a positive integer n, write a function
void printSumsOf(int n)
that finds all ways of writing n as a sum of nonzero natural numbers. For example, given n = 3, you’d list off these options:
3, 2 + 1, 1 + 2, 1 + 1 + 1
Next, write a function
void listKOrderings(Set<string> choices, int k)
that, given a set of strings and a number k, lists all ways of choosing k elements
from that list, given that order does matter. For example, given the objects A, B, and C and k = 2, you’d list
A B, A C, B A, B C, C A, C B
Finally, we will revisit one of the problems from earlier in this handout. In particular, one of the problems from the "Container Classes" section of this handout discussed compound words, which are words that can be cut into two smaller pieces, each of which is a word. You can generalize this idea further if you allow the word to be chopped into even more pieces. For example, the word "longshoreman" can be split into "long," "shore," and "man," and "whatsoever" can be split into "what," "so," and "ever."" Write a function
void printMultCompoundWords(Lexicon& dict)
that takes in a Lexicon representing the English dictionary and prints out all words in the dictionary that can be split apart into two or more smaller pieces, each of which is itself an English word.
The key insight for the first problem is that some positive number has to come first in our ordering, so we can just try all possible ways of breaking off some initial bit and see what we find.
void printSumsOf(int n) {
/* Handle edge cases. */
if (n < 0) error("Can't make less than nothing from more than nothing.");
printSumsRec(n, {});
}
/* Print all ways to sum up to n, given that we've already broken off the numbers
* given in soFar.
*/
void printSumsRec(int n, Vector<int> soFar) {
/* Base case: Once n is zero, we need no more numbers. */
if (n == 0) {
printAsSum(soFar);
} else {
/* The next number can be anything between 1 and n, inclusive. */
for (int i = 1; i <= n; i++) {
printSumsRec(n - i, soFar + i);
}
}
}
/* Prints a Vector<int> nicely as a sum. */
void printAsSum(Vector<int>& sum) {
/* The empty sum prints as zero. */
if (sum.isEmpty()) {
cout << 0 << endl;
} else {
/* Print out each term, with plus signs interspersed. */
for (int i = 0; i < sum.size(); i++) {
cout << sum[i];
if (i + 1 != sum.size()) cout << " + ";
}
cout << endl;
}
}
The second problem is half combinations, half permutations. We use the permutations strategy of asking "what is the next term in our ordered list?" at each step, and the combinations strategy of cutting off our search as soon as we have enough terms.
void listKOrderings(Set<string> choices, int k) {
/* Quick edge case check: if we want more items than there are options, there
* are no orderings we can use.
*/
if (k < choices.size()) {
listOrderingHelper(choices, k, {});
}
}
void listOrderingHelper(Set<string> choices, int k, Vector<string> soFar) {
/* Base case: If no more terms are needed, print what we have. */
if (k == 0) {
cout << soFar << endl;
}
/* Recursive case: What comes next? Try all options. */
else {
for (string choice: choices) {
listOrderingHelper(choices - choice, k - 1, soFar + choice);
}
}
}
The main insight for the final problem is that a word can be broken apart into two or more words if it can be split into two pieces such that the first piece is a word, and the second piece is either (1) a word or (2) itself something that can be split apart into two or more words.
void printMultCompoundWords(Lexicon& dict) {
for (string word : dict) {
if (isMultCompoundWord(word, dict)) {
cout << word << endl;
}
}
}
bool isMultCompoundWord(string word, Lexicon& dict) {
/* In an unusual twist, our base case is folded into the recursive step. We
* will try all possible splits into two pieces, and if one of them happens
* to be a pair of words, we stop.
*/
/* Try all ways of splitting things. */
for (int i = 1; i < word.length(); i++) {
/* Only split if the first part is a word. */
if (dict.contains(word.substr(0, i))) {
string remaining = word.substr(i);
/* We're done if the remainder is either a word or a compound word. */
if (dict.contains(remaining) || isMultCompoundWord(remaining, dict)) {
return true;
}
}
}
/* Nothing works; give up. */
return false;
}
2) Dynamic Arrays and Classes (BigNum.h/.cpp)
The int type in C++ can only support integers in a limited range (typically, -2^31 to 2^31 – 1). If you want to work with integers that are larger than that, you’ll need to use a type often called a big number type (or “bignum” for short). Those types usually work internally by storing a dynamic array that holds the digits of that number. For example, the number 78979871 might be stored as the array [7, 8, 9, 7, 9, 8, 7, 1] (or, sometimes, in reverse as [1, 7, 8, 9, 7, 9, 8, 7]). Implement a bignum type layered on top of a dynamic array. Your implementation should provide member functions that let you add together two bignums or produce a string representation of a bignum, and a constructor that lets you initialize the bignum to some integer value. For simplicity, you don’t need to worry about negative numbers.
Let’s begin with the interface for our class, which will look like this:
class BigNum {
public:
BigNum(int value = 0); // Default to zero unless specified otherwise.
~BigNum();
std::string toString() const; // Get a string representation
void add(const BigNum& value);
private:
int* digits; // Stored in reverse order
int allocatedSize; // In # of digits
int numDigits; // In # of digits.
void reserve(int space); // Ensure we have space to hold numDigits digits
int numDigitsOf(int value) const; // How many digits are in value?
};
Here, the constructor takes in the value we’ll store. The toString function produces a string representation of the number, and the add function takes in another BigNum and adds its value to the total.
Interally, we’ll represent the BigNum as an array of integers, each of which represents a single digit. The allocatedSize and numDigits variables track how many digits we have space for and how many digits we actually have, respectively. (A note: it’s actually not a good use of space to store each digit as an integer because the int type can hold much, much larger values than a single digit, but for simplicity we’ll opt for that approach. Take CS107 to see some alternatives!)
We’ll also write a function named reserve(), which takes as input a number of digits and then does whatever needs to be done to ensure that we have space for at least that many digits. Think of it as a more cautious version of the grow() function we wrote for our stack type: it’ll make the array bigger, but only if it needs to.
To make the implementation simpler, we’ll store the digits of our number in reverse order, so the number 137 would be stored as 7, 3, 1. This makes the math easier and makes it easier to add digits in, since it’s usually easier to add new items further in an array rather than earlier. The implementation itself is presented below.
BigNum::BigNum(int value) {
/* Set up an initial array of elements. */
digits = new int[kDefaultSize]; // Some reasonable default
allocatedSize = kDefaultSize;
/* Count how many digits are in our number. 0 is an edge case, so we'll make
* this work by reducing the number of digits down to the last one.
*/
numDigits = numDigitsOf(value);
/* Copy the number into the array, one digit at a time. */
for (int i = 0; i < numDigits; i++) {
digits[i] = value % 10;
value /= 10;
}
}
int BigNum::numDigitsOf(int value) const {
/* Pro C++ tip: Since this function doesn't read or write any member
* variables, this should either be a free function or a static member
* function. We didn't discuss those sorts of concerns in CS106B, though.
*/
int result = 1; // All numbers have at least one digit.
/* We've already counted one digit. Now count the rest. */
while (value >= 10) {
result++;
value /= 10;
}
return result;
}
BigNum::~BigNum() {
delete[] digits;
}
string BigNum::toString() const {
/* Because characters are stored in reverse order, we have to scan them
* backwards to make our number.
*/
string result;
for (int i = numDigits - 1; i >= 0; i--) {
result += to_string(digits[i]);
}
return result;
}
void BigNum::add(const BigNum& value) {
/* First, ensure we have space to hold the result. Adding two numbers produces
* a result whose size is at most one digit bigger than either input number.
*/
int digitsToVisit = max(numDigits, value.numDigits);
reserve(1 + digitsToVisit);
/* Use the grade school algorithm to add the numbers. */
int carry = 0;
for (int i = 0; i < digitsToVisit; i++) {
int sum;
if (i < numDigits && i < value.numDigits) sum = digits[i] + value.digits[i] + carry;
else if (i < numDigits) sum = digits[i];
else sum = value.digits[i];
/* Write the one's place. */
digits[i] = sum % 10;
/* Store the carry. */
carry = sum / 10;
}
/* We need at least as many digits as before, plus one if there is a final
* carry.
*/
numDigits = digitsToVisit + carry;
if (carry == 1) digits[digitsToVisit] = 1;
}
/* Reserving space uses the regular "double in size" trick. */
void BigNum::reserve(int space) {
/* If we have the space, then we don't need to do anything. */
if (space <= allocatedSize) return;
/* Double and copy. We deliberately don't just grow to the size requested,
* since that may not be efficient.
*/
allocatedSize *= 2;
int* newDigits = new int[allocatedSize];
for (int i = 0; i < numDigits; i++) {
newDigits[i] = digits[i];
}
delete[] digits;
digits = newDigits;
}
3) Linked Lists (lists.cpp)
Write a function
ListNode* kthToLast(ListNode* list, int k)
that, given a pointer to a singly-linked list and a number k, returns the kth-to last element of the linked list (or a null pointer if no such element exists). How efficient is your solution, from a big-O perspective? As a challenge, see if you can solve this in O(n) time with only O(1) auxiliary storage space.
There are a couple of ways we could do this. One option would be to sweep across the list from the front to the back, counting how many nodes there are, then calculate the index we need. That’s shown here:
int listLength(ListNode* list) {
int count = 0;
/* Cute little for loop trick to visit everything in a linked list. This loop
* is great if you are not making any changes to the list, but if the list is
* either being rewired or being deallocated, this loop won't work.
*/
for (ListNode* curr = list; curr != nullptr; curr = curr->next) {
count++;
}
return count;
}
ListNode* kthToLastSimple(ListNode* list, int k) {
/* Find length of the list */
int len = listLength(list);
/* If the list is too small, just return nullptr. */
if (len < k) return nullptr;
/* Move len - k + 1 steps into the list */
ListNode* curr = list;
for (int i = 0; i < len - k; i++) {
curr = curr->next;
}
return curr;
}
Another option, which is a bit less obvious but is quite beautiful, is to walk down the list with two concurrent pointers, one of which is k steps ahead of the other. As soon as the lead pointer falls off the list, the pointer behind it is k steps from the end. Do you see why?
ListNode* kthToLast(ListNode* list, int k) {
/* Set up two pointers, one leader and one follower. */
ListNode* leader = list;
ListNode* follower = list;
/* March the leader k steps forward. If we fall of the list in this time,
* there is no kth-to-last node.
*/
if (leader == nullptr) return nullptr;
for (int i = 0; i < k; i++) {
leader = leader->next;
/* Question to ponder: Why are there two checks, above and here? */
if (leader == nullptr) return nullptr;
}
/* Keep walking the leader and follower forward. As soon as the leader walks
* off the follower is in the right spot.
*/
while (true) {
leader = leader->next;
if (leader == nullptr) return follower;
follower = follower->next;
}
}
4) Sorting (sorting.cpp)
Write an implementation of insertion sort that works on singly-linked lists. Implement the following function header:
void listInsertionSort(ListNode*& list)
The singly-linked list requirement here suggests that our pattern of repeatedly swapping elements back in the sequence is not going to be easy to implement – we’ll keep losing track of where our preceding element is. There are many ways we could deal with this. One would be to build the sorted list in reverse, then fix up the pointers at the end to reverse it. Another, shown below, works by taking the element, moving it to the front of the list, then swapping it forward until it’s in the right position.
void listInsertionSort(ListNode*& list) { // Question to ponder: why by reference?
ListNode* sortedList = nullptr;
ListNode* curr = list;
while (curr != nullptr) {
/* Need to store the pointer to the next cell in the list, since after
* we do the insert operation we'll lose track of where the next cell
* is.
*/
ListNode* next = curr->next;
sortedInsert(curr, sortedList);
curr = next;
}
list = sortedList;
}
/* Adds the given node into a sorted, singly-linked list. */
void sortedInsert(ListNode* toIns, ListNode*& list) {
/* See if we go at the beginning. */
if (list == nullptr || toIns->value < list->value) {
toIns->next = list;
list = toIns;
} else {
/* Find the spot right before where we go, since that's the pointer we
* need to rewire.
*/
ListNode* curr = list;
ListNode* prev = nullptr;
while (curr != nullptr && curr->value < toIns->value) {
prev = curr;
curr = curr->next;
}
/* Splice us in. */
toIns->next = curr;
prev->next = toIns;
}
}
5) Trees (trees.cpp)
A binary tree (not necessarily a binary search tree) is called a palindromic tree if it’s its own mirror image. For example, the tree on the left is a palindromic tree, but the tree on the right is not:
Write a function
bool isPalindromicTree(TreeNode* root)
that takes in a pointer to the root of a binary tree and returns whether it’s a palindrome tree.
To solve this problem, we’ll solve a slightly more general problem: given two trees, are they mirrors of one another? We can then check if a tree is a palindrome by seeing whether that tree is a mirror of itself.
bool isPalindromicTree(TreeNode* root) {
return areMirrors(root, root);
}
bool areMirrors(TreeNode* root1, TreeNode* root2) {
/* If either tree is empty, both must be. */
if (root1 == nullptr || root2 == nullptr) {
return root1 == root2;
}
/* Neither tree is empty. The roots must have equal values. */
if (root1->data != root2->data) {
return false;
}
/* To see if they're mirrors, we need to check whether the left subtree of
* the first tree mirrors the right subtree of the second tree and vice-versa.
*/
return areMirrors(root1->left, root2->right) &&
areMirrors(root1->right, root2->left);
}