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 . Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK and US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics and referencing style.
Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.