Exam & Solution - A Concise and Practical Introduction to Programming Algorithms in Java - page 237

true

false

t=3 t=4 t=6 t=7

- Write a recursive function
static Transition shift (Transition t , int delta) that shall return a new
list of transition states, identical to t but with values shifted by delta .
You shall not modify the original list t .

Then give a function static Signal shift (Signal s , int delta) .

- A Signal object that does not have a strictly increasing sequence of
transition states is not correct. In order to detect program errors, it
is useful to have a function static boolean isWellFormed(Signal s) that
returns true if and only if s is correct.

Write a recursive function using an auxiliary function. Time com-
plexity shall be linear to the list length of transition events stored in
s .

- The commutable exclusive or operation ( XOR for short) that takes
two operands is defined by the following logic table:

XOR false true

false false true

true true false

That is, b 1 XOR b 2 is true if and only if b 1 = ¬ b 2 . In Java, it can be

written as b1 != b2 .

We now want to compute the output signal of the XOR of two input
signals. We notice that at a given time step, if only one signal changes
then the result changes, and if both signals change at a same time,
then the result does not change.

Write a function static Transition xorTransitions(Transition t1,
Transition t2) that returns a new transition state list that corresponds
to the output. This function shall not modify the source list t1 and t2 ,
but in some cases, it is possible to share a sub-list. The time complexity
shall be linear to the length of both lists.