Searching a 2D array of binary Data

I’m working on optimizing the structure of an optical metadevice. I have a randomly generated 2D matrix, where 0,1 represents the presence/absence of a hole. Each structure manipulates light in a different way, thus giving rise to a unique spectrum.

The problem I wish to solve is to maximize the efficiency of this structure. Given the large size of the solution space ($ 2^{100}$ in this case), it isn’t possible to simulate each structure. Is there any search method I could use to complete this optimization?

A General workflow would be:

  1. Generate a random hole structure
  2. Flip one or some bits (based on the optimization algorithm)
  3. Compute the spectrum
  4. Go back to step 2 and make decision based on the previously computed spectrum.

Here’s a link to a sample hole array.

Apologies for the vague statement of the problem. Thanks in advance!

Binary subtraction with numbers in 2’s complement

How can i perform binary subtraction of two numbers that are already in 2’s complement? I have to subtract 01010011 from 10100110,both numbers are in 2’s complement. I know that 10100110 is -90,and 01010011 is 83,so the result should be -173. So if i use 8 bits that means that there’s overflow. But i don’t get how can i perform the subtraction when both the numbers are in 2’s complement. If i just perform the subtraction i get the same number 01010011. How do i show the result and that there’s overflow?

Recurrence Relations for Perfect Quad Trees (same as binary trees but with 4 children instead of 2)

I have to write and solve a recurrence relation for n(d), showing how I arrive at the formula and solve the recurrence relation, showing how I arrive at the solution. Then prove my answer is correct using induction for perfect quad trees which are basically binary trees but with 4 children at each node rather than 2 and the leaf nodes in the deepest layer have no children. Nodes at precisely depth d is designated by n(d). For example, the root node has depth d=0, and is the only node at that depth, and so n(0) = 1

Does this mean it would be T(n)= 4T(n/4) + d ? then prove

I’m really confused and would appreciate any help or resources.

Does the heap property in the definition of binary heaps apply recursively?

The definition of binary heaps says that it should be a complete binary tree and it should follow the heap property where according to the heap property, the key stored in each node is either greater than or equal to or less than or equal to the keys in the node’s children.

Binary tree

In the above tree, the node with value 70 is greater than its parent 10 breaking the heap property. However, 70 is also greater than 40 and lies in the subtree of 40. Will we say that the heap property is also breaking at 40, even though 40 is greater than its two children 10 and 2?

Product of all nodes except for one in Binary Tree

Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node omitted. I am looking for a solution without divisions (i.e. integers can be zero).

One way to go about this I thought of is I can compute all possible partial products starting at the root. That is each node stores the product of the unique path from the root up this node ( but except the integer stored at that particular value ). Then for each leaf node I can walk up the path to the root node multiplying the integers on the way. At a given node before accumulating the node into the product I can multiply the product with the prefix product stored in the node.

It feels like I am doing a lot of redundant multiplications when visiting each path from a leaf to the root, since these paths potentially share a lot of nodes. Is there a way faster way to do this?

Delta rule for binary step function

I have a question of understanding about the Delta Rule:

Δwᵢ = (y – ŷ)*xᵢ

Why does x have to be multiplied again after the difference? If the input is 0, the product of w and x remains 0 anyway. Then it should not matter if the weight changes with an input of 0.

let us take the following example:

  • w_i = the ith weight of the weight vector
  • Δw_i = the change in weight w_i
  • y = the desired output of the neuron for the learning example
  • ŷ = the actual, calculated output for the learning example
  • x_i = the input

Step t:

  • Input (x) = 1 0 0
  • Random weights = 0.1 0.1 0.1
  • Scalar product –> 0.1
  • Step function outputs 1 –> ŷ = 1

BUT we want as output y = 0 So the weights have to be adjusted as follows:

Step t+1:

  • Δw_0 = (0 – 1) * 1 = -1
  • Δw_1 = (0 – 1) * 0 = 0
  • Δw_2 = (0 – 1) * 0 = 0

w_i(new) = w_i(old) + Δw_i

  • New weights: -0.9 0.1 0.1
  • Scalar product = -0.9
  • Output (y = 0)

You can totally skip the multiplication by x, can’t you? Because at the latest when the scalar product is created, the weight which is multiplied by x = 0 is still not included. So why multiply by x in the delta w?

Where is the theory about “binary toggling games”?

Let us — using parameters $ M, N$ and $ L$

  1. create an ordered set of size $ M$ of $ N$ -bit long vectors $ V$ and initialize them randomly: $ V_k[i] = b \sim Bin(n=1, p=0.5)\ \forall i \in \{0\ ..\ N-1\}, \forall k \in \{0\ ..\ M-1\}$ .

  2. create an N-bit long vector $ A_0$ and initialize it to ones.

  3. create an $ M$ -bit long vector $ S$ and initialize it randomly in the same manner as any $ V_k$ .

  4. for $ i$ from $ 0$ to $ M$ , if $ S[i] = 1$ , then $ A_i = A_{i-1} \oplus V_k$ , otherwise $ A_i = A_{i-1}$ , resulting in $ A_M$ after $ M$ steps

  5. present an agent/player with $ A_M$ together with all vectors $ V_k$ and make him return $ S$ or the set of indices of vector $ S$ where $ S[i] = 1$ . It follows that $ A_M \oplus V_{i_0} \oplus V_{i_1} \oplus V_{i_2} \oplus\ …\ \oplus V_{i_{last}} = A_0$ .

A simple example with $ N=4$ and $ M=3$ :

$ A_M = [0, 1, 0, 1]$ , $ V_0 = [1, 1, 0, 1]$ , $ V_1 = [0, 0, 1, 1]$ , $ V_2 = [0, 1, 1, 1]$

solution $ \rightarrow S = [1, 0, 1],$ because $ A_M \oplus V_0 \oplus V_2 = [1, 1, 1, 1]$

This problem occurs in many games I have encountered and never really gave it much thought, until now. For the purpose of this question, I have called it the “binary toggling game”.

What I wonder is:

  • what are “binary toggling games” really called
  • what is the theory being them: algorithms, their complexity (classes), edge cases, etc.

Could you please provide links? I hope they exist.

Amortized Analysis of Binary Counter and Dynamic Table together

Let m ≥ 2 be a fixed positive integer. Consider the following ADT. A state of the ADT is an m-tuple of integers (v1, v2, . . . , v_m). The ADT supports two operations:

• Increment(i) which increases the value of vi by 1.

• Max returns an index of the maximum value, that is it returns an i such that vi ≥ vj for all j.

I am designing a data structure for this ADT as a dynamic sized table Ti. Each entry of Ti stores single bit of vi. This allows each component to grow arbitrarily large because we can resize the table to get longer and longer as value grows.

Now, Suppose the Algorithm for Max is :

Max res ← 1 for i ← 2..m if (number represented in Ti) > (number represented in Tres) then res ← i end if end for return res end Max 

Now, Given a sequence of s operations and initial state (0,0,0,0..0). I want to do amortized analysis of this case and find the total time and amortized time.