Characterising $(aa)^*$ in first order logic In my descriptive complexity class, we've been asked to find a formula that characterises the language $(aa)^*$ (over the alphabet $\{a\}$) with a first order formula over the language $\{<, P_a\}$.

This was the first class, so I will recall what we've learned to be sure that I understood. To a $L$-formula $\phi$ we associate a language $\mathcal L(\phi)$ which is the class of all $L$-structures in which $\phi$ is valid.

In my case, we then are looking for a $\{<, P_a\}$-formula for which words of even length are models. I guess I have to say in $\phi$ that $<$ is a total order, so that I can interpret the models as words, and that $\forall x, P_a(x)$ to say that all points are labelled as 'a'. But how to say that there has to be an even number of points in the model? The definition of having an even number of points seems recursive, so I get the impression that a formula for $(aa)^*$ should be of infinite length in first-order logic..

Short answer. There is no such first-order formula, you need a monadic second order formula.

Details. This can be proved directly using an Ehrenfeucht-FraÏssé games argument if you want to stay inside logic, but the real answer to your question is the conjunction of three results.

[1] Büchi (1960): A language is monadic second order expressible iff it is regular.
[2] McNaughton-Pappert (1971): A language is first-order expressible iff it is star-free.
Counter-free Automata. Research Monograph 65. With an appendix by William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9.
[3] Schützenberger (1965): A regular language is star-free if and only if its syntactic monoid is aperiodic.  On finite monoids having only trivial subgroups

[3] gives an algorithm to decide whether a given regular language is star-free (and hence, first-order expressible, by [2]). Now, the syntactic monoid of $(aa)^*$ is the cyclic group of order $2$, which is not aperiodic. To get a monadic second order formula, you need first to have first order "macros" to express $\min$, $\max$ and $+1$ and then the following second order formula will do the job
$$
  \exists X\ \forall x\ (\min \in X \wedge \max \notin X) \wedge (x \in X \leftrightarrow x+1 \notin X)
$$


Is this definition of $\alpha$-equivalence correct? I want to extend $\alpha$-equivalence to cover substitution.
That is, I will implement runSubst_Term : Subst -> Tm -> Tm and prove:
  Theorem runSubst_Term_main_property :
    forall sub : Subst,
    forall tm : Tm,
    AlphaSubst sub tm (runSubst_Term sub tm).

where the definitions of Subst, Tm, AlphaSubst are below.
But I don't sure that AlphaEquiv is a correct $\alpha$-equivalence relation.
So it would be appreciated if you could check that the definition is correct.
  Definition IVar : Set :=
    nat
  .
  Inductive Tm : Set :=
  | Var : forall iv : IVar, Tm
  | App : forall tm1 : Tm, forall tm2 : Tm, Tm
  | Abs : forall iv : IVar, forall tm1 : Tm, Tm
  .
  Fixpoint runSubst_Var (sub : Subst) (iv0 : IVar) : Tm :=
    match sub with
    | [] => Var iv0
    | (iv, tm) :: sub' =>
      if Nat.eq_dec iv iv0
      then tm
      else runSubst_Var sub' iv0
    end
  .
  Inductive AlphaSubst : Subst -> Tm -> Tm -> Prop :=
  | AlphaSubstVar :
    forall sub : Subst,
    forall iv : IVar,
    forall tm : Tm,
    runSubst_Var sub iv = tm ->
    AlphaSubst sub (Var iv) tm
  | AlphaSubstApp :
    forall sub : Subst,
    forall tm1_1 : Tm,
    forall tm1_2 : Tm,
    forall tm2_1 : Tm,
    forall tm2_2 : Tm,
    AlphaSubst sub tm1_1 tm2_1 ->
    AlphaSubst sub tm1_2 tm2_2 ->
    AlphaSubst sub (App tm1_1 tm1_2) (App tm2_1 tm2_2)
  | AlphaSubstAbs :
    forall sub : Subst,
    forall iv1 : IVar,
    forall iv2 : IVar,
    forall tm1 : Tm,
    forall tm2 : Tm,
    AlphaSubst ((iv1, Var iv2) :: sub) tm1 tm2 ->
    AlphaSubst sub (Abs iv1 tm1) (Abs iv2 tm2)
  .
  Definition AlphaEquiv (tm1 : Tm) (tm2 : Tm) : Prop :=
    AlphaSubst [] tm1 tm2
  .

The approach itself makes sense, but the relationship with runSubst_Var probably makes proofs more difficult.
I think it's better to work on De Bruijn indices for alpha-equivalent semantics.


Calculating unbalanced binary trees Two-part question:

Is there any more specific name than "unbalanced binary tree" to describe the tree below? The distinguishing characteristics are:

i. The root node and left children must have either 0 or 2 children.

ii. Right children must have 0 children.

iii. All nodes must be positive non-zero integers.

iv. Any node with children must equal the sum of its children.

Given the value of the root node (in this case, 77), is there a standard algorithm to efficiently calculate all possible trees of this type?

i.e. (77, 76, 1), ..., (77, 1, 76), (77, (76, 75, 1), 1), etc.

         77
        /  \
       68   9
      /  \
     48   20
    /   \
   47    1
  /  \
 42   5

It is a special caterpillar.
Let $d(i)$ be the number of such trees with root $i$. We have $d(1)=1$; and $d(n)=\sum_{i=1}^{n-1}d(i)+1$, where "plus 1" is for the case of no children and $d(i)$ in sigma for the case that the left child is $i$.
One can easily compute $d(n)$ in $O(n)$ time using a simple loop. Or it is not hard to solve the recurrence relation and get $d(i)=2^{i-1}$ for $i\geq 1$.


Proving that no 2-state DFA decides the language A = {x ∈ {0, 1}* | bnum(x) is divisible by 3} I am doing a problem where I need to prove that no 2-state DFA decides the language
A = {x ∈ {0, 1}*| bnum(x) is divisible by 3}.

It's seems pretty obvious at first, because aren't there only 4 DFA's with two states that define it? Also, since x is divisible by 3, the DFA would need to have 3 states to define the remainder values.

So I feel like I have a good understanding of the problem, but how do I more formally prove the statement? Any help is appreciated.

Remainder values is indeed the clue! Obviously the strings $1$ and $10$ cannot end in a final state as they represent number 1 and 2 respectively. But can they end in the same state?


Lower bound for finding majority element in a sorted array Suppose $A$ is a sorted array with $n$ elements.  I want to know whether we can determine if there are majority elements in $A$ with time complexity $O(1)$.

Recall that a majority element of $A$ is an element which appears over $n/2$ times in $A$.

I can find a $O(\log(n))$ algorithm to solve this problem. But I'm not sure whether this can be done in $O(1)$. I was trying to use the adversary method, but I don't know how to construct it.

Any algorithm would need $\Omega(\log n)$ queries.

To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. We assume that $x$ appears in $A[m],A[m+1],\dots,A[M]$, and that $k\triangleq\min\{a, m-1, n-M\}$.

Notice that in these notations we are looking to bound $f(\lfloor n/2 \rfloor)$.

Claim: $f(k)\ge \log k$.

Proof:

Consider the first query made by the algorithm.

If it was done within radius $k/2$ of the interval (i.e. somewhere in $[m-k/2,\ldots,M+k/2]$), and found the median at the spot, then we still need at least $f(k/2)$ queries to decide the problem.

If it was done outside that radius, consider the case where the queried cell did not contain the median. Once again, this leaves us with at least $f(k/2)$ queries to be made.

Continue with induction and you get the $\Omega(\log n)$ bound.


ILP runtime seems to be linear? I have a variation the shortest path problem, formulated as an ILP.
The system model is as follows:

There is a connected digraph consisting of 20 nodes, with each link having an associated weight delay which is a float. The graph is modeled as a python networkx object as follows:

g = nx.DiGraph(nx.barabasi_albert_graph(20, 2))
for u, v in g.edges:
    g[u][v]['delay'] = random.uniform(50, 1000)  # uS

There are multiple source-destination pairs and each pair has an associated 'demand' in terms of delay. The problem is modeled in python PuLP and solved using Gurobi solver.

# get cost
delay_d = nx.get_edge_attributes(self.graph, 'delay')

# get links
links = []
for i, j in self.graph.edges:
    links.append((i, j))

# instantiate the problem
prob = pulp.LpProblem("Shortest Path Problem", pulp.LpMinimize)

# create binary variables to state a link is chosen on shortest path
var_dict = {}
for flow_name in self.list_of_flows:
    for (i, j) in links:
        var = pulp.LpVariable('x_(%s,%s)_%s' % (i, j, flow_name), cat=pulp.LpBinary)
        var_dict[(i, j, flow_name)] = var

# create slack variables for every flow
delay_slack = {}
for flow_name in self.list_of_flows:
    delay_slack[flow_name] = pulp.LpVariable('d_%s' % flow_name, lowBound=0.0, cat=pulp.LpContinuous)

# formulate the objective
prob += pulp.lpSum([pulp.lpSum([delay_d[(i, j)] * var_dict[(i, j, flow_name)] for (i, j) in links])
                    for flow_name in self.list_of_flows ]) \
        + pulp.lpSum([1000 * delay_slack[flow_name] for flow_name in self.list_of_flows])

# formulate the constraints
for flow_name, flow in self.list_of_flows.items():
    # conservation of flow constraints
    for node in self.graph.nodes:
        if node == flow['source']:
            prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                    pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == 1
        elif node == flow['target']:
            prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                    pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == -1
        else:
            prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                    pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == 0

    # delay constraint
    prob += pulp.lpSum([var_dict[(i, j, flow_name)] * delay_d[(i, j)]
                        for (i, j) in links]) - delay_slack[flow_name] <= flow['qos']['delay']

# solve the optimization problem
prob.solve(pulp.GUROBI_CMD(msg=0))

There are no issues with the solution and correct results are obtained.
However, when I calculated the runtime, the results seem to be linear.

Now, I know that if an ILP satisfies the property of unimodularity, then the LP relaxation gives integer solution. Thus such an ILP can be solved in polynomial time using methods such as simplex.

However, if we look at the delay constraints, the coefficients of LHS are not integers, nor is the RHS integer. Thus it seems unimodularity property is not satisfied. Hence, shouldn't the runtime be exponential?

Can anyone explain why the runtime graph is linear?

I will try to answer to your question with an example.
Consider the following time complexity: $f(n)=2^\frac{n}{1000}$.

It is clearly exponential in $n$, but look at the plot.

For $n \in [0,80]$:

From this perspective it looks constant, right?

For $n \in [0, 1.5 \cdot 10^4]$:

From this perspective everything changes.

What I want to show, is that inferring the complexity just looking at the runtime with different inputs size is not possibile.


How expensive is it to verify that a gate is universal? I know that a NAND gate is considered universal because we can use it to implement an AND, OR, and NOT gate.
Given an arbitrary gate, or set of gates, how many operations would it take to verify if these gates are universal (by brute force), and does there exist a more efficient way to do this? How expensive is this in general?
With the example of the NAND gate we can construct a NOT, AND, and OR, pretty easily, but is there a systematic way to do this?
More specifically, assume we are given $n$ two input, one output gates, where the gates are specified as a truth table.
Is there a way to also generalize this to, given $n$ gates, in which all the gates take $m$ inputs and 1 output, how expensive would this be?

The problem is actually much more tractable than the other answers suggest.
Specifically, for your first problem

assume we are given  two input, one output gates, where the gates are specified as a truth table.

