texts:
I need fast (not worse than about log of the sum of maximum number of nodes and the maximum number of subnodes per node) and fully persistent trie.
I need an easy (quick to code) implementation.
The best thing I came up is a HAMT with each node storing its subnodes as a red-black tree. But that would be (log ...)^2 not (log ...).
Anything more suitable for my problem?


texts:
In a two-dimensional grid, there are $n$ "snakes" (sets of contiguous grid-blocks). The snakes do not touch each other. The goal is to cut the grid into $n$ rectangles using $n-1$ "fences" (horizontal or vertical lines along grid lines, from edge to edge or to a previously-built fence). It is allowed to "trim" at most a single sqaure from each snake (by all fences together).

Below is an example with $n=3$ snakes. Fence #1 runs from edge to edge and trims a square from the bottom snake. Fence #2 runs from the leftmost edge to fence #1 and trims a square from the upper-left snake.

Below is another example with $n=4$ snakes.

Finally, here is an example where the snakes cannot be separated, since each initial fence would trim at least two squares from one of the snakes.

QUESTION: Is there a polynomial-time algorithm for deciding whether or not it is possible to separate the snakes?

NOTE: without the option to trim a single square from each snake, there is a simple greedy polynomial algorithm: at each step, find a horizontal or vertical fence that can be built without trimming any snake. If such a fence exists, build it; otherwise, declare that it is impossible.


texts: Is it possible to get information from websites as a human?

texts:
If I want to read any websites and get some information as names (or dates) on some part of the site as a human. What solution I could use in order to get these datas using deep learning or machine learning?. Is it possible?.. it is not necessary artificial inteligence? .... or maybe it might be as a part of a Phd thesis about machine learning?... If someone has a PAPER about it, could you share it with me?.

Sorry I dont know a lot about this topic.


texts: Invertible function that randomizes order

texts:
I am looking for an invertible discrete function $f:\{0,1,2,\dots,n-1\} \to \{0,1,2,\dots,n-1\}$ for some given integer $n$.  I want $f(0),f(1),\dots,f(n-1)$ to return all the integers in range $[0..n)$ exactly once, but in a "messy", random-seeming arrangement.  I anticipate that $n$ will be not bigger than $2^{30}$.

I thought about finding a generator for the group <Zn,*>, but I'm not sure if it would work for any given $n$ (would it?).  Any other ideas?


texts: Selecting a node of a singly-linked list such that the probability of each node being selected is equal

texts:
The Question: You are given a singly-linked list with n nodes that you can only iterate through once at most. You are given additional space to store one node (i.e. a pointer to it).  Devise an algorithm that can operate under these conditions, choose/select one node from the list such that the the probability of each node being selected/chosen is equal.

My Friend's Solution:

Store the first node in the additional space.
Move to the next node.
Randomly select one node between the one in the additional space and the current node.
Store this "winner" in the additional space.
Repeat steps 2-4 until the last node in the list is processed.
The node stored in the additional space at the end is the one that the algorithm selects.

My Issue With My Friend's Solution: Consider the case n = 3. There are 2^*(n-1) = 2^2 = 4 possible ways to go through the list in terms of which node is selected during each iteration of the algorithm:

Select 1 -> from (1, 2) select 1 -> from (1, 3) select 1 -> 1 is finally selected
Select 1 -> from (1, 2) select 1 -> from (1, 3) select 3 -> 3 is finally selected
Select 1 -> from (1, 2) select 2 -> from (2, 3) select 3 -> 3 is finally selected
Select 1 -> from (1, 2) select 2 -> from (2, 3) select 2 -> 2 is finally selected

Then, node 3 has a 50% chance of being selected, whereas nodes 1 and 2 each have a 25% chance of being selected.

Intuitively, this makes sense to me; if the first node is not selected while the beginning of the list is being processed, it can never be the one that is finally selected. However, the last node still has a chance of being selected no matter what happens while processing the the rest of the list that comes before the last node.

However, my friend says that my issue with his solution is inconsequential because I didn't model the situation correctly. Can someone tell me where I went wrong?


texts: What is partial expansion in Monte Carlo Tree Search?

texts:
I'm trying to understand the modification to the MCTS algorithm called Partial Expansion.

From what I've been reading it enables one to not require all child nodes to have been expanded before expanding grandchild nodes.

However, I'm having a hard time conceptually understanding this process and its potential benefits. Can anybody please help me out?


texts:
I'm recently reading some papers on the maximum independent set problem, all the algorithms' time complexity is donated by $O^*()$ notation, like $O^*(1.0836^n)$. One paper says "the $O^*$notation suppresses polynomial factors in the input size."  I'm a little bit confused and couldn't find helpful materials on the Internet. Could you guys clarify it for me? Any related literature or links will be appreciated.

Thanks in advance!


texts: Number of ways to bicolor a graph with some constriants

texts:
Given a graph G, I need to find the number of ways to color it using two colors Black and White.
Constraints:

G will already have some nodes colored Black.
Every node of color White needs to have one or more Neighbors of color Black.

The nodes that are colored Black will always be leaf nodes.
Vertices<=32
Edges<=Vertices^2


texts: Preserving connectivity from a vertex by edges deletion

texts: Given a connected graph $G$ and a vertex $v$, is it polynomially solvable to find a maximal cardinality set of edges incident to $v$, which deletion (still) leaves vertex $v$ to be connected with all the other vertices in $G$?


texts: How can we prove that radix sort correctly sorts an array of 2 elements with 2 digits each ?


texts: What happens when we increase or decrease capacities in the minimum flow?

texts:
I am confused from these 2 true-false questions on the max flow and am seeking clarity on the basics.

If in a network we increase the capacity of an edge in the minimum cut, the maximum
flow gets increased.
If in a network we decrease the capacity of an edge in a minimum cut, the maximum
flow gets decreased.

My thoughts:

Increase case: I think this is not always true as increasing the minimum could result in what was originally the $2^{nd}$ min flow becoming the lowest value and thus the new max flow. Hence because it isn't always true, the answer is false. This question indicates that max flow needs to be recalculated.

Decrease case: I think this is true because we already have the minimum cut so lowering the minimum brings us to a new minimum. Hence the answer is true.

Is my reasoning correct or is there something I misunderstood.


texts: Prove NP-completeness of deciding satisfiability of monotone boolean formula

texts:
I am trying to solve this problem and I am really struggling.

A monotone boolean formula is a formula in propositional logic where all the literals are positive. For example,

$\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5)$

is a monotone boolean function. On the other hand, something like

$\qquad (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor x_3) \land (\neg x_1 \lor x_5)$

is not a monotone boolean function.

How can I prove NP-completeness for this problem:

  Determine whether a monotone boolean function is satisfiable if $k$ variables or fewer are set to $1$?

Clearly, all the variables could just be set to be positive, and that's trivial, so that is why there is the restraint of $k$ positively set variables.

I have tried a reduction from SAT to monotone boolean formula. One thing I have tried is to substitute a dummy variable in for every negative literal. For example, I tried replacing $\neg x_1$ with $z_1$, and then I tried forcing $x_1$ and $z_1$ to be different values. I haven't quite been able to get this to work though.


texts: For what values of A and B is the gap-VC-[A,B] problem NP-HARD?

texts:
For which values $A,B$ is the problem $\mathsf{gap\mathord-VC}\mathord-[A,B]$ NP-hard? VC is the vertex cover problem. I am given three options: $B=\frac{3}{4},A=\frac{1}{2}$ or  $B=\frac{3}{4},A=\frac{1}{4}$ or none.

I would to review what I think that I need to do, I'm not sure that the way I think of it is correct. This is what I think: I need to decide if it NP-hard to approximate the VC to $\frac{1}{2}$, i.e., can I build an NP Turing machine that would return Yes iff for a given graph, it can guarantee that it has less than $\frac{1}{4}V$ vertices that cover the whole graph? Maybe even for $\frac{1}{2}V$ vertices?

 This is a question from a past midterm that I'm solving now in order to prepare myself for my own midterm in a "Computational Complexity Theory" course.


texts:
I have N by N symmetrical matrix with each side having the same items.

     A    B    C    D
A    0
B    4    0
C    8    3    0
D    3    1    8    0

In reality this would be much larger (100 x 100)

I am trying to find a subset of a fixed size in this matrix with the highest score. For example the selection ABC would be:

  AB = 4;
  AC = 8;
  BC = 3;
Total  15

It is kinda like traveling salesman problem, but with the final distance only determined by the final selection.


texts: Asymptotic Properties of Functions in Complexity Analysis

texts: When dealing with the analysis of time and space complexity of algorithms, is it safe to assume that any function which has tight bounds ( i.e. $f(n)=\Theta(g(n))$ is asymptotically positive and asymptotically monotonically increasing.  I mean that for all $n$ greater than or equal to some $n_0$ both those properties hold?


texts: Insertion of n consecutive keys in an initially empty B-Tree

texts:
Consider this question ( 18.2-4 of CLRS) which states that:

Suppose that we insert the keys ${1,2,...,n}$ into an empty B-Tree with minimum degree 2. How many nodes does the final B-tree have?

My approach:
We add each element one by one. We'll need 3 elements at first (namely 1,2 and 3), after which the $4th$ element will cause a split. This split is  a root node split.
A normal node split results in one extra node.
A root node split results in 2 extra nodes.
Thus after the 4th element we have 3 nodes in total. Now, as we keep on adding more elements to the B-tree, we can see a pattern in splitting. 3 lower level splits initially produce a higher level split, and then each higher level split will require 2 splits only. Since we've to approximate only, we can disregard the initial 3 split condition and go on with the 2 lower level splits to produce an upper level split.
Notice that there is atleast a split at the insertion of these elements: $4,6,8,10,12...... $
That are all even numbers leaving 2.
Thus total such splits are $n/2$
Total higher level  splits are thus:$n/4$
Total splits for the higher level than the previous one: $n/8$
Thus the total splits until the $nth$ element is inserted in the B-Tree is:
$n/2+n/4+n/8+......$
Which results in $n$.
This is more than expected. I've made two approximations here:
1)  Number of higher level splits is equal to half of the immediate lower level splits.This increases our answer.
2)  Some starting elements don't contribute to the splits.
Maybe these are the reasons why the answer is coming more. I can't enumerate these values exactly. Finding these values exactly would help me very much. Any help appreciated.
Moon


texts: Algorithm for solving system of congruences

texts:
I'm trying to understand an algorithm shown in my textbook for solving a system of congruences. The problem states:

Let $r$ and $m$ be arrays of size $n$, such that every two numbers (modulos) from $m$ are coprime. Find $x$ such that

$$x \bmod m_0=r_0\\x \bmod m_1=r_1\\...\\x \bmod m_{n-1}=r_{n-1}$$

So yeah, the classic congruence system problem. The naiive approach is shown first and then comes this:

  Let $M = m_0 \cdot m_1 \cdot ... \cdot m_{n-1}$. Let's assume we can
  find the numbers $w_0, w_1, ...w_{n-1}$ such that $w_i \bmod m_i = 1$
  and $w_i \bmod m_j = 0$ for $i \neq j$. So we're finding numbers $w_j$
  such that it is divisible by every number except for $m_j$ where the
  remainder is $1$. Then the solution x can be constructed as: $$x =
 r_0\cdot w_0  + r_1\cdot w_1 + ...+r_{n-1}\cdot w_{n-1} (\bmod M)$$

