Over the past couple of days I have been working on coding the Caesar cipher in C for CS50. While it seems pretty straightforward in theory, actually coding it was more complicated than I anticipated. The program takes any integer provided by the user as the key, and shifts the letters in the alphabet by that number to provide a coded message:
~/ $ ./caesar 45
It sounded relatively easy at first since letters hold a numerical value (see ASCII values), so it should be as simple as adding the key value to the ASCII value and there’s the code, right? Wrong. I won’t post the code here (academic integrity policy) but basically, it was necessary to first convert the letter to its alphabetical index (
b=1, etc.) and then shift by the key value, using the modulo
% operator to make sure to keep looping through the alphabet (
XYZABC rather than
XYZ[\]). The assignment gave us the formula for the Caesar cipher (
cipherLetter = (plainLetter + userKey) % 26) but without that alphabetic index conversion. Tricksy!
The last problem for this week’s assignments was to code the Vigenère cipher which is slightly more complex than the Caesar cipher. Instead of shifting each letter by the same numerical key, there is a keyword and you shift each letter by the corresponding rotating key value. So the for loop required two variables–one for the key and one for the plaintext. Thankfully this one didn’t take so long after understanding the basics from the Caesar cipher.
~/ $ ./vigenere candyfloss
In the next lecture we learned about different ways to sort data.
repeat until no swaps
for i from 0 to n-1
for i from 1 to n-1
All three of these methods run on the order of n-squared, so not very fast. This comparison animation shows how they each work.
on input of n elements
Merge sort runs on the order of n log n so is faster than the other methods above.
I took a quick glance at this week’s homework assignments and surprise! Will be sorting lots of numbers.