Pallot

Arvioi ensin 1-säteisen ympyrän pinta-alaa hylkäysotannalla. Tuloksen pitäisi olla suunnilleen 3.141.

Entä 1-säteisen pallon tilavuus? Tai n-ulotteisen hyperpallon?

Epäjärjestykset

Taulukon 1, 2, \dots, n järjestys on epäjärjestys, jos mikään luku ei ole alkuperäisellä paikallaan. Arvioi epäjärjestysten määrää hylkäysotannalla.

Sulkulausekkeet

Kelvollisessa sulkulausekkeessa on yhtä monta alku- ja loppusulkua ja kullakin sululla on pari lausekkeessa. Esimerkiksi seuraava on kelvollinen sulkulauseke:

()(())

Voitko hylkäysotannalla tuottaa satunnaisia kelvollisia lausekkeita? Entä arvioida niiden määrää?

Kokonaisluvut

Pussissa on \lceil\sqrt{k}\,\rceil kappaletta lukua k, kullekin k = 1, 2, \dots, n. Nosta pussista satunnaisia lukuja nopeasti hylkäysotantaa hyödyntäen.

Sarja

Arvioi sarjan \sum_{n=1}^{\infty} \frac{1}{n^2} arvoa hylkäysotantaa hyödyntäen.

Vinkki: vagrtebv k:a xääagrvfyhiha aryvö (rot13)

DNF-SAT

Annetaan n muuttujan ja m klausuulin SAT-kaava (ks. KKKK luku 17.2.) muotoa C_1 \lor C_2 \lor \dots C_m, jossa jokainen klausuuli C_i on muotoa a_{i1} \land a_{i2} \land \dots \land a_{i,\ell_i} ja jokainen a_{ij} on jokin muuttuja tai sen negaatio. Esimerkkikaava: (x_1 \land \lnot x_2) \lor (\lnot x_1 \land x_3 \land x_4).

Kehitä algortmi, joka arvioi kelvollisten muuttujavalintojen määrää.