2.3 Lab 2

Encryption is a way to hide information, and is key to keeping information safe. We will be implementing a very well known encryption algorithm: substitution ciphers. Though there are much more complicated and secure encryption methods, substitution ciphers are a great way to practice using data structures.

Compression is very similar to encryption in that we take original data and use a key to convert the data; however, the goal of compression is not to obfuscate the data, but rather to decrease the the data’s size.

Objectives

This lab is intended to evaluate your ability to:

• use linear and associative structures to organize data
• iterate through structures to analyze data
• understand and implement substitution ciphers
• understand and implement run-length and Huffman encoding

Task

Submit your code and a write-up that addresses the following questions:

1. Briefly explain what a substitution cipher is, and more specifically, what a rotation cipher is.
2. How can we use frequency analysis to decrypt substitution ciphers?
3. Why might frequency analysis not work?
4. What is the decrypted message?
5. Compress the decrypted message using run-length and Huffman encodings. Which one produces fewer characters?

Materials can be found on Google Classroom.

Academic Honesty

You are allowed to work with others on this lab, as long as you do not share any code! Please refer to the syllabus for more details.

---

1. Write functions to rotate a list of Strings.
2. Write functions to bruteforce decrypt a rotation cipher.
3. Write functions to run-length encode the message.
4. Write functions to count the frequency of each letter in a body of text.
5. Write functions that use the frequencies to construct a Huffman encoding key. Use this key to encode the message.
6. Write functions to decode Huffman encodings.

---