Solving T(n) = 2T(n/3) + 2 T(2n/3) + n The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:

Recursion tree. We see that
$$\begin{align}
\sum_{i = 0}^{\log_{3}(n)}n2^i & = \Theta(n^{1+\log_3(2)})\\
& \ll T(n) \\[1em]
& \ll \sum_{i = 0}^{\log_{\frac{3}{2}}(n)} n2^i \\[0.5em]
& = \Theta(n^{1+\log_{\frac{3}{2}}(2)})
\end{align}$$
but cannot, as I can see, get $\Theta(T(n))$ exactly.
Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$, as far as I can see there is no way to get a closed form for p from this equation (but it gives a numerical approximation consistent with 1, $p$ is about $2.19$ so that is good).

What I want is to find a closed form for $p$, one better than $2+2^{p+1}=3^p$. I believe such a closed form does exist, it might be found with domain transformations or something like that.

This is problem 2(m) from Jeffrey Erickson's notes on recurrences:
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

Any help is appreciated.

Completely unscientifically, the 2T (N/3) can be ignored. The 2T (2N/3) doubles whenever N is multiplied by 1.5, which starting with T(1) happens log N / log 1.5 times, so the result is about $2^{\log N / \log 1.5}$ or $N^{\log 2 / \log 1.5}$ which is about $N^{1.709}$. The n that is added is less than this, so $\Theta(N^{1.709})$ is my unscientific answer.

It just so happens that $p = \log 2 / \log 1.5 = 1.709$ also solves your equation $2 + 2^{p+1} = 3^p$. At least up to 9 decimals according to my spreadsheet.


What is the difference between operator and function? We have operator and operands, function and formal arguments. Is the difference purely lexical (we use alphanumerics for funciton identifiers but identify operators with special characters, e.g. "+" and ">=") or it is syntactical, like I guessed here

f(a,b) -- prefix notation used for functions
a.f(b) -- infix notation for method invocation (used in OOP)
a f b  -- infix notation without dot and parenthesis used in operator invocations

so that when we write a + b we have an operator but "+"(a, b) (both ways are acceptable in VHDL) makes it a function? Do tools treat them differently? Can you differentiate them? Can you say that this is not a function, it is an operator or vice-verse? When I read the definitions in wikipedia, I do not see that syntax is a distinguishing feature of a concept. So, is it right that operators and functions are synonyms, two different words for the same thing, same meaning, same notion? I have such guess but have never seen it stated explicitly. Please agree with my guess or say what is the difference.

Historically, my guess is that the difference is rooted in how things were (and still are) translated into machine code.

An operator such as addition of integers or exclusive-or of booleans would be translated into one (or few) assembler commands which would be directly executed by the processor (resp. its ALU). It would also be part of the syntax.

A function (or procedure, method), on the other hand, is a subprogram the (main) program would explicitly jump to during execution. That is, a new stack frame is allocated, register values are saved, parameters are passed and only then is the function executed. See here for details. Furthermore, functions are defined by the programmer.

Younger programming languages have introduced more abstraction, partially or totally removing the distinction. In C#, for instance, you can overload operators for your own types. In Scala, there are no operators but only syntactic sugar for binary methods. Once these languages are compiled, though, you can see which language elements are translated to flat instructions and which to subroutine calls. Keep in mind that optimising and/or just-in-time compilers may liberally move between worlds.

There's is no real difference in computer science.  The distinction occurs to those who do lambda calculus.  There, the difference is akin to math`s distinction between f(x) and f.  Both are functions in some sense, but the latter is the name of the function, while the former is the function itself.


What is a good binary encoding for $\phi$-based balanced ternary arithmetic algorithms? I've been looking for a way to represent the golden ratio ($\phi$) base more efficiently in binary.  The standard binary golden ratio notation works but is horribly space inefficient.  The  Balanced Ternary Tau System (BTTS) is the best I've found but is quite obscure.  The paper describing it in detail is A. Stakhov, Brousentsov's Ternary Principle, Bergman's Number System and Ternary Mirror-symmetrical Arithmetic, 2002.  It is covered in less depth by this blog post.

BTTS is a balanced ternary representation that uses $\phi^2 = \phi + 1$ as a base and 3 values of $\bar 1$ ($-1$), $0$, and $1$ to represent addition or subtraction of powers of $\phi^2$.  The table on page 6 of the paper lists integer values from 0 up to 10, and it can represent any $\phi$-based number as well.

BTTS has some fascinating properties, but being ternary, I didn't think I'd be able to find a compact bit representation for it.

Then I noticed that because of the arithmetic rules, the pattern $\bar 1 \bar 1$ never occurs as long as you only allow numbers $\ge 0$.  This means that the nine possible combinations for each pair of trits ($3^2$) only ever has 8 values, so we can encode 2 trits with 3 bits ($2^3$, a.k.a octal).  Also note that the left-most bit (and also right-most for integers because of the mirror-symmetric property) will only ever be $0$ or $1$ (again for positive numbers only), which lets us encode the left-most trit with only 1 bit.

So a $2^n$-bit number can store $\lfloor 2^n/3\rfloor * 2 + 1$ balanced trits, possibly with a bit left over (maybe a good candidate for a sign bit).  For example, we can represent $10 + 1 = 11$ balanced trits with $15 + 1 = 16$  bits, or $20 + 1 = 21$ balanced trits with $30 + 1 = 31$ bits, with 1 left over (32-bit).  This has much better space density than ordinary golden ratio base binary encoding.

So my question is, what would be a good octal (3-bit) encoding of trit pairs such that we can implement the addition and other arithmetic rules of the BTTS with as little difficulty as possible.  One of the tricky aspects of this system is that carries happen in both directions, i.e.
$1 + 1 = 1 \bar 1 .1$ and $\bar 1 + \bar 1 = \bar 1 1.\bar 1$.

This is my first post here, so please let me know if I need to fix or clarify anything.

--Edit--

ex0du5 asked for some clarification of what I need from a binary representation:

I want to be able to represent positive values of both integers and powers of $\phi$.  The range of representable values need not be as good as binary, but it should be better than phinary per bit.  I want to represent the largest possible set of phinary numbers in the smallest amount of space possible.  Space takes priority over operation count for arithmetic operations.
I need addition to function such that carries happen in both directions.  Addition will be the most common operation for my application.  Consequently it should require as few operations as possible.  If a shorter sequence of operations are possible using a longer bit representation (conflicting with goal 1), then goal 1 takes priority.  Space is more important than speed.
Multiplication only needs to handle integers > 0 multiplied to a phinary number, not arbitrary phinary number multiplication, and so can technically be emulated with a series of additions, though a faster algorithm would be helpful.
I'm ignoring division and subtraction for now, but having algorithms for them would be a bonus.
I need to eventually convert a phinary number to a binary floating point approximation of it's value, but this will happen only just prior to output.  There will be no converting back and forth.

I'm going to try to answer this myself, in the hope that my answer will give others a better idea of what I'm after and lead to better answers than mine.

I found that framing the problem in terms of the original golden ratio base helped me to think about a binary encoding more effectively.  I want to note however that there is no difference between BTTS and phinary except the length of the representation.  Both number systems represent the same set of numbers, save that BTTS more easily encodes negative numbers.  Just as 3 bits can theoretically represent 2 trits of BTTS, they should also be able to represent 4 bits of phinary (which is what 2 trits encode).  Keep in mind that in standard base-$\phi$ all instances of $011_\phi$ are replaced with $100_\phi$ and $1_\phi + 1_\phi = 10.01_\phi$, with a carry both one place to the left and two to the right.  The following table is my best attempt thus far:

Phinary  |  Binary | Octal
0 0 0 0  |  0 0 0  |   0
0 0 0 1  |  0 0 1  |   1
0 0 1 0  |  0 1 0  |   2
0 1 0 0  |  0 1 1  |   3
0 1 0 1  |  1 0 0  |   4
1 0 0 0  |  1 0 1  |   5
1 0 0 1  |  1 1 0  |   6
1 0 1 0  |  1 1 1  |   7

There are some benefits to this encoding. One is that $0_\phi$ and $1_\phi$ are the same as for binary.  Another is that a carry in the forward direction works as expected automatically:

$1010_\phi + 1_\phi = 1011_\phi = 1100_\phi =  1\ 0000_\phi$, and $111_2 + 1_2 = 1\ 000_2$.

Another advantage is that addition almost works as is:

$0101_\phi + 0010_\phi = 0111_\phi = 1001_\phi$ and $100_2 + 010_2 = 110_2$.

As far as I can tell, the only places addition breaks down are for $2_8 + 2_8$, $5_8 + 7_8$ and $7_8 + 7_8$.

$0010_\phi + 0010_\phi = 0020_\phi = 0100.1_\phi$, not $0101_\phi$.
$1000_\phi + 1010_\phi = 2010_\phi = 1\ 0020_\phi = 1\ 0100.1_\phi$, not $1\ 0101_\phi$.
$1010_\phi + 1010_\phi = 2020_\phi = 2100.1_\phi = 1\ 1000.1_\phi$, not $1\ 1001_\phi$.

All other additions work (excluding right carry logic).

We can handle right carries by looking at how they are produced. I'll be using octal for brevity.

1, 4, and 6 produce a right carry of 3 to the previous 3 bits when they are added to themselves or each other.
2 and 7 produce a right carry of 5 added to the previous 3 bits when added to themselves or each other.
4 + 3 gives a right carry of 3 and 5 + 7 gives a right carry of 5.

That's all we need to check for (I think) with the exception of also testing for 2 + 2, 5 + 7, and 7 + 7 and subtracting 1 from the result.

So basically we are taking advantage of the redundancy in a 4-bit phinary representation ($011_\phi = 100_\phi$) to represent the same numbers without redundant cases in 3-bits of binary.
A $2^n$ bit number can store $\lfloor 2^n / 3\rfloor * 4 + 1$ phinary bits.

I'm sure there are clever bit-hacky ways to do this better, but I'm hoping that this will clarify my intent and provide a starting point for both myself and anyone else wanting to tackle this.

The easiest way (assuming I understand your question - I was a very bored Year 10 graduate) is to go to base 2.618~ and use the following system:
if initial bit = 0 then 0
if initial bit = 1 then see next bit.
if next bit = 0 then 1
if next bit = 1 then 2

Advantages: uses space efficently. Uses 1.618~ bits per notation.
Disadvantages: Hard to work with. (and slow).


Understanding PDA and Equivalence of PDA and CFG When we wanted to construct a PDA for $0^n1^n$ the idea was to put all the zeroes (which is a part of the input string) to the stack associated with the PDA, and then pop each of them when we get a $1$ from the latter part of the input.

