Hunter Liu's Website

14.1. Some Midterm Practise Solutions

Some of you have expressed interest in seeing a set of solutions to the practise problems from the last discussion, so here they are. I won’t solve the coding problems; there are many different approaches to those, and we usually spend our “normal” discussion sections doing coding problems anyways.

Predict the Output

As described last time, I highly recommend writing down in pseudocode or even common English what the more complicated segments of code (i.e. complex loops and functions) do, then see how they fit together and interact. If you absolutely need to, you can still write out each iteration of each loop and see what happens to each variable after every significant line of code; however, this quickly becomes impractical, and it’s more important to develop the abliity to read and interpret code without writing out every step.

 1#include <iostream> 
 2#include <string> 
 3
 4using namespace std; 
 5
 6void foo(string& s, char c1, char c2) {
 7    for(int i = 0; i < s.length(); i++) {
 8        if(s.at(i) == c1) { 
 9            s.at(i) = c2; 
10        } else if(s.at(i) == c2) { 
11            s.at(i) = c1; 
12            return; 
13        } 
14    }
15} 
16
17int main() {
18    string str = "C++ is a programming language."; 
19    foo(str, 'i', 'z'); 
20    cout << str << endl; 
21
22    foo(str, 'n', 'p'); 
23    cout << str << endl; 
24
25    foo(str, 'z', 't'); 
26    cout << str << endl; 
27
28    return 0; 
29} 

Since the parameter s is passed by reference in the function foo, any changes to s in the function will be reflected in whatever variable is passed in. That is, the contents of the string str will most likely be modified after lines 19, 22, and 25 are run, and we will most likely see this change in the output.

The function foo performs the following:

• For each index i = 0, 1, ..., s.length() - 1, repeat the following:
  • If the character at index i is ch1, change it to ch2.
  • If the character at index i is ch2, change it to ch1, and immediately end the function.

In words, foo(s, ch1, ch2) swaps the characters ch1 and ch2 until it sees a ch2. Line 19 therefore replaces every i with a z and every z with an i in the string str, until it sees a z. There are no z’s in str, so it replaces every i with z. The first line of output is thus

C++ zs a programmzng language.

Line 22 replaces n’s with p’s and vice versa, stopping at the first p, so the second line of output is

C++ zs a nrogrammzng language.

And finally, line 25 replaces z’s with t’s and vice versa, stopping at the first t. Thus, the final output is

C++ ts a nrogrammtng language.

There are two important concepts to remember from this problem:

1. Passing by reference allows the function foo to modify the contents of the string str, even though the latter is only defined in the main function.
2. The return statement inside foo immediately ends the function! This empty return statement is allowed only in void functions, where nothing is supposed to get returned anyways. The loop does not finish running over the remaining characters of the string when the return statement is encountered.

 1#include <iostream> 
 2#include <vector> 
 3
 4using namespace std; 
 5
 6// prints out the contents of an int vector, 
 7// separated by spaces. 
 8void print_vector(const vector<int>& v) {
 9    for(int i = 0; i < v.size(); i++) {
10        cout << v.at(i) << ' '; 
11    } 
12    cout << endl; 
13} 
14
15vector<int> f(vector<int> v, int j) {
16    vector<int> w; 
17    for(int i = v.size() - 1; i > 0; i -= j) {
18        w.push_back(v.at(i)); 
19    } 
20
21    return w; 
22} 
23
24int main() {
25    vector<int> v = {1, 4, 9, 16, 25, 36, 49}; 
26    print_vector(f(v, 1)); 
27    print_vector(f(v, 4)); 
28    print_vector(v); 
29
30    return 0; 
31}

The print_vector function exists only to make the output easier to read and format in code; the meat of this problem is understanding what f is doing. The function signature is somewhat intimidating, but recall that the general syntax for defining a function is

[return type] [function name]([parameters]) { ... } 

Matching this up with the function signature of f, we see that f takes in a vector of int’s (v) and another integer as parameters, and it returns another vector of int’s. This is also apparent within the function body: it creates a vector of int’s w, does some stuff to it, then returns w.

Unwrapping the loop, we can write out the function as follows:

1. Create a new empty vector of integers w.
2. For each index i, starting at v.size() - 1, counting down by j, and stopping before 0, repeat the following:
   • Get the item at index i from v (v.at(i)) and append it to the end of w (w.push_back(...)).
3. Return w.

Let’s write out the contents of v with indices first:

i       | 0   1   2   3   4   5   6   
v.at(i) | 1   4   9   16  25  36  49

In accordance with the pseudocode we reverse-engineered earlier, the function call f(v, 1) will create a vector w, fill it with v.at(6), v.at(5), ..., v.at(1) in this order, then return it. Thus, the first line of output is:

49 36 25 16 9 4 

For the second function call, f(v, 4), it will instead create a vector w with the contents v.at(6), v.at(2) and nothing else; thus the second line of output is

49 9

Of course, since v was not passed by reference (and isn’t getting modified anyways), the last line of output is just the vector v itself:

1 4 9 16 25 36 49

 1#include <iostream>
 2#include <string>
 3#include <vector> 
 4
 5using namespace std; 
 6
 7void f(vector<string>& v, char t) {
 8    for(int i = 0; i < v.size(); i++) {
 9        if(i < v.at(i).length()) {
10            v.at(i).at(i) = t; 
11        }
12    } 
13} 
14
15int main() {
16    vector<string> names = { 
17        "Alice", "Bilbo", "Candace", "Ding", "Ed"
18    }; 
19
20    f(names, '#'); 
21    for(int i = 0; i < names.size(); i++) {
22        cout << names.at(i) << endl; 
23    } 
24
25    return 0; 
26}

