Lecture Quizzes

These are the questions and answers from the Gradescope lecture quizzes that we gave out this quarter.

Lecture 4

1. References

In lecture we discussed passing parameters by reference. Look at the following code snippet:

void bamboozle(int& a, int& b, int c) {
    c = b;
    a += c;
    b++;
}

int main() {
    int a = 1;
    int b = 4;
    int c = 3;
    bamboozle(c, a, b);
    cout << a << endl;
    cout << b << endl;
    cout << c << endl;
    return 0;
}

Select all which are true:

A. The first cout will print "2"
B. The second cout will print "1"
C. The 3rd cout will print "7"

2. Vectors

Consider the following code snippet:

Vector<char> vec;
vec.add('c');
vec.add('b');
vec.add('a');
vec.insert(1, 'z');
vec.remove(3);

Select all which are true:

A. vec.get(2) and vec[2] will give the same value
B. 'z' is the first element of the vector
C. vec.remove('a') would accomplish the same thing as the last line
D. The lines putting 'a' and 'z' in the vector were the same amount of work for the computer
E. vec.size() == 3

3. Vectors and Loops

Which of the following is a valid way to loop over a vector to print each of its elements?

Vector<int> v = {1, 2, 3};

\\ Method A
for (int i = 0; i < v.size(); i++) {
    cout << v[i] << endl;
}

\\ Method B
for (int elem : v) {
    cout << v[elem] << endl;
}

\\ Method C
for (int elem : v) {
    cout << elem << endl;
}

A. Method A
B. Method B
C. Method C

4. Grids

Consider the following grid:

Grid<int> mat(3,3);

Which of the following are true?

A. mat.inBounds(3, 1) will return true
B. mat.numRows() will return 2
C. mat.numRows() will return 4
D. Accessing mat[3][3] will cause an error
E. We can construct a grid where the rows are each different lengths

Lecture 5

1. Stacks

Consider the following code snippet:

Stack<string> pancakes;
pancakes.push("blueberry");
pancakes.push("maple");
pancakes.push("chocolate chip");

Select all which are true:

A. pancakes.pop() will return "blueberry"
B. pancakes.pop() will return "chocolate chip"
C. We can access the string "maple" in the middle using pancakes[1] or pancakes.get(1)

2. Queues

Consider the following code snippet:

Queue<int> nums;
nums.enqueue(1);
nums.enqueue(2);
int a = nums.dequeue();
nums.enqueue(3);

Select all which are true:

A. a == 1
B. nums.peek() would return 2
C. nums.size() == 3

3. Stacks and Queues

Consider the following code snippet:

Queue<int> q = {1, 2, 3, 4, 5};
for (int i = 0; i < q.size(); i++) {
     int value = q.dequeue();
     cout << value << " ";
  }

Which numbers will be printed?

A. 1
B. 2
C. 3
D. 4
E. 5

Lecture 6

1. Map Tweets

We want to create a map called tweets that looks like the following: { "stephen": "tweet1", "draymond": "tweet2" }

Select all of the following code snippets that would produce a map like this.

Code snippet 1:

Map<string, string> tweets;
tweets["stephen"] = "tweet1";
tweets["draymond"] = "tweet2";

Code snippet 2:

Map<string, string> tweets;
tweets.put("draymond", "tweet2");
tweets.put("stephen", "tweet1");

Code snippet 3:

Map<string, string> tweets;
tweets.put("tweet1", "stephen");
tweets.put("tweet2", "draymond");

Code snippet 4:

Map<string, string> tweets;
tweets.put("stephen") = "tweet1";
tweets.put("draymond") = "tweet2";

A. 1
B. 2
C. 3
D. 4

2. Set Locations

Suppose we have the following code.

Set<string> csLocations;
csLocations.add(“huang”);
csLocations.add(“durand”);
csLocations.add(“huang”);
csLocations.add(“gates”);

for (int i = 0; i < csLocations.size(); i++) {
   cout << csLocations[i] << ", ";
}

Set<string> dormLocations;
dormLocations.add("rinconada");
dormLocations.add("durand");
dormLocations.add("griffin");
for (string location : dormLocations) {
   cout << location << ", ";
}

Set<string> allLocations = csLocations + dormLocations;

Select all which are true:

