Homework 3 (S2 2022)

This is the third homework assignment. Your goal in this assignment is to write functions that perform a (slightly) more complex calculation and return a value. You will need to use some conditional branching (if statements) and looping.

Practical information#

The assignment is due on Monday the 29th of August, at 9.00am. To submit your solution, upload your python file number_walk.py via Wattle. Here is the assignment submission link.

In addition to submitting your solution, you must attend the following lab (in week 6). In the lab, your tutor will ask you some questions about your solution, and give you feedback if there is anything you need to improve. This discussion with the tutor is also part of the assessment.

If you fail to show up for the discussion with the tutor, you will receive zero marks for this assignment. If you do not submit a solution, you may still get partial marks for the discussion with the tutor.

The homework is individual. You must write your own solution, and you are expected to be able to explain every aspect of it.

As usual, you should have followed last week’s lectures and worked through the exercises in lab 3 before starting on the assignment. The assignment should not take more than one or two hours to complete. The Wattle submission is:

https://wattlecourses.anu.edu.au/mod/assign/view.php?id=2647856

The problem#

Numbers, as you may know (or can learn in this and other programming courses), can have various representations, or formats. The most familiar is the decimal format, in which an integer is represented by a sum of powers of the base 10 with the multipliers which are featured in the representation:

When other base values are used (2, 8, 16…) the corresponding formats are called binary, octal, hexadecimal — they are all used in computer science. Such formats can also be used to represent non-integer numbers, rational and irrational (also known as real or floats), but it usually implies an approximation since the number of symbols which can be used in those formats are finite. For example,

Such base formats are not the only possible. A different way to represent numbers involves a binary tree, which is constructed as follows:

• We start with two fractions \(\frac{0}{1}\) and \(\frac{1}{0}\) (the second fraction should not, for convention, be regarded as actual division to avoid division-by-zero issue, though, symbolically it can be regarded as an infinity, whence the first fraction represents 0)

• Repeat the following insertion operation as many times as necessary to represent an arbitrary positive rational number \(\frac{m}{n}\) (\(m, n\) is a pair of two positive integers):

  • Insert \(\frac{m+m'}{n+n'}\) between two adjacent fractions \(\frac{m}{n}\) and \(\frac{m'}{n'}\)
  • The first application of this rule gives \(\frac{0}{1},\frac{1}{0} \rightarrow \frac{0}{1},\frac{1}{1},\frac{1}{0}\)
  • Then \(\frac{0}{1},\frac{1}{1},\frac{1}{0} \rightarrow \frac{0}{1},\frac{1}{2},\frac{1}{1},\frac{2}{1},\frac{1}{0}\)
  • Then \(\frac{0}{1},\frac{1}{2},\frac{1}{1},\frac{2}{1},\frac{1}{0} \rightarrow \frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1},\frac{3}{2},\frac{2}{1},\frac{3}{1},\frac{1}{0}\)

• When extended as required, the set of fractions (rationals) can be organised into a binary tree:

  

• This tree is ordered in the traditional sense, and any pair of neigbours is used to generate the number between them, as defined above — for example, the number \(\frac{3}{5}\) is generated by its left and right parents, \(\frac{1}{2}\) and \(\frac{2}{3}\) (while the “boundary” number \(\frac{1}{4}\) is generated by \(\frac{0}{1}\) and \(\frac{1}{3}\)).

This tree has properties (which we shall not prove):

• A rational number appears in the tree only once (because of insertion mechanism, all numbers are ordered).

• Every rational number \(\frac{p}{q}\) can always be represented by a unique pair (p,q) if they are mutally prime (gcd(p,q) = 1), for example \(\frac{2}{14}\) and \(\frac{1}{7}\) are the same rational number, while the latest pair (1,7) are mutually prime. One can always use such mutually prime pair for representing a rational number. A rational number has a unique place on the tree. The full path to it from the top can be written as the string containing only two symbols L and R (left and right symbolic turns on the route of descending from the top to the number location), eg:

  \[\frac{2}{3} = LR, \qquad \frac{3}{5} = LRL\]

