texts: Word tiling, where you must use each tile exactly once

texts:
Given words $w_1,\ldots,w_n$ in binary alphabet and another word $w$, decide if $w$ can be written as a product $w = w_{i_1} \cdots w_{i_n}$ (in the monoid $\{0,1\}^\ast$) for some permutation of indices.
Is this a known problem? Is it NP-complete?
Details:

The words $w_1,\dots,w_n$ are part of the input.  Therefore, there is no a priori upper bound on $n$, $|w_i|$, or $|w|$.  However, we may assume that $|w|=\sum |w_i|$.

If we restrict the problem to instances with $|w_i|\le k$ (where $k$ is a fixed constant), we obtain a new problem $WT_k$.  $WT_k$ belongs to $P$.  It's possible to build a polynomial-time algorithm for $WT_k$, using dynamic programming.  Indeed, in this case the number of different words $w_i$ is bounded by $2^k$. Hence any sequence $\{w_1,\ldots,w_n\}$ can be encoded by a $2^k$-tuple of integers (an element of $\mathbb{Z}^{2^k}$). It is convenient to assume that $w_i\ne  \varepsilon$.
Now with every initial segment $w'$ of $w$ we associate a set of tuples in $\mathbb{Z}^{2^k}$ that describe sequences of $w_i$'s resulting in $w'$. For instance, with $\varepsilon$ we associate a single tuple $(0,\ldots,0)$ and $\varepsilon$ is considered processed. Then for every processed segment $w'$ we go over its tuples and see which ones we can append to $w'$ (which $w_i$'s are still available).  For instance, if $w' w_i$ gives another initial segment $w''$ of $w$ then we add the corresponding tuple for $w''$. Eventually, all initial segments will be covered.  Here it is crucial that $k$ is fixed, as it ensures that the sets of tuples associated with every $w'$ is polynomially bounded (with a very large degree).

I suspect that the general problem is NP-complete and I'd appreciate any suggestions.

Clearly the problem can be viewed as a sort of a bounded Post correspondence problem with a fixed collection of pairs $(w,\varepsilon),(\varepsilon,w_1),\ldots,(\varepsilon,w_n)$. Not sure if this helps, though.

Clearly, the restriction to a binary alphabet is irrelevant. One can work with any countable alphabet. Need to be careful though: the item 2 does not hold when the alphabet is unbounded.


texts: Is the given language decidable for turing machine?

texts:
I am going through undecidability of TM and found this question

$L=\left \{ \left \langle M \right \rangle |M\ is\ TM \ and \ number\ of\ strings\ in\ the\ language\ \ is\ prime\right \}$

I think it is decidable as number of strings in the language is prime ,i.e , 2,3,5,7,11,13,17,............. It seems to me like it is accepting all the strings.

If it has accepted 17 strings, then it must have accepted 12 strings, 14 strings, 16 strings and so on. Actually i am not getting from where to start.

Can anyone provide legal explaination of what is actually happening here ?


texts:
I am currently a high school 12th grader and am very interested in computer theory and pure mathematics. I also have a strong interest in astronomy and a desire to study quantum information.

However, physics and I really don't have a nice relationship. I am having trouble figuring out what major holds the topics I am interested in. Most university research on quantum information seems to be found in the physics/astronomy department, but I have also found joint computer theory/mathematics programs in their respective departments.

I don't want to be a physics major, but how can I fulfill my curiosity with quantum information? I am having great difficulty finding a university that offers undergraduate research in these fields.

Any tips on how to find research opportunities in these topics as an undergrad?


texts: What if $PSPACE$ falls to non-uniformity?

texts:
We know if every language in $EXP$ has polysize circuits, then $P\neq NP$ and $EXP=PSPACE=\Sigma_2^P\cap\Pi_2^P$.

If every language in $PSPACE$ has polysize circuits, then does it give anything (note if it gave does $P\neq PSPACE$ then this would give $P\neq PSPACE$ unconditionally since $P\subseteq P/poly$ and $P=PSPACE\implies PSPACE\subseteq P/poly\implies P\neq PSPACE$ a contradiction)?

If every language in $PSPACE$ is in $BPP$ then $BPP=\Sigma_2^P\cap\Pi_2^P=PSPACE\neq EXP\not\subseteq P/poly$.

If every language in $PSPACE$ is in $RNC$ then $NC\neq P=PSPACE=RNC=BPP=\Sigma_2^P\cap\Pi_2^P\neq EXP$ (note $NC=PSPACE$ is not possible unconditionally).

If every language in $PSPACE$ is in $BPP$ or is in $RNC$ do they give anything beyond?


texts:
I came across the following question:

A source $X$ emits symbols from the alphabet $A_x$ with $|A_x| = 8$. We want to construct a preﬁx-free source code for this source.

We want to ﬁnd a code with codeword lengths $(1,3,3,3,5,5,5,5)$. Can such a code exist? If yes, give such a code. If not, prove that.

I checked Kraft's inequality for the given set of lengths and it's fulfilled. So how can we write such a code?


texts: Hash function floating point inputs for genetic algorithm

texts:
I am implementing a genetic algorithm to use as an optimisation algorithm to evolve robots. The robots have certain parameters (represented as floats) which can lie anywhere within a certain range defined for each parameter. My goal is to optimise these parameters to produce the fittest robot.

There are about 25 parameters to optimise over, all of which are >= 0. A generation consists of 32 robots and a typical evolutionary run may have 6000 generations, so that is 192000 robots in total.

One problem I was noticing was that many times, the same robot was being produced by the random mutation function and its fitness was re-evaluated. I want to try and minimise this from happening as the physics simulation engine has a large time expense.

It would be impractical (especially from a memory point of view) to remember all robot parameters that have ever been produced and use a brute force solution.

One solution I thought of was to use a hash function to and a large array of booleans, and everytime a mutation occurs, largeArray[hash(robotParameters)] is checked to see if it is set. If it is, the mutation occurs again to produce a different set of parameters, and if it isn't, largeArray[hash(robotParameters)] is then set.

What is a good hash function implementation that would work for me? Preferably, there would already be an implementation in Python or C++.


texts: Why do we not use CFGs to describe the structure of lexical tokens?

texts:
This was an exam question for my course and I am struggling to actually answer it in a way that is not fluff.

Here is my current answer:

CFGs describe how non-terminal symbols are converted into terminal symbols via a parser. However, a scanner defines what those terminal symbols convert to in terms of lexical tokens. CFGs are grammatical descriptions of a language instead of simply defining what tokens should be scanned from an input string.

What is the correct way to answer this?


texts:
So I've been implementing AlphaZero for Chess from scratch and there were a few things the papers mentioned that I'm not sure how to implement. I'll reference both the original AlphaGoZero paper and the general AlphaZero paper since some concepts explained in the original paper are reused in the general one.

Repetitions/No progress count:

the repetition count for that position (3 repetitions is an automatic draw in chess; 4 in shogi); and the number of moves without progress in chess (50 moves without progress is an automatic draw)

Maybe I am unfamiliar with how repetitions work in these games, but what exactly does it mean by repetitions and no-progress? How are these represented as input planes?

Training Data:

The data for each time-step $t$ is stored as ($s_t$, $\pi_t$, $z_t$) where $z_t=±r_T$ is the game winner from the perspective of the current player at step t.

Regarding the policy at time t $\pi_t$, I understood this as the probability distribution of taking some action that is proportional to the visit count to each child node i.e. given some parent node (state), if some child node (subsequent state) $a$ is visited $N_a$ times and all children nodes are visited $\sum_b N_b$ times, then the probability of $a$ (and its corresponding move) being sampled is $\frac{N_a}{\sum_b N_b}$, and this parametrizes the distribution $\pi_t$. If this is the case, then for some terminal state $T$, we can't parametrize a distribution because we have no children nodes (states) to visit. Does that mean we don't add $(s_T, \pi_T, z_T)$ to the training data?

Action Space:

We represent the policy π(a|s) by a 8 × 8 × 73 stack of planes encoding a probability distribution over 4,672 possible moves. Each of the 8 × 8 positions identifies the square from which to “pick up” a piece. The first 56 planes encode possible ‘queen moves’ for any piece: a number of squares [1..7] in which the piece will be moved, along one of eight relative compass directions {N,NE,E,SE,S,SW,W,NW}...

Not sure why we represent this as a stack of planes. Also, this action space implies that we can sample illegal moves (and I imagine that a majority of the moves are illegal especially in early game, but I could be wrong). Do we just continue resampling until we get a legal move? What about during test time when we greedily choose the move with the highest probability, and it turns out this move is illegal?


texts: Proving a certain primitive recursive function exists

texts:
Assume $f\colon ω × ω → ω$ is a computable function. How can we prove that there is a primitive recursive function $g\colon ω × ω → ω$ where the following holds:

$∀n [∃s(f(n, s) = 1) ↔ ∃k(g(n, k) = 1)]$

So for every $n$, there is an $s$ such that $f(n, s) = 1$ if and only if there is a $k$ such that $g(n, k) = 1$.

Been working on this problem for a while now, if anyone could please help?


texts: Combinatorial Problem similar in nature to a special version of max weighted matching problem

texts:
I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem.
I have a general graph $G(\mathcal{V},\mathcal{E},\mathcal{W})$. I want to find a maximum weight matching of the graph $G$ that must cover a certain subset of vertices and has a specific size. For example, if I have a graph with eight vertices, I want to find a max weighted matching that must cover the subset of vertices $\mathcal{V}'=\{1,2,3\}$ and the size of the matching is $\lceil{|\mathcal{V}'|/2}\rceil$. So one more vertex needs to be chosen that maximizes the weighted matching. How to find the optimal solution in polynomial time if possible?


texts: Is it possible to retrive the Hash from an encrypted folder?

texts:
So first of all I've a software which basically locks/encrypts a folder with a given password. Afterwards it's almost impossible to open the folder without entering the password through the software.

I locked some of my much needed files and accidently forgot the password.

So my question is, is it possible to retrive the hash from the encrypted folder? I'm planning to brute-force if it's possible.

If it's not, then should I reverse engineer the software to open the encrypted folder without entering the password?

What other possible options do I have?


texts: Job Shop Problem: How do you get an ordered sequence of operations from the disjunctive acyclic graph?

texts:
Intro
The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its processing time) over the set of jobs. Jobs must be processed on a sequence of machines in a particular order. An operation refers to a particular job being processed on a particular machine.

Representation
A disjunctive graph is typically used to represent the problem of minimising makespan. Each node in the graph is labelled $(i,j)$ where $i$ refers to the job, and $j$ to the machine on which the job is to be run. Conjunctive arrows between nodes indicate precedence constraints for a particular job. Each conjunctive edge is given a weight, corresponding to the processing time $P_{i}$ for the particular operation $O_{i}$ at the base of the edge. Disjunctive edges are placed between operations that take place on the same machine. An example of two simple jobs is given below:

Note that $J_{1}$ is comprised of the upper row of nodes, and $J_{2}$ the lower row.

Problem
My problem is with the terminology used to describe how to solve the JSP. The book "Scheduling Theory, Algorithms, and Systems" (Pinedo, 2008) states on page 181 that:

A feasible schedule corresponds to a selection of one disjunctive arc from each pair such that the resulting directed graph is acyclic

However, if I do just that, I can derive a graph that looks something like this:

Now, it is said that:

The makespan of a feasible schedule is determined by the longest path in G(D) from the source U to the sink V

And if I sum the longest weighted path, I can indeed derive a "makespan" value. However, I still don't get why this is a "feasible schedule". Because I don't really have a schedule at all. The path doesn't give me an ordering for how to execute the callbacks. That is because the path necessarily does not visit every operation. Meaning that it does not give a feasible schedule at all.
Verdict
In light of what I have described above, my question is: How can I derive the full sequence of operations to perform from the disjunctive graph model of the job shop problem?
Edit: There's a mistake in my graph, the last edges going to $V$ should be labelled with a weight.


texts: Parallel algorithm to find if a set of nodes is on an elememtry cycle in a directed/undirected graph

texts:
I'm looking to find / develop a simple parallel algorithm that does this:

Input:

vs: list of root vertices
max_length: max cycle length
max_dist: max distance to root

Variants

one variant of the algorithm should support directed graphs
the other variant should support undirected graphs (or treat a directed graph as undirected)

Output:

for each vertex in the root vertices, "numberOfCycles" should be set for the number of cycles (I assume the right term is elementary cycles) that pass via the root, that are no more than max_length length, and no more than max_dist (shortest path) from the root (e.g. all vertices in the path are up to max_dist distance from the root, if even one is more, then the cycle is ignored).

What I thought of so far:

I'm sure this can be highly optimized, (this is why I asked the question) and probably very native and perhaps incorrect, please be patient with me :)

first, do a parallel BFS starting from the roots running for max_dist iterations (e.g. pregel for shortest paths for N iterations on GraphX), mark all nodes within that range with their distance from the root (using a map as a node can be in the proximity of more than one root) - this is covered with built in Spark ShortestPaths code (a little modified to allow for limiting number of iterations + support treating a directed graph as undirected)

This is where I am not sure how to continue.

if it's a directed graph, then strongly connected components is the answer? but won't it find only one cycle (the largest one I assume?) e.g. each vertex can only be in one strongly connected component, right?
should I find bridges using Tarjan's algorithm?
do a DFS and keep track of the path depth, and add + 1 when I reach back root node or any node that reached the root node? if I'm running a pregel - like paralel algorithm, when should I stop? when all nodes in the radius of max_distance were visited?
how do I filter out cycles that are too long? save the cycles in a list and filter it out? or some other way?

Related questions:

https://mathematica.stackexchange.com/questions/9434/finding-elementary-cycles-of-directed-graphs
single algorithm to work on both directed and undirected graph to detect cycles?
https://stackoverflow.com/questions/546655/finding-all-cycles-in-graph


texts: Finding pair of sum in sorted array in time complexity less than $O(n)$

texts:
In a sorted array, I am trying to find just one pair that sum up to a certain value. I was wondering if anyone could help me improve my code in performance or memory. I know the code which is $O(n)$. If there are other method for finding pairs the sum up to a certain value that is much more efficient.
I was asked this in an interview recently and interviewer told me that there exists a solution with $O(\log n)$ time complexity.
Any ideas are appreciated.


texts: Hamiltonian cycle, verifying and finding

texts:
If we have an algorithm that in polynomial time says if a graph G has an hamiltonian cycle, can we have an algorithm that in polynomial time find an hamiltonian cycle?

My attempt is to delete an edge of graph G and have G', after run the algorithm on G' to know if it has an hamiltonian cycle if not it means that the edge is in some hamiltonian cycle. Now I don't know how to go on.


texts: Find optimal local alignment of two strings with restrictions

texts:
I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.
The problem:
We want to find an optimal local alignment of two strings S1 and S2, we know that there exists such an alignment
with the two aligned substrings of S1 and S2 both of length at most q.
Besides, we know that the number of the table cells with the maximal value, opt, is at most r.
Describe an algorithm solving the problem in time O(mn+r*q^2) using working space of at most
O(n+r+q^2).
Restrictions: run the algorithm of finding the optimal local alignment value, with
additions to your choice (like the list of index pairs), only once. Besides, you can run any variant of the algorithm for solving the global optimal alignment problem as many times as you wish
I know the solution to this problem with running the local alignment many times and the global alignment only once, but not the opposite.
the global alignment algorithm:

the local alignment algorithm:

Any help would be appreciated.


texts: Universal theorem proving algorithms for sequent calculus (e.g. for cut-free logics)?

texts:
Some of the logics admit Gentzen-style sequent calculus. Are there universal algorithms that allow to find proof (derivation of the proof) in sequent caculus for every hypthetical theorem?

Some of the proof assistants support formalization of general sequent calculus that can allow to define sequent calculus for the concrete object logics and find proofs for these logics (i.e. this is the use case how proof assistant ar adapted for use as theorem provers):

Isabelle/HOL has formalization https://www.cl.cam.ac.uk/research/hvg/Isabelle/dist/library/Sequents/Sequents/Sequents.html https://www.cl.cam.ac.uk/research/hvg/Isabelle/dist/library/Sequents/Sequents/ILL.html
Coq has formalization like http://www.cs.nuim.ie/~jpower/Research/LinearLogic/

So - current theorem provers have more or less universal backward reasoning algorithms for theorem proving. Where can I find the reference for these algorithms? I guess I can refactor the mentioned theorem provers but I hope that theoretical descriptions of these algorithms can be found.

Especially I am interested in quantified linear logic but algorithms for other logics are interesting for me.

I am aware that the original goal for the proof assistants was proof checking and not the derivation of the proof but current state of the art is that the proof assistants can automatically derive large parts of the proof and human intervention is necessary only for the hardest cases. Human intervention can take the two forms: 1) developer can program new tactics for the automatic derivation of the proof; 2) mathematician can choose the specific tactic for the proving the current subgoal. The second task can be left to Artificial Intelligence.

So - I am seeking for the reference - where the proof algorithms for sequent calculus are described. It is quite possible that full algorithms does not exists (similarly - proof assistants require new tactics) but still - are there good reference about such automatiazion?


texts: What's an upper bound for this recurrence so I can take advantage of the Master Theorem?

texts:
Let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\
T(\varphi(N)) + 2T(\sqrt{N}) + \lg(\varphi(N))^3 & \text{otherwise}
\end{cases}$$

where $\varphi(N)$ is Euler's totient function.  My objective is to find an upper bound so that I can apply the Master Theorem and find a closed-form formula.


texts: Given tree with 0 or 1 assigned to each node, count paths with odd number of ones in it

texts:
Let's say we have given tree of $N$ nodes and $N-1$ edges, each of the $N$ nodes is assigned one integer, either $0$ or $1$. We want to count all paths between two nodes $u$ and $v$ such that on the shortest path from node $u$ to node $v$ there are odd numbers of ones ( or in other words the sum of all integers on this path is odd number ).

I know that this can be solved easily by running a single DFS from each node, but this works in $O(N^2)$. I'm trying to find way to narrow it down to $O(N\log N)$ or $O(N)$. I was thinking about applying some dynamic programming, but I couldn't find the relations between the nodes.


texts: a lower bound for the maximum fraction of matchings not containing an edge

texts:
I am trying to prove the following statement (from book, page 317):

Let $G(A,B,E)$ be a bipartite graph, where $A$ and $B$ are the two disjoint sets of vertices s.t. $|A|=|B|=n$. Let the number of matchings of size $k\le n$, be $m_k$. If $|E|>k$ then there exists an edge $e$, such that $\frac{m_{ne}}{m_k} \ge \frac{1}{n}$, where $m_{ne}$ is the number of matchings of size $k$, that do not include/contain edge $e$.

The book gives a hint to use pigeonhole principle. But I am only able to get a weaker result.
Each matching of size $k$, contributes towards a matching of size $k$ not containing an edge, for $|E|-k$ edges. Thus as there are in total $m_k$ matchings, it can be seen as distributing $(|E|-k)m_k$
balls in $|E|$ bins. Thus by pigeonhole principle there is a bin (an edge) with at least $\frac{(|E|-k)\cdot m_k}{|E|}$ matchings which do not contain it. That is there is an edge $e$ such that
$$m_{ne} \ge \frac{(|E|-k)\cdot m_k}{|E|}$$
$$\frac{m_{ne}}{m_k} \ge \frac{|E|-k}{|E|} \ge \frac{1}{|E|} \ge \frac{1}{n^2}$$
How can I prove that the lower bound is at least $\frac{1}{n}$ for some edge ?


texts: Witness length independent $\exists$-Operator

texts:
Short version:

Is there an operator $\exists$ (on complexity classes) s.t. $\exists P = NP$ and $\exists REC=RE$, i.e. you can use the same operator on multiple interesting classes without explicitly stating a class of functions that limits the length of the witnesses?
The construction should not rely on the existence of a definition of the class using any specific computation model (like Turing machines), i.e. it should be defined for any class of languages.

Long Version:

For any complexity class $\mathcal{C}$, any language $L$ and any class of functions $F\subseteq\{f|f:\mathbb{N}\rightarrow\mathbb{N}\}$ define