A. The first loop will not work
B. The second loop will not work
C. csLocations.size() == 4
D. allLocations.size() == 5

Lecture 7

1. Big-O basics

Select all that Big-O analysis takes into account:

A. how big each step is
B. how fast the computer is
C. the amount of time it takes to run code
D. the number of steps it takes to run code

2. Big-O Boogaloo

void vector_fun(int n) {
  Vector<int> vec;

  // Part 1
  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      vec.insert(0, i + j);
    }
  }

  // Part 2
  for (int v : vec) {
    for (int i = 0; i < 100000; i++) {
      cout << v << " ";
    }
  }
  cout << endl;

  // Part 3
  for (int i = 1; i < vec.size(); i*= 2) {
    cout << v << " ";
  }
}

Select all which are true:

A. Part 1 is O(\(n\ log(n)\))
B. Part 1 is O(\(n^2\))
C. Part 1 is O(\(n^3\))
D. Part 2 is O(\(n\))
E. Part 2 is O(\(n^3\))
F. Part 3 is O(\(log(n)\))
G. Part 3 is O(\(n^2\))
H. The whole function is O(\(n^2\))
I. The whole function is O(\(n^2\ log(n)\))
J. The whole function is O(\(n^3\))

Lecture 8

1. Recursion Basics

Select all which are true:

A. A recursive function doesn't necessarily need a base case B. A recursive function always has a recursive case C. The recursive case should work on a simpler version of the original problem D. It is ok for a recursive function to not have a case handling certain valid inputs

2. Reading Recursion

Look at the following code, with line numbers labeled.

line 1: int function(int num) {
line 2:   if (num == 1) {
line 3:      return 7;
line 4:   } else {
line 5:      return 1 + function(num - 1);
line 6:   }
line 7: }

Select all which are true:

A. Lines 2-3 are the base case
B. Lines 2-3 are the recursive case
C. Line 5 is the base case
D. Line 5 is the recursive case
E. function(4) == 10
F. function(2) == 9
G. This function should probably have a comment indicating that only positive values of num are valid inputs

3. Recursive Big-O

Look at the following code, with line numbers labeled (same as above).

line 1: int function(int num) {
line 2:   if (num == 1) {
line 3:      return 7;
line 4:   } else {
line 5:      return 1 + function(num - 1);
line 6:   }
line 7: }

What is the Big-O of this function?

A. O(\(log(n)\))
B. O(\(n\))
C. O(\(n^2\))
D. O(\(n!\))

Lecture 9

1. Fractal Facts

Select all which are true:

A. A fractal is a shape which is made up of smaller versions of itself
B. Fractals are an example of recursion
C. Fractals are largely a CS-exclusive concept and do not appear in nature

2. Sierpinski Sneak Attack!

An order \(n\) Sierpinski triangle is a fractal made up of three order \(n-1\) Sierpinski triangles joined corner to corner, with an order 0 triangle being a completely filled in triangle as the base case. Look at the below image.

The first object is an order 0 Sierpinski triangle, and the second is an order 1 Sierpinski triangle. What order is the 3rd object?

A. 2nd order
B. 3rd order
C. 4th order

Lecture 10

1. Sequence Generation

Consider the following function.

void generateSequences(int len, string soFar)
{
    if (length == 0) {
        cout << soFar << endl;
    } else {
        generateSequences(length - 1, soFar + " A");
        generateSequences(length - 1, soFar + " B");
        generateSequences(length - 1, soFar + " C");
    }
}

Select all which are true:

A. The height of the decision tree represents len (or len + 1 depending on how you count)
B. Each layer of the decision tree will be twice as wide as the layer above it
C. This function will print every possible string of 'A', 'B', and 'C' of length len or less
D. To have this function print all length len sequences of 'A', 'B', and 'C', the user must always pass in the empty string to "soFar"
E. Since soFar should always be the empty string, it is an unnecessary parameter and we can just delete it

2. Permutations

Consider the following functions:

void mystery(string soFar, string rest) {
  if (rest.length() == 2) {
      cout << soFar + rest[0] + rest[1] << endl;
      cout << soFar + rest[1] + rest[0] << endl;
  } else {
      for (int i = 0; i < rest.length(); i++) {
          string remaining = rest.substr(0, i) + rest.substr(i+1);
          mystery(soFar + rest[i], remaining);
      }
  }
}


void mystery(string word) {
  mystery("", word);
}

Select all which are true:

A. In most cases, mystery(word) will print all possible substrings of length word.length() - 1
B. In most cases, mystery(word) will print all possible permutations of word
C. There is a bug caused by the base case of the first function
D. There is a bug caused by the recursive case of the first function
E. The fact that there are two functions called mystery is a bug that will cause problems when we try to run this code

Lecture 11

1. Backtracking Basics

Which of the following are true about recursive backtracking:

A. We follow the strategy of "choose, explore, unchoose"
B. The choose step is represented by going down the decision tree
C. The unchoose step is represented by going up the decision tree
D. Backtracking always requires us to explore the entire decision tree

2. Backtracking Types

Select all which are true:

A. If we want to find out whether a particular problem has a solution, we may be able to return true before exploring the entire decision tree.
B. If we want to find out whether a particular problem has a solution, we may be able to return false before exploring the entire decision tree.
C. If we want to return any solution to a problem, we may be able to stop before exploring the entire decision tree.
D. If we want to find the best solution to a problem, we may be able to return before exploring the entire decision tree.

Lecture 12

1. Knapsack Notes

Select all which are true about the Knapsack problem decision tree:

A. There is one layer for each object
B. Each layer is twice as wide as the previous
C. Every "leaf" (bottom endpoint of a branch) in the tree will be the same distance from the top \

2. Knapsack Knowledge

Select all which are true about the Knapsack solution code from lecture (reproduced below):

int fillKnapsack(Vector<objectT> &objects, int weight, int currentScore,
                 Vector<objectT> &currentSolutionObjects,
                 Vector<objectT> &bestSolutionObjects) {
    // base case #1: too much weight!
    if (weight < 0) {
        return 0;
    }

    if (objects.isEmpty()) {
        // calculate the score of the best solution
        int bestScoreSoFar = 0;
        for (objectT obj : bestSolutionObjects) {
            bestScoreSoFar += obj.value;
        }

        if (currentScore > bestScoreSoFar) {
            bestSolutionObjects = currentSolutionObjects;
        }
        return currentScore;
    }

    // remove an object for recursion, and save
    objectT originalObject = objects.remove(objects.size() - 1);

    // don't include the object
    int scoreWithoutObject =
        fillKnapsack(objects, weight, currentScore, currentSolutionObjects,
                     bestSolutionObjects);

    // include the object
    int newWeight = weight - originalObject.weight;
    int newScore = currentScore + originalObject.value;

    // put the object into the current bag
    currentSolutionObjects.add(originalObject);

    int scoreWithObject =
        fillKnapsack(objects, newWeight, newScore, currentSolutionObjects,
                     bestSolutionObjects);

    // remove the object from the current solution
    currentSolutionObjects.remove(currentSolutionObjects.size() - 1);

    objects.add(originalObject);

    return max(scoreWithObject, scoreWithoutObject);
}

A. currentSolutionObjects stores our best guess about the solution until we've found our final answer
B. currentScore represents the amount of weight currently in the backpack
C. weight represents the total amount of weight the backpack could hold if it were empty
D. We compute the best score by recursively finding the best score possible while including an object, and the best score possible while excluding that object, and picking the better of those two scores. \

Lecture 13

1. Giraffe

We want to write a class that models a Giraffe. We have the following code, some of the lines labeled with numbers. ​

// Giraffe.h
​
class Giraffe {
  public:
    (1) Giraffe(string name, double height); 
    (2) Giraffe(string name); 
​
    (3) void eatGrass(double grassAmount); 
    (4) void walkAround(double timeToWalk);
​
  private:
    (5) string _name;
    (6) double _height;
};
​

Select all which are true: ​ A. Lines 1 and 2 are constructors
B. There will be an error since we have two constructors of the same name
C. Lines 3 and 4 are public member variables
D. A user with a giraffe object named gir can change its height to 10 by writing gir._height = 10;.
​

2. Class Facts

If we put #include giraffe.h at the top of one of our code files, which of the following are ways to create a giraffe object? ​ A. Giraffe gina;
B. Giraffe gabriel();
C. Giraffe gerald("gerald");
D. Giraffe ("Gracie", 10.0);
E. Giraffe gianna("Gianna", 9.5);
F. Giraffe gabriella = "Gabriella"
​

