讲解 DSA1002、辅导 Java/c++设计编程
Page 1 of 9
Curtin College Bentley
DSA1002 Data Structure and Algorithm
Trimester 1, 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. You have 14 days (336 hours) to complete and submit your answers, from 09:00
am on 29th April 2024 until 09:00 am on 13
th May 2024 (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.
DSA1002 Trimester 3, 2023
Page 2 of 9
• Find detailed granular level marking rubrics at the end of the assignment.
**** READ COMPLETE DOCUMENT BEFORE STARTING****
DSA1002 Trimester 3, 2023
Page 3 of 9
1. Overall Assignment Description
In practicals you have implemented and learned about a number of 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
In this assignment, you'll utilize your knowledge of algorithms and data structures to develop
a contact list management system for mobile phones. This system will provide users with a
user-friendly interface to store, manage and access their contacts effortlessly.
Problem Description
This assignment aims to develop a Contact List Management System for mobile phones, using
a range of data structures and algorithms to efficiently organize and manage contact
information. This system will enable users to add new contact, update existing contact, delete
contact, and search for contacts. The system while also offer advanced features such as sorting,
and grouping. This system will empower users to effortlessly manage their contacts while on
the go.
Task 1: Creating DSAContact class:
Create DSAContact class to represent individual contact entry. The essential attributes of a
contact includes: name, phone number, email address and group. Group can have one of the
following values (F (family), W (workplace) and FR (Friends)). Maintaining group information
in each contact will help to categorize contacts based on different groups.
Task 2: Maintain a Contact List:
In the context of a contact list, each contact entry will be represented as a key-value pair, where
the key is a unique identifier such as contact's phone number, and the value is the contact's
information which is typically an object of DSAContact class. Use hash table data structure to
store and maintain contact information.
Input: Utilize a file (contact_list.txt) containing list of different contacts.
Output: Successful storage of contact information within the hash table, with each contact
entry represented as a key-value pair.
Task 2: Adding, Deleting or Updating Contacts:
After storing contact information in a hash table, the next step involves implementing
functionalities to interact with and manipulate the contact data.
When adding a new contact, the system should prompt the user to input the contact's
information. The system calculates the hash value based on unique key (phone number) to
determine the index in the hash table where the contact information will be stored. If a collision
occurs during insertion (i.e., multiple keys hash to the same index), the system employs
DSA1002 Trimester 3, 2023
Page 4 of 9
collision resolution technique such as chaining or double hashing to manage the collision
and ensure all contact information is accurately stored.
To delete a contact, the user specifies the phone number of the contact, system then calculates
the hash value to determine the index in the hash table where the contact is stored. If the contact
is found at the calculated index, it is removed from the hash table, effectively deleting the
contact from the system otherwise the system must inform the user that the contact does not
exist.
When updating a contact, the user must specify the phone number of the user along with the
updated information. The system calculates the hash index of the specified contact in the hash
table where the contact is stored. If the contact is found at the calculated index, the system
updates the contact information with the provided updates otherwise the system must inform
the user that the contact does not exist.
Task 3: Searching through the contact list:
The system will prompt the user to input search terms (name or phone number). Matching
contact or contacts will be presented to the user for further action.
Task 4: Sorting contact list:
The system will provide option to the user to arrange the contacts in alphabetical order by their
names. Extract the names of contacts by iterating through the hash table and collecting the
names of each contact. Sort the names using either of Merge Sort, Quick Sort or Heap Sort
algorithm.
Task 5: Categorizing contacts in groups:
The system should allow users to filter contacts based on the group attribute. System will iterate
through the hash table, whenever its encounter a contact that belongs to the desired group e.g.
F (family group), it will add it to the filtered list of contacts.
Task 6: Interactive Interface and Testing:
Design the interactive menu of the Contact List Management System. When you run the
system, it should display a list of options like:
• View contacts list
• Add new contact.
• Delete contact.
• Update contact.
• Search contacts.
• Sort contact list.
• Display contact belonging to a particular group.
• Exit
Create a proper Test Harness by defining a set of test cases that cover various aspects of the
system's functionalities. This includes testing features such as adding contacts, searching,
updating, deleting contacts, categorizing in groups, and sorting contacts.
DSA1002 Trimester 3, 2023
Page 5 of 9
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 required to use the program (software).
• Terminologies and abbreviations used in the code.
• Future directions: suggested future improvements.
Class UML Diagrams:
• Readme file, describing related information1
.
• 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 (e.g. Load data, etc.).
• 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.
1Example good Readme files can be found here. (https://github.com/matiassingers/awesomereadme)
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 file name.
The file should contain following deliverables:
• Your code. This means all python/java files needed to run your program. Do include
code provided to you as part of the assignment if that is required to run your program.
Do not include .class files or anything else that is not required to recompile python/java
files.
• README file includes short description of all files and dependencies, and information
on how to run the program (see section 2).
• 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
DSA1002 Trimester 3, 2023
Page 6 of 9
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 describe 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.
DSA1002 Trimester 3, 2023
Page 7 of 9
5 Academic Integrity
Please see the Coding and Academic Integrity Guidelines on unit Moodle page.
In summary, this is an assessable task. If you use someone else’s work or assistance to help
complete part of the assignment, where it’s intended that you complete it yourself, you will
have compromised the assessment. You will not receive marks for any parts of your submission
that are not your own original work. Further, if you do not reference any external sources that
you use, you are committing plagiarism and/or collusion, and penalties for academic
misconduct may apply.
Curtin college also provides general advice on academic integrity at
https://www.curtincollege.edu.au/content/dam/navitas/upa/curtin/pdfs/academic-integritypolicy.pdf
The unit coordinator may require you to provide an oral justification of, or to answer questions
about, any piece of written work submitted in this unit. Your response(s) may be referred to as
evidence in an academic misconduct inquiry.
DSA1002 Trimester 3, 2023
Page 8 of 9
Granular Marking Rubrics
Code Implementation (20 Marks)
a) Demonstrates correct implementation of the hash table representing the
contact list. (4)
b) Collisions occurrence while inserting new contact are handled propelry using
double hashing or chaining. (3)
c) Delete and update functions implemented correctly. (3)
d) Searching for a contact from the list is implemented correctly. (3)
e) Contact can be accurately categorized in groups. (3)
f) Accurate implementation of sorting algorithm for arranging list in alphabetical
order. (4)
Project Report (10 Marks)
• Usage Information: (2 Marks)
a) Clear introduction explaining the program's purpose and functionalities.
b) Dependencies and required libraries detailed for using the software.
• Terminologies and Future Directions: (2 Marks)
a) Clear explanation of terminologies and abbreviations used in the code.
b) Well-articulated suggestions for future improvements in the software.
• Class UML Diagrams and Complexity Analysis: (6 Marks)
a) Complete UML class diagrams depicting classes used for implementation and
their associations.
b) Thorough complexity analysis of all operations performed by the software,
e.g., load data, pathfinding, etc.
• Traceability Matrix and Comments on Code: (6 Marks)
a) A detailed traceability matrix showcasing feature implementation and testing
of the code.
b) Comprehensive comments within the code, aiding understanding and
readability.
Code Testing (10 Marks)
• Testability and Correctness: (5 Marks)
a) Demonstrated implementability and testability of the code with a
DSA1002 Trimester 3, 2023
Page 9 of 9
comprehensive test harness.
b) Successful execution and correctness of the code against various test
scenarios. (Hint: you can try some contacts in the designed phone book,
pasting images in the report)
• Error Handling and Robustness: (5 Marks)
a) Proper error handling mechanisms incorporated within the code. (Hint: you
can use custom exceptions)
b) Robustness demonstrated against unexpected inputs or scenarios.