Description

Assignment 3
IMPORTANT POINTS 1. Languages Allowed : C/C++
2. Submission Format: Copy all the codes in a folder with name as your roll no. and submit the zip file in moodle. Ex: 2019201001_A3.zip
PROBLEM 1: Implementation of suffix array
AIM: Implement a Suffix Array that is capable of performing following operations on Strings in a most efficient way.
1. Given a string S print its minimum lexicographic rotation. O(nlogn)
2. Given an integer K, print the length of the longest substring that appears in the text at least K times.If no such substring exist, print -1. O(nlogn)
3. Given a strings S determine its longest substring that is also a palindrome. In the case of multiple solutions, print the lexicographically smallest palindrome. O(nlogn)
EXAMPLE:
Input String: S = “dcabca”
1. All possible rotation are “dcabca” , “cabcad” , “abcadc” , “bcadca” , “cadcab” , “adcabc”.
Among all lexicographically minimum is “abcadc” .
2. If K=2 than since “ca” is a substring that appears twice and its length is 2, so the answer is 2
3. Since only length 1 substring are palindromic, and among them “a” is lexicographically smallest, hence answer is “a”.
INPUT FORMAT: You will be given a large string S (length <= 10 ^5 ). Print the corresponding output for each case Q1a, Q1b and Q1c.
Constraints:
• 1 <= String length <= 10^5
• String consist of either Lower/Upper Case Alphabet and Numeric digits.
Submission Format: For each subpart implement a different code. Submit it as rollnumber_Q1a.cpp, rollnumber_Q1b.cpp, rollnumber_Q1c.cpp. We will run each file separately.
PROBLEM 2: Trie Implementation
AIM: Given an array A of N numbers, you will be given q queries. Each query will contain a single integer x. You have to find then maximum xor of x from any number in A.
Constraints:
• 1 <= N, q <= 10 ^ 5
• 1 <= A[i] <= 10 ^ 12
INPUT:
First Line contains N and q
Second line contains N space separated intergers. Next q lines contain q queries of single integer
Example:
3 2
1 2 3
4
5
A = {1, 2, 3}
Case 1: x = 4 Maximum xor of x is with 3, therefore answer is 4 xor 3 = 7
Case 2: x = 5 Maximum xor of x is with 2, therefore answer is 5 xor 2 = 7
Submission Format: Submit it as rollnumber_Q2.cpp
PROBLEM 3: External Sorting
AIM: External Sorting is a class of algorithms used to deal with massive amounts of data that do not fit in memory.
The question aims at implementing one such type: K-Way merge sort algorithm to sort a very large array. This algorithm is a perfect example of the use of divide and conquer where with limited resources large problems are tackled by breaking the problem space into small computable subspaces and then operations are done on them.
Input Constraints:
1. A file containing a large unsorted list of integers (Will not fit in your usual Laptop
RAM).
2.Do not use any in-built data structures.
Output: A file containing non-Descending sorted list of the given integers
Evaluation parameters :
1. Time and Space Complexity of the algorithm
2. Efficient use of Data-Structures
Input Format: Your code should take two arguments.
• First is the name of input file.
• Second is name of output file.
• Example Format: If your input file is at ./data/input.txt And if you need your output file at ./data/ named output.txt
For c++, code should be of format rollnumber_Q3.cpp compiled file should accept two arguments ./a.out “./data/input.txt” “./data/output.txt”
Generation of unsorted file:
To generate the unsorted file, python script is uploaded along with this pdf. It contains all the instructions required to run it.
Submission format: Submit it as rollnumber_Q3.cpp