texts:
I'm trying to come up with an algorithm to optimize the shape of a polygon (or multiple polygons) to maximize the value contained within that shape.

I have data with 3 columns:

X: the location of the block on the x axis
Y: the location of the block on the y axis
Value: Value of the block (can have positive or negative values)

This data is from a regular grid so the spacing between each x and y value is consistent.

I want to create a bounding polygon that maximizes the contained value with the added condition,

There needs to be a minimum radius maintained at all vertices of the polygon (it can't "turn too sharply").

This means that we will either lose some positive value blocks or gain some negative value blocks.

The current algorithm I'm using does the following:

Find the maximum block value as a starting point (or user defined)
Find all blocks within the minimum radius and determine if it is a viable point by checking the overall value is positive
Remove all blocks in the minimum search radius from further value calculations and flag them as part of the final shape
Move onto the next point determined by a spiralling around the original point.

This appears to be picking up some cells that aren't needed.  I suspect there are better algorithms out there but I don't have any idea what to look up to find help.

Background: I'm an engineer with minimal formal knowledge in programming or computer science.  I like using code to help increase efficiencies in the office.

Below is a picture that hopefully helps illustrate the situation.  Positive cells are shown in red (negative cells are not shown).  The black outline shows the shape my current algorithm is returning.  I believe the left side should be brought in more.

Effectively my algorithm is covering the areas with circles since each value check is done on a circular radius and all the blocks are flagged at the same time.  Spiraling is done on the grid cells so it always moves by 1 deltaX or 1 deltaY.  I saw someone mention Minkowski dimension or ball packing but I'm not familiar with those.  My problem seems different: ball packing looks like you want complete coverage of the desired surface whereas I want to select or omit cells based on the total value inside the circle.


texts: What happens to multi-qubit quantum state after one of qubits is measured?

texts:
If we have a quantum state consisting of (let's say) 3 entangled qubits and we read the value of one of them, what happens to the probabilities of the remaining possible states?

For example, if we have three entangled qubits and have an amplitude for every state from $|000\rangle$ to $|111\rangle$ and we measure the second (middle) qubit to be 1, the remaining states are $|010\rangle, |011\rangle, |110\rangle, |111\rangle$. If we know the amplitudes for all possible 9 states before the measurment, how do we get the amplitudes of the remaining states after measurment?


texts: How to know for sure that a router is congested?

texts:
Suppose a router X is dropping packets. Another router A will investigate whether X is dropping packets due to congestion. What are the procedures that A should follow?

A already knows X's buffer capacity. Please explain the procedures and assume an arbitrary threshold T (if needed).


texts: What are some problems which are easily solved by human brain but which would take more time computers?

texts: Are there any problems which can be solved by human brain in a very less time but a computer may take a lot of time or a computer could never solve it ?


texts: How to estimate maximum n given complexity and amount of time?

texts:
Say you've implemented a program that completes it's work with O(2n) time complexity, and you measure the actual running time of the program as:

n1: 0.006s
n100,000: 16.057s

Since time will grow exponentially as n increases, what is the typical way to estimate the maximum n given a time t? For example, if time t is 1 minute or 1 hour, how do you "correctly" estimate n?


texts: I have a file containing a subset of possible strings from a context free language. I am looking for a mechanism to induce the grammar from this information. Is that possible?


texts: Questions on shortest path and minimum spanning tree

texts:
T/F Questions

Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem.
Solution - False

I think this should be True, as Dijkstra's Algorithm sums the paths from source to each vertex. If every edge weight is increased by a constant, then nothing should be changed if all edges are positive. If some edges are negatives, then I don't know if Dijkstra's Algorithm still applies here.

Adding a constant to every edge weight does not change the solution to the MST problem. (I don't have the solution for this)

I think this is True for the same reason above.

Can someone confirm on this?


texts: Is there any known method to simulate a UTM with an instance family of the three body problem in physics?

texts: I think it would be challenging since the three body problem is about continuous movement and Turing machines execute in discrete steps.


texts: About logarithmic cost model and bit complexity model?

texts:
So I heard that there are such models for finding time complexity of an algorithm as logarithmic cost model and bit complexity model. But from the information I have found in the internet, I cannot understand what operations  are taken to be constant time, but I understood that arithmetic operations are not taken to be constant time. I suppose these could be operations of reading and rewriting of the bits, but its just my guess. So what operations are taken to be constant time in logarithmic cost model and bit complexity model ? It may be that I am losing some details by thinking that these models are different from others by/only by operations taken to be constant time, if thats the case I will be grateful if you explain me the details. Also it may  be that my question is not that correct, then I will be grateful, if you help me make it better.
Thanks in advance.


texts: IEEE 754 addition wrong result floating point numbers

texts:
I want to add two IEEE 754 numbers.
I followed the steps to add two 754 numbers. However the result it not correct.
Number 1:
S:0
E:01111111
M:11111111111111111111111
Number 2:
S:0
E:01111111
M:00000000000000000000000
Here is my calculation:

The site http://weitz.de/ieee/ gives this result:
S: 0
E: 10000000
M: 10000000000000000000000
in my calculation the mantissa is 01111...
Why?


texts: If a decision problem $A \in \text{NP}$ and there exists reduction so that $A \leq_p B$, for decision problem B, what can be deduced about B?

texts:
I think that it implies that B can be solved by a non-deterministic polynomial time or worse Turing machine, but I realise that there is possibly some greater result that I'm missing.

Thanks in advance.


texts: Min-max the component-wise sum of two sets

texts:
When I was trying to prove a problem at hand to be NP-complete, I coined the following problem:

  Given two integer sets $A = \{ a_1, \cdots, a_n \}$ and $B = \{ b_1, \cdots, b_n \}$.
  We know that there are $n!$ bijections between $A$ and $B$.
  For a bijection $f\colon A \to B$, define
  $$\max f = \max_{a \in A} \{ a + f(a) \}.$$
  This problem is to find a bijection which minimizes $\max f$.

I think it is polynomial solvable (which is thus of no use in reduction).
The algorithm is simple: Sort $A$ non-decreasingly and $B$ non-increasingly and map $A$ to $B$ component-wisely.

However, I could not find a proof.

Problem: How to prove (or disprove) this algorithm?


texts: How to define the dimension function for searching in a 3D-array?

texts:
Problem:

Propose a plan (pre- and post-condition, invariant, dimension function) for searching a value in a 3D-array.

Solution:

This is the first solution I've foreseen:

$[\text{Ctx}\ C: m\geqslant 0\wedge\ n\geqslant0\ \wedge\ p\geqslant0\ \wedge\ b[0..n-1,0..m-1,0..p-1]$

$\{\text{Pre}\ Q: T\}$

$\{\text{Inv}\ P: 0\leqslant i\leqslant n\ \wedge 0\leqslant j\leqslant n\ \wedge\ 0\leqslant k < p\ \wedge\ $

$\}$

$\{\text{Dimension function}\ T: (m-1)*(n-1)-j\}$

$do\ ...\ od;$

$\{\text{Post}\ R: 0\leqslant i\leqslant n\ \wedge 0\leqslant j\leqslant n\ \wedge\ 0\leqslant k < p \wedge\ [(i=m\ \wedge\ x\in b)\ cor\ (i<m \wedge x=b[i,j,k]\ )]\}$

The matrix in this plan is part of the invariant: what it means is the actual searched area (green color).

Now, what I want to know is if the dimension function is sufficient to represent the remaining area to be searched in the $do$ loop.


texts: Systems for inter-human touch classification?

texts:
I'm trying to find any publications involving a system that can classify if there is physical contact in a video. Ideally, if the physical contact is brief, it would also be beneficial to classify. However, despite this clearly defined problem, I've been unable to find any mention of this in the literature. I am able to find many references for human action recognition, but no such fine-grained distinction of physical contact.

Do any systems exist that move towards these goals?


texts:
$L_0=\{\langle M,w,0\rangle\mid M \text{ halts on } w\}$

$L_1=\{⟨M,w,1⟩\mid M \text{ does not halts on } w\}$

Here $\langle M,w,i \rangle$ is a triplet, whose first component $M$ is an encoding of a Turing Machine, second component $w$ is a string, and third component $i$ is a bit.

Let $L=L_0 \cup L_1$. Is $L$ non R.E ?

After seeing the question I was able to figure out that there are some strings that do not belong to $L_0$ as well as $L_1$.

Like, lets take the case for $L_0$ and a string $001\dots10−01−1$, ("$-$" shown for notation purpose only) where the  first component describes a TM $M$ followed by input "$w=01$" and last bit "$1$". Now suppose M halts on "$01$". Still the given input is not in $L_0$ as the last bit is "$1$" and not "$0$" as required by $L_0$. So, this input must be in $L_1$. But since $M$ halts on $w$, this input is not in $L_1$ either.  So there are infinite strings like these. I am not able to prove that these infinite  set of strings are not r.e.

Is there any method to solve these kind of problems? I am not able to master these kind of problems.

Please someone help.


texts:
We know that the longest common substring of two strings can be found in $\mathcal O(N^2)$ time complexity.
Can a solution be found in only linear time?


texts: Would an optimization version of the 3-partition problem also be strongly np-complete / np-hard?

texts:
Anyone know if an optimization variant of the 3-partition problem (as explained there) would also be strongly np-complete?

This would be where the goal is to group a multiset whose size is evenly divisible by 3 into triplets that sum to as close to a target as possible and to produce this grouping. This would not be a decision problem but an actual optimization problem.


texts: Is there a name for this graph transformation (remove a 'thru' node)

texts:
I have a directed graph, eg:

$$A\to B\to C$$

$A$ and $C$ may have multiple in- and out-edges, but B has exactly one in- and one out-edge.

I want to remove node $B$ and replace the edges $(A,B)$ and $(B,C)$ with a single edge $(A,C)$.

Is there a name for this operation?  In particular a name or algorithm for finding all nodes such as $B$ and removing them from the graph.


texts: How do we make sure in Paxos that we don't propose a different value if a majority has formed?

texts:
Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and I was confused about one specific part. How does or why does property $P2^b$ satisfy property $P2^c$?

These are the properties:

$P2^b = $ If a proposal with value $v$ is chosen, then every higher-numbered (i.e. approx. later in time)  proposal issue by any proposer has value $v$.

$P2^c$ = For any $v$ and $n$, if a proposal with value $v$ and number $n$ is issued, then there is a set $S$ (some majority) of acceptors such that either:

(a)no acceptor in $S$ has accepted any proposal numbered less than $n$, or

(b)$v$ is the value of the highest-numbered proposal among all proposals numbered less than $n$ accepted by the acceptors in $S$ (some majority).

The paper uses $S$ to denote some majority and $C$ to denote some majority that has actually chosen a value.

The thing that I am confused about is, for me $P2^b$ is saying, ok once a value has been chosen, say at sequence number $n$ (i.e. roughly time $n$), then after that time, we want to make sure that any proposer is only able to propose the value of the majority (chosen value). If we have that, then, we do not risk the already formed majority from reverting weirdly. i.e. once we have formed a majority, we want it to stick and stay like that. However, it was not 100% clear to me why property $P2^c$ satisfied that requirement. I kind of see why (a) is a nice property to have, since, having (a) means that its safe to issue a new proposal $(n, v)$ since we contacted some majority $S$ and none of them had accepted anything in a time earlier than now $n$. So, if a majority had formed we would have seen at least one value and we did not see anything accepted, its safe to propose something since a majority has not formed.

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research


texts:
I have a set of expressions $E_1 .. E_n$ over boolean variables and I'm looking for an assignment to the variables so that all expressions are satisfied. Normally this would be NP-complete, but I found two particular properties over the set and I'm looking to combine and exploit them.

The idea I have is based on gaussian matrix elimination. In matrix elimination, you take a nonzero column and a row and use them to sweep the column from all other rows. Even for an integer matrix solution, you can find a solution in such a way if the number of rows is about the same as the number of columns and the matrix has exactly 1 solution. In my particular application, I have about as many variables as expressions and in some cases there is only 1 solution and the expressions do not imply each other. (property 1).

I take $E_1$ and one of it's variables. I combine $E_1$ with $E_2$ only if $E_2$ contains that variable. If so, I eliminate the variable from $E_2$ and I will (deterministically but somewhat arbitrarily) eliminate some more variables from $E_2$ that are both in $E_1$ and $E_2$. I keep the expressions as a truth table. Suppose for example that I want to eliminate a, b and c, $E_2$ would become

E_2 =
    (substitute/a,b,c/0,0,0 (E_1 && E_2)) ||
    (substitute/a,b,c/0,0,1 (E_1 && E_2)) ||
    (substitute/a,b,c/0,1,0 (E_1 && E_2)) ||
    ...
    (substitute/a,b,c/1,1,1 (E_1 && E_2))

$E_2$ may take over some new variables from $E_1$. I would then combine $E_1$ and $E_3$ in the same way until $E_1$ with $E_n$ and then I'd start with $E_2$ with $E_3$ .. $E_n$ etc. at the end, $E_n$ will be an expression in a single variable. Normally this can lead to an exponential blowup for the size of an expression, but in my particular application, I found that because of variables are eliminated, $E_i$ && $E_k$ never has more than 39 variables (Property 2). Truth tables in 39 variables are still feasible.

Unfortunately, unlike matrix gaussian sweep, when substituting the variables, I lose information. For example, if
$E_1 = a \rightarrow b$ and $E_2 = b \rightarrow c$ and I'm sweeping with $E_1:b$. $E_2$ would become $E_2 = a \rightarrow c$.
Before the sweep, $a,b,c = 0,1,0$ was not a valid assignment, while after the sweep it is valid.

I'm not sure if this limitation can be overcome. Perhaps I should remember the original $E_2 = b \rightarrow c$ in a side-set of expressions, but then how to combine all the expressions in the side set? Or can I perhaps add $c$ to $E_1$, but then Property 2 won't hold anymore? Is there some 3rd property I should look for in my set of expressions, so that this method would work?

Truth table example

The truth table for $E_1 = a \rightarrow b$ (used above) is:

E_1 =
-------------
|a|b|allowed|
-------------
|0|0|    1  |
|0|1|    1  |
|1|0|    0  |
|1|1|    1  |
-------------

A truth table can express any boolean expression (or function) and the size is exponential in the number of variables.


texts: Proof that a given language is not context-free

texts:
Given the language $L = \{w \in \{a,b\}^* \, | \, |w| = n \cdot \sqrt{n} \text{ and } n \geq 42\}$ and the assignement to proof that $L \notin CFL$ with the Pumping lemma.

Assuming $L \in CFL$, would it be possible to start with defining a language $L' := L \cap a^+$ which has to be context-free since $CFL$ is closed under intersection with $REG$.
Now I would have to proof that $L' = \{w \in a^+ \, | \, |w| = n \cdot \sqrt{n} \text{ and } n \geq 42\}$ isn't regular because the alphabet contains only one symbol.

Let $k$ be the constant of the Pumping lemma and $m > k$ and $m > 42$. So $z = a^{m^2\cdot\sqrt{m^2}} = a^{m^3} \in L'$.

$|z| = |uvw| = m^3 ...$

How to continue?


texts: Determining number of $j$ such that $b_j \le c_i$ and $a_j \le b_i$ in time $O(\log n)$

texts: I have an array $A$ of length $n$, containing triplets (think of it as a $3\times n$ matrix). Can I re-order the array (without reordering a triplet's inner values) in time $O(n\log n)$ so that it is possible to answer the following query in $O(\log n)$? Given $i$, determine the number of $j$ such that $A_{2,j} \le A_{3,i}$ and $A_{1,j} \le A_{2,i}$.


texts:
During the presentation (a talk) Answer Set Programming: Boolean Constraint Solving for Knowledge Representation and Reasoning Torsten Schaub (University of Postdam) stated around twenty-one minutes into the talk, "You can't translate an ASP (answer set program) into SAT (propositional formula) in a modular way...." continuing... "If you don't extend the language and if you translate ASP into SAT you risk an exponential blowup."
Is there an example that clearly shows that Answer Set Program to SAT translation is exponential.
PS: Allowed to use Plaisted Greenbaum encoding or Tseitin transformation.


texts: For two regular languages, why is the set of words from one that don't have a subsequence in the other also regular?

texts:
In general, a string $x$ is a subsequence of $w = w_1\dots w_n$ if there are integers $i_1<\dots< i_k$ such that $x = w_{i_1}\dots w_{i_k}$.  The subsequence is proper if $k < n$ and $k > 0$.

With this definition given, a homework problem asks the following: Suppose $L$ and $L_1$ are languages, and define $L \diamond L_1$ to be the set $\{x \in L : \text{no string }  x' \in L_1 \text{ is a proper subsequence of } x\}$.  If both $L$ and $L_1$ are regular, does it follow that $L \diamond L_1$ is regular?  Justify your answer.

I've attempted to construct an NFA that would recognize $L \diamond L_1$, but this went nowhere, as things soon got overly complicated.  Any ideas or suggestions?


texts: Understanding recursion tree for withdrawal formula

texts:
$$
T(n) = T(n-a) + T(a) + cn
$$

Now the solution says that the height of the tree $(h)$ is:
$$
h = \left \lfloor n/a \right \rfloor
$$

And I don't understand why. Maybe I didn't understand the withdrawal formula as needed.


texts: How to calculate $\sum_{i=1}^n \mu^2(i)$ in less than $O(n)$'s time

texts:
To go with $O(n)$, we can use the linear sieve according to that $\mu(n)$ is multiplicative. But it seems that we don't have to work each $\mu(n)$ out and accumulate them together, because I only want to get $\sum_{i=1}^n \mu^2(i)$.

I am interested that is there any solutions that are faster than $O(n)$ to work $\sum_{i=1}^n \mu^2(i)$ out.


texts:
I'm currently trying to implement this paper. Based on a bayesian network, the paper stays unclear about how to ultimately use it's content ("straightforward inference").  But after a lot of researches (I have no background in that field), I think I can apply Viterbi algorithm to get the expected result. I will give here a description of my problem but as I might have misunderstood some things, the non biased description of the algorithm is available Section 3.1 of the paper.

We try to find a set of breakpoint S.

The test case is "aaa bb cc ddddd" with text width 6 which should result in:

aaa
bb cc
ddddd

which is a set of breakpoints S = {0,1,3,(4?)}. Just for information, for the test, I use o-=14 and o+=3 to get more manageable results (ref. paper).

We try to find the boolean value of i ∈ S for each word (character in the paper). We start with the beginning of the paragraph with nlw0=0 (nwli is the width of a line from previous breakpoint) and 0 ∈ S.

First take next token c1 = "aaa" with width cw1 = 3.

So, trying to use viterbi algorithm, I explore both possibilities of i ∈ S and i ∉ S. It leaves us with two paths, set of breakpoints with nlwi = 3 (Pa is described page 7):

{0,1} with Pa(0, -6)≅0.8713
and {0} with Pa = 1

No choices here to make so it's seems okay. But I'm not sure if I even use Pa the right way...

Then I tried a few things which all ended wrong. It more or less looked like this:

Take next token cw2, try all possibilities and keep only the best ones for 2 ∈ S and 2 ∉ S.

It gives use 4 different sets:

{0,2} with Pa(3, -3) 4.45 product previous Pa. Total≅ 4.45
{0,1,2} with Pa(3, -3)≅ 4.45 product previous Pa. Total≅ 3.877
{0} Pa=1. Total=1
{0,1} Pa=1. Total≅ 0.8713

The best two sets we keep are {0,2} and {0} which already discards the expected result. Anyway I usually end up with no breakups at all...

So I'm probably missing something important. There are a few things I don't get in the paper either:

What is node bi used for?
and why is Pa described as the "acceptability of breaking-up up to ci instead of ci-1?


texts: Where can I find some free benchmarks to evaluate a MCU?

texts:
At present, I'm designing a soft processor with single-precision floating point unit (FPU). I am going to put my soft core into an FPGA and do some performance evaluation. The benchmarks are supposed to contain many single-precision floating point calculations, such as fadd, fmul, fdiv and fsqrt. Therefore, I can know the speed-up provided by FPU. Besides, I also want to compare my soft core with popular cores from ARM such as Cortex-M0, M1, M3. Since ARM provides DesignStart of these cores, it should be easy to put them into an FPGA and do comparision.

I only know 2 free benchmarks that could run on a soft core: Dhrystone and CoreMark. Can anyone share other free benchmarks for evaluation? Spending 1000+ dollars to buy a benchmark is not affordable for me.


texts: CRF message passing as convolution operation

texts:
I was reading the paper _Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials (Philipp Krähenbül and Vladen Koltun, in Proceedings of 25th Annual Conference on Neural Information Processing Systems (NIPS), 2011 pdf), and I didn't understand this equation (eq 5) in the paper:

I understand the first equation, but not the second one. If $k(f_i,f_j) = e^{-1*(f_i-f_j)^{2}}$, then $k(f_i,f_j)$ would return a scalar value between 0 and 1 ; 0 if $f_i$ and $f_j$ are far apart in the feature space, 1 otherwise. So, $k(f_i,f_j)Q_j$ adds a fraction of $Q_j$ to $Q_i$ . The first equation is clear. I don't understand how this leads to the 2nd equation. In the 2nd equation, the Gaussian kernel is now over $Q$  instead of being over $f_i,f_j$  and then multiplied by $f_i$. Where is the $f_j$? Can someone explain how the 2nd equation is derived from the first one?
$G \otimes Q$ would again return a value between 0 and 1, which is multiplied by $f_i$ (which is an n-dimensional feature vector). So the result of $(G \otimes Q)(f_i)$ would be an n-dimensional vector, and we subtract $Q_i$ (a scalar) from that. Am I misunderstanding something here?


texts:
I need to find the Myhill-Nerode equivalence classes for the language $$ L = \Sigma^*\setminus \left( \{\epsilon, cc \} \cup \{ cca^i: i\geq 2 \} \right) $$ over $\Sigma = \{a, b, c \}$
I'm familiar with the idea of separating suffix, but I really don't know where to start here.
Thanks!


texts: Does anyone know what are the most efficient algorithms for factoring polynomials in a field of characteristic zero, i.e, a field that may contain infinitely many elements. I'm mainly concerned within the context of the field of integers but I wouldn't mind the rationals as well.


texts: Closed form solution for optimization problem

texts:
Consider the problem of finding the real-valued matrix $C$ so that

$$\|S-AC\|_F^2\qquad(1)$$

is minimal. ($S$ and $A$ are real valued matrices and $_F$ denotes the Frobenius norm). This problem has a closed form solution of $C=A^+S$, where $A^+$ is the pseudo-inverse of $A$.

I need to control the magnitude of the elements in $C$, that is an extra regularization term $\varepsilon\|C\|_F^2$ must be added to (1). Is it there a closed form solution for minimizing

$$\|S-AC\|_F^2 + \varepsilon\|C\|_F^2\,?\qquad(2)$$


texts:
TL;DR: I implemented a special (?) binary tree and can't find any further details on the method I used on the internet. I would like to know if there are any  scientific papers discussing my implementation.

Long version:

I saw this very interesting binary tree using "bin numbers" in RFC 7574. The leaf nodes contain data and consist of even numbers, and a single integer can be used to address ranges of leaves.

                               7
                              / \
                            /     \
                          /         \
                        /             \
                       3                11
                      / \              / \
                     /   \            /   \
                    /     \          /     \
                   1       5        9       13
                  / \     / \      / \      / \
                 0   2   4   6    8   10  12   14

                 C0  C1  C2  C3   C4  C5  C6   C7

Implementation details are not part of this RFC, so I did the implementation myself. I use a flat array so that every node is positioned at the index of their "bin number" for fast O(1) access:

Tree = [ Node0, Node1, Node2, ... ]

I created some methods to inspect a single node:

depth(index) = log2( ~index & (index + 1))        // depth from bottom
pos(index)   = (index >> (depth(index) + 1)) & 1  // left or right

And some helper methods to navigate the tree/array:

lChild(index) = (index & 1) ? index - 2 ** (depth(index) - 1) : -1
rChild(index) = (index & 1) ? index + 2 ** (depth(index) - 1) : -1
parent(index) = pos(index) ? index - 2 ** depth(index) : index + 2 ** depth(index)

** = exp operator

I am asking myself if I'm reinventing the wheel here. I would like to verify and optimize my implementation but could not find any more information about this tree or storage method.

Does anybody know how to call this thing?


texts: Is it a problem that "successful" machine learning algorithms have large VC dimension?

texts:
In my limited exposure, it appears that "successful" machine learning algorithms tend to have very large VC dimension.  For example, XGBoost is famous for being used to win the Higgs Boson Kaggle competition, and Deep Learning has made many headlines.  Both algorithm paradigms are based on models that can be scaled to shatter any dataset, and can incorporate boosting which increases VC dimension.

According to VC dimension analysis, a large dimension is supposedly a bad thing, it allows models to overfit or memorize the data instead of generalize.  For example, if my model shatters every dataset, e.g. a rectangle around every point, then it cannot be extrapolated outside the dataset.  My grid of rectangles tells me nothing about points outside the grid.  The larger the VC dimension, the more likely the model will shatter a dataset instead of generalizing, and thus once exposed to new data outside the training dataset, it will perform badly.

Back to the original point, many of the most "successful" machine learning algorithms have this common trend of having a large VC dimension.  Yet, according to machine learning theory this is a bad thing.

So, I am left confused with this significant discrepancy between theory and practice.  I know the saying "In theory there is no difference between theory and practice, in practice there is" and practitioners tend to brush aside such discrepancies if they get the results they want.  A similar question was asked regarding Deep Learning, and the consensus was that it did have large VC dimension, but that doesn't matter because it scores very well on benchmark datasets.

But, it is also said "there is nothing more practical than good theory."  Which suggests such a large discrepancy has a significance for practical application.

My question then, is it true that the only thing that really matters is low error scores on test datasets, even when the theoretical analysis of the algorithm says it will generalize poorly?  Is overfitting and memorizing instead of generalizing not that big of a deal in practice if we have hundreds of billions of samples?  Is there a known reason why the theory does not matter in practice?  What is the point of the theory, then?

Or, are there important cases where a very large VC dimension can come back to bite me, even if my model has great scores?  In what real world scenario is low error and large VCD a bad thing, even with hundreds of billions of samples in the training data?


texts: Verifying that $f(x) \leq Cg(x)$ for $x \geq k$

texts:
I'm revising for a test and having problems with a past question. It states that $f(x)=5x^2+4x+3$ is $O(x^2)$ and has a series of sub-parts asking if particular values of $C$ and $k$ (e.g., $C=12$, $k=0$) are witnesses of this fact (i.e., $f(x)\leq Cx^2$ for all $x>k$).

My method so far has been to establish some "test scenarios" / cases for each pair of witnesses. E.g., for $C=12$, $k=0$, I need to verify that
$|5x^2 + 4x + 3| \leq 12|x^2|$ for $x > 0$.

In this case my method has been to test for  $x = 0$, which is true and some other arbitrary values $x> 0$. It seems to me that this may cause errors, because I'm only checking cases instead of actually proving it.

For example, for $C=12$, $k=1$, I got the wrong answer answer because
$f(x) > x^2$ for $x \approx 1.2$ and I did not check for that x-values in that area.

Any suggestions for a bulletproof method for questions like these?
Could I do it by induction?


texts: Given a graph, finding if a node has three adjacents from a node subset $N$

texts:
Given a graph $G = (V,E)$, assume that we have two disjoint vertex sets $N = \{n_1, n_2 ...\} \subset V$ and $P = \{p_1, p_2, ...\} \subset V$ such that $N \bigcup P \neq V$.

I want to find if there exists an edge subset such that $\{<n_i,p_l>, <n_j,p_l>, <n_k, p_l>\}$ i.e. three nodes from $N$ and one node frpm $P$.

Should I first list the triplets of $N$ and search if they have a common adjacent in $P$ or for each $p \in P$, check if $p$ has three adjacents in $N$?

Which method would be more efficient? Or does it depend on the sizes of the sets?

Edit:
What if I want to list all the edge subsets for all $p_l$?


texts: What are examples of inconsistency and incompleteness in Unix/C?

texts:
In Richard Gabriel's famous essay The Rise of Worse is Better, he contrasts caricatured versions of the MIT/Stanford (Lisp) and New Jersey (C/Unix) design philosophies along the axes of simplicity, correctness, consistency, and completeness.  He gives the example of the "PC loser-ing problem" (discussed elsewhere by Josh Haberman) to argue that Unix prioritizes simplicity of implementation over simplicity of interface.

One other example I've come up with is the different approaches to numbers.  Lisp can represent arbitrarily large numbers (up to the size of memory), while C limits numbers to a fixed number of bits (typically 32-64).  I think this illustrates the correctness axis.

What are some examples for consistency and completeness?  Here are all of Gabriel's descriptions (which he admits are caricatures):

The MIT/Stanford approach

Simplicity -- the design must be simple, both in implementation and interface. It is more important for the interface to be simple than the implementation.
Correctness -- the design must be correct in all observable aspects. Incorrectness is simply not allowed.
Consistency -- the design must not be inconsistent. A design is allowed to be slightly less simple and less complete to avoid inconsistency. Consistency is as important as correctness.
Completeness -- the design must cover as many important situations as is practical. All reasonably expected cases must be covered. Simplicity is not allowed to overly reduce completeness.

The New Jersey Approach

Simplicity -- the design must be simple, both in implementation and interface. It is more important for the implementation to be simple than the interface. Simplicity is the most important consideration in a design.
Correctness -- the design must be correct in all observable aspects. It is slightly better to be simple than correct.
Consistency -- the design must not be overly inconsistent. Consistency can be sacrificed for simplicity in some cases, but it is better to drop those parts of the design that deal with less common circumstances than to introduce either implementational complexity or inconsistency.
Completeness -- the design must cover as many important situations as is practical. All reasonably expected cases should be covered. Completeness can be sacrificed in favor of any other quality. In fact, completeness must be sacrificed whenever implementation simplicity is jeopardized. Consistency can be sacrificed to achieve completeness if simplicity is retained; especially worthless is consistency of interface.

Please note I am not asking whether Gabriel is right (which is a question not appropriate for StackExchange) but for examples of what he might have been referring to.


texts: Nandgame--I am not sure I understand the Data Flip-Flop specifications

texts:
Nandgame (nandgame.com) has you solve puzzles of increasing complexity which culminate in constructing a simple CPU. You start at the level of nand gates, and build everything else up out of those.

I'm having trouble understanding the specifications for the Data Flip-Flop puzzle. If I'm reading it correctly, when the "clock" bit changes from zero to one, the storage device should send its value to output, but while the "clock" bit remains either one or zero, nothing should change the output value.

What I'm stuck on is this idea of having output change when and only when the clock changes from zero to one I can't see a way to do that which doesn't allow the output to change any time the clock bit is equal to one (or trivially, equal to zero if I thrown an inverter on it fsr). But that results in a failure when I submit such solutions.

Could I just be reading the specifications incorrectly somehow?

Here is a transcription of the specification:

A DFF (Data Flip-Flop) component stores and outputs a bit, but only change the output when the clock signal change from 0 to 1.

When st (store) is 1 and cl (clock signal) is 0 the value on d is stored. But the previous value is still emitted.

When the clock signal changes to 1, the flip-flop starts emitting the new value.

When st is 0, the value of d does not have any effect.

When cl is 1, the value of st and d does not have any effect.


texts: A dynamic programming problema on containers and product

texts:
We have two production lines - product and container (two integer arrays product_list[N] and container_list[M]).
If the volume of a container is equal or larger than that of a product, then we could put the product into that container.

We want to put as many products into containers as possible.

We can pick any initial position of products (any i in product_list array), and match each container one by one. We can't skip product but we can skip containers. No recurring of arrays i.e. product line won't go back if reach the end.

My solution is that, start from first product until last product (for i = 0; i < N), then match the container list from 1st to the last (for j = 0; j < M).
For each starting point i, count the number of matched products (count_array[i]+1 if container_list[j] >= product_list[i]).
Finally output the maximum of the count array.

I believe my algorithm isn't optimal, but I can't come up with a better way to do this problem in dynamic programming.

Any help will be appreciated! Thanks for everyone reading this problem!


texts: Longest Common Sequence reduction proof question

texts:
I'm trying to get at least a laymans understanding of how the Longest Common Sequence (LCS henceforth) can be shown to be NP-Hard and I'm trying to do that by reducing it to an NP-Complete problem like Vertex Cover. I read through this downvoted question on another stack exchange.

  I am trying to understand the demostration of intractability of the
  LCS problem, as stated as a reduction from Vertex-Cover problem, and
  so far, i'm stuck with the demostration of the problem in this paper
  from David Maier

  Anybody know some simple example to reduce LCS from Vertex-Cover?

With a self answer of

  It was as simple as:

  Take a Vertex-Cover problem to convert to LCS
  Create a string template from the Vertex-Cover graph
  Take each vertex from the Vertex-Cover problem and generate an equivalent string for it, ommiting the vertex selected
  Presto, you have a LCS problem equivalent.

  Thanks for the downvotes

I've been trying to work out on paper how this makes sense but keep coming up against a wall. Could someone show me how this is either incorrect or how it is correct with a more worked out example/proof?


texts: Non-deterministic Finite Automata | Sipser Example 1.16

texts:
I am working through the Sipser Book (2nd edition) and came across this example, which I do not understand. In the book it states that this NFA accepts the empty string, $\epsilon$.

Could someone run me through why this is the case?

My understanding is that $\epsilon$ will move to $q_3$ which is not an accept state.


texts: What goes into proving two complicated programs are equivalent?

texts:
Say I wanted to prove that two programs were equivalent (either rigorously if possible, or informally if not). More specifically, say I have something relatively complex such as an HTTP server implemented in C, and one implemented in Node.js/JavaScript. What can I do in terms of saying "these two are effectively the same"? What are my options? What is possible? What is not possible?

It's been a little while since I've looked into proving program equivalence (I'm currently linked to this, but I can't read it yet haha, and it looks like it's focusing on extremely simple programs like equality checks or basic loops, whereas I'm asking about a robust HTTP server).

Essentially (I'm imagining) I want to say "these two programs in JS and C do the same thing". That "do the same thing" is obviously vague, but at the same time it means something specific. Any observable outcome on either system is generally the same, give or take. So it's like a proof, but without being a perfect proof. It's like it's a partial proof or something.

I would like to be able to say of my programs "these two implementations are equivalent for all intents and purposes". I would probably start by providing measurable guarantees or observations about performance and input/output behavior, and then write some tests, and ... I don't quite remember, somehow make statements about the system. Or should I just be thinking that "a functioning HTTP server in either language is an AXIOM". That would simplify it :) Just assume it does the same thing as one another. But that's sidestepping it feels like.

Wondering what are my options here? How far can I take this in theory? I am not concerned with how long this would take to implement or define, if it takes years, fine. I just would like to know what is possible in terms of making the statement "these two programs in C and JS are equivalent" more rigorous and nailed down. What techniques/theories/research-directions could I look into to make it possible?

Right now I am just assuming they are equal implicitly, allowing my code to call either the C function or the JS function knowing that the ~overall effect~ is the same (nebulous, I know, don't know how to pin it down). I would like to apply some math or model checking or program simulation or something to this so that I can make it more solid, if possible :)

At the other end of the spectrum is proving that 3 > 2 is equivalent in both C and JS. What am I even supposed to do in this simple case? Making that slightly more complex on it's way to a full HTTP server, copying a string in C is very different than in JavaScript, but it's a relatively simple thing. Where do I even begin to prove those "operations" equivalent between the two languages? Or if not "prove", then just "state" that they are equivalent, with some backup evidence or something, I dunno.

Here is not much, but this diagram is what I'm basically trying to do:

At a broader level, the problem seems to be similar to this.... Say I want to get a medallion. I can either go the store and buy one, or I can 3D print one. Both "algorithms" (going to the store, or 3D printing) are way different from each other, but they are effectively the same. There would be no straightforward way to step-wise prove these are equivalent operationally (from what my imagination provides), but visibly the end result is the same. How would you (even here) state this with rigor?


texts: Lower bound of degree of polynomial approximating parity

texts:
Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$

It is known [See e.g. Lemma 5 of this lecture note] that any polynomial $f(x_1,\dots,x_n) \in \mathbb{R}[x_1,\dots,x_n]$ of degree at most $\sqrt{n}$ must disagree with $\text{MOD}_2$ on at least a constant fraction of inputs.

  Is this true for a polynomial with degree $n^{0.5+\epsilon}$ for some small constant $\epsilon>0$ ? How about a polynomial with degree $o(n)$?


texts: Type system with subtyping on abstract data types?

texts:
Consider this example on binary trees in some ML-like language:

type tree =
  | Null
  | Node of tree * tree

let rotate_left p =
  match p with
  | Null -> p
  | Node (a, q) ->
    match q with
    | Null -> p
    | Node (b, c) ->
      Node (Node (a, b), c)

In the definition of rotate_left above I only want to consider rotation on trees where the right subtree is also a node:

let rotate_left (Node (a, Node (b, c))) =
  Node (Node (a, b), c)

In relation to a ML-like type system, this second version of rotate_left is partial where as the first version is total.

Is there a type system expressive enough that such functions would be considered total?

Note;
I use the term "subtyping" in the title of this question, since I think of the values of the type of the second version of rotate_left, to be a subset of the values of the type of the first version of rotate_left.


texts:
In algorithm analysis what exactly defines a subproblem?

I know that one of the optimality conditions for greedy algorithms is that all subproblems of the solution are also optimal, but to me this begs the question. Are subproblems defined relative to a data set, a problem on that data set, or a solution to that problem?

As an example, a shortest path algorithm on a connected graph with vertices {a,b,c,d,e} for a path from a to e may return {(a,b),(b,c),(c,d),(d,e)}, and the subproblems here to me are every path from an earlier vertex in the list to a later vertex in the list, implying that you have subproblems relative to a solution.

An example that confuses me, however, is dealing with sequence alignment on strings.
Given an optimal alignment for two sequences, what are the subproblems? Is it the alignment of any partition of the two strings? Because the answer to an alignment problem can actually return different strings.

For example, if we're aligning ["AT","CAT"] we should get ["_AT","CAT"]

But for the 0th index here it doesn't make sense to say that ["_","C"] is a subproblem, or that ["A","C"] is a subproblem, because they're both trivial (alignment of two singletons can never be suboptimal), and ["A","C"] is never actually aligned/compared in the result.


texts: How can computer memory remember after the computer runs out of battery?

texts: According to my fragile knowledge of computer hardware the way computers store information is by electric circuits. If there is current the bit is 1 if there isnt its 0. My question is after a computer runs out of battery the memory stil holds all of the information, how? Wont it be the case that all the bits are 0?


texts:
I am currently studying model theory and I am trying to decide if a clause is a Horn Clause. I know that a Horn Clause is a clause with at most one positive literal, but there are some clauses that it is not easy to decide whether they are Horn or not.

E.g.,

(P->Q)->W

Is there any way to decide whether this clause is Horn or not, or do I have to make further calculations in order to bring it to a Disjunction form?


texts: How to find a Deterministic PDA for an intersection of languages

texts:
There are two languages,

$\qquad L_1 = \{w\in\{a,b\}^*: N_a\leq N_b\}$ and
$\qquad L_2=\{w\in\{a,b\}^*: N_b\leq 2N_a\}$

where $N_a$ means the number of occurrences of $a$ in the string $w$. Same for $N_b$.

I've proved that $L_1$ has a DPDA (hope this is right).

Now I want to know whether $L=L_1\cap L_2$ has a DPDA or not.

I applied the Pumping lemma but it seems like there is no contradiction. I tried to draw the DPDA but failed. Maybe $L$ has a nondeterministic PDA but not a DPDA. However I cannot prove this.

Could anyone give me some hints?


texts: Principle of locality for object-key data pairs

texts: It seems that if we only have object-key cache then we won't have spatial locality and only temporal locality. I use memcached in a python application and that has only object-key pairs and no hierarchy. Is this observation correct and why don't object-key caches behave more like physical cache memories where the latter have hierarchies like L1, L2, L3 etc?


texts: Decider for the family of Turing machines that move infinitly to the right on some input

texts: I need help finding an algorithm which, given a Turing machine description $\langle M \rangle$, decides whether there exists an input $w$ such that in the computation of $M(w)$, the head only moves right and $M$ never stops.


texts: Difficulty understanding a quote from SICP

texts:
Not sure if I should ask it here but I'll just go ahead. I was reading SICP (Structure and Interpretation of Computer Programs). And there was one quote from Alan Perlis in the preface to the second edition.

  Is it possible that software is not like anything else, that it is meant to be discarded: that the whole point is to always see it as a soap bubble?

First, I can't understand at all what he tries to say here, despite the sentence being totally grammatically-correct. Second, I would like to know how does this sentence fit into the context of SICP?(e.g., how might one get additional insight from understanding this sentence, in line with SICP?)

Thanks in advance!


texts: Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$

texts:
I have recently encountered the following problem which I heard can be solved by using BIT (binary indexed trees) but I am not sure how:

Given an array $a[1, 2, \ldots, n]$ and $Q$ queries of the form $(L, R, i)$ $(L\leq i\leq R)$. For each query, you have to print the number of $j$ such that $L\leq j\leq R$ and $a[j] \leq a[i]$.

I tried coordinate compression and then sorting the queries by increasing order of $i$ (answering the queries offline), but the L, R part make things hard. I think we can convert the query $(L, R, i)$ into two parts $(1, R, i)$ and $(1, L-1, i)$ (and subtract them), but how to find the answer for that either?

Also note that this problem can be solved by Mo's algorithm, but I am looking for something like $O(q \log n)$ or $O (q \log^2 n)$ (maybe binary search on the answer and do some magic with bits?).

Thanks :)


texts:
It is given that for a relation R all the attributes of the relation appear in some of the candidate keys. It is also given that there is only one compound candidate key which exists for a relation, all the other candidate keys are simple candidate keys. What can be said about the normal form of R?

In my opinion, since all the attributes are part of some candidate attribute, it is surely in 3NF. But I am not sure if we can extend our reasoning to claim that R in also in BCNF(as claimed by the solution).

Can anyone please help me out why R can be said to be in BCNF normal form?

Thanks in advance!


texts: Prove a statement about searching in binary search tree

texts: Suppose search $n$ times in  a given binary search tree $T$ with $n$ nodes. each searching have cost $C_i$, and $\sum_{i=1}^{n}C_i=O(n\log n)$. Now the problem is to find height of $T$. I think it be $O(\sqrt{n\log n})$, but after reading this post, what is correct proof to get that result?


texts: Theory for programs that are "embedded" in other programs?

texts:
We can make the following distinctions: (I will use the term "program" and "machine" as synonyms).

A (baseline) machine. This can be formalized by a Turing machine. It receives an input, and computes an output, fully by itself.
An oracle machine $T$. This is a Turing machine, but with an additional feature: it can use some black box "oracle" as a subroutine.
A ??? machine $T$. This is a machine that does not have any subroutines like an oracle machine. Rather, it is itself a subroutine of some black-box (parent?) machine $P$.

The third type is supposed to capture the idea of "dependency injection". Suppose we have a fixed parent machine $P$, which takes as input our machine $T$, and uses it (in some way) to compute its output.

In the case of oracle machines $T$, we can "plug" an oracle $O$ into $T$, and study what can be achieved by $T$ given this oracle.
in the case of ??? machines, we do the opposite: we "plug" $T$ into a $P$, and see what can be achieved by $T$ given the constraint that it will be used as a subroutine by $P$.

The question is: What can we make $P$ compute, by programming $T$, given the constraint that $T$ will be used in some way (exactly how depends on the specific context we're interested in) by $P$? i.e. which functions are "$P$-computable"

Some observations:

oracle machines $T$ with oracle $O$ can compute at least as much as Turing machines, since they can just ignore the oracle.
??? machines $T$ with "parent" $P$ can compute less than Turing machines, since they are constrained by being used by $P$ in some way that the programmer of $T$ cannot control. At two extremes: (1), $P$ may simply ignore $T$, in which case there is only a single unique "$P$-computable" function, namely whichever $P$ computes. (2) $P$ may literally copy its input into $T$, and output the output of $T$, in which case every Turing-computable function is also "$P$-computable". In between these extremes, $P$ may use $T$ as a subroutine, and use the output in some restricted way.

Alternatively, here is a more "mathematical" way of stating this:

  Suppose we have a space $\mathcal C$ of "computable functions" (e.g. Turing-computable), and we have a "parent function", $P:\mathcal C\to \mathcal C$, which gives a family of function-parameterized functions $P_c$. $P$ takes a computable function $c$ (the function that is computed by the turing machine $T$ in our earlier formulation), and outputs a computable function $P_c$ (the function that is computed by giving $P$ the machines $T$ as its subroutine). The question now is: What is the image of $P$? These are the $P$-computable functions.

Is there a theory about something like this?


texts:
"Can QTM (Quantum Turing machine) solve halting problem"
Why not have an immediate answer "No QTM Can't do this", we know that Turing proved it impossible when DTM , i meant , " Why we cant use the same proof which turing use it"
Let H be a program in a quantum turing machine that will solve the issue of halting , why not say that a contradiction will occur
Thanks


texts: The class of grammars recognizable by backtracking recursive-descent parsers

texts:
It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring two alternatives starting with $k$ occurrences of the same terminal).
My question is the following: Is there an identifiable strict superset of $\bigcup_{k \in \mathbb{N}} \text{LL}(k)$ grammars that can be parsed by a backtracking recursive-descent parser, regardless of complexity?
If yes, is the maximal superset also identifiable?


texts: Is this argument wrong "since DOM is special kind of RDOM, then RDOM is NP-hard"?

texts:
The domination problem $DOM$ is defined as
$$
DOM = \{ \langle G,k \rangle\ | \ G \text{ has a domination of size } k, K \in \mathbb{N} \},
$$
and the rainbow domination problem $RDOM$ is defined as
$$
RDOM = \{ \langle G,r,k \rangle \ | \ G \text{ has a r-dominating set of size } k; r,k \in \mathbb{N} \}.
$$
A $r$-rainbow domination for a graph $G=(V,E)$ is a mapping of the form  $f:V \rightarrow 2^{\{ 1,\ldots, r\}}$ such that $f(v) = \emptyset$ implies $\cup_{u \in N(v)} f(u) = \{ 1,\ldots , r\}$ where $N(v) = \{ u \ | \ \{u,v\} \in E \}$.  The size of $r$-domination is defined as $\sum_{v \in V} |f(v)|$.

To show that $RDOM$ is $\mathbf{NP}$-hard, one must show that $DOM \leq_P RDOM$, i.e. given an instance $\langle G,k \rangle$, construct an instance $\langle G',r,k' \rangle$ in polynomial time such that $\langle G,k \rangle \in DOM$ if and only if $\langle G',r,K' \rangle \in RDOM$.

My friend states that we know that a domination is a $1$-rainbow domination in the same graph, i.e. domination is a special kind of rainbow-domination, and since domination is $\mathbf{NP}$-hard, then $RDOM$ is also $\mathbf{NP}$-hard. How to convince him that this is wrong? or this argument is correct?


texts: what is the complexity of recurrence relation?

texts:
what is the complexity of below relation

$ T(n) = 2*T(\sqrt n) + \log n$

and $T(2) = 1$

Is it $\Theta (\log n * \log \log n)$ ?


texts: How do we show $\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$ in lambda calculus?

texts:
How do we show $$\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$$?

I was going through the slides here  and it asked to do the above but by page 16 of the slides we have not defined what lambda applications are suppose to be. Thus is remained complete unclear because I don't know what the syntax:

$$\lambda x . x (\lambda y .y)$$

means. Can someone clarify to me how to proof this rigurously using alpha-conversion et al?

i.e. without using $\beta$ equivalence which is the application rule I assume.


texts:
Does there exist a Boolean function for which no sum-of-products expression that minimizes the number of products also simultaneously minimizes the number of literals (counting repetitions)? Minimization methods like K-maps choose one of these objectives and optimize; I am just wondering if minimizing one automatically minimizes the other, or there is a counter-example.

Some clarificatory comments:

Sum-of-products refers to OR of ANDs. Each AND involves an arbitrary number of literals. Each literal is a variable of its complement. While counting the number of products of such an expression, each product contributes 1 irrespective of the number of literals it involves.
The function could be partial (i.e. "don't care" on some inputs)


texts: How to read off the set represented by a van-Emde-Boas tree?

texts: I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to understand the actual data structure. I have no clue how the "min" and "max" members are actually used, I'm not talking about the procedures but just how the following picture is supposed to be interpreted. Can anyone help me with this?


texts: Mathematical model on which current computers are built

texts:
It is said that "The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation." [Wikipedia]

So on which model current machines are built?


texts: Intersections of some context-free languages

texts:
Suppose We have Some language as follows:

$L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$

$L_2=\{ww^R ww^R | w \in ( \Sigma  + \Sigma)^*\}$

$L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a substring of } x\}$

1) there is a PDA (push down automata) that accept $L_2 \cap L_3$

2) there is a PDA (push down automata) that accept $L_2 \cup L_3$

3) there is a PDA (push down automata) that accept $L_1 \cap L_3$

4) there is a PDA (push down automata) that accept $L_1 \cup L_2$

I read in some sites that:

(a) is false, and we can say 3 and 4 are wrong because we have no language that is not closed under union but closed under intersection.

I read a lot of material for finding the answer of this question mentioned by Prof. M. Farshchi on Entrance Exam in 2012, but I failed. I need some one to help me with a bit detail for each one. Thanks.


texts: How can I prove or disprove that the following function is bijection?

texts:
For a research project, I tried to prove or disprove that a function called xxhash128_low is a bijection from 64 bit unsigned integer to 64 bit unsigned integer. I have shown that it is sufficient to prove that the following critical code is a bijection:
Input: a 64-bit integer x
0. Let c=0x9e3779b185ebcaa7
1. Let x_low= the 8-low bytes of c*x.
2. Let x_high= the 8-high bytes of c*x.
3. w= x_high+2*x_low.
4  y= shift right 3 bits of w.
5. return x_low XOR y.

What I have proved till now: returning only the low 64 bits, x_low, can be shown to be a permutation. Also, y can be expressed as a function of x_low (i.e., y=f(x_low)).


texts: Control flow graph for 3 Address Code inquiry

texts:
I'm supposed to do a three address code for the following semantic action

S-> repeat S1 until E times_in_a_row B holds

Which is meant to be:

Repeat Statement 'S1' as long as the condition B had not been 'true' 'E' times consequently. So I drew a control graph (not sure if it's called like that).

But I'm baffled, if I can use the block E->t before using the block for S1 code. Because in the semantic action the E appears after the S1. I think it will cause problems when I put markers for back-patching..

If you think so too, can you recommend a better alternative?

PS: the nextlist for S1 should have an arrow to the label B. But it's missing in the picture.


texts: Can anyone give me an instance of 3SAT with exactly one solution?

texts: I need an instance of 3SAT with exactly one solution but I cannot think of or find one anywhere. Can anyone please give me an example?


texts: In a DAG, finding the path with the highest score

texts: Given a directed, acyclic graph in which each node has an assigned integer score, what is a fast way of finding the path from a start and end vertex with the highest cumulative score? I thought of a DFS approach in which we start at the end and run the graph in the reverse way, saving at each node the best cumulative score attainable. To print the results, we start at the first node and greedily pick the next node with the highest cumulative score. However, I don't think this is the best way as we might be traversing the same paths a lot of times if we are given an unfriendly graph. Is there a better way of doing this?


texts:
I'm reading a paper which has quite a few formulas. I'm getting quite confused with some of the notation. For example
I am able to pick-up on the BNF Notation (::= -> "is defined as") but the dot and vertical line, I'm not sure of. Coming from a computer science background, I would assume it's an "or" operator, but that wouldn't make much sense. It looks like the right side is a tuple? Not sure what the dot/vertical line is supposed to represent.
Any advice on a framework on how to break these down? Most of the time the paper describes the equation in an abstract sense, but still leaves me in the dark understanding the different parts of the equation. Is there a cheat sheet I can reference?


texts: Finding the number of distinct maximal matching in a bipartite graph

texts:
In a bipartite graph, how can we find the total number of ways of getting a maximal matching?

The cardinality of both the sets in the bipartite graph may not be the same. So two matchings are said to be different if they have at least one distinct edge.


texts: How to generate snowflakes of a fixed area as challenges for the FridgeIQ puzzle?

texts:
I have been presented a set of FridgeIQ by a friend and she has planted an idea in my head.

FridgeIQ is a geometric disection puzzle consisting of 16 polygonal tiles as seen in the terrible picture near the bottom of this post

The shapes of the tiles are based on a square grid with the occasional diagonal across one of the grid fields. The total area of all the tiles is 40 such grid units. Each tile is identified by a single unique letter.

In the box comes a set of challenges, each giving a subset of the tiles and a shape to create. For example one challenge is: "construct a square using the tiles BDQSYJN". Which I have done in that picture and I have some left-over tiles that were not part of that particular challenge.

In addition to the standard challenges my friend has presented me with an extra set of target shapes which finally are the point of this question. I have attached another picture showing one of them in solved state.

These extra challenges all use the complete tile set, so their total area is 40 units, and they all have fourfold mirror-symmetry. Not all of them are as simple like the one in the picture, some have a hole or holes, but they are all connected.

I shall call these shapes "snowflakes" because they in a way resemble decorative snowflakes cut out of folded paper to generate the symmetries. Especially the ones with holes.

I have been asking myself: How many such shapes with these constraints are there that can actually be made from the given tiles?

Snowflakes per se there are infinitely man. But I believe the set of connected ones with finite area made only of half-unit triangles must be finite. Propably enormous, but finite. The solveable ones are a subset of those.

What would be a good algorithm to generate them? I do not expect there to be an efficient way, nor do I believe the universe has enough time left to actually make them all. But I would love to find at least some new ones.

Here's some unfinished thoughts so far:

As a first step I have built a simple recursive-backtracking solver that reproduced my manual solutions (and found loads of alternative ones). So even if it would be terribly inefficient I could just generate snowflake-shapes at will and use my solver to check them.

I have been thinking that it would suffice to generate one eighth of the shape, one half-quadrant, with a total area of 10 units. Symmetry provides the rest. Note that the solution does not have the same symmetry when considering individual tiles, only when the complete shape is taken into account.

To generate candidate shapes I could just put 20 half-unit-triangles into the half-quadrant. Hopefully in some systematic fashion. Most of those arrangements will not be compact enough and be unsolvable, though. And without a good idea for weeding them out their numbers are absolutely intractable.

Another approach would be to just generate combinations of the tiles and check them for symmetry. Again the algorithm would have to favour symmetric layouts or the exploding combinatorics mean I can never hope to find even a single new layout.

Any ideas? Keywords for searches and/or pointers to literature are also appreciated.

Thank you very much.


texts: Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$

texts: Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the algorithm / data structure and improve the time complexity to $O(|V|+|E|)$?


texts: Spectral clustering algorithm doesn't use all available clusters

texts:
We have implemented a spectral clustering algorithm according to the article Multiclass Spectral Clustering (Yu and Shi, Proc. IEEE ICCV '03, vol. 2, pp. 313–319, 2003; PDF).

We used the algorithm to test simple cases of clustering and it seems to work, however in some cases the algorithm doesn't use all the available clusters meaning we get some empty clusters.

A few questions:
1) Can spectral clustering give empty clusters?
* If it can, is there an algorithm that demands that all clusters are occupied?
2) Is there a newer or better algorithm we should consider?

Below link has a matlab code we wrote and an example:
* The example is for 20 clusters and a specific weight function.

https://technionmail-my.sharepoint.com/personal/sgiladfe_campus_technion_ac_il/_layouts/15/guestaccess.aspx?folderid=12ab9758bb2af4935aa5f0cda34ecd81b&authkey=AVooH-7f_D1umLEeI5PsREM

Thank you,
Gilad


texts: Constructing a turing machine from a PDA - dealing with non-determinism

texts:
Given a PDA $P$, I believe we can simulate it with a turing machine with 2 tapes - one for keep reading the input and one for the stack.

But, a PDA transition function may have multiple transitions for a given state, letter, and the stack top (the non-deterministic part, or splitting). How can we deal with that in a turing machine?


texts: Complexity of simulating idle games (pt1)

texts:
An idle game (Cookie Clicker is a well-known example) is a game where you set up automatic resource production, and most of reasonable human play is then waiting as resources accumulate. Typical implementation is in the form of a "tick loop", where resources update say once per second, generally increasing.
But many games can implement an "offline mode" where instead you can exactly calculate any number of ticks in one step. For example if you were producing 1000 cookies/second, and you come back after 1 hour, you've produced 3.6 million cookies exactly--no need to simulate all 3600 ticks. Then the player can reduce the update rate on screen, or come back to the game in 5 hours without running a program continuously. (Aside: many real games offer an "offline mode" which does NOT exactly match what would happen playing the game for the same length of time, but here I'm asking about exact simulation).
I am trying to figure out for which idle games an it's possible to efficiently compute many ticks in one step ("offline mode").
In a typical idle game (think "cookie clicker"), you have a bunch of resource generators, and each one generates some resources each tick. For example, maybe you have a cookie stove, which produces 5 cookies/tick. And you could also have a generator factory, which produces 1 cookie stove/tick.

