texts: Nondeterministic Turing Machine for $L^*$

texts:
If $T$ is a Turing Machine that accept a language $L$, I want to define a Turing Machine $T'$ such that accepts the language $L^*$.
An approach:

$T'$ is a nondeterministic Turing Machine which has many tapes.
$T'$ 'copies' in a nondeterministic way a prefix from the original string to another tape and then it is applied $T$

So well, what I should know is:

How many tapes has $T'$ ?
What happens next if $T$ accept this prefix
How is this prefix selected?
What is the end condition to accept a string in $L^*$.


texts: Examples of higher order algorithms ($\mathcal{O}(n^4)$ or larger)

texts:
In most computer science cirriculums, students only get to see algorithms that run in very lower time complexities. For example these generally are

Constant time $\mathcal{O}(1)$: Ex sum of first $n$ numbers
Logarithmic time $\mathcal{O}(\log n)$: Ex binary searching a sorted list
Linear time $\mathcal{O}(n)$: Ex Searching an unsorted list
LogLinear time $\mathcal{O}(n\log n)$: Ex Merge Sort
Quadratic time $\mathcal{O}(n^2)$: Ex Bubble/Insertion/Selection Sort
(Rarely) Cubic time $\mathcal{O}(n^3)$: Ex Gaussian Elimination of a Matrix

However it can be shown that
$$
\mathcal{O}(1)\subset \mathcal{O}(\log n)\subset \ldots \subset \mathcal{O}(n^3)\subset \mathcal{O}(n^4)\subset\mathcal{O}(n^5)\subset\ldots\subset \mathcal{O}(n^k)\subset\ldots
$$
so it would be expected that there would be more well known problems that are in higher order time complexity classes, such as $\mathcal{O}(n^8)$.
What are some examples of algorithms that fall into these classes $\mathcal{O}(n^k)$ where $k\geq 4$?


texts: find a path to visit every node in graph not necessarily once

texts:
I meet a problem but when I google, there are all Hamiltonian Path Problem: How to find a path to visit every node in directed graph(not necessarily once)?
This problem is different from Hamiltonian Path.
For example:
1 --> 2 -->  3 ↔ 4
             ↕
             5

I have a path $1\rightarrow 2\rightarrow3\rightarrow4\rightarrow3\rightarrow5$ to visit all nodes in this graph, however this graph has no hamiltonian path.
My questions:

What's the terminology of this problem?

Is there algorithm or theorem to determine whether a general graph has such path? If a graph has such graph, how to find the detailed
path?

Thanks


texts: Linear programming, Checking a constraint based on condition

texts:
I have a constraint $X \ge Y$ in a Linear programming formulation, where both $X$ and $Y$ are binary. I want to check this constraint on a condition like:

if (Y==1)
      then check the constraint
else
      Don't care about the constraint

How to do it.


texts: How powerful are DFA with recursive calls?

texts:
A family of deterministic finite automata of degree $n$ over an alphabet $Σ$, with   $\bigcap Σ = ∅$, consists of a set $\mathcal{A} =\{(K_i,Σ∪\{1,\dots,n\},δ_i,s_i,F_i) : 1 ≤ i ≤ n\}$ of deterministic finite automata. We fix implicitly a subscript function over $\mathcal{A}$, so that we can refer to the “$i$-th automaton   $\mathcal{A}_i = (K_i, Σ ∪ \{1, \dots, n\}, δ_i, s_i, F_i)$ of $\mathcal{A}$.”

Such a family performs the following processing:

Given an input $w ∈ Σ^∗$, the automaton $\mathcal{A}_1$ starts processing the input as usual, following the transitions in $δ_1$, until it reaches a transition of the form $δ_1(q, i) = p$, with $i ∈ \{1, \dots, n\}$. It then gives control to the automaton $\mathcal{A}_i$. The automaton $\mathcal{A}_i$ processes the not yet consumed input until it reaches a final state. When such a state is reached, $\mathcal{A}_i$ terminates and gives control back to $\mathcal{A}_1$, which resumes its operation from state $p$. $\mathcal{A}_1$ accepts the input iff it is in a final state when the end of the input is reached.
More generally, any automaton $\mathcal{A}_i$ can “call” some other automaton $\mathcal{A}_j$, which happens whenever $\mathcal{A}_i$ performs a transition of the form $δ_i(q, j) = p$. When such a transition happens, $\mathcal{A}_i$ gives control to $\mathcal{A}_j$. When the operation of $\mathcal{A}_j$ reaches a final state, $\mathcal{A}_i$ takes the control back and resume its operation starting from state $p$.

Call the whole system a deterministic finite automaton with recursive calls. It is in fact a usual finite automaton, with the added functionality that some edges represent a call to a different automaton instead of the acceptance of one input symbol.

How to show any language accepted by a deterministic finite automaton with recursive calls is context-free?
Are all the languages accepted by deterministic finite automata with recursive calls deterministic context-free?


texts:
I have a 2D polygon defined by a list of $n$ points: $A$, $B$, $C$... These points are sorted in clockwise order. Example:

I would like to find the most performant algorithm to detect all points which are close together (distance < $x$).In the above example, it is $(H, I)$ and $(B, F)$. I could compare each points with all others points and check their distance => complexity $O(n^2)$. Is it possible to have a better performance knowning that points are already sorted in clockwise order ?


texts: Unreachable Real Numbers - Randomness & Computability

texts:
I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there are infinite real numbers between two integers so Real numbers infinity is bigger than integer numbers.

Well my question is, couldn't we overpass this limitation by writing a program that prints out a random number in every execution? I know this is not a warranty that every real number would be printed but at least they would all have a chance.

Please point out if my reasoning is wrong and why.

Thanks you all very much!


texts:
Are there any standard Prolog knowledge bases available anywhere that have the same purpose as Cyc, namely to encode generally accepted common sense and human knowledge?

Typically containing generally accepted facts such as the ones given at

http://www.cs.utsa.edu/~wagner/CS1023/readings/prolog.html


texts: How to find an optimal sequence of matching

texts:
Given a graph $G(V.E,w)$ Here $w: E \mapsto R$. We need to find optimal set of matchings(set of edges that have no common vertices) and $t_i$'s such that after all these matchings, it results in  $\forall e \in E,  w(e) =0$. Each edge i.e $\forall j \in  M_i,  w(j) \leftarrow w(j) - t_i$. Weights cannot be negative, hence if you have non integer weights if $w(j) < 0$ then $w(j) = 0$. Hence we need $ [(M_1,t_1), (M_2,t_2), \cdots (M_k,t_k)]$ such that k is minimum. Each $M_i$ reduces the weight of edges chosen in that $M_i$ to be reduced by $t_i$. We need to determine a sequence of Matchings with least length, after which all edge weights become zero. I want to design an algorithm which finds a optimal sequence of Matchings, $t_i$ pairs. I have no idea how to find the optimal matching other than very inefficient algorithms like maximum weight matching,etc and going through every sequence. I am unable to come up with any general algorithm.

Equivalently: given a graph $(V,E)$ with weights on the edges $w:E \to \mathbb{R}$, I want to find a set of matchings $M_1,\dots,M_k$ and non-negative numbers $t_1,\dots,t_k \in \mathbb{R}_{\ge 0}$ such that

$$\sum_{e \in M_i} t_i = w(e)$$

for all $e \in E$, where the sum is taken over all $i$ such that the matching $M_i$ includes the edge $e$.  In particular, I want to find the minimal $k$ such that such a solution exists.  Is there an efficient algorithm to solve this problem?


texts: Why is CAN protocol preferred to be used in automotive application?

texts:
Is it only because of the fact that it is asynchronous and can be used for long distance message transfer. An example of where other protocols will fail would help.
Thanks.


texts:
As a follow-up to this question
, I've found a recursive algorithm that solves the given problem, but it runs too slow to pass all given tests.

int solve(int i, int crane1_pos, int crane2_pos, int dist)
{

    if(i == n)
    {
        return dist;
    }

    int dist1 = dist + get_dist(crane1_pos, t[i].first);
    int dist2 = dist + get_dist(crane2_pos, t[i].first);

    return min(solve(i + 1, t[i].second, crane2_pos, dist1), solve(i + 1, crane1_pos, t[i].second, dist2));

}

Where, get_dist is a function that looks like this:

int get_dist(int crn_pos, int fin_pos)
{
    if(crn_pos == -1)
        return 0;

    return abs(crn_pos - fin_pos);
}

$t$ in this particular situation is a vector of pair<int, int>, $n$ is the size of this vector and the initial call of the function is solve(0, -1, -1, 0).

I'm pretty sure this could be further improved by using DP, but upon doing some research on this issue, I found that I'm unable to transform this recurrence into some form of dynamic programming. I've derived the recurrence trees for several examples and I can't find the overlapping subproblems and a way to use memoization.

So I guess my question is, how do you turn this recurrence into DP?


texts: Spot the formalism (some kind of process logic)

texts:
Consider the following specification technique.

A specification consists of a finite set of triples $\langle C, A, C' \rangle$,
where $A$ is the name of an action and $C, C'$ are conditions, that is,
propositional formulas over propositional variables.

Example rules (in a more suggestive notation):

$C_1 \wedge \neg(C_2 \vee C_3) \stackrel{A_1}{\longrightarrow} C_1 \wedge \neg C_2$
$C_1 \vee C_3 \stackrel{A_2}{\longrightarrow} C_2 \vee C_3$

Each triple specifies an event together with its preconditions and postconditions:
the semantics can be defined by saying that the system being described has a state space consisting of the set of possible truth value assignments to the propositional variables, and that the actions may take the system from any state in which the precondition of a rule for that action holds to any state in which the postcondition of that same rule holds.

This formalism, or a restriction (e.g. no negation in formulas, or only Horn clauses) will only suit my purposes if software exists that can answer questions such as

Given a condition, which events may happen?
Given a condition, may it lead to deadlock (a condition in which no event can happen)?
Given a condition, will it never lead to deadlock?
Do deadlock conditions exist at all?
Given a condition, which events can never happen?

in under a second.

My question: what to Google for?

Does this formalism have a name?
Can it be converted to one for which equivalent problems have been studied?
I'm thinking of safe Petri nets, for which I've found some papers, Hoare logic, dynamic logic, no doubt there is more.

Does such software exist?  How do I Google for it?


texts: Min-cut in graph with demands/lower bounds

texts:
This week I read something about network flow from Algorithm Design. But I am confused about some concepts.

We say, if a graph G contains some nodes with demands, positive or negative, how to define the min cut for these graphs? If we still use the definition for simple graph, the value of max flow is not equal to the capacity of min cut. Or is it totally meaningless to talk about min-cut in a network with demands on some nodes.

Another thing is  how to define the capacity of a min-cut for graph with lower bound on its edges. Still the sum of capacities of edges out of starting set? Or say, now we have a lower bound for this cut which is the sum of lower bounds of edges out of starting set.


texts: On the Turing Completeness of First Order Logic

