[go: up one dir, main page]
Scribd
Upload
3 views5 pages

DAA Assignment 2

Uploaded by

harshithasappidi1430
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views5 pages

DAA Assignment 2

Uploaded by

harshithasappidi1430
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

DESIGN AND ANALYSIS OF ALGORITHMS

ASSIGNMENT-02
NAME:S.HARSHITHA
ROLL NO:160122733307
CLASS:CSE 3RD YEAR V-SEM
SECTION:CSE-I
DESIGN AND ANALYSIS OF ALGORITHMS-22CSC14N
ASSIGNMENT-02

LONGEST INCREASING SUB-SEQUENCE[LIS]:


The Longest Increasing Subsequence (LIS) is defined as:
A subsequence of a given sequence where the elements are arranged in strictly increasing
order, and the subsequence is as long as possible.
1. Subsequence: A sequence derived from the original sequence by deleting some or
no elements without changing the order of the remaining elements.
o Example: For A=[10,22,9,33,21] possible sub sequences are [10,22],
[10,33,21] etc.
2. Strictly Increasing: Each element in the subsequence must be greater than the
previous one.
o Example: From A=[10,22,9,33,21], [10,22,33] is increasing.
3. Maximum Length: Among all increasing sub sequences, the LIS has the greatest
length.
Example:
For A=[10,9,2,5,3,7,101,18]:
 The LIS is [2,3,7,101] with a length of 4.
Given a sequence X of n integers, the objective is to find the longest sub-sequence,
Xk1 ,Xk2 ,...,Xkm , such that ki > ki−1 and Xki > Xki−1 . For example, for the following
sequence:
3, 8,2,7,3,9,12,4,1,6,10,
the longest increasing sub-sequence would be: 2, 3,4,6,10.
The idea of the algorithm is to keep an array L where Li represents the length of a LIS with Xi
as its final element. First start Li with 1, then for every j from 0 to i−1, check if Xj < Xi and Lj
+1 >Li, if that happens then make Li = Lj +1. What we are doing here is to check if we can add
the element Xi to the LIS that ends in Xj, if we can, then check if that LIS is longer than the
one we already have ,and keep the longest one. The length of the LIS of the whole sequence
will be the maximum value in L.
For the sequence above, the array L will look like this.
X= 3 8 2 7 3 9 12 4 1 6 10
L= 1 2 1 2 2 3 4 3 1 4 5
The value of Li represents the length of the LIS ending with Xi. Since for every element we
have to go through for all its previous elements. The number of operations is n(n−1)/2. So

NAME:S.HARSHITHA ROLL-NO:160122733307
DESIGN AND ANALYSIS OF ALGORITHMS-22CSC14N
ASSIGNMENT-02

the time complexity for this algorithm is O(n2). To keep track which elements are part of the
LIS, every time that Xj<Xi and Lj+1>Li we say that element j precedes element i. In that way
we only need the last element of the LIS and then move backwards until reach the first
element to obtain the whole sequence.
1. Algorithm Design Approach
The Longest Increasing Subsequence (LIS) problem involves finding the length of the longest
subsequence in an array where the elements are strictly increasing. Below are key steps in
designing the solution:
1. Problem Understanding:
o Given an array A of length n, the task is to find the maximum length of
subsequence SSS such that S[i]<S[i+1]S[i] < S[i+1]S[i]<S[i+1] for all valid iii.
o Subsequence implies we can skip elements but must preserve order.
2. Approach Selection:
The two common approaches are:
o Dynamic Programming (DP): Straightforward but less efficient.
o Binary Search + DP: Optimized solution using a greedy approach.
3. Optimal Design:
o Use Binary Search + DP for O(nlogn) time complexity.
o Maintain a list dp, where each element represents the smallest possible end
value of an increasing subsequence of a particular length.
o Use binary search to find the position where an element fits into dp, replacing
it if necessary, or appending it to extend the subsequence.

2. Algorithm
Input:
An array A of length n.
Output:
The length of the Longest Increasing Subsequence.
Pseudocode:
python
Copy code
def length_of_LIS(A):

NAME:S.HARSHITHA ROLL-NO:160122733307
DESIGN AND ANALYSIS OF ALGORITHMS-22CSC14N
ASSIGNMENT-02

dp = [] # Will store the smallest end element of increasing sub sequences


for num in A:
# Binary search for the position of num in dp
pos = binary_search(dp, num)
if pos == len(dp):
dp.append(num) # Append num if it's greater than all elements in dp
else:
dp[pos] = num # Replace to maintain the smallest possible end element
return len(dp)
def binary_search(dp, target):
left, right = 0, len(dp) - 1
while left <= right:
mid = (left + right) // 2
if dp[mid] < target:
left = mid + 1
else:
right = mid - 1
return left

4. Time Complexity
For an input array A=[10,9,2,5,3,7,101,18]
1. Traversal (O(n)):
o Each element is processed once.
2. Binary Search (O(logk)):
o Element 10: O(1) to add to dp.
o Element 9: O(log 1) = O(1) to replace 10 in dp.
o Element 101: O(log 4) = O(2) to append to dp.
o Overall, this is log-efficient per element.

3. Combined, for n=8, the cost is proportional to 8⋅log8, i.e., approximately 24


operations.This efficiency makes O(nlogn) the preferred choice for larger inputs.

NAME:S.HARSHITHA ROLL-NO:160122733307
DESIGN AND ANALYSIS OF ALGORITHMS-22CSC14N
ASSIGNMENT-02

 Binary Search: Each insertion or replacement in dp is O(logn).


 Loop over Array: Runs n times for all elements in the array.
Total Time Complexity: O(nlogn).

4. Report
The problem is to compute the Longest Increasing Subsequence (LIS) of an array using an
efficient algorithm.
Solution Description:
We use a greedy approach combined with dynamic programming. By maintaining a list dp
that stores the smallest end element of sub sequences, we utilize binary search to efficiently
determine the position of each element.
Implementation:
1. Binary search ensures O(logn) efficiency for updates to dp.
2. The dp array at the end represents an abstraction, not the LIS itself, but its length
gives the correct result.
Strengths of the Approach:
 Efficient with O(nlogn) time complexity.
 Simple to implement and understand with a focus on key operations.
Example:
For A=[10,9,2,5,3,7,101,18]:
1. Initial dp=[].
2. Process each element:
o 10: dp=[10]
o 9: Replace 10, dp=[9]
o 2: Replace 9, dp=[2]
o 5: Append, dp=[2,5]
o 3: Replace 5, dp=[2,3]
o 7: Append, dp=[2,3,7]
o 101: Append, dp=[2,3,7,101]
o 18: Replace:101, dp=[2,3,7,18]
Result: LIS length = 4.

NAME:S.HARSHITHA ROLL-NO:160122733307

You might also like