University of Sheffield Department of Computer Science
COM2001: Advanced Programming Techniques Semester 1 Assessment 2016-17
Semester 1 of COM2001 will be assessed by 3 Haskell programming assignments. All the assignments are about codes and code breaking. Assignment 1 is about substitution ciphers, assignment 2 simulates the wartime Enigma cipher machine and assignment 3 reconstructs the method by which Enigma was broken at ‘Station X’ – Bletchley Park. If you get interested in the history, here are some links:
http://www.codesandciphers.org.uk/enigma/index.htm http://www.codesandciphers.org.uk/virtualbp/tbombe/thebmb.htm http://www.ellsbury.com/enigmabombe.htm
Assignment 1: Substitution Ciphers
This assignment counts as 12.5% of the assessment for COM2001
In cipher systems the aim is to encode a message (a String of Chars) in such a way that it will be meaningless to anyone who does not have the key which specifies how the transformation from the original plain text was done.
In a substitution cipher, each character is replaced by another, using a fixed mapping, e.g.
Plain ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher EKMFLGDQVZNTOWYHXUSPAIBRCJ
So that the message “SPANGLES” would be transmitted as “SHEWDTLS”. The key is the mapping.
All our messages will contain upper case letters only. Punctuation is done by words – “STOP”, “COMMA”
etc. Numbers are spelt out.
1. Define a Haskell data structure Cipher to represent a substitution cipher
2. Define and test a Haskell function validateCipher to validate a cipher – which must contain each letter
once and once only.
A common variation is to add an offset of n Chars : the cipher moves n places to the right and wraps around, so if n=2 we have
Plain ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher CJEKMFLGDQVZNTOWYHXUSPAIBR
3. Define and test a Haskell Function encode which is given a Char, a Cipher and an offset and returns the encoded Char.
4. Define and test a Haskell function encodeMessage which is given a String representing a message, a Cipher and an offset and uses encode to encode the complete message.
Substitution ciphers can be used in reverse: returning to our original
Plain ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher EKMFLGDQVZNTOWYHXUSPAIBRCJ
Reverse encoding is given the cipher and returns the plain – this is how you’d decode the message if you had the key. So “SHEWDTLS” would be reverse encoded to “SPANGLES”
5. Write and test reverseEncode and reverseEncodeMessage corresponding to encode and encodeMessage above.
Breaking Substitution Ciphers
A substitution cipher can be broken using knowledge of letter frequencies. In English the most common letter is E so the most frequently occurring letter in the coded message is most likely (though not certain) to decode to E. The next most frequent is T, then A and so on – the full list is given in the help file on MOLE – see below.
6. Write and test a function letterStats, which is given a message String and returns the percentage of each letter occurring in this String, e.g. letterStats “STDDWSD” should return
[(‘D’,43),(‘S’,29),(‘W’,14),(‘T’,14)]
It will be useful if letters with zero scores are removed and the remainder are returned in decreasing order of frequency in the message. You can use my mergeSort from the lecture notes, which is in the help file
Results from letterStats can be used to make guesses for letter encodings, which can then be substituted back into the coded message.
7. Write and test partialDecode, which is given a list of guesses for letters in the message and returns the message with these guesses filled in, in lower case. E.g. if the message is “DXPWXW” and the guesses are
that E ciphers to X and S ciphers to W then partialDecode should return “DePses”. The guesses are supplied by hand.
8. To test partialDecode, decipher the message mystery given in the help file The Help File
The file AssignmentHelp.hs on the COM2001 MOLE site contains some functions might find useful (for instance to find the alphabetic position of a letter and to convert upper to lower case) and data you will need (for instance the mystery message). You can import it into your code by copying it to the same directory as your own module and then starting like so
Module Ciphers where
import AssignmentHelp
What you must do
The 8 tasks above
Marking Scheme
Task
Credit(%)
Cipher
10
validateCipher
20
encode
10
encodeMessage
10
reverseEncode and reverseEncodeMessage
10
letterStats
25
partialDecode
15
About 60% of the credit for each function is for the code, 20% for documentation and 20% for testing.
How to Hand In
Hand in via MOLE.
What to Hand In
Your commented code, as a .hs file ready to run. Give your name in an initial comment.
Test results for the functions you’ve written (cut and paste from the console window)
Deadline
Midnight on Monday 24th October (Monday of week 5)