texts:
It is well known that in Descriptive Complexity Theory FO is equivalent to AC0.

However, this accepts a couple of a theory and a string <T,s> iff the interpretation of s as a query is satisfied by the theory T.

My question now is if there is an interpretation of which is stronger than AC0. For example, is there an interpretation of s as a theory so that the formalism accepts if s is a theory that is logically entailed by T. This problem is undecidable, but maybe it is possible to express problems in it which are stronger than AC0. (Reachability would be an interesting example if anyone could make this work)


texts: Hardness of $2$ edge-disjoint spanning trees decomposition

texts:
The question is clear from the title. What is the complexity of the following decision problem:

Input: An undirected graph $G(V, E)$
Output: $\mathrm{YES}$ if $G$ can be decomposed into two edge-disjoint spanning trees, $\mathrm{NO}$ otherwise


texts: Relationship between Las Vegas algorithms and deterministic algorithms

texts:
I'm wondering why the following argument doesn't work for showing that the existence of a Las Vegas algorithm also implies the existence of a deterministic algorithm:

Suppose that there is a Las Vegas algorithm $A$ that solves some graph problem $P$, i.e., $A$ takes an $n$-node input graph $G$ as input (I'm assuming the number of edges is $\le n$) and eventually yields a correct output, while terminating within time $T(G)$ with some nonzero probability.

Suppose that there is no deterministic algorithm that solves $P$. Let $A^\rho$ be the deterministic algorithm that is given by running the Las Vegas algorithm $A$ with a fixed bit string $\rho$ as its random string.
Let $k=k(n)$ be the number of $n$-node input graphs (with $\le n$ edges).
Since there is no deterministic algorithm for $P$, it follows that, for any $\rho$, the deterministic algorithm $A^\rho$ fails on at least one of the $k$ input graphs. Returning to the Las Vegas algorithm $A$, this means that $A$ has a probability of failure of $\ge 1/k$, a contradiction to $A$ being Las Vegas.


texts: How do you produce a CNF from a circular graph with colouring?

texts: If you had a circular graph e.g. A->B->C->D->E->A, and a legal coloring system with 3 colours (e.g. Red, Green Blue), where each node is assigned a colour and no node can be connected to another node of the same colour, what is the easiest way go about producing a Conjunctive Normal Form of node states (e.g. AR means A is coloured Red) where the models of the CNF correspond on a one to one basis to a legal colouring of the graph?


texts: Is the solution to Independent Set or Vertex Cover from 3-SAT optimum?

texts:
There are plenty of resources online discussing 3-SAT reductions to Independent Set or Vertex Cover problem. I am unable to find a resource which states that a satisfiable assignment to 3-SAT results in a vertex cover or an independent set which is optimum for the graph induced by 3-SAT in its reduction.

Say, I have a 3-SAT formula with n boolean variables and c clauses, which is reduced to an Independent Set problem on a graph. Its known that if the 3-SAT is satisfiable, then there exists an independent set of size c in the reduced graph. Is this the maximum independent set? Logically, adding one more vertex to the set will violate the property of the independent set, so it should be the maximum independent set. Can someone confirm this?

Now, if I do a reduction to vertex cover graph, a satisfiable assignment should correspond to a vertex cover of size n + 2c. Is this the minimum vertex cover achievable?

Any suggestions will be highly appreciated. Thanks!


texts: Using a greedy algorithm to find a cut S which at least half of the edges cut

texts:
Let $G$ be an undirected graph.

Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut.

I tried to think about something like choosing the vertex with the highest degree, add it to $S$, remove it from the graph and then repeat this process until I'm done.

However, this is nothing more than a guess and I could not prove it.

I tried to think of the problem in another way - removing no more than half of the edges in the graph until I get a bipartite graph, but finding the cycles takes too long.

Online solutions to this problem included using random algorithms - something we haven't learned in the course where I was handed this question. Other solutions were not clear to me (including one that was posted on this site), or seemed too complicated for the course level.

Could someone provide guidance please?


texts: Is master theorem applicable for $T(n) = 8T(\frac{n-\sqrt n}4) + n^2$?

texts:
Is master theorem applicable for this example?

$$T(n)= 8T \biggl(\frac{n-\sqrt n}4\biggr)+ n^2$$


texts: "Definition of NP via relations and quantifiers; not via NTMs"

texts:
I have the following question on an assignment, and despite asking my prof, I can't get a grasp on it..

  Let $L_1, L_2$ be languages in ${\sf NP}$. Using the definition of ${\sf NP}$ via relations and quantifiers (not the non-deterministic Turing machines) prove that the following language is in ${\sf NP}$:  $L=\{ x | x \in L_1 \text{ or } xx  \in L_2 \}$, where $xx$ is two concatenated copies of $x$.

Her notes say the following on this:

  Let $L\subseteq\Sigma^{*}$. We say $L\in{\sf NP}$ if there is a two-place predicate $R\subseteq\Sigma^{*}\times\Sigma^{*}$ such that $R$ is computable in polynomial time, and such that for some $c,d\in\mathbb{N}$ we have $\forall x\in\Sigma^{*},x\in L\iff\exists y\in\Sigma^{*},|y|\leq c|x|^d$ and $R(x,y)$.

I would imagine that this is a well known definition (though possibly worded differently)... but I don't know where else I can get details on it. My textbook has a somewhat similar definition, but it doesn't talk about this $c,d\in\mathbb{N}$ stuff..

  A verifier for a language $A$ is an algorithm $V$, where
  $$A=\{w\mid V\text{ accepts }\langle w,c\rangle\text{ for some string c}\}.$$
  We measure the time of a verifier only in terms of the length of $w$, so a polynomial time verifier runs in polynomial time in the length of $w$. A language $A$ is polynomially verifiable if it has a polynomial time verifier.

The $y$ in the first definition is supposed to be analogous to $c$ in the second; it is a certificate or witness used by the verifier. But that's all I can understand between the two.

Now... what I think I know about this question is that $R(x,y)$ is supposed to be a verifier for $L$, while $R_1(x,y_1)$ is a verifier for $L_1$ and $R_2(x,y_2)$ is a verifier for $L_2$. She said something about $y=\langle y_1, y_2\rangle$ being an encoding of the two certificates for the verifiers $R_1$ and $R_2$. But from there I'm lost. I have no idea how to answer this question even after asking for help two or three times.

Anybody here able to help? Thanks in advance.


texts:
I have an NFA, and the question I am asked is :
Let  <  < . Now in simple English, express the language of the NFA to explain what type of strings are accepted by it.
In simple English, my answer is
The NFA accepts strings over alphabet {a, b, c} such that the last symbol appears twice.
Which I know is correct, however my problem lies in the question where "a < b < c". How does this affect my NFA and is my answer still correct? My answer seems really short for 6 marks.


texts: Find the minimal number of runs to visit every edge of a directed graph

texts:
I am looking for an algorithm to find a minimal traversal of a directed graph of the following type. Two vertices are given, a start vertex and a terminating vertex. The traversal consists of several runs; each run is a path from the start vertex to the terminating vertex. A run may visit a node more than once. The length of a traversal is the total number of vertices traversed by the runs, with multiplicity; in other words, the length of a traversal is the number of runs plus the sum of the lengths of the runs.

If there are edges that are not reachable (i.e. the origin of the edge is not reachable from the start vertex, or the terminating vertex is not reachable from the target of the edge), they are ignored.

To illustrate my needs, I give a simple graph and post the result, I would like to receive by the algorithm (start vertex $1$, terminating vertex $4$):

Graph edges:

$1 \to 2,3$
$2 \to 1,3,4$
$3 \to 4$

Result:

Run A: $1, 2, 1, 3, 4$
Run B: $1, 2, 4$
Run C: $1, 2, 3, 4$

Each edge (also each direction) has been covered. Each run begins with vertex $1$ and ends with vertex $4$. The minimum total number of visited vertices is searched. In the given example, the minimum number is $5+3+4=12$. There is no unreachable edge in this example.


texts:
Currently I'm working on my thesis. I'm writing about subgraph isomorphism problem and various algorithms, solving this problem. One of my task is to integrate that problem in a testing framework, developed by my mentor. It's some kind of universal framework, where you define a problem, implement some algorithms, solving the problem, perform some tests, analyze and compare different algorithms...

I've searched the web about similar frameworks, but I haven't found any framework, similar to the one described above. Is there really no such thing as universal framework to define some problem, run algorithms and analyse the results?


texts: What is tag-only forced cache inclusion called?

texts:
Is there a commonly accepted term for caches that are guaranteed inclusive with respect to tags but not data?

Inclusion can be helpful to simplify cache coherence, for which use only tags need to be included (avoiding the overhead of storing additional data). Is there a commonly accepted term for this kind of inclusion to distinguish it from inclusion that also replicates data?

I have used "tag-inclusive", but a professional (Mitch Alsup on the comp.arch Usenet newsgroup) used "virtually inclusive". (The former is more physically descriptive, but the latter has some conceptual attractiveness and might fit with the use of an approximate but conservative filter.)


texts: Complete $\mu$-recursive function that is not primitive recursive

texts: Could you find an example of a complete $\mu$-recursive function that is not a primitive function?


texts: Computer Scientific term for languages outside the Logic Programming paradigm

texts:
Is there a term for languages, imperative, declarative, procedural, functional alike; a term describing the quality of functions being represented as a (reversible) relationship between inputs and outputs? Or alternatively, where inputs and outputs are done away with in favor of just *puts, where any given *put can be used as either an input or an output at call site?

I feel that the term "non-logical", while also slightly misleading linguistically, doesn't really convey the idea explained in the previous paragraph quite well — it's not the quality of not being logical, nor the quality of being functional, imperative or whatnot, but the quality of how functions are represented and how the notions of input and output are unified, and the consequences of such guts-wide-open representations


texts: I'm coding a few set comparisons and noting their big O's using different algorithms and set implementations. I got to one particular function and I decided that it is $O(max(n,m))$ runtime. Is that the proper way to express this?


texts: Implementation/translation of the $s^1_1$

texts:
This is the Lisp code (from wikipedia) that implements the $s^1_1$ form of the $s^m_n$ theorem

(defun s11 (f x)
   (let ((y (gensym)))
     (list 'lambda (list y) (list f x y))))

since I don't know Lisp, can someone explain me what this code does and/or translate this code into other languages


texts: Time complexity of the travelling salesman problem (Recursive formulation)

texts:
According to this recursion formula for dynamic programming (Held–Karp algorithm), the minimum cost can be found. I entered this code in C ++ and this was achieved (neighbor vector is the same set and v is cost matrix):
recursion formula :
C(i,S) = min { d(i,j) + C(j,S-{j}) }

my code :
#include <iostream>
#include <vector>
#define INF 99999
using namespace std;
vector<vector<int>> v{ { 0, 4, 1, 3 },{ 4, 0, 2, 1 },{ 1, 2, 0, 5 },{ 3, 1, 5, 0 } };
vector<int> erase(vector<int> v, int j)
{
    v.erase(v.begin() + j);
    vector<int> vv = v;
    return vv;
}
int TSP(vector<int> neighbor, int index)
{
    if (neighbor.size() == 0)
        return v[index][0];
    int min = INF;
    for (int j = 0; j < neighbor.size(); j++)
    {
        int cost = v[index][neighbor[j]] + TSP(erase(neighbor, j), neighbor[j]);
        if (cost < min)
            min = cost;
    }
    return min;
}
int main()
{
    vector<int> neighbor{ 1, 2, 3 };
    cout << TSP(neighbor, 0) << endl;
    return 0;
}

In fact, the erase function removes the element j from the set (which is the neighbor vector)
I know about dynamic programming that prevents duplicate calculations (like the Fibonacci function) but it does not have duplicate calculations because if we draw the tree of this function we see that the arguments of function (i.e. S and i in formula and like the picture below) are never the same and there is no duplicate calculation.
My question is, is this time O(n!)?
picture :
If yes,why? This function is exactly the same as the formula and it does exactly the same thing. Where is the problem? Is it doing duplicate calculations?


texts: How can I calculate the maximum sum/product of sequence?

texts:
I am looking for an algorithm in $O(N^2)$ that finds the maximum value that be obtained from a sequence of real numbers greater than 0 (e.g. $\{ 1, 2, 3 , 4\}$) by inserting a plus ($+$) or multiplication ($\times$) between the elements.

Really not having much luck and wondering if anyone has any insight on this?

It must follow normal order of precedence.

For example with $\{1,2,3,4\}$, the maximum is $1+2\times3\times4 = 25$
not $1\times2\times3\times4 = 24$ and not $1\times2+3+4 = 9$.


texts: Turing machine - definition of program - naive question

texts:
In the paradigm of Turing machines what is considered a program?
Can't find a definition anywhere.
Is it a member of L(M)?


texts: Prove that every maximal flow yields the same minimal cut

texts:
Hi I'm trying to prove the following proposition:

Given a network $G,s,t,\omega$ where $\omega$ is the capacity, create a minimal cut cut  ${S=\left\{ (s,v)\in E_{G_{r\_max}}\right\} }$ where $G_{r\_max}$  is graph representing the the residual network(meaning we take the group of all vertices that are reachable from s in $G_{r\_max}$). So that the cut is $\left(S,V\backslash S\right)$.

Given two maximal flows $f_1\neq f_2$ prove that $\left(S_1,V\backslash S_1\right)=\left(S_2,V\backslash S_2\right)$ (which are defined in the above mentioned form for each maximal flow).

I've tried proving by assuming the contrary and saying that $S_1 $ is not subset of $S_2$.
Tried to say that this leads to $\exists \ v\in S_1 \ \ \mbox{s.t} \ \ v\notin S_2$.
Tried looking at the intersection and union of these groups but to no avail.

I'd appreciate some guidance\explanation as to how best prove this claim.


texts: Is there a recursive problem encoding the Turing completeness of a model of computation?

texts:
Suppose we have a model of computation $C$ we want to show to be Turing complete. The usual strategy would be to emulate within $C$ any model of computation we already know to be Turing complete (e.g. an arbitrary Turing machine). On the other hand, a model of computation is Turing complete if and only if it can compute (the indicator function of) all recursive sets. Is there a special recursive set $S$ (or finite subset of recursive sets) so that it is enough for $C$ to compute $S$ to assure that $C$ is Turing complete? Informally, $S$ would be a set for whose computation branching, looping and memory are all needed in an unavoidable way. If such sets do exist, which are the simplest ones?

In a practical sense, the utility of these sets would be the following test: if your model of computation can solve this type of (e.g. numerical or geometric) problem, then it is Turing complete.


texts: Contrasting Peterson’s and Dekker’s algorithms

texts:
I am trying to understand the algorithms by Peterson and Dekker which are very similar and display a lot of symmetries.

I tried to formulate the algorithms in informal language like follows:

Peterson's: "I want to enter."                 flag[0]=true;
            "You can enter next."              turn=1;
            "If you want to enter and          while(flag[1]==true&&turn==1){
            it's your turn I'll wait."         }
            Else: Enter CS!                    // CS
            "I don't want to enter any more."  flag[0]=false;

Dekker's:   "I want to enter."                 flag[0]=true;
            "If you want to enter              while(flag[1]==true){
             and if it's your turn               if(turn!=0){
             I don't want to enter any more."      flag[0]=false;
            "If it's your turn                     while(turn!=0){
             I'll wait."                           }
            "I want to enter."                     flag[0]=true;
                                                 }
                                               }
            Enter CS!                          // CS
            "You can enter next."              turn=1;
            "I don't want to enter any more."  flag[0]=false;

The difference seems to be the point where "You can enter next." occurs and the fact that "if it's your turn I don't want to enter any more." occurs in Dekker's.

In Peterson's algorithm, the two processes seem to be dominant. A process seems to force his way in into the critical section unless it's the other one's turn.

Conversely, in Dekker's algorithm, the two processes seem to be submissive and polite. If both processes want to enter the critical section, and it's the other one's turn, the process decides to no longer want to enter. (Is this needed for starvation-freedom? Why?)

How exactly do these algorithms differ? I imagine that when both processes try to enter the critical section, in Peterson's, the process says "I enter", while in Dekker's the process says "You may enter". Can someone clear up the way the processes behave in each algorithm? Is my way of putting it in informal terms correct?


texts: Higher order verification in a complete logic

texts: I'd like to design a language that is able to reason over itseslf, means, able to get as input a code in that language (that might have went through some external redundant preprocessing, or "reflection" if to use another term) and reason over it. MLTT is of course a natural choice. But I'm seeking for a logically complete language, obviously sacrificing expressiveness (in fact it must not be able to express arithmetic, otherwise by Godel or more directly by the mortal matrix problem or Hilbert's 10th problem it cannot be complete). Therefore as first candidadte I thought of MSO over graphs. My question is how can MSO over graphs reason over itself, or more precisely, if we had a prolog-like (kb&query) language in MSO over graphs logic, how could it interpret or compile itself (and as a byproduct also reason over itseslf)?


texts: Why analysis of Aloha protocol uses Poisson distribution?

texts: Pretty much in all of the analysis of the Aloha protocol that I read, it is assumed that the distribution of packet arrivals is Poisson. What is the rationale behind it? Isn't it actually binomial distribution that is approximated by Poisson because $n$ (number of users) is large and $p$ (transmission probability) is close to zero?


texts: How to create RGB-colors with equal vector norm?

texts:
I am trying to do the following:

Interprete RGB color values as a 3-D vektor
Transform the RGB color into polar coordinates L, teta and phi
Create colors with constant L

The math behind this is the standard transformation into spherical coordinates:

b = L * Sin(teta) * Cos(phi)
r = L * Sin(teta) * Sin(phi)
g = L * Cos(teta)

With L beeing the norm of the RGB vektor I want to create.

L=(r^2+b^2+g^2)^0.5 'between 0 and 441.67 = sqrt(3)*255

So far so good. Onto the first issue: r,g and b need to be between 0 and 255

This means that this holds true (I calculated that myself, it's possible that it has errors in it):

If L>255 Then
   arccos(255/L) < teta < pi/2 - arccos(255/L)
   arccos(255/L) < phi < pi/2 - arccos(255/L)
End If

Here my calculations:

The idea is that teta goes from (pi/4 - delta) to (pi/4 + delta) where
Which basically means that teta and phi are restricted in what they can be according to the ratio of 255/L. This restriction gets upto a point were L=441.67 the maximum length. Here phi and teta can only be pi/4.

I think upto this points my conclusions are valid, but there is a problem I cannot figure out.

If phi = teta = pi/4 and L = 441.67 the RGB value should be (255,255,255) and the forumlas above yield: RGB= (221,255,221)

Which is what the forumlas for r,g and b above yield if phi = teta = pi/4 and L = 441.67 are inserted.

So how would one generate RGB vektors with a constant norm that are still valid RGB values? (0 < r,g,b < 255)


texts: Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset

texts:
I am working on a problem defined as the following
Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our resources and $G$ is our necessary minimal reward, is there a set $R' \subseteq R$, so that $\sum_{(z,g)\in R'}z \leq Z$ and $\sum_{(z,g)\in R'}g \geq G$?
I want to show its NP-completeness and have shown that it is in NP already. I am struggling with the NP-hardness. My known NP-hard problems are the SAT, 3SAT, partition, subset sum and bin packing.
My struggle seems to be mostly with the fact that we have to balance two different values now, the cost and the reward. This is not the case in any of the set related problems I mentioned and I am unable to think of how to model this in SAT or 3SAT. What am I missing here? How can I show the NP-hardness and as such the NP-completeness of this problem using only these given problems?


texts: Kleene star of an infinite unary language always yields a regular language

texts:
Let $L = \{a^n \mid n \ge 0\}$, where $a^0 = \epsilon$ and $a^n = a^{n-1}a$ for all $n \ge 1$.

Thus $L$ consists of sequences of $a$ of all lengths, including a sequence
of length $0$. Let $L_2$ be any infinite subset of $L$. I need to show there always exists a DFA to recognize $L_2^*$.

If $L_2$ is a finite subset it is very obvious as $L_2$ would be a DFA and hence by Kleene closure $L_2^*$ would be recognized by a DFA. But I am unable to get it for infinite subset as $L_2$ may not be expressed as DFA when, e.g., string lengths are prime.


texts: Which algorithms can not be parallelized?

texts:
Is there any algorithm which is very difficult to parallelize or the research is still active?

I wanted to know about any algorithm or any research field in parallel computing.

Anything, I searched for, has a 'parallel' implementation done. Just want to do some study on any unexplored parallel computing field.


texts: How can a probability distribution across classical states be computed for the measurement of a Quantum State represented by a Complex Vector?

texts:
Suppose I have a quantum state represented by a Complex vector, arbitrarily:

$[~-0.538, 0.044 - 0.323i, 0.706, 0.044 + 0.323i~]$

With each value in that vector corresponding to some classical state:

$[~ |00\rangle, |01\rangle, |10\rangle, |11\rangle ~]$

What is the correct mathematical formula to derive a probability distribution across possible classical states that could be observed in measurement from this complex vector?

E.g. how do I find individual real values for $p(|00\rangle)$, $p(|01\rangle)$ etc. in this example?


texts: Proof that a language involving $gcd$ is not context-free

texts:
How would you prove that the following language is not context-free?

$$ L= \{a^n b^m |\, gcd(n,m)=1 \}$$

I suspect the solution uses the pumping lemma, but I'm not sure how to apply it.


texts: Finding minimum path in a matrix algoritm

texts:
I'm looking for an algorithm that do the following thing.

Given $n$ the number of rows and columns of a matrix of positive integers.

Given $(x_1,y_1)$ the starting coordinates.

Given $(x_2,y_2)$ the ending coordinates.

and $k$ an integer.

This are some rules of how you can travel through the matrix:

When stepped in some coordinate $(x,y)$ with a given value $w$, you can travel to $(x \pm w,y)$ or any value between this range or $(x ,y \pm w)$ or any value between this range.
Also you can spend the integer $k$ in order to travel a little further in a row or a column. For example with $k=4$ you can travel to $(x ,y + w + 3)$ spending $3$ of your $k$. In this case, now you only have $k=1$ to spend.

The objective here is find the minimum path between $(x_1,y_1)$ and $(x_2,y_2)$.

I already implemented an algorithm that do this in $O(n^3k)$, the problem it's that given the implementation it's very difficult to justify its correctness.

How would you resolve this problem in a way that is easily shown it's correctness?


texts: Why is $\sum_{j=0}^{\lfloor\log (n-1)\rfloor}2^j$ in $\Theta (n)$?

texts:
I am trying to understand summation for amortization analysis of a hash-table from a MIT lecture video (at time 16:09).

Although you guys don't have to go and look at the video, I feel that the summation he does is wrong so I will attach the screenshot of the slide.


texts: Can the compiler convert recursive algorithm into a dynamic programming

texts:
So I was going through the idea behind dynamic programming (memoization), and thought of this question.

Can a compiler convert any recursion into a table filling DP solution, of course given the hint(like some keyword or macro) from the programmer that the following recursive function can be solved with DP (so programmer knows that it exhibits overlapping sub-problems and optimal substructure)?

If it's possible why don't many of them have it, if there exists anyone that does?


texts: How to estimate the average time complexity of greatest common divisor?

texts:
As we know, the time complexity of $\gcd(x,y)$ is $O(\log \min(x,y))$ by using Euclidean algorithm. Now we fix a constant $n$ and consider the average time complexity of $\gcd(x,n)$.

Formally, let $f(x)$ be the number of divisions when calculating $\gcd(x,n)$. How to give a bound of $\frac 1 n \sum_{x=1}^n f(x)$?

I don't konw whether it is strictly $o(\log n)$ or $\Theta(\log n)$. How to prove the bound?

I list some of $n$ and the coresponding value here.

$n$ ; $\frac 1 n \sum_{x=1}^n f(x)$
1000;6.42;
10000;8.34;
100000;10.26;
1000000;12.20;
10000000;14.13;
100000000;16.07;


texts: Equivalence of two lambda expressions for NOT

texts:
I've seen two different lambda expressions for the logical NOT function.
One of them just applies its parameter to constants true and false internally in a reverse order:

$NOT \;\;=\;\; \lambda x.\; x \; \mbox{false}\; \mbox{true} \;\;=\;\; \lambda x. \; x \; (\lambda t.\lambda f.f) \; (\lambda t. \lambda f. t ) $

and the other one which captures two more parameters instead of passing them to the returned function externally, and applies $x$ to them in reverse order too:

$NOT \;\;=\;\; \lambda x. \; \lambda t.\lambda f.xft$

of which the other one seems a bit simpler (and it is also simpler when encoded in binary).

So my question is this:
Is there any transformation which could get me from one of these representations to the other?

I see they are equivalent "extensionally", that is, both produce the same results. But I'd like to "prove" it somehow by algebraic transformations, such as those for alpha, beta and eta conversions. Unfortunately, none of these can help me in this case: Alpha is just for renaming. Beta works only for function calls, but we don't have any function call here which could be reduced, since $x$ is free in the function body (not the whole expression, though) in all these expressions until we actually call NOT on something. The most close one seems to be the eta, which is related to extensional equivalence and forwarding parameters, but when the parameters are being reversed, it's not a simple forwarding anymore and eta doesn't seem to apply here.

Is there any more conversion rule I'm missing?
(Well, I guess they won't just skip two Greek letters from no particular reason, wouldn't they?)

P.S.: This question is actually a model one, since there are many other definitions for other functions which have several different forms which seem to be extensionally equivalent, but completely different with regard to the known reduction rules. I've chosen the simplest example of this problem.

Edit:
To better clarify what I'd like to know, here's a diagram showing the reduction steps for both versions of the not function:
http://sasq.comyr.com/Stuff/Lambda/Not.png

As you can see, they really both reduce to the same results (contrary to what @Jonathan Gallagher was saying below). This is what I already know: that they are confluent, and so they're Church-Rosser equivalent. What I don't know however is if there is any conversion rule (similar to alpha, beta & eta) which could allow me to transform one form of not to the other. This would allow me to at least make sure if some other functions (more complicated than these two here), are also equivalent, which could be hard when they can reduce to more than just two possible answers. I'd like to know if there's some conversion rule which could allow me to convert one intensional definition into another when two functions are already extensionally equivalent (i.e. they give the same results for the same parameters). Or (which would be better) if some function can be converted somehow to the other even if I don't know whether they're extensionally equivalent.


texts: Does the intersection of VC and CLIQUE belong to NPC?

texts:
Define: $$L=\{(G,k) :  G\text{ has a vertex cover of size at most $k$, and a clique of size at least $k$}\}$$

I need to determine whether $L\in \mathrm{NPC}$ or $L\in \mathrm{P}$. I suspect that $L\in \mathrm{NPC}$, been trying to prove it by looking for a reduction from Vertex Cover, but couldn't find one.


texts: How to understand out of bound in the following theoretical context?

texts:
Consider the following initialization step of loop invariant for merge procedure

Initialization: Prior to the first iteration of the loop, we have
$k=p$, so that the subarray $A[p .. k - 1]$ is empty. This empty subarray contains the k- p= 0 smallest elements of $L$ and $R$, and since
$i = j = 1$, both $L[i]$ and $R[j]$ are the smallest elements of their arrays that have not been copied back into  $A$.

I have doubt in the above statement that if $k=p$, then array $A[p..p-1]$ is impossible and hence the further argument cannot proceed, which didn't happen. Where am I going wrong?


texts: Can someone interpret what this is asking for

texts:
I have this programming problem, but I really cant figure out what it wants me to do. Heres what it is:

  The cube root of a number can be found based on the observation that, if $t$ is an approximation of the cube root of $a$, then $\tfrac13\left(\tfrac{a}{t^2} + 2t\right)$ is a better approximation.

  Create a method double betterCubeRoot(double a, double t) that will find the cube root of $a$ accurate enough so that the difference between $t^3$ and $a$ is less than 0.0001. Use recursion.

  Then write the method double cubeRoot(double a) that makes use of the method with 1 as the initial value of $t$. Write a program that will test values both positive and negative.

Can someone please explain what this means. I dont understand how I am supposed to find the cube root of 'a' using the given equation. Thanks.

Here is what i have done:

public static double betterCubeRoot (double a, double t)
{
    double tCubed = Math.pow (t, 3);
    double dif = Math.abs (tCubed - a);

    double eq = ((a / (t * t)) + 2 * t) / 3;

    if (dif < 0.001)
    {
        return eq;
    }
    else
    {
        return betterCubeRoot (eq, t) ;
    }
}


texts: Are comparison sort algos appropriate for SUBJECTIVE sorting?

texts:
I've been tasked with creating an online feature that ranks 50 fantasy characters from a variety of domains based on combat acumen and polls users one which one is the most powerful based on their votes on a series of face-to-face matchups. (Spiderman vs. Jon Snow, etc. etc.). If this is designed well, we hope to attract a large audience and high participation.

My first instinct was to use some variety of comparison sort--probably Bubble or Heap, given the manageable size. But as I brush up on the mechanics, all the literature I can find seems to be oriented toward stochastic sorts in which any pair of items can be definitely compared.

Another curveball here is that, as more people participate, the ordered list can (but needn't mustn't) be informed by all the people who have already weighted in. This will probably be necessary since we can't expect every user to weigh for hundreds of matchups. I'm not clear on how to tell the algorithm which items are already somewhere near their appropriate place in the list thanks to a lot of preexisting votes.

I'm sure I'm not the first to confront this issue since comparison algos are commonly used exact crowd wisdom on the best of, say, a few dozen photographs. I'm just not quite sure where to start. Am I looking for a variation on comparison sort with some addition search phrase for Google, or a different approach entirely?

Thanks![Insert favorite fantasy sign-off.]


texts: What is the maximum number of indices one can create on a table with N columns?

texts: Say, I have a database table with $N$ columns. What is the (theoretical) maximum number of indices I can create on that table? For $N = 1,2,3$ it's easy enough to calculate the answer $(1, 4, 15)$, but is there any formula? Also, is there a "name" for this number?


texts: Time complexity of proximity search in distance matrix

texts:
I am a high school student computationally studying the 3-dimensional structure of chromosomes by 40 kilobase loci. In a nutshell, loci that are close in space tend to express their genes at the same time ― loci are different stops on a 3D-winding DNA chain.

The best way to understand the 3D structure is by gathering what are basically distances between loci.

Now I have an $n\times n$ ($n$ = number of loci studied) matrix where the $(i,j)$ entry is the distance between locus $i$ and locus $j$. I also have a (somewhat miraculous) 3-dimensional of the same chromosome that maps each locus to a certain point in a 3D $(x,y,z)$ coordinate system.

My task is to find all of the loci within a certain radius of locus $L$. With the matrix, I would have to go to $L$ and traverse many nearby locus-distance chains, possibly for a long time, before being any bit certain that I had everything I wanted (i.e. brute force). With the spatial model, I would only have to conduct a simple search within that radius.

Here is my question. What is the complexity of finding nearby loci in the 3D model and the 2D matrix with respect to loci count and radius size (whichever you think is more complex)? (Compare the two complexities and give both.)

I am not very studied in CS, but here is what I guess:

$$C_\text{2D search best-case} = O(n^2)$$
$$C_\text{2D search worst-case} = O(2^n)$$

Best-case is what you'd expect, and worst-case would be going through every permutation of the distance.

$$
C_\text{3D search any case} = O(n)
$$

This is just my rather fallible intuition.


texts:
We have two sets of vectors of positive numbers, $X$ and $Y$ where for
$x\in X$ we write $x=(x_1,x_2,\ldots,x_k)$ and similarly for $y\in Y$
we write $y=(y_1,y_2,\ldots,y_k$).

We are given two vectors $l=(l_1,l_2,\ldots,l_k)$, and
$u=(u_1,u_2,\ldots,u_k)$ such that $l_i\le u_i$ for all $i$.

We want to find all pairs $(x,y)$, $x\in X$, and $y\in Y$ such that
$l_i\le x_i+y_i\le u_i$

Handwaving a bit, we can do this in a divide and conquer sort of way,
separating each set into pieces that are larger and smaller than
$l_i/2$ and throwing away the pairs where both are in the smaller
half.
This gives a recurrence
$$T(m,n) = T(m,n/2) + T(m/2, n/2) + c(m+n)$$
where $m=|X|$ and $n=|Y|$.  For equal size sets, this gives
$T(n,n) = O(n^{1.7})$, which is better than quadratic, but less than I
would hope for.

A similar question could be asked for three or more sets.


texts:
A k-query oracle Turing machine can query its oracle for at most $k$ times. How could I show that assuming $\text{NP} \not= \text{coNP}$, we have $\text{NP} \cup \text{coNP} \subsetneq \text{P}^{\text{SAT},1}$ (query only once)? I tried to show this strict inclusion directly or its counterexample but to no avail... There was such a question on this site, but the top vote isn't a direct answer. Could somebody provide me more insight into this again? Thanks!
More specifically, I wonder how should I think of these $k$-query machines from machines with unlimited number of queries. I can see that they should have limited computation power, but I'm not sure how to utilize that for the proof.


texts: Why every finite language is polynomial?

texts: I understand that it's possible to build TM that check all the finite number of cases, so it's definitely in $R$, but I'm not sure why it's in $P$


texts: Maximising a particular colour in a vertex colouring

texts:
I'm looking for a paper that discusses the maximising of one colour in a vertex colouring.

Suppose that for an unweighted, undirected graph $G=(V,E)$ we define a vertex colouring as a function $c : V\to\mathbb N$ (where we use $\mathbb N$ for the colours). I would then like to maximise $\#\{v\in V\mid c(v)=n\}$ for particular $n\in\mathbb N$. The algorithm should return the size of the largest set of vertices that can be coloured with the same colour.

Has there been any literature on this topic?


texts: Non-Parametric Methods Like K-Nearest-Neighbours in High Dimensional Feature Space

texts:
The main idea of k-Nearest-Neighbour takes into account the $k$ nearest points and decides the classification of the data by majority vote. If so, then it should not have problems in higher dimensional data because methods like locality sensitive hashing can efficiently find nearest neighbours.

In addition, feature selection with Bayesian networks can reduce the dimension of data and make learning easier.

However, this review paper by John Lafferty in statistical learning points out that non-parametric learning in high dimensional feature spaces is still a challenge and unsolved.

What is going wrong?


texts: Minimum spanning tree classification problem with adjacent neighbors

texts:
I am new to minimum spanning trees. But have used the last few days on a problem I think matches MST, but cannot really figure out the connection.

The problem is a minimum cost problem where N ordered sections 1...N all need to be connected. I.e. section N_k needs to be connected to it's adjacent neighbors N_k-1 and N_k+1. The cost function of connecting it to each of the neighbors depends on the value of N_k-1 and also whether or not N_k-1 is already connected to N_k-2 and in that case also the value of N_k-2...

Can anyone direct me to a programming example of a similar problem?


texts: Minimizing total distance traveled by points in points cloud transformation

texts:
I have a point cloud of size n (in the example on picture n = 5). The starting coordinates are in green, destination coordinates are in red. What I need is to move the points from the starting coordinates to the destination ones so that the total distance, traveled by all points is minimal.

There is one important restriction - points' trajectories should not intersect (so, trajectories could be curvy). To handle this, we may introduce some ε to denote the minimum distance between two trajectories, after which they will be considered intersecting.

Non-intersecting trajectories can be changed in favor of non-colliding points (the distance between several points can't be smaller than ε at the same moment of time) if that makes the task easier to solve (if not - let's stick to the original conditions). In such a case maximum point speed, V, should be introduced.

More than 2 points may lay on a line (e.g. 2 starting points and 2 destination ones may be collinear).

For the particular case described at the picture, the minimal path will look like A -> F + B -> G + C -> H + D -> I + J -> E.

Solutions that came to my mind:

The greedy approach will not work, because if we start from point A
and choose the nearest destination point, we'll end up with E
moving to F, which is far from being optimal.
Brute dynamic programming solution will result in something like O(n!) complexity, which is not really acceptable.

None of those solutions save me from intersecting trajectories.

My gut tells me, that some kind of gradient descent may be useful for this task, but I can't figure out how to apply it to this task.

What I need is not a working code, but advises or directions to related topics/articles/papers which will help me to understand how to solve this task.

P.S. I saw Assign m agents to N points by minimizing the total distance and Given 2 sets of n points: minimize sum of traveled distances but wondered how this task can be handled after the introduction of the aforementioned trajectory-related restriction.


texts: Circles covering a rectangular, how to verify it?

texts:
This may be basic to some of you, but excuse my inexperience with comp. geometry:

Given a set of $n$ circles with centers $(x_i, y_i)$ for $1 \leq i \leq n$  and each having radii $r$. Also given a rectangle. All objects are on a plane. How to verify that every point inside the rectangle (including its edges) is fully covered by the circles. That is, each point in the rectangle lay on at least one of the circles.

Anyone have hints ? I am currently trying with voronoi diagrams.


texts: Why does this Pumping Lemma example show irregularity?

texts:
the first 4 steps of these are my own work - however the following steps are from my book, and I don't understand what it's saying, and I have not found any resources. Could someone clarify this?

Show C = {w|w has an equal number of 0s and 1s} is not regular. Show by contradiction.

1) Assume C is regular, and thus the Pumping Lemma conditions hold.

2) Assume a pumping length of p.

3) Let the string s = $0^p$$1^p$.

4) s = xyz and let x and z be the empty string. Therefor for i > 0, x$y^i$z always has an equal number of 0s and 1s, so it seems like it can be pumped.

