Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cs190c:lab15_09 [2009/05/01 11:32] (current)
tang created
Line 1: Line 1:
 +<​html><​script src="/​jsMath/​easy/​load.js"></​script></​html>​
 +
 +====== 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 {{cs190c:​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 [[http://​en.wikipedia.org/​wiki/​Rot13|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.
 +
 +<code python>​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()
 +
 +    return</​code>​
 +
 +  * 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:
 +     - Reads the given mapping in from the above file.
 +     - Processes the mapping into the data structure of your choice.
 +     - Prompts the user for a message to encipher.
 +     - Encipher the message using the given mapping, and print out the enciphered message.
 +     - 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