texts: Karp hardness of testing for homomorphisms to a fixed non-bipartite graph

texts:
Description: Suppose that we are given a fixed non-bipartite graph $H$. A graph $G$ is loopless surjectively homomorphic to $H$ if there exists a loopless surjective homomorphism $\varphi:V(G)\to V(H)$ such that:

  For every $u,v\in V(G)$,  $(\varphi(u)=\varphi(v))\lor(uv\in E(G)\implies\varphi(u)\varphi(v)\in E(H))$.

Note that we do not allow loops and multiple edges. This is just because $H$ is  a fixed simple undirected graph. So, mapping to the same vertices is good but remember to map to every vertex of $H$. This also does not put constraint on those vertices mapped to the same $H$-vertex. By standard definition, without a loop at that $H$-vertex, the set of $G$-vertices mapped to it needs to be an independent set.

We want to decide whether a given graph $G$ is loopless surjectively homomorphic to $H$. Note that for each fixed non-bipartite $H$, we have a decision problem, denoted by $\mathrm{HOMOMORPHIC}_H$.

Formally, for every fixed (i.e. not part of the input) non-bipartite graph $H$, $\mathrm{HOMOMORPHIC_H}$ is defined as below:

  Input: An undirected graph $G$

  Output: YES if $G$ is loopless surjectively homomorphic to $H$, otherwise NO

We want to know the computational complexity of this problem.


texts: Can a language have $\Sigma^{*}$ as its syntactic monoid?

texts:
As per the title I was wondering if it's possible for a language $L \subseteq \Sigma^{*}$ to have $\Sigma^{*}$ as its syntactic monoid and if so could one give an example of such a language? I first thought that this was probably an easy question with a simple answer but I haven't been able to make much progress with it, maybe it has a simple answer and I am just overlooking it?

If we look at the syntactic congruence $\sigma_L = \{(w,z) \in \Sigma^{*} \times \Sigma^{*}: (\forall u, v \in \Sigma^{*}) \; uwv \in L \Leftrightarrow uzv \in L\}$ we see that in order to have $w \cong_{\sigma_{L}} z \Leftrightarrow w = z$ we must have that $(\forall w, z \in \Sigma^{*} \; w \not = z) \; (\exists u, v \in \Sigma^{*})\; uwv \in L \Leftrightarrow uzv \notin L$. Which seems like quite a strong condition. It's also clear that such a language couldn't be regular as it is known that a language is regular if and only if it has a finite syntactic monoid.


texts:
I have array containing the weight of ‘N’ distinct items, and two knapsacks that can withstand ‘W1’ and ‘W2’ weights, the task is to find the sum of the largest subset of the array, that can be fit in the two knapsacks. And it’s allowed to break any items between 0 to 1, i.e an item should be put in one of the bags as a whole.
The question is there any greedy algorithm that solves this problem?


texts: A new definition of recursively enumerable set?

texts:
Given a Turing machine $M$, we associate a partial function $f_M : \Sigma^{\ast} \to \Sigma^{\ast}$ to it (this is called the function computed by the machine), where $\Sigma$ denotes the finite input and output alphabet, defined as
$$
 f(u) = v :\Leftrightarrow \mbox{The machine halts on input $u$ with output $v$}.
$$
Then we say an arbitrary partial function $f : \Sigma^{\ast} \to \Sigma^{\ast}$ is called computable iff $f = f_M$ for some Turing machine $M$.

Then we define a language $A \subseteq \Sigma^{\ast}$ to be recursively enumerable iff it is the domain of some computable function. Clearly with the above definition $\operatorname{dom}(f_M) = \{ w \in \Sigma^{\ast} \mid \mbox{The machine halts on input $w$.} \}$, i.e. this is equivalent to say that a language is recursively enumerable iff we can find a machine that halts exactly for the words in the language.

But on other sources I found the following definition, a language $A \subseteq \Sigma^{\ast}$ is recursively enumerable, iff there exists a Turing machine such that
$$
 A = \{ w \in \Sigma^{\ast} \mid \mbox{The machine halts in an accepting state} \}
$$
or
$$
 A = \{ w \in \Sigma^{\ast} \mid \mbox{The machine halts and outputs a specified output } \}.
$$
Both notions, by special state or special output, are clearly equivalent. But they do not require the machine to run forever if $w \notin A$. This could be fixed, by letting the machine enter an endless loop if it enters a non-accepting state after finishing its computation. But this seems quite unnatural to me.

But I think a better definition, more closely at the definition by acceptance states or special output, in terms of computable functions, would be to call a language $A$ recursively enumerable iff there exists a computable partial function $f : \Sigma^{\ast} \to \Sigma^{\ast}$ such that $A = f^{-1}(B)$ for some $B \subseteq \Sigma^{\ast}$.

Surely with the above definition we can enlarge $B$ always by values not in the range of $f$, so $B$ is not unique, but it would be no problem that the machine halts on some other input $\notin B$ and we would have $A \subseteq \operatorname{dom}(f)$.

So is this definition used anywhere, does it make sense? I could not find it, so I am asking here. Also nobody discusses the two definitions together, either in books they always work with Turing machines, or they work with primitive and $\mu$-recursive functions.


texts: Prove Context Free languages not closed under difference?

texts: Given two context-free languages $L_1$ and $L_2$, the language given by the difference of the two languages, $L_1 - L_2$, is (in general) not context-free. Is it possible to prove this without using pumping lemma?


texts: Prove that PP is closed under complement

texts:
I found this proof in Wikipedia, but one of the most important steps in it  doesn't make any sense to me. I'll explain:

  By the definition of PP there is a polynomial-time probabilistic
  algorithm A with the property that ${x\in L\Rightarrow \mathrm {Pr}
 [A(x) =  1]>\frac{1}{2}} $ and ${x\not \in L\Rightarrow \mathrm {Pr} [A(x) = 1]\leq \frac{1}{2}}$.

  Let $f(|x|)$ be the
  polynomial upper bound on the running time of A on input x. Thus A
  makes at most $f(|x|)$ random coin flips during its execution. In
  particular, $ x\in L\Rightarrow {\mathrm  {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$.

I understand that:

By definition of PP, ${x\in L\Rightarrow \mathrm {Pr}
 [A(x) =  1]>\frac{1}{2}} $. It means that if indeed $x \in L$, more than half of the possible coin flip combinations would cause the algorithm to accept.
The algorithm's running time is bound by $f(|x|)$, then the probability of getting some specific combination of coin tosses (that accepts or rejects, we do not know) is bound by $(\frac{1}{2})^{f(|x|)} = \frac{1}{2^{{f(|x|)}}}$.

But why is it so obvious that $ x\in L\Rightarrow {\mathrm  {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$?

That one specific combination of coin flips could easily be one of the half that was already counted in the definition of PP, and in that case, it would not make any sense add together "half of the possible coin flip combinations and one specific combination". What am I missing here?


texts: Finding the k-th smallest ternary sum of elements from three different arrays

texts:
The problem goes like this:

Given arrays $\{ a_i: 0\leq i \leq n-1 \},\{ b_i: 0\leq i \leq n-1 \} $ and  $\{ c_i: 0\leq i \leq n-1 \}$, we want to know what is the $k$-th smallest combination $a_r+b_s+c_t$ where $r, s, t$ are arbitrary indices.

Since $k$ is relatively much smaller than $n^3$ (we may suppose $k \approx n $ for simplicity), it would be wasteful to: naively enumerate all $n^3$ possibilities and find the $k-$th smallest using a binary heap.

What is a more efficient way (in terms of time complexity) to solve this problem? I try to optimize the naive algorithm described above by first sorting three arrays then do the heaping for $\{ a_r + b_s + c_t: r+s+t < k \}$, but I believe this is far from a most efficient algorithm. Thanks.

(Rmk: the algorithm is intended to be comparison-based, since elements might be non-integers.)


texts:
why is this Problem$$L = \{ \langle M\rangle \mid L(M) \text{ is undecidable}\}$$ undecidable?

I thought if we know $L(M)$ the turingmaschine accepts all $x \in L(M)$, so $L(M)$ is in every case decidable and $L=\emptyset$ especially finite and decidable.

I know we cannot find an algorithm but every TM has a language and we even if we don't it, we know it is decidable.

Can someone help me where I do have a misunderstanding?


texts: Existence of shortest path in a graph with no negative cycles?

texts:
Suppose that the input graph $G$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let $s$ be the source vertex.

How do I prove that for every vertex $v$ in $G$, there is a shortest $s-v$ path with $<= n - 1$ edges?

Where $n$ is the number of vertices in $G$.


texts: Descriptive complexity: 3-colorability example

texts:
So in Neil Immerman's book http://books.google.co.kr/books?id=kWSZ0OWnupkC&pg=PA113&lpg=PA113#v=onepage&q&f=false, 3-colorability problem in descriptive complexity fashion is expressed as following: $\exists R \exists Y \exists B \forall x \left[(R(x) \vee Y(x) \vee B(x)) \wedge (\forall y) (E(x,y) \rightarrow \neg(R(x) \wedge R(y)) \wedge \neg(Y(x) \wedge Y(y)) \wedge \neg (B(x) \wedge B(y))) \right]$.

My previous question seems to have been misunderstood - I was not asking about what first-order or second-order logic is, but rather on the use of quantifier. Here $\forall x$ seems to imply that universe is already predefined to refer to vertices only. Is this correct understanding? If so, why is it the case? Is it pre-defined rule of descriptive complexity usage of logic?

Also for any similar graph problems, is universe of sets restricted to vertices only, or are we allowed to add sensible sets to universe?


texts: augmenting bst - is there exist pair (a,b) of numbers such that |b-a| = d?

texts:
How to check if exist pair $(a,b)$ of numbers in BST such that $|a-b| = d$, where $d$ is given.
Example:
contain of tree: $1, 4, 5, 3, 8, 45, 532$
$d=5$,
answer: $yes$, there is pair $(5,8)$
$d=52$
answer: $no$.

I can solve it when number are in array - then I sort them, and in linear time I can find that pair. Neverthelress I can't idea how to augment BST in this task.
Can you give me a hint ?


texts: Do add commands in an pipeline wait for each other's result?

texts:
Let be given a 4-step pipeline with the steps "Get command, get operands, Execute command, Write back result" and an Assembler Code:

1 movl $1 , %eax
2 movl $2 , %ecx
3 movl $3 , %edx
4 addl %edx , %ecx
5 addl %ecx , %eax

The line 4 addl command is forced to wait until command 3 completely walked through the pipeline. After line 3 is done, results are written back, line 4 addl command proceeds.
However what does the addl command of line 5 do? Does it wait or does it immediately follow line 4 addl command?

There is no Forwarding, jump forshadowing and in the beginning pipepline is empty.


texts: Maximum number of segments with no intersection

texts:
This is an interview question.
Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: (1,3).

Two segments s1,s2 are intersecting if
 (s2.start<=s1.start<=s2.end) or (s1.start<=s2.start<=s1.end)
For example: (1,3),(2,4) are intersecting.

Find an algorithm for finding maximum number of segments in the array (and returning those segments in some list) which don't intersect.

My attempt: I thought maybe some sorting can help, but didn't find how so tried something else. Then the interviewer gave me a hint: the run time expected is O(nlogn).

So now I'm sure the solution need to involve some sorting algorithm, but I don't know how to use it.

Any suggestions?


texts:
How to change the constraint's arity from n to 3?
I know how to perform binarization of constraints, explained here: https://cw.fel.cvut.cz/b172/_media/courses/b4b36zui/binarization.pdf, but I don't know how to get a constraint of arity 3.

A ternary constraint is one based on four variables, for example, constraint $C=\{(X,Y,Z) \& X+Y=Z\}$.

And the binary constraint is simply based on two variables: $A=\{(X,Y) \& X<Y\}$.

When given a constraint of arity n, so a constraint based on n variables I want to make a ternary constraint out of it.


texts: Relations between different time complexities of an algorithm

texts:
If I have an algorithm A that, in the worst case, has a lower bound of $Ω(n\log n)$ and an upper bound of $O(n²)$, how can I go about determining possible time complexities for best and average cases?

For instance, only one of the following is possible:

a. Best case $\Theta(n)$

b. Worst case $\Theta(n\sqrt{n})$

c. Average case $\Theta(n^3)$

d. Worst case $\Theta(n)$

Now right off the bat I know we can eliminate (d) since it’s also dealing with the worst case, and being that $n$ is out of the given bounds, falling below $n\log n$.

What I’m stuck on is how to approach the other worst case option since it falls in the range and am even more confused about how to deal with the two choices that aren’t even worst case.


texts: Which permutations can not be obtained by moving elements through two stacks?

texts:
I have a Stack1 which  has the entries a,b,c ( with a on the Top) and  Stack2 which is empty.The condition is.

  An entry pooped out of the stack1 can be printed immediatly or pushed to stack2. An Entry popped out of the stack2 can only be printed.

In this Arrangement, which of the permutation of a,b,c is not possible.

I tried diagrammatically by popping out the initial stack and found the first arrangement as c,a,b...Then i mind a formula taught in Permutation's course as (n-1)! possibilites so came up with answer of 5.

so, which arrangement will be not possible.??


texts: Write-To-Read Relaxation in Cache Consistency

texts:
Write-to-Read Relaxation means that for a processor:

  later reads can bypass earlier writes

But what does that mean?
What exactly is the difference between a read and a write for a Cache?

An example we had in the lectures about Processor Consistency:

Isn't c2 also a write for w? How can it be before c1?
Why can CPU C execute c2 before c1?

Why does B see a1 before b2 while C sees b2 before a1?

Thanks in advance!


texts: On the queue automaton and acceptance of this language

texts:
We have this language:
$$ L = \{^r|∈Σ^∗\} $$
We want to show that it can be accepted by QA.

consider a letter like #, before anything we push it to the queue.
using this additional letter, we push  every letter we get such that it would be the first letter of the string inside the queue (i.e. letter after #)
then (using Lambda Transition), we remove # from the queue, and we pop the letters come from input one by one out of queue. E.g. we get abccba from the input, we want to get string:
abc#E
in the queue, then remove # to reach abcE. then from this point when we get c from the input, we remove c from the queue's head.

Is this approach correct? Could you show me the queue automaton of it?
Thanks in advance.


texts:
On the haskell wiki there is the following example of conditional usage of the IO monad (see here).

when :: Bool -> IO () -> IO ()
when condition action world =
    if condition
      then action world
      else ((), world)

Note that in this example, the definition of IO a is taken to be RealWorld -> (a, RealWorld) to make everything more understandable.

This snippet conditionally executes an action in the IO monad. Now, assuming that condition is False, the action action should never be executed. Using lazy semantics this would indeed be the case. However, it is noted here that Haskell is technically speaking non-strict. This means that the compiler is allowed to, for example, preemptively run action world on a different thread, and later throw away that computation when it discovers it doesn't need it. However, by that point the side-effects will already have happened.

Now, one might implement the IO monad in such a way that side-effects are only propagated when the whole program has finished, and we know exactly which side-effects should be executed. This is not the case, however, because it is possible to write infinite programs in Haskell, that clearly have intermediate side-effects.

Does this mean that the IO monad is technically wrong, or is there something else preventing this from happening?


texts: Have I proved $\sum_{i=1}^{\lg n} 2^{i-1} = \Theta(n\lg n)$?

texts:
I have an exercise problem and don't know why its answer is like this.
$$ \sum_{i=1}^{\lg n} 2^{i-1} \in \Theta(2^{\lg n}) = \Theta(n).  $$

Regarding this equation, I think it would be,
$$ \sum_{i=1}^{\lg n} 2^{i-1} \in \Theta(\lg n \cdot 2^{\lg n}) = \Theta(\lg n \cdot n),  $$
with the proof,
$$ \sum_{i=1}^{g(n)}f(i) \le \sum_{i=1}^{g(n)}f(g(n)) = g(n)\cdot f(g(n)).  $$

My thought with this question,  $ f(n) =  2^{i-1} $ and $ g(n)= \lg n $. Then result would be $ \lg n \cdot 2^{\lg n - 1} $.

Can anyone point out where I made a mistake? (I am not asking grading mine, but tell me where I mis-think)


texts:
Is there a way to get O(1) without extra space in the union find algorithm?

Imagine I have 3 sets

set1 = {1, 3, 5, 7}
set2 = {4,20,25}
set3 = {9, 13}

Now imagine I have a new edge between 3 and 20. So I would need to merge set1 and set2, but before I do that I need find which set 3 belongs to and which set 20 belongs to. So how can I get an O(1) find operation to find the set the element belongs to without extra space?

With extra space I can easily store each node and its corresponding set in a hashmap.


texts: Was the "cuckoo search" independently discovered before 2009? If so, what was the name given to it?

texts:
Background: I would like to experiment with evolutionary algorithms to generate the "optimal" poem, according to a fitness function to be determined later. However, I cannot think of a good way of implementing 'crossing over' for the 'surviving' poems in each generation. Therefore, I gained some interest in the Cuckoo Search algorithm, due to it not requiring any "crossing over" and being very simple to implement. "Cuckoo Search" is a fairly new algorithm that was invented in 2009, and is just one of many algorithms inspired by naturalistic metaphors.

However, the computer science paper "Metaheuristics: The Metaphor Exposed" (by Kenneth Sörensen) and the Metaheuristics page on Scholarpedia (by Fred Glover and Kenneth Sörensen) seem to cast doubt on whether Cuckoo Search is actually new or innovative. From the Scholarpedia page:

  A large (and increasing) number of publications focuses on the development of (supposedly) new metaheuristic frameworks based on metaphors. ... Sörensen (2013) states that research in this direction is fundamentally flawed. Most importantly, the author contends that the novelty of the underlying metaphor does not automatically render the resulting framework "novel". On the contrary, there is increasing evidence that very few of the metaphor-based methods are new in any interesting sense. Weyland (2013) demonstrates convincingly, that Harmony Search (Geem, 2001) is nothing more than a special case of Evolution Strategies (Beyer, 2002) in which each of the concepts of Evolution Strategies has been relabeled from an evolution-inspired term to a term inspired by musicians playing together. ... Recently several journals, including the flagship Journal of Heuristics, have revised their editorial policies to prevent methods whose only novelty is the metaphor they are based upon from being published.

Problem - If Harmony Search could be seen as a special case of Evolution Strategies, then it is possible that that many other algorithms (including Cuckoo Search itself) may also have been previously discovered  in the past. But as the Scholarpedia page admits, "very few of the metaphor-based methods are new"...and "very few" means "more than 0". So I'm stuck knowing whether Cuckoo Search is indeed brand new or if it had existed before.

Here's my attempt at writing pseudocode for Cuckoo Search, removing all metaphors from the discussion to make it easier to compare it with other approaches. Hopefully I wrote the pseudocode correctly.

User set the following parameters: the population of candidate solutions  to generate (n), a percentage (p_a), and the number of iterations.
The initial population of candidate solutions (n) are generated.
Several candidate solutions are randomly selected for evaluation (this selection would be done using Lévy flight).
For each candidate solution selected for evaluation:

Generate a new candidate solution (called NewSolution)
Compare the fitness of NewSolution with the current candidate solution
If the NewSolution's fitness is greater than the fitness of the current candidate solution, replace the current candidate solution with NewSolution
Else, throw away NewSolution

All candidate solutions are ranked, according to their fitness.
The worst (p_a)% of candidate solutions are discarded. The best candidate solution is saved in the variable "current_best".
New candidate solutions are generated to replace the candidate solutions that were discarded in step 6.
Repeat steps 3 to 7 until the number of iterations is reached.
Return "current_best".

Clarification, as requested by Raphael - I would consider the Cuckoo Search to be "novel" if its pseudocode has not appeared in the computer science literature before its publication in 2009.


texts: Calibration and overlay of RGBD with a thermal camera

texts:
I have a thermal camera that I would  like to overlay automatically to the output of a RGBD camera (e.g., Kinect).

I can retrieve the intrinsic parameters of the thermal camera by using a special board I built, that allows the thermal camera to give as output a series of points similar to the ones obtained with a visible sensor and a typical calibration chessboard.

Once the intrinsic parameters of the thermal camera are obtained, what would the next steps be to align all the cameras?  It's important to take into account that the two cameras deeply differ from each other, because they operate in different wavelengths.


texts: Is the set of non-deterministic Turing machines countable?

texts: We know that deterministic TMs are countable (enumeration). Does the same hold for NTMs? Are TMs and NTMS equinumerous?


texts: trace vs. computation vs. run vs. execution vs. walk

texts:
Many folks use the terms "trace", "execution", "computation", "run", "walk" ... interchangeably when they speak about state machines with labeled transitions.  Does any work distinguish between these concepts?  E.g., which work says that XXX is a sequence of states, YYY is a sequence of labels and ZZZ is a sequence of states and labels between them, for pairwise different XXX, YYY, ZZZ in {trace, execution, computation, run, walk, ...}?

Here, a state machine with labeled transitions is simply a rooted directed graph (where arbitrarily many roots are allowed, which are interpreted as initial states) with edges labeled by letters from a fixed alphabet.


texts:
I'm new to asymptotic notations and right now I'm trying to prove that $n^4 = \mathcal{O}(2^n)$.
In my current solution (written below) I used L'Hôpital's rule repeatedly, proving that the limit of $n^4/2^n$ goes to zero. Is this correct?
Additionally I'm wondering whehter there is a simpler solution to this problem.
I tried induction but didn't get far. If you see an easier solution I would gladly appreciate any hints.

Thanks for any answers.

$ \lim_{n\to\infty} \frac{n^4}{2^n} = \lim_{n\to\infty} \frac{4*n^3}{2^n * ln(2)} = ..... = 0$


texts: Minimum fare price on public transportation network

texts:
In a public transportation network each stop has an assigned zone. The price of a trip depends on the number of adjacent zones that the user touches during a given trip. If the user touches two adjacent zones it must pay a Z2 title, and it can travel with that title during 1 hour. The time to travel (and price) increases as the number x in Zx also increases.

Imagine the following trip: The user starts at stop A (zone B6) at 16:00h and it arrives at location B (zone B1) at 16:30h. Because the user only touched two adjancent zones (B6 and B1) and the trip took less than 1 hour to complete, the user only pays a Z2 title (the minimum that is possible).

Now imagine a more complex trip: The user starts at stop A (zone B6) at 16:00h, travels to location B (zone B1) and it arrives at 17:00h, and finally it travels to location C (zone B1) and it arrives at 17:30h. On this case the user could pay a Z2 title to travel between 16:00h(Location A) and 17:00h(Location B) and another Z2 title to travel between 17:00h(Location B) and 17:30h(Location C) (2xZ2=2x1€=2€) or it could buy a Z3 title which allows him/her to travel 2 hours between three adjacent zones and it costs 1.50€. In this case the Z3 title would be a better choice.

This looks like a combinatorial optimization problem. I need to combine all trips during one day to find the minimum price. I'm here to ask for a starting point. Which algorithm should I look for to begin solving this problem? Thanks in advance.


texts: minimum subgraph whose cost is greater than a predefined threshold

texts:
is there an approximate algorithm that takes as input: an weighted  undirected graph $G = (V,E,W)$ and an integer $k > 0$ and outputting: a subgraph $g'$ with $w(g') \geq k $, and $|g'|$ is minimum. For example

in this graph, with $k= 65$, the solution is $g'=\{2,4,5 \}$


texts: Showing semidecidability without using diagonalization

texts:
All the methods I know which shows a given language $L$ is $RE$ but note $REC$ deep down boils down to the cantor's diagonalization arguement in one way or the other, and most commonly it boils down to reducing it to membership/halting problem.
Is there any other fundametnally different way of showing some language is $RE$ but not $REC$, or otherwise is there any heuristic arguement as in we must employ diagaonlization arguement in some form (see also: https://ncatlab.org/nlab/show/Lawvere%27s+fixed+point+theorem)?


texts:
Currently I am taking a computational geometry course and I have learnt that:

Orientation is formally defined as the sign of the determinant of the
points given in homoge- neous coordinates. For example, in the plane,
we have Orient(p,q,r) = determinant of the matrix:

1 ax ay

1 bx by

1 cx cy

What is the mathematical explanation for this formula?

I have expand the determinant and come up with this:

det(P) = (bx - ax)(cy - ay) - (cx - ax)(by - ay)

I also know an additional information which may lead to something useful, if the crossproduct (b-a)x(c-a) results in the +z direction then the rotation is positive. However, I am not able to derive anything from there. What should be my next step?

Thanks


texts: Enumerating the set of polynomial time Turing machines

texts:
I was checking this question and wondered how to apply it to the following language to prove it is in $RE$:
$$ L = \{ \langle M \rangle : \exists P \text{ such that } M \text{ halts on every input } w \text{ within } P(|w|) \text{ steps}  \},$$

where $P(x)$ is a polynomial with coefficients $a_1,\ldots,a_n \in \mathbb{N}$.

Those are the two approaches I am thinking of so far, in order to build a Turing Machine $M_L$ which accepts $L$ above:

Let $d$ be the degree of the polynomial $P$. For each $d=1,2,3,\ldots$, iterate over all possible $d$ coefficients, and check whether the current $P$ satisfies $L$'s condition above. I think it might work because if there is no such $P$, then the Turing machine $M$ won't stop and this is OK.
Here I am taking $P$ to be a constant (i.e. $P(x)=k \in \mathbb{N}$), and then iterate over all $k$ and apply the Turing machine from the question I linked at the beginning, where the language at the question above is in $R$ then there is a Turing machine $M_k$ which decides it, thus, while we get Rejection from $M_k$ for the $k$ values we're iterating on, $M_L$ does not stop.

I am not sure even where I made a mistake above, since the concept of iterating over all $k \in \mathbb{N}$ does not seems robust.

Does the approach of building a Turing machine work?
Since I could not get to a reduction which proves that $L \in RE$.


texts: Substitution for Landau's O notation formula

texts:
I found the following description when I was reading a paper on computational complexity theory.

  This can be done ... in time 2n･poly(logs,n)+2O(logs)c. For s≤2no(1), the runtime is 2n･poly(n).

I know this means substituting s≤2no(1) for 2n･poly(logs,n)+2O(logs)c results in 2n･poly(n), but I don't know how this is done. So please tell me the calculation process.


texts: Order a list of edges to make the the complexity of searching for an edge O(lg E)

texts:
I was reading this article on how to represent graphs, and probably the simplest way to think about it is to have a list of edges, with an edget being usually a list of the vertices that are related (connected).

Now, at a certain point, there's a question:

  How can you organize an edge list to make searching for a particular edge take
  O(lg E) time?

I was thinking to the trivial solution of sorting, but it is not so easy to sort a list of edges. For example, let the following be our initial list of edges:

[[3, 2], [1, 2], [1, 3]]

Now, if we try to sort it by using the first vertex, we obtain:

[[1, 3], [1, 2], [3, 2]]

I am not visualizing well if this search would be O(lg E), where E is the number of edges.

Could you please explain how could we organize the edges in order to have a edge searching algorithm with a time complexity of O(lg E)? And why it should be O(lg E)?


texts: Computing theory: can a single node be a subgraph?

texts:
Can a single node be considered a subgraph?

For example, if I had this graph, G:

X-----Y

and I deleted Y, leaving me with the graph

X

is this a subgraph (induced) of G?

What about the following argument?

Assume a single node can be considered a graph. Any graph is an induced subgraph of itself. Therefore, a single node graph has a single-node induced subgraph.

Though this is only valid if a single node can be considered a graph.

In computing theory, what is the generally accepted norm?


texts: Is it possible to do multitasking without context switch with just one cpu?

texts: All the article I can find seems to talk about multitasking and context switch as its a two different thing. It seems that multitasking and context switch are the same thing.


texts:
I want to construct a busy beaver TM which has the alphabet $\Sigma = \{1,2, X\}$ and $X$ is the blank symbol. I want to do this using 3, 4 and 5 states (means one just for halting, so 3 states = 2 'normal', 1 for halt). I am looking for kind of a system (theoretical pattern)
to do this...is there anything like that?

I managed to construct busy beavers but I did not manage to come up with something like a system.


texts: What is the exact meaning of a Predicate, decidability and computability?

texts:
In the Computability, Complexity and Languages book written by Davis in page 5 he defines a predicate as:

  By a predicate or a Boolean-valued function on a set $S$ we mean a total function $P$ on $S$ such that for each $a \in S$, either $P(a) = True$ or $P(a)=False$.

So every predicate is a total function. in Page 30 he says:

  A given partial function $g$ (of one or more variables) is said to be partially computable if it is computed by some program
  A function is said to be computable if it is both partially computable and total.

in page 68 he says:

  Theorem 2.1. $HALT(x, y)$ is not a computable predicate.

Since every predicate is total, so the only reason which causes this theorem to be true is that there must be no program that computes $HALT(x,y)$, it means $HALT(x,y)$ is not a partially computable, if it was then it would be computable because it is total!

Not that in page 76 the writer says:

  Note that a partially computable predicate is necessarily computable

In this link I found two statements that seems to be a contradiction.

  In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable or Turing-acceptable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.
  The Halting problem is recursively enumerable but not recursive.

I know that decidability terminology is used for sets but computability terminology  is used for languages. if we can say that recursively enumerable sets are partially computable (= partially deciable) then Since Halting problem is r.e. so it is partially computable. If it is partially computable and since it is total so Halting problem must be computable !!!


texts: There is any notation for a language that is empty infinite?

texts: Assume that $L$ is a language, is there any established notation that means that $L$ is infinite or empty?


texts: Analysis of a randomized algorithm for independent set construction

texts:
Suppose that $G = (V,E)$ is a 3-regular graph on $n$ vertices and $m$ edges. Below I propose a randomized algorithm for obtaining an independent set for $G$.

Step $1$: Delete each vertex (independently) with $\frac{2}{3}$ probability.
Step $2$: For each remaining edge, delete one of its endvertices.

I want to upper bound the probability that this $2$-step algorithm yields an independent set of size smaller than $\frac{n(1-\varepsilon)}{6}$, where $0 < \varepsilon  \leq 1$. My partial attempt is below.
Let $X_1, X_2, \dots, X_n$ be independent Poisson trials satisfying $\textbf{Pr}[X_i = 1] = \frac{1}{3}$. Hence, $X = \sum_{i=1}^{n} X_i$ gives us the number of vertices in $G$ that survive Step $1$, and $\textbf{E}[X] = \frac{n}{3}$.
Let $Y_1, Y_2, \dots, Y_m$ likewise be independent Poisson trials satisfying $\textbf{Pr}[Y_i = 1] = \frac{1}{9}$. Hence, $Y = \sum_{i=1}^{m} Y_i$ gives us the number of edges in $G$ that survive Step $1$, and $\textbf{E}[Y] = \frac{n}{6}$.
Thus, $X-Y$ gives us the minimum number of vertices remaining after the algorithm terminates.
Now, the following Chernoff bound seems especially pertinent to this problem, where $Z$ is a sum of independent Poisson trials, $\mu$ is its expectation, and $0 < \delta \leq 1$:

$\textbf{Pr}[Z < (1 - \delta)\mu] < \exp(\frac{-\mu \delta^2}{2})$

Of course, $X-Y$ is a lower bound on the size of the output independent set, but I'm not sure how I can apply the expression to the Chernoff bound. Can $X-Y$ can be conceived as a sum of Poisson indicator variables, which would be required if I wanted to put $X-Y$ in place of $Z$ in the above bound? If so, then it seems to me that I can use this Chernoff bound to derive an upper bound on the probability that the minimum size of the output independent set is smaller than $\frac{n(1-\varepsilon)}{6}$. How can I get from this to my objective: an upper bound on the probability that the actual size of the output independent set is smaller than $\frac{n(1-\varepsilon)}{6}$?


texts: How are faces of a DCEL updated when triangulating a polygon?

texts:
In chapter 3 book how to triangulate a polygon is explained, however it doesn't seems to me that how to handle the faces are explained. My guess would to add two new face and erase the old one every time a diagonal is inserted (both while decomposing the polygon in monotone pieces, and during the actual triangulation). Is my guess correct?

Is there a smarter way to do that?


texts: Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?

texts:
To prove that some decision problem $A$ is NP-complete, my understanding is that it suffices to show that the problem is in NP (i.e. that one can verify or reject all statements in polynomial time), and to demonstrate that some known NP-complete problem $B$ can be reduced to $A$ (such that we can write $B \leq_p A$), by some kind of appropriate reduction in polynomial time.  We can then say that we can solve $B$ in polynomial time with an oracle for $A$.

One famous example of this would be the reduction of 3SAT to 3-coloring.

So sure, I understand that with an oracle for 3-coloring, one could solve arbitrary instances of 3SAT in polynomial time.  But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT?  The 3SAT $\leq_p$ 3-coloring reduction, of course, requires the use of special and restricted graphs where a 3-coloring exists iff a satisfying assignment for the 3SAT problem exists.

Doesn't this conflict with statements (at least I thought I heard in CS classes) saying that an oracle for 3SAT would prove P = NP?  Might it not be the case that such an algorithm would be worthless for solving families of 3-coloring problems?

Doesn't this imply some kind of hierarchy of NP-complete problems?

(Said a bit differently: If an oracle that allows one to solve a single NP-complete problem in polynomial time must necessarily be an oracle that allows one to solve all NP-complete problems in polynomial time, shouldn't we need to show $B \leq_p A$ AND $A \leq_p B$, where $B$ is some known NP-complete problem, to prove that some problem $A$ is NP-complete?)


texts: Simulating a turing machine with DPDA with two stacks

texts:
In general, the idea for simulation a turingmachine using a PDA with two stacks, is to use one stack representing the already read input and the second stack representing the unread part of the input.
To do so we need to read the complete input into one of the stacks.
If we use a nondeterministic PDA we are able to read the input and put it on stack 1 and guess the end of the input in order to change state, copying stack 1 to stack 2 in reverse order and to start the simulation.

My question is, how can we archieve a simulation using a deterministic PDA with two stacks? Especially, how do we recognize the end of the input in order to reverse it and to start the simulation. The only way I came up so far, is to demand a special character $ that marks the end of the input.


texts: How to iterate over vectors in order of probability

texts:
Consider a random $n$ dimensional vector $v$ where $v_i \in \{0,1\}$.  For each $i$ we know $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent.  Using these probabilities, is there an efficient way to iterate over all possible binary $n$ dimensional vectors in order from most likely to least likely (with arbitrary choices for ties)?

Take for example $p = \{0.8, 0.3, 0.6\}$. The most likely vector is $(1,0,1)$ and the least likely is $\{0,1,0\}$.

For small $n$ we could label each vector with its probability and sort although this isn't very efficient. However, consider $n=100$ for example. This is no longer an option.


texts: How to handle horizontal lines in the Polyfill Algorithm?

texts:
When I look at polyfill algorithm tutorials/articles or examples, nothing mentioned about how to handle horizontal lines. Does anyone have any idea how horizontal lines should be handled?

For instance, consider the following image:

For intersection I wrote if the line on the scan line count it as 1 point, even I count as 2 point or no point, wont help. Any idea how should I handle the horizontal line?

Edit: here a complex example of horizontal line intersection, let's take a look at line 3:

Alright, if we take a look at next point and previous point of the intersection of both end of horizontal line, if those point are in same side, means I can count them in or out, doesn't effect the whole calculation.
But if they are are opposite side, I have to count them in and count one side extra.

What do I mean?
Take InterS1 and InterS2 as an example, so when I get this I have count that horizontal line as 3 points:

point1 = InterS1
point2 = InterS2
point3 = InterS2

Why I need to do that?

When next point and previous point are in different direction, is letting us know that our intersection line crossing outside and passing through inside of shape.
Also because line can be created when there is start point and end point, so I need to have even number to draw lines.

So now I have no idea base on what I need to add the extra point to one side.
Do I make sense?


texts: Validity of list of articulation points in a graph after a node is deleted

texts: Say I have a bidirectional graph G and I have the list of articulation points and bridges of this graph. Say, the list of articulation points is ap[] and the list of bridges are bridges[]. Now, if I remove a node which does not belong to the list of ap[], meaning, this node is not an articulation point and deleting this node will not divide the nodes of this graph into different connected components. Now, do I have to update the list of the articulation points ap[]? I mean after deleting the node, is it possible that some more node(s) in the graph will become articulation points? The same question is for the list of bridges. If I remove an edge which is not a bridge in the graph, after deleting it, is it possible that some more existing edge(s) will become bridge?


texts: Finding representatives of equivalence classes

texts:
I have a table of pairs of objects, which defines an equivalence relation. How can I extract a single object from each of the equivalence classes using relational algebra?

It can easily be done with iteration. For example, associate a unique classId with every object, then for every pair (a, b) set classId(a) = classId(b) = min(classId(a), classId(b)), until all pairs share the same classId on both ends.
I wouldn't know how to do it more efficiently.


texts: Complexity of a cutting operation on a list of binary trees

texts:
Consider a list of full binary trees of heights $(h_0, h_1, \ldots, h_{n-1})$ where a tree with a single leaf is deemed to have height 0.
The list has the property that the height of the tree when going through the list is, at first strictly increasing, and then strictly decreasing, i.e $$\exists k, 0 \leq k < n, ~\forall i, (1 \leq i \leq k \implies h_{i-1} < h_{i}) \wedge (k \leq i < n \implies h_{i} > h_{i+1})$$
Examples of list of heights that have this property
()
(4)
(0, 1, 5)
(0, 1, 3, 2, 1)
(3, 0)

Examples of lists that do not  have this property
(3, 3)
(3, 4, 2, 3)

The total number of leaves in this list $\sum_{i=0}^n 2^{h_i}$ so, in the worse case, the length of the list is bounded by $2 \log_2 l$ if $l$ is the number of leaves.
We define the "take" operation on a list in pseudocode as follow
take quantity forest :
   result = []
   while quantity > 0 and forest not empty:
      if 2^(forest.head.height) < quantity:
         forest = forest.tail
         insert = front
         while result not empty and result.front.height = insert.height
              insert = merge(insert, result.head)
              result = result.tail
         result = cons(insert, result)
         quantity = quantity - 2^(front.height)
      else:
         forest = cons(forest.head.left, cons(forest.head.right, forest.tail))
   return result

It's not too hard to convince oneself that this take operation preserves the property of being increasing then decreasing of the list (although the invariant can be temporarily violated in the loop).
It's a bit less obvious than the list returned by the procedure also has this property, but it still seems true.
Much less obvious is the worst-case complexity of the operation as a function of $l$, the number of leaves. The inner while looks like it could introduce some quadratic $\mathcal{O}(\log^2 l)$ complexity, but it is not obvious that this is actually the case.
So what is the worse case complexity of this procedure?


texts: Show that if vertex cover is reducible to a mod-inverse than P=NP

texts:
Let MOD-INVERSE consist of all pairs $\langle N,c \rangle$ such that $c$ has an inverse modulo $N$.
Let VERTEX-COVER consist of all pairs $\langle G,k \rangle$ such that $G$ is an undirected graph with a vertex cover of size $k$.
Prove that if VERTEX-COVER reduces to MOD-INVERSE then P=NP**.

My Thoughts :
$\langle N,c \rangle$ is a member of MOD-INVERSE iff $\gcd(N,c) = 1$.
So we have to show that if VERTEX-COVER is reducible to MOD-INVERSE then P=NP.
Now P is the class of all problems that can be solved in polynomial time and NP are those
that have polynomial time verifiers.
I found out that VERTEX-COVER is NP-Complete. That means that it's NP-HARD.
Does NP-HARD mean that given any problem in NP, VERTEX-COVER can be reduced to that problem?
I am somewhat confused here: do I have to use this heavy fact, that VERTEX-COVER is NP-complete, in order to solve the question?
If VERTEX-COVER  is reducible to MOD-INVERSE then VERTEX-COVER would be in P and since it is
NP-HARD, all problems in NP would be in P.
Not sure if that's a correct argument.


texts: Simpler proof of Rabin's Compression Theorem?

texts:
I was doing a presentation on Rabin's Compression Theorem, when someone in the audience brought up a point I have no answer to.

Rabin's Compression Theorem states that every reasonable complexity class has a problem that can be solved optimally in it.  The proof is a little involved, but not horribly difficult.

The audience member proposed a much simpler proof.  For the given complexity class, calculate the target volume of computation from the input length.  Then write that many hashes to the output.

Does this really prove the same result?

Also, I have had a lot of trouble finding Rabin's original paper.  Does anyone know how to get it?

A formal version of the argument would be:
Given a constructible function $f$, find a program that is optimal for $O(f(x))$ time, where $x$ is the length of the input.

def program(input):
    x = len(input)          # takes O(x) to read input of length x
    target = f(x)           # f is constructable, computing f(x) takes at most O(f(x))
    for _ in range(target): # takes exactly O(f(x)) to loop f(x) times
        print('1')          # assume we can append to the output in O(1)

The runtime of the algorithm is clearly $O(f(x))$.

The algorithm is optimal:
Any program that prints $f(x)$ "1"s requires at least $f(x)$ steps.

As far as I can tell, this proof seems to work. It almost certainly proves something similar. However, I can't understand why the original proof would be so complicated, if this simpler proof works.  This makes me worry that maybe I misunderstood something: e.g., about why the original statement is important/interesting, or about whether this simpler proof is correct and proves what it needs to prove.  Can anyone help clear this up for me?


texts: Approximation ratio when optimal solution is $0$

texts:
This might be a basic technicality but I'd like to make sure how to handle it.
The question is: how do we measure an algorithm's approximation (multiplicative) factor on instances with optimal value $0$.

Suppose I have a minimization problem $Pb$, and it is NP-Hard to decide if a given instance $I$ has optimal value $OPT(I) = 0$.

As a concrete example, say that $Pb$ is the problem of removing a minimum number of edges from a graph so that it is $3$-colorable.  Deciding if $0$ edges suffice is NP-hard.

Suppose now that I have an approximation algorithm $A$ for $Pb$ that runs in polynomial time.  How could $A$ achieve any kind of approximation factor?
Suppose $A$ always finds a solution of value $APP(I)$ within factor $\alpha$.  Then on instances of value $0$ it must return a value $APP(I) \leq \alpha \cdot OPT(I) = 0$.  Thus $APP(I)$ decides whether $OPT(I) = 0$.  Unless $P = NP$, this is impossible and so $A$ cannot approximate $Pb$ within any factor in polynomial time, let it be constant, $poly(n)$, superexponential in $n$, whatever...

Is that it?  Or is there some way around this technicality?


texts:
I have this question to answer: "Please shortly explain how an interface virtualizes a peripheral device to the CPU."

I don't really understand what the question is asking for. I know the theory behind virtual memory. I understand that a harddisk can be seen as a peripheral device.

Could the theory behind virtual memory be what the question is asking for or did I totally misunderstand it?


texts: Distance from high dimensional convex hull to target point T

texts:
I have a set S of high dimensional points in Euclidean space, with convex hull H (not known); and some target point T in that space not in or on H.

Rather than worry about calculating both H and the distance to it explicitly, is there an efficient way to calculate just the distance from T to the closest point on H?  I was thinking something involving binary space partitioning with spitting planes, but can't quite figure out how to formulate the approach (esp. which planes to choose).


texts: Language of strings of lengths that are prime is regular? Is C^* regular?

texts:
With $\Sigma = \{a\}$ I want to see if a language $C = \{a^p \ | \ p \ \text{is prime}\}$ is regular and whether or not $C^*$ is regular.

How would I go about showing whether $C$ or $C^*$ are regular? I know I can construct a DFA/NFA to accept them but I am very confused about the fact that there are an infinite number of primes.


texts: A Recursive Formula For Generalized Josephus problem

texts:
The Josephus Problem asks where to start taking out every kth person in the circle consisted of n people, such that you are the last "survivor".

The following recursive formula is given:
$$\begin{align}
f(1,k)&=1, \\
f(n,k)&=((f(n-1,k)+k-1) \bmod n )+1.
\end{align}$$

But this is not enough explanation, so I don't get where does it come from.

Can anyone help?


texts: Difficulty understanding pre-emptive vs non-preemptive CPU scheduling

texts:
I'm having difficulty understanding what my book is trying to say in regards to preemptive and non-preemptive CPU scheduling.

It says the following:

  CPU Scheduling decisions may take place under the following four
  circumstances:

  When a process switches from the running state to the waiting state (for example, I/O request..)
  When a process switches from the running state to the ready state (for example, when an interrupt occurs)
  When a process switches from the waiting state to the ready state (for example, completion of I/O)
  When a process terminates

  In circumstances 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be selected for
  execution. There is a choice, however, in circumstances 2 and 3.

  When scheduling takes place only under circumstances 1 and 4, we say
  that the scheduling scheme is non-preemtive; otherwise, the scheduling
  scheme is preemptive. Under nonpreemptive scheduling, once the CPU has
  been allocated to a process, the process keeps the CPU until it
  releases the CPU either by terminating or by switching to the waiting
  state.

It is mainly the bolded part that confuses me. What does it mean by there "being a choice"? The way it's worded almost sounds like it's saying that in circumstances 2 and 3, a new process DOESN'T have to be selected for execution. I'm not quite sure I follow at all what this section of my book is trying to tell me, especially the bolded part.


texts:
Is it true to say that Huffman codes always satisfy Kraft's inequality with strict equality?

At first, I thought the statement is wrong since for Huffman coding there is no assumptions on the probabilities. However, when I tried evaluation the Kraft inequality for several Huffman codes, I realized that it's got nothing to do with the probabilities. It's the algorithm.

I looked for a nice mathematical proof for this, but couldn't find any. Would appreciate your help.


texts: reduce reduce and shift reduce error in LALR grammar

texts:
I have to write a grammar for Pascal, and there is just one thing that is causing problems.

Lets say we have operators (sorted by priority from low to high):

Postfix ^.
Prefix ^.
[ ], and ., (same priority and left associative).
The only terminal is id, which is any lowercase letter.

Now let's say that an expression is:

Any id.
Any expression with the Postfix ^ operator.
Any expression with the Prefix ^ operator.
Any expression with . followed by id.
Any expression with [ and another expression and ].

Now I would like to know how can I make a LALR grammar without shift-reduce and reduce-reduce conflicts, OR if that can't be done how can I prove that it can't be done.

Some examples:

good:
a.b.c.d
a.b^.c
^a.b^
a.b^^[c]^^.d.e
^^a.b^.d.e^[]

bad:
a.^b.c

Without the prefix ^, this problem is easy to solve, but the prefix sign keeps getting me. Can anyone help? My solutions so far:

// this works without the prefix but it does not produce a.b^.c which is wrong.
A ::= B | A ^ ;
B ::= C | ^ B ;
C ::= id | C [ A ] | C . id;

So I thought that the prefix can only occur before the first dot, and between dots, there can only be a postfix ^ and brackets. So I came up with this:

A ::= B | A ^ ;
B ::= C | ^ B ;
C ::= id | C [ A ] |id D;
D ::= id E;
F ::= E | F ^;
E ::= id | F . id;

But this causes 3 conflicts.


texts: Longest subsequence such that A[i].x < A[i+1].y

texts:
I have an issue for which I am looking for an algorithm (if it exists)

What I have:
An array of items which have certain properties, e.g. item $A$ has properties $x$ and $y$.

Example: $[ A(x,y), B(x,y), C(x,y), D(x,y), E(x,y) ]$

What I want:
A result list consisting of elements of the original list, such as $[ A(x,y), C(x,y), E(x,y) ]$, for which the following properties are true:

No reordering of elements, they are in the same order as the original list
The result has the maximum number of elements, i.e. the longest 'path' possible
For each pair of consecutive items $(A(x,y), B(x,y))$ in the result, $A.x \lt B.y$. In other words, an item's $x$ must be less than the next item's $y$.

Complexity: The list in the case I have is about 35 items long, so an algorithm which is $O(n!)$ might not work.

Does such an algorithm exist?


texts: Converting context-free grammar to Chomsky/Greibach Normal Form

texts:
Is it necessary to remove all lambda productions, unit productions and useless productions from a context free grammar(CFG) before converting to Chomsky Normal Form(CNF) or Greibach normal form (GNF). If so why is it required?

Also my Professor said that we should convert a CFG into CNF before converting it to GNF. Is that required or can we straight away convert a CFG into a GNF?


texts: Problems that are NP but polynomial on graphs of bounded treewidth

texts:
I heard here that the Hamiltonian cycle problem is polynomial on graphs of bounded treewidth.

I am interested in examples/references to different problems which is essentially hard but having polynomial complexity on graphs of bounded treewidth.


texts: An algorithm for identifying a fruit with words

texts:
Let's say a person picked up a fruit and wanted to identify it.

The person knows certain features about the fruit, such as its color and where it was plucked from, but not its name. They also have knowledge that's relevant for identifying the fruit, but they're not aware that it's relevant (such as the color of the soil below them).

What algorithm could you use to narrow the space of possible answers, such that you could identify the fruit with questions and facts alone?

For an example of how an algorithm/software might work:

Question One

"Is this fruit red?"

Yes / No

Question Two

"Did you find this fruit in May?"

Yes / No

Question Three

"Does this fruit taste sour?"

Yes / No

Question Four

"Does the fruit feel hard?"

Yes / No

A bit like the game of 20 Questions, except in this case, the person does not know what the answer may be—only certain characteristics of the answer.

Is there any algorithm or approach that might work to solve this problem in this particular way?


texts: When are existential quantifiers in the intuitionistic propositional calculus eliminable and when not

texts:
I am so ignorant I don't even know where should I ask this - on FOM? On mathoverflow? On cstheory? So please consider as sort of a meta-question readdressing me in case you think this is a wrong site. (Also my tags are most probably wrong, sorry)
The simple case when I definitely know the answer and it is positive: given some propositional formula $\phi$, I know that there is an $x$ such that $\phi$ is IPC-equivalent to $x\lor\neg x$ if and only if $\neg\phi$ is equivalent to $\bot$.
Two simplest cases when I suspect the answer is negative but I don't know how to prove it: again given some $\phi$, when does there exist an $x$ such that $\phi$ is IPC-equivalent to $\neg x\lor\neg\neg x$; or when does there exist an $x$ such that $\neg x$ is equivalent to $\bot$ and $\phi$ is equivalent to $x\lor\neg x$. In these two cases I can formulate necessary first order conditions on $\mathscr V(\phi)$ in any valuation $\mathscr V$ under either Kripke or some more general semantics, but I suspect that I cannot eliminate existential quantifier staying in IPC.
How to approach such questions? What science is this? Is there some software which I can use for MUCH more complicated expressions?


texts: Showing that graph of spanning trees are connected

texts:
Suppose we have a graph $H$, where each vertex represents a spanning tree of another graph $G$.

We create an edge between 2 vertices in $H$ if $ST_1$ (spanning tree) contains exactly one edge not in $ST_2$ (and vice versa).

How do we show that $H$ is connected?


texts:
For $P(x)=N(\mu,\sigma^2)$ and $Q(x)=N(0,1)$ I am supposed to calculate $KL(P(x)||Q(x))$, here is what I did

\begin{align*}
    KL(P(x)||Q(x)) & = \int P(x) \cdot \log\left(\frac{P(x)}{Q(x)}\right) dx \\
    & = \int P(x) \cdot \log\left(\frac{\frac{1}{\sqrt{2\pi \sigma ^2}} \exp{-\frac{(x-\mu)^2}{2*\sigma ^2}}}{\frac{1}{\sqrt{2\pi}} \exp{-\frac{x^2}{2}}}\right) dx\\
    & = \int P(x) \cdot \log\left(\frac{1}{\sigma^2}\right)^{\frac{1}{2}} dx + \int P(x) \left(-\frac{(x-\mu)^2}{2\sigma^2} + \frac{x^2}{2} \right) dx \\
    & = \frac{1}{2} \log\left(\frac{1}{\sigma^2}\right) \int P(X) dx + \frac{1}{2\sigma^2} \left(-\int (x-\mu) ^2 P(x) dx \right) + \frac{1}{2} \left( \int x^2 P(x) dx \right)
\end{align*}

now I use that
$$\int x^2 P(x) dx = V(x)-E(x)^2 = \sigma^2 - \mu^2$$
$$\int P(X) dx = 1$$
$$-\int (x-\mu) ^2 P(x) dx = V(x) = -\sigma^2$$

so I get

$$KL(P(x)||Q(x)) = -\frac{1}{2}\log(\sigma^2) - \frac{1}{2} + \frac{\sigma^2}{2} - \frac{\mu^2}{2} = -\frac{1}{2}\left(log(\sigma^2)+1-\sigma^2 + \mu^2\right)$$

But I am supposed to get
$$KL(P(x)||Q(x)) = -\frac{1}{2}\left(log(\sigma^2)+1-\sigma^2 - \mu^2\right) $$

I cannot see where the mistake with the $+\mu^2$ comes from? Is it not true that $\int x^2 P(x) dx = E(x^2)$ ??


texts: Algorithm to count number of overlapping rectangles of the same colour?

texts:
Say you have a grid of pixels. And there are 20 overlapping red rectangles on a blue background.
I want to find an algorithm to count the minimum number of rectangles that are needed to form the image. And also the maxium extent of these rectangles.
Any good algorithms for doing this? It is easier said then done. Perhaps there is a nice functional or recursive way of doing this?


texts: More complicated resources than time and space complexity

texts:
The wikipedia page on computational resources states that there are many different resources that have been defined:

In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.
The simplest computational resources are computation time, the number of steps necessary to solve a problem, and memory space, the amount of storage needed while solving the problem, but many more complicated resources have been defined.[citation needed]

Unfortunately, this claim doesn't have a citation.
What are these more complicated resources that have been defined?

I can imagine something like parallel processes used?

the wikipedia talk page talks about communication bandwidth: e.g. network bandwidth, and memory busses. ( this seems fairly "processor-dependent"? Not sure if there is a theoretical analysis of this).


texts: Matrix Multiplication Algorithms for Non-Square Matrices

texts:
I'm interested in learning about some of the algorithms available for multiplying non-square matrices, yet despite exhaustive Googling efforts I have been unable to find any discussions of such algorithms except for a couple of extremely general pieces of pseudocode that I found on Wikipedia and MIT OCW.

If anyone could pass on some links to papers that discuss these algorithms in greater detail, I would greatly appreciate it! Thanks!


texts:
There are two nice tree constructions, that use a stack in a similar manner:

Construct a binary search tree from a pre-order traversal (e.g. see http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversal-set-2/)
Construct a Cartesian tree from an array of numbers (e.g. https://en.wikipedia.org/wiki/Cartesian_tree)

I feel like these could be more or less the same thing, if looked from a proper angle, but I can't find a unified way to look at them. Any suggestions?

UPDATE: this is actually pretty cute: both are related to so-called stack-sortable permutations (https://en.wikipedia.org/wiki/Stack-sortable_permutation): rotating a properly labeled cartesian tree gives its preorder traversal, which can be used to recover the tree using the first construction.


texts:
If we have the following in Haskell:

f x y = x + y
:type f
f :: Num a => a -> a -> a

then GHC would report Num a1 => (a2 -> a1) -> a2 -> a1 -> a1 as the type for (f .).
Would you please explain me the steps through which GHC comes to such conclusion?


texts: Finding the smallest string that contains a given set of substrings

texts:
The algorithm I am looking for has the following requirements: Input is a set of strings. You are looking for a string containing all input strings. The resulting string should be as short as possible. At least shorter than just concatenating all input strings if possible.

Examples:

Input: a ab bc
Output: abc

Input: abcd bcde ef
Output: abcdef

Is there a name for this problem with which it is better to search for solutions?


texts: Is $T(n) = Ω (n^2)$ the same as $n^2=O(T(n))$?

texts:
Question: In the problem below, does proving $T(n) = O(n^2)$ and $n^2 = O(T(n))$ lead to the same result as proving $T(n)=O(n^2)$ and $T(n)=Ω (n^2)$? Which would be the better approach to take? I feel like I am not getting the big picture. Right now I am just trying around until I find something that seems plausible.

Here is what I have tried so far:

Problem: Prove that $T(n) = \theta(n^2)$ where $T(n) = \frac{n(n+1)}{2}$

My Approach: I know that T(n) is $\theta(n^2)$ if $T(n) = O(n^2)$ and $n^2 = O(T(n))$ both apply, if I can prove both, the statement is therefore true.

In order to proof  $T(n) = O(n^2)$, I check if $\lim\limits_{n\to \infty}\frac{T(n)}{n^2}$ exists, which it does: $\lim\limits_{n\to\infty}\frac{n(n+1)}{\frac{2}{n^2}} =\lim\limits_{n\to\infty} \frac{\frac{1}{2}n^2+\frac{1}{2}n}{n^2}=\lim\limits_{n\to\infty}\frac{1}{2}+\frac{1}{2n}=\frac{1}{2}$
To prove that $n^2=\theta(T(n))$ I argue that  $n^2 \le 2 * \frac{n(n+1)}{2}=n^2+n$
and that therefore, for all $c =2>0$ and for all $n \ge n_0 = 1:n^2 \le c *T(n)$ applies $n^2 = O(T(n))$


texts: Give a grammar to show whether a language is regular or context-free

texts:
I have to generate a grammar for the language $L = \{ w \in \{ a, b\}^* \mid |w| \in 2\mathbb{N},  w \neq w^R\}$ and give the type of the language.

I've generated the grammar

$\qquad \begin{align}
  S &\to aSa \mid bSb \mid aAb \mid bAa \\
  A &\to abA \mid baA \mid aaA \mid bbA \mid \varepsilon
\end{align}$

This grammar is a context free grammar. I now can say that $L$ is a context free language. But how can I say for sure that this language isn't regular ?


texts: Tricks, Tips and Nontrivial Insights with Higher-Order Functions

texts:
Many years ago I briefly skimmed a physical book (or perhaps a preprint?) on programming in Racket that included lots of really unique uses of map and fold (reduce) in particular, although it had plenty of genuinely unique tricks with curried (curryed?) functions et al. -- all of these without (notable) loss of generality across language.

I distinctly recall amazingly tiny and elegant ways to traverse and manipulate trees, produce huffman encodings, generate a min/max heap and much more. If my memory serves, many of them relied on folding up a function (e.g, the value being accumulated and ultimately returned was an anonymous function), ultimately there was some very general and nontrivial rule concerning map and fold individually that was rooted in computer science.

In trying to scrape my brain for the list all I came up with was a very lame rehashed version of a recursive function to extract the leaves from a tree.

(define-fn get-leaves
     (mapc (lambda g
           (print g#value)
           get-leaves)
     graphs)

alternatively

function getLeaves(node) {
  if (node.children == null) console.log(node.value);
  else node.children.map(getLeaves)
}

If someone knows the name of this article or book, that would be the absolute greatest.

If not, I'd love a list of unique and powerful insights or snippets involving map/fold or otherwise related concepts.

I'll ask the reader to omit the generic uses of map and reduce (apply-to or summing of lists, building an associative array, etc) that most are already familiar with


texts: Run time of pseudo code in big theta notation

texts:
I am looking for the run time of the following pseudo code.

FunctionA(n)
a ← 2
b ← 2n²
while b>1
    a ← a +1
    c ← n
    while c ≥ n
        b ← b - a
        a ← a/2
        c ← 2n/c

So I think the inner while loop has a run time complexity which will be definde by the outer loop since c is allways 2 and because it allways executes as long as the outer loop runs.
The outer loop decreases b with every step by 1 and a. a is allways the half of the precursor. Therefor I have the feeling that the outer loop runs $\Theta(log_2(n))$ and hence the result is $\Theta(2*log_2(n))$.
Would somebody comfirm this?


texts: Intuition behind cellular automaton mixed bulking function?

texts:
I'm reading the paper of Nicolas Ollinger on intrisically universal 1d cellular automata: https://arxiv.org/abs/0906.3213.

On page 3 (201), he gave the definition for mixed bulking quasi order. I'm unable to grasp the intuition behind such a defintion, injective universality seems to already capture what I can imagine universality to be. Another issue is that the mixed bulking map $\phi$ has domain $2^{S_B}$, how is $\phi$ composed with the global function $G_B$ when $G_B$ has domain $S_B^{Z^d}$？


texts: Why is my regular grammar for palindromes wrong?

texts:
I've seen that people prove somehow that set of all palindromes isn't regular language by using a pumping lemma, which I am not familiar with.

I've created grammar which can generate all palindromes and that is why I wonder why it's wrong.

A -> e
A -> a | b | ... | z
A -> aAa | bAb | ... | zAz


texts:
Consider a 2,3,4 tree like so,

           53
         /    \
        /      \
       /        \
     46          60 | 70
    / \         /    \   \
   /   \       /      \   \
  /     \     /        \   \
 41     48  55|59    65|68  73|75|79

How to delete 41 from the tree from here ? I would like to know the intermediate steps involved.


texts: CRC: false positive under some circumstances

texts:
Consider two computers $A$ and $B$. $A$ uses $G$ and $B$ uses $G'$ for the CRC computation. It is given that $\deg G \ne \deg G'$. Computer $A$ wants to send a data $D$.

The claim says that:

  There couldn't be data $D$ such that $A$ sends it as a CRC-message corresponding to computer $B$ which will accept it as a valid message. Why is that?

We know that computer $A$ sends $D\cdot 2^r \text{ XOR } R$ ($r$ is the degree of $G$) and computer $B$ divides by $G'$. So in other words, why can't $G'$, accidentally, divide $D\cdot 2^r \text{ XOR }  R$?

Obviously it has something to do with the fact that $\deg G \neq \deg G'$ but I didn't figure it out.

Thanks!


texts:
Can anyone help me with this test question ? I am not really expert on this.

Assume $1000$BASE-LX network. Communication is using sliding window protocol with $15$ frames, each frame with $1000$ data bytes. The trace is $100$ km long and there is $3$ routers between sender and receiver. Calculate maximum possible data throughput.

So far, i calculated propagation time, which is $500$ us, ($\frac{d}{v}$; $v=2*10E8$, $d=10E4$).  Now i am wondering how to continue. I presume, that this network has $1$Gbit/s, so one packet will have transmission time $8$ us. There is nothing about ACK frame in the question, so can I ignore it ? Thanks for help, i am really lame beginner in the networking.


texts: Simulated annealing to find the correct permutation of 20 words

texts:
I have 20 words. One permutation of these 20 words is the "correct" one. Assume I have a metric to find the correctness of the permutation.

I'm trying to figure out how to use simulated annealing to find the correct permutation of these 20 words. To begin with, I'm not even sure if I understand simulated annealing entirely, so I'll describe an algorithm that I think resembles simulated annealing.

For an arbitrary number (preferably a big number) of times, generate a random permutation and measure how correct it is. If the answer is more correct than any previous attempt, save the score and the sentence. Once we are done iterating, we have found something that it is probably close to the global maximum (the "correct" permutation).

I'm not sure where to go from there. Essentially, I have two questions.

Does that sound like a good approach?
Is my algorithm simulated annealing?


texts: Returning two array indices in an array for a given value

texts:
Give an algorithm that takes as input an array A sorted in non-decreasing order, and a value x, and that returns two indices (F and L) into A, where A[F] is the first value equal to x and A[L] is the last value equal to x. Your algorithm should run as fast as possible in the worst case. State the worst case running
time of your algorithm.

A O(n) algorithm is very easy for this. A for loop running on the input array could easily find F,L. I think for sure there is a better algorithm. I am thinking of modifying binary search to search for the same value repetitively. I think O(logn) might not be possible, but something like $O(log ^2 n)$ might be. I am unable to come up with a precise algorithm that achieves something like this running time.


texts: Asymptotic notation and random variables

texts:
I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values).

Suppose that the two variables can have different distributions with values chosen from $[1, n]$. But $X$ is always upper bounded by $Y \cdot c\log{n}$ for some constant $c$. Can I write this as $X = O(Y\log{n})$ (if I care about the behavior for large $n$). I'm not sure what is the convention wrt to random variables and asymptotic notation.


texts: Finding Second large element from a set of 4 element

texts: Is there any special algorithm of lowest complexity for finding 2nd largest element from a set of 4 elements?


texts: Which object-oriented programming language is the closest to the untyped sigma-calculus?

texts: I'm wondering which of the dynamic object-oriented (or prototype-oriented) languages (like JavaScript, Ruby, Python, etc.) can be considered as the closest to Abadi and Cardelli's untyped sigma calculus?


texts: Reducing from a Turing machine that recognizes is regular to the halting problem

texts:
I'm trying to understand reduction, this is from my textbook and is not a homework problem or even any exercise, just trying to understand an example they present.

This is the reduction they give:

PROOF We let R be a TM that decides REGULARTM and construct TM S to
decide ATM . Then S works in the following manner.

S = “On input $M$, $w$ , where M is a TM and w is a string:

Construct the following TM $M_{2}$ .

$M_{2}$ = “On input x:

If x has the form $0^{n} 1^{n}$ , accept .
If x does not have this form, run M on input w and
accept if M accepts w.”

Run R on input $M_{2}$ .
If R accepts, accept ; if R rejects, reject .”

So, we start with a machine that decides whether a language of a TM is regular. And we want to use that to decide if a TM halts on a given input.

My question: What if $w$ does have the form $0^{n} 1^{n}$? Well, $M_{2}$ accepts that string just cause of the form. But we never actually run $M$ on $w$. So how can we say that it will accept or reject it? We have no idea what it does because we never ran it on $w$.


texts: Computing gaussian kernel for image blurring

texts:
When I compute a gaussian kernel for image blurring should I normalize the 1D vectors? Because when I apply the raw values sometimes the image gets lighter or darker.
The function I'm using is $f(x) = \frac{1}{\sqrt{2\pi}\sigma}e^{\frac{-x^2}{2\sigma^2}}$ or the 2D function.
So, should I just apply the results using cross correlation/convolution or should I normalize first?


texts: How does one enter in a boolean expression into an SAT solver?

texts: For example, if we had an extremely large expression, how do we even first get it into the program? I can't imagine entering each clause in one by one..


texts: Is Starvation Possible in LOOK Algorithm

texts:
The LOOK algorithm (wiki) is the same as the SCAN algorithm in that it also honors requests on both sweep direction of the disk head, however, this algorithm "Looks" ahead to see if there are any requests pending in the direction of head movement. If no requests are pending in the direction of head movement, then the disk head traversal will be reversed to the opposite direction and requests on the other direction can be served.

In wiki there is a line which says

  LOOK behaves almost identically to Shortest seek time first (SSTF),
  but avoids the starvation problem of SSTF.

Is it(LOOK) always successful in avoiding starvation or there might be some order of disk request where it may lead to starvation.


texts: Find four sets where each element from those four appears in at least two of those four sets

texts:
I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array:

$A_i = \{x_{i,1}..x_{i,c_i}\}$
$x_{i,p} < x_{i,p+1}$

$A_i$ has length $c_i$ and the average of $c_i \ll n$. For example in one of the runs, the average $c_i$ ranged from $10$ to $15$ and $n$ from $2000$ to $15000$.

I want to find all combinations of four different arrays $M=\{A_r,A_s,A_t,A_u\}$, where each element that appears in any of the $A$'s, appears in at least one of the other $A$'s:

$\forall A_i \in M: \forall x \in A_i: \exists A_{j \ne i} \in M: x \in A_j$

  Assuming that only a small number of the combinations $\epsilon \ll n
(\ll O(n^4))$
  satisifies these requirements, is there a way to do this
  more efficiently than the obvious $O(n^4f(c))$? Here $f(c)$ is some
  reasonably small function in the average $c_i$.

It's probably viable for me if it can be done in $O(n^2c)$ but not if it's $O(n^3c)$.

If we consider the problem described so far to be the case with $|M|=4$, is there also an efficient algorithm for the case with $|M|=3$?

For the case with $|M|=2$, I can simply add each $A_i$ to a hash set after checking if another $A_j$ with the same values is already in the hash set, with expected time about $O(nc)$.

I'm also very interested in the cases where there's up to $y$ cases of $x_i$ that appear in only one of the sets of $M$, where $y = y'-|M|$ and $y'$ is $4$ or $5$

So where would I use such an algorithm? I'm writing a SAT solver. The idea of the solver is that it looks for an integer solution to an ILP problem (without inequality constraints). I have a rectangular matrix with very small integers (0,1,2 mod 3, without the n=2m constraint and the promise) and bring it into Smith normal form. To reduce the search search space, I look for a small set of rows with a small number of nonzero entries, but such rows could be hidden as linear combinations of the rows in the matrix. However since the matrix is in Smith normal form, a row with 4 nonzero entries can only be a linear combination of up to 4 rows, as any 5 rows have 5 pivots. Each row of the normal-form matrix becomes an $A_i$ in the described problem, with the pivot column removed.

The current implementation on github (first link above) only finds rows with 2 nonzero entries and it takes $O(n^2)$ in the worst case.


texts: Is there a formal CS definition of VCS and file versions?

texts: I don't know whether it was a joke, but once I read what was referred to as a formal definition of a file in a versioning system such as git, hg or svn. It was something like a mathematical object like a homeomorphism. Was that a joke or is there really computer science theory about versioning systems and the mathematics of VCS?


texts: Why is DFS considered to have $O(bm)$ space complexity?

texts:
According to these notes, DFS is considered to have $O(bm)$ space complexity, where $b$ is the branching factor of the tree and $m$ is the maximum length of any path in the state space.

The same is said in this Wikibook page on Uninformed Search.

Now the "infobox" of the Wikipedia article on DFS presents the following for the space complexity of the algorithm:

  $O(|V|)$, if entire graph is traversed without repetition, $O($longest path length searched$)$ for implicit graphs without elimination of duplicate nodes

which is more similar to what I thought was the space complexity of DFS, i.e., $O(m)$, where $m$ is the maximum length reached by the algorithm.

Why do I think this is the case?

Well, basically we don't need to store any other nodes than the nodes of the path we're currently looking at, so there's no point of multiplying by $b$ in the analysis provided both by the Wikibook and the notes I'm referred you to.

Moreover, according to this paper on IDA* by Richard Korf, the space complexity of DFS is $O(d)$, where $d$ is considered the "depth cutoff".

So, what's the correct space complexity of DFS?

I think it may depend on the implementation, so I would appreciate an explanation of the space complexity for the different known implementations.


texts:
Suppose that $\Sigma = \{c_1, \dots, c_m\}$ is some finite alphabet and supposing $s \in \Sigma^*$, let $\mathcal{I}_j(s)$ denote the number of instances of character $c_j$ in $s$. Call a string $s$ odd-parity absent iff $|\{j : \mathcal{I}_j(s) = 0\}|$ is odd. That is, $s$ is odd-parity absent iff an odd number of characters from the alphabet are missing from $s$. Call a language $L \subseteq \Sigma^*$ odd-parity absent iff every string in $L$ is odd-parity absent.

Now, suppose that $G$ is a CFG. I'd like to come up with an algorithm for deciding whether or not $L(G)$ is odd-parity absent.

I thought it'd make things simpler if we first convert $G$ into an equivalent Chomsky-normal form grammar. Now, If I could determine what types of terminal strings each variable yields in the grammar (e.g., variable $A$ yields strings with a's and strings with a's and b's, etc.) then I could just inspect the right-hand sides of the start variable rules. But $A$ of course can yield a whole bunch of different variables along the way to derive a string of terminals, and each of those variables can yield a whole other bunch of different variables along the way, etc.


texts: Is the open question NP=co-NP the same as P=NP?

texts: I'm wondering this based on several places online that call $\sf NP=$ co-$\sf NP$ a major open problem... but I can't find any indication as to whether or not this is the same as $\sf P=NP$ problem...


texts: Proving NP hardness of maximum sum of means of a partition into k sets

texts:
I am trying to show the following problem is NP-hard and would like some help.

Inputs: Integer $k$, and unordered set of $N$ numbers, $O$
Output: the $\max \sum\limits_{S_i \in S} \operatorname{mean}(S_i)$
where $S=\{S_1,S_2,...,S_k\}$, $O=S_1 \cup S_2 \cup \dots \cup S_k$ and elements of $S$ are disjoint.

In simpler terms, partition $O$ into $k$ sets to maximize the total sum of the means of the sets.
This problem is a special case of a graph partition problem I am trying to prove NP-hard. I suspect even this special case that removes the graph structure is NP-hard and might be easier to prove. I have tried to reduce from the partition problem (minimize difference of sum of 2 sets).


texts: Would a polynomial-time algorithm for an NP-hard problem implies that P=NP?

texts:
An NP-hard problem is not in NP. (If it was in NP, it would be an NP-complete problem not NP-hard.)

So my question is: if someone can find a polynomial-time algorithm for an NP-hard problem, would that means that P=NP?

I think yes (I am almost sure) but I can't find the reason why?


texts: Do regular languages belong to Space(1)?

texts:
I was wondering, if we take some regular language, will it be in Space(1)?

For a regular language X, for instance, we can construct an equivalent NFA that matches strings in the regular language.

But I cannot see why is X in Space(1).

If it is true, why is X or any other regular language in Space(1)?


texts: Does anyone know of a non-trivial reduction from XORSAT to 2-sat since they are both in P?  (By non-trivial I mean one that does not just solve the instance of XORSAT and map it to a fixed instance of 2-sat.  Rather I'm looking for a way to solve XORSAT by a different method other than just using Gaussian Elimination or some other method of linear algebra.)


texts: What would happen if a multi-layer perceptron is insufficient to learn a function?

texts:
Suppose that something is wrong with its configuration (ie topology), for example there are too few neurons in a certain layer, or not enough layers.

I have an intuition that some neurons' "delta" ($\Delta$) values will be fluctuating wildly without settling down to fixed values.  Is this a justifiable belief?


texts: Can I Use Machine Learning to Predict the Likelihood of an Order Being Shipped?

texts:
Let's say I have a database of freight orders.  The job is to match freight carriers with customers who need their freight moved.  I have the customer's information, the freight carrier's information, and all details related to the freight orders including date ordered, date shipped, the amount of money it took to hire the freight carrier, and whether a carrier was even found to ship the order.

If I have thousands of these past freight orders, could I use machine learning to look at future freight orders to predict whether or not a freight carrier will be found to move it?

Bonus:
If it is possible, what steps would I need to take to find the best data points to focus on?  From what I understand, I need to convert everything to a number in order to train the classifier, but I am having trouble figuring out what data features are going to help make these types of predictions.

I have been studying how to do machine learning and I am not looking for somebody to tell me everything there is to know on the subject, I just don't know how to determine what data points are going to be useful and am also looking for an answer to whether or not this is something machine learning can do(or if it's something a beginner in machine learning can do).  Sorry if the question seems vague, it's kind of hard to articulate on a subject you are just starting to learn about.  If anybody has materials they can link that would help me to better understand these things, I would appreciate that as well..


texts:
Is it possible to count in Automata theory?

I am begginer in Automata theory and I am trying to do some examples.

Currently I am working on a program that will recognise equal numbers of 0 and 1, but they are orderd in such manner that they are together, example:
$$
000111\rightarrow true \quad
0001111\rightarrow false \quad
00011 \rightarrow false \quad
010101\rightarrow false  \quad
$$
I am trying to figure out is there any possibility to count in Automation theory. If not can you please advise me how it would be possible to solve this assingment, because the only way for me is counting.

Thanks.


texts:
There is a way for finding K entries of N given entries using a binary search?

I mean, I have N entries, indexed from 0 to $N-1$ and I have to find $K$ of them that satisfy some constraint.

The naive way is to iterate one after one and check whether it answers the condition or not.
The naive way of Binary Search is using A Binary search until it covers all the tree, this method have a running time $O(K \log n)$.
In this way, I will check whether half of the entries answer the condition or not, if they are I will keep investigating the half of the half and so on.
It's possible to make it more efficient with saving a dictionary from state to its answer.
However, what will be its running time?

Example -
Let's say I have a system and I want to check whether deleting some file corrupt it. The naive way is to delete file after file and to check whether the system behaves normally after each deletion. In Binary search, we can index the files from 0 to N-1 and delete each time half of the files. After each deletion, we can check whether the system behaves normally or not. If it behaves normally, the files we deleted in this step do not affect the system. If not, At least one of the files that were deleted affect the system. I asked, how can I find K files that affect the system?

Thanks.


texts: Constructing a reduction between two languages about pairs of Turing machines

texts:
I'm curious about a potential relation between the following two languages.

$L_1 := \{\langle M_1, M_2 \rangle : L(M_1) \cap L(M_2) \ne \emptyset \}$.

$L_2  := \{\langle M_1, M_2 \rangle : L(M_1) \ne L(M_2) \}$.

  Is it true that $L_2$ mapping reduces to $L_1$?

I've had many failed attempts to construct a reduction and would appreciate any help.


texts: Reduction from an assignment problem to an independent set problem: NP-hard

texts:
The problem I have is as follows:
I have a complete bipartite graph $G=(V \cup C,E)$ as input, where $|V|=1, |C|=n, |E|=n$
The interpretation is that the node of $V$ is a vehicle, the $n$ nodes of C are incidents and the $n$ edges from $V$ to $C$ are the travel times from the vehicle to the incidents.
Now the incidents occur at a certain time and due to that not all incidents can be assigned to the vehicle. Every incident induces a set $D_i$ that consist of incidents that may not be assigned to the vehicle if incident $i$ is assigned to the vehicle:
$D_i = \{k|\text{incidents $k$ that may not be assigned to the vehicle if incident $i$ is assigned to the vehicle}\}$
Out of the sets $D_1, \dots , D_n$ a 'Forbidden Incident' Graph $G=(C,E)$ can be constructed where an edge $(h,i)\in E$ if ($i \in D_h$ or $h \in D_i$).
See the following figure as an example:
Forbidden Incidents Graph

So the problem is: Give a set of incidents, is this set an independent set in the forbidden incident graph?
It is known that an Independent Set problem is NP-hard. Now I aim to proof the conjecture that this problem is also NP-hard.

So I want to find a reduction from my problem to the independent set problem.

Any hints?


texts:
I'm interesting in teaching programming to middle school students.  I'd like a programming language with the following criteria:

Simple - pared down to the absolute minimum needed to support sophisticated programming without too much code.  As such, for this language, I'm not interested in pointers and am weary of object-orientation (although functions are good).
Powerful - I'd like to be able to program 21st-century elements, including graphics, networking, and distributed processing.
Debuggable - I'd like an elegant Integrated Development Environment with a human-readable debugger (i.e. not some strange error message with a stack trace, but a clear explanation that an average middle school student can use to determine what is wrong with the code).

The standard programming languages (C,C++,C#,Java) fail the first criterion.  Basic programming languages like Scratch fail the second (and possibly third) criterion.
Scripting languages (perl, python, php) fail the last criterion.

I'd like to know if someone knows of such a beast, before I sit down to make it up myself.


texts: Imbalance of variables in Mixing Newton's method and Linear solver for a Non-linear system

texts:
Problem

Solving a non-linear system of equations.

The number of variables is the same as the number of equations.

When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{x}$), the system becomes an under-determined, dense, and linear system of the subset of variables
$$A(\vec{y})\vec{x} = \vec{b}(\vec{y})\tag{1}\label{system1}$$

where $A(\vec{y})$ is a dense matrix, and $\vec{b}(\vec{y})$ is a dense vector). Let's call this sub-system $\eqref{system1}$ as system 1.

When I fix $\vec{x}$ and keep $\vec{y}$ free, the system becomes an over-determined, sparse, and non-linear system of the subset of variables
$$F(\vec{x}, \vec{y}) = 0\tag{2}\label{system2}$$

The Jacobian $J(\vec{x}, \vec{y})$ is available in a closed form. Let's call this sub-system $\eqref{system2}$ as system 2.

About half of the equations in $\eqref{system2}$ are equality constraints that are linear in terms of $\vec{y}$. Each of the constraints is quite sparse and involves only about 5% of all variables.

Can I solve it with the following?

Algorithm 1

Initialize $\vec{x} = \vec{x}_0$, and $\vec{y} = \vec{y}_0$
Fix $\vec{y}_{n - 1}$, solve $A(\vec{y}_{n-1})\vec{x}_{n} = \vec{b}(\vec{y}_{n-1})$ for one of all the possible $\vec{x}_{n}$ because this system is under-determined.
Fix $\vec{x}_{n - 1}$. Perform one iteration of Newton's method for solving $F(\vec{x}_{n-1}, \vec{y}_{n}) = 0$ for $\vec{y}_{n}$.
If not converged, go to step 2.

Algorithm 2

If I replace step 2 in Algorithm 1 by a Newton's method iteration for solving system 1 $\eqref{system1}$, then I guess the steps become a block Newton's method.

Question

But I don't know if these two algorithms can work because system 1 $\eqref{system1}$ is under-determined and system 2 $\eqref{system2}$ is over-determined.

Can this work?

Related

A. Yeckel, L. Lun, and J. J. Derby, "An approximate block Newton method for coupled iterations of nonlinear solvers: Theory and conjugate heat transfer applications," J. Comp. Phys., vol. 228, no. 23, pp. 8566–8588, Dec. 2009

B. Polyak and A. Tremba, "Solving underdetermined nonlinear equations
by Newton-like method"
Solving over-determined non-linear equations with Newton's method and Moore-Penrose inverse is fine.
V. Meñkov. "Solving block linear system with low-rank off diagonal blocks is easily parallelizable"
Block triangular form allows some blocks to be over-determined while other blocks to be under-determined. Newton's method is equivalent to solving the system linearized at current approximation of solution. The question is equivalent to if it is possible to solve a system of linear equations by alternatively performing iterations of Newton's method on two groups of variables.
Śmietański, M. J. "A generalized Jacobian based Newton method for semismooth block-triangular system of equations" J. Comput. Appl. Math.. 2007.
Solving block triagular system by newton iteration on each block can work. "We prove locally superlinear convergence of parameterized version method that is well defined even when the generalized Jacobian is singular."

Guess

It is similar to a coordinated descent over two groups of variables. So I hope algorithm 2 should be generally fine. Algorithm 2 would keep the approximate solution in each iteration close to each other. Algorithm 1 might make the variables jump around in some cases (might. but I am not sure). I assume the trajectory of approximate solutions don't form a stable cycle or orbit. But Newton's method in general has the same  assumption.


texts: Find MST on grid graph with only weight of 1 and 2 in $O(|V|+|E|)$

texts:
Given a grid graph $G=(V,E)$ which has only two different integer costs/weights of 1 and 2. Find Minimum Spanning Tree in $O(|V|+|E|)$.
I tried the following:

Changing Kruskal using a counting Sort in $O(|E|)$. But can I say that this results in O(|E|+|V|)? Since Kruskal would normally be ${\displaystyle O(T_{sort}(|E|)+|E|\cdot \alpha (|V|))} =O(|E|)$ when $\alpha (|V|) \in O(1)$ Can this be stated for this case? I lack detailed understanding of inverse ackerman behaviour.
Other possibility changing Prim so that I use a priority queue which support del_min, decreaseKey and insert in $O(1)$. I thought about using two simple stacks or queues and only del_min from the one, which holds the 1 integers, but descreaseKey seems not efficient since I have to loop through the lists to find the elements. So maybe combine this with some kind so hash mapping to directly access each element in $O(1)$ for decreaseKey?

Both seem really close to the actual result, though I am struggling to see the right solution for this case.


texts: approximation algorithm for Travelling Salesman Problem: with a different inequality and not triangle inequality

texts:
I have the following question for the travelling salesman problem:

The TSP algorithm is to find a complete hamilton cycle with minimum cost in a weighted graph G. Instead of the traingle inequality, the weight function satisfies the following inequality:

cost(u,w) < cost(u,v) + 2 x cost(v,w)

Find the approximation ratio if we use the following approximation algorithm:

1. Select any vertex as root vertex
2. Compute a minimum spanning tree T from graph G
3. Let L be the list of vertices visited in a preorder tree walk of T
4. return the hamilton cycle H that visits the vertices in the order L

My work so far

I figured out that it is 2-approximation if it is the triangle inequality, since going directly from one vertex to another has a cost no greater than going to a vertex in between these two vertices, so cost(H) is not greater than the cost of the preorder tree walk and therefore no greater than twice the cost of the optimal tour.

However, inequality cost(u,w) < cost(u,v) + 2 x cost(v,w) would make it different than triangle inequality that going directly from u to w could result in higher cost than from u to v to w (unless cost(v,w)=0). I think the worst case is extra cost of cost(u,v) + 2 x cost(v,w) - (cost(u,v) + cost(v,w))= cost(v,w)

Any advice on this? I need to find the approximation ratio.


texts: Minimal size of contracting a DAG into a new DAG

texts:
We have a DAG. We have a function on the nodes $F\colon V\to \mathbb N$ (loosely speaking, we number the nodes). We would like to create a new directed graph with these rules:

Only nodes with the same number can be contracted into the same new node. $F(x) \neq F(y) \Rightarrow x' \neq y'$. (However, $x' \neq y'\nRightarrow F(x) \neq F(y)$.)
We add all the old edges between new nodes: $(x,y) \in E \land x' \neq y' \iff (x',y')\in E'$.
This new graph is still a DAG.

What is the minimal $|V'|$? What is an algorithm creating a minimal new graph?


texts: Assigning packages to different points by minimizing distance: is this a known problem?

texts:
Imagine we have N houses, on a standard euclidean 2D plane. We also have N "packages", each of which contains several "objects" of different types, let's call them A, B, C, etc. We know the content of all boxes beforehand, but can't change them (they're randomly generated).

We need to send one package to every house, and we know that the person who lives in the house will need to use one or more of the objects, but we can't know which of them they will need. To use the object, they will travel to the nearest house that has it (ideally their own), use it there, and go back to their house. We need to assign a package to each house to minimize the potential distance they will have to travel.

For example:

Package 1 contains B, C, D, E
Package 2 contains A, B, D, F
Package 3 contains A, E, F, G
House 1 is at (0,0)
House 2 is at (0, 5)
House 3 is at (12, 0)

We send packages 1, 2 and 3 to houses 1, 2 and 3:

Owner of house 1 needs A and B: travels 5 to house 2 to get A (and back, but we're not counting that).
Owner of house 2 needs C and G: travels 5 to house 1 to get C, goes back, then 13 to house 3 to get G (total = 18)
Owner of house 3 needs A and G: travels 0 to their own house.

Total distance = 23

Since we can't know what they will want, we assume everyone needs everything. This means I need to minimize the sum of the shortest distance between every location and every type of object. Is this a known problem? How can I make an approximation algorithm for it? It sounds simple enough but I'm stumped, I have no idea how to search for it.

I was thinking along the lines of calculating a "differentness" of every package to every other one, then trying to place the "most different" packages closer to each other and the more similar ones further, but I don't really know how to do that either.


texts: How to Show that an Algorithm Depends on all N inputs (and thus has a lower bound of Omega(n))

texts: In the algorithm detailed on this page: Fastest Algorithm for Computing Expected Value, I was wondering how to prove that the algorithm depends on all $n$ of the inputs it is fed (and thus has $\Omega(n)$).


texts: Construct a computable function from non-computable funciton

texts:
Let $f_1 $ and $f_2$ be two functions from $\mathbb{N} \rightarrow \mathbb{N}$.

$f_1$ is turing-computable while $f_2$ is not.

$h(i)$ is a function that returns $1$ when $f_1(i) = f_2(i)$ and $0$ else.

The challenge is to construct $f_1 $ and $f_2$ so that $h(i)$ is computable and additionally so that it is not.

My thought process is that for either scenario we have to use the computability and non-computability property and pass that forward to $h(i)$ but I am not sure how.

One thought I had to make $h(i)$ uncomputable is to define $f_2$ and $f_1$ on a for a small set of numbers and let $f_2$ be uncomputable on all other numbers. This way I cannot compute if $f_2 = f_1$ so I cannot compute wether $h(i)$ outputs $1$ or $0$.

But I dont know how to make $h(i)$ computable given the requirements that $f_2$ be uncomputable.

Can anyone nudge me in the right direction ?


texts: Temporal logic - mixing AF and AG in CTL formula

texts:
Let's look at example AF(φ1 -> AG(φ2)).

Does it mean that:

In all paths it eventually happens that if φ1 was satisfied, φ2 is satisfied all along the path (so it basically means φ2 is satisfied in all states in all paths)

or

In all paths it eventually happens that if φ1 was satisfied, φ2 is satisfied starting when the φ1 satisfaction started

or

Something else?

If 1, then isn't it equivalent to AF(φ1) -> AG(φ2)?

If 2, will the G start at the current or at the next iteration?

For example if φ1=p , φ2=q, are both A and B in the language, or just A?

A. q-p-q-pq-q-q-q-q-q...

B. q-p-q-p-q-q-q-q-q...