5) But since condition 3 of the pumping lemma says that |xy| <= p, then y must consist of only 0s.

How does step 5 justify y consisting of only zeros? If we said ealrier that x and z are the empty strings, then doesn't that imply that s = y = $0^p$ $1^p$?

How does this make y only zeros?

Thanks!


texts:
Both convolution and linear block codes can be used for error correction. The main benefits I gathered from using convolutional codes is that, it's easy to implement and does better (than linear codes) in cases where you have higher error probability rates and noisy channels. Information bits are spread along the sequence. Lastly, these codes have memory.

However, linear block codes, especially the newer ones such as polar code, can actually achieve the channel capacity. And, in block codes, information bits are followed by parity bits and code information in blocks. Lastly, they are memory less.

How exactly can a noisy channel contain "memory?" I've read some articles,
    but would like some more clarification. Right now, I am under the impression that, if we find that an error occurs, with much higher frequency, on the  4th bit, for example, then we shall have some redundancy bit at that location, so no real information is lost. So that when we decode, we simply ignore the 4th bit. Am I right in my understanding?


texts:
I am trying to generate models for the following sequent.

$$\exists x \exists y \forall z (z = x \lor z = y)$$

What I have come up with is this.

$$A= \{0,1\}$$

So in this model, for all the values of $z$ there exists $x$ such that $z = x$ or there exists $y$ such that $z = y$. Is this model correct? What other models are there that satisfy this?


