texts:
Sorry if I am doing it wrong in some way.

Some days ago I have passed trough an technical test in which I had 3 tasks to complete. The tasks were a problem and I have to write an algorithm to solve it.

One of the 3 tasks I could not complete. Really, I have absolutly no idea how to start.

I am not asking for ready algorithm here.

I'll try to reproduce here.

Command 'X': X = ( 2 * X ) - Y
Command 'Y': Y = ( 2 * Y ) - X
Initial values: X = 0, Y = 1;

Given a N number, what's the minimum of commands where X or Y reach N. Each command change it's own value.

If I send the command 'X', the value of X will be '-1', and so on

The exemple was N = -11
Commands: 'X','X','Y','X', this way X will be equal -11.

Command 'X', X = ( 2 * 0 ) - 1 = -1  , Y = 1
Command 'X', X = ( 2 * ( -1) )  - 1 = -3  , Y = 1
Command 'Y', X = -3                  , Y = ( 2 * 1 ) - (-3) = 5
Command 'X', X = ( 2 * -3 ) - 5 = -11, Y =5


texts: Why does a polynomial-time language have a polynomial-sized circuit?

texts:
I wish to understand why P is a subset of PSCPACE, that is why a polynomial-time langauge does have a polynomial-sized circuit. I read many proofs like this one here on page 2-3, but all the proofs use the same technique used in the Cook-Levin theorem to convert the computation of M on an n-bit input x to a polynomial sized circuit.

What I don't understand is that the resulting circuit is dependent on the input x, because what is being converted into a circuit is the computation of M on the specific input x. By definition of PSIZE, the same circuit must work for all the inputs in a fixed length, and thus is not dependent on one specific input.

So how is the process of creating a poly-sized circuit family for a poly-time deterministic Turing machine works exactly?


texts: Is there a free online computer calculator that is more powerful than wolframalpha.com?

texts:
I need a calculator that accepts inputs using product notation, can compute the following, and can return the result in scientific notation:

$$\dfrac{\prod_{i=1}^{3.1536\times10^{16}}(52!-i)}{52!^{3.1536\times10^{16}}}$$

I have tried wolframalpha.com, desmos.com, and Excel. None of them can do the calculation. Is there another calculator that would work?


texts: The correct way to calculate the performance of my approximate algorithm

texts:
I've got a question about how best to classify the performance of an approximate algorithm. I'm trying to find the 'correct' value of a graph problem instance whose cost function has an objective function and a penalty function. I've configured my method such that the optimum solution of the problem has the highest value, fulfilling the objective criterion adds to the cost function value, and the penalty subtracts from it. This means that some poor solutions have negative values.
Typically the performance of an approximate algorithm is measured as:
$ \frac{C_{i}}{C_{max}}   = r $.
I'm a little confused where to set my baseline of $0$ however. Should I translate my objective values such  that they are all positive, and so add the $ |{\min C}|$ to all my cost function values and the best possible solution? Or is it best practise to calculate $r$ as found ?


texts: Any Non-trivial Logic System Defined with only Equality

texts:
Preface
We can define a system of logic by conjunctions of rules that system must follow. For example, if we wanted to define transitivity of numbers:
$$F_1: \forall a,b,c. a < b \land b < c \rightarrow a < c$$
We could similarly define associativity:
$$F_2: \forall d,e,f. (d + e) + f = d + (e + f)$$
Then we could define a system that follows these rules by the conjunction of all these rules:
$$F : F_1 \land F_2$$
Then if we wanted to check if a statement is satisfiable, say $S: c + 2 = b \land b = 1 \land c = 0$, we could take the conjunction of $S \land F$ and then calculating their congruences classes to see if any contradictions arise.
Question
I am curious: Can any valid non-trivial systems of logic be describe only using equalities ($=$) and conjunctions ($\land$)?
What I mean by non-trivial is that for the logical system in question, $F$, there exists some statements $S$, only using conjunction and equality for both $F$ and $S$, such that:
$$SAT(S \land F) \neq SAT(S)$$
Where $SAT$ evaluates to $\top$ or $\bot$ if the logic is satisfiable or not.
This is to say, the conjunction of $F$ with $S$ changes the satisfiability of $S$. If $S$ were already satisfiable, $F$ may define a system where $S$ is in fact a contradiction.
Example 1
As an example say:
$$S: x = 1 \land x = 0$$
This is satisfiable by $x = 1 = 0$, because we haven't defined what the relation of 1 and 0 are. If we introduce a system of logic:
$$F: 1 \neq 0$$
Then take their conjunction:
$$1 \neq 0 \land x = 1 \land x = 0$$
This is no longer satisfiable. You can see this is mainly because we introduced an inequality from $F$. I am wondering if you could define such an $F$ only using equality and conjunction that changes the satisfiability of an $S$.
Example 2
I don't think this is possible. Let's say, for instance we define a system of logic $I$ that defines a set of integers and the addition operation ($+$), conjunctions of associativity, transitivity, reflexivity, axioms, etc. Let's assume we do this only using equality and conjunctions.
Then we describe a statement:
$$S: a = b \land a = b + 1$$
$S$ is perfectly satisfiable on it's own because they would all be in the same congruence class, and because $+$ is not defined we have $a = b = b + 1$. Then introduce $I$:
$$I \land S$$
Clearly this should not be satisfiable. However, if we have only used equality then there is nothing to let us know that any particular congruence class will have a conflict and thus it is still satisfiable (I think). Thus resulting in a contradiction that we have not actually define the logic system of integers. From this, I would conjecture that this is not possible, as you would need some inequality ($<, \neq, >$) to refute or at least discover a contradiction.


texts: Complexity of Computing Volume of Convex Polytope

texts:
Given a convex polytope $\{x\in \mathbb R^n | Ax\leq b\}$ where $A$ is a matrix, and $b$ is a vector, and inequality between two vectors (like $Ax\leq b$) means inequality between their components ($\forall i : (Ax)_i \leq b_i$).

Is it NP-complete to compute its volume? Or are there efficient algorithms for doing that?

Thanks in advance!


texts: Algorithm for creating a directed graph using flat data input

texts:
Given flat data like this:

01001, Butter, salted
01002, Butter, whipped, with salt
01145, Butter, without salt
04601, Butter, light, stick, with salt
04602, Butter, light, stick, without salt

What's the best approach to convert into this:

Butter (01001, 01002, 01145, 04601, 04602) -> salted (01001)
                     -> whipped (01002) -> with salt (01002)
                     -> without salt (01145)
                     -> light (04601, 04602) -> stick  (04601, 04602) -> with salt (04601)
                                                                      -> without salt (04602)

I was thinking of recursive sorting first, but I realized there may be a lot of string comparisons to be efficient.


texts: Why is it that Ternary search trees are memory efficient?

texts:
I'm trying to figure out why ternary search trees are memory efficient. I have tried to read up on this, but all articles I find only state it's memory efficient compared to tries, but not why.

I believe it has something to do with the middle node, and with its ability to handle duplicate keys in a better way than tries, but I'm still not sure.

Why are TST's more memory efficient then tries?


texts: I have to write a JS program to solve a 4x5 grid puzzle . how to I write code to construct a tree with all possible moves?

texts:
Here is the link to the puzzle: http://www.cs.brandeis.edu/~storer/JimPuzzles/ZPAGES/zzzQuzzle.html

My idea is to construct the tree of all possible moves and then use a search algorithm (probably BFS or A*) to find the shortest path to the solution.

This is the initial state:

  1 1 2 2
  1 1 3 4
  0 0 3 4
  5 6 6 7
  5 8 8 9

This is the final state (mirror of the start state):

  2 2 1 1
  4 3 1 1
  4 3 0 0
  7 6 6 5
  9 8 8 5

I need help to figure out how to construct the tree of possible states from the start state. Only sliding vertically and horizontally is allowed. no rotations)


texts: Problem A is polynomially reducible to problem B... what can we say about A and B?

texts:
This is a question on a practice final.

  Problem A is polynomially reducible to problem B. Which of the following
  statements is correct?

  I. If problem A is solvable in a polynomial time then problem B is solvable in polynomial time.

  II. If problem A is NP-complete then problem B is NP-complete.

  III. If problem A is NP-hard then problem B is NP-hard

  a) I

  b) II

  c) III

  d) I and II

  e) I, II and III

We are told that the solution is (c), but there's no explanation why on the key. I have tried to figure this out, and the only conclusion I've come to is:

(I) cannot be true because if A is polynomially reducible to B, this implies B is at least as hard as A. (Not sure if this is a correct conclusion, so feedback on this would be appreciated.)

This is the first time I'm learning about the notion of hardness, so I don't understand most of the technical explanations I've found. Any clarifications on why II is incorrect, and why III is correct would be appreciated.

Self study I've done includes reading multiple StackExchange posts, multiple Wiki pages, and the corresponding section in the Cormen book. I just personally understand concepts better if I see different explanations.


texts: Is there any type system which can assign a type to any halting lambda calculus term?

texts:
Some lambda terms, such as the church number 3: (f x -> (f (f (f x)))), are easily typeable on the simply typed lambda calculus. Others, such as pred, (a b c d e f -> (d (g -> (t -> (t (g e)))) (g -> f) (g -> g))), are known to require more complex systems such as System-F. Some of them aren't typeable on System-F itself, as this zip I posted in another question. As András Kovács observed on the follow-up, that function can be typed in Agda, although the technique he used for doing so isn't trivial.

I have a lot of similarly tricky terms such as nTuple = (k -> (k (b c d -> (b (e -> (c e d)))) (b -> b) (b -> b))), which receives a church number and returns an N-Tuple of that length. I don't know if those terms are typeable. I would like to know:

Some systems seems to ban many "desirable" terms, while others bans less of those. What is the property of a system that determines if it is more accepting or more restricting?
Is there any type system in which arbitrary lambda terms are typeable?
Is there any general technique/algorithm to find the types of those expressions in such system?


texts: Expressing classic automata in modern terms

texts:
This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions (electrical, mechanical, whatever...), I find the terms used in describing these machines rather extravagant. It's as if the terminology is meant to be agnostic of any specific implementation, but ends up just reflecting the time and the area of application of its provenance. Hence references to tape, read/write head, and the like.

I'm wondering if I could better understand the essence of and the differences among the FSM, PDA and TM if these were cast in terms of the basic computer architecture of today. It would seem that an FSM would require, at a minimum, a read-only memory (ROM) to implement branching (jumps), acceptance or rejection, as well as register(s) to store the input and compare it to the finite states loaded in ROM. By contrast, a PDA adds a rather peculiar kind of writeable stack-based memory allocation to store the input for later processing. Finally, the TM relaxes the stack-based restrictions on the implementation of RAM.

Is this an accurate description of the three machine types? Does such a description lose in explanatory power to the traditional presentation in terms of states, tape etc.? Is such a description of necessity more complicated and adds extraneous detail compared to the bare minimum necessary to understand these concepts in the traditional presentation -- beyond the fact that these terms, too, will be rendered obsolete and are application specific?


texts: Is there such a problem as b-Matching with different b values?

texts:
Consider a bipartite Garph $G=(L \cup R, E)$. Naturally, a b-Matching problem is to find a set of edges $M \subset E$, such that each node in $L$ and $R$ are adjuscent to maximum $b$ neighbors, and a weight function $w(e), e \in E$ is maximized.
What if we have different $b$? e.g., $b(v)=5, \forall v \in R$ and $b(v)=2, \forall v \in L$. How do you call the problem? Is is constrained matching, or k-cardinality assignment, or what? I need to find some literature for it.
Thanks!


texts: Strategies for becoming unstuck in understanding TCS

texts:
I am a graduate student taking a course in theory of computation and I have serious trouble producing content once I'm asked to. I'm able to follow the textbook (Introduction to the Theory of Computation by Michael Sipser) and lectures; however when asked to prove something or come up with a formal description of a specific TM, I just choke.

What can I do in such situations? I guess my issue is with fully comprehending abstract concepts to the point I can actually use them. Is there a structured way to approaching a new, abstract concept and eventually build intuition?


texts: How to show that hard-to-compute Boolean functions exist?

texts:
How can one show that there exist Boolean functions on $n$ inputs which require at least $2^n/\log{n}$ logic gates to compute?

This problem was originally stated in Exercise 3.16 of Nielsen & Chuang's Quantum Computation and Quantum Information.


texts: Expected number of comparisons in a merge step?

texts: I know that merging two sorted arrays takes worst case n comparisons. However, there will often be cases where one array is depleted before the other, letting us just append the remainder of one array to the combined sorted array. I've also read that merging takes the same amount of comparisons (wrt to n) to any input of size n. How is this represented in the mergesort recurrence relation and time complexity?


texts: What is the worst-case big-O time complexity for this code?

texts:
I had a quiz in my class and didn't do so well on it. I'm looking to find out if someone can explain to me what I did wrong here - our professor is overwhelmed with office hours as we moved online so I thought I'd post here.

def functionC(L):
    for i in range(len(L)):
        if L[i] == i:
            v = L.pop(i)
            L.insert(i, 2*v)
    return

I supplied the following answer:

  The above function is O(n) because the for-loop grows with the size of
  L. The pop and insert functions are both constant time.

the word time is crossed out, but there is no other explanation as to why I received 6/10 for the question. What did I get wrong in this and why?

Here is an image of the question and my answer to prove the quiz has already been graded and handed back.


texts: Number of sentences and sentential forms generated by a grammar

texts:
In this question, I'm considering only "finite grammars". A finite grammar can only produce a finite number of distinct sentences. The following grammar is finite in my definition:
S         → AB
A         → B | a
B         → a | b

It can only generate the following finite number of sentences: aa, ab, ba, bb
On the other hand, the following grammar is not finite:
S         → AB
A         → AA | B | a
B         → a | b

Because it can create an infinite number of sentences: aa, aaa, aaaa, aaaaa, ...
Now to the actual question. Suppose the following finite grammar:
S         → variable = math_expr
variable  → a | b | c
math_expr → INT | function
function  → func_1() | func_2(INT, INT, INT, INT)
INT       → 1 | 2 | 3 | 4 | 5

I want to know if there is some kind of formula that calculate the number of sentences and sentential forms that can be generated by a finite grammar.
Example of sentences: b = func_2(2,4,3,3), a = func_1()
Example of sentential forms: b = func_2(2,2,INT,INT), c = math_expr,  S
At the moment, I am able to know the number of sentences and sentential forms by applying a Breadth-First Search (BFS) starting from the S node.
However, because I'm working with search in program synthesis, it would be great to know the size of the domain without the need of applying an exhaustive search on it.
Question: How can I find the number of sentences and sentential forms given only an arbitrary finite grammar?
For the first finite grammar I showed here, the answer is easy to calculate by hand:
Sentences: aa, ab, ba, bb
Sentential forms: S, AB, BB, aB, bB, Aa, Ab
So the final answer would be 4 + 7 = 11
However, for the second finite grammar I showed, it is not that easy to calculate it.
PS.: In my original problem, I am working with program synthesis with a Domain Specific Language (DSL). I tagged CFG with the hope that the same applies, granted I'm not 100% sure.


texts: Is finding a path with more red vertices than blue vertices NP-hard?

texts:
Given a connected, directed graph $G=(V,E)$, vertices $s,t \in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either red or blue, is it possible to find a simple path from $s$ to $t$ with more red than blue vertices in polynomial time?

I think it should be possible but our TA said this was NP-hard.

Idea for a solution:

From $G$ create $G'=(V',E')$ as follows:

Split all $v \in V\setminus \{s,t\}$ in two vertices $v_{in}$ and $v_{out}$. $V'$ is made up of the split vertex pairs and $s$ and $t$.
For all $e=(u,v) \in E$ introduce an edge $(u_{out},v_{in})$. (For edge $(x,v)$ or $(u,x)$ where $x \in \{s,t\}$ create edge $(x,v_{in})$ or $(u_{out},x)$ resp.). Also, introduce an edge $(v_{in},v_{out})$ for any of the split vertices. So $E'$ contains two types of edges: the ones that correspond to edges from $E$ and the ones that correspond to vertices from $V$.

Now, we introduce weights as follows:

$w((v_{in},v_{out})) = -1$ if the corresponding vertex $v$ was red.
$w((v_{in},v_{out})) = +1$ if the corresponding vertex $v$ was blue.
$w(e) = 0$ for all other edges, i.e. the ones that correspond to edges of $G$ rather than vertices.

Now, conduct an algorithm for shortest paths of your choice like Dijkstra, Bellman-Ford,... , check whether the length of the given path is $<0$ and you are done.

Why does this not work? Is it because we may have negative cycles? We could detect those with Bellman Ford but then we'd have to find the desired path with non-efficient means rendering this decision problem NP-hard?
Is there an elegant reduction to show NP-hardness?


texts: Propagation and contamination delays with different delays for rising and falling edges

texts:
In the Digital Design and Computer Architecture by David Harris, Sarah Harris the authors explain what are propagation delay and contamination delay in the following way:

The propagation delay $t_{pd}$ is the maximum time from when an
input changes until the output or outputs reach their final value. The
contamination delay $t_{cd}$ is the minimum time from when an input changes until any output starts to change its value.. . $t_{pd}$ and
$t_{cd}$ may be different for many reasons, including different
rising and falling delays..

So I draw from the bold text (emphasized by me) for any circuit there is a only pair of these measures values. That is to say, if a circuit has a different delays for its rising edge (transition from 0 to 1) and falling edge (transition from 1 to 0), $t_{pd}$ is about the longest between them, and $t_{cd}$ - about the shortest.
The authors show such circuit to define the critical and short paths:

and then expand on the aforementioned measures by stating that taking notice of both the critical and short paths, it is true for this circuit:
$$t_{pd} = 2*t_{pdAND} + t_{pdOR}$$
$$t_{cd} = t_{cdAND}$$
Let's suppose we encounter the very case: the AND gate has a different delays for its rising and falling edges. Does it mean these equations might be wrong? There is the falling edge shown in the picture. So if this edge is quicker in terms of delays, it's either nonsense to use $t_{pdAND}$ here (because it indicates the slower rising edge measure but we are talking about the falling one) or $t_{pd}$ is not relevant to the matter in hand (falling edge).
As I'm concerned, for these types of situation it would be reasonable to exploit two different pairs of values: one for a rising edge and another for falling one but this is out of line with the bolded author statement. What's the right way to address these possible circuit delays differences?


texts: Graphs: Dectect a sink in $\mathcal{O}(V)$

texts:
Given a directed conected graph which representation is its adjacency matrix $A$, design an algorithm to detect a sink in $\mathcal{O}(V)$ time, being $V$ the number of vertices.

As definitions can vary, in this context, a sink is defined as a vertex with $0$ exit degree and $V-1$ enter degree.

Obviously, the problem is reduced to find a $j\in\{1,\dots,V\}$ such as $a_{ji}=0$ for all $i$ and $a_{ij}=1$ for all $i\not=j$, thats what I tried. However, this solution is in $\mathcal{O}(V^2)$.

Any idea?


texts:
Let $$\texttt{EQU}=\{u\#v \mid T(M_u)=T(M_v)\} \\
\texttt{UNI}=\{w \mid T(M_w)= \Sigma^*\}$$

How can you prove $\texttt{EQU} \leq \texttt{UNI}$?

The idea I have so far is, to simulate the TM that decides whether a given $w = u\#v$ is in $\texttt{EQU}$ or not. In case it is, our TM halts and we simply accept everything ($f(w) \in \texttt{UNI}$). But, as far as I know, there are two options for $w \notin \texttt{EQU}$ :

The simulation won't ever stop
The simulation stops but not with $q \in F$

The first case isn't a problem as I think. We won't ever accept because the TM never finishes with simulating.
But the second case is a problem, as the TM accepts with $w \notin \texttt{EQU}$.


texts:
Text message constantly keeps adding more emoji so I know the protocol could be extended with a delimiter at minimum.
How does RCS compare to extending text message protocol? I ask this because I somehow doubt Apple will adopt the new standard but could be wrong when it doesn't support encryption.
Here is a list of feature comparisons to iMessage


texts: Clarification of Theorem 1.11 in the book Computational Complexity by Arora/Barak

texts:
The book Computational Complexity: A Modern Approach by Arora/Barak provides the following:

Theorem 1.10
There exists a function $UC: \{0,1\}^* \to \{0,1\}$ that is not computable by any TM.

Theorem 1.11
HALT(The halting problem) is not computable by any TM.

Table 1.7 that shows how Theorem 1.10 can be proved using diagonalization. Essentially this table says that there exists an uncomputable function UC that can always reverse the output of any TM, therefore, function UC is uncomputable.

The proof of Theorem 1.11 essentially creates a TM $M_{UC}$ that computes UC by assuming that HALT is computable and also by using a universal TM to simulate $M_{UC}$ and thus contradicts Theorem 1.10 and concludes that HALT is uncomputable.

My question is this: Since $M_{UC}$ is a TM, it already exists as a part of Table 1.7. In this case (as explained by the note attached to this table), function UC will (by definition) reverse the output of $M_{UC}$. Thus the $M_{UC}$ does not compute function UC even if we assume that HALT is computable.

Also, it seems that $M_{UC}$ will go into a type of recursion when the input to $M_{UC}$ is a bit representation of $M_{UC}$, i.e., each simulation on a universal TM will lead to another call on the universal TM and thus lead to a type of loop. Perhaps this is the reason the proof of Theorem 1.11 invokes a call to the HALT function (which is assumed to be computable).


texts:
In some paper I read,

  A theoretical worst case study shows that a single regular
  expression of length $n$ can be expressed as an NFA with $O(n)$
  states. When the NFA is converted into a DFA, it may generate
  O($\Sigma^n$) states. The processing complexity for each character in the inpuyt it $O(1)$ in a DFA, but is $O(n^2)$ for an NFA when all $n$ states are active at the same time.

Please explain how NFA has at its maximum just $n$ states and its equivalent DFA has at most $O(\Sigma^n)$ states?


texts:
Can we construct minimum spanning tree for an undirected graph with distinct weights using bfs or dfs?

I have gone through many answers but each answer says something different and I am not convinced.


texts: Hoare logic - partial/total correctnes and strength invariant

texts:
I'm studying Hoare logic and I can't understand the relation between partial and total correctness regarding loop invariant. Suppose for example that I have the following program:

{X ≥ 0}
Y := 0;
Z := 0;
{Y =2Z}
while (Z ̸= X) do (
Z := Z + 1;
Y := Y + 2 )
{Y =2X}

The solutions says that for partial correctness I can use the invariant Inv = 2Z.
But when I have to prove total correctness the invariant must be strengthened with X - Z >= 0.
Which is the hoare logic property that let me strength the invariant, adding the condition to it, only for total correctness?


texts: If you have a Cook reduction in both directions, do you also have a Karp reduction?

texts:
If there exists a Cook reduction of a decision problem $\mathcal{P}_1$ into another decision problem $\mathcal{P}_2$ and also a Cook reduction of $\mathcal{P}_2$ into $\mathcal{P}_1$, then is there also a Karp reduction (a polynomial transformation) between $\mathcal{P}_1$ and $\mathcal{P}_2$ (in both directions)?
These are the definitions I use:

Cook reduction
$\mathcal{P}_1$ polynomially reduces to $\mathcal{P}_2$ if there is a polynomial-time oracle algorithm for $\mathcal{P}_1$ using an oracle for $\mathcal{P}_2$.
Karp reduction
$\mathcal{P}_1=(X_1,Y_1)$ polynomially transforms to $\mathcal{P}_2=(X_2,Y_2)$ if there is a function $f:X_1\rightarrow X_2$ computable in polynomial time such that for all $x\in X_1$, $x\in Y_1$ if and only if $f(x)\in X_2$.


texts: How to prove an identity of regular expressions

texts:
I am in trouble how to prove that these two regular expressions are equivalent. I know what are closures and all the basics of automata. But the problem is I don't know the method or way of solving this kind of problem.
Question:

Prove that R.H.S regular expression is same as L.H.S
$$ (a+b)^* a (a+b)^* b (a+b)^* = (a+b)^* ab (a+b)^* $$


texts: Learning juntas, with membership queries

texts:
The junta problem is the following: we have a boolean function $f:\{0,1\}^n \to \{0,1\}$ that actually happens to depend on only $k$ of its input variables.  Given the value of $f(x)$ for many random values of $x$, we want to identify the $k$ input variables that $f$ actually depends upon.  In other words, secretly $f(x_1,\dots,x_n) = g(x_{i_1},\dots,x_{i_k})$ for some indices $i_1,\dots,i_k$; given many pairs $(x,f(x))$ where each $x$ is random, we want to find the $i_1,\dots,i_k$.

I am interested in a variant of the junta problem, where we are allowed membership queries.  In particular, at any point, we can choose a value $x$ and receive the value of $f(x)$.  The goal remains the same: We want to learn the junta, i.e., learn the indices $i_1,\dots,i_k$.

How many membership queries are needed, and what is the running time to learn the junta?

There is a simple, straightforward algorithm that uses something like $O(n)$ membership queries (first find $x,y$ such that $f(x)\ne f(y)$, then move from $x$ to $y$ by changing one bit of the input at a time, to identify $x',y'$ such that $f(x')\ne f(y')$ and $x',y'$ differ in a single bit position).  But can it be done with many fewer membership queries?  For instance, can we learn the junta with, say, $O(\lg n)$ membership queries?


texts: Why does lower integer represent higher priority in scheduling literature?

texts:
I'm studying Real Time Systems, and in the textbook most of the focus is on scheduling algorithms. (Textbook: Real-Time Systems by Jane W. S. Liu)

In the algorithms that involve priorities, it is said that smaller integer represents higher priority (e.g. a process with priority 1 has more priority than one with 3). Then, in the subsequent discussions, there are terms involved like: "Let Pi be a process with a higher priority..." On such occurrences, I get confused whether higher priority means actually higher priority or larger integer. In most of the cases it means the former, however sometimes I've to guess that from the context, which is a bit time consuming.

As far as I know, all algorithms will work well with slight modifications if larger integers represented higher priority, and that would avoid confusion. So my question is:
Is there any reason, apart from conventional / historical one, for using smaller integer for denoting higher priority? If not, why not amend it and avoid confusion?


texts: What is the difference between Cased-based Reasoning and Rule-based reasoning?

texts:
As stated here, Rule-based Reasoning systems are considered to be "old style" AI that uses rules prepared by humans - as opposed to Neural Networks where machine recognizes pattern i.e. acquires new knowledge and takes decision based upon that.

What I understand about Case-based Reasoning (CBR), it looks at the new cases in light of similar past cases, finds suitable reference cases, evaluates their application on the new case and revises it accordingly, applies it on the new case, and finally stores the case and solution as newly acquired knowledge.

Considering this, can I state that Case-based Reasoning should be considered as "new style" AI? Or is there a gap in my understanding?

I wanted to add: If anyone can offer a rough spectrum, that puts different AI approaches on different points depending on how independently they can take decision or how much prone they are to learn from experience (i.e. train their mind) instead of being 'pre-configured', that will also be welcome.


texts: How to use Parallel Semaphores for Dining Philosophers Problem

texts:
I am in an intro to OS class and we are learning about mutual exclusion and semaphores. One classical problem we learned about was the dining philosophers problem. My professor touched on the different cases using simple semaphores (i.e asking the last philosopher to grab the right fork before the left while the others grab right first) however, these still violates the concurrency requirement.
He explained that these types of problems begin to show the importance of advanced synchronization and how we need more but he didn't go into details because that subject belongs to the actual Operating Systems course.
I am curious as to how you could implement AND semaphores to solve the dining philosophers problem. I did some research and could not find any great resources showing implementations using AND or monitors.
Could someone go into some detail or point me to an article/textbook that does?


texts: Why do modern processors need a runtime stack?

texts:
Professor said that modern processor needs runtime stack.

But he didn't explain the reason.

Why is the runtime stack required in the modern processors?


texts:
can you tell me how i can use a bloom-filter by a joining operation with two tables?

let's assume that:

Table A ={A_id,B_id,age}, Table B = {B_id, color}.

now i want to use a bloom-filter so i can do the join operation faster, but i do not know how i can use this in this case.
I would first take from A the PK A_id and bloom-filter that with some hash functions and just mark the indexes with 1 and then i would do the same operation with Table B and finally just AND both results. but it's not correct...


texts: Universal Turing machine and virtualization technology

texts: I was wondering if virtualization technologies (VmWare, virtual box) are possible thanks to the theoretical existence, translated into practice, of the concept of universal turing machine or if the two are simply a coincidence. As far as I'm concerned they seem to me to be closely linked but I could be wrong.


texts: Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function

texts:
A boolean-valued function defined in the set of positive integers, $\mathcal Z$.

$$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal Z $$

$f(n)$ is computationally expensive and it's analytical form (a closed-form equation producing these binary-valued outputs is unknown, since it is the result of a time-domain simulation of complicated system of non-linear PDEs meeting certain exit conditions etc.). Furthermore, $\frac{\partial{f}}{\partial{n}}$ is also obviously not available.

The goal is to compute $n\ast$, i.e. the first occurrence of the integer-valued function input, $n$ that produces a Boolean $1$. Needless to say, this can be trivially achieved in computer code by using a simple $for$ loop and rejecting the values of $n$ one by one, until we hit $n\ast$.

The lower and upper bounds, $n_{min}$ and $n_{max}$ are known apriori.

However, given the expensive nature of computing $f(n)$, I am looking for an efficient algorithm beyond this naive implementation, especially one that requires small number of function evaluations. A pseudo-code implementation of your proposed solution would be much welcome too.

A conceptual schematic/visualisation of the problem is also shown here, purely to aid the understanding of the task at hand


texts: Count number of pairs of elements whose product is a perfect square

texts:
Given two arrays whose elements lie between $[1,10^5]$ and the size of arrays is $[1,10^5]$, how can we find the total number of pairs of elements from these arrays such that their product is a perfect square? The arrays may have same elements.

For example:

  Array 1: {1, 2, 4, 5}

  Array 2: {4, 8, 16, 125}

  Output : 6

The pairs are (1, 4), (1, 16), (2, 8), (4, 4), (4, 16), (5, 125).

If the array size is $10^5$, an $n^2$ algorithm would be inefficient.


texts: say you have a min-heap.  Popping removes the root and replaces it with the value of one of the leaves and then heapifies. couldnt this last heapify result in an unbalanced tree? is there something you have to do to maintain the balance of the tree?


texts: interval scheduling variant: 1 machine with 2 tasks need to complete only

texts:
I am looking for an optimal solution of an interval scheduling variant.

Basically, given n tasks with the start time Si and end time Ei, select EXACTLY two tasks whose execution periods are maximum and do not over lap (Equal start/end time counts as overlapping).

So if there are these task [9-14], [7-13],[1,4],[2-5],[2-10],[4-9]

The answer would be [1,4] and [7-13], whose execution time are 3+6=9 in total.

I can only think of an algorithm with n^2 complexity. That is the obvious solution of matching every period together, check if they overlap, and if they don't, replace a previously initialized Max value with their sum if it > Max. It does not seem to be optimal, as it does not pass the time test in my professor exercise.

So anyway, can anyone think of a more optimal solution?


texts: Algorithm to calculate shortest path when updating the heaviest edge in a path

texts:
For a given graph $G=(V,E)$ and path $p= v_1 \to v_2 \to ...\to v_k$, $w^\ast(p)$ represents the weight of the path between $v_1$ and $v_k$ excluding max_edge.
$$w^\ast(p) = \sum_{i=1}^{k-1} w(v_i, v_{i+1}) - \max \{ w(v_i, v_{i+1}) \vert 1 \leq i < k\} $$

For a given vertex $s$ in $V$

I would like to find an algorithm that calculates using Dijkstra the shortest path with value $w^\ast(p)$ between $s$ and every $v$ in $G$.

I'm guessing, I should start off by changing the original graph $G$. Maybe duplicating an edge with value (-1*max edge) .. or maybe making the heaviest edge zero

I'm not sure, so anything would be appreciated.

Thank you advance.


texts:
I'm trying to find an algorithm that finds an optimal matching between $A$ and $B$, where each element $a$ of $A$ provides a preference order $\prec_a$ over $B$. I will notate the index of an element $b$ in $a$'s preference order as $i_a(b)$, where if $b$ is most preferred then $i_a(b) = 1$. This mapping needs to satisfy two requirements:

If the mapping $m$ has $m(a_1) = b_1$ and $m(a_2) = b_2$, then either $b_2 \prec_{a_1} b_1$ or $b_1 \prec_{a_2} b_2$.
If $m(a) = b$, then for every $a'$, $i_{a'}(b) \geq i_{a}(b)$ or there exists $b'$ such that $m(a')=b'$ and $i_{a'}(b)\geq i_{a'}(b')$.

Note that there can be many matchings that satisfy both criteria, as in the case with 2 $A$s, $a_1$ and $a_2$, which both prefer $b_1$ to $b_2$. Here, the algorithm should pick randomly between $a_1$ and $a_2$ for $b_1$.

This is not precisely a stable matching problem ($B$ has no preferences, and the global constraint prevent it from being so). I suspect that this reduces to an instance of the assignment problem with clever edge weighting, but I am having a hard time coming up with weights that satisfy the first criteria.


texts: Simplest complete combinator basis pair for flat expressions

texts:
In Chris Okasaki's paper "Flattening Combinators: Surviving Without Parentheses" he shows that two combinators are both sufficient and necessary as a basis to encode Turing-complete expressions without the need for an application operator or parentheses.

