Fix sub to mean $S,u,v\mapsto S,u-v$. If the depth-minimizing order evaluates the right operand $f$ before the left operand $e$, the stack ends in $S,f,e$, so ordinary sub would compute the wrong sign. Two possible instruction set architecture extensions are:

Both preserve the same peak operand stack bound:The first trades extra dynamic instructions for a smaller instruction set; the second trades a larger instruction set for fewer executed instructions. Neither extension makes order-sensitive side effects safe to reorder.

Let $d_e=\mathrm{depth}(e)$ and $d_f=\mathrm{depth}(f)$ measure the extra operand stack space required from the current base, with each evaluation leaving one result. Evaluating $e$ first uses $d_e$ slots. Its result occupies one slot while evaluating $f$, so that stage uses $1+d_f$ slots. The final add reduces two slots to one. ThusBy commutativity of addition, choose the smaller of these two bounds. Evaluate the child of larger depth first. The optimum recurrence on a binary expression tree isAssign depth one to a literal or a simple already-addressable value, and compute the child depths recursively. If $d_e>d_f$, the depths are integers, so $d_e\ge 1+d_f$; evaluating $e$ first therefore attains $d_e$, while reversing the order needs $d_e+1$. If the depths are equal, whichever child goes second needs the extra retained-result slot. These lower bounds prove the recurrence is optimal for evaluating each child subtree without interleaving or spilling. Apply it at every node to minimize peak operand stack occupancy for the given binary expression tree; this is optimal stack evaluation of a binary expression tree.

This changes child evaluation order, not the parenthesization. For example, a chain-shaped binary expression tree can have depth two, whereas a balanced tree of eight leaves has depth four under this model. The reordering assumes expressions have no order-sensitive side effects or observable exceptions. Reassociating floating-point addition would require additional care because it can change floating-point rounding.

A computed memory address is just another integer on the operand stack. For a pointer held at fixed address $p$, const p; load obtains the pointed-to address; another load obtains its contents. More generally, any expression that leaves an address on top may be followed by load, or may be retained beneath a computed value for store.

For an array whose base address is $b$ and whose element size is $w$ address units, the address of entry $i$ is $b+wM[p_i]$, where $p_i$ stores the index. Add zero-address instructions mul and dup, with dup mapping $S,p$ to $S,p,p$. A suitable sequence isThe first six instructions leave the element address $p=b+wM[p_i]$. The remaining suffix evolves aswith the final effectThe address is computed once and duplicated, so both accesses refer to the same array element. For unit-sized elements omit const w; mul. If the base address is itself held in a variable, replace const b by the instructions loading that variable's value. No instruction other than const requires an explicit operand.

Use two zero-address instructions for indirect access to computer memory. Define load to replace the top memory address by the value at that address, and define store to pop a value followed by the address just beneath it:Both have no encoded address operand; the stack supplies it. If the known fixed memory addresses of the variables are $p_x,p_y$, implement the assignment withThe successive stack suffixes are $p_x$, then $p_x,p_y$, then $p_x,M[p_y]$, then empty. HenceThe surrounding stack is restored. Other store conventions are possible, but the operand order must be stated and used consistently.

A zero-address instruction has no explicit operand addresses, so its operands and result location must be implicit in the instruction set architecture. A stack machine supplies these naturally: operations remove their inputs from the top of an operand stack and push the result. A fixed-processor register design is logically possible, so “almost certainly” is appropriately weaker than a proof that only a stack machine could work.

Write the stack from bottom to top, with its top on the right. Let $S$ stand for any unchanged prefix. Suitable effects areThus add pops two operands and pushes one sum, reducing stack occupancy by one. The special const c instruction pushes its immediate constant and increases occupancy by one. Only const needs an explicit value in its encoding.

For the unsigned interpretation of the binary string, the set positions have weights $2^{15},2^{13},2^{12},2^{11},2^{10},2^8,2^6,2^5,2^4$. ThusIn 16-bit two's complement, the most significant bit is set, so subtract $2^{16}$ from that unsigned interpretation:For a half-precision floating-point number, split the fields at their actual boundaries rather than the printed groups of four:The sign is negative, the true exponent is $15-15=0$, and the fraction is $2^{-2}+2^{-4}+2^{-5}+2^{-6}=23/64$. It is a normal finite value, so

The smallest positive normal half-precision floating-point number uses $E=1$ and a zero fraction, while the largest uses $E=30$ and all ten fraction bits equal to one. HenceThe corresponding words are 0 00001 0000000000 and 0 11110 1111111111. The stored exponent $31$ is reserved and cannot extend the finite normal range.

For a subnormal number, $E=0$ and the implicit leading bit becomes zero, while the scale remains $2^{1-15}=2^{-14}$. The least positive nonzero fraction is $0.0000000001_2=2^{-10}$, givingUsing scale $2^{-15}$ here would be incorrect: the subnormal number convention uses the minimum normal scale, not the ordinary biased-exponent formula at $E=0$.

Both signs are positive, so perform addition of the aligned significands. The true exponents are $-1$ and $3$, a difference of four. Shift the smaller significand right four places, retaining its low bits:Add at the common exponent:Renormalization raises the true exponent to $4$ and the biased exponent to $E=19=10011_2$. There are only seven fraction places to retain, so no floating-point rounding changes the result:The complete word is 0100110000001000.

For a normal half-precision floating-point number, write the stored fields as sign $s$, biased exponent $E$ and ten-bit fraction $f$. The value is $(-1{)}^s(1.f{)}_2{2}^{E-15}$ for $1\le E\le 30$. The leading one is implicit: the ten stored fraction bits give eleven significant binary digits including that one. The normalized binary representations and stored fields are

Thus the four 16-bit words areEvery conversion is exact: all four numbers have terminating binary representations within the available precision.

For an estimate, use the usual equal-device CMOS series-stack model: a $k$-input NAND gate or NOR gate has a worst-case propagation delay approximately $k$ times that of an inverter, because a conducting path contains $k$ series transistors. An AND gate or OR gate adds an output inverter. With a 1 ns inverter this gives, for $k\ge 2$,For $k=2$ it reproduces the stated 3 ns. This is a technology estimate under equal sizing and comparable loading, not a unique physical law inferable from a single measured delay. Actual propagation delay also depends on capacitance, fan-out and transistor sizing. If instead only the supplied two-input gates were allowed, a balanced tree would have worst-case depth $\lceil {\log }_{2}k\rceil$ and delay $3\lceil {\log }_{2}k\rceil$ ns; that is a different construction from a single $k$-input gate.

For the explicit circuit in part (a), the longest combinational logic path starts at $A$, passes through the shared inverter, either direction-match exclusive or, the AND gate, and the final exclusive or feeding $D_2$:The path $A\to D_1$ takes 5 ns, the paths from $B0$ or $B1$ to $D_2$ take at most 7 ns, and $B0\to D_0$ takes 1 ns. Both direction-match exclusive or gates act in parallel; their delays are not added together. The 8 ns excludes clock-to-Q delay, setup time, hold time and clock-distribution effects, because the question asks only for the combinational logic delay.

Use three positive-edge-triggered D flip-flops, all driven by the same clock signal $CLK$. Write the current binary representation as $B2B1B0$, with $B0$ the least significant bit. The next state is the current value plus one when $A=1$ and minus one when $A=0$, in each case modulo eight. A bit toggles under exclusive or with a one.

For upward counting, $B1$ toggles when $B0=1$, while $B2$ toggles when $B1=B0=1$, the respective carry conditions. For downward counting the corresponding borrow conditions are $B0=0$ and $B1=B0=0$. Define the shared inverted direction $N=\neg A$ and the two direction-match signalsEach $T_i$ is one exactly when $Bi=A$: it equals $Bi$ for upward counting and $\neg Bi$ for downward counting. Thus the Boolean functions for the three D inputs areImplement this with two NOT gates for $N,D_0$, four two-input exclusive or gates for $T_0,T_1,D_1,D_2$, and one two-input AND gate. Connect $D_i$ to the D flip-flop whose output is $Bi$; feed the three outputs back into the indicated gates. All three flip-flops capture simultaneously, so each equation uses the old state.

For completeness, the state transition table is

Every three-bit state is valid. A reset may initialize the binary counter to zero if required; counting itself needs no extra state. The direction input must meet the setup time and hold time requirements at the active clock edge.

The elementary row operations used above add multiples of other rows, so preserve the determinant. The determinant of an upper triangular matrix is the product of its diagonal entries. HenceEquivalently, $\det L=1$ and multiplicativity of the determinant gives $\det A=\det L\det U=6$.

Use Gaussian elimination without row exchanges. First apply $R_2\leftarrow R_2-3R_1$ and $R_3\leftarrow R_3-2R_1$; then apply $R_3\leftarrow R_3-R_2$:The elimination multipliers are $m_{21}=3$, $m_{31}=2$ and $m_{32}=1$. Put them below the diagonal of a unit lower triangular matrix:To see why these multipliers reconstruct the rows, row 2 of $LU$ is three times row 1 of $U$ plus row 2 of $U$, giving $(3,8,14)$. Row 3 of $LU$ is twice row 1 plus row 2 plus row 3 of $U$, giving $(2,6,13)$. This directly verifies the LU factorization.

Suppose an invertible matrix has two LU factorizations, $A=L_1{U}_1=L_2{U}_2$, with $L_1,L_2$ unit lower triangular matrices and $U_1,U_2$ upper triangular matrices. All four factors are invertible matrices, since their square products are invertible. Multiplication by the appropriate inverse matrices givesBy the supplied closure properties, the left side is a unit lower triangular matrix and the right side is an upper triangular matrix. A matrix of both types is diagonal; its diagonal entries are all one. Thus both sides are the identity matrix, whenceQualification of the printed wording: this establishes uniqueness if the specified LU factorization exists. Invertibility alone does not guarantee an unpivoted LU factorization. For example $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ is invertible, but in a product $\left(\begin{array}{cc}1& 0\\ \ell & 1\end{array}\right)\left(\begin{array}{cc}{u}_{11}& u_{12}\\ 0& u_{22}\end{array}\right)$, the zero top-left entry forces $u_{11}=0$, making the bottom-left entry $\ell u_{11}=0$ as well, contrary to the required value one. A permutation matrix is needed in general, as in PLU factorization.