texts: Running time and stack depth of a lisp recurrence

texts:
Consider the following sequence $a_n$:

\begin{align*}
  a_0 &= \alpha \\
  a_k &= \beta a_{k-1} + \kappa
\end{align*}

Now consider the implementation of this sequence via lisp:

(defun an (k)
  (if (= k 0) alpha
    (+ (* beta (an (- k 1))) kappa)))

What is the running time to compute (an k) just as it is written? Also, what would be the maximum stack depth reached? My hypothesis would be that both the running time and stack depth are $O(k)$ because it takes $k$ recursive calls to get to the base case and there is one call per step and one stack push per step.\
.

Is this analysis corect?


texts:
Possible Duplicate:
  Language of the values of an affine function

Let $C_n = \{x\mid x \text{ is a binary number that is a multiple of } n\}$. Show that for each $n$, the language $C_n$ is regular.

Just provide a generic recipe (i.e., a formal definition for arbitrary $n$).


texts: recursion code counting down and counting up

texts:
My apologies in advance if this is going to cause further confusion.  So, I wrote a very simple recursive method shown below. As you see line # 3 keeps track of value of n before recursive call and line # 5 keeps track of n after recursive call. As you can see both lines # 3 and 5 are printed to see the change in n value. I am puzzled why line 5 is printed in increments of one six times where n value goes from 0 to 5 as the unexpected (to me) output shows: "after: n: 0" ... "after: n: 5".

