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 ).

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. 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. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of