Quantum Islands, Parts 2 and 3 written by Dan Compton (DC)
Part 1: Count Islands
Given an NxN matrix where 1 represents "land" and an element populated with 0 represents "water", find the number of islands on the map.
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1
For example, in the matrix above there are two islands.
Task: Write an algorithm which returns the number of islands in the matrix in a language of your choice. Provide it's time and space complexity.
Part 2: New Symbol and Maximization
Given a similar NxN matrix where 1 represents land and 0 represents water, let us add an additional symbol "X" which represents land or water -- you get to make the choice.
0 0 0 0 1 0 0 0 0 0 X 1 X 0 0 X
Task: Verbally discuss an algorithm which maximizes the number of islands given the special symbol "X" described above which you choose to set to 1 or zero. Provide it's computational complexity.
Part 3: Quantum Symbol Pairs
Given an similar NxN matrix where 1 represents land and 0 represents water and X represents "your choice of water or land", let us introduce a new concept: The Quantum Pair.
We denote quantum "pairs" as a tuple of identical symbols Q_i..sqrt(n), where subscript i represents the pair number. The elements of any entangled pair will contain the same pair number, but will exist in disparate matrix cells. For example in the matrix below note the quantum pairs Q1 and Q2.
Q1 0 0 Q2 1 0 0 Q1 0 Q2 1 1 0 0 0 1
For any quantum pair you must make a choice: you make pick one symbol and make it either an island or water. The other symbol instantly becomes the opposite value so as not to upset the quantum nature of the islands matrix. Maximize the number of islands.
Task: Lead a cooperative discussion on an algorithmic solution to this problem optimized for the average case. The algorithm shouldmaximizes the number of islands given 0...sqrt(n) entangled quantum symbol pairs are uniformly distributed about the matrix. Discuss complexity and theory