[CSE2304]

Quick Questions

 L.A.  Comp.Sci.& SWE
1. small, x and y have been declared to be floating-point variables; x and y have proper defined values in them.
Write code to set small equal to the smaller of x and y.

2. big, x and y have been declared to be floating-point variables; x and y have proper defined values in them.
Write code to set big equal to the larger of x and y.

3. min, x, y and z have been declared to be floating-point variables; x, y and z have proper defined values in them.
(a) Write a piece of efficient C-code to set min equal to the smallest of x, y and z.
(b) What is the average number of comparisons that your code executes, assuming that all possible orderings of x, y and z are equally likely? Why?

4. mid, x, y and z have been declared to be floating-point variables; x, y and z have proper defined values in them, not necessarily all different.
(a) Write a piece of efficient C-code to set mid equal to the median of x, y and z.
(e.g. If it were the case that x is less than or equal to y and y is less than or equal to z, then the median would equal y.)
(b) What is the average number of comparisons that your code executes, assuming that all possible orderings of x, y and z are equally likely? Why?

5. Write the shortest possible piece of C-code to solve this problem:
If x is positive, and y is greater than x, set p to true, otherwise set p to false.
It is important that the piece of code be as short as possible.

6. Write the shortest possible piece of code to solve this problem:
If x is greater than y set p to true, otherwise set p to false.
It is important that the piece of code be as short as possible.

7. Write the shortest possible piece of C-code to solve this problem:
If x and y are negative, set p to true, otherwise set p to false.
It is important that the piece of code be as short as possible.

8. Translate the following English statements (which can be true or false) into logical expressions that are as close to C-code as possible:

(i) x and y are larger than z.
(ii) ch is an upper-case letter.
(iii) The key value is between positions i and j inclusive, if it is in the array A at all.
NB. x, y, z, ch, key, A are variables of the appropriate types. You must not call any subroutines.

9. Translate the following English statements (which can be true or false) into logical expressions that are in C-code, or as close to C-code as possible:

(i) n is a multiple of five.
(ii) x and y are both positive or both negative.
(iii) x is positive whenever y is.
NB. x, y, n, can be assumed to be variables of the appropriate types. You must not call any subroutines.

10. Negate and simplify (i.e. form the simplified opposite of) each of the following statements, giving your answers as logical expressions that are as close to C-code as possible:

(i) N is either even or prime. (Assume that `int prime(int)` is already defined.)
(ii) A[left] > median and left < right
(iii) k>=i and k<j and A[k]<=A[k+1]

11. Negate and simplify (i.e. form the simplified opposite of) each of the following statements, giving your answers as logical expressions in C-code, or as close to C-code as possible:

(i) At least one of x and y is positive.
(ii) The integer variables i, j, and k are all odd.
(iii) key < T->c and key > T->left->c

12. P1 and P2 are conditions (Boolean expressions, statements, ...). P1 is said to be stronger than P2, or equivalently P1 is said to imply P2, written P1=>P2, if P2 is true whenever P1 is true.
Below are pairs of statements. For each pair, say which is the stronger statement:

(i) (a) It's raining.   (b) It's pouring.
(ii) (a) The animal is a kangaroo.   (b) The animal is a marsupial.
(iii) (a) N is a multiple of 10.   (b) N is even.

13. P1 and P2 are conditions (Boolean expressions, ...). P1 is said to be stronger than P2, or equivalently P1 is said to imply P2, written P1=>P2, if P2 is true whenever P1 is true.
Below are pairs of statements. For each pair, say which is the stronger statement:

(i) (a) The cup contains tea.   (b) The cup contains a drink.
(ii) (a) N2 is greater than nine.   (b) N is less than minus three.
(iii) (a) T is a binary search tree.   (b) T is an AVL-tree.

14. What is the time-complexity of the following code as a function of N? Why?

```k = 0;
for(i = 0; i < N; i++)
for(j = i; j < N; j++)
k = k+j;
```

15. What is the time-complexity of the following routine in terms of N? Why?

