Practice Questions¶

In a vector<string>, a repeat is when two identical strings occur next to each other. For example, {"a", "b", "c", "c", "d"} has a repeat that starts at index location 2. However, the vector<string> {"a", "b", "c", "d", "c"} does not have any repeats.

Write two different functions for finding the first repeat in a vector<string>. Call the first function first_repeat_iter(v), and write it so that it uses a loop and no recursion. Call the second function first_repeat_recur(v), and write it so that it uses recursion and no loops.

Sample solution:

int first_repeat_iter(const vector<string>& v) {
    for(int i = 1; i < v.size(); ++i) {
        if (v[i - 1] == v[i]) {
            return i - 1;
        }
    }
    return -1;
}

//////////////////////////////////////////////////

int first_repeat_recur(const vector<string>& v, int begin) {
    int n = v.size() - begin;
    if (n < 2) {
        return -1;
    } else if (v[begin] == v[begin + 1]) {
        return begin;
    } else {
        return first_repeat_recur(v, begin + 1);
    }
    // return -1; // will never be reached, but required by compiler
}

int first_repeat_recur(const vector<string>& v) {
    return first_repeat_recur(v, 0);
}

In this question your task is to write different versions of a function that counts the number of vowels in a string. The vowels are a, e, i, o, and u, both uppercase and lowercase.

For example:

vowel_count("apple") returns 2
vowel_count("APPLE") returns 2
vowel_count("") returns 0
vowel_count("fgh") returns 0

Implement different version of vowel_count using:

a regular C-style while-loop.
a regular C-style for-loop.
a ranged for-loop.
recursion
using the count_if function from the STL.

Hint: First implement a helper function called is_vowel(c) that returns true if the character c is a vowel, and false otherwise.

Sample solution:

bool is_vowel(char c) {
    return c == 'a' || c == 'A' || c == 'e' || c == 'E' ||
           c == 'i' || c == 'I' || c == 'o' || c == 'O' ||
           c == 'u' || c == 'U';
}

int vowel_count_a(const string& s) {
    int result = 0;
    int i = 0;
    while (i < s.size()) {
        if (is_vowel(s[i])) {
            result++;
        }
        i++;
    }
    return result;
}

int vowel_count_b(const string& s) {
    int result = 0;
    for(int i = 0; i < s.size(); ++i) {
        if (is_vowel(s[i])) {
            result++;
        }
    }
    return result;
}

int vowel_count_c(const string& s) {
    int result = 0;
    for(char c : s) {
        if (is_vowel(c)) {
            result++;
        }
    }
    return result;
}

int vowel_count_d(const string& s, int begin) {
    if (begin >= s.size()) {  // base case
        return 0;
    } else if (is_vowel(s[begin])) {
        return 1 + vowel_count_d(s, begin + 1);
    } else {
        return vowel_count_d(s, begin + 1);
    }
}

int vowel_count_d(const string& s) {
    return vowel_count_d(s, 0);
}

int vowel_count_e(const string& s) {
    return count_if(s.begin(), s.end(), is_vowel);
}

Write a function called is_prime(n) that returns true if the int n is a prime number, and false otherwise. An integer n is prime if it is greater than 1, and has exactly two different divisors, 1, and n itself. The first few primes are 2, 3, 5, 7, 11, 13, ….

Sample solution:

bool is_prime(int n) {
    if (n < 2) return false;       // 2 is the smallest prime
    if (n == 2) return true;       // 2 is the only even prime
    if (n % 2 == 0) return false;  // all other even numbers are not prime

    // Next we generate trial divisors, d, starting with 3. We increment d by
    // 2 each time because we know by this point in the function that n is
    // odd, and so there is no need to see if it is divisible by an even
    // number.
    int d = 3;
    while (d * d <= n) {
        if (n % d == 0) {
            return false;
        }
        d += 2;
    }
    return true;
}

Write a function called ends_with_s(v) that takes a vector<string> as input, and returns a new vector<string> containing just those strings in v whose last character is either s or S.

For example:

ends_with_s({"cats", "dog", "hats", "mice"}) returns {"cats", "hats"}

Sample solution:

vector<string> ends_with_s(const vector<string>& v) {
    vector<string> result;
    for(const string& s : v) {
        if (s.back() == 's' || s.back() == 'S') {
            result.push_back(s);
        }
    }
    return result;
}

Consider the following fragment of code:

int a = 3;
int b = 5;

cout << a << " " << b << "\n"; // 3 5
swap(&a, &b);
cout << a << " " << b << "\n"; // 5 3

Implement the swap function.

Sample solution:

void swap(int* p, int* q) {
    int temp = *p;
    *p = *q;
    *q = temp;
}

Write a program that prints all 456,976 four-character strings consisting of lowercase letters a - z:

aaaa
aaab
aaac
...
aaba
aabb
aabc
...
zzzx
zzzy
zzzz

Make your program as short and simple as possible while still being relatively readable.

