Data Structures and Algorithms Problem Set 1

CS2040S: Data Structures and Algorithms
Problem Set 1

Overview. You have two basic tasks this week.
• Your first job this week is to set up your environment for writing programs in CS2040S. By
the end of this problem set, you should be able to write simple Java programs.
• Your second job is to implement a linear feedback shift register. This is a simple data structure
that can be used as part of a simple encryption schemes, or as a part of a pseudorandom
number generator.
For each problem, upload the Java files to Coursemology as individual files, and write any
textual answers in the text box.
Collaboration Policy. You are encouraged to work with other students on solving these problems. However, you must write up your solution by yourself. We may, randomly, ask you
questions about your solution, and if you cannot answer them, we will assume you have cheated. In
addition, when you write up your solution, you must list the names of every collaborator, that is,
every other person you talked to about the problem (even if you only discussed it briefly). You can
do so in Coursemology by adding a comment. Any deviation from this policy will be considered
cheating and will be punished severely, including referral to the NUS Board of Discipline.
1
Problem 1. (Getting up and running)
In CS2040S, we will be writing programs in Java. We will be using IntelliJ as our basic development
environment. IntelliJ is available as an open-source (Apache 2.0) Community version that has all
the functionality needed for CS2040S, and runs on Windows, Macs, and Linux. It contains useful
editing, debugging, and profiling tools. You can download it at:
https://www.jetbrains.com/idea/download/
Problem 1.a. Start IntelliJ and create a new Java project called ps1 for this problem. Choose
Java version 11.0.13 for Project SDK. If you do not have the SDK, download it here. You will need
to create an Oracle account in order to download it. Inside the src folder, create a new Java class
called Main.java (the name is case sensitive!). Within this class, create the following method:
static int MysteryFunction(int argA, int argB) {
int c = 1;
int d = argA;
int e = argB;
while (e > 0) {
if (2 * (e / 2) != e) {
c = c * d;
}
d = d * d;
e = e / 2;
}
return c;
}
Also, create the following main function:
public static void main(String args[]) {
int output = MysteryFunction(5, 5);
System.out.printf("The answer is: " + output + ".");
}
Run your program. What is the answer output in your solution?
Problem 1.b. What is MysteryFunction calculating? If you try a few examples, you might be
able to guess the answer.
Problem 1.c. Create a “Hello CS2040S!” program that is designed to introduce yourself to your
tutor and name it HelloWorld.java. It can be as simple or as complicated as you like. It should
output (in some form):
2
• your name (as you prefer to be called),
• your favourite algorithm or your favourite joke,
• a few sentences of additional information on your background and who you are (but nothing
private that you would want kept secret from the rest of the class),
• the answer(s) to the previous parts, i.e. Problems 1.a and 1.b.
This HelloWorld.java file is the only file that you should submit for Problem 1.
3
Problem 2. Linear Feedback Shift Register
A shift register is an array of bits that supports a shift operation which moves every bit one
slot to the left. For example, below is an example of a shift register initially containing the seed
“10101111”. It is shifted twice. Each time it is shifted, the most significant bit is dropped, every
other bit is moved one place to the left, and the least significant bit is replaced with a ‘0’. Notice
that after it is shifted 8 times, the shift register will be all zeros.
Note: In the usual convention, the most significant bit is written as the leftmost bit.
A linear feedback shift register is a special type of shift register that, instead of setting the least
significant bit to zero, updates the least significant bit with some linear function of the other bits.
That is, when a shift operation occurs, it feeds back some information into the least significant bit.
We will build a linear feedback shift register based on the exclusive-or (XOR) function. (In Java,
(a^b) calculates the XOR of a and b.)
Our linear feedback shift register takes two parameters: a size and a tap. The size refers to the
number of bits. The tap refers to one of the bits and must be between 0 and size−1 (inclusive).
size specifies number of bits the register should be dealing with and tap specifies which bit (starting
from the least significant bit) is going to used in the XOR operation.
Every time a shift operation occurs, the following four things happen: (1) The feedback bit is
calculated as the XOR of the most significant bit and the tap bit. (2) The most significant bit
is dropped. (3) Every bit is moved one slot to the left. (4) The least significant bit is set to the
feedback bit.
Here are two examples of a linear feedback shift register in action. In both cases, the size is 8
and the tap is 4 (which is the 5th least significant bit, i.e., if the tap was 0, then we would XOR
with least significant bit).
4
Download ps1.zip. Inside, you should find the relevant files that you would require to complete
the following tasks. Open the code folder using IntelliJ (the folder containing mystery.bmp) and
configure Project SDK to be Java version 11.0.13.
Problem 2.a. Implement a linear feedback shift register called ShiftRegister that implements
the ILFShiftRegister interface:
public interface ILFShiftRegister {
void setSeed(int[] seed);
int shift();
int generate(int k);
}
The interface requires that the following methods be supported:
• void setSeed(int[] seed): Sets the shift register to the specified initial seed. The initial
seed is specified as an array of 0’s and 1’s (represented as integers). If the seed contains any
other value, that is an error. (Recall that the seed is the initial set of bits stored in the shift
register.)
IMPORTANT NOTE: The given input array seed will be such that the least significant
bit is on index 0 of the integer array. For example, if the actual seed is 00101, then it will be
given as {1, 0, 1, 0, 0} in the program.
• int shift(): Executes one shift step and returns the least significant bit of the resulting
register.
• int generate(int k): Extracts k bits from the shift register. It executes the shift operation k times, saving the k bits returned. It then converts these k bits from binary into an
integer. For example: if generate is called with a value of 3, then it calls shift 3 times. If
5
the shift operations return 1 and then 1 and then 0, then generate returns the value 6 (i.e.,
“110” in binary).
Your implementation should also support the following constructor:
• ShiftRegister(int size, int tap)
This constructor initializes the shift register with its size and with the appropriate tap. Submit
your implementation.
Problem 2.b. Test your code with a variety of test cases. Make sure to test the corner cases
(e.g., when the shift-register has size 1, etc.). Here are two sample test cases to use. The first tests
the shift functionality, while the second tests the generate functionality.
Test 1: seed = ‘101111010’, tap = 7
int[] array = new int[] {0, 1, 0, 1, 1, 1, 1, 0, 1};
ShiftRegister shifter = new ShiftRegister(9, 7);
shifter.setSeed(array);
for (int i = 0; i < 10; i++) {
int j = shifter.shift();
System.out.print(j);
}
This code should produce the following output:
1100011110
Test 2: seed = ‘101111010’, tap = 7
int[] array = new int[] {0, 1, 0, 1, 1, 1, 1, 0, 1};
ShiftRegister shifter = new ShiftRegister(9, 7);
shifter.setSeed(array);
for (int i = 0; i < 10; i++) {
int j = shifter.generate(3);
System.out.println(j);
}
6
This code should produce the following output:
6
1
7
2
2
1
6
6
2
3
Now test your code using the provided JUnit tests (these are a subset of the tests that the tutors
will use when evaluating your code). Load the file ShiftRegisterTest.java in IntelliJ. Then run
the tests by clicking the button beside line number 10 or using keyboard shortcuts (Ctrl+Shift+R
for Mac and Ctrl+Shift+F10 for Windows). Other useful keyboard shortcuts can be found in this
reference sheet.
Look at the last test: it is testing what happens when the seed is larger than the specified
register. Explain what you think a proper response is to this erroneous situation, and what is the
right way to test this case? (We will cover error handling later in the semester.) Submit your
answer as in a comment in ShiftRegisterTest.java.
Write some additional JUnit test cases for your code in ShiftRegisterTest.java (you may
reference the existing test cases in the test class). We expect you to sufficiently test your code.
You will be expected to test for the two previously mentioned scenarios, along with some other
scenario, and at least one more corner case.
Problem 2.c. Think about how you might use a shift register to perform a simple encryption
scheme. (Hint: initially, the seed of the shift register should be set to your “password.”) How
would you encrypt a text file? How would you encrypt an image?
The two released classes ImageEncode.java and SimpleImage.java implement a simple encryption/decryption scheme using a shift register. You will need to add a couple lines of code
to ImageEncode.java so that it properly uses your shift register. To decode the picture, use the
following “code”:
• Tap: 7
• Seed: 0111011001011
If your shift register works correctly, you should then be able to decode the included mystery
picture. Who is it a picture of? (The only thing you are required to submit for this part is an
identification of the decoded picture.)
Problem 2.d. (Extra, for those who are interested) Think of the output of a linear feedback
7
shift register as the sequence of 0’s and 1’s that you get if you call getBit() after each shift. A
linear feedback shift register is only useful for encryption if the resulting output sequence does not
repeat very often. Experiment with how many times a shift register has to be shifted in order to
cause the output pattern to repeat. Are all taps equally good?
Also, notice that a short binary password will not provide very good security. Optionally write
a modified version that takes a text string (such as, “TheCowJumpedOverTheMoon”) and converts
it to a (long) binary string to use as a seed for a shift register.
Another use of linear feedback shift registers is to generate pseudorandom numbers. One basic
property of a pseudorandom number generator is that it outputs roughly the same number of 0’s
as 1’s. Is that true of your linear feedback shift register?
This is an open ended question, feel free to submit anything that you think is appropriate with
the relevant explanations.
Hints for question 2:
Do I need to comment my code? Yes. Be sure to write a comment explaining: the purpose of each
class instance variable, and the purpose/workings of each method. You should also explain any
critical steps in your code.
What data structure should I use to store the current value of the shift register? One of the advantages of encapsulation is that you can store the value of the register in any way that you want. For
simplicity, we recommend that you use an array of integers (as is passed to setSeed). However, if
you want to optimize the running time of the shift operation, there are more efficient solutions.
Implement the best solution you can!
For generate, how do I convert the bits produced by shift into an integer? Begin with a variable
v set to zero. Every time you get a new bit from shift, multiply v by two, and add the new bit
(either 0 or 1). The final result will be the integer representation of the bits.
How do I create a variable to store the array of integers in the register when I don’t know its size?
Declare it simply as an array of integers: int[] intArray. Then, initialize it in the constructor
once you have learned the correct size.
For Test 2, my first call to generate produces the value 3 instead of the value 6. You are interpreting
the bits in the wrong order. Notice that the binary string ‘110’ is 6, while the binary string ‘011’ is 3.
I get an ArrayOutOfBounds error (or a NullPointerException). Did you remember to initialize
all your class instance variables?
When I try to run ShiftRegisterTest, it does not execute properly. Perhaps it asks if you want
to run an Ant build? Perhaps it asks something else strange. Make sure that you have the JUnit
package properly installed by adding a new JUnit test to your project. (You can do this under
File→New→JUnit test.) This ensures that IntelliJ is properly set up to run tests. Alternatively,
you can check that the libraries are there. Go to Project→Properties, then look in the section Java
8
Build Path→Libraries. You should see two entries: JRE and JUnit. If JUnit is not there, click add
library and choose JUnit.
I am getting an error that says that each interface/class must be defined in its own file. Yes. In
Java, each interface or class has to be in its own file, and the name of the file should match the
name of the class (with the addition of the .java extension).
Where should I put the mystery file? Put it in the folder that contains the src folder, i.e., the
project’s root folder.
I placed the mystery file in the src folder but the output is a blank window. What do I do? In the
main function of Main.java, use the full path to the mystery file instead, i.e. /path/to/mystery.bmp
instead of mystery.bmp.
How should I debug my program, when I cannot see the internal state of my object? Wouldn’t it
be nice if you could just type System.out.println(shifter) and have it print out the value of
the shift register? In fact, you can if you implement:
public String toString()
This method should convert the value of the register into a string and return it. Then, you can
modify your test code to include:
System.out.println(shifter + " " + j);
and you will get the following output for the first test:
011110101 1
111101011 1
111010110 0
110101100 0
101011000 0
010110001 1
101100011 1
011000111 1
110001111 1
100011110 0
9