Exercise 6: Searching and Sorting

Prerequisite

You have completed Exercise 5.

Learning Outcomes

Be comfortable studying properties in the input and apply them to efficiently solve problems.

Deadline

This exercise is part of the CS1010 formative assessment. Submit your solution before 30 October 2023, 23:59 to receive feedback and earn your achievement "badges".

Acceptance Link

The link to accept the exercise is not available publicly. Visit Canvas for the link.

Concepts and Difficulty

	Question	Sorting	Searching	Difficulty
1	Sort
2	Valley
3	Inversion
4	Lexicon

Question 1: Sort

A v-array is an array of integers with a special property. The array can be partitioned into two segments: in the first segment, the numbers are sorted in non-ascending order. In the second part, the numbers are sorted in non-descending order. For example, 9 4 2 5 5 8 is a v-array. 9 4 is in non-ascending order, while 2 5 5 8 are in non-descending order. On the other hand, 9 4 5 2 5 8 is not a v-array.

A v-array can be only non-ascending or non-descending. For instance, both 1 2 3, 8 8 8 8, and -2 -5 -10 are all valid v-arrays.

Write a program sort, that reads from standard input:

• a positive integer $n$,
• followed by $n$ numbers that form a v-array.

The program sort then sorts the numbers in the v-array in non-descending order and prints the numbers to the standard output, one number per line.

You must solve this problem with an $O(n)$ algorithm. Solving this in $O(n^2)$ or $O(n\log n)$ is trivial and such solution will be categorized as "Need Improvement"

Sample Runs

ooiwt@pe119:~/ex06-skeleton$ cat inputs/sort.1.in
5
5 4 2 1 3
ooiwt@pe119:~/ex06-skeleton$ ./sort < inputs/sort.1.in
1
2
3
4
5

Question 2: Valley

A strict v-array is a v-array where no two adjacent elements have the same value.

In this problem, we wish to find the minimum value of a strict v-array, known as a valley.

Write a program valley, that reads from standard input:

• a positive integer $n$,
• followed by $n$ numbers that form a strict v-array.

The program valley then prints the valley of the array to the standard output.

You must solve this problem with an $O(\log n)$ algorithm. Solving this in $O(n)$ is trivial, and such solution will be marked as "Need Improvement."

Sample Runs

ooiwt@pe119:~/ex06-skeleton$ cat inputs/valley.1.in
5
5 4 2 1 3
ooiwt@pe119:~/ex06-skeleton$ ./sort < inputs/valley.1.in
1

Question 3: Inversion

In an array that is supposed to be sorted in some order, an inversion is a pair of numbers that is out of order. For instance, if we want to sort the array "1 3 4 2", in increasing order, the pair (3, 2) and (4, 2) are out of order. So there are two inversions in this array.

An array that is sorted has no inversion, while an array of size $n$ that is inversely sort has $n(n-1)/2$ inversions.

The concept of inversion is not new. In the problem kendall, you have counted the number of inversions. In bubble sort, every pass removes some number of inversions until no more inversion is left.

In this question, you are given an array of $n$ integers where the elements are unique, i.e., there is no duplicate in the inputs. Furthermore, the input is the inverse of a v-array. There is some $k$, $0\le k\le n$, where the first $k$ elements in the array are in increasing order, and the remaining $n-k$ elements are in decreasing order.

Write a program inversion that reads, from the standard input, the following:

• An integer $n(n\ge 1)$, followed by
• $n$ integers

You program should then prints, to the standard output, the number of inversions in the input.

You have already solved this problem in kendall in $O(n^2)$ time, so, an $O(n^2)$ solution would be marked as "Need Improvement". An $O(nlogn)$ solution would be "Good", while an $O(n)$ solution would be "Excellent".

Sample Runs

ooiwt@pe119:~/ex06-weitsang$ cat inputs/inversion.1.in
5
1 3 5 4 2
ooiwt@pe119:~/ex06-weitsang$ ./inversion < inputs/inversion.1.in
4
ooiwt@pe119:~/ex06-weitsang$ cat inputs/inversion.2.in
3
1 20 300
ooiwt@pe119:~/ex06-weitsang$ ./inversion < inputs/inversion.2.in
0
ooiwt@pe119:~/ex06-weitsang$ cat inputs/inversion.3.in
1
-100
ooiwt@pe119:~/ex06-weitsang$ ./inversion < inputs/inversion.3.in
0

Question 4: Lexicon

Given a lexicon consisting of words that are made up of a set of symbols, we wish to sort them in increasing lexicographical order. Assume that the order of two symbols is defined, the ordering of two words is defined as follows:

• Given two words $W_1=a_0{a}_1..a_k$ and $W_2=b_0{b}_1..b_k$ of equal length. Let $i$ be the smallest index where the two words differ, i.e., $a_j=b_j$ for $j=0,1,..,i-1$ and $a_i\ne b_i$. Then $W_1<W_2$ if $a_i<b_i$.

• Given two words $W_1=a_0{a}_1..a_l$ and $W_2=b_0{b}_1..b_k$ of different length, with $l<k$, then the ordering pads $W_1$ with a special symbol that is smaller than every other symbols, until both $W_1$ and $W_2$ are of equal length.

For this question, we consider the set of printable ASCII characters, except the white space ' ', as the set of symbols in our lexicon. The ordering of two symbols is defined by the ordering of the ASCII value of the characters. We can thus use the null character `'\0', with an ASCII value of 0, as the padding symbols.

For instance, the word ooi is smaller than oops. The first symbol that differs is at position 2 (the first letter is position 0) and the ASCII code for i is smaller than p.

As another example, given ooi and ooink, the ordering pad ooi with the null character at position 3, to give the order ooi < ooink.

Write a program lexicon, that reads from standard input:

• a positive integer $n$,
• followed by $n$ words

Print, to the standard output,

• the list of words in lexicographical order, one word per line.

Suppose that $k$ symbols are used in the lexicon, and the longest string is of length $m$. You must solve this problem with the running time of $O(m(n+k))$.

Solving this in $O(m{n}^2)$ or $O(mn\log n)$ is trivial, and such solution will be marked as "Need Improvement"

Sample Runs

ooiwt@pe119:~/ex06-skeleton$ cat inputs/lexicon.1.in
6
c
s
1
0
1
0
ooiwt@pe119:~/ex06-skeleton$ ./lexicon < inputs/lexicon.1.in
0
0
1
1
c
s
ooiwt@pe119:~/ex06-skeleton$ cat inputs/lexicon.2.in
9
cow
dog
cat
muk
ant
bee
fox
hen
for
ooiwt@pe119:~/ex06-skeleton$ ./lexicon < inputs/lexicon.2.in
ant
bee
cat
cow
dog
for
fox
hen
muk
ooiwt@pe119:~/ex06-skeleton$ cat inputs/lexicon.3.in
3
ooi
oops
ooink
ooiwt@pe119:~/ex06-skeleton$ ./lexicon < inputs/lexicon.3.in
ooi
ooink
oops