Sample solution:

int main() {
    for(char a = 'a'; a <= 'z'; ++a)
        for(char b = 'a'; b <= 'z'; ++b)
            for(char c = 'a'; c <= 'z'; ++c)
                for(char d = 'a'; d <= 'z'; ++d)
                    cout << a << b << c << d << "\n";
} // main

Write a recursive program (that doesn’t use any loops or any STL functions) that prints all 676 2-character strings consisting of lowercase letters a - z:

aa
ab
ac
...
ba
bb
bc
...
zx
zy
zz

Sample solution:

void print_az_recur(char c, char a) {
    if (a > 'z') {  // base case
        return;
    } else {
        cout << c << a << "\n";
        print_az_recur(c, ++a);
    }
}

// Recursively prints ca, cb, ..., cz.
void print_az_recur(char c) {
    print_az_recur(c, 'a');
}

void print_recur(char a) {
    if (a > 'z') {
        return;
    } else {
        print_az_recur(a);
        print_recur(++a);
    }
}

// Recursively prints aa, ab, ..., az, ..., za, ... zz.
// There are 26 * 26 = 672 pairs of letters printed.
void print_recur() {
    print_recur('a');
}

int main() {
    print_recur();
} // main

Create a class called Product that stores the name and cost (in pennies, as an int) and works with code such as this:

const Product cheese{"Plasma Cheese", 230};
cheese.println();  // prints: Plasma Cheese, 230

const Product cheese_copy{cheese};
cheese_copy.println();  // prints: Plasma Cheese, 230

Your Product class must also meet these requirements:

It must use an initialization list in its constructors to initialize its variables.

An error is thrown (using the error function from the course) by the constructors if an empty name or negative cost is passed to the constructor. For example:

const Product widget{"Lupper", -450};  // throws an error: -450 is not allowed

const Product shoe{"", 3200};  // throws an error: name can't be empty string

There should be no (legal!) way to set or modify the name or cost of a Product object after it is constructed.
There should be no unnecessary work done or memory used.

Sample solution:

class Product {
    string name;
    int cost;
public:
    Product(const string& n, int c)
    : name(n), cost(c)
    {
        if (cost < 0) error("cost can't be negative");
        if (name.empty()) error("name can't be empty");
    }

    Product(const Product& other)   // copy constructor
    : name(other.name), cost(other.cost)
    { }

    string get_name() const { return name; }
    int get_cost() const { return cost; }

    void print() const {
        cout << "Name=\"" << get_name() << "\", cost=" << cost;
    }

    void println() const {
        print();
        cout << "\n";
    }
}; // class Product

Write a function called is_sorted(v) that tests if the strings in v, a vector<string>, are in alphabetical order. Do it in two different functions: the first should use a loop, and the second should use recursion (with no loops).

Sample solution:

bool is_sorted_a(const vector<string>& v) {
  for(int i = i; i < v.size(); ++i) {
     if (v[i - 1] > v[i]) {
        return false;
     }
  }
  return true;
}


bool is_sorted_b(const vector<string>& v ,int begin, int end) {
    if (end - begin <= 1) {
        return true;
    } else {
      return (v[begin] <= v[begin + 1]) && is_sorted_b(v, begin + 1, end);
    }
}

bool is_sorted_b(const vector<string>& v) {
    return is_sorted_b(0, v.size());
}

Define each of the following terms, and list at least one good thing and one bad thing for each:
1. black box testing
2. white box testing
3. exhaustive testing
Make your answers brief, and use clear, grammatical English.

Sample solution:
1. black box testing is the process of creating test cases for a function based only on the function’s specification, i.e. its header and pre/post conditions. The body of the function is not considered.
  
  One good thing about black box testing is that the test cases can be developed before, or at the same time, as the development of the function itself. Plus, if later the body of the function changes, then the black box test cases are still useful.
  
  One bad thing about black box testing is that it might miss some important test cases that can only practically be discovered by looking at the body of the code.
2. white box testing is the process of creating test cases for a function based only on the function’s implementation, i.e. its body.
  
  One good thing about white box testing is that you can be sure to choose test case that cause every statement in the function to be executed. You can also make sure that important execution paths are tested.
  
  One bad thing about white box testing is that it if the implementation changes, white box test cases may no longer be useful because the thing they tested has changed, or may even have disappeared.
3. exhaustive testing is when you generate all possible test cases for a function. For example, to exhaustively test the absolute value function int abs(int x), you would need to make one test case for every possible value for x. If an int is 32 bits, then that would be \(2^{32}\) test cases, i.e. just over 4 billion test cases.
  
  One good thing about exhaustive testing is that it guarantees that the function being tested returns the correct value in all possible cases.
  
  One bad thing about exhaustive testing is that it is often impractical. For example, you can’t practically do exhaustive testing on any function that takes a string as input because there are an astronomically huge number of possible strings to test for.