I give an $O(n)$ solution. The problem is more difficult in the generalization to where each gate has $m$ inputs, where the solution below will be $O(n \cdot m \cdot 2^m)$. But this is in principle kind of unavoidable, because it actually takes $n \cdot 2^m$ just to write out all the truth tables. In other words, if you don't spend this amount of time, you won't even be able to test all possible inputs to your existing gates, so it makes sense you wouldn't be able to determine universality. It's possible the additional $O(m)$ factor can be avoided, though it's not very significant compared to the $2^m$.
I will give a solution that:

Either proves universality or disproves universality, in a finite amount of time; and
Works for any number of gates.

The solution actually falls out of a very beautiful and lesser-known theorem of universal algebra due to Emil Post in 1941. Your problem is, given a set of gates, to determine if they are Functionally Complete.
In what follows, we assume that constants are not allowed; but if you prefer to allow the constants $1$ and $0$, then just add constant gates (with 0 inputs) that output $1$ and $0$, respectively.
Theorem (Post, 1941). A set of gates is NOT functionally complete if and only if one of the following five conditions is satisfied:

All of the gates are monotone. This means that if any of the inputs change from false to true, the output will only change from false to true and never from true to false (if it changes at all). For example, AND and OR are monotone; NAND, NOR, and NOT are not.

All of the gates are affine. This means that the output depends in a "linear" way on the input; it means that the gate is really just an XOR of some of the input variables. NOT is also affine.

All of the gates are self-dual. This means that switching false and true in all inputs always switches false and true in the output. For example, NOT is self-dual as is the MAJORITY gate, but AND, XOR, and OR aren't. Note also that if you allow constant inputs (1 and 0), then these are not self-dual and so this criterion is not satisfied.

All of the gates are  truth-preserving. This means that if all inputs are true, the output is true. For example, the constant 1 is truth-preserving, as is AND, but 0 is not.

All of the gates are false-preserving. This means if all inputs are false, the output is false.

We can use this theorem to derive the following $O(n \cdot m \cdot 2^m)$ decision procedure for deciding whether $n$ gates, with $m$ inputs each, are expressively complete.

First run through all the gates, and check if they are truth-preserving or false-preserving. This can be done in $O(1)$ per gate because we only have to check two inputs (all false, and all true). If all gates are truth-preserving or all are false-preserving, return false.

Next run through all gates and check if they are self-dual. This takes $O(2^m)$ per gate because we need to check, for each input, how it compares to the negated input where true and false are switched. If all gates are self-dual, return false.

Next we run through all gates and check if they are monotone. This requires checking for each of the $2^m$ possible inputs, what happens if any of the $m$ input wires switch from false to true, so it takes $m \cdot 2^m$. If all gates are monotone, return false.

Finally, we run through all gates to check if they are affine. Iterate through each of the $m$ input wires. For each wire, then try all possibilities for all the other $(m-1)$ wires, with that wire both true and false. If the gate is affine, you should see that irrespective of the other wires, either this wire always has no effect on the output, or it always flips the output. If neither of these behaviors is observed for some input wire then the gate is not affine. If all gates are found to be affine, return false.