Compared to John Trump's encodings of combinatory logic in "Binary Lambda Calculus and Combinatory Logic" through prefix coding S and K combinators with an application operator, only needing two combinators for flat expressions increases the code density to optimality. The resulting Goedel numbering maps every integer to a valid, well-formed closed-term expression unlike most calculi and minimal description length relevant esolangs whose canonical representations usually permit descriptions of syntactically invalid programs.

However Okasaki's encoding was meant to be most helpful in a one-way mapping from lambda calculus terms to bitstrings, not necessarily the other way around as the two combinators used in this reduction are relatively complex when used as practical substitution instructions.

What is the simplest complete combinator basis pair that does not require an application operator?


texts:
I was wondering if it can be said that $\mbox{NL}^\mbox{NL}=\mbox{NL}$. That is, a decision problem  $S$ can be decided using a nondeterministic TM using logarithmic space with oracle calls to $S'\in \mbox{NL}$ iff $S\in \mbox{NL}$.
My intuition is yes, because if $S'\in \mbox{NL}$ then there is a NDTM $M$ that decides it in logarithmic space. And so one can use the NDTM $M'$ for $S$ but every oracle call will be simulated on $M$, preserving the logarithmic space constraint.
I am not sure if this approach is correct, and if it is, how to formally explain such an algorithm for the simulation.


texts: Find the longest possible path in full binary tree

texts:
Given the depth of the tree, I need to calculate the longest possible path in the full binary tree (also known as the diameter).

When attempting this problem, I experimented with what the depth has to do with the path length. However, the solutions I came up with depended on going through the root, while the longest path could obviously exist outside of the root.

What's an equation I can use to find the diameter of the full binary tree using the depth?


texts: minimum spanning tree and minimum heavyweight spanning tree

texts:
a minimum heavyweight spanning tree is a spanning tree in which the heaviest edge is as light as possible.
Formally,
input : given connected undirected weighted graph, $G$.
output : a spanning tree $T$ for $G$ with property that every spanning tree $T'$ for $G$ has some edge $e'$ such that $w(e')\ge w(e)$  for every edge $e$ in $T$.

provide a greedy algorithm to solved the problem.
is every minimum heavyweight spanning tree a minimum spanning tree ?

first thing comes into my mind was using Kruskal's algorithm with $O(|E| \log |V|)$ running time. If I use kruskal's algorithm for 1, the output will guarantee to be a MST, thus 2 will be true? Can someone verify this for me, thanks in advance


texts: How can I prove impossibility of generalizing a given higher order function from pure to monadic or applicative?

texts:
There is a great divide in Haskell between pure and monadic algorithms. While the latter are indistinguishable from their usual imperative counterparts, the former can get much more magical. What this means is that some pure higher order functions do not admit translation from pure to monadic arguments, or from monadic to applicative ones. While there are beautiful abstractions that collapse and rebuild enormous depths of pure recursion in a blink of an eye, traversing a filesystem is a pain.

I specifically have two examples back there on Stack Overflow that I will refer to now:

Translating from pure to monadic.
Translating from monadic to applicative.

While there has been quite some impressive hand-waving and heuristic arguments that the precise translation is impossible, I'm still somewhat unhappy as a foundation for exact reasoning about such issues seems lacking.

In the first case above, it seems very plausible that we cannot have a function convergeM of type [m a] -> [m a] -- only of [m a] -> m [a], but I don't know how to go about obtaining an argument of ELI5 level of convincingness.

In the second case, it is shown that, going some way, we can reach a point where a monadic function is necessary, but there is still space to be suspicious: what if there is another way to go that will lead to an applicative function being needed instead?

I want to have some grasp on issues like this, some proven ground under my feet. Given that category theory does not support higher order functions, what can be done?


texts: Is the language of binary strings that contain a substring of the form $ww$, where $w \in (0+1)(0+1)^*$ regular?

texts:
Consider the language:
$L=$binary strings that contain a substring of the form $ww$, where $w
   \in (0+1)(0+1)^*$.
I am convinced this language is not regular, as $w$ can have arbitrary length due to the $(0+1)^*$ term, and whatever is generated by this term must be remembered for the next occurrence of $w$ immediately thereafter. So, a DFA cannot accept this language. Is this correct? Perhaps, I could show this more formally with the pumping lemma, but I just want to make sure the intuition is correct.
Now, do you agree that the way I have defined the language above implies that the first occurrence of $w$ must be the same as the second occurrence of $w$? For example, $w$ cannot equal $01$ in its first instance, but $011$ in its second instance.
Now, consider the language:
$T=$binary strings that contain a substring of the form $wy$, where $w,y
   \in (0+1)(0+1)^*$.
T is regular. Because $(0+1)^*(0+1)=(0+1)(0+1)^*$, the regex representing $T$ can be written as $(0+1)^*(00+01+10+11)(0+1)^*$. Is this correct?
Now, back to language $L$. This was defined in some exercises I was doing exactly as it is above. The solution said that $L$ is regular and can be represented by regular expression: $(0+1)^*(00+11+0101+1010)(0+1)^*$.
Lastly, If my thinking about $L$ is incorrect for some reason, does the regular expression $(0+1)^*(0+1)(0+1)^*(0+1)(0+1)^*(0+1)^*$ equal $L$?
I hope I have communicated my thoughts clearly on this matter. Please help me understand.


texts: Globally-optimized nearest neighbors lookup

texts:
I have a set $\mathcal{A}$ of $\mathcal{m}$ vectors in $\mathbb{R}^a$. I also have a different set $\mathcal{B}$ of $\mathcal{n}$ vectors  in $\mathbb{R}^a$.  These two sets are disjoint: $\mathcal{A}\cap\mathcal{B} = \varnothing$.

My goal is to find a set $\mathcal{C}$ such that $\mathcal{C} \subset \mathcal{A}$ and $\vert\mathcal{C}\vert = \vert\mathcal{B}\vert$, that minimizes the sum
$$
\sum\limits_{j}\Delta(\mathcal{C}_{j}, \mathcal{B}_{j})
$$
where $\Delta$ is some distance metric.  All elements of $\mathcal{C}$ must be unique, and there are no restrictions on the ordering of sets $\mathcal{B}$ or $\mathcal{C}$ in the calculation of the above formula.  The crucial challenge here is that we can't match two different points of $\mathcal{B}$ to the same point of $\mathcal{A}$, so you can't just assign each point of $\mathcal{B}$ to its nearest neighbor in $\mathcal{A}$.

Is this equivalent to an already-studied problem? If so, which problem?
Assuming the answer to 1 is yes, are there better approaches than the greedy one?

Answer to 2 is optional, I can do the research myself, just having difficulty nailing down an equivalent problem.


texts: Calculating the number of non-intersecting routes in an Euclidean graph

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 found a geometric proof that every optimal TSP solution contains no intersections.

How many non-intersecting routes could be there? Or in other words: what is the probability to guess an optimal solution to a TSP problem if we just enumerate or sample non-intersecting routes?

Edit: I want to ignore the case that D.W. mentioned. For every path that you can swap between two neighbors vertices(If we represent the path as an array of vertices so neighbors will be two vertices with consecutive indexes) without changing its non-intersecting quality, all of those paths will be considered as one.

Edit I found that this kind of removing crossings from the graph also know as 2-OPT


texts: I think this question arises from not having a clear idea on encoding. So, If I have a problem intuitively there may be many ways of encoding it using TM's alphabet set. Slight variation in the encoding may(intuitively) not affect the computability of the problem, Is it true? Can I have a computable problem which on changing the encoding turns uncomputable?For eg given a graph and two vertices, the problem is whether there is path between them. We know this is compuatable. But if we consider encoding as just a mapping, then If I have encoding such that set of all instance of the problem with the answer as yes mapped to some undecidable language(bijectively)?Is it possible?


texts: Can we approximate the number of possible witnesses for an NP language?

texts:
Assuming $L \in NP$, meaning that L could be verified by some $V(x,y)$, such that there exists a polynomial $P(X)$ such that $|y| \leq P(|x|)$ for every $x \in L$.

I was wondering - can I assume something about the possible witness space?
My intuition says that this number is bounded by $O(2^{P(|X|)})$ (all possible subsets of a certain problem, all possible strings by the length at most $P(X)$ etc...)

Thanks


texts:
So I'm trying to split on an attribute "Color" that has possible values (Blue,Green,Red,Orange,Pink).

I'm splitting on entropy values, and the best split can either be Multi-Way 5, Multi-Way 4, Multi-Way 3, or Binary. For example:

5: (Blue, Green,Red,Orange,Pink)

4: (Blue, Green), (Red), (Orange), (Pink)
   (Green,Pink), (Blue),(Red),(Orange)

3: (Red,Orange), (Blue,Green), (Pink)
   (Red,Blue), (Green, Orange), (Pink)

2: (Blue,Green,Red), (Orange,Pink)
   (Pink), (Blue, Green, Red, Orange)

And so on. But how can I make a comprehensive list of all the possible splits? Is there a specific algorithm I could use? Or how would I even know how many max possible combinations there are with this?

Any help would be greatly appreciated, thanks!!!


texts: What is the underlying structure of problems?

texts: We all the time write and talk about mathematical problems in plain English. For example, we define "the traveling salesman problem". But what is the actual, underlying structure of a "mathematical problem"? Can arbitrary mathematical problems be expressed exactly, in a formal language? Is it meaningful to talk about an algorithm that solves any arbitrary problem? Of course, that wouldn't decidable, but can we express it? For example, can we write a program which accepts, as input, a problem (example: "find an algorithm that sorts a list optimally") and outputs a solution (example: the merge sort algorithm)?


texts: Algorithm for multiplying multivariate polynomials

texts:
Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multidimensional polynomials in $R$ with maximal total degree $\delta$.
How fast can we compute the product of $f$ and $g$, i.e. the resulting coefficients of each term?

I have only been able to find a non-trivial algorithm for when $R$ is a field of characteristic 0, but not for $R$ being a general commutative ring.


texts: Undecidable definition of pure function?

texts:
I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this:

  DEFINITION: A statement is impure if

  it is an assignment, unless it assigns to a local variable
  OR, it evaluates a call to a function, unless that function is pure
  OR, it is a block containing an impure statement

  DEFINITION: A function is pure if it doesn't contain any impure  statement.

For simplicity, let's ignore assignments altogether and assume that a block is simply an ordered set of statements. (it shouldn't make a difference)

Now, this definition seems to work great until somebody defines a function that refers to itself, e.g.