But when we try to prove that, we can create a PDA for a given CFG we put nonterminals and terminals in the stack and try to match it with input and pop from the stack.

Why do we do something like this? For a problem, we push some part of my input to the stack and match rest of them, and for some problems do not push any input symbol rather only use inputs to compare?

Maybe I am missing some intuitive part of it.

Your question is, in essence,

  Why does the proof that every context-free grammar can be converted to an equivalent PDA proceed in a particular way rather than in another way?

It's hard to answer such a question unless it gets more specific. For example, you can ask why the resulting PDA have to invoke nondeterminism. The answer is that some context-free languages cannot be accepted by a DPDA. Indeed, while this particular proof uses PDAs acting in a certain way, another proof might use PDAs acting in a different way.

One alternative such proof uses the Chomsky–Schützenberger representation theorem. The theorem states that every context-free language can be realized as
$$ h(D \cap R), $$
where $D$ is a Dyck language (the language of all correctly nested strings of parentheses of some fixed number of sorts), $R$ is a regular language, and $h$ is a homomorphism. This theorem, which can be proved directly using context-free grammars (see, for example, Context-free languages and pushdown automata by Autebert, Berstel and Boasson, from the Handbook of Formal Languages), allows to convert a context-free grammar to a PDA which is more like the one for $0^n 1^n$, along the following lines:

Start with a PDA for $D$. This is a PDA that pushes whenever encountering a left parenthesis, and pops whenever encountering a right parenthesis (checking that the two parentheses, the one on the stack and the one being read, have the same type).
Construct a DFA/NFA for $R$, and use the product construction to construct a PDA for $D \cap R$.
Construct a PDA for $h(D \cap R)$ by replacing each transition on $\sigma$ to a transition on $h(\sigma)$.

If you apply this construction to $0^n1^n$ (which you can realize as $D \cap 0^*1^*$, where $D$ is the Dyck language with a single type of left parenthesis $0$ and the corresponding right parenthesis $1$) then you get a PDA which is remarkably similar to the one you describe.

That,

we can create a PDA for a given CFG


Sequencing or continuation-passing in pure lambda-calculus I am trying to solve the following exercise given here.
Consider the following number representation. How to define the addition?
|0| = λx.x
|1| = λx.λx.x
 ...
|n + 1| = λx.|n|

The successor and predecessor operators are easy to define:
Succ n = λx.n
Pred n = n (λx.x)

