CSP2348 Assignment 3, semester 1, 2021

CSP2348 Data Structures

Assignment 3: Paired programming project

- A mini-programming project in Python/Java

- Video presentation: demonstration and reflection

Objectives from the Unit Outline

• Apply mathematical theory to algorithm analysis.

• Design algorithms using ADT and various data structures.

• Employ Python classes to encapsulate ADT and implement algorithms.

General Information:

• This is a mini programming project, requiring up to two students to work as a team to complete it. You will need to complete a project, write a short project report, and produce a short video demonstrating the project completed. Required knowledge/skills of the project tasks include algorithm design, algorithm complexity analysis, and algorithm implementation using Python (or Java) programming language.

(Note: You should use one single programming language for all programming tasks. If you wish to use a programming language other than Python (or Java), please let your tutor know beforehand, and you may be required to do a live demonstration of your work in the end).

• You are responsible for forming your team for the team-based project. You can form your team by signing in a group via the link “A3 group sign-up page” (underneath the “Assignments” in the “Assessment” section) on BB, or alternatively if you have decided to form a group with a friend/classmate, you may email the details of all your team members to your tutor so that he can help you set up a group. Please make sure you form your group by week 09.

• There are a total of three tasks: the first task is to modify some existing tree-based algorithms/methods and then convert them into Python (or Java) code/s to implement some specific application scenario/s; the second is a virtual mini-project using AVL-tree based ADTs; and the last is a video presentation, to be submitted separately, to demonstrate that your program works/functions to purpose.

• If you really prefer to work individually, you may do so, but you must let your tutor know your decision (by week 9), and agree to do the entire assignment without reducing workload of the assignment.

Due: (See Due date in Assignments section on BB)

Marks: 100 marks (which will be converted to 50% of unit mark)

Format requirement of the Assignment report (main document) (2 marks):

Submission Instructions (3 marks)

• Report submission (one submission per team): This submission should include a written report, all implementation codes (source codes, and executable if applicable) and any additional documentation associated with the report/project. This submission should be submitted by the team leader only (i.e., through the team leader’s BB submission portal - the other team member should not submit the same copy version).

This submission should be one single compressed file (e.g., in .zip format), containing all your documents (e.g., written report, source and/or executable codes/files and any other support documents, if any). The written report file must be in Word or PDF format (please refer to the section of Format requirement of the Assignment report). Please rename the .zip file in a format of

<Team-leader’s Student ID>_< team-leader’s first & last name>_< the other team member’s ID_ first name>_CSP2348_A3.zip.

If the assignment is done by an individual, please rename the .zip file in a format of

<Student ID>_< first name>_<last name>_CSP2348_A3.zip.

Note that files found to contains viruses or other infecting mechanisms shall be awarded a ZERO mark (to all team members).

• Video submission: The submission should include a video demonstration of the project (one submission per team). However, if you wanted, you may also produce a separate individual reflection video and submit it individually (one per team member).

Students Identity Verification (SIV) requirements:

For assessment integrity, the team’s video demonstration requires SIV. All team members should be present at the demonstration/presentation (i.e., unless otherwise discussed with the tutor, each team member should show or demonstrate a part of the project in the video), and SIV should be arranged in some way, e.g., either by capturing your face using computer camera (for at least 10 seconds) in the video, or capturing your student ID card during the demo, etc.

Note that separate submission links are available for video submission.

• No hard copy submission is required.

• Your attention is drawn to the university rules governing cheating/plagiarism and referencing. Please refer to the section of Academic Integrity and Misconduct in the next page.

• ECU rules/policies will apply for late submission of this assignment.

1. The project

Q1: Application to binary tree traversal & BST (40 marks)

Refer to the Lab code/s in Module 06. For a given BST, rooted at N, it prints the Pre-order, In-order and Post-order traversal sequences of the BST.

Your Task:

a) Modify the pre-order traversal algorithm such that, for a given node N in a BST, it calculates the total number of nodes of the sub-tree rooted at N, and prints all nodes, including N, of the sub-tree.

b) Modify the in-order traversal algorithm to form two code versions: one prints all leaf nodes, and the other prints all non-leaf nodes of the BST;

c) Modify the post-order traversal algorithm so that, for a given node N in a BST, it calculates the depth of the sub-tree rooted at N.

d) Up on completion of the above steps a) ~ c), write Python (or Java) code/s to implement a tiny BST application system that allows user to build a BST first and then do specific operations on the BST.

To build a BST, the system accepts a list of integers (as input), inserts them, one by one, into an (initially) empty BST.

The system then displays a Menu (see below) allowing the user to navigate through and execute the following Menu options:

1. Print the pre-order, in-order, and post-order of the BST, in sequence

2. Print all leaf nodes of the BST, and all non-leaf nodes (separately)

3. Print the total number of nodes of a sub-tree

4. Print the depth of a subtree rooted at a particular node

5. Insert a new integer key into the BST

6. Delete an integer key from the BST

7. Exit

The system continues looping and prompt user to choose one of the options until the user chooses to exit.

