This week’s section will get you more practice with the ADTs you’ve been learning about for the past few weeks, as well as getting practice with new concepts from lecture this week such as Big-O analysis and even a little bit of practice with recursion!
We have a Qt creator project linked below that contains starter code + testing infrastructure for this week’s problems. When a problem name is followed by the name of a .cpp file, that means that you can practice writing code for it in Qt creator. Here’s the zip of the starter code:
📦 Starter project
1. Grid Basics (grid.cpp)
Topic: Grids
a. Maximum of a Row in a Grid
Write a function named maxRow that takes a grid of non-negative integers (numbers from 0 to infinity) and an in-bounds grid location and returns the maximum value in the row of that grid location.
// solution1 (manally loop through the row in the grid)
int maxRow(Grid<int>& grid, GridLocation loc) {
int max = -1;
for (int col = 0; col < grid.numCols(); col ++) {
if (grid[loc.row][col] > max) {
max = grid[loc.row][col];
}
}
return max;
}
// solution2(use GridLocationRange)
int maxRow(Grid<int>& grid, GridLocation loc) {
int max = -1;
int endCol = grid.numCols() - 1;
for (GridLocation cell : GridLocationRange(loc.row, 0, loc.row, endCol)) {
if (grid[cell] > max) {
max = grid[cell];
}
}
return max;
}
b. Average value
Write a function named avgNeighborhood that takes a grid and a grid location and returns the average of all the values in the neighborhood of the grid location. A neighborhood is defined as all cells in a grid that border the grid location in all four directions(N, S, E, W). If the average
is not an integer, return a truncated average.
// solution1 (we put the 4 locations in a Vector and loop over them)
int avgNeighborhood(Grid<int>& grid, GridLocation loc) {
Vector<GridLocation> possibleLocations = {
{loc.row - 1, loc.col}, // north
{loc.row + 1, loc.col}, // south
{loc.row, loc.col + 1}, // east
{loc.row, loc.col - 1} // west
};
int sum = 0;
int numValidLocations = 0;
for (GridLocation dir : possibleLocations) {
if (grid.inBounds(dir)) {
sum += grid[dir];
numValidLocations += 1;
}
}
return sum / numValidLocations;
}
// solution2 (Don't do this please!! We manually get all 4 locations and sum them up)
int avgNeighborhood(Grid<int>& grid, GridLocation loc) {
int sum = 0;
int numValidLocations = 0;
GridLocation north {loc.row - 1, loc.col};
if (grid.inBounds(north)) {
sum += grid[north];
numValidLocations += 1;
}
GridLocation south {loc.row + 1, loc.col};
if (grid.inBounds(south)) {
sum += grid[south];
numValidLocations += 1;
}
GridLocation east {loc.row, loc.col + 1};
if (grid.inBounds(east)) {
sum += grid[east];
numValidLocations += 1;
}
GridLocation west {loc.row, loc.col - 1};
if (grid.inBounds(west)) {
sum += grid[west];
numValidLocations += 1;
}
return sum / numValidLocations;
}
2. Friends (friendlist.cpp)
Topic: Maps, Sets
a. Building the friendList
Write a function named friendList that takes in a file name, reads friend relationships from the file, and writes them to a Map. friendList should return the populated Map. Friendships are bi-directional, so if Abby is friends with Barney, Barney is friends with Abby. The file contains one friend relationship per line, with names separated by a single space. You do not have to worry about malformed entries.
If an input file named buddies.txt looked like this:
Barney Abby
Abby Clyde
Then the call of friendList("buddies.txt") should return a resulting map that looks like this:
{"Abby":{"Barney", "Clyde"}, "Barney":{"Abby"}, "Clyde":{"Abby"}}
Here is the function prototype you should implement:
Map<string, Set<string> > friendList(String filename)
Map<string, Set<string> > friendList(string filename) {
ifstream in;
Vector<string> lines;
if (openFile(in, filename)) {
lines = readLines(in);
}
Map<string, Set<string> > friends;
for (string line: lines) {
Vector<string> people = stringSplit(line, " ");
string s1 = people[0];
string s2 = people[1];
friends[s1] += s2;
friends[s2] += s1;
}
return friends;
}
b. Finding common friends
Write a function named mutualFriends that takes in the friendList above, and two strings representing two friends, and returns the names of the mutual friends they have in common. For example, if the friendList is {"Abby":{"Barney", "Clyde"}, "Barney":{"Abby"}, "Clyde":{"Abby"}} and friend1 is Barney and friend2 is Clyde, then your function should return {"Abby"}
Set<string> mutualFriends(Map<string, Set<string> >& friendList, string friend1, string friend2) {
return friendList[friend1] * friendList[friend2];
}
3. Twice (twice.cpp)
Topic: Sets
Write a function named twice that takes a vector of integers and returns a set containing all the numbers in the vector that appear exactly twice.
Example: passing {1, 3, 1, 4, 3, 7, -2, 0, 7, -2, -2, 1} returns {3, 7}.
Bonus: do the same thing, but you are not allowed to declare any kind of data structure other than sets.
// solution
Set<int> twice(Vector<int>& v) {
Map<int, int> counts;
for (int i : v) {
counts[i]++;
}
Set<int> twice;
for (int i : counts) {
if (counts[i] == 2) {
twice += i;
}
}
return twice;
}
// bonus
Set<int> twice(Vector<int>& v) {
Set<int> once;
Set<int> twice;
Set<int> more;
for (int i : v) {
if (once.contains(i)) {
once.remove(i);
twice.add(i);
} else if (twice.contains(i)) {
twice.remove(i);
more.add(i);
} else if (!more.contains(i)) {
once.add(i);
}
}
return twice;
}
4. Check Balance (balance.cpp)
Topic: Stacks
Write a function named checkBalance that accepts a string of source code and uses a Stack to check whether the braces/parentheses are balanced. Every ( or { must be closed by a } or ) in the opposite order. Return the index at which an imbalance occurs, or -1 if the string is balanced. If any ( or { are never closed, return the string’s length.
Here are some example calls:
// index 0123456789012345678901234567
checkBalance("if (a(4) > 9) { foo(a(2)); }")
// returns -1 (balanced)
// index 01234567890123456789012345678901
checkBalance("for (i=0;i<a;(3};i++) { foo{); )")
// returns 15 because } is out of order
// index 0123456789012345678901234
checkBalance("while (true) foo(); }{ ()")
// returns 20 because } doesn't match any {
// index 01234567
checkBalance("if (x) {")
// returns 8 because { is never closed
int checkBalance(string code) {
Stack<char> parens;
for (int i = 0; i < code.length(); i++) {
char c = code[i];
if (c == '(' || c == '{') {
parens.push(c);
} else if (c == ')' || c == '}') {
if (parens.isEmpty()) {
return i;
}
char top = parens.pop();
if ((top == '(' && c != ')') || (top == '{' && c != '}')) {
return i;
}
}
}
if (parens.isEmpty()) {
return -1; // balanced
}
return code.length();
}
5. Oh No, Big-O, Too Slow
Topic: Big-O, code analysis
Give a tight bound of the nearest runtime complexity class for each of the following code fragments in Big-Oh notation, in terms of the variable N.
Code Snippet A
int sum = 0;
for (int i = 1; i <= N + 2; i++) {
sum++;
}
for (int j = 1; j <= N * 2; j++) {
sum++;
}
cout << sum << endl;
Code Snippet B
int sum = 0;
for (int i = 1; i <= N - 5; i++) {
for (int j = 1; j <= N - 5; j += 2) {
sum++;
}
}
cout << sum << endl;
Code Snippet C
int sum = 0;
for (int i = 0; i < 1000000; i++) {
for (int j = 1; j <= i; j++) {
sum += N;
}
for (int j = 1; j <= i; j++) {
sum += N;
}
for (int j = 1; j <= i; j++) {
sum += N;
}
}
cout << sum << endl;
Code Snippet B has a runtime complexity of O(N^2).
Code Snippet C has a runtime complexity of O(1).
6. More Big O
Below are five functions. Determine the big-O runtime of each of those pieces of code, in terms of the variable n.
void function1(int n) {
for (int i = 0; i < n; i++) {
cout << '*' << endl;
}
}
void function2(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << '*' << endl;
}
}
}
void function3(int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
cout << '*' << endl;
}
}
}
void function4(int n) {
for (int i = 1; i <= n; i *= 2) {
cout << '*' << endl;
}
}
Finally, what is the big-O runtime of this function in terms of n, the number of elements in v?
int squigglebah(Vector<int>& v) {
int result = 0;
for (int i = 0; i < v.size(); i++) {
Vector<int> values = v.subList(0, i);
for (int j = 0; j < values.size(); j++) {
result += values[j];
}
}
return result;
}
The runtime of this code is O(n): We print out a single star, which takes time O(1), a total of n times.
The runtime of this code is O(n^2). The inner loop does O(n) work, and it runs O(n) times for a net total of O(n^2) work.
This one also does O(n^2) work. To see this, note that the first iteration of the inner loop runs for n – 1 iterations, the next for n – 2 iterations, then n – 3 iterations, etc. Adding all this work up across all iterations gives (n – 1) + (n – 2) + … + 3 + 2 + 1 + 0 = O(n^2).
This one runs in time O(log n). To see why this is, note that after k iterations of the inner loop, the value of i is equal to 2^k. The loop stops running when 2^k exceeds n. If we set 2^k = n, we see that the loop must stop running after k = logâ‚‚ n steps.
Another intuition for this one: the value of i doubles on each iteration, and you can only double O(log n) times before you overtake the value n. For the final function, Let’s follow the useful maxim of “when in doubt, work inside out!”" The innermost for loop (the one counting with j) does work proportional to the size of the values list, and the values list has size equal to i on each iteration. Therefore, we can simplify this code down to something that looks like this:
int squigglebah(Vector<int>& v) {
int result = 0;
for (int i = 0; i < v.size(); i++) {
Vector<int> values = v.subList(0, i);
do O(i) work;
}
return result;
}
Now, how much work does it take to create the values vector? We’re copying a total of i elements from v, and so the work done will be proportional to i. That gives us this:
int squigglebah(Vector<int>& v) {
int result = 0;
for (int i = 0; i < v.size(); i++) {
do O(i) work;
do O(i) work;
}
return result;
}
Remember that doing O(i) work twice takes time O(i), since big-O ignores constant factors. We’re now left with this:
int squigglebah(Vector<int>& v) {
int result = 0;
for (int i = 0; i < v.size(); i++) {
do O(i) work;
}
return result;
}
This is the same pattern as function2 in the previous problem, and it works out to O(n^2) total time.
7. Recursion Mystery
Topic: recursive function calls, return value tracing
Code Snippet A
int recursionMystery(int x, int y) {
if (x < y) {
return x;
} else {
return recursionMystery(x - y, y);
}
}
For each call to the above recursive function, indicate what value is returned by the function call.
Call Return value
recursionMystery(6, 13); ______________
recursionMystery(14, 10); ______________
recursionMystery(37, 12); ______________
6
4
1
8. Recursion Tracing
Topic: Recursion, strings, recursion tracing
Below is a recursive function to reverse a string.
string reverseOf(string s) {
if (s.empty()) {
return "";
} else {
return reverseOf(s.substr(1)) + s[0];
}
}
Trace through the execution of reverseOf("stop") along the lines of what we did in lecture, showing recursive call information for each call that’s made and how the final value gets computed.
reverseOf("stop") fires off a call to reverseOf("top"). This call fires off a call to reverseOf("op"). This in turn calls reverseOf("p"). This in turn calls reverseOf(""). This triggers the base case and returns the empty string. (Notice that the reverse of the empty string "" is indeed the empty string “”). We now append p to return "p". We now append o to return "po". We append t to return "pot". And finally we append s to return "pots" back to whoever called us. Yay!