FIT3155 S2/2021: Assignment 3 (Due midnight 11:55pm on FRIDAY 22 Oct 2021) [Weight: 10 = 2.5 + 2.5 + 5 marks.] Your assignment will be marked on the performance/efficiency of your program. You must write all the code yourself, and should not use any external library routines (that conflict with the core components being assessed. Standard data structures (such as dictionary, list, etc.) are allowed, but you will have to consider their efficiency in places of use. Also, use of bitarray is permitted for this assignment. Follow these procedures while submitting this assignment: The assignment should be submitted online via moodle strictly as follows: ˆ All your scripts MUST contain your name and student ID. ˆ Use gzip or Winzip to bundle your work into an archive which uses your student ID as the filename. (STRICTLY AVOID UPLOADING .rar ARCHIVES!) – Your archive should extract to a directory which is your student ID. – This directory should contain a subdirectory for each of the three questions, named as: q1/, q2/ and q3/. – Your corresponding scripts and work should be tucked within those subdirectories. ˆ Submit your zipped file electronically via Moodle. Academic integrity, plagiarism and collusion Monash University is committed to upholding high standards of honesty and academic integrity. As a Monash student your responsibilities include developing the knowl- edge and skills to avoid plagiarism and collusion. Read carefully the material available at https://www.monash.edu/students/academic/policies/academic-integrity to understand your responsibilities. As per FIT policy, all submissions will be scanned via MOSS. Assignment Questions 1. Towards a string-based proof of an observation you have learnt in this unit: In this question you will implement something really straightforward. Although the exercise itself is easy, the result your program will produce will inform a proof for an observation we made in one of the weeks in this unit. (Feel assured that you will be assessed only for Prepared by: Arun Konagurthu, Monash University your implementation and output. Yet it is encouraged that you reason and analyse the observed behaviour of your output.) Your program takes two inputs: (i) the size of a (small) alphabet, say |A|. ˆ For practicality during testing, restrict |A| within the range [1, 5]. ˆ Also, assume the characters in the alphabet start from ‘a’ onwards. That is, if |A| = 3, assume the alphabet A is: {‘a’,‘b’,‘c’}. (ii) the length of the string, say N . ˆ For practicality during testing, restrict N within the range [1, 10]. Using the two input parameters, |A| and N , write a program to: ˆ generate all possible strings of length N from the alphabet A, and ˆ for each string, report the number of distinct cyclic rotations that are possible for that string. (Refer to Week 1 tute sheet, questions 4 and 5, for the definition of a cyclic rotation.) Note: Although the inputs (|A| and N) are restricted within a range for testing, your implementation however must be generalizable to any values (≥ 1) of those parameters. Strictly follow the following specification to address this question: Program name: stringtest.py Arguments to your program: Two integers: (i) alphabet size (during testing, restrict to the range [1, 5]) (ii) string length (during testing, restrict to the range [1, 10]). Command line usage of your script: stringtest.py

Output to the terminal the following statistics (in a single line, space separated)