texts: How to evaluate all possible groups of adjacent tiles in 2D array?

texts:
I'm working on a tile based game idea in Javascript. It's a math puzzle game where players move around tiles with numbers on them, and the goal is to connect groups of tiles that have a sum of certain goal number, for example 5 or 7 or 9.

However, I'm stuck on the algorithm to detect these sum groups. I know how to do a flood fill algorithm using recursion to detect a group of adjacent tiles, like in the same game. But I don't know how to iterate through all the possible permutations of possible groups, and what is the best way to approach this?

Because the problem is that adjacent tiles form a group, but within that group of tiles there are many possibilities for sub groups. See tiles example below

Tile letters     Contains numbers    Represented as graph
+---+---+---+    +---+---+---+
| A | B | C |    | 1 | 5 | 2 |       1---5---2
+---+---+---+    +---+---+---+       |   |
| D | E | . |    | 2 | 1 | . |       2---1
+---+---+---+    +---+---+---+       |
| F | . | . |    | 4 | . | . |       4
+---+---+---+    +---+---+---+

So the group is all the tiles A though F, and a subgroup could be A, B and E (1+5+1) but also A, D and F (1+2+4). But A, C and F is not a possible group because those tiles are not adjacent. I suspect it could maybe be approached like it's a graph problem. But then I still don't know how to handle the many possible circular nodes.

So my question is; How to systematically go through and evaluate all possible permutations? Is there an algorithm for something like this? Or can someone explain how to approach this problem?

EDIT:
I've put my code in the jsfiddle in the link below. It uses flood fill from a starting tile, in the example tile with nr 2. Then for each cell it counts to 15 and uses the bits of that counter to flood-fill to the 4 adjacent tiles (up,down,left,right). However it doesn't work properly because it doesn't consider branching paths. For example, in the jsfiddle example the combination 3-2-4 is never evaluated.
https://jsfiddle.net/wu6p49r2/

I know how to do it by hand, see examples below. But what would the algorithm look like, to systematically gather these possible adjacent combinations starting at A?

Tiles ex.1    Tiles ex.2        Tiles ex.3
+---+---+     +---+---+---+     +---+---+---+
| A | B |     | A | B | C |     | A | B | C |
+---+---+     +---+---+---+     +---+---+---+
| D |         | D | E |         | D | E |
+---+         +---+---+         +---+---+
                                | F |
                                +---+
All possible adjacent combinations,
starting at A:

A             A                 A
A-B           A-B               A-B
A-D           A-B-C             A-B-C
A-B-D         A-B-E             A-B-E
              A-B-C-E           A-B-C-E
              A-B-E-D           A-B-E-D
              A-B-C-E-D         A-B-C-E-D
              A-D               A-B-E-D-F
              A-D-E             A-B-C-E-D-F
                                A-D
                                A-D-E
                                A-D-F
                                A-D-E-F


texts: Protocols for "almost equality" with one-sided error

texts:
In the well-known communication task EQUALITY, Alice has a string $x$ of $n$ bits, Bob has a string $y$ of $n$ bits, and their task is to determine whether $x = y$. In the public coin model, there is a probabilistic protocol which uses 2 bits, is always correct when $x = y$, and is correct with constant probability when $x \neq y$ (in fact, with probability 1/2).

The following generalization came up in a recent question. In the task $k$-HAMMING (where $k$ is a constant parameter), Alice and Bob hold strings $x,y$ of length $n$ bits, and their task is to determine whether the Hamming distance between $x$ and $y$ is at most $k$. EQUALITY is the case $k=0$.

When $k = 1$, we have the following nice protocol, which uses 5 bits, is always correct in the Yes case, and is wrong in the No case with probability at most 5/8. Alice and Bob agree on two random strings $z,w \in GF(3)^n$. Alice and Bob each compute the inner product of $z,w$ with their input, and compare the values. If both are equal or both are different, they output Yes, and otherwise they output No.

If the Hamming distance between $x$ and $y$ is $d$ then the probability $p_d$ that $\langle z,x-y \rangle = 0$ is $1/3 + (2/3)(-1/2)^d$. We have $p_0 = 1$, $p_1 = 0$, and $1/4 \leq p_d \leq 1/2$ for $d \geq 2$. This shows that the error probability when $d \geq 2$ is at most $p_d^2 + (1-p_d)^2 \leq (1/4)^2 + (3/4)^2 = 5/8$.

When $k > 1$, a similar protocol works since using enough samples we can estimate $p_d$ to any required accuracy. However, the resulting protocol no longer has one-sided error. One-sidedness can be recovered in many ways at the cost of using $O(\log n)$ bits of communication.

  Is there a one-sided error protocol for $k$-HAMMING for $k \geq 2$ using $O(1)$ communication?


texts: Number of combinations without given pairs

texts:
Given a set of elements {e1, e2, ... en}, a set of pairs of these elements (each element may be present in several pairs) and a number k.
I need to count how many combinations of size k exist which not include any pair?
For example: if there only one pair {e1, e2} result in number of all combinations without elements e1 and e2. It may be counted in constant time: $$C^k_n - C^{k-2}_{n-2}$$
This task can be solved with the naive algorithm on python:
def combinations_without_pairs(elements, pairs, k):
    def iterable_len(iterable):
        return sum(1 for _ in iterable)

    def not_include_pairs(combination):
        for pair in pairs:
            if pair[0] in combination and pair[1] in combination:
                return False
        return True

    return iterable_len(filter(not_include_pairs, itertools.combinations(elements, k)))

But this algorithm is ineffective: it requires iterating over each element combination and each pair.
Is there any way to solve this problem with better complexity? At least reduce the impact of a big count of elements and pairs?
I want to find an algorithm with the lowest time complexity.


texts: Prove that regular expression is unambiguous

texts:
I've got following definition:

Function $f$ is a valid mapping of word $w$ to regular expression $R$, if any of following conditions is true:

$R = w$ and $f$ is the identity or $R = \epsilon$ and $w = \epsilon$;
$R = R_1 + R_2$ and $f$ is a valid mapping of $w$ to $R_1$ or $f$ is valid mapping of $w$ to $R_2$;
$R = R_1R_2$, and $w$ can be written as $w_1w_2$ such that $f$ limited to $w_1$ is a valid mapping of $w_1$ to $R_1$, and $f$ limited to $w_2$ is a valid mapping of $w_2$ to $R_2$; or
$R = S^*$ and $w$ can be written $w = w_1w_2\dots w_k$ for some $k \geq 0$ and, for all $1\leq i\leq k$, $f$ limited to $w_i$ is a valid mapping of $w_i$ to $S$.

A regular expression $R$ is deterministic (unambiguous) if, for every $w\in L(R)$, there exists exactly one valid mapping from $w$ to $R$.

I need to prove that the regular expression $R = 0^*(11^*000^*)^*11^*01(1+0)^*$ is deterministic. I think that first I should prove that there exists a valid mapping for every word $w$ to $R$ and then assume that there's a different mappings and lead to a contradiction. But I've got problems with details (especially with the second part of the proof).


texts: Is there an isomorphism between (subset of) category theory and relational algebra?

texts:
It comes from big data perspective. Basically, many frameworks (like Apache Spark) "compensate" lack of relational operations by providing Functor/Monad-like interfaces and there is a similar movement towards cats-to-SQL conversions (Slick in Scala). For instance, we need natural join (assuming no repetitions on indexes) for element-wise multiplication of vectors from SQL-perspective, which could be considered as zip + map(multiply) (Spark's MLib, however, already has ElementwiseProduct) in Category Theory's applications.

Simply saying (following examples are in Scala):

the referenced subcase of join can be thought as applicative functor (over sorted collection), which in its turn gives us zip: List(1,2,3).ap(List(2,4,8).map(a => (b: Int) => a * b)) --> (List(1,2,3) zip List(2,4,8)).map(x => x._1 * x._2). Moreover, we can induce it to some other joins, assuming some preprocessing (groupBy operator or just surjection, or generally - an epimorphism).
other joins and selection can be thought as monad. For instance, WHERE is just: List(1,2,2,4).flatMap(x => if (x < 3) List(x) else List.empty) --> List(1,2,2,4).filter(_ < 3)
data itself is just ADT (GADT too?), which in its turn looks like a simple Set-category (or more generally speaking - Cartesian-closed), so it should (I suppose) cover Set-based operations (due to Curry-Howard-Lambek itself) and also operations like RENAME (at least in practice).
aggregation corresponds to fold/reduce (catamorphism)

So, what I'm asking is can we build an isomorphism between (maybe subset of) category theory and (the whole) relational algebra or is there something uncovered? If it works, what exact "subset" of categories is isomorphic to relalgebra?

You can see that my own assumptions are quite broad while formal solutions like Curry-Howard-Lambek correspondence for logic-cats-lambda are more precise - so actually, I'm asking for a reference to an accomplished study (that shows a direct relationship) with more examples in Scala/Haskell.

Edit: the accepted answer made me think that I went too far representing joins and conditions as a monad (especially using an empty value that effectively instantiates FALSE), I think pullbacks should suffice at least for relalgebra subset of SQL. Monads are better for higher order (nesting) stuff like GROUP BY, which isn’t part of relalgebra.


texts: Show that the following algorithm doesn't always find the optimal matching

texts:
Consider the following algorithm for the maximum matching problem:

Sort all nodes by their $\deg(v)$
Take the node with minimal $\deg(v)$
Take a random edge $(u,v)$ $\in$ $E$
Add $(u,v)$ to $M$
Delete all edges of $u$ and $v$ in $E$

I have to show that the algorithm isn't correct for undirected graphs with maximum degree 3. (It does find the maximum matching if the maximum degree is 2.)

To prove that the algorithm does not find a maximal matching for a graph $G$, I have to give a counterexample.

My problem is that I am drawing and drawing graphs, but the algorithm is always able to find the optimal matching. Could somebody help me to find a graph where the algorithm cannot find the optimal matching?


texts: Intuition behind balancing of link/cut data structure

texts:
My question concerns link/cut tree structure after an access operation. I am assuming an implementation with splay trees. As far as I can tell, once you access a node v and splay it to the root, it no longer has a preferred child and therefore no longer has a right sub-tree. Furthermore, you move this tree up to the root of the entire structure, thus the link/cut tree is unbalanced at the root.

My question is about intuition. It seems very counter-intuitive to purposefully unbalance the tree at the root. I understand in the amortised sense, unbalanced trees are perfectly fine but I cannot understand the intuition behind the choice. Is the gain you get from having the most recently accessed item at the root outweigh the fact that you only have 1 child? Is there something else I am misunderstanding? Are there other examples of structures were a counter-intuitive choice is still a benefit?


texts: computational and messages complexity equivalence between STP and Leader election

texts:
I'm doing a presentation for a distributed systems and networks course.
I'm using the book "Design and Analysis of Distributed Algorithms", written by Nicola Santoro. This book contains the proof of equivalence between SPT and leader election but there are some points that I don't understand at all.

Santoro uses this method:

We create an algorithm $B$ that solves SPT as follows.
  Let $A$ be an universal election algorithm. At the first step, we execute $A$, and at the second step we use the leader elected in first step to use the protocol "Shout", (which constructs an ST because the leader is the single initiator). This takes exactly $2m$ messages.
So the message complexity of $B$ is given by
$$M[B]=M[A]+2m\,.\tag1$$
At this point because we have previously found a lower bound for $M[SPT]$ ($M[\mathrm{SPT}]\geq \Omega(m)$)
Santoro says, "with at most $O(m)$ additional messages, any election protocol can
be made to construct a spanning tree; as $\Omega(m)$ messages are needed anyway" therefore

$$M[\mathrm{SPT}]\leq M[\mathrm{Elect}]\,.\tag2$$

On the other side it's easy to see that we can use a SPT protocol $C$ to create a Spanning Tree and then with $O(n)$ additional messages (the cost of notification from the root to the leafs it's exactly $n-1$) simulate an Election algorithm $D$. we obtain that:

