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
  1. every element is a string of n bits
  2. any two elements of the sequence are different and
  3. any two consecutive elements differ in exactly one bit.

Here, the first and last elements are considered to be consecutive.

Design a divide-and-conquer 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 even-parity strings, by induction on the length of the string.

Hint: It helps to define two concepts simultaneously, both the even-parity strings and the odd-parity 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:
  1. 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 non-empty string s.)
  2. There is some i > 0 such that cj = dj for j = 1,2,...,i-1 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.

  1. if z = 0 then return(0) else
  2. if z is odd then return(multiply(2y, z/2 ) + y)
  3. 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
  1. any number or identifier is an expression
  2. if E1 and E2 are any two expressions, then E1 # E2 is also an expression where # denotes any operator
  3. 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.