Here is a histogram for the minimum number of iterations before the "mincut" of a graph with 200 nodes is found using the Karger's algorithm:

As an R newbie, here is how I generated the graph using R version 2.15.1:

> data <- c(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 33, 33, 33, 33, 33, 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 36, 36, 36, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 38, 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43, 43, 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, 47, 47, 47, 47, 47, 48, 48, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49, 49, 49, 49, 50, 50, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 53, 53, 53, 53, 53, 54, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 60, 60, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 67, 67, 67, 67, 67, 68, 68, 68, 68, 68, 69, 69, 69, 69, 69, 70, 70, 71, 72, 72, 72, 72, 72, 72, 73, 73, 73, 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, 75, 75, 75, 75, 75, 76, 76, 76, 76, 76, 76, 77, 77, 77, 77, 78, 78, 78, 78, 79, 79, 79, 79, 79, 80, 80, 80, 81, 81, 81, 81, 81, 81, 82, 82, 82, 83, 83, 83, 84, 84, 85, 85, 85, 85, 85, 86, 86, 86, 86, 86, 86, 86, 88, 88, 88, 89, 89, 89, 90, 90, 90, 90, 91, 91, 91, 92, 92, 92, 92, 92, 92, 93, 93, 93, 93, 93, 94, 94, 94, 94, 95, 95, 96, 96, 97, 97, 98, 98, 98, 98, 98, 99, 100, 100, 102, 102, 102, 102, 103, 103, 103, 103, 103, 103, 104, 105, 105, 106, 106, 106, 106, 107, 107, 107, 107, 107, 110, 110, 110, 111, 112, 112, 113, 113, 114, 114, 115, 115, 116, 116, 117, 117, 118, 118, 118, 119, 120, 120, 121, 121, 122, 122, 123, 123, 124, 124, 125, 126, 126, 126, 126, 126, 127, 127, 127, 127, 128, 129, 129, 129, 133, 134, 134, 261, 137, 137, 137, 139, 139, 139, 140, 140, 143, 144, 147, 147, 148, 149, 150, 151, 151, 152, 155, 155, 156, 156, 160, 161, 162, 162, 163, 163, 262, 166, 167, 170, 172, 172, 175, 177, 178, 178, 180, 185, 356, 187, 187, 188, 194, 197, 205, 206, 209, 217, 220, 220, 264, 227, 228, 296, 342)
> png(file="/tmp/mincut.png",width=800,height=700)
> hist(data, col="cornsilk", xlab="#Iterations per search", ylab="Frequency", main="1,000 Mincut Search [mean=16, median=34]", font.main=4, breaks=100,xlim=c(0,400), ylim=c(0,100))
> dev.off()

The Shelmikedmu are an elusive and nomadic tribe whose members are unusually heterogeneous in respect of hair and eye color, and skull shape. A persistent anthropologist establishes the following facts:

1. 75% have dark hair, the rest have fair hair
2. 80% have brown eyes, the rest have blue eyes
3. No narrow-headed person has fair hair and blue eyes
4. The proportion of blue-eyed broad-headed tribespeople is the same as the proportion of blue-eyed narrow-headed tribespeople
5. Those who are blue-eyed and broad-headed are fair-haired or dark-haired in equal proportion
6. Half the tribe is dark-haired and broad-headed
7. The proportion who are browned-eyed, fair-haired, and broad-headed is equal to the proportion who are brown-eyed, dark-haired, and narrow-headed

What is the proportion of the tribe who are narrow-headed ?

(Stop scrolling down if you want to give this a shot :))

Solution:

The challenge is how to represent these various facts in a form that can be manipulated via simple arithmetic. First, observe that the entire sample space consists of only three underlying attributes: Hair color, Eye color and Head shape, each with only 2 possible values, giving a total of 2^3 possible outcomes:

Hair: {Dark, Fair}
Eye: {Brown, Blue}
Head: {Narrow, Board}

If we use A, B, and C to represent Hair, Eye and Head, and {A1, A2}, {B1, B2}, {C1, C2} to represent the respective values, this would give:

