Question 3: Give an algorithm that finds the maximum size sub-array that is increasing (the entries may not be contiguous. It may be any set but you need to keep the order). In the array, A = [1, 7, 2, 5, 4, 6, 8, 9, 3, 14, 16, 11, 30], the maximum non contiguous increasing subset is 1, 2, 4, 6, 8, 9, 14, 16, 30 that forms an increasing sequence. Please explain the algorithm in words and state the run time.
algorithm by dynamic approach:
1. Create an array lisLength, of length same as input
array length, to store longest increasing subsequence defined
as:
lisLength[i] = length of longest increasing
subsequence in the array [0..i] including ith element
2. Initialize lisLength[i] to 1.
3. The lisLength array is then updated one element by
element:
lisLength[i] = Max(lisLength[j]) + 1, for all values
of j where input[j] < input[i] and j < i
How this works:
For j = 0 to i-1, if input[j] < input[i], then input[i] can be
added to the longest increasing subsequence which is formed from
array elements 0 to j.
Therefore, to find longest increasing subsequence in 0..i,
lisLength[i], we need the Max(lisLength[j]) value which satisfies
this condition.
If there is no such j, then longest increasing subsequence in input
array 0..i, lisLength[i] = 1 which is formed by adding only ith
element.
Example:
lisLength[] : [1, 0, 0, 0, 0, 0, 0, 0]
i = 1: lisLength[1] = 1
j = 0: input[0] = 12 < input[1] = 18,
also lisLength[1] = 1 < lisLength[0] + 1 = 2, so we
update:
lisLength[1] =
lisLength[0] + 1 = 2
lisLength[] : [1, 2, 0, 0, 0, 0, 0, 0]
i = 2: lisLength[2] = 1
j = 0: input[0] = 12 > input[2] =
7
j = 1: input[1] = 18 > input[2] =
7
lisLength[] : [1, 2, 1, 0, 0, 0, 0, 0]
i = 3: lisLength[3] = 1
j = 0: input[0] = 12 < input[3] = 34,
also lisLength[3] = 1 < lisLength[0] + 1 = 2, so we
update:
lisLength[3] =
lisLength[0] + 1 = 2
j = 1: input[1] = 18 < input[3] = 34,
also lisLength[3] = 2 < lisLength[1] + 1 = 3, so we
update:
lisLength[3] =
lisLength[1] + 1 = 3
j = 2: input[2] = 7 <
input[3] = 34, but lisLength[3] = 3 > lisLength[2] + 1 = 2, so
lisLength is not updated.
lisLength[] : [1, 2, 1, 3, 0, 0, 0, 0]
i = 4: lisLength[4] = 1
j = 0: input[0] = 12 < input[4] = 30,
also lisLength[4] = 1 < lisLength[0] + 1 = 2, so we
update:
lisLength[4] =
lisLength[0] + 1 = 2
j = 1: input[1] = 18 < input[4] = 30,
also lisLength[4] = 2 < lisLength[1] + 1 = 3, so we
update:
lisLength[4] =
lisLength[1] + 1 = 3
j = 2: input[2] = 7 <
input[4] = 30, but lisLength[4] = 3 > lisLength[2] + 1 = 2, so
lisLength is not updated.
j = 3: input[3] = 34 > input[4] =
30
lisLength[] : [1, 2, 1, 3, 3, 0, 0, 0]
i = 5: lisLength[5] = 1
j = 0: input[0] = 12 < input[5] = 28,
also lisLength[5] = 1 < lisLength[0] + 1 = 2, so we
update:
lisLength[5] =
lisLength[0] + 1 = 2
j = 1: input[1] = 18 < input[5] = 28,
also lisLength[5] = 2 < lisLength[1] + 1 = 3, so we
update:
lisLength[5] =
lisLength[1] + 1 = 3
j = 2: input[2] = 7 <
input[5] = 28, but lisLength[5] = 3 > lisLength[2] + 1, so
lisLength is not updated.
j = 3: input[3] = 34 > input[5] =
28
j = 4: input[4] = 30 > input[5] =
28
lisLength[] : [1, 2, 1, 3, 3, 3, 0, 0]
i = 6: lisLength[6] = 1
j = 0: input[0] = 12 < input[6] = 90,
also lisLength[6] = 1 < lisLength[0] + 1 = 2, so we
update:
lisLength[6] =
lisLength[0] + 1 = 2
j = 1: input[1] = 18 < input[6] = 90,
also lisLength[6] = 2 < lisLength[1] + 1 = 3, so we
update:
lisLength[6] =
lisLength[1] + 1 = 3
j = 2: input[2] = 7 <
input[6] = 90, but lisLength[6] = 3 > lisLength[2] + 1, so
lisLength is not updated.
j = 3: input[3] = 34 < input[6] = 90,
also lisLength[6] = 3 < lisLength[3] + 1 = 4, so we
update:
lisLength[6] =
lisLength[3] + 1 = 4
j = 4: input[4] = 30 < input[6] = 90,
but lisLength[6] = 4 = lisLength[4] + 1, so lisLength is not
updated.
j = 5: input[5] = 28 < input[6] = 90,
but lisLength[6] = 4 = lisLength[5] + 1, so lisLength is not
updated.
lisLength[] : [1, 2, 1, 3, 3, 3, 4, 0]
i = 7: lisLength[7] = 1
j = 0: input[0] = 12 < input[7] = 88,
also lisLength[7] = 1 < lisLength[0] + 1 = 2, so we
update:
lisLength[7] =
lisLength[0] + 1 = 2
j = 1: input[1] = 18 < input[7] = 88,
also lisLength[7] = 1 < lisLength[1] + 1 = 3, so we
update:
lisLength[7] =
lisLength[1] + 1 = 3
j = 2: input[2] = 7 <
input[7] = 88, but lisLength[7] = 3 > lisLength[2] + 1, so
lisLength is not updated.
j = 3: input[3] = 34 < input[7] = 88,
also lisLength[7] = 3 < lisLength[3] + 1 = 4, so we
update:
lisLength[7] =
lisLength[3] + 1 = 4
j = 4: input[4] = 30 < input[7] = 88,
but lisLength[7] = 4 = lisLength[4] + 1, so lisLength is not
updated.
j = 5: input[5] = 28 < input[7] = 88,
but lisLength[7] = 4 = lisLength[5] + 1, so lisLength is not
updated.
j = 6: input[6] = 90 > input[7] =
88
lisLength[] : [1, 2, 1, 3, 3, 3, 4, 4]
Solution: Maximum value in lisLength array = 4.
Time complexity of this solution is O(n^2).
If have any doubts or need more explanation ..
Ask me..I will respond as soon as possible..
Question 3: Give an algorithm that finds the maximum size sub-array that is increasing (the entries...
Give an algorithm that finds the maximum size subarray that is increas- ing (the entries may not be contiguous. It may be any set but you need to keep the order.). In the above array the maximum non contiguous increasing subset is 1, 2, 4, 6, 8, 9, 14, 16, 30 that forms an increasing sequence. There are no other array provided in this question, thank you
Design And analysis algorithm
course .
Remarks: In all the
algorithms, always explain their correctness and analyze their com-
plexity. The complexity should be as small as possible. A correct
algorithm with large complexity, may not get full credit
Question 2: Give an algorithm that finds the maximum size subarray (the entries may not be contiguous) that forms an increasing sequence.
f a as a sequence of adjacent array elements such that each value in the run array was of size 10 9. We define a "run" of elements o (except for the first) is one greater than the previous and looked like: value. For example, say the 3 2 16 9 7 8 9 2 a: position 0 3 We have three runs in this array: (1) between 9,10,1, 12) and, (3) between positions 7 and 8, (15, 16) positions...
(20 points) You are given an array A of distinct integers of size n. The sequence A[1], A[2], ..., A[n] is unimodal if for some index k between 1 and n the values increase up to position k and then decrease the reminder of the way until position n. (example 1, 4, 5, 7, 9, 10, 13, 14, 8, 6, 4, 3, 2 where the values increase until 14 and then decrease until 1). (a) Propose a recursive algorithm to...
In this project, you will work on the algorithm (discussed in Module 1) to determine the length of the longest sub sequence of consecutive integers in an array You will implement the algorithm using Hash tables. You are provided with sample code (in C++ and Java) representing the linked list-based implementation of Hash tables (as an array of Linked Lists). You could go through the code to understand the implementation of a Hash table and the functions that can be...
Sorting Sort the following array using the quick sort algorithm: (4 Marks) a. 12 26 8 9 7 0 4 Pivot selection is defined to be the first element of each sub-list. Show the array before and after each quicksort round (when the array is partitioned after placing the pivot at its correct position). Also, clearly highlight the pivot in each partition b. Consider an unsorted array of integers of size n. Write a Java program to arrange the array...
Write a C function that implements the Liner Search algorithm instead of Binary Search. However, this linear search algorithm returns the indices of the longest sorted subset of numbers in an array of integers of size n. The longest sorted subset of numbers must satisfy three conditions. First, the subset consists of unique numbers (no duplicate); second, all the numbers in this subset is divisible by m, the minimum size of the subset is two elements. In the main method...
Write a c program that finds the uncommon elements from two array elements using pointers only . For example : Enter the length of the array one : 5 Enter the elements of the array one: 9 8 5 6 3 Enter the length of the array two: 4 Enter the elements of the array two: 6 9 2 1 output: 8 5 3 2 1 void uncommon_ele(int *a, int n1, int *b, int n2, int *c, int*size); The function...
Write a program in C++ language that finds the largest number in an array of positive numbers using recursion. Your program should have a function called array_max that should pass in an int array, and an int for the size of the array, respectively, and should return an int value. As an example, given an array of size 10 with contents: {10, 9, 6, 1, 2, 4, 16, 8, 7, 5} The output should be: The largest number in the...
I need to create a Java program that, given an array of size N whose entries are numbers between 0 and 10^6, finds the largest repeating subarray. Doesn't matter how many times the array is repeated. For example, an array [0 1 2 1 4 1 2 1 0 5] should return 3 for the subarray [1 2 1]. I need this to be quite time efficient. I was recomended Suffix array but no idea how to implement.