## Rolling Code

### May 16, 2014

In the early days of automatic garage door openers, all openers shared a single code, so that every garage door opener worked with every garage door; you could open your neighbor’s garage door and walk into his garage whenever you wanted to. The next generation of garage door openers had 8 DIP switches, and thus 256 codes, which solved the problem of casually preventing your neighbor from opening your garage but was hardly a deterrent to thieves.

Nowadays garage door openers and car lock keychain fobs use rolling codes, sometimes called hopping codes, for security. Each fob has a unique serial number; each garage door opener or car lock is programmed to recognize only signals from specific fobs. The signals themselves are randomized and encrypted by the rolling code.

It works like this: Each time a button on the fob is pressed, the requested signal is sent to the receiver along with the serial number of the fob and the rolling code, which is an encrypted random number. The receiver ensures the fob has a recognized serial number, decrypts the rolling code, compares it to the receiver’s synchronized random number generator, and performs the requested action if everything agrees or denies the requested action if it doesn’t.

It’s possible for the fob to send a signal when it is out of range of the receiver. To allow that, the receiver checks the next 256 numbers in the random sequence, instead of just one number, and accepts the signal if any of the 256 numbers agree. Additionally, in case the fob sends more than 256 consecutive signals out of range, the receiver performs the requested action and resynchronizes its copy of the random number sequence if the fob sends two successive numbers from the random sequence.

Your task is to write programs that simulate the actions of the fob and the receiver. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Three Interview Questions

### May 13, 2014

One of the sites that I watch from time to time is Career Cup, which publishes coding questions that have been asked in actual job interviews. These questions came through this morning:

1) Consider a sorted singly-linked list having the following nodes: 10 -> 30 -> 50 -> 70 -> NULL. You are given a pointer to node 50 and a new node having the value 40. Can you insert node 40 correctly in the list maintaining the ascending order?

2) Given a linked list 5 -> 4 -> 3 -> 2 -> 1 produce a linked list 4 -> 2 -> 0 -> 2 -> 1 by subtracting the last node of the list from the first, the next-to-last node from the second, and so on, stopping at the midpoint of the list.

3) Write a program to output the number of consecutive trailing zeros in the factorial of a number. For example, if the number is 5, then 5! = 120, and there is one trailing zero.

Your task is to write programs to answer the three interview questions posed above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Cluster

### May 9, 2014

Clustering is the process of collecting in groups all of the items from an input collection that share some common feature; for instance, the `GROUP BY`

operator of SQL performs clustering. We will define `cluster(proc, lt?, lst)`

as a function that takes an input list and returns a list of lists; `proc`

computes a signature of each item in the input list, and each sub-list in the output list contains all those elements of the input list with identical signatures, with sub-lists in increasing order of signature according to `lt?`

. The type of `cluster`

is (α → β) × (β × β → `boolean`

) × (`list`

α) → (`list`

(`list`

α)).

Your task is to write the function `cluster`

. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Packed Ascii

### May 6, 2014

Packed ascii is a method for compressing a useful subset of ascii characters in 6 bits, used in HART-enabled devices. The characters that may be transmitted are the space character, the 26 upper-case letters, the 10 digits, and the following punctuation characters: `! " # $ % & ' ( ) * + , - . / : ; ? @ [ \ ] ^ _`