$M[D]=M[C]+O(n)\,.\tag3$

now santoro says:"In other words, the message complexity of Elect is no more than that of Elect plus at most another $O(n)$ messages; as election requires more than $O(n)$ messages anyway" therefore

$$M[\mathrm{Elect}]\leq M[\mathrm{SPT}]\,.\tag4$$

combining equation $(2)$ and $(4)$ we obtain that the problems are computationally equivalent and that they have the same complexity (in terms of messages).

what i do not understand are the conclusion $(2)$ and $(4)$.

the data given are: $$1) M[\mathrm{Elect}]=\Theta(m+ n\log n)$$;
$$2) M[\mathrm{SPT}]\geq \Omega(m)$$;
$M[X]:=$ message complexity of algorithm $X$


texts: Remove vertices to get k-connected components

texts: In a graph, I need to remove some vertices in order to get at least k-connected components. The no. of removed vertices should be low. Is there a heuristic that I could follow for this?


texts: The law of excluded middle and decidability

texts:
I will divide my question in two parts. The first part I am sure that there is a objective answer, but I am not sure about the second part.

First part:
Is it all (decisions) problems trivial to prove decidable after assuming the Law of Excluded Middle (LEM)? e.g. There is no problem hard to prove decidable after assuming LEM.

Second part:
Does make any sense to agree with a non-constructive proof that a problem is decidable?

Edit:

I will give an example of what I meant in the first part.

Consider the problem of deciding the eveness of a number.
If I assume LEM, this problem can be easily proved decidable. There was no need to do the "hard" proof of building the decider.

Here is the demonstration in Coq of that:

Inductive even : nat -> Prop :=
| ev_0 : even 0
| ev_SS : forall n, even n -> even (S (S n)).

Axiom LEM : forall P : Prop, P \/ ~ P.

Lemma even_dec : forall (n : nat), even n \/ ~ even n.
  intros.
  apply LEM.
Qed.

The first part of my question was basically asking if this is always the case.


texts: How do we know that Icosoku always has solutions?

texts:
This is a continuation of a question I asked here. The puzzle Icosoku is now described by Wikipedia as: "The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-triangular snap-in tiles with black dots and 12 yellow pins for the corners. The pins are printed with the numbers from 1 to 12, and the triangular tiles have up to three dots in each of their corners. The object of the game is, for any arrangement of the pins, to choose the positions and orientations of the triangles so that the total number of dots on the five joining corners of each pin equals the number of the pin. The manufacturer asserts that there is a solution for each pin arrangement. The puzzle is shipped in a solved state. The pins are not suitable for children under three, but this toy is otherwise suitable for all ages."

My question is how can one prove that there is a solution for each pin arrangement, as the manufacturer asserts? There are 12 factorial ways of arranging the pins (less by a factor of 1/120 if one considers the symmetry of the icosahedron), so using brute force to prove this might be a bit challenging.


texts:
$A(x)$ is generating function of $\{a_n\}_{n=0}^{\infty}$ and $B(x)$ is generating function of $\{b_n\}_{n=0}^{\infty}$, what is
$$A(x^2)+xB(x^2)$$?


texts: How to find a nearly-optimal covering of a set using SAT?

texts:
I have recently started thinking about application of SAT in solving different problems and how I can encode those problems into a SAT problem.

I think one of the interesting problems where SAT solvers can be used is finding a minimal representation for a logic expression. However, I have trouble encoding the problem into a SAT problem.

In very old representations of an n-input logic circuit, three sets F, R, and D are defined. F represents the ON-set, which corresponds to permutations of input that cause a one in the output. R is the OFF-set, which corresponds to permutations of input that cause a zero in the output. Finally, D is the DON'T CARE-set which corresponds to permutations of input where output is not specified (could be set to either one or zero during optimization).

The objective is to find a minimal conjunctive normal form (CNF) that has the minimum number of clauses and each clause has the minimum number of literals. This CNF should cover all elements of F and may potentially cover some elements of D, but should not cover any elements of R.

For example, assume that a 3-input function is defined in the following way:

A B C | Y
---------
0 0 0 | 0
0 0 1 | 0
0 1 0 | 1
0 1 1 | 1
1 0 0 | -
1 0 1 | -
1 1 0 | -
1 1 1 | -

where A, B, and C are inputs, Y is the output, and a - determines a don't care output.

In this problem, a minimal CNF that meets the objective is O = B, because whenever B is true, the output is either true or don't care, but never false. Without having the DON'T CARE-set, a minimal representation would be O = ~A B, but DON'T CARE-set has allowed a more compact representation.

Is there a method to encode this problem as a SAT problem where inputs are F and R?


texts: How to find Maximum perimeter of rectangle in a grid with obstacles? (Dynamic Programming)

texts:
Can someone tell me what am I doing wrong?

Problem: https://codeforces.com/contest/22/problem/B
Editorial: https://codeforces.com/blog/entry/507 ( I followed the DP solution O((n*m)^2) )

Eg:
00001
00000
10100     //ans is 12

####1
####0
10100

My approach: rectangle with coordinates (x1, y1, x2, y2) is correct if and only if rectangles (x1, y1, x2-1, y2) and (x1, y1, x2, y2-1) are correct, and board[x2][y2] = ‘0’.

ie: dp[x1][y1][x2][y2]=(dp[x1][y1][x2-1][y2] && dp[x1][y1][x2][y2-1] && (board[x2][y2]==0))

If it is correct then find it's perimeter (perimeter = 2*(x2-x1+y2-y1+2)) ie ans=max(ans,perimeter)
And dp[x1][y1][x2][y2]=1 for all i,j when board[x2][y2]==0. Because from point p1 to point p1, ie the same point always have a perimeter is the base case.


texts: What is the name of this positive integer set data structure?

texts:
Google is failing me, so here goes:

The data structure is used to describe a set of positive integers.
It works conceptually, by keeping track of disjoint ranges [a,b) on the number line.
These ranges are stored, in a sorted manner. For two consecutive ranges [a, b), [c, d) the invariant is that a < b < c < d.
The ranges are stored flat in an internal array, meaning that for the ranges [a, b), [c, d) the internal representation is [a, b, c, d].
To look up if an integer x belongs to the set, we perform a binary search. If x is found in the array at an even position, x is a member; if x is not found in the array, but can be inserted at an odd index while preserving order, it is also a member. Otherwise x is not a member.
The internal array does not necessarily contain an even number of elements; if there is an odd number of elements, the last range is open-ended above. [a, b, c] is the set [a,b) ∪ [c,∞)
Conceptually you start excluding numbers up from zero until you reach the first number in the array, then you include numbers up until the second number of the array, then you exclude until the third, include until the fourth, etc.
Union of a collection of sets is made by iteratively taking the least element from the set with the smallest least element. If that element used to occupy an even index, we increment a counter, if it used to occupy an odd index, we decrement. Whenever the counter moves away from zero, or falls to zero, we include the just-removed element in the new array, otherwise we discard it.
Complement of a set is computed by inspecting the first element of the array. If it is zero, remove it, it it is not zero, prepend zero.
This data structure is often used to store information about Unicode properties, as it very compactly describes consecutive ranges of Unicode code points.

What is the name of this beast?


texts:
Diameter of the tree is defined as a long path or route, between any two nodes in a tree. The path may or may not goes through the ROOT.

Print the Longest leaf to leaf path in a binary tree and its length

I worth an algorithm that calculates the diameter in Swift:

func diameter() -> Int {
 return diameterHelper(root).Diameter
}

typealias HeightAndDiameter = (Height: Int, Diameter: Int)

private func diameterHelper(node: TreeNode<T>?) -> HeightAndDiameter {

   guard let node = node else {
     return HeightAndDiameter(Height:0, Diameter:0)
   }

   let left  = diameterHelper(node.left)
   let right = diameterHelper(node.right)

   let height   = max(left.Height, right.Height) + 1
   let diameter = max(left.Height + right.Height + 1, max(left.Diameter, right.Diameter))

   return HeightAndDiameter(Height: height, Diameter: diameter)
}

I have tried to adapt this algorithm, but it doesn't work for all the cases.

  func diameterPath() -> [T] {
    return diameterPathHelper(root).Path
  }

  typealias HeightAndDiameterAndPath = (Height: Int, Diameter: Int, Path: [T])

  private func diameterPathHelper(node: TreeNode<T>?) -> HeightAndDiameterAndPath {

    guard let node = node else {
      return HeightAndDiameterAndPath(0, 0, [])
    }

    let left  = diameterPathHelper(node.left)
    let right = diameterPathHelper(node.right)

    let height = max(left.Height, right.Height) + 1

    if left.Height + right.Height + 1 > max(left.Diameter, right.Diameter) {
      let currentDiameter = left.Height + right.Height + 1
      let path = left.Path + [node.data] + right.Path
      return HeightAndDiameterAndPath(height, currentDiameter, path)

    } else {
      if left.Diameter > right.Diameter {
        return HeightAndDiameterAndPath(height, left.Diameter, left.Path)
      } else {
        return HeightAndDiameterAndPath(height, right.Diameter, right.Path)
      }
    }
  }


texts: What do "JAMZ", "JAMN", and "JMPC" stand for in Mic-1?

texts:
I am wondering what do JMPZ, JMPN, and JMPC stand for in Tanenbaum's Mic-1 architecture. I know that MPC, the control store’s memory address register, stands for "MicroProgram Counter", but what does J mean? Likewise, there are 1-bit flip-flops where the values of N and Z are latched. The book says that if JAMN is set, the 1-bit N flip-flop is ORed into the high-order bit of MPC. Similarly, if JAMZ is set, the 1-bit Z flip-flop is ORed there. If both are set, both are ORed there. Effectively, this changes the address of the next instruction to be executed. So, it looks like J has something to do with "jump", but I'm not quite sure that's the case. The book does not spell out the names anywhere, just abbreviations. I also assume that N has to do with "negative", and Z with "zero", but those are just wild guesses.
Here is the Mic-1 microinstruction format:

Here is the Mic-1 block diagram:


texts: If we allow a database, what complexity class it is?

texts:
Let we have some problem $A$. Input length is $n$. Now we write a database that will store info about some positive instances of problem $A$. For every $n$ size of $n^{th}$ sector of DB is $O(f(n))$. $f(n)$ is some function.

Then we assume that some solver for problem in complexity class $C$ (for example, $GI$) can use this DB to solve the problem $A$. Can we say that $A\in C/f(n)$ ($C$ solver with advice of size $f(n)$)?


texts: If L is a regular language, then the particular L′ is also regular?