The algorithm to compute the path to a particular pair of integers (m, n) is rather simple:

1. Begin with a pair of integers (m, n) and let S = '' be the empty string
2. If m < n, set n to be n-m and add L on to the end of S (\(S\hookrightarrow SL\))
3. If m > n, set m to be m-n and add R on to the end of S (\(S\hookrightarrow SR\))
4. If m = n, the process stops and the path S is found
5. Until this happens, repeat step 2 or 3 depending on the condition

It can be proved (it’s easy, but we skip it as well) that this repetition will stop after a finite number of step.

Your first task in this homework, is to write a function which will compute the path towards the number on the binary tree for a rational number given by the pair of (m,n); this function is to be called number_to_string(m, n). Your second task, is to reverse the problem, and compute the pair of positive mutually prime integers (m,n) which is represented on the binary tree by the string-path s, consisting of symbols L and R only.

Assumptions and restrictions:

• You may assume that the arguments to the function number_to_string are two positive integers (hence, the symbolic zero — the left root parent (0,1), and the symbolic infinity — the right root parent (1,0) are excluded).

• you may assume that the argument to the function string_to_number is a string which consists of only characters ‘L’ and ‘R’ (or it is an empty string '').

Testing#

The skeleton file has two testing functions: test_number_to_string() and test_string_to_number(). Each of them runs some tests on the corresponding function, and will raise an error if any of the tests fail. If all tests pass, each testing function prints the message “all tests passed” at the end.

Remember that testing only checks a small number of predefined cases; it can never prove that your function works correctly for all valid arguments. You should examine the test cases that are provided, and think about whether there are any important ones that are missing.

Marking#

Code quality

In this homework (and in the following two) we will also be marking your submission for its code quality. This includes aspects such as:

• Using good function, parameter and variable names. The names of some functions in the homework are fixed, but if you define additional functions (to decompose the problem) then they should be given descriptive names.

• Appropriate use of comments and docstrings.

  This means not too little comments but also not too much. Comments should be accurate, relevant, and readable. Docstrings should be used only as the first statement in a function definition or in a file.

• Good code organisation.

  This includes appropriate use of functions to decompose a problem and avoid code repetition.

What to submit

You should edit the skeleton file number_walk.py that you downloaded, then upload only this file with your solution using the assignment submission link on Wattle.

The file that you submit must meet the following requirements:

• It must be syntatically correct python code.
• Like the file you downloaded, it should contain only function definitions; inline comments and docstrings (if they are used appropriately) are, of course, OK to include. Anything that is not a function definition will be ignored when we check your submission.

As mentioned above, you must also attend the following lab (in week 6) and answer your tutor’s questions about your solution. This discussion is part of the assessment. You should be prepared to answer or demonstrate how to deal with the following questions:

• Can you download the file that you submitted from Wattle?
• Can you run that file in the python interpreter (using an IDE of your choice) on the CSIT lab computer?
• If the file has syntax errors, can you use the error messages from the interpreter or IDE to identify where the syntax errors are?
• Does your submitted file meet the requirements stated above? Does it contain anything that is not a function definition? If so, can you point it out?
• Does your implementation pass all the tests run by the unmodified testing functions?
• Is your implementation of the two functions correct for any valid arguments (non-negative integers)?
• Do your functions always return a value of the correct type?
• Did you think of any other test cases that should be used to test the two functions, in addition to or in place of those provided?
• What is the difference between the print function and the return statement?

In marking this assignment we will consider the following:

• Does your submitted file satisfy the requirements specified above?
• Does your implementation of the two functions number_to_string, and string_to_number compute the correct value for all valid arguments?
• The quality of your submitted python code, including its organisation, naming and documentation (with docstrings and comments).
• Your ability to use the tools (e.g., the IDE or python interpreter), your understanding of python’s error messages, and your understanding of the solution, as demonstrated in your discussion with the tutor.

The assignment is worth 3% of your final mark. 2 marks are based on the functionality of your submission, and 1 mark on the quality and readability of your code.