texts: What will be the complexity of the function having two input sizes?

texts:
What will be the complexities in the following case:

T(m,n) = T(m-1,n) + T(n-1,m) + O(m*n)

After a bit of searching I found that if I could make this function monotonic and then try to find the solution. But I am feeling that this is not the correct way to do it.

Kindly suggest the solution to it.


texts: Computational complexity of finding a spanning tree in planar hybergraphs

texts:
Using a bipartite graph to represent hypergraphs as described by Wikipedia :

  A hypergraph $H$ may be represented by a bipartite graph $BG$ as follows:
  the sets $X$ and $E$ are the partitions of $BG$, and ($x_1$, $e_1$) are
  connected with an edge if and only if vertex $x_1$ is contained in edge $e_1$
  in H.
  Conversely, any bipartite graph with fixed parts and no unconnected
  nodes in the second part represents some hypergraph in the manner
  described above. This bipartite graph is also called incidence graph.

Now if we assume that a hybergraph is planar if and only if it can be represented by a planar bipartite graph. What is the complexity of finding a spanning tree in planar hybergraphs? It is also ok if you can provide any source on how to approach this problem.

Note: It is known that the spanning tree problem of general hybergraphs is $NP$-complete, while spanning tree of $3$-uniform hypergraphs, where all hyperedges are of size $3$, has a polynomial algorithm using matroid matching [ref].

Note: Under the bipartite representation of hypergraphs the problem of spanning tree becomes equivalent to the problem of finding a subset of vertices that induces a tree such that the tree contains all vertices of one of the bipartitions of the bipartite graph. The problem is a bit similar to the Induced-Tree problem defined in this paper, but in this problem the induced tree must contain any set $S$ of vertices as part of the problem input. The Induced-Tree problem is $NP$-complete even for planar bipartite cubic graphs.


texts:
I would like to find a prove of (a) so that the two E are acyclic and disjoint union and I dont unterstand b Could someone shed light on this problem, preferably spiced with some intuition?
Thanks, DarkDragon.


texts: A question about the clique problem (specifically k-clique). Is there any algorithm that takes advantage of the properties of connected graphs to find cliques of a given size k, if such cliques exist?


texts: Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less

texts:
I am trying to prove that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ such that a DFA accepting $A_k$ has $k$ states but no less.
I thought about proving this in two ways: constructively, or by contradiction.
By Contradiction: For some $k > 1$, suppose there is no language $A_k \subseteq \{0, 1\}^*$ where a DFA accepting $A_k$ exists with exactly $k$ states but no less. Then any language $L \subseteq \{0, 1\}^*$, that has an accepting DFA with $n$ states, also has an accepting DFA with $n - 1$ states. Extending this reasoning downward, this implies that every $L$ has an accepting DFA with $1$ state. This is a contradiction.
By construction: Let $A_k = \{w \in \{0, 1\}^* | w \text{ has } 0^{k - 1} \text{ as a substring}\}$. But now I need to prove that $A_k$ cannot be accepted by a DFA with less than $k$ states. I am unsure of how to do this even though it feels true intuitively.
Is my proof by contradiction valid and is the proof by construction doable? Maybe both are wrong and I need to use some other perspective.
Attempt 2:
We can easily construct a DFA with $k$ states, call it $M_k$, that accepts the language $$A_k = \{w \in \{0, 1\}^* | w \text{ has } 0^{k - 1} \text{ as a substring}\}$$
Suppose for contradiction that there exists a DFA, $M_{k - 1}$, accepting $A_k$ with $k - 1$ states. Consider the string $w = 0^{k - 1} \in A_k$, we can apply the pumping lemma because $|w| \geq k - 1$. Thus, the run of $w$ on $M_{k - 1}$ must contain a cycle of length 1 (since $|w| = k - 1$).
Then $M_{k - 1}$ actually accepts strings of the form
$$w' = 0^x \cdot 0^i \cdot 0^z$$
where $i \geq 0$, $x + 1 \leq k - 1$ and $x + z + 1 = k - 1$. Letting $i = 0$, we see $M_{k - 1}$ accepts $0^{k - 2} \not \in A_k$. A contradiction.
This reasoning is applicable to every $M_i$ with $1 < i < k$, so we are done. Is this a correct attempt?


texts: Standard information-theoretic lower bound?

texts:
There should be a simple argument, but I'm struggling to see it.

Suppose Alice has a string $x \in \{0, 1\}^n$ and sends a message $s = s(x)$ to Bob. And suppose that given $s$, Bob can reconstruct each bit of $x$ with probability $2/3$ (say). (Note that this is weaker than the claim "with probability $2/3$, Bob can recover the entire string $x$." A clean proof of this case would be appreciated too.)

Then we should be able to conclude $|s| = \Omega(n)$, and this seems obvious, but can someone formalize this for me?


texts: What types of string properties are verifiable in polynomial time?

texts:
When given the string and the property in question as a potential certificate. Is there any classification theorem that says something along the lines of: all properties (of strings) that have this property (as a sub property) are verifiable in polynomial time?

Are there any collections of types of patterns in strings that are verifiable in poly time?

A trivial property is that a collection of strings with these properties belong to a language in NP (belonging to NP being the sub property).

I'm looking for something more concrete.

I'm looking for the common thread between string properties like these that makes these properties verifiable in poly time for any string.

i.e. is there a way to pick properties of strings out of a hat in such a way that the properties you pick are guaranteed to be verifiable in poly time in any string.

Maybe there is a way to do this with implicit complexity--where the only properties you can build (in some restricted language) are the ones that are verifiable in poly time?


texts: Is there a tool that can check whether m |= p holds, where m and p are both ltl formula

texts:
To the best of my understanding, m |= p asks whether the ltl formula p satisfies the ltl formula m. In other words, m -> p is a tautology. Here are some example of where m |= p hold:
Xp |= Fp

q  |= p U q

Gq |= Fq

Of course, trying to visualise all this in you head and trying to work out if m |= p holds can get very time consuming, especially if m and p are very long. So, I was wondering there is some tool/software/platform that can compute m |= p.


texts: Showing $A-B$ is a CFL where $A$ is a CFL and $B$ is finite

texts:
Show that if $A$ is a context-free language and $B$ is finite, then $A - B$ is a context-free language.

I'm just not sure how to use their properties to formally show this. Thanks for all the help in advance.


texts: How broken is LCG in the case of partial output?

texts:
Suppose we have a linear congruential generator defined by $X_{n+1} = (a X_n + c) \mod 2^n$ where $a, c, n$ are all known and we would like to determine the initial value $X_0$. However, if we can only see the $k$ high-order bits of each of the $X_i$ for $i \geq 0$, the best algorithm I know of is a brute force which tries $O(2^{n-2k})$ possibilities, and this is exponential in $n$.

Compare this to the Mersenne Twister, whose initial state can be computed in polynomial time given only the high-order bits of each output (it reduces to solving a system of $n$ equations in $n$ unknowns). Is there a better algorithm out there which can solve for the initial state of an LCG given only the high-order bits of each output, and if not, is LCG actually broken?


texts: In what case would bi-directional BFS have the same asymptotic run time as a regular BFS?

texts:
I'm not quite sure when they would have the same asymptotic running time. Would it be if the graph was each node connected to one other node in a line? I know that for a bi-directional BFS to have a worse running time a star graph would work, but I'm not quite sure how they would have the same asymptotic running time or how to design a set of graphs that would cause this.

Thanks.


texts: Max-Flow: Detect if a given edge is found in some Min-Cut

texts:
Given a network $G=(V,E)$ , a max flow f and an edge $e \in E$ , I need to find an efficient algorithm in order to detect whether there is some min cut which contains $e$.
Another question is, how do I decide whether if $e$ is the lightest edge of at least one minimal cut?

I've thought about running Ford-Fulkerson algorithm, and then increasing / decreasing the capacity of the given edge and see what happens, but I haven't came up with something that might help me solve the problem.

I'd be grateful if anyone could point me to the solution, thanks in advance.


texts: Why each function may be computed with circuit with 2^n gates?

texts:
Why each function may be computed with circuit with 2^n gates ?

I am trying to understand this thing, but I can't. In particular why function constant $1$ requires $2^n$ gates. For me, it should be simple to return $1$ regardless of input.


texts:
I'd really like your help with the proving or refuting the following claim: $BPP(0.90,0.95)=BPP$. In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most $\frac{1}{3}$ for all instances. $BPP=BPP(\frac{1}{3},\frac{2}{3})$.

It is not immediate that any of the sets are subset of the other, since if the probability for an error is smaller than $0.9$ it doesn't have to be smaller than $\frac{1}{3}$ and if it is bigger than $\frac{2}{3}$ it doesn't have to be bigger than $0.905$.

I'm trying to use Chernoff's inequality for proving the claim, I'm not sure exactly how.
I'd really like your help. Is there a general claim regarding these relations that I can use?


texts: Optimal algorithm for signaling for help?

texts:
I was thinking about the following problem the other day:

  You are stuck on a desert island with a battery-powered emergency radio.  You know that if you feed enough power into the radio that you should be able to alert someone to your position.  In fact, as soon as you provide the radio enough power to reach someone else, they'll respond back to you and send help.

  The problem is that you don't know where anyone else is, so you have no idea how much power to feed into the radio.  You can assume that the radio can transmit at power levels that are natural numbers.

  What is the most power-efficient way to signal for help?

One inefficient solution to this would be to transmit at power $1, 2, 3, ...$ until you reach the necessary power $n$.  This works, but it requires power usage $1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}$.

The algorithm I currently think is optimal is to instead transmit at power $1, 2, 4, 8, 16, ... $ until the necessary power $n$ is reached or exceeded.  This requires power
$$1 + 2 + 4 + 8 + ... + 2^{\lceil \log_2 n \rceil} = 2^{\lceil \log_2 n \rceil + 1} - 1$$

which is somewhere between $2^{\log_2 n + 1} - 1 = 2n - 1$ and $2^{\log_2 n + 2} - 1 = 4n - 1$

My question is whether or not this is the optimal algorithm for solving this problem, given that $n$ is completely unknown.  I can't seem to find a more efficient algorithm, nor can I find a proof that this is optimal.

Is there a better way to solve this problem?  Or is this the optimal solution?


texts: Why is the objective in a multi-armed bandit problems to minimize (cumulative) regret?

texts:
In a multi-armed bandit, the objective is to maximize the expected cumulative reward. This objective is usually (equivalently?) stated in terms of expected cumulative regret.

Question: Why not just deal with the reward? Why formulate the objective in terms of regret?


texts: Why is the step property in a balancing network defined as it is?

texts:
I was trying to understand why the equation $y_i = \left( \frac{n}{w} \right) + (i \pmod w) $ describes the step property in a balancing network?

First, recall $x_i$ to be the number of tokens a network gets as input and similarly $y_i$ to be the number of output tokens. Recall that a balancing network is just a network that distributes tokens to its output.

I was reading the art of multicore programming and in page 272 it says:

  If the number of tokens n is a multiple of four (the network width),
  then the same number of tokens emerges from each wire. If there is one
  excess token, it emerges on output wire 0, if there are two, they
  emerge on output wires 0 and 1, and so on. In general,

  $$ n = \sum x_i $$

  then

  $$y_i = \left( \frac{n}{w} \right) + (i \pmod w) $$

  we call this property the step property.

It also defines equivalent ways to see the step property as:

For any $i<j$, $0 \leq y_i - y_j \leq 1$

i.e. as we go up the output wires, the wire can only increase one step at a time or not increase (so top values are always larger or equal). An example:

However, the formula $y_i = \left( \frac{n}{w} \right) + (i \pmod w) $ doesn't make sense to me also, specifically the following doesn't make sense:

  if there are two, they emerge on output wires 0 and 1, and so on...

I tried plugging in the numbers too say, $ n = 6 $, but the results don't quite make sense.

For example according to the formula above we get:

$$ y_0 = \left( \frac{6}{4} \right) + (0 \pmod 4) = 1 + 0 = 1 $$
$$ y_1 = \left( \frac{6}{4} \right) + (1 \pmod 4) = 1 + 1 = 2 $$
$$ y_2 = \left( \frac{6}{4} \right) + (2 \pmod 4) = 1 + 2 = 3 $$
$$ y_3 = \left( \frac{6}{4} \right) + (2 \pmod 4) = 1 + 3 = 4 $$

which doesn't agree with what  the picture of the diagram would be because it seems to be backwards. Not sure if I made a mistake or misunderstood the formula, but it should be giving something as in the figure/diagram/picture from the book. Also, according to the formula, is it ever possible for it be equal? It seems to always increase in the wrong direction.


texts: Flajolet-Martin Algorithm : question about use of certain hash functions

texts:
this is a question given in a PDF about streaming algorithms (this isnt an assignment but im trying to understand)

  Exercise 4.4.1 : Suppose our stream consists of the integers 3, 1, 4,
  1, 5, 9, 2, 6, 5. Our hash functions will all be of the form h(x) =
  ax+ b mod 32 for some a and b. You should treat the result as a 5-bit
  binary integer. Determine the tail length for each stream element and
  the resulting estimate of the number of distinct elements if the hash
  function is:

  (a) h(x) = 2x + 1 mod 32.

  (b) h(x) = 3x + 7 mod 32.

  (c) h(x) = 4x mod 32.

  ! Exercise 4.4.2 : Do you see any problems with the choice of hash
  functions in Exercise 4.4.1? What advice could you give someone who
  was going to use a hash function of the form h(x) = ax + b mod 2k ?

I have already resolved the first exercise, finding a max R tail length of 0 for (a) and 4 for (b) and (c), therefore the resulting estimation of distinct elements is respectively 1,16,16. (it is not asked to do averages/medians of the hash functions to find a better value)

However, I can't seem to figure the answer to the second exercice ? Is it simply to choose 'a' and 'b' in a certain manner ? or are these functions not good to generate equally randomly numbers with trailing 0s and no trailing 0s ?

Thank you in advance

you can observe the results of each hash functions by running this code : https://onlinegdb.com/rJXC4f4VL


texts: Difficulty understanding the faster multiplication hardware

texts: This is a picture of faster multiplication hardware taken from Computer Organization and Design (5th Edition). I'm having some difficulty understanding it. I was trying to simulate this for a test multiplication of : 1011 x 101. Firstly, P0 is simply the LSB of the (Mplier0 * Mcand) which gives P0 = 1 The two operands of the upper rightmost adder would be then, 1011 (Mplier0 * Mcand) and 0000 (Mplier1 * Mcand) which would produce the result 1011 with P1 = 1. This 1011 would then be one of the inputs of the second stage adder. The other input of the second stage/level adder would come from the upper 2nd rightmost adder. Which gives 1011 (Mplier2 * Mcand) + 0000 (Mplier3 * Mcand) = 1011. So the two inputs of the second stage adder are both 1011. Finally the output of this second stage adder will be 1011 + 1011 = 10110. The penultimate result is 1011011. But the correct answer is 110111. What am I doing wrong here?


texts: What are the differences between the set of Real Numbers and the Java datatype float?

texts: Besides the fact that the real numbers ℝ go on forever whereas the floats only go up to a certain point (Float.MAX_VALUE) in Java, what else could I compare between these two sets of numbers?


texts: Is there a simple argument why graph isomorphism is not NP-complete?

texts:
I need to provide one simple evidence that graph isomorphism (GI) is not NP-complete.
I saw a number of papers on google scholar and answers on StackExchange. However, I have very limited knowledge of graph isomorphism, and I would like to just provide one simple evidence which I both understand and can explain clearly.

Below is what I can think of. Is this a valid argument?
Currently, we can solve GI in Quasipolynomial Time. If GI is NP-complete, then we should be able to solve other NP-complete problems in Quasipolynomial Time as well. However, right now, we are unable to solve any NP-complete problem in Quasipolynomial Time. Therefore, GI cannot be in np-complete.


texts: modifing CYK to compute the number of different parsing trees of a given sentence

texts:
Given a CFG in Chomsky Normal Form and a sentence s.
I want to count the number of different parsing trees that parses s.
assuming I know how to change the CYK algorithm so it would count the number of parsing trees, how can I determine if one tree X is different then tree Y? obviously it can be done in a naive way that I would save all my current parse trees and for every new tree I would check if it already exists but it's time-consuming and space-consuming as It requires to save all the previous parsing trees in a data structure... I would like to avoid that.


texts:
forest : set of disjoint trees.

So a connected forest is a forest, a tree, a spanning forest and a spanning tree.

Is that correct?

Edit: disjoint trees in the forest are connected by single edge, so as to make the forest connected


texts: Can undecidability theorems be detected by a machine?

texts:
this question was originally written in mathoverflow, but a comment recommended me to rewrite it as a CS question.

This is not a mathematically formalized question. I'm sorry for that but think it's more like mathematics than philosophy.

When we proved a theorem A which says "B is undecidable", we don't try to prove neither B nor (not B). Can a machine do the same thing? Can it detect "meaning" of a statement, like "something is undecidable"?

Here's a reason why I don't think so.

Suppose a sentence

universal_Turing_machine(program, input, output)

is true if and only if resulting output of "program" with given "input" is "output". Of course, if the program doesn't halt, it would be false for any "input" and "output".

Now, let x be a Godel number of a sentence. Consider the following sentence:

there is no y such that:
y is a Godel number of a string which ends with a sentence encoded as x,
and universal_Turing_machine(program, y, true)

If the program acts as a "decision program accepting valid proofs", this sentence obviously means "a sentence encoded as x is not provable". If not, this sentence doesn't mean any undecidability. Hence if a machine can detect undecidability theorems, it has to detect programs which act as "decision programs accepting valid proofs"

But according to Rice's theorem, detecting programs which has a specific property is not possible.

Do you think this "reason" makes sense? Since this is not a pure mathematical question, I hope to listen to your opinions. Thank you.


texts: Is There An Established Way To Send Code Over a Network?

texts: Let's say I have two computers on a network. I want to write code in some language on machine A, send the code in an efficient way over a network, and run the code on machine B. It seems to me that this would be inherently slow and would run into a bundle of problems (not having required dependencies) but perhaps some work has already been done on this problem? Is there any known processes or systems that already do this?


texts: what is the difference between Operating system and Window Systems?

texts:
Quoting from Tannenbaum_Operating_Systems_Design :

  On top of the operating system is the rest of the system software.
  Here we find the command interpreter (shell), window systems,
  compilers, editors, and similar application-independent programs. It
  is important to realize that these programs are definitely not part of
  the operating system

I am not getting the difference between these two keywords ,isn't the Windows an Operating system so what's the meaning of this Window Systems which is not the part of Operating System.
When we say that windows is an operating system then how can we make a distinction between windows systems and an Operating system ?


texts: How to show that some problem is in NP and that it's NP-complete

texts:
I need some help with the following question:

Recall the subset sum problem, which is known to be NP-complete:
"Given a finite set of natural numbers and a number $n$, decide whether a subset of the given set exists such that the numbers in that subset sum up to $n$."
We consider the great subset sum problem:
"Given a finite set of natural numbers adding up to $N$ and a number $n > N/2$, decide whether a subset of the given set exists such that the numbers in that subset sum up to $n$."
a. Show that the great subset sum problem is in NP by giving the notion of certificate and arguing that the certificate can be checked in polynomial time.
b. Show that the great subset sub problem is NP-complete.
(Hint: extend the set by adding one large number.)

This was my "proof" but I think it lacks details and I feel it's wrong because I didn't use the hint for part B. Can someone tell me if did something wrong? But please, don't get use too many technical terms as we mainly use text and I might not understand your explanation.

a) A certificate for the great subset sum problem is a subset of the given set of natural numbers.
Certificate checking is done by adding up the numbers in the subset and comparing the result to the number n without forgetting the extra requirement that n > $N/2$.
Clearly, if m is the size of the original set of numbers (i.e., the size of the input), then the verification requires at most $m-1$ additions, one comparison, and final checking step, so it can be done in $O(m)$.
$O(m)$ because of the following: Adding 2 numbers takes O(1), you have to do that m-1 times. Then do one computation which also takes O(1) and finally do one comparison which also takes O(1), so in total that's O(m).
b) From the first part of the exercise it already follows that the great subset-sum problem is in NP.
To show that the great subset-sum problem is NP-complete, it remains to prove that it is NP-hard. The latter we can do by showing a polynomial-time reduction from the subset sum problem to the great subset sum problem.
Let S be a set of natural numbers and let n be a natural number. Let  $S^\prime$ be obtained from S by dividing every number in S by 2; clearly, $S^\prime$ can be obtained by an algorithm whose running time is linear in the size of S. Note that S has a subset such that the numbers in that subset add up to n if, and only if, $S^\prime$ has a subset such that the numbers in that subset add up to n where n > $N/2$.
So, we have now presented a polynomial-time reduction from the subset-sum problem to the great subset-sum problem. Since the subset sum problem is NP-hard, it follows that the great subset sum problem is NP-hard too.


texts: Are there sorting algorithms that take advantage of a metric space?

texts:
We know comparison sorting algorithms use the ternary information (lt, eq, gt) garnered from a single comparison to make decisions about what to do next. Is there any research into using a metric? That is, if we compare $x$ and $y$ and we not only know that $y > x$ but we also know the value $y - x$. Presumably if $y - x$ were a very large number we could heuristically separate them from each other, or move $y$ closer to end of the array, or move $x$ closer to the beginning. Could you make fewer than $O(n \lg n)$ comparisons in this way?

This is not a very precise idea (and credit goes to my friend Ian who brought it up out of the blue one day), but I Googled around for a little bit and I was unable to find anything to help me narrow the question.


texts: Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$