texts:
Show that if $L ⊆ Σ^∗$ is a regular language then the following language is also regular:
$$L' = \{w\mid ∃x, y ∈ Σ^∗ : w = xy ∧ yx ∈ L\}$$
Can you give me a hint how to solve that?


texts: G1, G2, H1, H2 are submatrices of the generator and parity check matrices of a code as described below. Can G1 * H2' and G2 * H1' both be all zeroes?

texts:
$ G $ and $ H $ are the generator and parity check matrices respectively of a linear block code.

Let $ G_1 = G(:, 1:n-s) $ (Matlab style representation of sub matrices). That is, $ G_1 $ is equal to the first $ n-s $ columns of $ G $, and $ G_2 = G(:, n-s+1:n) $. Let $ H_1 = H(:, 1:s) $ and $ H_2 = H(:, s+1:n) $, where $ s \in \{1, 2, ... n-1\} $; it represents the number of columns in $ G_2 $.

Is it possible for $ G_1 H_2' $ and $ G_2 H_1' $ both to be all zeroes?


texts: Implementation-level of a Turing machine that accepts a specific language

texts:
I'm trying to figure out a way to implement this kind of a Turing machine that accept the following language:

$$\Sigma = \{ 0,1,2 \}, \quad\quad
L(A) = \{ abc \mid a=b \land c = a^R \}$$

I was thinking of a 3-tape Turing machine or using $\#$ symbol that separates the $a$, $b$ and $c$, but I'm struggling for the $c$ part.

I only need Implementation-level or the way it works.


texts: Worst case using the first fit $2$-approximation for the bin packing problem

texts:
I am with the phone so I would be more verbose when I will have a pc on hand, if you desire.

The first fit algorithm for approximating the bin packing problem (NP-hard) is a $2$-approximation for the optimum. Can you show me a concrete worst case showing that $2$ is a good (or bad) extimate for the bound?


texts: Time complexity of kruskal using array data structure

texts:
I was going through MST(minimum spanning tree) algorithms in a given undirected graph. By using the disjoint data structure It is fairly easy. All I have to do follow these steps:

Sort the edges as per there edge weights. O(ElogE)
And then select edges one by an check by the union and find algorithm if they form a cycle or not. Time for this step for the single edge will be O(logv) so for E edges it will be O(ElogV).

Time complexity according to this implementation is O(ElogE)+O(ElogV)

For Desnse graph E=O(V^2) so time is O(ElogV^2) + O(Elogv) = O(Elogv)

But now the question is How to implement Kruskal using array data structure.
From above algorithm step, 1 will remain the same So time for sorting edges will be O(ElogE)

But how to implement the second step using array data structure without using Disjoint-set data structure?

If I store each set of disjoint set in an array then the second step will take O(V) time for each edge. So total time will O(EV) for the second step.
So total time for Kruskal using array data structure will be O(ElogE)+O(EV).

But questions in the below link does not have this option where I am wrong in above steps?

https://gateoverflow.in/92864/kruskals-mst


texts: if $DSPACE(\log^2n) \subseteq NTIME(n^2)$ is $DSPACE(\log^3n) \subseteq NTIME(n^2\log n)$?

texts:
I am trying to prove that if $DSPACE(\log^2n) \subseteq NTIME(n^2)$ then $DSPACE(\log^3 n) \subseteq NTIME(n^2\log n)$ using padding, but I'm not sure if the claim is correct, or how to do the padding.

