given a le of records and a query which consists of two parameters, id_prefix and last_name_prefix to nd the indices of all records .

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Task 1: Querying a database

Input

Input is a text le, named database.txt, containing N records: record index, identi cation number, rst name, last name, phone number, and email address.  In the input le, every line is an entry that represents the details of one person only. No two lines are identical, though some fields may be the same (e.g. same rst name). The indices start at 0 and increase by 1 each line, so they are unique. The identification numbers are also unique. Moreover, each piece of information about a person is space-separated. Below is the example of the part of the large text database database.txt

 

0 20876514	David Williams 0398764532 davwil@gmail.com
1 20876515	David Miller 0423567854 david1967@yahoo.com
2 20876526	Jonathan Squire 0399762314 jonie0107@bigpond.com.au
3 20876538	Zhongxian Shao 0459763457 shao1984@gmail.com
4 20876517	Davis Williamson 0496774832 dav67@gmail.com

 

Format of each line in the input:

In the input le, record indices, identi cation numbers, and phone numbers are only an integer. Identi cation numbers can have different lengths. The first name and last name contains only English alphabets in both cases. Email address is the combination of alpha-numeric values with 4 special characters: at(@), dot(.), hyphen(-), and underscore(_).

As mentioned earlier, each line contains only one person's information, therefore, the number of lines in the input le is N . The maximum length of a single record is M characters, so the size of the input le database.txt will be O(N M ).

 

Functionality

In this task you will solve the following problem: given a le of records and a query which consists of two parameters, id_prefix and last_name_prefix to nd the indices of all records which have an identi cation number (id) whose pre x is id_prefix and a last name whose pre x is last_name_prefix.

To solve this problem, write a function query(filename, id_prefix, last_name_prefix). This function nds all records whose identi cation numbers start with id_prefix and whose last names start with last_name_prefix and returns a list of their indices (which are given in the rst column of the input le). This list can be empty. This list does not have to be sorted, it can be in any order.

 

 

Complexity requirement

In order to do this efficiently,  you will rst construct appropriate TRIEs inside this function.   The construction of these tries should take, in total, O(T ) times where T is the number of characters in all identi cation numbers and  all last names ((note that it does not include the  time complexity needed to read the input le in O(N M )).  The space complexity should be O(T + NM ). The queries should take O(k + l + n_k + n_l) times, where k is the length of id_prefix, l is the length of last_name_prefix, n_k is the number of records matching the id_prefix and n_l the number of records matching the last_name_prefix.

 

Task 2: Reverse substrings search

In this task, you will be given a long string of text.  You need to all substrings of length >  1 whose reverse also exists in the text (not necessarily at the same position).

 

For example, if the original text is cabcdbadccc then the output should be [[ ab ,1], [ ba ,5], [ cd ,3], [ dc ,7], [ ccc ,8], [ cc ,8], [ cc ,9]]. Notice that "Palindromic" substrings are a special case (eg ccc ), where the string and its reverse exist at the same position.

You need to write a function reverseSubstrings(filename) which takes as input a le- name where the le contains a single line containing only lowercase a-z characters. The function returns a lists of lists, where each inner list will contain two values. The rst value will be a substring with length >1 whose reverse exists in the string, and the second value will be the index of that substring in the input text. There is no order requirement for the output list, as long as it contains all the correct values.

 

Complexity requirement:

The function should run in O(K² + P ), where K is the total number of characters in the input string and P is the total length of all substrings whose reverse appears in the string. The space complexity should be O(K² + P ).

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. Develop a program to emulate a purchase transaction at a retail store. This  program will have two classes, a LineItem class and a Transaction class

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme