Discussion 4: Handcoding and mock code review

Discussion 4 on Sep 29-30 comes the week before the project 1 code review, and a week and a half before the first midterm. To prep for both, we will work through some hand-coding problems and then peer code-review each other's work.

Students should work in pairs, with each person in a pair working on a different problem before swapping for feedback and questions.

The problems are described first, below, and then the code review instructions are available after that for reference.

Problem 1: How much room is left

#![allow(unused)]
fn main() {
struct Backpack {
    weights: Vec<u32>,
    limit: u32,
}
}

weights holds the weight of each item in the backpack, in grams. limit is the most the backpack can carry.

Write two methods.

(a) room_left gives back how many grams of room are left. If the backpack is already at or over its limit, it gives back 0.

(b) try_add takes the weight of one new item and tries to put it in. If it fits, it goes in and the method gives back true. If it does not fit, the backpack is left alone and the method gives back false.

#![allow(unused)]
fn main() {
impl Backpack {

}
}

Worked examples for room_left:

Worked examples for try_add, each call picking up where the last one left off, starting from weights = [300, 450, 120] and limit = 2000:

Problem 2: How many halvings

Write a function halvings that takes a u32 and gives back how many times you can halve it before it reaches 1, using whole-number division. Write both a version with a loop and a version with recursion. Which do you prefer?

Worked examples:

Discussion 4 Handcoding Guide

Overview

The actual code review for the project include a rubric that is split across several categories, such as "explain this to me" questions, "what if this were different" questions, Git questions, etc. Due to practical constraints, this mock code review only has 3:

• Explain this to me.
• What if this were different?
• Did you actually write this code?

You will grade each other in an identical manner to how we will grade you for the actual code review, with the following criterion:

There will be two questions for each section, and answering the question correctly should account for the bulk of the grade, the follow-up mostly seperates a two from a three.

Note: This grading criterion only pertains to the first two sections here. The last one will also be graded out of three, but by evaluating how well the student did at climbing the question ladder (see below).

Explain this to me

This section pertains to reasoning through code and explaining your thought process behind writing it.

Problem 1: How much room is left?

Primary Question: What happens when an item fits exactly, such that no space is left over? What does this tell you about using < vs <=?

Secondary Questions:

• Checking the limit in room_left() with >= vs > doesn't matter here, but why might you want one vs the other, philosophically?
• Did try_add call room_left(), or recompute the total from scratch? Both work, why did you do it the way you did?

Problem 2: How many halvings?

Primary Question: Which do you prefer and why? Do you expect one to be faster than the other, or similar?

Secondary Questions:

• What is your base case in your recursive implementation? What does the recursive call and subsequent stack look like?
• For the iterative case, did you first check if current <= 1? If not, why isn't it necessary to separate it out like in the recursive version?

What if this were different

This section pertains to evaluating hypothetical counterfactuals and explaining how they would have changed your code had they been true.

Problem 1: How much room is left?

Primary Question: How might the composition of our Backpack and its implementation been different if weights were represented as a fixed length array instead of a vector array?

Secondary Questions:

• If we wanted to implement some method retrieve to Backpack which allows us to take out items from the top of the backpack, what abstract data structure should weights be?
• If the first item we put in the bag is the maximum value storable in a u32 representation, what will happen when we add another item?

Problem 2: How many halvings?

Primary Question: Consider the answer you gave to the preference question posited in the first question. What problem might warrant the other option?

Secondary Questions:

• Whole number division in Rust naturally truncates the decimal value, meaning it always rounds down. Would the speed of your algorithm be affected if it instead rounded up?
• Instead of halving the value, assume that we instead quarter the value each time. How do the big O runtimes compare?

Did you actually write this code

This section ensures that you actually wrote your code, and that you can provide actual line-by-line explanations for how it works. In the actual code review, this section is represented slightly differently as a ladder of questions, so this section only contains one question with multiple segments. Allot one point per ladder rung climbed.

Problem 1: How much room is left?

Question Ladder: Point to the line in room_left that ensures you consider every item in the backpack, weight wise. Why did you choose to implement it this way? Are there alternative ways?

Problem 2: How many halvings?

Question Ladder: Point to the line in both of your solutions that ultimately keeps track of how many halvings it takes. What is different about how each is stored? Are each mutable or immutable? Explain.

Answer key

