# Homework 1: Scheme and induction

- Due: 01/25 at 11:55pm
- Points: 15 (each question 5 points)

Please prepare your solution for problem 1 as a .scm file and your answers to problems 2-3 as a PDF file (scanned handwriting is okay, but no .doc or .docx, please). Submit both files in Sakai.

## 1. Caesar ciphers

This exercise is a refresher in Scheme, particularly in using higher-order functions and lexical scoping.

The Caesar cipher was used by Julius Caesar to encrypt his private letters (Suetonius *Vita Divi Iulii* 56.6). A Caesar cipher with a shift of *k* replaces the *i*’th letter of the alphabet with the (*i* + *k*)’th letter of the alphabet (mod 26). For example, a Caesar cipher with a shift of −3 would change ECCE to BZZB. In this problem, you’ll implement this cipher in Scheme.

Install Guile. On

`student0x.cse.nd.edu`

, it’s installed at`~dchiang/Public/guile/bin/guile`

. To enable editing and history, create a file called`~/.guile`

with the expressions`(use-modules (ice-9 readline)) (activate-readline)`

Write a function called

`caesar`

that takes no arguments. It should choose a random number*k*between 1 and 25 (inclusive) and return a pair (`cons`

) of functions, one which encodes strings with a shift of*k*and one which decodes strings with the same shift. Assume that strings use only uppercase letters. For example,`> (let ((encdec (caesar))) (let ((encode (car encdec)) (decode (cdr encdec))) (encode "ECCE"))) "YWWY"`

(but since the shift is random, you might get a different result). And encoding then decoding should yield the original string:

`> (let ((encdec (caesar))) (let ((encode (car encdec)) (decode (cdr encdec))) (decode (encode "ECCE")))) "ECCE"`

It should be possible to create multiple encoder/decoder pairs at the same time. (In other words, don’t store

*k*in a global variable.)Try to make your encoder and decoder run in

*O*(1) space. It’s not a requirement, but it’s good functional programming practice.The following Scheme functions should be handy:

`(random n)`

gives a random integer between 0 and*n*− 1 inclusive. (This function is part of Guile; other Schemes might be different.)`(modulo n m)`

is the same as Python’s`%`

operator. (It behaves differently from C/C++’s`%`

for negative numbers.)`string->list`

and`list->string`

convert strings to lists of characters and vice versa.`char->integer`

and`integer->char`

convert characters to integers and vice versa. Note that the letter`A`

converts to 65.

## 2. Red-black trees: definition

This exercise and the next are for practicing the style of inductive definitions and proofs used throughout the book.

Here’s a definition of binary trees with nodes that are colored either red or black:

`t`_{1} bintree t_{2} bintree
——————————————————————— c ∈ {red,blk}
c(t_{1},t_{2}) bintree
————————— c ∈ {red,blk}
c bintree

This definition represents trees as terms. For example, the tree in Figure 1 is represented as `blk(red(blk,blk),blk)`

.

- Modify the above definition into a definition of the judgement
`t rbtree`

that holds iff the colors satisfy the rules for red-black trees:

- The root is black.
- The leaves are black.
- If a node is red, then both its children are black.
For each node, there is a number

*b*(called its*black-height*) such that every path from the node to a leaf has exactly*b*black nodes.Hint: First define the judgement

`t rbtree(c,b)`

, which holds iff`t`

is a red-black tree with root color`c`

and black-height`b`

. (For this “helper” judgement, we suspend the requirement that the root is black.) Then define`t rbtree`

in terms of`t rbtree(c,b)`

.

- Write a derivation tree that shows that the tree shown in Figure 1 is a red-black tree.

## 3. Red-black trees: height bound

Define the *height* of a tree to be the maximum number of edges in a path from root to leaf. (Yes, it’s strange that black-height counts nodes but height counts edges.) You learned in Data Structures, but may not have proven, that the height of a red-black tree is *O*(log *n*), which makes them good for implementing dictionaries.

Prove, by induction(s) on the structure of derivations, that a red-black tree with *n* nodes has height at most 2 log_{2}(*n* + 1) − 2. Hint: Do this in three steps:

Prove that if

`t rbtree(c,b)`

, then`t`

has*n*≥ 2^{b}− 1 nodes.Prove that if

`t rbtree(c,b)`

, then`t`

has height*h*≤ 2*b*− 1 if*c*is red, and*h*≤ 2*b*− 2 if*c*is black.Conclude that

*h*≤ 2 log_{2}(*n*+ 1) − 2.

Note: This is the last time you will see a logarithm in this class!