Assignment on Data Structures and Algorithms
13 Pages6840 Words207 Views
Added on 2019-09-24
Assignment on Data Structures and Algorithms
Added on 2019-09-24
ShareRelated Documents
Data Structures and AlgorithmsAssignmentSemester 2, 2016Department of ComputingCurtin University1PreambleIn practicals you have implemented and learned about a number of algorithms and ADTs and will beimplementing more of these in the remaining practicals. In this assignment, you will be making useof this knowledge to implement a system that is somewhat more open ended. In this system, youwill be deciding (for the most part) how to structure the program, how to use the abstract data typesand your program will need to decide on the flow of objects in and out of them. Feel free to re-usethe generic ADTs from your practicals. However, remember to self-cite; if you submit work that youhave already submitted for a previous assessment (in this unit or any other) you have to specificallystate this.The start of this assignment specification document does look somewhat daunting and confusing. Irecommend that you highlight and/or take notes. Jump to Section 4 for a breakdown of what yourprogram is expected to do for each set of marks. Note that, as you can see from Section 4, you canget many of the marks for properly completing your practicals properly and then doing a smallamount of work to apply that to this assignment.1.1 Requirements for passing the unitPlease note: As specified in the unit outline, it is necessary to have attempted the assignment inorder to pass the unit. As a guide, you should score at least 15% to be considered to have attemptedthis assignment. We have given you the exact mark breakdown in Section 4.2. Note that the marksindicated in this section represent maximums, achieved only if you completely satisfy therequirements of the relevant section.Plagiarism is a serious offence. This assignment has many correct solutions so plagiarism will be easyfor us to detect (and we will). For information about plagiarism, please refer tohttp://academicintegrity.curtin.edu.au.In the case of doubt, you may be asked to explain your code and the reason for choices that youhave made as part of coding to the unit coordinator. A failure to adequately display knowledgerequired 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 apublic repository) you will be held partially responsible for any plagiarism that results.
1.2 Late SubmissionI know for the vast majority of you, I don’t need to tell you what is in this section. But everysemester, someone always tries to see what they can get away with here. For the benefit of fairnessto the vast majority of you who do the right thing, we need to make the rules surrounding latesubmission clearAs specified in the unit outline, you must submit the assignment on the due date. Acceptance of latesubmissions is not automatic and will require supporting documentation proving that the latesubmission was due to unexpected factors outside your control. See the unit outline for details as tothe procedure for requesting that an assessment be accepted after the due date.Note that external pre-scheduled commitments including, but not limited to, work, travel, scheduledmedical, sporting, family or community engagements are not considered unexpected factors outsideyour control. If you know you have, or are likely to have, such engagements and that they may affectyour ability to complete the assignment, you will be expected to have planned your workaccordingly. This may mean that you need to start and/or complete your assignment early to makesure that you are able to hand it in on time.Also note that IT related issues are almost never a valid excuse. These include computer crashes,hard disk corruption, viruses, losing computers/storage media, networks going down (even if it isCurtin’s network - outages of the entire Curtin network of more than 24 hours may be considereddepending on circumstances) or the like. As IT professionals in training, you are expected to havesuitable backups and alternative ways of getting your assignment completed in the event that any ITproblems are encountered. You are also expected to submit your assignment ahead of time to allowfor unforeseen issues.In the event that you submit your assignment late and are deemed to have a valid excuse, you willbe penalised 10% (that is, 10% out of 100%, not out of what you would have received) per calendarday that you are late, up to a maximum of seven (7) calendar days. Any work submitted after thistime will not be marked and you will automatically fail the unit. Note that if you are granted anextension you will be able to submit your work up to the extended time without penalty – this isdifferent from submitting late.Note that the requirements for passing this unit are applied after penalties. An assignment normallyscoring 20% that is submitted one day late, even with a valid excuse, will score only 10% and thusnot satisfy the requirements for passing this unit.1.3 Clarifications and AmendmentsThis assignment specification may be clarified and/or amended at any time. Such clarifications andamendments will be announced in the lecture and on the unit’s Blackboard page (not necessarily atthe same time and not necessarily in that order). These clarifications and amendments form part ofthe assignment specification and may include things that affect mark allocations or specific tasks. Itis your responsibility to be aware of these, either by attending the lectures, watching the iLectureand/or monitoring the Blackboard page.Note that there will be at least one minor amendment to these requirements. In a normal real-worldproject a large number of amendments and clarifications would be made, so marking at least one
minor amendment is helpful in teaching you to adjust. The planned amendment(s) will not require alarge amount of time assuming you have made sensible decisions.2The ProblemYour assignment will address the problem of computing the reliability of a network. In particular,you will compute the two-terminal reliability of a directed network. This is surprisingly hard to do; allexisting solutions have an exponential worst-case complexity. Compare this with the algorithms thathave been covered so far that generally have quadratic complexity at worst. For comparison, aquadratic with input 100 (in other words we computer 1002=10,000) isn’t very large, but even asmall exponential function with input 100 is huge (2100 has about 30 digits). In other word it’s hard tocompute the two-terminal reliability of even a network with only 100 devices. In this assignment youwill be computing the reliability of networks with thousands of devices.The first part of the problem is to read the network in from a provided file. These files are discussedin Appendix II. Once this is done, the data may need to be sorted as specified in Appendix I and thespecifications for the Network class in Section 3.4.The second part of the problem is to process the network, one vertex at a time, to compute thereliability value. The main algorithm in the OBDDH class will be provided to you, as will the details ofHNode creation and modification which make up the most challenging parts of the algorithm. Thedetails of both of these classes can be found in Section 3. The OBDDH class represents the maindecision diagram used to compute the reliability and each node of that diagram is a HNode object.Your job is to provide the support classes that will allow this to function. This simulates working in ateam with an expert in the area who will supply the algorithm-specific code while you provide theproduction code.As part of the teamwork simulation, you are required to write code for a number of classes andother code will be provided for you. This is specified in Section 3. The code provided will be releasedin parts, to simulate your team member’s progress on their work. This means that you’ll have to docoding on your sections without being able to test how your code fits in with the provided code. Theonly way to do this is for both parties to stick to specifications exactly and to carefully unit test theircode.3Class SpecificationsThis section contains the specifications of the main classes required in this assignment. Some of thecode for this will be given to you over time (this represents code created by other members of yourprogramming team). All code given to you will adhere to the specifications in this section, meaningyou have to be careful that your code does as well or you will not be able to fit the various pieces ofcode together. You may not change any part of the code given to you.In order to implement the classes that are your responsibility, you may need to create other classes.Decisions such as this (and all main decisions) must be documented – see Section 4.1. You will bemarked not just on having working code but also on the efficiency of the overall solution (part ofwhich is making good decisions) and the quality of your code.
Each class lists the methods that will be provided and those that you are required to write. Providedmethods will be made available over time and required methods are ones that will be utilized by theprovided methods; you must code required methods to exactly match the specifications or they willnot work with the provided code. You may also need to code other methods that are not listed inorder to use the classes yourself. Your implementation of all classes listed below must be namedexactly as specified.Note that while the classes must implement the required methods, it is acceptable for these to beinherited from a parent class where appropriate. In other words the calls to those methods mustfunction but the actual code can be elsewhere, at your discretion. When to use inheritance is animportant part of OO programming, and you should identify this in your documentation (see Section4.1).You must write the classes yourself. You may not use existing Java classes for any class listed below.3.1FloatingPointThis ADT is responsible for safe handling of floating point numbers. This class should have a staticclass variable precision that is of type double. This should be set to 0.00000001 by default.Provided: NoneRequired:public FloatingPoint( double value) – constructor that sets the initial contents of theFloatingPoint to the double valuepublic FloatingPoint( FloatingPoint num) – copy constructorpublic boolean equals( FloatingPoint num ) - checks to see whether the two numbers arewithin precision of each other.public static void setPrecision( double value ) – sets the precision to the new value.public void add( FloatingPoint num ) – adds the given FloatingPoint number to the currentone. So calling a.add( b ) will result in a containing the sum of a and b.public void add( int num ) – adds the given integer to the current FloatingPoint one. Socalling a.add( b ) will result in a containing the sum of a and b.public void invert() – inverts the floating point number using probability laws by subtractingit from 1. So calling a.invert( ) will result in a containing the result of 1.0 - a.public void multiply( FloatingPoint num ) – multiplies the given FloatingPoint number intothe current one. So calling a.multiply( b ) will result in the object a containing the product ofthe values previously stored in objects a and b. The value in object b should not be changed.public String toString() – returns the floating point number stored in the class as a String3.2VertexThis ADT is responsible for storing the devices of the network as vertices in the graph. Vertices muststore all of the information related to them from the network file (see Appendix II).Devices must have one of the following device types: RV325, 2291K9, 1841Provided: None
End of preview
Want to access all the pages? Upload your documents or become a member.
Related Documents
Innovation and Commercialisation: A Brief History of the Mobile and Smartphonelg...
|12
|3678
|84
Unit 4: Management & Operations Assignmentlg...
|19
|7364
|387
Assignment On Programming Competition By Club Of OUMlg...
|7
|1706
|50
POM A1.1: Operations Management Assignmentlg...
|4
|961
|85
Unit 5: Management Accounting Semester and Academic Year 2020 - 2021lg...
|22
|5556
|222
Business Environmental Analysis - Assignmentlg...
|26
|8739
|87