For option (menu item) 3, the system prompts user to enter an integer, N (as the key value of the BST). It then searches the integer N from the BST: If found, it calculates and prints the total number of nodes of the sub-tree rooted at N (by calling the algorithm developed in a)). Otherwise it prints “ERROR: Node <N> not found!”, where <N> is the entered value of N.

For option 4, the system first prompts user enters an integer, N. It then searches the integer N from the BST: If found, it calculates and prints the depth of that node in the BST (by calling the algorithm developed in c)). Otherwise it prints “ERROR: Node <N> not found!”.

For option 5, the system first prompts user enters an integer, N. It then searches the integer N from the BST: If found, it prints a message “ERROR: node key already exists in the BST!”. Otherwise it inserts N as a new node of the BST.

For option 6, the system first prompts user enters an integer, N. It then searches the integer N from the BST: If found, it deletes the node from the BST. Otherwise it prints “ERROR: Node <N> not found!”.

To test your code, enter the following list of integers to build a BST:

55, 81, 65, 20, 35, 79, 23, 14, 21, 103, 92, 45, 85, 51, 47, 48, 50, 46

[Hint: you may manually draw the BST generated from the above data set and use it to verify your code’s running results!]

Q2: AVL tree: deleting a node (25 marks)

Refer to the AVLTree class given in the Lab code (named testAVLTree.py) in Module 07. For a given list of integers, the code takes the integers as keys and inserts them, one by one, into an initially empty AVL tree (if the key is not in the AVL tree). It then prints the in_order traversal sequence of the AVL tree, and finally displays the structure of the AVL tree in a specific format (e.g., for each node, it shows its height, balance factor, together with the depth, its parent, etc. in a particular hierarchical structure).

Read the code and try to understand all methods in the class, AVLTree, including the methods insert(…), rebalance(…), lrotate(…), rrotate(…), and inorder_traverse(…), display(…), etc.

Your Task:

a) Refer to the PPT lecture 07-AVL tree.pptx in Module 7 (together with content in Module 6), design an algorithm to delete a node from an AVL tree. Then, convert the algorithm to a method (e.g., delete_ (self, key) if in Python) and add the new method into the AVLTree class. Use some test data to test the new method.

b) Up on completion of the above steps a), write Python (or Java) code/s to implement a tiny AVLTree application system that allows user to build a AVL tree first and then do specific operations on the AVL tree.

To build an AVL tree, the system accepts a list of integers (as input), inserts them, one by one, into an (initially) empty AVL tree.

The system then displays a Menu (see below) allowing the user to navigate through and execute the following Menu options:

1. Insert a new integer key into the AVL tree

2. Delete an integer key from the AVL tree

3. Print the in-order traversal sequence of the AVL tree

4. Print all leaf nodes of the AVL tree, and all non-leaf nodes (separately)

5. Display the AVL tree, showing the height and balance factor for each node.

6. Exit

You may use the existing display method for menu item 5.

To test your code, enter the following list of integers to build your initial AVL tree:

55, 81, 65, 20, 35, 79, 23, 14, 21, 103, 92, 45, 85, 51, 47, 48, 50, 46

And then test other functionalities of the code.

2. The written report (10 marks)

Refer to the Format requirement of the Assignment report in page 2. Write a project to cover (but not limited to):

i. (A brief) Introduction of project and requirements

ii. Algorithm design and implementation procedure, separated by Q1 and Q2

iii. Optional: User manual: application setting-up and usage steps (with possible screenshots)

(Note: If your project is implemented using a programming language other than Python and Java, you must include this section to allow/guide your tutor to install your project code/s to their computer environment before testing your project codes).

iv. Test cases to be used in your team’s video demo (including inputs and expected outputs, etc.)

v. Snapshots demonstrating application running status and input/outputs

vi. A conclusion or summary of the project completed

(Note: Project source codes are required and must be included separately in the .zip files)

3. The video demonstration/presentation (20 marks)

This video should mainly be a demonstration of the group project, although you may also present other contents such as explanation of the project report, etc.

Some requirements:

(1) The duration of video should be between 5 and 10 minutes.

(2) SIV should be presented.

(3) The demo should include

- the demonstration over some test cases:

(i) the case/s where a sequence of valid data is entered for BST;

(ii) the case/s where a sequence of valid data is entered for AVL tree;

(iii) the cases with some invalid data input (e.g., duplicated integers entered for insertion, non-existing key for deleting, etc.), causing the system to show error handling messages, etc.

(4) Any special features that your team wanted to show.

4. The video reflection (optional)

This video is an individual one and is optional. It should not longer than 5 minutes.

Each team member may take this opportunity, in this video, to explain his/her own contribution to the group project and written report, and to provide their individual comments to the team work that they want the tutor know, plus any further discussion into the project matter, and/or lessons learnt from the project, etc.

This video may be used to support a different mark distribution between team members if the project contributions made by individual team members are significantly different.

Indicative Marking Guide:

The END of the Assignment Description