For each resource, it produces some fixed list of resources each tick. Let's say we just have a list of what each resource produces each tick.

A resource costs something to buy. This is actually irrelevant for the simulation--buying is only a player action, and can't be done automatically.

A problem input will be a set of starting resources, and a number of ticks to simulate. Output should be the resources after that number of ticks.

If there are no cycles, an offline mode is definitely possible. The number of each resource is a linear (if it is not produced by anything else), quadratic (if it is produced by a linear resource), etc. So it's always a polynomial, which is easy to calculate.

My first question: is this still easy if we allow cycles, ex a "general purpose factory" that produces both general purpose factories, and cookies?
Second question: is this easy if we allow simple "autobuy"? Ex. convert 1000 cookies into a cookie factory, and buy as many as possible, on each game tick.
If it's easy, show how to do it. If it's hard, prove it!


texts: Simple question about grammar derivations

texts:
I'm learning the basics of grammars and compilers for a comparative programming languages class, but having a bit of trouble with one aspect of grammar derivation.

Here is an example of a grammar derivation in a Youtube lecture I found. I get everything he covers here except that it isn't clear to me how a derivation is chosen when there are multiples available.

For example, in the video he constructs a grammar E that has productions E + E, E * E, and id. I'm assuming that the correct derivation is chosen by pattern matching the input string to the grammar but that isn't made clear, nor is it really made clear in other sources I've read and watched. The derivation used at a given step sometimes seems arbitrarily chosen.

My reason for asking is because if it isn't matched to the input pattern, what is to keep his grammar from expanding an E into the (arbitrarily chosen) non-terminal production E + E infinitely, and never reach a terminal condition?

Edit Related question:

On the bottom of this page there is a discussion of leftmost and rightmost derivation. In the leftmost derivation example, how does it know the correct derivation to use to move from the second to third derivation? In other words, how does it know to make this derivation: a+X → a+ X*X

Why couldn't it just derive a+X → a+a and terminate? I know it doesn't match the input string, but what actually prevents that incorrect derivation from being chosen?


texts: Time complexity: Using linear programming to solve a system of linear equations

texts:
As far as I know, most direct methods for solving linear systems of equations have time copmlexity $O(n^3)$ (where $n$ is the number of variables), with the few methods being faster having huge constants, which make them only useful for very large matrices.
(Though, the best known bound I've found is $O(n^{2.373})$)

As every system of linear equations is also a system of linear inequalities, the formulation as linear program is one possibility, at least if one is satisfied with finding any possible solution.

My question now is:
How do solvers for linear programs fare against the regular methods of solving systems of linear equations? Are there cases in which they are better?


texts: Find a maximum matching that saturates a given set of vertices

texts:
In an unweighted bipartite graph $G = (X + Y,E)$, we would like to find a maximum matching, but among all those maximum matchings, we would like to find one that saturates a given subset $X_0\subseteq X$.
A necessary condition for the existence of such a matching is that $X_0$ satisfies Hall's marriage condition, i.e., for every $X'\subseteq X_0$, the number of neighbors of $X'$ is at least $|X'|$.
If this condition is satisfied, we can find a matching $M$ that saturates all vertices of $X_0$, but $M$ is not necessarily a maximum matching in $G$.
Is it always possible to extend $M$ into a maximum matching? Alternatively, is there a different way to find a maximum matching that saturates $X_0$ when the necessary condition is satisfied?


texts: Why is it not a good idea to branch a thread outside of a parallel region while other threads are still executing?

texts:
Say I have $n$ threads executing in a parallel region and one of them leaves the parallel region when others are still continuing to execute in the parallel region. Why this is a $BAD$ idea? For example you can consider this program.
$OMP PARALLEL IF(EXECUTE==true)

10 sum(id)=next(id)

30 result(id)=sum(id)*9.8
   if(converged(result(id)) goto 20
   go to 10

$SOMP END PARALLEL
   if(not_FINISHED) goto 30

20 print *,id

In this code we are branching out of the parallel region. I have read that its a $BAD$ idea to do so, but I have not got the reason. So it will be very helpful if someone can shed some light on this.


texts: Bad character rule in the Apostolico–Giancarlo algorithm

texts:
In the paper "Tight bounds on the complexity of the Apostoliko-Giancarlo algorithm" by Crochemore and Lecroq authors prove that algorithm performs not more than $1.5n$ comparison of characters in the processing stage. If I understand their proof correctly than there is no dependency on the bad character rule. Is it true?

Does the modification of Apostoliko-Giancarlo algorithm without bad character rule also perform not more than $1.5n$ character comparisons?

UPD: It seems, that Apostoliko-Giancarlo algorithm even without both rules (shift always by one) works in $O(n)$ and performs not more than $2n$ comparison of characters. But for $1.5n$ bound we definitely need the rule of a good suffix


texts:
I'm trying to implement an autocomplete feature for a search engine. I have a database of words(stemmed) that occur in the documents that I have. what I'm doing is:

Constructing a graph with words as nodes and weighted edges with weights as the number of times those 2 words have been searched together.
Each node also keeps track of which is the most commonly typed word next to it.
Whenever a user starts typing his query, this graph is queried and the first word is predicted by string matching and then ranking the matched words according to search frequency.
When the user starts typing the next word, the graph is visited and the neighbours of this node are retrieved and shown to the user in order of frequency(weight of edges.).

This is a rough overview of what I am trying to achieve. Are there any optimizations that could be made to this or something else entirely that can replace this?


texts:
Can someone please explain to me why this function runs in O($n^2$) rather than O($n^3$). I feel like since that for loop runs in O($n^2$) and f() is recursively called around n times, that it should end up being $n\cdot n^2$ for an overall O($n^3$).

f(n) {
    if (n == 0) {
        return 0
    }

    int result = 0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            result += j

        }
    }
    return f(n/2) + result + f(n/2)
}


texts: Problems that are easy on bipartite but hard on general graphs

texts:
Are there any problems that are easy for bipartite graphs, but hard for general graphs?

I am asking because some classical problems are formulated in reference to people looking for a spouse, such as the marriage problem (for straight people) and the stable marriage problem (for straight people). Both are in FP.

If one removes the requirement that there are two genders and that every man has to marry exactly one women, the general stable marriage problem (my term) is the same as the stable roommates problem, and a solution is no longer guaranteed to exist. I wonder if there are other problems which are explained using similar metaphors for which there is also an increase in complexity.


texts: Why are optimization problems always NP-hard and not NP-complete and what does this mean for other levels of the polynomial time hierarchy?

texts:
I have read that optimization problems cannot be $\mathcal{NP}$-complete, but are always classified as $\mathcal{NP}$-hard. When a problem is NP-complete, I know it is contained in $\mathcal{NP}$P. This implies in particular that it is not hard for the second level of the polynomial time hierarchy, e.g. for $\Sigma_2^P$ or $\Pi_2^P$. But since optimization problems are only NP-hard, I have no such knowledge. Or are optimization problems usually also $\Sigma_2^P$-hard or $\Pi_2^P$-hard, or just some of them?

Are there any interesting problems from combinatorial optimization that are harder than $\mathcal{NP}$-hard, e.g. hard for the second level of the polynomial time hierarchy?

I am in particular interested in problems from combinatorial optimization, e.g. BP (bin packing), TSP and CVRP (capacitated vehicle routing problem). They are all classified as $\mathcal{NP}$-hard, but CVRP is a generalization of both TSP and BP, so it should be harder? Bin packing should be easier, are there any results showing this?
Does anyone know, if there are hardness results for any of these problems that imply more difficult than $\mathcal{NP}$-hard?

I know there are many versions of CVRP and TSP and unfortunately I know not a lot about them.


texts:
When performing a local search, for example, a 2-node exchange in a metaheuristic (like GRASP), what is the usual stopping criteria for that procedure?
Some bibliography says that the local search stops when no further improvement can be found in the neighboorhoud of the current solution. My question is: whether it is correct to stop the local search as immediately as a first better solution is found?


texts:
How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?

If I have a recursive function like this for example (This is just an example, its not a real thing, it just demonstrates my question):

someFunction(n){
  base case:
    return 0
  if (some case)
    return someFunction(3n/4)
  else if (some other cases)
    return someFunction(n/4)
}

As we can see, the recursion calls itself in different cases and in different cases, the n is fractioned by different value, how can I write down the recursive formula for finding out the run time?

Is the formula something like:

T(n) = T(3n/4)?
T(n) = T(n/4)?
T(n) = T(3n/4) + T(n/4)?
T(n) = (Probability of first case)*T(3n/4) + (Probability of first case)*T(n/4)?

What if I have no idea what is my probability for each case?


texts:
Consider

Procedural flow control
Object oriented flow control
Functional flow control

In (strict) procedural flow control we can go only from start to finish but in OOP/Functional flow controls I guess we could start in the middle, go to the "start" and then to the end and alike (say by calling functions anywhere);
Do such engineering operations / code writing preferences have any ground in a theory in which at least two different flow control types are described?


texts:
So the problem I'm solving is this: I have a list of conversations of 3 messages each (for eg. "hi", " how are you", "remind me to fix this bug" is one conversation, and my problem will have many of these) and need to pick out the message that is most likely to be a task ("remind me to fix this bug" would be the message in the conversation above; "don't forget to commit your code" would be another in some other conversation). What kind of machine learning/NLP model could I use to relatively rank the messages in a conversation and "learn" across conversations? And what would my training data look like?

My thoughts: each data point in the training data is one conversation (a set of 3 messages) along with the message with the highest likelihood of being a "task." I was thinking of using a linear weighted function of features such as TF-IDF score. But how would I learn the weights?


texts: Problem complete for the class of ALL languages

texts:
$\text{ALL}$ is literally the class of ALL languages.

Are there $\text{ALL}$—complete problems?  That is, are there problems for which a solution would allow one to solve any problem whatsoever?  Such problems could reasonably be considered"the hardest problems, bar none".

One such problem seems to be: given a problem and an input size, output it's truth table.


texts: What is the relation between Universality and Geometric shapes in cellular automata?

texts:
When wolfram described Elementary Cellular Automata, most of the rules appeared as triangle and lines.

Now, Rule 110 consists of triangles which is proved to be universal.

Is there a relation between these triangles and universality like rule 110, or even other geometric shapes can be related to universality?


texts: Can $\{a^mb^nc^n\mid m,n \ge 1\}$ be proved non-regular using the pumping lemma?

texts: $\{a^mb^nc^n\mid m,n \ge 1\}$ intuitively seems like a non-regular language. It looks like the machine needs to remember the number of $b$s (which isn't limited). The pumping lemma can be used to prove a language is non-regular. In reference to the Wikipedia article linked (see "Use of Lemma"), every string I have tried doesn't give a contradiction. For example, a string like $a^1b^pc^p$ (where $p$ is the pumping length) seems to nicely split into $x = \varepsilon$, $y = a^1$, $z = b^pc^p$. What am I missing here?


texts: Find all words of length $k$ in lexicographic order

texts:
Given the alphabet $\Sigma = \{1,2,\dots, n \}$ and a parameter $k$ how can we find all words of length $k$ over $\Sigma$ in lexicographic order?
I thought of doing this recursively, but although the task is basic it seems pretty hard to come up with a general algorithm, even when using the last word as a parameter using recursion.
Will be glad for any help


texts:
Let Σ = {0, 1, ⊕, =} and define a language A as follows: A = {x = y ⊕ z | x, y, z are binary integers, and x is the XOR of y and z}. For example string “1011 = 1111 ⊕ 0100” is in A, whereas string “1011 = 1011 ⊕ 1011” is not

How can I show that A is not regular? How should I have the string?

Also, if the binary numbers are of fixed length, 64 bit long, would A then be regular or not?


texts: Explanation about the condition for connectivity in Erdos Reyni model

texts:
I am currently studying the Erdos-Reyni model, the $G(n,p)$ model to be specific.

Its easy to understand that all graphs with $m$ edges have generating probability of $p^{m}(1-p)^{n(n-1)/2 - m}$ where p is the probability that there is an edge between a pair of vertices.

What I am not able to understand is the following:

Almost every graph in $G(n, 2ln(n)/n)$ is connected. In other words,
As $n$ tends to infinity, the probability that a graph on $n$ vertices with edge probability $p = 2ln(n)/n$ is connected, as $n$ gets very large.

Any idea how to get this?


texts: Is there a 'string stack' data structure that supports these string operations?

texts:
I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing the set of strings $S$.

Add-Prefix-Set on $\mathcal{D}(S)$: given some set $T$ of (possibly empty) strings, whose size is bounded by a constant and whose string lengths are bounded by a constant, return $\mathcal{D}( \{ t s\ |\ t \in T, s \in S\} )$. Both these bounding constants are global: they are the same for all inputs $T$.
Get-Prefixes on $\mathcal{D}(S)$: return $\{ a \ | \ as \in S, a \in \Sigma \}$. Note that I don't really mind what structure is used for this set, as long as I can enumerate its contents in $O(|\Sigma|)$ time.
Remove-Prefixes on $\mathcal{D}(S)$: return $\mathcal{D}( \{ s \ | \ as \in S, a \in \Sigma  \} )$.
Merge: given $\mathcal{D}(S)$ and $\mathcal{D}(T)$, return $\mathcal{D}(S \cup T)$.

Now, I'd really like to do all these operations in $O(1)$ time, but I'm fine with a structure that does all these operations in $o(n)$ time, where $n$ is the length of the longest string in the structure. In the case of the merge, I'd like a $o(n_1+n_2)$ running time, where $n_1$ is $n$ for the first and $n_2$ the $n$ for the second structure.

An additional requirement is that the structure is immutable, or at least that the above operations return 'new' structures such that pointers to the old ones still function as before.

A note about amortization: that is fine, but you have to watch out for persistence. As I re-use old structures all the time, I'll be in trouble if I hit a worst case with some particular set of operations on the same structure (so ignoring the new structures it creates).

I'd like to use such a structure in a parsing algorithm I'm working on; the above structure would hold the lookahead I need for the algorithm.

I've already considered using a trie, but the main problem is that I don't know how to merge tries efficiently. If the set of strings for Add-Prefix-Set consists of only single-character strings, then you could store these sets in a stack, which would give you $O(1)$ running times for the first three operations. However, this approach doesn't work for merging either.

Finally, note that I'm not interested in factors $|\Sigma|$: this is constant for all I care.


texts: DFA which accepts all strings starting and ending with 'aa'

texts:
I have to construct a DFA which accepts set of all strings over {a,b} which start and end with 'aa'.
I have constructed the following DFA, but it does not accept 'aa' and 'aaa'. How can I make it accept all strings in the language.


texts:
I've got this question from an exercise and i'm not sure if it is possible to do so

Think of new data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure need to support the following operations:
Insert(v,Q) which insert into Q (no time complexity constrain here)
Delete-Median(v,Q) which takes the median out of Q in $O(1)$
The question is, What data do you store in your data structure and write pseudocode for both operations

I've thought about using binary search tree and when I insert I will try to make the tree as balanced as possible but when i delete the median( which is the root) I need to rearrange the tree and it won't be $O(1)$ and I'm not sure if it's possible to delete in $O(1)$ but I know that I show "print" the median in $O(1)$
Any help would be appreicaited


texts: Polytime algorithm for SUBSET-SUM assuming P=NP

texts:
In the Wikipedia page on P vs. NP problem there is an algorithm that "solves" SUBSET-SUM in case P=NP in polynomial time. (It's idea is to find a TM that gives a certificate). But it gives "yes" in polynomial time and runs forever if the answer is "no". It can be obviously fixed to give "no" in exponential time (just to run exponential algorithm if the first one is running for too long).

But can we explicitly describe an "honest" algorithm, which solves (and I mean, really solves) SUBSET-SUM (or any other NP-complete problem) in polynomial time assuming P=NP?

By "honest" and "really solves" I mean that the algorithm meets the classical definitions for a polynomial-time algorithm, i.e., here should exist constants $C_1, C_2$ such that at any input $x$ algorithm would terminate in no more than $C_1 \cdot |x|^{C_2}$ steps and output "yes" if $x \in $ SUBSET-SUM and "no" otherwise. The Wikipedia algorithm does not satisfy the first condition, so it doesn't "really solve" the problem.


texts: What are the models of distributed storage systems in the literature?

texts:
To understand the effectiveness and/or efficiency of a protocol implemented in distributed storage systems, it is often desirable to evaluate it in a quantitative way under a hypothetical model.

Obviously, every model is an approximation to the reality and there is not an all-purpose one. I expect to do a mini survey of the models of distributed storage systems in the literature. Specifically, I am interested in the models on system throughput, read/write rate, read/write pattern, read/write duration (interval), read/write latency, communication delay, failure pattern, and more professional ones such as data consistency, quorum size, recovery mechanism, and so on.

Therefore, I am requesting references, including but not limited to

statistical reports of commercial/open source distributed storage systems
hypothetical models used in research papers.
a typical example: costs and availability of replicated services
 which studies availability, consistency, partition.
experimental results given in research papers, talks, and technical reports.
typical examples: Dynamo in Amazon [section 6] and PNUTS in Yahoo! [section 5].
personal comments on such topics from blogs, non-research articles, and you.


texts: What is considered an asymptotic improvement for graph algorithms?

texts:
Lets say we are trying to solve some algorithmic problem $A$ that is dependent on input of size $n$.
We say algorithm $B$ that runs in time $T(n)$, is asymptotically better than algorithm $C$ which runs in time $G(n)$ if we have:
$G(n) = O(T(n))$, but $T(n)$ is not $O(G(n))$.
My question is related to the asymptotic running time of graph algorithms, which is usually dependent on $|V|$ and $|E|$.
Specifically I want to focus on Prim's algorithm. If we implement the priority queue with a binary heap the run-time would be $O(E\log V)$. With Fibonacci heap  we could get a run-time of $O(V\log V + E)$.
My question is do we say that $O(V\log V + E)$ is asymptotically better than $O(E\log V)$?
Let me clarify: I know that if the graph is dense the answer is yes. But if $E=O(V)$ both of the solutions are the same.
I am more interested in what is usually defined as an asymptotic improvement in the case we have more than one variable, and even worse - the variables are not independent ($V-1\le E<V^2$, since we assume the graph is connected for Prim's algorithm).
Thanks!


texts:
Just a quick question,

If i were to alter the general DFS algorithm to do this:

minDFS(Vertex v)
{
   if (!v.getVisted())
   {
       v.setVisited();
       Vertex temp = findClosestVertex();
       graph.addEdge(v, temp);
       minDFS(temp);
   }
}

Would I eventually (at the end of DFS) get  minimum spanning tree? I know there are other ways of getting the MST (Kruskal's, Prim's etc..),but I was just wondering if this would work.


texts: Minimum-cut with balanced and limited number of nodes in each partition: Does this have an efficient solution or even a name?

texts:
I'd like to remove the minimum number of edges from an undirected unweighted graph to partition the nodes into an arbitrary number of connected components $S_1$, $S_2$,$S_3$,... $S_k$ while maximizing the size (number of nodes) of the smallest partition and with a constraint limiting the size of every partition: $|S_i| \leq c$ for all $i$

Example input: $c=30$; Graph with 40 nodes that are fully connected and 20 nodes that each have one edge
Example output: 30 of the fully connected nodes are placed in $S_1$ and everything else (30 nodes) is placed in $S_2$.

This is similar to minimum k-cut, but I can't find a name for this problem with arbitrary k. I can't use a minimum k-cut solver because it would break up the 10 single-edged nodes into 10 sets before it starts breaking up the 40 fully connected nodes. Closest I could find was Most balanced minimum cuts, but that only deals with a single st-cut.

Approximate and probabilistic/randomized solutions are totally ok for my application if that's what it takes to get decent space/time complexity.

Backstory: I'm trying to solve a difficult problem with large graphs where I can only process a small number of nodes (say 30) at a time because the problem is otherwise intractable. If these partitions have many edges to the rest of the graph, the merged solution will be sub-optimal.

Comments discussing similar problems or providing background knowledge are also appreciated!


texts: Can Homotopy Type Theory be used to derive more efficient algorithms on more efficient data representations from less efficient ones?

texts:
I've read here that in HoTT, compilers could swap out less efficient representations of data for more efficient ones and I'm wondering whether my interpretation of that statement is correct.

Say we have two different ways of representing the natural numbers, unary (zero and successor) and binary. Here is a function that checks evenness on the former representation:

even : UnaryNat -> Bool
even zero = true
even (succ zero) = false
even (succ (succ n)) = even n

If we then have an isomorphism between the unary and binary representations, we trivially get an evenness function for the binary representation "for free", simply by converting a given binary natural number to a unary one, applying the even function, and converting the result back to the binary representation. Obviously, this is not very efficient, and we also don't need HoTT for this.

A better way to check whether a binary natural number is even would be to check if its least significant digit is a zero. My question is: Could we derive this more efficient algorithm for binary natural numbers from our definition of evenness for unary natural numbers using HoTT? If so, would this also be possible for other data types? I haven't studied any HoTT yet and since its appears to be a pretty complex subject I would like to find out whether it's as exciting as I think it is. Thanks!


texts: When are adjacency lists or matrices the better choice?

texts:
I was told that we would use a list if the graph is sparse and a matrix if the graph is dense. For me, it's just a raw definition. I don't see much beyond it. Can you clarify when would it be the natural choice to make?

Thanks in advance!


texts: Backpropagation on a matrix of functions

texts:
As nicely described in this article, backpropagation for multi-layer perceptrons defines the error term for a neuron in terms of the partial derivative of the weights.

It's traditional to represent the weights between neutrons in matrix form: $w_{ij}$ representing the weight between neuroma $i$ and $j$.
Since a weight can be considered as being as constant multiplier of any input, so a possible generalisation is instead to replace the $w_{ij}$ with some univariate function $f_{ij}$.

Since. a 3 layer MLP is already a universal approximator for continuous functions, this generalisation won't be more expressive, but the hypothesis is that it might converge faster for some problems.

My question then concerns the nature of the learning algorithm for this extended formulation:

How might it be possible to define backpropagation if the weight matrix is replaced by a matrix of functions? The functions can be assumed to be differentiable as required.


texts: Is there a well-known algorithm for arranging inputs according to their category?

texts:
Background:

(I’m a complete beginner in computer science in general, so I do apologise if my question is not formulated in a sensible way. E.g. I have avoided technicalities in formulating my problem, but perhaps this causes issues. I'm willing to edit accordingly if so).

I’m trying to get to grips with the way that algorithms are/can be used in economics. I think I understand the (very) basics of how sorting algorithms and clustering algorithms could apply to some problems, but there is a (seemingly) elementary problem which I can’t find a well-known algorithm for.

The problem:

Suppose my entire input consists of a set of different quantities of two types of good. For example, apples and oranges:

Input: { 1 apple, 1 orange, 10 apples, 10 oranges }

Is there a well-known algorithm which can arrange these inputs by type of good, such that the output is the following two sets?:

Set 1 (apples): { 1 apple, 10 apples }

Set 2 (oranges): { 1 orange, 10 oranges }

Clustering and sorting algorithms do not seem to be appropriate:

From my (very, very basic) knowledge of clustering algorithms, they would not be appropriate here, as clusters are meant to represent closeness of data points in space. But, if I were to plot these goods as data points, I would have a representation of their values, whereas I'm trying to group them via their categories.

I also don’t think that a comparison based sorting algorithm would work, as these algorithms produce an ordering (total preorder) of the values input. Whereas, again, I'm trying to group them via their categories.

Is my definition of algorithm the issue?

Perhaps I'm misunderstanding the type of thing that can be input into an algorithm? Cormen et al. (Introduction to Algorithms, 2009, §1.1) informally define an algorithm as

  ...any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.

So perhaps an algorithm can only take numerical values as an input and not numerical values attached to a category label (like 'apple', or 'orange')?

I’d be very grateful for any help :)


texts:
Let $\mathcal{F} = \{ f_{s} \}_{s \in \{\, 0,1 \,\}^{*}}$ be a family of computable functions, where $f_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$.

We define a family of functions $\mathcal{H} = \{ h_{s} \}_{s \in \{\, 0,1 \,\}^{*}}$, where $h_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$ and $h_{s}\left( \cdot \right) = f_{s}\left( f_{s} \left( \cdot \right) \right)$.

Let $F_{n}$ ($H_{n}$) be the distribution of functions $f_{s}$ ($h_{s}$), where $s$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$. And let $R_{n}$ denote the uniform distribution over the set of all functions from $\{\, 0,1 \,\}^{n}$ to $\{\, 0,1 \,\}^{n}$.

We know that for any PPT adversary $A$, if for all $n$,
$$\left\vert \Pr\left[ A^{F_{n}}\left( 1^n \right) = 1 \right] - \Pr\left[ A^{R_{n}}\left( 1^n \right) = 1 \right] \right\vert \leq \epsilon (n)$$
then $\mathcal{F}$ is a family of PRFs. And if $\mathcal{F}$ is a family of PRFs, then $\mathcal{H}$ is also a family of PRFs.

How about $A$ can only can query the oracle of a function sampled only one time? In other words, if
$$\left\vert \Pr\left[ A\left( F_{n} \right) = 1 \right] - \Pr\left[ A\left( R_{n} \right) = 1 \right] \right\vert \leq \epsilon (n)$$
holds true, can we get that
$$\left\vert \Pr\left[ A^{F_{n}}\left( 1^n \right) = 1 \right] - \Pr\left[ A^{R_{n}}\left( 1^n \right) = 1 \right] \right\vert \leq \epsilon (n)$$

PS: The title may not clear enough, but I don't know how to make it better :(. Thanks for anyone helping me to make it better :).