These are what a full-credit answer should touch on. Your partner does not need to use these exact words, but if they miss the core idea of the primary question, that's a 1 at most. The "why" parts are what separate a 2 from a 3.

Explain this to me

Problem 1: How much room is left?

Primary: When an item fits exactly, weight == room_left(), so the check has to be weight <= self.room_left(). For instance, with <, try_add(630) would wrongly return false even though the backpack can hold exactly 630 more grams.

Secondary:

• >= vs > in room_left: when total == limit, both branches give back 0 so the output is the same. The reason the check exists is so that u32 can't go negative: if total > limit, self.limit - total would underflow. Either >= or > protects against that. >= says "full or over means no room" explicitly, while > relies on the subtraction happening to give 0.
• Calling room_left() vs recomputing: calling it avoids duplicating the summing loop, so if the rule for "how much room is left" changes, it only changes in one place. Also reduces boiler plate code. Both are O(n) in the number of items.

Problem 2: How many halvings?

Primary: Either preference is fine if it's justified. Both do the same number of halvings, so both are O(log n) time. The loop uses O(1) extra space, while the recursion uses one stack frame per halving, so O(log n) space. For a u32 that's at most 32 frames, so in practice neither is noticeably faster. The recursive version reads closer to the definition ("one halving, plus however many the half needs").

Secondary:

• The base case is n <= 1, which gives back 0. For halvings(10), the calls stack up as halvings(10) → halvings(5) → halvings(2) → halvings(1), then unwind: halvings(1) gives 0, halvings(2) gives 1 + 0 = 1, halvings(5) gives 2, halvings(10) gives 3.
• No separate check is needed in the loop, because the while current > 1 condition is checked before the first pass. If n is 0 or 1, the body never runs and count stays 0. The loop condition plays the role of the base case.

What if this were different

Problem 1: How much room is left?

Primary: A fixed-length array ([u32; N]) has its size set at compile time, so there's no push. The struct would need an extra field such as count: usize to track how many slots are actually filled. try_add would write to weights[count] and bump count, and it would also have to give back false when the array is full, even if the weight fits. room_left would only sum 0..count, not the whole array. A Vec handles all of this for us by growing as needed.

Secondary:

• Taking items out from the top means the last item in is the first item out, which is a stack (LIFO).
• Nothing bad happens if properly implemented. try_add(u32::MAX) only succeeds if limit is also u32::MAX (a u32 limit can't be any bigger). After that, room_left() is 0, so any later try_add(w) with w > 0 gives back false and the backpack is untouched. The danger is in other ways of writing it:
  • If try_add checks total + weight <= self.limit, then u32::MAX + 1 overflows.
  • If someone builds Backpack { weights: vec![u32::MAX, 1], limit: 2000 } directly, the summing loop in room_left overflows.

Problem 2: How many halvings?

Primary: Any reasonable pairing works. Recursion fits problems that naturally split into smaller copies of themselves, especially more than one copy where a loop would need to manage its own stack. A loop is the better choice when the recursion would get very deep, e.g. counting down by 1 from a large n makes O(n) stack frames and can overflow the stack, while a loop uses constant space.

Secondary:

• Rounding up ((current + 1) / 2) is still O(log n). It sometimes takes one extra step, e.g. 10 → 5 → 3 → 2 → 1 is 4 halvings instead of 3. It still stops because for any value of 2 or more, rounding up still makes it smaller.
• Quartering takes log₄(n) steps, which is log₂(n) / 2, so about half as many. But logs of different bases differ by only a constant factor, so both are O(log n).

Did you actually write this code

One point per rung, as described above.

Problem 1: How much room is left?

1. Point to it: the loop header, e.g. for i in 0..self.weights.len(), together with total += self.weights[i].
2. Why: any honest reason tied to their code, e.g. indexing is what they're used to from arrays, or they wanted i available.
3. Alternatives: Any other valid loop header works, i.e. for w in &self.weights { total += w; }.

Problem 2: How many halvings?

1. Point to it: in the loop version, count += 1. In the recursive version, the 1 + in 1 + halvings(n / 2).
2. How it's stored: the loop keeps a single variable, count, and updates it in place each pass. The recursive version has no count variable at all. The count is built up out of the values given back as the stack unwinds, with each frame adding 1 to what the frame below it gave back.
3. Mutable or immutable: count (and current) must be let mut because they change. Everything in the recursive version is immutable, since each call gets its own n and nothing is ever reassigned.