## Looking for two-way communication/consensus/contract algorithm for use in marriage proposal

I am looking for some sort of communication or consensus algorithm with the following properties:

• Can be used with just two parties (and ideally doesn’t collapse to a trivial case with two parties)
• Requires each party to initiate some sort of communication to which the other responds (ideally in a binary way)
• Non-hierarchical
• Bonus points if it’s some sort of consensus, decision-making, or contract signing algorithm

Context: my boyfriend and I are planning on getting engaged soon. For various reasons, we would both like to propose to each other. The challenge is that we don’t want whichever proposal is second to feel like it was unnecessary. Since we’re both computer scientists, we figure there must be an algorithmic solution to this problem! So we are looking for a communication protocol/consensus algorithm/something else in that vein in which it is necessary for both parties to initiate and respond to a communication. We will be implementing the chosen algorithm verbally, not over an actual internet connection. In case you’re having a hard time picturing this, it would be kind of like how a lot of textbooks will have conversational English versions of the messages being sent under various communications protocols, e.g.:

Except we would replace “Hey. Can I talk to you?” with something more like “Will you marry me?”.

Before anyone asks, yes, this is entirely symbolic/for fun, but we feel that’s true of most aspects of getting engaged/married. And yes, we are nerdy enough that we will happily exchange random numbers with each other in public if that’s what the protocol (or its associated cryptography) demands.

Possibilities we’ve considered so far:

• TCP: This was our first thought, but it’s not a great fit. For connection establishment all the server sends is a SYN-ACK, which isn’t really satisfying either as a response to the first proposal or as the question being asked in the second proposal. The connection termination protocol seems like it would be weird to adapt to verbal communication.
• Dining cryptographers: Would be great (although we’d have to use 0 to mean yes, which is a little gross), except it falls apart with only two parties. So we’d have to include a third person (and give them veto power over our engagement). It would be perfect for a polyamorous engagement, though!
• Some sort of blockchain consensus algorithm: All the ones I’m aware of seem like they’d collapse to a trivial case with two parties (but I could be wrong about this)
• Some sort of contract signing algorithm: Probably the best option we’ve found so far. These are the closest to being designed to solve the actual problem that we have, but all the ones I’ve seen require some sort of trusted third party (we could make that work but it wouldn’t be ideal).

Does anyone know of an algorithm that is a better fit than these? Apologies if this is off-topic (I’m hoping it falls under “we do not hate fun”)!

## Is there a minimum color class cover algorithm for bipartite graphs?

Let $$G$$ be a bipartite graph with color classes $$X, Y$$. Is there an algorithm for determining a minimum set $$S \subseteq X$$ such that each $$y \in Y$$ is a neighbor of some $$s \in S$$?

Furthermore, are there any theoretical results related to this problem, such as bounds on the size of $$S$$ based on degrees of vertices and sizes of vertex neighborhoods?

I feel like this is a really basic problem, but I’m having trouble finding anything related to it. Any help would be appreciated. Thank you.

## How can I rewrite this algorithm in order to avoid endless loops?

I have the bellow algorithm which I wrote in order to loop through an dictionary array. which looks like: ["mediaX": AnyObject]

The problem is that sometimes, although it has only consistently happened with one post among hundreds, it will loop forever printing the error print statement. How could it be changed in order to make it more efficient or more safe?