Lecture 14

1. Storage Basics

When would we want to use a dynamically allocated array over a statically allocated array?

A. When we want persistent memory that we have control over deleting.
B. If we want to resize the array.
C. If we don’t want to do the extra work of deleting the array. \

2. Function Fiasco

Consider the following snippet:

int myFunction() {
  int* myArray = new int[2];
  heapArr[0] = 7;
  heapArr[1] = 13;
  return 42;
}

Which of the following are true about the above code?

A. It will compile / run smoothly
B. It will cause a memory leak
C. It will crash
D. No issues here \

3. New

Select all which are true:

A. Every call new char call you make should have a matching call to delete somewhere in your code
B. Every call new int[] call you make should have a matching call to delete somewhere in your code
C. If you call new in a class's constructor, a good place to call delete is the destructor
D. Accessing out of bounds in an array will always cause it to crash
E. Creating a new int array using new int[10] will create an array with 10 int slots, each initialized to 0 \

Lecture 15

1. More memory issues

Which of the following code snippets won’t cause any memory issues?

Snippet 1:

int* arr = new int[3];
delete [] arr;
arr[0] = 5;

Snippet 2:

int* arr = new int[3];
arr[0] = 5; 
delete [] arr;

Snippet 3:

int* arr = new int[3];
arr[0] = 5; 

Snippet 4:

int* arr = new int[3];
arr[0] = 5; 
delete [3] arr;

A. 1
B. 2
C. 3
D. 4

2. Pointers

What would we expect to printed out by the following code, with print statements numbered?

double *pieLoc = nullptr;
(1) cout << pieLoc << endl;
pieLoc = new double;
(2) cout << pieLoc << endl;
double iLikePie = 3.14;
*pieLoc = iLikePie;
(3) cout << *pieLoc << endl;
iLikePie = 6.28;
(4) cout << *pieLoc << endl;
pieLoc = &iLikePie;
(5) cout << *pieLoc << endl;

Select all which are true:

A. We don't know what (1) will print
B. (1) will print 0
C. (2) will print the address of the double created on the previous line
D. (2) will print 0
E. (3) will print 3.14
F. (3) will print the address of iLikePie
G. (4) will print 6.28
H. (4) will print the address of iLikePie
I. (5) will print 6.28
J. (5) will print the address of iLikePie

Lecture 16

1. Changing memory size

What steps must we take any time we resize a dynamic array?

A. Create a new array with a new size
B. Initialize the new array elements to 0
C. Copy the old array elements to the new array
D. Delete the old array
E. Point the old array variable to the new array
F. Delete the pointer to the new array
G. Update the capacity variable for the array

2. Resizing

What amount do we usually increase a dynamic array's size by, and why?

A. Add 1, so we don't use too much space
B. Add 10, so we don't have to resize every time
C. Double it, so adding a new element remains O(1) in expectation

Lecture 17

1. Applications

What are some real world places where priority queues are used?

A. Triage
B. Vaccines
C. Waiting in line in Wilbur
D. Organ donation
E. College admissions
F. Social assistance programs

2. Fairness

Consider this quote from the lecture on the fairness of an algorithm for scoring the need of the unhoused:

“I’m doing the matching and it’s very unbiased as far as our work because the computer tells me, based on a scoring system, which families are higher need than other families”

A. Having a scoring system make the decisions means it will be fair and neutral
B. The fact that a system is deciding does not necessarily make it unbiased
C. The systems we design encode certain values, and so without careful thought systems can be inequitable

Lecture 18

1. Heap Issues

Look at the following tree:

         13 
        /   \ 
      19     36     
     /       /  \
   24       28  27 
  /  \
25   26 

What, if anything, is wrong with this structure if it claims to be a min-heap?

A. The 36 can't be above its current children
B. The 28 and the 27 are in the wrong order
C. The 26 needs to move to fill in the third layer

2. Heap Maintenance

Which of the following are true about maintaining heaps?

A. Whenever we want to insert a new element, we start by putting it in array[0]
B. We start by inserting it at the end of the array
C. After insertion, we swap an element with its parents until the heap property is satisfied
D. When we want to remove the top element, we bubble it downwards
E. To remove the top element, we swap it with the last element, then bubble that new top element downwards