Otherwise, once all of these checks pass (there's at least one non-truth-preserving gate, at least one non-false-preserving gate, at least one non-monotone gate, at least one non-self-dual gate, and at least one non-affine gate), then return True.
Note: If you are allowing constant inputs 1 and 0, then modify the algorithm by removing the "self-dual", "truth-preserving", and "false-preserving" checks. So, all you have to do is check if all your gates are monotone and if all your gates are affine.

Finally, here are a couple of examples to illustrate the way the theorem works. First, for the NAND gate: NAND is special because it is not false-preserving, not truth-preserving, not monotone, not self-dual, and not affine. As a result, it alone is functionally complete. Another common example of a functionally complete set of gates is NOT and AND. In this case: NOT is not truth-preserving, false-preserving, and monotone, covering those three requirements; and AND is not self-dual or affine, covering the other two requirements. But if either AND or NOT is dropped, then not all five requirements are satisfied.


Max flow algorithm for floating-point weights and E~=10*V Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e.   O(V^3) algorithms take too much time, but O(E^2) algorithms are much more preferable. More specifically, you can assume V~=1M and E~=10M where M stands for millions.

Orlin's algorithm can solve max flow in sparse graphs in $O(|V| |E|)$ time.  See

Max flows in O(nm) time, or better.  James B. Orlin. STOC 2013.

You'll have to decide whether the potential speedup is worth the time to implement it, as I believe the algorithm is quite complex.  I don't know whether the algorithm is better in practice.

Perhaps someone else will have better suggestions for you.


Strings of infinite length? Suddenly a thought came to my mind and I thought of resolving it as follows.
We know that:
String is a finite sequence of symbols from an alphabet $\Sigma$

i.e. we cannot have an infinite sequence representing a string, which means there is no definition such as
$w = "abcabe...........$

which is unending

Now when we consider the definition of ${\Sigma}^*$, we see that the set is infinite, which implies that there could be strings having infinitely large length => which seems to sort of contradict the basic defintion of strings at a first glance.

But if we look into the matter closely then we shall see that for whatever value of length of the strings ($n$) we choose, we get a string of finite length, no matter however large $n$ is .

Is the way in which I resolved it correct or a more refined method of resolution exists?

Here is a simpler example. Consider the set $\mathbb{N}$ of natural numbers:
$$
\mathbb{N} = \{0, 1, 2, \ldots\}.
$$
The set $\mathbb{N}$ is infinite, but each number is finite.

In fact, your situation is very similar, since
$$
\Sigma^* = \bigcup_{n \in \mathbb{N}} \Sigma^n.
$$
Each of the sets $\Sigma^n$ is finite, yet the set $\Sigma^*$ is infinite.

Each word in each $\Sigma^n$ is finite, so each word in $\Sigma^*$ is finite.

Here is a related point.

Words in $\Sigma^n$ have bounded length, but the length of words in $\Sigma^*$ is unbounded. Yet the length of each word itself is finite.

Similarly, each number in $\mathbb{N}$ is finite, yet $\sup \mathbb{N} = \infty$.

Finally, let me say that words of infinite length are quite useful. The set $\Sigma^\omega$, known as the set of $\omega$-words, consists of all "one-way" infinite words. A word in $\Sigma^\omega$ is a mapping $w\colon \omega \to \Sigma$ ($\omega$ is another symbol for $\mathbb{N}$). We think of it as given by symbols $w_n \in \Sigma$ for all $n \in \mathbb{N}$.

Two-way infinite words form $\Sigma^\zeta$, where $\zeta$ is the same as the set $\mathbb{Z}$ of all integers.

More generally, you can consider $\Sigma^\alpha$ for every linear order $\alpha$.


Is every problem in NP? My friend and I were studying NP-hard problems and NP-completeness. I don't think we have understood the concept very well so I thought I would come here to solve our doubt.

To show that a given problem is in NP, we have to verify a solution to a given instance of the problem can be solved in polynomial time. We get this. What we wanted to know is that is by default then every existing problem is in NP until a solution for the problem is derived in polynomial time? Or is it that we have completely missed the concept?

There are plenty of problems where there is likely no way to verify a solution in polynomial time.

Amazingly, the problem "is p a prime number" is in NP due to some deep mathematical theorem that shows that for every prime number, there is a polynomial time proof that it is a prime number. (For many, many NP complete problems the part that there is a polynomial time proof is quite trivial).

A simple problem: Given an integer n, how many prime numbers p <= n are there? There are ways to calculate this in $O(n^{2/3})$ and possibly a bit faster (which is exponential in the problem size). But there seems to be no possible proof that is less time consuming then finding the solution from scratch. so no proof that doesn't take exponential time.

Here's a simple problem that I believe has an absurdly high time complexity: On the UK TV show "Countdown", the contestants are given six slightly random numbers, and another larger number, and are asked to form the larger number by combining any or all of the six random numbers using + - * and /. That's the simplest problem. The next, harder problem: Given six integers and some larger n, can all integers 1 ≤ i ≤ n be formed that way? The next, harder problem: Given n, are there six numbers a1 to a6 so that all integers ≤ n can be formed by combing a1 to a6?

And the final problem (as a decision problem): Given an integer k ≥ 1, and a larger integer n ≥ 1, are there k integers $a_1$ to $a_k$ such that all integers 1 ≤ k ≤ n can be formed by combining any or all of $a_1$ to $a_k$ using +, -, *, / ?


does godel's incompleteness theorem shed any light on dynamic vs typed languages? I'm clojure user myself. I'm trying really hard to learn haskell and to better understand the type system. However, I feel that trying to 'type' everything is quite restrictive when the problem or the data is less defined.

I intuitively feel that godel's incompleteness theorem offers some insight into the typed/untyped debate. What are some simple problems that may trip up the typing system but not untyped ones?

According to http://en.wikipedia.org/wiki/Type_theory. "The types of type theory were invented by Bertrand Russell in response to his discovery that Gottlob Frege's version of naive set theory was afflicted with Russell's paradox. This theory of types features prominently in Whitehead and Russell's Principia Mathematica. It avoids Russell's paradox by first creating a hierarchy of types, then assigning each mathematical (and possibly other) entity to a type. Objects of a given type are built exclusively from objects of preceding types (those lower in the hierarchy), thus preventing loops."

Godel's theorem invalidated Principia Mathematica. What consequence does it have on Type Theory.

Haskell is Turing-complete.  That means, any computation that can be expressed in Clojure, can also be expressed in Haskell (and vice versa).  Consequently, there is no difference in the expressibility of the two languages.  This remains true despite the type system.

I'm not aware of any insight that Godel's incompleteness theorem offers into whether statically typed languages are "better" than untyped languages (for some unspecified definition of "better").


Steps to create a heuristic for solving a problem I am completely new to AI and doing self-learning to acquire this knowledge.
I went through the different available search algorithm like BFS, DFS and A* but something that I can't understand is a heuristic function that needs to be embedded in these algorithms. I am fine with algorithms but I don't know how we find a good heuristic function for every problem. Is there any steps that needs to be take to achieve a heuristic?

Any comment would greatly appreciated.

There is no general method. Like all mathematics, algorithm design, programming, etc., coming up with heuristics is a creative act which requires you to use your intelligence and understanding of the problem domain.


fastest way to identify "singular row" of a matrix Suppose I have a matrix that I know to be singular. This means that there is at least one row in the matrix which is a linear combination of the other rows. What is the fastest way to identify which row that is or which rows they are?
I'm aware that the solution to this problem is not unique in general. The goal is to determine a set of rows which, if removed, leave only linearly independent rows. Then, more linearly independent rows can be added to get a non-singular matrix. Obviously I'm leaving out a bit of context regarding why I would be doing this, but I believe I have included everything relevant to the question.
My thinking is basically to attempt to attempt Gram Schmitt and just mark whatever step returns a zero vector. I doubt there's a faster approach than this, but suspect this problem has been studied to the point that a definitive answer exists.
Edit: To be clear, I only want to find a minimal set of rows such that, if they are removed, I get back a linearly independent set of vectors.
Also, let me give an example of the algorithm that I am proposing. I'm using an example given by nir shahar but slightly modified.
Suppose I have a matrix with rows (1, 0, 0), (0, 1, 0), (1, 0, 0)
The Gram Schmitt algorithm returns
first:  (1, 0, 0)
second: (0, 1, 0) - 0 * (1, 0, 0)
third:  (1, 0, 0) - 1 * (1, 0, 0) - 0 * (0, 1, 0)
I'm not actually returning this set of vectors. All I care about is the fact that the third step returns the zero vector. So, I flag the third row as being a "problem."

This is not an answer, but a response to this comment.
Assume that $A$ is the matrix which columns are the rows that we want to test for linear independence. I am putting them are columns for no other reason than personal comfort.
Doing the row transformations required in Gaussian elimination correspond to multiplying $A$ from the left by some elementary matrices. Assume that $T$ is the product of all elementary matrices corresponding to the row transformations needed to put $A$ in echelon form. So, $TA$ is is echelon form.
If each column has an echelon then the system $TAx=0$, with $x$ a column vector of the right size, has only the solution $x=0$. Since $T$ is invertible, we have that $Ax=0$ has only the solution $x=0$. Since $Ax$ is nothing else than a linear combination of the columns of $A$ using the components of $x$ as coefficients, what we got is that the columns of $A$ are linearly independent.
Now assume that some columns of $TA$ don't have echelons. Let's call these the dependent columns. You can give any values you want to the components of $x$ corresponding to the positions of the dependent columns and then solve the resulting system $TAx=0$ for the remaining components, by backward substitution. In particular we can put non-zero values to the components of $x$ corresponding to the dependent columns of $TA$. This gives you a solution of $TAx=0$. Since $T$ is invertible, it is also a solution of $Ax=0$. For this $x$ the expression $Ax$ is a linear combination of the columns of $A$ that is equal to zero and the coefficients of the dependent columns are non-zero. So, the equation $Ax=0$ expresses each of the dependent columns in terms of all the other columns.
So, the dependent columns are linearly dependent of the columns with echelon in them (independent columns).


Solving $T(n)=4T(n/4) +(n/\log n)^2$ Solving $T(n)=4T(n/4) +(n/\log n)^2$.

When I looked at the question I thought that this can be solved by the 3rd case of the master theorem since $f(n)$ is polynomially larger than $n^{\log_ba
}=n.$ But someone said that this is not polynomially larger since it has $(\log n)^2$ in the denominator.

Then I tried the substitution method.
I have found an upper bound of $n^2$ and a lower bound of $n\log n$ but I am unable to proceed any further.

I want a theta bound.


Trying to find Worst Case complexity I have to find computational complexity of an expression for Euclidean distance

d(x,y)= {(x1-x2)^2 + (y1-y2)^2}^1/2

But I have certain confusion because of which I am unable to proceed. Firstly there are two variables. Secondly since there is a root ,what will be  its effect? If there were no roots, I can understand its worst case complexity would have been O(n^2).

I will really appreciate if someone can enlighten me in this regard
        Thanks in advance for your spending valuable time!

Update

I assume that my program will run on abstract machine RAM.

The computational complexity depends on what you want to measure. If you you're doing this computation on a common computer with floating point arithmetic, then you can estimate it mi $O(1)$, because every floating point operation (addition, multiplication and square root) is in $O(1)$.

If you use fixed point arithmetic for $n$-bit numbers, then addition can be done in $O(n)$, multiplication in $O(n^2)$, and square root in $O(n^2)$ steps (Note: For multiplication and addition are existing better bounds). Putting this together, you will add two $O(n)$-bit numbers and take the square root of the result which gives $O(n^2)$ steps.

As you can see, the runtime depends on the arithmetic used, and arithmetic determines what $n$ means. If you use $n$-bit complex number in a $n$ dimensional vector space (where $x^2$ denotes the scalar product), you probably will get other estimates.


Task Distribution Algorithm Different machine has different efficiency on different tasks, like:

| T/M | M1  | M2  | M3  |
| T1  | a11 | a21 | a31 |
| T2  | a12 | a22 | a32 |
| T3  | a13 | a23 | a33 |

So, Machine $M_1$ needs $a_{11}$ time on finishing Task $T_1$.

Each machine can process one task everytime. Each single task cannot be splited up. How to find the min finishing time for all tasks in sum? (finishing time of each task include its waiting time and processing time).

I only has a awful enumerate algorithm for this, enumerate all possible solution and find out the min one. That costs $O(n^n)$.

Is there any optimized algorithm for this question?

The problem is also called scheduling unrelated machines and as observed in the comments, it is NP-hard.

If you really want an optimal solution, I recommend to use an integer linear programming solver, such as lp_solve, SYMPHONY or GLPK. The problem can be formulated as an integer linear program as follows:

$$
\sum_{i=1}^m x_{ij}=1, \qquad j = 1,...,n
$$
$$
\sum_{j=1}^n p_{ij} x_{ij} \le T, \qquad i = 1, ..., m
$$
$$
x_{ij}=0, \qquad \text{if} p_{ij}>T
$$
$$
x_{ij} \in \{0,1\}, \qquad \forall i, j.
$$

Here $m$ is the number of machines, $n$ the number of jobs, $p_{ij}$ the time required to run job $j$ on machine $i$, and the variable $x_{ij}$ stands for 1 or 0 depending whether the job $j$ will be assigned to machine $i$ or not. The number $T$ is a parameter: if the integer linear system can be satisfied, then there is an assignment of jobs to machines that has overall finishing time (makespan) at most $T$. For any given $T$, the integer linear programming solver will tell you if the system is feasible (and if so, what are the values $x_{ij}$). Then you can find the best value of $T$ (and the corresponding $x_{ij}$s) by running a simple binary search.


Relationship between depth and the vertical displacement of the object between two frames I am trying to find the relation between the vertical displacement of an object to the depth of the object.

Say, there is an object in an image and as the center of gravity of this object moves vertically upwards, we know that it is moving away from the camera.

We know at the same time, that the dimension of the image would reduce because the object is moving away from the camera.

So, two things are happenning - 1 . the objects center of gravity is moving up vertically and 2. the object dimension is decreasing because the object is moving away from the camera.

Is it possible to find a relationship between "the vertical displacement of the object from one frame to another frame" and "the distance  of the object from the camera from one frame to another frame" ?

Yes.  This all comes down to some simple trigonometry.  An object that is at horizontal distance $x$ and vertical distance $y$ from the camera's viewing direction will be at angle $\tan^{-1} (y/x)$ from the viewing direction, and the distance to the object will be the length of the hypotenuse, i.e., $\sqrt{x^2+y^2}$ (draw a picture).

So, if the object starts at height $y_1$ and then moves upward to height $y_2$, the distance to the object will increase from $\sqrt{x^2+y_1^2}$ to  $\sqrt{x^2+y_2^2}$.  Now you can compute the absolute or relative change in the distance to the object, if you know $x,y_1,y_2$.  For instance, if you know the distance to the object originally and the original angle $\theta_1$ from the camera's viewing direction, you can compute $x,y_1$; if you know how much it moved upward, you can compute $y_2$; and that will let you compute the new distance.


A problem that is computable yet doesn't lie in NP? I'm trying to find a problem that is computable but not in NP.

I checked and I havent found any duplicates(I hope so too). We were asked if there is a problem that exists that is computable yet doesnt lie in NP and we should name the problem and explain why is it so?

The time hierarchy theorem says that, if you allow more time, you can solve more problems. It's normally stated for deterministic machines but it applies to nondeterministic ones, too. In particular, nondeterministic Turing machines running in exponential time can solve problems that no polynomial-time NTM can. NTMs running in doubly-exponential time can solve even more, and so on for triply-exponential, quadruply-exponential and so on.

So you need to investigate the class NEXP, and find some problems in there that are known not to be in NP.


Efficient algorithm for getting from 1 to n with 3 specific operations The question:

  Given those 3 valid operations over numbers and an integer $n$:

  add $1$ to the number
  multiply the number by $2$
  multiply the number by $3$

  describe an efficient algorithm for the minimal number of operations of getting from $1$ to $n$ with the 3 operations mentioned above.

  For example for $n=28$ the answer is $4$ : $1\times 3\times 3\times 3+1=27+1=28$.

My approach:

I noticed that there is a recursive algorithm that will provide the answer but even when I used memoization the algorithm took a lot of time to end with $n\geq 1000$. I thought of a way to start with $n$ instead and try to reduce it to $1$ with the inverse operations of subtracting $1$ dividing by $2$ or by $3$ and trying to get it to be devisible by $3$ or by $2$ by subtracting $1$'s and checking the mod. But my second approach had some (more than some) mistakes where It stated that the smallest number of operations is more than it is. Please help or give a hint I clearly missing some kay fact about the nature of such operations.

Edit:

def ToN(n):

d=dict()
def to(x,num,di):
    if (num==x):
        return 0
    elif (num>x):
        return num
    elif num in di:
        return di[num]
    else:
        if num+1 not in di:
            di[num+1]=to(x,num+1,di)
        if num*2 not in di:
            di[num*2]=to(x,num*2,di)
        if num*3 not in di:
            di[num*3]=to(x,num*3,di)
        di[num]=min(di[num+1],di[num*2],di[num*3])+1
        return di[num]
return to(n,1,d)

I wrote the code above in python and it takes a lot of time to end for num=1000. Can you help me understand what is wrong w.r.t. efficiency.

Find the shortest path from $1$ to $n$ on an appropriate graph on vertices $\{1, \dots, n\}$.  This approach will work whenever it's guaranteed that intermediate values in the calculations will lie within some bounded range.


Using the decision problem, PATH in order to solve the optimization problem, SHORTEST-PATH in polynomial time So, if I were using a black-box decision algorithm, PATH in which I could say, "does a path of weight k exist in this graph from S to V", problably the typical way one would solve the optimization problem of shortest path is to start at k at zero and increment until PATH returns true. But since paths start at -inf shouldn't we be starting there? (Thus making this optimization problem not solvable in polynomial time)

I know this isn't right, I'm just having a hard time seeing which part I am missing here.

For non-negative weights $0$ is a lower bound and thus sufficient. For arbitrary weights you can binary search in $[l,u]$, for a lower bound $l=\sum_{a\in A\mid d_a<0} d_a$ and an upper bound $u=\sum_{a\in A\mid d_a>0} d_a$ on the length of any simple path.


How to solve $T(n)=n+T(n/2)+T(n/4)+\cdots+T(n/2^k)$? How do I solve the recurrence relation $T(n)=n+T(n/2)+T(n/4)+\cdots+T(n/2^k)$, for constant $k$?

I am told that the answer does not depend on $k$.

Suppose that the base case ensures that $T(n) \geq 0$. Clearly $T(n) \geq n$. On the other hand, guessing that $T(n) \leq Cn$, an inductive proof would work as long as
$$
n + C(n/2 + n/4 + \cdots + n/2^k) \leq Cn.
$$
Now the left-hand side is at most $n(1 + C(1-1/2^k))$, so we would need $C$ to satisfy
$$
1 + (1-1/2^k)C \leq C.
$$
In other words, $1 \leq C/2^k$, and so we can choose $C \geq 2^k$. Concluding, we have shown that $T(n) = \Theta(n)$. While this is true for every finite $k$, the hidden constant depends on $k$ and on the initial conditions.

The case in which $k$ is unbounded – let's say goes all the way to $\lfloor \log_2 n \rfloor$ – is more interesting. In this case we guess a solution of the form $T(n) \approx nf(n)$. The function $f(n)$ has to satisfy the recurrence
$$
f(n) = 1 + \frac{f(n/2)}{2} + \frac{f(n/4)}{4} + \cdots.
$$
A reasonable guess is $f(n) = \log_b n$, under which the right-hand side reads
$$
1 + \frac{\log_b n - \log_b 2}{2} + \frac{\log_b n - 2\log_b 2}{4} + \cdots = \log_b n - \kappa + o(1),
$$
where the constant $\kappa$ equals
$$
\kappa = 1 - \sum_{m \geq 1} \frac{m}{2^m} \log_b 2 = 1 - 2\log_b 2.
$$
Choosing $b=4$, we see that $T(n) \approx n \log_4 n$, and certainly $T(n) = \Theta(n\log n)$.


Why isn't there a .= operator? (or ->= etc) Considering how often we do:

variable = variable + another;
variable = variable - another;
variable = variable * another;
variable = variable / another;
variable = variable & another;
variable = variable | another;
variable = variable ^ another;

we then made the following language shortcuts:

variable += another;
variable -= another;
variable *= another;
variable /= another;
variable &= another;
variable |= another;
variable ^= another;

so, then, considering how often we do this:

variable = variable.different();
// or variable = variable->different();
// or variable = variable::different();

(for instance, stringVar = stringVar.toUpperCase()), why isn't there one of these?

variable .= different();
// or variable ->= different();
// or variable ::= different();

is it a parsing issue? Would it be too hard? Or is there some obvious thing I don't see here?

I'm not asking for opinions, here.
I want to know if there's any documented, historic, technical, or other verifiable reasons for why there is no such operator.

IMO, the biggest reason is that identifiers are not first class values in programming languages and "." is not a real operator like + or - are. For example, you can't convert

var foo = variable.bar()

into

var name = bar
var foo = variable.name()

The same way you can convert

var foo = 1 + 10

into

var x = 10
var foo = 1 + x

In more technical terms, in most languages x + y is an expression, while x, x.y and x[i] are identifiers.

Summing up, when using your hypothetical .=, the right hand side needs to be interpreted as a field name, not an expression. This leads to unintuitive results - the following two lines look very similar but do wildly different things.

x += bar() // calls the bar() global function and add its value to x
y .= bar() // calls y's bar() method, and sets `y` to its result.

Additionally, as Guy Coder pointed out, when using +, -, etc its guaranteed that the type of the resulting expression is the same as the arguments so += always makes sense. On the other hand, we can have y.bar() return a type different from y, in which case .= bar() would make no sense.


Time Complexity and graphs I'm learning graphs these days and need to clear few doubts-

Can I determine weather 5 points in two dimensions whose X and Y coordinates are given lie on the same straight line in O(1).
What is the efficient way to find out the degree of the specified vertex in an undirected graph (V,E)? I'm thinking of O(|E|)?
What is the efficient way to find degrees of all vertices in an undirected graph (V,E)? I'm think of O(|V||E|)
if |E| ≥ |V| can I say grapgh will be have guaranteed Euler circuit?
Is it possible to find slope of a straight line in O(1)time given the X and Y coordinates of n points on the line?

Yes, anything that has constant input could be done in $O(1)$. Howether if the coordinates have size more than $O(1)$ than you will not be able to even read them in time.
That depends on your representation of the graph and what operations do you count. If you assume that you read the whole graph in some way and then find the needed degree, the complexity will be $O(|V| + |E|)$ if your representation is an edge list, $O(|V|^2)$ if it is an adjacency matrix. If you assume that you already have some representation of the graph in memory you can find the degree in $O(|V|)$ if you have the adjacency matrix.
You can do it in $O(|V| + |E|)$, start with an empty graph (all the degrees are zero) and add the edges one by one. When you add an edge to the graph only two vertices change their degrees.
No, consider the graph $K_4$ (complete graph on $4$ vertices). All the degrees in it are odd so it does not have even en Euler path.
If you want to read the coordinates it takes $O(n)$ operations, so no.


Counting the number of subsets with positive sum I have some constant vector $\mathbf{s}$ on $n$ dimensions, where every element of $\mathbf{s}$ is a real number, and I would like to multiply it by every possible $n$-dimensional binary vector $\mathbf{v}_j\ (0\leq j < 2^n)$.

I only care about whether $\mathbf{s}\cdot \mathbf{v}_j > 0$. I would like to count all of the times this condition holds.

Question: As the naive algorithm has complexity $O(2^n)$, it blows up fast. What are my options for optimizing this for large $n$?

Suppose that you could solve this in $T(n)$. Given a list of positive integers $a_1,\ldots,a_n$ and a target $T$, consider the two instances $a_1,\ldots,a_n,-T$ and $a_1,\ldots,a_n,-T+1$. Denoting by $N(\cdots)$ the number of positive sums, we get:

$N(a_1,\ldots,a_n,-T)$ is the number of subsets of $\{a_1,\ldots,a_n\}$ whose sum is larger than $T$.
$N(a_1,\ldots,a_n,-T+1)$ is the number of subsets of $\{a_1,\ldots,a_n\}$ whose sum is at least $T$.

By comparing these two numbers, you can solve SUBSET-SUM in time $T(n+1)$.

(There are some potential differences in the computation models, that I leave you to ponder.)

There is a simple $O(2^{n/2})$ algorithm, which proceeds as follows. We break the array $s_1,\ldots,s_n$ into two equal halves. We compute an ordered list $A_1,\ldots,A_{2^{n/2}}$ of all sums of the first half, and an ordered list $B_1,\ldots,B_{2^{n/2}}$ of all sums of the second half. This takes time $O(2^{n/2})$ if done carefully (by iterative merging). We put a pointer $j$ at $B_{2^{n/2}}$, and decrease it until $A_1 + B_j \le 0$. The value of $j$ tells us the number of pairs $(1,j')$ satisfying $A_1 + B_j > 0$. Then we do the same for $A_2$ — note that we can start the scan at the current value of $j$; and so on. This phase also takes $O(2^{n/2})$.


Single tape TM that converts numbers from binary notation to unary I need to construct a TM that converts a number from binary notation to unary and calculate time complexity.
I have done the first part.
The idea is as follows:

binary number is decremented by 1 until it reaches 0. At each
decrement an additional 1 is written on the left side.

e.g.

111 -> 1111111
111x (TM goes to the end of the binary number and writes x)
110x1
101x11
100x111
011x1111
010x11111
001x111111
000x1111111
1111111 (TM removes zeros and x; end)

And now comes the time complexity part. So far I have:
(1) TM will do $n$ (length of the binary number) steps to reach the end of the input word, additional  1 for writing x and 1 for moving back, so $n+2$;
(2) there are $2^{n}-1$ decrements, at that time TM will take in total $2 \times \frac{(2^{n}-1) (2^{n})}{2}$ steps on the left side, plus $2\times (2^{n}-1)$ for the x's. (no idea how many on the right side).
(3) TM will take $2n+1$ steps for removing unnecessary zeros and x at the end.
I don't know how to put this all together, plus some missing information in (2). Can anyone tell me if I'm computing correctly and how to proceed.
Any help will be much appreciated.

As you have said, there are $2^n-1$ total "decrements". Notice that at the $k$'th decrement, you "waste" $O(n)$ time on the left side, plus $O(k)$ at the right side. Sum everything up, from $k=1$ up to $k=2^n-1$:
$\sum_{k=1}^{2^n-1} n+k = n(2^n-1)+\sum_{k=1}^{2^n-1} k = n(2^n-1) + O(2^{2n})=O(2^{2n})$


Mapping intuitionistic logic to the modal logic S4 In his famous Semantical Analysis of Intuitionistic Logic,
S. Kripke speaks of the "well-known mappings of intuitionistic logic
into the modal system S4". I'm not sure which mappings Kripke means.
One guess would be K. Gödel's "Eine Interpretation des
Intuitionistischen Aussagenkalküls" (translated into English as "An
Interpretation of the Intuitionistic Propositional Calculus". I don't have
access to either.)

Could somebody please point me towards a text that details these
translations?

That is the right paper, but there are actually several equivalent embeddings.

The book Basic Proof Theory by Troelstra and Schwichtenberg gives two such embeddings. Here's one. If $P$ is atomic but not $\bot$:

$$P^\circ := P$$
$$\bot^\circ := \bot$$
$$(A \wedge B)^\circ := A^\circ \wedge B^\circ$$
$$(A \vee B)^\circ := \square A^\circ \vee \square B^\circ$$
$$(A \rightarrow B)^\circ := \square A^\circ \rightarrow B^\circ$$
$$(\exists x A)^\circ := \exists x \square A^\circ$$
$$(\forall x A)^\circ := \forall x A^\circ$$

Here's the other:

$$P^\square := \square P$$
$$\bot^\square := \bot$$
$$(A \wedge B)^\square := A^\square \wedge B^\square$$
$$(A \vee B)^\square := A^\square \vee B^\square$$
$$(A \rightarrow B)^\square := \square (A^\square \rightarrow B^\square)$$
$$(\exists x A)^\square := \exists x A^\square$$
$$(\forall x A)^\square := \square \forall x A^\square$$

They are equivalent in the sense that $S4 \vdash \square A^\circ \leftrightarrow A^\square$, and the embeddings are sound and faithful. The proofs are left as an exercise, or you can dig out the book.


Providing $1^n$ as input to protect against degenerate cases The following language is NP-complete:

$$\{ (\alpha, x, 1^n, 1^t): \exists u \in \{0,1\}^n s.t. M_\alpha \text{ outputs 1 on input } (x,u) \text{ within t steps}\}$$

I would like to have a stronger understanding of the $1^n$ and $1^t$ inputs that are provided as auxiliary inputs. Is the above language equivalent to the following one?

$$\{ (\alpha, x, 1^t): \exists \text{ polynomial p and }u \in \{0,1\}^{p(t)} \text{ s.t. } M_\alpha \text{ outputs 1 on input } (x,u) \text{ within t steps}\}$$

I believe this gets around the technicality of allowing certificates that are sufficiently large, but not too large.

As for the $1^t$ input, what is the situation we are trying to protect ourselves against? Why isn't it sufficient to provide $(\alpha, x))$ as inputs and require that $M_\alpha$ run in time $p(|x|)$?

Your second language is (probably) not in NP, since it allows witnesses of arbitrary size. For every size $m$ there is a polynomial $p$ such that $p(t) = m$, for example the constant polynomial $p \equiv m$. A polynomial time machine should have its running time bounded by a fixed polynomial in the input size.

Regarding $t$, if you replaced the unary encoding of $t$ by its binary encoding then you would get a problem in NEXP rather than in NP, since simulating $t$ steps of a machine scales proportional to $t$, whereas the size of the binary encoding of $t$ is only $\log t$.


Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a I have created the following solution but its left recursive:
S--> a|bSc|cSb|Sbc
Also it is not accepting:
"ab" or "cba" or "abb" or abc.

Somebody please guide me.

Zulfi.

$$S\rightarrow aA, bS,cS$$

$$A\rightarrow bA, cA, \epsilon$$

Note that you need at least two non-terminals for this language, since you need to differentiate two states, namely whether an $a$ has already been added/found or not.


Are there more partially recursive functions than and recursive functions? Is the cardinality of the set of partially recursive functions greater than the cardinality of the set of recursive functions ?

No they have the same cardinality. They have the cardinality $\aleph_0$. Both sets are infinite in size so we have to compare them based on their level of infiniteness, since as we know there are infinite levels of infinity. Both sets are countably infinite so we say they have the same cardinality.

To expand on this and show why this is the case:

The set of partially recursive functions are infinite by design. Also they are computable, so by the Church-Turing thesis they are solvable by a Turing machine. Since there are only countably infinite Turing machines there can only be countably infinite partial recursive functions.

The same argument can be used on the set of recursive functions.


Floating point rounding Can an IEEE-754 floating point number < 1 (i.e. generated with a random number generator which generates a number >= 0.0 and < 1.0) ever be multiplied by some integer (in floating point form) to get a number equal to or larger than that integer due to rounding?

i.e.

double r = random() ; // generates a floating point number in [0, 1)
double n = some_int ;
if (n * r >= n) {
    print 'Rounding Happened' ;
}

This might be equivalent to saying that does there exist an N and R such that if R is the largest number less than 1 which can be represented in IEEE-754 then N * R >= N (where * and >= are appropriate IEEE-754 operators)

This comes from this question based on this documentation and the postgresql random function

Assuming round-to-nearest and that $N > 0$, then $N * R < N$ always. (Be careful not to convert an integer that's too large.)

Let $c 2^{-q} = N$, where $c \in [1, 2)$ is the significand and $q$ is the integer exponent. Let $1 - 2^{-s} = R$ and derive the bound

$$N R = c 2^{-q}(1 - 2^{-s}) \le c 2^{-q} - 2^{-q - s},$$

with equality if and only if $c = 1$. The right-hand side is less than $N$ and, since $2^{-q - s}$ is exactly $0.5$ units in the last place of $N$, either $c = 1$ and $2^{-q} - 2^{-q - s}$ is exactly representable (since $N$ is normal and not the smallest normal), or $c > 1$, and the nearest rounding is down. In both cases, $N * R$ is less than $N$.

Upward rounding can cause a problem, not that it should ever be selected in the presence of unsuspecting users. Here's some C99 that prints "0\n1\n" on my machine.

#include <fenv.h>
#include <math.h>
#include <stdio.h>

int main(void) {
    double n = 10;
    double r = nextafter(1, 0);
    printf("%d\n", n == (n * r));
    fesetround(FE_UPWARD);
    printf("%d\n", n == (n * r));
}


Fill in objects that pop out from background? I need some help with a program that will fill in objects that pop out from the background. For example I have this picture and would like to get an output like this.  I don't know how to do this though (obviously otherwise I wouldn't be asking). And I was wondering if there was some way of filling in objects that don't match the background. The only other thing is that the background isn't always going to be white for example the background could be a blue blanket with a brown dog on it. In that picture it would fill the dog in Black. The last thing about this is that the object that will be filled in will always be centered in the image.

Here is one simple approach:

Step 1. Find the background color.  (This is an entire topic in its own right, so if you're not sure how to do this, ask a separate question about it.)

Step 2. Binarize the image so that all pixels whose color is close to the background color are white, and all pixels whose color is not similar to the background color are black.  This will get you a rough approximation to what you want, but there might be holes in the middle of the black shape (e.g., if the cat was wearing a white collar).

Step 3. Apply a suitable morphological operator, e.g., the closing operator.

This approach will have some limitations, e.g., if the background is not flat but rather has shading or a gradient, but it is simple to implement and try.

If the simple approach I outlined above is not sufficient, the broad problem area you are looking at is image segmentation; you should check out the techniques that have been developed in the literature.  There are many, many methods for image segmentation that you could explore.  For instance, you could look at methods based upon graph cuts.


Regular expressions with cycles A knob is used to select one of three positions A, B, C.

The knob can never be turned from A to C, or from C to A, without spending at least one second in position B. The initial position of the knob can be any of A, B, C.

Give a regular expression for this language.

I tried starting from B, and ended up with:

BB*((AA*(BB*)*) u (CC*(BB*)*)*

But, it seems impossible to express all possible transitions.

We can build it up from smaller pieces:

How can you describe sequences made up of only a's? Just $a^*$

How about sequences made up of only a's and b's? $(a|b)^*$
These can be thought of as turning the knob from A to B, then going back to A, etc..

Similarly for b's and c's:  $(b|c)^*$

Say we stay in positions A-B for a while, and then we want to go to C; this can be expressed as:
$(a|b)^*  (bb^*)  c$

Now let's say we stay in positions A-B for a while, and then we switch to C, and stay in B-C for a while. Then the rule means we must pass through b at least once:
${(a|b)^*  (bb^*)  (b|c)^*}$

Now what if we want to stay in A-B, then switch to C, stay in B-C, then switch back to A, and stay in A-B again? ${(a|b)^*  (bb^*)  (b|c)^* (bb^*) (a|b)^*}$

The pattern starts to appear. You can see that whenever we want to transition we need to stick a $bb^*$ in between.

To get full sequences, we could try:

$(\,  (a|b)^*(bb^*) \, | \, (c|b)^*(bb^*) \, )^*$
which you can check, obeys the transition rule. The only problem is that this assumes the sequence ends with b.  To fix that, we just include options to end at a or c; naming the above as
$$
L=(\,  (a|b)^*(bb^*) \, | \, (c|b)^*(bb^*) \, )^*,
$$
we arrive at an answer:  $L\, | \,La^* \,| \,Lc^*$


Algorithms with polynomial time complexity of higher order I was learning about algorithms with polynomial time complexity. I found the following algorithms interesting.

Linear Search - with time complexity $O(n)$
Matrix Addition - with time complexity $O(n^2)$
Matrix Multiplication - with time complexity  $O(n^3)$

Is there any algorithm with a higher complexity like $n^4$, $n^5$ etc? I would like to know about practical algorithms with polynomial time complexity only.

(I am familiar with algorithms having exponential complexity and class NP algorithms. My doubt is not about them.)

The AKS primality test runs in time $\tilde{O}(n^6) \subseteq O(n^7)$, $n$ the length of the input number (in binary). This is the best known bound; as far as I know, there is no proven lower bound.


What is the intuition behind the way of reading off a dual optimal solution from simplex primal tabular in CLRS? Section 29.4 "Duality" of CLRS (3rd Edition) describes the way of reading off an optimal dual solution from the last slack form of the primal as follows:

  Suppose that the last slack form of the primal is
  $$
\begin{align}
z &= v' + \sum_{j \in N} c'_j x_j \\
x_i &= b'_i - \sum_{j \in N} a'_{ij} x_j, \; i \in B.
\end{align}
$$
  Then, to produce an optimal dual solution, we set
  $$
\overline{y_i} = \begin{cases}
  - c'_{n+i} & \text{if } (n + i) \in N, \\
  0          & \text{otherwise}.
\end{cases}
$$

I am able to follow the proof of a later Theorem (Theorem 29.10: LP Duality) to convince myself that this $\overline{y_i}$ is indeed an optimal dual solution.

However, what is the intuition behind the way the optimal dual solution is constructed? I notice that each non-zero $\overline{y_i}$ corresponds to a tight constraint in the optimal primal solution. Is this fact helpful to understand the optimal dual solution?

Answer My Own Question:

I found that the interpretation in Section 8.3 of the textbook "Introduction to Linear Algebra; 4th Edition" by Gilbert Strang is quite intuitive and much easier to understand than that in CLRS.

Note: The textbook of Gilbert Strang takes the "min" program as the primal and the max program as the dual. I follow this convention. Besides, it adopts the matrix form of linear programs, which, in my opinion, helps a lot in understanding the simplex method and the duality theory.

Quoted from the textbook:

  The $m$ inequalities $Ax \ge b$ were changed to equations by introducing the slack variables $w = Ax - b$:
  $$\begin{bmatrix} A & -I \end{bmatrix} \begin{bmatrix} x \\ w \end{bmatrix} = b$$ and
  $$\begin{bmatrix} x \\ w \end{bmatrix} \ge 0.$$
  Every simplex step picked $m$ columns of the long matrix $\begin{bmatrix} A & -I \end{bmatrix}$ to be basic, and shifted them (theoretically) to the front. This produce $\begin{bmatrix} B & N \end{bmatrix}$. The same shift reordered the long cost vector $\begin{bmatrix} c & 0 \end{bmatrix}$ into $\begin{bmatrix} c_{B} & c_{N} \end{bmatrix}$. The stopping condition, which brought the simplex method to an end, was $r = c_N - c_B B^{-1} N \ge 0$. At the stopping moment, the cost was as low as possible:
  $$cx^{\ast} = \begin{bmatrix} c_{B} & c_{N} \end{bmatrix} \begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix} = c_B B^{-1} b.$$
  If we can choose $y^{\ast} = c_B B^{-1}$ in the dual, we certainly have $y^{\ast}b = cx^{\ast}$. The minimum and maximum will be equal.

It turns out that $y^{\ast} = c_B B^{-1}$ is exactly the one read off in the final slack form of the primal program in the way CLRS describes. Its feasibility in the dual is due to the stopping condition $r = c_N - c_B B^{-1} N \ge 0$.


Does the pigeonhole principle rule out the possibility of losslessly simulating a universe the size of our own? Say you had a very powerful computer and wanted to run a completely lossless simulation of a universe approximately the same size as our own: $10^{80}$ particles.

Each particle in the simulation has properties like velocity, mass, charge, etc. Assuming that your program didn't use any tricks (like compressing this simulated universe by storing groups of 1000 particles as if they were one), does the pigeonhole principle mean that you would need a computer made out of at least $n$ particles to losslessly simulate a universe of $n$ particles?

I say this because I don't see how it's possible to store all of the physical properties of a particle on a piece of hardware without using at least one actual, physical particle.

Am I right about this? Does this mean it would be impossible to ever hope we could create a high resolution, lossless simulation with a number of particles similar to the actual number of particles in our universe?

No, the pigeonhole principle doesn't immediately imply that.  It might be true, but you'd need some additional reasoning to prove it.

For instance, you seem to be assuming that the way the simulation works is by separately simulating each simulated particle using one or more real particles, and that a single real particle cannot simulate more than one simulated particle. It's not obvious that either of these need to be true.  For instance, perhaps you can simulate K simulated particles using L real particles, using a complex algorithm that simulates them jointly without any clear mapping from simulated particles to real particles.  It's also not clear why we'd need to have $K \le L$; perhaps there is some algorithm where $L=K/2$ (say).  Some additional reasoning would be needed to rule out these possibilities -- the pigeonhole principle alone isn't enough.

It does seem like a plausible-ish sort of conclusion, under reasonable assumptions about your model of computation.  But I don't think it's that easy to prove.


Term for the tree of all paths starting from a given vertex in a graph What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex?

This is the tree that is implicitly or explicitly constructed when doing shortest path search.  It appears, for example, in a lecture on search of an MIT Artificial Intelligence course, but I didn't understand if it has a name.

This is not a search tree and not really a decision tree.

Mathematically, it is a covering tree, but is there a more appropriate term in the context of shortest path search?

It's the self-avoiding walk tree (SAW tree).

The trees seem to have been first considered by C.D. Godsil (Matchings and Walks in Graphs, Journal of Graph Theory 5(3):285–297, 1981; DOI link; just before Lemma 2.4), though Godsil doesn't use the name.

(And, yes, "self-avoiding walk" is just a mighty-long way of saying "path".)


Difference between CNOT and 2nd bit bitflip I understand how the outcome of each is supposed to be different, but in matrix form are these gates not the same? The CNOT matrix negates the second bit regardless of the input of the first.

The controlled NOT gate is represented by the matrix
$$
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&0&1\\
0&0&1&0
\end{pmatrix}
$$
In contrast, the matrix corresponding to negating the second bit is
$$
\begin{pmatrix}
0&1&0&0\\
1&0&0&0\\
0&0&0&1\\
0&0&1&0
\end{pmatrix}
$$


Knapsack problem, partition problem, or in general dynamic algorithm with negative numbers allowed How to think about dynamic algorithms which allows negative integers in input (where it's problematic, because obviously it's not always the case)?

Examples:

Partition Problem with negative numbers in set allowed
Knapsack problem with negative weights are allowed

Is there some general idea to handle these or other similar dynamic algorithms?

In the two examples you mention, the dynamic programming algorithms work just as well. Let's take partition as an example. The dynamic programming approach computes, for every $m$, the sums of all subsets of $\{w_1,\ldots,w_m\}$. This works just as well if negative numbers are allowed. The range of the table has to be modified accordingly, to account fo the largest possible positive and negative amounts. With knapsack it's similar, and I'll let you work out the details.


Does a distance matrix have to be Euclidean in order to be clustered by an average-linking algorithm (UPGMA)? What are the exact assumptions behind the use of UPGMA? Can I use a non-Euclidean metric? This may result in a non-Euclidean distance matrix. What kind of bias may I encounter if I do so? References are appreciated.

While you can modify any algorithm as you see fit, in its pure form UPGMA has the following underlying assumptions at work:

UPGMA (Unweighted Pair-Group Method with Averages), arithmetic average - the average distance between elements of each cluster (weighted by the number of elements).

For example, (AB) and C+(DE) = (55+3x45)/3 = 63.33

Additional Comparative Algorithmic Context

Below is a list of algorithms and their general framework as it relates to each algorithm:

SINGLE (Single-link method) – brings together the closest elements.
WPGMA (Weighted Pair-Group Method with Averages), arithmetic average (not weighted by the number of elements).
WPGMC (Weighted Pair-Group Method with Centroid Average), centroid average (assumes dissimilarity).
WPGMS (Weighted Pair-Group Method with Spearman Average), Spearman's average (assumes correlation).

Reference for Modifying UPGMA

The paper below is a wonderful resource for "what-if" scenarios as it relates to UPGMA:

Vavrek, M. J. (2016). A comparison of clustering methods for biogeography with fossil datasets. PeerJ, 4, e1720. http://doi.org/10.7717/peerj.1720


Creating a Deterministic Push-Down Automaton for the Union of two languages Suppose, we have $L_1:=\{w\in\{a,b\}^*\mid \#_a(w) \equiv 0 \mod 4\}$ and $L_2:=\{w\in\{a,b\}^*\mid abaab \text{ is a substring of } w\}$. Now we want to create a Deterministic Push-Down Automaton for $L_1\cap L_2$

I've created PDA's for both languages:

$M'=(Q,\Sigma,\Gamma,\Delta,s,F)$ with $\Sigma=\{a,b\}$, $\Gamma=\{\}$, $Q=\{1,2,3,4\}$, $F=\{0\}$, $s=\{0\}$ and
\begin{align}
\Delta=\{&(0,a,\lambda,1,\lambda),(0,b,\lambda,0,\lambda)(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,3,\lambda),(2,b,\lambda,2,\lambda)\\
&(3,a,\lambda,0,\lambda),(3,b,\lambda,3,\lambda)\}
\end{align}
where $\Delta\subseteq Q_{old}\times (\Sigma \cup \{\lambda\})\times(\Gamma\cup \lambda)\times Q_{new}\times\Gamma^*$

and

$M''=(Q,\Sigma,\Gamma,\Delta,s,F)$ with definitions above and $\Sigma=\{a,b\}$, $\Gamma=\{\}$, $Q=\{1,2,3,4,5,6\}$, $F=\{6\}$, $s=\{1\}$ and
\begin{align}
\Delta=\{&(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,2,\lambda),(2,b,3,\lambda),(3,a,\lambda,4,\lambda),(3,b,\lambda,1,\lambda),\\&(4,a,\lambda,5,\lambda),(4,b,\lambda,3,\lambda),(5,a,\lambda,2,\lambda),(5,b,\lambda,6,\lambda),(6,a,\lambda,6,\lambda),(6,b,\lambda,6,\lambda)\}
\end{align}

$M'$ accepts $L_1$ and $M''$ accepts $L_2$, but how to construct $M^{\star}=M'\cap M''$ which accepts $L_1\cap L_2$?

I know, that we could possibly do this with Deterministic Finite Automata, but I want to know how it would work with PDA's.

There is no general algorithm for computing a DPDA $M^*$ as the intersection of two DPDA $M,M'$; that problem is undecidable.  See Undecidable problem intersection of two DCFL languages is DCFL? for a proof.

So, you will have to look for some pattern in this particular problem that makes it easier than the general case.  Hint: what level in the Chomsky hierarchy is $L_1$ at?  what about $L_2$?


Writing a linear program to model balanced bin packing Say we want to write a (MI)LP to model the following problem:

  Find a parking plan for a set of cars $K=\{1, ..., k\}$ with lengths
  $\lambda_i$. Parking is organised in lanes $P=\{1, ..., p\}$. The
  length of a lane is the sum of the cars parking there and may not exceed a specified constant $L$. The goal is to balance the lengths of
  the parking lanes as well as possible. More specifically, we want to
  minimise the difference of the length of a longest and shortest line.

To me, this seems quite akin to some variant of the Bin Packing problem. Usually, however, we want the number used bins to be minimised.

Here, I am quite confused on how I could come up with an objective function that expresses the balance between the lanes/bins. My main problem is that -- as far as I understood it -- the objective function has to be linear. Thus, I couldn't use operations like max, min, absolute value etc.

Can someone help me out here with a hint?

Define a variable $b$ that represents the imbalance between the lengths of the parking lanes.  For instance, if $b=5$, that means that the lengths of every pair of parking lanes differs by at most 5.  Define other variables to represent the lengths of the parking lanes.

Write constraints to enforce that $b$ is set consistently with your other variables.

Minimize $b$.


Generate Regular Grammar for a Language with Modular Condition This is a homework problem.  I've wrestled with it for quite awhile and can't come up with a valid solution.  The problem is:

Find a regular grammar that generates each of the following languages:
$$L = \{ w \in {a,b}^* \mid \text{na}(w) – \text{nb}(w) = 1 \mod 3 \} , $$

where $\text{na}(w)$ is the number of $a$s and $\text{nb}(w)$ the number of $b$'s occurring in $w$, respectively.

It seems as though a DFA can't accept this language since any difference of $a$'s and $b$'s resulting in 1 will be in the language, but that gives an infinite number of possibilities.

Any help pointing me in the right direction for this problem would be much appreciated.

Hint: How many states do you need to keep track of $n_a(w)-n_b(w) \pmod{3}$, where $w$ is any prefix of the input? Consider how many possibilities this quantity has, and whether knowing the value for a word $w$ helps you calculate the value for the word $w\alpha$ ($\alpha$ being a single symbol).


Owned state in MOESI protocol-transitions? I understand that MESI is a subset of the MOESI cache coherency protocol. But what does the Owned state in the MOESI protocol represent? What are the differences in state transition due to the extra Owned state in MOESI as compared to MESI?

For example consider same cache line in processor P1 is in OWNED state & processor P2 is in SHARED state. What happens when there is a write request to P2?

Owned state indicates that the data is shared between multiple caches/memory levels and is modified(by the owner) unlike modified state which indicates that only this cache has the only valid value and has modified the value. This eliminates the need for writing back to the main memory before sharing the data with anyone. Hope that helps.


Set theory pertaining to category theory and functional programming I'm reading an unfinished Introduction to Category Theory/Products and Coproducts of Sets and have come across the following:

A power set of a set is the set of all its subsets. A script 'P' is used for the power set. Note that the empty set and the set itself are members of the power set.
\begin{equation}\mathcal{P}\{1,2,3\} = \{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}\end{equation}
Set operations are functions from the product of a power set to a power set.
\begin{equation}\text{Union}:\mathcal{P}(X) \times \mathcal{P} \to \mathcal{P}(X),
\text{Union}(A,B) = A \cup B\end{equation}

I don't understand the last part.
To me a product of a power set should equate to a set of tuples where the first of the ordered pair is a subset from first power set and the  second is a subset from the second power set. Whereas a power set is just a set of subsets.
How can this mismatch be explained or is it a mistake?

Taking on board the advice below:
If the set $X$ is a singleton value $1$, then:
\begin{equation}X = \{1\}\end{equation}
The power set of $X$ is then:
\begin{equation}\mathcal{P}(X) = \{\varnothing,\{1\}\}\end{equation}
The product of $\mathcal{P}(X)$ is then:
\begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) = \{(\varnothing,\varnothing),(\varnothing,\{1\}),(\{1\},\varnothing),(\{1\},\{1\})\}\end{equation}
Applying $\text{Union}$ to the $\mathcal{P}(X)\times\mathcal{P}(X)$ is:
\begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) = \{(\varnothing,\varnothing)\mapsto\varnothing,(\varnothing,\{1\})\mapsto\{1\},(\{1\},\varnothing)\mapsto\{1\},(\{1\},\{1\})\mapsto\{1\}\}\end{equation}
As the result is a set, duplicates can be removed:
\begin{equation}\{\varnothing,\{1\},\{1\},\{1\}\} = \{\varnothing,\{1\}\}\end{equation}
Thus:
\begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) \to\mathcal{P}(X)\end{equation}
And so the set operation of $\text{Union}$, which is one of a family of set operations (a set of functions) is a function from the product of a power set to a power set

