3.6. Exercises

3.6.1. Exercise 1: Realistic Complexity of Laplace Expansion

Recall the definition of a matrix determinant by Laplace expansion

\[|M| = \sum_{i = 0}^{n - 1}(-1)^{i} M_{0, i} \cdot |M^{0, i}|\]

where \(M^{0, i}\) is the corresponding minor of the matrix \(M\) of size \(n\), with indexing starting from \(0\).

This definition can be translated to OCaml as follows:

let rec detLaplace m n =
  if n = 1 then m.(0).(0)
  else
    let det = ref 0 in
    for i = 0 to n - 1 do
      let min = minor m 0 i in
      let detMin =  detLaplace min (n - 1) in
      det := !det + (power (-1) i) * m.(0).(i) * detMin
    done;
    !det

A matrix is encoded as a 2-dimensional array m, whose rank (both dimensions) is n. Here, minor returns the minor of the matrix m, and power a b returns the natural power of b of an integer value a.

Out of the explanations and the code above, estimate (in terms of big-O notation) the time complexity \(t(n)\) of the recursive determinant computation. Start by writing down a recurrence relation on \(t(n)\). Assume that the complexity of minor is \(c \cdot n^2\) for some constant \(c\). Consider the complexity of returning an element of an array to be 0 (i.e., \(t(1) = 0\)). For \(n > 1\), power, addition, multiplication and other primitive operations to be constants and approximate all of them by a single constant \(c\).

3.6.2. Exercise 2

Implement a function that generates takes (a) a sorting procedure sort for a key-value array, (b) a number n and a number length, and generates n random arrays of the length length, testing that sort is indeed correct on all those arrays.

3.6.3. Exercise 3

Find a procedure that takes an unsorted array and a given range of keys (represented by a pair of numbers lo < hi, right boundary not included), and returns the list of all elements in the array, whose keys are in that range. Estimate the complexity of this procedure.