CS 234 Spring 2020 | Assignment 2
Instructors: Ten Bradley and Armin Jamshidpey
Due date: June 24, 2020 at 5:00pm
Coverage: Modules 3, and 4
This assignment consists of a programming and written component. Please read the course website carefully to ensure that you submit each component correctly. Assignment solutions are to be submitted to Markus.
(a) (2 Marks) Create interface for the Stack ADT. The Stack must support the operations listed in Section 3.1. You must write the full design recipe for each operation.
(b) (5 Marks) Implement the Stack ADT using a Linked List (Single or Double). Other operations can be included but are not necessary.
For the Linked List, you can design your own Linked List or use the code presented in class. Include the code for the Linked List you are using in stack.py.
P2. (10 marks) In class, a Stack was used to match brackets in Racket code. Another part of a Racket program that requires matching is strings. A string is text that is enclosed in double quotes. Characters in a string are not included when checking if the program’s brackets match.
In this question, you will write an algorithm that determines if a Racket program has matching parentheses using a Stack. For this, you must ensure that all square brackets, parentheses, and braces are matched. You are welcome to build your algorithm on top of the pseudocode presented in class that solved the original problem.
Additionally, you must account for strings given in double quotes. Any characters that are within a string are not matched with characters outside of the string. For example, the following Racket program has matching
parentheses:
(define func "world)")
The parenthesis after world is not matched with the open parenthesis at the beginning because it is contained in a string. Also note that characters in a string following a backslash are called escaped characters. In particular, n" is a way to have a double quote as part of a string without having it match an open double quote (and therefore closing the string). You can read more about these characters here:
https://docs.racket-lang.org/guide/strings.html
You will need to add support for the double quote escaped character in your algorithm. For example, the following Racket program has matching double quotes and brackets: (define func "world)\"boo")
For testing purposes, we have provided you with an implementation of Stack that uses Python lists stack.py.
Submitting this implementation to Question 1 will result in no marks for the question. You may not use Python lists for this assignment.
Your solution file should contain a function is matched which takes a filename and returns a boolean, True if matched, False if not. Make sure your program runs when called like so: from matching_racket import is_matched
is_matched("input.txt")
Submit your solution in the file matching racket.py.
P3. (10 marks) The Queue ADT restricts the user to adding elements to one end of the Queue, and removing elements from the other end of the Queue. A possible extension to a Queue is to allow elements to be added and removed from both ends of the Queue. The interface for this new ADT (we will call it TwoWayQueue) is given in Section 3.2.
Implement the methods given in the interface for the TwoWayQueue ADT using a doubly linked list. The running time of all operations should be Θ(1). For the Linked List, you can design your own Linked List or use the code presented in class.
Submit your solution (including the code for the underlying data structure) in the file two way queue.py.
Note: self must not be empty for operations dequeue last, dequeue first, last, first, shift last, and shift first.
The ADT represents a circular singly-linked list containing Node objects. The only field of the class is tail.
Due date: June 24, 2020 at 5:00pm
Coverage: Modules 3, and 4
This assignment consists of a programming and written component. Please read the course website carefully to ensure that you submit each component correctly. Assignment solutions are to be submitted to Markus.
1 Programming Component
P1. The Stack ADT follows a first-in, last-out model. That is the item most recently added is the next item that will be removed from the Stack. Both parts of this question should be submitted in the file stack.py to Markus. Only one file needs to be submitted.(a) (2 Marks) Create interface for the Stack ADT. The Stack must support the operations listed in Section 3.1. You must write the full design recipe for each operation.
(b) (5 Marks) Implement the Stack ADT using a Linked List (Single or Double). Other operations can be included but are not necessary.
For the Linked List, you can design your own Linked List or use the code presented in class. Include the code for the Linked List you are using in stack.py.
P2. (10 marks) In class, a Stack was used to match brackets in Racket code. Another part of a Racket program that requires matching is strings. A string is text that is enclosed in double quotes. Characters in a string are not included when checking if the program’s brackets match.
In this question, you will write an algorithm that determines if a Racket program has matching parentheses using a Stack. For this, you must ensure that all square brackets, parentheses, and braces are matched. You are welcome to build your algorithm on top of the pseudocode presented in class that solved the original problem.
Additionally, you must account for strings given in double quotes. Any characters that are within a string are not matched with characters outside of the string. For example, the following Racket program has matching
parentheses:
(define func "world)")
The parenthesis after world is not matched with the open parenthesis at the beginning because it is contained in a string. Also note that characters in a string following a backslash are called escaped characters. In particular, n" is a way to have a double quote as part of a string without having it match an open double quote (and therefore closing the string). You can read more about these characters here:
https://docs.racket-lang.org/guide/strings.html
You will need to add support for the double quote escaped character in your algorithm. For example, the following Racket program has matching double quotes and brackets: (define func "world)\"boo")
For testing purposes, we have provided you with an implementation of Stack that uses Python lists stack.py.
Submitting this implementation to Question 1 will result in no marks for the question. You may not use Python lists for this assignment.
Your solution file should contain a function is matched which takes a filename and returns a boolean, True if matched, False if not. Make sure your program runs when called like so: from matching_racket import is_matched
is_matched("input.txt")
Submit your solution in the file matching racket.py.
P3. (10 marks) The Queue ADT restricts the user to adding elements to one end of the Queue, and removing elements from the other end of the Queue. A possible extension to a Queue is to allow elements to be added and removed from both ends of the Queue. The interface for this new ADT (we will call it TwoWayQueue) is given in Section 3.2.
Implement the methods given in the interface for the TwoWayQueue ADT using a doubly linked list. The running time of all operations should be Θ(1). For the Linked List, you can design your own Linked List or use the code presented in class.
Submit your solution (including the code for the underlying data structure) in the file two way queue.py.
2 Written Component
W1. (6 marks) Write the pseudocode for removing and returning only the second element from the Stack. The top element of the Stack will remain the top element after this operation. You may assume that the Stack contains at least two items before this operation.(a) Write the algorithm as a provider implementing a Stack using a contiguous memory implementation. You can refer to the implementation given in stack.py. Your implementation should directly access the fields of the Stack, specifically a contiguous array called data, and and integer first that contains the first empty slot in data.W2. For each of the following, briefly describe an algorithm using the ADT Stack and/or Queue to achieve the goal. You may use multiple of both ADTs if desired. Your solution can contain pictures, pseudocode, and point form to describe your algorithm. Unless otherwise specified, the state of the original data does not need to be preserved.
(b) Write the algorithm as a provider implementing a
(b) Write the algorithm as a provider implementing a Stack using a linked implementation, such as your implementation for P1. b). Your implementation should directly access the fields of the Stack, specifically head that stored the first node in a linked list.
(c) Write the algorithm as a user with the provided interface for
(c) Write the algorithm as a user with the provided interface for Stack. You can only use the provided operations for the Stack
(a) (2 marks) Given an ADT Queue named Q, provide an algorithm to create a new ADT Queue with all instances of item removed from Q while maintaining the order of the items.
(b) (2 marks) Given an ADT Stack named S, provide an algorithm to create a new ADT Stack containing all the elements in S in the opposite order they were in S. The first element that was would be removed from S will be the last element removed from the new Stack.
(c) (4 marks) Given an ADT Stack names S, provide an algorithm to take the top k items and reverse their order in S. This algorithm modifies S.
W3. (4 marks) Suppose you have created a class called CircularLinkedList whose interface is provided in the ADT Interfaces.
As the provider with access to the fields, write pseudocode for a function Length(L) that computes and returns the length of a CircularLinkedList. You cannot add any other fields to the class.
3 ADT Interfaces
3.1 Stack
| Name | Returns | Modifies |
| Stack() | An empty Stack | |
| is empty(self) |
True if self is empty, false other wise |
|
| push(self, data) |
Adds data as the most recent ele ment to self. |
|
| top(self) |
The most recent element added to self. |
|
| pop(self) |
The most recent element added to self. |
Removes the most recent element added to self. |
3.2 TwoWayQueue
| Name | Returns | Modifies |
| TwoWayQueue() | An empty TwoWayQueue | |
| is empty(self) |
True if self is empty, false other wise |
|
| first(self) | First element in self | |
| last(self) | Last element in self | |
| enqueue first(self, data) |
data is added as first element in self |
|
| dequeue first(self) | First element in self | Removes first element from self |
| enqueue last(self, data) |
data is added as the last elemenf in self |
|
| dequeue last(self) | Last element in self | Removes last element from self |
| shift first(self) |
The first element in self is moved to the end of self |
|
| shift last(self) |
The last element in self is moved to the front of self |
|
| dequeue all(self) | Removes all elements from self |
3.3 CircularLinkedList
The list is implemented using Node. The last element of a circular linked list points to the first node of the list.The ADT represents a circular singly-linked list containing Node objects. The only field of the class is tail.
| Name | Returns | Modifies |
| CircularLinkedList() | An empty CircularLinkedList | |
| Is Empty(L) | True if L is empty, false otherwise |
3.4 Node
A Node is a data structure with two fields: data and next.
2020-06-19