The notation $f:E\times F \to G$ means that $f$ is a function that needs two arguments, one from $E$, one from $F$, and the image is in $G$.
This is how the function $\text{Union}$ is defined: the two arguments $A$, $B$ are in $\mathcal{P}(X)$ and the image $\text{Union}(A, B) = A\cup B$ is in $\mathcal{P}(X)$.


Why does everyone say that NFA guesses it's next state? In the picture above e is an empty string, and a is a symbol from an alphabet. Every book or professor I have heard from, says than when we make transitions in the NFA, the NFA must guess which state to go to next. In the example above, the NFA must guess whether it should go left or right.

Why do they use the word guess? I have written a simple regular expression engine once and used dfs to go both right then left, if the right path didn't lead to a final state.

There are many equivalent ways to describe the operation of an NFA. One is using guesses. If you don’t like it, I suggest not using it.

Guesses come up very naturally in the union construction. Suppose we are given NFAs for two languages $A,B$. We create a new NFA with a new initial state which points to the initial states of the NFAs for $A,B$, with $\epsilon$-transitions. When considering the semantics of the new NFA, it is natural to think of the NFA as first “guessing” which of the two $\epsilon$-transitions to take initially — this amounts to guessing whether the input belongs to $A$ or to $B$.

An NFA accepts a given input word if it can work its way from the initial state to an accepting state, following the input symbols and using $\epsilon$-transitions at will. Tracing the operation of the NFA, at a given point there might be many possible transitions to take, and the NFA has to choose one of them. If the input belongs to the language of the NFA, then there must exist a set of correct choices which leads the NFA to an accepting state. We refer to the process in which the NFA chooses an accepting path by the name guessing. This is a metaphor which many people find helpful, but if you don’t, feel free not to use it.


