CS112 Boston University Problem Sets for Java Distributions Homework One Homework Problem set that mainly about distributions in java. Shouldn’t be too har

CS112 Boston University Problem Sets for Java Distributions Homework One Homework Problem set that mainly about distributions in java. Shouldn’t be too hard. CS 112 Summer II, 2020– Homework Three
Due Friday, June 24th at 11:59pm with 12 hour grace period.
Introduction
This homework has two parts: in Part A you will write up answers to analytical problems related
to the lectures in the past week, both to confirm and extend your understanding of the abstract
principles discussed; in Part B you will write code to implement this understanding, and to
practice your Java coding skills. I suggest you read this whole assignment carefully and for Part
B, it is definitely worth thinking about your solution for a bit before launching Eclipse and
beginning to type. In addition to the requirements for the Java problems, you must observe the
following requirements (for all homework submitted in this course):
•
•
•
•
All programs should be literate, i.e., easily understandable by a human (say, your grader),
with appropriate header comment and other comments to explain your code as necessary;
All files for this homework should be submitted using Gradescope by the due date and
time;
You may not use data structure libraries such as ArrayList, since we are learning to write
Java from the ground up and you must learn how these libraries are built; however, you
are free to use (unless specifically directed otherwise) the basic libraries String,
Character, Scanner, and Math;
You may freely use code from the class web site, the textbook, or lecture (unless
specifically directed otherwise) as long as you cite the source in your comments; but you
may NEVER use code from the web or other students’ programs—this will be considered
plagiarism and penalized accordingly.
Part A: Analytical Problems (15 points)
The questions below are designed to reinforce the material exposed to you at lecture and from
assigned readings. Please submit your answers as a file hw04.txt (ONLY a text file, not .rtf,
Word or PDF etc.).
1.
2. Manipulating a stackGiven the following stack, depicted here from top to bottom:
+
+
3. | 6 |
4. | 8 |
5. | 1 |
6. | 3 |
7. | 7 |
8. -+—+9.
What would the stack look like after the following sequence of pushes and pops?
pop();
// assume you simply throw away the value after
popping it
10. push(2);
11. push(9);
12. push(0);
13. pop();
14. push(7);
15.
16. Manipulating a queueGiven the following queue, depicted here from the back of the
queue (left) to the front (right):
+——————-+
17. | 3 | 8 | 1 | 5 | 2 |
18. +——————-+
19.
What would the queue look like after the following sequence of enqueues and dequeues?
dequeue();
// assume you simply throw away the value
after dequeueing it
20. dequeue();
21. enqueue(9);
22. enqueue(3);
23. dequeue();
24.
25. Manipulating a priority queueGiven the following MaxQueue, depicted here from the
back of the queue (left) to the front (right):
+——————-+
26. | 1 | 4 | 6 | 7 | 9 |
27. +——————-+
28.
Assuming that items in this priority queue are kept in max order, such that larger items
leave the queue before smaller items, what would the queue look like after the following
sequence of enqueues and dequeues?
getMax();
// assume you simply throw away the value
after dequeueing it
29. insert(5);
30. getMax();
31. insert(12);
32. insert(2);
33. getMax();
34.
35. Suppose a number of push() and pop() operations are performed on a stack S.
The push() operations put the integers 0 through 9 onto S in order, and
the pop() operations print the return value. That is, the sequence looks like this:
push(0);
36. pop() and print 0 or more times;
37. push(1);
38. pop() and print 0 or more times;
39. push(2);
40. pop() and print 0 or more times;;
41. ….
42. push(9);
43. pop() and print 0 or more times;
The question is. what possible sequences of values could be produced by such a
sequence? For example, we could produce
0 1 2 3 4 5 6 7 8 9
44.
45. by pushing 0, popping it, pushing 1, popping it, and so on.
Or, we could produce
46.
47.
9 8 7 6 5 4 3 2 1 0
48.
49. by pushing 0, pushing 1, etc. up to 9, then popping all of
them off. Or, we could do
50.
51.
5 4 3 2 1 0 9 8 7 6
52.
53. by pushing 0 through 5, popping them all off, then pushing
54. 6 through 9 and popping them all of.
55.
Ok, your turn! For each of the following sequences, state whether or not they could occur
as a result of such a sequence of stack operations.
a. 9 8 7 6 5 4 3 2 1 0
b. 8 7 6 5 4 3 2 1 0 9
c. 4 3 2 1 0 5 6 7 8 9
d. 4 6 8 7 5 3 2 9 0 1
56.
57. This problem considers the same problem as (5) but for MaxQueues. Suppose a number
of insert() and getMax() operations are performed on a MaxQueue M.
The put() operations put the integers 0 through 9 onto M in order, and
the getMax() operations print the return value. That is, the sequence looks like this:
insert(0);
58. getMax and print 0 or more times;
59. insert(1);
60. getMax and print 0 or more times;
61. insert(2);
62.
63.
64.
65.
getMax and print 0 or more times;;
….
insert(9);
getMax and print 0 or more times;
For each of the following sequences, state whether or not they could occur as a result of
such a sequence of MaxQueue operations.
a. 9 8 7 6 5 4 3 2 1 0
b. 0 1 2 3 4 5 6 9 8 7
c. 5 4 3 7 6 9 8 2 1 0
d. 1 2 3 4 5 0 9 7 8 6
66.
67. Suppose we consider the same problem as in (5) and (6) for standard queues. Of course
one sequence of numbers that could be produced is the numbers in order:
0 1 2
3 4 5 6 7 8 9
68.
Is this the only sequence that you can produce, or is there is another sequence that is
possible? Explain your answer by giving another sequence or explaining why the one
given is the only possible sequence.
69.
70. Suppose you have a queue Q and a stack S and you perform the following operations:
while(! Q.isEmpty() )
// push every element of Q
onto the stack
71.
S.push( Q.dequeue() );
72.
while(! S.isEmpty() )
// Enqueue every
element popped off the stack
73.
Q.enqueue( S.pop() );
How would you describe what you have done to the queue?
74.
75. Now suppose you have a stack S and a MaxQueue M, and you perform the following
operations:
while(! M.isEmpty() )
// push
every element of M onto the stack
76.
S.push( M.getMax() );
77.
while(! S.isEmpty() )
// Insert every
element popped off the stack
78.
M.insert( S.pop() );
How would you describe what you have done to the priority queue? You may assume
there are no duplicate numbers involved.
79.
80. Now suppose you have a priority queue M, a normal queue Q, and a stack S; M and S are
initially empty, but Q has elements in it. You perform the following operations:
while( !Q.isEmpty() )
81.
M.insert( Q.dequeue() );
82.
83.
84.
85.
while( !M.isEmpty )
S.push( M.getMax() );
while( !S.isEmpty() )
Q.enqueue( S.pop() );
How would you describe what you have done to the queue Q? You may assume there are
no duplicate numbers involved.
86.
87.
88. This is an exercise in the use of reference types. Recall that Strings are reference types,
and the name of a String object can be changed, just as arrays can. What would the
following code fragment print out? String s = “Hithere”;
89. String t = “Folks”;
90. String u = “CS112”;
91. String v = s;
92. s = t;
93. t = v;
94. u = s;
95. System.out.println(s.charAt(0));
96. System.out.println(t.charAt(1));
97. System.out.println(u);
98. System.out.println(v);
99.
100.
101.
102.
Write your answers to these questions as a file hw04.txt and hand in as part of your
homework submission into the hw04 folder in Websubmit.
Again, do these by hand to verify understanding, and don’t just type them into Java for the
answers. If you do so, then you will be unable to do such problems on tests!
Part B: Programming Problems (85 points)
Problem B.1 (Lab Problem) (5 points)
For this problem, you must hand in the Challenge Problem code from Lab 2.
Problem B.3 Ring Buffer Deque (40 points)
For this problem you will create a Deque ADT using the circular-buffer technique presented in
lecture. Please review the lecture slides on circular buffers before starting this problem.
For this problem, you will not use a Java interface file (as you will in the next problem) but
simply provide the appropriate methods as specified in the template code.
Dealing with Overflow by Resizing the Array
A simple but effective way to deal with the problem of overflow for array-based data structures
such as stacks and queues is to reallocate a larger array and move all the data items over to the
new array. This is called resizing, and you should create a method resize() following this
pseudo-code:
// Assuming that the data is held in an array A whose length is
given by the variable SIZE,
// this method will replace A by an array twice as big, with the
same data items.
public void resize() {
// allocate an array B twice as big as A
// update the variable SIZE to indicate the new maximum
size
// copy all the elements from A over to B
A = B;
// replace A with B
}
This method would be called from inside enqueueFront and enqueueRear if the data
structure is full and can not store any more elements. One complication is that the elements in the
queue almost certainly will not line up perfectly at the beginning of A (i.e., with the front at
A[0]), and so you can’t just copy them over to the same locations. So, you would need to do
something like this:
B[0] = A[front];
B[1] =
next item clockwise around circle from A[front];
// naturally, you will use nextSlot(front)
….
B[A.length – 1] = item at end of queue, which is in fact
previous item counter-clockwise around the circle from A[front]
// the rest of B will have 0’s.
and then reset front and next appropriately.
Requirements and Suggestions
You should start from the template IntDeque.java and MUST satisfy the following requirements
for this problem:
•
•
•
•
Provide your solution as a file IntDeque.java, providing implementations for all the
interface methods; you may provide any other methods you like, but make them private;
Use the circular-buffer implementation as shown in lecture;
Deal with overflow using the resize() method as described above;
Initialize your array to a length of 10 using a variable SIZE;
•
Remove all debugging code before submission;
•
Make sure that your program compiles with the interface file Dequeable.java;
•
Make sure that your program satisfies the Unit Tests in the template.
You SHOULD do the following while developing your program:
•
Read over the lecture notes on circular buffers and the dequeue ADT from the lecture
slides before starting to work;
•
Apply the debugging techniques from the lab as necessary to develop your program;
•
Use step-wise refinement to develop your solution, following these steps, in order:
1. Fill out the IntDeque.java template file with “stubs” for all methods; get it to
compile by returning a 0 for any method that returns an int; Verify that your
program compiles (but it will fail all the performance tests);
2. Comment out all but the first performance test; and then write the basic circularbuffer code, and verify that it passes the first test;
3. Similarly, write the size() and isEmpty() methods and test them with the second
performance test; as you proceed, uncomment each successive test one at a time;
4. Implement enqueueRear() and test it with the third test (Hint: this is just
enqueue() from the normal queue);
5. Implement dequeueFront() and test it similarly (Hint: this is just dequeue() from
the normal queue);
6. Write a method int previousSlot(int k) by analogy with nextSlot(….) and
temporarily add tests to the unit test to make sure it (i) works in the middle of the
array (i.e., previousSlot(5) should return 4) and (ii) as it moves over the ends of
the array (i.e., previousSlot(0) should return 9); after testing this method, then
delete these tests (they aren’t permanently useful);
7. Implement enqueueFront() and write tests to verify that it works;
8. Implement dequeueRear() and write tests to verify that it works;
9. Now implement a private method resize() and write code at the very beginning of
enqueueFront() and enqueueRear() to test whether the queue is full; if it is, then
call resize() before proceeding to do the insertion; write unit tests to verify that
your queue will resize at least once.
10. Verify that your code satisfies all tests; you may leave your own tests in or delete
them, as you wish.
•
Check the formatting and commenting and make sure everything looks great before
submitting.
Submit your file IntDeque.java as part of your homework submission for HW 03.
Problem B.3 Building a Queue from Two Stacks (40 points)
For this problem you will explore the relationship between stacks and queues by considering
how a queue may be implemented by two stacks. This is a clever algorithm which explores the
relationship between these two data structures. It is also another alternative since most enqueue
and dequeue operations take a fixed amount of time, and you do not have to move all the
elements over every time. Finally, it will exercise your knowledge of Java interface files, which
will be covered first thing in the next lecture.
Implementing a queue with two stacks
The basic of idea of the program follows from the observation that in some sense, you can
consider a queue to be two stacks with their bottoms stuck together, with their tops facing in
opposite directions. Let us call them InStack and OutStack; here is the queue from problem
A.3 above with 3 at the rear of the queue and 2 at the front:
+——————-+
| 3 | 8 | 1 | 5 | 2 |
+——————-+
There are multiple ways to represent this queue as two stacks. Here is one way:
InStack
| OutStack
+———–+——-+
| 3 | 8 | 1 | 5 | 2 |
+———–+——-+
|
that is,
InStack:
| 3 |
| 8 |
| 1 |
-+—+and here is another:
OutStack:
| 2 |
| 5 |
-+—+-
InStack |
OutStack
+——-+———–+
| 3 | 8 | 1 | 5 | 2 |
+——-+———–+
|
that is,
InStack:
| 3 |
| 8 |
-+—+and here is yet another:
OutStack:
| 2 |
| 5 |
| 1 |
-+—+-
InStack
|
+——————-+
| 3 | 8 | 1 | 5 | 2 |
OutStack
+——————-+
|
that is,
InStack:
| 3 |
| 8 |
| 1 |
| 5 |
| 2 |
-+—+-
OutStack (empty):
-+—+-
Now, the question is: how do we implement the standard queue operations using stack
operations on InStack and OutStack? Let’s consider this and show examples using the first
representation of the queue above. Some are very easy:
To enqueue a number, simply push it on the InStack:
InStack
| OutStack
+———–+——-+
| 3 | 8 | 1 | 5 | 2 |
+———–+——-+
|
=>
enqueue(7)
=>
InStack
| OutStack
+—————+——-+
| 7 | 3 | 8 | 1 | 5 | 2 |
+—————+——-+
|
To dequeue a number, simply pop it off the OutStack (let us continue with the previous
configuration):
InStack
| OutStack
+—————+——-+
| 7 | 3 | 8 | 1 | 5 | 2 |
+—————+——-+
|
=>
dequeue()
=>
InStack
| OutStack
+—————+—+
| 7 | 3 | 8 | 1 | 5 |
+—————+—+
|
=>
2
But what if, when we want to dequeue a number, the OutStack is empty? In that case, we pop all
the members of the InStack off and push them all onto the OutStack. Let us do two more
dequeue()’s on the previous configuration and see how this works:
=>
dequeue()
=>
InStack
|
+—————+
| 7 | 3 | 8 | 1 |
+—————+
|
OutStack
=>
5
=> dequeue() … Outstack empty, so pop off Instack and push
on OutStack until InStack is empty:
InStack
| OutStack
+———–+—+
| 3 | 8 | 1 | 7 |
+———–+—+
|
InStack | OutStack
+——-+——-+
| 8 | 1 | 7 | 3 |
+——-+——-+
|
InStack | OutStack
+—+———–+
| 1 | 7 | 3 | 8 |
+—+———–+
|
InStack | OutStack
+—————+
| 7 | 3 | 8 | 1 |
+—————+
|
Finally we can complete the dequeue() by popping the OutStack:
InStack | OutStack
+———–+
| 7 | 3 | 8 |
=> 1
+———–+
|
So, the punchline is: if the OutStack is empty when you want to dequeue(), empty out the
InStack and push its contents onto the OutStack before proceeding.
Notice how this algorithm cleverly uses the fact that if you push a list of numbers on a stack and
pop them off, they come off in reverse order: since the list of numbers being enqueue()’ed must
come out of the queue in the same order they came in, we reverse them twice, once as they move
from the InStack to the OutStack, and once as they come out of the OutStack. (If this were a
Trump Tweet, I would conclude with: Nice!)
I will leave it to you to figure out peek(), size(), and isEmpty(). Overflow will be
handled by resizing in the stacks, and as usual we will not worry about underflow for now.
The Problem
You must fill in the template code IntQueue.java, which has a Unit Test Main as usual. Here is
the Queueable.java interface you need for this template. You must follow these requirements:
(1) You must use the AnotherStack.java ADT to implement the queue, as shown above, and you
must follow the paradigm from lab by using the interface Stackable.java to declare your stacks,
e.g.,
Stackable S = new AnotherStack();
(Hint: the two stacks will be fields inside the IntQueue object.)
(2) The IntQueue object must implement the Queueable.java interface you created in lab;
you will see this in the template and the Unit Test Main.
(3) The toString() method must print out the queue by rotating the queue, building up the result
String by concatenating each element as it is dequeued and before it is enqueued back into the
queue:
If there are N elements in the queue, do this N times:
int n = dequeue();
…concatenate n and a tab (“t”) onto the result String…
enqueue( n );
At the end of this process, you will have a String representation of the queue, in order, and the
queue will be back in its original configuration.
(4) You may NOT declare an array or any other data structure (except for the two stacks) to help
implement the queue;
(4) You may NOT change anything about AnotherStack.java or Stackable.java;
(5) All performance tests in the Unit Test Main must be satisifed.
Hand in your solution as IntQueue.java.
Submission Checklist
•
•
•
Submit all files by the due date and time; the time of submission will be when the LAST
file is uploaded.
Verify that you have satisfied all of the requirements for all the problems, and verify that
you have tested your code thoroughly.
Submit the following files:
1. hw03.txt
2. The challenge problem code from lab
3. IntDeque.java
4. IntQueue.java

Purchase answer to see full
attachment