I tried to create for $L \in DSPACE(\log^3 n)$ the language $L_{\mathrm{pad}} = \{ x\#^{\log^3(|x|)-|x|}\mid x \in L\}$ and then show that $L_{\mathrm{pad}} \in DSPACE(\log^2 n)$ but I am not sure that this is right.

From there, I think that the rest is just a standard padding argument proof.


texts:
What is the time complexity of this loop?

k=1
for(j=0;j<=n;j+=k)
    k++;

Is it $O(n)$ as we are increasing $j$ linearly?


texts: How to conceive a Turing machine that is the intersection of the languages of two Turing machines?

texts:
We have $ M = (Q,Σ,Γ,δ,q_0,q_a,q_r) $ and $ M′= (Q′, Σ , Γ′, δ′,q_0′,q_a′,q_r′)$.
We want to construct a standard Tm that recognize L(M) ∩ L(M′). How do I go about it? I don't have much more information than this. Anything to get started would be appreciated.


texts: Proof of SAT is randomly reducible to UNIQUE-SAT

texts:
I am asking for help to explain some crucial points of the central lemma and it's proof of famous paper NP is as easy as detecting unique solutions by L.Valiant and V.Vazirani.
The proof can be found in the section 2. The proof of the paper.
The idea of the lemma: lemma shows that there is a randomized polynomial - time reduction from SAT to Unique-SAT. Lemma uses GF[2] inner product with polynomial few {0,1} vectors.
Problem in general: I have some difficulties in understanding the definition of the lemma and in usage of GF[2] for proving the lemma.
Specific questions:
Following is the number of citations from the paper with relevant question to the citation.

Lemma 2.1. If $f$ is any CNF formula in $x_1,...,x_n$ and $w_1,...,w_k \in \{0,1\}^n$,

Q:I think $x_1,...,x_n$ are literals, but what are $w_1,..,w_k$? Are they literals or something else? If yes, why to distinct between them and $x$ literals.
A:$w_1,..,w_k$ are the truth assignments.

then one can construct in linear time a formula $f'_k$ whose solution $v$ satisfy $f$ and the equations $v\cdot  w_1=...=v\cdot w_k=0$. Furthermore, one can construt a polynomial-size CNF formula $f_k$ in variables $x_1,...,x_n,y_1,...y_m$,

Q: $x_1,...x_n$ are unknown literals, how can we construct $f_k$ with unknown literals and where $y_1,...,y_m$ came from?

for some $m$ such that there is a bijection between solutions of $f_k$ and $f'_k$, defined be equality on the $x_1,...,x_n$ values.
Proof: It is sufficient to show the lemma for $k=1$. Then, $f'_k$ is
$f \wedge (x_{i_1} \bigoplus x_{i_2} \bigoplus ... \bigoplus x_{i_j} \bigoplus 1)$

Q: this is the most vague point, how do we come to the such construction of $f'_1$ and why showing only $f'_1$ sufficient for the proof.
I hope you forgive me for my naivety. I will appreciate any hint in accordance to the above questions.


texts:
I think of type as a range of values that the variable can take whereas the rest is known constant or does not matter. Variables (instances or objects), which share common properties, are considered to belong to the same type/kind/class. That is, the type properties are constant across the type. The type is actually a common property of a class of objects (variables). The variables have a variable part, which may change, making them flipping from one subtype to the other. However, the same applies to subtypes: subtypes also share a common constant property.

I may describe a class by a circle in Vienn Diagramm. Its subspheres would be types or variables. I think that the variable means that it has some fixed part, its type, and variable part, which make it variable and not constant. The constants or values would be an elementary point in the diagramm.

For instance, integer is a subtype of real. Integer variable means that it can take concrete values within the range of the integer area. Similarly, boolean variables, taking only values 0 and 1, are subtype of integer. But, what is a constant 1? Is it a real or integer or boolean variable or it is a specific type, instances of which have a common property: they have a value of 1? Is it a known treatment?

My interest stems from the practice: how can I save memory fixing the common part of variables in a language processing framework?


texts: Show that $(\log(n))^\alpha = O(n^\beta)$

texts:
I am trying to show that $\forall \beta \gt0, \log(n^\alpha) = O(n^\beta)$, however I cannot use the limit definition, as demonstrated in similar questions on the forum.
First I show that $\log(n^\alpha) = O(n)$, using the following method:
$\log(n^\alpha) = \alpha \cdot \log(n) \leq \alpha \cdot n$
Thus for $c=\alpha^\alpha, n_0=0$, we have $(\log(n))^\alpha \leq c \cdot n$ which implies $\log(n^\alpha) = O(n)$
Now I will show $\forall \beta \gt0, \log(n^\alpha) = O(n^\beta)$, we have two cases
$\beta \ge 1$: Since $\forall n \ge1, n\leq n^\beta$, then from the above result, for $c=\alpha^\alpha, n_0 = 1$, we have $\log(n^\alpha) \le c \cdot n^\beta$ which implies $\log(n^\alpha) = O(n^\beta)$
$0 \lt \beta \lt 1$: I can't seem to find a series of inequalities, as shown above, that prove $\log(n^\alpha) =O(n^\beta)$ in this case


texts:
Lots of (quantum) applications need thousands of qubits. But suppose we are short of stable qubits, is it possible (in general) using more time (or classical computation resources) to made up this shortage? Or is there any lower bound for this proving it can't be done?

Apology for phrasing the problem in just a few word, I just can't think of any technique for now.


texts:
I'm struggling to understand why this function is computable.
This is the requirement:

Consider the following program P, written in a pseudo-C language:

P:
{
    int x, y, z;
    read (x, y, z);
    while (x != y)
    {
       x = x - y;
       z = z + y;
    }
    write z;
}

Let $f(x, y, z)$ be the function computed by P. Is the following function g computable?

$g(x, y, z) = \begin{cases}
  1 & f(x,y,z)\ halts \\
  0 & else
   \end{cases}
$

Whenever I encounter a problem like this, I try to imagine a program that does exactly what $g$ does. In this case, a P2 program that checks if $f(x,y,z)$ halts.

Now, P halts if, basically, $x>y \ and \ y=1 $ or $x=y$ (there are probably more cases). In the other cases, P would just remain in the while loop, so $f$ is not total.

But how would P2 return $0$ if P wouldn't even halt? P2 would have to wait, and never return 0, so for some values the function is not computable, and x,y,z isn't always computable.

What am I thinking wrong here?


texts: If one-way functions exist are we definitely using them?

texts: I know that if one-way functions exist then there are certain universal one-way functions that exist, but to my knowledge they are too impractical to implement (which is the main reason why they are not being used in modern cryptographic protocols).  However, if one-way functions exist are the modern implementations (like RSA and its computational equivalents) definitely one-way?  Conversely, if it can be shown that these cryptosystems are insecure, do one-way functions definitely not exist?


texts: Does entangling 100 qubits require a 2^100 X 2^100 Hadamard gate?

texts:
Suppose I have 100 qubits that I want to entangle and put into superposition. To do so I construct a Hadamard gate to do this. By definition, the Hadamard is going to be a 2^100 X 2^100 matrix - which is huge.

How does one go about actually performing this operation? The size of the Hadamard matrix is exponential relative to the number of qubits (ie 2^100 X 2^100). Is there a way to perform this operation without actually making this huge matrix? Or can we only work with a 'small' number of qubits at once?

Follow up question: does using 100 4x4 Hadamard gates (one for each qubit) do the same thing as using a single 2^100 x 2^100 Hadamard gate? If so, how do these qubits become entangled?


texts: Finding an automaton with a given number of states

texts:
Define an NFA with 4 states that is equivalant to the following Regular Expression. $(01 + 011 + 0111)^*$.

My main problem is that to check for a string of length 4 (0111) I need at least 5 states to begin with. So to my (novice) little brain the question seems wrong.


texts: Reference asking: phase transition in SAT

texts:
This is not a technical question, I hope this community has a room for such questions, but I will delete it in case this is inappropriate.

It has been experimentally observed (e.g. here) that when choosing a $3$-SAT formula by the following process:

On input $(n, \alpha n)$: choose $\alpha n$ clauses uniformly at random from the set of all clauses of $3$ literals over $x_1, \ldots, x_n$, and return the conjunction of these clauses.

The probability that the outputted formula is satisfiable depends on $\alpha$: if $\alpha \ll c$ the probability is very close to $1$, and if $\alpha \gg c$ the probability is very close to $0$ (it has been observed for a general $k$-SAT instances).

My question is what is the theoretical understanding of this problem? To the best of my knowledge, for other  problems it is possible to prove similar claims quite easily (e.g. the probability that a random graph $G(n,p)$ has a clique of size $4$ is almost $1$ when $p(n) = \omega(n^{-2/3})$ and is almost $0$ when $p(n) = o(n^{-2/3})$, and it can be proven by a basic use of second moments).

However, for SAT I couldn’t find proofs. Do you know of any progress in this problem?


texts: I am in High School (P.R.) and I am a regular person in math. Should I try computer science?


texts: If-Then with disjunctions (OR) in Integer Linear Programming (ILP)

texts:
I have the following constraints I'm trying to model in Linear Integer Programming. I will try out diverse solvers for this later, but first I need to model the problem.

Given the integer variables: x1, x2, x3, x4, y1, y2, y3, y4, I have the following constraints:

IF (y1 ≤ y3 ≤ y2  OR  y1 ≤ y4 ≤ y2)
THEN (x1 ≥ x4  OR  x2 ≥ x3)

Additionally for all of these variables I have upper and lower bounds.

I think I have to use the "big M" technique, but I'm not sure how to handle the logical OR in the IF condition and in the THEN condition and how to built up one complete model.

Does anyone of you know how to resolve this?
Many thanks in advance.


texts: How to prove the following properties of Small-step semantics?

texts:
I have to prove the following 2 properties of the Small-step semantics of the WHILE programming language:

If $\langle C_1; C_2, s\rangle \rightarrow^k s'$ then there is a
state $s''$ and natural numbers $k_1$ and $k_2$ such that $\langle C_1;s
   \rangle \rightarrow^{k_1} s''$ and $\langle C_2; s'' \rangle
   \rightarrow^{k_2} s'$ where $k_1 + k_2 = k$.
If $\langle C_1, s \rangle \rightarrow^k s'$ then $\langle C_1; C_2,
   s \rangle \rightarrow^k \langle C_2, s'\rangle$.

I am not quite sure which kind of induction I should use. I am not asking for a full proof, I would rather appreciate some hints on which kind of induction I should use in this case. Thanks in advance!


texts: Hamiltonian non intersecting path in plane

texts: $N$ points are located in 2D plane. Some of the pair of the points are connected by line segments. What is the complexity of the problem of existence of Hamiltonian non intersecting path? What if we consider it in special cases of graphs.


texts: Is it possible for a network to have a negative cycle that is not found by the Bellman–Ford algorithm?

texts:
I'm struggling to think of such a network. According to the definition I'm working with:

Given a network $(V, A, w)$.
For all arcs $(u, v) \in A$ :
$\quad$ If $d[u, |V| - 1] + w(u, v) < d[v, |V| - 1]$:
$\quad\quad$ Print “Negative cycle!” and stop immediately

To me this implies the only way a negative cycle isn't detected is if all arcs from any $u$ to my $v$ must have a positive weight. How, then, could there be a negative cycle?


texts: How do I find the roots of the disconnected subgraphs of a directed graph?

texts: If I have a directed acyclic graph $G(V,E)$, which may consist of several disconnected subgraphs $G_i(V_i,E_i) \subset G(V,E)$, how do I find the root of every subgraph $G_i(V_i,E_i)$?


texts: An efficient way for the sum of weighted inputs?

texts:
There are $N$ weights, $w_i$. and signal starting from $a_0$.
I would like to moving weighted sum of signals, such as:

$$
s_1 = w_1a_1 + w_2a_2 + ... + w_Na_N\\
s_2 = w_1a_2 + w_2a_3 + ... + w_Na_{N+1}\\
s_3 = w_1a_3 + w_2a_4 + ... + w_Na_{N+2}\\
$$

and so on.

If we are to calculate the sums from $s_1$ to $s_M$, an brute-force algorithm will naturally have $\mathcal{O}(MN)$ for the summations. How one could have a better performance for this? I could do slightly better with:

$$
s_{i+1} = s_{i} - \Sigma_a(i+N-1) + \Sigma_a(i-1) + Na_{i+N}
$$

where $\Sigma_s(i) = \sum_{j=0}^{i}a_j$. And by using a dynamic programming for $\Sigma_s$, we may reduce the number of summation, 4 summations for each $s_i$. Is there any simpler recursion relation for this?


texts:
Consider a network with five nodes, N1 to N5, as shown as below.

The network uses a Distance Vector Routing protocol. Once the routes have been stabilized, the distance vectors at different nodes are as follows.

N1: (0,1,7,8,4)

N2: (1,0,6,7,3)

N3: (7,6,0,2,6)

N4: (8,7,2,0,4)

N5: (4,3,6,4,0)

Each distance vector is the distance of the best known path at that instance to nodes, N1toN5, where the distance to itself is 0. Also, all links are symmetric and the cost is identical in both directions. In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors.

It's a GATE-2011 question.

I have a doubt here.

Suppose when the cost of the link N2-N3 changes to 2, this will be immediately known to N2 and N3 and they will update their routing table entry to reflect this change. Now, this would cause triggered update.

Suppose After receiving the vector from N2, N3 finally changes it's vector to (3,2,0,2,5).

Now my query is whether this vector (3,2,0,2,5) would be communicated to N4 or the old vector of N3(7,6,0,2,6) would be communicated to N4?


texts: Relaxation of the null production restriction in Regular and Context Free Grammars

texts:
I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of some production.

However, in most definitions of regular and context-free grammars (such as those on Wikipedia), this restriction is nowhere to be seen (as an exception, the restriction is mentioned in the article on the Chomsky hierarchy for Type-3 languages).

Is this relaxation intentional in that both variants (with and without the restriction) have the same expressive power, or is this just a "sloppy" definition?
Even if they do have the same expressive power, wouldn't that ensure that Context Free Grammars are not a subset of Context Sensitive Grammars, thus violating Chomsky's Hierarchy?


texts: How to calculate the maximum sum over all arrays?

texts:
Following question was asked in a online hackathon that has been concluded.
Given arrays $A_1,\ldots,A_n$ of length $\ell_1,\ldots,\ell_n$, we want to find cyclically rotate each array in a way which maximizes $$ \sum_{i=1}^{n-1} i|A_i[\ell_i] - A_{i+1}[1]|. $$

For example, on input $2,3,1 \mid 3,2 \mid 4,5$ the best cyclic rotation is $2,3,1 \mid 3,2 \mid 5,4$, and so the answer is $1|1-3| + 2|2-5| = 8$.

There could be up to $10^5$ arrays, and the sum of all elements in all arrays can be at most $10^6$.

I tried solving this by focusing on the two last arrays, but this turned out to be the wrong approach. I am unable to figure out the correct one. How can this be calculated efficiently?


texts:
In lambda calculus, starting from $KII$ we can get by a single $\beta$-reduction to either

$\lambda y.II$

or $KI$

Now, according to Church-Rosser, these should be reducing into a common normal form. But the first reduces to $I$ and the second to $\lambda y.\lambda z.z$.

Am I doing wrong $\beta$-reductions or the theorem holds only on some condition? I do not see a common reduct here.


texts: Get term type during evaluation using Hindley-Milner type system

texts:
I've implemented a lambda calculus evaluator and use the Hindley-Milner algorithm to infer terms types and ensure type correctness without the user having to explicitly annotate types.

But now I'd like to add a typeof operator that given a term, it returns the type of the term. So far, what I do is keep a hash map of terms to types that is populated during type checking. So if I do typeof 123, when the type checker determines the type of 123, it'll add 123 = Number to the hash map and look it up when typeof 123 is evaluated.

The problem with this approach is that if I have this term:

let _typeof = \a.(typeof a) in (_typeof 123)

Since \a.(typeof a) is polymorphic and has type a -> Type, the result will be a instead of Number as I'd expect. If instead I had this:

(_typeof.(_typeof 123) \a.(typeof a))

Then I'd get the right type Number since \a.(typeof a) is not polymorphic.

So all I need is a way to handle polymorphism. I'm having a hard time getting my head around it and I wonder if there is a known way to do this.


texts:
I'm having a bit of trouble determining what language the following non-deterministic finite state automaton accepts.

Assuming the alphabet of this machine is ${a, b}$, I deduced that this automaton would accept words of the following characteristic: a word $w$ would be accepted if $w$ had zero or more $a$'s or $b$'s followed by a single $a$ followed by zero or more $a$'s or $b$'s followed by a single $a$ followed by zero or more $a$'s and $b$'s.

Is there a more clear and concise explanation of what sorts of words are accepted by this automaton or would my explanation be suffice? Any suggestions would be appreciated!


texts: Dividing EX stage of a pipeline into EX1 and EX2 stages

texts:
There is this problem about pipelining that does not have an answer, and I'm wondering what the answer could be:

 In the five stage pipeline with forwarding support to EX, the first operand of ALU comes from 3-to-1 input multiplexer. As the memory latency increases, MEM stage now takes 2 cycles (from 1
cycle) To adjust the pipeline for the latency increase, the MEM stage becomes MEM1 and MEM2.

How should the input mux for the ALU be changed, if forwarding to EX needs to be fully supported?
Even with the full forwarding to EX, show an example where the number of stall cycles increase in the new pipeline compared to the old one.

I don't get what it means to divide MEM stage with MEM1 and MEM2. Why would any additional input be necessary?


texts:
I'm trying to give a meaningful definition for NFAs with more than one initial state. I know from the formal definition in Wikipedia that it is possible to have more than one initial state, it mentions that "There is an easy construction that translates a NFA with multiple initial states to a NFA with single initial state, which provides a convenient notation."

I believe the power set construction could help me on this matter but I'm having a hard time understanding it. It could probably be modified so that it can be applied into the definition I want to give, but i don't know how.

I would appreciate any help I can get on this matter.


texts:
What i actually want to do is to turn a math problem ,i have to solve,to a Boolean Satisfiability problem and solve it using a SAT Solver.
I wonder if someone knows any manual,guide or anything that will help me to make my problem solve using a SAT Solver.From what i found so far,SAT Solver's do not have any good documentations..


texts: Proving that Pre(L) is regular using automatas: Should I prove that Pre(L) is the semantic of the new automata?

texts:
Let $L$ be a regular language, and $Pre(L)$ be the set of all words that are prefix of some word in $L$. Prove that $Pre(L)$ is regular.
My proof:

Let $M = (\Sigma, Q, \delta, q_0, F)$ be an automata such that $\mathcal{L}(M) = L$ and $Q' = \{ q \in Q \ | \ (\exists q_f, w \ | \ q_f \in F \ \wedge \ w \in \Sigma^{*}: [q, w] \mapsto^{*} [q_f, \lambda]  ) \}$, that is, $Q'$ is the set of all states that have a path to a final state of $M$.
Hence, $M' = (\Sigma, Q', \delta, q_0, Q')$ is an automata such that $\mathcal{L}(M') = Pre(L)$. QED.