Code and time complexity of multiplication à la française This references the multiplication algorithm in Chapter 1 of Algorithms by Dasgupta et al.
I am trying to understand how the code for multiplication à la française works from the multiplication by hand. This is the example given.

This is the code given for it.

I went ahead and did multiplication of $13 \times 11$ (odd) case and $13 \times 10$ (even) in a spreadsheet and this is what I got.

It seems to me that in the code the rows of the columns are flipped with respect to handwritten example, that is, in $13 \times 11$, the 1 shows up where 13 is and not where 104 is as in the handwritten example. I still get the correct answer. Where did I make a mistake? In the evaluation or understanding the conversion from handwritten algorithm to algorithm in code.
I also have trouble seeing how to get $O(n^2)$ for the time complexity. I understand that there is bit shifting and addition and so at some point, assuming both $x$ and $y$ are n bits, we end up adding $1 + 2 + 3 + \dots + n = \frac{n}{2}(n+1) = O(n^2)$ but aren't we shifting the bits $n$ times and therefore need to multiply by another factor of $n$ to get $O(n^3)$?
This is what I get when I think of the equation for master theorem: $T(n) = T(\frac{n}{2}) + O(n)$ because there is 1 recursive call and the problem is halved and it takes $O(n)$ time to add n bits. However, this equation would give me $\Theta(n)$ which is wrong.  What step did I miss in the recurrence equation?

