DSA- Assignment 3 Solved

Data Structures & Algorithms for Problem Solving

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.

Given a string S print its minimum lexicographic rotation. O(nlogn)
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)
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” 

All possible rotation are “dcabca” , “cabcad” , “abcadc” , “bcadca” , “cadcab” , “adcabc”.
Among all lexicographically minimum is “abcadc” .

If K=2 than since “ca” is a substring that appears twice and its length is 2, so the answer is 2
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.
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

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:

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 : 

Time and Space Complexity of the algorithm
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: