Today’s lab gives you even more practice designing computer algorithms: the sets of steps that a computer takes to solve a problem. You’ll design a string-processing algorithm with your lab and then implement it as a homework problem. If you have extra time, working on finishing up MP0, your first MP checkpoint, which is due this coming weekend.
1. String Algorithm Design and Implementation (60 Minutes Total)
Recently we’ve discussed both computer algorithms—the steps a computer uses to solve a problem—and strings—how computers store text.
Today’s lab bring’s both together, providing you with practice at algorithm
design and implementation using Java’s
To successfully complete today’s lab homework you’ll have to both design your
algorithm carefully and learn more about Java
Strings to implement it.
1.1. Design ROT13 Encryption (10 Minutes)
Like last week, today’s lab prevents you from trying to jump right into the
You must spend the next 10 minutes designing a algorithm with the rest of your
You’ll also want to spend some time reviewing the
to find useful methods to aid your implementation.
Only then can you begin to implement and test it.
Today our challenge is to implement a so-called Caesar cipher. This is a primitive form of encryption known as a substitution cipher, where each letter in a message or string is replaced with a single other letter. In a Caesar cipher each letter is replaced with a letter a fixed places down the alphabet. So, for example, "CS125" could become "DT236" with each letter replaced with the letter one place down the alphabet, or "EU347" with each letter replaced with the letter two places down the alphabet.
Note that a Caesar cipher is not a secure way to encrypt information. It may have worked in the days before computers, but now computers can trivially break any substitution cipher.
Note that to shift a letter down the alphabet we both have to decide what characters we are going to include and the order in which they appear in our alphabet. Our examples above assume the standard ordering of characters that we’ve all been taught in school and by the song: "ABCDEFGHIJKLMN…", etc. We also need to handle cases where a character shifts around from the end of the alphabet to the beginning.
1.2. Implement ROT13 Encryption (40 Minutes)
Next, you should 40 minutes on our in-lab homework problem, which you can find on PrairieLearn. Just like last week, you will only be able to access this homework beginning 10 minutes after your lab starts and ending a few hours later. If you are in the wrong lab you will not be able to complete the lab homework assignment—please attend the right lab next time.
Please feel free to work with a partner or in a small group on the lab homework. But every student must submit their own answers to receive credit.
Note that to finish this problem you will need to use several
that you may have not used before.
Please review the
As a 1 hint, you may find
2. Help with MP0 (Remaining Time)
We’ve set aside the remainder of lab for you to continue working on our first MP checkpoint: MP0. Please take advantage of this opportunity to work with the rest of your lab and the course staff!