More on Imperative Programming with Loops
-
Given a randomly ordered array of $n$ elements partition the elements into two subsets such that elements less than $x$ are in one subset and elements greater than $x$ are in separate subset. For instance, $|28|26|25|11|16|12|24|29|6|10|$ and $x = 17$ lead to the array $|10|6|12|11|16|25|24|29|26|28|$. We provide here a high level algorithmic description of the problem.
- Establish the array $a[0,…,n]$ and the partitioning value $x$.
- Move the partitions towards each other until the wrongly placed elements are encountered. Allow for special cases such as $x$ being outside the range of array values.
- While the two partitions have not crossed over
- exchange the wrongly partitioned pair and extend both partitions inward by one element
- extend left partition while elements less tha or equal to $x$
- extend the right partition while elements are greater than $x$
- Return the partitioning index $p$ in the partitioned array.
-
Give an algorithm to find the $k^{th}$ smallest element in a given randomly ordered array of $n$ elements. Note that one could solve the problem by first sorting the array and subsequently returning the $k^{th}$ element in the array as the solution. However, such sorting is unnecessary and costly. Use the partitioning strategy from Question(2) to develop a solution for this problem. We provide some hints to solving this problem:
- Set $l$ and $u$ to be the bounds of the array
- While $l < u$ do:
- Choose some random $x$ about which to partition the array
- Partition the array in to two partitions $A$ and $B$ marked by indices $i$ and $j$
- Choose a partition to perform further search by using a test: if $j<k$ then $l:=i$, if $i>k$ then $u:=j$
-
Given a array of $n$ distinct integers, find the length of the longest monotone increasing subsequence. Consider an array: $|1|2|9|4|7|3|11|8|14|6|$. In this example the longest increasing subsequence is of $1,2,4,7,11,14$ and is of length 6. Note that in for a monotone increasing subsequence, the numbers are not required to be adjacent in the original array. A general algorithmic description is as follows:
- Establish $a[0,…,n]$ of $n$ elements
- Set the initial condition of the longest subsequence terminating in the first position of the array
- For the remaining $n-1$ positions in the array do:
- if current element is less than the maximum in the longest previous set then locate the position and value of maximum among the predecessors and update the position and length of maximum, if required. Else, update the length, position of maximum and the maximum length so far.
- Return the length of longest monotone increasing sequence.