Guide to Project for Supervisors
Page 1 of 6 CRICOS Provider No. 00103D
ITECH1400 Fundamentals of Programming
ASSIGNMENT 1 – THUE-MORSE SEQUENCES
Overview
In this assignment you will have the opportunity to test your
Python skills in generating and manipulating text. Throughout
the assignment you are expected to apply the principles of
problem solving that we have already discussed in this course.
Timelines and Expectations
Percentage Value of Task: 20%
Due: Fri, May 6,2022 17:00 (Week 7)
Minimum time expectation: 20 hours
Learning Outcomes Assessed
The following course learning outcomes are assessed by
completing this assessment:
Knowledge:
K1. Identify and use the co
ect syntax of a common programming
language.
K2. Recall and use typical programming constructs to design and
implement simple software solutions.
K4. Explain the importance of programming style concepts
(documentation, mnemonic names, indentation).
Skills:
S1. Utilise pseudocode and/or algorithms as a major program
design technique.
S2. Write and implement a solution algorithm using basic
programming constructs.
S4. Describe program functionality based on analysis of given
program code.
Application of knowledge and skills:
A1. Develop self-reliance and judgement in adapting algorithms
to diverse contexts.
A2. Design and write program solutions to identified problems
using accepted design constructs.
Page 2 of 6 CRICOS Provider No. 00103D
ASSESSMENT DETAILS
0.Introduction. The Thue–Morse sequence is an infinite word in
the alphabet of two symbols, ‘0’ and ‘1’, which can be
constructed in the following way:
(0) t0 = ‘0’
(1) t1 = ‘0’ + ‘1’ = ‘01’
(2) t2 = ‘01’ + ‘10’ = ‘0110’
(3) t3 = ‘0110’ + ‘1001’ = ‘ XXXXXXXXXX’
...
(n) tn = tn-1 + ????−??������ , where ????−??������ denotes the ‘inverse’ of tn-1,
i.e. all ‘0’s in tn-1 are replaced by ‘1’s and vice versa.
...
It is easy to see that each ti is the first half of ti+1, and ti+1
can be seen as an extension of ti.
This sequence of extensions can be performed infinitely many
times, thus building an infinite word, T, which contains all tis
as its prefixes (beginnings):
T = ‘01101001100101101001011001101 XXXXXXXXXX...’
T has an important property: it does not contain “cubes”, i.e.
three consecutive identical blocks (sub-words).
Thue–Morse sequence has multiple applications ranging from Chess
to Group Theory and Differential Geometry.
Task 1. Building Thue-Morse sequence. In this task you are
equired to write a Python function named
thue_morse(n),
that takes a positive integer parameter, n, and returns the
string tn (defined above).
In your program you may define other (auxiliary) functions with
a
itrary names, however, the solution function of this task
should be named thue_morse(n).
[5 marks]
Page 3 of 6 CRICOS Provider No. 00103D
Task 2. Building a square-free word in the alphabet of three
symbols.
In this task you are required to write a function in Python that
uilds an a
itrarily long (potentially infinite) square-free
word in the alphabet of three symbols, ‘1’, ‘2’, ‘3’. I.e. a
word that does not contain “squares” – two consecutive identical
sub-words.
Although, this can be done by using the Thue-Morse sequence, in
this task we will use another construction, suggested by S.
Arshon.
2.1. Construction of the Square-Free Word: Again, as in Task 1,
we will build a sequence of finite words, ai, that can be
extended to an infinite word.
We start with a0 = ‘1’.
Each next word, ak+1, is constructed by replacing each occu
ence
of the symbols ‘1’, ‘2’, ‘3’ in the previous word, ak, with 3-
letter words according to the following rules:
(1) if symbol ‘1’ is in an odd position in ak, then it is
eplaced with the word ‘123’, if ‘1’ is in even position, it is
eplaced with ‘321’.
(2) if symbol ‘2’ is in an odd position in ak, then it is
eplaced with the word ‘231’, if ‘2’ is in even position, it is
eplaced with ‘132’.
(3) if symbol ‘3’ is in an odd position in ak, then it is
eplaced with the word ‘312’, if ‘3’ is in even position, it is
eplaced with ‘213’.
Here’s the table repeating the replacement rules in a tabular
format:
Please note, that in this description the first symbol is
considered to be in position 1. Therefore, you will need to make
Symbols in odd
positions
Replacement string
for odd positions
Symbols in even
positions
Replacement string
for even positions
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
Page 4 of 6 CRICOS Provider No. 00103D
the necessary adjustments when using Python strings, which are
zero-based.
Below you can see the first few steps of the construction
process:
a0 = ‘1’
a1 = ‘123’
a2 = ‘ XXXXXXXXXX’
a3 = ‘1231323 XXXXXXXXXX’
...
A = ‘12313231232131213231232123121323132 XXXXXXXXXX...’
2.2. The Programming Tasks.
(a) You are required to write a Python function named
square_free(n), that takes a positive integer parameter n and
eturns the string an (defined above).
Again, as in Task 1, you may define other (auxiliary) functions
with a
itrary names, however, the solution function of this
task should be named square_free(n).
[9 marks]
(b) Write a Python function named print3Blocks(s) that takes a
string, s, as a parameter and prints it in blocks of 3 symbols
separated by white spaces. For example, print3Blocks(a3) will
print:
XXXXXXXXXX XXXXXXXXXX
[1 mark]
Task 3. Counting the number of squares in a string.
In this task you are required to write a Python function named
count_squares(s) that takes a string, s, as a parameter and
eturns the number of “squares” in s, i.e. the number of
occu
ences of two consecutive identical sub-words in s.
For example, count_squares (‘1231233’) should return 2 as there
are two “squares” in its argument: ‘1231233’ and ‘1231233’.
[5 marks]
Page 5 of 6 CRICOS Provider No. 00103D
Allocated Marks: See Course Description
Due Date: See Course Description
Please refer to the Course Description for information
elating to late assignments and special consideration.
Assignment Submission
You must supply your program source code files and your
documentation as a single zip file named as follows:
YOUR-NAME>_
.zip,
e.g. John_SMITH_ XXXXXXXXXX
Your documentation should be in PDF format.
Assignments will be marked on the basis of fulfilment of the
equirements and the quality of the work.
In addition to the marking criteria, marks may be
deducted for failure to comply with the assignment
equirements, including (but not limited to):
• Incomplete implementation(s), and
• Incomplete submissions (e.g. missing files), and
• Poor spelling and grammar.
You might be asked to demonstrate and explain your work.
Submit your assignment (all program source files plus your pdf
document to the Assignment 1 Upload location on Moodle before
the deadline of Friday of week 7 at 5 pm.
Page 6 of 6 CRICOS Provider No. 00103D
Marking Criteria/Ru
ic
Student ID: ___________ Student Name: _____________
Tasks Weight Awarded
Marks deducted for badly commented or
adly written code (-4)
Task 1. thue_morse function
• Algorithm in pseudo-code
• Python code
• Demonstration that code works
co
ectly using representative
samples
1
3
1
Task 2. square_free function
• Algorithm in pseudo-code
• Python code
• Demonstration that code works
co
ectly using representative
samples
2
6
1
Task 2. print3Blocks function
• Python code
1
Task 3. count_squares function
• Algorithm in pseudo-code
• Python code
• Demonstration that code works
co
ectly using representative
samples
1
3
1
Total 20+(-4)
Overview
In this assignment you will have the opportunity to test your Python skills in generating and manipulating text. Throughout the assignment you are expected to apply the principles of problem solving that we have already discussed in this course.
Timelines and Expectations
Learning Outcomes Assessed
Assessment Details
Thue–Morse sequence has multiple applications ranging from Chess to Group Theory and Differential Geometry.
Task 1. Building Thue-Morse sequence. In this task you are required to write a Python function named
thue_morse(n),
that takes a positive integer parameter, n, and returns the string tn (defined above).
Assignment Submission
Marking Criteria/Ru
ic