Data Structures and Algorithms
1 Introduction
Assignment v1.0 Semester 2, 2020
Department of Computing Curtin University
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.
2 The Problem
This assignment requires the development of a solution to analyse crypto-currency trading data. You will be downloading and reading in the trade data, which defines connections between different currencies. Where currencies are not connected directly, there will be a path to follow to find an overall “exchange”, via intermediate trades. We will access data from www.binance.com via their API, to collate the currencies and valid trade pairs. From there it should be possible to query for currencies, trades and trade paths.
To get an idea of the dataset, explore the following links:
• API Documentation: https://binance-docs.github.io/apidocs/spot/en/#general-info
• Markets and trade overview: https://www.binance.com/en/markets
• Tradeable tokens: https://www.binance.com/api/v3/exchangeInfo (1062 pairs)
• Last 500 trades on a token: https://www.binance.com/api/v3/trades?symbol=ETHBTC
• Trade information for last 24 hours: https://www.binance.com/api/v3/ticker/24hr (527KB)
Your program should be called cryptoGraph and have three starting options:
• No command line arguments : provides usage information
• “-i” : interactive testing environment
• “-r” : report mode
usage: cryptoGraph –r
(1) Loaddata
o Assetdata
o Tradedata
o Serialiseddata
(2) Findanddisplayasset
e.g. “BTC”
(3) Findanddisplaytrade details
e.g. “ETHBTC”
(4) Find and display potential trade paths
Given a base asset (e.g. “BTC”) and a quote asset (e.g. “ETH”) find and display direct and indirect trade paths
(5) Setassetfilter
Choose to include or ignore certain assets e.g. ignore BTC to take those assets out of the analysis – thereby removing ~270 trade pairs
(6) Assetoverview
As statistics, or some other representation
(7) Tradeoverview
As statistics, or some other representation e.g. Top 10 for price, volume, count
(8) Savedata(serialised)
(9) Exit
You can structure the menu/UI differently, just make sure at least those options are included.
When running in report mode, you will give the input files and any parameters on the command line, then output the statistics for the dataset.
You will then investigate particular assets and trades, using the code you have developed. This investigation will be written up as the Project Report.
3 Submission
Submit electronically via Blackboard.
You should submit a single file, which should be zipped (.zip) or tarred (.tar.gz). Check that you can decompress it on the lab computers. These are also the computers on which your work will be tested, so make sure that your work runs there. The file must be named DSA_Assignment_
The file must contain the following:
• Your code. This means all .java/.py 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.
• README file including short descriptions of all files and dependencies, and information on how to run the program.
Remember: think before you code!
• Your unit 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. Make it easy for us to test your work – the test harness for class X should be called UnitTestX, or can be included in the class file for Python.
• Documentation and Report for your code, as described in Section 2.1.
• A signed and dated cover sheet. These are available from Blackboard with the assignment specification. You can sign a hard copy and scan it in or you can fill in a soft copy and digitally
sign it.
• Java Students:
o Do not include .class files or anything else that we do not need. We will recompile
.java files to ensure that what we’re testing is what we’re reading. We will use javac *.java to compile your files and run the unit tests by their expected names.
Make sure that your file contains what is required. Anything not included in your submission will not be marked, even if you attempt to provide it later. It is your responsibility to make sure that your submission is complete and correct.
3.1 Project Report
Please submit the Project Report in PDF format. Your Report will be minimum 8-10 pages (excluding UML and Javadocs) and should include the following:
Information for Use
• Introduction: Briefly discuss the functionality of your program
• Installation: requirements, dependencies & description of files/directories
• Terminology/Abbreviations:
• Walkthrough: Demonstrate all functionality, indicating anything that isn’t
implemented or working properly
• Future Work: Missing items or suggested enhancements
Traceability Matrix
Map the requirements in the specification to the implementation and tests – indicating whether they have been done and where to find more information (Class Descriptions, Justification and/or Information for Use).
Class Diagram
A UML class diagram of your code
Class Descriptions
A description of any classes you have, you need to let us know not only what the purpose of that class is but why you chose to create it. As part of this, also identify and justify any places where it was possibly useful to create a new class but you chose not to, especially when it comes to inheritance.
Justification
Explain any questions that the marker may have. This is supplemented by the comments in your code – however marks are allocated for the information being in the Project Report. In particular, when you choose an ADT, underlying data structure or an algorithm, you need to justify why you chose that one and not one of the alternatives.
You should include some prediction of the expected “performance” of your code – this includes time complexity and/or memory usage. Include the commands, input files, outputs – anything needed to reproduce your results.
References
Chicago referencing style
3.2 Marking
Marks will be awarded to your submission as follows:
Code demonstration [30 marks]
We’ll have a number of tests to run, and you get marks proportional to how many tests your code passes. If your code passes all of the tests, then you will get all of these 30 marks.
Project Report [40 marks]
PDF document – see Section 3.1
Implementation [30 marks]
We will use unit testing as well as looking at code quality; your test harnesses will have a big impact on these marks.
Students are encouraged to use testing frameworks for their harnesses – don’t stress about it though… DIY test harnesses are fine.
Bonus Marks [5 marks each]
There will be bonus marks available exceptional/additional features. Examples of enhancements could include: visualisation and plotting, optimising the trading paths, finding profitable trading loops etc.
• Marks will be deducted for not following specifications outlined in this document, which includes incorrect submission format and content and using built-in Java ADTs.
• If the cover sheet isn’t provided with your submission, your submission will not be marked and you will be awarded zero (0) marks. If you forget to submit the cover sheet you will be allowed to submit it separately to the unit coordinator but will lose 5 marks.
3.3 Requirements for passing the unit
Students must submit an assignment worthy of scoring 15% to pass the unit.
This assignment has many correct solutions so plagiarism will be easy for us to detect (and we will). For information about plagiarism, please refer to http://academicintegrity.curtin.edu.au.
In the case of doubt, you may be asked to explain your code and the reason for choices that you have made as part of coding to the unit coordinator. A failure to adequately display knowledge required to have produced the code will most likely result in being formally accused of cheating.
Finally, be sure to secure your code. If someone else gets access to your code for any reason (including because you left it on a lab machine, lost a USB drive containing the code or put it on a public repository) you will be held partially responsible for any plagiarism that results.
3.4 Late Submission
Late submissions will incur a 10% deduction per day.
3.5 Clarifications and Amendments
This assignment specification may be clarified and/or amended at any time. Such clarifications and amendments will be announced via Blackboard. These clarifications and amendments form part of the assignment specification and may include things that affect mark allocations or specific tasks.