1 Introduction
Programming Assignment
INT3071 Advanced Programming 2020/21 Semester 1
Due Date: 6 December 2020
In this assignment, you are required to implement an array-based queue and the breadth first search algorithm. You are required to read reference materials to learn how to implement them based on the foundational knowledge you acquired in this course.
2 Part 1: Array-Based Queue (60%)
The first part of this assignment is to implement a queue based on a fixed-length array. The fixed- length array is implemented based on the Array class in the file assignlib.py. Your array-based queue should meet the following requirements:
1. The queue should use the provided Array class to hold its items. It should not use any other collections such as list to do so. You should also access the stored items in Array through its instance methods. Failure to do so may result in zero mark for this part.
2. The class that implements the queue should be named ArrayQueue.
3. An integer should be used to indicate the capacity of the queue (i.e. the maximum number of
items that the queue can hold) when the queue is being created.
4. Ithasaninstancemethodnamedis_emptythatreturnsabooleanvaluetoindicatewhetherthe queue is empty or not.
5. Ithasaninstancemethodnamedenqueuethatacceptsanitemasitsparameterandimplement the typical enqueue operation of a queue. The method should print Error: The queue is full! if the queue has reached its maximum capacity.
6. It has an instance method named dequeue that returns an item and implements the typical dequeue operation of a queue. The method should print Error: The queue is empty! if the queue does not contain any item.
7. It has an instance method named to_list that returns the item held by the queue as a list object.
Remarks: You may refer to Chapter 5 (Pages 148–151) of Stephens (2019) for more information. In particular, you may need to handle the case after the number of items that have been enqueued and dequeued has reached the capacity.
3 Part 2: Breadth-First Search (40%)
Given a directed graph such as the one shown below, the breadth-first search can be used to determine whether a target node can be reached from a source node, i.e. there is a path from the source node to the target node. For example, in the graph below, node a is reachable from node b but not the opposite.
To represent a graph, one can uses a node object similar to the one below. The Node objects is similar to those used in linked lists. A Node object holds its value (name) and the links to its neighbouring
Last updated: 2020-11-09 1
abc
de
nodes. Unlike those in linked list, each node can have more than one neighbouring nodes. The code below shows also the nodes in the aforementioned figure.
class Node:
def __init__(self, name):
self.name = name
self.neighbours = []
a = Node(‘a’)
b = Node(‘b’)
c = Node(‘c’)
d = Node(‘d’)
e = Node(‘e’)
a.neighbours = [d]
b.neighbours = [d, e]
c.neighbours = [e]
d.neighbours = [e]
e.neighbours = [a]
# Nodes that can be reached from this node
In this part, you should implement a method that checks whether a target node is reachable from the source node with the following requirements:
4
1. Thesearchmethodshouldbenamedbfs.Itshouldaccepttwoparameters,indicatingthesource node and target node, respectively. The method should return True if the target node is reachable from the source node, and False otherwise.
2. The search method should be based on the breadth-first algorithm. Specifically, it should explore all nodes that have the same distance from the source node before exploring nodes that have a longer distance from the source node.
3. The search method should be able to handle directed graph with cycles. For example, it should be able to handle the cyclea→d→e→ain the example graph.
Remarks: You may refer to Chapter 6 of Bhargava (2016) and the Breadth-First Search entry in Wikipedia1 for more information.
Submission and Testing Requirements
• YoushouldwritethecodefortheArrayQueueclassandthebfsmethodinaPythonfilenamed assignment.py. You should submit only assignment.py through Moodle. Failure to submit the file properly will result in a penalty of 5 to 20 marks.
• See Moodle for the exact time of the deadline for submission. Late submission is usually not accepted. You should submit earlier to avoid possibly high traffic around the deadline.
• The file assignment.py will be tested with external test files that call the required class and methods directly. Therefore, make sure that you have named them correctly. You may use the given sample test files on Moodle for testing your code.
1https://en.wikipedia.org/wiki/Breadth-first_search
Last updated: 2020-11-09 2
• Test cases will be used to test your code. They are similar to the one given in the sample test files but may contain additional ones. The score of your assignment will be given based on which test cases your code can pass.
5 Plagiarism Policy
The assignment should be done only by yourself. Every line of code should be written by you. Discus- sions on the assignment should be kept at a high-level only. You are suggested to refer your classmates to the relevant notes or lab exercises if you want to help them.
If cheating is found, both the copier and originator will get zero mark for the assignment.
Repeat offenders may result in a deduction of the course grade.
If you have discussed the assignment with anyone, you should provide an acknowledgment at the start of your program file. Give the names of all classmates that you have discussed with. For example, your acknowledge may look like this at the start of your program file:
# Acknowledgement: I have discussed with Peppa Pig, Richard Rabbit, and Suzy Sheep.
References
Bhargava, A. Y. (2016). Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People. Manning, Shelter Island, NY.
Stephens, R. (2019). Essential Algorithms: A Practical Approach to Computer Algorithms Using Python and C#. Wiley, Hoboken, NJ.
Last updated: 2020-11-09 3