Problem Set 2: Substitution

Evidence of a 5-point submission

• Uses a key validation method that requires only a single loop through the key; validate unique and alphabetic characters simultaneously using an array of size ALPHASIZE.
• Stores substitution keys as all same-case letters (for efficiency later - only needs to convert one substitution to uppercase or lowercase during encryption)
• Uses an efficient method to encrypt plaintext (minimal repeated code, printing out the encrypted text directly instead of using a variable, uses the isupper and islower functions)
• Does not use 26 as a magic number

Evidence of a 4-point submission

• Uses a method better than exhaustive search to validate unique characters (does not use two nested for loops that both iterate ALPHASIZE times; may use an array of size ALPHASIZE but in a way that does not short-circuit - see implementation example)
• Stores substitution keys as all same-case letters (for efficiency later - only needs to convert one substitution to uppercase or lowercase during encryption)
• Prints out encrypted text directly (does not store in a variable)

Evidence of a 3-point submission

• Uses an exhaustive iterative method to validate unique alphabetic characters that short circuits
• Uses a for loop to iterate through each character of the input and encrypt it

Evidence of a 2-point submission

• Uses a method worse than exhaustive (e.g., in O(n²)) to validate unique alphabetic characters (uses multiple nested loops to check the same characters more than once)
• Uses a non-constant time operation to find the index of the key to encrypt a given letter, when plaintext[i] - 'a' or plaintext[i] - 'A' will do.
• Loops over plaintext multiple times to encrypt

Evidence of a 1-point submission

• Uses a confusing method worse than exhaustive to validate unique alphabetic characters (checks for uniqueness in one nested loop, checks for alphabetic characters in a separate loop, doesn’t short-circuit)
• Uses a confusing and/or very unclear method for encryption

Example Implementations (Worse vs. Better)

Validate Key

Worse implementation

In the example below, though this method does use a key validation method check for duplicates, it does not short-circuit.

int letters[26];
for (int i = 0; i < 26; i++)
{
    letters[i] = 0;
}
for (int i = 0; i < 26; i++)
{
    int letter = tolower((int)(key[i]));
    letters[letter - 'a']++;
}
for (int i = 0; i < 26; i++)
{
    if (letters[i] != 1)
    {
        printf("invalid key\n");
        return 1;
    }
}

In the example below, the method uses an exhaustive check method, but the method will short-circuit.

for (int i = 0; i < 26; i++)
{
    for (int j = 0; j < 26; j++)
    {
        if (i != j && s[i] == s[j])
        {
            return 1;
        }
    }
}

Better Implementation

The example below can be validated using O(1)-check calls. Simultaneously checks for alphabetical AND unique characters.

char substitution[ALPHASIZE] = {0};
bool used[ALPHASIZE] = {false};
for (int i = 0; i < ALPHASIZE; i++)
{
    if (!isalpha(key[i]))
    {
        printf("Key must contain only alphabetic characters.\n");
        return 1;
    }
    char c = toupper(key[i]);
    if (used[c - 'A'])
    {
        printf("Key must not contain repeated characters.\n");
        return 1;
    }
    used[c - 'A'] = true;
    substitution[i] = c;
}