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))
  • 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")))

    (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"))))
  • 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:

t1 bintree   t2 bintree
———————————————————————   c ∈ {red,blk}
    c(t1,t2) 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).

Figure 1: Example binary tree.
Figure 1: Example binary tree.
  1. 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).

  1. 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 log2(n + 1) − 2. Hint: Do this in three steps:

  • Prove that if t rbtree(c,b), then t has n ≥ 2b − 1 nodes.

  • Prove that if t rbtree(c,b), then t has height h ≤ 2b − 1 if c is red, and h ≤ 2b − 2 if c is black.

  • Conclude that h ≤ 2 log2(n + 1) − 2.

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