Question

In: Computer Science

1. Theory. The most obvious way to represent a sequence of objects is simply to list...

1. Theory.

The most obvious way to represent a sequence of objects is simply to list them, one after the other, like this.

a  

a  

b  

b  

b  

c  

a  

a  

d  

d  

d  

d  

Note that the same objects often appear many times in a row. This is called a run of those objects. In the example sequence, there is a run of 2 a’s, a run of 3 b’s, a run of 1 c, a run of 2 a’s, and a run of 4 d’s. You can represent a sequence with runs by listing its objects, along with the number of times each object appears. For example, you can represent the sequence shown above like this.

a  

b  

c  

a  

d  

2

3

1

2

4

Representing a sequence in this way is called run-length encoding. If a sequence has long runs, or many runs, then run-length encoding will represent it more efficiently than simply listing its objects. However, if a sequence has short runs, or few runs, then run-length encoding may represent it less efficiently, because extra space is needed to store the lengths of the runs.
      Since a stack is just a simple kind of sequence, you can use run-length encoding to implement it. In this assignment, you will write a Java class called RunnyStack that implements a stack which uses run-length encoding. Here are some examples of how it works. Suppose you push an object a on an empty RunnyStack. Then the stack will look like this, with a run of 1 a.

a 1

Now suppose you push b. The stack now looks like this, with a run of 1 b, and a run of 1 a.

b 1

a 1

If you push another b on the RunnyStack, then the length of the run on top of the stack is incremented, so the stack looks like this.

b 2

a 1

If you push yet another b, then the length of the run at the top of the stack would increase to 3. However, suppose that you pop the RunnyStack instead. Then the length of the run at the top is decremented, so that the stack looks like this.

b 1

a 1

If you pop the RunnyStack one more time, then the length of the run on top of the stack is decremented to 0. However, a run of 0 objects is like no run at all, so it vanishes, and the stack looks as it did after the first push.

a 1

Stacks with run-length encoding are used internally by some compilers and interpreters, because they often push the same objects over and over again.

2. Implementation.

You must write a class called RunnyStack that represents a stack. Your class must implement run-length encoding, as described previously. It must also hold objects of type Base, so it will look like this.

class RunnyStack<Base>
{
  ⋮
}

Your class must define at least the following methods, as described below. To simplify grading, your methods must have the same names as the ones shown here.

  • public RunnyStack()

    Constructor. Make a new, empty instance of RunnyStack.

  • public int depth()

    Return the depth of the stack: the sum of the lengths of all the runs it holds. This is not necessarily the same as the number of runs it holds, which is returned by the method runs.

  • public boolean isEmpty()

    Test if the stack is empty.

  • public Base peek()

    If the stack is empty, then throw an IllegalStateException. Otherwise, return the Base at the top of the stack.

  • public void pop()

    If the stack is empty, then throw an IllegalStateException. Otherwise, decrement the length of the run on top of the stack. If this leaves a run of zero Base’s on top of the stack, then remove that run.

  • public void push(Base base)

    If the stack is empty, then add a new run of one Base at the top of the stack. If the stack is not empty, then test if base is equal to the object in the run at the top of the stack. If it is, then increment the length of that run. If it isn’t, then add a new run of one base at the top of the stack. Note that base may be null.

  • public int runs()

    Return the number of runs in the stack. This is not necessarily the same as its depth, which is returned by the method depth.

Here are some hints, requirements, and warnings. First, all these methods must work using O(1) operations, so they are not allowed to use loops or recursions. You will receive no points for this assignment if you use loops or recursions in any way!
      Second, your RunnyStack class must have a private nested class called Run. You must use instances of Run to implement your stack. Each instance of Run represents a run of Base’s. You will receive no points for this assignment if you use arrays in any way! The class Run must have three private slots that have the following names and types. The slot base points to the Base that appears in the run. The slot length is an int that is the length of the run. The slot next points to the instance of Run that is immediately below this one on the stack, or to null. It must also have a private constructor that initializes these slots.
      Third, your push method must test non-null Base’s for equality using their equals methods. It must use the Java ‘==’ operator only for testing null Base’s. It is helpful to define an extra private method called isEqual that takes two Base’s as arguments, and tests if they are equal. If either Base is null, then isEqual uses ‘==’. If neither Base is null, then isEqual uses equals.
      Fourth, RunnyStack’s methods are not allowed to print things. If you were writing RunnyStack in the Real World, then it might be part of some larger program. You don’t know if that larger program should print things.

Solutions

Expert Solution

1. Theory.

The most obvious way to represent a sequence of objects is simply to list them, one after the other, like this.

a

a

b

b

b

c

a

a

d

d

d

d

