Midterm Review

CS 106B: Programming Abstractions

Fall 2024, Stanford University Computer Science Department

Lecturers: Cynthia Bailey and Chris Gregg, Head CA: Jonathan Coronado

Announcements

  • For even more review, see review session led by Jonathan last Thursday! Video and slides available, see pinned Ed post.
  • For important announcements, be sure to see the weekly announcements post on the Ed Q&A board! https://edstem.org
  • Also on Ed: live lecture Q&A with Chris & Jonathan

Slide 2

The Midterm Exam

  • Time: 2 Hours
  • 4 questions.
  • I’d plan 25 minutes per problem, which leaves you 20 minutes at the end to re-check your work etc.
  • Very first thing you should do: write your SUID on every page.
    • Forgetting this would be the saddest reason to lose points! And you will NOT be given extra time after time is called to do this. No writing at all after time is called!

Slide 3

Exam Format

  • Format: Handwritten on paper
  • I would be sure to solve some practice problems with pen & paper so this doesn’t feel completely new and strange!
  • In grading, we try to ignore minor "typos" in handwritten code that likely would have been prevented or caught by an IDE Just make sure intent is clear—i.e. we are happy to ignore that you wrote "stepcount" instead of "stepCount," but not if you have variables with both names in your code and we actually do need to know which one it is on a given line.
  • You won’t be able to actually compile, run, and test your paper-written code, but you’ll very much want to be thinking in terms of what you would put in "STUDENT TEST" for the code you’re writing.
    • To simulate a test: pick a concrete example, then try to set your intent aside and painstakingly trace through the example input line by line to check.
    • (Note: familiarity with our STUDENT TEST code format is expected knowledge on the exam.)

Slide 4

Exam Topics

(Same general categories as the practice exam)

  • C++ Fundamentals
  • ADTs
  • Big-O
  • Recursion

Slide 5

Exam Rules

  • Closed book, no devices
    • This is actually to make the exam easier, I promise! 
  • Reference Sheet (included in exam)
    • It’s on the course website, so study it ahead of time!
  • Cheat Sheet (your own to bring with you)
    • One sheet of paper (8.5x11), both sides, handwritten

Slide 6

Sample Q1: C++ fundamentals

  • What to Expect:
    • Strings
    • Loops, nested loops
    • Multi-part conditionals inside a loop
    • Thinking carefully about edge cases
  • Grid of theater seat reservations
    • You are given a Grid<string> representing the seating chart of a theater.
    • Your function will help customers looking to make group reservations by taking the grid and looking for a row with at least n consecutive open seats.
    • If the seat has been reserved, the string is that person’s name, otherwise the string is empty string.
    • Return the GridLocation of the leftmost seat of the matching block of seats.
      • You may assume a satisfying location exists.
  • Strategy:
    • We need to loop over the Grid. Should we use for (string entry : grid) style loop?
    • Not in this case, because we need to be aware of our current row (blocks can’t cross from one row to another)
    • Use int row/col nested loops
    • Within a row, we need to count free seats
    • Start count at 0 again each row
    • Iterate over cols, incrementing if empty
      • If not empty, reset count to 0
    • If we find something that works, immediately store location and return

Slide 7

Sample Q1 Solution

GridLocation findSeats(Grid<string>& seatGrid, int n) {
   GridLocation loc(0, 0);
   for (int r = 0; r < seatGrid.numRows(); r++) {
      int count = 0; // count consecutive empty seats
      for (int c = 0; c < seatGrid.numCols(); c++) {
         if (seatGrid[r][c] == "") {
            count++;
            if (count == n) {
               loc = { r, c – n + 1 };
               return loc;
            } 
         } else {
            count = 0; // if non-empty string, need to reset counter
         }
      }
   }
   return loc; // shouldn’t reach this but keep compiler happy
}

Slide 8

Sample Q2: ADTs

  • What expect:
    • Uses of the ADTs that really "fit" the situation
    • Either by our design, or we ask you to choose the best design
    • Code that is much simpler (!!) if you use elegant ADT features
      • Range-based for loop (example: for (string s : themap))
      • Push/pop on a Stack vs manual equivalent on a Vector
      • Set operations vs manual equivalent
      • One kind of ADT alongside or inside another kind of ADT
    • Theme: really let the ADTs “shine”
  • Write a function that takes a Queue<int> and returns a Queue<int> where the elements are in reverse of the original order.

  • The challenge: Your function may declare only one local variable: your choice of either a Stack or a Queue.

  • Queue<int> reverse(Queue<int> q);

Slide 9

Sample Q2 solution

Queue<int> reverse(Queue<int> q) {
    Stack<int> theStack;
    while (!q.isEmpty()) {
        theStack.push(q.dequeue());
    }
    while (!theStack.isEmpty()) {
        q.enqueue(theStack.pop());
    }
    return q;
}

Slide 10

Sample Q3: Big O

  • What to Expect
    • ADT operations with known costs, inside loops and recursive function calls
    • Your job is mainly to analyze the loop or recursion structure, then you can just plug in what you see for that ADT operation, using the Reference Sheet
    • Loops one after the other: additive cost
    • Loops nested in one another: multiplicative cost
    • Remember to simplify! (O(N), not O(3N + 5))
  • (no additional samples for this one—refer to practice exams)

Slide 11

Sample Q4: Recursion

  • What to Expect:
    • Similar to pre-backtracking recursion examples from lecture: Fibonacci, Coin Flip, Fractals, permutations
  • This roller coaster at the Santa Cruz Beach Boardwalk is a train of rows that are two seats wide.
    • There are N amusement park guests in line for the roller coaster, and they must board in order. The train is loaded from front to back.
    • When guests reach the front of the line, they tell the ride attendant whether they want to ride alone (1 person that row) or share with the next person in line (2 people in that row).
    • Assume that the train has at least N rows, so it is long enough to accommodate all N riders in any configuration (rows aren't skipped except there are possibly extra empty rows after all riders have been seated).
    • How many different rider configurations are possible?
    • int countConfigs(int n);
    • Can we make this faster using memos?
    • int countConfigs(int n, Map<int, int> memos);
    • See Fibonacci example!
  • Strategy:
    • N is the number of riders guests, and recursively will track how many remain to be seated
    • Base cases: 0 guests, 1 guest, 2 guests
    • Recursive case: Each recursive call we either seat 1 or 2 guests (decreasing the remaining guests by 1 or 2). For each choice, recursively explore how many options from there.

Slide 12

Sample Q4 Solution

int countConfigs(int n) {
    if (n < 3) {
        return n;
    }
    return countConfigs(n - 1) + countConfigs(n - 2);
}