A: {A1, A2}
B: {B1, B2}
C: {C1, C2}

The 8 possible outcomes are:

A1,B1,C1
A1,B1,C2
A1,B2,C1
A1,B2,C2
A2,B1,C1
A2,B1,C2
A2,B2,C1
A2,B2,C2

Suppose the total number of tribespeople is 100. Let's go through the given facts above from most specific to least specific:

• "No narrow-headed person has fair hair and blue eyes" => |{A2,B2,C1}| = 0
• "The proportion who are browned-eyed, fair-haired, and broad-headed is equal to the proportion who are brown-eyed, dark-haired, and narrow-headed" => x = |{A2,B1,C2}| = |{A1,B1,C1}|
• "Those who are blue-eyed and broad-headed are fair-haired or dark-haired in equal proportion" => y = |{A2,B2,C2}| = |A1,B2,C2}|

This gives us:

          Size
          ====
A1,B1,C1    x
A1,B1,C2    
A1,B2,C1
A1,B2,C2    y
A2,B1,C1
A2,B1,C2    x
A2,B2,C1    0
A2,B2,C2    y

Continuing,

• "The proportion of blue-eyed broad-headed tribespeople is the same as the proportion of blue-eyed narrow-headed tribespeople" => |{*,B2,C2}| = |{*,B2,C1}| => |{A1,B2,C1}| = 2y

Now let z = |{A1,B1,C2}|, we get:

          Size
          ====
A1,B1,C1    x
A1,B1,C2    z
A1,B2,C1   2y
A1,B2,C2    y
A2,B1,C1
A2,B1,C2    x
A2,B2,C1    0
A2,B2,C2    y

Given the assumed total population is 100, |{A2,B1,C1}| = 100 - 2x - 4y - z, or:

          Size
          ====
A1,B1,C1    x
A1,B1,C2    z
A1,B2,C1   2y
A1,B2,C2    y
A2,B1,C1    100 - 2x - 4y - z
A2,B1,C2    x
A2,B2,C1    0
A2,B2,C2    y

Moving on,

• "75% have dark hair, the rest have fair hair" => 75 = x + z + 2y + y = x + z + 3y
• "80% have brown eyes, the rest have blue eyes" => 20% have blue eyes => 20 = 2y + y + y = 4y, so y = 5
• "Half the tribe is dark-haired and broad-headed" => 50 = z + y, so z = 45

This means:

• 75 = x + z + 3y = x + 45 + 15, so x = 15
• Number of narrow-headed => x + 2y + (100 - 2x - 4y - z) = 15 + 10 + (100 - 30 - 20 - 45) = 30

The answer is therefore 30% :)

Via the excellent Coursera online crypto course offered by Stanford University, I learned from Professor Dan Boneh that we should never use symmetric cipher alone. Instead, we should always use authenticated encryption with optional associated data to simultaneously provide confidentiality, integrity and authenticity assurances. One such recommended standard is AES/GCM, which is mentioned to be supported both by openssl and Java.

In Java, unfortunately, although the SPI for AES/GCM has arrived in Java 7 as described in the javadoc of the Cipher class, there is actually no such implementation in the JDK. This prompted me to look into the latest Bouncy Castle library. In the latest BC version 1.4.7, even though there exists a GCMBlockCipher, it is apparently not properly exposed via JCE in the sense that no associated data can be updated via the JCE API without causing an exception if "BC" is used as the security provider.

On one hand, the GCMBlockCipher per se does seem to be fully functional. On the other hand, I don't seem to be able to find any example of doing authenticated encryption with associated data with it. So I went ahead and try to come up with some sample code in the form of a unit test below. Can anyone see if I am doing something silly ?

import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import java.nio.charset.StandardCharsets;
import java.security.SecureRandom;
import java.util.Arrays;

import javax.xml.bind.annotation.adapters.HexBinaryAdapter;

import org.bouncycastle.crypto.InvalidCipherTextException;
import org.bouncycastle.crypto.engines.AESEngine;
import org.bouncycastle.crypto.modes.GCMBlockCipher;
import org.bouncycastle.crypto.params.AEADParameters;
import org.bouncycastle.crypto.params.KeyParameter;
import org.junit.Test;

