File LocalOptima.h

↰ Parent directory (ADS/search)

The local optima of a vector and of a binary tree, found without looking at all the items.

Definition (ADS/search/LocalOptima.h)

Detailed Description

A peak of A[ 0 .. n - 1 ] is an item not smaller than its neighbours, the items out of A counting as smaller than any item, and a local minimum is an item not larger than its neighbours; the maximum is a peak, so that a peak always exists, but finding the maximum needs n - 1 comparisons while a peak needs only a logarithmic number of them.

  • findPeak(): a binary search on the invariant that A[ lo .. hi ] holds a peak of A, true when A[ lo - 1 ] < A[ lo ] (or lo = 0) and A[ hi ] is not smaller than A[ hi + 1 ] (or hi = n - 1): the middle item A[ m ] is compared with A[ m + 1 ], and the search goes on in A[ m + 1 .. hi ] if it is smaller and in A[ lo .. m ] otherwise, both keeping the invariant; :math:` lceil log_2 n rceil ` comparisons, and :math:` Omega( log n ) ` are needed in the worst case. With distinct items the peak is strict;

  • localMinimum() of a vector: findPeak() with the order reversed;

  • localMinimum() of a binary tree: a node not larger than its parent and its children, found by going down from the root to the first child smaller than the current node, until no child is smaller; each node reached is smaller than its parent, the last one is not larger than its children, :math:` O( h ) ` comparisons for a tree of height h, i.e., :math:` O( log n ) ` on a complete tree.

The same idea works in two dimensions, where a peak of an n x n matrix costs :math:` Theta( n ) ` probes by the search on the middle row and the middle column alternately, but not on general graphs: on the hypercube of dimension d, Aldous showed that every randomized algorithm needs about :math:` 2^{d / 2} ` evaluations to find a local minimum.

The contracts [see File Contract.h]: findPeak() and localMinimum() of a vector need a vector that is not empty and localMinimum() of a tree a tree; the result is checked against its neighbours, a postcondition. The functions are defined in LocalOptima.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, Esercizi Divide-et-impera, Raccolte da compiti scritti

  1. Aldous, Minimization algorithms and random walk on the d-cube, The Annals of Probability 11(2), 403-413, 1983, doi:10.1214/aop/1176993605

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions