Assignment_01.pdf + -> @ File | D:/Monash/2019%20Semester%202/FIT2004%20Algorithms%20&%20Data%20Structure/Assignment1/Assignment_01.pdf Q K Nathan has asked for your help. You have agreed to write an algorithm for him which allows the user to quickly look up songs which contain specific words. A detailed breakdown of what you need to do is given in the tasks below. Algorithm Descriptions (2 mark) For each of the three tasks, you must also write a brief description of your algorithm. The total length should be no more than 800 words. These three descriptions will be submitted in the pdf file descriptions. pdf mentioned in the "Submission Requirement" section. These descriptions should explain the steps your algorithm takes to solve the problem, and the complexity of each step. Please try to keep these descriptions at a fairly high level, talk about your data structures and algorithms, not individual variables or lines of code. 1 Sorting and Collating (12 marks) You start with a file containing lyrics from many songs. This is not in a useful format for quickly looking up individual words, so you will need to preprocess it first. You must write a function process (filename) which takes as input a string of a filename (the format of this file is specified in 1.1). The function will sort the words of all the songs, and output these sorted words to another file. 1.1 Input For this task, we define a word to be a sequence of lowercase English characters (a-z). A word does not contain any kind of punctuation or other symbols. Song lyrics are a sequence of words separated by spaces. Each line of the input file will start with a non-negative integer, which is the song ID. This number is followed by a colon, then the song lyrics on a single line. Since song lyrics can be quite long, each line of the file may also be quite long. Example: 1234: an example song 222222:a second song 0:a example an example Type here to search e 9 W A D () TENG 8:09 AM 15/8/2019 E.Assignment_01.pdf + -> File | D:/Monash/2019%20Semester%202/FIT2004%20Algorithms%20&%20Data%20Structure/Assignment1/Assignment_01.pdf Q K Example: 1234: an example song 222222:a second song 0:a example an example 1.2 Output process will write output to a file named "sorted_words. txt" (which it will create). This file will consist of T lines, where T is the total number of words over all songs in the input file. Each line will start with a word, then a colon, and then the song ID of the song that word belongs to. The order of the lines depends on the words. If the word in line r is lexicograph- ically less than the word in line y, then a will appear before y in sorted_words. txt. If two line have the same word, then the one with lower song ID will appear first. Example: a: 0 a:222222 an : 0 an : 1234 example : 0 example : 0 example : 1234 second : 222222 3 song : 1234 song : 222222 1.3 Complexity process must run in O(TM) time, where . T is the total number of words over all songs in the input file . M is the length of the longest word Type here to search e 9 M W 8 ~ D ( ENG 8:10 AM 15/8/2019 E