```   int recf(int N)
{ int i, k;
if( N > 0 )
{ k = 0;
for( i = 0; i < N; i++ )
k = k+i;
return ( k + recf( N-1 ) );
}
return 0;
}
```
16. x, y and z are three integer variables. Write a piece of efficient C-code to find the number of different values in x, y and z, some of which may be equal, and store that number (i.e. 1, 2, or 3) in N. Your code must be as efficient as possible.

17. x, y and z are three variables. Write a piece of code to set x equal to the smallest of their initial values, z equal to the largest of their initial values, and y to the remaining one of their initial values. e.g.

```/* e.g. if x equals 2.2, y equals 3.3, z equals 1.1 initially
(but x,y,z could have any values) */
/* your code here */
/* POST: x<=y<=z.
In this example
x equals 1.1, y equals 2.2, z equals 3.3 after */
```

18. Algorithms and problem solving, assumes a 1st year programming subject.

19. Write a piece of efficient code to print all positive integers less than or equal to 'limit', that are expressible as the sum of two squares, i2+j2, in two or more different ways, e.g. 50 = 52+52 = 12+72. (NB. 13 = 22+32 = 32+22 does not count as 2 different ways.)

20. For a right-angled triangle with sides h, x and y, we have h2=x2+y2, e.g. 52=32+42. Write a piece of efficient C-code to print all triples of positive integers, (h,x,y), where h, x and y are less than or equal to 'limit', h2=x2+y2, and x>=y.

21. S[ ] is a string of N letters. N can be arbitrarily large. A substring, S[i..j], consists of the elements   S[i], S[i+1], ..., S[j],   if j>=i, and is empty otherwise. The letters {a, e, i, o, u, y} are vowels. The letters {b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z} are consonants. Note that y is both a vowel and also a consonant for present purposes.
Write a piece of efficient C-code to find the longest substring of S[ ] that contains all vowels or all consonants, and print the start and end positions of the interval. Resolve ties arbitrarily. S must not be changed in any way.

22. A[ ] is an array of N integers.
Write a piece of efficient C-code to find the positions of the two largest elements in the array. Resolve ties arbitrarily
(e.g. if A[ ] holds 3, 2, -3, 0, 5, -1, 3, 5, 1, 5,   a possible answer is A[4] and A[7].
e.g. if A[ ] holds 3, 2, -3, 0, 5,   the answer is A[0] and A[4].) Resolve ties arbitrarily. The array must not be changed in any way.

23. A[ ] is an array of N integers. M<<N.
Write a piece of efficient C-code to find the positions of the M largest (not necessarily distinct) elements in the array. Resolve ties arbitrarily. The array must not be changed in any way.

24. A[ ] is an array of N integers.
Write a piece of efficient C-code to print the the second-largest distinct value in the array.
(e.g. if A[ ] holds 3, 2, -3, 0, 5, -1, 3, 5, 1, 5,   the answer is 3.) Resolve ties arbitrarily. The array must not be changed in any way.

25. A[ ] is an array of N integers.
Write a piece of efficient C-code to print the position of the second-largest distinct value in the array.
(e.g. if A[ ] holds 3, 2, -3, 0, 5, -1, 3, 5, 1, 5,   the answer is 0 or 6.) Resolve ties arbitrarily. The array must not be changed in any way.

26. A[ ] is an array of N integers. M<<N.
Write a piece of efficient C-code to find the Mth largest (not necessarily distinct) element in the array and print its position. Resolve ties arbitrarily. The array must not be changed in any way.

27. A[ ] is an array of N integers. N>=M.
Write a piece of efficient C-code to find the M largest distinct elements values in the array and print their positions of first occurrence. (Assume that there are at least M distinct values in the array.) The array must not be changed in any way.

28. A[ ] is an array of N integers. An interval, A[i..j], consists of the elements   A[i], A[i+1], ..., A[j],   if j>=i, and is empty otherwise.
Write a piece of efficient C-code to find the longest interval that contains no positive values, and print its start and end positions. (You can assume that there is at least one negative value in the array.) Resolve ties arbitrarily. The array must not be changed in any way.

