Prova scritta - 07/10/2010

Ricerca in una matrice bi-ordinata

Data la seguente funzione che verifica se un elemento k è presente o meno in una matrice quadrata n x n bi-ordinata (una matrice è bi-ordinata se sono ordinate tutte le righe e tutte le colonne):

Funzione MATRIX-SEARCH

MATRIX-SEARCH(A, i, j, k)

1    if    a_ij = k

2        then return true

3    else if    a_ij < k

4        then if    i < rows[A]

5            then return    MATRIX-SEARCH(A, i+1, j, k)

6            else return false

7    else if    j > 1

8        then return    MATRIX-SEARCH(A, i, j-1, k)

9        else return false

Richieste

• Scrivere e risolvere la ricorrenza che descrive T(n), con n numero di righe della matrice (N.B: n è anche numero di colonne, dal momento che la matrice è quadrata).
• Dimostrarne la correttezza, ovvero che la chiamata MATRIX-SEARCH(A, 1, rows[A], k) restituisce correttamente true se il valore k è presente nella matrice bi-ordinata e false altrimenti (rows[A] è l'attributo che indica il numero di righe della matrice A).