I think the challenging thing about this problem is seeing the expressions v.at(i).length() and v.at(i).at(i) on lines 9 and 10. However, if we just read this from left to right and process the function calls one at a time, we get:

• v.at(i) is the string at index i in the vector v.
• v.at(i).length() is the length of the string at index i.
• v.at(i).at(i) is the character at index i in the string at index i (the “i-th” character of the “i-th” string).

Therefore, the function f takes a reference to a vector of strings and a character t, then performs the following:

• For each index i in the vector v, repeat the following:
  • Get the string at index i in v.
  • If i is a valid index in this string, replace the character at index i with the character t.

So, when names is the vector

i   | 0         1           2           3           4
    | Alice     Bilbo       Candace     Ding        Ed

the function f(names, '#') replaces the index 0 character of Alice with #, the index 1 character of Bilbo with #, etc., as long as these indices remain valid. So, the output becomes:

#lice
B#lbo
Ca#dace
Din#
Ed

Ed was unchanged because 4 is not a valid index in that string.

Spot the Error

After a student asked for advice on how to approach these problems in general, I’ve realised that these “spot the error” style questions are not exactly the most practical skills, although they certainly serve as a decent proxy for understanding. In “real life”, at least within my own experience, I rely first and foremost on compiler warnings and error messages to debug and catch errors, and I flood my code with cout statements so I can check the internal state of my program at certain checkpoints if there’s a logical error. Very rarely do I rely on combing through code by hand alone to identify errors. But perhaps this is not an appropriate time or place to discuss these opinions.

 1#include <iostream>
 2#include <string> 
 3
 4using namespace std; 
 5
 6bool is_odd_digit(char c) {
 7    // odd digit
 8    if('0' < c <= '9' && (c - '0') % 2 == 1) {
 9        return true; 
10    }
11
12    // even digit
13    else if('0' < c <= '9' && (c - '0') % 2 == 0) {
14        return false; 
15    } 
16} 
17
18int main() {
19    string input; 
20    getline(cin, input); 
21
22    // replace all of the odd digits with *! 
23    for(int i = 0; i < input.length(); i++) {
24        if(is_odd_digit(input.at(i))) {
25            input.at(i) = '*'; 
26        }
27    } 
28
29    return 0; 
30} 

This code here has two types of errors. The first is a build error: is_odd_digit is missing a return statement when neither the if nor the else if conditions are true. For instance, running is_odd_digit('a') would trigger neither of these conditions, and C++ would get confused and just not know what to return.

There are several fixes — you can either add return false; to the bottom of the function, or just convert the else if statement into a plain else statement. Both of these would guarantee that the function encounters a return statement, no matter what the input is.

The second error is more subtle, and it’s in the conditions '0' < c <= '9'. While this is a human-readable inequality, it’s not quite a valid C++ condition. It compiles (after fixing the previous error), but it first computes the boolean expression '0' < c, then converts that into an integer value, and finally compares that integer to the character 9. What we mean to check is that '0' < c and c <= '9' are true; we should therefore replace this condition with '0' < c && c <= '9'.

I’m also an imbecile and forgot to add the line cout << input << endl; to the end of the main function…oops.

SAMPLE RUN: 
INPUT   3
OUTPUT    *
OUTPUT   ***
OUTPUT  ***** 

 1#include <iostream>
 2#include <string>
 3#include <vector>
 4
 5using namespace std; 
 6
 7int main() {
 8    // accept user input
 9    int n; 
10    cin >> n; 
11
12    // set up n lines of a single * 
13    vector<string> triangle; 
14    for(int i = 0; i < n; i++) {
15        triangle.push_back("*"); 
16    } 
17
18    // for each i = n-1, n-2, ..., 1, repeat: 
19    // add a * before and after each of the bottom i lines.
20    // add a space before and after the remaining lines. 
21    for(int i = n - 1; i > 0; i--) {
22        for(int j = 0; j < n; j++) {
23            string line = triangle.at(j); 
24
25            if(j < i) { line = " " + line + " "; } 
26            else      { line = "*" + line + "*"; } 
27        } 
28    }
29
30    // print out the triangle 
31    for(int i = 0; i < n; i++) {
32        cout << triangle.at(i) << endl; 
33    } 
34     
35    return 0; 
36} 

This piece of code has no build errors, but running it with the input 3 just produces a vertical line of 3 asterisks. This constitutes a logical error.

What the code intends to do is start with a vertical chain of asterisks, i.e. 3 identical strings in the vector. Each row of output is an individual string in the vector:

*
*
*

Then, it surrounds the bottom two rows with an extra asterisk on either side, and it pads the first row with spaces:

 * 
***
***

Finally, it surrounds the last row with an extra asterisk and pads the first two rows with spaces:

  *
 ***
*****

The issue is when it tries to perform these “padding” operations on the elements of the vector. On line 23, it declares string line = triangle.at(j);, making a copy of the j-th string in the vector triangle. Then, it modifies the variable line as described above, but it doesn’t save these changes to the vector — triangle.at(j) is still the dinky little single-asterisk string it was before.

The fix would be to add the line triangle.at(j) = line; after line 26 so that the changes are “saved” to the vector.

Note that this is a horribly inefficient way to create a triangle. Can you write a solution without using vectors?