1    def countdown(n)
2      return n if n == -1
3      p "before: n: #{n}"
4      countdown(n-1)
5      p "after: n: #{n}"
6    end
7
8    countdown(5)

Output:

"before: n: 5"
"before: n: 4"
"before: n: 3"
"before: n: 2"
"before: n: 1"
"before: n: 0"
"after: n: 0"
"after: n: 1"
"after: n: 2"
"after: n: 3"
"after: n: 4"
"after: n: 5"


texts: $L = \{\alpha^i \beta^j \gamma^k \vert i,j,k \in \mathbb{N}_0, (i=1) \Rightarrow (j=k)\}$

texts:
I am asking this question here, because I am not allowed to comment on the thread that I am actually interested in, but maybe someone can still help me?

I alredy found an anwser to the Problem above (in the post linked to this question), but I still don't understand, why I can't just use that one case $s = \alpha \beta^p \gamma^p$. I can show for that case, that it doesn't fit the pumping lemma for regular languages. Isn't the point of condratiction, that I have to find just one case that doesn't fit the hypothesis?

Actually I am not even supposed to use the pumping lemma, but the definitions of closure for regular languages. And that is where I started with $(i=1) \Rightarrow (j=k) = i \neq 1 \vee j = k$. And then I wanted to use the properties of closure, like in the first anwser in the post I linked.
(I was also thinkg of using a regular expression? It seemed easier)
But if I can't just find that mentioned one word to proove the language not regular (without the PL)? I am confused.
I hope it makes sense. I am genuinely interested in understanding this problem.

Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$


texts: Prove that two different concatenations of relations are equivalent

texts:
I've had this question on my exam today and I couldn't figure it out, I would like to know the answer.
The question:

Given relations $R$, $S$ on a set $U$.
$R$ is transitive, $S$ is reflexive.
Prove that $(R;S;R)^2$ is a subset of $(R;S)^3$.

Partial answer of mine:

By using associativity you get an equivalent question of:
Prove that $R;S;R;R;S;R \subseteq R;S;R;S;R;S$.
By monotonicity you have that $R;S;R \subseteq S;R;S$.
Then I took $(x, y) \in R;S;R$, so there exist $a, b \in U$ such that $xRa \land aSb \land bRy$.
Now I need to conclude that $xSa \land aRb \land bSy$.

Here I am stuck, nowhere I see how I should be using that $R$ is transitive and $S$ is reflexive, and I know they are obvious hints. I tried using them directly, proving by contradiction, but I am just stuck.


texts: Approximate dot product between neural network output layer's parameter vector and input activations with winner-take-all hashing

texts:
In the paper Deep Networks with Large Output Spaces, Vijayanarasimhan et al. describe their approach to approximating the dot product between a neural network's output layer's parameter vector and input activations with winner-take-all hashing. I'm trying to grasp the main idea described in the following paragraph:

  Our main idea is to approximate the dot product between the output layer’s parameter vector and the input activations using hashing. We first compute binary hash codes for the parameter vectors, $W$, of a layer’s output nodes and store the indices of the nodes in locations corresponding to the hash
  codes within hash tables. During inference, given an input activation vector, $x$, we compute the hash codes of the vector and retrieve the set of output nodes $O_k$ that are closest to the input vector in the hash space. Following this we compute the actual dot product between $x$ and the parameter vectors of $O_k$ and set all other values to zero.

I understand that only the most relevant vectors are being retrieved from the hash thus allowing less dot products. Yet the details are still unclear to me.

Why are indices of nodes stored?
Why are said indices stored in locations corresponding to the hash codes within hash tables?
If the binary hash codes are first computed for the the parameter vectors $W$, why is the hash of the activation vector $x$ computed during inference? How do these relate?
Given the previous step, a set of output nodes $O_k$ is retrieved. Aren't the relevant weight vectors in $W$ what should be retrieved?

Adding a reference to the paper which introduced the WTA hash The Power of Comparative Reasoning


texts:
According to this source, Chaitin's constant $\Omega$ is normal.

  Each halting probability is a normal and transcendental real number that is not computable, which means that there is no algorithm to compute its digits. Indeed, each halting probability is Martin-Löf random, meaning there is not even any algorithm which can reliably guess its digits.

Source (Wikipedia)

Furthermore, the definition of normal is that each digit occurs with equal probability $1/b$. And that each duets of digits occur with $1/b^2$ probability and every triplets occurs with probability $1/b^3$ and so on.

Chaitin's omega is calculated via

$\Omega = \sum_{p \in halts} 2^{-|p|}$

Writing $\Omega$ in binary, we obtain a list of 0 and 1. For example,

2^-1=0.1 +
2^-2=0.01 +
2^-3=0.001 +
~skip 2^-4 as it does not halt
2^-5=0.00001 +
...
=\Omega
=0.11101...

Clearly, we can see that the position of each bits corresponds to the halting state of the program of length corresponding to the bit.

Here is what I am struggling with

If $\Omega$ is indeed normal, then it means that exactly 50% of programs halt and exactly 50% do not. This seems very counter intuitive.

For example, suppose I generate java programs by randomly concatenating single characters. The majority of them, I would guess more than 99.99% would not even compile. Would this not imply that at least 99.99% of them will not halt? How do we justify that exactly half will halt and exactly half will not, by virtue of $\Omega$ being normal.

Or is wikipedia incorrect about $\Omega$ being normal?


texts: Given a PRAM may use arbitrarily many processors, why is Hamiltonian Cycle not in NC?

texts:
In my parallel algorithms class, the PRAM model is described as having an "arbitrary number of processors, bounded by some polynomial in the input size."

I think that this may be missing a constraint.  For example, this would imply that finding a Hamiltonian cycle is in NC:

If I give all of the permutations of the vertices of a graph as input,
then I can assign a processor to each permutation, and each processor can
then check for the appropriate edges in O(|E|) time, which would mean that
finding a Hamiltonian cycle would be in NC.

So is there some constraint that is missing from the definition we are using in class, or am I missing something else?

Edit

For clarification:  Consider a classical TM, which accepts as input a sane representation of a graph, followed by all of the permutations of a graph's vertices.  It then performs the best currently known algorithm for finding Hamiltonian Cycles, and as output writes out a permutation of the vertices describing such a cycle.

The algorithm would perform in time linear in the input size, but in time factorial in the order of the input graph.  (The extra inputs don't seem to count as computations for a classic TM.)

In the PRAM model (as I have described it), the algorithm would perform in time linear in both the input size, and in the order of the graph.  (The extra inputs seem to count as computations for the PRAM model...  Which makes me think that "computation" means something subtly different here...)

If this is the way it is supposed to work: awesome.  If not, than am I missing some constraints on what the allowed inputs are?


texts: Linear Regression using a Neural Network

texts:
I am trying to create a regression model using a Neural Network. I am currently learning how to work with neural networks (deeplearning.ai) and so the model is not implemented using any existing frameworks like keras.

Based on what I have learned,

the model is configured to use no activation function in the output
layer (which, obviously, has only one node).
Input is images of fashion articles (shirt, jackets etc).
output predicts prices for input article images.
Hidden layers all use ReLU.
Random initialization is done for all weights.
Cost function is Mean Squared Error:
$$J = \frac{1}{2m}\sum_{i=1}^m (a^{(i)} - y^{(i)})^2$$

Based on the formula for backpropogation, the last layer should get the error based on cost function. For a single example, we have:
$$ \mathcal L =  \frac{1}{2}(a - y)^2 $$
$$ error = \frac{d\mathcal L}{da} = (a - y) $$

where L is the loss function, a is the predicted value and y is the actual price of the article.

For the entire training set, we have (vectorized):
$$ error = \frac{d\mathcal L}{dA} = (A - Y) $$
where m is the number of examples,  A, Y are (1 * m) vectors where each value corresponds to each single example. A contains m predictions and Y has all the m prices.

Is this error value correct?

My problem is that the model converges to a what appears to be a local minima. The error after a few 100 iterations gets stuck. The error is also not very small (~ 0.0005). I am not sure if I have the equations right.


texts: Are there quantum algorithm that solve the boolean satisfiability problem in subexponential time?

texts: Are there quantum algorithms that solve the boolean satisfiability problem in subexponential time? Do they just give a determination as to whether an expression can ever evaluate to true, or can they also tell which input will cause the expression to evaluate to true?


texts: Proving $L = \{\langle M, w, n \rangle$ : $M$ accepts $w$ within $n$ steps $\}$ is decidable

texts:
Show the following problem is decidable: Given $w\in \Sigma^{*}$, $n\in \mathbb{N}$, and a Turing machine $M$, does $M$ on $w$ halt within $n$ steps.

My Thoughts:

I am new to proving results like these with Turing machines, so I'm often not sure what is "legal" or "not legal" with a Turing machine. For example,
my textbook often gives "high level" descriptions of Turing machines doing a computation instead of formally step by step. This is the way we are expected to describe Turing machines in class, but it often leaves me unsure if I'm being rigorous enough in my description.

My Attempt:

Construct a Turing machine $M'$ the following way:

$M'$ = "On input $\langle M,w,n \rangle$:

(1) Represent $n$ on the tape by $n$ consecutive $1$'s

(2) Simulate $M$ on $w$

(3) Each "execution" of the transition function is followed by a mark on one of the $1$'s

(4) If $M$ enters an accepting state, accept; Otherwise, reject if $M$ enters a rejecting state or after all of the $1$'s are marked."

My main concern is step (1) of the algorithm. I'm really unsure if that can be done. I'm also not sure how $n$ is represented as a string for the input $\langle M,w,n \rangle$. Am I able to choose how it's encoded?

Thank you for your time and feedback.


texts: Relaxations for MILP with logical constraints

texts:
I have an LP with a (non-fixed) number of logical constraints in the form of $X_1 \rightarrow X_2$ (where $X_1$ and $X_2$ are linear functions inequalities of the $n$ input variables). To express these logical operations I introduce binary variables (as in here) $\gamma_1$, $\gamma_2$ so I end up with a Mixed Integer Linear Program that looks something like this:

$$
\begin{equation*}
\begin{aligned}
& \underset{x, \gamma}{\text{minimize}}
& & c^T \mathbf{x} \\
& \text{subject to}
& & X^i_{1} \leq \gamma^i_1, \;  i \in [n], \\
&&& X^i_{2} \leq \gamma^i_2, \;  i \in [n], \\
&&&  \gamma^i_1 \leq \gamma^i_2,  \;  i \in [n], \\
&&& \gamma^i_1, \gamma^i_2 \in \left\{ 0,1\right\}, \;  i \in [n] \\
&&& \mathbf{x} \succeq 0
\end{aligned}
\end{equation*}
$$

I know these types of problems can be solved well in practice using a wide range of heuristics, but I am interested in a provably efficient algorithm for approximating this problem.

I don't see why the LP relaxation of this MILP (obtained by only asking that the $\gamma$'s be in $[0,1]$) gives me anything: unlike classic examples like Set Cover, is it clear how to obtain a feasible solution (integral) to the original problem from a solution to the LP relaxation? A rounding approach seems useless here, because I can do whatever I want to the values of $\gamma$, but that doesn't actually effect the solution $\mathbf{x}$. If I can't "translate" a solution to the LP to an integral solution, how can I say anything about the integrality gap?

My questions:

Am I correct in that for this particular type of MILP (resulting from logical constraints), the LP relaxation is useless?
Is there any other approach which I might be able to use to say something about the ability to approximate my problem?

I have very little background in approximation algorithms so I would really appreciate any pointers. I hope the question is clear and made sense. Thanks!


texts:
Pseudocode:

if n < 2
    return false
while n != 1
    if n % 2 != 0
        return false
    n = n/2
return true

The loop will terminate when n is odd. If n = 1, true is returned and that means that n0 was a power of 2. Otherwise it's false.

I'm new at this and struggle with the proving the power of 2 part for before and during iterations and after the loop terminates. Also what does a loop invariant look like for a true vs false return on a loop?

Is it reasonable to say something like:

at the every iteration i, 1 <= n <= n0/(2^i)
true returned when n = 1 and n0 is a power of 2
false returned when n is odd and n > 1

Is it possible to even make strong loop invariant here without referencing the initial value of n?


texts: Is there any statement about the spacecomplexity ofF and FNP?

texts: I was wondering if there is a statement about the spacecomplexity of F and FNP, like P subset of NP subset of PSPACE?


texts: Fast algorithm for finding a minimum cost path through points in the plane

texts:
Consider the following problem:

There are $n$ points in the plane.
Starting from one of them I want to visit each of them once (except the starting node which has to be visited twice) but in a way that minimizes the cost of the total path.

The weight of each edge changes depending on the path followed.
For example imagine $n=3$: $A$, $B$, $C$ and we start at $A$.
The weight of the edge $xy$ is $Sd_{xy}$, where $d_{xy}$ is the distance between the points $x$ and $y$ and $S$ is a given constant)
If I pick the edge $A\to B$, the weight of the edge $B\to A$ is now
$(S-s_B)d_{AB}$ because $B$ changes $S$ by a constant amount $s_B$.
Similarly if I pick the edge $A\to C$, the weight of the edge $B\to C$ is now
$(S-s_C)d_{AC}$ because visiting $C$ changes $S$ by a constant amount $s_C$.

Developing the $n=3$ case, imagine S=11, $d_{AB}=5,d_{AC}=3,d_{BC}=4$ and $s_{A}=2,s_{B}=5,s_{C}=4$.
Then there are 4 possible paths:

A->B->C->A with cost $11*5+(11-5)*4+(11-5-4)*3$

(we stop once we reach A because 11-5-4-2=0)

A->B->A->C with cost $11*5+(11-5)*5+(11-4-2)*3$

A->C->B->A with cost $11*3+(11-4)*4+(11-4-5)*5$

A->C->A->B with cost $11*3+(11-4)*3+(11-4-2)*5$

For $n=4$ there will be 3*3!=18 possible paths and so on.

I know that $s_A+s_B+s_C=S$. This generalizes for $n$ points.
 What is an efficient algorithm for finding the minimum cost path?


