Algorithms, Data Structures, and Complexity
Övning 1, January 15, 1998
1.
Write a divide and conquer algorithm to solve the MAXMIN problem.
Count the number of comparisons required in your algorithm.
MAXMIN
Input: An array of n numbers.
Output: The maximum and minimum numbers in the array.
2.
A Gray Code is a sequence of length 2**n such that
 every element is a string of n bits
 any two elements of the sequence are different and
 any two consecutive elements differ in exactly one bit.
Here, the first and last elements are considered to be consecutive.
Design a divideandconquer algorithm to construct a Gray code for any
given n.
Can you think of any applications for a Gray code?
3.
Consider the following function:
void PrintList(LIST list)
{
while (list != NULL) {
printf("%d\n",list>element);
list = list>next;
}
}
Prove that the function PrintList prints the elements on the list that
it is passed as an argument.
What statement S(i) do you prove inductively?
What is the basis value for i?
4.
Define recursively the set of evenparity strings, by induction on the
length of the string.
Hint: It helps to define two concepts simultaneously,
both the evenparity strings and the oddparity strings.
5.
A common way to define an ordering on character strings (known as
Lexicographic, Dictionary or Alphabetic ordering) is as follows:
We say c1c2...ck < d1d2...dm if either of the following holds:

The first string is a proper prefix of the second, which means that k < m
and for i = 1,2,...,k we have ci = di. (We will use E to denote the
empty string, the string with zero characters. We always have E < s for
any nonempty string s.)

There is some i > 0 such that cj = dj for j = 1,2,...,i1 and ci < di.
Give a recursive definition that equivalent to this iterative
definition of lexicographic ordering. Prove that the two definitions
are in fact equivalent.
6.
Prove that the following recursive algorithm for the multiplication of
two numbers is correct.
function multiply(y,z) // Returns the product yz.
 if z = 0 then return(0) else
 if z is odd then return(multiply(2y, z/2 ) + y)
 else return(multiply(2y,z/2)).
Note: The symbol " " denotes the floor function. " x " means the
greatest integer less than or equal to x.
7.
Prove that any set of regions defined by n lines in the plane can be
colored with two colors so that no two regions that share an edge have
the same color.
8.
Define an "expression" recursively as
 any number or identifier is an expression
 if E1 and E2 are any two expressions, then E1 # E2 is also an
expression where # denotes any operator
 if E is any expression, then (E) is also an expression.
(As a technicality, we must also stipulate that only things generated
by these rules are expressions.)
Consider an expression E whose operators are all binary. The length
of E is the number of symbols in E, counting an operator or a left or
right parenthesis as one symbol, and also counting any operand such as
123 or abc as one symbol.
Prove that E must have an odd length.