DSA1002 Data Structure and Algorithm
Trimester 3A, 2024
Assignment
Weight: 40% of the unit
Assignment Location: Assignment is uploaded under Assessments section (Assessment 3: Final Assessment) on unit Moodle page.
Answer Format. When you write an answer, clearly indicate the relevant question number/letter. Include your name and student ID at the start. Also add appropriate comments to code files to indicate author name and student ID. Detailed submission guidelines can be found below in section 3.
Timeframe. The assignment will be available from Monday of 10th Week. You have to complete and submit your answers by 09:00 amon 13th January 2025 (UTC+8). You may schedule your work within this period. However, late submissions are not allowed (also check late submission policy in unit outlines).
Submission. Submit your answer document(s) to the “Assessment 3: Final Assessment” area on Moodle under assessments section. You must verify that your submission was successful. Correctly submitting is entirely your responsibility.
Report: There is a separate submission point for Report, make sure to submit report part on this submission point.
Implemented Code: There is a separate submission point for Implemented Code, make sure to submit code part on this submission point.
Reference Material. This is an OPEN BOOK and OPEN COMPUTER assignment. You may refer to any written material, including your notes, course materials, books, websites, Unit Moodle page recordings etc. However:
• You must complete this assignment entirely on your own.
• You should answer all questions in your own words and code.
• You can use pseudo code and algorithms provided in the unit slides (Moodle page) for your implementation.
• During the assignment, you may not communicate with any other students/anyone helping.
• Your answer document will be checked by text matching software for signs of cheating,collusion and/or plagiarism.
• The assignment questions have been designed such that neither of the two students, working independently,should not produce the same answers.
• The coding part of this assignment can be submitted in either python/java.
• Find detailed granular level marking rubrics at the end of the assignment.
**** READ COMPLETE DOCUMENT BEFORE STARTING****
1. Overall Assignment Description
In practicals you have implemented and learned about several algorithms and ADTs and will be implementing more of these in the remaining practicals. In this assignment, you will be making use of this knowledge to implement a system to explore and compare a variety of ADT implementations. Feel free to re-use the generic ADTs from your practicals. However, remember to self-cite; if you submit work that you have already submitted for a previous assessment (in this unit or any other) you have to specifically state this. Do not use the Java/Python implementations of ADTs - if in doubt, ask.
Introduction
This project involves developing an Inventory Management System using basic data structures and algorithms. The system will provide basic functionalities i.e., add new items, delete existing items, place orders, sorting records and retrieve low stock items.
Problem Description
The Inventory Management System will help users to manage inventory items in a store. Users can add new items, delete items, sort records, place order and retrieve low stock items. The system will make use of heap data structure to efficiently manage and retrieve low-stock items.
Task 1: Define InventoryItem Class
Create an InventoryItem class to represent individual inventory items. Include the following
attributes: Item ID, name, quantity and price.
Task 2: Manage Inventory Records using Heap
Implement following functionalities to manage inventory records using a heap:
• Adding Inventory Records: Allow users to input new item details and store them in a max heap based on quantity (high stock items first). Make sure that system does not accept two items with the same Item ID.
• Deleting Inventory Records: Implement a function to delete record using Item ID. If item not found in the record, then system should display the message “Item not found” .
Task 3: Order placement
Create a function that enables users to place an order by providing an item ID and the desired quantity. The function should first verify the availability of the item. If the item not found, it should display a message: "Item not found." If the item is available and there is enough stock to fulfill the order, the function should decrease the item's stock by the ordered quantity. If there is insufficient stock, the function should display a message: "Insufficient quantity."
Task 4: Sorting Inventory Records
Since the heap is a priority queue, items will naturally be accessible in order of their quantities (high stock items first). Since we know that heap is weakly sorted, so we need to use heap sort to sort the items based on quantity in ascending order.
Task 5: Retrieve Low Stock Items
Implement a function that returns only those items with a quantity below 5. (Hint: It can be done easily if you first sort the array using heap sort in ascending order).
Task 6: Interactive Interface and User Interaction
Design a simple text-based interface for the Inventory Management System. Menu should offer functionalities such as
• Add new Item
• Delete existing Item
• Place order
• Sort inventory records
• Display available items list
• Retrieve and display low stock items
• Exit
Create a proper Test Harness by defining a set of test cases that cover various aspects of the system's functionalities.
2 Project Report
A project report of minimum 8-10 pages should be submitted (pdf format) including following details:
Usage information:
• Introduction: describing basic introduction of your program (software).
• Dependencies: any libraries/classes required to use the program (software).
• Terminologies and abbreviations used in the code.
• Future directions: suggested future improvements.
Class UML Diagrams:
• Complete UML class diagrams of the classes used for implementation.
• A complete association of classes/objects (i.e., class relationship).
• Complexity analysis of all operations performed by the software.
• Traceability matrix of feature implementation and testing of your code2.
Comments on Code: it is suggested to add detailed comments to your code.
References: (if any) all materials should be referenced Chicago referencing style.
2Traceabiliy matrix help. (https://www.youtube.com/watch?v=8_5xZAXdS_A)
3 Submission
Submit electronically through Moodle unit page under assessments section (“Assessment 3: Final Assessment”).
You should submit a single file, which should be zipped (.zip) or tarred (.tar.gz). Check that you can decompress it on the lab/personal computers. Your work will be tested on lab/computer other than your PC so try to check your code on other PCs too. The file must be named DSA_Assignment 1 , use underscores instead of the spaces in the filename.
The file should contain following deliverables:
• Your code. This means all python/java files needed to run your program. Do not include .class files or anything else that is not required to recompile python/java files.
• Your program (software) test harnesses. One of the easiest ways for us to be sure that your code works is to make sure that you’ve tested it properly.
• Documentation and Report for your code (Project Report)
Please verify that your submission is correct and not corrupted. You may make multiple submissions, only your last one will be marked. However, late submissions are strictly not allowed (also check late submission policy in unit outlines).
4 Marking Criteria
The assignment will be marked based on the following breakdown of the submission:
Code Implementation: (20 Marks) Code should be demonstrated during the tutorial to achieve this requirement. The code should be appropriately written, as ADTs with comments. The code developed will be tested against different tests (as per requirements given in section 1).
Project Report: (10 Marks) A minimum 8-10-page report based on information described in section 2.
Code Testing and Demonstration: (10 Marks) Code should be implementable, and testable with the test harness. Also, should be demonstrated as per given schedule.