In mathematics, the 1-norm of a vector \(\boldsymbol{x} = (x_1, x_2, \ldots, x_n)\) is defined as the sum of the absolute values of the entries, i.e.:

\[\begin{split}\|\boldsymbol{x}\|_1 &= |x_1| + |x_2| + \ldots + |x_n| \\ &= \sum_{i=1}^{n} |x_i|\end{split}\]

Write five different C++ functions, each of which calculates the 1-norm of a mathematical vector in the following different ways:

Represent the mathematical vector as an array of \(n\) doubles. Use a C-style for-loop (with an index variable) in your answer.
Represent the mathematical vector as vector<double>, and use a for- each loop (with no index variable) in your answer.
The same as the previous question, except use a while-loop in your answer.
Represent the mathematical vector as a vector<double>, and use recursion (with no loops) in your answer.

Instead of passing the vector directly to the function, pass in a pointer of type double* representing the first element, and a pointer of type double* representing one past the last element. You would use it like this:

double arr[] = {5.5, -1.0, 2.66, 0.4};
double x = norm(arr, arr + 4);

Sample solution:

#include "error.h"
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

double norm1_a(double v[], int n) {
    double result = 0.0;
    for(int i = 0; i < n; ++i) {
        result += abs(v[i]);
    }
    return result;
}

double norm1_b(const vector<double>& v) {
    double result = 0.0;
    for(double x : v) result += abs(x);
    return result;
}

double norm1_c(const vector<double>& v) {
    double result = 0.0;
    int i = 0;
    while (i < v.size()) {
        result += abs(v[i]);
        i++;
    }
    return result;
}

double norm1_d(const vector<double>& v, int begin) {
    if (begin >= v.size()) {
        return 0;
    } else {
        return abs(v[begin]) + norm1_d(v, begin + 1);
    }
}

double norm1_d(const vector<double>& v) {
    return norm1_d(v, 0);
}

double norm1_e(double* begin, double* end) {
    double result = 0.0;
    while (begin < end) {
        result += abs(*begin);
        begin++;
    }
    return result;
}

int main() {
    double arr[] = {5.5, -1.0, 2.66, 0.4};
    vector<double> v = {5.5, -1.0, 2.66, 0.4};

    double a = norm1_a(arr, 4);
    double b = norm1_b(v);
    double c = norm1_c(v);
    double d = norm1_d(v);
    double e = norm1_e(arr, arr + 4);

    cout << a << "\n" << b << "\n" << c << "\n"
         << d << "\n" << e << "\n";
}

The following questions are related:
1. Write a function called is_upper(c) that returns true if the char c is one of the uppercase letters 'A', 'B', …, 'Z', and false otherwise.
  
  Solution:
```
bool is_upper(char c) { return 'A' <= c && c <= 'Z'; }
```
2. Write a function called to_lower(c) that returns the lowercase version of c if c is an uppercase letter, and c unchanged otherwise.
  
  Solution:
```
char to_lower(char c) {
  if (is_upper(c)) c = c + 32;
  return c;
}
```
3. Using a loop (and no recursion), write a function called to_lower_loop(s) that returns a new string that’s the same as string s, except all uppercase letters have been converted to lowercase.
  
  Solution:
```
string to_lower_loop(string s) {
  for(int i = 0; i < s.size(); i++) {
    s[i] = to_lower(s[i]);
  }
  return s;
}
```
4. Using recursion (and no loops), write a function called to_lower_rec(s) that returns a new string that’s the same as string s, except all uppercase letters have been converted to lowercase. You can write helper functions if needed.
  
  Solution:
```
string to_lower_rec1(const string& s, int begin) {
  if  (begin >= s.size()) {
    return "";
  } else {
    string first = string(1, to_lower(s[begin]));
    return first + to_lower_rec1(s, begin + 1);
  }
}

string to_lower_rec1(const string& s) {
  return to_lower_rec1(s, 0);
}
```

The following questions are related:

Implement the following function:

// Pre-condition:
//    none
// Post-condition:
//    returns a new string that is the same as s, but all
//    occurrences of c have been removed
// Example:
//     remove_all('a', "alley cat") returns "lley ct"
string remove_all(char c, const string& s)

Solution:

// other good solutions are possible!
string remove_all(char c, const string& s) {
  string result;
  for(int i = 0; i < s.size(); i++) {
    if (s[i] != c) {
      result += string(1, s[i]);
    }
  }
  return result;
}

Implement the following function:

// Pre-condition:
//    none
// Post-condition:
//    returns a new string that is the same as s, but all
//    occurrences of every character in bad have been removed
// Example:
//     remove_all("l a", "alley cat") returns "eyct"
string remove_all(const string& bad, const string& s)

Solution:

// other good solutions are possible!
string remove_all(const string& bad, const string& s) {
  string result = s;
  for(char c : bad) {
    result = remove_all(c, result);
  }
  return result;
}

Previous topic

Next topic

Practice Questions¶