Anyone
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 correct 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’ = ‘01101001’ ... (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 = ‘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. 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). 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). [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 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. 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 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 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 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 = ‘123132312’ a3 = ‘123132312321312132312321231’ ... A = ‘1231323123213121323123212312132313213123212313213121323...’ 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 above). 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). [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: 123 132 312 321 312 132 312 321 231 [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 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’. [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 relating 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:
_.zip, e.g. John_SMITH_30000000 Your documentation should be in PDF format. Assignments will be marked on the basis of fulfilment of the requirements and the quality of the work. In addition to the marking criteria, marks may be deducted for failure to comply with the assignment requirements, 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/Rubric Student ID: ___________ Student Name: _____________ Tasks Weight Awarded Marks deducted for badly commented or badly written code (-4) Task 1. thue_morse function • Algorithm in pseudo-code • Python code • Demonstration that code works correctly using representative samples 1 3 1 Task 2. square_free function • Algorithm in pseudo-code • Python code • Demonstration that code works correctly 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 correctly 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/Rubric