| ASSESSMENT 3 BRIEF | |
| Subject Code and Title | ADS103 Algorithms and Data Structures |
| Assessment | Integrated Programming Assignment 3 |
| Individual/Group | Individual |
| Length | 2 source code solutions to programming problems |
| Learning Outcomes | The Subject Learning Outcomes demonstrated by successful completion of the task below include: Identify and utilise appropriate algorithms to solve software engineering problems. Identify and utilise appropriate data structures to solve software engineering problems. Apply fundamental object-oriented programming concepts to demonstrate understanding. Design and develop functions and classes to manage levels of code complexity. Demonstrate an understanding of recursive algorithms through appropriate application. Demonstrate the ability to read and interpret moderately complex code, describe its purpose, and systematically debug for issues in syntax or logic. |
| Submission | Due by 11:55pm AEST/AEDT Sunday end of Module 12 |
| Weighting | 40% |
| Total Marks | 100 marks |
Assessment Task
Implementing the two tasks below will demonstrate your understanding of binary search trees (BST), max heaps, polymorphism, and how to practically apply this knowledge to solve complex problems in the software engineering space.
Please refer to the Task Instructions for details on how to complete this task.
Context
The tasks below aim to examine your ability to implement various data structures and adapt them to suit custom-made classes.
Task 1 populates three different data structures and compares their search times against each other. In theory, a binary search tree should be able to output perform a linked list for searching on large data sets, and a balanced binary search tree even more so. But is this true in all circumstances? Is there a clear winner?
Binary search trees are quite quick to search through if you are looking for a particular node. These patterns are branched out to solve all sorts of problems, from storing data in a map with easy retrievals, to organising 3D elements in a game to render only those on screen at the time.
Task 2 asks you to delve into a more complicated aspect of object-oriented programming, polymorphism. To show this level of understanding, you will need to implement a class hierarchy and max heap data structure to house 10 or more employees, sorted with highest salary on the top. Polymorphism allows you to conveniently group similar but different objects together, amongst other benefits.
Heap is a different type of binary search tree that is more focused on keeping either the smallest or largest elements at the top of each branch. Using this, you can prioritise which data is worked with first.
Polymorphism can be used in any situation where there is a group of similar but still distinctly different datatypes. For example, it can be used to manage a user interface system where all text boxes, buttons, drop down lists, etc., are very different controls but still live under the idea of a user control. Being able to generalise your datatypes enough to group them will create shorter and easier code to test in the long run.
Instructions
For this assignment, you will create two projects to complete the tasks below.
Task 1
In this task, you will need to compare how efficient it is to search three different data structures using a large data set. The structures we will use are list (C++ Standard Library linked list implementation), binary search tree, and a balanced BST of your choice (Adelson-Velsky and Landis Tree (AVL) or red-black tree).
Step 1
Implement a binary search tree with integer-based nodes.
Step 2
Extend your BST by making a sub class of AVL or red-black tree utilising inheritance.
Step 3
#Include list in your main source file. Now insert 150,000 random numbers into a list, a BST, and a balanced BST (AVL or red-black tree). Make sure the same numbers are inserted into each.
Reference the pseudocode below for guidance:
Step 4
Present the user with a simple menu:
If the user selects 1, the user is asked to input a number. This number is searched for in the list,
binary search tree, and balanced binary search tree, recording how long it takes in milliseconds to do each. If the number is found in the structures, display the time taken to find it in each structure. If not, let the user know that the number could not be found in any of them and still show the time to complete the search on each structure.
Task 2
This task’s goal is to explore the uses of a max heap with polymorphic data. You will implement a system to store different types of employees and retrieve the highest paid from the top.
Step 1
Implement the employee class hierarchy below, taking advantage of inheritance:
Employee Class Diagram
Janitor, Programmer and CEO all inherit from Employee class. Build appropriate constructors, getters, and setters to help set and retrieve their attributes.
Step 2
Override OutputJobDescription() in each of the sub classes to output information about what they do. Programmer should also output bugsFixed and bugsCreated. CEO should also output their projected annualBonus.
Step 3
Implement a max heap structure that stores Employee pointers (for polymorphism, we need a pointer of the base type). Use employees’ salaries to help sort them into the structure with biggest salary on top and the lowest on the bottom.
Step 4
Instantiate at least 10 different Employee type objects (a mix of Employee,Janitor, Programmer, CEO types) and insert them into the max heap.
Step 5
Write a loop that retrieves the Employee pointer from the top of the max heap. Call that employee’s OutputJobDescription() and OutputEarning() methods. Then remove the top employee from the max heap structure. Repeat until the heap is empty.
The program should output to the screen the employees’ details in order of highest paid to lowest.
Referencing
It is essential that you use appropriate APA style for citing and referencing research. Please see more information on referencing here: https://library.torrens.edu.au/academicskills/apa/tool
Crediting Sources of Acquired Code
Any source code you acquire from external sources (reference works, documentation, help and tutorial sites etc.) must be preceded by a code comment that lists the original site/creator and followed by a comment that declares the end of the acquired code. Acquisitions should be kept to a few lines or fewer, and solve single problems (i.e. changing the range of a randomly generated number, handling unexpected types of input data).
Submission Instructions
Zip all projects, related files and any instructional readme.txt files for submission. Name this zip file using this format: ADS103_[your name]_[studentID]_Assignment3.zip
Submit this task via the Assessment link in the main navigation menu in ADS103: Algorithms and Data Structures. The Learning Facilitator will provide feedback via the Grade Centre in the LMS portal. Feedback can be viewed in My Grades.
Before you submit your assessment, please ensure you have read and understand the conditions outlined in the Academic Integrity Code Handbook. If you are unsure about anything in the Handbook, please reach out to your Learning Facilitator.
Academic Integrity Declaration
I declare that, except where I have referenced, the work I am submitting for this assessment task is my own work. I have read and am aware of Torrens University Australia Academic Integrity Policy and Procedure viewable online at: http://www.torrens.edu.au/policies-and-forms
I am aware that I need to keep a copy of all submitted material and their drafts, and I will do so accordingly.
Assessment Rubric
| Assessment Attributes | Fail (Yet to achieve minimum standard) 0-49% | Pass (Functional) 50-64% | Credit (Proficient) 65-74% | Distinction (Advanced) 75-84% | High Distinction (Exceptional) 85-100% |
| Task 1: Demonstrate understanding of binary search trees through implementation. Percentage for this criterion = 35% | Implements little to none of Task 1 requirements or only demonstrates a partially developed understanding of binary search trees. | Demonstrates functional knowledge of algorithms by: Implementing binary search tree and populating it with data.Building a Standard Library list and populating it with data.Demonstrating the ability to search the Standard Library list.Demonstrating the ability to search the data binary search tree. | Demonstrates proficient knowledge of algorithms by: Implementing binary search tree and populating it with data.Building a Standard Library list and populating it with data.Demonstrating the ability to search the Standard Library list.Demonstrating the ability to search the data binary search tree.Measuring time taken to search each data structure. | Demonstrates advanced knowledge of algorithms by: Implementing binary search tree and populating it with data.Building a Standard Library list and populating it with data.Demonstrating the ability to search the Standard Library listDemonstrating the ability to search the data binary search tree.Implementing a balanced binary search tree but without inheritance.Measuring time taken to search each data structure. | Demonstrates exceptional knowledge of algorithms by: Implementing binary search tree and populating it with data.Building a Standard Library list and populating it with data.Demonstrating the ability to search the Standard Library list.Demonstrating the ability to search the data binary search tree.Extending the binary search tree using inheritance to implement a balancing structure. |
| Measuring time taken to search each data structure. | |||||
| Task 2: Demonstrate understanding of object polymorphism and max heap data structure through implementation. Percentage for this criterion = 35% | Implements little to none of Task 2 requirements or only demonstrates a partially developed understanding of object polymorphism and max heap data structure. | Demonstrates functional knowledge by: Implementing the Employee class hierarchy.Implementing max heap with insert, retrieve top, and remove top methods. | Demonstrates proficient knowledge by: Implementing the Employee class hierarchy.Overriding Employee methods correctly in sub classes.Implementing max heap with insert, retrieve top, and remove top methods. | Demonstrates advanced knowledge by: Implementing the Employee class hierarchy.Overriding Employee methods correctly in sub classes.Implementing max heap with insert, retrieve top, and remove top methods.Inserting sub types of Employee correctly into the max heap. | Demonstrates exceptional knowledge by: Implementing the Employee class hierarchy.Overriding Employee methods correctly in sub classes.Implementing max heap with insert, retrieve top, and remove top methods.Inserting sub types of Employee correctly into the max heap.Retrieving and running each employee’s methods polymorphically so that the overridden sub type version of the methods are called. |
| Adheres to submission, quality and file naming guidelines, and subject’s coding conventions. Percentage for this criterion = 15% | Project displays inconsistent styling, naming, and commenting and/or some files may be missing from submission. Project may have issues running or compiling. | Project exhibits two of the below qualities: Project runs without issues, bugs, or crashes.Correct files are submitted, including a readme.txt if necessary.Naming of files, classes, functions, and variables consistently matches subject coding conventions.Project’s indentations and whitespaces are consistent and communicative.Code is well commented, explaining each code segment’s intention. | Project exhibits three of the below qualities: Project runs without issues, bugs, or crashes.Correct files are submitted, including a readme.txt if necessary.Naming of files, classes, functions, and variables consistently matches subject coding conventions.Project’s indentations and whitespaces are consistent and communicative.Code is well commented, explaining each code segment’s intention. | Project exhibits four of the below qualities: Project runs without issues, bugs, or crashes.Correct files are submitted, including a readme.txt if necessary.Naming of files, classes, functions, and variables consistently matches subject coding conventions.Project’s indentations and whitespaces are consistent and communicative.Code is well commented, explaining each code segment’s intention. | Project exhibits all below qualities: Project runs without issues, bugs, or crashes.Correct files are submitted, including a readme.txt if necessary.Naming of files, classes, functions, and variables consistently matches subject coding conventions.Project’s indentations and whitespaces are consistent and communicative.Code is well commented, explaining each code segment’s intention. |
| Creates and uses classes and functions to manage complexity, displaying an | Project does not use functions and classes, or uses them incorrectly. | Functions and classes are used within the expected minimal scope of each task. | Functions and classes are used within the expected minimal scope of each task. | Functions and classes are used within the expected minimal scope of each task. | Functions and classes are developed and designed exceptionally well, making |
| understanding of modular software design Percentage for this criterion = 15% | Some additional functions or classes have been developed to help manage complexity. | Some additional functions or classes have been developed to help manage complexity. Some functions or classes have been shifted into their own files cleanly and used correctly. | the project more manageable throughout. Classes and functions shifted into separate files cleanly and used correctly. |
| The following Subject Learning Outcomes are addressed in this assessment | |
| SLO a) | Identify and utilise algorithms appropriately to solve software engineering problems. |
| SLO b) | Identify and utilise data structures appropriately to solve software engineering problems. |
| SLO c) | Apply the fundamental applications of object-oriented programming paradigms to demonstrate understanding. |
| SLO d) | Design and develop functions and classes to manage levels of code complexity. |
| SLO e) | Demonstrate an understanding of recursive algorithms through appropriate application. |
| SLO f) | Demonstrate the ability to read and interpret moderately complex code, describe its purpose, and systematically debug for issues in syntax or logic. |
Get expert help for ADS103 Algorithms and Data Structures and many more. 24X7 help, plag free solution. Order online now!