Is the last step right or should I now proof that the semantic of $M'$ is in fact $Pre(L)$?


texts:
The question is as follows:

  A scientist creates a new compound, called compound A, that will explode 10 days after being mixed with compound B. This compound A was stored in a label-less bottle on a shelf with $n-1$ bottles of non-reactive material, and the scientist doesn't know which is compound A. There is exactly one bottle of compound A among the $n$ bottles on the shelf. The scientist has $O(log(n))$ beakers full of compound B. How can he determine which of the $n$ bottles is the compound A in exactly 10 days time?

I am a little stuck because I don't know how to narrow down the specific bottle in only 10 days. It is pretty obvious that you can just apply the first half of the bottles to the first beaker, and then if it doesn't react you know that the desired bottle is in the second half and so forth. But how do I narrow it down without witnessing the results of the first few tests?

We need to create something where a series of explosions will help us narrow down which one it is (lets say at first its amongst n/4, then n/10, then n/100, etc).
How the heck do I do this?


texts:
Some confusion about time-complexity and A*.

According to
A* Wiki the time-complexity is exponential in the depth of the solution (shortest path):

  The time complexity of A* depends on the heuristic. In the worst case of an unbounded search space, the number of nodes expanded is exponential in the depth of the solution (the shortest path) d: $O(b^d)$, where $b$ is the branching factor (the average number of successors per state).

The comment to this accepted answer points out that it makes more sense to give the complexity in termes of the size of the graph and therefore it should be $O((|V| + |E|) \cdot log |V|)$

Obviously, if the heuristic assigns a value of 0 to every node, A* becomes Dijkstra's algorithm and any uniform cost heuristic will essentially disable the heuristic.

If we assume the heuristic to be $O(1)$ (and consistent), it would make sense that the worst case is essentially degrading A* to Dijkstra's algorithm which has complexity

$O(|E|+|V|\log|V|)$

with a min-priority queue implementation (Fibonacci heap).

Am I wrong?

Any book etc I have been looking at always gives the complexity in terms of the depth of the solution


texts:
I have read a few algorithms for $LR(k)$ parser, in which there is a frequent mention of selecting a handle from the grammar given.
For example, one document said  - "the essence of LR parsing is identifying the handle on top of stack"

Please help me understand, what are handles in parsing?


texts: Runtime-Analysis for single loop incremented by a factor of 3

texts:
So, I'm trying to understand how to  get the run time of this loop:

for(int i = 1; i < n*n*n; i*=3) {...}

So, far I know:

loop starts at 1
finishes when $i  > n^3-1$
that $i$ is multiplied by 3 each iteration.

Intuitively it seems like as $n$ gets larger the number of iterations decreases which makes me think that the run-time is $O(log$ $n)$. My question is if this is correct if it is what is a mathematical way I could derive that answer?


texts: Data structure for finding nearest squares from current square

texts:
For my project I can have 0-500 moving squares. The largest possible square width is at most 3 times longer than the smallest possible square width. The squares can move up to 3 of their own body's width per second. About 1 square is added and about 1 square is deleted every second.

What I'm trying to implement now is a neural network to drive the speed and direction of the squares. Each square will have their own neural network which will take the x and y position of the 5 nearest squares to it. To find the nearest squares, I will be taking the euclidean distance from the center of their squares bodies.

My problem is that calculating the distance of each square to every single other square - to find its 5 nearest other squares - is going to make my program run at a snail's pace.

So what is a good data structure I could use to reduce the number of checks I'm performing?

Also I heard that kd-trees were good at finding the nearest neighbor. However, because the squares are going to be moving a lot I'm not sure if it'd actually be the best data structure to use.


texts: Exact algorithm for the partition problem

texts:
The partition problem is: given a set of numbers, find a partition to two subsets in which the difference between the sums in each subset is minimized. This optimization problem is NP-hard. The simple exact algorithm - checking all the possible partitions - takes time $O(n 2^n)$. Is there a more efficient exact algorithm?

NOTE: If the numbers are small integers, then it can be solved by a pseudo-polynomial algorithm, but I am interested in a problem with real numbers (e.g. "double"s in Java).


texts: Simple algorithm for listing all 6-cycles in a directed graph

texts:
What's an easy-to-program way of listing all 6-cycles in a directed graph? I've done some reading on the general case of even cycles, but it's rather complicated. I found a really neat approach for 4-cycles, in this post, and I was wondering if there's something similar for 6-cycles.

My graph isn't that big (maybe a few hundred nodes) so I'm not too worried about computation time.


texts: Backpropagation for 'Classification' Neural Network

texts:
Question: How does one formulate a back propagation algorithm (either batch, gradient, anything that works) for a neural net, playing a game of Tic Tac Toe?

(Java is being utilized)

Scenario: There are 9 input neurons, one for each square. A value of -1 represents X, 1 represents O, and 0 represents an empty space. These values are stored in 1x10 array (the tenth input being bias). These lead to a single hidden layer, with n nodes (n selected on boot). The weights between the input and hidden layer are stored in a 10 x n array. A typical sigmoid activation function is used on the hidden layer. The hidden layer then leads to 9 output neurons, with weights stored in a n x 9 array. A separate function is used to normalize the output, dividing every point by the largest output, and whichever neuron is storing "1", the next move is made there. I've gotten this portion to work.

The cost function is as follows- Every board has an "advantage", which is equal to 10(turns till lose) - 8(turns till win) - 100(boolean invalid[i.e. placing a piece over another piece]). A negative advantage is bad for the AI, positive is good. Cost therefore, is cost = 1/2(best possible delta(advantage), - the delta(advantage) that the AI comes up with)^2. Squared in order to make the function convex, multiplied by .5 for the power rule to make it cleaner.

Here lies the problem: I need to calculate the derivative, so I know what way is down hill. How do I calculate the derivative for the advantage function, if it uses if statements, loops, etc.? It really is more of an operator, than a function- is there a way to re-write a cost function for tic-tac-toe which would be more conducive to machine learning? Or is there a way to derive around this?

I hope I explained that correctly- P.S. This is not for a class, rather my own blatant curiosity.


texts: Maintaining balanced BSTs in order to get $\frac{n}{2}$ largest elements in constant time

texts:
I wonder what is the best data structure I can use in order to achieve the following:
Given a data structure based on a balanced BST, I would like to get a tree with the $\lfloor\frac{n}{2}\rfloor$ greatest values in $O(1)$.
I thought about maintaining another balanced BST and a variable containing the middle value, but I don't think it's a good idea, since the root of a balanced BST might not divide the tree into 2 halves so that the $\lfloor\frac{n}{2}\rfloor$ largest elements are to the right (the tree might be right heavy).
Another idea was to use heap, but I don't see how it can help me.
Do you have any idea how to implement it? What do you think about mine?


texts:
Given boolean function $f$, let $F$ denote the unique multiaffine real polynomial representing $f$.

Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$ where $x^i=x\oplus\Bbb 1_i$ where $\oplus$ is $XOR$ operation.

Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$

Is there an easy proof to show $S(f)\leq \mathsf{deg}(F)$?


texts:
I'm studying random tries in one of my classes, and was wondering if anyone could offer any guidance regarding a problem.

Question:
Given a random $m$-ary trie with $n$ total leaves, letting $I$ be the number of internal nodes in the tree (that is, nodes which aren't a leaf), show that $E(I)$ is $O(n)$.

About the distribution:
We have an alphabet of $m$ letters (hence an $m$-ary trie), each with a corresponding probability $p_i$. We randomly create $n$ words of infinite length by drawing the first letter from our distribution, the second letter, etc. Finally, we insert these $n$ infinite words into a $k$-ary trie. This trie will be infinite in length, but we prune it by removing any paths which are traversed by only one of our $n$ words, to eliminate 'redundancy'.

Attempt: I tried relating things back to the size of the random trie, which I call $S$. Every non-root node in the trie is the child of some internal node, so $mI = S-1$

That is $E(I) = E\left(\frac S m\right) - \frac 1 m$

So if I can show that the expected size of a random trie is O(n) I'm golden. But unfortunately everything we've covered in class relates to expected depths and heights of a given trie, and I don't have any ideas moving forward. Could anyone offer advice on what might be useful here?


texts: Confluence proof for a simple rewriting system

texts:
Assume we have a simple language that consists of the terms:

$\mathtt{true}$
$\mathtt{false}$
if $t_1,t_2,t_3$ are terms then so is $\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$

Now assume the following logical evaluation rules:

$$ \begin{gather*}
\dfrac{}
      {\mathtt{if}\: \mathtt{true} \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to t_2}
      \text{[E-IfTrue]} \quad
\dfrac{}
      {\mathtt{if}\: \mathtt{false} \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to t_3}
      \text{[E-IfFalse]} \\
\dfrac{t_1 \to t_1'}
      {\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to \mathtt{if}\: t_1' \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3}
      \text{[E-If]} \\
\end{gather*} $$

Suppose we also add the following funky rule:

$$
\dfrac{t_2 \to t_2'}
      {\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to \mathtt{if}\: t_1 \:\mathtt{then}\: t_2' \:\mathtt{else}\: t_3}
      \text{[E-IfFunny]}
$$

For this simple language with the given evaluation rules I wish to prove the following:

Theorem: If $r \rightarrow s$ and $r \rightarrow t$ then there is some term $u$ such that $s \rightarrow u$ and $t \rightarrow u$.

I am proving this by induction on the structure of $r$. Here is my proof so far, it all worked out well, but I am stuck at the very last case. It seems like induction on the structure of $r$ is not sufficing, can anyone help me out?

Proof. By induction on $r$, we will seperate all the forms that $r$ can take:

$r$ is a constante, nothing to prove since a normal form does not evaluate to anything.
$r=$ if true then $r_2$ else $r_3$. (a) both derivations were done with the E-IfTrue rule. In this case $s=t$, so there is nothing to prove. (b) one deriviation was done with the E-IfTrue rule, the other with the E-Funny rule. Assume $r \rightarrow s$ was done with E-IfTrue, the other case is equivalently proven. We now know that $s = r_2$. We also know that $t =$ if true then $r'_2$ else $r_3$ and that there exists some deriviation $r_2 \rightarrow r'_2$ (the premise). If we now choose $u = r'_2$, we conclude the case.
$r=$ if false then $r_2$ else $r_3$. Equivalently proven as above.
$r=$ if $r_1$ then $r_2$ else $r_3$ with $r_1 \neq $ true or false. (a) both deriviations were done with the E-If rule. We now know that $s =$ if $r'_1$ then $r_2$ else $r_3$ and $t =$ if $r''_1$ then $r_2$ else $r_3$. We also know that there exists deriviations $r_1 \rightarrow r'_1$ and $r_1 \rightarrow r''_1$ (the premises). We can now use the induction hypothese to say that there exists some term $r'''_1$ such that $r'_1 \rightarrow r'''_1$ and $r''_1 \rightarrow r'''_1$. We now conclude the case by saying $u =$ if $r'''_1$ then $r_2$ else $r_3$ and noticing that  $s \rightarrow u$ and $t \rightarrow u$ by the E-If rule. (b) one derivation was done by the E-If rule and one by the E-Funny rule.

This latter case, where one derivation was done by E-If and one by E-Funny is the case I am missing... I can't seem to be able to use the hypotheses.

Help will be much appreciated.


texts: Computer vision training procedures: SVM/AdaBoost vs Neural Networks

texts:
With SVM, adaboost or similar alogrithms, image training sets must be cropped with specific constraints (keep image cropping ratio the same, have object tightly cropped, same resolution)

In general, does a training set for a neural network based classifier need to be generated under the same constraints?

If not, which constraints can be removed or loosened?


texts: $\mathbb{NEXP\subseteq(NEXP\cap coNEXP)/poly}\implies \mathbb{NEXP=NEXP\cap coNEXP}$

texts:
We already know that $NEXP\subseteq EXP/poly\implies NEXP=EXP$. What if we change $EXP$ to $NEXP\cap coNEXP$.

As the title states, prove the statement in the title.

The original proof use the self-reducibility of the searching problem. For a language $L\in NEXP$, the corresponding search problem has its decision version as $L'=\{<x,y>| y$ is a prefix of a certificate for $x\}$. Clearly, $L'$ is in $NEXP$. Then, we brute force all the poly-long advice and plug it in the $EXP$ advice-taking machine to construct a supposed certificate.


texts: External fragmentation in fixed size partitioning

texts:
Can external fragmentation occur in fixed size partitioning ?

I searched everywhere but couldn't find a sentence which says external fragmentation is not possible in fixed size partitioning.

Please someone clear my doubt.


texts: Is the emptiness of intersection of two CFLs decidable?

texts:
Consider $L = \{\langle L_1, L_2\rangle\mid L_1, L_2 \in \text{CFL} \text{ and } L_1 \cap L_2 = \emptyset \}$. How to prove that $L \notin R $?
$L_1, L_2$ encoded in chomsky-normal-form.


texts: Convert integer of mixed radix to standard positional numeral system and vice versa

texts:
I have multiple numbers (e.g. [1, 4, 2]) where each number can be one of a specified range of numbers (e.g. [0-1, 0-5, 0-3]). I think one can represent my so chosen numbers by seeing them as digits of a number in the mixed radix numeral system with different bases for each position. In the above example, the bases would be [2, 6, 4] and the number would be 1 4 2.

With the bases given in this example one could specify 48 different numbers (2 * 6 * 4).
If I know the bases, how can I construct an algorithm that converts such a number to another number in a standard positional numeral system (like e.g. decimal, binary or hexadecimal) without just building a big generated lookup table? The conversion has to be bijective and there should not be any gaps - so for this example the mixed radix numbers should be represented by the integers from 0 to (inclusive) 47 in the decimal system.

Actually I want to encode these mixed radix numbers in binary data, so a gapless and bijective conversion to the binary system would be sufficient.


texts: KDD Machine Learning using K-NN Algorithm Classification Problem

texts:
I'm trying to solve a classification problem from the KDD cup archive of 2004.
Details can be found here: KDD 2004 Archive
I'm only dong the particle physics part.
The description of dataset is as follows:
Each line in the training and the test file describes one example. The structure of each line is as follows:

  The first element of each line is an EXAMPLE ID that uniquely describes the example. You will need this EXAMPLE ID when you submit results.
  The second element is the class of the example. Positive examples are denoted by 1, negative examples by 0. Test examples have a "?" in this position. This is a balanced problem so the target values are roughly half 0's and 1's.
  All following elements are feature values. There are 78 feature values in each line.
  Missing values: columns 22,23,24 and 46,47,48 use a value of "999" to denote "not available", and columns 31 and 57 use "9999" to denote "not available". These are the column numbers in the data tables starting with 1 for the first column (the case ID numbers). If you remove the first two columns (the case ID numbers and the targets), and start numbering the columns at the first attribute, these are attributes 20,21,22, and 44,45,46, and 29 and 55, respectively. You may treat missing values any way you want, including coding them as a unique value, imputing missing values, using learning methods that can handle missing values, ignoring these attributes, etc. Training data for the quantum physics task: 50,000 train cases
  Test data for the quantum physics task: 100,000 test cases

The elements in each line are separated by whitespace.
My actual problem is, that when I run the code, I get two outputs. One is the "predicted" value, which is obtained after comparing the nearest neighbors and getting the average (either 0, or 1). Second output is the "actual" value, which comes out to be a question-mark ('?'). In order to calculate the accuracy, I need to compare the "predicted" values with some "actual" values, which, in my case are question-marks. I don't know how to exactly compare the values, because apparently, I don't have any values from which I can compare my predicted values.
Here is an attached screen-shot of my output:


texts: Find all rational roots of a polynomial equation

texts: I'm going to try to design an algorithm to find all the rational roots of a polynomial equation in range [a, b]. Can someone please tell me which algorithm currently solves the problem with lowest worst-case complexity? This algorithm will be for a general purpose computer(Turing Machine).


texts: Find the median element of two AVL trees in $O(\log n)$

texts:
I'm attempting the problem of finding the median element in two AVL BST's in $O(\log n)$ time. In this problem, we are given two AVLs, with a combined size of $n$ (the distribution across the two trees need not be balanced – it could be that one AVL contains $n-1$ elements, and the other $1$), and the goal is to find the median of the union of the elements in both AVLs.

I am currently trying to come up with an algorithm to solve this. Each node, besides holding its integer value and pointers to its parent and child nodes, holds the subtree size for the subtree rooted at it. I've approached it by initially finding the number of elements $n$ (we assume this to always be odd) via the size of the subtree stored in each AVL tree's root. Let the subtrees be $A$ and $B$, where $A_L$ is the left subtree of $A$ and $A_R$ is the right. I've begun by operating on the AVL tree of a larger size and then comparing $A_L$ and $A_R$'s sizes. With this approach, I am trying to rule out the existence of the median in one of the subtrees, but I'm currently confused on how to do this. Any ideas?


texts: What are the drawbacks of Normalized Mutual Information clustering evaluation method?

texts:
What are the drawbacks of Normalized Mutual Information (NMI) clustering evaluation method?
For evaluating what clustering algorithms, is the NMI evaluation method suitable?


texts: interplay between evolutionary algorithms and machine learning from neuroscience

texts: Evolutionary algorithms (EA) being those inspired by the natural evolution (mutation and selection), and Machine Learning (ML) motivated by the neural concepts of human and animal learning (brain's synaptic plasticity), considered from the neuroscience point of view, how can we make computers learn faster than a human lifespan - actually multiple generations via genetic modification - by combining these two methods?


texts: Isomorphic induced subgraph problem using Courcelle's theorem

texts:
The isomorphic induced subgraph problem, is the problem of deciding whether, given two graphs $G$ and $H$, $G$ contains an induced subgraph isomorphic to $H$.
Is there a proof using Courcelle's theorem, that this problem is fixed-parameter tractable when parameterized by $|H|$ and $\mathrm{tw}(G)$ (treewidth)?


texts: Proving $L = \{a^iba^j|i\ge2j\ge0\}$ isn't regular

texts:
I need to prove the following language is not regular, I think I need to use the pumping lemma. The trouble I am having is that there is multiple variables and I am not used to that.
Could someone tell me if the pumping lemma is the correct proof by contradiction of
$$L = \{a^iba^j|i\ge2j\ge0\}$$

I took $xyz = a^{2p+1}ba^p $
so
$|xy| = 2p+2$ which is greater than $p$ and must be false.
Is this solution correct?


texts:
I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints.

The Myhill-Nerode Theorem provides the minimum number of states of a DFA to recognize a regular language. Argue that an analogue for context-free languages is unlikely to be discovered.
Prove that the grammar with fewest variables equivalent to a grammar G is uncomputable.


texts: Is the validity of some instance of an equational problem decidable?

texts:
Is the following FOL-problem (equality is a logical symbol)
effectively decidable?

Given.  A finite equation system $E$ and an equation $s = t$.

Question.  Is there a substitution $\sigma$, such that $\sigma(E)
\models \sigma(s = t)$?

Some useful information.

Obviously one can restrict $\sigma$ to be a ground substitution.
This problem is decidable:  Given a finite system $E$ of
ground equations and a ground equation $s = t$, does $E \models s = t$
hold? (c.f. [1: Corollary 4.3.6])

References

[1] Franz Baader, Tobias Nipkow: Term Rewriting and All That,
© 1998 Cambridge University Press.


texts: Need an algorithm to find the input factors that are most affecting the output

texts:
I apologize if this question is already answered and appreciate any pointers to existing answers. I'm not familiar with statistical or data mining terms so my search was limited to basic words used in the title of this question. I did look at some algorithms but could not decide if they serve the purpose.

I'm looking for an algorithm that can give me % probability or % confidence that out of given set of input factors which inputs are affecting the output most. Let us take an example below and assume that input and output will be recorded 4 times a day for a month.

Output:

Phone's battery drainage
Phone heating up (temperature).

Input:

Ambient temperature
Which apps were used most when the output was measured (multiple input points)
Number of calls received and call length
Screen brightness
GPS connectivity enabled?
Bluetooth enabled?
Cellular signal strengh

If we measure this data for month, we will find that Cellular Signal Strength and screen brightness probably will be linked to Battery Drainage most. On the other hand 3D resource intensive games will be linked to Phones heating up the most. Can I deduce such relationship using any existing algorithm(s)?


texts: Recursive macros and termination of assembler

texts:
A debate has arisen in the course of using an assembler (which does a bit of preprocessing first, but is mainly a static assembler):

This particular assembler allows recursive macros to be defined, which it then attempts to resolve (statically, at compile time) and embed in the binary output.

The question is, does this language feature still allow the assembler to terminate (for all input) or is there a case where the assembler will never terminate - excluding memory considerations?

From an empirical perspective "even short programs take forever to compile" but whether this is theoretically rigorous is a different story, at which point we defer to cs.stackexchange!


texts: Prove that a language is not regular with process of elimination

texts:
When deterministic automaton, I need to prove that you can't implement the language in it, because the language is not regular.

Easiest way to prove that a language is regular, is just by making an automaton for it. But if the automaton is not regular, you can't just say that it's not regular because you couldn't build an automaton for it.

So I am wondering, how to prove that a language is not regular the simplest way?

Given language:

$$ L = \{a^n b^n | n > 0\} $$

Definition: The language accepts series of a's and b's where the amount of as equals to the amount of bs. This is not a regular language.

How can you prove that it's not a regular language?

From what I remember (I didn't understand it much), you had to take a sub-langauge of that language, and mark it as W

So $$ W = \{a^i\} $$

Then select 2 words from W and mark them as w1 and w2

$$ w1 = a^i $$
   $$ w2 = a^j $$

where i != j

And then I don't really remember what to do.


texts: Brzozowki's algorithm doesn't work for this corner case

texts:
I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example:

In this DFA, $S_0$ and $S_1$ are nondistinguishable and should be merged after minimization, but they are not.
The process of minimization is like this:

I tried to find out why by reading @Hendrik Jan's proof here, Proof of Brzozowski's algorithm for DFA minimization?

However, I find that this case bypasses the proof, because that in the reversed DFA, the initial state $q_0$ cannot be reached by $q_0$ using any words (but initial state is always considered reachable and cannot be removed). So did I miss anything, or does Brzozowki's algorithm has any specification for this corner case?

(It bypasses the proof like this: in the second series of reversal-determinization, $S_0 = \{q_1\}$ and $S_1 = \{q_0, q_1\}$, for any $w$, $\delta(q_0, w)$ in $S_0$ iff $\delta(q_0, w)$ in $S1$, so we say $S_0
= S_1$, assuming all states can be reached by $\delta(q_0, w)$, but $\delta(q_0,w)$ will never be $q_0$)

the initial DFA I was working on:


texts: Finding solution of given recursive equation?

texts:
$T(n) = 1+ \sum_{j=0}^{n-1} T(j)$
I've proved $2^n$ be the solution of this equation using induction. But is there any other way to find the solution? I just proved not solved.


texts: Asymptotic estimate for $\sum_{k=1}^{N} {\frac{1}{k^2 H_k}}$

texts:
I am working on finding the asymptotic estimate for $$ \sum_{k=1}^{N} {\frac{1}{k^2 H_k}}.$$
All I know is that ${\frac{1}{k^2 H_k}}$ is convergent because $${\frac{1}{k^2 H_k}}<\frac{1}{k^2}$$ and $\frac{1}{k^2}$ is convergent.

Am I right to conclude that the asymptotic estimate for this is $O(\frac{1}{k^2})$?


texts: Does every thread have its main function?

texts:
Does every thread have its own main function?
I know that its have its own stack, but what about main function (not necessarily a function which called main).
For example, when creating a thread, we pass a function as an argument for the new thread to run it.
I tried to search about this topic, but couldn't find answers.


texts: Running time for Breadth-First-Search vs Depth-First-Search

texts:
Can someone explain why BFS is $O(V + E)$ whereas DFS is $\Theta(V + E)$.
I understand the definitions of both notations, but I just don't see why the bound for DFS should be tighter than that of BFS.

Is it because DFS is guarenteed to visit all vertices and hence has the lower bound $\Omega(V+E)$?

Note: I am studying the CLRS book, which is where the running times is coming from


texts: How can I write a genetic programming algorithm, given that the Halting problem is unsolvable?

texts:
I am learning genetic programming and to practice I want to write a simple algorithm which evolves a program that solves a simple function (say, square root). I intend to represent programs as abstract syntax trees.

However, one of the functors is the while loop. Of course, in assesting a tree's fitness, I have to evaluate the program: but the halting problem is unsolvable. How can I tell if a given tree stops? Of course I can't, so what are some practicals ways to approach this problem?

Should I make my simple tree-language not turing complete? Or maybe give a timeout to each tree?


texts: An efficient way of calculating ((p*q)) where p and q are prime

texts:
Let $p$ and $q$ be prime numbers and $\phi$ Euler's totient function. Is there an efficient way of computing $\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, that is not simply based on factoring $p-1$ and $q-1$?
Obviously, if $p$ and $q$ do not equal two, $p-1$ and $q-1$ are even and consequently their prime factorization is entirely different from the prime factorization of $p$ and $q$. Therefore I assume that no such shortcut exists.
Do I overlook something?


texts:
In an assignment I've been asked to find a CFG for $a^x b^y a^z b^w$, where, $x,y,z,w \in \mathbb{N}^+$, $y > x$, $z > w$, and $x+z = y+w$. A hint was given, think of the language as $(a^p b^p)(b^q a^q)(a^r b^r)$.

I've had a go at it, and have come up with

S -> A
A -> aAbB | ab
B -> bBaC | ba
C -> aCb | ab

This language will give me equal $a$'s and $b$'s. The reason I've chained the productions together is that since $x,y,z,w$ can't be 0, when one production is done, the others must be done as well (that was my thinking). However, I can't help but be worried about order. Even the smallest production won't come out as in the order "abab". Is it possible to construct a CFG that imposes order and memory? Or do I have to go to a PDA then CFG? Or is it irrelevant?


texts: If compilers have an inheritance of compilers(for example, a compiler needs to be compiled by another compiler, and that compiler needs to be compiled by another compiler, and so on) then if there is an inefficiency in one of the compilers up the line of inheritance(like the compiler's compiler's compiler's compiler), would the current compiler inherit that inefficiency?


texts: Is there any decision problem not in NPH but can be reduced to a NPH problem?

texts: I just have taken an algorithm class exam and there was a T/F problem 'one can show that a problem A is in NPH by giving a polynomial reduction from A to a NPH problem B'. I know the direction of reduction is silly, but no counter examples come to mind right now...


texts: How does this left-associative recursive descent parser work?

texts:
For personal enlightenment, I'm trying to write a recursive descent parser for lambda calculus without abstraction, i.e., just identifiers and function application.

The BNF grammar that describes the language could be this, where <var> is a terminal standing for identifiers:

<exp> ::= <exp> <var>
        | <var>

But this grammar can't be parsed by a recursive descent parser because it is left-recursive. So we need to rewrite it to something like this:

<exp> ::= <var> <app>
<app> ::= <var> <app> | ""

We can now write a recursive descent parser, in Standard ML here, that parallels the grammar:

type token = string

datatype ast =
  VAR of string
| APP of ast * ast

fun exp tokens =
  case tokens of
    [] => raise Fail "missing expression"
  | var :: tokens =>
    case app tokens of
      NONE => SOME (VAR var, tokens)
    | SOME (absyn, tokens) => SOME (APP (VAR var, absyn), tokens)

and app tokens =
  case tokens of
    [] => NONE
  | var :: tokens =>
    case app tokens of
      NONE => SOME (VAR var, tokens)
    | SOME (absyn, tokens) => SOME (APP (VAR var, absyn), tokens)

However, while the new grammar doesn't exhibit left-recursion, the parser that implements it will produce right-associative function application nodes. This is a fairly known limitation of recursive descent parsers.

- exp ["a", "b", "c"];
val it = SOME (APP (VAR "a",APP (VAR "b",VAR "c")),[])

Here's what puzzles me, though. I can write a function that can parse a list of tokens into an AST with the correct left-associative function application nodes, but I'm not sure why I can do that. Is this parser still a recursive descent parser? What's the grammar that it implements? Does it work because it uses a 2-token lookahead? I'm unsure.

fun exp tokens =
  let
    fun loop tokens ast =
      case tokens of
        [] => SOME (ast, tokens)
      | name :: rest => loop rest (APP (ast, VAR name))
  in
    case tokens of
      [] => NONE
    | name :: rest => loop rest (VAR name)
  end

- exp ["a", "b", "c"];
val it = SOME (APP (APP (VAR "a",VAR "b"),VAR "c"),[])

Is this a known, formalized, trick for hand-writing recursive descent parsers?


texts: Finding all marked elements using Grover's algorithm

texts:
Grover's algorithm uses an oracle function $f(x) \to \{0,1\}$ to find the location of a single marked element from an unordered database of $2^n$ elements with high probability. As part of an assignment I am supposed to design a variant of the algorithm that finds all of the $t$ marked elements ($t$ is known). I want to do this by repeating the following procedure $t$-times:

Use Grover's algorithm to find any marked element $x$.
Delete $x$ from the data base.

I think my solution is correct, but I am still not feeling comfortable with quantum computing. In particular, I am unsure of how one could implement the removal step since it would mean to manipulate the function $f$.

Can anyone clarify?


texts: How are virtual nodes placed / calculated to implement consistent hashing

texts:
I am reading about consistent hashing for system design and I understand the application of consistent hashing and the use of virtual nodes. I want to understand how to calculate the optimum number of virtual nodes and how to place them on the unit circle.
https://youtu.be/zaRkONvyGr8?t=433
in the above video the author explains that k hash functions are required, pass the key through each hash function to have k points for each server and the optimum number of hash functions k = log(M).
where M is number of servers (not sure if I completely understand this portion, feel free to correct me). The presenter in the video says "search space", but imo I think he means he means # of
How / Why does this work ?
Other resources I have gone through are:

https://www.toptal.com/big-data/consistent-hashing
https://en.wikipedia.org/wiki/Consistent_hashing
https://medium.com/@sandeep4.verma/consistent-hashing-8eea3fb4a598

but this portion isn't explained


texts: Lazily computing a random permutation of the positive integers

texts:
Are there any existing efficient algorithms for lazily computing a random permutation of the positive integers in a given range (e.g. the range offered by an unsigned integer type in a CPU)?

What I mean is this:

An algorithm that, given a source of randomness and a positive integer range (for simplicity it could be restricted to starting at 0 and ending at n), can be asked to produce the next value in that range. This can be repeated n times, and a different number is provided by the algorithm each time.

If the caller were to push all of the values retrieved from the algorithm into a queue the resulting ordering would be just as random as if the result had been generated with the Fisher–Yates shuffle.

The naïve implementation would be to pick a random number in the range, check to see if it has already been selected, and choose again if so. This algorithm starts efficient enough, but has increasing complexity for subsequent calls -- too expensive for real-world applications.
To really be useful it would have to be O(1) for each trial, though a good logarithmic time might be applicable.

It has to be lazy because with large ranges (such as a 64 bit unsigned integer) it would take Exabytes of storage to precompute the whole permutation, and it is unlikely that a real-world application is going to actually need all of the range; merely it needs that the entire range was considered in values it is actually going to use.

Essentially the problem is just lazily generating a mapping between the integers in a range and a random permutation of those same integers, though being able to access the mapping at arbitrary points instead of just sequentially is but a bonus.


texts: Minimum-cut with Maximal number of edges

texts: My question is: in a DAG, each edge has a different value of capacity, we can assume these capacities are integers multiples of the total number of edges. Also, sometimes we can have many minimum cuts, but these cuts have a different number of edges, how can we know which cut has the maximal number of edges?


texts: Execution time of NP and NP-Complete algorithms

texts:
For P algorithms, we say that the execution time can be logarithmic O(log n), lineal O(n), quadratic O(n^2), etc.

For NP and NP-Complete algorithms is there a way to represent the execution time? Or is there a 'standard' way of doing it?


texts: Network Flow with multiple connected subsets

texts:
Given a set of buyers, houses, agents with the following constraints:

Agents only know a subset of buyers
Agents only know a subset of houses
Agents can only do some amount of transactions

Construct a flow network to model the problem.
Disclaimer this is homework

I have put together some thoughts on a solution to this problem.  First I realized that agents should be right before the sink node with a max flow equal to the number of possible transactions.  This would then limit the number of transactions that can flow through an agent since the max flow can't be exceeded.

I was then thinking that it would be possible to put an edge between each person and house that an agent knows (example if agent knows person A, B and house 1, 2 there are edges (A,1), (A,2), (B,1), (B,2)). Finally, connect each house that an agent knows to an agent with max flow of 1. Then by running a Ford-Fulkerson algorithm across it the inflow of the sink node would indicate max number of transactions.

However, I am concerned that there is no limit of stopping a house from being purchased more than once. I have tried building the network with various configurations (swapping houses and clients, building nodes of client/house pairs) and nothing seems to solve this specific problem.

I am mostly looking for hints to solve this problem.


texts: Big Oh notation for a function with two inputs of linear growth

texts:
I'm quite new to time-complexity analysis so I might have misunderstood some basic concepts but lets say we have the following function:

    function(int x, int y)
    for (int i = 0; i < x; i++)
    {}

    for(int i = 0; i < y; i++)
    {}

From my understanding this function will for large inputs of $x$ and $y$ have two loops of linear growth. If the first loop is said to run $k$ times and the second $m$ times, will the big Oh notation be $O(k + m)$, or can the two inputs be merged into one variable of linear growth, like $n$, $O(n)$? Can $k$ and $m$, since they both have the same growth rate and (in the case of Big Oh analysis) equally large inputs be simplified into one variable or should they stay separate?


texts:
I am studying about DFS these days from the book "Algorithm Design" by Jon Kleinberg. Here a DFS algo is given which is as follows:

DFS(s):
    Initialize S to be a stack with one element s
    While S is not empty
        Take a node u from S
        If Explored[u] = false then
            Set Explored[u] = true;
            For each edge (u,v) incident to u
                Add v to the stack S
            Endfor
        Endif
    Endwhile

Now, how will the following graph be traversed using the above algo?

[TIP] We have to use stack as a data structure

Why I am asking this is because I am confused about the contents of stack at any point of time. I want to see how would you guys do it.


texts: How to Efficiently Define the Natural Numbers in Type Theory

texts:
A while ago I wondered about how Proof Assistants like Coq prove $m \leq n$ and the like. It looks like they actually need to traverse the natural numbers based on the successor/predecessor formulation:

  Coq < Eval compute in le_lt_dec 100000 1000000.
  Warning: Stack overflow or segmentation fault happens when working with large numbers in nat (observed threshold may vary from 5000 to 70000 depending on your system limits and on the command executed).
  Stack overflow.

One of the answers suggested using the BinInt (Binary Integers representation) to perform this operation.

  When a mathematician looks at a claim like $1000 ≤ 1000000$ and says "obviously", they are taking advantage of the fact that we wrote the claim in decimal notation. If you want to do something similar in CoQ, you could try to prove, e.g., $10∗10∗10≤10∗10∗10∗10∗10$.

So I'm wondering if there is a standard way of representing numbers as types without defining them like Peano's axioms style, using successor/predecessor and the like. Something that allows you to prove two numbers have a relation such as $m \leq n$ or $m \neq n$ or do other common things with numbers like adding/subtracting, in such a way where the "formal definition" (i.e. succ/pred) of the numbers is combined with some more computationally optimal version so you can use it in practice. Not sure what best-practice is to do here, but I would like to define a numbers type and have it gain all the advantages of proof theory / proof assistants, while also being the actual type definition used to construct i.e. integers.


texts: Consequence of NP-complete, and DP-complete w.r.t. randomized reductions

texts:
If a problem is NP-complete with respect to randomized (polynomial time) reductions, but not with respect to deterministic reductions, then we have P $\neq$ BPP (See Question 2 here and its answer).
Suppose a decision problem is proved to be NP-complete; and it is also proved to be DP-complete with respect to randomized reductions. Does this have any real consequence?
Context (updated)
Given a graph $G$, it is DP-complete with respect to randomized reductions to test whether $G$ has exactly one 3-colouring upto swapping of colours  [2]. I thought the same problem is coNP-complete because the "another solution" problem associated with 3-colouring is NP-complete [1]. My reasoning was wrong. Only the associated promise problem (give a promise that the graph has a 3-colouring) is coNP-complete (two different 3-colourings together serve as a no certificate). If that promise is not given, there is no obvious way to give a no certificate in the case when the graph is not 3-colourable.
[1] Dailey, David P., Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, Discrete Math. 30, 289-293 (1980). ZBL0448.05030.
[2] Barbanchon, Régis, On unique graph 3-colorability and parsimonious reductions in the plane, Theor. Comput. Sci. 319, No. 1-3, 455-482 (2004). ZBL1043.05043.


texts:
Let us have a finite set $S$ and a finite set of its subsets $S_1, S_2 \dots S_k$. For any $S_i$ we have two numbers: $l_i$ and $h_i$. We need to figure out if there is such a subset $T$ of $S$, that for any $i$ we have $l_i \leq |T \cap S_i| \leq h_i$.

Prove that this problem is in NP & NP-complete by reducing 3SAT to it.


texts: Using backtracking to find all possible permutations in a string

texts:
I came across this algorithm in a book, and have been struggling to understand the basic idea. The books says it uses backtracking to print all possible permutations of the characters in a string. In Python, the algorithm is given as:

def bitStr(n, s):
    if n == 1: return s
    return [digit + bits for digit in bitStr(1, s) for bits in bitStr(n - 1, s)]

print(bitStr(3, 'abc'))

I'm pretty weak in algorithmic thinking and am struggling for both an intuitive understanding of this, as well as tracing it. Can somebody explain what this algorithm does and how exactly is uses 'backtracking'?


texts: Delete a node with 2 children in a binary search tree

texts:
Recently in class we learned how to delete a node from a binary search tree. Since in a binary search tree, each node can have at most 2 nodes, there are 3 cases of deletion.

Case 1: The node is a leaf node. In that case you can simply delete the pointer to that node and free up the memory for that.

Case 2: The node has one child. In that case, you can connect the parent and child of that node and delete the pointer to and from the node you want to delete.

Case 3: The node has 2 children. Here is where I'm having a bit of a problem. Let's assume we have the following example.

I want to delete the node "4". To do this, I go to the largest integer node on its right side, i.e. "5" and swap their values. So 4 becomes 5 and 5 becomes 5. The I can simply delete the node "5" and I'll be done. Is this approach correct or am I missing anything?


texts: Do poly-time algorithms exist whose time complexity is unprovable?

texts:
If not, is there a decision procedure that successfully classifies any
polynomial time algorithm as poly-time within a time polynomially bounded
by the length of the input algorithm?


texts: NPDA, guessing capability and stack as an exclusive resource

texts:
Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA).

We can view a nondeterministic transition as a guess; for example if $L = \{x x^R \}$ then an NPDA can guess the middle of the string and correctly recognize $L$.

But this kind of guess "cosumes the stack resource", and the NPDA cannot use it to "accomplish another task" in parallel, so it fails recognizing:

$L = \{ xy \in \{0,1\}^* \mid |x| = |y| \text{ and } x,y \text{ contain the same number of 1s}\} $

  I'm wondering if this type of approach to NPDAs has ever been considered and studied ?
  In particular does there exist a "classification" of "structural properties" (invented term) of a CFL language that require a guess and/or an "exclusive use" of the stack.


texts: scale-free networks and adjacency matrix

texts:
Given a distribution over graphs with $n$ nodes having the "scale-free" property, I would like to compute for a pair of vertices $(a,b)$ the probability that they are connected (or more precisely the probability that there is a directed edge from $a$ to $b$).

Is it possible to have such probability distribution ?

Note that the case without the "scale-free" property is not a problem. I can define the probability of having an edge from $a$ to $b$ as $P((a,b))=1/2$ for all $a, b$, $a \neq b$ in the graph.

Thank you.


texts: How to use machine learning algorithm for different input data?

texts:
Yes, You heard it right. My title is "How to use a machine learning algorithm for different input data?",

For example, we have an algorithm called "Email spams detector". Okay, so how to apply the algorithm for 1M users with different input data? because each user creates its own data. So instead of training 1M for every single user. Do we have any method to train once for different input data?

To answer what do I mean by different input data:

For example, I have a time series data collected from a server called "Server A", the data consists of attributes like (CPU level, ram level, protocol...). Next, I put the data collected from Server A to "model X" to predict the server's usage. Now I have a data center with hundreds of servers. Are there any ways to train these hundreds of servers' data once with the same model (model X)? Of course, I don't want to train hundreds of times with model X to get the prediction.


texts: Efficiently finding the maximum pairwise GCD of a set of natural numbers

texts:
Consider the following problem:
Let $S = \{ s_1, s_2, ... s_n \} $ be a finite subset of the natural numbers.
Let $G = \{$ $\gcd(s_i, s_j) \mid s_i, s_j \in S,$ $ s_i \neq s_j  \}$ where $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$
Find the maximum element of $G$.
This problem can be solved by taking the greatest common divisor of each pair using Euclid's algorithm and keeping track of the largest one.
Is there a more efficient way of solving this?


texts: Constrained Smallest Enclosing Ball Problem

texts:
Let $X = \{x_1, x_2, ..., x_n\} \subset \mathbb{R}^m$ be a finite set of points. Smallest enclosing ball is a well-known problem that asks for the $m$-ball that covers all $x_i \in X$, while having the smallest radius possible.

I am interested in solving a related, more constrained problem. Namely, in my version, the enclosing $m$-ball's center can not be chosen freely, but is constrained to be one of the points in $X$. In other words, I would like to find the point $x_j \in X$ such that the maximum distance (i.e. the enclosing radius)

$$\max_{x \text{ } \in \text{ } X} \; \lVert x - x_j \rVert$$

is minimized.

Obviously, one can simply compute all distances in $O(m n^2)$ time, and find the desired point. A less naive way to tackle the problem would be to generate a space-subdividing acceleration structure, say a kd-tree. We can do this in $O(m n \log n)$. Then, per-node maximum distances can be computed in $O(f(m, n))$ time, and we can pick the node having the minimum-maximum distance. This method would have a complexity of $O(n (f(m, n) + m \log n))$. Here, $f(m, n)$ is a function that stands for the query complexity of the kd-tree. Therefore, $f(m, n)$ "looks like" $m \log n$ for small $m$, but $m n$ for large $m$.

All in all, we would still be making many repeated (and unnecessary) distance computations. Also, because of how $f(m, n)$ behaves, the latter method degrades to the former for big $m$. Therefore, even the latter solution is not very satisfactory.

Can we do better? What is the best (in terms of time complexity and practical performance) known algorithm to tackle this problem?


texts: Why don't 2 GPUs double the graphics performance of a computer compared to a single GPU?

texts: Obviously, if you have 2 GPUs, it is double the hardware, and thus it should be double the power of a single GPU (assuming all GPUs are the same, of course). So why is this not the case? I searched this question on Google and things about optimization and things came up, but I still don't understand.


texts:
Consider the following scenario. There are N localities in a town where population for locality $L_i$ is denoted by $P_i$, $i \in {1,\ldots,n}$. We need to place K hospitals around the town in a way that the cost of accessing the hospital is minimized.

We are basically trying to
$$\min_O(\sum_{i=1}^N P_i \times C(d(L_i,O(L_i))))$$
where, $$O(L_i) = \textrm{Nearest hospital's location to }L_i\\d=\textrm{Euclidean distance between 2 locations}\\C = \textrm{Cost function to travel distance }``d"$$

It doesn't seem we can use gradient descent. Consider 3 localities $L_1,L_2$ and $L_3$ and 2 hospitals $H_1,H_2$. If we initially put $H_1,H_2$ on $L_1,L_2$ e.g.

$$L_1H_1\ldots L_2H_2 \ldots L_3$$

If the gradient descent starts moving projects to the right, then we may find ourselves in the following situation. The final location of nearest hospital to $L_2$ would have changed from $H_2$ to $H_1$.

$$L_1\ldots H_1L_2 \ldots H_2L_3$$

So could you please give me some pointers on how to solve this problem?