Exam Rules
The exam is due at 3:30PM Eastern on December 2. You can take as long as you need on the exam until the due date.
No collaboration is permitted.
The exam is open note, meaning that you can use any resources from the course website, any HW or recitation work you’ve already completed, and any notes that you have generated yourself. You can also refer to JavaDocs as you need. No other sources are permitted, including Google and StackOverflow.
Do not change any provided method signatures. The only cases you need to write your own method signatures is when writing test cases. Leave all provided signatures intact.
Finally, good luck! STUB FILES HERE
Part 1 (Code Review & Analysis)
Answer questions for this part on Gradescope.
Question 1
Your team has been presented with the following task:
Create a biometrics system for our new mobile device, the 591Phone. The device will need to be able to scan a full fingerprint and convert the image into a sequence of identifiers. Then, the device will also decide whether to accept or reject the identifier sequence by comparing it against the stored information for each of the permitted users. Finally, if the fingerprint is determined to belong to an allowed user, the device should unlock.
Your teammate comes up with the following interface for implementing a solution. Assume that all referenced classes are defined and that they are responsible for what their names suggest (e.g. a DatabaseConnection is a connection to a database of users).
public interface BiometricHandlerInterface {
// handles fingerprint reading and interpretation
public FingerprintImage scan();
public IdentifierSequence parseFingerprint(FingerprintImage fpi);
// queries and matches IdentifierSequences against the database of allowed
// users
public Map<User, IdentifierSequence> queryValidIdentifiers(DatabaseConnection users);
public boolean containsMatch(Map<User, IdentifierSequence> userSeqs, IdentifierSequence fingerprint);
public User findMatch(Map<User, IdentifierSequence> userSeqs, IdentifierSequence fingerprint);
// Handles device lock/unlock
public void unlockDevice();
public void rejectUnlockAttempt();
}
This interface is not especially well designed. Answer the following questions in one or two short sentences each. Remember that an interface is an abstract class, so any ideas we have about how classes should be written apply to interfaces as well.
-
Which principle of good design is being violated here (high cohesion, low coupling, or D.R.Y.) and in what way?
-
Briefly outline how you might solve this issue.
Question 2
After making changes to the program design, you and your partner get to work implementing the necessary methods to get this task done.
Your partner returns to you with this version of the scan() method completed:
public Fingerprint scan() {
FingerprintReader fpr = initializeReader();
Fingerprint data = new Fingerprint();
while (fpr.hasNextVertex()) {
Vertex v = fpr.nextVertex();
if (v.isCorrupted()) {
data.incrementCorruptedCount();
}
data.addVertex(v);
}
if (data.getCorruptedCount() <= THRESHOLD) {
return data;
}
fpr = initializeReader();
data = new Fingerprint();
while (fpr.hasNextVertex()) {
Vertex v = fpr.nextVertex();
if (v.isCorrupted()) {
data.incrementCorruptedCount();
}
data.addVertex(v);
}
if (data.getCorruptedCount() <= THRESHOLD) {
return data;
}
fpr = initializeReader();
data = new Fingerprint();
while (fpr.hasNextVertex()) {
Vertex v = fpr.nextVertex();
if (v.isCorrupted()) {
data.incrementCorruptedCount();
}
data.addVertex(v);
}
if (data.getCorruptedCount() <= THRESHOLD) {
return data;
} else {
System.out.println("Could not get a good reading after three tries");
return null;
}
}
Again, your partner has provided code that is not especially well written. Answer the following questions in one or two short sentences each.
-
Which principle of good design is being violated here (high cohesion, low coupling, or D.R.Y. code) and in what way?
-
Briefly outline how you might solve this issue.
Part 2 (Testing)
Your partner is really just not very concise when writing code. You don’t have time for another code review, but you do need to get some test cases written for their method isAnagram(). isAnagram() is a method that should return true when the two String inputs are the same length and they contain the same characters. Write a class ScratchTest.java with enough test cases to achieve full coverage over isAnagram().
import java.util.HashSet;
import java.util.Set;
public class Scratch {
public static boolean isAnagram(String one, String two) {
if (one == null && two == null) {
throw new IllegalArgumentException("Both inputs shouldn't be null");
} else if (one == null) {
return false;
} else if (two == null) {
return false;
}
if (one.equals(two)) {
return true;
}
if (one.length() > two.length()) {
return false;
} else if (two.length() > one.length()) {
return false;
}
Set<Character> oneSet = new HashSet<Character>();
for (int i = 0; i < one.length(); i++) {
oneSet.add(one.charAt(i));
}
for (int j = 0; j < two.length(); j++) {
char twoChar = two.charAt(j);
if (!oneSet.contains(twoChar)) {
return false;
}
}
Set<Character> twoSet = new HashSet<Character>();
for (int k = 0; k < two.length(); k++) {
twoSet.add(two.charAt(k));
}
for (int l = 0; l < two.length(); l++) {
char oneChar = one.charAt(l);
if (!twoSet.contains(oneChar)) {
return false;
}
}
return true;
}
}
Part 3 (Writing Code)
Many simple encryption strategies can be defeated by a basic task of “frequency analysis”. Frequency analysis is the process of determining how frequently certain character sequences appear in a particular document.
Your task is to read a dictionary file of words, each on their own line. Ultimately, you will return a mapping from two-character Strings to the relative frequency with which each two-character String appears in all of the words in the dictionary. There is a file of test cases provided to help you understand how each method should behave. You can assume you don’t have to worry about null-checking or malformed inputs.
Here is a high-level, complete walkthrough of the process of frequency analysis:
We provide the file dictionary.txt for you, which contains the two words "aaa" and "aab". Overall, then, the total set of two-character sequences that appears is "aa", "aa", "aa", "ab". So, "aa" appears three times total and "ab" appears once total. There are four total two-character sequences, so the frequency of "aa" is 3.0/4.0 = 0.75 and the frequency of "ab" is 1.0/4.0 = 0.25.
Do not change any of the provided function signatures.
twoCharSequences
Given a String, return a list of all consecutive two-character sequences in that String.
For example, twoCharSequences("aab") --> <"aa", "ab">
public static List<String> twoCharSequences(String word) {
return null;
}
incrementFromList
Given a Map from String to Double and a List of String, for each String in the List, increment the value that String maps to by 1. If that String is not yet present in the Map, set its value to 1.
public static void incrementFromList(List<String> sequences, Map<String, Double> counts) {
}
normalize
Compute the sum of all values in the Map counts. Divide each key’s value by the sum of all values, and replace each key’s value with this new, normalized value.
After running this function on counts, the sum of all values contained in counts should sum to 1.0.
public static void normalize(Map<String, Double> counts) {
}
calculateFrequencies
Use the three previous helper methods to calculate how often each two-character sequence appears in the given file.
public static Map<String, Double> calculateFrequencies(String filename) throws FileNotFoundException {
return null;
}
Submission
Submit your answers to Part 1 on the “Exam 2 Short Answer” assignment on Gradescope.
Submit ScratchTest.java and your completed FrequencyAnalysis.java to “Exam 2 Coding” on Gradescope. There is no advance autograding.