In the function $T(n)$, the parameter $n$ represents the length of the input in bits. The recursive call reduces $y$ to $\lfloor y/2 \rfloor$, which reduces the length of the input by a single bit. Hence the recurrence is really $T(n) = T(n-1) + O(n)$, whose solution is indeed $T(n) = O(n^2)$.


Splitting a set of points in the plane evenly and sorting it Input: A set of points P(x,y). There are two versions of it - Px, sorted by x and Py, sorted by y.

Output: The two even halves of Px, sorted by y.

The trick here is that it has to work in linear time, otherwise, it's rather useless. What I've come up with so far is finding the midpoint of Px, let's call it Px[mid] and then iterating over Py, checking if each point's x coordinate is bigger than Px[mid] and then assigning it to the appropriate half.

Example:

Px = [(1,7),(2,3),(3,1),(4,-2)]
Py = [(4,-2),(3,1),(2,3),(1,7)]
Px[midpoint] = (2,3)
Ly = [(2,3),(1,7)]
Ry = [(4,-2),(3,1)]

This works quite well, if you account for points with equal x coordinates and compare said points by y instead (and vice versa), which sorts them in a way that avoids potential surprises. Where it fails is the following case:

Px = [(1,7),(2,-3),(2,-3),(4,-2)]
Py = [(2,-3),(2,-3),(4,-2),(1,7)]
midpoint = 2
P[midpoint] = (2,-3)
Ly = [(2,-3),(2,-3),(1,7)]
Ry = [(4,-2)]

