Truest Stack Detectives

The questions below are due on Sunday November 01, 2026; 11:59:00 PM.
 
You are not logged in.

Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.
Back to Exercises
If you have not completed the Stack Detective and True Stack Detectives exercises, then please complete those first before moving on to this exercise.

This is a stack study question taken from a previous exam. This should help give you a sense of the level of difficulty you should be ready to see on assessments in this course. If you feel comfortable with this category of question, we suggest trying to answer everything in one attempt like a real exam. If you're not comfortable yet, answer one by one and view explanation to keep you on the right track.

Here is a C implementation of a function linearConvergence that determines if a series of operations on input leads to convergence to 0. The function returns depth if the input is ever equal to 0 and 0 if the maximum recursive depth is exceeded.

int linearConvergence(int input, int alpha, int beta, int depth) {
    if (depth >= MAXIMUM_DEPTH) {
        return 0;
    }
    
    int shifted = input >> alpha;
    
    if (input == 0) {
        return depth;
    } else if (input > 0) {
        return linearConvergence(shifted - beta, alpha, beta, depth+1);
    } else {
        return linearConvergence(shifted + beta, alpha, beta, depth+1);
    }
}

In RISC-V, this function has the equivalent implementation shown below. stack is a custom instruction that prints the stack trace and the value of stack pointer whenever it executes. It does not modify the state of the system (registers, memory etc. in any way).

linearConvergence:
    addi t0, zero, MAXIMUM_DEPTH
    blt a3, t0, body
    stack                 # Get stack trace
    addi a0, zero, 0
    jalr zero, 0(ra)
body:
    addi sp, sp, -8
    sw s0, 0(sp)
    sw ra, 4(sp)
    stack                 # Get stack trace
    sra s0, a0, a1
    blt a0, zero, negative
    blt zero, a0, positive
    ???
    jal zero, end
negative:
    add a0, s0, a2
    addi a3, a3, 1
    jal ra, linearConvergence
    jal zero, end
positive:
    sub a0, s0, a2
    addi a3, a3, 1
    jal ra, linearConvergence
End:
    lw s0, 0(sp)
    lw ra, 4(sp)
    addi sp, sp, 8
    stack                 # Get stack trace
    jalr zero, 0(ra)

Complete the line left blank in the code so that the assembly implementation matches the C implementation.

We obtain the stack trace just before the first call to the function linearConvergence occurred (TIME 0 in the table). Then we run linearConvergence to determine convergence. Some stack traces are produced as given in the table below. The last row of the table also gives you the value in the register sp at the corresponding time. Execution may not have reached completion by time point TIME 5.

Address TIME 0 TIME 1 TIME 2 TIME 3 TIME 4 TIME 5
0x000802a0 0x000a05a0 0x000a05a0 0x000a05a0 0x000a05a0 0x00000003 0x00000003
0x000802a4 0x00000211 0x00000211 0x00000211 0x00000211 0x00000270 0x00000270
0x000802a8 0xfffffffe 0xfffffffe 0xfffffffe 0xfffffffe 0xfffffffe 0xfffffffe
0x000802ac 0x00000000 0x00000000 0x00000000 0x00000260 0x00000260 0x00000260
0x000802b0 0x8f000010 0x8f000010 0x0000000b 0x0000000b 0x0000000b 0x0000000b
0x000802b4 0x0000001a 0x0000001a 0x00000270 0x00000270 0x00000270 0x00000270
0x000802b8 0x00001986 0x00000019 0x00000019 0x00000019 0x00000019 0x00000019
0x000802bc 0x00001986 0x00000214 0x00000214 0x00000214 0x00000214 0x00000214
0x000802c0 0x00000a50 0x00000a50 0x00000a50 0x00000a50 0x00000a50 0x00000a50
0x000802c4 0xffffffff 0xffffffff 0xffffffff 0xffffffff 0xffffffff 0xffffffff
0x000802c8 0x00000000 0x00000000 0x00000000 0x00000000 0x00000000 0x00000000
0x000802cc 0x00000214 0x00000214 0x00000214 0x00000214 0x00000214 0x00000214
sp 0x000802c0 0x000802b8 0x000802b0 0x000802a8 0x000802a0 0x000802a0

What is the address of the instruction that initiates the first call to linearConvergence? 0x

What address does the label negative correspond to? 0x

If alpha is 2 and beta is 17, what is the smallest possible value for the initial value of input? Express the answer in hex. 0x

Assume that linearConvergence is initially called with a depth of 0. Does the function converge in time?

If yes, then how many recursive calls are necessary (value of depth when the function completes)? If not, what is our value of MAXIMUM_DEPTH?

Back to Exercises