$$\exists^{f,\#} L =\{x \in (\Sigma\setminus\{\#\})^*|\exists w\in(\Sigma\setminus\{\#\})^*: x\#w \in L, |w| \leq f(|x|) \}$$
$$\exists^F \mathcal{C} =\{L|\exists\#\exists f\in F\exists L'\in\mathcal{C}:L=\exists^{f,\#} L'\} \qquad .$$

Note: If $F=\mathbb{N}^{\mathbb{N}} = \{f|f:\mathbb{N}\rightarrow\mathbb{N}\}$ the length of the witness $w$ becomes unrestricted (set $f(n)$ to be the maximum length of a witness for all inputs of size $n$).

It is well known that $NP=\exists^pP$, where $p$ is the set of all polynomials (see WP:Polynomial hierarchy) and $\exists^{\mathbb{N}^{\mathbb{N}}}REC=RE$ (see WP:Arithmetical hierarchy).

Now I'd like to know, if one could get rid of the class of functions $F$ or define $F$ depending on the class $\mathcal{C}$ without using a certain way to define the class (Not: If $\mathcal{C}$ is the class of languages accepted by a TM in $\mathrm{DTIME}(\dots)$, then $F:=\dots$)

Things I've tried so far:

$\exists\mathcal{C} = \exists^F\mathcal{C} \text{ where } \exists^{o(F)}\mathcal{C} \subseteq \mathcal{C} \text{ and } \exists^F\mathcal{C}\nsubseteq \mathcal{C}$
$\exists\mathcal{C} = \exists^{F'}\mathcal{C} \text{ where } F'=\{2^f|f\in F\} \text{ and } F \text{ maximal s.t. } \exists^{F}\mathcal{C} \subseteq \mathcal{C}$

(added:) $\exists\mathcal{C} = \exists^F\mathcal{C} \text{ where } F=\{f\,|\,\forall L\forall\#\notin\Sigma(L):\, \{\#^{f(|w|)}w|w\in L\} \in \mathcal{C} \Leftrightarrow L \in \mathcal{C}\}$, i.e. those functions s.t. $\mathcal{C}$ is "invariant" under padding ($\Sigma(L)=\{a|\exists i\exists w_1,\dots,w_k \in L:\, w_i = a \}$).

1 and 2 don't work for P, I'm not sure about 3.


texts: 4-bit input, 5-bit output, logical right shift by 2, which is the correct set of 5 output bits?

texts:
Suppose I have the following inputs:

1110
1111

If I perform a logical right shift by 2 on each, are the 5-bit outputs these:

00111
00111

or these:

01110
01111

If it's neither, then I'd appreciate an explain why and what I've done wrong!


texts:
Given a graph $G$ where loops and multiple edges are allowed.
A path {$e_1, e_2, ..., e_k$} (a sequence of edges) has a cost
$$ cost = e_1 | e_2 |...|e_k$$
where $|$ is the bitwise OR.

Assume for all edges in $G$, $e_i \ge 0$.

Now, the triangle inequality is satisfied, for this definition of cost. Meaning, as the path size increases, the path cost can never decrease.

So theoretically, to find the shortest between two vertices, Dijkstra's algorithm should give the right answer?


texts: Is it reasonable to assume modern computers can do hardware math with integers up to 2^64?

texts:
I was writing up an algorithm that involved knowing the size of integers my hardware can manage without having to resort to software implementations of math operations and the additional computational load that comes with them, and I realized that I've never given this much thought.
In theory, a 64-bit computer has 64 lines on the address/data bus, and thus can't send an integer to the CPU's ALU any higher than 2^64-1, making that the starting point. But I also know that some modern hardware has support for SIMD operations with 256-bit data, or even higher, and how that's possible I don't know (multiple operations to load in the data, 64 bits at a time, I assume?).
Without limiting this question to specific hardware, which would greatly diminish its usefulness, is there a reasonable rule of thumb for how large of an integer a typical modern computer (2015-2020 era) can handle in a single go?


texts: Analysis of Dijkstra algorithm's (Lazy) running time

texts:
I'm trying to figure out the running time for a Dijkstra algorithm. All the sources I have read say that the running time is O(E * log (E)) for a lazy implementation.

But when we do the math we get O(E * (Log(E)+E*Log(E))).

Since E isn't a constant, I don't see how someone could reduce this to O(E * log (E).

Are we analyzing the wrong or is it possible to reduce?

        while (!minPQ.isEmpty()) { <=== O(E)
            Node min = minPQ.poll(); <=== O(log(e)

            for (Edge edge : graph.adj(min)) { <=== O(E)
                if (min.getId() == target.getId()) {
                    // Source and Target = Same edge
                    if (edgeTo.size() == 0) edgeTo.put(target, edge);

                    return;
                }

                relax(edge, min, vehicle); <=== log(e) (because of add method on PQ)
            }
      }


texts: Common Algorithms without Asymptotically Tight Bounds

texts: I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds,  but are there actually common algorithms in computer science that don't have asymptotically tight bounds on their worst case running times?


texts: Are there more succint algorithm for translating NFA's to DFA's?

texts:
When translating an NFA to its deterministic equivalent, we get an exponential  blowup due to the powerset construction method. I tried to search but couldn't find an appropriate question regarding this question:
I was wondering if there are algorithms that are better, even if it's just a tiny bit, for translating NFAs to DFAs?


texts: What's the difference between environment and memory in terms of programming languages?

texts:
I've been reading up on programming languages to better my understanding with the textbook Essentials of Programming Languages (3e) - Friedman & Wand.

In a chapter regarding the states of languages (i.e. when we account for the effects that a computation may have rather than the immediately evaluated value), I've noticed that the terms environment and memory are used frequently, but I'm not sure how to grasp the difference.

  According to the text, "an environment associates a value with each element of a finite set of variables," and "memory is a finite map from locations to a set of values called stored values."

Does this mean that environments are a part of memory? The part that especially confuses me is when we "extend the environment."

To give a short example, if I had a procedure such that

let f = proc (x) (x + 1) in
  f (1)

then the text states that we "extend our environment" so variable f points to a location (say, l1) and argument x points to l2.

l1 in turn points to the procedure tuple (x, (x + 1), empty_env), and finally l2 points to the actual argument 1.

We update the location contents according to the procedure, which means we update l2 with 2, and the program finally returns 2.

Thank you.


texts: Going deeper with pseudo-polynomial time algorithm for set partitioning

texts:
If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next?
To illustrate this problem let's take a look at this example: {100,1,2,3}.
The p-p algorithm will give an answer False, and then I can end with result: This set can be partitioned into two set with difference 100-6 = 94
(The 6 is the last result from p-p algorithm on with [_][vector.size()] = True, the 106 is the sum of all digits).
But what if I really would like to know the maximum by sum two-split of this set in which every subset has the same sum - for example the result that I'm looking for should be 3. This set - {100,1,2,3} can be split (by bypassing the 100) into two subset with the same sum - {1,2} and {3}.
How can I achieve this result?


texts: Expectation for the number of leaf nodes in a randomized tree construction

texts:
Consider this procedure for building a tree from $v_1, v_2, ..., v_n$:

insert $v_1$
insert $v_2$ and connect it to $v_1$ via a directional edge from $v_2$ to $v_1$
insert $v_3$ and with a uniform probabiliy connect it to $v_1$ or $v_2$
...
insert $v_n$ and with a uniform porability connect it to $v_1$ or $v_2$,... $v_{n-1}$

The question is what is the expectation for the number of leaf nodes?


texts: Minimize number of math operation of a specific matrix vector multiplication?

texts:
Let's say we have a Matrix M and a column vector v like below

multiply

equals

Assume we can only perform multiplication, addition and substraction operation.
With normal approach we need 3 multipliction and 3 addition to calculate row1
row1 = v_1 + 2v_2 + 2v_3 + 4v_4.
However we can do it smartly by

t1 = v_1 + 2*v_3
t2 = v_2 + 2*v_4
row1 = t1 + 2 * t2
row2 = t2 - t1
row3 = ...

Totally we only need 4 multiplication and 5 addition/substraction to do the calculation.

Is there any algorithm or approach to figure out the minimum number of operations?

P.S. I know sub-expression elimination algorithm can be used for this kind of problem.
However I am trying to figure out whether it can be solve by linear algebra method or explaination.


texts: Formulating a linear program s.t. only extreme point solutions are found

texts: If there are many solutions to a linear program s.t. the objective function is minimized/maximized (= optimal solutions are on an edge of the polytope), how can I force an LP solver to find only an extreme point solution?


texts: If a problem is complete for NP, is its complement complete for co-NP?

texts:
I am trying to prove that for a NP problem that is complete, its complement co-NP should be complete as well.

We know that a decision problem A $\in$ NP-complete if a) it is in NP and b) if every other NP problem is polynomial-time many-one reducible to it. There is a similar relationship between co-NP-complete and co-NP problems.

By definition, the complement of a problem is the same decision problem but instead of looking to validate the answer, we are looking to negate it. So it should be "common sense" to say that if a problem is NP-complete, then its complement is co-NP-complete, but how do you prove this? I know it should be easy to prove but I'm out of proofs or ideas.


texts: Why bound of linear function is same as that of quadratic equation

texts:
I am learning algorithms. So, I came along with something very interesting.

The asymptotic bound of linear function $an+b$ is $O(n^2)$ for all $a>0$.

This is same as for $an^2 + bn + c$. But shouldn't it be different?


texts:
Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \{u\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is the complexity?

Can I please have a hint?


texts: Could Subset Sum Problem Be Solved In linear Time Using Logarithmic Space?

texts: Is there any known lower bound on the complexity of subset sum problem? For example, could it be solved in linear time using logarithmic space?


texts:
So, as is known, ILP's 0-1 decision problem is NP-complete. Showing it's in NP is easy, and the original reduction was from SAT; since then, many other NP-Complete problems have been shown to have ILP formulations (which function as reductions from those problems to ILP), because ILP is very usefully general.

Reductions from ILP seem much harder to either do myself or track down.

Thus, my question is, does anyone know a poly-time reduction from ILP to SAT, that is, demonstrating how to solve any 0-1 ILP decision problem using SAT?


texts: Polynomial Time Reduction: Set Cover to CNF-SAT

texts: How to prove that Set Cover can be polynomial-time reduced to CNF-SAT?


texts: Do you >have< to define the upper and lower bound? (context: traveling salesman)

texts:
Do one have to define the upper and lower bound to be able to solve the tsp, or is that just an unnecessary intermediate step? And if so, why would one define those bounds? (context: the traveling salesman problem (TSP))

Additional question:
After having calculated the upper bound (using eg. the Nearest Neighboor algorithm), and the lower bound (using eg. kruskal's algorithm) ... let's say we get:  [4; 8]

Can we say for sure that the cost of the optimal route is a number in the interval [4; 8]? Is it possible to find a route whose cost is not within the interval?


texts: Is distinguishing Hadamard matrices _really_ NP-hard?

texts:
In a few different places ( http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01539-4/S0025-5718-03-01539-4.pdf and https://books.google.com/books?id=qYYKBwAAQBAJ&pg=PA21&lpg=PA21&dq=np-hard+completing+hadamard+matrix&source=bl&ots=8sKv9bAtc8&sig=ITZSmtD2p2xr6Q4RDqhbQQk0NDI&hl=en&sa=X&ved=2ahUKEwiotuLdvfzdAhWBKHwKHUF9AO0Q6AEwB3oECAMQAQ#v=onepage&q=np-hard%20completing%20hadamard%20matrix&f=false, to give two ) it is claimed that determining the "equivalence" of two Hadamard matrices (in the sense of allowing sign-flips and permutations on rows and columns) is NP-hard. No source I found for this statement provided a citation, and I couldn't find any paper claiming to prove this.

On the other hand, https://core.ac.uk/download/pdf/82725146.pdf provides an $n^{O(\log n)}$ algorithm for identifying equivalent Hadamard matrices. This is somewhat to be expected, since Hadamard matrix equivalence is a lot like graph isomorphism. (It's also not hard to reformulate Hadamard matrix equivalence as a GI problem on $O(n^2)$ vertices directly, leading to a quasipolynomial solution under a variety of well-studied GI algorithms.)

If both of these claims were true, of course, this would be big news and violate the ETH. Is the claim of NP-hardness just a (false) folk theorem?


texts: Difference between Turing machine and Universal Turing machine

texts: I've read what a Turing machine and a UTM are, but I don't get the difference. What can a UTM do which a normal Turing machine can not?


texts: Conditions for string substitution commutativity

texts:
Let's say I have two substitutions given [a:=b] and [c:=d]. What are some conditions that hold for a,b,c,d ∈Σ* iff forall s∈Σ* s[a:=b][c:=d]=s[c:=d][a:=b]

Also you can assume that a,c≠ but you cannot assume so for b and d.


texts: If $f(n)=\Omega(g(n))$ and $h(n)=\theta (g(n))$ then does this implies $f(n).g(n)=\Omega(g(n).h(n))$?

texts:
If $f(n)=\Omega(g(n))$ and $h(n)=\theta (g(n))$ then does this implies $f(n).g(n)=\Omega(g(n).h(n))$

I saw a proof where they have proved  If $f(n)=O(g(n))$ and $h(n)=\theta (g(n))$ then this implies $f(n).g(n)=O(g(n).h(n))$.

So I thought may this should also hold. I have taken some examples and the formula holds on all of them. However I can't be sure. There can be a contradicting case.


texts:
Wikipedia says that

There are several practical methods of computing minimal unsatisfiable cores.

but I cannot find any. I suppose that “practical methods” means polynomial algorithms. Be careful, a polynomial algorithm, that finds a minimal unsatisfiable core of a given CNF $F$, doesn’t mean that $P=NP$, because the algorithm could output a Boolean formula $G$ such that if $F$ is unsatisfiable, $G$ is a minimal unsatisfiable core of $F$; if $F$ is satisfiable, $G$ is a subset of the clauses of $F$ and  it is satisfiable. Therefore, the output of the algorithm is a CNF but we don’t know if it is satisfiable or not.


texts:
(I've been stuck on this homework assignment for far too long)

I need to find the number of independent sets in a tree.

For example, say the set of nodes in a tree is {A, B, C, D, E}. B and C are children of A and D, E are children of B. This tree has 14 independent sets.

I assume that the algorithm will be recursive and I think that I should make each level of a tree into a linked list, so B->C and D->E, but more than that I'm stumped.

Would grealy appreciate help.


texts: Linear Programming Problem - what is feasible size for solution on a PC

texts:
I need to get feeling for the feasible size of a LPP, that can be solved on a PC.
Say, its a good one (8 cores @ 3+GHz,  64GB RAM).
We also assume that number of variables is close to the number of additional conditions.
I know it depends on the solver, but what size is feasible for solution in several hours/few days?
1000 of variables? A million?
Order of magnitude would be enough.
Update. Let's consider a general form:
matrix is not sparce/diagonal/blotchy or whatever.
Let's say matrix's rows are filled with many hundreds of values (@ thousands of variables).


texts: Why encoding of graph in adjacency matrix is $\Omega (\sqrt n)$?

texts:
in the textbook of CLRS, p.1062 he says the following:

  if we use "reasonable" encoding of a graph as its adjacency matrix, the number m of vertices in the graph is $\Omega (\sqrt n)$, where n = |$\langle G\rangle|$ is the length of the encoding of G.

I want to know why $\Omega (\sqrt n)$? I mean it is adjacency matrix which takes $m^2$ but I don't know how he calculates it, so I would like someone to explain to me how we get this time complexity?

Thank you!


texts: Represent an octree as a binary tree of thrice the depth?

texts:
In an octree, each node has up to eight child nodes. This can be implemented with eight pointers per node that are set to null pointers if the child is not used. Another implementation uses a byte as bit-mask that stores which children are used and a pointer to the first child. The children are stored consecutively then.

I'm interested in ray-tracing of sparse voxel octrees, so finding the first intersecting leaf with a ray is the main operation on the tree.

To simplify current implementations, I wonder whether it would make sense to represent an octree as binary tree that at each node bisects the space exactly in the middle. The depth layers would alternate between the three possible orientations of the cutting plane. So three levels of the binary tree correspond to one level in an conventional octree.

YZ-plane (root)
XZ-plane
XY-plane
YZ-plane
...

This is similar to the idea of k-d trees, which are binary trees for space partitioning as well. However, they store cutting planes with the nodes to allow for uneven partitioning.

Is there a difference between the octree and a binary tree of three times the depth, or are they equivalent? If there is, why is the octree used more commonly? I haven't found any reference of someone using the explained binary tree for space partitioning. Maybe I'm just missing the correct term for it though.


texts: Create a shallow logic circuit that increments a binary number

texts:
This circuit should be reasonably efficient in size and depth, but with priority on depth.

If depth was not a concern, then I guess I could make a specialized adder for the least significant bit and then modelled the rest of the circuit as a ripple adder with only that initial, possible carry. The carry has to ripple through the first sequence of consecutive bits set to 1. For example:

$inc(0111) = 1000$
$inc(0001) = 0010$
$inc(0100) = 0101$ (no ripple)

But this takes linear time, in the worst case (binary string is $1...1$). How do you optimize for depth? Does the optimal circuit have a $log_2(n)$ depth?

Is perhaps the best strategy to use a parallel prefix circuit? If so, I guess one would make a specialized adder for the least significant bit. Then you have the result of the least significant bit, which is 0 if a carry was generated, 1 otherwise. If a carry was generated, then you need to efficiently ripple it through all the adjacent, consecutive 1-bits. If one is to use a prefix sum, then you need an associative binary operator. It also needs to preserve the value of the bits that are not part of the initial, consecutive 1-bits (from right to left). This might mean that you pass in the carry bit that was (possibly) generated after the increment on the least significant bit, while the rest of the operators gets fed predefined bits which preserve the values of the relevant bits of the number (bit vector).

At this point, I'm stuck.


texts:
When NOPs are introduced in the pipeline by the control unit, how does they really cause the pipeline to stall? I mean, at every clock cycle, the pipeline register will eventually forward its contents to the very next stage, so how does NOPs prevent that from happening?

Also when NOPs are introduced the PC doesn't increment and no fetch occurs? How does that happen?


texts: Generating all maximal lists from a graph

texts:
I define a list to be a path where every vertex along the path has precisely two edges, except possibly the starting and ending vertex. In the language of electric circuits, I'm interested in finding all components that are in series for a given circuit. I'm specifically interested in finding all maximal lists.  As noted in the comments:

if $a \rightarrow b \rightarrow c \rightarrow d$ is a list, then so, too, is $a \rightarrow b$.  However, since this list is contained within the first, (it's a sub-list, I guess) I want the largest list containing it.

Is there an efficient way of doing this?

My thoughts are something that seems too complex - start at an arbitrary vertex that has not yet been visited. If its degree is 2, then it lies on a list. Move along this list until you find a vertex that has degree 1 or degree > 2 (you've found the end of the list), or until you end up back at your original vertex (the graph is a loop). Move back along the list, marking all vertices along it as visited, and writing down the nodes you've visited until you find the other end. Repeat until you're out of non-visited vertices.

On the other hand, if your initial vertex does not lie on a list, then it is potentially an end point of one. Check the degree of all vertices connected to it. For any of them that have degree 2, continue as above.

This seems drastically inefficient. Is there:

a) A term for such a thing?

b) An efficient algorithm for finding them?

I've asked on math stack exchange and they mentioned that this sounds like an "ear decomposition", but I don't think so, due to the constraint that all nodes along the path must have 2 edges only.


texts: Async Distributed Algorithm Time Complexity

texts:
In theory of distributed systems, I understand message complexity and time complexity are common performance measures, with the first being the number of messages sent in the overall execution of the algorithm, and the time being the number of "steps" it takes to complete the algorithm.

My question is, with asynchronous distributed algorithms, where we assume that at least one message is received and processed per step, how can the time complexity differ from the message complexity? If I have to send m messages to complete the algorithm, it seems to me the worst case time complexity would be $m$, sending one message per time step. For example, the time complexity of an async flood algorithm is $O(n)$ while the message complexity is $O(m)$. Why is the time complexity not $O(m)$ too? Here $m$ is the number of edges and $n$ is the number of vertices. Same goes for constructing a rooted spanning tree.

Again, this is for async systems where messages don't have to be received in parallel.


texts: For a graph to be connected, you need at least n-1 edges rigorous proof

texts:
This fact seems obvious but I was unsure how to go about proving it very rigorous.

Let $|V| = n$ and $|E| = m$ for some connected graph $G$. Then consider the following proposition:

  If a graph is connected then $|E| \geq n-1$, i.e. it needs at least n-1 edges.

The fact seems simple and maybe obvious but I was unsure how to rigorously prove the implication. Maybe contrapositive?

The issue that I have with it is that it nearly feels like an axiom. Is there a way to conclude this without assuming it to be true?


texts:
I don't understand the proof of below sentences.

$O(f(n))=O(g(n)) \iff \Omega(f(n))=\Omega(g(n)) \iff \theta(f(n))=\theta(g(n))$
$f(n)=\theta(g(n)) \iff g(n)=\theta(f(n))$

How can I prove these statements?


texts:
A set of English words is given.
Is there linear or sublinear algorithm to build minimal DFA for the given dictionary?
I tried different approaches, and they all were concerned with building Trie and then minimizing such automata.
So it is very interesting for me is there some algo using it to solve my problem.

P. S. The problem must be quite common because of DFA connection with regexps, and at the same time its statement seems like special case, so I think I am missing some simple idea.


texts: Worst known case for log rank conjecture

texts:
The log rank conjecture states that there is some universal constant $c > 0$ so that

$$CC(f) = O(\log^c \text{rk}\,(M_f))$$

where $f : X \times Y \to \{0, 1\}$ is a boolean function, $CC$ denotes the deterministic communication complexity, $M_f$ is the $|X| \times |Y|$ binary matrix associated to $f$, and $\text{rk}\,(M_f)$ is the rank of $M_f$ calculated over the reals. In the literature, it mentions that this $c$, if it exists, is at least $\log_3 6 \approx 1.631\ldots$, and attributes this to an unpublished result of Kushilevitz in 1994.  Does anyone know what example Kushilevitz uses to achieve this lower bound? I think it would be interesting to see what the worst case might be and it might give insight into how to solve the problem in general.


texts: What do I need to study in order to understand and design a programming language?

texts:
What do I need to read in in order to :

understand the specs of an already made programming language
Design a programming language
Design a compiler and assembler for that language
make an architecture of a processor


texts:
Assume I have a list of functions, for example

$\qquad n^{\log \log(n)},  2^n, n!, n^3, n \ln n, \dots$

How do I sort them asymptotically, i.e. after the relation defined by

$\qquad f \leq_O g \iff f \in O(g)$,

assuming they are indeed pairwise comparable (see also here)? Using the definition of $O$ seems awkward, and it is often hard to prove the existence of suitable constants $c$ and $n_0$.

This is about measures of complexity, so we're interested in asymptotic behavior as $n \to +\infty$, and we assume that all the functions take only non-negative values ($\forall n, f(n) \ge 0$).


texts: Markov Model to compute the probaility on the $n^{th}$ day

texts:
This is a question about Markov Models. Let's say we have the following situation

Let's say that we want to find the probability that $2$ rainy days follow a nice day. You'd simply have $0.25 \cdot 0.5=0.125=12.5\%$. However let's take it up a notch. What's the probability that on the $7^{th}$ day it's snowy? Or in general how would you find the probability that on the $n^{th}$ day it's a certain weather?

I think that you could take one possibility of a sequence of events, such that on the $7^{th}$ day it snows, such as nice, rain, snow, nice, rain, snow and snow which has a probability of $0.1953\%$ and then add all such probabilities but I'm not a 100% sure.


texts: Can I show that project scheduling is a type of programming or something similar?

texts: Project schedules are made of activities, durations associated with each activity, and relationships between activities (SS, SF, FS, FF) with a lag (can be positive, negative, or 0). Let's say I have 3 activities A, B, and C with durations of 2, 3, and 4 respectively and FS relationships between A & C and B & C. A and B will both start on day 1, A will finish at the end of day 2, B will finish at the end of day 3, C will start on day 4, and C will end at the end of day 6. I'm finishing a work term report after working as a scheduler and I'm trying to get it counted as software engineering experience. I vaguely remember one of my professors explaining monoids to me and I feel like I could use that, but I'm not 100% sure.


texts: Is the superset and subset of a semi-decidable language also semi-decidable?

texts:
Given three languages $L_1, L_2, L_3$ with $L_1$ and $L_3$ being semi-decidable and $L_1 \subseteq L_2, L_2 \subseteq L_3$. Can I deduce from these properties, that $L_2$ is also semi-decidable and how would I proof this?

Intuitionally it seems obvious that $L_2$ is also semi-decidable, but I didn't find a way to prove (or falsify) it.

So far I only found information about the closure of semi-decidability under $\cup$ and $\cap$. Can I use these properties in any way?


texts: How to structure device driver software?

texts:
I'm asking here for both the scientific, programmatic, and structural format of a device driver. What does that mean? Basically, I'm not asking how to write a driver in general ... I'm asking how to structure one to behave as software that can act as the "middleware" between higher-level code and the hardware itself. I've decided to embark on a journey of low-level computer programming (e.g. systems programming)
to develop reusable software that can "expose" accessibility of hardware memory access by driver calls.

I basically run a freelance group of a small programming team/company, and I've decided to take on development across various retro-gaming platforms from the ground up (those which have decent documentation, or reverse engineering will endue). What I'm asking here is how would one envision the development or structure of software that can act as a intermediary between the application software and the hardware; developmentally, structurally, and programmatically. My choice of console was originally the Nintendo 64's GPU (which I have documentation for). The issue isn't with writing the code to access the GPU, it's with developing a reusable driver/graphics engine (I'm new to it).

I would have asked this at Programmers.SE, but they reject these kind of questions since they're not about specific programming issues, but about careful design methodologies, modularity, and structuring.

So I'll ask again with hope to receive a somewhat explanatory answer on this process ... how do I go about the design methodology, structural format, or developmental logic to create a piece of software that can be accessed by other software to enable device access modularly? In other words, how do I structure and design a driver (i.e. what procedure should I take in creating such software)?

Again, to clarify, I am not asking how to write a driver, but how to go about structuring the system, methodology, and behavior of a driver. Are there any specific ways of going about this that prove successful (e.g. certain data types to define behavior for accessibility, methods used in accessing parts of a driver independently, etc.)?


texts: What is the best algorithm known to learn the regular expression from a set of positive examples?

texts:
I have a blackbox program that generates a set of strings. What is the best regular expression learner that I can use to learn (approximate) what the blackbox program uses as a generator? Note that I only have positive examples. (Checking whether a string is accepted or rejected is possible but rather costly). I see that algorithms like RPNI and L* requires both positive and negative examples.

I especially want to avoid over-generalization.

Update: I have been making do with using Sequitur to identify repeating patterns in single strings, and then lining up the resulting patterns to identify common repetitions. However, this feels really kludgy and I would like to improve it. Is this the best one can do? are there better ways?


texts:
I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph.

For example in the article Optimal state-space lumping in Markov chains they provide the following definition of a CTMC (continuous time Markov chain):

  We consider a finite CTMC $(\mathcal{S}, Q)$ with state space
  $\mathcal{S} = \{x_1, x_2, \ldots, x_n\}$ by a transition rate matrix
  $Q: \mathcal{S} \times \mathcal{S} \to \mathbb{R}^+$.

They don't mention the Markov property at all, and, in fact, if the weight on the edges represents a probability I believe the Markov property trivially holds since the probability depends only on the current state of the chain and not the path that lead to it.

In an other article On Relational Properties of Lumpability Markov chains are defined similarly:

  A Markov chain $M$ will be represented as a triplet $(S, P, \pi)$
  where $S$ is the finite set of states of $M$, $P$ the transition
  probability matrix indicating the probability of getting from one
  state to another, and $\pi$ is the initial probability distribution
  representing the likelyhood for the system to start in a certain
  state.

Again, no mention of past or future or independence.

There's a third paper Simple O(m logn) Time Markov Chain Lumping where they not only never state that the weights on the edges are probabilities, but they even say:

  In many applications, the values $W(s, s')$ are non-negative. We do
  not make this assumption, however, because there are also applications
  where $W(s, s)$ is deliberately chosen as $-W(s, S \setminus \{s\})$,
  making it usually negative.

Moreover, it's stated that lumping should be a way to reduce the number of states while maintaining the Markov property (by aggregating "equivalent" state into a bigger state). Yet, to me, it looks like it's simply summing probabilities and it shouldn't even guarantee that the resulting peobabilities of the transitions to/from the aggregated states are in the range $[0,1]$. What does the lumping actually preserve then?

So, there are two possibilities that I see:

I didn't understand what a Markov chain is, or
The use of the term Markov chain in those papers is bogus

Could someone clarify the situation?

It really looks like there are different communities using that term and they mean widely different things. From these 3 articles that I'm considering it looks like the Markov property is either trivial or useless, while looking at a different kind of papers it looks fundamental.


texts: Domain theory: Definition of isomorphisms

texts:
Consider the following definitions of CPOs, monotonicity and continuity:
The pair $(M, \leq)$ is called CPO (complete partial order), if

$M$ is a set,
$\leq$ is a partial order on $M$,
there exists a least element according to $\leq$ in $M$ (called bottom, $\bot$),
for every chain $m_0, m_1, m_2, \dots$ in $M$ its supremum $\bigsqcup \{m_0, m_1, m_2, \dots\}$ (least upper bound) exists in $M$.

(where a chain is a sequence $m_0, m_1, m_2, \dots$ of elements in $M$ such that for all $i, j \in \mathbb{N}$ $m_i \leq m_j \vee m_j \leq m_i$ holds)

A function $f \colon M \to N$ between two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ is called monotone if for all $a, b \in M$

$$a \leq b \implies f(a) \sqsubseteq f(b)$$

holds.

A function $f \colon M \to N$ between two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ is called continuous, if it is already monotone and for all chains $m_0, m_1, m_2, \dots$ we have

$$f\left(\bigsqcup \{m_0, m_1, m_2, \dots\}\right) = \bigsqcup \{f(m_0), f(m_1), f(m_2), \dots\}.$$

I read in a book using above definitions that two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ are isomorphic if there exists a function $f \colon M \to N$ such that

$f$ is bijective
$f$ and $f^{-1}$ are continuous (and therefore monotone).

I understand the demand of $f$ and $f^{-1}$ being monotone, so that they preserve the order.

Question:
Why is this not sufficient? Why do we also demand $f$ to be continuous? Why its inverse function too? What are examples where a violation of one property would result in a strange view of equivalence?
Another question: Is it possible to drop one property, because the other would imply it? I'm thinking about to demand only $f$'s continuity and to show that $f^{-1}$'s continuity follows – however I was not able to do so, or to come up with a counter example.

Edit: I suggest a »domain theory« tag.


texts: what is the time complexity for binary division by repeated subtraction?

texts:
The divisor and dividend are of length n and m bits respectively.

According to Wikipedia article,
https://en.wikipedia.org/wiki/Output-sensitive_algorithm
division by substraction is an output sensitive algorithm and has the time complexity of Θ(Q). Can the time complexity be calculated in terms of length of input bits?


texts: Local and Global storage with multithreading pools + locking threads

texts:
I am having difficulty answering the following questions relating to the use of threading.

Question 1 is of relating to the possibility of a local storage per thread and a global storage accessible to all threads. Consider the following scenario; A program creates a series of threads each with their own local storage, kind of like a mutex system except for that no thread can access another's memory, and a square matrix stored in global storage which is accessible to all threads. When the space complexity of the following program is calculated, is the space complexity (# of elements in the square matrix)2 + (local storage of finishing thread) or (# of elements in the square matrix)2 + (local storage of all threads at the time that the finishing thread completed)?

Question 2 relates to timing threads to go at a very precise rate. Consider the following scenario; A program creates a series of threads that continually add a random set of elements to their local storage. The program finishes and returns the thread that received the shortest number of elements in its random set. If one thread was to go faster than another, the program would be incorrect. Is there a way to "lock" the threads to go at the same speed?

Any help on the answering of these questions would be appreciated. Please comment if additional info is required.


texts: Are there simple core languages which are consistent and expressive?

texts:
The Calculus of Constructions is a very simple core functional language with dependent types. Per curry-howard isomorphism, it could, potentially, be very useful for writing programs and proofs. It, though, has a few problems: induction isn't derivable, it isn't possible to prove 0 != 1, and pattern matching on algebraic data structures take linear time. In order to solve those issues, practical languages such as Coq are based on the Calculus of Inductive Constructions instead, which add a layer of primitive datatypes on top of CoC. That, unfortunately, makes the core language very complex.

An alternative solution to those problems is a new primitive, self, which is a construction that allows a type to reference its typed term. This construct, together with the Parigot encoding, and a slightly weakened but still useful notion of contradiction, is sufficient to solve the problems above. The proposed language, though, is still somewhat complex. In particular, it has different Pi types, complex kind machinery and requires a restricted form of recursion (for the Parigot encoding).

Is it possible to be simpler? I.e., can the calculus of constructions with only self types and nothing else from this paper still be able to derive induction and employ the parigot encoding?


texts: What is the exact definition of undirected graph, directed graph, unidirectional graph, bidirectional graph?

texts: I've read many literature papers, but I still cannot understand their exact formalization definitions. Is their any difference among them or is there any relationship among them?


texts:
I wonder what is the fastest way to check whether the intersection of a set of half-spaces is empty.

Right now I'm using a linear programming formulation (with Gurobi as solver) to check if there is any feasible solution to a linear program constrained with a lot of linear inequalities. Is it possible to perform the feasibility check without actually optimizing an objective function? I know that there are polynomial time optimization algorithms in O(n^3.5), but is it possible to reduce the time even more by skipping the linear optimization part?

In particular an iterative algorithm may be very beneficial for me, since I'm adding and removing inequalities to the system all the time and after each addition, I'm checking the feasibility again. Thus, the best would be a king of inductive approach which (using some previously collected information) quickly determines if the set stays feasible after addition of a new inequality.

I would prefer to write my own piece of code for this problem instead of using a 3rd party solver library.

I have seen a related post, but my question targets a general set of equations.


texts: Inferences about Branching in TSP algorithm

texts:
I am building a program that uses branching-and-bounding to find an optimal path in a complete graph (the heuristic, faster algorithm is the second part). I have to begin and end at node 0. I was given a large hint that eliminating "hopeless" branches early in the algorithm will lead to an overall much faster runtime. I have tried several things: greedily selecting the smallest edge as either the first or last edge in the tour, branching into two subsets of solutions with one branch being solutions including the smallest available edge and the other being solutions that exclude the largest available edge. Neither have proved to be worth any salt, and I was wondering if there were any clever optimizations to branch-and-bound I could implement to help speed up my program. Any help will be appreciated!

Edit: any advice on computing better bounds and how to use them effectively is also welcomed.


texts: Is the language that accepts strings concatenated with their reverse regular?

texts:
If the set of regular languages is closed under the concatenation operation and is also closed under the reverse operation ($x^R$ is the reverse of $x$) then is the language generated by $$\{ww^R|w\in\Sigma^*\}$$ for some input alphabet $\Sigma$, also regular? If not, why not?

I've been trying to find a proof for this using the pumping lemma, but it seems that selecting any substring towards the middle of the string being pumped could also be of the form $\{ww^R|w\in\Sigma^*\}$, causing the original string to remain in its original form.

Here's a try:

$\textbf{Theorem:}$ The language, $A$, generated by $\{ww^R|w\in\Sigma^*\}$ is not regular.

$\textbf{Proof:}$ Assume $A$ is regular (We will use the Pumping Lemma for Regular Languages to show a contradiction). Let the input string $s$ be $ww^R$ and let $p = |w|$.

When splitting $s$ into substrings $x, y, z$ such that $s=xyz$ we see that $xy$ must be a substring of $w$ by the third condition of the Pumping Lemma ($|xy|\le p$).

By the first condition of the Pumping Lemma, we see that all strings of the form $xy^iz$ must be in $A$ for all $i \ge 0$. Taking $i$ to be zero, we obtain the string $xw^R$. $|x| < |w^R|$ so $xy^0z \notin A$.

QED? What if $xw^R$ can still be split so that for some substring $k$, $kk^R = xw^R$?

I think I may be overthinking this but it's really bugging me.


texts: Can the lambda functions in Church numbers be swapped?

texts:
I've learned that one can represent natural numbers with lambda calculus like this:

\begin{align*}
c_0 &= \lambda s. \lambda z. z\\
c_1 &= \lambda s. \lambda z. s~z\\
c_2 &= \lambda s. \lambda z. s~(s~z)\\
c_3 &= \lambda s. \lambda z. s~(s~(s~z))\\
\end{align*}

But could one also write

\begin{align*}
c'_0 &= \lambda z. \lambda s. z\\
c'_1 &= \lambda z. \lambda s. s~z\\
c'_2 &= \lambda z. \lambda s. s~(s~z)\\
c'_3 &= \lambda z. \lambda s. s~(s~(s~z))\\
\end{align*}

?

Why / why not?


texts: HandyAR finger tip detection and tracking

texts:
I am reading this paper Handy AR.

As suggested I am adding certain quotes from paper to get basic idea of what is it about :

Intro

  In this paper, we present and evaluate a method to use a
  user’s bare outstretched hand in the same way a cardboard AR
  marker would be used, enabling spontaneous tangible user interfaces
  in mobile settings

Steps:

Adaptive Hand Segmentation

  Given a captured frame, every pixel is categorized to be
  either a skin-color pixel or a non-skin-color pixel. An adaptive
  skin color-based method 17 is used to segment the hand
  region. According to the generalized statistical skin color
  model 14, each pixel is determined to be in the hand region
  if the skin color likelihood is larger than a constant threshold.
  In order to adapt the skin color model to the illumination
  change, a color histogram of the hand region is learned for
  each frame and accumulated with the ones from the previous
  n frames (n = 5 works well in practice). Then the probability
  of skin color is computed by combining the general skin
  color model and the adaptively learned histogram.

Accurate Fingertip detection

  Fingertips are detected from the contour of a hand using a
  curvature-based algorithm similar to the one described in [2].
  We then fit the curvature points to ellipses in order to increase
  the accuracy. The curvature of a contour point is measured on
  multiple scale levels in order to detect fingertips with various
  sizes as follows: The points with higher curvature values than
  a threshold (on any scale level) are selected as candidates for
  fingertips.
  Since the detection algorithm may produce false positives
  of fingertips for initial detection, we choose the most frequently
  detected points above the center of the hand for a
  certain number of consecutive frames as our final fingertips.
  Thus, for initial detection, the hand has to be held fingers
  up, which is the most convenient and by far the most common
  pose anyway. After fingertips have been detected, we
  eliminate false positives by tracking a successful configuration
  over time.

FingerTip Tracking

  Once fingertips are detected, we track them based on
  matching the newly detected fingertips to the previously
  tracked fingertips. Similar to 21, we track the fingertip trajectory
  by a matching algorithm that minimizes the displacement
  of pairs of fingertips over two frames. In addition, we
  use our knowledge about the centroid of the hand blob to effectively
  handle large movements of the hand as follows: The
  matching cost is minimized as the formula I mentioned below.

I have a couple of doubts in this :
1. In the 2nd paragraph of the 2nd points of steps:

  After fingertips have been detected, we
  eliminate false positives by tracking a successful configuration
  over time.

What does 'successful configuration over time' mean?
If we already are tracking a successful configuration , then why are there false positives.

2.In the next section, Fingertrip tracking has been explained. From what I understood , it has two parts

Using a matching algorithm
Using centroid to effectively handle large movenments.

My doubt is in the second part, I am not able to understand properly how does it handle large movenments and also the correctness proof of that statement.

Formula for fi+1

where fi fi+1 are the sets of N fingertips at the ith and
i + 1th frame and
 Ci , Ci+1 are centroids at ith and i + th frame.

Citation -

I got this from 1 paper published by Taehee Lee, Tobias Hollerer in 2007 11th IEEE International Symposium on Wearable Computers

Handy AR


texts: Can a DPDA decide if two letters appear the same number of times mod 5?

texts:
$ L = \{ w  ∈\{0,1\}^* \mid      |w|_0 = |w|_1 \mod 5 \}$

So i tried figuring out why this is CFL and whether its DCFL or not but i couldn't come up with any PDA!

I'm studying for my exam and this was on the book, the book says its CFL but doesn't say whether its DCFL or not and does not draw any PDA for it!

i tried making 5 states and go to the next state everytime i see a 0 {because 0 will always be between 0 and 4} but didn't work

also $|w|_0$ means number of 0's


texts: Problem with understanding two sided Matching Algorithm: maximium cardinality

texts:
I am trying to understand the maximum cardinality problem in the context of stable matching algorithm. I am reading the following article at the link:

A Two-Sided Matching Decision Model Based on Uncertain Preference Sequences

The article says that:

  In general, we can categorize two-sided matching problem into three
  typical kinds of models in terms of different decision objectives:
  stable matching, maximum cardinality matching, and maximum weight
  matching. In the first model, the objective is to seek a stable matching
  solution, and we count a solution as stable matching only when there
  does not exist any alternative pairing (, ) in which  and  are
  individually better off than they would be with the element currently
  matched. Gale and Shapley put forward an approach, also named
  Gale-Shapley algorithm, to get a stable matching solution in the
  perspective of mathematics and game theory, which symbolizes the
  beginning of two-sided matching research and enlightens the subsequent
  scholars to pay more attention to this topic. In the second model, the
  objective is to seek a solution in which the number of matching pairs
  is maximized.

I am able to understand stable matching. I can’t understand how the number of matching pair is maximized. This may occur because we have 2 sets. One of boys and other of girls. One element in one set has more than
one matching in the other set. This might occur due to preference sequence.
Am I right about maximum cardinality?

What I understand preference sequence as the order of preferences of elements of one set for the other. Due to maximum cardinality, it is possible  that element
Of one set has same preferences for  multiple elements of the other set.

Am I right about preference sequences?

Somebody please guide me.

Zulfi.


texts: Any mathematical tools for analyzing mutable memory

texts:
Wondering if there are any documents, theories, or methodologies for dealing with mutable memory mathematically. Basically a formal algebraic model of how computers manipulate memory. Along the lines of, say I want to model an add operation at a low level, and it writes its output to a register. Then we can model the computer state as a memory, and:

$$add : a \times b \times m \to m'$$

the function $add$ transforms the memory into a different state, holding the final value. Then the second time we call add, the memory is different than it was before. So it's always changing:

$$m \neq m' \neq m'' \neq \dots \neq m^{(n)}$$

Wondering if there are any formalisms out there that deal with this. I would specifically like to see it applied to abstract algebra or category theory. Whereas in abstract algebra typically, everything is immutable and you never worry about "state". I would like to explore the state / mutable memory from a math framework.


texts: Is there any property about height of PDA?

texts:
I'm trying to find a PDA for $L$ which modifies the stack height at most one.

$L=\{a^ib^i\mid i\geq 0\}$

I think there is no such PDA but how can I prove it?

My attempt is for a given string, find a relationship between stack height in PDA and  leftmost derivation in CFG then prove that there's no CFG which satisfies the condition using pumping lemma. But I couldn't find any relationship. Am I doing right way?

Any help appreciated.


texts: Identifying system events affecting timing behavior of an application

texts:
Q: What are those events (system level and architecture level) that can cause an application to take longer to terminate and complete the job?

My question is purely in the context of Worst Case Execution Time (WCET) analysis.

I have gathered a short list of events, which I think are the contributors to WCET of an application, by utilizing some knowledge about computer-architecture:

A wrong branch prediction
Cache misses
Pipleline stalls
Fetch related delays
. . .

I would like to enrich this list both in breadth and length. So any addition to the list of such events or the details of how any particular event causes a delay is most welcomed.

P.S. If my question if not well formulated, please do help me to improve.


texts: Iterated multiplication of permutation matrices

texts:
Given $m$ matrices of size $n\times n$ each of which is promised to be a permutation is it in $\mathit{quasiAC}^0$ or $\mathit{AC}^0$ to multiply the permutations where

$m=\mathit{poly}(n)$
$m=\mathit{poly}(\log n)$ which means $m=O(\log^k n)$ where $k\in\mathbb N_{>1}$
$m=O(\log n)$?

Given $\mathit{poly}(n)$ inputs it is clearly in $\mathit{AC}^0$ to test the promise every input matrix is a permutation.
On other hand general iterated matrix multiplication is is $\mathit{NC}^2$.


texts: State Machine and State transition Table - Explanation and Creation Of

texts:
How do I create a state transition table/array in actual code/pseudo-code?

I haven't experienced the "ah-ha" moment yet with the state machine to coding (and I really want to). I've looked at several code sample and read blog posts, but it's not clicking yet.

I'm looking for a pragmatic explanation of how the state transition table works and how it's created in an array format. If possible, is there a "step-by-step" method to get to the solution?

The particular case/excercise I'm working on is this:
I'm writing a gray-code rotary encoder driver for A micro-controller based on the .netMF framework. It's not real-time and therefore changes the rules a little. Interrupts are captured and queued and then run in a high priority thread. There is a delay so it makes capturing the state of the both encoder pins at the actual time of interrupt in-accurate. In-accurate enough to cause some errors. That being said, when the interrupt is queued, it's state IS captured at that time. When the ISR is finally executed, the pin's state state is passed into it as an argument. Therefore, I can only get ONE pin's state at a time. I think that's sufficient to get this working.

Encoder States For Pin A and B:
A B
0 1
0 0
1 0
1 1 - base state(neutral position of the encoder) (move up for one direction and down for opposite direction)
0 1
0 0
1 0

The mechanical bounce in the encoders will be captured and queued as well, but from what I understand, the state machine can handle these "errors" and continue to produce a good result if the device makes it through a cycle.

I hope this question is clear. I can add additional information as needed.


texts:
I'm using Knuth's Dancing Links (dlx) algorithm to solve for solutions to tiling a 2xN rectangle using 3 different pieces of one, two, or three squares. It's working correctly in its basic form but now I want to add some additional constraints that limit how the pieces can fit together. I want the solutions to adhere to a rule that states that 4 pieces cannot share a common point. To me, this implies some sort of memor, or finite state machine, is required so that only a subset of available pieces can be used based on previous piece insertions.

To depict this graphically, if the solver has proceeded to the following state:

 > -----+--+
    >      |  |
    > -----+--+
    >      |
    > -----+

There is no other piece that can be placed that won't violate the rule so the solver would backtrack one level and try the next option. If that option happened to be

> -----+--+
>      |  |
> -----+  +
>      |  |
> -----+--+

The placement of this vertical piece means that the rule won't be violated at this stage so the solving may continue.

Can additional constraints be devised to reject states that will violate the rule as necessary?


texts:
In Arduino's architecture, multi-threading is not supported. However, interrupt handlers are being used as "placebo/replacement" if you may. However, I am not quite sure how these interrupt handlers work. For instance:

void functionA()
{    //x is a global boolean
    x = true; //as soon as this is set to true, before the next line executes, it jumps to functionB
    int y = 10;
}
void functionB()
{
    while(x) executeSomeOperation;
}

Something of that sort takes place(forgive my crude code, it is just to get my point across). More specific examples can be found in the VirtualWire library of Arduino. How is that possible without multi-threading? Because as function A is taking place, the program must surely be waiting to see if x is being set to true. Which sounds like "multi-threading" to me. Thus, can someone clarify the differences between how multi-threading and interrupt handlers work?


texts: Example of a false proposition when assuming Type : Type

texts: In Type Theory if one allows Type to be a member of itself, it makes the theory inconsistent. I understand it by analogy to Russel's paradox in Set Theory, but would prefer to see it done in Type Theory. Is there a short example of the equivalent in Type Theory?


texts: String matching problem needed some explanation

texts:
This is a question from CLRS book. (Chapter 32, string matching, the question is the problem for the whole chapter, it's in the end of the chapter)

  Let $y^i$ denote the concatenation of string y with itself $i$ times. For example,
  $(ab)^{3}$ = $ababab$. We say that a string $x\in X$ has repetition factor $r$ if x = $y^{r}$ for some string $y\in X$ and some $r > 0$. Let $p(x)$ denote the largest $r$ such that $x$ has repetition factor $r$. Give an efficient algorithm that takes as input a pattern $P[1..m]$ and computes the value $p(P_i)$ for $i = 1, 2,\dots,m$. What is the running time of your algorithm?

I found an answer like this:
First compute Prefix function (based on the prefix function from the book), so we return $π$. Then, Suppose that $π[i] = i −k$. If $k|i$, we know that
$k$ is the length of the primitive root, so, the word has a repetition factor of $\frac{i}{k}$. We also know that there is no smaller repetition factor $i$. Now, suppose that we have $k$ not dividing $i$. We will show that we can only have the trivial repetition factor of 1. Suppose we had some repetition $y^{r} = \Pi$. Then, we know that $π[i] ≥ y^{r}−1$. However, if we have it strictly greater than this, this means that we can write the $y$’s themselves as powers because we have them aligning with themselves.

COMPUTE-PREFIX-FUNCTION (P)
1 m = P.length
2 let π be a new array
3 π[1]= 0
4 k = 0
5 for q = 2 to m
6    while k > 0 and P[k+1] != P[q]
7       k = π[q]
8    if  P[k+1] != P[q]
9       k = k + 1
10   π[q] = k
11 return π

The prefix function is a part of KMP algorithm

KMP-MATCHER (T,P)
1 n= T.length
2 m =P.length
3 π=COMPUTE-PREFIX-FUNCTION (P)
4 q= 0 // number of characters matched
5 for i = 1 to n // scan the text from left to right
6    while q > 0 and P[q+1] != T[i]
7        q= π[q] // next character does not match
8    if P[q+1] == T[i+1]
9        q = q + 1 // next character matches
10   if q == m // is all of P matched?
11       print “Pattern occurs with shift” i - m
12       q=π[q] // look for the next match

I can't still really understand completely the answer.
Why should we suppose $k$ not dividing $i$? And the explanation for the case of $k$ not dividing $i$, the repetition factor is 1, is confusing to me.


texts:
Is the grammar

$\qquad S \to 1A0A \mid 0A \mid \varepsilon$

a right-linear grammar? $A$ is a nonterminal here, $0$ and $1$ are terminals.

I know $0A$ is right-linear but what about $1A0A$?

Trying to construct a right-linear grammar for language $10(0+1)^*10$.


texts: Finding Minimum Weight Subgraph Spanning Tree

texts:
Suppose we have a graph $G = (V, E, w:e\in E \to x \in \{0,1\})$. That is, a set of vertices, a set of edges and a weight function that assigns edges weights of 0 or 1.

Suppose we also have a subset of vertices $S \subset V$ and that we want to find a minimum-weight tree that spans the vertices in $S$. Since the vertices in $S$ might not be directly connected, we are allowed to use vertices in $V$ that may not be in $S$ to build our minimum-weight tree.

Is there an algorithm similar to Prim's or Kruskal's that we can use to solve this?


texts:
I found this question in the exercise of Tanenbaum (operating systems):

  Two processes, $A$ and $B$,each need three records $1, 2, \text{ and } 3$ in a database. If $A$ asks for them in the
  order $(1, 2, 3)$ and $B$ asks for them in the same order, deadlock is not possible. However, if B asks for them in the order $(3, 2, 1)$ then deadlock is possible. With three resources, there are $3!=6$ possible
  combinations each process can request resources. What fraction of all combinations is guaranteed to be deadlock free?

I haven't gotten any farther than that there are $6$ possible ways that $B$ can request:
$(1,2,3), (1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$

Please help me out.


texts: Can I change the order of iteratorion in the Floyd-Warshall Algorithm?

texts:
I am studying how Floyd-Warshall works and came across this doubt.
In the code:

for(int k = 0; k < V; k++)
    for(int i = 0; i < V; i++)
        for(int j = 0; j < V; j++)
            Matrix[i][j] = min(Matrix[i][j], Matrix[i][k] + Matrix[k][j]);

I can see I can not change order of k because it is the intermediate vertex. The order of i and j, on the other hand, seems like don't necessarily need to be in that position.

Am I wrong?  All I can see is that they are just the combination of pairs with k in the middle.


texts:
Does Iterative Deepening DFS only guarantee the shortest path for DAGs, assuming a visited list is used to prevent infinite cycles?
I can't seem to find any answers online specifically related to cyclic graphs.


texts:
The same question has been asked here

  Some authors define $\Omega$  in a slightly different way: let’s use
  $ \overset{\infty}{\Omega}$
  (read “omega infinity”) for this alternative definition. We say that $f(n) = \overset{\infty}{\Omega}(g(n))$
  if there exists a positive constant $c$ such that $f(n) \geq c\cdot g(n) \geq   0$ for infinitely many integers $n$, whereas the usual $\Omega$ requires that this holds for all integers greater than a certain $n_0$.

  Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically nonnegative,
  either $f(n) = O(g(n))$ or $f(n)= \overset{\infty}{\Omega}(g(n))$ or both, whereas this is not true if we use $\Omega$ in place of $\overset{\infty}{\Omega}$

The solution given in the link hints that we can negate the definition of $ \overset{\infty}{\Omega}$ which gives us the definition of big O.

But negation of the definition of $ {\Omega}$ also gives us the same result, doesn't it?

I cannot wrap my head on how the condition of infinitely many integers makes difference rather than saying for all n greater than certain $n_0$.

Please help me understand this.


texts: The use of multiset ordering in proving termination

texts:
Based on the definition of a multiset and the information in this paper, why do we use multisets in proving the termination of a program?
Is not the well-founded order enough?


texts: How are problems classified in Complexity Theory?

texts:
I'm reading Sipser's Introduction to the Theory of Computation (3rd edition). In chapter 0 (pg. 2), he says we don't know the answer to "what makes some problems computationally hard and others easy," however, he then states that "researchers have
discovered an elegant scheme for classifying problems according to their computational difficulty. Using this scheme, we can demonstrate
a method for giving evidence that certain problems are computationally hard,
even if we are unable to prove that they are."

So my question is: HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?

Also, what/where is this "scheme" that does this classifying. (I did some googling and couldn't find anything)


texts: Parallel shortest path in directed acyclic graphs

texts:
Finding the shortest path in a DAG is extremely easy:

See the example here http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf

However, I cannot find a way of parallelising this code. Is there a way of doing that?


texts: Finding a convex hull for a collection of points

texts:
I have an alternative algorithm for the problem of finding a convex hull for a collection of points. It is somewhat similar but not the exact of Graham scan.

Find a point that is guaranteed to be inside the convex hull, this can be done by finding the line connecting the left most and right most points. And then pick a point between the two end points.
Use the point in (1) as origin and convert all other points into polar coordinate.
Sort all other points in counter clockwise motion and iterate (same way one orders angles in radian of the unit circle)
When the point has y coordinate higher than the origin, then the tangent value between the current point and the last point in the convex hull has to go up compared to the last tangent value. If not we need to wrap the previous points to some earlier point to satisfy this requirement.
When the point has y-coordinate lower than the origin, then the tangent value has to go down.

The running time is $O(n\log n)$ because that is of sorting and for each point in step 4 and 5, one only needs $O(\log n)$ to search for appropriate previous point.

My question is this seems much simpler than Graham scan.
Is there any problem in it (correctness) other than the running time in which iteration in Graham scan is only linear while it is $O(n\log n)$ here


texts: the meaning of heuristics in artificial intelligence

texts:
I would like to know what 'heuristics' actually means in artificial intelligence. For example, I am reading a paper by Engelbrecht on the convergence analysis of the particles of the algorithm. The section where the author discusses the mathematical reasons why the particles behave the way they do was entitled 'heuristics'. Does it, in any way, mean ... the mathematical rigour, methodology, convergence, etc?

Your insights would be helpful.


texts:
I'm a little confused by Wikipedia's definition of a regular language:

  The collection of regular languages over an alphabet $\Sigma$ is defined recursively as follows:

  The empty language $\emptyset$ is a regular language.
  For each $a \in \Sigma$ ($a$ belongs to $\Sigma$), the singleton language ${a}$ is a regular language.
  If $A$ and $B$ are regular languages, then $A \cup B$ (union), $A \cdot B$ (concatenation), and $A^\ast$ (Kleene star) are regular languages.
  No other languages over $\Sigma$ are regular.

This seems defines a regular language as any set that contains a finite number of unique elements, though the set can be countably infinite (it's worth noting that the article doesn't explicitly state that $\left\vert{\Sigma}\right\vert$ is finite in the definition), i.e., a regular language is any set $S$

$$
\left\vert{S}\right\vert \le \left\vert{\infty}\right\vert, {S} \in \Sigma \\
\left\vert{\Sigma}\right\vert \lt \left\vert{\infty}\right\vert
$$

I think this is correct because the union, concatenation or Kleene star of a singleton that is part of a finite set or the empty set must be also part of that set, even when operated on recursively.

It's been a fair while since I did any maths, and even longer since I've touched set theory. Have I completely misread Wikipedia's definition? If so, how? If I haven't how is a regular language different from my definition?


texts: Is this lower bound proof for the comparison-based sorting problem correct?

texts:
Here is a lower bound proof for the comparison-based sorting problem:

Any comparison-based sorting algorithm can be considered to work by putting elements into their final positions one by one (Take the last time one element is put into its final position.).
To put the element $e$ which is the $i$-th one being put into its final position, the algorithms should know the relative ordering between $e$ and the first $n-1$ elements that are already put into their final positions. This costs at least $\Omega(\lg i)$ comparisons.
Therefore, the total number of comparisons is at least
$$\sum_{i=1}^{n-1} \lg i = \Omega(n \lg n).$$

Is this a reasonable proof? (I am quite confused about the second step.) If so, how to formalize it more rigorously?


texts:
I have to make an algorithm that finds all the topological orders(using predecessor counting) and the highest cost paths and their costs between 2 pairs of vertices. My algorithm looks like this for now:

 def topologicalSort(self):
        sorted = []
        count = {}
        q = deque()
        for x in self.parseX():
            count[x] = self.innerDegree(x)
            if count[x] == 0:
                q.append(x)
        while len(q) > 0:
            x = q.popleft()
            sorted.append(x)
            for y in self.parseNout(x):
                count[y] -= 1
                if count[y] == 0:
                    q.append(y)
        return sorted

And the highest cost path algorithm is good:

    def highestCostPath(self, sorted, source, destination):
        distances = [-math.inf] * len(sorted)
        prev = [-1] * len(sorted)
        distances[source] = 0
        for vertex in sorted:
            if vertex == destination:
                break
            for outboundNeighbours in self.parseNout(vertex):
                if distances[outboundNeighbours] < distances[vertex] + self.Cost(vertex, outboundNeighbours):
                    distances[outboundNeighbours] = distances[vertex] + self.Cost(vertex, outboundNeighbours)
                    prev[outboundNeighbours] = vertex
        return distances[destination], prev[:]

It works fine but the problem is that is will find only one topological order. And my question would be: How can I make it to find all the topological orders?


texts:
Are there specific terms or adjectives in graph theory to name these two situations?

Two vertices are non-adjacent (disjoint? I have seen that the term "disjoint" is rather used for paths with non-common vertices or edges).
Two connected non-adjacent vertices (the shortest path or paths connecting them have a lenght $> 1$).


texts: Ackerman hierarchy for higher order primitive recursion in System T

texts:
Gödel defines in his System T primitive recursion over higher types. I found notes from Girard where he explains the implementation of System T on top of simply typed lambda calculus. On page 50 he mentions that once we use more types in the recursor we gain more expressive power with the system.

I don't understand how exactly this happens. Is it possible to come up with sort of Ackermann hierarchy with the higher order primitive recursion, i.e. a hierarchy of faster and faster growing functions where each function is expressible in System T but the diagonal is not? I guess so, but the construction does not seem evident to me and I would be interested seeing how one would construct it, or receive pointers to literature.

I'm after something concrete. I'm aware of the general diagonal argument that proves existence of a function not in T, but I would like to see how one would really "step up in the type hierarchy".


texts: Which of these languages is regular? The Pumping Lemma seems to show none are

texts:
I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular?
$$
\{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge 0\}\
$$
$$
\{\ 0^m1^{2m}0^m\ \colon\ m \geq 0\}\
$$
$$
\{\ 0^m1^n0^m\ \colon\ m\ge 0\ \&\ 0 \le n \le 1\}\
$$
$$
\{\ 0^mw\ \colon\ m\ge 0\ \&\ w \in \{0,1\}^*\ \&\ w\ \text{contains at least m 0's} \}\
$$
I have tried to apply the Pumping Lemma, but all my proofs seem to show these languages are not regular. I highly doubt the question is wrong, as the examiners' report makes not mention of it. Can anyone help be figure out which is regular?


texts: What is the order of the Pancake graph in Given example & what are the properties of Pancake graph?

texts:
Pancake graph have least diameter & degree (log n/ log log n)

pancake Graph with order-2 will be one single line with two nodes, labeled with permutation of node {12, 21}.

pancake Graph with order-3 will be one single line with one hexagonal, labeled with permutation of node {123, 132, 213, 231, 312, 321}.

Similarly for order-4 graph will be with 4-hexagonal.

This graph is in three dimension or four dimension?
if this graph is in four dimension, then how graph will look like in three dimension?


texts:
Given a set of point $P$. Find the euclidean minimum spanning tree where each points is equally distributed on the plane using randomization.

We can solve this problem with Prim's algorithm in $O(n^2)$ which is too slow. I've found an algorithm called Delanuay Triangulation but is there any other ways to solve this problem in $O(n log n)$ or faster?


texts: Algorithm or Method to reconstruct 3D world coordinates from 2D pixels with some known corresponding real-world dimensions

texts:
I have an algorithm than can recognize the 2d pixel locations of certain 3d points within a 2d image. Ultimately we are interested in computing a real-world horizontal distance between these points. See the below example.

We have some known a-priori information about the world and the camera.
First of all, we know the real vertical distances between the two pairs of points, and this is always a fixed value in the real world (e.g. 2 meters). We hope to use this information as a reference value to somehow proportionalize to other points in the world.

Other assumptions that we have (and hence may be used in the algorithm) are

known corresponding world distances between points (vertically)
detected points line in the same plane
camera's optical axis points approximately with a right angle w.r.t. this plane
focal length f
field of view (angular)
more than 1 image taken at potentially different heights

Our current method of solving this, (i.e. obtaining the real-world horizontal distance) is by linearly extrapolating the known reference distances (vertical) to fit the pixel locations.
Now this should (and theoretically will) work perfectly given the above assumptions. However, if the pixel location is off by 1 or 2 pixels, then this can propagate back to an error of ~20 mm depending on the height. Not to mention other variations in the real world like cam angle, object height offsets etc., which may yield too big of an error. Also, this computation involves not all the information available: that is we only need 1 of the two 2 known distances and only 1 image to perform this computation.

Now I'm wondering if we can't approach this problem in a better way, by combining:
 - multiple images,
 - the information of the focal length/angle
 - and potentially multiple reference distances within the image.

Research suggest that there are algorithms like Kanade-Tomasi and back projection, but I'm not sure if they are relevant to us, because they use different assumptions (like constant distance to objects?).

Anyway, I myself was thinking in terms of a least squares approach, but not sure how to parametrize the model such that a 3d reconstruction (or real-world distances) is predicted by it, given the knowns (focal length etc.).

So I'm seeking for a push in the right direction, that can help solve our prediction/computation problem, given the above assumptions.


texts: About showing algorithmic gap instance for the Goemans-Williamson SDP

texts:
Using usual notation we have,

$SDP(G) \geq OPT(G) \geq Alg_{GW}(G) \geq \alpha_{GW} SDP(G) \geq \alpha_{GW} OPT(G)$

where we mean,

$SDP(G)$ = The maximum value that the SDP finds of the objective function $\sum_{(u,v) \in E} w_{uv}( 1-\vec{y_u}.\vec{y_v})/2$  (one unit vector $\vec{y_v}$ in $\mathbb{R}^d$ for each vertex $v$ for some $d$) And $w_{uv}$ are the given edge weights such that $\sum_{(u,v) \in E} w_{uv} =1$

$OPT(G)$ = The actual size of the max-cut for the graph

$Alg_{GW}(G)$ = The value of the max-cut returned by the randomized rounding prescription of Goemans-Williamson

$\alpha_{GW}$ = the famous constant of $\sim 0.878$

If say someone shows that for every $\epsilon$ there is a graph $G(\epsilon)$ such that $(\alpha_{GW}+\epsilon)OPT(G(\epsilon)) \geq Alg_{GW}(G(\epsilon))$ then does this imply that this is a class of graphs on which the algorithm is performing as bad as it could?
Why does showing the existence of such a family of graphs as above also  necessarily imply that on this family $SDP(G(\epsilon)) = OPT(G(\epsilon))$ ?