texts:
We know that $st\text{-}non\text{-}connectivity$ is in $\mathsf{NL}$ by Immerman–Szelepcsényi theorem theorem and since $st\text{-}connectivity$ is $\mathsf{NL\text{-}hard}$ therefore $st\text{-}non\text{-}connectivity$ is many-one log-space reducible to $st\text{-}connectivity$. But is there a direct/combinatorial reduction that doesn't go through the configuration graph of the Turing machines in $\mathsf{NL}$?

$\mathsf{stConnectivity}$ (a.k.a. $stPATH$):
Given directed graph $G$ and vertices $s$ and $t$,
Is there a directed path from vertex $s$ to vertex $t$?

Clarifications:
You can assume a graph is given by its adjacency matrix (however this is not essential since standard representations of graphs are log-space convertible to each other.)
It is possible to unpack the proof of $\mathsf{NL\text{-}hard}$ness of $st\text{-}connectivity$ and move it into the proof so the proof does not use it that theorem as a lemma. However this is still the same construction essentially. What I am looking for is not this, I want a conceptually direct reduction. Let me give an analogy with the $\mathsf{NP}$ case. We can reduce various $\mathsf{NP\text{-}complete}$ problems to each other by using the fact that they are in $\mathsf{NP}$ therefore reduce to $SAT$ and $SAT$ reduces to the other problem. And we can unpack and combine these two reductions to get a direct reduction. However it is often possible to give a conceptually much simpler reduction that doesn't go through this intermediate step (you can remove mentioning it, but it is still there conceptually). For example, to reduce $HamPath$ or $VertexCover$ or $3\text{-}Coloring$ to $SAT$ we don't say $HamPath$ is in $\mathsf{NP}$ and therefore reduces to $SA$ since $SAT$ is $\mathsf{NP\text{-}hard}$. We can give a simple intuitive formula that is satisfiable iff the graph has a Hamiltonian path.
Another example, we have reductions from other problems in $\mathsf{NL}$ to $st\text{-}Connectivity$ which do not rely on $\mathsf{NL\text{-}complete}$ness of $st\text{-}Connectivity$, e.g. $Cycle$, $StronglyConnected$, etc, they involve modification on the input graph (and do not refer to any Turing machines that is solving them).
I still don't see any reason why this cannot be done for this one.
I am looking for a reduction of this kind.
It might be the case that this is not possible and any reduction would conceptually go through the $\mathsf{NL\text{-}hard}$ness result. However I don't see why that should be the case, why the situation would be different from the $\mathsf{NP}$ case.
Obviously to give a negative answer to my question we would need to be more formal about when does a proof conceptually include another proof (which is proof theory question that AFAIK not settle in a satisfactory way). However note that for a positive answer one does not need such a formal definition and I am hoping that is the case. (I will think about how to formalize what I am asking in a faithful way when I find more free time. Essentially I want a reduction that would work even if we didn't know that the problem is complete for $\mathsf{NL}$.)
Using the proof of Immerman–Szelepcsényi theorem is fine, using $\mathsf{NL\text{-}complete}$ness of $stPATH$ and configuration graph of an $\mathsf{NL}$ machine is what I want to avoid.


texts: In an FSA, can you have more than one transition for the same symbol from a single state?

texts:
My textbook asks:

  Consider the sets of strings on $\{0,1\}$ where the 4th symbol from the right end is different
      from the leftmost symbol. Construct an accepting FSA.

The answer it provides is below. However, I don't understand how you can have one transition for 0,1 and another for 1 from the same state. What does this mean?


texts:
I want to make folders of images of users in a meaningful way. The images have only the timestamp of creation associated with them. Each folder can have a maximum of k images.

I can use median or mean as a way of deciding which images were taken in a definite time period.

What approach should I use to group these images in folders in such a way that the user is most intuitively able to make sense of the folders?

I am also asking here what would be an intuitive distinction for the user(I cannot use the day or hour of the image to group as I have the k images restriction.)


texts: MIPS Pipeline Hazards - Branch Delay Slot

texts:
I'm confused about this exercise.

We have assembly code:

01: ADDI $1, $0, 1000
02: LW   $2, 0($1)
03: BEQ  $0, $0, LABEL
04: MULT $3, $2
05: ADDI $2, $2, 1000
LABEL:
06: MFLO $4
07: ADDI $2, $1, 5
08: SW   $2, 0($1)
09: NOP

with:
- 6-stages Pipeline
- Branch Delay Slot
- No Bypassing

Is this correct?

Does the Instruction in Branch Delay Slot effect on/by the others Instructions. For example here:
02: LW   \$2, 0(\$1) and 04: MULT \$3, \$2
04: MULT \$3, \$2 and 06: MFLO \$4


texts:
In set builder notation, we can represent the set: $$\{ 2, 7\}$$ as: $$\{ x | x=2 \vee x=7 \}$$.

Therefore, the PA arithmetic predicate: $$φ(x) :=  x=2 \vee x=7$$ is capable of representing this set. The boolean expression: $$x=2$$ can also be represented in arithmetic by the function:

$$1-sgn(x-2)²$$

So: $$x=2 \vee x=7$$ is equivalent to: $$(1-sgn(x-2)²) \vee (1-sgn(x-7)²)$$.

Since: $$x \vee y = x+y-xy$$

we can represent:

$$φ(x) := 1-sgn(x-2)² \vee 1-sgn(x-7)²$$

$$φ(x) := 1-sgn(x-2)² + 1-sgn(x-7)²-(1-sgn(x-2)²)(1-sgn(x-7)²)$$

which simplifies to:

$$φ(x) := 1 - sgn((x-7) (x-2))²$$

So, we can have an arithmetic predicate that does not need to use boolean operators and that can represents the set:

$$ \{ a_1, a_2, a_3, ... , a_n \}$$

arithmetically as:

$$φ(x) := 1 - sgn((x-a_1)(x-a_2)(x-a_3)...(x-a_n))²$$

Now I am stuck trying to use a similar technique to represent the embedded set expression:

$$\{1, 2, \{ 4, 9\}, 7\}$$

The inner embedded set { 4, 9 } in the expression above may look somewhat like:

$$φ_2(x) := 1 - sgn((x-4)(x-9))²$$

The outer set may look somewhat like:

$$φ_1(x) := 1 - sgn((x-1)(x-2)(x-φ_a(x))(x-7))²$$

But I cannot figure out how to express:

$$φ_a(x)$$ in terms of: $$φ_2(x)$$

Can this actually, uberhaupt, even be done?


texts:
I'm referring to a post on a black-box algorithm and the Independent Set problem.
Question

Suppose that someone gives you a black-box algorithm $A$ that takes an undirected graph $G = (V, E)$, and a number $k$, and behaves as follows.

If $G$ is not connected, it simply returns “$G$ is not connected.”
If $G$ is connected and has an independent set of size at least $k$, it returns “yes.”
If $G$ is connected and does not have an independent set of size at least $k$, it returns “no.”

Suppose that the algorithm $A$ runs in time polynomial in the size of $G$ and $k$.
Show how, using calls to A, you could then solve the Independent Set Problem in polynomial time: Given an arbitrary undirected graph $G$, and a number $k$, does $G$ contain an independent set of size at least $k$?

Solution

There are two basic ways to do this. Let $G = (V, E)$; we can give the answer without using $A$ if $V = \emptyset$ or $k = 1$, and so we will suppose $V \neq \emptyset$ and $k > 1$. The first approach is to add an extra node $v^*$ to $G$, and join it to each node in $V$; let the resulting graph be $G^*$. We ask $A$ whether $G^*$ has an independent set of size at least $k$, and return this answer. (Note that the answer will he yes or no, since $G^*$ is connected.)
Clearly if $G$ has an independent set of size at least $k$, so does $G^*$. But if $G^*$ has an independent set of size at least $k$, then since $k > 1$, $v*$ will not be in this set, and so it is also an independent set in $G$. Thus (since we’re in the case $k > 1$), $G$ has an independent set of size at least $k$ if and only if $G*$ does, and so our answer is correct. Moreover, it takes polynomial time to build $G*$ and ask call $A$ once.

My question
I think I don't understand the solution(or the question), like I don't understand why it needs to create a new $G^*$ to check whether $G^*$ has Independent set of size at least $k$. I'm thinking naively if algorithm $A$ can solve this problem, can't we just input $G$ into $A$ to get a result?
I'm learning to prove a problem is NP-complete currently, these steps looks like reduction to me. So, whenever we see a problem like given algorithm $A$ able to solve a graph problem, we always need to create a new graph $G^*$ to verify it?


texts: Why is addition in GF(2^8) the same as XOR?

texts: I get the impression it has to do with either some quirk involved with limiting to 2^8 or that I'm misunderstanding what addition can be within the context of a finite field, but I'm not quite sure why it's described as 'addition' in the literature I read but the code I see implements it with XOR.


texts: How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs

texts:
The Bellman-Ford algorithm on a graph with $n$ vertices, normally includes a loop executed $n-1$ times. Each time through the loop we iterate over the list of edges $(u,v)$ and relax $v$.  Note that we don't relax $u$ and $v$ on each iteration through the edges.

What I don't understand is that if $G$ is an undirected graph with $n$ vertices, then it is equivalent to a directed graph with $2n$ vertices.    We simply think of the edge between $u$ and $v$ as a set $\{u,v\}$ for an undirected graph, and as the ordered pair $(u,v)$ for a directed graph.

I don't understand why the Bellman-Ford algorithm needs only $n-1$ repetitions for both a directed and undirected graph.  It seems like it should take $n-1$ repetitions for directed graph, and $2n-1$ repetitions for undirected graphs or we should relax both vertices of an edge on each iteration.

Otherwise stated, why does running Bellman-Ford on a directed graph, also find the shortest paths of the undirected graphs?


texts: Deriving from a terminal word in a context free grammar

texts:
Just to make it clear.
(since my book doesn't mention anything like this)

Suppose we have a context free grammar $G=(V,T,P,S)$.
where $T=\{a,b\}$ (The other sets doesn't really matter).

Since $\Rightarrow^*$ is the reflexive transitive closure of the relation $\Rightarrow$ on the set $(V\cup T)^*$, I see no problem in writing a thing like $ab \Rightarrow^* ab$ (where $ab\in T^*$ and there are no variables on the left hand side of the arrow) since the $\Rightarrow^*$ relation is reflexive.

Now I want to ask wether it common to write a thing like $ab \Rightarrow^* ab$?

By definition I see no problem.

Thanks.


texts: Description for languages that can be solved in time(n)?

texts:
How can one describe all languages that are in
$\mathrm{TIME}(n)$?

It can't be all the regular languages only, as for example $L = \{a^n b^nw \mid w \in \Sigma^* \land n \geq 1\}$ is not regular but in $\mathrm{TIME}(n)$. Furthermore there are regular languages (like any modulo languages) that are not in $\mathrm{TIME}(n)$.

So, is there a nice description for all $L \in \mathrm{TIME}(n)$?


texts:
On Wikipedia it is Written: NP and co-NP are also thought to be unequal.[1] If so, then no NP-complete problem can be in co-NP and no co-NP-complete problem can be in NP.[2]

So Subset Sum is NP-complete (given integers find a Subset that sums to 0).

CoNp is, the set of decision problems for which a "no" answer has a deterministic polynomial-time verifier.

What does No mean here in the subset sum Example? I can trivally Test if there is a subset that Doesnt sum to Zero.


texts: How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free?

texts:
This page on Wiki states that $\{a^nb^nc^nd^n \ | \ n > 0\}$ can not be generated by a CFG. This does not make sense to me as $\{$S $\to$ ABCD, A $\to$ aA | a, B $\to$ bB | b, C $\to$ cC | c, D $\to$ Dd | d$\}$ seems to be the desired CFG. By the Pumping lemma for CFG, I understand that it is not context-free but that seems very much contradictory.
Can someone clarify this? I got this doubt while I wondering if CFGs can generate all languages.


texts:
I need a queue $[x_0, ..., x_n]$ that supports the following operations:

$\operatorname{enqueue}([x_0, ..., x_n], x) = [x_0, ..., x_n, x]$
$\operatorname{dequeue}([x_0, ..., x_n]) = [x_1, ..., x_n]$
$\operatorname{lookup}([x_0, ..., x_n], i) = x_i$
$\operatorname{update}([x_0, ..., x_n], i, y) = [x_0, ..., x_{i - 1}, y, x_{i + 1},
   ... x_n]$
$\operatorname{insert}([x_0, ..., x_n], i, y) = [x_0, ..., x_i, y, x_{i + 1}, ...,
   x_n]$
$\operatorname{delete}([x_0, ..., x_n], i) = [x_0, ..., x_{i - 1}, x_{i + 1}, ...
   x_n]$
$\operatorname{length}([x_0, ..., x_n]) = n + 1$

All operations should be in $O(\log n)$. The data structure should be atomic and persistent, i.e. it is written to a random-access data storage device, such a hard disk or flash memory. Therefore the data structure should minimize the number of seeks. I thought about using Counted B-Trees without keys and with a rollback journal. I also looked at several purely real-time functional data structures that use multiple lists (lists can be efficiently implemented with a file system with a truncate operation) but they seemed to be too complicated or not randomly accessible.

Assume that the filesystem has the following operations:

write(file, offset, x)
read(file, offset, length)
append(file, x)
truncate(file, length)

Is there any other data structure that I is more efficient or easier to implement while being as efficient?


texts: How to iterate through all values of an array?

texts:
I'm trying to implement a brute-force algorithm.

If I have one variable x, I can iterate through all its values using a for loop:

for x in {1,2,..,MAX}:
    do something with x

But what if I have an array A?  The array has length SIZE, and each element takes values in the range 1..MAX.  Thus, there are MAX^SIZE possible values of this array.  How do I iterate through all such possible values?

I'm asking for an algorithm, not an implementation on a particular language. Both MAX and SIZE are arguments.  SIZE is not fixed, so I can't just create a set of nested for-loops (the number of for-loops that would be needed isn't fixed in advance and depends on the value of SIZE).


texts:
I am working on a computability assignment, I want to define a helper predicate IsDefined by:

$IsDefinied(x,n) = \{ 1$ if $\Phi^{(1)}(x,n)$ is defined, $0$ otherwise.
Where $\Phi^{(1)}$ is the universal $L$ program, $x \in N$ and $n = \#(P)$ for some program $P$.

I'm not sure if it is computable or not. It looks a lot like the HALT predicate, which leads me to believe that it is not.

I guess what I'm really asking is, what does it mean for a function to not be defined for some input?


texts:
I come across this definition but it's not so clear for me !

  An array is partially sorted if the number of inversions is less or
  equal a constant times the array length. if array length is N then
  (number of inversions) <= c*N, with c constant.

For me c should be <= 1 is this what they meant ?

For more context : insertion sort running time is linear for partially sorted arrays.


texts: When do the gradients exist in a Reinforcement Learning setting?

texts:
I am getting properly stuck into reinforcement learning and I am currently reading the review paper by Kober et al. (2013).

And there is one constant feature that I cannot get my head around, but which is mentioned a lot, not just in this paper, but others too; namely the existence of gradients.

In section 2.2.2. they say:

  The approach is very straightforward and even applicable to policies
  that are not differentiable.

w.r.t. to finite difference gradients.

What does it mean to say that the gradients exist and indeed, how do we know that they exist? When wouldn't they exist?


texts: Prove or refute that language $L=\{a^{n}b^{m}c^{{m}\choose{n}}\}$ is regular

texts: I'm little confused with proving if this language is regular: $L=\{a^{n}b^{m}c^{{m}\choose{n}}\}$. What are $n,m$? Are they arbitrary? If yes, this language has only one word and I need to prove or refute that exists FA that accepts this word?


texts: How to solve F(n)=F(n-1)+F(n-2)+f(n) recursive function?

texts:
Like in the title the following equation:

$F(n)=F(n-1)+F(n-2)+f(n)$, with $F(0)=0, F(1)=1$
$f(n)=f(n-1)+f(n-2)$, with $f(0)=0, f(1)=1$

I don't know how to solve this. The $f(n)$ is basically just $F(n)$, but
then I have
$$F(n)=F(n-1)+F(n-2)+F(n) \Rightarrow F(n-1)+F(n-2)=0$$
and I cannot go anywhere from this.


texts: BFS vs DFS, and Timing of Marking Vertex as Visited

texts:
The Wikipedia article on Depth-Frist Search states that:

  The non-recursive implementation is similar to breadth-first search
  but differs from it in two ways:

  it uses a stack instead of a queue, and
  it delays checking whether a
  vertex has been discovered until the vertex is popped from the stack
  rather than making this check before adding the vertex.

(emphasis mine)

Conversely, the article on Breadth-First Search states that:

  This non-recursive implementation is similar to the non-recursive
  implementation of depth-first search, but differs from it in two ways:

  it uses a queue (First In First Out) instead of a stack and
  it checks whether a vertex has been discovered before enqueueing the vertex rather than delaying this check until the vertex is
  dequeued from the queue.

My two questions are:

Why is this important (i.e., why does each algorithm need to do it in a different way), and
Why does it specifically apply to the non-recursive implementation?


texts: Equivalence of two context free grammars [for the given example]

texts:
I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck:

G1:

S->e|aB|bA
B->bS|aBB
A->aS|bAA

G2:

S->e|aSb|bSa|SS

I tried to apply Arden's rule in the first grammar, to variables A and B, but I think it might be bringing me to a loop since the productions are right-recursive. I'm not really good at manipulating grammars so I don't know how to proceed in the proof.

Also, the exercise has a second question:

Show that all the words generated by G1 have even length.

I thought that if I can demonstrate that G1=G2, it is easier to conclude the proof using G2, and in fact that is something I was able to do, but I miss the fundamental equivalence so as for now I only showed the property for G2...


texts:
It seems to me that one way computer science could be divided up, is into three domains:

What is efficient for humans to represent and comprehend
What is efficient for computers to represent and process
An idealized form of how computation/problems are defined that is extremely succinct, specific, and not tied to human or computer limitations

What I am most interested in, is this third domain. I believe if a lot of effort is invested there, it will drive the advancement of the other two domains.

Towards that end, I am interested in the development of an "ultimate" virtual machine. Something with a gratuitously minimal and impoverished grammar, and an extremely advanced type system.

I am wondering if anything like this exists. I am also trying to develop something like this, with the idea that it doesn't.


texts:
We define an onto function from $[n] \times [n]$ to $[n-2] \cup \{0\}$ as follows, where $[n] = \{1,2,3,\ldots ,n\}$,

$$f : [n] \times [n] \rightarrow [n-2] \cup \{0\}.$$

1) $f(x,x) = 0$.

2) $f(x,y) = f(y,x) > 0$, for $y ≠ x$.

3) $f(x,y) \leq \max\{f(x,z),f(z,y)\}$ for all $x,y,z$ belonging to $[n]$.

How many such functions are possible for a given $n$? I have tried my best but I am not able to get any close to the solution! One may even see it as a undirected simple graph with n vertices, f(x,y) representing the edge weights. Any help is appreciated!

EDIT: i have been able to find that there are no such functions for n<3.

for n=3 we have one such function, for n=4, 13 are possible.


texts:
Lets say that we have the  language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ }
What is the way that i should  follow to prove
that the language is not regular?

Assume that the language is regular.
So,there is a string $w\in L$  such that $w = xyz$ , $|xy|\leq n, y\neqε  $, n is the pumping length

Lets say that the string that i choose( w string)  is $w = a^nb^mc^{m+n}$
Is this choice correct ?
Can someone explain me the best choice of $y$ ?
Should be $y = a^{n-r} $  and $x = a^n $ ?  Because  of $|xy|\leq n$ ?
Thank you and sorry for my english.


texts: Why we treat sentence letter $Q$ as conclusion in one form and premise in other?

texts:
Sorry for asking such a dumb question.

I am CS student and I am trying to understand the basic tenets of Logic. I am new to the subject and I am lost understanding Implication.

In formal logic, $(P\rightarrow Q)$, The sentence letter $P$ is premise and $Q$ is conclusion, right?

Now, we know that $(P\rightarrow Q)$ is equivalent to $-(P\wedge -Q)$ i.e. It is not the case that $P$ and not $Q$. Here, $Q$ acts as premise, right?

So, why we treat sentence letter $Q$ as conclusion in form and premise in other?


texts: Addition modulo 2 notation (Quantum Computing)

texts:
I am studying Quantum Computing using the book Quantum Computation and Quantum Information of Michael Nielsen and Isaac Chuang. I am confused by the meaning of the $\oplus$ (addition modulo 2) symbol in the notation.

Given a starting state $|\psi\rangle|\phi\rangle$ and a unitary gate $U$ such that $U|\psi\rangle|\phi\rangle = |\psi\rangle|\phi \oplus f(\psi)\rangle$. What does in this case $\oplus$ mean, in the general case for $|f(\psi)\rangle = \alpha_0 |0\rangle + \alpha_1|1\rangle$ and $|\phi\rangle = \beta_1 |0\rangle + \beta_2 |1\rangle$?


texts: Soon to be computer science major with some questions

texts: I'm going to apologize in advance for this wall of text, and if you're looking for me to ask technical questions about the field, that isn't what this post is going to be. So this Fall I'm going to be starting my degree for computer science. To be honest I'm not sure what to expect. I've done research and some people say that the degree will be far more math heavy than it needs to be for a lot of fields, while others disagree. The problem, besides there not being a very helpful answer, is that none of these people seem to even be in the field. What will I be learning besides programming? My goal is to actually be a video game programmer, but I'm getting this degree because I know that could change, and I also like the idea of a degree that isn't quite that niche. So is that a wise choice? I began teaching myself to program some with online resources and such, and have focused mainly on Python as a starting point. However, when I see some of the things people on this site and other places, I have no clue what's going on half the time. Is this a bad sign, or should I just quit stressing? Any advice is greatly appreciated.


texts: IO efficiency of a complete binary search tree

texts:
I was given this as a homework exercise, yet I don't know whether my solution is sound:

Given a complete binary search tree where blocks are formed in order of the value of the nodes. What would the amount of IOs be to reach any leaf from the root?

I think I can define the amount of IOs recursively as follows:

search(A) = search(A/2)+1 if n>B/2
          = 0 otherwise

Where n is the size of A and B is the block size.
Since I think storing in order would always store a complete subtree of size B/2 in the same block.
This would then give log2(2n/B) IO operations for any root to leaf traversal.

Firstly, is that a correct bound? Secondly, is the storing of a complete B/2 sized subtree guaranteed with block size B?

Note that the bound is for amount of IO operations, not time complexity.


texts:
When I went to London, I wondered how to visit all the London Underground stations as fast as possible.

Given

a randomly-chosen start station,
timetable of train arriving & departing of every station,
the time it takes to change from one to another line.

Assuming that there is no Tube strike on that day, and trains run on time, what is the best route to visit all the London Tube stations? (By visiting, just passing the station while being on the train counts.)

I've tried breaking the problem down to a smaller size and computing all possible routes, but that'd take ages to run with all 270 stations.

So, could you guys give me some ideas how to do this better? Or if this something similar to this problem, could you please show me those?

What I've tried:

I've Googled, and I found something like optimum road trips, but it doesn't work with train stations that have interchanges.
Took a look at A*, Dijkstra's but they give a tree as an answer which ignores loops.

Thanks!


texts:
I am designing an algorithm that solves a linear system using the QR factorization, and the matrices I am dealing with are sparse and very large ($6000 \times 6000$). In order to improve the efficiency of the algorithm, I am trying to exploit the sparsity of the matrix by finding its bandwidth, but I have to run through the matrix a lot of times to find it, and it is taking too long.

The main idea I am using to find the bandwidth is:

for each row, find the start(row) and end(row): these are the intervals in which the elements are different of $0$;
to find start(row): iterate from the beginning of the row until the element is not $0$;
to find end(row): iterate from the end of the row until the element is not $0$;

The problem is that I am running through many unnecessary $0$'s, but I can not figure out how to avoid this and guarantee a solid result. Thanks.


texts:
With reference to the Heuristics section of Classical planning in Artificial Intelligence: A Modern Approach by Russell and Norvig, there is a question: consider
an air cargo problem with 10 airports, 50 planes, and 200 pieces of cargo. Each plane can
be at one of 10 airports and each package can be either in one of the planes or unloaded at
one of the airports. So there are 5010 × 20050+10 ≈ 10155 states.

I think it should be 1050 + (50+10)200 (each of the 50 planes can be in any of 10 places; each of the 200 packages can be in any of the 50 planes or unloaded at any of the 10 airports).

What is the actual number of states?


texts: Serializability and the Lost Update Problem

texts:
Serializability is the strongest consistency level with regard to the execution of two concurrent transactions T1 and T2. That is, if T1 and T2 independently change the application between consistent states, and a concurrent execution of T1 and T2 is equivalent to a serial execution of T1 and T2, then that concurrent execution results in a consistent state, after committing both transactions.

For example, the following concurrent execution (time advances to the right)

T1: w(a=1)         w(c=4)
T2:     w(a=2)w(b=3)

where W(x=v) sets (i.e., writes) x to the value v, is equivalent to the serial execution T1;T2, thus it is serializable and both transactions are committed.

However, it is clear that T2's write of a causes T1's write of a to be lost, i.e., we have a lost update despite serializability.

That is, serializability ensures consistent states in face of concurrency, though it does not prevent lost updates, which may have serious consequences (for example, imagine that T1 writes the correct delivery address of a VIP customer, and T2 writes the wrong address, T1 and T2 are run concurrently by different operators, who do not notice the mistake).

Is my statement correct about serializability and lost updates?

If it is correct then the table in "Isolation levels, read phenomena, and locks" in this wiki page can only be wrong with regard to serializability and lost updates.

If so, what other stronger consistency level ensures that there are no lost updates?

Thanks


texts: Is it assumed that lower bounds on the size of monotone circuits apply to general Boolean circuits too?

texts:
A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:

fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT nodes
fan-in=0 for the IN nodes
fan-out=0 to exactly one node (the OUT node)
Unbounded fan-out to the rest of the nodes (but the OUT node)

A monotone circuit is a Boolean circuit with 0 vertices labeled as "NOT".

The size of a circuit is the number of "gates" (vertices with labels "AND", "OR" or "NOT") it contains.

We know many lower bounds on the size of monotone circuits, that we do not know how to prove on a general Boolean circuit (such as this one on the Clique problem).

My question is: do we assume that lower bounds proven on monotone circuits apply also for equivalent general Boolean circuits (since they compute monotone function), and we just don't know how to prove it; or we assume\ know that these lower bounds do not apply to equivalent general Boolean circuits?

In the latter case, could you supply me with an example of a monotone function computed by both a monotone circuit and a general Boolean circuit, whilst the size of the monotone circuit is gretater than the general Boolean circuit? (I have been stuck on this for hours, seeking for such an example, so I believe that there is no such an example..)


texts: Decidability of $E_{TM}$ and $A_{TM}$ for "erasing" Turing machines

texts:
Why is the $A_{ETM}$ for a variant of a Turing machine (an erasing Turing machine), where changing a tape symbol to a nonblank symbol is prohibited, decidable? Why does the following diagonalization argument not work:

  Assume $A_{ETM}$ is decidable, and $R$ decides $A_{ETM}$. Then, $R$
  accepts $\langle M, w \rangle$ when ETM $M$ accepts $w$. Let $D$ be
  an ETM that accepts exactly when $M$ does not accept $w$. Then, $D$
  rejects $\langle D \rangle$ when $D$ accepts $\langle D \rangle$, a
  contradiction.

Why does this not work?

Alternatively, if $A_{ETM}$ is decidable, why is $E_{ETM}$  undecidable? The conventional contradiction argument would not work in that case, and I don't know how to reduce it any other way.

Thanks in advance!


texts: Formula for finding number of colors to color a map such that no two adjacent counties have the same color

texts: Is there a formula for determining the minimum number of colors to color a map with n counties such that no adjacent county have the same color?


texts: How about boolean formula that is satisfied on every reject path and falsified on every accept path of non deterministic Turing machine?

texts:
Cook-Levin reduction is both deterministic polynomial time and parsimonious and that's mean that from every non deterministic Turing machine $M$ and string $w$ it is possible in polynomial time deterministically to create the boolean formula $\alpha_{M,w}$ so that every satisfying assignment of $\alpha_{M,w}$ is accepting path/route of $M$ with input $w$ and every falsifying assignment of $\alpha_{M,w}$ is rejecting path/route of $M$ with input $w$, and also $\alpha_{M,w}$ is in conjunctive normal form.

Therefore $\alpha_{M,w}$ is satisfiable if and only if $M$ with input $w$ has accept path/route and $\alpha_{M,w}$ is falsifiable if and only if $M$ with input $w$ has reject path/route.

I think that it is also possible from every non deterministic Turing machine $M$ and string $w$ it is also possible in polynomial time deterministically to create the boolean formula $\beta_{M,w}$ so that every satisfying assignment of $\beta_{M,w}$ is rejecting path/route of $M$ with input $w$ and every falsifying assignment of $\beta_{M,w}$ is accepting path/route of $M$ with input $w$ and $\beta_{M,w}$ will be also in conjunctive normal form.

Therefore $\beta_{M,w}$ is satisfiable if and only if $M$ with input $w$ has reject path/route and $\beta_{M,w}$ is falsifiable if and only if $M$ with input $w$ has accept path/route.

Am I right?


texts: Counting permutations whose elements are not exactly their index ± M

texts:
I was recently asked this problem in an algorithmic interview and failed to solve it.

Given two values N and M, you have to count the number of permutations of length N (using numbers from 1 to N) such that the absolute difference between any number in the permutation and its position in the permutation is not equal to M.
Example - If N=3 and M=1 then, 1 2 3 and 3 2 1 are valid permutations but 1 3 2 is invalid as the number 3 is at position 2 and their difference is = M.

I tried NxM Dynamic programming but failed to form a recurrence that doesn't count repetitions.


texts:
I am having trouble understanding the following problem and Q learning in general.

What I know so far about Q learning is that Q-learning is a model free method, i.e., it doesn’t need to learn P(s’|s,a). Thus it can compare the expected utility of the available actions without the model of the environment.It will also eventually find a policy that is the maximum achievable. However, I am not able to use this knowledge to do this problem. The answer is given in red.

If we are to look at time t = 1, then the equation becomes the following: $$ Q_{t+1}(s,a)=(1-1/2)(1)+1/2[R(s,a,s^{'})+(1)  maxQ(s^{'},a^{'})] $$
How do I proceed from here?


texts: An algorithm to check if two DFA are disjoint

texts: What is the algorithm to check if two DFA are disjoint? I want to know if there exist any string accepted by both automata.


texts: Is the set of all possible finite alphabets uncountable?

texts: In my opinion it is uncountable since we can think every natural number as a member of one alphabet like $\quad0\in\sum_0 ,1\in \sum_1, ... \quad$ And there are also other symbols than natural numbers in alphabets. So there is no possible 1:1 and onto mapping from set of all alphabets to natural numbers. Thus they cannot be enumerated which means they are uncountable. Is there anything wrong with my approach?


texts: It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" multi head Turing machine?


texts: Designing a neural network with LSTM and feedforward NN combination

texts:
Currently, I'm designing a neural network that works with reinforcement learning. In summary, the agent takes in information about itself and nearby agents and, in conjunction with global world information, makes a decision.
I'm currently thinking of implementing this as a LSTM to take in information about itself and a variable number of nearby agents and a feedforward neural network to combine the information from the LSTM output and global world information to produce an action.
Would this approach be sufficient to produce meaningful results? I thought that another approach would be to take in the global world information and each agent at each LSTM cell, though it may use much more resources (resources during forward propagation are a main concern with this project). Also, if the second approach is used, how would I be able to link the inputs to outputs if they had different shapes (attempting to learn without a library)? How would I be able to map an input with shape [1, x, 6] to [1, 1, 4] or [1, 4].


texts: Finite State Machine that only accepts strings with equal number of 0's and 1's

texts:
Question: Suppose you have a finite state machine that accepts only strings with an equal number of zeros and ones. Show that you can then construct a finite state machine that accepts only strings of the form 0^n 1^n, i.e., an arbitrary finite number of zeros followed by the same number of ones.

My attempt at a response:

A Finite State Machine that accepts strings with an equal number of 0’s and 1’s (e.g. n zeros and n one's, where n is some arbitrary finite number), must have a counter that keeps track of the total number of 0's and 1's. This is impossible, since by definition a FSM has no counter or memory. But suppose this were possible. Then it’d be possible to construct another FSM that keeps track of the count of consecutive 0's in the prefix of a given string, and ensure that number equals the count of consecutive 1's in the suffix of that string.

I feel like there is more to the answer than this, but I don't really know what else can be said. I know that no FSM can be constructed to accept only strings in the format 0^n 1^n where n could be any arbitrary nonnegative integer, but that it is possible to do for any fixed, specific value of n. For example, it's possible to build FSM to accept only strings that contain three 0's, followed by three 1's. But I don't know whether this detail is relevant at all. Thanks for any help.


texts: Reference selection for rating assignment based on pair comparison

texts:
Background: a set of 300 images are prepared, randomly pair compared with 60 other images, assigned a rating (from 1-star to 5-star) based on the pair comparison score (+1 if wins a pair comparison and +0 if loses a pair comparison), the score range for the rating assignment is 0-11 for 1-star, 12-23 for 2-star, 24-36 for 3-star, 37-47 for 4-star, and 48-60 for 5-star
Objective: want to rate 1000 more images based on the 300 rated images, again through pair comparison, but with some of the 300 rated images instead of between themselves
Problem:

what images should be selected from the 300 rated images for the pair comparison, and how many?
how should the score function be defined for the pair comparison with the selected image?

Could somebody help this experiment design?  Thank you very much for you attention and help!


texts: If the difference between two oracles is negligible, is the difference between a PPT algorithm with these two oracles also negligible?

texts:
We say a negligible function is a function $\epsilon(n):\mathbb{N}\rightarrow \mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $n > N_c$,
$$\epsilon(n)<\frac{1}{n^c}$$
(From wikipedia)

Assume that two probabilistic polynomial-time algorithms $O_{1},O_{2}$ satisfy that
$$
\Sigma_{y \in \{\, 0,1 \,\}}\left\vert \mathrm{Pr}\left[ O_{1}(x) = y \right] - \mathrm{Pr}\left[ O_{2}(x) = y \right] \right\vert \leq \epsilon_{1}(n)
$$
for all $x$, where $\left\vert x \right\vert = n$ and $\epsilon_{1}$ is negligible.

Let $A$ be a probabilistic polynomial-time algorithm. Can we get that
$$
\Sigma_{y \in \{\, 0,1 \,\}}\left\vert \mathrm{Pr}\left[ A^{O_{1}}(x) = y \right] - \mathrm{Pr}\left[ A^{O_{2}}(x) = y \right] \right\vert \leq \epsilon_{2}(n)
$$
for all $x$? Where $\left\vert x \right\vert = n$ and $\epsilon_{2}$ is negligible.


texts: Sampling random graphs with Eulerian paths

texts:
How to generate random graphs with eulerian Paths?
Its well known that there is a eulerian path if the number of nodes with odd degree is exactly 2 or zero. I'm interested in an algorithm to make uniformly distributed random graphs with such paths.
Until know I've developed this simple algorithm:
Given the number of nodes in the desired graph:

Create a chain, by definition it is a eulerian path. With exactly 2 odd degree nodes.
Take one of the odd nodes and make an edge with one of the even nodes (Both choose randomly). If multiple-edges between a pair of nodes is not allowed make an edge iff previously there is not an edge.
Repeat step 2 until there is a maximum number of edges or an edge cannot be made.

This algorithms works for eulerian paths, but I think is highly biased and the graphs that it generates are just a sub set of all the eulerian paths that can be made (If not, how can be proved the contrary?).

In the other hand the algorithm above doesn't generate any eulerian tour.
Is there a better approach to solve this task?


texts:
Given $s$ as a string over some alphabet, what is the best known algorithm to compute a corresponding deterministic finite-state automaton (DFA) that accepts any string that contains $s$?

I am mostly interested of the lowest time complexity so if you tell me what is the best known complexity in O notation to build an automaton for a string that would be just as good.


texts:
First post here so hope I'm not missing too many guidelines.
I've had this idea for a few weeks now and I can't myself see where I'm going wrong with it, hope it makes some sense to you and thanks in advance for the help.
Here we go:
Assuming we could solve a NP-complete problem in logn SPACE, e.g. TSP. Then by reachability we could show that $P = NP$.
The machine will keep track of this information:

$\log n$ nodes for a path walked, call this memory pathMem
$\log n$ nodes for a reconstructed path walked, call this memory pathMemTemp
$\log n$ numbers indicating the chosen path, call this chosenPathNums
$\log n$ nodes for ending nodes of each path, call this endMem
some representation of the cost of the walk.

Step 1: Walk $\log n$ steps, note down the $\log n$ walked nodes in pathMem
Step 2: Check that there are no duplicates in pathMem (that means that you've walked $\log n$ unique nodes).
Step 3: Use a modified version of Savitch that counts the number of possible paths between start node and last node in pathMem. This should be at most $(\log(n)!)$ paths, represented in that number using binary and we get $O(log(log(n)!))$
Step 4: Find which of these paths that is in pathMem. Save that number in chosenPathNums at pos 1.
This gives us a deterministic way of refinding a specific path.
Step 5: Move last node in pathMem to endMem pos 1, clear pathMem.
Step 6: Walk $\log n$ steps from node at endMem pos 1, note down walked nodes in pathMem.
Step 7: Check that there are no duplicates in pathMem (that means that you've walked $\log n$ unique nodes).
Step 8: Reconstruct path that was taken from start node to node at endMem pos 1 by using Savitch's and the chosenPathNum, save it in pathMemTemp.
Step 9: Check that pathMem and pathMemTemp has no overlap. If there is overlap, halt with no, otherwise continue.
Step 10: Find the path number that is in pathMem. Save that number in chosenPathNums at pos 2.
Step 11: Move last node in pathMem to endMem pos 2, clear pathMem.
Step 12: Rinse and repeat, now checking pathMem vs start->(endMem pos 1) and then (endMem pos 1)->(endMem pos 2) etc., until you've walked $n$ nodes, thus having $\log n$ nodes in endMem and $\log n$ numbers in chosenPathNums.
Step 13: Calculate distance walked, check if less or equal to threshold.
This algorithm could be turned deterministic by looping every possible $\log n$ walk that is found from a node to another node.


texts: How can this grammar parse such an input?

texts:
I've an example which I simply don't get at all.

  Implement an attributed grammar that checks that either

  the word ends in $b$ or
  each prefix of the word contains at least as many $b$s as $a$s

  E.g. the word $bbbbaabaabaa$ is allowed but $abbabaabba$ is not. (I know - what an example!)

However, the grammar looks like this:

  \begin{align}
V &\rightarrow S \\
S_0 &\rightarrow S_1 a \\
S_0 &\rightarrow S_1 b \\
S &\rightarrow \epsilon
\end{align}

and I am allowed to extend it to an attributed grammar. But I can't imagine how this can even be parsed from those rules since removing element by element from e.g. $abbab$ will never end up such that a rule can be applied.

What am I missing here?


texts: How many maximum height AVL trees given height?

texts: I am having some trouble finding a recursive formula for finding the number of maximum height AVL trees of height h. Height 0 has 1, height 1 has 2, height 2 has 4, height 3 has 8, etc. is that correct?


texts: Can't figure out how to make a grammar LL(1)

texts:
Let's say I start with:

$A \rightarrow Ba$

$B \rightarrow dab | cBb | Acb$

Now I want to make this grammar LL(1), so I need to get rid of the left recursion. I'll work with $B \rightarrow Acb$.

I'll replace where $A$ occurs with its production:

$B \rightarrow dab|cBb|Bacb$

And that gives me a direct left recursion, which I rewrite as:

$B \rightarrow dabB' | cBbB'$

$B' \rightarrow acbB' | \epsilon$

At this point this seems like this should be LL(1), so I'm checking:
$FIRST$ sets: For $A: \{d,c\}$, $B: \{d,c\}$ and $B': \{\epsilon, a\}$.

$FOLLOW$ sets: $A: \{eof\}$, $B: \{a,b\}$ and $B': \{a,b\}$.

Now I'd like to check $FIRST^+$, but if I do $FIRST^+(B' \rightarrow acbB') = \{a\}$ and then $FIRST^+(B' \rightarrow \epsilon) = \{\epsilon, a, b\}$ which does NOT have a non-empty intersection.

Does it make sense to look at $FIRST^+$ in terms of each production that has the same left hand side? Or, have I made a mistake in calculating $FIRST$ or $FOLLOW$ sets to begin with? Is there an issue with the rule $B \rightarrow cBb$ (not left recursive exactly but does have the $B$ nestled inside).


texts:
Question:

  Is true that $L_1 = \{01^*0\}$ is $m$-complete in the class of
  decidable languages?

  $L_1$ is defined as:

  $$L_1 = \{01^*0\} := \{01^n0: n \in \mathbb{N}\}$$

Definition of a $m$-complete language:

  A language $L^*$ is $m$-complete in the class of decidable language,
  if for any decidable language $L$ we have that $L \leq_m L^*$ (that
  is, $L$ reduces to $L^*$).

I'm really new in this realm, so I'm quite lost about how to tackle this exercise.

I'm not sure if my approach is correct but I was trying to prove that the statement is not true by using a reduction from the Busy Beaver Function to $L_1$ (then, from this reduction and from $L_1$ being decidable we would have that BB problem is decidable, which is not possible).

Let $A$ be the algorithm deciding $L_1$ and $w \in L_1$ a word with $|w| = m$ ones. Now when running $A$ on $w \in L_1$ we keep track of the number of steps $t$ it made just before halting. Since $t = m|\Gamma|^m|Q|$, where $\Gamma$ is the set of tape symbols and $Q$ is the set of states. From here we can find the number $|Q|$ of states required for printing $|w| = m$ ones...

I stopped here because I feel there is already something wrong.

First, even is we find that number $|Q|$ for which $A$ performed $t$ steps before $A(w) = \text{Accept}$, that does not necessarily mean that $|w| = m$ ones could have been achieved with a TM with lesser number of states. Second, ''knowing'' the numbers of ones I'm determining the numbers of states and not the other way around, which is as $BB$ is defined.

Another alternative I was exploring was, on input $w$, to run all TM's $T_1, ... T_n$, that return $|w| = m$ ones. Then we record the input $w$ and the description of the machine $T_i,\ (i \in [1,n])$, that had the least number of states. If we do this $\forall w \in L_1$, we end up with a UTM $T'$, such that:

$$T' = \{ \langle T^*, w\rangle: |Q|_{T^*} = \mathrm{min}(|Q|_{T_1}, ..., |Q|_{T_n}\ \text{}\}$$

Then clearly $T'$ decides $L_1$ (just have to run it on input $w \in L_1$) and at the same time allows us to compute $BB(n)$ for a fixed $n \in \mathbb{N}$ (since $n$ is encoded in the description of $T^*$).

Probably here there are some flaws in my reasoning, but in this case, do I have to wait that, on input $w$, all those TM's reach a halt or can I assume that the first machine that halted is the one with the least number of states?

I'd appreciate any help.


texts: How do I compute this non terminal positions evaluation, for tic-tac-toe?

texts:
Looking at this solution on page 3 but having trouble understanding the evaluation function specifically.

  For non terminal positions, we use a linear evaluation function
  defined as

  Eval (s) = 3[X2(s)]+X1(s)−(3[O2(s)]+O1(s))

  We define X n ( s ) as the number of rows, columns, and diagonals in
  state s with exactly n X’s and no O’s, and similarly define O n ( s )

Looking at this state 's' for example (these problems accounts for symmetry):

|X| | |
| |O| |
| | | |

It shows an evaluation of -1

However, got 0:

X2(s) = 0 because there are no rows or columns with 2 X's.
X1(s) = 2 because the top row and left column both have 1 X (but the diagonal has an O)

O2(s) = 0 because there are no rows or columns with 2 O's.
O1(s) = 2 because the middle row and middle column both have 1 O (but the diagonal has an X)

Plugging in:

0+2 - (0+2) = 0

So, I thought I am missing symmetry but I just get a bigger scale that still = 0's.

I must be overlooking something simple but not sure.

Any help is appreciated.


texts:
I am writing a paper on the invariance thesis introduced by Cees F. Slot and Peter van Emde Boas as;

  'Reasonable' machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.

The paper I am writing is in Croatian where I cannot find a properly convenient word like "overhead". Also, I am unable to find a strict Computer Science definition for the term.

Specifically, I have $Time(M)$ as the cost of reducing the $\lambda$-term $M$ to its normal form and a Turing machine able to simulate this reduction in $O((Time(M))^4)$. Therefore, I would like to say  "this TM can simulate $\lambda$-calculus with polynomial-time [overhead]" concisely as it is in English.

I would appreciate any suggestion in the form of literature references for the definition, advice on how to best define it myself or even synonyms of the word.


texts: Can you explain in step-by-step basis of how motion capture system work? Especially the part, that enables the 3D models to mimic the movement of the actor.


texts: Is there a relationship between time taken to reduce A to B and the time taken to solve B?

texts:
Example: If it takes $O(n^2)$ to solve A and it takes $O(n^3)$ to reduce A to B.
So, it is certain that that B is at least as hard as A and takes at least $O(n^2)$ time to be solved.

Can we say something similar for reduction time and B such as B takes at least $O(n^3)$ time to be solved?

My thoughts: I think it has no relationship with the time complexity of B. However the reduction should be at most of polynomial time complexity otherwise, the reduction may not be possible practically. I do not have a proof for this as this point so, I'm unsure if this is correct. Any help is appreciated. Thank you.


texts: Time complexity of transforming one string to another

texts:
Here is the problem:

Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. If it does produce $t$, output the length of of the shortest production sequence, otherwise, output $-1$.

Example: $D$ = [bat, cot, dog, dag, dot, cat], $s$ = cat, $t$ = dog, the shortest production sequence would be [cat, cot, dot, dog], giving us an output of four.

Here is the algorithm (Breadth First Search):

private static class StringWithDistance {
    public String candidateString;
    public Integer distance;

    public StringWithDistance(String candidateString, Integer distance) {
    this.candateString = candidateString;
    this.distance = distance;
    }
}

public static int transformString(Set<String> D, String s, String t) {
    Set<String> visited = new HashSet<String>(D);
    Queue<StringWithDistance> q = new ArrayDequeu<>();
    visited.remove(s) // mark as visited by erasing it
    q.add(new StringWithDistance(s, 0);

    stringWithDistance f;
    while ((f = q.poll()) != null) {
        if (f.candidateString.equals(t)) {
            return f.distance;
        }

        for (int i = 0; i < str.length(); ++i) {
            String strStart = i == 0 ? "" : str.substring(0, i);
            String strEnd = i + 1 < str.length() ? str.substring(i + 1) : "";
            for (int c = 0; c < 26; ++c) {
               String modStr = strStart + (char)('a' + c) + strEnd;
               if (visited.contains(modStr)) {
                   visited.remove(modStr);
                   q.add(new StringWithDistance(f, f.distance + 1);
               }
            }
        }
    }

I'm having a hard time understanding why this algorithm is $O(n^2)$. I know that the time complexity of processing the vertices/words is $O(n)$, but based on the text I'm reading, processing the edges in the worst case would be $O(n^2)$, so we would have $O(n + n^2)$, giving us $O(n^2)$.

I just can't see how that is taking place. The second loop is a constant (right?), it doesn't change with the size of $n$, so I don't think that is a part of the calculation for the run time.

Any help would be greatly appreciated.


texts:
Is there an algorithm that fills the area outside the edges?

e.g.:

From this

to this


texts: Using diagonal argument to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension

texts:
Hello everyone just like the title says I want to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension such that if we had a function $BIG(x)$ that is both total and agrees with $H(x)$ whenever $H(x)$ is defined, then $BIG(x)$ is not computable. This is a homework question so I don't want a full solution just some help!

$\bf{NOTE}:$ The predicate $T(y,x,z)$ means that it holds iff program $y$ takes an input $x$ (could be $n$-ary) and has a computational history z! This is supposed to be the Kleene T predicate basically.

The function $H(x)$ I believe returns the smallest computational history $y$ such that a program $\{x\}(x)$ (program takes input of its own configuration and runs) runs and halts, since $\mu y R(x,y)$ means the smallest $y$ such that $R(x,y)$ holds. Maybe I am not quite clear what it means for $BIG$ to agree with $H(x)$ or what it's own input. I think I need to create a diagonal function that uses $BIG$ if $BIG$ was computable and show that if I had some program $e$ then it must agree with $BIG$ but based on my definition of that diagonal function it isn't. If you are reading this you might see the mess of my thinking, any help would be greatly appreciated!


texts: Is there a universal learning rate for NeuralNetworks?

texts:
I'm currently creating a NeuralNetwork with backpropagation/gradient descent. There is this hyperparameter introduced called "learning rate" (η). Which has to be chosen to guarantee not overshooting the minimum of the cost function when doing gradient descent. But you also do not want to slow down learning unnecessarily. It's a tradeoff. I've found that for too small or too big η the NeuralNetwork doesn't learn at all.

I've successfully trained the NN on the sin-function with η = 0.1. But for other functions like any linear combination of the inputs, a different η is required (more like η = 0.001). For the quadratic function, I still haven't been able to make the NN converge at all, maybe I just haven't found the right hyperparameters.

My question now is:
Is there any way I can find a η that works for any function, so I don't have to try and search for it manually.

Thanks in advance,
Luis Wirth.


texts: How does 0 have two values in one's complement?

texts: It is said that in 2's complement 0 has only one value, while in 1's complement both +0 and -0 have separate values. What are they?


texts: Recognizing Regular Languages in Layman terms

texts:
I understand that regular languages are languages which can be computed by Finite Automata however i am having some trouble understanding how one can identify a regular from non-regular.

I know that 0*1* is regular because the machine just needs to make sure the 0s and 1s are in order

I know that 0^n 1^nis non regular because the machine needs to keep count to make sure there is an equal number of 0s and 1s

But why is (01)^n considered regular? Doesn't the machine have to keep track to make sure that there are n amount of 01?

How about {0^m 1^n | n>m}?

What is the general rule for quickly figuring out if something is regular or not in layman terms?


texts:
im looking for efficient algorithm to expand $(x+a)^n$ without using binomial theorem

is the repeating square method efficient for that problem with the help of binary representation of n ?


texts: Dynamic programming to find the least possible balance of a full binary tree

texts:
I am given $n$ positive integers $x_1,x_2,\cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an internal node $v$ is defined as the sum of weights of the leaves in the subtree rooted at $v$. The balance of an internal node is defined as the larger ratios of the weights of its two children. The balance of a tree is the maximum of the balances of its internal nodes.

I need to find the least possible balance of any full binary tree with $x_1,x_2,\cdots,x_n$ as the weights of its leaves. I don't need to output the tree, just the value.

I am having trouble finding the sub-problems. I have tried doing some examples, say the input is: $(5, 4, 3, 4, 4)$. I found the least possible balance of this to be $1.5$ by drawing all the possible trees. The tree that I ended up with is below and I put the balance beside each internal node:

For the example input, a smaller sub-problem would obviously be $(4,3,4,4)$, but I don't see how knowing the least possible balance of that helps me find the least possible balance of the tree with leaves $(5, 4, 3, 4, 4)$. I tried finding the balance for $(4,3,4,4)$ which came to be $1.33$. The tree I ended up with is:

I am looking for some hints as to what the sub-problems might be.


texts: Less used data (1 byte) in memory address holding 4 bytes

texts:
I need to store two distinct variables of 1 byte size in memory.

My memory system stores 4 bytes at one address; therefore, you cannot address byte 3 directly, and you have to logically access it after all 4 bytes are fetched of that address (correct me if I'm wrong please).

So, if I assign the following two variables: char var1 = "a" and char var2 = "b",

Will my system store them in memory at two different addresses?

Will 3 bytes in each of those addresses be useless (i.e., will the two variables occupy 8 bytes of memory)?


texts:
Looking at the Independent Set problem and its complement, I want to show that IS is poly-time reducible to its complement, however I am struggling on coming up with the reduction function.

I will define its complement for further clarity, does every subset such that its size is at least $k$ in $V$ contain at least one edge between its vertices? My intuition is below.
$$f(G, k) = (G, i-k),$$
where $i = |V|$?


texts:
A set of n points and m line segments is given. We are given two disks of radius r. We need to place the disks in such a manner so that maximum number of points are covered. A disk covers a point only if its center and the point can be directly connected, i.e, the line joining the center of the disk and a point should not be intersected by any of the m line segments. Any ideas to solve this problem?

An idea to solving this problem can be to consider every two points in the point set. For every pair of points there can be two possible disks of radius r that touch both points. For all such combinations of disks the 2 disks covering the maximum number of points can be the answer. But will this give the right and optimal solution? For example taking the disk which covers the maximum points and then the disk which covers the second maximum points might not be the optimal answer. How to find the two disks covering the maximum points?


texts: Depth of binary tree with few single children

texts:
The node of a binary tree is called a single child if it has a parent but does not have a sibling. The root is by definition not considered a single child.

Let $T$ be a binary tree of size $n$, and let $k$ be the number of vertices in $T$ that are single children.
Is it true that if $\frac{k}{n}\leq \frac{1}{2}$
then the height of $T$ is $O(\log n)$?


texts: Is maximising (or minimising) something enough to say that I am solving a decision problem?

texts:
We know that every optimisation problem has an equivalent decision problem.

So say I keep going up a mountain (I.e. I am maximising my altitude) following a certain number of finite steps (similarly to a TM). Is that enough to assert that I am solving a decision problem?

If yes which one?


texts: How do you prove two languages are equivalent using the definition of acceptance?

texts:
I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$
where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ and

$\delta'(q,a) =
      \begin{cases}
        \delta (q,a)  & \text{if }q\in Q\\
        \delta (q_0,a) & \text{if }q= q_f.
      \end{cases}$

I'm assuming I need to use induction but I'm not sure how to go about it


texts: Quicksort vs. insertion sort on linked list: performance

texts:
I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm.
Does anyone have any idea why this is?
Insertion sort has a complexity of $\Theta(n^2)$ and quicksort $O(n\log n)$ so therefore quicksort should be faster. I tried for random input size and it shows me the contrary. Strange...

Here the code in Java:

public static LinkedList qSort(LinkedList list) {

    LinkedList x, y;
    Node currentNode;
    int size = list.getSize();

    //Create new lists x smaller equal and y greater
    x = new LinkedList();
    y = new LinkedList();

    if (size <= 1)
        return list;
    else {

        Node pivot = getPivot(list);
        // System.out.println("Pivot: " + pivot.value);
        //We start from the head
        currentNode = list.head;

        for (int i = 0; i <= size - 1; i++) {
            //Check that the currentNode is not our pivot
            if (currentNode != pivot) {
                //Nodes with values smaller equal than the pivot goes in x
                if (currentNode.value <= pivot.value) {
                    {
                        x.addNode(currentNode.value);
                        // System.out.print("Elements in x:");
                        // x.printList();
                    }

                }
                //Nodes with values greater than the pivot goes in y
                else if (currentNode.value > pivot.value) {
                    if (currentNode != pivot) {
                        y.addNode(currentNode.value);
                        // System.out.print("Elements in y:");
                        // y.printList();
                    }
                }
            }
            //Set the pointer to the next node
            currentNode = currentNode.next;
        }

        //Recursive calls and concatenation of the Lists and pivot
        return concatenateList(qSort(x), pivot, qSort(y));

    }
}


texts: Particularly Tricky Recurrence Relation (Master's Theorem)

texts:
Master's theorem is shown below,

The recursive function to be solved is shown below,

I understand that a refers to the number of recursive calls in this function (3 in this case). b refers to what the input size is being divided by in each recursive call. Which I believe should be 4.
d refers to the overhead of each recursive call, which should be 1.

So we have:

a = 3
b = 4...?
d = 1

The problem is, b apparently doesn't equal 4.

Now the actual answer shows that the answer is:

Which seems incorrect, since given the Master's Theorem, I don't see how n is being subtracted by a constant.

Thank you for your help.


texts: What do we know about the reciprocal busy beaver series?

texts:
[Cross-posted from Math SE - apologies if this is not appropriate.]

I just read these excellent lecture notes by Scott Aaronson, and I found the second homework problem at the end to be incredibly thought-provoking (this course was offered over ten years ago, so I think it's now safe to discuss the homework online):

  Let BB(n), or the "nth Busy Beaver number," be the maximum number of steps that an n-state Turing machine can make on an initially blank tape before halting. (Here the maximum is over all n-state Turing machines that eventually halt.)

  Prove that BB(n) grows faster than any computable function.
  Let S = 1/BB(1) + 1/BB(2) + 1/BB(3) + ...
  Is S a computable real number? In other words, is there an algorithm that, given as input a positive integer k, outputs a rational number S' such that |S-S'|<1/k?

I understand question #1 - it's #2 I'm wondering about. Clearly the series converges, since the sequence $1/BB(n)$ falls off much faster than $1/n$ (to put it mildly...). I suspect that $S$ in uncomputable like Chaitin's constant. (Although in some vague sense S seems to me to be more "natural," because it does not rely on a specific choice of prefix-free universal computable function "programming language" - so perhaps it's more analytically tractable?) Am I correct?

Also, is there anything at all that we can say about $S$ quantitatively? (Beyond the trivial result that it's greater than $1/4 + 1/6 + 1/13 = 77/156 = 0.494...$ based on the known values of $BB(2)$, $BB(3)$, and $BB(4)$.)


texts: Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average?

texts:
I thought of some mixed algorithm: binary + interpolation search. While first has $O(\log n)$ runtime in both worst and average cases, second has $O(n)$ worst case runtime and $O(\log \log n)$ average case.

However, I think, if such algorithms can exist, there are more than one of them.

Anyway, what I want to know if there is any known algorithm with restrictions given in title.

Note. It must be appliable to simple arrays without repeatitions (no precomputing/hashing).


texts:
A question from a lecture of mine.
The way I see it, while summing sets is meaningless, O(f(n)) + O(g(n)) is obviously limited from above by the greatest function in either, which means that I practically take the maximum of O(f(n)) and the maximum O(g(n)), and claim that either is the maximal one, or they are equal.

Would this be a legitimate claim in an exam?


texts: Operations making non-context-free languages regular

texts:
If $A$ is a non-context free language, is $A^*$ a regular language?
If $A$ is a non-context free language and $B$ is a regular language, is it possible that their concatenation is a regular language?


texts: Finding the language generated by a context-free grammar

texts:
This is a question from the Dragon book (I apologize for translation mistakes, I don´t have the English version on hand):

What language is generated by this grammar?
$S \rightarrow a S b S \mid b S a S  \mid \epsilon$

I don't know what I'm supposed to do here. The definition in the book about languages says this (and that's pretty much it in the chapter):

a language is the set of all words that can be produced by any parse
tree.

So, if I want to make "any" parse tree out of this grammar, I can recursively keep building it, using just the first two rules. I searched a bit and got the impression that every rule has to be used once, but I'm not sure. It would be very helpful if someone were able to provide some tips on solving these sorts of problems.


texts:
Given the runtime of an algorithm to be m!/(n!*(m-n)!) That is mCn, where both m and n are variables, is the complexity factorial or polynomial? Or is it something else?
Please elaborate.
Thanks


texts:
This is a question involving regular expressions for regular languages.

I am currently stuck trying to prove that the operand ∅ is not necessary unless the language is the empty set. That is, a regular expression is either equivalent to ∅ or is a ∅-free regular language. (A language is ∅ free if it contains no occurences of ∅)

This seems to be an induction proof, but I'm not really sure how to prove this. It seems like you're possibly trying to show that if a set is ∅ free, then doing anything involving ∅ will either result in the language ∅ or a ∅ free language.

So if r is ∅ free, then (r+∅) = r, r∅=∅ etc

I'm not really sure if this is really complete. I'm not overly comfortable with regular languages yet, so any help is much appreciated.


texts: Question about labeling in Dijkstra's Proof of Correctness

texts:
I am trying to understand the proof of correctness for Dijkstra's algorithm (shown below) and also at the following link: CS Auskland

  Proof by contradiction

  Suppose that $u$ is the first vertex added to $S$ for which $d[u] \ne \delta(s,u)$. We note:

  $u$ cannot be $s$, because $d[s] = 0$.

  There must be a path from $s$ to $u$. If there were not, $d[u]$ would be infinity.

  Since there is a path, there must be a shortest path.

  When $x$ was inserted into $S$, $d[x] = \delta(s,x)$ (since we hypothesise that u was the first vertex for which this was not true).

  Edge $(x,y)$ was relaxed at that time, so that
      $$d[y] = \delta(s,y)
\le \delta(s,u)
\le d[u]$$

  Now both $y$ and $u$ were in $V-S$ when u was chosen, so $d[u] \le d[y]$.

How can we say that $d[u] \le d[y]$?  And why aren't we saying that $d[u] \ge d[y]$?  Wouldn't the label on $u$ be larger if it is further down the path from $y$?

  Thus the two inequalities must be equalities,
      $$d[y] = \delta(s,y) = \delta(s,u) = d[u]$$

  So $d[u] = \delta(s,u)$ contradicting our hypothesis.

  Thus when each $u$ was inserted, $d[u] = \delta(s,u)$.


texts:
I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.

I am randomly creating a path thru all the vertices and I want to know if there is any efficient way to find all the intersections on my path.


texts: Difference between Bayesian Networks and Dynamic Bayesian Networks

texts:
I'm studying Bayesian networks and want to clarify a couple of things with people who are more knowledgable in the area than me.

As far as I understand it, a Bayesian network (BN) is a directed acyclic graph (DAG) that encodes conditional dependencies between random variables. The graph is drawn in such a way that the the distribution (dictated by a conditional probability table (CPT)) of a random variable conditioned on its parents is independent of all other random variables. I'm assuming that, by definition, both the structure (nodes and edges of the DAG) and the entries of the CPT in a BN assumed to be fixed in time.

Now, I'm wondering about the distinction between BNs and Dynamic BNs (DBNs), specifically, where the dynamic term in a DBN arises from:

Does this mean that the structure AND conditional dependencies between variables are time-varying? If so, is a BN with a fixed structure (DAG) but time-varying probabilities also considered a DBN (does this type of 'DBN' have a name)?

I'm not sure if what I've said is correct. Please let me know if I went wrong anywhere or if there is a better way of thinking about this.


texts: How efficient of this prime sieving algorithm?

texts:
I just found there is an old program of mine where I implemented the following prime sieving algorithm:
#define MAX=1000001
#define SQRT=1000
// ...
not_prime[1] = 1;
for (int a = 2; a <= SQRT; a++)
  if (!not_prime[a])
     for (int c = MAX / a, b = a * c; c >= a; c--, b -= a)
        if (!not_prime[c])
           not_prime[b] = 1;

It seems like my logic that time is: For any given composite a and all corresponding composite cs such that MAX >= b; b = a * c. But I forgot why I set restriction on c that c >= a? Could anyone help explain this line for me and help me analyze how efficient this algorithm is?


texts: Recommender System - Binary Ratings without explicit dislike

texts:
I'm currently looking into developing a system in which media from various sources is collected, with the notion that the media collected for each user is media they 'like'. This results in a set of n users, each with their own respective set of m liked items.

Most papers on recommender systems I find either require explicit ratings, or work within a binary domain with likes and dislikes.

How would I go about making recommendations based mainly on what is in a users preferred / liked set, without information on what they dislike?

Thanks.


texts: Shortest past including an edge from a given set

texts:
I am working on the following problem.

There are N vertices and M roads connecting them. Some of the roads are broken. I have to go from vertex 1 to vertex N taking at least one good road and find the minimum number of broken roads taken. If no good road is taken, display −1.

I am trying to use Dijkstra shortest path algorithm for this. I have assigned weight 0 to the good roads and 1 to broken roads. Then I find the shortest path taken. According to me, this shortest path should be equal to the minimum number of broken roads taken. For considering the case where all the roads are broken, I check if the total weight of path is equal to the number of roads taken, then display −1. But I understand, this algorithm will not work always.

What would be the right approach for this problem?


texts:
Could anyone point me to simple tutorial on greedy algorithm  for Minimum Spanning tree - Kruskal's and Prims' Method

I am looking for a tutorial which

does not include all the mathematical notation
explains algorithm along with the analysis of the running time.


texts: Edge removal to convert a non-planar DAG to a planar DAG while maintaining reachability?

texts:
Is there an algorithm that removes edges to convert a non-planar DAG to a planar DAG while maintaining reachability? For example, the graph $G$ below is non-planar:

but, by removing certain edges to produce $G'$, it can be made planar but every vertex still has the same transitive closure (meaning vertex $t$ is reachable form vertex $s$ in $G'$ iff the same is true in $G$)

Is there an algorithm to do this for any general DAG (or return an error if it's not possible)?

My use case is that I'd like to use Thorup's algorithm for reachability, but it only works on planar graphs.