Warning: Outdated Content
This lab is from a previous version of CS 125. Click here to access the latest version.
Strings
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. Next we’ve set aside time for you to get started on MP1, which is due in under two weeks!
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 String class.
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 (20 Minutes)
Like last week, today’s lab prevents you from trying to jump right into the
code.
You must spend the next 20 minutes designing a algorithm with the rest of your
lab.
You’ll also want to spend some time reviewing the
String
documentation
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 20 minutes after your lab starts and ending 40 minutes 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 String methods
that you may have not used before.
Please review the
String
documentation.
As a 1 hint, you may find indexOf useful.
2. Getting Started on MP1 (Remaining Time)
We’ve set aside the remainder of lab for you to work on MP1. Please take advantage of this opportunity to work with the rest of your lab and the course staff! MP1 is harder to get started with, but the course staff will be able to help you if you get stuck. If you haven’t started, your goal should be to get to the point where you have submitted for the first time—and maybe even earned a few points! If you have started, your goal should be to make some progress. And if you’ve finished 2, then help out others around you.
3. Before You Leave
Don’t leave lab until:
-
You’ve designed your encryption algorithm and completed our third lab homework problem
-
You’ve made some progress on MP1…
-
And so has everyone else in your lab!
If you need more help completing the tasks above please come to office hours or post on the forum.