Scribd
Upload
145 views4 pages

Python Assignment: Array & String Problems

The document describes a 3 question assignment involving: 1. Finding the minimum element in a rotated sorted array. 2. Calculating the minimum number of edits to convert one string to another using a replace operation with a cost of 1. 3. Writing pseudo-code to explain an approach for grouping boxes in an image by label and proximity, and returning the coordinates of the new grouped boxes.

Uploaded by

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

Python Assignment: Array & String Problems

The document describes a 3 question assignment involving: 1. Finding the minimum element in a rotated sorted array. 2. Calculating the minimum number of edits to convert one string to another using a replace operation with a cost of 1. 3. Writing pseudo-code to explain an approach for grouping boxes in an image by label and proximity, and returning the coordinates of the new grouped boxes.

Uploaded by

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

Assignment contain 3 Question

1. All Questions compulsory


2. Python programming language
3. Time duration 4-5 Hours

Q1.A sorted array is rotated at some unknown point, find the minimum element in
it.
Following solution assumes that all elements are distinct.
Examples:

Input: {5, 6, 1, 2, 3, 4}
Output: 1

Input: {1, 2, 3, 4}
Output: 1

Input: {2, 1}
Output: 1
[Link] two strings str1 and str2 and below operations that can
performed on str1. Find minimum number of edits (operations) required to
convert ‘str1′ into ‘str2′.
Operation :- replace

** replacement cost =1

Examples:

Input :

Str1= Quantom
Str2= Quantum

Output:
1
As Quantom can be changed to Quantum by replacing o with u
Examples 2:

Input :

Str1= Week Experience


Str2= Work Experience

Output:
2
As ee can be replace by or in 2 operation
Q3 .

Write a sudo code To explain your approach

Given: An Image with rectangular Boxes and labels associated to those Boxes. Index of every Box
and its Coordinates.

Problem Statement: Group together Boxes by labels and Neighboring Criteria and return the
Coordinates of the New Boxes formed.

Input: Index, Label and Coordinate of the Box(x0,y0,x1,y1) where (x0,y0) represents top-left corner
and (x1,y1) represents bottom-right corner of box with origin at top-left corner of image

Neighboring Criteria: Make a new Box that is 0.5 units away from the boundary of a selected original
box for all the sides. Now if the original boxes intersect with this new box, we consider them as
neighbors.
If label of the Neighbor Boxes matches within the newly formed Box we group them all together and
re-calculate the new Box using the same method that we used in Neighboring Criteria (0.5 units
away from extreme points among all the neighbor boxes).

Output:

Common questions

Powered by AI

The concept involves organizing rectangular boxes on an image based on shared labels and proximity criteria. For each box defined by its coordinates and label, create an expanded boundary that extends 0.5 units outward from each side. If another box intersects with this boundary and shares the same label, consider them neighbors. Group all intersecting, labeled boxes together and calculate the new enclosing box for the group by extending 0.5 units outward from the extreme points of all grouped boxes. The purpose of this process is to effectively merge recognized grouped boxes, facilitating operations like bounding regions of interest in image processing tasks.

The task involves using the edit distance principle to transform one string into another with a minimum number of operations, specifically focusing on replacement operations with a defined cost of 1. The approach is similar to the Levenshtein distance algorithm. Construct a distance matrix where the cell (i, j) represents the minimum number of operations required to convert the first i characters of str1 to the first j characters of str2. Iterate over each character comparison, and if they differ, increment the cost by 1 for the replacement. Otherwise, carry the cost from the previous state. This solution calls for a dynamic programming approach to ensure efficient computation.

To find the minimum element in a sorted and rotated array where all elements are distinct, utilize the binary search approach. Begin by selecting the middle element. If this mid element is greater than the last element of the array, this indicates that the smallest value is in the right half of the array. Otherwise, it resides in the left half. Continue dividing the problem space in half until the smallest element is found, which will be the point of rotation. This algorithm runs in O(log n) time complexity.

You might also like