# CS2040S: Data Structures and Algorithms Problem Set 1 solved

\$35.00

Category:

## Description

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
Problem 1.a. Start IntelliJ and create a new Java project called ps1 for this problem. Choose
Java version 11.0.5 for Project SDK. If you do not have the SDK, download it here. 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 + “.”);
}
Problem 1.b. (Optional.) What is MysteryFunction calculating? If you try a few examples,
you might be able to guess.
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 complicated as you like. It should
output (in some form):
• your name (as you prefer to be called),
2
• 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.
This HelloWorld.java file is the only part of this problem to submit.
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. e.g. If the tap was 0, then we would XOR
with least significant bit).
4
Download code.zip. Inside, you should find the relevant files that you would require to complete
the following tasks. Open the folder using IntelliJ and configure Project SDK to be Java version
11.0.5.
Problem 2.a. Implement a linear feedback shift register called ShiftRegister that implements
the ILFShiftRegister interface:
public interface ILFShiftRegister {
public void setSeed(int[] seed);
public int shift();
public 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 the shift
operations return 1 and then 1 and then 0, then generate returns the value 6 (i.e., “110” in
binary).
5
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