Exercises for the week 4 exercise session¶

Exercise 1¶

A string (word) which reads the same from left to right and right to left is called a palindrome. Spaces, punctuation and upper/lower case does not matter. For example the following are palindromes: Anna, A lad named E. Mandala, A Santa dog lived as a devil God at NASA.

Write recursive and iterative algorithms which check whether a string is a palindrome. Write your answer using pseudocode. If necessary, you can assume that you are given a separate algorithm/function which you can call and which converts the string into a suitable form (strips spaces, punctuation, all to lower case letters).

Exercise 2¶

The BINSEARCH procedure searches a sorted array A[1..n] for the number key using a binary search. In a binary search the starting array A[L..R] is divided into two (nearly) equally sized subarrays at each iteration (or recursion level): A[L..mid] and A[(mid+1)..R]. By comparing the element at the split point, it can be deduced whether the search should continue in the left or right half (unless the split point contains the element we search for). In a ternary search a similar approach is used, except that at each iteration (or recursion level) the starting array A[L..R] is divided into three (nearly) equally-sized subarrays: A[L..mid1], A[(mid1+1)..mid2] and A[(mid2+1)..R]. The number key can occur in only one of these three subarrays and hence the other two can be discarded. Write a procedure TERNSEARCH using a ternary search approach that is an alternative to BINSEARCH.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

BINSEARCH(A,L,R,key)
  input A[1..n] is an array containing numbers; L and R are the
  leftmost and rightmost indices that concern us; key is the value
  we want to find
  output: the index at which key occurs in A, or -1 if it doesn't
  /* The numbers in A must be in order from smallest to largest.
  We search in array A[L..R] for key. If key is found, we return
  its location, otherwise we return -1.*/
  if L == R then
    if A[L] == key then
      return L
    else
      return -1
    end
  else
    mid = floor( (L+R)/2 )
    if key <= A[mid] then
      return BINSEARCH(A,L,mid,key)
    else
      return BINSEARCH(A,mid+1,R,key)
    end
  end