Assignment Detail:- ITECH1400 Fundamentals of Programming - Federation University
ASSIGNMENT 1 - THUE-MORSE SEQUENCES
OverviewIn 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-
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--
Learning Outcome 4: Utilise pseudocode and/or algorithms as a major program design technique-Learning Outcome 5: Write and implement a solution algorithm using basic programming constructs-Learning Outcome 6: Describe program functionality based on analysis of given program code-
Learning Outcome 7: Develop self-reliance and judgement in adapting algorithms to diverse contexts-Learning Outcome 8: Design and write program solutions to identified problems using accepted design constructs-
ASSESSMENT DETAILS
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' = ‘01101001'---
-n- tn = tn-1 + -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 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 = ‘0110100110010110100101100110100110010110011010010---'
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-
Part 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--
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--
Part 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 builds 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 Part 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'-
-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'-
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
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 = ‘123132312'a3 = ‘123132312321312132312321231'---A = ‘1231323123213121323123212312132313213123212313213121323---'
The Programming Parts-
-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 above--
Again, as in Part 1, you may define other -auxiliary- functions with arbitrary names, however, the solution function of this task should be named square_free-n--
-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:
Part 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'-
Attachment:- Fundamentals of Programming-rar
Most Recent Questions