30. A[ ] is an array of N floating point numbers. An interval, A[i`..`j], consists of the elements A[i], ..., A[j] if i<=j and is empty if j<i.
The interval is said to be non-decreasing if A[k]<=A[k+1] for all k such that i<=k<j.
e.g. if ```A[0..6] = (32.1, 35.0, 10.0, 8.0, 17.1, 63.3, 41.9)```
then the desired interval is A[3..5].
Give efficient C-code to find the longest non-decreasing interval in A[ ], and print its start position and its end position. Resolve ties arbitrarily. The array must not be changed in any way.

31. A[ ] is an array of N integers.
An interval, A[i`..`j], consists of the elements A[i], ..., A[j] if i<=j and is empty if j<i.
The interval is said to be an arithmetic progression if: `A[i+1]-A[i] = A[i+2]-A[i+1] = ... = A[j]-A[j-1]`
e.g. if A[ ] contains `80 82 84 80 76 72 72 72 73 70`
then the intervals A[0..2], A[2..5], A[5..7], A[7..8] and A[8..9] are arithmetic progressions that cannot be extended and A[2..5] is the longest of them.
Give efficient C-code to find the longest arithmetic progression in A[ ]. Resolve ties arbitrarily. The array must not be changed in any way.

32. A[ ] is an array of N integers. An interval, A[i..j], consists of the elements A[i], A[i+1], ..., A[j],  if i<=j, and is empty otherwise. An interval A[i..j] is said to be an odd-even-run (OER) if there are nowhere three or more odd numbers adjacent to each other in the interval, and nowhere three or more even numbers adjacent to each other in the interval. Write a piece of efficient C-code to find the longest OER in the array A, and print the start and end positions of this OER. Resolve ties arbitrarily. The array must not be changed in any way.

33. A[ ] is an array of N integers. M is a given integer, M<<N. An interval, A[i..j], consists of the elements A[i], A[i+1], ..., A[j],  if i<=j, and is empty otherwise. max(A[i..j]) is the largest value in A[i..j] and min(A[i..j]) is the smallest value in A[i..j]).
Give efficient C-code to find the interval A[i..i+M-1] such that the range, max(A[i..i+M-1])-min(A[i..i+M-1]), is as small as possible and print the interval's start position. Resolve ties arbitrarily. The array must not be changed in any way.

34. A[ ] is an array of N integers. M is a given integer. N>>M. An interval, A[i..j], consists of the elements A[i], A[i+1], ..., A[j],  if i<=j, and is empty otherwise. Give efficient C-code to find the interval A[i..i+M-1] that contains the fewest distinct values and print the interval's start position. Resolve ties arbitrarily. The array must not be changed in any way.

35. s/fewest/most/. As above but "most" distinct values.

36. A[ ] is an array of N integers. An interval, A[i..j], consists of the elements A[i], A[i+1], ..., A[j],  if i<=j, and is empty otherwise. An interval A[i..j] is said to be nearly constant if  max{A[k] | i<=k<=j} - min{A[m] | i<=m<=j} <= lim for a given, small value 'lim'.
Write a piece of efficient C-code to find the longest nearly constant interval in the array A and print its start and end positions. Resolve ties arbitrarily. The array must not be changed in any way.

37. A[ ] is an array of N integers. Write efficient C-code to find the shortest interval of the array such that the interval contains at least m non-zero elements. The array must not be changed in any way.

38. The following is a version of a well known algorithm;
(a) which algorithm?
(b) It has a bug in it (i.e. it compiles and runs but may give wrong results). Where is the bug and what is it?
(c) Give a small example to demonstrate the bug; trace the code through it to show the code failing.
(d) Fix the bug, i.e. give corrected code.
(e) Give a convincing argument that your corrected code works.

```/* Assume declarations:  sometype key, A[N] */

L=0;  R=N;                             /* b */
while( L < R-1 )                       /* u */
{ M=(L+R)/2;                          /* g */
if( key > A[M] ) L=M; else R=M;     /* g */
}                                     /* y */
F = (A[L]==key);                       /* ! */
```

39. The string S[ ] contains N opening parentheses,'(', and N closing parentheses, ')', but they might or might not be matched correctly. Give efficient C-code to determine if the parentheses are matched correctly or not. The string must not be changed in any way.

40. The string S[ ] contains N '(' and/or '[', and N ')' and/or ']', but they might or might not be matched correctly. Give efficient C-code to determine if the string is valid, i.e. contains no mismatched round or square brackets. e.g. "(()[()])[]" is valid, e.g. "([)]" is not valid, nor is ")(", or "[)".)

41. Strings of N matched parentheses can be ordered lexicographically (alphabetically), e.g. N=3: ((())), (()()), (())(), ()(()), ()()().
S[ ] contains a string of N matched parentheses (not the last such string). Give efficient C-code to change S[ ] so that it contains the next such string.

42. s/next/previous/. As above but "previous" string.

43. Permutations of the integers 1..N can be ordered lexicographically (alphabetically), e.g. N=3: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. Array A[ ] contains a permutation of 1..N (not the last permutation). Give efficient C-code to change A[ ] so that it contains the next such permutation.

44. s/next/previous/. As above but "previous" permutation.

45. A partition of an integer, n, is a list of positive numbers that add up to n. Here, each partition is written in non-increasing order, e.g. 3+2, not 2+3. Partitions can be ordered lexicographically,
e.g. 5: 1+1+1+1+1+1, 2+1+1+1, 2+2+1, 3+1+1, 3+2, 4+1, 5.
Write an efficient C routine, nextPartition(int length, int partition[]), which is given a (non-increasing) partition and prints the next partition, if any, in lexicographical order. e.g. Given 2+1+1+1, print 2+2+1.

46.  ``` F . . . . L F <----> FLFLL . . L L ```
47. A strict binary tree is made of fork and leaf nodes (only), where every fork node has exactly two non-empty sub-trees (not ''at most two''). Such a tree can be represented by its prefix traversal string, writing 'F' for a fork and 'L' for a leaf. Note that the string has one more 'L' than 'F', and no prefix of the string has that property. Every tree has such a string and the tree can be reconstructed from the string. The set of all such strings representing strict binary trees can therefore be put in an ordered series, first by length and within that lexicographically (alphabetically), i.e. L, FLL, FFLLL, FLFLL, ...
Give the next six strings in the series. Give efficient code to change a valid string, S[ ], into the next string in the series.

48. A[ ] is an array of N elements.
The function `int colour(element x)` returns one of the two values `red` or `blue`.
Write a piece of efficient code to rearrange the contents of A so that all of the `red` elements are adjacent to each other, and all of the `blue` elements are adjacent to each other, in the array.
Briefly (!) explain what your code does.
Your code must run in linear time!

49. The following questions require some specialised knowledge, e.g. CSE2304.

50. You are given an ordered list of words in a newly-discovered, ancient (natural) language. The language uses the usual alphabet {a-z} but the alphabetic ordering is non-standard, i.e. not a,b,...,z. You must work out the alphabetic ordering of the 26 letters in the language.
NB. There may be letters that do not begin any word in the list. If multiple alphabetic orderings are consistent with the word-list, return any one of them.
What algorithm(s) and/or data structures could be used to solve this problem? Why? (Do not write any code.)
(Based on an ACM programming competition question.)

51. A chromosome consists of a very long sequence made up of the four DNA building blocks called bases, {A,T,C,G}, e.g. . . . ACCTGCA . . . . Some DNA sub-sequences are found to be repeated at different positions in chromosomes. Molecular biologists are very interested in finding long sub-sequences that occur more than once.
What algorithm(s) and/or data structure(s) could be useful (how and why) in finding the longest such sub-sequence in a chromosome? Do not write any code.

52.  ``` AU CG ^ GC | | UA v CG CG ...AU... hair-pin```
53. An RNA molecule consists of a long string made up of four building blocks called bases, {A,U,C,G}, e.g. . . . ACCUGCA . . . . The bases are complimentary in pairs, i.e. an 'A' will bind to a 'U' and a 'C' will bind to a 'G'. If a substring is immediately followed by its reversed compliment, e.g. . . . ACCUGCAUGCAGGU . . ., the RNA may form a stable hair-pin loop. Molecular biologists are therefore interested in the longest substring that is immediately followed by its reversed compliment.
What  algorithm(s) and/or data structure(s) could be useful (and why) in finding the longest such substring in an RNA molecule? Do not write any code.

© L.Allison, Computer Science and Software Engineering, Monash University, Clayton, Australia 3800,
2006, 2017,