Final Review
The following practice problems are meant to be supplemental to the lecture notes, and give some extra practice for problem types you might encounter on the final.
Everything we've gone over this quarter is subject to examination! Some of the possible topics include:
Constructors, initialization lists, copy constructors, assignment overloading, and destructors
Dynamic Arrays
Linked Lists / Double Linked Lists
Stacks and Queues
Inheritance
Polymorphism
Templates
Algorithmic Complexity
Sorting Algorithms
Recursion
Trees
Heaps
Graphs
This review will focus on the later topics not covered on the previous midterms, but I'll attempt a breadth coverage!
I suggest the following workflow:
Review your notes / mine, skimming through sections you know pretty well (maybe linked lists and stacks, for example)
Take the practice final / midterms listed on the course site by hand (they're very good)
Take my practice final (either by hand or by computer)
Would It Be a Review Without NoisyClass?
Well... maybe... but not a good one.
class NoisyBase {
private:
string s;
public:
NoisyBase (string sBase) {
cout << "[B] Base Constructor: " << sBase << endl;
s = sBase;
}
virtual ~NoisyBase () {
cout << "[B] Base Destructor!" << endl;
}
virtual string getS () {
return s;
}
void shout () {
cout << "[B] LOUD BASE NOISES" << endl;
}
};
class NoisyDerived: public NoisyBase {
private:
string s;
public:
NoisyDerived (string sBase, string sDerived): NoisyBase(sBase) {
cout << "[D] Derived Constructor: " << sDerived << endl;
s = sDerived;
}
~NoisyDerived () {
cout << "[D] Derived Destructor!" << endl;
}
virtual string getS () {
return s;
}
void shout () {
cout << "[D] LOUD DERIVED NOISES" << endl;
}
};
Using the class definition for NoisyDerived and NoisyBase above, what will the following code print out?
int main () {
NoisyBase b("base");
NoisyDerived d("base", "derived");
NoisyBase* bPtr = &b;
NoisyDerived* dPtr = &d;
cout << bPtr->getS() << endl;
bPtr->shout();
bPtr = &d;
cout << bPtr->getS() << endl;
bPtr->shout();
cout << dPtr->getS() << endl;
dPtr->shout();
}
Using the class definition for NoisyDerived and NoisyBase above, what will the following code print out?
int main () {
vector<NoisyBase*> noisyVector;
noisyVector.push_back(new NoisyDerived("base", "derived"));
noisyVector.push_back(new NoisyBase("base"));
vector<NoisyBase*>::iterator it = noisyVector.begin();
while (it != noisyVector.end()) {
cout << (*it)->getS() << endl;
(*it)->shout();
delete *it;
it++;
}
}
One more for good measure, a templated version of NoisyClass; what will this print out?
template <typename T>
class NoisyTemplate {
private:
T t;
public:
NoisyTemplate (T input) {
t = input;
cout << "Constructor: " << t + t << endl;
}
};
int main () {
NoisyTemplate<int> ni(5);
NoisyTemplate<string> ns("yo");
}
OK I lied... uno mas.
class NoisyClass {
private:
string s;
public:
NoisyClass () {
cout << "DEFAULT" << endl;
}
NoisyClass (const NoisyClass& other) {
cout << "COPY" << endl;
}
};
int main () {
vector<NoisyClass> nv;
NoisyClass n;
nv.push_back(n);
}
Binary Tree Stuffs
You're probably sick of these by now... why not a couple more?
Questions
Is it possible for a binary search tree to have the preorder traversal: 16, 13, 12, 14, 20, 15, 21
No! Assume to the contrary that it is a binary search tree... We know that 16 is the root, and in a preorder traversal, 14 must be the right-most item of the left subtree of the root... therefore, 20 must be the first item of the right subtree of the root. Now we see the 15 value, which must come to the left of the 20. Contradiction: 15 is less than the root 16 and should have gone within the left subtree. Therefore, this traversal could not have been elicited from a BST.
Consider a heap in a binary tree form; is it possible for some heap to have the inorder traversal: 30, 45, 20, 50, 28, 29
Yes! Now draw it :)
The following heap is given to you in array form; draw its corresponding binary tree representation:
100, 19, 36, 17, 3, 25, 1, 2, 7 (thanks wiki)
Exercises
A few weeks ago, we talked about the following, simple, BinaryTree struct:
struct BinTree {
// BinTreeNode struct internal
// to the BinTree
struct BinTreeNode {
int data;
BinTreeNode* left;
BinTreeNode* right;
BinTreeNode(int d) {
data = d;
left = nullptr;
right = nullptr;
}
};
// Root just points to a single
// BinTreeNode
BinTreeNode* root;
BinTree() {
root = nullptr;
}
~BinTree() {}; // TODO!
void insertAt (int i, string path);
};
// Creates a new node with the given data member
// if input string p specifies a path in terms of
// L and R children to follow to an empty spot in
// the tree
// The path p will look like some string of "LRL"
void BinTree::insertAt (int data, string p) {
BinTreeNode* b = root;
BinTreeNode* last = nullptr;
int i = 0;
while (i < p.length()) {
if (b == nullptr) {
break;
}
last = b;
b = (p[i] == 'L') ? b->left : b->right;
i++;
}
if (i == p.length()) {
if (b != nullptr) {
return;
}
b = new BinTreeNode(data);
if (root == nullptr) {
root = b;
}
if (last != nullptr) {
if (p[i - 1] == 'L') {
last->left = b;
} else {
last->right = b;
}
}
}
}
Using this class, let's go over a couple of algorithms, hmm?
There are some great tree example problems (some of which I shamelessly stole from) located here.
Implement the doubleTree function, which modifies a binary tree by duplicating each node and placing that duplicate at the original's left-child pointer. Preserve the tree structure. (Hint: consider traversal orders in your solution!)
(Example credit to the site mentioned above)
This tree:
2
/ \
1 3
Is changed to:
2
/ \
2 3
/ /
1 3
/
1
void doubleTree (BinTreeNode* node) {
// ...
}
Click for a possible solution
void doubleTree(BinTree::BinTreeNode* node) {
BinTree::BinTreeNode* oldLeft;
if (node == nullptr) return;
doubleTree(node->left);
doubleTree(node->right);
// Duplicate this node to its left
oldLeft = node->left;
node->left = new Node(node->data);
node->left->left = oldLeft;
}
What traversal method did you use in your solution? Which does the given solution use?
Yours: ???, The above solution: postorder
Implement the sameTree function, which takes in pointers to two trees and determines if they are equivalent (same Nodes at each position and same values in each corresponding Node).
(Example credit to the site mentioned above)
bool sameTree(BinTree::BinTreeNode* b1, BinTree::BinTreeNode* b2) {
// ...
}
int main () {
BinTree b1;
b1.insertAt(14, "");
b1.insertAt(10, "L");
b1.insertAt(8, "LL");
b1.insertAt(11, "LR");
b1.insertAt(15, "R");
BinTree b2;
b2.insertAt(14, "");
b2.insertAt(10, "L");
b2.insertAt(8, "LL");
b2.insertAt(11, "LR");
b2.insertAt(15, "R");
cout << sameTree(b1.root, b2.root) << endl; // true
b2.insertAt(27, "LLR");
cout << sameTree(b1.root, b2.root) << endl; // false
}
Click for example solution
bool sameTree(BinTree::BinTreeNode* b1, BinTree::BinTreeNode* b2) {
// Case where both nullptr
if (b1 == nullptr && b2 == nullptr) {
return true;
}
// Case where neither are nullptr
if (b1 != nullptr && b2 != nullptr) {
return (
b1->data == b2->data &&
sameTree(b1->left, b2->left) &&
sameTree(b1->right, b2->right)
);
}
// Otherwise one was nullptr and the other wasn't
return false;
}
Big 'Ole Big-O Review
Remember our guidelines for determining time complexity:
Identify the statements that rely on the size of the input
Of those that are reliant on the size of the input, which are dependent upon each other?
Remember that a single statement, particularly a function call, is not a guarantee for a constant time operation!
You ready to do this? Let's start off with some non-programmatic analyses and then move to the hard stuff...
Andrew continually loses socks in his dryer... one day he discovers why: a quantum sock portal has opened up within the lint rack and has been sucking socks in; finally it reaches critical mass, and then expodes into an (almost) infinite number of socks!
Rather than work on his research, Andrew decides to do something more exciting and starts sorting the socks into their respective pairs. Because he's particularly devoted to procrastinating, he desides to pick up one sock, and then look at other socks in the pile until he finds a match.
If more socks continue to spill out of the quantum sock portal, what is the time complexity growth of Andrew's sort algorithm?
Click for solution
Andrew, that was an *excessive* amount of setup for the answer of O(n^2); we see that the sort is much like bubble sort in that you're needing to take each sock and run it through the rest of the "input" until we find a match.
Well, it took awhile, but Andrew finally finished sorting all those damn socks. He decided he'd keep about a million socks just in case, but where to put all of them?
As it turns out, the sock pairs have a couple defining characteristics:
They have a color (every pair of socks falls, conveniently, evenly distributed across the hexadecimal color spectrum from #000000 (black) to #FFFFFF (white))
They have a shape-pattern of 1 of 3 shapes: squares, circles, and triangles. 1/3 of the socks have squares, 1/3 circles, and 1/3 triangles.
Luckily, Ikea sells SOK, a drawer apparatus for storing millions of socks that lets you add an arbitrary number of drawers...
SOK also comes with a data pad that allows you to know exactly the drawer (note: not necessarily where in the drawer) that contains a given sock color OR a given shape, but not both.
Would it be more efficient for Andrew to store his socks by shape or by color if, on any given day, he is interested in searching for a pair of socks with a given color AND shape pattern?
Click for solution
It would be more efficient to keep drawers indexed by color, because the SOK data pad could thin the results to a more unique color, which would only have a few pairs with different shapes within the drawer. If you indexed drawers by shape, then you'd only have 3 drawers with about 333,333 socks each, which would then need a linear search to find the right color!
"Andrew, what *were* those examples? Is this a creative writing class?"
So I wanted to break the monotony a bit!
Fine, you want programmy stuff? Here you go:
What is the time complexity of the following function?
void funkyFunc (int n) {
for (int i = 0; i < n; i++) {
for (int j = 10; j > 0; j--) {
cout << j << endl;
}
}
}
Click for solution
O(n) because the inner loop runs a constant number of times
What is the time complexity of the following function?
void funkyFunc (int n) {
for (int i = 0; i < n * n; i++) {
for (int j = 0; j < n; j++) {
cout << i << j << endl;
}
}
}
Click for solution
O(n^3) because the outer loop relies on the size of the input squared, and the inner loop relies on the size of the input as many times as the outer loop. n * n^2
What is the time complexity of the following function?
void funkyFunc (int n) {
for (int i = 0; i < n * n; i++) {
for (int j = 0; j < i; j++) {
cout << i << j << endl;
}
}
}
Click for solution
sum(i)_i=1 to n^2 = 1 + 2 + 3 + ... + (n^2 - 2) + (n^2 - 1) + n^2 = (n^2 + 1) + (n^2 + 1) + ... + (n^2 + 1) // how many (n^2 + 1)'s? = (n^2)/2 * (n^2 + 1) // (n^2)/2 of them! = (n^4)/2 + (n^2)/2 => O(n^4)
Say the following algorithm takes in a pointer to a Node in a linked list. Assume N to be the size of the linked list. What is the time complexity of the following function in terms of N?
void funkyFunc (Node* n) {
int i = 1;
while (true) {
int j = i;
while (j > 0 && n != nullptr) {
n = n->next;
cout << n->data << endl;
j--;
}
if (j != 0) {
return;
}
i *= 2;
}
}
Click for solution
O(N); it might LOOK like we're reducing the size of our data set at every step by the i *= 2, but if you look at the innermost loop, we're actually visiting every Node once!
What is the time complexity of the following function in terms of q and r?
void funkyFunc (int q, int r) {
for (int i = q * r; i > 0; i--) {
cout << q << r << endl;
}
for (int i = q * r; i > 0; i /= 2) {
cout << r << q << endl;
}
}
Click for solution
O(q*r); note that the second loop runs with O(log(q*r)), which is NOT dependent on the first loop and a lesser complexity than the colinear case in the first loop, so we reduce from O(q*r + log(q*r)) to O(q*r).
What is the time complexity of the following function in terms of input n and size of input list, L?
void funkyFunc (int n, list<int> listy) {
vector<int> victor;
for (int i = 0; i < listy.size(); i++) {
victor.push_back(i * n);
}
vector<int>::iterator vit = victor.begin();
list<int>::iterator lit = listy.begin();
while (vit != victor.end()) {
lit = listy.insert(lit, *vit);
vit = victor.erase(vit);
}
}
Click for solution
void funkyFunc (int n, list<int> listy) {
vector<int> victor;
// [!] Goes L times; n is irrelevant to steps
for (int i = 0; i < listy.size(); i++) {
// [!] Push to back of vector O(1)
victor.push_back(i * n);
}
vector<int>::iterator vit = victor.begin();
list<int>::iterator lit = listy.begin();
// [!] Goes L times because victor was constructed
// with all L elements
while (vit != victor.end()) {
// [!] Insertion into linked list constant time O(1)
lit = listy.insert(lit, *vit);
// [!] Deletion of front of vector requires re-ordering
// proportional to size of the vector, in this case, that size
// is L; so O(L)
vit = victor.erase(vit);
}
// [!] Therefore, above loop has complexity O(L^2)
// [!] Total complexity: O(L + L^2), which reduces to
// O(L^2)
}
What is the time complexity of the following function in terms of the number of nodes in s1 (call that number S) and the number in s2 (call that number R), assuming that s1 is a subset of s2?
void funkyFunc (set<int> s1, set<int> s2) {
set<int>::iterator sit = s1.begin();
while (sit != s1.end()) {
if (s2.find(*sit) != s2.end()) {
s2.insert(*sit);
}
sit++;
}
}
Click for solution
void funkyFunc (set<int> s1, set<int> s2) {
set<int>::iterator sit = s1.begin();
// [!] Goes through all S elements of s1
while (sit != s1.end()) {
// [!] Find operation is binary search so log(R) (but will grow
// as we insert, and trend toward log(R + S) see below)
if (s2.find(*sit) != s2.end()) {
// [!] Insertion into BST takes log(R), but by assumption
// s1 is a subset of s2, so we must also take into account the growth
// of s2 from insertion, giving us log(R + S)
s2.insert(*sit);
}
sit++;
}
// [!] Therefore, outer loop runs S times and with every loop
// we're performing O(log(R + S)), giving us total complexity:
// O(S*log(R + S))
}
What is the time complexity of the following function in terms of the size of the input stack (S) and the number of elements in the unordered_set (U)?
void funkyFunc (stack<int> si, unordered_set<int> ui) {
while (!si.empty()) {
if (ui.find(si.top()) == ui.end()) {
ui.insert(si.top());
}
si.pop();
}
}
Click for solution
void funkyFunc (stack<int> si, unordered_set<int> ui) {
// [!] Go through all S elements of the stack
while (!si.empty()) {
// [!] unordered_sets are hashes! Average case constant time lookup O(1)
if (ui.find(si.top()) == ui.end()) {
// [!] Same thing with hashes; average case constant time insertion O(1)
ui.insert(si.top());
}
// [!] Popping from stack is constant time
si.pop();
}
// [!] Total time complexity: O(S)
}
What is the time complexity of the following function?
void funkyFunc (int q, int r) {
map<int, int> mappy;
for (int i = 0; i < q; i++) {
for (int j = r * r * i; j > 0; j--) {
mappy[i] = j;
}
}
}
Click for solution
void funkyFunc (int q, int r) {
map<int, int> mappy;
// [!] Go through q times in outer loop
for (int i = 0; i < q; i++) {
// [!] Inner loop goes r^2 * i times, and i is dependent
// on q, so really this loop is proportional to O(r^2 * q)
for (int j = r * r * i; j > 0; j--) {
// [!] Insertion into map takes a log time on the keys...
// since we're inserting into the map with keys related to
// i, and i is dependent on q, then our insertion time is
// proportional to O(log(q))
mappy[i] = j;
}
}
// [!] Total, then, we have complexities of:
// Outer loop: O(q)
// Inner loop: O(r^2 * q)
// Inner map assignment: O(log(q))
// Total: O(r^2 * q^2 * log(q))
}