Strict Standards: Declaration of Doku_Renderer_metadata::table_open() should be compatible with Doku_Renderer::table_open($maxcols = NULL, $numrows = NULL, $pos = NULL) in /home2/cp-wiki/htdocs/inc/parser/metadata.php on line 480

Strict Standards: Declaration of Doku_Renderer_metadata::table_close() should be compatible with Doku_Renderer::table_close($pos = NULL) in /home2/cp-wiki/htdocs/inc/parser/metadata.php on line 480

CS 190C LAB 15: Friday, May 1, 2009

Final Exam Review

A sample final exam is posted on Blackboard for your reviewing pleasures.

Computability Review

  • Problem 1: Write a program to find the smallest positive integral solution to x^2 - 4729494y^2 = 1.
  • Problem 2: Given a list of numbers, divide it into two new lists that add up to the same sum.
  • Problem 3: Write a Python P program that takes an an input another Python program Q which has no input. P should decide if Q ever prints “done”.

In Lab Problem

Write a program that encrypts and decrypts simple lower-case strings using a substitution cipher, like a cryptoquote. Simply put, each letter is substituted with one other letter for encryption, and the process is reversed for decryption. Each letter must be replaced by a unique letter. Thus, A and B cannot both be replaced by C. An example key, or the mapping from the plaintext letters to the code letters, is given in cipher.txt. This is only one possible mapping; there are 26!-1 different mappings. Notice that each letter only appears once in both columns, which shows that each letter is transformed uniquely.

One popular mapping is known as rot13, where the alphabet is rotated halfway. Thus,

A B C D E F G ... 

maps to:

N O P Q R S T ...

If we wanted to encrypt “hello world”, we find the letter 13 positions after each letter (with wraparound, meaning o becomes b). Our result is then: “uryyb jbeyq”. To decrypt, we find the letter 13 positions *before* each letter. Note that a substitution cipher does not have to be a simple rotation like rot13 (the provided cipher is not such a case).

You are given the following function that will read the mapping from a file. However, it does not store the mapping; it is your choice how to store the data for easy and efficient lookup. There is more than one good choice, so COMMENT in why you chose to do it this way. This comment is required. You should take into account that you need to support both encrypt and decrypt operations.

def load_mapping(path):
    Load a mapping stored in a file at path.
    f = open(path)
    for line in f:
        u,v = line.strip().split()
  • You will need to write two utility functions:
    • encrypt(encrypt_mapping, message): This function should take the mapping data and a message. It should perform lookups on the mapping, and replace all of the plaintext letters with the ciphertext letter indicated in the mapping, and return the enciphered string.
    • decrypt(decrypt_mapping, code):This function should take the mapping data and an enciphered message. It should perform lookups on the mapping, and replace all of the ciphertext letters with the plaintext letter indicated in the mapping, and return the deciphered string.
  • To check your code, either write a small main function or manually test in this order:
    1. Reads the given mapping in from the above file.
    2. Processes the mapping into the data structure of your choice.
    3. Prompts the user for a message to encipher.
    4. Encipher the message using the given mapping, and print out the enciphered message.
    5. Decipher the message using the mapping, and and print out the result.

Submit your file along with a comment on why you picked the mapping structure you picked on Blackboard.

cs190c/lab15_09.txt · Last modified: 2009/05/01 11:32 by tang
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki