任选算法并实现，这里选择Boruvka’s Algorithm.
Problem Statement
In this assessment you are asked to write a technical report of an algorithm chosen by yourself, implement it using a programming language, and create a video to demonstrate your code and its results.
- Your report is suggested to include the following contents about the chosen algorithm:
- The main principals of the algorithm;
- The pseudo code to describe the algorithm;
- The complexity (time and space) analysis of the algorithm;
- The limitations or constraints of the algorithm and the advances that could overcome them;
- The applications of this algorithm in diverse areas for problem solving (e.g. how the algorithm changed or is changing the world).
The report should be no more than 1500 words. The title page, references and appendices are not counted. Please respect the following formatting constraints: Times New Roman or Arial (If you use Latex, the default font, Computer Modern, is also fine. ), at least font size 11, margins (2.0cm sides, 2.0cm top and bottom), and single line spacing.
A separate title page containing the title, student number, abstract, word count and a signed declaration stating: I certify that all material in this report which is not my own work has been identified. should be provided.
- Implement the algorithm using a programming language of your choice (Python and Matlab are recommended), and submit the source code along with the report. Your script should perform correctly and have sufficient comments.
- Create a short video (no more than 5 minutes) to introduce the algorithm including its background, principles, importance and your implementation, and demonstrate how the code works. You can submit the video file to the module ELE page, or a publicly accessible website (e.g. Youtube or Vimeo) and clearly attach the link to this video in the report.
Algorithms
You can choose an algorithm from the list below. Alternatively you can suggest an algorithm that is not covered by this module (in this case, you should discuss your choice with the module leader within one week of handout).
- Multicast routing algorithm for sensor networks.
- Frequent pattern growth (FP-Growth) algorithm.
- The Edmonds-Karp algorithm for finding the maximum flow.
- Orthogonal range searching and k-d trees algorithms.
- Boruvka’s algorithm.
- Reed-Solomon algorithm.
- Quickhull algorithm.
- Iterative solvers, e.g. Jacobi, Gauss Seidel.
- One derivative-free optimization algorithm.
Writing
Your technical report must be well structured and written in good English. Pay attention to the following:
- Spelling, punctuation and grammar.
- Writing in short, snappy sentences.
- Making sure to define acronyms.
- Referencing properly.
References
If you refer to other published documents in your report, you must cite the source using a standard citation style (e.g. IEEE, Harvard, etc. ).
- All references must be presented in a consistent and uniform style.
- All references must be presented in a font no smaller than 11 point.
Deliverables
The deliverables for this coursework comprise one electronic submission. You should name the submission as StudentID CandidateNumber.
- The source code, video file and report should be compressed into one single file and submitted to E-BART system by 11:59am on the date indicated on the front page of this document. The link to the submission page can be found using the method introduced in the handbook above. See the On-line Submission Student Handbook for other requirements.
If the file size is over 99MB, you should submit the video to a publicly accessible website such as YouTube and clearly indicate the link in the report.
You are suggested to complete the submission at least a few hours before the deadline, leaving enough time for potential last-minute amendments.
Feedback
What contributes to an outstanding report: An excellent description of the main principles and aims of the algorithm and the pseudo code. The complexity is analysed correctly and concisely. The limitations of the algorithm are clearly described and the suggestions to overcome these limitations are reasoned with sufficient supports. The applications are clear and appropriate. The report is logically structured, professionally formatted and well written in academic English.
What contributes to an outstanding source code submission: The code produces intended results correctly, without clear bugs and any unexpected outputs. The algorithm adopts proper data structures and is efficiently implemented. There is a good software design that prints adequate instructions and displays the results clearly and informatively. The layout of the source code is clear and nicely formatted. There are correct and sufficient comments.
What contributes to an outstanding video submission: There is an excellent introduction of the algorithm and all the key points are presented with sufficient details. The presentation is well organised with relevant, eective and sufficient visual aids. Outstanding language skills are demonstrated.