I can't seem to think of a way to exclude non-distinct points from the left half, when they're equal to the midpoint. Again, keep in mind that this has to work in linear time, so I can't just split Px into two halves and search for points which might belong to it for the odd case.

This is not so hard to fix. First, calculate the median $m$. Then calculate the number of points strictly left of the median $\ell$. Take all of them from Py, and take the first $n/2-\ell$ points whose $x$ value is $m$ (where $n$ is the total number of points). These form the first half, and the rest of the points form the second half.


Logarithmic space verifier with unbounded witness this is a HW question, but its considered a bonus question so I'd appreciate a direction.

Definitions:

The actual question:

**Images taken from HW in TAU Complexity course by Amnon Ta-Shma.

My thoughts on the question:

My intuition is that C2 = NL, because NSPACE(O(f(n)) ⊆ DTIME(2^O(f(n))), so for a verifier for a language in C2 as defined in the question, as it anyway runs in logarithmic space will run in polynomial time and therefore it won't be able to read more than a polynomial length witness so it doesn't add power. I already proved that the set of languages that are decided by a logspace verifier with read once witness tape and polynomial length witness are NL.

So more formally:

For Nl ⊆ C2, then for a language L that is in NL and decided by a logspace NTM M, it feels to me like I could just treat the witness as a configurations sequence that describes the choices that M did, and just check the validity of the transitions according to the delta function of M and accept only if all transitions are valid and the last configuration is accepting. This will need logarithmic space. So L in C2 (basically this is the same as bounded length witness case).

For C2 ⊆ NL:
This feels harder. Denote L as a C2 language that is decided by a verifier as defined in the question. When I think about this, the verifier can read from the witness tape without writing the content to the work tape, so it could read the whole witness and still remain in the logarithmic space bound, and it would be equal to a NTM that performs |w| (length of the witness) of non deterministic choices while using logarithmic space on its work tape. Basically it means the NTM makes unbounded number of choices.

So on one hand, I don't think the definition of a NL NTM bounds the number of non-deterministic decisions (as long as the space complexity holds). So even with the arbitrary number of non deterministic choices, the complexity class is still NL because the space complexity doesn't change. But on the other hand, this means a "deeper configuration graph" and it feels like the time complexity of this NTM is greatly increasing and it doesn't feel right.

So in the case that the number of choices doesn't affect the complexity, this will mean that C2 ⊆ NL cause every time the verifier reads a character of the witness, we can make a non deterministic choice for that character and simulate the verifier.

But if this is wrong, then I'm not sure how to proceed.

I would appreciate pointing me to the correct direction, thanks!

*** Again, this is not for submission, by I would really like to solve it.

Let $N$ be the total number of configurations of the machine other than the witness tape, namely state, location of the input tape head, contents of the work tape, and location of the work tape head. Note that $N$ is polynomial in $n$.

We can assume without of generality that at each step, the machine reads a bit from the witness tape, and it affects its decision (we can accommodate that by adding dummy bits to the witness tape at locations where the original machine doesn't read the witness tape). The machine terminates once the witness tape runs out.

I claim that for any witness $w$, there is an equivalent witness $w'$ with $|w'| < N$. Here equivalent means that when the machine terminates, it is in the same configuration. The proof resembles that of the pumping lemma: if $|w| \geq N$, then some configuration must repeat, and so we can remove the corresponding part from the witness.

Thus, without loss of generality, the witness is of size at most $N=\operatorname{poly}(n)$. So this definition coincides with the usual definition of $\mathsf{NL}$.


R-tree insertion procedure when leaf is full I am implementing an R-tree with the quadratic splitting method.

However in most articles I have read there a piece of information that is missing or misleading (or the most probably case, I completely misunderstood something).

R-trees are supposed to be balanced, yet you need to find the node that will increase less in area to insert your new object, and split such node if full. However this can clearly lead to having a very unbalanced tree in depth, as that node can always be on a single branch (say, leftmost in a graph-type representation of the tree).

Should the insertion criteria say " find the node that will increase less in area to insert your new object among those that are not full, [...]" ?

OR can the quadratic splitting method create very unbalanced trees if you are unlucky with new entries? Say if after N insertions all the new insertions are are very localized, e.g. in always fit in the leftmost leaf in the following figure

Or is there something else that I did not understand?

Nope, you are wrong!

In your example, if you keep adding nodes to the leftmost entry, the splits propagate upwards. There will be more levels, but as they propagate upwards, the leafs are always in the same level, thus it always makes a balanced tree, as long as you make sure you follow the insertion and splitting rules tightly (e.g. make sure there are always $m$ minimum objects in a node)


Proving tautology with coq Currently I have to learn Coq and don't know how to deal with an or :

As an example, as simple as it is, I don't see how to prove:

Theorem T0: x \/ ~x.

I would really appreciate it, if someone could help me.

For reference I use this cheat sheet.

Also an example of a proof I have in mind: Here for double negation:

Require Import Classical_Prop.

Parameters x: Prop.

Theorem T7: (~~x) -> x.
intro H.
apply NNPP.
exact H.
Qed.

You cannot prove it in "vanilla" Coq, because it is based on intuitionistic logic:

  From a proof-theoretic perspective, intuitionistic logic is a restriction of classical logic in which the law of excluded middle and double negation elimination are not valid logical rules.

There are several ways you can deal with a situation like this.

Introduce the law of excluded middle as an axiom:

Axiom excluded_middle : forall P:Prop, P \/ ~ P.

There is no more need to prove anything after this point.
Introduce some axiom equivalent to the law of excluded middle and prove their equivalence. Here is just a few examples.

Double negation elimination is one such axiom:

Axiom dne : forall P:Prop, ~~P -> P.

Peirce's law is another example:

Axiom peirce : forall P Q:Prop, ((P -> Q) -> P) -> P.

Or use one of the De Morgan's laws:

Axiom de_morgan_and : forall P Q:Prop, ~(~P /\ ~Q) -> P \/ Q.


3-partition problem: why $b/4 < x_i < b/2$? Why does the definition of the 3-partition problem contain the condition
$$\frac{B}{4}<x_i<\frac{B}{2}?$$

I don't understand why leaving out this condition changes the 3-partition problem.

The 3-PARTITION problem is NP-complete even without this condition. It is a stronger result that 3-PARTITION is NP-complete even with this condition. The condition presumably comes from the reduction used to prove that 3-PARTITION is NP-hard.

The fact that 3-PARTITION is NP-complete even when all integers are bounded in $(B/4,B/2)$ can be helpful when using 3-PARTITION to prove that other problems are NP-hard.


Sort an array that contain two sorted array in $O(n)$ Given an array $A[1..n]$. $A$ is mixed of two sorted arrays $B$ and
$C$ of equal sizes, such that $B$ is in the ascending order and $C$ is in
the descending order.
Consider the following example: $B=[2,4,6,8]$ and $C=[9,7,5,1]$. As a
result $A=[2,9,7,4,6,5,8,1]$. Interestingly, The instructor said: $A$
can be sorted in $O(n)$. Anyone can give me a hint?

My attempt:
I tried to partition the array $A$ into sorted arrays $B$ and $C$, but I could not do it because my approach encountered counterexamples.

Let $a$ is the first element of $A$. Let $A$ is composed of array $B = (b_{1},\dotsc,b_{n})$ and array $C = (c_{1},\dotsc,c_{n})$.
Now, we will partition $A$ into arrays: $B'$ and $C'$ in the increasing and decreasing orders respectively. Following is the process:

Let $p$ be a pointer. Initially, $p$ is pointing to $a$. Let $b$ be the element in $A$ next to $a$.
There are two possibilities:

Case 1: $a<b$. Then, one of them must be an element of $B$. In this case, if $a$ is greater than the last element of $B'$, add $a$ to $B'$. Move the pointer to $b$ and go to step $1$.
Otherwise, add $a$ to $C'$ and $b$ to $B'$. Move the pointer to the element next to $b$ and go to step $1$.
Case 2: $a>b$. Then, one of them must be an element of $C$. In this case, if $a$ is smaller than the last element of $C'$, add $a$ to $C'$. And, move the pointer to $b$ and go to step $1$.
Otherwise, add $a$ to $B'$ and $b$ to $C'$. Move the pointer to the element next to $b$ and go to step $1$.
The above process produces the array $B'$ in increasing order and $C'$ in decreasing order. However, note that these arrays might not be of the same size.
Correctness: Proof by induction.
Base Step: $A$ is composed of $B$ and $C$. $B'$ and $C'$ are empty right now. In Step $2$, Case 1, we add $a$ to $B'$. If it is indeed an element of $B$ then we are good. If not, then $b \equiv b_{1}$ and we can assume that $A$ is composed of a new array $B' = (a,b_{1},\dotsc,b_{n})$ having elements in the increasing order, and array $C' = C \setminus a$ having elements in the decreasing order. Therefore, adding $a$ to $B'$ is correct.
Similarly, we can prove the correctness of Step $2$, Case $2$.
And, the correctness of the further steps follows from the induction step.

After obtaining $B'$ and $C'$, you can merge them using merge sort like step in $O(n)$ time.


Does Huffman algorithm generate a minimal weight of a tree? Does Huffman algorithm generate a minimal weight of a tree?

I noticed that by trying to make two different trees with the same frequencies of letters, I get different weights of the trees.

We defined the weight of the tree as $\displaystyle\sum_{c\in C}f(c)d(c)$ where $C$ is all the letters, $f()$ is the frequency of the letter, $d()$ is the depth in the tree of that letter.

If you normalize the frequencies so that they add to 1, then the weight of the tree is just the average codeword length, which is exactly what Huffman's algorithm tries to minimize. Check this section of the Wikipedia article you link to.


How to calculate the dimension of a convex polyhedron? A convex polyhedron can be represented by a set of linear inequalities. If the inequalities involve $n$ variables, then the polyhedron can be $n$-dimensional, but it can also be of a smaller dimension - in case some of the inequalities in fact define equalities. As a simple example, the following inequalities:
$$x_1 \geq 0, x_2\geq 0, x_3 \geq 0\\
x_1 \leq 1, x_2\leq 1, x_3 \leq 1
$$
define a 3-dimensional polyhedron (a cube). But if the last inequality is changed to $x_3 \leq 0$ then the polyhedron becomes 2-dimensional (a square).
What is an algorithm for determining the dimension of a polyhedron given by a set of linear inequalities?
EDIT: By "convex polyhedron" I meant any object that can be represented by the intersection of a finite number of half-spaces (i.e., conjunction of finitely many linear inequalities).

While there are probably much more efficient approaches, the following method can be used to compute the dimension in polynomial time, and is not too complicated.
Implicit inequalities
The dimension of a polyhedron $P$ is defined as the dimension of its affine hull, i.e. $\dim P := \dim \mathrm{aff}(P)$.
Let $a^i x \leq b_i$ for $i\in M$ be the linear inequalities that compose the system $A x\leq b$ defining $P$. An inequality $a^i x \leq b_i$ is called an implicit inequality of this system if $a^i x = b_i$ for all $x$ such that $A x\leq b$. Let $A^= x\leq b^=$ denote the subsystem of $Ax\leq b$ that consists only of the implicit inequalities in $Ax\leq b$. Now, we have the folllowing theorem:

Let $P = \{x\in \mathbb{R}^n \mid Ax\leq b\}$ be a nonempty1 polyhedron. Then, $\mathrm{aff}(P) = \{x \mid A^= x= b^=\} = \{x \mid A^= x\leq b^=\}$. Additionally, $\dim P = n - \mathrm{rank}\ A^=$.

(see Theorem 3.17 from Integer Programming by Conforti, Cornuéjols, and Zambelli. Chapter 3.8 contains additional examples for computing the dimension by hand)
So, to compute the dimension of $P$, we first find all implicit inequalities to obtain $A^=$, and then compute the rank of $A^=$. The latter is easy to do, but the first can be rather complicated to do in general (although it is often doable 'by hand' for well structured cases).
Finding implicit inequalities via linear programming
Note that an inequality $a^i x \leq b_i$ is implicit if and only if the hyperplane $a^i x = b_i$ (i.e. the 'border' of the halfspace defined by the inequality) contains $P$. We can determine whether this is the case by solving a pair of linear programs (thanks to @plop for pointing this out). The inequality $a^i x \leq b_i$ is implicit if and only if
$$\max \{a^i x \mid Ax\leq b\} = \min \{a^i x \mid Ax\leq b\} = b_i,$$
or in other words when optimizing within $P$ in the directions of $a^i$ and $-a^i$ both yields the value $b_i$.
To see why this is true, first note that if either of the results of these programs give a value other than $b_i$, we have found some $x\in P$ with $a^i x \neq b^i$, so the inequality is not implicit2.
For the other implication, any point $x'\in P$ that lies outside the hyperplane $a^i x =b_i$ lies inside the hyperplane $a^i x = b'_i$ for some $b'_i\neq b_i$. If $b'_i < b_i$, then $\min \{a^i x \mid Ax\leq b\} \leq a^i x' = b'_i < b_i$, and if $b'_i > b_i$, then $\max \{a^i x \mid Ax\leq b\} > b_i$. So at least one of the linear programs gives a value unequal to $b_i$  if $a^i x \leq b$ is not implicit.
The algorithm
So, a possible algorithm for finding the dimension of $P$ in $\mathbb{R}^n$ when given by a system of $m$ inequalities is

Solve $2m$ linear programs to find the implicit inequalities and $A^=$.
Compute the rank $r$ of $A^=$, and return $n-r$.

Linear programs can be solved in polynomial time via e.g. the interior point method (although the simplex method is much faster in practice), and the rank of a matrix can be computed in polynomial time via Gaussian elimination. So, the dimension of a polyhedron can be computed in polynomial time.
As I mentioned earlier, there are probably much better approaches than what I suggest here. The suggestions offered by @plop in the comments look promising and I recommend anyone looking for something better than what I'm suggesting here to follow them through, but I will end my answer here, it is already long enough.

(The first part of this answer is taken from these slides by Rudi Pendavingh , page 8)

1: If $P$ is empty, then its dimension is $0$. Additionally, we can test whether $P$ is empty via linear programming. So, we can and I will assume that $P$ is non-empty for the remainder of this answer.
2: It may happen that the minimization and maximization program give the same value, but a different one than $b_i$. (Try to think of an example!) In this case, the inequality must be redundant: it can be removed from the system without changing $P$.


Regular Expression converted to NFA Hello, all,

First time poster, here.
Anyways, here is my question from the textbook Introduction to the Theory of Computation, 2nd Ed. (Sipser, 2006). Question 1.19 is asking us to convert a regular expression to a nondeterministic finite automaton. The regular expression is given as:

(0 union 1)* 000 (0 union 1)*

Which I interpret as:

"Any number of 0's or 1's, followed by 000, followed by any number of 0's or 1's."

This is the solution that I came up with:

However, the professor of this course I am taking provided a solution, albeit unsimplified, that is different from mine. I am wondering where I went wrong. I have asked this same question to my professor via e-mail (distance ed.), but since I am not expecting a reply based on past experience, I have also asked this question here. Any help you can provide would be greatly appreciated.

Notice that the word 000 is not accepted by your automaton. To see why your automaton is wrong. Look at the strongly connected component that includes the initial state (the first two states in your figure, lets call them $q_0$ and $q_1$). This component is meant to read the (0|1)* prefix. Hence, you must be allowed to get out of this component(i.e., guess when to start reading the 000 part of the word) from either $q_0$ or $q_1$. To fix your solution, you should add a transition, labeled with 0, from $q_0$ to the third state in your figure (lets call it $q_3$). Or you can replace the whole component with a single state q. such that q is initial, has a self-loop labeled with 0,1 and has a transition, labeled with 0, to $q_3$.


Dynamic programming, coming up with an algorithm I've been banging my head against the wall for the past two days and can't seem to come up with anything useful. The problem that needs to be solved is the following: I get an array of integers and I must return an array containing the elements that would give the maximum sum with the following condition: If I select an element, then I cannot use the one before or after it. I think I must, like it often is with dynamic programming, somehow order my results in a matrix, but I have no idea how to go about it. Any help is greatly appreciated.

For each $m$, let $\sigma(m)$ be the maximum sum of non-adjacent values among the first $m$ values of the array $A$. Then:
$$
\begin{align*}
&\sigma(0) = 0, \\
&\sigma(1) = A(1), \\
&\sigma(m) = \max(A(m) + \sigma(m-2), \sigma(m-1))
\end{align*}
$$
As an exercise, now try to solve similar problems in which you slightly modify the constraints. For example, suppose that if you select an element then you are not allowed to use $a$ elements before or after it; or that among any $b$ adjacent elements, you are allowed to choose at most $c$.


What is the probability of friendship conditioned on the number of mutual friends Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends?

I am interested both in the experimental values (or estimates) from currently existing social networks (e.g. Facebook) and values predicted by random graph models for these social networks.

Okay, this is my approach to this problem. I think the key concept here is the clustering coefficient $c$. The value of $c$ is denotes how likely it is that two nodes are connected by an edge, if the have a common neighbor. In SN-friendship graphs the clustering coefficient is usually high compared to classical random graph models, such as Erdös-Rényi.

What is known about the clustering coefficient of the facebook-graph? If you follow the presentation of this paper, for a node of degree 100, we have $c=0.14$. Assuming that you have 100 friends is a reasonable assumption than it is close to the median degree (about 99, see here) and the average degree (might be around 95, see here).

Lets make the bold assumption, that the events that a tie between two nodes $A$ and $B$ is present if they have friend $X$ in common, are independent. Then we get

$$\begin{align}
P[\text{$A$ and $B$ are friends}] & = 1 - P[\text{$A$ and $B$ are not friends}] \\
&=1-(1-c)^k.
\end{align}$$

A plot of this function looks like this:

So if $A$ and $B$ have 5 friends in common it is slightly more likely they are friends, than they are not.

This is just a rough calculations that ignores several effects.


Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge I'm pracitcing exams towards finals,

Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$.

Prove :
for every 2 distinct MST $T,T'$ there is a sequence of $k$ MST's such that every 2 MST's $T_i,T_i+1$(+1 on the index) in the list are neighbours and at the end of the sequence we get $T$

$T' = T_1,T_2,T_3,\ldots,T_k=T$

hope to get help.

This is a generalization of the Uniqueness property of minimum spanning trees, and the proof is almost the same:

Note there is at least one edge that belongs to exactly one of $T$ and $T'$. Among such edges, let $e_1$ be the one with least weight. Without loss of generality, assume $e_1 \in T$.
As $T'$ is an MST, $e_1\cup T'$ must contain a cycle $C$ with $e_1$.
As a tree, $T$ contains no cycles, therefore $C$ must have an edge $e_2\notin T$.
Since $e_1$ was chosen as the lowest-weight edge among those belonging to exactly one of $T$ and $T'$, the weight of $e_2$ must be no less than the weight of $e_1$.
As $e_1$ and $e_2$ are part of the cycle $C$, replacing $e_2$ with $e_1$ in $T'$ therefore yields a spanning tree $T''$ with no larger weight, thus also a minimum spanning tree. Since $e_1\in T$ and $e_2\notin T$, $T''$ is more "closer" to $T$ than $T'$.
Repeat the processes above for $T$ and $T''$. Finally you will get a sequence of mimimum spanning trees between $T$ and $T'$.


Pumping lemma for regular languages I have a vey specific question regarding the pumping lemma in the context of regular languages. The theorem states that if $L$ is a regular language, then there exists a constant $n$ such that for every string $w$ in L, with $|w|\geq n$, $w$ can be broken into $w=xyz$ with the following properties:

$|y|>0$
$|xy|\leq n$
For all $k\geq 0$, $xy^kz \in L$

My question concerns the third and first properties. In the third property, does $k=0$ not imply that $|y|=0$, therefore contradicting the first property?
As far as I can tell, when $k=0 \rightarrow xy^kz=xz$ and, consequently, $y=\epsilon$. What am I missing?

How long is the word "cat"?

If I write "catcat", how long is the word "cat"?

If I write nothing at all, how long is the word "cat"?