Well I guess my question is simply - why? I can't seem to reason this out.
It seems to me that $x$ is always going to be zero. If we take the sum given above and break it up into sums
$$(r_0\cdot w_0)\bmod M + (r_1\cdot w_1)\bmod M + ...$$

it seems like everything should be zero? Let's take the first expression $(r_0 \cdot w_0) \bmod M$. We've got $r_0$ times something that's a multiple of every $m$ except for $m_0$ (because of the way the numbers $w$ were defined), meaning that whole thing will be a multiple of every $m$ except for $m_0$. And then we're taking a modulo $M$ which is also a multiple of every $m$.

How does this give us a solution? The textbook is pretty vague about this and doesn't explain why it works this way. So, any ideas?

Thanks.


texts: Turing recognizable & decidable: binary strings with even length. Let A = {(M) | M is a DFA such that L(M) is not the same as EVEN}

texts:
Having trouble with this homework problem. In order to show that A is Turing recognizable and decidable.

$\text{EVEN} = \text{binary strings with even length}$

$Let\;A = \{(M) | \,M\; \text{is a DFA such that L(M) is not the same as EVEN}$

$\text{Show that A is Turing-recognizable}$
$\text{Show that A is decidable}$

So, at first glance it seems we need to just find a word that M accepts that is an odd length binary string. I'm a bit lost at where to start though.

I believe I'd start by using the TM from Theorem 4.1 of Sipser's Introduction to Theory of Computation which states if a DFA is a decidable language we can use Turing machine T to test if it's decidable:

$\text{T = "On input (B,w) where B is a DFA and w is a string:}$

$\text{Simulate B on input w}$
$\text{If the simulation ends in an accept state - accept, otherwise reject"}$


texts: How can we add back edges in Ford - Fulkerson algorithm?

texts:
I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent to sending -x units from B to A, so we add a back edge from B to A of capacity x units. And the FF algorithm can send a flow of x units from B to A in the future.
But the property of a directed graph is that you can go from A to B and not from B to A.
As an analogy let me take the traffic network and say the path from A to B is one-way. Adding a back edge and sending a flow via that back edge contradicts with our assumption that the path from A to B is one-way.
Am I missing something? Or there is a better intuitive way to understand this?


texts: Best way to preserve SSD health when performing routine delete operations?

texts:
I'm coding an application with a mechanism that performs routine disk cleanup (on smartphone devices, which all use solid-state drives). I want to limit the disk usage to a certain threshold and see two approaches:

Whenever disk usage goes above the threshold by even a single byte, delete as many files as needed until usage is below the threshold. This means fewer delete operations per run but the task itself will be performed more frequently.
Whenever disk usage goes above the threshold by a certain factor (i.e. 1.5x), delete as many files as needed until usage is below the threshold. This means more delete operations per run but the task itself will be performed less frequently.

Apple Developer guidelines explicitly warns developers against wearing out the SSD by performing unnecessary write and delete operations. Is there a difference between the two approaches above in terms of preserving the health of the SSD?


texts: Longest common sub-sequences with a condition

texts:
A sequence is called good if it contains at least one pair of numbers which are adjacent and equal. A good sub-sequence of an array is a sub-sequence of that array which is good and has maximal length.
Now you are given two arrays $S$ and $T$ with integers. You need to find a sub-sequence which is common to both arrays, has maximum length, and is a good sub sequence.
This is a pure dynamic programming problem, in which states ( I am not sure,but is is my guess) are $dp[i][j]$  is answer for $S[1:i]$ and $T[1:j]$ ($A[1:i]$ means subarray of $A$ from $1$ to $i$). But I could not find transition between states, could anyone help me.
P.S - Problem link


texts: Trying to Classify MNIST where pixels are shuffled with a seed.Why is it not working?

texts:
I transformed the MNIST dataset as follows:(X (70000 x 784) is the training matrix)

np.random.seed(42)
def transform_X():
    for i in range(len(X[:,1])):
        np.random.shuffle(X[i,:])

I had thought that shuffling the pixels in an image would make the digits unrecognizable by humans,but the machine learning algorithms would still be able to learn from the images with shuffled pixels correctly.

I cannot understand the mathematical reason behind not learning. Do you think this should work and I should recheck my code for any mistakes?
I trained on SVC and SGDClassifier of sklearn.Results from both are just randomness.


texts: The maximum number of uniquely intersected elements from the all possible intersection scenarios among the sets in a two-column matrix

texts:
Let us define a $n \times 2$ matrix M consisting of integer sets, such
  that the first column consists of the so-called intersecting sets,
  and the second column consists of the so-called intersected sets.

Also, for each element $a_{i,j}$ in $M$, $a_{i,1} \supset a_{i,2}$, i.e. i-th intersecting set is a superset over the i-th intersected set.

Let us define a single intersection chain as an ordered subset of indexes of $M$ which always ends with $n$. E.g. for $n = 3$ the intersection chains can be: (1,2,3) or (1,3) or (2,3). Also, in intersection chain each index intersects the succeeding indexes of a chain.

  Also, let us assume that for each integer $a$ in the intersecting set $a_{i,1}$ of a chain,
  $a_{i,1}$ can only intersect at most one $a$ from all occurrences of $a$
  in the higher indexed intersected sets of the chain.

E.g. Let (4,5,6) be an intersecting chain, and let $a_{4,1} = \{8,9,10\}$. Assuming that sets $a_{5,2} = \{8\}$ and $a_{6,2} = \{8,11\}$, then only one intersection of integer 8 by $a_{4,1}$ should be accounted since $a_{4,1} \cap \{a_{5,2} \cup a_{6,2} \} = \{8\}$.

Finally, we define an intersection scenario as a set of disjoint intersection chains such that all $n$ elements are present in the chains of the scenario. I.e. no two chains are the same and all $n$ elements are present in the chains of a scenario.

  What is the maximum number of the intersected integers among the all possible scenarios? Is there a low-complexity algorithm or mathematical method which can derive this number?

Example:

Given the following matrix:

$M = \begin{bmatrix}
    \{ 1,2,3,4,5,6 \}       & \{ 1,2,3,4,5,6 \}   \\
    \{ 1,2,3,4,7,8 \}       & \{ 1,2 \}   \\
    \{ 3,4,5,6,7,8 \}      & \{ 3,4,5,6,7,8 \}
\end{bmatrix}$

There are two possible intersection scenarios:

scenario 1: ((1,2,3)),

i.e. $a_{1,1}$ intersects $a_{2,2}$ and $a_{3,2}$,

and $a_{2,1}$    intersects $a_{3,2}$

scenario 2: ((1,3),(2,3)),

i.e. $a_{1,1}$ intersects $a_{3,2}$,

and $a_{2,1}$ intersects $a_{3,2}$

The maximum number of uniqely intersected integers in scenario 1 is 8 since in this scenario:

$a_{1,1} = \{ 1,2,3,4,5,6 \}$ intersects the following six integers from $a_{2,2}$ and $a_{3,2}$: $count(\{1,2,3,4,5,6\}) = 6$, and
$a_{2,1} = \{1,2,3,4,7,8\}$ intersects the following two integers from $a_{3,2}$: $count(\{3,4\}) = 2$

The maximum number of uniqely intersected integers in scenario 2 is also 8 since in this scenario:

$a_{1,1} = \{ 1,2,3,4,5,6 \}$ intersects the following four integers from $a_{3,2}$: $count(\{3,4,5,6\}) = 4$, and
$a_{2,1} = \{1,2,3,4,7,8\}$ intersects the following two integers from $a_{3,2}$: $count(\{1,2,7,8\}) = 4$

  NOTE: I am aware of the solution where the scenarios can be
  generated and the intersected integers computed, as given in the
  example. This may be done since there is a number of ways to partition
  a set of elements in non-empty disjoint subsets (called Bell number).
  However, I am interested in a low-complexity solution for a given
  problem.


texts: Reduce duplicate subset sum problem to distinct subset sum problem?

texts:
In duplicate subset sum problem (DuSSP), we are given a multiset $\{a_1,a_2,\ldots,a_n\}$ where some of the $a_i$ are duplicates. We can assume that $a_1\leq a_2\leq \cdots\leq a_m.$ We are also given a target $s$. The problem is to find a subset of $\{a_1,a_2,\ldots,a_n\}$ that sum up to $s$.

In distinct subset sum problem (DiSSP), we are given a set $\{b_1,b_2,\ldots,b_n\}$ where all the elements $a_i$ are distinct. We are also given a target $t$. The problem is to find a subset of $\{b_1,b_2,\ldots,b_n\}$ that sum up to $t$.

Given an instance of DuSSP, create an instance of DiSSP such that DuSSP is solved iff DiSSP is solved.

What I did so far is. Let $b_i=a_i+i$, in this way we guarantee that all the elements $b_i$ are distinct. I cannot create $t$...!

What I said is the following, given a subset $S$ of $\{a_1,a_2,\ldots,a_n\}$ such that $\sum_{i\in S}a_i=s$. We prove that $$\sum_{i\in S}a_i=s\iff\sum_{i\in S}b_i=s+\sum_{i\in S}i.$$

So, $t=s+\sum_{i\in S}i$, but can we choose $t$ to depend on the solution set $S$?

Is this reduction correct? Why or why not?


texts: Most of us know the correspondence between combinatory logic and lambda calculus. But I've never seen (maybe I haven't looked deep enough) the equivalent of "typed combinators", corresponding to the simply typed lambda calculus. Does such thing exist? Where could one find information about it?


texts: Is the problem of deciding whether two programs have the same semantics decidable?

texts:
If I have program and I want to check whether other programs have the exact same semantics or not, could I always build a machine that could make that decision?

This is a question relevant to information security as metamorphic malware will perform transformations on its own code which will make it look different to static malware detectors while preserving its semantics. If it is possible to write a machine that can detect whether two programs carry the same semantics, then it is impossible to write "undetectable" malware.


texts:
Given the question below:

Consider that, on the procedure below, the variable X is defined globally and the parameters of the vr function are passed by value

procedure vr(u,v) {
   u = 2*u;
   x = u+v;
   u = u - 1;
}

Define the value of x in the end of the following:

x = 4;
y = 2;
vr(x,y);
print(x);

I always knew that parameters passed by value were actually a copy of the original value, but in this case i can't tell what scope is being used for the function.

I also would like to read more about cases like that. If you can, please leave any suggestive material so i can get more in depth of this subject.

I know that this is a very bad practice of naming variables and should be avoided, but in this case i guess it was intentional for the problem.


texts: Do reductions form a total binary relation?

texts:
I was wondering if the following property holds true:

$$\forall A, B \subseteq \Sigma^* : A \leq_m B \lor B \leq_m A$$

And the same for Turing reductions

$$\forall A, B \subseteq \Sigma^* : A \leq_T B \lor B \leq_T A$$


texts: When outputting every timestep of an LSTM, is outputs in timesteps with missing training data also affected by overfitting?

texts:
I'm referring to things like the "timedistributed" layer in Keras or how in Pytorch LSTM the output is included in every timestep.
An example illustrating my question, say I'm trying to simulate 100 years of rainfall time series across 40 different locations. I designate 10 of those locations as my test dataset and 30 locations as my train dataset. Rainfall measurements are sparse throughout the 100 years. If I build a model on the train data and find an error on the test data, can I assume that test error is also an estimate of how good predictions are on days where rainfall data did not exist in the training set? Assuming training and testing data come from similar data distributions based on expert knowledge.


texts: Compilation with a witness / certificate

texts:
Sometimes, to install a program, you have a choice between compiling it yourself or downloading a precompiled binary. In theory (using a new programming language and a new compiler designed specifically for this), is it possible to generate a witness / certificate with the compiled binary such that checking the witness / certificate is very easy when compared to compiling things yourself, but ensures that the compilation indeed yields this binary ?

To avoid trivial answers, I'll specify things a bit more: The source language should contain ML, and the target language should be some realistic assembly language. The compiler should do many optimizations so that speed of the compiled program is comparable to that of OCaml, and in particular the compilation can not be just concatenating an interpreter and the source.

From what I've read, the longest thing in compilation is the optimizations. So my question is more or less: Can optimizations run much faster on a non-deterministic machine (in which case, we can use the witness to know which path to take on the real machine).


texts: Computational complexity of Wang tiling of a finite plane

texts:
For a given set of Wang tiles on an $L \times L$ plane (where a tile is $1\times 1$) we first need to determine whether a tiling of the plane is possible. If so, we can then consider the problem of how to construct such a tiling.

Is it known what the computational complexity of these problems are (i.e., how they scale with $L$)?

I've searched and found a lot of interesting info about the problem. But I've seen no statement of a complexity.


texts: Graph ordering with smallest max vertex "discrepancy"

texts:
Consider an undirected graph $G=(V,E)$ and a bijective function $f:V \rightarrow [|V|]$ which orders the vertices by mapping them onto the first $|V|$ natural numbers.

Define the cost of an ordering of a graph to be:

$$\text{cost}(G,f) = \max_{(u,v) \in E} f(u)-f(v)$$

(I refer to $f(u) - f(v)$ in the title as "discrepancy" to avoid confusion with terms such as length or distance)

Intuitively, if we were to construct $G$ by adding on one vertex at a time and adding the appropriate edges to the already-existing vertices, the cost is how far back in our list of vertices we'd have to go and add edges to.

Question: How difficult is the problem of minimizing this cost? Is there an efficient algorithm for finding an optimal ordering? Also is there a name for this cost that i'm not aware of?

Ideas:

A BFS ordering can do arbitrarily bad on this problem: Consider a complete binary tree -- the optimal cost is $O(\log N)$ but a BFS ordering can cost up to $O(N)$.

A DFS ordering can do arbitrarily bad on this problem: Consider a path graph modified such that each vertex is connected to an additional leaf vertex -- the optimal cost is $2$ but a DFS ordering can cost up to $O(N)$.


texts:
How can I design a sorting algorithm of n elements using a Fibonacci Heap?

Will it be a flavoured version of heap-sort where I replace the heap data-structure with Fibonacci Heap?

Your help is appreciated


texts: Suggest structure for query $sumRange(low,high)$ which returns sum of elements whose key $k$ satisfies $low \le k \le high$ in $\Theta(\log n)$ time

texts:
Suggest a data structure to perform a query $sumRange(low,high)$ which will return the sum of the elements whose key $k$ satisfies $low \le k \le high$ in $\Theta(\log n)$ time.

I found the original problem here (although it's for counting) but it runs in $\Theta(n)$ time. However, I think with additional data structures and/or improvements this can be done in $\Theta(\log n)$.

I think we need a balanced binary search tree, for example, red-black tree.

Then I thought of the following algorithm:

sumRange(low, high)
sum <- 0
temp
closestToLow <- findClosest(low)

if(low=closestToLow)
    sum += closestToLow.key

temp <- successor(closestToLow)
sum += temp.key

It will only find the low point and its successor. I guess we need a similar piece of code to find the high point. Not sure how to traverse in between though.


texts: Is there an analysis of the creation of axioms for a mathematical structure as a computational problem?

texts:
Historically, what has happened is the following:

There is a "mechanical" structure, most importantly, arithmetic, which operates according to a set of well-defined rules that a stupid computer can easily follow. e.g. a computer can easily calculate $5349\cdot 5345=...$
There is a "mechanical" proof-system, most importantly, first order logic, which also operates according to well-defined rules that a stupid computer can follow. e.g. a computer can easily apply derivation rules to go from $\forall x \phi(x)$ to $\exists x \phi(x)$, etc.
Then there is a non-mechanical "creative" human, who uses his badly-understood "natural insight" to formulate a set of "axioms about arithmetic", which are words in (2)'s language "about" the operations of (1)'s arithmetic computations. He also formulates a set of "logical axioms", the rules by which the mechanical proof system should operate. He chooses these rules because his intuitive insight says that they are "obviously correct".

It seems to me that this third element in the chain (though it happens first chronologically), is always done in an ad-hoc way. But the fact that this has always been done this way so far, doesn't mean that it necessarily has to be this way.

My question is: Has there been an analysis of the creation of axioms as a computational problem? That is, of the problem of choosing axioms about some mathematical structure, for use in a logic-language?

This computational problem is essentially: given e.g. the rules of arithmetic, find a first-order statement that we can use as an axiom to then derive further properties.

ps. I know that this is a vague question. I am simply asking whether someone has analysed this problem in some way.


texts: Do all the cells in a recurrent neural network share learned parameters?

texts:
Most descriptions of modern RNNs present a "folded" characterisation, that is to say, a single cell with a loop back to itself transmitting the hidden state from one step to the next. However, in implementations the RNN is computed "unfolded", so a new cell is created for every step of the sequence up to some maximum sequence length, and the state is passed from one cell to the next.

My question is: are the learned parameters shared between all the cells in the unfolded sequence? E.g. in the case of a stack of LSTMs, does each LSTM have its own set of forget, input-gate, candidate and output parameters, or does the whole stack share and update a common set?


texts: Approximability of the edge-disjoint shortest paths problem

texts:
In the edge-disjoint paths problem (EDP), we are given a (possibly directed) graph $G=(V,E)$, and a set of distinct source-sink pairs $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$, and we want to maximize the number of pairs that can be simultaneously connected in an edge-disjoint manner. When we add the constraint that the paths need to be shortest paths, we get the edge-disjoint shortest paths (EDSP) problem.

According to [1], the EDSP problem is hard for a graph with unit edge lengths, even when the graph is planar. Furthermore, it claims this is so for both directed and undirected graphs.

  What is known about the approximability of the EDSP problem?

I'm especially interested in results for undirected graphs. In [2], the authors seem to only consider variants of the EDP problem, but not the EDSP problem. Further following the references, it seems like the EDP problem has been studied extensively.

[1] Eilam-Tzoreff, Tali. "The disjoint shortest paths problem." Discrete applied mathematics 85.2 (1998): 113-138.

[2] Guruswami, Venkatesan, et al. "Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems." Journal of Computer and System Sciences 67.3 (2003): 473-496.


texts: Turing Machine that computes maximum steps of halting machines

texts:
Suppose that $TM_{halting}$ is the set of machines that halt.

Given a number of states $m$ and a length $n$ of the input, let $f(m,n)$ be the maximum number of steps a machine with $m$ states in $TM_{halting}$ can take on an input of length $n$.

Is the function $f(m,n)$ computable?


texts: Machine with an oracle for a language that cannot decide another language in polynomial time

texts:
We usually see examples of languages contained in $P^A$ for some language $A$, or cases where $P^A=P^B$ (or $P^A\subseteq P^B$) for two languages $P^A$ and $P^B$.

However, there is any explicit example of two languages $A$ and $B$ such that $P^A\not\subseteq P^B$ and $P^A\not\supseteq P^B$?

I was thinking in something like $\mbox{HALT}$ and $\mbox{EMPTY}$ but Yuval Filmus made me see that in fact $P^{\mbox{HALT}} \subseteq P^{\mbox{EMPTY}}$, because $\mbox{EMPTY}$ is stronger than $\mbox{HALT}$. Nevertheless is possible to find an explicit language satisfying the desired property? What about $\mbox{FINITE}=\{<M>: L(M) \mbox{ is finite}\}$, it can be compared with $\mbox{HALT}$ in the same way as $\mbox{EMPTY}$?


texts: Algorithm to find the size of a quotient of a free group

texts:
Are there any algorithms to find the size of an algebraic quotient of a free group? It would take the generators as input and output the size. For example, an input could be something like
{a,b: a^8=b^2=1, ab=ba^3} (a quasidihedral group), and the output would be the integer 16, since there are 16 different ways to write a string formed of a's and b's if you treat aaaaaaaa and bb as the empty string, and the string ab as the same as the string baaa.

Ideally the algorithm would also be able to say if a group was infinite. It's not obvious by looking at the presentation what the size of the group is, and I think it's a fairly interesting question that I've comes across a few times in my algebra class, so I was surprised that I couldn't find a tool to solve it for me or any papers talking about it, it seems that computers should be good at this. Wondering if anyone has any good ideas.


texts:
I'm having a little problem with the abstraction layers in linear types. If every variable is used exactly once, there is no way to copy data, since you have to read each datum twice in order to write it twice to two different locations.

However, you could argue that once a variable is loaded into a register, you may do whatever you want with it, so a -> (a,a) is a possible function. I'm simply not sure where the line is drawn, or why.

Linear types in programming allows a compiler to build efficient pipelines of data transformation. Single-use variables allows in-place mutations in pure functional languages, and/or a memory-efficient implementation without using a garbage collector. Copying a value might make this process a lot more difficult, if not impossible, but I'm not sure.

Is it possible to copy data in a linear type system? Why?
Are there any (big) programming languages that implement linear types with/without copying?


texts: Paxos: Accepting Proposals With Different Values and Consensus in Paxos

texts:
I have a number of questions about Paxos which I can't answer in full confidence from reading the paper (Paxos Made Simple).

My questions are loosely based around the following quote:

  In Paxos, a value is chosen when a single proposal with that value has been accepted by a majority of the acceptors. However, we can allow for multiple proposals to be chosen, but we must guarantee that all chosen proposals have the same value.

The first property, P1, states:

  P1: An acceptor must accept the first proposal that it receives.

Therefore, if we have an proposer, which sends an prepare(n) statement to a majority of acceptors, this majority can always respond to a prepare request, and because this is the first proposal, the majority must accept this proposal.

However, in the case where multiple proposals are proposed at about the same time, it can be possible that no single value is accepted by a majority. For this reason, it is necessary for an acceptor to be able to accept multiple proposals.

Question 1: This means that an acceptor can accept a proposal with a value v2 after it has accepted a proposal with value v1. Otherwise, I don't see how it can be guaranteed that a majority of acceptors accept proposals with the same value. Is this correct?

Now, if we look at P2B:

  If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

And then later:

  If the proposer receives the requested responses from a majority of the acceptors, then it can issue a proposal with number n and value v, where v is the value of the highest-numbered proposal among the responses...

Question 2: Does this mean that if a proposer proposes a value, v1, that is accepted by a majority, it is now impossible for the same proposer, or another proposer, to propose another value, v2? If they want to make a proposal, they must propose the same value, v1? The only way they could propose a different value would be to start a new instance of Paxos. The reason you would want to make a proposal with the same value as the chosen value is because the chosen value might not have been received by any of the learners. Is this correct?

Question 3: Can an acceptor respond to a proposer with a promise if consensus has already been reached?

Question 4: The promises guarantee that a majority of acceptors will always accept a value, because the proposer must receive a promise from the majority of the acceptors before it can send an proposal, correct?


texts: Bloom filter alternative supporting deletion without false negatives

texts:
There are several alternatives to bloom filters that support deletion from the set, for example Cuckoo filters or Counting Bloom filters.
However, deleting an element from these data structures assumes that the element really is in the set. Deleting an element that is actually not in the set might introduce false negatives.
Is there a data structure that avoids this problem, trading it off against something else?


texts: physical significance of membership function greater than one

texts: In fuzzy logic, when we associate an element with a set, we usually do it in terms of membership grade which suggests the "belonging" of this element to the set. Membership grade value 0 means that the element is certainly not the set member while grade value = 1 means that the element is definitely a part of the set. In some problems that I was solving, I came across membership grade values of some elements greater than 1. What does it actually mean?


texts: algorithm for encoding segmentations in RGBA data

texts:
I'm trying to figure out a good way of encoding object segmentation data into a single RGBA image. I'd like to not only distinguish between classes, but also individuals within classes, and be able to have multiple classes and objects per pixel.

For example, I could have a pixel represent both "road sign" and "speed sign" classes, as well as indicating that the particular collection of pixels belongs to one individual.

Is the pairing function my best bet? How would I calculate the maximum number of classes and objects I could encode in a 32bit value? I guess I'm looking for a reversible 32 bit hash function.

https://en.wikipedia.org/wiki/Pairing_function


texts: What is name of type " Function->Value->Bool = if (Bool) Function (Value) " in Category theory?

texts:
I am very new to functional programming so sorry if the question is stupid.
Having this function
const noname = func => val => bool => bool? func(val) : val

And following situation
// if event.target has css class 'draggable-box' , add drag listener to it, using event
compose(
    noname( add_drag_listener )(event),
    elem_has_css_class('draggable-box'),
    prop('target'),
)(event)

In Category theory, what is the correct name for the noname function? Is there such a type?


texts: Turing machine M overwrites a non-blank char by B (Blank)?

texts:
What are the implications of a non-blank character being over-written by a Turing machine M for the given input variable 'x'?

Intention of the question: I am trying to answer how the halting problem can be made decidable provided we have a TM which can say whether 'M' overwrites a non-blank character by Blank or not?


texts:
Consider that a currency system has $k$ denominations $d_0, d_1, ... d_{k-1}$. $d_0, d_1, ... d_{k-1}$ are such that $d_0 < d_1 < ... < d_{k-1}$ and $d_i$ divides $d_j$ for all $0<=i<j<k$. Example: ₹1, ₹5, ₹10, ₹20, ₹40, ₹80. As a cashier at a cash register I need to service $n$ customers, buying things that are worth $p_0, p_1, ... p_{n-1}$, and they pay me $c_0, c_1, ..., c_{n-1}$ (and of course, customers pay enough money i.e, for all $i$ in $0, 1, ... n-1$, $c_i>=p_i$).

I start with no cash at hand (if $|d_j|$ denotes the number of $d_j$ bills/coins I have available, then $|d_i| = 0$ for all $i$ in $0, 1, ..., k-1$).

I have to make change for a customer, if the amount they pay is more than the price of the stuff they want to buy ($c_i > p_i$).

There are two cases where I fail and stop.

I fail at the $m^{th}$ customer where I cannot make change. That is, if the cash I have available at hand
is lesser than the amount I'll have to pay them back (i.e, if they pay $c_m$ to buy something that is worth $p_m$ and, $(c_m-p_m) > (\sum_{i=0}^{k-1}|d_i|*d_i)$). For example, the first customer has to pay the exact change, else I fail at the very first step.
It might be the case that, I have enough cash but I just can't make change (I don't know how to write this down formally, so I'll just give an example: A person buys something for ₹5 and pays me a ₹20 bill, but I happen to have just two ₹10 bills - though I have more money than what's required, I don't have the right denominations).

Given the setup, If I want to serve the maximum number of customers, I think an optimal strategy would be to try and spend higher denominations as much as I can before I use smaller ones. For example, suppose I have three ₹5 bills and one ₹10 bills. To pay back ₹15 I will use one ₹10 bill and ₹5 bill instead of spending the three ₹5 bills at this time.

Is this the optimal strategy ? If yes, how should I prove this is optimal. If not, what is ?

Customers have to be processed one at a time (like an online algorithm), I cannot skip someone and come back to them later.


texts: I know that BFGS is a general quasi-Newton method, whereas Levenberg-Marquardt (LM) is specifically for non-linear least squares (NLLS). That said, is there a big advantage of using LM instead of BFGS for NLLS problems?


texts: Tight analysis for the ration of $1-\frac{1}{e}$ in the unweighted maximum coverage problem

texts:
The unweighted maximum coverage problem is defined as follows:

Instance: A set $E = \{e_1,...,e_n\}$ and $m$ subsets of $E$, $S = \{S_1,...,S_m\}$.

Objective: find a subset $S' \subseteq S$ such that $|S'| = k $ and the number of covered elements is maximized.

The problem is NP-hard, but a simple greedy algorithm (at each stage, choose a set which contains the largest number of uncovered elements) achieves an approximation ratio of $1-\frac{1}{e}$.

In the following post, there is an example of when the greedy algorithm fails.

Tight instance for unweighted maximum coverage problem?

I wish to prove that the approximation ration for the greedy algorithm is tight. That is, the greedy algorithm is not an $\alpha-$approximation ratio for any $\alpha > 1-\frac{1}{e}$.

I think that if I will find, for any $k$, (or for an ascending series of $k's$), an instance where the number of elements covered by greedy algorithm is $1-(1- \frac{1}{k})^k$ times the number of elements covered by the optimal solution, the tightness of the ratio will be proved.

Can someone give a clue for such instances?

I thought of an initial idea:
let $E = \{ a_1 ,...a_n,b_1,...,b_n,...,k_1,...,k_n\}$, a set with $n\cdot k$ elements. Let $S$ include $k$ sets of $n$ elements each, $A = \{ a_1 ,...a_n\},...,K= \{k_1,...,k_n\}$. The optimal solution will select these $k$ sets and cover all the elements in $E$.
Now I want to add $k$ sets to $S$, that will be the solution the greedy algorithm will find, and will cover $1-(1- \frac{1}{k})^k$ of the elements in $E$.
The first such set, of size $n$: $S_1 = \{a_1,...a_\frac{n}{k},b_1,...b_\frac{n}{k},...,k_1,...k_\frac{n}{k} \}$ ($\frac{n}{k}$ elements from each of the first $k$ sets). The second such set, of size $n - \frac{n}{k}$: $S_2 = \{a_\frac{n}{k},...a_{\frac{n}{k}+ (n - \frac{n}{k})\cdot\frac{1}{k}},b_\frac{n}{k},...,b_{\frac{n}{k}+ (n - \frac{n}{k})\cdot\frac{1}{k}},...,k_\frac{n}{k},...,k_{\frac{n}{k}+ (n - \frac{n}{k})\cdot\frac{1}{k}} \}$ , (that is, $(n - \frac{n}{k})\cdot\frac{1}{k}$ elements from each of the first $k$ sets) and so on till we have $k$ additional such sets.

I don't think this idea works for every $k$ and $n$, and I'm not sure it's the right approach.

Thanks.


texts: How strong is an oracle that avoid don't-halt

texts:
Consider such an oracle:

  Given a turing machine[1], return the halting state it falls on, or arbitary result(but don't stuck in) if the TM doesn't halt.

How strong is a TM with the oracle?
Can the oracle exist(or does the question always have an answer) if change [1] into a TM with the oracle?

Some results I get:

It's as strong as a TM with oracle that compare running time of two programs, or arbitary returned value if both don't halt.
If the oracle returns integer the TM returns(may need to define a way it outputs integer), or arbitary integer if it doesn't halt, we can solve the halting problem by getting the runtime and check. However, currently I can't output from the oracle a string of any finite length if the length can be arbitary long, promising it's finite.

(Moved to here)


texts: Which is the equivalent processing of human brain in terms of computer processing?

texts:
How many flops my brain can process, or how many GHz is a human brain capable of?
Is it valid to think that each celular brain is like a small cpu? (like cuda architecture). Our brains works in parallel, right?


texts: Given $k$ sorted lists, $O(n \log k)$ complexity, Mergesort rather than Heapsort

texts:
I was convinced that my idea for a solution to sort $k$ sorted lists into one list would work with a 'variation' on MergeSort. I was told this would not work and had to use Heapsort, but didn't get any explanation or intuition behind it. (I believe the assumption is that each of the $k$ lists had size $\frac{n}{k}$)

Essentially, my intuition behind using Mergesort was that we have $n$ total elements, but all the steps below height $\log k$ in our recursion tree had already been solved. So at height $\log k$ each list is of size $\frac{n}{k}$, so we perform $\frac{n}{k}$ comparisons and $2\frac{n}{k}$ inserts (to form a new list from the two $\frac{n}{k}$ lists) $k$ times in total, which seems to be on the scale of $O(n)$.

We are now one step up on the recursion tree with $\frac{k}{2}$ lists and we will eventually perform $O(n)$ operations $\log k$ times.

Can anyone provide insight as to why this intuition is wrong? Or if right, how I should go about formally proving it?


texts: Building an NFA where where proceeding part of string has same or more 1's

texts:
Having trouble figuring out a NFA for the following language, the objective is to use only 3 states:
$L = {\{1^ky : y \in \{0,1\}^* }\text{ and y contains atleast k 1's, for k} \ge 1 \}$
I have got to as far as the NFA below, which would only work if the y contains clause wasn't included:

So I need a different approach to this, but can't figure out how to go about it. Is there a different way of looking at the language that would make more sense for creating the NFA?


texts: Verification of atomic primitives using Petri Net Models

texts:
I want to verify semantics of a library of atomic primitives that I wrote. The idea is, only if the semantics of all the primitives are consistent with each other, an application that uses them could behave predictably.
For example, a composition of a primitive Fx(lck) which takes exclusive lock on an lck object could be -
Fx(Fx(lck)). But this could lead to a dead lock when operated on a single thread. This is a valid scenario if lck is a non-recursive lock.
I wonder if I could create a Petri Net model of my primitives to check if they are present a perfect synchronization tool.
You can also propose an alternate solution.


texts: Quadratic Diophantine equation - Polynomial Time Cases

texts:
In number theory, solving a Quadratic Diophantine equation (a, b, c constants)
$$
    a*x^2+b*y= c
$$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete.

The solution (x, y) are positive integers.

Query: What are the conditions on values of constants for which solving the problem is Polynomially feasible? Any link to the references?


texts: What the heck is a memory channel "CS bus"?

texts:
While I was reading about memory architecture from the CMSC 22200's Lecture 17 of University of Chicago, I got stuck on determining the meaning of the word "CS" used for describing a bus as part of memory channel:

However I didn't find any additional source pointing out that bus. And furthermore, I found on different reference that:

  The memory channel is made up of a data bus and an address/comm and
  bus.

So, I don't know from where they got the information about the "CS bus"? And what is it exactly?


texts: Finding the rightmost element in an array of duplicate elements using binary search

texts:
i was reading Binary Search in the wikipedia and i came across this part of 'rightmost index of an element in an array of duplicate elements'. i understood the process of determining the leftmost index, but for rightmost index, i am unable to get it.

Here is the link :
Binary search

Algorithm:

function binary_search_rightmost(A, n, T):
L := 0
R := n
while L < R:
    m := floor((L + R) / 2)
    if A[m] > T:
        R := m
    else:
        L := m + 1
return L - 1

How the  the while loop content is derived (Any logical explanation  or example)?


texts: Many to one reductions from undecidable Turing Machine to a decidable language

texts:
From what I read, a many-to-one reduction $A \leq_m B$ means that $\forall x \in A$, there exists a computable function $f$ s.t. $f(x) \in B$. However, $f$ is not necessarily surjective (i.e. not all elements in $B$ have to be mapped).

But what if I try to reduce the language $ATM$ : {$(i,w)$ | $TM_i$ accepts $w$} to a well-known computable Turing-decidable language (i.e. $VERTEX-COVER$) using this function $f$:?

Where $f$: On input $(i,w)$, if Turing Machine $i$ accepts $w$, then a Turing Machine $M$ outputs a Graph $g$ that has a 2-vertex cover (any arbitrary graph with a valid 2-node vertex cover), and does otherwise.

In this case, $f$ is computable, and if $(i,w) \in A$, then $f(i,w)$ = $g \in VERTEX-COVER$. Since many-to-one reductions do not have to be surjective, I do not have to map all elements in the vertex-cover set, and yet, $g$ meets the conditions of the many-to-one reduction. There is also no necessary condition for $f$ to have a 'pullback' function $\hat{f}$, where $\hat{f}$ is an 'inverse' that maps all elements in vertex-cover back to $ATM$ since $A \leq_m B$ does $\textbf{not}$ necessarily imply $B \leq_m A$. (the pullback function $\hat{f}$ holds only if $f$ is surjective, which is not necessary in $\leq_m$).

Given the lemma, if $A \leq B$ and $B$ is decidable, then $A$ is decidable. In this case, $VERTEX-COVER$ is decidable, then $ATM$ should be decidable... which is clearly wrong.

There is something obvious that I am missing here ...


texts: What defines the interaction between CPU, Memory and I/O parts?

texts:
From Wikipedia:

  In computer engineering, microarchitecture, also called computer organization and sometimes abbreviated as µarch or uarch, is the way a given instruction set architecture (ISA), is implemented in a particular processor.

  Computer architecture is the combination of microarchitecture and instruction set.

I kept reading some Q&A like this. Definition says that computer microarchitecture is how ISA is implemented in a processor, but tells nothing about how CPU, memory and I/O interact with each other. Does architecture defines this interaction? For example, which term defines this picture?


texts: Can we write algorithms without conditional statements?

texts:
Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional.

Consider the factorial problem, we would typically define the algorithm as

Solution 1.

int fact(int n)
{
if n == 0 then
 return 1;
else
 return n*fact(n-1);
}

An alternative would be to define the function fact as

Solution 2.

int fact(int n)
{
 if n == 0 then return 1;
 elseif n == 1 then return 1;
 elseif n == 2 then return 2;
 elseif n == 3 then return 6;
 ....
 all cases define as above
}

Also, another solution would be to have functions like:

Solution 3.

int fact0()
{
return 1;
}

int fact1()
{
return 1*fact0;
}

int fact2()
{
return 2*fact1;
}

int fact3()
{
return 3*fact2;
}

Then we would have an array of function pointers p which we would have to index according to the factorial we want to determine, such that p[0] points to fact0, p[1] points to fact1, and so forth.

I know that this might sound dumb, but it actually works! What makes solution 1. a valid argument to show that conditionals are required to compute the factorial?

Some additional thoughts on my part:
1. Is solution 1 the only true "algorithm"? Because the other 2 solutions to not seem to "compute" anything
2. Are conditionals required only because we dont know the results (or execution steps) of functions beforehand?

Thanks in advance


texts: Regular expression for language that does not accept x string (3 letters, |x|=3)

texts: The language I am interested in is $L=\{w∈\{a,b,c\}^*| w$ contains "$bac$" but not "$cab$"$\}$. I am thinking that the result will have the form $L=X_1X_2X_3$, where $X_1=\{w∈\{a,b,c\}^*| w$ does not contain "$ca$" at the end nor "$cab$" anywhere$\}$, $X_2=$"$bac$" and $X_3=\{w∈\{a,b,c\}^*| w$ does not contain "$ab$" at the start nor "$cab$" anywhere$\}$. What I find difficult to express is that "$cab$" does not appear anywhere in $X_1, X_3$ (the situation for "ca" and "ab" is simple because they consist only of 2 letters, we can split $X_1, X_3$ so that the "cab" problem remains). I have tried creating a NFA for this purpose but the automata needs to have quite a few loops (thus it is hard to find the regular expression). My question is whether there is a clever way to find the representation of non-existance of "cab", other than counting all the possibilities in the NFA that accepts such strings. If there is no such way, how can I find the regular expression of L from the start?


texts:
The above answer taken from the book https://www.amazon.com/Operating-Systems-Sibsankar-Haldar/dp/8131730220 says starvation freedom may not imply progress as processes can be deadlocked.

I think that starvation freedom implies deadlock freedom so there is no chance of deadlock and progress is also satisfied.

Is the answer in the picture correct ?


texts:
Ex.1. Give a Search Problem whose deciding Problem is in co-NP.

Assuming 3SAT is in NP then asking wether a given Boolean formula has a Solution is a search problem in NP right?

Then would asking wether a given Boolean formula has no Solution be in co-NP?


texts: Add lines to star with fixed coordinates maximizing smallest angle

texts:
I have the following problem:

There are existing stars (as in graph-theory stars) with a fixed representation in a 2D coordinate space, meaning that angles between the edges are not allowed to change.

Now I want to add additional edges from the star center. Both the amount of existing edges and the amount of edges to add can vary.

How can the new edges be added in a way that maximizes the smallest angle between edges in the resulting star? For this minimization, the angles between newly added edges, as well as the angles between newly added and existing edges are relevant.

Here are two trivial examples, the black edges are the existing ones, the blue ones the newly added:

However, there could also be more complex examples, consider adding a different amount of edges(1,2,3,..) to this star:

Ideally, the algorithm is fast and easy to implement in object-oriented programming languages.

Background:
The underlying use case is drawing of Hydrogens for 2D Molecule depictions. In a software, a 2D molecule depiction might be loaded from a file or even drawn by a user, then, the user can trigger an action, adding missing Hydrogen atoms to all existing atoms.
For each atom (star), a varying number of hydrogens depending on the atom type and charge (usually 1-3), should be added and drawn in a visually pleasing way.

The existing edges and angles can not be modified, because they are given by the user. Small angles tend to look bad, therefore, the goal is to maximize the smallest angle.

Currently, this is done by choosing the largest angle, then adding an edge in the middle. Then repeating this until no more edges are to be added. This is very fast and looks reasonably well, but obviously doesn't always find the best solution.


texts: Where can I find a short and 'easy' peer reviewed paper on something from computability, decidability or complexity?

texts:
It's a homework assignment, we were asked to read, understand, and present to our colleagues a short paper/article (suggested 4-6 pages) for our Computability, Decidability or Complexity class.

The articles I was able to find in the past couple days using google scholar a way over what we were taught, plus, 50-100+ pages is way over the scope of my assignment. In class, we were provided with an introduction to the three topics, complexity classes, relations between them, and (mostly informal) proofs for the most representative problems from each class by modelling them using all kinds of Turing Machines.

Any possible solutions? It's the first time in my life I'm touching anything related to research, I can barely understand even the scope of most papers I find.. I guess any advice would be welcome.


texts: Testing whether a determinant polynomial is identically zero

texts:
Suppose we are given matrices $A_1, \ldots, A_k$ which are $n \times n$ matrices with rational entries and are asked to determine whether the polynomial ${\rm det}(\alpha_1 A_1 + \alpha_2 A_2 + \cdots + \alpha_k A_k)$ is identically zero. How can we do this deterministically in polynomial time in $n$ and $k$?

I'm aware that black-box polynomial identity testing is a difficult problem, but then this is not quite a black box.


texts: Bridge theorems for group theory and formal languages

texts:
Is there some natural or notable way to relate or link math groups and CS formal languages or some other core CS concept e.g. Turing machines?

I am looking for references/applications. However note that I am aware of the link between semigroups and CS languages (namely via finite automata). (Does this literature on semiautomata ever look at "group-automata"?)

I have seen one paper many years ago that might come close, that converts TM transition tables into a binary operation, possibly sometimes a group in some cases, conceivably based on some kind of symmetry in the TM state table. It didn't explore that in particular, but also didn't rule it out.

Also, in particular, regarding the large body of math research on classification of finite groups, does or could it have any meaning or interpretation in TCS? What is the "algorithmic lens" view of this massive edifice of mathematical research? What is it "saying" about a possible hidden structure in computation?

This question is partly inspired by some other notes e.g.:

Use of algebraic structures in TCS
RJ Lipton on Gromov's theorem


texts: Help for implementing the maintenance of the connected components in the Euclidean plane in logarithmic time

texts:
I am aware of a logarithmic-time algorithm to maintain the connected components of graphs in the Euclidean plane (D. Eppstein, GF Italiano, R. Tamassia, RE Tarjan, J. Westbrook, and M. Yung. Maintenance of a minimum spanning forest in a dynamic plane graph. J. Algorithms, 13 (1): 33 {54, 1992.).

Does anyone know if there is an implementation of this work or if there are other results that are easier to implement?


texts: Are there any tetrational-time problems?

texts: I know there exists problems decidable in polynomial-time, exponential-time, etc. I couldn't find any tetrational-time problems, however. Are there any and if not, why?


texts: What is the name of this size method calculating the size of a node?

texts:
My confusion is that if the recursive call calls the left nodes, and then adds with the right nodes, how are the nodes that are to to right of the left nodes and vice versa being called?

int size (BinaryNode t) {
  if (t == null)
    return 0;
  else
    return 1 + size(t.left) + size(t.right);
}


texts: Famous hacker koan: who was it about, though?

texts:
Read this many years ago and can't remember who it was about. Nor can I remember the exact quote. The story goes:

  Famous computer scientist/professor is teaching a class. Student is having some problem w/ a machine and wants to reboot it, hoping to fix the issue. Professor chides him, saying something to the effect of "you can't expect rebooting to fix the problem unless you 'Truly Understand What Is Going On'". Professor then proceeds to reboot the computer and the issue resolves. ;)

Who was it?


texts: if (λ x . x x) has a type, then is the type system inconsistent?

texts: If a type system can assign a type to λ x . x x, or to the non-terminating (λx . x x) (λ x . x x), then is that system inconsistent as a consequence? Is every type under that system inhabited? Can you prove false?


texts:
I am trying to apply MADDPG, a policy gradient algorithm that uses centralized training and decentralized execution, to a project. In the work of Lowe et al., the actor returns a pmf for a discrete actions pace. If I set it to Discrete(5) for each agent, it would return something like [0.1 0.15 0.05 0.34 0.46]. I am confused about how is this deterministic? Shouldn't it collapse to a specific actions [0 0 0 0 1]? Also, then it proceeds to apply these operations for the MPE (multi-particle-environment):
agent.action.u[0] += action[0][1] - action[0][2]
agent.action.u[1] += action[0][3] - action[0][4]

Then in the environment, it seems this u represents the force:
p_force[i] = agent.action.u

Shouldn't it sample from that distribution to take an action? How is it that manipulating the elements of the action can get the force? What is action[0][0] for?


texts: How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work?

texts:
Given a hash function $H:\{0,1\}^*\rightarrow\{0,1\}^n$, a difficulty $d\in\mathbb{N}$, and data $D\in\{0,1\}^*$, the framework of the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $c$ such that $H(c\Vert D)$ starts with $d$ zero’s.  That is to say, Hashcash/Bitcoin Proofs-of-Work appear to find a preimage $c\Vert D$ that partially inverts a hash $H$.  Depending on $d$ and the size of the nonce, it may be impossible to find a nonce $c$ without having to change the data $D$. Currently (Aug. 2017) with Bitcoin, the target difficulty $d$ is, I think, 17 consecutive hexadecimal 0's.

Given a set $S\subseteq\{0,1\}^m$ and a number $K$, the Goldwasser-Sipser Set Lower Bound Protocol is an Arthur-Merlin protocol for Merlin the prover to show Arthur the verifier that $|S|\geq K$.   Letting $k$ be a number such that $2^{k-2}\leq K\leq 2^{k-1}$, Arthur chooses a random hash $H$ from pairwise independent hash function collection, along with a random $y\in\{0,1\}^k$.  Merlin’s goal is to find an $x\in S$ such that $H(x)=y$.  That is to say, Merlin’s goal in the Goldwasser-Sipser Set Lower Bound Protocol is to find a preimage $x$ that inverts a hash function $H$.  The larger the set $S$, the easier it may be to find a preimage.  Indeed, if $S\leq \frac{K}{2}$, then Merlin has a much smaller chance of finding a preimage than if $S\geq K$.  Thus, Merlin may provide evidence to Arthur that $S$ is large.  This may be used, e.g., to show that two graphs are not isomorphic.

My question is: can we reinterpret the Hashcash/Bitcoin Proof-of-Work as a Set Lower Bound?  In other words, can we consider finding a nonce $c$ in the Bitcoin Proof-of-Work as similar to finding a preimage $x$ in the Goldwasser-Sipser Set Lower Bound, which may show that some (arbitrary) set is large?

Or is the similarity between the two not very strong?

EDIT

Following up on D.W.'s answer, I wonder if $D$ could be considered as the input to a test of membership of $x\in S$.  For example, $S$ could be the set of all permutations of two graphs $G_1$ and $G_2$, $D$ might "encode" the two graphs $G_1$ and $G_2$, and $x$ might "encode" a permutation $\pi$ of one of $G_1$ or $G_2$.  The fact that a preimage $x$ was found might indicate that $G_1$ is not isomorphic to $G_2$, because it indicates $S$ is large.

However, I think there may be no easy way to tell what the "encoding" is.  So I wonder if a Proof-of-Work can, by design, be based on some interesting problem in $\mathsf{coNP}$, by having the encodings of the problem specified a-priori.

For example, the adjacency matrix of the two graphs $G_1$ and $G_2$ may be encoded in $D$.  The miner may engage in looking for another graph $G_3$ that is a permutation $\pi$ of one of $G_1$ or $G_2$, such that the hash $H_2$ is $0$.  That is, the miner may treat $G_3=\pi(G_1)$ or $G_3=\pi(G_2)$ as $x$ (i.e. the "nonce" $c$.) The miner may "succeed" if $H(\pi(G_1) \Vert G_1 \Vert G_2)$ begins with $d$ zeroes, or $H(\pi(G_2) \Vert G_1 \Vert G_2)$ begins with $d$ zeroes, thus indicating that the number of permutations of $G_1$ and $G_2$ together is "large" and not "small."


texts:
I am doing some reviewing for the term final on computability and found out this simple exercise. I am very fresh on theoretical computer science so if you do have an answer please make it simple.

The question is fairly simple: Is there any recursive function f whose code is unique? That is $comp(p_1, ) \doteq comp(p_2,) \doteq f $ implies $p_1=p_2$.

$comp$ is the universal recursive function.
That is, the function that for every recursive function $ f: \mathbb{N}^m \rightarrow \mathbb{N}  $, exists a code $p_f$ such that $f  \doteq  comp(p_f, <x_0,x_1,...,x_{m-1} > )$. And $\doteq$ designates equality in Kleene sense.

I found in my notes Rice's theorem in the following form.

Let $k$ be an arbitrary natural number and $ g: \mathbb{N} \rightarrow \mathbb{N}  $. If g satisfies the following conditions, the $g$ is not recursive.

1.Totality: For any $p\in\mathbb{N}$, the value $g(p)$ is defined and $g(p)\in {0,1}$

2.No constant: $g$ is not constant. There exists two natural numbers
 $p_0,p_1\in\mathbb{N}$ such that $g(p_0)=0 $ and $ g(p_1)=1$

3."Reflects equivalence of codes" If p,q are codes for the same recursive function $\mathbb{N}^k \rightarrow \mathbb{N}$ then $g(p)=g(q)$

I know the answer must be No there is not by property 3 but how can I formally write it.


texts:
I am stuck and having a hard time with this question. I want to construct a CFG for the language $$L = \{{a^lb^mc^n | l,m\in N, n=|l-m|\}}$$
I know that the language consists of strings where:
1. number of a's = number of b's, so c=0
2. number of a's more than number of b's, c=l-m
3. number of a's less than number of b's, c=-(l-m)

I started with
$$S->ab$$
$$S->aSb$$
This generates all of case one, where number of a's = number of b's and c=0. I know that I could increment a's and c's by having aSc but I cant put that in the second line because it could generate a(aSc)b which is not in the language.


texts: What exactly is the difference between supervised and unsupervised learning?

texts:
I am trying to understand clustering methods.

What I I think I understood:

In supervised learning, the categories/labels data is assigned to are known before computation. So, the labels, classes or categories are being used in order to "learn" the parameters that are really significant for those clusters.
In unsupervised learning, datasets are assigned to segments, without the clusters being known.

Does that mean that, if I don't even know which parameters are crucial for a segmentation, I should prefer supervised learning?


texts: Representing partialled/curried functions in postfix notation?

texts:
I'm working on a small query language in JSON. A query consists of a JSON array of JSON elements, such as strings, numbers, booleans, etc. Strings starting with a '$' or '@' represent postfix unary or binary operators, respectively.

I want to include some functional aspects to my query language (e.g. a map operator that takes a function and an array, and produces a new array). However, I'm having trouble representing these "functions-as-arguments" in postfix notation! As an example, let's say I want to add a fixed number to each element of an array. I would instinctively want to write something like this:

[[0, 2, 4, 6, 8], 1, "@add", "@map"]

However, this would be interpreted as "perform an add operation on 1 and [0, 2, 4, 6, 8], and then call map". This would produce an error in my query! Instead, I want to interpret the query as "perform a map operation using add(1) on [0, 2, 4, 6, 8]". Is it possible to achieve this, given the use of postfix notation?


texts: Time complexities of state-of-the-art SAT solvers with respect to length of the formula

texts:
I am learning about DPLL and CDCL SAT solvers, and I know that they have time complexity exponential to the number of variables.

If I am not mistaken, one of the reasons why most believe P does not equal to NP is that there exists no polynomial-time algorithm for SAT despite tremendous effort from mathematicians and computer scientists. However, the P vs NP problem only cares about the time complexity with respect to the length of the formula, not the number of variables.

If these state-of-the-art SAT solvers were run on 3CNF formulas, then a time complexity exponential to the number of variables implies a time complexity exponential to the length of the 3CNF.

However, if they were run on arbitrary CNFs, whose length can be exponential to the number of variables, then a time complexity exponential to the number of variables would not necessarily imply a time complexity exponential to the length of the CNF.

Thus, a related question is, are these SAT solvers run on 3CNF or CNF while measuring time complexity?


texts: Clock skew vs clock offset in the context of clock synchronization network protocols

texts:
In the context of clock synchronization among nodes of a network, what is clock offset and what is clock skew?

Are these terms synonymous or is there a difference between them?


texts: Examples of languages not decidable by a TM using certain upper bounds on space/time

texts:
I'm learning about time and space complexity involving Turing Machines at the moment, and would really like some concrete examples of specific languages that belong (or don't belong) to certain classes of time / space hierarchies. For example, what are some examples of a decidable language that can't be decided by a TM using space O(log n) and time less than n, on inputs of length n?

Might the Travelling Salesman Problem be an example to the above question, since I think the brute-force algorithm for TSP would take space O(n) (store the current shortest path, and compare it with each new path that's being explored)?


texts: Example of *small* non monotone circuit such that any equivalent monotone circuit has greater size?

texts:
A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:

fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT nodes
fan-in=0 for the IN nodes
fan-out=0 to exactly one node (the OUT node)
Unbounded fan-out to the rest of the nodes (but the OUT node)

A monotone circuit is a Boolean circuit with 0 vertices labeled as "NOT".

The size of a circuit is the number of "gates" (vertices with labels "AND", "OR" or "NOT") it contains.

In Yuval's answer here I've learned of two examples (Tardos function and bipartite perfect matching) where it has been proven that monotone circuits admit greater size than general Boolean circuits, but I cannot get the intuition, as I don't have any concrete small size example in hand.

Hence, my question is: could you please supply me with an example of a small (say, up to 10-20 gates) non monotone circuit such that any equivalent monotone circuit has greater size?

Edit

I guess that the smallest-size circuit computes the 3-Clique decision problem, as this is the smallest size where we can exploit fast matrix multiplication for the k-Clique problem (where non-monotone circuits may have smaller size than their equivalent monotone circuits, as I mentioned before).

Since the key part of exploiting fast matrix multiplication is (roughly): does $X^2$ contain any non-zero?
Hence, I guess that a circuit that computes this decision problem is the minimal-size one. So, it is equivalent to $$\bigvee_{i,j,k\leq n}{(x_{ij}\wedge x_{jk})}\equiv\bigvee_{i,j\leq n}\left(x_{ij}\wedge{\left(\bigvee_{k\leq n} x_{jk}\right)} \right)$$.

If it is true, we just need to find some small $n$ (preferably, the smallest $n$), and some non-monotone function of size $\lneq n^2\cdot (n+1)=n^3+n^2$, which is the size of RHS, which is probably the minimal-size monotone circuit that computes this function.

Now, smallest size for Strassen is $n=4$, so it admits $n^2=4^2=16$ variables, but I guess that simpler manipulation than Strassen could do the desired on smaller $n$, and with simpler manner.

To sum up, I almost get it, but still do not have an explicit simple and small example in hand.


texts: How important is initial state for local search optimisation?

texts:
I have been enjoying Pascal van Hentenryck's Discrete Optimisation course and we're in Week 4 on the wonders of Local Search algorithms for combinatorial optimisation.
I'm wondering how important the initial configuration is to the quality of solution achievable in a fixed time or, somewhat equivalently, how quickly a solution of a given quality can be reached.
So if I have a good heuristic or intuition for how to arrange things in the first place, is it helpful to devote some processing time to setting that up or is it all dominated by the effect of the local search process?
For example, in the Cartesian Travelling Salesman Problem (where we're working in a 2D plane and the cost of a journy is simply the straight-line distance) I might "feel" that a good route could roughly follow a clockwise sweep from the centre of the space.  So I could use this to set my initial tour (i.e. order the nodes by their angle from the mean of all points).  This intuition might be rubbish for certain instances and great for others, I was hoping to see a study where (let's say random TSP) instances had been solved by following a heuristic first state as opposed to a completely random (but legal) first state.


texts: Is Equality problem decidable in DCFL and CFL?

texts:
Equality problem is checking if 2 DCFL's or CFL's are producing same language.

I read that it is decidable for DCFL and undecidable for CFL.

If we consider a DCFL like a^n b^2n / n>=1, here we can draw a PDA for this in two ways.
So how can we check if 2 DCFL's produce the same language by just looking at the PDA as they are not unique?


texts:
I was looking at this: http://www.cs.odu.edu/~toida/nerzic/390teched/tm/othertms.html

At the very beginning, they show a 2d tape and (I assume) it's 1d equivalent. However, I cannot figure out they got from the 2d case to the 1d case. I was hoping someone could elaborate.


texts:
I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$.
First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get
$L\left( aa^{\ast }\left( a+b\right) \right)$ $= L\left( a\right) L\left( a^{\ast }\right) L\left( a+b\right) $
Then I constructed an NFA for it , which is given below :

But I am not able to simplify the above NFA to a DFA as the state $q_1$ has two $\lambda$ transitions and I am not understanding how to deal with them .


texts:
I am trying to find a good model the following problem:

Given a collection of work packets x, y, z, ..., and a collection of worker nodes A, B, C, ..., assign packets to nodes.

Each work packet has an affinity per worker-node, shown as a cost-value for how long a packet takes to process on a specific node. For example, packet x runs twice as fast on node B, and packet z cannot run on node C at all. We get an affinity table like this:

\begin{array}{c|c|c|c|}
 & A & B & C \\ \hline
x& 1& 0.5& 1\\ \hline
y& 1& 1& 1\\ \hline
z& 1& 1& \infty\\ \hline
\end{array}

Now I want to distribute all packets across all available nodes with the best total affinity possible. If each node would take any number of work packets, this is trivial, as each packet would just get assigned to the node it has the best affinity on. However, nodes process their work in parallel, and therefore I primarily want to minimize the maximum cost across all nodes.

For the example above, the solution looks like this:

A: z  cost: 1
B: x  cost: 0.5
C: y  cost: 1
      ----------
      max:  1    <-- needs to be minimized, primarily
      sum:  2.5  <-- should also be minimized

I could just brute-force a solution by permutating all possible combinations, but that isn't feasible for a larger number of nodes and/or packets.

Is there a model for this, which I can research into to find a good algorithm to solve this problem?


texts: Which combinatorial problem is similar to this problem?

texts:
I have $n$ clients and for each client I have different options to choose from, for example, $C= \{C_1,C_2 \}$. For each combination of $n$ options, there is a cost. I want to choose the best combination that minimizes the cost without calculating the cost for each option one by one and then choose the best one and I do not have any constraints. Which combinatorial problem is similar to this one?

For example, If I have $n=3$ and $C =\{1,2\}$, I have set of triples $(x_1,x_2,x_3)$ as $\mathcal{M}= \{(1,2,1),(1,2,2),(1,1,1),(1,1,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)\}$ and equation $cost=x_1+x_2+2x_3$ I want to find the triple that minimizes the cost without calculating one by one. The cost function can be any function not nessesary linear.


texts: Find the kth smallest element in an unsorted array of non-negative integers

texts:
I need to find the kth smallest element in an unsorted array of non-negative integer.

kth smallest element is the minimum possible n such that there are at least kth elements <= n.

The rub here is that the array is read only so it can't be modified. Also i have to do it in constant space.

Can anybody help come up with the most optimal solution ?


texts: Scott/Lawson topology for function space domain

texts:
Given two domains, $D_1$, $D_2$,
already equipped with Scott (or Lawson) topology,
the product domain $D=D_1\times D_2$
has the Tychonoff product topology, e.g.,
Mathematical Theory of Domains, page 124.

I can't seem to find a similar discussion of the function space topology
for $D=[D_1\rightarrow D_2]$,
though I assume it's well-known.
Can someone explain it and/or give a reference which discusses it?

More generally,
if you have a general domain equation
$D=F(D_1,\ldots,D_n)$,
where $F(\cdot)$ is built up from $D_1,\ldots,D_n$
by usual operations like product and function space,
what can you say about $D$'s Scott/Lawson topology?
In particular, how can you construct the open sets of $D$
from the open sets of $D_1,\ldots,D_n$?


texts: Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s

texts:
Design a Pushdown Automata, accepting either by final state or by
  empty stack to accept the set of all strings of 0’s and 1’s such that
  no prefix has more 1’s than 0’s

This is a homework question, but not graded.

I'm not looking for the answer, right now I'm just trying to understand the question. I don't understand what sort of words would be accepted and what would be rejected. For example, I can't understand whether the following word would be accepted:

011011 ; where 01 is prefix and 1011 is suffix
011011 ; where 011
is prefix and 011 is suffix
011011 ; where 0110 is prefix and 11 is
suffix

My question is: Given a word, how do I know which part of it is the prefix?

Please try to give an explanation without the actual PDA answer, I'd like to try it myself first.


texts: A question about halt (or stop) of Turing machine

texts:
I try to understand something:
At Turing machine we have two stats: $q_{accept}$ and $q_{reject}$.

Now, if machine $M$ runs on word $w$ (I hope I write it right...) and the final configuration is: $C(w,q_t,\varepsilon )$,
 and $q_t =Q-\{q_{accept},q_{reject}\}$.

Of course $M$ don't accept $w$ and don't reject $w$, but my question is:
We can say that $M$ Stops on $w$?

I try to look for an answer but I didn't found...

Thank you!


texts:
Is there any algorithm which can transform any graph to tree, with providing mapping from one to another?
Suppose we have directed graph:

E->A
A->C
C->C
C->B
B->A
B->D

I want to convert it to tree in such way, that all biggest cycles is converted to node, and all dependencies out of this cycle is binded to this node. So, in other words, all cycles represented as nodes.

For example, the biggest cycle here:

A B C

Biggest cycle is a cycle which do not contained in other cycles. So, in example [C] is one-node-cycle but it contained in bigger cycle [A,B,C], so it is not biggest. On the other hand [A,B,C] is not contained in any other cycle, so it is biggest. Graph can contain multiple biggest cycles.

Output will be:

E->F
F->D

where F is alias for A,B,C

Is there some algorithm for this?

Other interesting example with 2 biggest cycles:

A->B
B->A

A->C

C->D
D->C

Will be converted to:

E->F
where E is alias for A,B
where F is alias for C,D


texts: Group values up to a threshold and minimize groups

texts:
Given a threshold $t$ and a list of numbers $N$. $\forall n \in N: n \leq t$
Now group the numbers so that the sum of the numbers $s$ is lower or equal $t$. Minimize the amount of groups.

Example: $N={20,19,18,17,14,12,9,5,4}$ and $t = 40$

Possible Grouping: ${(20,19),(18,17,4),(14,12,9,5)}$ (Greedy)

Is greedy a strategy/algorithm, that will lead to the optimal solution? If not, are there other algorithms to solve this problem?


texts:
Im having some problems with a qeuestion regarding converting a context free grammar to chomsky normal form.

I have
        S -> abC | babS | de
        C -> aCa |b

I know what to do with the case of aCa and de and b but im not sure how to handle the abC case or the babS case. I believe that chomsky normal form is supposed to have outputs of only 2 characters. so with something like aCa you make and output aa and have A->a and create another nonterminal? X -> SA but I dont know how im supposed to handle the abC case or the babS case.


texts: Big-O complexity of finding exception handler for zero-cost exceptions

texts:
I am wondering what the time complexity of finding the most appropriate exception handler for dispatching zero-cost exceptions is.

For zero-cost (this refers to execution under the assumption that no exceptoins occur) exception dispatching, the compiler stores a big table of all possible exceptions. An entry consists of Type, Handler, start+end of the try-block.

Then one can find the most appropriate handler by

taking those with a try-block enclosing the address where the exception occured
then of those, choosing the most specific type
if one is found: done, else: move up the callstack

Naively I would say: O(callstacksize * sizeoftable).

But we have to be able to do better. I looks to me the callstacksize factor wont go away, but what about the sizeoftable factor?

There should be more performing way to search through the handlers. What is the best we can do O-notation-wise?


texts: Why "Choice Points" introduce non-determinism in a program?

texts:
I'm studying the didactic programming language Oz, following the book "Concepts, Techniques, and Models of Computer Programming".

In the book, the nondeterminism is introduced through the concept of choice, as it's explained here.
However, in the Oz language if the programmer calls a choice between alternatives A, B, C it happens that the alternative A is always travelled first, and consequently (in case of backtracking) first B and then C. So the choice happens to be deterministically, since I know a priori how the choices' tree will be constructed.
So what's the link between choice and nondeterminism?

I also have another question. In the book, the authors state that if I want to introduce the choice concept in my computation model I am obliged to use a stateful (non-declarative) computation model. Why?


texts: Pseudocode for A-star algorithm removes nodes from the currentList which are not in the list

texts:
I am trying to implement A star algorithm with Python. I am trying with this pseudocode found on Medium:
// A* (star) Pathfinding
// Initialize both open and closed list
let the openList equal empty list of nodes
let the closedList equal empty list of nodes
// Add the start node
put the startNode on the openList (leave it's f at zero)
// Loop until you find the end
while the openList is not empty
    // Get the current node
    let the currentNode equal the node with the least f value
    remove the currentNode from the openList
    add the currentNode to the closedList
    // Found the goal
    if currentNode is the goal
        Congratz! You've found the end! Backtrack to get path
    // Generate children
    let the children of the currentNode equal the adjacent nodes

    for each child in the children
        // Child is on the closedList
        if child is in the closedList
            continue to beginning of for loop
        // Create the f, g, and h values
        child.g = currentNode.g + distance between child and current
        child.h = distance from child to end
        child.f = child.g + child.h
        // Child is already in openList
        if child.position is in the openList's nodes positions
            if the child.g is higher than the openList node's g
                continue to beginning of for loop
        // Add the child to the openList
        add the child to the openList

I don't understand the following part:
put the startNode on the openList (leave it's f at zero)
// Loop until you find the end
while the openList is not empty
    // Get the current node
    let the currentNode equal the node with the least f value
    remove the currentNode from the openList

According to the pseudocode we put the startNode in the openList, then we let the currentNode being equal to another node (I guess it's from the child of the currentNode), and then we remove the currentNode from the openList. Yet the openList only have startNode isn't it?
So is this pseudo code wrong for A star algorithm?
I'm happy to hear any other sources.


texts: Delay Constrained Shortest Path in $O(D \cdot |E|)$ time

texts:
I have the following homework exercise:

  We are given a network $N=(G,w,d)$, $G=(V,E)$ together with a designated
  source node s∈V and target node $t \in V$, where $w\colon E \to Z^+$ and $d\colon E \to Z^+$. The
  values $w_{i,j}$ correspond to arc weights, $d_{i,j}$ correspond to delays,
  i.e., using the arc $(i,j)$ requires $d_{i,j}$ time. We are further given a
  positive number $D \in N$, the delay constraint. Develop an efficient, i.e.,
  $O(D \cdot |E|)$, algorithm to find a shortest path $P$ from some $s$ to $t$, which
  does not exceed the global delay constraint $D$, i.e., $\sum_{(i,j) \in P} d_{i,j}≤D$ (Hint: use a similar approach as the one used in the Bellman
  Ford algorithm).

I was able to find an algorithm that runs in $O(D \cdot |E| \cdot |V|)$ time. However I'm struggling with finding an algorithm that runs in $O(D \cdot |E|)$ time and I'm starting to think, that such algorithm is not even possible to create (although I don't have a formal proof for this).

Could you give me a clue how would such an algorithm look like?


texts:
I have been studying search problems in AI, and I am having some troubles understanding some points in these concepts:

State Space: "represents the environment of the problem, the set of all states reachable from the initial state."
Search Graph: "the nodes are states and the arcs between nodes are actions"
Search Trees: a conversion of the Search Graph to a tree.
Branching Factor: the maximum number of states we can get by moving from old state to a new state using the successor function.

Specifically, how can I estimate the size of my space? and the branching factor? is there any counting rules that usually help?

I have mainly studied from the book "Artificial Intelligence A Modern Approach" and I couldn't find answers to these questions.  Online resources mainly focus on either the 8-puzzle or n-queens problem.

If you could suggest any examples or resources that would be great.


texts: Finding optimal set for a sum of a product function over a 2D lattice

texts:
Given a 2D lattice with coordinates $1 \leq x \leq c$ and $1 \leq y \leq d$, we define $f(x, y) = xy$.

We wish to find a boolean function $I(x,y)$ that determines in $O(1)$ time whether or not $(x,y)$ belongs to the set of points $S$ of size $k$ such that the sum $Z(S) = \sum_{(x,y) \in S} f(x,y)$ is smaller or equal to any other set of size $k$. One may use $O(c+d+k)$ time and space to construct $I$.

Is this possible? Is this a known problem (my search turned up nothing)? Can https://en.wikipedia.org/wiki/Divisor_summatory_function and its approximation help us?

Motivation: I work in NLP and am trying to find an optimal way of storing part of a word-word cooccurrence matrix in memory and part on disk. This matrix is very sparse. I'm making the simplifying assumption that the probability of two works co-occurring is proportional to their unigram frequencies. By ranking words in terms of frequency, we get the $c$ and $d$ terms. So the smaller the ranks $c$ and $d$, the more likely they are to co-occur, so this value should be stored in memory. Since there will be billions of lookups, $I$ needs to be fast.

Thanks!


texts: How to show two models of computation are equivalent?

texts: I'm seeking explanation on how one could prove that two models of computation are equivalent. I have been reading books on the subject except that equivalence proofs are omitted. I have a basic idea about what it means for two models of computation to be equivalent (the automata view: if they accept the same languages). Are there other ways of thinking about equivalence? If you could help me understand how to prove that the Turing-machine model is equivalent to lambda calculus, that would be sufficient.


texts: Confusion about $EXP \subseteq P^{EXPCOM}$ claim from Arora and Barak

texts:
In Computational Complexity -- A Modern Approach, by Arora and Barak, they have the following claim (Example 3.6).

Let EXPCOM be the following language
$$ \{ \langle M, x, 1^n\rangle \mid M \text{ outputs 1 on $x$ within $2^n$ steps} \}  $$
Then $\mathbf{P}^{\mathrm{EXPCOM}} = \dots = \mathbf{EXP}$. [...]
Clearly, an oracle to EXPCOM allows one to perform an exponential-time computation at the cost of one call, and so $\mathbf{EXP} \subseteq \mathbf{P}^{\mathrm{EXPCOM}}$. [...]

I believe their reasoning is as follows:

Suppose we have a language $L \in \mathbf{EXP}$.

Thus there is a TM $M$ that decides it in time $2^{n^c}$.

We want to create a poly-time oracle-TM $T^{\mathrm{EXPCOM}}$ that decides $L$.

$T$ works as follows on input a string $x \in \{ 0, 1 \}^{*}$. It queries its EXPCOM oracle on input $\langle M, x, 1^{n^c} \rangle $, and outputs the same answer as the oracle.

Clearly $T$ runs in polynomial time, and it decides the same language as $M$. QED.

Here is my confusion. For $T$ to call its EXPCOM oracle, it needs to know which $M$ that decides $L$ (in exponential time). However, 2. only promises the existence of a machine $M$; it doesn't actually tell you how to find it!
(this problem also applies to the running time $2^{n^c}$ of $M$).
So clearly I'm misunderstanding something, but what? Is it my understanding of the language EXPCOM? Is it my description of $T$? Or have I misunderstood oracle-TMs altogether? (Or maybe all three?)


texts: Is relation following given characteristic already in 2NF, 3NF and BCNF?

texts:
The definitions of 2NF, 3NF and BCNF goes like this:

  2 Normal Form (NF) definition
   A relation is in second normal form if and only if it is in first normal form and all the non-key attributes are fully functionally dependent on the candidate key.

  3 NF - definition
    A relation schema $R$ is in third normal form (3NF) if, whenever a nontrivial functional dependency $α→β$ holds in $R$, either

  $α$ is a superkey of $R$, or
  $β$ is a prime attribute of $R$.

  BCNF (Boyce–Codd normal form) - definition
  A relation schema $R$ is in BCNF, if whenever a nontrivial functional dependency $α→β$ holds in $R$, $α$ is a superkey in $R$.

Based upon these decision, I want to know if the relation having below characteristic is already in some normal form.

All candidate keys are of single attributes: this one is definitely in 2NF as there cannot be any partial dependency, but full functional dependency on CK. I am more confused about 3NF and BCNF. I feel its not in 3NF and BCNF since there can exist $\alpha \rightarrow \beta$, such that both $\alpha$ and $\beta$ are non key, violating 3NF and BCNF definitions.

Am I right with this?


texts: In what ways are deep neural networks not black boxes?

texts:
When reading up on deep learning from various sources, one is often presented with the notion that deep learning is essentially a black box: A set of recipes, heuristics and empirical best practices that have been found to often work, but where the mechanism by which good results are achieved is usually not well understood. See for example http://www.nature.com/news/can-we-open-the-black-box-of-ai-1.20731.

I am looking specifically for resources (e.g. specific papers or research groups working in the field) of how this is not the case, i.e. work aimed at understanding why deep learning techniques work, both in the backward and forward direction.

I know about work on optimizing the input to a network in such a way as to activate some unit maximally (see http://yosinski.com/deepvis) and this seems interesting, but that's also a rather descriptive than mechanistic approach.

I would greatly appreciate any pointers!


texts: How to analyze the Steiner tree problem?

texts:
I have a problem where I am supposed to analyze the Steiner tree problem by doing the following 3 steps.

1) Look up what the Steiner tree problem is.

2) Find a polynomial time reduction to it from one of these 8 known NP-complete problems:

3-col
subset-sum
clique
hampath
Uhampath
sat
3-sat
vertex-cover.

3) Prove that it is NP-complete.

My first problem is that I don't understand what the Steiner tree problem is. I can't find the problem anywhere. Wikipedia has  a page on it, but doesn't really describe it in simple terms.

Can anyone help me out on this, and also give me hints for number 1, 2 and 3?


texts:
Assume we have a sorted list of n numbers, I want to map those numbers to m buckets or clusters. For each bucket the average of all numbers in that bucket will be computed. The task is to find a mapping, so that the difference between those cluster averages and the original numbers is minimal.

Example:
List: [1, 2, 3, 4], desired number of buckets: 2
Optimal Solution:
Bucket 0: [1, 2], Average: 1.5, Difference: abs(2 - 1.5) + abs(1 - 1.5) = 1
Bucket 1: [3, 4], Average: 3.5, Difference: abs(4 - 3.5) + abs(3 - 3.5) = 1
Overall Difference: 2

I know how to create a mapping by brute force, but I would need a more efficient algorithm.


texts: Proving a Language is Irregular using Myhill-Nerode

texts:
I'm trying to prove that the language: \begin{equation*}
L = \{ w \in \{ 0, 1 \}^* : w  \text{ contains more 0's than 1's} \}
\end{equation*} is irregular using the Myhill-Nerode theorem. I've been through all the basic examples in the book, and thought I understood them, but I'm having trouble with this one.

So far, I've been thinking about letting $ x_i = 1^i 0^i $ and $x_j = 1^{j+1} 0^{j-1}$, then if I let $ w_{ij} = 0$, only $x_iw_{ij} \in L$. That seems to be sufficient, but it seems weak compared to some of the other examples.

Am I on the right track here? I would really appreciate any hints/suggestions.


texts: What is the difference between the research area of "ad hoc networks" and "device-to-device communication"?

texts:
I wonder what "device-to-device communication" (from a research perspective) covers what "ad hoc networks" don't.

To the context of this question: I am reviewing papers which deal with "device-to-device communication" (D2D). And all aspects of the presented approaches are known to me from the research field of "ad hoc networks" (which started emerging 20 years ago). Obviously, I was searching for the background information and Wikipedia and Google only confirmed the similarities between both fields. Hence, my question is what are the differences between both (research fields)? And I would mostly be interested from the point of view of research questions, since I am aware that technologies changed in the last 20 years.

http://www.comsoc.org/wirelessmag/cfp/device-device-d2d-communications-social-awareness
https://en.wikipedia.org/wiki/Wireless_ad_hoc_network