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.
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.
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?
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?
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.
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.
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.
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.
- (ii) ch is an upper-case letter.
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.
- (ii) x and y are both positive or both negative.
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]
- (ii) A[left] > median and left < right
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
- (ii) The integer variables i, j, and k are all odd.
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.
- (ii) (a) The animal is a kangaroo. (b) The animal is a marsupial.
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.
- (ii) (a) N2 is greater than nine. (b) N is less than minus three.
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;
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;
}
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 (
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 */
Algorithms and problem solving, assumes a 1st year programming subject.
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.
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.
S[ ] is a string of N letters. N can be arbitrarily large.
A substring, S[i..j], consists of the elements
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.
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.
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.
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.
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.
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.
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.
A[ ] is an array of N integers.
An interval, A[i..j], consists of the elements
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.
|
L . A l l i s o n © |
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] =
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.
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.
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.
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.
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.
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
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.
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.
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); /* ! */
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.
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.
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.
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.
s/next/previous/.
As above but "previous" permutation.
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,
F
. .
. .
L F <----> FLFLL
. .
L L
|
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.
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!
The following questions require some specialised knowledge, e.g. CSE2304.
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.)
A chromosome consists of a very long sequence made up of
the four DNA building blocks called bases, {A,T,C,G},
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.
AU CG ^ GC | | UA v CG CG ...AU...hair-pin |
An RNA molecule consists of a long string made up of
four building blocks called bases, {A,U,C,G},
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.