FIT2004 S2/2019: Assignment 3Nathan CompanezDEADLINE: Friday 11th October 2019 23:55:00 AESTLATE SUBMISSION PENALTY: 10% penalty per day. Submissions more than 7 dayslate are generally not accepted. The number of days late is rounded up, e.g. 5 hours latemeans 1 day late, 27 hours late is 2 days late. For special consideration, please completeand send the in-semester special consideration form with appropriate supporting documentbefore the deadline to [email protected] CRITERIA: It is required that you implement this exercise strictlyusing Python programming language (version should not be earlier than 3.5). Thispractical work will be marked on the time complexity, space complexity and functionalityof your program.Your program will be tested using automated test scripts. It is therefore critically impor-tant that you name your files and functions as specified in this document. If you do not, itwill make your submission difficult to mark, and you will be penalised.SUBMISSION REQUIREMENT: You will submit a zipped file (namedstudentId_A3.zip, e.g. if your student id is XXXX, the name of zipped file must beXXXX_A1.zip). It should contain a single python file, assignment3.py, and a single pdffile, description.pdfPLAGIARISM: The assignments will be checked for plagiarism using an advanced pla-giarism detector. All suspected cases will be investigated. The faculty takes academicintegrity seriously and consequences for such misconduct can include receiving zero marksfor the assignment or unit or suspension or exclusion. Please see the University Policyhttps://www.monash.edu/students/admin/policies/academic-integrity for more details.“Helping” others is NOT ACCEPTED. Please do not share your solutions partially or/andcompletely to others. If someone asks you for help, ask them to visit us during consultationhours for help.1Learning OutcomesThis assignment achieves the Learning Outcomes of:• Analyse general problem-solving strategies and algorithmic paradigms, and apply themto solving new problems• Prove correctness of programs, analyse their space and time complexities• Compare and contrast various abstract data types and use them appropriately• Develop and implement algorithms to solve computational problems.In addition, you will develop the following employability skills:• Text comprehension• Designing test cases• Ability to follow specifications preciselyWarningFor all assignments in this unit, you cannot use python dictionaries or sets. For all assignmentsin this unit, please ensure that you carefully check the complexity of each python function thatyou use. Common examples which cause students to lose marks are list slicing, inserting ordeleting elements in a list, using the in keyword to check for membership of an iterable, orbuilding a string using repeated concatenation of characters. These are just a few examples, sobe careful. Remember, you are responsible for the complexity of every line of code you write!Assignment timelineIn order to be successful in this assessment, the following steps are provided as a suggestion.This is an approach which will be useful to you both in future units, and in industry.Planning1. Read the assignment specification as soon as possible and write out a list of questionsyou have about it.2. Clarify these questions; You can go to a consultation, talk to your tutor, discuss the taskswith friends or ask in the forums.3. As soon as possible, start thinking about the problems in the assignment.• It is strongly recommended that you do not write code until you have a solid feelingfor how the problem works and how you will solve it.4. Writing down small examples and solving them by hand is an excellent tool for comingto a better understanding of the problem.2• As you are doing this, you will also get a feel for the kinds of edge cases your codewill have to deal with.5. Write down a high level description of the algorithm you will use.6. Determine the complexity of your algorithm idea, ensuring it meets the requirements.7. Write your description.pdf.• You should be able to start working on this before you write your code.• If you cannot, perhaps your it is worth thinking a little more about how exactly yourcode will work.Implementing1. Think of test cases that you can use to check if your algorithm works.• Use the edge cases you found during the previous phase to inspire your test cases.• It is also a good idea to generate large random test cases.• Sharing test cases is allowed, as it is not helping solve the assignment.2. Code up your algorithm, (remember decomposition and comments) and test it on thetests you have thought of.3. Try to break your code. Think of what kinds of inputs you could be presented with whichyour code might not be able to handle.• Large inputs• Small inputs• Inputs with strange properties• What if everything is the same?• What if everything is different?• etc…Before submission• Make sure that the input/output format of your code matches the specification.• Make sure your filenames match the specification.• Make sure your functions are named correctly and take the correct inputs.• Make sure you zip your files correctly3StoryAfter winning last week’s games night (due entirely to your help), Nathan was allowed tochoose the game for the following week. Still enraged after his loss in the Song Game, hehas challenged the gaming group to a rematch.This time, armed with more efficient data structures, you will smash the previous com-plexity bounds and allow Nathan to claim his rightful place as the Song Game Master.On your advice, Nathan has also added a second round to the game. You mentionedthat with the new data structures that you have learned, even more complex queries arenow possible. As a result, players will also need to think of the most common word whichstarts with some given prefix.This week’s warm up game is going to be “find the palindrome”, where players are givena long string of characters, and need to find all of the palindromes hidden inside the stringas fast as possible. Whoever finds the most wins!Algorithm Descriptions (2 mark)For each of the three tasks, you must also write a brief description of your algorithm. Thetotal length should be no more than 1200 words.These three descriptions will be submitted in the pdf file description.pdf mentioned in the”Submission Requirement” section. These description should explain the steps your algorithmtakes to solve the problem, and the complexity of each step. Please try to keep these descriptionsat a fairly high level, talk about your data structures and algorithms, not individual variablesor lines of code.41 Radix sort RevengeGiven a file of song lyrics and a file of queries, (identical to the ones from assignment 1), youagain need to find out which songs contain the words in the query file. To do this, you willwrite a function lookup(data_file, query_file).1.1 InputFor this task, we define a word to be a sequence of lowercase English characters (a-z). Aword does not contain any kind of punctuation or other symbols. Song lyrics are a sequenceof words separated by spaces.Each line of data_file will start with a non-negative integer, which is the song ID. Thisnumber is followed by a colon, then the song lyrics on a single line. Since song lyrics can bequite long, each line of the file may also be quite long.query_file contains words, each one on a separate line. Note that these words may not bein sorted order.Example:data_file1234:an example song excellent excellent excellent excellent lyrics222222:a second example song0:a example an example excellent excellent excellent extraordinaryquery_fileexampleanthe1.2 Outputlookup will write output to a file named “song_ids.txt”. This file will contain the samenumber of lines as query_file.If the word on line i of query_file appears in at least one song, then line i of “song_ids.txt”will contain the song IDs (in any order) of songs which contain that word. If the word doesnot appear in any song, then the corresponding output line should be the string “Not found”.Example:”song_ids.txt” fo
r the examples given in 1.1.0 1234 2222220 1234Not foundNote that the song IDs in the first two lines could be in any order.51.3 Complexitylookup must run in O(CI + CQ + CP ), where• CI is the number of characters in data_file• CQ is the number of characters in query_file• CP is the number of characters in song_ids.txt62 Most common lyricIn this task, you will be given a prefix, and you need to determine which word is present in themost songs and begins with that prefix. To do this, you will write a function most_common(data_file,query_file). These files have the same formats as data_file and query_file specified insection 1.12.1 InputThe formats of data_file and query_file are specified in section 1.1.2.2 Outputmost_common will write to a file “most_common_lyrics.txt”. This file will contain the samenumber of lines as query_file. If the string on line i of query_file is the prefix of a word inany song, then line i of “most_common_lyrics.txt” will contain the word whicha) Is present in the most songsb) Has the string on line i of query_file as a prefixIf the string on line i of query_file is not the prefix of any word in any song, then the corre-sponding output line should be the string “Not found”.If two or more words are tied for appearing in the most songs, any of them isacceptable.Note: A word appearing multiple times in one song does not contribute to its frequency.We only care about how many songs a word appears in, not how many times is appears indata_file.Example:Given the example data_file1234:an example song excellent excellent excellent excellent lyrics222222:a second example song0:a example an example excellent excellent excellent extraordinaryand the following query_file:extexa”most_common_lyrics.txt” should containextraordinaryexampleanExplanation:7• The only word in any song which begins with “ext” is extraordinary• “example”, “excellent”, “extraordinary” all begin with “ex”, but “example” appears inall three songs• The last line could also be “a”, since both “a” and “an” appear in two songs2.3 Complexitylookup must run in O(CI + CQ + CM), where• CI is the number of characters in data_file• CQ is the number of characters in query_file• CM is the number of characters in most_common_lyrics.txt83 Palindrome findingIn this task, you are given a string S[0..n-1], and you need to find all palindromic substringsof S, with length at least 2. A palindromic substring is some S[i..j] such that S[j..i] =S[i..j]. To do this, you will write a function palindromic_substrings(S)3.1 InputA string S, containing only lowercase a-z.3.2 OutputA list of tuples, where each tuple represents the start and end index of a palindromic substring.The order of the tuples is not important.Example:Calling palindromic_substrings(“ababcbaxx”) would return[(0,2), (1,3), (3,5), (2, 6), (7,8)], or some permutation of that list.• (0,2) – “aba”• (1,3) – “bab”• (3,5) – “bcb”• (2,6) – “abcba”• (7,8) – “xx”3.3 Complexitypalindromic_substrings must run in O(N2) where N is the length of S.9