Note that the same objects often appear many times in a row. This is called a run of those objects. In the example sequence, there is a run of 2 a’s, a run of 3 b’s, a run of 1 c, a run of 2 a’s, and a run of 4 d’s. You can represent a sequence with runs by listing its objects, along with the number of times each object appears. For example, you can represent the sequence shown above like this.

a

b

c

a

d

2

3

1

2

4

Representing a sequence in this way is called run-length encoding. If a sequence has long runs, or many runs, then run-length encoding will represent it more efficiently than simply listing its objects. However, if a sequence has short runs, or few runs, then run-length encoding may represent it less efficiently, because extra space is needed for the lengths of the runs.
Since a stack is just a simple kind of sequence, you can use run-length encoding to implement it. In this assignment, you will write a Java class called RunnyStack that implements a stack which uses run-length encoding. For example, suppose you push an object a on an empty RunnyStack. Then the stack will look like this, with a run of 1 a.

a 1

Now suppose you push b. The stack now looks like this, with a run of 1 b, and a run of 1 a.

b 1

a 1

If you push another b on the RunnyStack, then the length of the run on top of the stack is incremented, so the stack looks like this.

b 2

a 1

If you push yet another b, then the length of the run at the top of the stack would increase to 3. However, suppose that you pop the RunnyStack instead. Then the length of the run at the top is decremented, so that the stack looks like this.

b 1

a 1

If you pop the RunnyStack one more time, then the length of the run on top of the stack is decremented to 0. However, a run of 0 objects is like no run at all, so it vanishes, and the stack looks as it did after the first push.

a 1

Stacks with run-length encoding are used internally by some compilers and interpreters, because they often push the same objects over and over again.

2. Implementation.

You must write a class called RunnyStack that represents a stack of objects. Your class must implement run-length encoding, as described previously. It must also hold objects of type Base, so it will look like this.

class RunnyStack<Base>
{

}

Your class must define at least the following methods, as described below. To simplify grading, your methods must have the same names as the ones shown here.

public RunnyStack()

(5 points.) Constructor. Make a new, empty instance of RunnyStack.

public int depth()

(5 points.) Return the depth of the stack: the sum of the lengths of all the runs it holds. This is not necessarily the same as the number of runs it holds, which is returned by the method runs.

public boolean isEmpty()

(5 points.) Test if the stack holds no objects.

public Base peek()

(5 points.) If the stack is empty, then throw an IllegalStateException. Otherwise, return the object at the top of the stack.

public void pop()

(5 points.) If the stack is empty, then throw an IllegalStateException. Otherwise, decrement the length of the run on top of the stack. If this leaves a run of zero objects on top of the stack, then remove that run.

public void push(Base object)

(10 points.) If the stack is empty, then add a new run of one object at the top of the stack. If the stack is not empty, then test if object is equal to the object in the run at the top of the stack. If it is, then increment the length of that run. If it isn’t, then add a new run of one object at the top of the stack. Note that object may be null.

public int runs()

(5 points.) Return the number of runs in the stack. This is not necessarily the same as its depth, which is returned by the method depth.

Here are some hints, requirements, and warnings. First, all these methods must work using O(1) operations, so they are not allowed to use loops or recursions. That means you may need to introduce extra private variables.
Second, your RunnyStack class must have a private nested class called Run. It must have three private slots that have the following names and types. The slot object points to the Base object that appears in the run. The slot length is an int that is the length of the run. The slot next points to the Run that is immediately below this one on the stack, or to null. It must also have a private constructor that initializes these slots. Each instance of Run represents a run of objects. You must use instances of Run to implement your stack. You will receive no points for this assignment if you use arrays in any way!
Third, your push method must test non-null objects for equality using their equals methods. It must use the Java ‘==’ operator only for testing null objects. It is helpful to define an extra private method called isEqual that takes two objects as arguments, and tests if they are equal. If either object is null, then isEqual uses ‘==’. If neither object is null, then isEqual uses equals.
Fourth, RunnyStack’s methods are not allowed to print things. If you were writing RunnyStack in the Real World, then it might be part of some larger program. You don’t know whether the larger program should print things (maybe it’s operating a toaster).
In addition to RunnyStack, you should also write a driver class that tests if RunnyStack’s methods work correctly. You will receive no points for the driver class. However, if you don’t write it, then you probably will not be able to find mistakes in your methods. Here is an example driver class; the comments show what it should print.

class RunnyDriver
{
public static void main(String[] args)
{
RunnyStack<String> s = new RunnyStack<String>();
  
s.push("A");
System.out.println(s.peek() + " " + s.depth() + " " + s.runs()); // A 1 1
  
s.push("B");
System.out.println(s.peek() + " " + s.depth() + " " + s.runs()); // B 2 2
  
s.push("B");
System.out.println(s.peek() + " " + s.depth() + " " + s.runs()); // B 3 2
  
s.pop();
System.out.println(s.peek() + " " + s.depth() + " " + s.runs()); // B 2 2
  
s.pop();
System.out.println(s.peek() + " " + s.depth() + " " + s.runs()); // A 1 1
}
}