. Omitted are the 26 lower-case letters, the rubout character, and the following punctuation characters: `` { | } ~`

.

Compression is achieved by keeping only the six low-order bits of each ascii character. Compressed characters are expanded to their original character by adding a high-order bit that is the complement of the compressed high-order bit. For instance, the string “PRAXIS” is compressed as the six 6-bit binary numbers 010000 010010 000001 011000 001001 010011.

A string of characters is compressed to 6-bit characters, then transmitted as 8-bit bytes by packing the bits from high-order to low-order, so that four characters are transmitted in three bytes, achieving a 25% compression. If the message length is not an even multiple of four, space characters are added to the end of the string as padding. Thus, the six 6-bit binary numbers representing “PRAXIS” would be padded with two space characters and transmitted as the six 8-bit binary numbers 01000001 00100000 01011000 00100101 00111000 00100000, which corresponds to the string “A X%8 “.

Your task is to write functions that compress and expand strings in packed ascii format. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Binary Reflected Gray Code

### May 2, 2014

An *n*-bit Gray sequence is a sequence of 2^{n} values, starting from 0, in which each differs from its predecessor by a single bit. There are always 2^{n−1} *n*-bit Gray sequences; for instance, the two 2-bit Gray sequences are 0, 1, 3, 2 and 0, 2, 3, 1. It is easier to see the Gray sequences when they are written in binary; the two 2-bit Gray sequences written in binary are 00, 01, 11, 10 and 0,0 10, 11, 01, where it is clear that each element of the sequence differs from the previous one by only one bit.

Although there are many possible Gray sequences for any given number of bits, there is one Gray sequence, known as the *binary reflected gray code* BRGC, that is almost always the Gray sequence that is being discussed. Such sequences are generated recursively from the next-smaller sequence by reversing the sequence, prefixing the entries of the original sequence with a 0-bit, prefixing the entries of the reversed sequence with a 1-bit, then concatenating the two sequences. For instance, given the 2-bit Gray sequence 00, 01, 11, 10, its reversal is 10, 11, 01, 00, adding a 0-bit to the original gives 000, 001, 011, 010, adding a 1-bit to the reversal gives 110, 111, 101, 100, and concatenating the two gives 000, 001, 011, 010, 110, 111, 101, 100, which is 0, 1, 3, 2, 6, 7, 5, 4.

Your task is to write a function that generates an *n*-bit binary reflected Gray sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Solovay-Strassen Primality Testing

### April 29, 2014

We have seen the Miller-Rabin and Baillie-Wagstaff primality tests in previous exercises. Today we look at a test developed by Robert M. Solovay and Volker Strassen in 1977. The test is no longer used, having been superseded by the other two tests, but was historically of great importance in the development of the RSA cryptosystem.

The test is based on *Euler’s Criterion*, which states that *a*^{(p−1)/2} ≡ (*a* / *p*) (mod *p*) for any odd prime number *p* and any integer *a* on the range 2 to *p* − 1 with gcd(*a*, *p*) = 1, where (*a* / *p*) is the Legendre symbol. If a number *n* being tested is prime, the test will indicate that *n* is prime; if a number *n* being tested is composite, the test will indicate that it is either prime or composite with equal likelihood, a coin flip. Thus, the Solovay-Strassen test chooses *k* different witnesses *a*; if any of them indicate *n* is composite, then it must be composite, but if none of them indicate *n* is composite, it is presumed prime with odds 2^{−k}.

If you are willing to assume the truth of the Extended Riemann Hypothesis, the Solovay-Strassen test can be made an absolute proof of primality by testing all prime *a* in the range 2 to min(*n *− 1, log^{2} *n*); if none of the *a* indicate the compositeness of *n*, then *n* is prime on the ERH.

The Solovay-Strassen test is no longer used, for three reasons: First, it takes more work to implement, as it involves computing the Jacobi symbol as well as modular exponentiation, whereas the Miller-Rabin test involves only modular exponentiation. Second, the Miller-Rabin test has a better error bound, *k*^{−4} compared to *k*^{−2}. Third, all Euler witnesses are also Miller-Rabin strong witnesses to the compositeness of *n*. The presence of the absolute proof of primality on the ERH is also not a bar to the use of the Miller-Rabin test, as there is a similar proof of primality based on Miller-Rabin strong witnesses.

Your task is to write two versions of the Solovay-Strassen primality test, one probabilistic and one on the ERH. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Assembler, Part 3

### April 23, 2014

We studied a simple assembler for a hypothetical computer in the two previous exercises. Today we finish our look at the assembler by writing a program that produces neat listings, like this one for our sample program:

# print sum of input numbers (terminated by zero) 000: 03010 ld zero # initialize sum to zero 001: 04011 st sum 002: 01000 loop get # read a number 003: 08007 jz done # no more input if number is zero 004: 05011 add sum # add input to accumulated sum 005: 04011 st sum # store new value back in sum 006: 09002 j loop # go back and read another number 007: 03011 done ld sum # print sum 008: 02000 put 009: 10000 halt 010: 00000 zero const 0 011: 00000 sum const

The listing shows the memory address in the first column, the contents of memory at the beginning of the program in the second column, the mnemonic label in the third column, the opcode in the fourth column, the object of the operation in the fifth column, and the comment in the sixth column.

Your task is to write a program that produces assembler listings. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Assembler, Part 2

### April 18, 2014

In the previous exercise we built an assembler for a hypothetical computer. Today we write a simulator for that hypothetical computer. The basic idea is simple: Start with a program counter at location 0, either perform the action at the location and advance the program counter to the next location, or set the program counter to the object of a jump instruction.

Your task is to write the simulator. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Assembler, Part 1

### April 15, 2014

In this exercise and the next one we will write a simple assembler for a hypothetical computer; we are following the assembler in the book *The Awk Programming Langauge* by Alfred V. Aho, Brian W. Kernighan and Peter J. Weinberger. Our computer has a memory of a thousand five-digit words, a single accumulator, and eleven opcodes:

OPCODE | INSTRUCTION | DESCRIPTION |
---|---|---|

`00` |
`const C` |
assembler pseudo-operator to define a constant `C` |

`01` |
`get` |
read a number from the input to the accumulator |

`02` |
`put` |
write the number in the accumulator to the output |

`03` |
`ld M` |
load accumulator with contents of memory location `M` |

`04` |
`st M` |
store contents of accumulator in memory location `M` |

`05` |
`add M` |
add contents of memory location `M` to the accumulator |

`06` |
`sub M` |
subtract contents of memory location `M` from the accumulator |

`07` |
`jpos M` |
jump to memory location `M` if the accumulator is positive |

`08` |
`jz M` |
jump to memory location `M` if the accumulator is zero |

`09` |
`j` |
jump to memory location `M` , unconditionally |

`10` |
`halt` |
stop program execution |

An assembly-language program is a series of blank lines and statements consisting of up to four fields: The first field, if it exists, is a label; it must start at the first position on the line and may not start with a digit. The second field, which is mandatory, is the opcode; it follows the optional label and mandatory spaces. The third field, which is used only with some opcodes, is the object; if it is present, it follows the opcode and mandatory spaces. The fourth field, which is optional, is a comment; everything on the line following a hash-sign is ignored. Here is a sample assembly-language program that prints the sum of a series of integers entered by the user, with the end of input marked by a 0:

# print sum of input numbers (terminated by zero) ld zero # initialize sum to zero st sum loop get # read a number jz done # no more input if number is zero add sum # add input to accumulated sum st sum # store new value back in sum j loop # go back and read another number done ld sum # print sum put halt zero const 0 sum const

The contents of memory after loading the sample program are shown on the next page.

Your task is to write a program that assembles a program written in our simple assembly language and loads the program into memory; we’ll write a simulator for our hypothetical computer in the next exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Plotter

### April 11, 2014

Programs that create graphs and charts are an important tool in many commercial and technical endeavors; for instance, a programmer might look at a graph of memory usage during a debugging run of his program to identify hot spots that need to be trimmed.

A simple type of graph is a scatter graph, sometimes called an x/y plot. The input is a list of points on an x,y-grid; the output is a picture with the points plotted on a grid. A simple input file appears on the next page.

Your task is to write a program to plot scatter graphs. When you are finished, you are welcome to read or run a suggested solution, or to post your own program or discuss the exercise in the comments below.