Full Name:
• Make sure that your exam is not missing any sheets, then write your full name on the front.
• Write your answers in the space provided on the page with each problem. If you make a mess, clearly indicate your final answer.
• The problems are of varying difficulty. The difficulty is not correlated with the problem number or the number of points so make a first pass and solve some easy problems.
Copyright By PowCoder代写 加微信 powcoder
• This exam is closed book, no notes, no electronics, no nothing. Just you and your trusty pencil.
Total (42)
Disclaimer: This number is not a measure of your worth as a human being; it is merely an (imperfect) measure of your mastery of the material in (the first half of) this class. Don’t lose track of the big picture.
The questions on this exam are about an abstract data type which we have not seen in this class: the deque. Fear not, your understanding of other ADTs and data structures will allow you to understand deques as well.
A deque is a double-ended queue, which means a queue where elements can be added and removed at either end. Accordingly, the operations provided by the deque ADT (as a DSSL2 interface) are as follows:
interface DEQUE[T]:
def empty?(self) -> bool?
def push_front(self, element: T) -> VoidC
def push_back(self, element: T) -> VoidC
def pop_front(self) -> T
def pop_back(self) -> T
When writing out abstract deque values, we will use a similar notation to the one we used in class for queues. The front of a deque being the left side, and the back the right side. For example:
Ÿ22 24 179Ÿ
is a representation of a deque with elements 22, 24, and 179, with 22 at the front and 179 and the back.
The names and signatures of the operations should give you an intuition about what each operation should be doing. But to make this precise, any deque implementation should satisfy the following laws.
ŸŸ.empty?pqñTrue
Ÿe1 …ek ek`1 Ÿ.empty?pq ñ False
tq “ Ÿe1 …ekŸu tq “ Ÿe1 …ekŸu tq “ Ÿe1 e2 …ekŸu
tq “ Ÿe1 …ek ́1 ekŸu
For example, if we start with the deque Ÿ22 24 179Ÿ and use the push_back operation to add a new element 34,
the resulting deque will be Ÿ22 24 179 34Ÿ.
If we then call the pop_front operation, it will return 22 and the deque will become Ÿ24 179 34Ÿ.
q.push_frontpeq tq “ Ÿe e1 …ekŸu q.push_backpeq tq “ Ÿe1 …ek eŸu q.pop_frontpq ñ e1 tq “ Ÿe2 …ekŸu
q.pop_backpq ñ ek tq “ Ÿe1 …ek ́1Ÿu
Problem 1 ( / 8)
Consider, as one possible implementation of the deque ADT, a linked-list based implementation.
This particular implementation consists of a singly-linked list with both a head and a tail pointer. For reference, the start of such a class would look something list this:
class LinkedDeque (DEQUE):
A. (3 points)
Draw a diagram of the deque Ÿ22 24 179Ÿ using that concrete implementation.
B. (1 point)
With the exact representation described above, without additions or modifications, what would be the time complexity of the empty? operation? Justify your answer (1 sentence).
C. (1 point)
The push_front operation? Justify your answer (1 sentence).
D. (1 point)
The push_back operation? Justify your answer (1 sentence).
E. (1 point)
The pop_front operation? Justify your answer (1 sentence).
F. (1 point)
The pop_back operation? Justify your answer (1 sentence).
Problem 2 ( / 8)
A. (3 points)
What (simple) modification could we do to the linked-list representation from the previous question to make some of the deque operations more efficient (in terms of time), while retaining its linked nature?
Name that modification; a keyword or short phrase is sufficient.
B. (1 point)
With this new representation, what would be the time complexity of the empty? operation? Justify your answer (1 sentence). If the justification is the same as for question 1, you can answer that it’s the same.
C. (1 point)
The push_front operation? Justify your answer (1 sentence).
D. (1 point)
The push_back operation? Justify your answer (1 sentence).
E. (1 point)
The pop_front operation? Justify your answer (1 sentence).
F. (1 point)
The pop_back operation? Justify your answer (1 sentence).
Problem 3 ( / 20)
In class, we have seen how the ring buffer data structure can be used to implement the queue ADT.
In this question, we will ask you to adapt the queue ring buffer we have seen to instead implement the deque ADT. Your answers should be in the form of DSSL2 code. As you do not have access to a computer, we will not be sticklers for exact syntax; do your best to write correct DSSL2, and make sure the intent of your code is clear.
Comments may be helpful in the event we need to divine what your code is meant to be doing. Tests are not necessary in this setting, but you may find it helpful to think about what the proper behavior should be on particular examples.
We expect your code to have proper handling of error cases. Throwing errors is a reasonable choice. Ignoring such cases and letting your implementation fall over is not. It is not necessary to ever grow the ring buffer for your solution to be correct.
For reference, the code for the queue ring buffer is on the last page of the exam. You may detach that page; just try not to make a mess. The methods you write may refer to existing fields and methods from that ring buffer class. You’re also allowed to answer that one of the requested methods would be identical to one from the original ring buffer; just tell us which one.
Incasethathelps,themodulooperationisdefinedfornegativeinputs:-1 % 4 == 3,-2 % 4 == 2,andsoon. A. (2 points)
Please list and describe any fields you would add to turn the queue ring buffer into a deque ring buffer.
B. (2 points)
Provide an implementation of the empty? method.
C. (8 points)
Provide an implementation of the push_front and push_back methods.
D. (8 points)
Provide an implementation of the pop_front and pop_back methods.
Problem 4 ( / 6)
A. (3 points)
Describe an advantage of the linked implementation over the ring buffer implementation. A sentence or two is sufficient.
B. (3 points)
Describe an advantage of the ring buffer over the linked implementation implementation. A sentence or two is sufficient.
The queue ring buffer implementation.
You may detach this page for easier reference; just try not to make a mess.
class RingBuffer (QUEUE):
def __init__(self, capacity):
self.data = [False; capacity]
self.start = 0
self.size = 0
def capacity(self):
return self.data.len()
def len(self):
return self.size
def empty?(self):
return self.len() == 0
def full?(self):
return self.len() == self.capacity()
def enqueue(self, element):
if self.full?(): error(‘RingBuffer.enqueue: full’)
self.data[(self.start + self.size) % self.capacity()] = element
self.size = self.size + 1
def dequeue(self):
if self.empty?(): error(‘RingBuffer.dequeue: empty’)
let result = self.data[self.start]
self.data[self.start] = False
self.size = self.size – 1
self.start = (self.start + 1) % self.capacity()
return result
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com