for anyImage in snapshot! {          var mediaNumArrayOrderd = [Int]()          guard var imageUrlString = anyImage.value as? [String:AnyObject] else { return }         print("inside the anyImage22, ", imageUrlString)          var values = [AnyObject]()         var keys = [String]()         var Done = false         var j = 1          //The bellow algorithom sorts the array and stores the correct values to then loop through the above two arrays         while !Done {             for i in imageUrlString {                  if "media\(j)" == i.key {                     values.append(i.value)                     keys.append(i.key)                     print(i, " This is teh i for in if ")                     if imageUrlString.count == j {                         Done = true                         break;                     }                     j+=1                 } else {                     print("No,,.")                     print("There was an error when sorting the medias. Line 136 in the p2 VC")                     break                 }             }         }          ...//more code

## Assume we have an algorithm HC for HAMILTONIAN CIRCUIT. How is it possible to convert the HC algorithm to an algorithm HP for HAMILTONIAN PATH?

My understanding is that I have to use the algorithm for Hamiltonian Circuit to help solve the Hamiltonian Path problem.

My understanding is that we have to perform a reduction from Hamiltonian Path—> Hamiltonian Circuit (since we have an alg for Hamiltonian Circuit the reduction should be from Ham path—> Ham circuit)

But in contrast, the question says CONVERT the Ham Circuit algorithm to an algorithm to an algorithm of HP. Does this imply that the Ham Circuit problem should be reduced to the Ham Path problem?

Any guidance/feedback greatly appreciated.

## Finding recurrence relation for running time of an algorithm

I am pretty new to this, consider the following algorithm:

Calc_a(n):     if n ==1: return 1     else:     sum = 0     for i=1 to n-1:         sum = sum + calc_a(i)     return sum

So after running this algorithm a few times I see it basically finds the n’th element in a sequence defined by this recurrence relation:

$$a_n = \sum_{i=1}^{n-1}a_i$$

I need to find the recurrence relation for this algorithm running time per input. Walk me through it 🙂

Lets define running time as $$T(n)$$.
So the base case n=1 is $$O(1)$$ (theta?), as we just return 1.
Then we iterate (n-1) times , each time performing addition and calling the function on the current index, this is where I get confused.
I know how to deal with loops and recursion individually, not together.

My homework specifies that I should use constants rather than asymptotic notations. Does that means I should define the running time of Calc_a(i) as some constant?

## How to prove there are unreachable states in this bit flipping algorithm only for lengths $n=3k+2$?

This is similar to Bit flipping algorithm, but the algorithm is a little different. Specifically, we have bit string of length $$n$$, and we can choose any bit to flip and then we flip also the two surrounding bits, if there are any. So we can either flip three consecutive bits inside or flip the left-most/right-most two bits. For example for $$n=3$$ we can draw transitions between states in a graph:

Now if we make a graph for $$n=2$$, the graph splits into two non-connected isomorphic sub-graphs as shown:

The same occurs for $$n=2,5,8,11,14$$, so I assume it holds for $$n=3k+2$$. For other $$n$$‘s it is a graph with single connected component. Can we prove that the graph splits for $$n\equiv 2 \pmod 3$$?

My attempts:

I was trying to find some attribute that is invariant for the bit flipping and show that there are two states with this attribute being different (for $$n=3k+2$$ that is). This is easy for $$n=2$$ case as we can see that bits parity is always preserved. However the same does not work for $$n=5$$: as an example there are two states such as $$00100$$ and $$00010$$ that cannot be reached from one another, but bits have the same parity. There is probably some simple argument for this, but I don’t see it.

By the way here is a Python code that can be used to generate such graphs, it requires graphviz:

length=5  def flip(N, bit):     pattern = 3 if bit == 0 else 7 << bit-1     return (N ^ pattern) & ((1 << length)-1)  def binary(n):     return format(n, '0%ib' % length)[::-1]  from graphviz import Graph dot = Graph()  for v1 in range(2**length):     for b in range(length):         v2 = flip(v1, b)         if v1 <= v2:             dot.edge(binary(v1),binary(v2),str(b+1)+".") dot.render('graph_complete%i' % length, view=True)

## algorithm for correctly rounded floating point radix conversion

Is there any generic algorithm which implements a floating point radix conversion?

Lets say we have a $$p$$-digit FP number

$$A = \sum_{i=0}^{p-1} A_i \beta^{e-i}$$

in radix $$\beta$$ and with $$0 \leq A_i < \beta$$.

How do we find the $$A’_i$$, $$e’$$ values for the $$p’$$-digit base $$\gamma$$ FP number

$$A’ = \sum_{i=0}^{p’-1} A’_i \gamma^{e’-i}$$

closest to $$A$$?

Also is an intermediate arbitrary precision FP calculation really necessary? (as in the function strtod in David Gay’s dtoa.c)

## Confused about constructing the “failure table” in Knuth-Morris-Pratt algorithm

I’m trying to learn how the “failure table” is constructed in the Knuth-Morris-Pratt algorithm since it seemed nontrivial to me that you could do it in $$O(k)$$ time (where $$k$$ is the length of the pattern, $$W$$). To be clear, we let the failure table $$T$$ be a length $$k$$ array where $$T[i]$$ is the length of the longest proper prefix of $$W$$ which is also a suffix of $$W[1]\cdots W[i]$$.

I was trying to understand it better by reading the following code:

vector<int> T(pattern.size());     T[0] = 0;     int j;     for (int i = 1; i < pattern.size(); i++) {         j = T[i - 1];         // Find largest j s.t. T[:j+1] == T[i-j:i+1]         while (j > 0 && pattern[j] != pattern[i]) {             j = T[j - 1];         }         T[i] = (pattern[j] == pattern[i]) ? j + 1 : j;     }     return T;

The part I’m confused about is why pattern[j] == pattern[i] is enough to guarantee that $$T[i] = j + 1$$. I was trying to prove this inductively but have had no luck. I’ve phrased the problem as follows:

Suppose $$W[1]\cdots W[T[i – 1]] = W[i – T[i – 1]]\cdots W[i – 1]$$. If $$W[i] == W[j]$$, then is it true that $$W[1]\cdots W[j] == W[i – j + 1]\cdots W[i]$$?

I can’t make any headway with this, nor can I see why it should be true. It still seems like we have to check $$W[\ell] = W[i – j + \ell]$$ for all $$\ell = 1…j$$. I can’t figure out how to use the inductive hypothesis to prove this result. Do I have to use strong induction (where we assume all prior steps are true and not just the previous step) to prove this?

## Question is about a paper “A Block-sorting Lossless Data Compression Algorithm” by M. Burrows and D.J. Wheeler

In the paper A Block-sorting Lossless Data Compression Algorithm by M. Burrows and D.J. Wheeler Link. On page number 5. please describe this line

If the original string $$S$$ is of the form $$Z^p$$ for some substring $$Z$$ and some $$p > 1$$, then the sequence $$T^i[I]$$ for $$i = 0,…., N – 1$$ will also be of the form $$Z’^p$$ for some subsequence $$Z’$$.

## Hard Sudoku Puzzle Creation Algorithm in quadratic time

To avoid backtracking, I’ve generated an algorithm with some research into a polynomial time algorithm.

Overall, I’m looking for constructive-criticism, improvement, recommendations, etc.

I’ve found out that if I control all parameters in the creation of a Sudoku puzzle I can generate the puzzle from a solution in quadratic time.

Here’s the summary of the entire description of the algorithm. Before you get into your reading.

Step 1 Follow the grid and puzzle generation method(mentioned at the end of the question).

Step 2 Enter for input l to generate a solution before generating the puzzle [8,5,9,6,1,2,4,3,7]

Step 3. Now generate the puzzle Example- Take the output of the complete grid and compare to the world’s hardest sudoku puzzle and arrange the elements in some algorthim(paper or computer) to match the below.

n = 0 l = input('Enter the first solved box to get a correct solution')  note when script asks for input you must write it like this  [1,2,3,4,5,6,7,8,9]  indices = [] for i in xrange(1, 1+len(l)):         indices.append(n % i)         n //= i         indices.reverse()          perm = l for index in indices:         perm.append(l.pop(index))         print(perm)

2nd part of algorthim not yet implemented in the script

To convert the result(which is an horizantal solution) into human readable format follow this method.

You take the first three rows from the output

[1,2,3,4,5,6,7,8,9]  [1,2,3,4,5,6,7,8,9]  [1,2,3,4,5,6,7,8,9]

and do this…. Line them up one by one side by side in this order and I’m seemingly always getting correct grids!!

Yeah, I know this isn’t in right order but just to show illustration

[1,2,3]

[4,5,6]

[7,8,9]

[1,2,3]

[4,5,6]

[7,8,9]

[1,2,3]

[4,5,6]

[7,8,9]

Here’s an actual output of a solution in horizontal format.

[9, 6, 1, 2, 4, 3, 7, 8, 5]  [6, 1, 2, 4, 3, 7, 8, 5, 9]  [1, 2, 4, 3, 7, 8, 5, 9, 6]  [2, 4, 3, 7, 8, 5, 9, 6, 1]  [4, 3, 7, 8, 5, 9, 6, 1, 2]  [3, 7, 8, 5, 9, 6, 1, 2, 4]  [7, 8, 5, 9, 6, 1, 2, 4, 3]  [8, 5, 9, 6, 1, 2, 4, 3, 7]  [5, 9, 6, 1, 2, 4, 3, 7, 8]

Following the aforementioned method.

You get a correct Sudoku grid. (The checker says its correct every time I’ve ran it) I’ve taken out some elements to see if there’s a puzzle with 1 solution and behold.

[9 6 1][2 4 3][7 8 5]  [2 4 3][7 8 5][9 6 1]  [7 8 5][9 6 1][2 4 3]  [6 1 2][4 3 7][8 5 9]  [4 3 7][8 5 9][6 1 2]  [8 5 9][6 1 2][4 3 7]  [1 2 4][3 7 8][5 9 6]  [3 7 8][5 9 6][1 2 4]  [5 9 6][1 2 4][3 7 8]

Pseudo-code

Python2.7

>>>World-s hardest Sudoku puzzle converted in vertical format  800000000003600000070090200050007000000045700000100030001000068008500010090000400   Manipulating your generated grid to match index by index of hardest puzzle. (This is making sure there should only be 1 solution)   961243785612437859124378596243785961437859612378596124785961243859612437596124378   Poof!! string manipulation done in linear time.  900000000002400000020070500040005000000059600000500020005000043009600030090000300

(warning manual typos will happen if done by hand)

Converting into correct format with one solution only(supposedly)

— Solve this. Warning I’ve probably got typos.

900 040 050 000 005 000 000 000 430  002 000 096 400 000 000 000 059 300  020 005 900 070 000 003 500 200 000

Since, I’ve made sure that the grids are always correct. I took a screenshot of Sudoku checker. Generating Complete Grids. Even the puzzles are seemingly always generated correctly in quadratic time.

Not enough testing has confirmed if every puzzle generated from this algorithm is correct, but every grid has been correct so far if you actually follow the method correctly.

http://www.birot.hu/sudoku.php