function fibonacci(n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

or

function f() { return g(); }
function g() { return f(); }

By the proposed definition, to prove that fibonacci is pure, you need to prove that fibonacci is pure. Similarly in the second example. Thus, the purity of fibonacci, f and g is undecidable, yet intuitively we know that all 3 of these are pure, so this definition must be flawed.

How would I modify this definition to be decidable (and give the intuitively expected answer) even in the presence of recursion?

This question refers to some definitions of functional purity, but they don't seem formal enough to be used as a base for further reasoning.


texts:
I gone through the Russel's paradox.

From Wikipedia :

  According to naive set theory, any definable collection is a set. Let R be the set of all sets that are not members of themselves. If R is not a member of itself, then its definition dictates that it must contain itself, and if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves.

Next Russell's and Alonzo Church developed type theory to avoid this paradox. Can someone explain clearly how these types (type theory) avoids this paradox. Thanks


texts: Can we think of information theory in terms of "a measure on set of information"?

texts:
In information theory, we deal with the quantities $I(X;Y), H(X),H(Y), H(X|Y), H(Y|X)$. These are just numbers, but I intuitively think of them as the "measure" of a set of information.

There is at least one special case where this interpretation is exact: suppose there are independent variables $V_1,...V_n$, and the variables $X,Y,Z$ are tuples of $V_i$. Then we can literally think of $I(X;Y)$ as the measure (entropy) of the intersection of $X$ and $Y$.

But it is not obvious to me whether we can define a more general measure of information, such that mutual information can be interpreted as the measure of the intersection, and analogously for the other information quantities. Is this possible?


texts: Proving $a^{2+n}a^{n}$ is regular using the Pumping Lemma

texts:
So I'm trying to practice (and learn, clearly) use of the Pumping Lemma, and this is my current equation. It's clearly regular- it can be simplified:

$a^{2+n}a^{n} = a^{2+2n}$ and from there it's fairly easy to derive the regular language $aa(aa)*$

However, I'm trying to explicitly solve this through the Pumping Lemma- but clearly doing something wrong. This is my process (assuming language $A$, string $s$ in $A$, pumping length $p$):

First take $s = aaaa$ for $n = 1$ (simple case).

Take $p = 2$, and so $xy$ must equal $aa$ to fit $|xy| \leq p$ and $|y| \gt 0$ , giving $x = a, y = a, z = aa$.

Finally insert into the equation $xy^{i}z \in A$ with a trivial value of $i \geq 1$ - $xy^{2}z$. This gives a result of $aaaaa$.

And that's the problem. $aaaaa$ is not a member of the language  $a^{2+n}a^{n}$. Is there a step I'm missing here or a wrong assumption?

Thanks. And apologies for yet another pumping-lemma question.


texts: Hopcroft und Karp Algorithm and a suitable representation for a graph

texts:
Hey Guys I have a small question about the Hopcroft and Karp Algorithm.

I have a task to solve where I have to calculate the perfect matching. My professor told me I should use the Hopcroft Algorithm. With that I can calculate the maximal matching and then valited with (number of edges/2 = number of matching) if there is a perfect matching

Some background: Currently the Graphs will be representated as followed.

|(0,0) (1,0) (2,0) (3,0) (4,0) (5,0)|

|(0,1) (1,1) (2,1) (3,1) (4,1) (5,1)|

|(0,2) (1,2) (2,2) (3,2) (4,2) (5,2)|

|(0,3) (1,3) (2,3) (3,3) (4,3) (5,3)|

The 2-Tupel representing node coordinates in a room and the big one are actual nodes for this example

We dont count the diagonal ones as neighbors, so (2,1) has just (3,1) and (2,2) as neighbors

Also this example has 2 Graphs (it could be more or less, the points are random) but its cleary not bipartite.

Now is the problem I dont know how to apply this algorithm. Actually I know that if you just consider the diagonal values of a graph you could form a bipartite graph.

Lets say Graph 1. is with the points (1,2) (2,1) (3,1) (4,1), the graph could be bipartite if we imgagine that each diagonal is a subset of the Graph.

For example the bipartite parts are for Graph 1. { (1,2) (2,1)}, { (3,1), (2,2)} and {(4,1}) but I dont know if this helps me, I just think it makes it harder to programm.

So the question is how could I use the Hopcraft Algorithm for a single graph which is representated as above(lets say for Graph 1)


texts: How to build a label flow graph for static analysis

texts:
I'm new to world of static analysis and am trying to build a new analysis of C programs for llvm compiler.

I've started with the build of the graph of the constraints of the program:
The edges represent the flow of data through the program (according to the statements or function calls) and the nodes the run-time memory locations.

I'm wondering if for the labeling of the constraints I do need a symbol table with all the constraints and their labels.
I found out that we can build a CFG on top of the LLVM by only parsing the LLVM IR.

for example, we could just have:

//Build list nodes without successors.
for (Function::iterator e = F.end() ; e != BB ; ++BB) {
    BI = BB->begin();
    for(BasicBlock::iterator BE = BB->end(); BI != BE; ++BI){
        Instruction * instruction = dyn_cast<Instruction>(BI);
        StaticAnalysis::ListNode* node = new StaticAnalysis::ListNode(counter++);
        node->inst = instruction;
        helper.insert(pair<Instruction*,StaticAnalysis::ListNode*>(instruction,node));
        CFGNodes.push_back(node);
    }
}

So, my question is:
Would this be possible also for a flow graph? Or a symbol table is needed to construct one?


texts: Why does a Turing Machine need at least two states?

texts:
I read in some text book ( either ullman or peter linz) that a turing machine must have at least two states. I don't understand why?

For example if we want to build a Turing Machine for the empty language then we can start in state $q_o$ (accept state). We will define only one transition for epsilon on which the input would be accepted. However if the input is something else then since we have not defined any transition we would enter dead configuration.

what's the problem with this approach?


texts:
For example, I have an NFA $A_n$ with alphabet $\Sigma = \{0, 1\}$.

The language recognized by this NFA is known to be $\{u1v\ |\ u, v \in \Sigma^*, |v| = n − 1\}$.

I was unable to get the answer on my own. What got me stuck was that there is a $1$ between $s$ and $q_1$, plus the $q_n$ toward $s$. I know without the edge $q_n \rightarrow s$, the answer should be $\{0,1\}^* \cdot 1 \cdot \{0,1\}^{n-1}$, which is exactly the solution our lecturer provides. Why doesn't the "go back to start" edge matter?


texts: How to check if my language is context-free can't seem to solve it using pumping lemma

texts:
I have a language and I am trying to see if it's context-free or not, by trying to use a pumping-lemma but I can't figure it out, been reading a lot of other posts but still struggling to apply it to my example

this is the language (sorry for using an image, i know how to write number exponents but i don't know how to write letters as exponents):

Thanks


texts: Multiple post-fix expressions for an in-fix expression

texts:
Today I was learning to convert post-fix expressions to in-fix expressions and vice versa. What I want to know is whether a post-fix expression can have more than one infix representations.

For example, if I consider the following in-fix expression:

A+B-D/X

I get these post-fix expressions:

ABDX/-+

and

AB+DX/-

I didn't use the stack table method for solving these. I did these conceptually and both these expressions evaluate to

A+B-D/X

post-fix expression. I even verified my result with this site and both the post-fix expressions evaluate to:

A+B-D/X


texts:
I know this question is posted many times, but i am still posting this because i have my own doubt which pulls me out to move forward to kruskal and prim's algorithm.So Please do help me out $-:$

Question

  Let $G=\left(V,E\right)$ be a be a connected, undirected graph with a real valued weight function $w$ defined on $E$.Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$.Let $\left(S,V-S\right)$ be any cut of $G$ that respects  $A$.Let $\left(u,v\right)$ be a light edge
    crossing $\left(S,V-S\right)$.Then, edge  $\left(u,v\right)$  is safe for $A$.

Terminologies Used

  we say that an edge $\left(u,v \right)$ crosses the cut if one of the endpoint is in $S$ and other in $V-S.$

  Safe edge is edge at each step that we can add in A without violating any invariant.

  we say that a Cut RESPECTS a set A of edges if no edge in A crosses the cut.

  we say that an edge is a light edge satisfying a given property if its weight is the minimum of any edge satisfying the property

MY Approach/Doubt

With the help of book, i am able to understand the proof as-:

We Assume that $T$ is a MST(Minimum Spanning tree) which do not have light edge $\left(u,v \right)$, if we can manage to construct another MST $T^{'}$which contains $\left(u,v \right)$ and have weight less than that of $T$, then we are done! i.e we have to prove that $w \left(T^{'}\right) \leq w \left(T\right)$

Consider the figure below

As MST $T$ will not contain $\left(u,v \right)$(given) ,there must be an edge that crosses the cut, otherwise it will be divided into 2 components.

Let that edge be $\left(x,y \right)$

Now let us construct the MST$T^{'}$ from $T$ by removing $\left(x,y \right)$ and adding $\left(u,v \right)$ given as-:

$$w \left(T^{'}\right)=w \left(T\right)-w \left(x,y\right)+w \left(u,v\right)
$$

$\Rightarrow \left(u,v \right) \leq  w \left(x,y\right)$ as $\left(u,v \right)$ is light edge

$\Rightarrow w(T^{'}) \leq w(T)$

My doubt is -:

  1.Is the above proof explained above correct?am i missing something?

  2.If the above proof is correct, then i have one issue .Issue is that after proving the above inequality $w(T^{'}) \leq w(T)$,the book says that
  $\left(u,v \right)$ is actually a safe edge for A,but is n't this contradictory?

I mean if $\left(u,v \right)$ is safe for $A$ ,then cut $\left(S,V-S\right)$
no longer respect $A$ because  $\left(u,v \right)$  is an cross edge .

please help me out !


texts: Why was primality test thought to be NP?

texts: To check if $n$ is prime, one only need to try dividing $n$ by numbers up to $\sqrt{n}$, meaning that the complexity would be $O(\sqrt{n})$. In my opinion, $O(\sqrt{n}) < O(n)$ so this simple algorithm is already P. But why did people think that primality test is NP, and were surprised by the AKS primality test?


texts: General question on approach to showing sample size required is $\Omega(\cdot)$

texts:
I was not able to find a similar question in the archives, so pardon this relatively elementary question if it has been asked before.

Let $E_n$ be some event that depends on the sample size $n$ and suppose we are looking for an upper bound on $n$ that guarantees $Pr(E_n)\geq 1-\varepsilon$ for some $\varepsilon\in(0,1)$.  For example, if we are flipping a biased coin that lands heads with probability $p>.5$ and we define the event $E_n = \{\text{# of heads}>\frac{n}{2}\}$ then we are looking for $n\in O(f(p))$ since the sample size will be a function of the parameter $p$.  One way I have seen this approached is to upper bound the probability of $E_n$ NOT occurring and then set this upper bound to be at most $\varepsilon$ and then solving such that we get $n\geq\text{ something involving } p$.  My interpretation of this is that it is sufficient to have $n$ this big to guarantee $Pr(E_n)\geq 1-\varepsilon$ which is why it is an upper bound.

My question then is this: if my interpretation above is correct, is there an analogous approach to showing a lower bound for $n$ i.e. $n\in\Omega(g(p))$?


texts: Are these sets of indices also index sets?

texts:
An index set is a set of all indices of some family of computably enumerable sets.  It is known that the empty set is an index set and that $K = \{e \mid e \in W_e\}$ is not an index set.

The following was an exam question I didn't manage to answer:

  Which of the following sets are index sets?

  1)  $\emptyset $

  2)  $K= \{ x \mid x \in W_x \}$

  3) $E = \{2,4,6,8, \dots \}$

  4) $\{ x \mid \phi_x = \phi_{x^2}\}$

I think:

It is known $K$ (i.e., the halting set) is not an index set so
(2) is ruled out.  I read on this on last page problem 4 that the set
of even numbers is an index set, so I'm not sure that (1) and (3) is
true!  But the answer sheet wrote just (1) is true.  I don't know what
is the definition of $E$ in (3) and not sure about (4).

Can anyone clarify me in order to better understand this challenging
 question?  Why are (3) and (4) not index sets?  I'm not familiar with
 notation (4), any description?


texts: Does every large enough string have repeats?

texts:
Let $\Sigma$ be some finite set of characters of fixed size. Let $\alpha$ be some string over $\Sigma$. We say that a nonempty substring $\beta$ of $\alpha$ is a repeat if $\beta = \gamma \gamma$ for some string $\gamma$.

Now, my question is whether the following holds:

  For every $\Sigma$, there exists some $n \in \mathbb{N}$ such that for every string $\alpha$ over $\Sigma$ of length at least $n$, $\alpha$ contains at least one repeat.

I've checked this over the binary alphabet, and this is quite easy for that case, but an alphabet of size 3 is already quite a bit harder to check, amd I'd like a proof for arbitrarily large grammars.

If the above conjecture is true, then I can (almost) remove the demand for inserting empty strings in my other question.


texts: Can there be two different left most derevations for a grammar?

texts:
Suppose there is a CFG with the rules

S--> Aa
A--> Bb
B--> A
B--> Epsilon

To my best understanding the left most derivation would go like this..

 S==> Aa ==>  Bba ==> Aba ==> Bbba ==> bba

or

 S==> Aa ==>  Bba ==> Aba ==> Bbba ==> Abba ==> Bbbba ==> bbba

or

 S==> Aa ==> Bba ==> ba

Of these which is the true left most derivation of the language? If it is true that all of them are valid left most derivations,why is it that many text book talk about left most derivations of a language rather than a final string??


texts: Number partitioning targeting ratio of subset sums and equal size

texts:
I've seen a number of questions and answers related to the partitioning problem of dividing a set into 2 subsets of equal size and sum that use greedy or dynamic programming solutions to get approximate answers. However, I am looking to split a set into 2 subsets of minimum difference in size but with a target ratio of sums.

I have tried variations of greedy algorithms that will work to minimize the largest difference of the two metrics at any point in the calculation, but this just results in a result that splits the difference between the two. I'm happy with an approximate solution since it needs to run in a reasonable amount of time.


texts: Usage of master theorem for solving recursions

texts:
I know that master theorem is used for the recurrence relations of the form:

T(n) = aT(n/b) + f(n)

But in my question, i am supposed to solve the following recurrence relation by using master theorem:

T(n) = 2T(n/7) + 5T(n/8) + n

Can i take f(n)=n and since f(n)=Θ(nlogba), i say T(n) is O(nlogn)? But if i do this, i neglect the fact that the relation must be of the form T(n) = aT(n/b) + f(n). What should i do? Thanks


texts: picking a word for pumping lemma for L = {a^n b^m c^n b^m a^n | m,n≥0}

texts:
If i have a language like $L = \{a^n b^m c^n b^m a^n \mid m,n\ge0\}$

when i pick a word for the language, would it be correct if i pick any of

these words: $w = a^k c^k$, $w = a^k b^m c^k $, $w = b^m  b^m$,   $w = b^m c^n b^m$.


texts:
The definition my professor gave us is: f(n) is O(g(n) for constant c > 0 and n0 ≥ 0 where all n ≥ n0 and f(n) ≤ cg(n). I was wondering what n0 and n are?

Example:
  for the function f(n) = an2+ bn + cn = (a+b+c)n2.
Assuming a,b,c were constants we can say: f(n) = O(n2) where f(n) ≤ cn2.

What am I actually looking and to make sure that n0 ≥ 0 where all n ≥ n0


texts: Algorithm for display nodes of a particular node based on in-degree and out-degree

texts:
Suppose we have following directed graph. When I click on say node $e$, it should make in-degree and out-degree of node $e$ and connected nodes red. As shown in Resulting Graph. My purpose is, when I click on any node of a directed graph it should tell me what nodes it is influencing(out-degree) and what are nodes which influenced it (in-degree).
I want to make an algorithm for it. I don't know how to make it.

Definition: For a directed graph $G=(V(G), E(G))$ and a vertex $x_1 \in V(G)$, the
Out-Degree of $x_1$ refers to the number of arcs incident from $x_1$. That is, the number of arcs directed away from the vertex $x_1$. The
In-Degree of $x_1$ refers to the number of arcs incident to $x_1$. That is, the number of arcs directed towards the vertex $x_1$.
From mathonline.wikidot.com:

Expected Result:

I want to make mathematical modeling for following pseudo code:

Click on node i (e in example).

look for in-degree relationship r and get nodes(node d in below example).

look for out-degree relationship r and get nodes (node b and f in example).

display the nodes visited    through relationship r including e (expected
result graph).


texts: Is an Event Counter essentially an integer version of Barrier?

texts:
Just like there exists binary and integer Semaphores, does the Event Counter play an integer version of a Barrier?

Event Counters are described in the paper

  Reed, DP; Kanodia, RK: Synchronization with eventcounts and sequencers. Commun. ACM 22(2):115-123, 1979, http://doi.acm.org/10.1145/359060.359076

There is an online versions of the paper here.


texts: Data structure for counting bits set on a table

texts:
I have a table that contains only bits. I would like to be able to do the following two queries:

SET any bit to 0 or 1;
GET the number of bits that are set to 1 from the beginning of the table up to a specifique index i.

Is there a data structure that is more efficient than a binary indexed tree, i.e. a Fenwick tree? A binary indexed tree performs both operations in $O(\log n)$ time, where $n$ is the number of elements.

For practical info, my tables are really large, containing up to millions of elements.


texts:
Based on following table, I have to show if there is any potential pipeline hazard in the following code segments:

X = R2 + Y
R4 = R2 + X
R1 = R2 + X
X = R3 + Y
Z = R1 + X

I've been a bit stuck in the problem involving instruction pipelining.

Any strategy about where to start according to the table?


texts: Algorithmic problem of regular, context-free, and recursively enumerable languages

texts:
Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free.
Are the following problems algorithmically decidable?

Is $L_1 \cap L_2 = L_3$?
Is $L_1 \cap L_3 = L_2$?

I think problem 1 is undecidable since $L_1 \cap L_2$ is a recursively enumerable language it can be expressed as a Turing machine and since $L_3$ is context free it can be expressed as a Grammar or Turing machine. Since we cannot determine the equivalence of two Turing machines, the problem is undecidable.
I think problem 2 is also undecidable for similar reasons, only the right hand side ($L_2$) is regular instead of context-free.
Am I correct?


texts: Can the sorting of a list be verified without comparing neighbors?

texts:
A $n$-item list can be verified as sorted by comparing every item to its neighbor. In my application, I will not be able to compare every item with its neighbor: instead, the comparisons will sometimes be between distant elements. Given that the list contains more than three items and also that comparison is the only supported operation, does there ever exist a "network" of comparisons that will prove that the list is sorted, but is missing at least one direct neighbor-to-neighbor comparison?

Formally, for a sequence of elements $e_i$, I have a set of pairs of indices $(j,k)$ for which I know whether $e_j > e_k$, $e_j = e_k$, or $e_j < e_k$. There exists a pair $(l,l+1)$ that is missing from the set of comparisons. Is it ever possible, then, to prove that the sequence is sorted?


texts:
I have the following question:
Given graph $G=(V,E)$ with given order on its vertices, I mean $v_1<v_2<...<v_n$ I need to find minimal colors ordered paining of the graph vertices s.t neighbor vertices don't have the same color, I mean:
$(v_1,v_2,...,v_j)$ - painted in fist color and non of them are neighbors.
$(v_{j+1},...,v_l)$ - painted in second color and non of them are neighbors. and so on.

The complexity needs to be $O(V+E)$. Anyone have an idea?


texts: Using Myhill-Nerode to prove a language is non-regular

texts:
I'm trying to prove

L={w∈{0,1}∗:w contains more 00 substrings than 11 substrings}

is a non regular language using Myhill-Nerode theorem.

I'm a bit lost and not sure what to do. Thanks


texts:
In class our professor showed us 3 methods for proving non-regularity:

Myhill–Nerode theorem
Pumping Lemma for regular languages
Proof of non-regularity, based on the Kolmogorov complexity

Now the first two, Myhill-Nerode theorem and Pumping lemma, I understood well and I was also able to do the exercises to the first two methods. But I did not understand the third one. The Definition of the third method is as follows:

Let $\ L \subseteq (\Sigma_{bool})^* $ be a regular language.
Let $\ L_x=\{ y \in (\Sigma_{bool})^* | xy\in L \} $ for every$\ x \in (\Sigma_{bool})^*$. Then there exists a constant $\ c$, such that for all $\ x,y \in (\Sigma_{bool})^* $
$\ K(y) \leq \lceil log_2(n+1)\rceil+c $
if $\ y $ is the n-th word in the language $\ L_x $.

Now I do not understand how to use this theorem to prove that a language is not regular, I don't really get the concept. We used the kolmogorov complexity before for determining the length of the shortest computer program of an object. How does one prove non-regularity with this theorem? And what is the thought behind it?
Thanks a lot!


texts: Expected weight of euclidean minimum spanning tree on a unit square

texts:
Suppose I randomly generate $n$ points from the unit square $[0,1]^2$, form a complete graph in which the weight of each edge is just the Euclidean distance between its endpoints, and compute the minimum spanning tree. I noticed empirically that the expected weight scales like $\sqrt{n}$. Using only back of the envelope arguments, how could I derive the $\sqrt{n}$ asymptotic behavior?

When I repeated the experiment in the unit cube $[0,1]^3$, the expected weight scaled like $n^{2/3}$, and when I repeated it on the unit hypercube $[0,1]^4$, the expected weight scaled like $n^{3/4}$. How could I derive this asymptotic behavior?


texts: Remove a vertex from a graph keeping shortest path distance same

texts: How could we delete an arbitrary vertex from a directed weighted graph without changing the shortest-path distance between any other pair of vertices? We are allowed to reweight the edges.


texts: Minimum distance of nodes from a set of two nodes

texts:
In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, which gives us $\mathcal{O}(V + E)$ running time.

Is there any better way to do this? possibly with one BFS?

EDIT: We can start two BFS from $w$ and $v$ simultaneously and one step at a time. First we find the nodes in distance 1 of the $w$ then the nodes in distance 1 of $v$ and then nodes at distance 2 of $w$ and so on. by the time there is no node in the queue of BFS of node $v$, we can end the search. any node which is first visited with $v$ BFS is closer to $v$ than $w$.

But again I suppose there is a more efficient way to do this.


texts: Louvain algorithm: self-loop weight is double?

texts: In the 2nd phase of the Louvain algorithm, self-loops are given by the sum of all the intra-community weights. I'm wondering from their own figure, why all of the self-loops seem to have 2w weights, rather than w. Note in the blue community for instance: 2 intra-community edges, self loop has weight 4.


texts: How do you prove a heuristic is admissible?

texts:
How does one prove that a suggested heuristic is admissible? Is this even possible?

For Example: Let's say I have the game Free Cell.
Rules: https://en.wikipedia.org/wiki/FreeCell

How can I prove that the number of cards not in the foundation plus every out of order card is an admissible heuristic?


texts: How do we guess the recurrence relation from the given equation

texts:
In this book introduction to algorithms , i have been reading about a method named substitution method to solve the recurrence, the recurrence equation is
\begin{equation}
T(n)=2 T(\lfloor n / 2\rfloor)+n
\end{equation}

the author guessed the solution was $O(n \log n)$ and proved it below, my question is how to make the guess? I wanted to know why it cant be $O(n^2)$? How do you guess them correctly at first?

\begin{aligned} T(n) & \leq 2(c\lfloor n / 2\rfloor \lg (\lfloor n / 2\rfloor))+n \\ & \leq c n \lg (n / 2)+n \\ &=c n \lg n-c n \lg 2+n \\ &=c n \lg n-c n+n \\ & \leq c n \lg n \end{aligned}


texts: Optimal root in shortest path tree (SPT)

texts:
I would like to find the "optimal" shortest path tree (SPT) in some undirected weighted graph. As "optimal" SPT, I mean so its maximal path from root to leaf is minimal from any other potential SPTs.

It is quite easy to find SPT from 1 root via Dijkstra's algorithm. So I can run Dijkstra from all vertices and find the "optimal" SPT and its root.

Is there any faster algorithm?


texts: Pseudo-polynomial time algorithm for NP-Complete Problems

texts:
For problems like Knapsack there is a pseudo-polynomial time algorithm and it is NP-complete. So we reduce every other problem in NP in polytime to Knapsack.

But why don't we have then a pseudo-polynomial time algorithm for all problems in NP?


texts: Enumerate over all halting Turing Machines?

texts:
I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the natural numbers and checking whether each number describes a syntactically well-defined TM.

I am wondering how it is possible to enumerate over all halting TMs. My intuition tells me that since the halting problem is undecidable, it should not be possible to filter an enumeration of all TM descriptions to only those TM descriptions which describe halting TMs.

Nevertheless, I recently came across a well-reputed Oded Goldreich and Bernd Meyer, Computational Indistinguishability: Algorithms vs Circuits, Theoretical Computer Science 191(1–2):215–218, 2998) that uses an enumeration of all halting Turing Machines (see Proposition 1, pg. 2). I'd appreciate any help in understanding this.


texts: If we are given an NFA and a DFA, can we determine if there exists a string accepted by the NFA and rejected by the DFA and vice-versa. What complexity class would these problems fall into?


texts:
$L = \{ w: |w| \bmod 3 \geq |w| \bmod 2 \}$

I know, when the length of strings is not $3, 9, 15, 21,\dots,$ they will be members of the given language but unable to write a grammar for this language.

Please confirm one more thing, that this given language is regular?


texts: Proof of Manna-Pnueli algorithm for mutual exclusion being incorrect

texts:
Suppose we have the Manna-Pnueli algorithm for mutual exclusion:

I was trying to find a sequence that violates mutual exclusion and I came up with this:

1. q1, q3; wantq=-1
2. p1
3. q4, q5; wantq=0
4. q1
5. p2; wantp=-1
6. p4
7. q3; wantq=-1
8. q4
9. p and q in critical section

Is my reasoning correct, supposing if is not atomic?

Also, were it atomic, how would I prove it to be correct? Should I just list all the possible combinations?


texts: How to evaluate is_empty for 2-tuple lists in Lambda calculus?

texts:
This question has been handled various ways, but let me show my case.

I want to find out, if the given list is empty with these constraints:

TRUE = (L a b . a)
FALSE = (L a b . b)
NIL = FALSE
ZERO = FALSE
ONE = (L x y . (x y))
TWO = (L x y . (x (x y)))

PAIR = (L a b s . (s a b))

EMPTY = (PAIR NIL NIL)
EMPTY? = (L l . (l FALSE TRUE))

a. (EMPTY? EMPTY) should give TRUE.

b. (EMPTY? (PAIR ZERO (PAIR ONE (PAIR TWO EMPTY)))) should give FALSE.

I've seen different versions for EMPTY? like (L l . (l (L _ , FALSE) TRUE)) and such, but none of them gives me correct resolution.

So I'd like to know, if there is something on the above definitions, that does not work. Also, to verify that one strategy works, I'd like to see reduction steps for finding out correct answers for a. and b. starting from these expanded forms:

a. (L l . (l (L a b . b) (L a b . a)) (L a b s . (s a b) (L a b . b) (L a b . b)))

b. (L l . (l (L a b . b) (L a b . a)) (L a b s . (s a b) (L a b . b) (L a b s . (s a b) (L x y . (x y)) (L a b s . (s a b) (L x y . (x (x y))) (L a b s . (s a b) (L a b . b) (L a b . b))))))


texts: Is $MIN_{TM}$ not in $\overline{RE\cup coRE}$

texts:
Given the language:

$MIN_{TM}$= $\{ \langle M,k\rangle: there\ exists\ a\ TM\ D\ s.t.\ L(M)=L(D)\ and\ D\ has\ less\ than\ k\ states \}$

I need to prove if this language is in $R$ or $RE-R$ or $coRE-R$ or $\overline{RE\cup coRE}$.

I suspect this language is in $\overline{RE\cup coRE}$
but I can't prove it. (I Tried using reduction but no help).


texts: Maximum Number of Edge Disjoint Paths of Length k in DAG

texts:
Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it?

I'd be interested if there are FPT algorithms as well, or even run time in O(n^k).

I'm aware that if there are no length restrictions and we're given two target nodes this is in P, using network flow.

It has some connections to Digraph Ordering (see Kenkre's recent paper) in terms of establishing upper bounds.

One way to begin to approach the problem is to define an LP which maximizes the sum of 0-1 path variables, and ensures no two paths given value 1 overlap. (If we're a little careful we can do this with polynomially many constraints) However, we have to round our solution to get anywhere.


texts:
Let say A and B are two decesion problems where A $\le$ B polinomial reduction is true.

Is this : A̅ $\le$ B̅ also true?

If so, can you show an exemple, if not why?


texts:
There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction.

I know that there are approaches that have been proven to not work, and there are probably more that have a history of failing. There also seem to be so-called barriers that many proof attemps fail to overcome.

We want to avoid investigating into dead-ends, so what are they?


texts: What is the proof for the lemma "For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge"?

texts:
For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds such a tree for a graph. A representant pair of nodes is defined as follows: if $R$ and $S$ are two components of the Gomory-Hu tree, and there is an edge $e$ between them, then the nodes $r \in R$ and $s \in S$ are representants if the weight of the edge $(r,s)$ is the same as the weight of $e$.

I have to learn not only the algorithm, but also all the lemmas needed to prove that it works. For this specific lemma, there is a proof given in my learning materials, but I am afraid I don't understand how it works.

It starts by picking two components of the Gomory-Hu tree, $A$ and $B$, with an edge $h$ between them, $a \in A$ and $b \in B$ being the representants. In the next iteration, nodes $x$ and $y$ in $A$ are picked, and a new minimal $(x,y)$-cut is calculated (dividing $A$ into the subsets $X$ and $Y$), such that now $h$ connects $X$ and $B$. If $a \in X$, then $a$ and $b$ are still representants. But if $a \in Y$, the proof claims that $x$ and $b$ are the new representants of $h$.

For this, it states that

  The cut which created $h$ divides $x$ and $b$. From that, it follows that $f(x,b) \le f(a,b)$.

[It uses $f(a,b)$ to denote the flow in the minimal cut between nodes $a$ and $b$.] Then it goes on to prove that also $f(x,b) \ge f(a,b)$. And then the two flows must be equal, so the flow between $x$ and $b$ is the same as the flow in the minimal $(a,b)$-cut, so $x$ and $b$ are representants.

But as I understand the algorithm, the cut which created $h$ was a minimal cut between the nodes $a$ and $b$. The node $x$ wasn't even a special node at the time the graph was divided into components $A$ and B$.$ Yes, this cut happens to divide $x$ and $b$ too, but there is no guarantee that it is the minimal cut between $x$ and $b$ (this is exactly what we are trying to prove here). So I think that we can follow that $f(x,b) \ge f(a,b)$, but not that $f(x,b) \le f(a,b)$. I suspect that there is an error in my reasoning and not in the reasoning of the prof who wrote the learning materials, but where is it?

And if there actually is an error in this proof, what is the correct proof?


texts: Length of distinguishing string for a DFA

texts: Is it possible for a $DFA$ which has $n$ states that, there exists two distinguishable states $p, q$ such that there exists a distinquishing string between $p$ and $q$ whose length is greater than $n$?


texts: Trying to simplify a particular regular expression

texts:
The question is as follows

$$(a^* (ba)^* )^* (b+\epsilon) = (a+b)^* (b+\epsilon)\,.$$

But I am unable to solve this regex expression. My answer is as follows:

\begin{alignat*}{2}
(a^* + (ba)^* )^* ( b+\epsilon)\qquad &\text{(using property} (a^* b^*)^* = (a^*+b^*)^* = (a+b)^*\text{)}\\
=(a+ ba)^* ( b+\epsilon)\qquad &\text{(using the above again)}
\end{alignat*}

This is my final answer but it is not as stated on the right side of the proof. So can you tell where am I doing wrong? Is my proof correct?


texts: Computing the number of bits of a large power of integer

texts:
Given two integers $x$ and $n$ in binary representation, what is the complexity of computing the bit-size of $x^n$?

One way to do so is to compute $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor n\log_2(x)\rfloor$ by computing an approximation of $\log_2(x)$ with sufficient precision. It appears that computing $\log_2(x)$ with $k$ bits of precisions can be done in $O(M(k)\log k)$ where $M(k)$ is the time needed to compute the product of two integers of length $k$. This yields a (not specially simple) algorithm of complexity approximately $O(s\log^2 s)$ if $s$ is a bound on the bitsize of both $x$ and $n$ (if I made no error).

Can we beat $O(s\log^2(s))$ where $s$ is the size of $x$ and $n$ (in the case where they have comparable sizes)? Is there a simple algorithm to get this complexity or better?

Note: I am interested in the complexity in a theoretical model such as Turing machines.


texts: Paint the balls: what patterns can be painted?

texts:
You are given a number $k$ which specifies the number of consecutive balls you can paint in a go. You are given a string $S$ of length $l$. $l$ is the number of balls and each character in the string specifies the color of the $i^{th}$ ball. I want to know whether it is possible to color all the balls in the given pattern.

e.g.,
$S=rrggg$,
$l=5$,
$k=3$

We can color this pattern in two operations. As a first step we paint first three balls in red color and in the second step last three balls in green. Hence the answer should be $2$.

I conjecture that we can always generate a pattern provided that there's at least one consecutive sequence that has same color and $l \ge k$. I've formed this conjecture using various sample tests but there's no concrete proof that I could produce.  Is the conjecture true?  Can you prove it?

If this can be proved logically, it's easier to code the solution of the above problem. I'd like to see the proof of the conjecture that it's always possible to produce the pattern if there's at least one consecutive sequence that has same color and $l \ge k$.


texts: Proof of inequality $\lceil x \rceil \le x+1$

texts:
I went through the Master Theorum extension for floors and ceiling section 4.6.2 in the book Introduction to Algorithms
It had the following statement:

Using the inequality $\lceil x \rceil \le x+1$

But I haven't seen the inequality anywhere and could not understand the verifiability of inequality.
Instead the Chapter Floors and ceilings defined floors and ceilings as:
$$x-1 \lt \lfloor x \rfloor \le x \le \lceil x \rceil \lt x+1 $$
Please clear my doubt over this.
On how to use this identity and which identity to be considered when because both of them define completely different inequalities.
Thank you.


texts: How to find (real-valued) roots of matrix polynomial

texts:
Assume you have a fixed ($d=O(1)$ for that matter) degree matrix polynomial
$$P(X)=A_0+A_1\cdot X+A_2\cdot X^2+\ldots+A_dX^d$$

Where $A_0,A_1,\ldots A_d\in\mathbb N^{n\times n}$ are given as input. Also given is some constant $\epsilon$.

  Can we find a matrix $X_0\in \mathbb R^{n\times n}$ such that $||P(X)||<\epsilon$, or assert such does not exist?

  What is the complexity of such algorithm?

There has been a lot of work of numerically finding (approximate) roots of polynomials over the reals, is there an equivalent to matrix polynomials?

For example, if $P(X)=-I+X^2$, then a solution could be $$X=
 \left( \begin{array}{ccc}
1 & 0 \\
2015 & -1 \\
\end{array} \right) $$


texts: Why is ARP needed in a host - router system if the router already has list of addresses it assigned using dhcp?

texts:
The hosts are assigned IP address by the router using dhcp. So, the router has a list (mac addresses) of all the hosts that are directly connected to it as well their ip addresses.
Now if a packet comes from outside, the router must be able to find the destination mac address from its logs. Then what is the need to use ARP in such a case (hosts connected to router)?

The only time I see an use of ARP is when router has to find new routers. Using ARP allows it to find new routers as well as to force a more rigid use of longest matching address method if needed. However what is the use of ARP during "router to host" packet transfer?


texts:
Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped:

Designate $G = (V, E)$ as an undirected graph that has at least two vertices. Every edge $(e)$ on this graph has capacity $c_e$. Pick two arbitrary vertices from $G$ and label them $s$ and $t$ respectively.
Now, we'll let $P*$ be the set of $s-t$ paths in the graph, and let $C*$ be the set of $s-t$ cuts -- meaning, $C*$ refers to the subset of edges in $G$ that constitute all possible $s-t$ cuts.
Demonstrate that the following equality is true:
$\max_{P\in P*} \min_{e \in P}c_e = \min_{C \in C*}\max_{e \in C}c_e$

My issue: I'm having trouble parsing the above equation. The LHS appears to be describing the longest(?) of all possible s-t paths, and the edge with the minimum capacity along that path. The RHS appears to be describing the minimum number of edges(?) possible in a subset of edges constituting an s-t cut, and the edge with the max. capacity within that subset? I'm frankly not even sure whether the above equation is meant to involve a multiplication.
Still, I figure there must be a way to parse and understand the equation correctly such that the equality would always hold, and that it can be demonstrated as such. I'd appreciate any help in this matter.


texts: How can I efficiently generate the shortest list of arguments for the range() function that will generate a given list of integers?

texts:
I ran into an interesting problem at work when trying to generate the inputs for an API given the expected output. I've tried to formalize and anonymize the problem below. I've been trying to design a fast algorithm that works here but I'm a little stuck. Thanks in advance for the help! I'm not an experienced question writer so please feel free to edit this to make it clearer. I'll do my best to answer any clarifying questions.

Background

In python 2.7, the range function takes 3 arguments (start, stop, and step) and returns a list of integers.

  The full form returns a list of plain integers [start, start + step,
  start + 2 * step, ...]. If step is positive, the last element is the largest start + i * step less than stop; if step is negative, the last element is the smallest start + i * step greater than stop.

Documentation

Examples

>>> range(0, 30, 5)
[0, 5, 10, 15, 20, 25]
>>> range(0, 10, 3)
[0, 3, 6, 9]

Problem

Given a list of positive integers, I, generate a list of 3-tuples that when fed into the range() function that will generate the same set of integers as I. The answer list must be the minimum possible length. If more than one minimum length solution exists, return any of the solutions.

Examples

Input: [1, 2, 3]
Output: [(1, 4, 1)]

Input: [1, 2, 3, 5, 7, 9]
Output: [(1, 4, 1), (5, 10, 2)] or [(1, 10, 2), (2, 3, 1)]

Input: [1, 2, 4, 5, 6, 11, 12, 13]
Output: [(1, 3, 1), (4, 7, 1), (11, 14, 1)]


texts: Can we construct a binary tree with width and height Θ(n)?

texts:
we know this definition:

Given a binary tree, Width of a tree is maximum of widths of all levels.

Let us consider the below example tree.

     1
    /  \
   2    3
 /  \     \
4    5     8
          /  \
         6    7

For the above tree,
width of level 1 is 1,
width of level 2 is 2,
width of level 3 is 3
width of level 4 is 2.

So the maximum width of the tree is 3.

can we have a binary tree with Height $\Theta(n)$  and Width  $\Theta(n)$

My solution:
is YES. for example a binary tree with one-node:

     1

am i right?


texts: Minimum number of processes for the deadlock?

texts:
A system has 6 identical resources and $N$ processes competing for
them. Each process can request at most two requests. Which one of the
following values of $N$ could lead to a deadlock?

1
2
3
4

My attempt:
Deadlock free condition is:
$R  \geq P(N-1)+1 ,$
Where R is total number of resources,
P is the number of processes, and
N is the max need of resources by each process.
$6 \geq P(2-1) + 1$
$6 \geq P + 1$
$5 \geq P$
So, the number of processes should be less than $5$ for the deadlock free condition.
Hence, all options can not be deadlocked.

In this exercise problem the answer given option (4).

Can you explain it in a formal way, please?


texts: What does it mean if we disable K-rule in Agda?

texts:
TL;DR: Can I say, "K-rule in Agda enables people to match $ \forall a.a \equiv a $ with $ refl $"?

In https://agda.readthedocs.io/en/v2.5.4.1/language/without-k.html#without-k, K-rule is introduced as an implicit rule and it's defaultly enabled. If I understand it correctly, it means parameter of type $ \forall a.a \equiv a $ can be matched with $ refl $. If we disable K-rule, what will happen? What kind of codes is it going to prevent me writing? Because we can always construct $ \forall a . a \equiv a $, even without K, we can always get an instance of $ T $ by passing $ refl $ to any functions with type $ \forall a.a \equiv a \rightarrow T $.

Agda's doc has given me an example which indeed shows a circumstance that can only work with K:

K : {A : Set} {x : A} (P : x ≡ x → Set) →
    P refl → (x≡x : x ≡ x) → P x≡x
K P p refl = p

In this code, if we can pattern match x≡x with refl, P refl can be trivially equivalent to P x≡x (but without K, we can't).

So does that mean: "K enables people to match $ \forall a.a \equiv a $ with $ refl $"? I didn't find the answer on the Agda doc.

If we disable K, will the semantic of Agda's equality type (CH-ISO) change?


texts: Are there consequences for P ≠ NP that are unintuitive?

texts:
It's often regarded that the most intuitive answer to the question of $P$ vs $NP$ is that $P ≠ NP$. This is often illustrated with some consequences that would follow if $P = NP$ were true. Things like being able to find a proof for the Goldbach conjecture in polynomial time (if one exists), and so on.

However, are there some unintuitive consequences for the definitive statement that $P ≠ NP$?

A good example of what I mean is the axiom of choice. If you assume it, you can prove some pretty weird things, but if you assume its negation you can prove things that might be even weirder. The only way to avoid those things is not to assume anything at all. (Or assume one of its weaker variants.)

In this case, it's probably different because unless $P$ vs $NP$ is independent of ZFC, you can prove any statement if you assume the negation of the correct answer, so one can expect to get some strange consequences. But I hope my example got the point across.


texts: Easy way to prove that this algorithm eventually terminates

texts:
Introduction and notations:

Here is a new and simple version of my algorithm which seems to terminates (according to my experiments), and now I would like to prove that.

Let the notation $x_i \in \mathbb{R}^p$ refer to a $p$ dimensional data point (a vector). I have three sets A, B and C, such that $|A| = n$, $|B| = m$, $|C| = l$:
$$A = \{x_i | i = 1, .., n\}$$
$$B = \{x_j | j = n+1, .., n+m\}$$
$$C = \{x_u | u = n+m+1, .., n+m+l\}$$

Given $k \in \mathbb{N^*}$, let $d_{x_i}^A$ denote the mean Euclidean distance from $x_i$ to its $k$ nearest points in $A$; and $d_{x_i}^C$ denote the mean Euclidean distance from $x_i$ to its $k$ nearest points in $C$.

Algorithm:

I have the following algorithm which iteratively modifies the sets A and B by moving some selected elements from A to B and vis versa, and C remains always the same (do not change). To make it simple: the purpose of the algorithm is to better separate the sets $A$ and $B$ such that "the points of $B$ are more similar to those of a known fixed set $C$" and "the points of $A$ are finally self-similar and farther from those of $C$ and the final set $B$":

$A' = \{ x_i \in A \mid d_{x_i}^A > d_{x_i}^C \}$ ... (1)
$A = A \setminus A'$; $B = B \cup A'$ ... (2)
$B' = \{ x_i \in B \mid d_{x_i}^A < d_{x_i}^C$ } ... (3)
$B = B \setminus B'$; $A = A \cup B'$ ... (4)
Repeat (1), (2), (3), and (4) until: (no element moves from $A$ to $B$ or from $B$ to $A$, that is A' and B' become empty) or ($|A| \leq k$ or $|B| \leq k$)

The algorithm terminates in two cases:

when $|A|$ or $|B|$ becomes less than or equals to $k$
or the most standard case, when $A' = B' = \emptyset$, which means that no more elements moves between A and B.

Question:

How to prove that this algorithm eventually terminates ? I didn't found a convenient potential function which can be strictly minimized or maximized by the algorithm.
I have unsuccessfully tried some functions: the function $\sum_{x \in A} d_x^C + \sum_{x \in B} d_x^A$ but it is not increasing at each iteration. The function $\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^C$ but it is not decreasing at each iteration. The function $\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$ seems not to be decreasing at each iteration. The function $\sum_{x \in A} d_x^B + \sum_{x \in B} d_x^A$ seems not to be increasing at each iteration. So what is the convenient potential function which can be show to either increase or decrease at each iteration ? Or should we show that the function decreases but not at each iteration (after some iterations rather) ? How ?

Notes:

The $k$ nearest points to $x$ in a set $S$, means: the $k$ points
(others than $x$) in $S$, having the smallest Euclidean distance to
$x$. You can just take $k = 1$ to simplify the analysis.
I don't know if this may help or not, but I have the following
property for my initial sets $A, B, C$: initially $\forall x_i \in B,
   x_j \in A$, if $x_b \in C$ is the nearest point to $x_i$ and $x_a \in
   C$ is the nearest point to $x_j$ then always $distance(x_i, x_b) <
   distance(x_j, x_a)$. This intuitively means that points in $B$ are
closer to $C$ than points in $A$.
If that makes the analysis easier: it is totally possible to consider a slightly different version of the Algorithm where as soon as a point from $A$ should be moved to $B$, it is moved from $A$ to $B$ (without passing by $A'$), and vis versa for $B$.


texts:
microsoft.com has the ip address 23.96.52.53

Since the first number is $23$, this is class A.
Does this mean microsoft owns all the addresses from 23.0.0.0 to 23.255.255.255 ?