This driver class does not necessarily implement a complete set of tests for RunnyStack’s methods. You should also do tests of your own.

3. Deliverables.

This assignment is worth 40 points. You must turn in all of the following.

The Java source code for the class RunnyStack.

The Java source code for your driver class.

Any output produced by your driver class.


Related Solutions

Javascript Questions: 1. Which of the following is not a way to avoid adding objects to...
Javascript Questions: 1. Which of the following is not a way to avoid adding objects to the global namespace? a. Create and assign variables and event handlers within an IIFE. b. Use the var keyword. c. Use an object literal as a namespace. d. Create and attach an event handler function within the event    onload handler. 2. Data properties added by assignment are writable, configurable, and enumerable by default. Data properties added with the defineProperty method are a. writable,...
Number the events below 1 – 7 to represent the correct sequence of events in skeletal...
Number the events below 1 – 7 to represent the correct sequence of events in skeletal muscle contraction and relaxation ___Ca2+ binds to troponin; tropomyosin moves, exposing the active site of actin ___Acetylcholine (ACh) triggers an end-plate potential in the motor end plate. ___ The motor neuron stops releasing ACh and Acetylcholinesterase degrades the ACh in the synaptic cleft ___An Action potential in the sarcolemma travels down the T-Tubules ___ Ca2+ is released from the sarcoplasmic reticulum into the cytosol...
1-List the different ways to represent signed integers and represent (-75) in these ways. Convert the...
1-List the different ways to represent signed integers and represent (-75) in these ways. Convert the following: (345)10 = (                          )2       (563)10 = (                            )16 (2AB5)16 = (                           )2 (1011111100111100)2 = (                        )16 Find the two's complement for the following (11011101100100)2 (34BC)16             2- Compute the following signed integer and determine if either there carry or overflow (01001110)2 + (10101100)2 (01111000)2+ (00110001)2 (00101101)2 - (01111110)2
Using Python to play Checkers: 1) Create classes to represent the necessary objects for game play....
Using Python to play Checkers: 1) Create classes to represent the necessary objects for game play. This will include, at least, the game board, the two types of pieces and the two sides. You will need to determine the best way to represent the relationship between them. 2) Set up one side of the board. Print the status of the board.
1. Suppose that the economy is hit by the coronavirus crisis. One way to represent this...
1. Suppose that the economy is hit by the coronavirus crisis. One way to represent this in the model is as lower productivity z, since some businesses need to reduce operations, and workers are less productive. a) Using the two-sided search model, determine the effects of lower z on the unemployment rate, the vacancy rate, the labour force, aggregate output, labour market tightness, and the wage. Use diagrams, and explain your results. b) Assume that to restore employment after the...
WRITE IN JAVA 1) Create a constructor that can create objects in the following way: c...
WRITE IN JAVA 1) Create a constructor that can create objects in the following way: c = Circle(X, Y, R); 2) Please add a constructor that only accepts R value and initializes the Circle at the origin. 3) Please implement a constructor that behaves the same way as the default constructor. 4) Add a method named “touches” to the Circle class which receives another Circle instance and checks whether these two circles touch each other externally and only at one...
1. when the sequence is uniquely determined? 2. what does a surplus variable represent?
1. when the sequence is uniquely determined? 2. what does a surplus variable represent?
1.List the four objects provided by the WSH to interact with the computer system using a...
1.List the four objects provided by the WSH to interact with the computer system using a scripting language: 2.What does the following instruction do? at 22:00 /every:monday dfrgui.exe 3. What does the following command line statement do? schtasks /create /? 4.What does the following command line statement do? schtasks /create /sc daily /tn t1 /tr chkdsk.exe /st 23:45:00 5.What does the following instruction do? schtasks /delete /tn task3 6. What does the following command prompt instruction do? move .\*.txt D:\files...
Q The dominant firm in the price leadership theory derives its demand curve by 1. simply...
Q The dominant firm in the price leadership theory derives its demand curve by 1. simply taking the market demand curve as its own. 2. at each price, plotting the difference between the dominant firm's demand curve and the horizontal sum of the MC curves of the fringe firms. 3. at each price, plotting the quantity supplied of the fringe firms. 4. at each price, plotting the difference between the market demand curve and the horizontal sum of the MC...
List the steps in the accounting cycle in their correct sequence: 1. Entries are made in...
List the steps in the accounting cycle in their correct sequence: 1. Entries are made in the journal 2. A business transaction occurs 3. A trial balance is prepared 4. Entries are made in the ledger
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT