texts: What is the intuition on why the longest path problem does not have optimal substructure?

texts:
I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think the statement needs to be corrected to longest simple paths on general graphs is not solvable by dynamic programming).

If we assume they have to be simple (for some reason this is required which I don't appreciate yet) and longest, then its easy to create a counter example. Consider the square graph with 4 nodes A→B→C→D→A.

A longest path from A to D is clearly A→B→C-D. But the longest path from B to C is not part of the longest path to from A to D because the longest path from B to C is B→A→D→C which is clearly not the same as the path B→C (which in this case is in fact a shortest path!).

This seems to work only because we required the paths to be simple. Is it necessary to assume that the paths must be simple for us to prove that optimal substructure is not present?

I think that the counter example should be good evidence/proof (which I don't deny), I just don't find the counter example very enlightening at all. I see why it proves the point that it doesn't allow optimal substructure but it fails to provide me real understanding or intuition why it should be obvious that there should be no longest path optimal substructure. Like for example, why doesn't a cut and paste argument work? If the subpath isn't longest, then just stick in a longer path! It sounds very tempting, I mean, if we put in place something longer then of course it should get longer...though, this is for some reason wrong. Does the example actually in fact prove that DP can never solve longest (simple?) paths efficiently? I don't require for a general proof that its not in P (since thats might be asking for a P vs NP solution). I am just after a proof that its not solvable by DP (or at least very strong evidence that DP can never solve this longest paths problem or that the problem does not have optimal substructure).

I have definitively seen in wikipedia that the problem should be NP-Hard, which means that there is probably no fast algorithm. Not sure if that is the only type of evidence/intuition that exists to provide that optimal substructure should be obviously lacking (or if its not lacking, that it can't be used to make the problem faster). Is that the only way to show that it should not be solvable by a fast dynamic program?

Is the reason we require simple just because if we don't place that requirement the problem becomes trivial/uninteresting? In other words, if there is any cycle then one has solved the longest path problem to all nodes reachable from that cycle (by finding any path to that cycle). For the nodes that don't have any cycle reachable, we have a acyclic graph, which is solvable by DP (if the weights are positive?). In addition if there are cycles, we have automatically made things have optimal substructure (I think) because any longest path just is made up of longest path which covers two cases, 1 the paths through the cycle or 2 the paths through the DAG, which both contain optimal substructure. So the problem has become trivial without the requirement of simple paths? Or am I missing something or are there better explanations to why simple paths are required? Doesn't the algorithm in this paragraph show that general longest paths are solvable by DP?

I am also not 100% sure what requirements are needed to guarantee that DP can't be used. Is it necessary to negative edge weights, positive, un-weighted, directed, undirected...what are the requirements?


texts: Difference between computational complexity theory and complexity theory

texts: I read that complexity theory is the study of complex systems. While I associate computational complexity theory with classification of problems.


texts:
It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete.

It is also suspected (somewhat less widely) that even deciding SAT should take time $2^{n-o(n)}$ according to the strong exponential time hypothesis.

I was wondering if there are any hardness results for APPROXIMATE #SAT, namely counting the number of satisfying assignments up to additive errors?  In particular, are there any explicit lower bounds?

Thanks!


texts:
I have a circuit that is represented as a netlist (specifically, an and-inverter graph).  The desired outputs of this circuit are known.  We can assume that some combination of the primary inputs will result in the desired outputs.  If it makes it easier, you can assume that there's only one combination of inputs that will give me the desired output.  How do I find those inputs?

Each output for the netlist can be represented as a combinatorial boolean equation, so I was tempted to convert each output, triangularise, and solve to obtain the suitable primary inputs.  However, converting the netlist to equation-form (i.e. a similar operation to unfolding it) incurs a prohibitive space cost.  Is there a way to "triangularise" the circuit so that I can find suitable primary inputs?  Or, alternatively, can anyone recommend a way to achieve the goal of finding suitable primary inputs?


texts:
I am implementing the multiphase level Chan Vese algorithm. I am using IPOL document as reference (http://www.ipol.im/pub/art/2012/g-cv/article.pdf)

Everything is clear for me, except the stopping criteria: In one level set, the method is terminated by calculating the difference between phi(n+1) and phi(n), and stop if below some threshold. My problem is how to represent this stopping condition when I have phi1 and phi2? Also, how I represent the new segmented image? In one level set, I used phi and manipulate it to zero or one values. But, now how I should represent the new segmented image?

Thank you


texts: Detailed explanation of Perlin Noise algorithmic complexity

texts: I am doing a project in analysis of algorithm and I have been looking all over for something more complex than Perlin Noise is $O(n \cdot 2^n)$ because of the doubling in $n$ dimensions and array operations. Anyone know where there is more information? I have another month before our group gives the presentation.


texts: Define a grammar to emmulate chess rules

texts:
Is it possible to define a 《chess language》:
language={alphabet = {(chess pieces, squares of chess board)}, grammar={rules of movement of pieces over the board}}?

I looked online but I cannot find a way to define the grammar. Every way I can think of, is either stupidly long and complicated, or does not cover all the rules.

I presume the hard part is that the grammar has to take in consideration the state of the board before evaluating a move as valid or not.

Do you have insight how to approach this problem i.e: define a grammar that emulates chess rules?

The way chess apps work(not engines), is that at every move they calculate all possible moves and then check if the user's move is among the calculated moves, else it is invalid.

I want to accept the user's move and only then check if it's a valid one.


texts: How to work out physical address corresponding to logical address?

texts:
I am looking to calculate the physical address corresponding to a logical address in a paging memory management scheme. I just want to make sure I am getting the calculation right, as I fear I could be wrong somewhere.

So, the data I have is as follows:

The logical address: $717$
Logical memory size: $1024$ bytes ($4$ pages)
Page Table:

\begin{array}{| c | c |}
\hline
Page\ Number & Frame\ Number\\ \hline
0 & 5\\ \hline
1 & 2\\ \hline
2 & 7\\ \hline
3 & 0\\ \hline
\end{array}

Physical memory: $16$ frames

So, with $1024$ bytes in the logical memory, and $4$ pages, then each page is $256$ bytes.

Therefore, the size of the physical memory must be $4096$, right? ($256 \times 16$).

Then, to calculate the logical address offset:

$$1024 \mod 717 = 307$$

Is that how we calculate the offset?

And, we can assume that $717$ is in page $2$ ($\frac{1024}{717} = 2.8$)?

So, according to the page table, the corresponding frame number is $3$.

And so to get the physical address, we multiply the frame number and page size?

$$2 \times 256 = 768$$

Then, do we add the offset, like so:

$$768 + 307 = 1,075$$

Thank you for taking the time to read. If I don't quite have this correct, would you be able to advise on the correct protocol to calculating this?


texts:
this MIT course gives a formula about Big O

$$n^{0.999999} \log n = O(n^{0.999999} \cdot n^{0.000001})$$

going through wiki, i cannot find a similar Big O properties or usages.

how to compute $O(n^{0.000001})$ to get a quantity like $\log n$ ?


texts: What are some comparative studies on program termination verification tools?

texts: Comparative studies of tools like AProver, 2LS


texts: Compute unknown matrices that minimize a sum

texts:
This problem is about working with smart-phone accelerometers.

To calibrate accelerometer, I need to find three unknown matrices T, K and B that minimize this sum:
$$\sum_{i=0}^N(|g|^2 - |TK(a_i + B)|^2)^2,$$
where $a_i$ is a known 3x1 vector and |$g$| is a known constant and unknown matrices are:
$$T = \begin{bmatrix} 1 & t_1 & t_2 \\ 0 & 1 & t_3 \\ 0 & 0 & 1\end{bmatrix},\ K=\begin{bmatrix} k_1 & 0 & 0 \\ 0 & k_2 & 0 \\ 0 & 0 & k_3\end{bmatrix},\ B=\begin{bmatrix} b_1 \\ b_2 \\ b_3\end{bmatrix}.$$

I have read in an article one can solve such problems by Levenberg-Marquardt
(LM) algorithm. Unfortunately I cannot figure out how. Can anyone suggest a solution to this minimization problem? And I need to implement the algorithm in python so if you know any good python library please  name it.


texts:
Given the following multiplication table how could one construct an NFA such that it accepts all strings that have a certain product (say a) ?

The string "abcb" would be evaluated as (a(b(cb))) = a

\begin{array}{c|ccc}
    \times & a & b & c \\
    \hline
    a & a & a & c \\
    b & c & a & b \\
    c & b & c &a
   \end{array}

I tried to take the transpose of the above matrix:

\begin{array}{c|ccc}
    \times & a & b & c \\
    \hline
    a & a & c & b \\
    b & a & a & c \\
    c & c & b & a
   \end{array}

And build an NFA for that. I then reversed all the transitions, but I don't think that works.


texts: Adapting Dijkstra to list all shortest paths

texts:
I found a code in the internet for Dijkstra's shortest path algorithm in PHP. The problem is it only shows one possible path. If there are several paths having the same distance, it only outputs one of them.

  How can I modify this algorithm to produce all shortest paths?

//set the distance array
$_distArr = array();
$_distArr[1][2] = 7;
$_distArr[1][3] = 9;
$_distArr[1][6] = 14;
$_distArr[2][1] = 7;
$_distArr[2][3] = 10;
$_distArr[2][4] = 15;
$_distArr[3][1] = 9;
$_distArr[3][2] = 10;
$_distArr[3][4] = 11;
$_distArr[3][6] = 2;
$_distArr[4][2] = 15;
$_distArr[4][3] = 11;
$_distArr[4][5] = 6;
$_distArr[5][4] = 6;
$_distArr[5][6] = 9;
$_distArr[6][1] = 14;
$_distArr[6][3] = 2;
$_distArr[6][5] = 9;

//the start and the end
$a = 1;
$b = 6;

//initialize the array for storing
$S = array();//the nearest path with its parent and weight
$Q = array();//the left nodes without the nearest path
foreach(array_keys($_distArr) as $val) $Q[$val] = 99999;
$Q[$a] = 0;

//start calculating
while(!empty($Q)){
    $min = array_search(min($Q), $Q);//the most min weight
    if($min == $b) break;
    foreach($_distArr[$min] as $key=>$val) if(!empty($Q[$key]) && $Q[$min] + $val < $Q[$key]) {
        $Q[$key] = $Q[$min] + $val;
        $S[$key] = array($min, $Q[$key]);
    }
    unset($Q[$min]);
}

//list the path
$path = array();
$pos = $b;
while($pos != $a){
    $path[] = $pos;
    $pos = $S[$pos][0];
}
$path[] = $a;
$path = array_reverse($path);

//print result

echo "From $a  to  $b";
echo "The length is ".$S[$b][1];
echo "Path is ".implode('->', $path);

?>


texts: Problem in understanding big-O notation and similiar

texts:
I am trying to understand the concept of big-O notation problem and came through this problem. Can you tell me how could

$$O(n) = 1 + \Theta(1/n)$$


texts: Number of ways to fill a 2xN grid with M colors

texts:
This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri.
In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two cells with the same row or same column have the same color.

The limits given are $1 \leq N$, and $M \leq 1000$ with 1000 test cases per input.

Based on the constraints the approach that comes to my mind after a long struggle includes having a precomputed DP table which can be used for every test case. I tried to apply the inclusion-exclusion principle but could not come up with any solution. I also tried to solve it using bipartite perfect matchings, but no success. How should I approach this question?


texts: Does the Kleene star distribute over each element? (0+1)* = 0* + 1*?

texts: Does the Kleene star distribute over each element? Is this true: $(0+1)^* = (0^* + 1^*)$?


texts: Proving program termination in the $\lambda$-calculus

texts:
Turing's Checking a large routine:

Finally the checker has to verify that the process comes to an end.
Here again he should be assisted by the programmer giving a further
definite assertion to be verified. This may take the form of a
quantity which is asserted to decrease continually and vanish when the
machine stops. To the pure mathematician it is natural to give an
ordinal number.

How do you apply this to a program written in the untyped $\lambda$-calculus?


texts: The name of "finding the path of a graph that is a variant of hamiltonian path"

texts:
Suppose that there is some graph, with $n$ vertexes. We wish to find the hamiltonian path, but we make the graph being searched a little different. There is a person A that travels each (undirected) edge that connects one vertex to the other vertex. But after the person crosses the edge, how edges connect pairs of vertexes change. (So, for example, before one crossed(traveled) one edge, there was an edge that connects vertex A to vertex B, but after some edge is crossed, there may no longer be the edge that connects vertex A to vertex B.) How the graph changes depends only on the order of the path being crossed - so, if he is on the third vertex in the path he chose, regardless of what path is, how the graph changes only depend on the fact that it is third vertex. Every change is known and inserted as input. Then we compute hamiltonian path.

We can replace human with machine.

So, what would be the name of finding hampath in such graph? And what complexity class would this be in?

I tried to search this in my complexity textbook, but failed miserably - so I wonder if this even has a name.


texts: maximal independent set on grid-based graph proof of approximation ratio

texts:
We have a G = (V, E, w), in form of a grid graph with a single diagonal line in each grid in form of below. Where w is the V weight.

We use a greedy algorithm that takes in each step maximum weighted vertex and adds it to the set and removes all the adjacent vertices to the vertex.
I want to prove that algorithm is 6-approximation.
Let $W^*$ be optimal solution $O$, and $W$ be greedy solution $S$.
We build a mapping for each $u \in O$ and we define $u'=u$ if $u\in S$ else $u'=$ $"u$ neighbor" in $S$, that means at some iteration in greedy algorithm the $u$ was excluded and the $u$ neighbour $w(u) \leqslant w(u')$ was chosen.
$W^* = \displaystyle\sum_{u \in O} w(u) \leqslant \displaystyle\sum_{u' \in S} w(u') $.
Afterwards I'm bit confused how to prove that it's 6-approximation, as in each step when we select vertex from S, we remove only at most 3 vertices from O, based on the graph. I understand that it's 1/6 because of the number of neighbours of vertex, but I'm bit confused about that choosing non-optimal vertex can remove up to 3 vertices only.


texts: Is Weighted Averages the Best Method to Aggregate Information?

texts:
I'm working on a recommendation system. My system uses user's past rating data, to predict future ratings.

I designed mathematical methods for generating recommendation algorithms that allows me to generate an unlimited number of recommendation algorithms (given a large enough set of relevant ratings).

I intend to aggregate the results from all this algorithms to compute a final expected rating of the user. So I thought of taking the weighted averages of the expected ratings of each algorithm to use to calculate a final expected rating.

Basically I either:
1. Assign weights based on the amount of information (ratings collected).
2. Assign weights based on the accuracy of the algorithm used.

The algorithms arrive at their answer via different means, and it is possible that two may give the same answer, but they may take into account different information and/or use different inferential techniques on that information.

So if an accuracy of 1 means there's no deviation between the algorithm's expected ratings, and the user's actual ratings, and an accuracy of 0 means there's maximum deviation between an algorithm's expected ratings and user's actual ratings, we may get $\{Al_1, Al_2, Al_3\}$ with accuracies of $(0.9, 0.85, 0.92)$.

I have a minimum information and/or accuracy threshold that I would use to filter the algorithms to assign weights to (I have not yet figured out what this threshold would be, and as it may vary on a per user basis, I want to leave determining the threshold to an ML system.

My question is this:

  Is weighted averages the Best methods for me to aggregate the data provided by my various algorithms/infer from it?
  If not, what other methods are more apt for the problem at hand?


texts:
I'm trying to prove that for arbitrary $c > 0$,

$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$

Intuitively, this seems to be true to me (little-o implies some gap "between" $f(n)$ and $n^c$ that we can formally express as $\epsilon$). However, I'm having some trouble formalising this argument.

What I've done so far:

$f(n) = o(n^c) \rightarrow \exists c_0, n_0 > 0 \ s.t. \forall n \geq n_0, 0 \leq f(n) < c_0 n^c$

Suppose (for a contradiction) that no such $\epsilon$ fulfilling the above condition exists.

Then we have

$\forall \epsilon > 0, \exists n \geq n_0 \ s.t. f(n) \geq c_0 n^{c-\epsilon}$

I'm not sure how to proceed from here.


texts: how to prove that log(n!) >= c n log(n) for some c >0?

texts:
as reading the book Algorithms by Dasgupta, C.H Papadimitriou.  on Page 63.

  And it is well known that $\log(n!)≥c\cdot n\cdot\log n$ for some $c > 0$. There are many ways to see this. The easiest is to notice that $n! \ge (n/2)^{(n/2)}$ because $n! = 1 · 2\cdot\cdots\cdot n$ contains at least $n/2$ factors larger than $n/2$; and to then take logs of both sides. Another is to recall Stirling’s formula.

Can someone help to find the proof on $n! \ge (n/2)^{(n/2)}$, or how should we prove it ourselves? As we take log on both side, it became
(assuming that its base is some number constant)  $\log(n!)$ on the left side,  on the right, it became $\log\left((n/2)^{(n/2)}\right)$, further simplify $(n/2)\log(n/2)$ --> $(n/2)\log(n^{-2})$, then finally on the right side: $(-n)\log(n)$. Then we completed the proof (?)

I have two questions, is the proof of $n! \ge (n/2)^{(n/2)}$ corrected?
If so, how can we argue back to   "$\log(n!)≥c\cdot n\cdot\log n$ for some $c > 0$",  if not, how can we proof that "$\log(n!)≥c\cdot n\cdot\log n$ for some $c > 0$"?


texts: Polynomial Time Complexity: O(loglog n) = O(n^2)?

texts:
Is O(loglog n) equal to O(n^2) in polynomial time?

I know O(log n) is eqaul to O(n) in polynomial time because this can change as follows:
log n > 2^(log n) > n^(log 2) > n.
So, my question is to determine whether O(loglog n) = O(n^2) or not.
Thank you for your time.


texts: Datastructure for managing (abstract) sets

texts:
I am looking for a datastructure to represent the complex relationships between a bunch of abstract sets. The "abstract" means that these sets are not defined by their elements, but by their relationship to each other. This means that for me a set is nothing more than a named thing with a relations to other named things in the same space. For two sets $A,B$ the relation can be

they represent the same set, i.e. $A=B$,
they are complementary, i.e. $\bar A=B$,
they are disjoint $A\cap B=\varnothing$ but not complementary,
they are overlapping, i.e. they are not equivalent but have a non-empty intersection,
one is a proper subset of the other set, e.g. $A\subset B$
essentially unknown, but maybe some of the former cases can be excluded.

Besides storing these relationships, I want to ask questions on the datastructure like

Are the sets $A$ and $B$ disjoint?
Name me a subset of $A\cap\bar B\cap \bar C$.
What is the relation between the sets $X$ and $\bar Y\cap Z$?

Also the datastructure should be updatable. There will be inserted new sets all the time which must be integrated in the structure correctly. There can be lots of sets and it is no option to explicitely store the relation between any pair of sets. Instead, some relations should be deducable by the query algorithms. For example, if we have $A\subset B\subset C$, then we will not store $A\subset C$ as this follows logically from the other two relations.

I thought about lots of tree like structures or cycle-free directed graphs. But maybe someone already developed exactly what I am looking for.

One more thing: I would prefer when the datastructure does note introduce big differences between sets and their complement. This means, asking whether $A\cap B$ is empty should not invoke vastly different algorithms than asking this for $A\cap \bar B$.

Update

To answer some comments, here are some more details on my intend.

You can think about this as a big (hyper-)graph problem, where the whole graph is too big to be stored but has much structure, so maybe can be stored very efficiently in another way. The nodes of the graph are sets. The (hyper-)edges are relations between the sets. The edges are colored to represent the six possible relation types from above. In this sense, the graph is an edge-colored complete graph. Note that the edge type unknown is very important to me!

To describe the queries in general, let me introduce the following notation: given a set $A$, we write $A^+=A$ and $A^-=\bar A$. The following queries should be supported as efficient as possible:

Given a sequence of nodes $A_i$ and a sequence of signs $s_i\in\{+,-\}$. Which of the following three options is true for $\bigcap_i A_i^{s_i}$: it is empty, there is a node representing a subset of this intersection, we do not know anything.
Given two sequences $A_i$, $B_i$ of nodes and two sequences $s_i$ and $r_i$ of signs. What kind of edge is between $\bigcap_i A_i^{s_i}$ and $\bigcap_i B_i^{r_i}$?

The last query seems trivial for the graph stored with all its edges. But as I said, the graph is probably too big to be stored in this naive way.

Of course, I never stated that for sets $A_i$ and signs $s_i$ my data structure must contain the set $\bigcap_i A_i^{s_i}$, but information can be deduced in other ways. For example, assume $A$ and $B$ are sets, but $A\cap B$ is not stored. But we have a set $C\subset A,B$. So we know that $A\cap B$ $-$ despite being not stored explicitely $-$ is not empty. If we lack any of these information, then we may conclude that "we do not know anything about $A\cap B$". The fact that $A\cap B$ is empty is stored by an edge between $A$ and $B$ signalling that these sets are disjoint.

Why I wrote hyper-edge instead of just edge? It might be necessary to store that $A\cap B\cap C=\varnothing$ but no two of these sets are disjoint. This cannot be deduced from any two set relation. So we may need edges involving more than just two sets.


texts:
Suppose that we have  $ \\ T(n)=\left\{\begin{matrix}
c, & \ \text{if } n<d\\
aT\left( \frac{n}{b} \right )+f(n), & \ \ \text{if } n \geq d
\end{matrix}\right.$

The Master theorem is the following:

If $f(n)=O(n^{\log_b a- \epsilon})$, then $T(n)= \Theta(n^{\log_ba})$
If $f(n)= \Theta(n^{\log_b a} \log^k n)$, then $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$
If $f(n)=\Omega(n^{\log_b a+ \epsilon})$, then $T(n)= \Theta(f(n))$, provides $af\left(\frac{n}{b} \right) \leq \delta f(n)$ for some $\delta<1$ for all $n \geq d$.

Proof:

Using iterative substitution, let us see if we can find a pattern:

$$T(n)=aT\left( \frac{n}{b}\right)+f(n)=a \left(aT \left(\frac{n}{b^2} \right) +f\left( \frac{n}{b}\right)\right)+f(n)= \dots\\= a^{\log_bn}T(1)+ \sum_{i=0}^{(\log_bn)-1} a^i f\left( \frac{n}{b^i} \right)=n^{\log_b a} T(1)+ \sum_{i=0}^{(\log_b n)-1} a^i f\left(\frac{n}{b^i} \right)$$

We then distinguish the three cases as

The first term is dominant
Each part of the summation is equally dominant
The summation is a geometric series

Don't we have to explain further which case correponds to which of the following cases

The first term is dominant.
Each part of the summation is equally dominant.
The summation is a geometric series

and justify why it is like that? How could we justify it?


texts: Meaning of $\stackrel{*}{\rightarrow}$ production rule?

texts:
I've seen the production rule $\stackrel{*}{\rightarrow}$ in some papers concerning regular languages.

What's the meaning of $\stackrel{*}{\rightarrow}$ production rule?


texts:
Wiki (http://en.wikipedia.org/wiki/Sharp-P) says 'In computational complexity theory, the complexity class #P (pronounced "number P" or, sometimes "sharp P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP'.

Is there a counting version for CoNP problems?


texts:
Can anyone suggest an algorithm faster than $\Theta(n^{2})$ for computing the following function:

$$||n||:=\frac{1}{\max\{k \in \mathbb{N}: 1|n, 2|n,\ldots,k|n\}}$$


texts: Size of the language accepted by a Turing Machine

texts:
I want to figure out if the following language is Turing decidable, Turing acceptable but not turing decidable, or neither. The language is

{ρ(M) : |L(M)| ≤ 10}

My question for this problem is what does |L(M)| ≤ 10 mean? At first, I thought it meant that the language will only accept strings that are less than or equal to 10 in length, but I am not sure


texts:
This seems like a silly question, but I couldn't find a conclusive answer for it.

As far as I know, ZPP contains algorithms which run in polynomial time and either return a known-correct answer or abort (this definition is equal to the one where they either return a correct answer or run in exponential time). It is also possible to get the failure probability of a ZPP algorithm  arbitrarily low (but $>0$) by rerunning it often enough without using exponential time.

BPP contains algorithms which will always return an answer in polynomial time, but this answer may be wrong with at max a $\frac{1}{3}$ chance.

Therefore, given a solver for ZPP problems, I can create a function which either solves my problem or abort in $\frac{1}{3}$ of the cases, while running in polynomial time$^1$.

Given this function, I can solve any problem contained in BPP by running the function created above on it and return a random response if it aborts. Since this will be in less than $\frac{1}{3}$ of the cases, the probability for a wrong answer will be less than  $\frac{1}{3}$ and it will always run in polynomial time.

This would imply that BPP is contained in ZPP, but it seems that it is actually the other way around. So where am I wrong?

$^1$ This might be my error, but it's described like this in our lecturer slides (which are not public). I couldn't find a direct citation for it, but Complexity Zoo states for RP: "implicitly: the class VPP that is defined is equivalent to RP by running the recognizer as many times as necessary to reach probability 1/2?", so I assume this can be applied to ZPP as well and my understanding is correct.
EDIT: Also, in case this doesn't hold true, at least ZPP($\frac{1}{3}$) should be equal to BPP, which I couldn't find anywhere either.


texts: Proof of shortest-paths optimality conditions

texts:
I am struggling with understanding the proof of shortest-paths optimality conditions.

Let $G$ be an edge-weighted digraph.
Then values in $distTo[]$ are the shortest path distances from $s$ iff:

For each vertex $v$, $distTo[v]$ is the length of some path from $s$ to $v$.
For each edge $e = v \rightarrow w$, $distTo[w] \le distTo[v] + e.weight()$.

Proof.

[$\Leftarrow$]necessary

Suppose that $distTo[w] > distTo[v] + e.weight()$ for some edge $e = v \rightarrow w$.
Then, $e$ gives a path from $s$ to $w$ (through $v$) of length less than $distTo[w]$.

[$\Rightarrow$]sufficient

Suppose that $s = v_{0}\rightarrow v_{1}\rightarrow v_{2}\rightarrow\cdots\rightarrow v_{k} = w$ is a shortest path from $s$ to $w$.

Then,
$$\begin{array}{rl}
distTo[v_{1}] &\le& distTo[v_{0}] + e_{1}.weight()\\
distTo[v_{2}] &\le& distTo[v_{1}] + e_{2}.weight()\\
&\vdots&\\
distTo[v_{k}] &\le& distTo[v_{k-1}] + e_{k}.weight()
\end{array}$$
($e_{i}: i^{th}$ edge on shortest path from $s$ to $w$)

Add inequalities, simplify, and substitute $distTo[v_{0}] = distTo[s] = 0:$
$$distTo[w] = distTo[v_{k}] \le e_{1}.weight() + e_{2}.weight() +\cdots + e_{k}.weight()$$
($e_{1}.weight() + e_{2}.weight() +\cdots + e_{k}.weight()$ is weight of shortest path from $s$ to $w$)

Thus, $distTo[w]$ is the weight of shortest path to $w$

QED

I do not understand "sufficient" part, especially,

$$\begin{array}{rl}
distTo[v_{1}] &\le& distTo[v_{0}] + e_{1}.weight()\\
distTo[v_{2}] &\le& distTo[v_{1}] + e_{2}.weight()\\
&\vdots&\\
distTo[v_{k}] &\le& distTo[v_{k-1}] + e_{k}.weight()
\end{array}$$

I thought each $distTo$ element should be equal to the left-hand side since each $e$ is the weight of the edge of the shortest path.

And for the last sentence of page 22,
"Thus, $distTo[w]$ is the weight of shortest path to $w$.", isn't this obvious because we know that $distTo[]$ are the shortest path distances from $s$? I even don't understand why this sentence is the conclusion for the proof.

I am really confused so I am glad if anyone can help me understand this process.


texts: Is the set of surjective recursive functions in RE/coRE?

texts:
Let L be a set of recursive funtions with $L = \{i\in \mathbb{N}|f_i\space is\space surjective\}$ where $i$ is a gödel number of f.Is $L\in RE,\space coRE$?

I can't think of a way to show either of the two.


texts:
I have a stream of 3-tuples of type (x,y,t) where x and y are in the range 0-127 and t is time, therefore monotonic increasing.

I want to be able to quickly search for points around a query point and think that constructing a kd-tree from the data is a good way to achieve that.

Now I can hardly construct a kd-tree by inserting each new point as, due to the monotonic increasing t, it will inadvertently become unbalanced.

Is there a way to create a "running" kd-tree, that is inserting elements on the one t-side, while dropping elements on the other t-side without the tree becoming unbalanced?


texts:
I am reading about a specific field of probabilistic programming, and trying to understand what the term "stateful computation" means.

See: http://projects.csail.mit.edu/church/wiki/Simple_Generative_Models

(search for "XRP")


texts: "Minimum" maximum flow with extra capacities

texts:
Problem:

Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, find a total extra capacity needed E so that maximum flow from source to sink is greater than or equal to F and flow in each edge that has nonzero flow.

I don't know how to solve this variation of maximum flow problem. It is obvious that if maximum flow I find without extra capacities is greater than or equal to F, then there is no need for extra capacity. If it is less than F, should I add extra capacity in each edge one by one and find max flow again till I find the closest one to F (if it is not enough, then take in pairs, triplets, etc.)? This solution seems inefficient to me.

EDIT:

Example:

Suppose source is node 0 and sink is node 5. Sink requires flow of 6 (F = 6). For the following format

(1st node, 2nd node), current capacity, extra capacity that can be added

we have following edges

0 1 3 0
0 3 3 0
1 2 3 0
1 3 2 0
2 4 4 0
2 5 2 2
3 4 2 1
4 5 3 1

Maximum flow from current capacities is 5 which is not enough for the sink (5 < F). The extra capacity from 3 to 4 and 4 to 5 is required. So total extra capacity is 2 (E = 2) and the flows are

0 1 3
0 3 3
1 2 3
2 4 1
2 5 2
3 4 3
4 5 4


texts:
This is a book question:

  Suppose that a machine has 48-bit virtual addresses and 32-bit
  physical addresses.

  Suppose this same system has a TLB (Translation Lookaside Buffer) with
  32 entries. Furthermore, suppose that a program contains instructions
  that fit into one page and it sequentially reads long integer elements
  from an array that spans thousands of pages. How effective will the
  TLB be for this case?

Answer: I think that we cannot know the effectiveness of the TLB because we do not know the number of instructions the program has. I hope I make sense.

source:
Modern Operating Systems
Question 15, chapter 3
ISBN-13: 978-0-13-359162-0


texts: Why do we use the CYK algorithm? In my book is written that with CYK algorithm you can faster see if a word is generated by a given Grammer. However I dont get it, because I need like 5 min in order to divide the word into other subwords.. and so on and only few seconds just to derive the word using the predicates.


texts: Finding the optimal point among several weighted points in linear time

texts:
I'm trying to find the best position in a set of points where each point p has a weight w. I need to take into account the distance between each point and the weight of the points, the point with the lowest weight to distance value is the solution. (A more detailed description can be found a bit further down the page.)

I've thought about implementing some sort of a graph algorithm to solve this but there are not many graph algorithms that run in linear time, I really don't understand how I'm supposed to solve it with that time complexity. Could anyone please give me a hint on what sort of an algorithm I should implement here?

Problem

  Superman can see through objects made of different materials using
  x-ray vision. However, the amount of energy he requires varies
  according to the opacity of the material, e.g., steel requires more
  energy than wood. In addition, the farther away, the more energy he
  must use.

  Along a straight coastline, n bunkers made of different materials have
  been built. Each bunker is placed at the one-dimensional coordinate
  position p2, p1,...,pn, with pi < pi + 1, along the coastline so you
  can assume that the bunkers are given in the order they appear along
  the coastline. Assume further that you have wi, 1 <= i <= n, the
  amount of energy ( a non-zero, positive value) superman needs to see
  into the i’th bunker if he stands next to it.

  Find an algorithm that computes the point s along the coastline for
  which superman can exert the minimum amount of energy to see into all
  the bunkers, i.e., s is the position for which

  max{ | s - pi | + wi }

  1<=i<=n

  is minimized. Your algorithm should take linear time.


texts: Is there no sorting algorithm with all specific desired properties?

texts:
On the Sorting Algorithms website, the following claim is made:

  The ideal sorting algorithm would have the following properties:

  Stable: Equal keys aren't reordered.
  Operates in place, requiring $O(1)$ extra space.
  Worst-case $O(n\cdot\lg(n))$ key comparisons.
  Worst-case $O(n)$ swaps.
  Adaptive: Speeds up to $O(n)$ when data is nearly sorted or when there are few unique keys.

  There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.

My question is, is it true that

  there is no [sorting] algorithm that has all of these properties

and if so, why? What is it about these properties that makes all of them simultaneously impossible to fulfill?


texts: Probability of a double cycle in cuckoo graph

texts:
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got stuck with a problem.

We have $m$ elements and $n$ buckets. Each element is hashed into two random buckets (we assume that two our hash functions are completely random).
If each bucket corresponds to a vertex and each element corresponds to an
edge. Then we have a random graph with $n$ vertices and $m$ edges.
Loops and multi-edges are allowed.

I don't understand how to get the probability to reconstruct the whole cuckoo hash table. We reconstruct (reinsert all elements with new hash functions) a cuckoo hash table when a connected component
has a double cycle. We can calculate probability that after inserting
an element a double cycle occurs. This probability is $\mathcal{O}(1/n^2)$.
To prove this, we consider the situation when the last inserted element creates a double cycle on exactly $k$ elements. Then before the insertion
there were $k$ edges among these $k$ vertices. There are ${n}\choose{k}$
ways of choosing these vertices, and ${m}\choose{k}$ ways of choosing the items that correspond to the edges. Then the authors write the following
sentence which I don't understand but I think it's kind of crucial:

  After adding the new edge for the inserted item, the k + 1 edges must
  form a spanning tree, as well as two additional edges.

Don't $k + 1$ edges suppose to form double cycle not a spanning tree?
Wasn't the spanning tree formed even before the insertion since we had $k$ vertices and $k$ edges among them?
Also I don't understand why two additional edges must form a spanning tree and how is this fact connected to what we want to prove at all?

Next, the authors write the formula for probability we want to calculate:

${n}\choose{k}$ ${m}\choose{k}$ $k^{k - 2}$ ${k + 1}\choose{2}$ $(k - 1)! \cdot \dots$.

This formula isn't complete but my question about this part. Here $k^{k - 2}$ -- the number of trees on $k$ vertices,
$(k-1)!$ -- the number of ways to map $k-1$ elements into $k-1$ edges.
I don't understand the term ${k + 1}\choose{2}$. Why do we choose $2$ edges from $k + 1$? Shouldn't we choose only one edge from $k$ edges? My point is that $k - 1$ edges form a spanning tree on $k$ vertices and one remaining edge as well as the edge that corresponds to the new item should form two cycles. Then we can choose the remaining edge in $k$ ways. I think the formula should be:

${n}\choose{k}$ ${m}\choose{k}$ $k^{k - 2}$ $k$ $(k - 1)! \cdot \dots$.

Could you please explain me the details. May be I don't understand something?

Thank you!


texts: Can an algorithm that yields $O(n^2)$ answers run in $O(n)$ time?

texts:
My question may actually be more broadly described as: can I use the fact that an algorithm is expected to return $(O(f(n))$ answers to show that it may never run better than $O(f(n))$? I would intuitively assume yes, but I am not sure.

Examples of what I'm talking about is algorithms to calculate all the paths that pass through a set of points. I can easily calculate a higher bound $O(f(n))$ on how many those paths are. Will that tell me the algorithm must be no better than $\Omega(f(n))$?

Thanks


texts: Why can't we compile 8086 Assembily for all OSs from any OS?

texts: If Mac OS, Linux, and Windows (mostly) all use Intel's 8086 64 bit instruction set, why can't we compile 8086 64 assembly from any operating system to any other operating system? (e.g. compile a Mac OS executable from assembly in Windows). Surely it would just be a matter of knowing what the machine code is for any given instruction?


texts: It is possible to write any program (i.e. Turing complete) with just one single expression?

texts:
So I'm currently taking discrete math II at my university and I came across a somewhat philosophical question (so I apologize if this is question is hard to answer precisely) of whether mathematicians and computer scientists view computation in the same way.

We computer scientists define computation with the Turing machine and/or lambda calculus. I was simply wondering if there is some language/notation (lambda calculus??) that allows a mathematician to write a computable (i.e. Turing computable) program using only one mathematical expression.

Again, I apologize if that's a bit of an abstract question (I'm new to these concepts and my terminology isn't great) but let me try to clarify: in math (or at least when I did math in school), there isn't the notion of control flow over time with different statements--there is only a single expression that evaluates to a value. Evaluating the expression may involve partially evaluating nested expressions in a certain order but the end result and the expression itself represented computation in some sort.

So now my question is this:

(Through the use of lambda calculus) is it possible to write any program (i.e. Turing complete) using only one expression with no more than one statement? Is lambda calculus set up in a way that removes or hides the notion of control flow?


texts:
Let $G=(V,E)$ be a directed graph, $ω:E→\mathbb{R}$ a weight function, and $s,t\in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Each edge has the color R or G or B. Find the shortest path under the condition:

we can use green edge after using at least one red edge
we can use blue edge after using at least one red edge and at least one green edge.

The shortest path do not have to be colorful.


texts: Polynomial time algorithm to find an induced cycle in non-chordal graph

texts: Let $G=(V,E),n=|V|,m=|E|$ be a graph. There exists an algorithm with time complexity $O(n+m)$ to test if given graph $G$ is chordal. If I know the graph is NOT chordal, is there a algorithm to find any of the cycles without a chord of length $k\geq 4$ (running in polynomial time of course)?


texts: Efficiency/Redundancy in Chomsky normal form

texts:
I have a context-free grammar with the following production rules, $S$ being the start symbol:

$$\begin{align*}
S &\to AB \\
A &\to a \\
B &\to a\end{align*}$$

Is this in Chomsky normal form?

My problem is I thought CNF is supposed to be an efficient way to write a grammar, yet the grammar is not efficient in the sense that we can clean its rules as follows:

$$\begin{align*}S &\to AA\\
A &\to a\end{align*}$$


texts:
Players #1 to #10 with hit probabilities $0.1,0.2,...,0.9,1$ (which are common knowledge) take part in a shooting game.

Rules of the game: Players from #1 to #10 take turns to fire at each other. After round one, survivors repeat the circle (still in the order of #1 to #10). The game lasts many rounds until only one player survives. Players are rational and each calculates to maximize his survival probability.

Question: What is each player's optimal choice of target in his turn, when all 10 players are alive? And what are their respective survival probabilities? (Technically, I'm looking for a pure strategy subgame perfect Nash equilibrium, where the players follow deterministic strategies. Barring the very unlikely circumstance of ties, in which firing at one or the other player yields the same survival probability for the shooter, such an equilibrium is unique.)

My problem is I don't know how to write a tractable program to solve it. Let's consider 4 players with probabilities $(p_1,p_2,p_3,p_4)$. In this case, my reasoning is that the problem is solved by the following equations:

$s_{i1}^4 = p_1*$(i's survival probability after 1 hits his target) $＋ (1-p_1) * s_{i2}^4$

$s_{i2}^4 = p_2*$(i's survival probability after 2 hits his target) $＋ (1-p_2) * s_{i3}^4$

$s_{i3}^4 = p_3*$(i's survival probability after 3 hits his target) $＋ (1-p_3) * s_{i4}^4$

$s_{i4}^4 = p_4*$(i's survival probability after 4 hits his target) $＋ (1-p_4) * s_{i1}^4$

for $i=1,2,3,4$, where $s_{ij}^4$ denotes i's survival probability when it's j's turn to fire, with 4 player alive. Notice that after a play hits his target, there's only 3 players left. So if we already know the 3 players case, the above equations can be solved. But I have no idea how to define a suitable structure and sub-programs to implement these thought... or maybe this is not the best way to look at the problem?


texts: How can I check if $n >m$ in $a^n b a^m$?

texts: How can I design a Turing machine that takes string $a^n b a^m$ and check if $n>m$ then convert the string to $a^{n-m}$, otherwise reject it?


texts: Finding missing range in multidimensional domain

texts:
Let's suppose that I have a monodimensional numeric domain and a list of ranges in this domain defined as

class Range {
    int lowerBound;
    int upperBound;
}

then it's trivial to check if the union of the List<Range> is covering the entire domain. However in case of a bidimensional domain I have a List<Pair<Range>> and I'm no longer able to figure out if my rectangles (bidimensional ranges) are covering the entire area.

For example suppose that I have these ranges:

pair{ range{0, 7}, range{0, 5} },
pair{ range{7, 10}, range{0, 7} },
pair{ range{0, 5}, range{5, 10} },
pair{ range{5, 10}, range{7, 10} }

covering the domain as shown below.

How can I know that part of the domain isn't covered? (gray area in the picture). In other words is there an algorithm or a data-structure allowing to find if there exists at least one point in that domain that is not included in any of the rectangles? Is this solution also extensible to the n-dimensional case?


texts: Prove that the equal-length concatenation of regular languages is context free

texts:
If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free.

So I'm trying to come up with the proof that looks something like this. Knowing that $A$ and $B$ are regular, we can conclude that there exists NFA for $A$ and $B$ respectively. Then, we can work out these NFA into two separate PDA: one PDA that would accept $x$ from $A$ and another PDA that would accept $y$ from $B$. Then we need to somehow merge two PDAs into one modifying it so that it controls the length of $x$ and $y$ too and accepts only in the case when $x=y$.

I am just trying to come up with the set of legitimate steps that would follow through this, and that these steps would always work so that given $A$ and $B$ are regular final the PDA will always accept $A@B$.


texts: How can context switch affect the modification of a variable?

texts:
float myTotalAmount=0;
void update(float amt){
    myTotalAmount+= amt;
}

Task A called update(10);

Calculated myTotalAmount+= amt;

Didn't store the value for myTotalAmount; -------X

Task B called update(5);

Can we say X didn't happen due to context switch? or is Task B able to call update method because context switch happened due to some reason before the X?

Overall I am trying to understand race condition.


texts: Difference between a turing machine and a finite state machine?

texts:
I am doing a presentation about Turing machines and I wanted to give some background on FSM's before introducing Turing Machines. Problem is, I really don't know what is VERY different from one another.

Here's what I know it's different:

  FSM has sequential states depending on the corresponding condition met while Turing machines operate on infinite "Tape" with a head which
  reads and writes.

  There's more room for error in FSM's since we can easily fall on a non-ending state, while it's not so much for Turing machines since we
  can go back and change things.

But other than that, I don't know a whole lot more differences which make Turing machines better than FSM's.

Can you please help me?


texts: Proving a language is not regular using Myhill Nerode Theorem

texts:
Let $L = \{\alpha\in\{a,b,c\}^{*} \mid \alpha \text{ is palindrome}\}$, show that $L$ is not regular using Myhill-Nerode relation.

I don't know how to show that $L$ has infinite equivalence classes because $\alpha$ is a palindrome. I tried to use something like this, but I don't know if its correct:

$\alpha \equiv_{L} \beta \iff \alpha (aba)^k \in{L} \iff \beta (aba)^k \in{L}$ $\forall k \in \mathbb N$ which implies that for every k there exists an equivalence class because the repetition of aba k times.


texts: Featurizing images of different dimensions

texts:
I'm building a non linear svm for images to solve a classification problem with domain {0, 1} and I'm currently doing featurization. What I want to do is create 3 features for each pixel representing the rgb value. However, my input images have different dimensions meaning that they are of different widths and heights. So doing just this would result in images having a different number of featurizations.

For example: If i have one image of (10, 2) dimension {(width, height)} then it has 10 * 2 pixels, each with a rgb value. So there would be 10 * 2 * 3 features for this image. If i have a (11, 2) image, then it has 11 * 2 * 3 features.

I am ordering the pixels by first moving horizontally and then verticall. So if I have a (2, 2) dimension image then F1, F2, F3 would be the first three features of pixel (0, 0) wheras F10, F11, F12 would be the features of pixel (1, 1)

One way I thought about solving this is by just extending each image to the maxwidth and maxheight over all images, filling values with -1's for rgb pixels where the image has been extended. For example if i have and image of dimension (2, 2) and the max width and height is (3, 3), then the new image would be of dimension (3, 3) and the with new pixels (2, 2), (0, 2) (1, 2) (2, 0) (2, 1). All of these new pixels would have -1 for all rgb values.

However, will this affect my classifiers ability to recognize patterns? I'm planning on using a svm with radial kernal to start. Is there a better way to fix this?


texts: Any reason why Turing Machine would prevail on recursion theory?

texts:
Nowadays, most introduction books, videos, and comments about theoretical computer science talk about Turing machines but don't discuss recursion theory anymore. These approaches are known to be equivalent.
What is the reason behind this? Has recursion theory simply gone out of fashion or is there a fundamental/mathematical reason explaining this?


texts: "Visited" vs "Seen" Positions in Breadth-First Search

texts:
I'm struggling to understand why there is such a radical difference in the execution time and number of steps required by two seemingly similar algorithms for Breadth-First Search in a 2d grid.

In the Python program below, uncommenting the indicated lines switches between versions.

As well as help with understanding the difference, I would like to know if there is a "canonical" version which is considered best practice. Clearly here the second version performs best, but it is a also different to most of the statements of the algorithm I have found, which add the current node to a "visited" list straight after dequeuing.

BFS Algorithm

These versions store the whole path at each stage in the queue.

Version 1

Enqueue a list containing the start position, as the initial path.
while the queue has elements in it:
    dequeue the next path
    name the last element frontier
    add the frontier to a set of visited positions
    check if the frontier is the goal position
        if so, return the path
    otherwise, check neighbouring cells:
        if the cell is legal and is not in the set of visited positions,
             enqueue a new path consisting of the current path + this new cell
if no successful path was found, return None

Version 2

Enqueue a list containing the start position, as the initial path.
while the queue has elements in it:
    dequeue the next path
    name the last element frontier
    check if the frontier is the goal position
        if so, return the path
    otherwise, check neighbouring cells:
        if the cell is legal and is not in the set of previously seen cells,
             enqueue a new path consisting of the current path + this new cell
             add the current cell to a set of previously seen cells.
if no successful path was found, return None

import collections

offsets = {
    "up": (-1, 0),
    "right": (0, 1),
    "down": (1, 0),
    "left": (0, -1)
}

def is_legal_position(maze, pos):
    i, j = pos
    num_rows = len(maze)
    num_cols = len(maze[0])
    return 0 <= i < num_rows and 0 <= j < num_cols

def bfs(grid, start, end):
    """
    Bread-First Search in a 2d list. Stores whole paths in queue.
    """
    queue = collections.deque([[start]])
    seen_or_visited = set()

    while queue:
        print("####### While queue is not empty #########")
        path = queue.popleft()
        print("Path", path)
        frontier = path[-1]
        print("Frontier:", frontier)
        seen_or_visited.add(frontier) # Uncomment for version (1)
        if frontier == end:
            return path
        enqueued_this_round = []
        for direction in ["up", "right", "down", "left"]:
            print("### Direction: ", direction)
            row_offset, col_offset = offsets[direction]
            next_pos = (frontier[0] + row_offset, frontier[1] + col_offset)
            if is_legal_position(grid, next_pos) and next_pos not in seen_or_visited:
                print("Enqueueing", next_pos)
                queue.append(path + [next_pos])
                # seen_or_visited.add(next_pos) # Uncomment for version (2)
                enqueued_this_round.append(next_pos)
        print("seen_or_visited:", seen_or_visited, "\n")
        print("Enqueued this round", enqueued_this_round, "\n")

maze = [[0] * 5 for row in range(5)]
start_pos = (4, 4)
end_pos = (0, 0)
print(bfs(maze, start_pos, end_pos))
```


texts: Efficient way to calculate the maximum curvature of a cubic spline

texts:
I've got a 2D cubic spline (Bézier) and I have the polygon-line that's a discretization of that spline.

Is there an efficient and simple to implement a way to calculate the maximum curvature of the spline either by using its smooth representation or the discrete poly-line? It doesn't have to be exact since it's for a game, an error around 10% would be totally acceptable.

Different wording: I would like to know: if I'd drive a car driving at constant speed along the spline, what would be the maximum degree I had to turn the steering wheel to stay on it?


texts: Generating flight path for aerial photography

texts:
I need to generate the shortest possible path for aerial photography using a fixed wing unmanned air vehicle (UAV).

The image below shows the area I'm going to search. The white cells are the cells I want to photograph (must be traversed), and the black tiles are not of interest (doesn't have to be traversed). The middle of each cell is a waypoint/node.

Because the camera view banks when the UAV changes direction, the cost of turning inside the white area is more costly than turning inside the black area.

I have looked at different graph search algorithm like A*, Dijkstras, etc, but I'm unsure how they can be applied.

I'd appreciate any pointers that could help me solve this problem.


texts: Separability of the nearest power of two function

texts:
I have a function $f$ given by

$f(x)=nearest\ upper\ power\ of\ two\ of\ x$

For example, $f(5)=8$ and $f(2)=2$.

Are $f(x \wedge y)$ and $f(x+y\mod{N})$ separable over some operator. For example, could we do:

$f(x\wedge y)=g(x)g(y)$

or

$f(x+y\mod{N})=g(x)\ op\ g(y)$

where $op$ is some arbitrary operator.

In other words, what can be done algebraically with the nearest power of two function?

In Warren's Hacker's delight, we have that the nearest power of two function is given by:

$
f(x)=1<<(32-nlz(x-1)-1)
$

on a 32 bit register and with $nlz$ being the number of leading zeros. Maybe this is of use?


texts: How to partition a set in order to minimize the number of the elements and their interactions?

texts:
Given two sets $S_1$ and $S_2$ of $n$ elements each. Each set $S_1$ (resp. $S_2$) has a revenue $R_1$ (resp. $R_2$). Each element $i$ of $S_1$ (resp. $S_2$) has a gain $g_{i1}$ (resp. $g_{i2}$). From set $S_1$ (resp. $S_2$), choose a subset of elements $O_1$ (and $O_2$) such that:

$\sum_{i\in O_1}g_{i1}\geqslant R_1$;
$\sum_{i\in O_2}g_{i2}\geqslant R_2$;
$|O_1|+|O_2|+|O_1\cap O_2|$ is minimized.

Can we solve this problem in polynomial-time?

I started by a greedy approach which chooses the elements by increasing order of their gains. I tried few examples but this does not provide optimal results.

I am now trying to prove that it is NP-hard using a reduction from PARTITION. Any hints?


texts: Are all Integer Linear Programming problems NP-Hard?

texts:
As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming problem, but the Wikipedia page states that this is NP-Hard. To me, this implies the assignment problem is in NP-Hard.

But surely the assignment problem can't be in both P and NP-Hard, otherwise P would equal NP? Does the Wikipedia page simply mean that the general algorithm for solving all ILP problems is NP-Hard? A few other sources state that ILP is NP-Hard so this is really confusing my understanding of complexity classes in general.


texts: Show that kleene plus language is a regular language by describing how you build a DFA or NFA for it

texts:
L ⊆ ∑* is a regular language. Show that L^+ (aka kleene plus) is a
  regular language by describing how you can build a DFA or NFA for the
  language.

I would build a NFA. That NFA must have exactly one starting state and one end state, where the starting state is never the end state.

The amount of characters of the given language equals the amount of states of the NFA +1.

Every state except for the end state has an (outgoing) arrow to the next state where every single character of the language occurs exactly once (ordered aka one after the other).

If the language is made up of just one character, do: The end state has an outgoing arrow to itself with that one character of the language.

Else do: The end state has an outgoing arrow to the second state (I mean that state where the starting state points at) with the first character of the language.

Here is an example:

Given is language (aba)^+ where ^+ means exponent +

The NFA for this language would look like this ("Beispiel" means example):

Do you agree with my idea and do you have any improvements?

For the case the language is made up of several pairs, for example (aba, ab, bb)^+ I would just do the entire procedure for every single. In the end you will have a NFA for language (aba)^+ another NFA for (ab)^+ and NFA for (bb)^+. Then concatenate all NFA to one entire NFA.


texts: Asymptotic time complexity for finding maximum element in an array

texts:
Consider a simple algorithm to find the maximum element of an array containing integers. We just loop through the array, storing the maximum found so far and updating it whenever an element larger than the existing maximum is encountered.

This algorithm is often considered to have $O(N)$ complexity. But doesn't accessing the array take $O(\log N)$ time in each iteration of the for loop? After all, an array of size $N$ requires $\log N$ address bits, so accessing each element should take $\log N$ time steeps? So the total time complexity should be $O(N \log N)$, unless I'm missing something here?


texts: Processing weighted points of interest. Is there a name for this task/algorithm?

texts:
Is there a name for the following problem? Is there a measure of quality of a given solution? How can we even define what a proper solution is?

Context: I want to detect long lines (most lines over 1000 pixel long) in an image. It is known that most of the lines have similar alignment. To detect those I use the  Standard Hough Transform. To detect long lines I need a high angle resolution of the accumulator. Now the idea is not to use an equidistant partition of the angle axis but to create a new partition based on the number of votes for each angle.

The Problem: Given weights
$$a_0, \ldots, a_{n-1} \in [0,1] \text{ with } \sum_{k=0}^{n-1}a_k = 1$$
which correspond to the equidistant partition of the interval $[0,1[$
$$0, \frac{1}{n}, \frac{2}{n}, ..., \frac{n-1}{n},$$ return a new partition with less or equal elements which is "finer" around points with larger weights and "coarser" around points with smaller weights. E.g. given the weights $(0.75, 0, 0, 0.25)$ on the partition $(0, 0.25, 0.5, 0.75)$ the result should be a new partition like $(-0.083, 0.0, 0.083, 0.75)$. As $0$ seems to be a point of interest there are three points near it which reflects that.

My solution: The idea is to treat the vector of weights as a density function and to use the  quantile function of its cumulative distribution function (cdf).

Example: Given the weights $(0, 0.5, 0, 0.5, 0)$ we construct the density function:

Then the cdf looks like this:

Now we shift the given equidistant partition by $+1/(2n) = 1/10$ and put its values into the quantile function, i.e. we put those values on the $y$-axis and search for corresponding $x$-values of the cdf as marked by the blue lines. $y=0.5$ is omitted since it "cannot decide" which peak it contributes to. The so obtained $x$-values are shifted by $-1/(2n) = -1/10$ and returned as the new partition. The returned partition in this example is $(0.14, 0.22, 0.58, 0.66)$.

Here is a C++ function which performes those tasks, where the vector "weights" represents the input weights and "sample" contains the new partition after execution:

#include <vector>
using std::vector;

void weighted_partition(vector<double>& sample, const vector<double>& weights) {
    const int n = (int)weights.size();
    double y;
    double F = 0.0;
    int i = 0;

    for (int j = 1; j < 2*n; j += 2) {
        y = (double)j/(2*n);

        while (F < y) {
            F += weights[i];
            ++i;
        }

        if (F == y) {
            continue;
        }

        --i;
        F -= weights[i];

        sample.push_back((y - F + weights[i] * i) / (weights[i] * n) - 1.0/(2.0 * n));
    }
}

This algorithm seems to return solutions which are intuitively correct but how can you define "correct"?


texts:
Okay, before I start with the question I would like to point out that I am aware that there are many proofs of this question online. However, I am interested in showing this with the definitions of my university script which are somewhat different from most of what I've seen online.

  Show that $P \subseteq NP$.

Before I start with my attempt, some definitions first:

Definition 1: A set of words $A$ is in $NP$ if and only if there is a polynomial $p$ and a set $B\in P$ such that

$$x\in A \iff \exists y(|y| \le p(|x|)\land x\#y \in B) $$

Definition 2:
$$P = \bigcup_{polynomial \; p}TIME(p(n))$$

Definition 3:
$$TIME(f(n)) = \{A\subseteq \Sigma^*:\text{there exists a multitape Turing machine M which computes} \;\chi_A \text{with}\;time_M(x)\le f(|x|) \}$$

Definition 4:
$$time_M:\Sigma^* \to \Bbb N$$ is the function that gives the amount of "computing steps" for a word $x$.

Definition 5:
$$\chi_A$$ is the indicator (also called characteristic) function of $A$.

My attempt:

The way I understand definition 1
$$P\subseteq NP :\iff$$
$$x\in P \iff (\exists polynomial \; p)(\exists B \in P)(\exists y \in \Sigma^*)(|y| \le p(|x|)\land x\#y \in B)$$

Proof:

(i) "$\Rightarrow$"

Let $x\in P$ and $|x|=n$ for an $n\in \Bbb N$

Define

$p(t):=n$ for all $t\in \Bbb N$

$y:=x$

$B:=\{x\#x\} = \{x\#y\}$

Then

$|y|\le p(|x|)$ since $|y|=|x|=n$ and $p(|x|)=p(n)=n$

and $\{x|\#y\}\in B$

(ii)
"$\Leftarrow$"

Let $p$ be a polynomial, $B\in P$, $y\in \Sigma^*$ such that

$$|y| \le p(|x|)\land x\#y \in B \text{ for an $x\in\Sigma^*$}$$

Now I have to show that $x\in P$ but I do not know how.

Furthermore, I do not understand is that in (i) I could have let $x$ be an element of any set and this implication would still hold. For example $x\in S$ for a set $S:NP\subset S$ with the rest of the proof being identical. This would mean that every set is in NP which is not the case. My guess is that my understanding of definition 1 is wrong.

This raises my first question: How come is not every set is a subset of NP using the definitions from above?

My second question: How do I go about solving (ii)?


texts: Count number of pairs of elements in an array whose bitwise OR is equal to a given integer

texts: Given an integer array and an integer $k$, we have to count the number of pairs of elements from the array whose bitwise OR is $k$ in $O(n)$ time complexity. How could this be done?


texts: Does graph G with all vertices of degree 3 have a cut vertex?

texts: I'm asked to draw a simple connected graph, if possible, in which every vertex has degree 3 and has a cut vertex. I tried drawing a cycle graph, in which all the degrees are 2, and it seems there is no cut vertex there. I know, so far, that, by the handshaking theorem, the number of vertices have to be even and they have to be greater than or equal to 4. So, I kept drawing such graphs but couldn't find one with a cut vertex. I have a feeling that there must be at least one vertex of degree one but I don't know how to formally prove this, if its true. I'd appreciate if someone can help with that.


texts: Dynamic changes to classes or context activation -- how to treat existing objects in a consistent way?

texts:
I am looking for references and papers on the following topic.

In general, some programming languages allow dynamic changes to classes. As an example, a new instance variable ‘weight’ can be added to the class Edge (the class of unweighted edges of graphs). But what should happen with existing edge objects?
They can be upgraded to include the new instance variable with a default value, perhaps weight 0, in the edge example. Or existing objects stay the same.

In context-oriented programming, similar situations can arise, when a context is dynamically activated at run-time. This may affect changes to methods which are currently executed (although I am concerned at the single thread execution at the moment).

Considering design patterns, when a proxy object wraps another object, references to the old object may expect certain invariants that the proxy object doesn’t adhere to. This may also lead to inconsistencies when an object is wrapped/’updated’ with a proxy object.

Are there any references that list possible ways to treat the problem in case of dynamic changes/activation? Like the options to keep the state consistent?
I looked primarily in the communities of dynamic software evolution, context-oriented programming and software components. Are there other important communities I can search to find references?


texts:
Here's a lab from a first-year computer science course, taught in Scheme: https://www.student.cs.uwaterloo.ca/~cs135/assns/a07/a07.pdf

At the end of the lab, it basically presents the halting problem, and shows that it is impossible to solve by introducing the function diagonal, which is defined as:

(deﬁne (diagonal x)
  (cond
     [(halting? x x) (eternity 1)]
     [else true]))

Where eternity is a non-terminating program defined as (define (eternity x) (eternity x)). What happens when you feed diagonal its own definition as input ... ?

This is all fairly standard stuff. Then, the lab says:

  For a real challenge, deﬁnitively answer the question posed at the end of Exercise 20.1.3 of the
  text, with the interpretation that function=? consumes two lists representing the code for the two
  functions. This is the situation Church considered in his proof.

So the gist of it is that function=? takes two inputs. Each is a list, which represents the definition of a function, i.e. it is a list of the form (define (id args ...) body ...). We can assume that both functions are syntactically valid and will terminate for all inputs (without runtime errors). function=? returns true if and only if the two functions will always return the same result when given the same inputs. For example,

(function=? '(define (foo x) (* 2 x))
            '(define (bar x) (+ x x))) ; should return #t

(function=? '(define (foo x) (+ x 1))
            '(define (bar x) (+ x 2))) ; should return #f

Now, function=? is obviously impossible to write - the challenge is to prove it is impossible. I thought about this for a while, and the best solution I could come up with is the following:

(define (disprove-function=? x)
  ((lambda (snip)
     (let ((self (list 'define '(disprove-function=? x)
                       (list snip (list 'quote snip)))))
       (if (function=? self '(define (id x) x))
           (list x)
           x)))
   '(lambda (snip)
      (let ((self (list 'define '(disprove-function=? x)
                        (list snip (list 'quote snip)))))
        (if (function=? self '(define (id x) x))
            (list x)
            x)))))

Basically, disprove-function=? uses standard quining techniques to generate its own source code (the variable self), and then asks function=? if it is equivalent to the identity function. If function=? says #f, then disprove-function=? will always behave like the identity function. Contradiction! If function=? says #t, then disprove-function=? will always behave differently from identity; in particular, it will behave like the list function. Contradiction! Thus, function=? can't exist. QED.

My question is: is there a more elegant way to approach this problem? My solution seems ... long and ugly. Not nearly as nice as the diagonal function for proving that the halting problem is unsolvable.

NB: Please give me answers and not hints! Even though this is a homework question, it is not my homework question: I don't go to this university! Further, as you can see from the lab, this question is under the Enhancements category and isn't worth marks, so even if you don't believe me, there is still no problem with just giving me an answer. Finally, I already have a solution, which I am pretty sure is right; I was just wondering if there was a better solution.


texts: Application of iterative algorithm $(\theta_n,w_n)$ converging to $\{(\theta,\theta):\theta \in \Bbb R\}$

texts:
I have a iterative algorithm $(\theta_n,w_n)$ which I am showing converges to $\{(\theta,\theta):\theta \in \Bbb R\}$.
The iterative algorithm is of the form :
$\theta_{n+1} = \theta_n + a(n)[h(\theta_n,w_n)]$,
$w_{n+1} = w_n + b(n)[g(\theta_n,w_n)]$

I want to know whether there could be any practical application of this.


texts: Algorithm for simplifying ANF or polynomials?

texts:
I have some digital logic circuits in Algebraic Normal Form, and am limited to using XOR and AND logic gates.

For instance:

$B_{out} = B_1 B_2 \oplus B_1 B_3$

I was wondering, are there any algorithms to simplify ANF to use a smaller number of gates?  I'm looking to minimize ANDs specifically.

The above equation would ideally become this:

$B_{out} = B_1 (B_2 \oplus B_3)$

Since AND and XOR act like multiplication and addition respectively, it also seems like the answer could be in algorithms which minimize operations in polynomials.  If that is the case, I'm specifically looking to minimize multiplications (which is the equivelant of ANDs in ANF).

One person suggested i use a Karnaugh map, but am unsure how (or if it's possible) to use a Karnaugh map with XOR/AND instead of OR/AND.  I could convert OR/AND back and forth to XOR/AND terms as needed, but in that case I don't believe the result is garaunteed (or likely) to be minimal anymore.

Are there algorithms for this? I feel like there has to be, but I haven't been able to find any.


texts: What are the common practices to weight tags relations?

texts:
I am working on a webapp (fullstack JS) where the user create documents and attach tags to them. They also select a list of tags they are interested in and attach them to their profile.

I am not a math guy, but I did some NLP as hobbyist and learnt about latent semantic indexation: as I understand it, you create a table where you store each couple of words you parsed, and then add weight to each of these couples of words when both are found next to each other.

I was thinking of doing the same thing with tags: when 2 tags appear on the same document or profile, I increase the weight of their couple. That would allow me to get a ranking of the "closest" tags of a given one.

Then I remembered that I came across web graphs, where websites were represented in a 2D space (x and y coordinates) and placed depending on their links using an algorithm called force vector.

While I do know how I would implement my first idea, I am not sure about the second one. How do I spread the tag coordinates when created? Do they all have an x:0, y:0 at the start?

Since I assume this is a common case of data sorting, I wondered what would be the common/best practices recommended by people of the field.

Is there documents, articles, libraries (npm?) or wikipedia pages you could point me out to help me understand what can or should ideally be done? Is my first option a good one by default?

Also, please let me know in comments if I should add or remove a tag to this question or edit its title: I'm not even sure of how to categorize it.


texts: Proving the probability of zero occurrences in training using Good-Turing maximum likelihood estimate

texts:
Background

Good-Turing (GT) smoothing is used in language models to estimate the counts of words in the test set that have not been seen in the training set.

In GT smoothing, $N_c$ is the count of things observed $c$ times (so a count of a count). As an example, the sentence "Sam I am I am Sam I do not eat" has unigram $N_1=3$ (do, not, eat), unigram $N_2=2$, ...

GT smoothing uses the count of words we've seen once in the training set to estimate the count of words in the test set that we've never seen before. The estimate of the count of these words in the test set that we've never seen before is given by: $$c^*\leftarrow (c+1)\frac{N_{c+1}}{N_c}.$$ This is known as the Good-Turing estimate of Maximum Likelihood Estimate (MLE) for language models. This redistributes probability masses of word occurrences.

The problem

The Good-Turing probability of a word with zero frequency is $$P_{GT}(c=0)=\frac{N_1}{N}.$$

I can't completely see where this comes from. Zero frequency in the training set implies that $c=0\implies c+1=1$, so that coefficient disappearing makes sense. Also, $N_{c+1}=N_{0+1}=N_1$ makes sense in getting the numerator.

But what confuses me is how this implies that $N_0=1$.

The reason $N_0 = 1$ is because: $$P_{GT}(c>0)=\frac{c^*}{N}=\frac{c+1}{N}\frac{N_{c+1}}{N_c},$$ so $$P_{GT}(c=0)=\frac{N_1}{NN_0}=\frac{N_1}{N}$$

How does $N_0=1$?

$N_0$ is the count of the words observed $1$ time, so don't see how this is $1$.

In other words, how is $P_{GT}(c=0)$ fully derived?


texts: Proof required for edges in a minimum spanning tree

texts:
G=(V,E) is an undirected simple graph in which each edge e has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?

I. If e is the lightest edge of some cycle in G, then every MST of G includes e.

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e.

The answer is only statement 2 is correct.

I was able to prove statement 1 is false using contradiction. When we think of a complete graph with 4 vertices and edge weights 1,2,5,6 in non diagonal and diagonal edges 3 and 4. 4,5,6 will create a cycle and we can exclude the lighest edge e (4) from it, in a MST.

But statement 2 cannot be proved using the same. What should be the proof for proving statement 2 is correct?


texts: Hash table open addressing without dummy

texts:
If a hash table is using open addressing as the collision resolution strategy, then  during deletion, we mark that slot as dummy.
I understand the reason behind that is because while probing, a dummy would indicate there are still used slots further down the chain to search for.

But my question is that is there any way to implement open addressing without need for a dummy, and without degrading the algorithmic complexity of the hash table operations?

I came up with and algorithm of moving the last non-Null element of the probe sequence to the place of the deleted element to make the probe sequence contiguous. But this would make it impossible to retrieve the moved element if its hash index value was greater than that of the removed element.

So is there any correct algorithm for this?

EDIT

There is a small article on Wikipedia regarding this.
I'll copy the relevant text (the whole article) here:

  In computer science, lazy deletion refers to a method of deleting
  elements from a hash table that uses open addressing. In this method,
  deletions are done by marking an element as deleted, rather than
  erasing it entirely. Deleted locations are treated as empty when
  inserting and as occupied during a search.

  The problem with this scheme is that as the number of delete/insert
  operations increases, the cost of a successful search increases. To
  improve this, when an element is searched and found in the table, the
  element is relocated to the first location marked for deletion that
  was probed during the search. Instead of finding an element to
  relocate when the deletion occurs, the relocation occurs lazily during
  the next search.

But I dont get it. If we move another element to the deleted place, it will again leave a hole in its probe sequence. How is it logically correct?

PS: This is another question somewhat related to the first one, so I dont know if I should make it a separate question or not.


texts: Does every turing machine have an equivalent, single-state, n-tape turing machine?

texts: Is it the case that every problem computable by a Turing Machine can also be represented by some kind of equivalent n-tape Turing Machine which one has only one state?  (We can assume that the accept and reject states are implicit here. If that bothers you, you may think about this as a question about 3-state machines instead.)


texts: Does a type-1 automaton always have to terminate?

texts:
For push-down automata it seems obvious to me that a program must always terminate (given the input is finite), because for each input symbol they advance until eventually they run out of symbols and then terminate.

The opposite is true for Turing machines as they read their input from the tape and are able to alter the position in the input string.

Linear bounded automata are basically Turing machines that have to operate on a bounded range on the tape. As far as I can see, that doesn't prevent you from writing a program for such a machine that just toggles between two states infinitely and thus never terminates.

Is this assumption correct? And can we infer anything about the language an automaton is able to accept from the property if it must terminate eventually? I'm a bit confused about the fact that type-1 languages are a subset of the decidable languages, where the decidable languages require an always halting Turing machine, but I can't find any such restriction for linear bounded automata.


texts:
I have a simple theoretical question in very basic algorithms, as the title mentions, is it always true that the depth of BFS is $\leq$ DFS?

From what I understand, the tricky part here is the possible cycles in the graph. Even though that I believe that the depth of BFS will always be less or equal to the depth of DFS.

In each iteration of BFS, from what I understand, the depth might grow by one, but DFS's grows in each vertex it can not reach, sometimes above the maximal value of BFS.

So, is it always true that the depth of BFS is $\leq$ DFS?


texts: Why is the most probable assignment for all variables in MRFs called MAP assignment?

texts: I am new to graphical model, especially Markov Random Fields. I have a question about MAP assignment. Let say we have the graph structure and all the potential functions. MAP assignment in MRFs is defined as the most probable assignment for all variables (no given evidence in this case). My question is why it is called MAP (why not MLE or anything else). What is the connection between them? I know MAP and MLE share a lot in common except for one thing that MAP uses the prior distribution of the parameters. But I cannot figure out the connection between the most probable assignment in MRF and MAP.


texts: How do I prove that any function is O(...) /Θ(...) /Ω(...)?

texts:
I'm taking my first algorithms class, and the first exam is tomorrow. I've been looking forward to this class since freshman year, but now that I'm in it the professor is less than stellar and I've been having trouble (making tomorrow's exam worrying). We've covered the meaning of each of the notations, but we'll be asked on the exam questions like:

Prove max(f, g) = Θ(f + g)
Prove (n + a)^b = Θ(n^b)
Is 2^(n+1) = O(2^n)?

I've never worked with these kinds of proofs before. I've been trying to look these problems up on a case-by-case basis, but I've realized that's a terrible idea. What my professor's failed to reasonably explain in class is how to actually approach these kinds of problems. Could someone help explain to me as simply as possible how to approach these so that I can handle any type of proof like this in the future?

Edit: This isn't a duplicate of the suggested question at all. I am not asking of the meaning of the given notations, the growth rates or certain function types, or which one to use at all. I am asking how to prove that a given specific function has a certain complexity.


texts: I am working on a branch and bound problem and I was wondering if it is correct to prune the node with z = 21.667 and if so, how do we know that we will not get a better solution if we branch on this node?


texts:
A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time.

The problem is: you have to travel $1000$ km. The only gas station is at the starting point. Your maximum fuel tank capacity is just enough for $50$ km traveling, you are allowed to "bury" fuels in the middle of the journey and save it for later.

For example you can travel $20$ km first, and bury $10$ km worth of fuel there, and then go back to refuel, so next time you can retrieve the $10$ km fuels you left and reach further with it.

You need to find the most efficient way to reach the destination.

What I thought of is using dynamic programming, however you have to assume the distance you travel before each time you do refueling is an integer in terms of kilometers, else you it is hard to do it with DP, I have not try linear programming yet, but I think it is possible.

Do you have any idea how to do it? Or any hints?

Most importantly what type of cs problem is it? is it NP hard? Is it solvable by machine or is it more of a mathematical problem?

Some more thoughts:

Since it is a continuous path, asking whether if it is NP might be bit silly, but I am still very curious.
$1000$ and $50$ might be deliberately picked to avoid complex computation.
Is there a greedy solution? I cannot think of any just yet.
I now think it more of a mathematical pattern finding problem, though my friend claims it is a cs problem, so I am decide to keep this post.

And if you have any scientific articles or textbooks related to this please tell me, I do not know where to start in the first place.


texts: Does this language have a context-free grammar?

texts:
Here is a question that I encountered in one of my exams:

  Find one context-free grammar that recognizes the language:
  $\qquad L = \{a^n(b^mc^m)^pd^n \mid m, n, p \geq 0\} $

Can you find such a grammar? I even doubt its existence, but I have not been able to prove that.


texts: Are automata useful in software verification?

texts:
I contrast the paradigm of SMT-based verification of software, such as in LiquidHaskell with the approach based on automata. To me it appears that automata are only used in the paradigm of model checking.
It also seems to me this paradigm has severe difficulties to scale to the verification of programs. In fact, I recall hearing Joseph Sifakis quoting a member of his PhD jury saying "there are no finite state programs out there".
Of course, there are (like protocols), but does automata scale to the full verification of software as well as the SMT-based + specification approach?


texts: Does an enumerator print the first occurrence of a word in finite time?

texts:
For a proof I need to use the fact that every word in the language of an enumerator occur on the output paper in finite time. Is it true?
For example, the language of the natural numbers in decimal representation. Can the enumerator print the odd numbers first and then the even numbers? (if yes, I am wrong)

$1, 3, 5, 7, ..., 2, 4, 6 ,8, ...$

As I know, we get to the even numbers but not in finite time (maybe transfinite induction based on this)


texts:
I am aware that this seems a very stupid (or too obvious to state) question. However, I am confused at some point.

We can show that P $=$ NP if and only if we can design an algorithm that solves any given instance of problem in NP in polynomial time.

However, I do not understand how on earth can we prove that P$\neq$NP. Please excuse me for the following similitude as it might be so irrelevant, but telling someone to prove if P is not equal to NP appears to me like telling someone to prove that God does not exists.

There is a set of problems, those are unable to be solved by a Non-deterministic Finite Automata (NFA) with polynomial number of states regardless of the current technology (I know this is a sloppy definition). In addition, we have a considerably large set of algorithms that makes some crucial problems (shortest path, minimum spanning tree, and even sum of integers $1 + 2 + \dots + n$) polynomial-time problems.

  My question in short: If I believe that P $=$ NP,
  you would say "then show your algorithm that solves an NP problem
  in polynomial time!". Suppose that I believe P$\neq$NP. Then what would you exactly ask? What would you want me
  to show?

The answer is clearly "your proof". However, what kind of proof shows that an algorithm cannot exist? (in this case, a polynomial time algorithm for an NP problem)


texts: Checking for $3$-colorability by searching for $K_4$ as a minor

texts:
Determining if a graph is $3$-colorable is NP-complete. But this is equivalent, by a resolved case of Hadwiger's Conjecture, to checking if the graph has $K_4$ as a minor.

Per https://en.wikipedia.org/wiki/Graph_minor#Algorithms, this can be done in $O(n^3)$ time, where $n$ is the number of vertices, as $K_4$ has a constant number of vertices. This would seem to be a contradiction (unless $P=NP$)


texts: Counting models satisfying a boolean formula

texts:
I'm trying to implement the #2-SAT algorithm from the paper "Counting Satisfying Assignments in 2-SAT and 3-SAT" (Dahllöf, Jonsson and Wahlström, Theor. Comput. Sci. 332(1–3):265–291, 2005). A few lines into the algorithm description the authors denotes a sub algorithm and claims "The function $C_E$ computes #2-SAT by exhaustive search. It will be applied only to formulas of size ≤ 4 and can thus be safely assumed to run in O(1) time". The size of formulas is referred to the number of clauses.

I've been trying to find this exhaustive search algorithm that computes a #2-sat instance with number of clauses less than 4. But the results only returns algorithms for generally solving/counting models for #2 or #3-SAT and does not talk about a special case when size ≤ 4. First of all, is this claim true? Since the paper was published by a well known journal, I guess it is. But if so, does anyone know about this special case?


texts: How can we reduce variables when converting from 3-SAT to 4-SAT?

texts:
If we suppose that we'd like to convert an instance of 3-SAT to an instance of 4-SAT, by how much can we reduce the amount of variables?

CONVERSION METHODS FOR PRODUCTS OF SUMS

If we are given a 3-SAT clause $(A \lor B \lor C)$, we can readily convert this to 4-SAT by rewriting it as $(A \lor B \lor C \lor x) \land (A \lor B \lor C \lor \overline{x})$, where $x$ is a free variable.  In other words, $x$ can be any one of the existing variables, or a completely new variable.  This entails that we can gaurantee that 3-SAT can be converted to 4-SAT without adding any new variables.

Additionally, we can convert 3-SAT into 4-SAT and eliminate one variable, given a special set of clauses.  The 3-SAT clauses

$$(x \lor B \lor D) \land (\overline{A} \lor \overline{C} \lor x) \land (A \lor C \lor \overline{x}) \land (A \lor \overline{C} \lor x) \land (\overline{A} \lor C \lor x)$$

readily "reduce" to $(A \lor B \lor C \lor D)$.  This eliminates the free variable $x$, assuming it only appears in these clauses, and also greatly reduces the number of clauses.  The significance of this is that we may be able to eliminate some variables using this technique.

THE MAIN QUESTION

What are some other techniques for reducing the number of variables when converting from 3-SAT to 4-SAT?

Note that converting from product-of-sums to sum-of-products form may also be useful.


texts: Computation equivalence of functional and procedural programming

texts:
I'm really interested in the idea of functional programming, it seems like a very modular way of doings things. I've seen some suggestion that functional programming is just as powerful as procedural programming (any problem you can solve with one can be solved with another).
I'm curious as to how this conclusion was originally derived, and whether there is a conclusive proof as to this (preferably one that a bit of a newb to lambda calculus like me can understand)
Related:
Why are functional languages Turing complete


texts: Is it possible to make partition of Quicksort run in O(lg n)?

texts: I was thinking maybe I can make it 2T(n/2) + C split the list into two halves and work on them recursively to partition the list.


texts: Why injection into sum type apparently leads to ambiguity?

texts:
I have been reading Benjamin Pierce's Types and Programming Languages, plus a couple of course notes on type systems and typed $\lambda$-calculus, and there is one thing I don't get: it seems that everybody defines sum types in the same way, and they way the language is extended to accommodate this new type includes the following typing rules:

if $\sigma$ and $\tau$ are types, then $\sigma+\tau$ is a type
if $M$ is of type $\sigma$, then $\operatorname{inl} M$ is of type $\sigma+\tau$
symmetrically for $\operatorname{inr}$, if $M$ is of type $\tau$, then $\operatorname{inr} M$ is of type $\sigma+\tau$.

However, suppose I have two sum types, $\sigma+\tau$ and $\sigma+\phi$,
and also that $M$ is of type $\sigma$.
Then it is not clear what the type of $\operatorname{inl} M$ is.

Is there something I missed, or is this really how sum types work? Because it would be quite easy to actually "fix" the definition to allow one to immediately infer the type of $\operatorname{inl} M$ in the example above -- just include the sum type in the annotation:

$\operatorname{inl_{\sigma+\tau}} M$ is, of course, of type $\sigma+\tau$.

But this is not what is usually done. Why? (Or is it actually done, implicitly?)


texts: Find a minimum weight matching of a specific size

texts: Given a positive-weighted complete graph $G=(V,E)$ and an even integer $k$, I want to find a minimum weight matching of size exactly $k$, i.e., I want to choose $k/2$ vertex disjoint edges such that the summation of their weight is minimum.


texts: Maximum number of non-overlapping rectangles where each contains a minimum number of points

texts:
Given n points and 0 < p < n, find the maximum number k of rectangles such that each rectangle contains at least p points and no two rectangles overlap.  Each point is distinct from every other point, and the edges of all rectangles must be parallel to the coordinate axes.

For example, 1 rectangle can contain all n points, but if it can be subdivided into 2 rectangles where each rectangle contains p points, then that would make k=2 if the rectangles could not be subdivided further.

Alternatively, n rectangles, each of which contains 1 point, could be constructed and iteratively merged together until all rectangles contain p points.

Is there an efficient algorithm in m dimensions?


texts: How a program is copied to RAM from harddisk

texts:
I know that for executing a program, it should be copied to RAM. But the problem is whole of it may not be copied always.

Since the size of the RAM is limited, there is mechanism called virtual memory. If the addressed thing is not in memory, a page fault occurs and the data is copied to the RAM. My question is who keeps track of which data is in the RAM and not in the RAM?


texts: single agent vs multiple agent reinforcement learning

texts:
I am confused about 'single' vs 'multiple' agent reinforcement learning.

Let's say that I have 1 hunter who I am training to hunt 1 static prey, so that only the hunter is moving around. This is definitely single-agent RL.

If there are two hunters and two preys (moving or static), then this becomes multiple agent RL. It would be 'easier' to study two independent hunters, perhaps, but that is a different problem.

My question is this: If there is 1 hunter only, but there are two preys. There is 'some form of interaction' (vaguely defined) between the hunter and prey. Is this still a single-agent RL? or a multiple one?

Is it possible that my agent is the hunter, and all preys be just part of the environment?


texts: Relation between deficiency and color class parity of graphs

texts:
Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its incident vertices receive same colour) with $\Delta+1$ colours. Let the vertices be properly coloured with $\Delta+1$ colours say, $c_i\ \ i\in\{1,2,\ldots,\Delta+1\}$. Let $n_i$ be the number of vertices in the $i$th colour class. In addition, let $r$ be the number of $n_i$ with $n_i\equiv|V(G)|\bmod2$. Then, is it true that $\sum_{v\in V(G)}\Delta-d(v)\ge\Delta-r+1$, where $d(v)$ is the degree of vertex $v$?

I think it is true, but the proof eludes me. Specificaly, there are $r$ and $\Delta-r+1$ colour classes of different parity. But, how does the deficiency between maximum degree and vertex degree and total colourability come into play here? Note that the inequality is strictly not true for graphs which cannot be totally coloured with $\Delta+1$ colours


texts: How to count the combinations not greater than a given volume in a knapsack problem?

texts:
You are given a certain set of items with weight wi and the volume of the bag.

Case:

Input:

3 (count of items) 10 (volume of the bag)
1 2 4 (weight for each item)

Output

8 (since you can put any item in or not 2 * 2 *2)

I have a naive solution using DFS as

public class Main {
    public static void main(String... args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int volume = scanner.nextInt();
        int[] weights = new int[size];
        for (int i = 0; i < size; ++i) weights[i] = scanner.nextInt();
        System.out.println(getCounts(weights, 0, volume));
    }

    private static int getCounts(int[] nums, int pos, int target) {
        if (target < 0) return 0;
        if (pos >= nums.length) return 1;
        return getCounts(nums, pos+1, target) +
            getCounts(nums, pos+1, target-nums[pos]);
    }
}

As expected, it produced TLE and I added cache to avoid re-calculation as

public class Main {
    private static int[][] cache;
    public static void main(String... args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int volume = scanner.nextInt();
        cache = new int[size+1][volume+1];
        for (int i = 0; i <= size; ++i) {
            for (int j = 0; j <= volume; ++j) {
                cache[i][j] = -1;
            }
        }
        int[] weights = new int[size];
        for (int i = 0; i < size; ++i) weights[i] = scanner.nextInt();
        System.out.println(getCounts(weights, 0, volume));
    }

    private static int getCounts(int[] nums, int pos, int target) {
        if (target < 0) return 0;
        if (pos == nums.length) return 1;
        if (cache[pos][target] != -1) return cache[pos][target];
        int count = getCounts(nums, pos+1, target) +
            getCounts(nums, pos+1, target-nums[pos]);
        cache[pos][target] = count;
        return count;
    }
}

But the OJ prompt me of memory error while the memory is within the limit => 13064K < 32768K, any idea to solve this issue?

Why did it fail?
Could a DP solution without backtracking be found for this?

Any help will be appreciated :)

Here is the original problem in Chinese.


texts: Which inductive schemes can encode the following Agda definition?

texts:
Which induction schemes (e.g. induction-recursion by Dybjer and Setzer, "Irish" induction-recursion by McBride or induction-induction by Forsberg and Setzer or perhaps some simpler ones) allow one to encode the following Agda definition

  data A : Set where
    a : Maybe (List A) → A

I can think of some tricks to reformulate List in this definition so that induction-recursion becomes applicable, but are there any schemes that would allow me to first say what a list is and then refer to this information to say what A is the way it's done in Agda?

Edit: As follows from András Kovács's answer, this particular definition can be reformulated as an inductive family. Here is how to do it:

data Three : Set where one two three : Three

data AG : Three → Set where
  a'       : AG three → AG one
  nil'     : AG two
  cons'    : AG one → AG two → AG two
  nothing' : AG three
  just'    : AG two → AG three

A = AG one
ListA = AG two
MaybeListA = AG three

a : MaybeListA → A
a = a'

nil : ListA
nil = nil'

cons : A → ListA → ListA
cons = cons'

nothing : MaybeListA
nothing = nothing'

just : ListA → MaybeListA
just = just'


texts: Is shuffling a set of items after popping an item meaningfully more random than doing it once, before starting?

texts:
I'm working on a thing to randomly assign people into a shift. There's mostly 2 sets of people, "free" and "assigned".

Is shuffling the "free" set after assigning an employee meaningfully more random than just doing it before I start putting people into the "assigned" set? How can I come up with proof of this?