FIT2004 2024 Semester 1: Assignment 2
DEADLINE: Wednesday 22th May 2024 23:55:00 AEST.
LATE SUBMISSION PENALTY: 10% penalty per day. Submissions more than 7
calendar days late will receive 0. The number of days late is rounded up, e.g. 5 seconds
late means 1 day late, 27 hours late is 2 days late.
For special consideration, please visit the following page and fill out the appropriate form:
https://forms.monash.edu/special-consideration.
The deadlines in this unit are strict, last minute submissions are at your own risk.
PROGRAMMING CRITERIA: It is required that you implement this exercise strictly
using the Python programming language (version should not be earlier than 3.5). This
practical work will be marked on the time complexity, space complexity and functionality
of your program, and your documentation.
Your program will be tested using automated test scripts. It is therefore critically impor-
tant that you name your files and functions as specified in this document. If you do not, it
will make your submission difficult to mark, and you will be penalised.
SUBMISSION REQUIREMENT: You will submit a single python file containing all
of the questions you have answered, assignment2.py. Moodle will not accept submissions
of other file types.
PLAGIARISM: The assignments will be checked for plagiarism using an advanced pla-
giarism detector. In previous semesters, many students were detected by the plagiarism
detector and almost all got zero mark for the assignment (or even zero marks for the unit as
penalty) and, as a result, the large majority of those students failed the unit. Helping others
to solve the assignment is NOT ACCEPTED. Please do not share your solutions partially
or completely to others. Even after the deadline, your solutions/approaches should not be
shared before the grades and feedback are released by the teaching team. Using contents
from the Internet, books etc without citing is plagiarism (if you use such content as part
of your solution and properly cite it, it is not plagiarism; but you wouldn't be getting any
marks that are possibly assigned for that part of the task as it is not your own work).
The use of generative AI and similar tools for the completion of your assignment
is not allowed in this unit!
1 Learning Outcomes
This assignment achieves the Learning Outcomes of:
• Analyse general problem solving strategies and algorithmic paradigms, and apply them
to solving new problems;
• Prove correctness of programs, analyse their space and time complexities;
• Compare and contrast various abstract data types and use them appropriately;
• Develop and implement algorithms to solve computational problems.
In addition, you will develop the following employability skills:
• Text comprehension.
• Designing test cases.
• Ability to follow specifications precisely.
Assignment timeline
In order to be successful in this assessment, the following steps are provided as a suggestion.
This is an approach which will be useful to you both in future units, and in industry.
Planning
1. Read the assignment specification as soon as possible and write out a list of questions
you have about it.
2. Try to resolve these questions by viewing the FAQ on Ed, or by thinking through the
problems over time.
3. As soon as possible, start thinking about the problems in the assignment.
• It is strongly recommended that you do not write code until you have a solid feeling
for how the problem works and how you will solve it.
4. Writing down small examples and solving them by hand is an excellent tool for coming
to a better understanding of the problem.
• As you are doing this, you will also get a feel for the kinds of edge cases your code
will have to deal with.
5. Write down a high-level description of the algorithm you will use.
6. Determine the complexity of your algorithm idea, ensuring it meets the requirements.
2 Implementing
1. Think of test cases that you can use to check if your algorithm works.
• Use the edge cases you found during the previous phase to inspire your test cases.
• It is also a good idea to generate large random test cases.
• Sharing test cases is allowed, as it is not helping solve the assignment.
2. Code up your algorithm (remember decomposition and comments), and test it on the
tests you have thought of.
3. Try to break your code. Think of what kinds of inputs you could be presented with which
your code might not be able to handle.
• Large inputs
• Small inputs
• Inputs with strange properties
• What if everything is the same?
• What if everything is different?
• etc...
Before submission
• Make sure that the input/output format of your code matches the specification.
• Make sure your filenames match the specification.
• Make sure your functions are named correctly and take the correct inputs.
• Remove print statements and test code from the file you are going to submit.
3 Documentation
For this assignment (and all assignments in this unit) you are required to document and com-
ment your code appropriately. Whilst part of the marks of each question are for documentation,
there is a baseline level of documentation you must have in order for your code to receive marks.
In other words:
Insufficient documentation might result in you getting 0 for the entire question for which it is
insufficient.
This documentation/commenting must consist of (but is not limited to):
● For each function, high-level description of that function. This should be a two or three
sentence explanation of what this function does.
• Your main function in the assignment should contain a generalised description of the
approach your solution uses to solve the assignment task.
• For each function, specify what the input to the function is, and what output the function
produces or returns (if appropriate).
• For each function, the appropriate Big-O or Big- time and space complexity of that
function, in terms of the input size. Make sure you specify what the variables involved
in your complexity refer to. Remember that the complexity of a function includes the
complexity of any function calls it makes.
● Within functions, comments where appropriate. Generally speaking, you would comment
complicated lines of code (which you should try to minimise) or a large block of code
which performs a clear and distinct task (often blocks like this are good candidates to be
their own functions!).
A suggested function documentation layout would be as follows:
def my_function(argv1, argv2):
|| || ||
Function description:
Approach description (if main function):
: Input:
argv1:
argv2:
Output, return or postcondition:
: Time complexity:
: Time complexity analysis:
:Space complexity:
:Space complexity analysis:
||||||
# Write your codes here.
There is a documentation guide available on Moodle in the Assignment section, which contains
a demonstration of how to document code to the level required in the unit.
4 1
Open reading frames
(10 marks, including 2 marks for documentation)
In Molecular Genetics, there is a notion of an Open Reading Frame (ORF). An ORF is a
portion of DNA that is used as the blueprint for a protein. All ORFs start with a particular
sequence, and end with a particular sequence.
In this task, we wish to find all sections of a genome which start with a given sequence of
characters, and end with a (possibly) different given sequence of characters.
To solve this problem, you will need to create a class OrfFinder. The constructor for this class
takes a string genome as a parameter. Additionally, this class will need a method find (start,
end).
1.1 Input
genome is a single non-empty string consisting only of uppercase [A-D]. genome is passed as an
arguement to the __init__ method of OrfFinder (i.e. it gets used when creating an instance
of the class).
start and end are each a single non-empty string consisting of only uppercase [A-D].
1.2 Output
find returns a list of strings. This list contains all the substrings of genome which have start
as a prefix and end as a suffix. There is no particular requirement for the order of these strings.
start and end must not overlap in the substring (see the last two cases of the example below).
1.3 Example
genome1 = Orf Finder ("AAABBBCCC")
genome1.find("AAA", "BB")
>>> ["AAABB", "AAABBB"]
genome1.find("BB","A")
>>> []
genome1.find("AA", "BC")
>>>["AABBBC", "AAABBBC"]
genome1.find("A","B")
>>> ["AAAB", "AAABB", "AAABBB", "AAB", "AABB", "AABBB","AB", "ABB", "ABBB"]
genome1.find("AA","A")
>>> ["AAA"]
#note that "AA" is not valid, since start and end would need to overlap
genome1.find("AAAB", "BBB")
>>> []
#23 note that "AAABBB" is not valid, since start and end would need to overlap
5