/**
 * @author rot13(Unafba Pune)
 */
public class GCMBlockCipherTest {
    private static final SecureRandom rand = new SecureRandom();
    private static final int MAC_SIZE = 128;
    private static final byte[] keybytes = new byte[16*2];
    private static final byte[] nouncebytes = new byte[16];
    private static final KeyParameter key = new KeyParameter(keybytes);
    private static final byte[] associatedText = "Some Associated Text".getBytes(StandardCharsets.UTF_8);
    private static final byte[] plaintext = "Some plaintext".getBytes(StandardCharsets.UTF_8);
    
    static {
         rand.nextBytes(keybytes); // a random key   
         rand.nextBytes(nouncebytes); // a random nounce
    }

    @Test
    public void testGCMEncryptDecryptWithAD() throws InvalidCipherTextException {
        System.out.println("plaintext: " + hex(plaintext));
        AEADParameters params = new AEADParameters(key, MAC_SIZE, nouncebytes, associatedText);
        byte[] ciphertext = encrypt(plaintext, params);
        System.out.println("ciphertext: " + hex(ciphertext));
        byte[] decrypted = decrypt(ciphertext, params);
        System.out.println("decrypted: " + hex(decrypted));
        System.out.println("nounce: " + hex(nouncebytes));
        assertTrue(Arrays.equals(plaintext, decrypted));
    }

    @Test(expected=InvalidCipherTextException.class)
    public void testNounceMismatch() throws InvalidCipherTextException {
        AEADParameters params = new AEADParameters(key, MAC_SIZE, nouncebytes, associatedText);
        byte[] ciphertext = encrypt(plaintext, params);
        AEADParameters paramsWithBadNounce = new AEADParameters(key, MAC_SIZE, new byte[16], associatedText);
        try {
            decrypt(ciphertext, paramsWithBadNounce);
            fail();
        } catch(InvalidCipherTextException ex) {
            assertTrue(ex.getMessage().contains("mac check in GCM failed"));
            throw ex;
        }
    }
    
    @Test(expected=InvalidCipherTextException.class)
    public void testADMismatch() throws InvalidCipherTextException {
        AEADParameters params = new AEADParameters(key, MAC_SIZE, nouncebytes, associatedText);
        byte[] ciphertext = encrypt(plaintext, params);
        AEADParameters paramsWithBadAD = new AEADParameters(key, MAC_SIZE, nouncebytes, new byte[16]);
        try {
            decrypt(ciphertext, paramsWithBadAD);
            fail();
        } catch(InvalidCipherTextException ex) {
            assertTrue(ex.getMessage().contains("mac check in GCM failed"));
            throw ex;
        }
    }

    /** Returns the ciphertext encrypted from the given plaintext and AEAD parameters. */
    private static byte[] encrypt(byte[] plaintext, AEADParameters params) throws InvalidCipherTextException {
        GCMBlockCipher gcm = new GCMBlockCipher(new AESEngine());
        gcm.init(true, params);
        int outsize = gcm.getOutputSize(plaintext.length);
        byte[] out = new byte[outsize];
        int offOut = gcm.processBytes(plaintext, 0, plaintext.length, out, 0);
        gcm.doFinal(out, offOut);
        return out;
    }

    /** Returns the plaintext decrypted from the given ciphertext and AEAD parameters. */
    private static byte[] decrypt(byte[] ciphertext, AEADParameters params) throws InvalidCipherTextException {
        GCMBlockCipher gcm = new GCMBlockCipher(new AESEngine());
        gcm.init(false, params);
        int outsize = gcm.getOutputSize(ciphertext.length);
        byte[] out = new byte[outsize];
        int offOut = gcm.processBytes(ciphertext, 0, ciphertext.length, out, 0);
        gcm.doFinal(out, offOut);
        return out;
    }

    private static String hex(byte[] values) {
        return new HexBinaryAdapter().marshal(values);
    }
}