Reference no: EM133683175
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.
Learning Outcome 1: Identify and use the correct syntax of a common programming language.
Learning Outcome 2: Recall and use typical programming constructs to design and implement simple software solutions.
Learning Outcome 3: Explain the importance of programming style concepts (documentation, mnemonic names, indentation).
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.
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.
Assessment Details
Task 1. Constructing a Cube-Free Word in the Alphabet of Two Symbols.
In this task you are required to develop a Python program that constructs an arbitrarily long (potentially infinite) cube-free word in the alphabet of two symbols, ‘0', ‘1'. I.e., a word that does not contain "cubes" - three consecutive identical sub- words.
Such words (sequences) are called Thue-Morse sequences and have multiple applications ranging from Chess to Group Theory and Differential Geometry.
Construction of the Cube-Free Word: The Thue-Morse sequence is a (potentially) infinite word in the alphabet of two symbols, ‘0' and ‘1', which can be constructed in the following way:
(0) t0 = ‘0'
t1 = ‘0' + ‘1' = ‘01'
t2 = ‘01' + ‘10' = ‘0110'
t3 = ‘0110' + ‘1001' = ‘01101001'
...
(n) tn = tn-1 + tn-1¯, where tn-1¯ 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 therefore ti+1 can be seen as an extension of ti.
This sequence of extensions can be continued indefinitely, thus constructing an infinite word, T, which contains all tis as its prefixes (beginnings):
T = ‘0110100110010110100101100110100110010110011010010...'
T has an important property: it does not contain "cubes", i.e.,
three consecutive identical blocks (sub-words).
Programming Task. 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 in the previous section).
In your program you may define other (auxiliary) functions with arbitrary names, however, the solution function of this task should be named thue_morse(n).
In your report, you are required to submit a brief explanation of your program in plain English. It will be useful in confirming ownership of your work.
Task 2. Constructing a square-free word in the alphabet of three symbols.
In this task you are required to write a function in Python that constructs an arbitrarily 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.
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 occurrence of the symbols ‘1', ‘2', ‘3' in the previous word, ak, with 3- letter words according to the following rules:
if symbol ‘1' is in an odd position in ak, then it is replaced with the word ‘123', if ‘1' is in even position, it is replaced with ‘321'.
if symbol ‘2' is in an odd position in ak, then it is replaced with the word ‘231', if ‘2' is in even position, it is replaced with ‘132'.
if symbol ‘3' is in an odd position in ak, then it is replaced with the word ‘312', if ‘3' is in even position, it is replaced with ‘213'.
Here's the table repeating the replacement rules in a tabular format:
Symbols in odd positions Replacement string for odd positions Symbols in even positions Replacement string for even positions
1 123 1 321
2 231 2 132
3 312 3 213
Please note, that in this description the first symbol is considered to be in position 1. Therefore, you will need to make the necessary adjustments when using Python strings since they are zero-based.
Below, you can see first few steps of the construction process:
a0 = ‘1'
a1 = ‘123'
a2 = ‘123132312'
a3 = ‘123132312321312132312321231'
...
A = ‘1231323123213121323123212312132313213123212313213121323...'
The Programming Tasks.
You are required to write a Python function named square_free(n), that takes a positive integer parameter n and returns the string an (defined in the previous section).
Again, as in Task 1, you may define other (auxiliary) functions with arbitrary names, however, the solution function of this task should be named square_free(n).
In your report, you are required to submit a brief explanation of your program in plain English. It will be useful in confirming ownership of your work.
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:
123 132 312 321 312 132 312 321 231
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 returns the number of "squares" in s, i.e., the number of occurrences 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'.
In your report, you are required to submit a brief explanation of your program in plain English. It will be useful in confirming ownership of your work.
*Task 4: Scalability Analysis.
Evaluate the scalability of your implementations for Task 1, Task 2, and Task 3 by testing them with increasingly larger input sizes. Measure their performance metrics based on execution time and memory usage. You may need to conduct research to identify appropriate commands or tools for this purpose.
In your report, present a detailed analysis of each Tasks complexity, including any trade-offs between time and space efficiency.
Propose recommendations for improving the scalability and performance of the implementations.
Note: Need only task 4.