ITECH1400 - Fundamentals of Computer Programming

Assignment 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 subwords. Such words (sequences) are called Thue-Morse sequences and have multiple applications ranging from Chess to Group Theory and Differential Geometry.

1.1. 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’

(1) t1 = ‘0’ + ‘1’ = ‘01’

(2) t2 = ‘01’ + ‘10’ = ‘0110’

(3) t3 = ‘0110’ + ‘1001’ = ‘01101001’ .

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) squarefree 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-F0ree 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:

(1) 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’.

(2) 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’. CRICOS Provider No. 00103D Page 4 of 6 (3) 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’.

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 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.

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.

This ITECH1400 - IT Computer Science has been solved by our PhD Experts at My Uni Paper.