Description
P1 : Polynomial Addition
Build a class to represent “sparse” polynomials (think about it!) and use it to add two polynomials. You are expected to build the necessary member functions too.
Input :
No. of terms in polynomial 1 having non-zero coefficients : n1
Space separated coefficients of polynomial 1
Space separated powers having the corresponding coefficients of polynomial 1
No. of terms in polynomial 2 : n2
Space separated coefficients of polynomial 2
Space separated powers having the corresponding coefficients of polynomial 2
Output:
Space separated coefficients of the multiplied polynomial
Space separated powers having the corresponding coefficients of the multiplied polynomial
Constraints:
nnIntegral Coefficients < 1012 < 10 <10 3 3 6
Examples:
Worked out example :
Input:
A[] = {5, 0, 10, 6} B[] = {1, 0, 0, 0, 4} Output:
add[] = {6,0,10,6,4}
The first input array represents => 5 + 10x4 2 + 6x3
The second array represents => 1 + 4x
And Output is => 6 + 10×2 + 6x3 + 4x4
| Input | Output |
| 3
5 10 6 0 2 3 2 1 4 0 4 |
6 10 6 4
0 2 3 4 |
File to be submitted : p1.cpp
P2: Merge Sort and Quick sort
Having learned the problem of sorting in the context of the divide and conquer paradigm, you have to implement the Merge Sort and Quick sort algorithm to sort arrays in files p2-ms.cpp and p2-qs.cpp respectively.
Input Format:
The first line contains a single integer n, the length of the array. The next line contains n integers.
Output:
Sorted array space separated
Examples:
| Input | Output |
| 6
3 4 2 1 5 6 |
1 2 3 4 5 6 |
| 6
3 3 4 1 5 7 |
1 3 3 4 5 7 |
File to be submitted : p2-ms.cpp and p2-qs.cpp
P3: Longest Prefix Common in a list of strings
Given a list/array of strings, find the longest common prefix among the list of strings. You need to assume case sensitivity, i.e. ‘L’ != ‘l’.
Expected complexity: O( n*log(n) ), where n is the size of the list/array.
Input:
The first line contains a single integer n, the length of the list.
Next n lines : ‘ s ’, s.t. | s | < 100
Output :
Longest common prefix, or -1 in case there are no common prefixes
Constraints : n < 105 |s| < 100
Examples :
| Input | Output |
| 3 hello hell holy | h |
| 2 great big | -1 |
| 4
Man Mango Mankind Mandatory |
Man |
| 2 Bat bat | -1 |
File to be submitted : p3.cpp
P4: Playing with array search
Consider that you are communicating with a backend server using an http connection. The backend server has an array of Strings, ‘arr’ of length N. Each element of the array is a lowercase string s such that |s| <= 20, i.e. length of the string is <= 20. This array is sorted according to the lexicographical order i.e. dictionary order. ( Read about it if you are not aware: Lexicographical Order Wiki). You are allowed to communicate with the backend in a very simple way : You send an index i s.t. (i < N), and the backend returns the string at index i, i.e. arr[i]. This communication or ‘access’ takes a certain time due to the network delays.
You have to search a given string in the array, i.e. output the index of the string in the array else -1 if it is not present. Assume 0-based indexing.
There are two types of accesses —
- Good Access : An access of index i, i.e. arr[i] is a good access if arr[i] < given string.
- Bad Access : An access of index i, i.e. arr[i] is a bad access if arr[i] >= given string. Here s1 < s 2 if s 1 occurs lexicographically before s 2 (If s 1 is a prefix of s 2 , then s 1 < s 2)
It turns out that the backend code written has some bugs in it due to which it can handle only at most k bad accesses. At the (k+1)th bad access the backend code will crash and you should have known your answer by then. i.e. at max you can do (k+1) bad accesses. You are to minimize the number of good accesses (thereby time) done by your search algorithm while keeping the bad accesses at max k+1. Keep in mind that this minimization is to take into account the different possibilities of the given strings positions in the array. i.e. it should not be the case that your algorithm works for certain cases really well and for certain cases it performs very poorly.
- For k = 0 : the answer is a simple linear search starting from the start of the array. If you encounter the given string a, output the index else keep on moving till you encounter the first element st. s > a, in which case it is a bad query and hence the backend will crash. At this point you know the answer that the given string is not present in the array. And hence you can output -1. This is the best guarantee we can give, hence the number of accesses would be O(n).
- For k >= log(N) + 1 : The answer is a O( log(N) ). This can be done using a binary search algorithm.
The task of this assignment is to do the search for k = 1, i.e. only one bad access allowed by the backend server.
Coding it up :
For the purpose of the assignment you have to model the backend server as an array and maintain a counter of the number of accesses that you are doing of an array. Thus, counter * Delay would model the actual delay of your algorithm. Essentially every single time you access an element, i.e. write arr[i] in your code you need to increment the counter by 1. Also you need to ensure that the number of bad queries in your algorithm is <= k + 1.
Input Format:
N : number of elements in the array
Next N lines : elements of the array, strings of size <= 20. Last line : given string to search, str
Output Format:
1st line contains the answer : index i of given search string, -1 is not present. Next line contains the number of good accesses made by your algorithm.