texts: Run-time of Hungarian algorithm - matrix formulation

texts:
There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a spreadsheet.

The problem is, I could not understand the argument of why this algorithm, in its matrix formalism, is polynomial in $n$. In particular, in the above presentation, I got stuck trying to prove that Step 5 (page 13) is executed $O(n)$ times, or more generally, $O(poly(n))$ times.

In step 5, we subtract a number $x$ from each uncovered row, and then add the same $x$ to each covered column. Since in this step, the size of the covering is less than $n$, there are more uncovered rows than covered columns, so we subtract $x$ more times than we add $x$. Hence, the sum of all elements in the matrix strictly decreases each time. Since the sum always remains positive, the algorithm must eventually end.

However, I could not understand why it must end after $O(poly(n))$ iterations.

What am I missing in the above argument?


texts: delete node from linked list (lang w/GC) -should deleted item 'next' be set to null

texts:
Regarding: delete a node from a linked list algorithm,in procedural languages with garbage-collection.
Should there be a step in the algorithm, of setting the removed-node-next-pointer  to null ?

(Several high-school-CS-teachers in my area teach YES, while others teach NO)

What is the right approach?

/thanks ran


texts: What does an NFA do if there's no transition with the correct symbol?

texts:
So I am learning about DFA and NFA, and I need some clarification for it.

DFA

accept empty set
transition for every element in the alphabet
path are deterministic

NFA

accept the empty set and empty string
path are not deterministic

My question is does NFA need a transition for every element in the alphabet? If not, then let say the alphabet is {0. 1} and I am at a state without the transition for 1, do I go to the empty state or something?


texts: Reducing closed TSP to open with fixed starting vertex

texts:
I have implemented a branch and bound algoritm for finding a Hamiltonian cycle in my software, but I actually need to find a shortest route from fixed vertex through all verticies ending at any of them.

As far as I understood, I can reduce closed-cycle TSP to open-cycle with fixed starting point by adding dummy vertex. But I can't find or figure out the weights of the edges of this vertex.

How can I do this?


texts: How can TSP be an NP-optimization problem, when a feasible solution $s$ must be polynomial bounded in the instance size $|I|$?

texts:
How can TSP be an NP-optimization problem ?

The definition of an NP-optimization problem $\Pi$ states that for each instance $I \in \Pi$ , the set of feasible solutions $S_\Pi(I)$ is non-empty and that the size of each $s \in S_\Pi(I)$ is polynomial bounded in $|I|$, where $|I|$ denote the size of $I$.

However, in the case of TSP an instance will be encoded using $n^2$ bits, where $n$ is the number of vertices in the instance graph, using the adjacency matrix representation.

But there are $n!$ feasible solutions ? In order to encode these one must use $n! \setminus 2^n$ bits. This number increase as $n$ increase, but $p(|I|)$ is fixed ?

How I overseen something ?


texts: Prove this langage isn't regular using the pumping lemma

texts:
How can I prove that this language isn't regular using the pumping lemma for regular language?

$$L = \{a^nb^m| n,m > 0, \gcd(n,m)=1\}$$

I've already checked this answer: Proof that a language involving $gcd$ is not context-free but don't understand this part.

"Let s' be $a^{(n+ik)}b^m \ with \ k \geq 1$. Then s' e L if $gcd(n + ik, m) =$ , however the modular equation $n+ik = 0(m)$ have a solution $i = nk^{(-1)(m)}$ ..."

I don't understand how he proved, $gcd(n+ik, m) \gt 1$, could someone explain me more clearly the answer please.

Thank you.


texts:
I came across of one excellent book Elements of Computing Systems and in chapter 1 we need to implement the "primitive" logic gates (for example: Not, And, Or, Xor, Mux, etc) based on a Nand gate.

Up to now I'm just solving these boolean implementations by guessing all required gates which is so much time consuming. I'm not able to find any logic in the implementation.

I'm wondering if you have any method, tipp how to solve this.

Here is an example of the Mux requirements presented in the book

Mux requirement image example
Mux requirement image example continue


texts: How powerful are CFGs that allow an infinite number of rules?

texts:
I was wondering recently what would happen if we'd allow context-free grammars to have an infinite number of rules. Clearly, if we'd allow arbitrary such infinite sets of rules, every language $L$ over some alphabet $\Sigma$ could be described by a CFG $G = (\{S\},\Sigma,R,S)$ with $R = \{S \rightarrow w  \mid w \in L \}$. But what if we restrict $R$ to such sets of rules that can be created by context free grammars?

For that purpose, given a set of nonterminals $N$ and terminals $\Sigma$, let us view rules not as elements of $N \times (N\cup \Sigma )^*$, but as strings over the alphabet $R_{(N,\Sigma)} = N \cup \Sigma \cup \{\rightarrow\}$. Now my question is, if we define an infinite rule CFG to be a tuple $G = (N, \Sigma, R, S)$ where

$N$ is a finite set of nonterminals
$\Sigma$ is a finite alphabet
$R$ is a set of rules of the form $A \rightarrow w$ with $A \in N$, $w \in (N \cup \Sigma)^*$ such that there is some CFG $G'$ over $R_{(N,\Sigma)}$ with $R = L(G')$
$S \in N$ is the initial nonterminal

and we define $L(G)$ for such infinite rule CFGs just like it is done for CFGs, what is the relation between the class of languages generated by infinite rule CFGs (let's call that class $irCF$), the class of context-free languages $CF$ and the class $RE$?

Obviously, we have $CF \subseteq irCF \subseteq RE$, but is $irCF$ equivalent to one of these classes (or some other class)?


texts: Return copy of array, each element product of all others, constant additional space, no division

texts:
Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. The task is as follows:

Given an array $<a_1, \ldots, a_n>$ of fixed-length ints, devise an algorithm which returns a new array $<b_1, \ldots, b_n>$ where each $b_i$ is the product of all $a_j$ with $j \neq i$. That is, each element of the result is the product of all other elements in the original array. Division is not allowed, and the algorithm  must run in $O(n)$ time and $O(1)$ additional space.

Example: $<1, 2, 3>$ should be updated to $<2*3, 1*3, 1*2>$.


texts: In a Min-Cut problem, how many times do i need to run Karger's Algorithm in a given set of nodes?

texts:
Question:

Given 22 nodes, how many times do I need to run Karger's algorithm in order to find A min-cut problem within an error range (say, <2 or between 0-1) ?


texts: Show that if $P=NP$ then there is an algorithm that finds a witness for the language $L = \{x | \exists_w M(x,w)=1 \}$

texts:
Let $M(x,w)$ be a polynomial Turing machine with $|w| = poly(|x|)$, and $L = \{x | \exists_w M(x,w)=1 \}$.
Assuming that $P=NP$ I want to show that there is a polynomial algorithm $N(x)$ that finds a witness for $x$ according to $L$. Namely:
$\forall_{x \in L}M(x, N(x)) = 1 $
My idea was to decide the bits of a witness $w$ using checks with the machine $M$
My attempt looks like this, on input $x \in \{0,1\}^*$, $N$ does:

since $L \in NP=P$, run the polynomial machine that decides $L$ to check if $x \in L$. If not, reject.
check if there exists $w$ such that $M(x,w) = 1$ and $w_1 = 0$. If there is, keep $w_1=0$, else set $w_1 = 1$
check if there exists $w$ such that $M(x,w) = 1$ and $w_2 = 0$ (with the $w_1$ from the previuos check), and do the same.
continue like that until all bits of $w$ are set.

However there are 2 things that I can't figure out.
First, the machine that decides $L$ only checks if $x \in L$, I can't set specific bits for the witness. So how can I force it to have specific bit for the witness. In the case of $SAT$ it is easy because I can just replace variables with constants, but in this general langugae i don't see how.
Secondly, I am not sure that I am using the assumption that $P=NP$ enough.
Help would be appreciated.


texts: Updating maximum sum subrectangle in a sparse matrix when one element is changed

texts: I have an m x n matrix which is sparse with N non-zero entries. A modified version of Kadane's 2-d algorithm can find the maximum sum subrectangle in O(m N log n) time, which beats traditional Kadane's 2-d algorithm of O(m^2 n) for sufficiently sparse matrices. The sparse matrix algorithm, which is also O(m^2 n) time for dense matrices, matching Kadane's algorithm, can be found here https://stackoverflow.com/questions/17558028/maximum-sum-subrectangle-in-a-sparse-matrix .Now I want to know if the optimal solution can be updated quickly if one entry in the matrix is changed. By "quickly" I mean something like O(m log n) time or better. It's possible that perhaps the matrix does not have to be sparse to work out a solution, however a solution when N = O(min(m,n)) would be ok. Preprocessing is also ok as long as the amortized cost of preprocessing time per element changed matches or beats something like O(m log n) time for m changes.


texts: Polynomial time algorithm for finding two or more vertex-disjoint cycles

texts:
The cycle detection problem for a directed graph has well-known polynomial time solutions, graph traversal algorithms such as Dijkstra algorithm can be used to find whether or not a cycle exists in a graph.

The difficulty however comes when we are required to find in polynomial time whether 2 vertex disjoint cycles exist in an arbitrary graph. Is there such a polynomial time algorithm which finds whether 2 vertex disjoint cycles exist in an arbitrary graph?

By vertex disjoint cycles, I mean cycles which do not share a common vertex.


texts: Reconstruction of drawing sequence from video

texts:
I have a video that record the drawing sequence with a pencil by a painter.

I want to reconstruction the sequence from the video.
And I have google some keywords like "drawing sequence reconstruction", "sketch reconstruction", and have searched like "moving object detection" but cannot found what I want to find.

I want to know how to detect and recognize the drawing between different frames. I have thought the "line detect" algorithm may work but fail. And pixel comparison seems to be bad idea. Because that the new drawing may overlap the old ones.

Could you give me some information that I can read or some keywords to search? Sorry about that because I am not familiar with Computer Image Processing.


texts:
Sudoku is well known puzzle which is known to be NP-complete and it is a special case of more general problem known as Latin squares. A correct solution of the $N \times N$ square consists of filling every row and every column with numbers from $1$ to $N$ under the condition that every number appears exactly once in any row or any column.

I define a new problem. The input is a correct solution of $N \times N$ Sudoku puzzle (more generally Latin square problem). I would like to decide whether there is permutation of rows and permutation of columns such that no row and no column contains consecutive triples.

An examples for a row without consecutive triple is 9 5 6 2 3 8 4 7 1. An example for a row with consecutive triple is 8 9 5 2 3 4 7 6 1. The triple is 2 3 4.

I suspect the problem is NP-hard but I was not able to find a reduction.

How hard is solving this variant of Sudoku puzzle? Is it NP-complete?

EDIT : To clarify, the same permutation must be applied to the columns and the rows.


texts:
In the
paper (p. 3)
and the
slides
presents the formulation of the Steiner problem on graphs
via so called Steiner cuts.
But according to the definition, the number of Steiner cuts and so the number of constraints grows exponentially with
the number of vertices in the graph.

First question: How to solve the problem in this cut-formulation? After all, we have too many constraints?
For example, to solve the problem in the formulation through the multi-commodity flow described in the first article,
we have only 'number of terminals' * 'number of vertices' constraints, and this can be solved.

Second question: Is there any practical benefit to solve the LP-relaxed problem,
and then improve it with metaheuristics?
Or is it the same to build a first Steiner tree aproximation with a greedy algorithm and then improve it?


texts: Split a list of elements into sub lists, each with different criteria

texts:
I have a list of elements of different values, say 0 to 3. I want to split it into a certain number of sub lists, each accepting only certains elements. The sub lists may not always have the same length.

For example, I have a list of 12 elements: [0,0,0,1,1,1,2,2,2,3,3,3]. I want to split it into 3 sub lists:

One that accepts all elements.
One that only accepts 1, 2 and 3. That list could be [1,1,2,2] but not [0,0,2,3].
One that only accepts 0, 2 and 3. That list could be [0,0,2,3] but not [1,1,2,2].

A sub list that accepts elements doesn't mean it needs to contain these elements.

I tried filling each sub list in order with random elements from the parent list meeting the sub list criteria. With the example above, it could go like this:

Fill the 1st list: [0,0,0,2]. Parent list is now [1,1,1,2,2,3,3,3].
Fill the 2nd list: [2,2,3,3]. Parent list is now [1,1,1,3].
Try to fill the 3rd list: only [1,1,1,3] is left but this list can't take 1s. Start again.

Because of the use of random this could never end in the worst case.

The algorithm must give uniform results, all combinations of sub lists having the same probability to be chosen.

Context: This is for a card game where the computer plays using Information Set Monte Carlo Tree Search. One step is too make a randomized state of the game from the point of view of a player. All cards unknown to the observer are shuffled together (making the parent list) and redistributed (the sub lists). In this particular game, the player has a way to know that other players may not have cards of a particular suit, so in the randomized state step, no cards of these suits should be distributed to those players (hence why sub lists can have certain values).

In this context there will always be 2 or 3 sub lists, and each sub list will always have between 1 and 13 elements. The difference in the size of two sub lists is never greater than 1.


texts: Is it possible to decide if a given algorithm is asymptotically optimal?

texts:
Is there an algorithm for the following problem:

  Given a Turing machine $M_1$ that decides a language $L$,
  Is there a Turing machine $M_2$ deciding $L$ such that
  $t_2(n) = o(t_1(n))$?

The functions $t_1$ and $t_2$ are the worst-case running times of Turing machines $M_1$ and $M_2$ respectively.

What about space complexity?


texts: Is model checking PSpace-hard *in formula size*?

texts:
Sistla/Clarke proved [SC82] that the LTL model-checking problem is PSpace-complete.
Sometimes people write that this problem is "PSpace-hard in $|\phi|$" (e.g. [LP85]). What does this mean formally?

How to prove that a decision problem that has several parameters (here, $\phi$ and system) is PSpace-hard in one of the parameters? I guess we would need to poly-time reduce some PSpace-complete problem to our problem with the unintereseting parameter being fixed, while the interesting parameter can vary.

But the original proof of Sistla/Clarke [Lemma 4.4, SC82] does not do the thing above! In their proof, both parameters of the resulting LTL model-checking problem instance depend on $n$, where $n$ is the TM tape bound. Is there a proof that fixes one of the parameters?


texts: context-free grammar for comma-separated list with comments

texts:
I'm trying to write a context-free grammar for a comma-separated list of statements with comments.  It is trivial if the comma appears at the end of a statement.  It is trivial if the comment is ignored.  But I don't know how to include a comma in the middle of a statement (before the comment).

This Python / Lark CFG:

start: def+

def: "{" statement ("," statement)* "}"

!statement: NAME "=" (
    | "Foo"
    | "Bar" "(" NAME ")"
    | "Tomato"
    | )

NAME: /[A-Z][a-z-]{0,15}/

COMMENT: "//" /.*/

%import common.WS
%ignore WS

parses this text:

{
    Mike = Foo,
    Fred = Bar(Chocolate),
    Joe = Tomato
}

producing this AST:

start
  def
    statement
      Mike
      =
      Foo
    statement
      Fred
      =
      Bar
      (
      Chocolate
      )
    statement
      Joe
      =
      Tomato

I want to parse the content of comments into the AST, not just ignore it:

{
    Mike = Foo,
    Fred = Bar(Chocolate),      // Yummy!
    Joe = Tomato
}

======= EDIT =========

The problem from which the question was distilled requires an optional description tied to each assignment.  Arbitrary comments (such as on the lines with braces) aren't needed.  So Yuval's answer (with the addition of a trailing comment) works like a charm.  For completeness, the working grammar is:

start: def+
def: "{" statement ("," COMMENT? statement)* COMMENT? "}"

statement: NAME "=" (foo | bar | tomato)
foo:    "Foo"
bar:    "Bar" "(" NAME ")"
tomato: "Tomato"

and produces the AST:

start
  def
    statement
      Mike
      foo
    // Stuff
    statement
      Fred
      bar   Chocolate
    // Yummy!
    statement
      Joe
      tomato
    // aaaargh


texts: Context Free or Context Sensitive and why

texts:
I was given two languages

$$L_1=\{0^k1^k0^m\mid k,m \in \mathbb{N}\text{ and }k < m\}$$

and

$$L_2=\{a^mb^{m+1}\}$$

and I was asked to prove whether they are context free or sensitive.

For $L_1$ : I did pumping lemma and I cannot clearly rule out the context free. So I accepted that it is and tried to do a high level description of a pda. I check the first part of the language $0^k1^k$ like this: push A for every 0 you read pop A when you read 1. If the stack is not empty reject. But I have trouble finding how to check the second part, $1^m$ with $m>k$. So now I do not know if it is indeed a context free.

For $L_2$ I followed a similar method with $L_1$ and again I stuck in the $m+1$ part.

Can someone help me? I am not proficient in grammar creation and pdas and lbas were only taught in our class in high level descriptions like the above.


texts: Drawing Zonotopes from an Adjacency Matrix

texts:
I'm conflicted whether to post this here or in either math.stackexchange or mathematica.stackexchange.

Define a "simple zonotope" to be a regular $2n$-gon which is tiled by the following rule: all tiles are rhombi. They key point here is that rhombuses have equal side lengths (say equal to 1), but their shapes are allowed to vary arbitrarly. Here's an example of a 12-gon zonotope:

There are many characterizations and properties of these objects. For example, one can encode a zonotope using $2n$ vectors (one for each outer edge) since we can just translate copies of each vector.

What I would like to do is the following: I have the adjacency matrix of a graph that I believe to be a simple zonotope. Specifically, you can assume that we are starting with a planer geometric graph, in that I have an adjacency matrix, in addition to having (x,y) coordinates of each point. In other words, it's fairly straightforward to identify which vertices go to the outer vertices of the $2n$-polygon.Here's an example of a geometric graph that I could have:

In the above picture, the two red vertices indicate the north/south poles of the zonotope they are mapped to (which happens to be the zonotope in the first picture).

  Question: What is the most painless way of drawing the simple zonotope from a given adjacency matrix plus geometric graph coordinates?

Some observations: part of the algorithm is somewhat clear to me: one should work from the outside in. Once a specific rhombus side has been identified, all sides below it must be the same until we run into the opposite side of the zonotope. However this all seems very computationally expensive. I am honestly not preferential to any specific solution. I would even accept something akin to attaching springs to vertices and then running the algorithm until the graph converges to a zonotope.


texts: Prove a language $A_{PTM}$ is not BPP-Complete

texts:
I am trying to prove that there are a language is not BPP-Complete. There are a couple of examples online, but they are not the best examples and are a bit complicated. I spoke with one of my computer science professors about the problem and he proposed the following proof sketch:

Proof (sketch):

We know $A_{TM} \le_m A_{PTM}$.

Construct a decider $D$ that given a Probabilistic Turing Machine $M$ and a string $x$, $D$ accepts if $M$ accepts $x$, and rejects otherwise. As $A_{TM} \le_m A_{PTM}$, a solution to $A_{PTM}$ would yield a solution to $A_{TM}$. However, $A_{TM}$ is not decidable, so therefore, $D$ cannot exist.

End of Proof

Where I am confused is how does this show $A_{PTM}$ is not BPP-Complete? As an acceptance problem, I would think $A_{PTM}$ is BPP-Hard, but I don't see how this shows it is not in BPP.


texts: How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $

texts:
I am trying to answer this question:
$3x^3 +2x + 1$ is $ \omega(x \cdot \log x)$

My question is how to solve this question.

Here is what I have tried so far:

I applied the definition $3x^3 + 2x + 1 > c \cdot x\log x$ for all c, given $n \geq k$, for some k

I tried to apply the technique of applying the equality that:
$n < n^3$

Since n is less than the highest order term we can just move all terms to order n ??

Giving $6x < c \cdot x \log x$

Then you can choose:
$k < 2^\frac{6}{c}$


texts:
Hey so I'm studying for a midterm and I've run into this problem in the material. I'm not sure how to go about solving it. If I use regular induction in part a, I get something a bit tautological. Any suggestions?

Questions

As we all know, US dollar is the official currency in United States. There are different bills of value 100, 50, 20, 10, 5, 2, 1 , and coins of value 1, 0.50, 0.25, 0.1, 0.05, 0.01. In this problem we consider the problem of buying something with the smallest number of bills/coins. A simple way to pay x dollars is to use the following Greedy-Pay algorithm:

Greedy-Pay(x)
   While x > 0
      Let u be the largest value bill/coin such that u <= x
      Pay the bill/coin with value u
      Let x = x - u

Prove that if you have unlimited number of bills of {1, 2, 5, 10} dollars (and you don’t have any other bills/coins), no matter what x is (as long as it is a multiple of 1) the Greedy-Pay algorithm minimizes the number of bills/coins used for the payment. (Change is not allowed here.
For example, you cannot pay 9 by a 10 bill and get 1 back.)


texts: Machine Learning and Neural Networks for High School Students

texts:
I hope this question is appropriate for this forum.
In this summer I am giving a 3-day workshop on machine learning and neural networks for advanced and very enthusiastic high school students which all know at least one programming language.
Typically a day consists of 2 hours lecture in the morning and later the students should solve a given problem (with help, of course).
For the first day we are going to sove a simple pixel counting problem in a picture (Or do you know any simpler interesting example)
For the second and third day I wanted to give them a more challenging problem:
Consider the set of binary $3\times 3$ matrices. One can imagine every matrix as a chessboard like picture where every $1$ corresponds to a black field and every $0$ to a white field. The objective is to count the connected components.
I allready produced the matrices and computed a neural network. It seems to work (training set 50%), however I am not an expert in machine learning so my solution is most likely not good!
So my questions are:

Has anybody allready computed a neural network for the problem above and is willing to share his data?
Do you know similiar problems accessible for high school students which are better suited for this occasion?