An "obvious" solution for defining the addition is to use the successor operation plus the test for zero together with the fixed point combinator, something like (Y F) for F given below (the operator if and booleans are defined as usual):
F = λf.(λm n. if (Is0 m) n (Succ (f (Pred m) n))

But defining Is0 seems non-trivial. The problem is that a numeral |N| consumes N+1 arguments, and N arguments are simply erased by it. Hence, if I apply such a function, it seems reasonable to stop its application when it becomes clear that the numeral, e.g. is not an identity. I guess it is some sort of continuation, but I cannot imagine how to model it in the pure lambda-calculus. Maybe someone knows any tips that may help?
A sequencing operator can also help to define the addition. If an application of a numeral |m| is delayed until a numeral |n| is applied to all its arguments, the result will be exactly a numeral |n+m|. Maybe there exists a variant of such a sequencing combinator in the pure lambda-calculus?
The answer which is provided by the author of the exercise uses a non-pure operation (namely, IsProcedure which checks whether its argument is a function).
UPD: It is not hard to do a CPS in lambda-calculus (details for CBV can be found here). Seems that is not enough for solving the problem.
UPD: If we have some version of quote-eval functions for the pure lambda-calculus, then there must be a function $eq$, which recognizes whether the quoted lambda-expressions are syntactically equal, and we can construct Is0 using $eq$. But I doubt that $eq$ is definable. The reason is "genericity lemma" (Barendregt book, lemma 14.3.24). If we were able to test equality on the quoted lambda-terms then ($eq$ (Quote $\Omega$) (Quote $\lambda x.x$)) would return $False$, and the genericity implies that ($eq$ (Quote $\lambda x.x$) (Quote $\lambda x.x$)) would also return $False$. Does that contradict a possibility of constructing Quote in the pure lambda-calculus?

I do not think you will find what you are looking for in the pure lambda calculus. The key is this statement you made:

A sequencing operator can also help to define the addition. If an application of a numeral |m| is delayed until a numeral |n| is applied to all its arguments, ...

Well, models of the lambda calculus are supposed to be like:
$$U \cong U^U$$
And the point of this is that every semantic value $u \in U$ may be applied to something. So it makes no sense to talk about something being "applied to all its arguments." There is no value that cannot be applied to more arguments in the pure lambda calculus.
I don't know off hand of a model/argument that this representation of naturals makes it impossible to implement IsZero, although some thinking about it makes it seem unlikely. However, if it is to be possible in the pure lambda calculus, it will have to make sense semantically, and not be based on notions that are only syntactic.
Edit: here is a sketch of an argument. A definition of $\mathsf{IsZero}$ must eventually reduce like:
$$\mathsf{IsZero}\ n \rightsquigarrow^* n \overrightarrow v$$
The reason is that applying to some number of values is the only mechanism in the lambda calculus to actually distinguish between numerals. It needs to be the case that: $$0 \overrightarrow v = \mathsf{true} \\ \mathsf{s}n \overrightarrow v = \mathsf{false}$$ However, for every $\overrightarrow v$ it is the case that: $$||\overrightarrow v| + k|\overrightarrow v = |k|$$ (where $|\overrightarrow v|$ is the length of $\overrightarrow v$). But only $|1| = \mathsf{false}$ (if that is the convention chosen). In English, there is no bound on the number of terms required to get a boolean by applying a numeral. So there cannot be a $\overrightarrow v$ that satisfies the equations for all numerals, and thus $\mathsf{IsZero}$ cannot be defined.

The most straightforward way to define addition in lambda-calculus is to treat the numbers as if they were linked lists, and catenate the lists.  To do this right, it is necessary to use extra variables to replace the outer variables of each number, so the resulting expression for the second number can be substituted for the inner variable of the resulting expression for the first number.  This yields the following expression for addition:
  λw.λx.λy.λz.w y (x y z)


Is integer sorting possible in O(n) in the transdichotomous model? To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem:

  Given a sequence of length $n$ consisting of finite integers, find the permutation where every element is less than or equal to its successor.

But is there a proof that it doesn't exist, in the transdichotomous model of computation?

Note that I'm not limiting the range of the integers. I'm not limiting solutions to comparison sorts either.

Integers can be stably sorted in $O(n)$ time with $O(1)$ additional space. More precisely, if you have $n$ integers in the range $[1, n^c]$, the can be sorted in O(n) time.

This was only shown a couple of years ago by a team including the late Mihai Pătrașcu (which should surprise nobody who is familiar with his work). It's a remarkable result which I'm surprised more people don't know about, because it means that the problem of sorting integers is (theoretically) solved.

There is a practical algorithm (given in the paper above) if you're allowed to modify keys. Basically, you can compress sorted integers more than you can compress unsorted integers, and the extra space that you gain is precisely equal to the extra memory needed to do the radix sort. They also give an impractical algorithm which supports read-only keys.

For integers, you can use the Radix sort.
It creates buckets and then sorts a list of numbers in $O(bn)$ where $b$ is an upper bound on the size in bits of any integer, and $n$ the number of elements to sort.

If there is no upper bound on the size of your integers, then I don't believe there is any known linear-time sorting algorithm.


Are programming languages ultimately procedural? I'm studying a declarative programming language (Prolog) and in thinking about how certain things are programmed at a low level, a question came to me:

are programming languages ultimately procedural ?

I imagine that by "procedural" you mean languages whose statements refer to changes of state in one ore more objects, but these references are implicit, not explicit (they follow a fixed pattern, for instance, the state change made by the execution of a statement is delivered to the next, resembling a procedure).

You may be referring to the fact that our computers, at a low level of abstraction, are usually state machines - so to speak - so all programming languages would have to be procedural languages disguised as something else.

This has happened for technical and economical reasons, it's not a theoretical imperative. It doesn't have to be that way. Inside your head there is a computational device that isn't like that, and we've been experimenting with all kinds of different models for low level implementation of general-purpose computers for decades. It is not unlikely that, at some point, one of these alternative models becomes commercially viable.

No. not every programming language is procedural at the end. as procedural languages follow the pattern as the statements are typed whereas Non procedural languages keeps jumping to different statements and methods...
take a look here too


What is the relation between Computer Graphics, Discrete Geometry, and Complexity Theory? I am a master computer science student, and I am interested in both geometry and complexity theory.
So I would like to know what is the relations between discrete geometry, computer graphics, and complexity theory ?

I know the answer partially but I would like to have a clear answer since I do like to work on these fields in the future.

Thank you in advance.

Have a look at this slide of David Eppstein in which he tries to draw connections between these subfields. In my opinion, a computational-geometric complexity result is likely to be confined to computational geometry itself without broadly affecting complexity theory in general.

Excerpt from the above slide: Some computational geometry problems have practical applications. Their theoretical hardness are all conjectured to be $NP$-hard but still have not been proven. Some have approximation schemes.


How to find the vertices on simple path between two given vertices in a directed graph Given a directed graph and two distinct vertices S and T, is there a polynomial-time algorithm which finds every vertex which is on at least one simple path from S to T?

It is not difficult to find all vertices that are both successors of S and predecessors of T but this is only a superset of the set above. For example, consider the following graph:
S -> a; a -> b; b -> c; b-> T; c -> a

While a, b and c are all successors of S and predecessors of T, there is no simple path from S to T going through c (because every path from S to T going through c contains twice a and b).

A closely related problem is the following:
Given a directed graph and three distinct vertices S and T and I, is there a polynomial-time algorithm to decide if there exist a simple path from S to T going through I.

A polynomial-time algorithm to this latter problem can be use to build a polynomial algorithm to the former since we can apply it succesively by replacing I by every node in the graph (or more efficiently to every node that is both a succesor of S and a predecessor of T).

Thanks for your answers.
As master foo pointed out, the second problem -- given a directed graph and three distinct vertices $s, t$ and $i$, decide if there exist a simple path from $s$ to $t$ going through $i$ -- is indeed NP-complete.

From the paper The Directed Subgraph Homeomorphism Problem by Steven Fortune, John E. Hopcroft and James Wyllie, it is clear that the pattern graph $s \to i \to t$ is one for which the fixed directed subgraph homeomorphism problem is NP-complete since it is a tree of depth two.

Here are few definitions from this paper:

  The subgraph homeomorphism problem is to determine: if a pattern graph p is
  homeomorphic to a subgraph of an input graph G. The homeomorphism maps nodes
  of P to nodes of G and arcs of P to simple paths in G. The graphs P and G are either both directed or both undirected. The paths in G corresponding to arcs in P must be pairwise node-disjoint. The mapping of nodes in P to nodes in G may be specified or left arbitrary. This problem can be viewed as a generalized path-finding problem. For example, if the pattern graph consists of two disjoint arcs and the node mapping is given, then the problem is equivalent to finding a disjoint pair of paths between specified vertices in
  the input graph.

Basically, only the pattern graphs that are trees of depth one and their reverse graphs (with possibly loops arcs on the root) can be solved in polynomial time.

  Let C be the collection of all directed graphs with a distinguished node called the root possessing the property that either the root is the head of every arc or the root is the tail of every arc. Note that the root may be both the head and tail of some arcs and thus loops at the root are allowed. Equivalently, a graph is in C if, when all loops at the root are deleted and multiple arcs between pairs of nodes are merged into single arcs, the resulting graph is a tree of height at most one.

  [...]

  Next we show that for each pattern P not in C the fixed subgraph homeomorphism
  problem with pattern P is NP-complete.

I have not read the proof yet so I'll stop here.

There is also a close connection from the problem I have just mentionned and the two disjoint paths problem as pointed out by one of my collegue. The two dijsoint paths problem is:

  Given a directed graph and four distinct vertices $s_1, t_1, s_2, t_2$, decide if there exist two pairwise node disjoints simple paths from $s_1$ to $t_2$ and from $s_2$ to $t_2$.

This problem for directed graphs is well known to be NP-complete.
However, there is a simple transformation from the two disjoint paths problem to the $s \to i \to t$ problem. In order to do that, we need to add one extra node $i$ and the two extra edges $t_1 \to i$ and $i \to s_2$.

If there was a polynomial algorithm to solve the $s \to i \to t$ problem, we could use it to solve the two disjoint paths problem in polynomial time with the simple transformation above and thereby solving the $s \to i \to t$ problem.

This is an NP-hard problem.

@article{DBLP:journals/tcs/FortuneHW80,
  author    = {Steven Fortune and
               John E. Hopcroft and
               James Wyllie},
  title     = {The Directed Subgraph Homeomorphism Problem},
  journal   = {Theor. Comput. Sci.},
  volume    = {10},
  year      = {1980},
  pages     = {111-121},
  ee        = {http://dx.doi.org/10.1016/0304-3975(80)90009-2},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


Algorithm for listing all binary trees of a given height I've been trying to find an algorithm to list all binary trees of a given height $h$.

Note that I'm not trying to count them: the number of such trees is given in the OEIS (A001699).

All the algorithms that I have been able to see list all binary trees for a given number of nodes. A very inefficient way of solving the problem would proceed by checking all the trees with a number of nodes between $h+1$ and $2^{h+1}-1$, but this is not great at all.

Any pointers or references would be much appreciated.

As hinted at in comments, just follow the recursive structure of binary trees.

We create a function listbt(h) that lists all binary trees of exactly height h.

type BTree = Leaf | Node(BTree, BTree)

def listbt 0 = { [Leaf] }
|   listbt h = {
  result = []
  for T in (listbt h-1) {
    for k in (0..h-1) {
      for t in (listbt k) {
         result += Node(T, t)
         result += Node(t, T) if k < h-1 || t != T
      }
    }
  }
  return result
}

Correctness follows with an elementary inductive proof over h.

If you memoize the results of listbt this is going to be as efficient as it gets; the sheer number of trees and thereby the number of checks t != T dominate.

Note that if you employ term sharing (i.e. only link t and T in Node(t, T) but do not copy them) you can reduce the size of the output significantly. That only makes sense if your BTree implementation is immutable, though.

My first thought was that this only involves trees built from paths of length h, which are isomorphic to h-bit integers, but those are only a subset of what's needed.  However starting with those all that's needed is to fill in each non-full intermediate node with trees that don't reach all the way to the leaf level.

That is:  Enumerate the $2^{2^h}-1$ nonempty sets of h-bit integers and convert them into trees.  Then for each tree T, for each non-full non-leaf node N (ie having one child only, since it's by definition already on a path to at least one leaf), attach all possible subtrees that don't reach the leaf level (height < height(N)-1, including the empty tree).  Then output the cartesian product across all of the N's in T.

My assertion is that this generates all trees and doesn't generate any twice, since the not-reaching-leaf-level condition makes it impossible to start with one T and convert it into another T' with a different leaf of depth h.


MAX 10-SAT Algorithm The MAX k-SAT problem is:

  “Given a set of clauses C1,…,Ck, each of length k, over a set of
  variables x1,…,xn, find a truth assignment that satisfies as many of
  the clauses as possible.”

I'm trying for find a randomized 0.999-approximation algorithm for the MAX 10-SAT problem. Help :(

Have a look at chapter 5 of this book (available for free):

The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys

The book discusses several randomized algorithms with different performance guarantees for MAX-SAT and MAX CUT (for details of the algorithms, you should have a look at the references in the book).


Difference between weak and strong AI I'm trying to understand the difference between weak and strong AI. For an example, let's say we would pass the turing test - would it show strong AI or weak AI then?

I don't believe that this is standard terminology, but more philosophical. It was mentioned  by John Searle in his "Chinese room argument". As I understand, strong AI is about computers really being intelligent such as having a mind and thus a conciousness, and weak AI refers more to computers being able to simulate the behaviour of human intelligence on only specific problems (think chess, etc.)

Now, the question is - if we would be able to pass the turing test, would it be called weak or strong AI then? Could it be strong AI due to the fact that the turing test is not limited to a certain area or a specific problem?

I came across it on wikipedia: http://en.wikipedia.org/wiki/Chinese_room

The usual distinction is that strong AI, also known as artificial general intelligence, refers to systems that can perform arbitrary tasks requiring intellect, whereas a weak AI is only able to perform specific intellectual tasks.  So, for example, a computer chess program or a system that was able to compose interesting music would be a weak AI, since it only does one thing.

Passing the Turing test would indicate something close a strong AI. Although one could argue that it only requires performing a specific intellectual task (i.e., conversation), that conversation could range over just about anything that humans can intellectualize about.  Indeed, the Wikipedia page I linked above mentions the ability to pass the Turing test as a component of an operational definition of strong AI.

I believe in order to really answer your question; it will take many more years of research in neuroscience, computer science, psychology, and chemistry. Even within this thread itself, how can you be so sure that there are intelligent beings parsing the thread who know english.  One would have to clearly define what it truly means to know something.  Well, we philosophically understand knowledge as something we have personally experienced empirically, which is known as a posteriori knowledge, or a priori knowledge , that is knowledge that is not from direct personal experience.  But who can really deny that there is such a mechanism for a computer to experience things in their own way of experiencing, that which is to be experienced.

The true crux of the problem is that we can't experience another conscience empirically except that of our own, that is, with today's current technology, which is also to say a priori.  And yet even our own consciences is mysterious to us, because it does not directly present itself to you as you would normally perceive an entity.  When you do perceive an entity, you are using your very conscience, and so, how do you begin to perceive that which gives you the ability to perceive in the first place.

What is essential to remember that just because one has not experienced something yet, does not imply that it will not be experienced.  Who is to say that there are not even greater forms of AI, then that of our own Intelligence?  What would be so inherently special about our species, that we would experience the "greatest" kind of "intelligence" that we have, that could not somehow be emulated outside of the constructs of nature.

I recommend reading the following philosophical book, that I myself have currently started reading.  Sein Und Zeit von Martin Heidegger, that is "Being And Time", and there is an english translation for it.


Assign m agents to N points by minimizing the total distance Suppose we have $N$ fixed points (set $S$ with $|S|=N$) on the plane and $m$ agents with fixed, known initial positions ($m<N$) outside $S$. We should transfer the agents so that in our final configuration they are all positioned to different points of $S$. How could we achieve it by minimizing the total distance covered by the agents?

My understanding of this question is that you have a two lists of $n$ two-dimensional coordinates. The first list represents the position of a bunch of agents (robots, maybe, or police cars). The second list represents where those agents need to go (which places need to have police cars dispatched to them), and may be longer than the first list.

It is always possible to minimize the sum distance traveled by all agents, if that's what you're worried about: there are $!n$ ways we could dispatch the robots to new positions, we can enumerate all of them, calculate the distance the agents have to travel, and pick the one that has the least distance. As written, "enumerate all the possibilities" I think counts as an answer to your question, though it's probably not the one you wanted.

There are a couple of more precise questions, all or none of which might be interesting and/or research-level. (I'm not a Theory A person...)

Is a solution possible if each agent (robot/police officer) has to make a decision independently, or has a limited ability to coordinate with other agents?
How quickly could the central dispatcher come up with a plan to dispatch everyone most efficiently? Aaron Roth observes in the comments that this can be solved as a min-cost flow problem. I think that solution looks like this (hopefully I won't make a total fool of myself here): each agent is a source vertex and each dispatch target is an intermediate vertex. There is a capacity-1 edge from each source to a vertex representing the dispatch target, and the cost along that edge is proportional to the distance between the agent's initial position and the dispatch target. There is also a capacity-1, cost-0 edge from each dispatch target vertex to the sink.
How quickly could the central dispatcher come up with a plan to dispatch everyone that is some multiple of the most efficient solution?

how about creating tuples of all M agents with N points, sorting them by distance and then greedily picking the first M.
this is basically what kruskal does. we could modulate this as a graph where we have a root noe connected to all agents(with edge weight 0) then create all edges from agents to points with the distance as weight, the mst should be the answer we are looking for.
is this correct?


Why do we need assembly language? We mostly write programme in high level language. So while studying I came across assembly language. So an assembler converts assembly language to machine language and a compiler does the same with high level language. I found assembly language has instructions like move r1 r3 , move a 5 etc. And it is rather hard to study. So why was assembly language created?or was it the one that came first even before high level language? Why am I studying about assemblers in my computer engineering class?

"So why was assembly language created?"

Assembly language was created as an exact shorthand for machine level coding, so that you wouldn't have to count 0s and 1s all day.  It works the same as machine level code: with instructions and operands.

"Which one came first?"

Wikipedia has a good article about the History of Programming Languages

"Why am I studying about assemblers in my computer engineering class?"

  Though it's true, you probably won't find yourself writing your next
  customer's app in assembly, there is still much to gain from learning
  assembly.

  Today, assembly language is used primarily for direct
  hardware manipulation, access to specialized processor instructions,
  or to address critical performance issues. Typical uses are device
  drivers, low-level embedded systems, and real-time systems.

  Assembly language is as close to the processor as you can get as a programmer
  so a well designed algorithm is blazing -- assembly is great for speed
  optimization. It's all about performance and efficiency. Assembly
  language gives you complete control over the system's resources. Much
  like an assembly line, you write code to push single values into
  registers, deal with memory addresses directly to retrieve values or
  pointers. (source: codeproject.com)

To date myself, I first learned RPG II using an IBM System 32, and later learned APL on a 370. I was all about size and speed. My mantra was smaller and faster. Assembly is the most compact and fastest language out there. I would make test programs in both C and Assembly. Where C programs would require 100's of Kb, an equivalent Assembly program would often be less that 5 Kb. When studying the output of the C compiler I would find code that would check and recheck parameters make conditional checks for possible errors that were quite often rare and exotic and quite unnecessary, all of which took time, but the biggest memory bloat was passing absolutely everything to and from the stack.

In today's programming environment writing code provides an extra level of security and protection. Being able to read info directly from a piece of hardware that is not accessible to high level languages, allows you to encrypt with Assembly in a way that a program can only be used on that particular machine. For example encrypting a user key using the MAC address of the network interface, and then parking that key on a specific unregistered sector of the hard drive then marking the sector as bad so that other files can't overwrite it. Of course you lose the sector, but what is that? 2048 or 4096 bytes out of billions or trillions?


Regular expression for words where the same symbol can repeat at most two times consecutively? Having the alphabet $\{a, b\}$, how can I generate a regular expression for the language that does not have substring of three or more consecutive same symbol?

For example, I can't have ${baaab}$ nor ${abbba}$, but I can have ${abbaabba}$.

Every string over $\{a,b\}$ can be decomposed into runs of the same letter. For example, $$ abbaabba = a^1 b^2 a^2 b^2 a. $$
Since the alphabet is binary, the runs just alternate between the two letter. In your case, every run has length 1 or 2. We can distinguish between four types of words in your language, depending on which run is first and which run is last; additionally there are some corner cases. The set of words in your language in which the first run is $a$s and the last run is $b$s corresponds to the regular expression $((a+aa)(b+bb))^+$.

I'll let you figure out the rest.

How about this C++ code?

string loc;
char sent[] = {a, b};
for (int i=0; i<N; i++)
{
   int pos = rand()%2;
   if (i>=2)
   {
      if (loc[i-2]==loc[i-1])
      {
         if (sent[i-2] == loc[i-1)
           loc.push_back(sent[!loc[i-1]]);
         else
           loc.push_back(sent[loc[i-1]]);
      }
      else
        loc.push_back(sent[pos]);
   }
   else
     loc.push_back(sent[pos]);
}


What is the formal justification for the correctness of the second formulation of rod cutting DP solution CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference.

Define $r_j$ to be the optimal way to cut a rod of integer length $j$.
Since we do not know where is the optimal place to cut the rod we consider every location $ i  \in \{0,\cdots,j\}$ (essentially doing exhaustive search) to do the cut. Then we are left with two rods of length $i$ and $j-i$ to cut optimally.
If we consider every location we could do a cut and then cut the remaining rods optimally, then we have essentially solved $r_j$ optimally. i.e. we get the following recursion:

$$ r_j = \max \{p_n, r_1 + r_{k-1}, r_2 +r_{j-2}, ..., r_{j-1} + r_1 \}$$

However there seems to be an alternative (or maybe simpler strategy to solve such a problem):

$$r_n = \max_{1 \leq i \leq n} \{ p_i + r_{n-i} \}$$

CLRS has the following discussion about it:

  In a related, but slightly simpler, way to arrange a recursive
  structure for the rod- cutting problem, we view a decomposition as
  consisting of a first piece of length $i$ cut off the left-hand end,
  and then a right-hand remainder of length $n -i$. Only the remainder,
  and not the first piece, may be further divided. We may view every
  decomposition of a length-n rod in this way: as a first piece followed
  by some decomposition of the remainder. When doing so, we can couch
  the solution with no cuts at all as saying that the first piece has
  size $i = n$ and revenue $p_j$ and that the remainder has size $0$
  with corresponding revenue $r_0 = 0$.
  In this formulation, an optimal solution embodies the solution to only one related subproblem-the remainder-rather than two.

Personally I've always found it harder to convince myself that this in fact optimal (and that is therefore equivalent to the first one). Therefore I was wondering if anyone had a good argument or maybe a good formal proof to arguing why this second formulation is in fact optimal.

Usually I've tried to justify it to myself by having the following thought experiment: well, if I want to have an optimal revenue I need to make sure that I some how explore all good solutions exhaustively and not miss any. If I want the solution to the whole thing $r_j$ then it could be that the full rod is required, then the cut is at position $i=n$. That is if the optimal solution contains no cuts. But if we have a cut we will have some part of the rod that must remain un cut.
If that is the case, then just consider all possible full parts of the rod from the beginning of the rod to the end that remain uncut. Basically, it seems that the solution is as follow, every solution to $r_j$ must contain a piece of rod from the beginning that is uncut to some cutting location $i$.
Since this is part of the optimal solution, we just consider all beginnings that are "full" rods up to $i$ and then make sure to solve the remaining optimally.
This justification feels close to being the argument of correctness but for some reason it just seems to be missing something (wish I knew what it was).

Does someone know how to write a better clear proof of correctness of this? If its really formal or rigorous that is ok with me, I just sort of want some proof for the second recursion where there is no doubt that its correct.

Thanks for the help!

Recall the rod cutting problem.
You manufacture steel rods of some fixed length and sell them in segments of integer length and because of the laws of supply and demand, the price per length is not constant.
Given a set of prices (i.e. an array $p_i$ indicating the price for an integer cut of length $i$) for each possible length segment, how should you cut a given rod of length $n$ into integer length segments to maximize revenue?
You may assume that no cost or loss incurred with each cut.

The proof of $r_n = \max_{1 \leq i \leq n} (p_i + r_{n-i})$ is divided into two parts. In the first part, we prove that $r_n \geq \max_{1 \leq i \leq n} (p_i + r_{n-i})$. In the second part, we prove that $r_n \leq \max_{1 \leq i \leq n} (p_i + r_{n-i})$.

First part. It suffices to prove that for each $1 \leq i \leq n$, $r_n \geq p_i + r_{n-i}$. Indeed, consider first breaking the rod into a piece of size $i$ and a piece of size $n-i$, and then cutting the second piece optimally. This strategy guarantees a profit of $p_i + r_{n-i}$.

Second part. It suffices to prove that for some $1 \leq i \leq n$, $r_n \leq p_i + r_{n-i}$. Consider any way of cutting the rod. Let $i$ be the size of the leftmost piece, which results in a profit of $p_i$. The other pieces (if any), put together, form a rod of size $n-i$, and so the profit gained from them is at most $r_{n-i}$. In total, the profit is at most $p_i + r_{n-i}$. In particular, the optimal profit $p_n$ is at most $p_i + r_{n-i}$.

Let's assume the optimal cut for 8 is: $8 = 1+2+3+2$.

When $i=3$, it means you cut at length 3, and leave 5 as a second part.

You can get the optimal value from $r_3$ and $r_5$, of course.

But please be noted, you must have already get this optimal value when $i=1$. When $i=1$, $r_8 = r_1 + r_7$, where $r_7$ can give you optimal cut as $7 = 2+3+2$.

Therefore, to avoid redundant re-calculation as above, keeping one side uncut, and try to find the best cut at the other side is the best solution.


Propositional Logic: Entailment Given the sentences, S1, S2, if S1 |= S2 then all models that satisfy S1 also satisfy S2, how is the following statement correct?
A ∧ ¬A |= B
How can something and not something equate to true?
I am stuck trying to work out how true and false can still entail true, actually how can A and ¬A occur at the same time?
Thanks.

It's not easy to give a full explanation without knowing your axioms and rules, however, $A \land \neg A$ is a contradiction, and it is by exploiting that, that you can prove whatever you like.
First, let $\top = A \lor \neg A$.
We know that "true or whatever else" must be true.  Since $\top$ is a tautology, then $\top \lor B$ must be true.
But since $A \land \neg A = \neg (A \lor \neg A) = \neg \top$ is assumed to be true we conclude the following:

from $\top \lor B$ and $\neg \top$
$B$

It all hinges on the fact that $A \lor \neg A$ is a tautology and that you assume that the negation of a tautology is true.
So to answer your question "actually how can $A$ and $\neg A$ occur at the same time?" It cannot, unless you have a contradiction.  When you assume a contradiction, you can prove anything.

Think of it this way.
There are no elements of the empty set $\emptyset$. Moreover, for all sets $A$, $\emptyset \subseteq A$.
But what does subset actually mean? $A \subseteq B$ means that any element of $A$ must be an element of $B$. That is, $\forall x \in A, x \in B$.
It follows that for all sets $A$, $\forall x \in \emptyset, x \in A$. Every single element of $\emptyset$, every one of them, every none of them, is an element of every other set.
Assuming that $A \wedge \neg A$ is false in your logic (there are logics that admit controlled contradiction), then there are no models satisfy $S_1$. It follows that all models that satisfy $S_1$, every one of them, every none of them, also satisfy $S_2$.


Isn't NP problems always also co-NP problems? I think I have a hard time understanding the definition for NP. It says: "All decision problem where every yes-instance can be verified in polynomial time". But doesn't this just mean that every possible solution can be verified to be yes or no in polynomial time? If co-NP then is verifying no-instances isn't NP already doing that?

So simply put, if you can verifiy yes-instances can't you implicitly verifiy no-instances?

The definition you give in the quesition is very imprecise so it's understandable that you've misunderstood it.  The formal definitions are given at our reference question on NP.

A decision problem is in NP if there's some polynomial $p$ and an ordinary, deterministic polynomial-time Turing machine $M$ such that:

For every "yes" instance $x$, there is some $y$ with $|y|\leq p(|x|)$ such that $M$ accepts the string $x,y$;
For every "no" instance $x$, $M$ rejects all strings $x,y$.

So, for example, 3-COLOURABILITY is in NP: the string $y$ is just a description of a $3$-colouring and $M$ accepts $x,y$ if $y$ is a valid $3$-colouring of the graph $x$ and rejects otherwise.  The point is not that you can "verify 'yes' instances" but, rather, that every "yes" instance has a certificate $y$ that you can use to easily prove that it really is a "yes" instance.

But there's a significant asymmetry in the definition.  If you give $M$ a "yes" input and a certificate $y$, then $M$ will say "I agree – that's a 'yes' instance." However, there's no input you can give it that will cause it to say "I agree – that's a 'no' instance." For any certificate you try, it will just say "That doesn't convince me it's a 'yes'." You could, of course, try all possible certificates. That would certainly prove that you had a "no" instance but there's a problem: there are exponentially many possible certificates to try, so trying all of them doesn't give you a polynomial-time algorithm.

No. As an intuitive argument, consider verifying primality. It is easy to show you that $8633$ is composite by $8633 = 89 \times 97$, whereas it is not evident that how this helps to develop a method to persuade you that some number is indeed a prime.


Reducing linear programming to positive linear programming Suppose we have an oracle that solves problems of the form

\begin{align*}
\text{maximize} ~~ & c^T x
\\
\text{subject to} ~~ & A x = b, x\geq 0
\end{align*}

when $c\geq 0$ (all coefficients in the maximization target are non-negative).

Can it be used to efficiently solve general linear programs?

FAILED ATTEMPT #1: replace each variable $x_i$ that appears with a negative coefficient in $c^T x$, with another variable $y_i := - x_i$.
Unfortunately, this $y_i$ does not satisfy the non-negativity constraint.

FAILED ATTEMPT #2: Ensure that all elements in $b$ are non-positive (multiplying the equation by -1 if necessary). Then create the dual LP:

\begin{align*}
\text{maximize} ~~ & - b^T y
\\
\text{subject to} ~~ & A^T y \geq c
\end{align*}

Here, all the coefficients in the objective are non-negative. However, this form does not match the form that the oracle can solve, since the constraints are not equational constraints and the variables $y$ are unbounded.

You can add a variable $y$ and a linear equality $y=c^Tx+c_0$ for some $c_0$. Then, the original problem is equivalent to maximizing $y$ in the new system.

Except for the condition $y\geq 0$. That is where $c_0$ comes in. We need to make $c_0$ large enough that for some feasible $x$ (that is $Ax=b$ and $x\geq 0$ hold) we have $c^Tx+c_0\geq 0$. In that case it does not matter that non-negativity cuts away parts of the feasible space. The optimal value is still the same.

So how to choose $c_0$? I am not an expert in linear optimization. Is finding some feasible $x_0$ easier than finding one that maximizes the objective function? If so, we can take $c_0$ to be $-c^Tx_0$.

If the given coefficients are rationals, there is another way.
First, let us establish that the polytope of feasible $x$ has vertices (unless it is empty):
Let $p$ be a point in a minimum-dimensional boundary cell of said polytope.
For contradiction, assume that the dimension of this cell is $\geq 1$.
Then, there is a different point $q$ in the same cell. As the cell has minimum dimension, it is unbounded, so points of the form $r=p+t(q-p)$ are in the same cell and thus in the polytope. As $q-p\not=0$, some such $r$ have negative coordinates, contradicting the polytope condition $r\geq 0$.

Now, make all coefficients of $A$ and $b$ integer by multiplying with the common denominator. Let $n$ be the dimension (the length of the vector $c$) and let $M$ be the maximum absolute value of any coefficient of $A$, $b$, or $c$. Then we can bound the coordinates of any vertex of the feasible polytope by $n!\cdot M^n$. Thus, choose $c_0:=n\cdot n!\cdot M^{n+1}$.

[EDIT]

Yet another approach, in case you are willing to call the oracle multiple times: First, try the above with $c_0=0$. If you get a solution or the answer "unbounded", you are fine. If the answer is "unsolvable", you need to find out if there are solutions with negative objective function. Hence, set $z=-c^T$ and maximize $z$ instead. If you get a solution, you can use it as $x_0$. If you get "unsolvable" again, you are done as well. The last case is the answer "unbounded". Then, you need to try out ever larger $c_0$ (for few oracle calls, use a fast-growing function; the Ackermann function may do) until you get a solution.

You can replace a variable x that has no restriction to be positive with two variables $x^+ - x^-$ where both $x^+$ and $x^-$ are restricted to be positive. All their coefficients will be identical except that they have the opposite sign.

In the simplex algorithm, it is always possible to put only one of these into the basis. Actually, you can avoid any additional calculations by just keeping track whether any basis variable is currently positive or negative.


Minimal number of states for an NFA of all different words Given $\Sigma =\{0,1,@\}$, I am looking at a language $L=\{u@v | u,v\in \{0,1\}^k\wedge u\neq v\}$. So $u,v$ have only $0,1$s, same length $k$, yet are different.
Also, for me $k$ is a known constant. So the language ìs regular (at most $(2^k)\cdot (2^k-1)$ words).
I want to build the most efficient NFA for $L$. So far, I have been able to cone up with an NFA of $O(k^2)$ states, but I want to find one with $O(k)$ states. Of course one could argue that as $k$ is constant, its the same as $O(1)$, but assuming $k$ is a constant parameter - that is, given a value of $k$, I construct $L$ and an NFA for $L$ with $O(k)$ states.
My idea to use $k^2$ states:

A path for each index, as $u$ and $v$ of size $k$... they differ means there is at least one $1\leq i \leq k$ where they differ at that character.
Read '0' in $i$th character and '1' in $i+k+1$th character (due to '@'). Or other way.
In between make sure that $u$s length and $v$s length is $k$. Which characters you read in between? I don't care.

But this will give me around $2k$ states (I can do a bit less, but still $O(k)$) for each index. Total $O(k^2)$, as there are $k$ indices.
I would ask for a way to improve my idea, to use $O(k)$ states. Or maybe a totally different approach.

Here is a matching $\Omega(k^2)$ lower bound.
Consider any NFA for your language. Let $Q_i$ be the set of states $q$ such that:

There is some word $w$ of length $i$ such that the NFA could be at state $q$ after reading $w$.
There is some word $z$ such that starting at $q$, after reading $z$ the NFA could be at an accepting state.

Since all words in $L$ have the same length, the sets $Q_i$ must be disjoint.
Now let $i \in \{0,\ldots,k\}$. For every word $w \in \{0,1\}^i$, let $Q_i(w) \subseteq Q_i$ be the set of states that the NFA could be in after reading $w$. I claim that if $w_1 \neq w_2$ then $Q_i(w_1) \neq Q_i(w_2)$. Indeed, the NFA behaves differently after reading $w_1$ and $w_2$: it accepts $w_1 0^{k-i} @ w_2 0^{k-i}$ but rejects $w_2 0^{k-i} @ w_2 0^{k-i}$. It follows that $2^{|Q_i|} \geq 2^i$, and so $|Q_i| \geq i$. Therefore the NFA has at least
$$ \sum_{i=0}^k i = \Omega(k^2) $$
many states.

I don't understand how you could do this in less than $2^k$ states. Your description of your plan doesn't fit at all with how I understand NFAs. You talk about reading to the $i$th character, as if you had some kind of random access, but an NFA must read symbols in order, and any knowledge it needs from those symbols must be reflected as part of the state it transitions to afterwards.
Following is my argument that at least $2^k$ states are required.
Let $q_x$ be the state the machine reaches after reading $x \in \{0,1\}^k$, and let $u,v\in \{0,1\}^k\wedge u\neq v$. Is it possible that $q_u=q_v$? No, because there is at least one set of remaining symbols that $q_u$ must accept, and that $q_v$ must reject: namely, a repetition of $v$.
Therefore, $q_x$ must be unique for each $x$. Since $x$ is $k$ items long, there are $2^k$ unique $x$s, each needing their own distinct $q_x$.
This is a lower bound; in practice you will need at least $k$ more states to use while consuming $v$, and one for consuming the $@$ symbol.


What exactly can finite-state machines not do? I know finite-state machines can be used to solve yes/no kind of problems, such as finding whether a word is in language or not. Can somebody tell me exactly what FSM cannot do and why?

The answer depends on what you mean by FSM.

If by FSM you mean finite automaton, then there's a lot that it can't do. As others have pointed out, you can't remember more than a constant amount of information using a finite automaton; the memory must be encoded in the state. This means you can't do things like recognize $a^nb^n$, since you'd need to remember how many $a$ symbols you've seen, which is not possible unless you have an arbitrary amount of memory. The pumping lemma for regular languages and, especially, the Myhill-Nerode theorem offer insight into the kinds of things that can and cannot be done.

If by FSM you mean any automaton formalism which is limited to using finitely many states, then Turing machines are among the most computationally capable FSM models available. Indeed, anything which is effectively computable is computable by a Turing machine, according to the Church-Turing thesis. However, there are still limitations to what a Turing machine can decide: there are problems it cannot answer, such as the halting problem.

Models which aren't limited to a finite number of states aren't particularly interesting for a few reasons, most prominent of which are the following: they are of limited practical importance since we cannot construct real computers with infinitely many configurations; any language can be recognized in such a model by mapping strings in the language to unique accepting states, and strings not in the language to unique non-accepting states.

FSM doesn't have memory, It can't remember the things unlike Push Down Automata (i.e nothing but a FSM with Memory).Anything which require memory can't accepted by FSM.


What would dynamically-typed languages actually do if type enforcement was removed? I program in Python, which is a well-known dynamically typed language. I understand dynamic typing to mean mainly that "operations" (in a loose sense) in the language are either allowed or denied (raise an exception) based on the type of their operands, and that this type-checking is deferred as long as possible. My question is this: if that is what a fair characterization of dynamic languages, what would happen if the run-time type checking was removed?

It seems to me that if you want to make a meaningful distinction between a dynamically typed language like Python and an untyped language, you would have to define what actually would happen in the untyped language in situations in which the type system of a dynamic language would take action. For example, in Python, if I attempt to subtract an Integer from a String, e.g., "spam" - 5, I receive a TypeError. If that's what makes Python dynamically typed, what would an "untyped Python" do in that situation?

A language in which automatic type checking is not available, an operation would make assumptions about the types of its operands. On the event that these assumptions are false, the operation, not knowing anything about this, may produce nonsense results.

Assembly is such language. It has, for instance, separate addition operations for integers and floats. If you perform integer addition on floating point values you will get a result which is correct as neither integer nor float. Depending on your definition of correct.

The below is the conclusion that I have drawn from answers to the SO question Does “untyped” also mean “dynamically typed” in the academic CS world?.

For a dynamic programming language L the following two statements are equivalent:

L is dynamically typed.
L is untyped.

In other words, there is no meaningful distinction between a dynamically typed language and an untyped language, whenever we speak about dynamic languages like Python, Ruby or JavaScript. These are high-level languages that implement some object model. Objects are the only data entities that can be referenced. There is no notion of pointers to memory chunks, no pointer arithmetic. There are two main kinds of situations that are reported as type error: (1) evaluation request is not understood, (2) the request is understood but rejected because a transition to an illegal state is requested.

A canonic representant of the (1) group is method (or attribute) resolution failure. That is, for an object o, there is a request of method invocation o.m() but no method is associated with o under the name m. (And no interception handler is defined.)

An example for the (2) group is a request to create a class that is a subclass of a non-class object (applies to both Python and Ruby). Or, in Python, to create a class with the metaclass parameter used whose value is a class that is not a descendant of the type class (i.e. whose value is not a metaclass). Or, in Ruby (as of 2016), to create a subclass of the Class class.

In my opinion, only the type enforcements of the (2) group can conceivably be removed. This would result into the possibility to create wild and/or unsupported  structures between objects. But in the case of the (1) group, there is no clear candidate of what a "type enforcement removal" should mean. One can only invent some nonsense behavior in response to such situations.

(Added after 2 days.)

To me, the title question can be formulated as:
How can a dynamic object-oriented language like Python potentially be untyped?
My answer is that there are basically just two ways how to achieve this:

Via the dynamically typed ↔ untyped equivalence.
By inventing nonsense behavior (a generalized nasal demon) for method resolution.

Let us consider Python, Ruby and JavaScript
as three significant languages that are relevant to the title question.
All of them are popular dynamic OO languages
in which
"classes are objects" and in all of them
there is a built-in TypeError class.
(JavaScript is sometimes claimed to be classless.
We will follow here JavaScript: The Definitive Guide by D. Flanagan,
where there classes are explicitly mentioned, including the
TypeError class.
Moreover, the notion of a class is explicitly supported in ECMAScript 6.)
At this point let us emphasize, that assembly or the C language
mentioned in some answers or comments are NOT relevant.

Having established the group of three languages that are relevant to the question
we can observe that the
dynamically typed ↔ untyped equivalence has already been established in
the literature.
There are probably more statements that the 3 languages are dynamically typed
but there is also considerable amount of statements about their
untypedness or typelessness.
As for Python:
(Py1), (Py2), (Py3), (Py4), (Py5), (Py6)
(Py7), (Py8), (Py9), (Py10), (Py11), (Py12).
As for Ruby:
(Rb1), (Rb2), (Rb3), (Rb4), (Rb5).
As for JavaScript:
(Js1) – quoted by Wikipedia in the opening sentence,
(Js2), (Js3).
Moreover, there are also articles ((eq1), (eq2)) where the equivalence
(dynamically typed ↔ untyped) is suggested explicitly.

The reason behind this terminological paradox is that removing what
is called run-time type checking would mean not throwing any TypeErrors
which is absurd. (Why then throw any Error at all?)
One can imagine that there is no detection of possible invalid states
as I have mentioned before.
(To give an example also for JavaScript, the x.__proto__ = x assignment
is a request to form a cycle in inheritance, and thus
rejected as a TypeError.)
But without the (absurd) concept of nasal demons,
I cannot imagine what should a "removal of type enforcement" mean in the
o.m() case of method resolution failure.
What is a possible meaning of calling a missing method?

I also think that the 1 + "a" example of typechecked  Python code
provided in the answer by Gilles
should be presented for a user-defined function, rather than a built-in one.
In this case, disallowing type checking would in fact mean
to prohibit the programmer from using isinstance
(issubclass, type(), __class__, ...)
and/or throwing Errors.
This is absurd too.

The only non-absurd removal of a type constraint that I am aware of
is disregarding the number of method arguments
– something that is realized in JavaScript
(probably due to missing default argument values).
But I doubt that this should be the dividing point - the reason why
JavaScript should be considered untyped while Python and Ruby dynamically typed.

Summed up, the
dynamically typed ↔ untyped equivalence can be
used as a mnemonic for an inconsistency in the terminology.
It is better than to pretend that the notions are well established.


Prove L = {a = b ⊕ c | a, b, c ∈{0, 1}*} is not regular Given that language $L = \{a = b ⊕ c \mid a, b, c ∈ \{0,1\}^*, a = b \oplus c\}$, with an alphabet $Σ = \{⊕, =, 0, 1\}$, I need to prove that this language is not regular. The following is as far as I have gotten in my proof, but I am getting stuck when showing why it is contradicting the pumping lemma:

$s = (1^p = 1^p ⊕ 0^p)$

$x = 1^l$

$y = 1^m$, where $l+m \le p$ and $m > 0$

$z = (1^{p-l-m}=1^p ⊕ 0^p)$

Taking $i=2$, $xy^2z = (1^l1^{2m}1^{p-l-m}=1^p ⊕ 0^p) = (1^{p+m}=1^p ⊕ 0^p)$

—This is where I am getting stuck. From my example, this appears to be a contradiction, but there is nothing in the language dictating that $b$ and $c$ be of equal lengths. Were they to be different lengths, it could certainly be possible that no contradiction would be found by adding $m$ to $p$. How could I fix my proof via pumping lemma?

---EDIT: SECOND TRY---

$s = ((10)^p = (01)^p ⊕ (10)^p)$

$x = (10)^l$

$y = (10)^m$, where $l+m \le p$ and $m > 0$

$z = ((10)^{p-l-m}=(01)^p ⊕ (10)^p)$

Taking $i=0$, $xy^0z = ((10)^l(10)^{p-l-m}=(01)^p ⊕ (10)^p) = ((10)^{p-m}=(01)^p ⊕ (10)^p)$

Now, I have that $|a|<|b|$ and $|a|<c$, which is not possible, since the result of the exclusive-or must contain a leading 1, which cannot be truncated to a smaller string length. Therefore, this is a contradiction.

Is this a contradiction strong enough to prove the language is not regular? It only works in the case of a leading 1; do I need to show something that is a contradiction even with leading 0's?

Suppose $L$ were regular. Let $p$ be the pumping constant assumed to exist and consider the string

$$s = 1^p = 1^p \oplus 0^p$$

Clearly, $|s| \geq p$ so for some strings $x,y,z$ we have $s = xyz$ where

$|xy| \leq p$
$|y| > 0$
$xy^iz \in L$ for all $i \geq 0$

If condition 1 is to hold, $y$ must be a string of $1$s. If condition 2 is to also hold, then $y = 1^k$ for some $k > 0$. But then condition 3 fails, since $xy^0z \notin L$.

For $xy^0z =  1^{p-k} = 1^p \oplus 0^k$, and this identity is false irrespective of whether we require $w_1 \oplus w_2$ to be defined for strings of the same length only, or in general.

Thought A)

Perhaps your definition of "a" needs to be reworked;
eg. not count all the leading zeros as significant (0000 = 0).
You can substantiate this by making the case that XOR is an arithmetic operation.

In this way given an acceptor for a given length of string you could pump through another string that output the same result proving that its not regular.

010 XOR 010 = 0
and
0110 XOR 0110 = 0

Thought B)

There are no "real" contradictions for the language "a". It consists of every string of { 0,1 }* by definition. However using thought A) you can pump through multiple "definitions" of an accepted word in the language.

Thought C)

What do you think?


Using humans as components to build a computer? Ok before I start I realise this is on the fringe of on-topic (I have read the Questions help for this site), particularly as this is not a real-world problem. However:

I cannot find anything relevant on Google
From a purist point of view surely it must fall within Computer Science?

In any case, if I have overstepped a boundary then I apologise and welcome the  Closure as I am an avid user of other SE sites so I understand the issues.

Caveats aside, here it is:
I have long wondered if it would be possible to build a functioning computing system, using humans as discrete logic components, to solve problems that individual humans could not solve in a practical timesscale. For example, imagine a number of humans stranded on an island without any machines, that needed to crunch some complex numbers to escape.

I imagine arranging people so that they receive inputs from other groups within the system, make simple decisions (perhaps binary decisions, perhaps not) and pass the outputs to other groups.

Then I imagine some kind of programming language could be developed to control the data and computation flow and the language could be used to solve complex problems without individuals understanding the overall problem.

So I guess the above is not an answerable question- but does anyone know of any research, books, papers or whatever on what it would take to achieve, what kinds of of problems could be addressed and potentially solved, what kind of control language could be deployed and how the architecture could be scaled up to handled more complex problems?

I suppose, in essence, I am looking for anything on "idealised" atomic (as in self contained) and standard computing units that could be arranged at will- I am just thinking in human terms.

I find the idea fascinating and alluring. I'd love to try it out one day and see what performance could be achieved! Sorry for the tags I have used, as I was searching the tags here I quickly became aware I have no idea of the correct terminology for what I am thinking, though I am sure it exists within the field...

Actually, until the 1950s the word computer was used to refer to a human who did arithmetic calculations.  One (or more) of Richard Feynman's (many) autobiographies contains anecdotes about his time on the Manhattan project, where he ran the group of human computers. For arranging a group of humans to perform a complex computation they wouldn't start with discrete logic components, but rather have each human perform multiple arithmetic operations and then coordinate their results (along with some error checking.)  How to organize these kinds of large computations may be covered in numerical methods books from the 1940s or early 1950s.

The first version of the Logic Theorist by Newell, Simon and Shaw was simulated using humans in 1956 (less expensive than computer time).  They later won a Turing Award for basic contributions to AI, the psychology of human cognition and list processing (the Logic Theorist may have been the first program to use linked-lists to represent data structures.)  And the experience influenced Simon's later ideas on emergent behavior (see his Sciences of the Artificial.)

As pointed out in the comments and other answers, there is now an emerging discipline of Human-Based Computation, where various incentives are used to get humans to do parts of a larger calculation, where those parts make good use of human problem solving or pattern recognition.  One example of this is reCaptcha, where users need to enter two words to prove that they are not a bot, one a distorted image that is used for the actual "proof" and the second an actual word from a scanned book, which is used to produce a digitized version of the book.  Another example is the Amazon Mechanical Turk where a business can outsource "microtasks" to human workers for small sums of money.  The mechanical turk has been used, for example, to collect annotations on 250,000 images for image processing research.  The key seems to be breaking the problem down into a pile of independent work items, with significant amounts of redundancy used to reduce errors.  (E.g., you assign the same work item to 2 different humans, and then if they provide conflicting answers you assign the work item to a third human to resolve the difference.)

This is a real world challenge and closely relates to workflows. The idea of having a workflow is to have a queue or ordered or un-ordered list of tasks that people or computers have to pick up at any time to complete a bigger process in which they may or may not be concerned or know about at all.

In effect you will have a machine that can make something and usually this is the main challenge and/or goal for an entrepreneur, mostly because money can be made if you can automate something and then step away from it (like a machine).

The inherent problem with using humans is that they make more mistakes or get bored with the work. Basically, this is also the reason for entrepreneurs to try to replace the real people parts with mechanical or computers parts.


How is it valid to use oracles in mathematical arguments? Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle".  Thus, Oracles do not exist almost by definition.  I don't understand how one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course).  Have a problem, ask the "magic" Oracle, problem solved $O(1)$ time.  Of course you can't say anything about what is happening in the oracle, because its "magic". From this point of view, Turing Machines (bizarre fetish formalism if you ask me) with Oracles do not exist.  Also, that X historic proofs rely on oracles makes oracle arguments valid is a circular argument.

Oracles are a very general formalization of the idea, "If I could solve $X$ efficiently, I could use that to solve $Y$ efficiently."  I accept that it sounds a bit silly to go as far as "If I could solve problem $X$ in constant time, I could use that to solve $Y$ efficiently" but, actually, that doesn't make any real difference at the level of detail we're working at, here.

For example, consider an oracle $O_1$ that can solve SAT in constant time, versus an oracle $O_2$ that solves SAT in, say, cubic time. The problems you can solve in polynomial time with access to $O_1$ are exactly the same as the ones you can solve in polynomial time with access to $O_2$. Sure, the polynomial will be better if you use $O_1$, but it's still a polynomial if you use $O_2$. In fact, the answer won't change whatever polynomial bound you assume on the running time of the oracle so we choose to simplify the analysis by choosing the simplest polynomial possible: $1$.

In some cases, you can see oracle arguments as hedging your bets. Although you lead your question with "Oracles don't exist", we don't actually know that. Suppose somebody produced a polynomial-time algorithm for SAT tomorrow. Wouldn't it be a shame if all we could solve with it was SAT? But because we have all kinds of oracle reductions available to us, we could already solve any NP-complete problem efficiently (the many-one reductions used to prove problems NP-complete are just a very restricted kind of oracle reduction). Conversely, if somebody proves tomorrow that SAT has no efficient algorithm, then all that work on oracles tells us that all the other NP-complete problems are also genuinely hard.

But remember that oracle arguments are conditional: if I could do $X$, then I could also do $Y$. If it turns out that you can't do $X$ then, OK, maybe you can't do $Y$ after all. But it's still a perfectly valid what-if question. So, for example, it still makes sense to consider Turing machines with an oracle for the halting problem, even though we know for a provable fact that no Turing machine can actually solve the halting problem. There's nothing wrong with asking the what-if, as long as we remember that it is a what-if.

To address a couple of other points,

  I don't understand how one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course).

So we're allowed to use some non-existent things but not others?  Why?

  Turing Machines (bizarre fetish formalism if you ask me)

Are you trying to get a rise out of me, Agent Kujan?

  Also, that X historic proofs rely on oracles makes oracle arguments valid is a circular argument.

Yes, that's circular. But it's also a strawman: I've never heard anyone make that argument.

I found nice answers to my concerns/confusions (OP) in these threads:

Why is Relativization a barrier?

  The reason this transfer from oracle-less framework to framework with oracles works is that simple diagonalization is based on black-box simulation of TMs and it doesn't matter how machines works, whether it has an oracle or not.

Why are non-relativizing proofs preferred to relativizing ones?

  This leaves one question which you haven't asked: Why do we care about relativized results? I don't know the historical reason. It might be that these techniques are commonplace in related ares that served as sources of inspiration. At the very beginning, people might have expected that relativized results do imply absolute results.... Since that point, much less attention has been given to oracle results, and they are now quite unfashionable. They have become an object of study in their own right, but with no pretensions to be relevant for separating P from NP.

This paper backs up the previous quote:
Relativization: a Revisionistic Retrospective, Hartmanis, et. all.

http://www.csee.umbc.edu/~chang/papers/revisionist/rev-book.pdf


Can the runtime of functions with no loops change with the number of calls? How can we perform time complexity analysis on a function that has no loops?

int somefunction(int param) {
  if (something)
    do this;
  else
    do this;
}

Would the time complexity of this function change depending on how many times the function is called within a program? I currently believe that the time complexity is O(n), because it is dependent on the amount of times that we call it.

Depends on what something and do this are. In particular, do we have to assume global (or object) state?

Consider this:

int switch(int param) {
  if ( !set.contains(param) )
    set.add(param);
  else
    set.remove(param);
}

Now the runtime clearly depends on the implementation of set and the number of entries it has when switch is called. Calling switch $n$ times starting with an empty set and using pairwise distinct parameters, you might get $\omega(n)$ runtime in total, hence not all calls run in time $O(1)$.

On the other hand, if somefunction does not access state outside of its scope -- assuming that the function itself does not have persistent state -- the runtime can only depend on param. That does not mean runtime is in $O(1)$ -- something and do this may still do non-constant things. Call methods, recurse, etc.

Note that depending on the cost model you use, even adding two numbers has non-constant cost.

It does not become linear just because it is called by linear-worst-case code; it retains whatever complexity it would have in isolation, which here looks an awful lot like constant-time, barring certain odd edge cases. Big-O of a chunk of code is not evaluated based on code that might include it in its own Big-O; you don't consider a hashtable access linear just because there's code that uses the hashtable to process a whole list of items and increment their occurrence counts.


What is meant by "solvable by non deterministic algorithm in polynomial time" In many textbooks NP problems are defined as:

  Set of all decision problems solvable by non deterministic algorithms in polynomial time

I couldn't understand the part "solvable by non deterministic algorithms". Could anyone please explain that?

Adding to Shitikanth's answer,
a nondeterministic algorithm is one that has multiple choices in some points during its control flow. The actual choice made when the program runs is not determined by the input or values in registers, or if we are talking about Turing machines, the choice is not determined by the input value and the state; instead an arbitrary choice among the possibilities can be made in a given run of the program. Thus multiple runs of the same algorithm on the same input can result in different outputs.

The point of using a non-deterministic algorithm is that it can make certain guesses at certain points during its computation. Such algorithms are designed so that if they make the right guesses at all the choice points, then they can solve the problem at hand.

A simple example is primality testing. To decide whether a number $N$ is not prime, one simply selects non-deterministically a number $n\le\sqrt{N}$ and checks whether $N$ is divisible by $n$. For any composite number, this algorithm finds a factor of the number by making the right guess.

The polynomial time part means that if the nondeterministic algorithm makes all the right guesses, then the amount of time it takes is bounded by a polynomial.

A non-deterministic algorithm is one where the input includes a random choice. Meaning, the input is composed of the nominal input plus a purely random selection -- so the answers differ when you run the algorithm with the same nominal input time and again.  If one of the random choices leads to an easy, short (polynomial) solution, the algorithm is NP (non-deterministic polynomial). The unresolved question (is P=NP?) comes down to: is there anyway to make the random choices non-random, but based on some mathematical smarts. Most mathematicians think that the random choice cannot be "improved" to insure a fast solution, namely they believe that NP problems are immunized against future insight that would solve them in short (polynomial) time. They say: P < NP; or at least claim so in order to give credence to a host of cryptographic products. Alas, even if in general P < NP there are numerous special cases where the solution is fast, so the crypto products that rely on them are vulnerable to advanced math (like the Enigma that was defeated by Alan Turing -- we don't know how many Alan Turings work for our adversaries).


Comparing complexities with 2 variables Suppose I have 2 possible algorithms: one runs in O(m+n) and the other runs in O(mn). Suppose also that the task is performed on a connected graph with m edges and n vertices. No other information is given about the graph. How do I know which algorithm is faster?

EDIT:
I don't think my question is a duplicate of the question quicksort refers to since that question asks for a definition and I'm asking for a calculation. I did search for a solution before I posted but couldn't find any sufficient solution to my question.

Since big O is only an upper bound, you cannot really tell which algorithm is faster. Let us therefore assume that the running times of the two algorithms are actually $\Theta(n+m)$ and $\Theta(nm)$. Since your graphs are all connected, you have $n-1 \leq m \leq \binom{n}{2}$, and so the first algorithm runs in time $\Theta(m)$ and the second in time $\Omega(m^{1.5})$. This shows that as $m\to\infty$ (equivalently, as $n\to\infty$), the first algorithm is asymptotically faster.

The function O() represent the number of steps to complete a task for a specific algorithm. O(m+n) will be always faster than O(m*n).

[edit]
sorry O() is not a function is a notation for classifying algorithm give an estimation (upper bound) of the number of steps for complete a task. If I have to choose between two algorithms for a specific task, one classifies O(m+n) and second classify O(mn), without any other information, I'll choose that classify O(m+n) because it's done with fewer steps.


LL(1) CFG for triple amount of b's compared to a's? I would like to construct a LL(1) context-free grammar for a formal language $A$ = "strings where the amount of character b is exactly triple compared to the amount of character a" for $\Sigma = \{a,b\}$.

I've tried to figure it out so that if we consider a string $w$ to have one a, then the acceptable presentations for $w$ considering language $A$ would be abbb, babb, bbab and bbba.

But how do I build the CFG rules for that? I have tried something like $$S \rightarrow A$$ $$A \rightarrow \epsilon | aAbbb |baAbb | bbaAb | bbbaA$$ but I think it's not very good because at least I cannot build an LL(1)-parser out of it (which would be good) because of ambiguity. And it doesn't quite work out for a string like bbbbbbaa $\in A$.

Is it possible to build a CFG for this language that can be parsed using a LL(1) parser?  If not, why not?

I believe that any string able to be represented by a CFG can also be parsed in LL or LR. That is just one of the features of CFG's. The grammar you have originally written can be parsed using LL as the upper-case $A$ will act always as your left-most variable to be expanded and simplified.

I think your problem with constructing the grammar can be solved by also including rules in which the lower-case and upper-case $a$'s are switched, though, that is a rather clunky solution.

$S \rightarrow A$

$A \rightarrow \epsilon | baAbb | bAabb | bbbaA | bbbAa | bbaAb | bbAab | aAbbb| Aabbb$


Satisfiabililty sufficient condition? The conjecture itself:

k-SAT formula is satisfiable if no pair of unit assignment $l$ and $\overline l$ imply the formula to contain unsatisfiable (k-1)-SAT.

Example (XOR-SAT has no edges and cycles in implication graph, so it's simple example):

$$(\overline x\oplus y\oplus z)\land(x\oplus y\oplus v)\land(x\oplus y\oplus w)\land(x\oplus z\oplus v)\land(x\oplus z\oplus w)\land(x\oplus v\oplus w)$$

If in this formula we'll put $x$, we get $(y\oplus z)\land(y\oplus\overline v)\land(z\oplus\overline v)$ which is unsatisfiable.

So, we only can put $\overline x$: this yields us $(y\oplus v)\land(y\oplus w)\land(v\oplus w)$ which is also unsatisfiable.

Now we conclude that formula is unsatisfiable.

My thoughts on it:

The rule surely works if $k = 2$: 2-SAT is unsatisfiable iff there are two unit assignments $l$ and $\overline l$ that make the formula to contain unsatisfiable 1-SAT (two opposing unit clauses).

In fact algorithm would be:

for i = 1..n
    assign x_i
    while unit clauses are presented
        apply unit propagation
    if opposing unit clauses found
        assign -x_i
            while unit clauses are presented
                apply unit propagation
            if opposing unit clauses found
                return UNSAT
return SAT

And it does actually the same as implication graph analisys (primitive, though).

But what about $k > 2$?

For $k=3$  we'd need to change algorithm:

for i = 1..n
    assign x_i
    while unit clauses are presented
        apply unit propagation
    run algorithm for 2SAT
    if 2SAT returned UNSAT
        b_i = 1
    assign -x_i
    while unit clauses are presented
        apply unit propagation
    run algorithm for 2SAT
    if 2SAT returned UNSAT
        b_i += 2
    if b_i == 3
        return UNSAT
    else if b_i == 2
        add clause x_i
    else if b_i == 1
        add clause -x_i
    if b_i > 0
       i = 1
return SAT

Maybe this is not the best implementation, but this is the idea of algorithm. It applies unit assignment and then solves 2SAT for all 2-clauses, in fact it finds all connectivities between opposing literals (finding connectivity between $x$ and $\overline x$ means new unit clause).

taking the contrapositive, another stronger way of stating your question is "a SAT formula f is satisfiable iff either the sub-formulas f1, f2 from the assignment of a variable x or not x are satisfiable". but this is exactly the idea behind the DPLL algorithm (originating as the simpler DP algorithm) provably guaranteed to find a SAT solution. your basic idea also shows the similarity of the method with Gaussian reduction; ie this is not usually remarked but DPLL algorithm appears to be like/ an analog of "boolean Gaussian reduction".


Longest path in an undirected tree with only one traversal There is this standard algorithm for finding longest path in undirected trees using two depth-first searches:

Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$.
Now start a DFS from $v'$ to find the vertex farthest from it. This path is the longest path in the graph.

The question is, can this be done more efficiently? Can we do it with a single DFS or BFS?

(This can be equivalently described as the problem of computing the diameter of an undirected tree.)

We perform a depth-first search in post order and aggregate results on the way,
that is we solve the problem recursively.

For every node $v$ with children $u_1,\dots,u_k$ (in the search tree) there are
two cases:

The longest path in $T_v$ lies in one of the subtrees $T_{u_1},\dots,T_{u_k}$.
The longest path in $T_v$ contains $v$.

In the second case, we have to combine the one or two longest paths from $v$ into
one of the subtrees; these are certainly those to the deepest leaves. The length
of the path is then $H_{(k)} + H_{(k-1)} + 2$ if $k>1$, or $H_{(k)}+1$ if $k=1$,
with $H = \{ h(T_{u_i}) \mid i=1,\dots,k\}$ the multi set of subtree heights¹.

In pseudo code, the algorithm looks like this:

procedure longestPathLength(T : Tree) = helper(T)[2]

/* Recursive helper function that returns (h,p)
 * where h is the height of T and p the length
 * of the longest path of T (its diameter) */
procedure helper(T : Tree) : (int, int) = {
  if ( T.children.isEmpty ) {
    return (0,0)
  }
  else {
    // Calculate heights and longest path lengths of children
    recursive = T.children.map { c => helper(c) }
    heights = recursive.map { p => p[1] }
    paths = recursive.map { p => p[2] }

    // Find the two largest subtree heights
    height1 = heights.max
    if (heights.length == 1) {
      height2 = -1
    } else {
      height2 = (heights.remove(height1)).max
    }

    // Determine length of longest path (see above)
    longest = max(paths.max, height1 + height2 + 2)

    return (height1 + 1, longest)
  }
}

$A_{(k)}$ is the $k$-smallest value in $A$ (order statistic).

Below is code that returns a diameter path using only a single DFS traversal. It requires extra space to keep track of the best diameter seen so far as well as the longest path beginning at a particular node in the tree. This is a dynamic programming approach based on the fact that a longest diameter path either doesn't include root, or is combination of the two longest paths of root's neighbours. Thus we need two vectors to keep track of this information.

 int getDiam(int root, vector<vector<int>>& adj_list, int& height, vector<int>& path, vector<int>& diam) {
    visited[root] = true;
    int m1 = -1;
    int m2 = -1;
    int max_diam = -1;
    vector<int> best1 = vector<int>();
    vector<int> best2 = vector<int>();
    vector<int> diam_path = vector<int>();
    for(auto n : adj_list[root]) {
        if(!visited[n]) {
            visited[n] = true;
            int _height = 0;
            vector<int> path1;
            vector<int> path2;
            int _diam = getDiam(n, adj_list, _height, path1, path2);
            if(_diam > max_diam) {
                max_diam = _diam;
                diam_path = path2;
            }
            if(_height > m1) {
                m2 = m1;
                m1 = _height;
                best2 = best1;
                best1 = path1;
            }
            else if(_height > m2) {
                m2 = _height;
                best2 = path1;
            }
        }
    }

    height = m1 + 1;

    path.insert( path.end(), best1.begin(), best1.end() );
    path.push_back(root);

    if(m1 + m2 + 2 > max_diam) {
        diam = path;
        std::reverse(best2.begin(), best2.end());
        diam.insert( diam.end(), best2.begin(), best2.end() );
    }
    else{
        diam = diam_path;
    }

    return max(m1 + m2 + 2, max_diam);
}


Why is the number of comparisons in a BST missing key lookup about 2 ln N? In (An Introduction to the Analysis of Algorithms) by Philippe Flajolet and Robert Sedgewick it's written that: Insertions and search misses in a BST built from N random keys require ~ 2 ln N (about 1.39 lg N) compares, on the average. I didn't get it well, even after I read their explanation, can you help to understand it by simplifying the idea to me? I mean why do we have 2 ln N compares?

The 2 comes from doing 2 comparisons at each node visited by the algorithm. The lg(n) comes from having to examine one node from each generation, or one node at each height in the tree. So, if we need to examine lg(n) nodes, and preform 2 operations at each node, we preform a total of 2lg(n) operations.

You can say that O(2ln(n)) = O(ln(n))

It is easy to show that the search and misses are O(ln(n)).

Consider a binary search tree (BST). If you are searching from root, you either go left or right based on the knowledge of whether your search key is less than or greater than the value at root. So, when you select to go left (or right), you move one level down ignoring the nodes on the right (or left).

This way you will have to cover at most one node at any level. So, the number of nodes you cover in total is O(h) which is height of the tree.

Now, the height of the tree depends on the number of nodes according to:

O(h) = O(ln(n))

therefore, total number of nodes covered is O(h) = O(ln(n))


Context-free grammars and priority This grammar is supposed to give priority to multiplication:

E -> E + T | T.
T -> T * F | F.
F -> x.

A derivation for "x + x * x" would be (unless I'm wrong):

E => E + T => T + T => F + T => x + T => x + T * F => x + F * F => x + x * F => x + x * x.

So how is multiplication given priority over addition? It appears that the addition is produced first.

You are correct that additions operator is produced first when you
derive. But when you parse, you do the opposite (reduction), and the
multiplications are recognized first, wich is precisely what you want.

THis need a bit of discussion, when you compare top-down and bottom up
parsing, but basically the bottom of the tree must be know correct
before the top can be.

More to the point, this is a consequence of the fact that the parse
tree produced with such a grammar will be structured to conform the
operator operand structure defined by priorities, up to idosyncrasies
of a CF grammar definition, which are ironed out in an abstract syntax
tree (AST). In other words, this gives the parse tree a shape that is close
to the shape desired for the AST (Thanks to Raphael for suggesting
comparison with the AST).

This is why such a grammatical definition is simpler to use to
generate the AST. More importantly, it was much more convenient in
older compilers and interpreters that did not use AST, as the parse
tree reflected the priority structure.

For example, the parse tree for x + x * x is

   E
 / | \
E  +   T
|     /|\
T    T * F
|    |   |
F    F   x
|    |
x    x

And the AST for x + x * x is

   +
 /   \
x     *
     / \
    x   x

It is derivable from the parse tree by moving all operators up one
edge on the preceding node, and then ignoring all non-terminals,
making each linear downward path a single edge. Essentially the same
shape.

This AST is the expression tree defined by the priorities, from which the meaning of the expression can be derived (by homomorphism), from which it can be evaluated or compiled.

I think this is the case of ambiguous grammar.In the rules' list addition is definitely above multiplication and that needs to be rectified,multiplication should go above addition.


Time complexity of min() and max() on a list of constant size? If you use min() or max() on a constant sized list, even in a loop, is the time complexity O(1)?

That depends what exactly you mean by "constant sized". The time to find the minimum of a list with 917,340 elements is $O(1)$ with a very large constant factor. The time to find the minimum of various lists of different constant sizes is $O(n)$ and likely $\Theta(n)$ where $n$ is the size of each list. Finding the minimum of a list of 917,340 elements takes much longer than finding the minimum of a list of 3 elements.

It depends if Array/List is sorted or not. The given answer is incorrect and my one was downvoted. Thanks voting bots!
https://stackoverflow.com/questions/35386546/big-o-of-min-and-max-in-python
FROM WIKIPEDIA:
O(1) is applicable

An algorithm is said to be constant time O(1)... In a similar manner, finding the minimal value in an array sorted in ascending order

O(n) is applicable

O(n).. finding the minimal value in an unordered array is not a constant time operation as scanning over each element in the array is needed in order to determine the minimal value

You need to check all of the the values to find the minimal one if the list is not sorted. My first idea is that Python does not have a hidden support for caching function return values. I'm not certain if min(value) is considered deterministic in python if you supply a reference instead of an actual list.
Below is an easy way to memoize a function and its return values in Python. If you apply this the complexity of your function can be reduced to O(1)+n
def memoize(func):
cache = dict()

def memoized_func(*args):
    if args in cache:
        return cache[args]
    result = func(*args)
    cache[args] = result
    return result

return memoized_func