Binary-ish search through partially ordered set I have an interesting function.  It takes subsets of {1,...,N} to positive integers, i.e. $f:P([N]) \rightarrow Z^+$.
I know that if S is a subset of S', $f(S) < f(S')$.  Also, if S and S' have the same cardinality, the ordering induced by f is lexicographic, so for example $f(\{1,2,4\}) < f(\{1,3,4\})$.
Given a value z, I'd like to find S such that $f(S) <= z$ and $f(S) <= f(T) <= z$ implies $f(S)=f(T)$ -- that is, I want to do a search on the lattice of subsets of [N].
If I knew the ordering were perfectly lexicographic, I'd use a simple binary search.  I don't know that, and I believe it is not (e.g., $f(\{1,2,3,4,5,6\})$ is possibly greater than $f(\{7\})$). Is there a good O(N) algorithm to do this search on the poset?  Obviously for N of any appreciable size I have to compute f on-the-fly and can't rely on in-memory storage.
Clarification after a discussion in the comments:
The particular $f$ I am dealing with is additive -- specifically, $f(S) = \sum_{k\in S} g(k) + f(\emptyset)$, with $g$ a monotonically increasing function. This may be easier than the general case (which is also interesting, but not my particular problem).

Here is a simple algorithm that runs in $O(N^2)$ time and $O(N)$ space, assuming that $f(\emptyset)$, $f(\{1\})$, $f(\{2\})$, $\cdots$, $f(\{N\})$ are given in an array.
The starting idea is about the same as what has been given by the OP in his comment. "We will search on subsets of size K using the lexicographic order, for each $K$ from $0$ to $N$. Retain the one with the best value of $f$."
The problem is then how to search the best value of $f$ on subsets of size $K$, named $b_K$, in $O(N)$ time. Instead of binary search, we will check whether $N$, $N-1$, \cdots, $1$ should be included in the best subset one by one, by taking the real advantage of the lexicographic order on subsets.

Initialize $b_K = f(\emptyset)$. $\ b_K$ will be the best value on subsets of size $K$ at the end of this procedure.
Initialize $count = 0.$ $\ count$ is the number of elements that we have included in the best subset so far.
Check $f(\{N\})$. If $b_K + f(\{N\}) + f(\{1, 2, \cdots, K-count -1\})\le z$, $N$ must be included. Add $f(\{N\})$ to $b_K$ and add 1 to $count$.
Check $f(\{N-1\})$. If $b_K + f(\{N-1\}) + f(\{1, 2, \cdots, K-count-1\})\le z$, $N-1$ must be include. Add $f(\{N-1\})$ to $b_K$ and add 1 to  $count$.
And so on.
Until either we have checked $f(\{1\})$ or $count == K$.

We might wonder, if it will take $O(N)$ to compute each $f(\{1,2, \cdots, K-count-1\})$, computing each $b_K$ alone will take $O(N * N)$ time. However, since $f$ is additive, we can compute all prefix sums of $f(\{1\})$, $f(\{2\})$, $\cdots$, $f(\{N\})$ upfront in $O(N)$ time. Then it takes $O(1)$ to access each prefix sum.
Since searching $b_K$ takes $O(N)$ time, for each $K$ from $0$ to $N$, the total running time is $O(N^2)$.

The description above of the algorithm skips the easiest case when $f(\emptyset)\gt z$. In that case, the algorithm should return that there is no such subset.


Dealing with intractability: NP-complete problems Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?

There are a number of well-studied strategies; which is best in your application depends on circumstance.

Improve worst case runtime
Using problem-specific insight, you can often improve the naive algorithm. For instance, there are $O(c^n)$ algorithms for Vertex Cover with $c < 1.3$ [1]; this is a huge improvement over the naive $\Omega(2^n)$ and might make instance sizes relevant for you tractable.
Improve expected runtime
Using heuristics, you can often devise algorithms that are fast on many instances. If those include most that you meet in practice, you are golden. Examples are SAT for which quite involved solvers exist, and the Simplex algorithm (which solves a polynomial problem, but still). One basic technique that is often helpful is branch and bound.
Restrict the problem
If you can make more assumptions on your inputs, the problem may become easy.

Structural properties
Your inputs may have properties that simplify solving the problem, e.g. planarity, bipartiteness or missing a minor for graphs. See here for some examples of graph classes for which CLIQUE is easy.
Bounding functions of the input
Another thing to look at is parameterised complexity; some problems are solvable in time $O(2^kn^m)$ for $k$ some instance parameter (maximum node degree, maximum edge weight, ...) and $m$ constant. If you can bound $k$ by a polylogarithmic function in $n$ in your setting, you get polynomial algorithms. Saeed Amiri gives details in his answer.
Bounding input quantities
Furthermore, some problems admit algorithms that run in pseudo-polynomial time, that is their runtime is bounded by a polynomial function in a number that is part of the input; the naive primality check is an example. This means that if the quantities encoded in your instances have reasonable size, you might have simple algorithms that behave well for you.

Weaken the result
This means that you tolerate errorneous or incomplete results. There are two main flavors:

Probabilistic algorithms
You only get the correct result with some probability. There are some variants, most notable Monte-Carlo and Las-Vegas algorithms. A famous example is the Miller-Rabin primality test.
Approximation algorithms
You no longer look for optimal solutions but almost optimal ones. Some algorithms admit relative ("no worse than double the optimum"), others absolute ("no worse than $5$ plus the optimum") bounds on the error. For many problems it is open how well they can be approximated. There are some that can be approximated arbitrarily well in polynomial time, while others are known to not allow that; check the theory of polynomial-time approximation schemes.

Refer to Algorithmics for Hard Problems by Hromkovič for a thorough treatment.

Simplicity is beauty: Improved upper bounds for vertex cover by Chen Jianer, Iyad A. Kanj, Ge Xia (2005)


The notion of PAC in approximation algorithms In computational machine learning, the notion of Probably Approximately Correct means that (generally speaking) we can find (or "learn") with a high probability a function which has "low error".
Is there a way to generalize this idea for approximation algorithms? What I thought of:
Given a language $L \subseteq \{0,1\}^*$, a confidence parameter $\delta\in[0,1]$, an error parameter $\epsilon > 0$, and a distribution $D$ over $L$, the algorithm $A$ is a PAC algorithm for $L$ if with probability at least 1 - $\delta$ it holds that $\text{ERR}(A,D)\leq \epsilon$, where $\text{ERR}(A,D) := \Pr_{x\text{~}D}(A \text{ answers wrong on } x)$.
One drawback of this definition is the following: suppose $L$ is a countable infinite set, and let $l_1, l_2,...,l_k,...$ be some enumeration of the elements of $L$. Since $D$ is a probability distribution over $L$, $\sum_{i}D(l_i) = 1$, and hence there must be some index $k$ such that $\sum_{j>k} D(l_j) <\epsilon$.
The algorithm $A$ can be defined as: remember the answers of the first $k$ words. When receiving $w \in \{0,1\}^*$ check if $w$ is saved (and if so answer correctly). Otherwise, answer "0".
Clearly this algorithm is a PAC by the above definition, but not a clever one.
Is there a way to define PAC algorithm for a formal language? Or: can we use the theory of machine learning in the theory of approximation algorithms?

Approximation algorithms don't make sense here, because here the output of the algorithm is 0 or 1.  (0 represents "the input is not in $L$", 1 represents "the input is in $L$".)  Approximation algorithms are useful when the output is a continuous variable, as then we can ask for the algorithm to output something that is close to the correct answer, but the concept is not useful when talking about algorithms that output a boolean.

Also, in your proposed definition, once you have fixed an algorithm $A$ and a distribution $D$ over $L$, the condition $ERR(A,D) \le \epsilon$ is either true or false.  It's not an event that you can assign a probability to.  So, it doesn't make sense to ask it to hold with probability at least $1-\delta$.


DFA and equivalence classes: counting odd numbers of b's I am studying for an exam and found an exercise about finding the equivalence classes for $L=a^*ba^*(ba^*ba^*)^*$, the language over $\{a,b\}^*$ with an odd number of b's.

We found three equivalence classes: $[a^*], [a^*ba^*(ba^*ba^*)^*], [a^*ba^*ba^*(ba^*ba^*)^*]$. This means the minimal DFA would have three states, and it was given so:

But it seemed to me that the following DFA with two states would achieve the same result (by merging q0 and q2).

This is a contradiction with having three equivalence classes.

What went wrong here, and where?

Your first and third equivalence classes are equivalent to one another. They both contain strings in which there are an even number of $b$s: in the first class, that number is zero; in the third class, it's at least two.  For any string in either of those classes, adding a string with an odd number of $b$s gives a string in the language, and adding a string with an even number gives a string not in it.


finding shortest negative cycle Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the shortest (uses the least number of edges) negative weight cycle in the graph?

I know that I can detect negative weight cycles using Bellman-Ford. Has this variation be studied before? Can you point me to a reference?

You can use dynamic programming (in this case, known as the Floyd–Warshall algorithm) to calculate the least weight of a walk of length $\ell$ from $x$ to $y$, for all vertices $x,y$ and $\ell \geq 0$. The first $\ell$ (if any) such that this weight is negative is the length of the shortest negative cycle. (This breaks if there are bidirectional negative edges, unless you consider them as simple cycles.)


Equivalence between two definitions of Tree width Treewidth :

1) By chordal graphs : size of the largest clique $(\omega (G))$ - 1 in a chordal completion of the graph $G$.

2)  By tree decomposition :

A tree decomposition of $G = (V , E)$ consists of a tree $T$ (on a different node set from $G$), and a subset $V_t ⊆ V$ associated with each node $t$ of $T$. (We will call these subsets $V_t$ the “pieces” of the tree decomposition.) We will sometimes write this as the ordered pair $(T , {V_t : t ∈ T })$. The tree T and the collection of pieces $\{V_t : t ∈ T \}$ must satisfy the following three properties

(Node Coverage) Every node of $G$ belongs to at least one piece $V_t$.

(Edge Coverage) For every edge $e$ of $G$, there is some piece $V_t$ containing both ends of $e$.

(Coherence) Let $t_1, t_2,$ and $t_3$ be three nodes of $T$ such that $t_2$ lies on the path from $t_1$ to $t_3$. Then, if a node $v$ of $G$ belongs to both $V_{t_{1}}$ and $V_{t_{3}}$, it also belongs to $V_{t_2}$

So we define the width of a tree decomposition $(T , {V_t })$ to be one less than the maximum size of any piece $V_t$ (over all $t$):
$$width (T , {V_t}) = max |V_t| − 1$$

Claim 1: If size of largest clique in a chordal decomposition of graph is  say $k$ then by tree decomposition we will get tree width $k$

Proof : let us assume that largest clique size in chordal completion graph is $k$, so there exist a bag (subset of vertices of graph) that contain the clique ( due to edge coverage ). so we are done.

claim 2 : If tree width is $k$ by tree decomposition method then by chordal completion method also is $k$

  Question : How to prove the claim 2 ?High level proof will be welcomed.

First, let me note that the claim, as stated in the question, is false:
Consider the following graph:

  $\begin{matrix}  & & 2& - & 3\\
& \diagup\\
1 & & | & & |\\
& \diagdown \\
 & &4 &-& 5
\end{matrix}
$

The complete graph on $5$ vertices is a chordal completion of this graph. However, this graph has treewidth $2$. (A decomposition is $\{1,2,4\}$, $\{2,3,4\}$, $\{3,4,5\}$ )

The correct claim is

  The treewidth of $G$ of is the size of the largest clique $\omega(G) - 1$ in a chordal completion with the minimum largest clique of the graph $G$.

Now, a proof is as follows: if the treewidth of $G$ by tree decomposition is $k$, then every tree decomposition has a bag of size at least $k$. We use the concept of a separator graph from a paper by Parra and Scheffler, in particular the fact that every maximal clique in the separator graph of $G$ is a tree decomposition of $G$ (This can be seen by comparing the definition of tree decompositions with those in the paper)

Then, by Theorem 4.7$^*$ from the same paper, every minimal chordal completion of $G$ has all the bags of some tree decomposition as a clique. This means every minimal chordal completion of $G$ has a clique of size $k$, so the chordal completion method also gives a tree-width of $k$. $\square$

*: Paraphrased in our notation, Theorem 4.7 states:

  A graph $H$ is a minimal chordal completion of $G$ if and only if $H$ is the graph $G$ with exactly the edges added such that all vertex sets in $\mathcal{S}$ are cliques. Here $\mathcal{S}$ is a maximal clique in the separator graph, which consists of minimal separators of $G$.

I attempted to find a proof using only elementary techniques, but I don't think an easy proof without any deeper theory would be easy to find.


Why are syntax trees used in genetic programming? Reading a course on genetic programming, the first chapter describes the syntax tree as the basic representation of programs in genetic programming.

What are the reasons leading to the choice of a syntax tree in genetic programming? Are there any particular assets in using this representation?

In short: AST representations of programs are more easily analyzed,
manipulated, and transformed, while preserving and enforcing the existence of a
formally defined program meaning through the transformations.

I am asssuming that the reader knows already what is an abstract syntax tree (AST), and does not need to be shown examples.

The question is an issue about abstract objects (semantics) and their
representations (syntax). We are usually interested in the semantics,
applying transformations to entities to change or combine their
meanings, their semantics, which can belong to all kinds of domains.
But semantics is elusive, mathematical abstraction, and all we can
actually manipulate to express our intent is syntax representations.

That is the basis of all programming, but is also to be found in
logic, proofs, and finally all of mathematics. That is what makes the
choice of representations and notations often so important. Good choice
of representation will lead to easier, possibly more perspicuous or
intuitive understanding of the problem and be better adapted at
expressing answers, and proofs, for given questions.

The point is well known to programmers, as they are taught that it is essential to
choose the right data structure in order to implement an algorithmic
solution to a given problem. The choice of data structure is the choice of
representation.  And I just made a similar answer to a question on
constructing (programming?) Turing Machines.

Note that there is a partially ambiguous use of the word syntax, which
can be any concrete representation of an abstraction, or can be
intended to mean only textual representation as strings (we are
getting close to Turing machines), possibly structured by some logical
system (a context-free (CF) grammar for example that specifies what
are the legitimate strings, the well-formed-strings.

In fact, the existing parsing-unparsing technology, especially for CF
grammars, makes it generally easy to switch between textual and an
associated tree representation, to the point that they are often not
distinguished much. Actually, mathematicians have been using tree
representation (formally defined as Algebras), long before that
technology existed, and this is what lead to using the representation of AST
in manipulating programs.

So what was so convenient about these tree (or AST) representations?

The key points are:

it is very convenient for associating precisely
semantic meaning to syntactic constructs, in a compositional way, by means of a simple
mathematical concept: the homomorphism;
it provides and enforces a syntactic type system (statement, expression, ...) that preserve the existence of some meaning when the program representation is transformed in a way that preserves the syntactic typing constraints;
it is easily manipulated to actually perform analysis and transformations;
it is easy to decorate it with localized information to help or guide these analyses and transformations.

First, if you take a string representation of a program, without
further structural information, there is no simple way to delimit
substrings that have naturally a meaning of their own (I am saying
naturally, because some people may always try to play at abstracting
syntactic context or indulge in syntactic (text oriented) continuation games - ignore this if
you do not get it).

The idea of a tree structure, with nodes labeled with operators, possibly
restricted by syntactic types (statement, expression, variable, ...)
is that they naturally decompose the syntactic structure into subparts
(the subtrees) that can have fairly naturally, and perspicuously with
respect to computational concepts, a semantic meaning of their own.

Then, if we associate a semantic function to each operator, we can get
the meaning of a tree representation by applying the semantic function
of the root operators to the semantic meaning of each of its subtrees.
If we also provide some semantics to leafs operators (which may be
defined as a mapping from syntactic representations to some semantic
domains possibly by other means, for example associating the integer
23 to the string "23"), we know how to define simply the semantics
of any well-formed tree, whether complete program or well-formed
program fragment. This is the basis of what is known as denotational semantics.

In other word, the homomorphism thus defined gives a rather simple and
tractable way to associate meaning to well-formed program fragments, by composing the meanings of its well-formed sub-fragments (this is known as semantic compositionality).
Then, it becomes much easier to attempt defining semantically
meaningful transformations. And semantics, what the program (fragment)
does is what we really care about.

Furthemore, AST are fairly easy to manipulate by programs to express these transformations that somewhat respect the semantic structure (as they manipulate subtrees that are semantically meaningful), which initially justified their use in program editors, program manipulation systems, and programming environment.

Actually, the concept of AST in programming appeared with the language
Lisp (and its ability to manipulate Lisp programs syntactically) in
the very late fifties. But it developed mostly in the seventies (Emily, Cornell synthesizer, Mentor/Centaur), and further in the eighties, at the
same time as denotational semantics (which is based on the above
approach), and most likely under the influence of denotational
semantics. The early work (LCF) on automated proofs about computation may also have been influencial.

From the point of view of genetic programming, the use of AST both facilitates and enforces the
creation of syntactic structures that are more likely to have some
meaning. Manipulating unstructured string representations  would be
likely to result in being swamped with string representations to which
no meaning can be associated.

Another advantage of AST representations is that they are fairly easy
to decorate with additional information: precomputed semantic
properties, weights, or whatever is deemed useful for the intended
program transformation or manipulation, including genetically programed transformations.

A detailed example

This section has been added later to answer some comments.

I will try to work out one example in some details to explain the
relation between manipulations on the AST and their semantics
conterpart.

We take a very simple example of crossover between two ASTs:
T1=foo(exp1,exp2) and T2=bar(exp3, exp4). I keep it small for
readability. Actually, exp1 to exp4 are meant to be subtrees of
some AST, while you may also see what is around them as standing for
the rest of some AST (or some AST subtree) that is the context in
which they occur.

We suppose first that the language does not have typing (in the usual
sense of programing languages), and accept any value in any context
expecting a value, so that any expression can legitimately replace any
other.

Then given T1 and T2, it is legitimate to apply a crossover that swaps
exp1 and exp4, thus producing T1'=foo(exp4,exp2) and
T2'=bar(exp3, exp1). Note that the algorithm could also consider
only one of these two trees (I am incompetent regarding genetic
splicing strategies).

Now, let us see what can be said about semantics, without getting too
much into details.

Let $S$ be the semantic function, $V$ the domain of values, $M$ the
domain of environments that map identifiers to values. The semantics
$S$(exp) of an expression exp is a function $e: M\to V$ that takes
an environment $m$ as argument (so that we have values for
identifiers) and returns the value of the expression in that
environment.

Now, if the operators foo and bar are supposed to compute
respectively two functions $f$ and $b$ on their arguments,
the semantics of T1, for example, will be defined as

$S$(foo(exp1,exp2))=$S$(foo)($S$(exp1),$S$(exp2))=$\lambda m.f(e_1(m),e_2(m))$

You notice that the semantic function is not necessarily easy to define in the
complex case of a programming language, since for foo we have here
$S$(foo)=$\lambda e, e', m\,.\, f(e(m), e'(m))$.

This complexity results from the choice of the Abstract Syntax, that
considers here foo and bar as AST operator nodes. Instead, the AST
could have a call operator that has several daughters, for example
as in call(foo, exp1, exp2). Then the complexity of dealing with the
environment $m$ would be factorized in the semantics of call, while
the semantics of foo would simply be the function $f$.

Sorry for this complexity.

The whole point is that we can define the semantics of an AST subtree
such as exp1 independently of any context, but as a
function $e_1$. Whatever information it needs from the context to be
evaluated is summarized in the arguments (here the environment $m$)
that are passed to its semantics. And this information is in turn
passed to the semantic functions associated to subexpressions.

So now we know that a subtree of AST can have a well defined
semantics, independently of its context.

But what about the context? Does it have a well defined semantics when
a subtree is missing. The nice point is that it does.

If you consider the context foo(??,exp2), what can its semantics be.
The natural answer is that it is whatever semantics it would have if
you provided the missing part. In other words, it is a functional
semantics that takes as argument the semantics of the missing part.
This is very similar to the semantics of the complete expression
$S$(foo(exp1,exp2)) that we defined above, except that the missing
exp1 must be accounted for with an argument $e$ standing for the
semantics of whatever expression could replace exp1.

We had $S$(foo(exp1,exp2))=$\lambda m.f(e_1(m),e_2(m))$

So, without going into further details, you have

$S$(foo(??,exp2))=$\lambda e.\lambda m.f(e(m),e_2(m))$

Then, given that $S$(exp1)=$e_1: M\to V$,
we have
$S$(foo(exp1,exp2))= $S$(foo(??,exp2))($S$(exp1))

which is precisely what we would like: syntactic abstraction directly
translate into semantic abstraction.

Then we also have, of course:

$S$(foo(exp4,exp2))= $S$(foo(??,exp2))($S$(exp4))

In other words, both AST subtrees and AST contexts (of subtree) have
well defined semantics, that do not change, and they compose to give
the semantics of the whole AST tree when a subtree is placed in a
permitted context.

But of course: $S$(foo(exp1,exp2)) $\neq$ $S$(foo(exp4,exp2))

I hope this explains how things work. Using well-formed AST will
ensure that you are actually manipulating semantic fragments that
compose meaningfully.

Actually, things may be a bit more complicated, because you want to
include in the process what is usually called static semantics,
i.e. constraints on the AST that are usually checked at compile time.
The best known examples are type constraints for statically typed
languages, or declaration of identifiers when that is required.  Thus
you may want to decorate ASTs with this statically computable
information, and use splicing techniques that will incrementally
preserve the information and check the required constraints on the AST, so that you produce only programs that at least compile.

Then as a last comment, I would like to remarks that linear genetic
programming seems to be doing pretty much the same, but restricts
splicing to sequences of statements, so that there is always some
executable semantics preserved. But I am not specialist of that.


Why does Feistel encryption algorithm encode half block every time? Why does Feistel encryption algorithm  encode half block every time? What would happen if the entire block is encrypted in each step?

You can't.  Some of the block is used as the input to the F function, and the rest is modified. Those can't overlap.  If you wanted to modify all of the block, there wouldn't be any input to the F function.

You might be interested in https://en.wikipedia.org/wiki/Feistel_cipher#Unbalanced_Feistel_cipher


Binomial heap multiplying nodes Input: A max binomial heap $H$, and a pointer to a node $V$.
Output: A max binomial heap, where all the children of $V$ are multiplied by 2.

I have tried solving this by taking out the node $V$ together with it's sub-tree, multiplying all the children of V by $2$, rearranging the heap to close the hole, and adding V's children to the heap.

It sums up to $O(k\log n )$, where $k$ is the number on nodes in the tree containing $V.$
Can I do better than this? I'm sure I can but I don't know how.

I think in this scenario you can just bubble-up one of the updated element to restore the max-heap property.

Notice that by the multiplication you have increased the keys in $V$ children. So the trees rooted at the children still have the max-heap property, but maybe $V$ does not anymore. You can repair this, by swapping the largest key of the children with the key of $V$. This restores the max-heap property for the subtree rooted at $V$. You continue by comparing the key of $V$ with the key of the father of $V$ and swap the key is necessary. You do this, until nothing was swapped, or you reach the root - its the typical heapify routine.

Since binomial heaps have depth at most $\log n$ and the degree is also bounded by $\log n$ the whole procedure needs $O(\log n)$.


How to build a graph of people where node connections are determined by name and age? I was given the following question (please don't mind the programming language semantics, it's a language-agnostic question):
Given a list of Persons, and two arbitrary Persons out of that list, we need to find the minimum nth-degree relationship between them.
Here are the definitions of Person and a "relationship":

A Person is defined as having 2 properties: Name and Age:
class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
}

A relationship between two Persons is defined as follows:

Two Persons are considered to be in a 1st-degree relationship if they have either the same name or the same age.
Two Persons are considered to be in a nth-degree relationship if they have n people of 1st-degree connecting them.

Example input:
Given the following list of Persons:
persons = [{ Name = "John", Age = 60 }, { Name = "John", Age = 50 }, { Name = "Ted", Age = 50 }]

Then:

The two Johns have a 1st degree relationship (because they have the same name).
The second John and Ted have a 1st degree relationship (because they have the same age).
Hence, the first John and Ted have a 2nd degree relationship (because the second John connects them).

Now, I understand that it's a simple Dijkstra's algorithm question, but what I don't know is how should we build the graph of Persons?
I'm looking for an algorithm, but preferably code, that can build the graph in a time complexity which is better than $O(|V|^2)$.
If you think this question can be solved without building a graph (e.g., using BFS as mentioned in the comments), please let me know how can this be done, but I still want to know how to build the graph.

I assume you want to build the graph of all people, with edges between each pair of people at degree 1.  Once you have this graph, it is straightforward to calculate the distance ("degree") between any two people using standard algorithms.
It's easy to build that graph in adjacency list format; or to store it implicitly and generate the adjacency lists on demand.
Store a hash table that maps from name to a list of all people with that name; and another hash table that maps from age to a list of all people with that age.  Now, given one person, you can use the hash tables to quickly find all other people who have a first-degree relationship with that person, i.e., who are adjacent in the graph.  This lets you build an adjacency list representation of the graph in $O(|V|+|E|)$ time, i.e., linear time rather than quadratic time.
Then, once you have this graph, you can compute distances using BFS in this graph.  Note that you can construct the graph on-the-fly as you execute the BFS algorithm; you don't need to build the entire graph in advance.

Footnote: I'm treating hash table lookups as $O(1)$ time.  This is a reasonable modelling assumption for practical work.  For theoretical work, you can ensure that lookups take $O(1)$ expected time if you use an appropriate hash function, which is nearly as good for most practical purposes.


How to compute a curious inverse Let $M$ be a square matrix with entries that are $0$ or $1$ and let $v$ be a vector with values that are also $0$ or $1$.  If we are given $M$ and $y = Mv$, we can computer $v$ if $M$ is non-singular.

Now let us take the second bit (from the right) of the binary representation of each $y_i$ as another vector $z$. So $z$ also has entries which are $0$ or $1$. If $y_i$ has fewer than two bits we just let $z_i=0$.

  If we are given $z$ and $M$, how (and when) can you find a $v$ so that
  $Mv$ would produce $z$ under this operation?

Here is an example

$$M = \begin{pmatrix}
  0 & 0 & 1 & 0\\
  1 & 1 & 0 & 1\\
  1 & 1 & 1 & 0\\
  0 & 1 & 1 & 1\\
\end{pmatrix}
, v = \begin{pmatrix}
  0 \\
  1 \\
  1 \\
   1\\
\end{pmatrix}
\implies Mv=\begin{pmatrix}
  1 \\
  2 \\
  2 \\
  3\\
\end{pmatrix}
.$$

So in this case

$$z =
\begin{pmatrix}
0 \\
1 \\
1 \\
1 \\
\end{pmatrix}.
$$

Is this problem in fact NP-hard?

This problem can be cast into a familiar form: it's an example of what is known as a 0-1 linear programming problem. You have a set of variables $v_1, v_2, \dots v_n$ subject to constraints of the form $m\le a_1v_1+a_2v_2+\cdots +a_nv_n\le M$. In your particular problem, we also have $a_i \in \{0, 1\}$. You are looking for any feasible solutions, namely tuples $(v_1, \dots, v_n)$ which satisfy all the constraints.

For example, suppose we have
$$
M = \left( \begin{array}{cccc}
         0 & 0 & 1 & 0\\
         1 & 1 & 0 & 1\\
         1 & 1 & 1 & 0\\
         0 & 1 & 1 & 1
       \end{array} \right), \quad{\text{and}}\quad
z= \left( \begin{array}{c}
     0\\1\\0\\1
   \end{array}\right)
$$
then you want
$$
v= \left( \begin{array}{c}
     a\\b\\c\\d
   \end{array}\right)
$$
such that $Mv$ will be, in binary (with the lower-order bit unspecified)
$$
Mv=\left(\begin{array}{c}
c \\ a+b+d \\ a + b + c \\ b + c + d
\end{array}\right)
=\left(\begin{array}{c}
\mathtt{0\_}\\ \mathtt{1\_}\\ \mathtt{0\_}\\ \mathtt{1\_}
\end{array}\right)
$$
From this we have the constraints
$$
\begin{array}{c}
0\le a, b, c, d\le 1\\
2\le a + b + d\le 3\\
0\le a + b + c\le 1\\
2\le b + c + d\le 3
\end{array}
$$
and you want to find $a, b, c, d$ such that all the constraints are simultaneously satisfied.
We've moved into 0-1 LP land because there are established procedures for solving problems like this, though sadly there's nowhere near enough room in this post to introduce them, so you'll have to do the legwork yourself. Be aware that problems like this are very compute-intensive (by which I mean NP-hard) and as far as I know you're not going to get anything like an elegant formulation of the form "This can be solved if and only if $z$ is of the form ..."

By the way, the example I used does indeed have a solution, $v$, and in this particular case is unique, though in general you'll have several solutions (if there are any at all).


Online shortest path in ordered DAG Suppose I have an edge-weighted connected rooted DAG $G = (V, E, r \in V, w \in E \to \mathbb{Z})$ where there exists a sequence of nonempty sets (called "levels") $L_0 = \{r\}, L_1 \subset V, \ldots, L_n \subset V$ such that $L_0 \cup \ldots \cup L_n = V$ and the outgoing edges of the nodes in $L_i$ only connect to nodes in $L_{i + 1}$.
Is there an online algorithm that can maintain a set of shortest paths as more levels are added to this DAG? In other words, it can answer the query "what is the minimum weight path from the root to some node $n$ in the bottom level of the graph?", even as more levels are added.
I couldn't find any research addressing this question.

If I understand your problem correctly then you probably didn't find any research because the problem is easy to solve.
Unless I missed something, you want to maintain an edge-weighted "layered" DAG $G=(L_0, \cup \dots \cup L_k, E)$ (as defined in your question) and support the following two operations:

Init(): Create a graph with only one layer $L_0$, a single vertex $r \in L_0$, and no edges.

Query(): return $\min_{v \in L_k } d(r,v)$.

Add_Layer($L_{k+1}, E'$): you are given a new set $L_{k+1}$ of vertices and a set of weighted edges $E' \subseteq(L_k \times L_{k+1})$. The vertex set of $G$ is updated to $L_0 \cup \ldots \cup L_k \cup L_{k+1}$ and the edge set of $G$ is updated to $E \cup E'$.

You can do the above by storing: 1) for each vertex $v \in L_k$, the distance $D[v]$ form $s$ to $v$ in $G$, and 2) the minimum distance $d^*$ from $s$ to a vertex of the last level.
The init operation amounts to setting $D[r]=0$. To perform the query operation just return $d^*$.
To implement Add_Layer($L_{k+1}, E'$), you proceed as follows:

Set $d^*$ to $+\infty$,
For each vertex $v \in L_{k+1}$:

Set $D[v] = +\infty$
For each edge $(u,v)$ in $E'$:

Update $D[v]$ to $\min\{D[v], D[u] + w(u,v) \}$

Update $d^*$ to $\min\{d^*, D[v]\}$

Notice that this requires time proportional to $|L_{k+1}| + |E'|$, and is therefore asymptotically optimal. Notice also that this solution does not need to store $G$.


Applying SVD compression to integral point images Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular values to construct the the best rank-$k$ approximation of $A$ to accomplish compression for data storage.

I understand that for a floating-point image, the compression rate for SVD is

$$\frac{mn}{k(m+n+1)},\tag{1}$$

as mentioned in a lot of places including some textbooks. For example, a quick internet search gives us this article and this convenient demo link.

Coming back to our case, the entries of $A$ are 8-bit unsigned integers, while we still need to use floating points (32 bits or 64 bits) for the storage of the singular values and vectors (because 8-bits do not seem enough for the precision), it would seem that the compression rate for this case should become

$$\frac{mn}{4k(m+n+1)}, \quad\text {or} \quad \frac{mn}{8k(m+n+1)}.\tag{2}$$

This would render this compression scheme not practical in most cases. For example, using the demo link above, for that default image there, we need at least the first 100 singular values for a less-than-satisfactory compressed image. Using Formula $(1)$, that is assuming the original image is using the floating point data type, the compression rate is $2.40$; but assuming the original image is using the 8-bit unsigned integer data type, using Formula $(2)$, the compressed image becomes at least $0.6$ times bigger than the original one.

Does SVD compression only work for floating point images? What am I missing here?

Does SVD compression only work for floating point images?

It seems quite obvious that it works for arbitrary images.  Whether you are satisfied with the amount of compression or not doesn't really change the fact that it works.

I think looking at the compression ratio is going to lead to misleading results.  Suppose you take two images: $I_1$ uses 8-bit RGB, and $I_2$ is the same image but captured using 24-bit RGB.  Note that it is often fairly challenging to distinguish between two such images, and the differences are often perceptually minor.  Now suppose you compress both with lossy compression.  Suppose that both compressed images happen the same size.  Then the compression ratio of $I_1$ is 3x worse than the compression ratio of $I_2$.  Does that mean that compression doesn't work for 8-bit RGB images?  No, it means that $I_2$ has a bunch of extra information that isn't semantically relevant.  Thus, a compression algorithm that throws away this irrelevant information will achieve a higher compression ratio.  That's not because the compression algorithm is better; it's just a reflection of the fact that $I_2$ has more irrelevant information (or information with low relevance).

And this is exactly the situation you're in.  There is no way that the low 8 bits of those 32-bit floating point numbers are perceptually meaningful; no human is going to be able to perceive those.  So, if you're capturing an image with 32-bit floats, then some of the bits of those floats are pure noise that are perceptually completely irrelevant.  So, of course a compression algorithm that throws away that irrelevant information is going to achieve a higher compression ratio.  Does that mean that compression on 8-bit images doesn't work?  No, it just means there was less irrelevant information to throw away.  This phenomenom is not specific to SVD-based compression; it will likely be true for any form of good lossy compression.

I can always make the compression ratio arbitrarily good by appending a bunch of irrelevant useless information to the input, and then modifying my compression algorithm to throw away the irrelevant information.  That doesn't mean I have a better compression algorithm, or that the compression algorithm doesn't work or is unacceptable on the original images.

For all of these reasons, I think a better way to compare the two schemes is by the size of the compressed image, not by the compression ratio.  And both variants you describe achieve the same size compressed image, so the apparent difference evaporates.

Second, when you're doing your comparison, there is no reason why you need to hold $k$ fixed.  Usually we think of lossy compression as a tradeoff between the size of the compressed image vs the perceptual quality.  You have two tunable parameters: $k$, and the number of bits of precision that use for the entries of the outputs of the compression.  You are free to choose those arbitrarily to maximize the perceptual quality of the image, for a given image.  For instance, instead of using one value of $k$ and 32-bit floats, you might do better to double $k$ and use 16-bit floats.  Probably only empirical experiments can help you set those parameters in the optimal way... but you shouldn't assume what the optimal setting will be, or that it will necessarily be the same for both settings (both 8-bit inputs vs 32-bit inputs).


Choosing a production with $\lambda$ in Context-Free Grammars Given the context-free grammar

\begin{align*}
& S \rightarrow AA \\
& A \rightarrow xA \\
& A \rightarrow B \\
& B \rightarrow yB \\
& B \rightarrow \lambda
\end{align*}
What is the meaning of $\lambda$? $\lambda$ itself means the empty string and will match anything without consuming it, but in terms of the productions, how do you know which one to use? Do you use the last $B$ production only if $B \mapsto yB$ cannot be used? Or can both be used interchangably?

For example, parsing the string $xyy$ could give two different results:

Is there a formal way to prefer one of the two possible options? Which one is the "default"?

I think you have understood this backwards. The CFG defines the language. All strings that can be derived by using the rules defined in the CFG are present in the language. The empty string itself is a terminal variable. You would substitute it in the string that you're deriving and is just empty.

What you are arriving at with the parse trees is called ambiguity of the grammar that you have defined. When the same string can be derived in more than one leftmost derivation, then the grammar is ambiguous. You could use two different substitutions and still arrive at the same string. So, yes, you could use either derivation, but the string itself does not change.

I would say the formal way to derive your string in exactly one particular way is to use a grammar without ambiguity.


What is the difference between $\log^2(n)$, $\log(n)^2$, $(\log n)^2$, $\log (n^2)$ and $\log \log n$? In research articles (e.g. this one's abstract), I often see the complexity of an algorithm expressed using a somewhat ambiguous notation:

$\log^2(n) = ?$
$\log(n)^2 = ?$
$(\log n)^2 = (\log(n)) \times (\log(n))$
$\log(n^2) = \log(n \times n)$
$\log \log n = \log(\log(n))$

The last three case are easy enough to understand, but what about the first two? The operator precedence is unclear. Do they mean $\log(n \times n)$, or do they mean $(\log(n)) \times (\log(n))$, or do they mean $\log(\log(n))$?

Citing a reliable source would be a plus, so that I can confidently add this information to Wikipedia.

Note I'm asking about the meaning of big-O or about $O(\log n)$ complexity. I'm interested in what the $^2$ means (square the $n$, square the result of $\log(n)$, or $\log^2$ = $\log \cdot \log$).

For the first one, you can find an answer here:

  (log(n))² means log²(n)

And from this question for example you can guess that:

  log(n)² = (log(n))²

So both the first and the second essentially mean

  (log(n)) × (log(n))

(Unfortunately, not with more reliable sources than stackexchange...)


Enumerating the List of `nPr` (n Permute r) objects I have been using MATLAB for a particular project, and have seemed to find a function that may or may not exist. This question isn't MATLAB specific, more algorithm specific.

I have a list of 12 items, indexed from 1 to 12. I want to be able to create a list of all possible permutations of these 12 items where I only want to select 6 of them per entry.

Here is a reference to what nPr is for those unfamiliar.

In MATLAB, there is a function called perms(A) such that it calculates nPn where n = A.length. However what I am looking for is nPr where n = 12 and r = 6. Is there a way to either

Exploit the perms function such that it does nPn such that n = 6, but in a way that it actually calculates nPr where n = 12 and r = 6.
Write a recursive algorithm to replace the perms(A) function and create a perms(A,r) function?

Any pointers or tips would be much appreciated and helpful.

This is more of a MATLAB specific answer

  arrayfun(perms,nchoosek(A,r))

*Think of this as conceptual answer, because I have have been away from MATLAB and can't test it right now.

In other words,

get unordered combinations of elements in A, taken r at a time. using nchoosek.
get ordered combinations (with perms) of each unordered combinations. Applying a function to each element of a list can be done via arrayfun.


Turing machine generating $a^b$ for given a and b I want to draw an state diagram for a Turing machine such as:
If "a" and "b" are the inputs, output in tape will be $a^b$.
I saw many Turing machines that output:
$a+b$ $~~$ ,$~~$ $a-b$ $~~$ , $~~$$a*b$ $~~$ ,$~~$ $a/b$
And also I know how to design a Turing machine for accepting $x^{2^n}$,$x^{3^n}$ and ...
But for generating I have no idea...
Question 1:
Is it possible to improve $a*b$ Turing machine inorder to generate $a^b$  ?  How ?
Question 2:
Should we add more than one tape to this machine or thats easy to show even with only one tape?

It is possible. Practically, $a^b=a*a*a*\dots*a$, hence can be computed using a combination of the multiplication turing machine (to compute the multiplications), and the subtraction TM, in order to count the number of multiplications.

There is a reduction from multiple tapes TM to a single tape TM, so anything possible with multiple tapes is also possible with a single tape (with increased time complexity). To see why, try to think of the "even" spots in a tape as one single tape, and all the "odd" spots as another tape. This allows us to effectively place any number of TM tapes inside one single tape, but if you look carefully into the way its implemented you will see that it will come at the cost of increased time complexity (specifically, its bounded by the space complexity times the time complexity of the multiple tape machine)


Should planar Euclidean graphs be planar straight-line graphs? An Euclidean graph, by definition is

  A weighted graph in which the weights are equal to the Euclidean
  lengths of the edges in a specified embedding

and a graph is called planar if

  it can be drawn in a plane without graph edges crossing

lastly, a planar straight-line graph (PSLG) is

  embedding of a planar graph in the plane such that its edges are mapped into straight line segments.

By these three definitions, I cannot conclude that if an Euclidean planar graph should be a PSLG or not.
For instance, given an Euclidean non-planar graph:

I can convert this graph into an Euclidean planar graph

by sticking with the definitions. Given the definitions above, the former one is a non planar straght-line graph whereas the latter one is a planar graph. Assume that the length of each edge is preserved. Then is the latter one still an Euclidean graph?

Fáry's theorem states that every planar graph can be drawn in such a way that its edges are (non-crossing) straight lines. Hence every planar graph is a planar straight-line graph.

However, this doesn't really have any bearing on the definition of Euclidean graph. According to the definition you link too, the edges need not be straight. A Euclidean graph is a planar graph in which the edge weights are their lengths in some specific (planar) embedding. In particular, a non-weighted graph isn't Euclidean any more than a cucumber.

Finally, the first graph in your question is planar – it's just that your specific embedding isn't a planar embedding.


When does a semaphore issue a wait and when does it issue a signal? In my textbook, Operating Systems: Internals and Design Principles (9th Edition) by William Stallings in chapter 5, it explains how semaphores work:

The fundamental principle is this: Two or more processes can cooperate
by means of simple signals, such that a process can be forced to stop at
a specified place until it has received a specific signal. Any complex
coordination requirement can be satisfied by the appropriate structure of
signals. For signaling, special variables called semaphores are used. To
transmit a signal via semaphore s , a process executes the primitive
semSignal (s) . To receive a signal via semaphore s, a process executes
the primitive semWait (s) ; if the corresponding signal has not yet been
transmitted, the process is suspended until the transmission takes
place.

I can't find a description in chapter 5 of when a semaphore would issue a semSignal vs a semWait (which are also sometimes called signal and wait). Can anyone describe the conditions under which semSignal would be issued vs a semWait?

The semaphore doesn't issue those.  A semaphore is an object that can be used by processes to coordinate between themselves.  Thus, a process will call semSignal or semWait on a shared semaphore.  We can't describe the conditions under which it will do that in general, because it's up to each process how it wants to use semaphores.  Semaphores are a primitive that can be used in many ways.  You should be able to find many examples online or in your textbook of using semaphores for coordination; that will give you some examples of specific processes and when those particular processes will invoke those operations on a semaphore.


On approximations and reductions This may be a naive question but I am a bit clueless. I was under the opinion that given two NP complete problems, $P1$ and $P2$, if $P2 \in APX$ and $P1 \notin APX$, then we cannot have a direct reduction $P2\leq P1$ but we can have a reduction $P1\leq P2$.

In this paper on page 165 http://www.lancaster.ac.uk/staff/letchfoa/articles/cut-projection.pdf, there is a reduction $MAXCUT \leq STABLESET$. That is, given an instance of STABLESET, I can find an instance of MAXCUT. Why cant I use the approximate solution for MAXCUT to find an approximate solution to STABLESET?

In short, a reduction need not preserve approximations. For more details, see my answer on cstheory to a similar question.


Infinite Huffman Tree We have to derive an optimal binary encoding for the infinite set of symbols $\{s_1, s_2, \dots \}$. They're distribution is given by
$$p(s_i) = 9 \cdot 10^{-i}$$

My intuition was to use a Huffman encoding. Obviously the Huffman encoding
algorithm needs to first find the smallest two elements, which we can't do. But, if we imagine the last step of the Huffman algorithm, it would have the two elements $s_1$ and the supersymbol $s_2s_3s_4\dots$ with probabilities $0.9$ and $0.1$ respectively. Thus, (if left is $0$ and right is $1$) symbol $s_1$ would get codeword $0$. The other symbols would all get a codeword starting with $1$. This tree is clearly self similar. If we represent binary trees as tuples with an empty tree as the nullset $\varnothing$, we have that this tree is given by

$$ T = (\varnothing, T) $$

That is, a left branch which is empty an the right branch which is identical to the whole tree. Thus, we get the codewords

$$ s_1 \mapsto 0, s_2 \mapsto 10, s_3 \mapsto 110, s_4 \mapsto 1110, \dots $$

Now, I know that these are optimal. You can do a proof by contradiction showing that changing any of these codewords and still satisfying the Kraft inequality will cause the expected length to increase.

My question is, is the fact that this infinite Huffman tree arrived at the answer a coincidence or is there a way to formalize Huffman encoding for an infinite set of symbols.

I don't think there is an algorithm that works for any infinite probability distribution. However, you have taken the case of a geometric distribution for which there happens to be a neat answer. It was proposed by Gallager in this paper [1]. So if you apply his algorithm, you will see that you obtain exactly the same answer you proposed.

[1] Gallager, R., & Van Voorhis, D. (1975). Optimal source codes for geometrically distributed integer alphabets (corresp.). IEEE Transactions on Information theory, 21(2), 228-230.


Can one have a condition like this in semidefinite programming? Is it possible to have the following condition in a semidefinite programming as a constraint?

$
         M=
            \left[ {\begin{array}{cc}
             a & \sqrt{u} \\
             \sqrt{u} & b \\
                \end{array} } \right]
        \geq 0$

where $\geq 0$ means positive semidefinite.

Assuming that a, b, and u are real variables in your semidefinite program, the answer is negative.

The important fact here is that each constraint in a semidefinite program defines a convex set.  Your condition cannot be written as a constraint in a semidefinite program because the set of points (a, b, u) ∈ ℝ3 that satisfy the condition is not convex.  I suggest that you try to prove that this set is indeed not convex, but here is a proof (put the mouse cursor in the box below to show the proof):

   Proof: (a, b, u) = (1, 1, 1) and (a, b, u) = (3, 3, 9) satisfy the condition, but their midpoint (a, b, u) = (2, 2, 5) does not satisfy the condition.


Graph theory, $n$ people sitting around table $n$ people want to have dinner together around a table for $k$ nights so that no person has the same neighbor twice.

How big can $k$ be in terms of $n$?
Does everybody get to sit next to everybody else?
How many seating arrangements are there?

Point 3. If the seats are unlabelled, the number of arrangements is $\frac{(n-1)!}{2}$.

Explanation: put a hat on one of the person and take it as the leader. Then you have $n-1$ choices for the person to his right and so on. But each arrangement is counted twice if you consider that circular arrangement $(a,b,c,d)$ is the same as the circular arrangement $(a,d,c,b)$.

Point 2. Answer is no. Take four people. They can only share one meal in your conditions. The people facing each-other will never eat side by side :-(

Point 1. You basically want to partition the edges of the complete graph on $n$ vertices into $k$ hamiltonian cycles. An obvious upper bound is then that $nk \leq {n \choose 2}$ so that $k \leq \left\lfloor \frac{n-1}{2} \right\rfloor$. This upper bound is met when $n$ is a prime number (take a first cycle then people at distance 2 then people at distance 3...)


Probability of detecting errors in codewords I have been struggling with the below question for quite some time, and I don't have a pointer to move forward.

  A certain Error Control Coding scheme using block codes takes an input block (dataword) of 500 bits
  and appends a 50 bit code to produce a 550 bit codeword which is then transmitted across channel that
  causes individual bits to flip with a probability of 0.1 independently. The pairwise Hamming distances
  between all the codeword pairs is so large that the probability of an error occurring that converts one to the
  other can be neglected, except as follows: two codewords C 1 and C 2 have a Hamming distance of 10, and
  two codewords C 3 and C 4 have a Hamming distance of 6.
  Assuming no knowledge about what datawords may be more or less likely to be desired to transmit, what is
  the probability that a given block transmission will be corrupted by the channel but the error will go
  undetected by the receiver? You may answer with an expression, but the answer has to be completely
  numerical (no symbols).

My thought process about this question is that the probability needs to be calculated as such :
Pr(Selecting either C1 or C2) * P(error in C1 or C2) + Pr(Selecting either C3 or C4) * P(error in C3 or C4).
I feel the Pr(error) is given by a binomial distribution of 55CX(0.1)^x(0.9)^550-x where X=10 or 6.

First, am I thinking about the problem correctly  ? If yes , how do i derive the probability of selection of a particular codeword ?

Edit: I don't have the exact source per se, because this question is from a random uni final exam that I found on the internet. I am prepping for my own exam, and came across this question.

I think your approach is fine, but the question is not fully well-defined (unless I'm missing something).

The general error probability is
$$\sum_{i} \Pr(C_i\text{ is transmitted})\Pr(\text{error}\mid C_i\text{ is transmitted}).$$
The questions explicitly says that the error probability of all codewords except $C1,C2,C3,C4$ is negligible, so the error becomes:

$$\sum_{i\in\{1,2,3,4\}} \Pr(C_i\text{ is transmitted})\Pr(\text{error}\mid C_i\text{ is transmitted}).$$

Computing the error probability is easy: if the Hamming distance is $x$, it takes $\lfloor x/2\rfloor +1$ bit-flips (or more) to corrupt the codeword, and $x$ bit-flips (or more?) to be undetected by the receiver. You can easily compute that in a similar way to what you wrote, and get a reasonable bound.
However, the question explicitly says that the terms $\Pr(C_i\text{ is transmitted})$ are unknown, yet it requires you to give an exact numerical answer. contradiction.


Turing Machine to Accept String from a 3 character alphabet I need to create a turing machine that accepts the language $a^ib^jc^k$ where $i \ge j \ge k$, but I am not even really sure how to start. Turing machines in this context are a hard concept for me to grasp for some reason.

One idea is to delete characters, to make it easier let me introduce @ character - it will denote empty space after scratching characters.
For example let input string be $BaabccB$, where $B$ is blank symbol.
At first check for $a$ and create state, say $qa$ which looks for $a$ and then replaces it with $@$ switches to $qb$ moves right until it finds $b$.
Then it replaces $b$ with $@$ switches state to $qc$ and moves right until it finds $c$.
Here again replaces $c$ with $@$ and switches to state $ql$ moves to the left until $a$ is found.
While moving right if blank symbol is encountered, it means that there are less symbols of particular character, this is good according to given language, if the next character is also missing otherwise it breaks inequality and we reject. Also when we seek $b$ but encounter $c$ we reject. After consecutive $c$ if there are other symbols, we reject (it is something like $abca$
When moving left, when blank is encountered, we are finished and accept.

It may happen that there are not sufficient number of $a$ or any character, so after reaching blank character we move right to delete $@$ characters. If we clear all and hit blank, we accept, otherwise we reject as some characters broke inequality.

Example: $BaabccB$
$B@abccB$ move right, switch state, replace $b$
$B@a@ccB$ move right, switch state, switch $c$.
$B@a@@cB$ move left until $a$ replace
$B@@@@cB$ move right, switch state, $c$ is encountered in $qb$ state, it means that $#c > #b$ reject.

Excersise 1:
Try to solve similar question where $i \ge j \le k$

Excersise 2:
Try to solve similar question where $i = 2j = 3k$


Showing NP-hardness of HALF-SAT Yesterday I wrote my undergraduate exam in complexity theory. I had to leave off one question, which bugs me since then. Consider:
$$ HALF-SAT = \{ \varphi \mid \varphi \text{ is a formula which is satisfied by at least half of all assignments }\} $$
I'd like to know how I can prove NP-hardness.

FWIW, here's what I figured out:

HALF-SAT is probably not $\in$ NP, at least in no verifiable way I can think of (not really relevant to the question)
SAT $\preceq$ HALF-SAT doesn't work, at least not by just adding clauses with new variables, doesn't change satisfiable-assignments/arbitrary-assignments ratio
TAUT $\preceq$ HALF-SAT via $\varphi \mapsto \varphi \wedge x_{new}$, but that's coNP-hardness (together with NP-hardness this further lets me assume 1., intuitively)

And no, this has nothing to do with the problem you find via googling "HALF-SAT".

Hint: Take a new variable $x$ and add it to all clauses. This shows that HALF-SAT' is NP-hard, where HALF-SAT' differs from HALF-SAT by strengthening "at least half" to "more than half". HALF-SAT is similar.

The $P$-closure of HALF-SAT' (and HALF-SAT) forms the complexity class $PP$.


Finding the size of the smallest subset with GCD = 1 This is a problem from the practice session of the Polish Collegiate Programming Contest 2012. Although I could find the solutions for the main contest, I can't seem to find the solution for this problem anywhere.

The problem is: Given a set of $N$ distinct positive integers not greater than $10^9$, find the size $m$ of the smallest subset that has no common divisor other than 1. $N$ is at most 500, and a solution can be assumed to exist.

I managed to show that $m \le 9$. My reasoning is: Suppose there exists a minimal subset $S$ of size $|S|=10$, with gcd = 1. Then all 9-subsets of $S$ must have gcd > 1. There are exactly 10 such subsets, and their gcds must be pairwise coprime. Let these gcds be $1 < g_1 < g_2 < ... < g_{10}$, where $\gcd(g_i,g_j)=1$, for $i \neq j$. Then the maximum number in $S$ is $g_2g_3...g_{10}$. But $g_2g_3...g_{10} \ge 3\times5\times7\times11\times...\times29=3234846615 > 10^9$, a contradiction.

However, even with this, a straightforward brute force is still too slow. Does anyone have any other ideas?

This problem is equivalent to the following, and it's trivial to construct reduction both ways.

Given a list of bit vectors, find the minimum number of them such that and all of them result the $0$ bit vector. $(*)$

Then we show set cover reduces to $(*)$. By set cover, I mean given a list of sets $S_1,\ldots,S_k$, find the minimum number of sets that covers their union.

We order the elements in the sets to be $a_1,\ldots,a_n$. Let $f(S) = (1-\chi_{a_1}(S),\ldots,1-\chi_{a_n}(S))$, where $\chi_x(S) = 1$ if $x\in S$, 0 otherwise. Note this function is a bijection so it has a inverse.

Now, if we solve $(*)$ on $f(S_1),\ldots,f(S_k)$, and the solutions is $\{ f(S_{b_1}),\ldots,f(S_{b_m})\}$, then $\{ f^{-1}(S_{b_1}),\ldots,f^{-1}(S_{b_m})\}$ is the solution to set cover.

Thus I would think this problem is testing one's ability to prune the search space.


If $L_1L_2$ is regular language then $L_2L_1$ is regular to? We have two languages: $L_1,L_2$. We know that $L_1L_2$ is regular language, so my question is if $L_2L_1$ is regular to?

I try to find a way to prove it...

I can't assume of course that $L_1,L_2$ are regular...
So I look for a way to prove it.

I'd like to get any hint!

Thank you!

I was posting only a hint, then I saw other full answers, so this is a full (hidden) succinct solution :-)

   Let $L_1 = \{ 1^p \mid p \text{ is prime}\}$, $L_2 = \{ 1^* 0 \}$; we have $L_1 L_2 = \{ 11^+ 0\}$ which is regular, but $L_2 L_1 = \{ 1^* 0 1^p \mid p \text { is prime}\}$ which is not regular.


If a predicate is not computable, what can be said about its negation? Doing the following exercise:

Let $\overline{HALT(x,y)}$ be defined as
$\overline {HALT(x,y)} \iff \text{program number y never halts on input x}$
Show that it is not computable.

Just want to make sure I have understood the concept correctly. We had in a theorem that HALT(x,y) is not computable which means that we cannot determine whether program number y eventually halts on input x. I realized that $\overline {HALT(x,y)}$ is the negation of HALT(x,y). Is it true (I cannot find it in my book or on the internet) that if a function is (not) computable, its negation is also (not) computable? A function being computable means there is a program p which computes it, we cannot say there is a program Q that computes its negation. Or can we draw such conclusion?

If a function F is computable, so is !F, as you can simply compute F and return the negated result.

For the same reason, if a function isn't computable, neither is its negation.


The complexity of BDD Synchronous Composition As shown in Byrant's original paper, the time complexity of (single-variable) composition algorithm is cubic, and it is a tight upper bound. My question is about synchronous composition, written as
$$f' = f(x_{1},\dots,x_{n})|_{x_1=g_1, \dots, x_n=g_n}$$
where you replace all variables of $f$ synchronously with other Boolean functions $G$ over $X$.

However, I couldn't find an explicit reference mentioning time and space complexity of synchronous composition for BDDs. Is anyone of you aware of such results?

I'm not aware of such a result in any paper, but that may be because it is relatively clear that this operation is non-polynomial.

And here is why. Assume that we have a satisfiability problem with $n$ variables and $c$ clauses. We allocate variables $v_1, \ldots, v_n$ and $v'_1, \ldots, v'_c$ in the BDD manager, build a BDD

$$B = \bigwedge_{i \in \{1, \ldots, c\}} v'_i$$

and also BDDs $x_1, \ldots, x_c$ that encode the clauses over $v_1, \ldots, v_n$. Note that all BDDs are of size $O(c)$ or $O(n)$, which is even independent of the variable ordering.

Now computing

$$C = B[x_1/v'_1,x_2/v'_2, \ldots, x_c/x'_c]$$

gives us a BDD that represents the set of all solutions to the SAT problem (where [...] is the application of the synchronous composition operator). If we could compute $C$ in time polynomial in the size of the SAT instance, that would give us a polynomial time algorithm for SAT. Even more, with $C$, we can count the number of solutions, which lies in a higher complexity class that finding them. Also, making use of a fixed variable ordering of the BDD, the argument can be extended to talk about the QBF problem, which is PSPACE complete.

Obviously, this does not answer your question to 100%. But in the light of this line of reasoning, I would find it surprising if the algorithm actually implemented in BDD libraries was polynomial-space (or even polynomial time).


What to call a script that runs other scripts? I have a number of small scripts that are being called, in order, by one larger script. So I can run them all with just one command. I was wondering if there was a technical name for this main program (that runs the smaller ones). Currently I am calling it the 'master', but am not sure if that is correct.

It's called a "driver". A program in C or C++ is a program just as much as a script is I would think. A script usually isn't compiled like the heavy-duty programs of the world like Java and C.


Where we Use Dynamic Programming and Greedy Algorithm? Can someone tell me where we use Dynamic/Greedy algorithm and how we trace from the question that it will solved by any one of the above?

Thanks

Greedy Algorithm:

  An algorithm that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems. [1].

Problems that can be solved by a Greedy Algorithm will have two properties:

Greedy Choice Property;
Optimal Substructure.

Essentially, Greedy Algorithms solve combinatorial problems having the properties of matroid.

For more detail you can consult Introduction to Algorithm.

Dynamic Programming:

  Solve an optimization problem by caching subproblem solutions (memoization) rather than recomputing them.  [2]

Dynamic Programming algorithms are often used for optimization because it will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem.

Now, problems that can be solved by a Dynamic Programming Algorithm will have this necessary condition:

  Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. [3]


van Emde Boas tree: why store max recursively? In both CLRS (third edition) and Erik Demaine's lecture, the van Emde Boas tree is defined to store max but not min recursively.  Why store max recursively?

If it is not stored recursively, insert(V, x) can take advantage of the special case where a cluster or summary contains one element (min = max), although I think the advantage gained from this is insignificant.  Keith Schwarz implements it this way in his Archive of Interesting Code.  So why do CLRS and Erik not make use of this optimization in the algorithm?  Is it actually a mistake?

take a look here he explains what you are saying , the theory does not guarantee the algorithm performance so what you pointed at to be weird is not but it is equivalent both cases and give the same $O(\log \log (u) )$ but it may differ in performance as you said .


Algorithm to determine two binary expression trees will give the same result based on associative and commutative properties of some operators Given n different numbers, I would like to find out whether there exists an algebraic expression using all the n numbers, with n−1 binary operators and unlimited number of parentheses, that evaluates to a certain number T. My idea is to make use of binary expression trees, construct all possible trees and then find the result by brute force.

As I have learned, the number of possible combinations will be:

$$\begin{aligned}
        \frac{(2(n-1))!}{(n-1)!n!} n! s^{n-1}\\
      \end{aligned}$$

where s is the number of different binary operators that is allowed to be used (e.g. if we allow +, −, × and ÷, then s=4), and

$$\begin{aligned}
        \frac{(2(n-1))!}{(n-1)!n!}
      \end{aligned}$$

is the number of different types of binary expression trees that can be constructed without considering the content of the nodes.

To speed up the search, I have an idea to make use of the associative and commutative properties of the operators + and ×. An intuitive case will be, if all the n−1 operators chosen are all +, then all the trees will evaluate to the same result, regardless of how the n numbers are allocated in the leaf nodes. However, this obviously does not apply to operators − and ÷. And, in the general case, the operators chosen will consist of a mixture of +, −, × and ÷, so is there an algorithm to check the trees will evaluate to the same result without actually doing the calculation?

e.g. A binary expression tree that represents (8−5)×(6+3)×(7−4) will give the same result as a binary expression tree that represents (8−5)×((6+3)×(7−4)). Going even further, they will also give the same result as a binary expression tree that represents (3+6)×(7−4)×(8−5). Is there such an algorithm to detect these trees will evaluate to the same result?

Note that if you just want to know if two equations without variables have the same result, then just evaluate them already.  But it's more tricky with variables:

I assume that you are basically just functionally rearranging lists (ie: like Python/JavaScript/Lisp code).  For associative binary operators, it's convenient to make them have n operands to avoid a re-association pattern matching mess.  A sum or product of one operand is a redundant parenthesis.  Because they happen to be commutative, have the sum and product objects consistently sort their operands if you want them to be efficiently comparable (ie: define a canonical form that everything should reduce to).

It is harder if variables are involved though.  The equals sign can be treated as just another binary operator to create new expressions, where you do things like:  a, (a=(b*2)), ((a=(b*2))+6), ((a+6)=(b*2)+6), ((a+6)=(2*b)+6).  At that point, you construct new expressions like:  equate(expr,expr), add(expr,expr), mul(expr, expr), ldistribute(expr,expr), rdistribute(expr,expr), commute(expr), etc.

Some of the rules are obvious like distributing multiplication over addition, or additive or multiplicative cancellation; and usually go in one direction (like automatic differentiation).  But there will be other times where you will need to do a more clever search (like a chess engine), doing things like multiply an expression times 1, and equate it with a new variable divided by itself, etc.  One of the more tricky things in an algorithm for solving is that some operations like division add new logical constraints.  If you construct  div(add(a,b),x), you implicitly construct a logical constraint for x!=0; and you need to work these constraints in so that the search for the solution doesn't generate nonsense.

These kinds of programs are usually written as pattern matching and rewriting, with provisions made to not go in infinite loops.


Combining Predicate Logic and BigO I am a beginner to predicate logic and BigO and am having though time understanding the definition of BigO in terms of predicate logic in the picture attached. I particularly am unable to understand what is meant by n0 in this context. Any help is greatly appreciated.

What the definition is saying is: $f\in O(g)$ if there's a number $n_0$ such that $f(n)$ is less than some multiple of $g(n)$ (that's where the $c$ comes in) for all $n$ larger than $n_0$. In simple terms, it's saying that $f$ is eventually bounded by some fixed multiple of $g$.

Big-O notation is essentially a simplification describing the ultimate rate of growth of a function. Here we don't care at all if, say, $f(n)$ is bigger than $43\cdot g(n)$ for the first thousand values of $n$: if $f(n)<43\cdot g(n)$ for all the rest (the bigger values of $n$), we've established that a multiple of $g$ is an upper bound on the values of $f$.


Alternatives for finding sources in a DAG I have a hard time seeing what the alternative approach is in linearizing a directed acyclic graph (DAG). Chapter 3 of Algorithms by Dasgupta et al. states:

Property Every dag has at least one source and at least one sink.
The guaranteed existence of a source suggests an alternative approach to linearization:

Find a source, output it, and delete it from the graph.
Repeat until the graph is empty.

However, we can linearize the DAG by arranging the post numbers in decreasing order. Isn't this the alternative above the same thing? How else can we find sources if we don't have to pick the largest post number, which is the source?
Isn't deleting the source an extra step and therefore unnecessary? I assume that we have already run depth-first search to obtain the pre and post numbers.

Use a priority queue to keep a list of all vertices with prioritization on in-degrees.
Pop off one vertex $v$ with in-degree zero, decrement the in-degree-count of the out-neighborhood of $v$.
Repeat until empty.
If the input graph is a DAG, this will give you a topological ordering.


circle packing algorithm used by Percolator I was admiring this rendition of the Mona Lisa from quasimondo's Flickr account.  He says:

  Combining circle packing with data visualization. The pie charts show
  the distribution of the dominant colors under the circle area.

  The circle packing technique used here is a combination of an image
  segmentation with a distance transform and the first one who came up
  with it is John Balestrieri: www.flickr.com/photos/tinrocket/

I have traced it to an app called Percolator

How are such circle packings calculated? How are the pie charts calculated from the image?

Since I created this I probably can explain it best ;-):

the first step is to calculate an image segmentation which will combine small areas of similar colors into bigger chunks. The tolerance values of that segmentation will influence how big the biggest circles can become (higher tolerance => bigger areas => bigger circles)
You proceed by processing each of the found areas individually:
calculate an euclidean distance map for the area. This map will tell for every pixel the distance to the nearest edge. Find the maximum value in that map. This is the pixel that has the furthest distance from an edge. Conveniently that distance will be the radius of the biggest circle that you can fit into that area. Add that circle (center position + radius) to a list. Now you subtract that circle from the area - subtract in this case means that if the original area is all white pixels surrounded by a black border you simply draw a black circle over it. Recalculate the distance map for the remaining white area pixels repeat the above process until there are no more distances bigger than some chosen threshold (the smallest radius you want to display).
the last part is to calculate the pie charts for all the circles you have collected. In order to do that you accumulate all the pixel colors of the original image that are lying under a circle and calculate a color quantization for them. In the Mona Lisa example all the colors are reduced to the 7 most representative. In order to calculate the pie ratios you simply count for each of the 7 representative colors how many of the original colors are their nearest neighbors. The only thing left to do is to draw a pie chart using the ratios and colors at the stored circle position.


Existence of Hamiltonian cycle in a 3-regular $C_n$-free graph I know that Hamiltonian cycle problem in $3$-regular triangle-free graphs is $NP$-complete. I would like to know how far we can stretch this result. Observing that a triangle is just $C_3$ cycle, what is the longest fixed-length cycle $C_g$ such that deciding the existence of Hamiltonian cycle in $3$-regular $C_g$-free graphs is still $NP$-complete?

Have a look at this paper "Not Being (Super)Thin or Solid is Hard: A Study of Grid Hamiltonicity" Theorem 6.1 states that HCP (Hamiltonian Cycle Problem) for planar graph of maximum degree $3$ and girth $g$ (i.e. $C_{g-1}$-free) is $NP$-complete, for arbitrary $g>6$ (i.e. $g\geq 6$ in your notation).

So, in your notation, we are left with the undetermined cases of $g=4,5$.

So if you are willing to relax $3$-regular to $\Delta(G)=3$, then $g$ (actually $g+1$ for the girth value) can be arbitrarily large.


How can I reduce Subset Sum to Partition? Maybe this is quite simple but I have some trouble to get this reduction. I want to reduce Subset Sum to  Partition but at this time I don't see the relation!

Is it possible to reduce this problem using a Levin Reduction ?

If you don't understand write for clarification!

Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = \sum L$. Let $L'$ be the list formed by adding $S+B,2S-B$ to $L$.

(1) If there is a sublist $M \subseteq L$ summing to $B$, then $L'$ can be partitioned into two equal parts: $M \cup \{ 2S-B \}$ and $L\setminus M \cup \{ S+B \}$. Indeed, the first part sums to $B+(2S-B) = 2S$, and the second to $(S-B)+(S+B) = 2S$.

(2) If $L'$ can be partitioned into two equal parts $P_1,P_2$, then there is a sublist of $L$ summing to $B$. Indeed, since $(S+B)+(2S-B) = 3S$ and each part sums to $2S$, the two elements belong to different parts. Without loss of generality, $2S-B \in P_1$. The rest of the elements in $P_1$ belong to $L$ and sum to $B$.


Formulas for which any equivalent CNF formula has exponential length I read a claim that

  there are formulas for which any equivalent CNF has exponential length.

Can you show me an example for such a boolean formula? I have been trying to build it myself and failed.

Try parity. Parity of $n$ variables has formulas of size $O(n^2)$, but every clause in the CNF must be of width $n$, so there must be at least $2^{n-1}$ of them.

Here are some more details. The $O(n^2)$ formula for parity is obtained by a recursive construction. For simplicity, let's assume that $n = 2^m$ and only count leaves. We use the following formulas:
$$
\begin{align*}
\operatorname{parity}(x_1,\ldots,x_{2n}) = &(\operatorname{parity}(x_1,\ldots,x_n) \land \lnot \operatorname{parity}(x_{n+1},\ldots,x_{2n})) \\ \lor &(\lnot \operatorname{parity}(x_1,\ldots,x_n) \land \operatorname{parity}(x_{n+1},\ldots,x_{2n}))
\end{align*}$$
and $\operatorname{parity}(x_1) = x_1$. Let $P(n)$ be the number of leaves in $\operatorname{parity}(x_1,\ldots,x_n)$. Then
$$ P(2n) = 4P(n), \quad P(1) = 1. $$
The solution to this recurrence is $P(2^n) = 4^n$. Since parity of $n$ variables can be obtained from parity of $2^{\lceil \log n \rceil} < 2n$ variables, in total parity for $n$ variables can be realized using a formula containing at most $4n^2$ leaves. The length of a binary encoding of the formula is $O(n^2\log n)$ (the $\log n$ factor comes from the fact that the indices have length $\log n$).

Regarding CNFs, let's consider DNFs instead; the situation is symmetric. Suppose $\phi = T_1 \lor \cdots \lor T_\ell$ is a DNF for $\operatorname{parity}$. Each $T_i$ must contain $n$ variables: given the values of even $n-1$ variables, you cannot be certain that $\operatorname{parity}$ is true. So each term "catches" one $1$-input of $\operatorname{parity}$, of which there are $2^{n-1}$.


Why isn't every monotonic grammar context sensitive free? The question is really confusing me. I know every context sensitive grammar is monotonic but not vice versa. e.g. AB--->BA is monotonic but not context sensitive. Can someone explain to me in simple terms why this is?

If you're asking why the grammar with the rule $AB \to BA$ is not context-sensitive, you can find an explanation here.

The short answer is that it depends on the definition, but with one standard definition, the rule $AB \to BA$ simply doesn't satisfy the criterion for a rule to be allowable in a context-sensitive grammar.


Is the closure of P under e-free homomorphisms equal to NP? The context free languages can be obtained as the closure of the Dyck language under the cone operations. The Dyck language $D_2$ is a deterministic context free language, and the cone operations correspond to the operations that can be implemented by nondeterministic finite state transducers. This result becomes less surprising, if we consider that nondeterministic finite state transducers can provide certificates (or verifiers, or witness strings, I wrongly called this oracle strings initially) of length $O(n)$, where $n$ is the length of the input string.

The definition of the class $\mathsf{NP}$ allows for certificates of length $O(n^c)$, but many $\mathsf{NP}$-complete problems are perfectly happy with certificates of length $O(n)$. The transducer should not change the length of the input uncontrollably, so we need faithful cone operations. For $\mathsf P$, this should be equivalent to closure under e-free homomorphisms. (Intuitively, the homomorphism removes the certificate). Hence my question:

  Is the closure of $\mathsf P$ under e-free homomorphisms equal to $\mathsf{NP}$?

As stated above, this question should be equivalent to the question whether certificates of length $O(n)$ (instead of $O(n^c)$) are enough for $\mathsf{NP}$.

As Ryan Williams explains on CSTheory.SE, the answer is probably no: certificates of linear size are probably not enough for NP; some NP problems seems to require certificates of super-linear size.

You can also find some examples of NP-problems that appear to require super-linear certificates over on CSTheory: see Natural NP-complete problems with “large” witnesses and Is the Witness Size of Membership for Every NP Language Already Known?.  Also Problem unsolvable in 2o(n) on inputs with n bits, assuming ETH? might be relevant as well.


A reduction of $HALT_{TM}$ to $A_{TM}$ A widely used example of reductions, is a reduction of  $A_{TM}$ to  $HALT_{TM}$.

How to show the opposite reduction, meaning of  $HALT_{TM}$ to $A_{TM}$, if possible.

A many-one reduction from $HALT_{TM}$ to $A_{TM}$ means that all instances of the $HALT_{TM}$ problem are transformed to an instance of $A_{TM}$ (can be just one instance), such that if $A_{TM}$ is turing-recognizable then $HALT_{TM}$ is also turing-recognizable.

This reduction can be done by encoding a $TM$ $N$, such that $N$ accepts input string $\langle M,w\rangle$ iff $M$ halts with input string $w$. So if $M$ halts with input $w$, it means that $\langle M,w\rangle \in HALT$, which implies that $N$ accepts $\langle M,w\rangle$, and that the instance $\langle N,\langle M,w\rangle\rangle\in A_{TM}$.


Is there a name for the 'scope tree' organization? I could describe JQuery as a library that allows you to easily select elements on and traverse the DOM, the DOM would be the name of the tree or organizational structure of the HTML.

When you are describing what JS (or any other language) scope bubbles up from the local scope, to its parent scope, to its parent scope, to its parent scope, ...., until there are no more parent scopes, where you have reached the global Object scope, what would you call this scope organization?

As Raphael says in his comment, this is a hierarchical scope organization. But this can qualified any kind of tree structured scope, and you state in the title that it is tree structured.

The whole purpose of this hierarchy is to allow reusing the same name in a different scope, for some other naming purpose. So, given a name, you have to decide where to lokk for its meaning, in what scope.

As you suggest, you start for the current scope (to be defined ...) and you buble up to parent scopes until you find a definition for that name (a declaration usually). The first one you find is usually supposed to be the right one.

But there is a major problem remaining: which is the parent scope of any given scope? There are two major policies regarding this: static scoping also called lexical scoping, and dynamic scoping.

Static scoping corresponds roughly to the way scopes are embedded according to the program text. Dynamic scoping corresponds to the way scopes are embedded according to program execution.

So, for example, take a function foo that is declared in your program. If defines a new scope, with the variables local to foo. If the function uses a variable x that it does not declare, the meaning of the variable must be found in the parent scope. For dynamic scoping, the parent scope is that of the scoping structure (function, method, module, and whatever creates new scopes) that called the function foo. For static scoping the parent scope is the scoping structure in which the function foo was declared.

Static scoping is usually preferred because the meaning of a programming construct is independent of where it is actually used (possibly many different places), and depends only of where it is defined (only one place).  Hence program analysis, understanding, and maintenance is usually much easier with static scoping.

The story goes that dynamic scoping was invented more or less by accident, as it was used in the first Lisp interpreter in the late 1950s. People were not yet aware of the difference at the time. When they found out (see the Funarg controversy), the language was being used and it was to late. Until Scheme came in as a statistically scoped version of Lisp.

But there can be other ways of organizing scopes, of importing one scope into another, and so on. I suggest that you read the wikipedia page on scope, which you should have done before asking.


How does the bitlength of the divisor affect the running-time complexity of division algorithms? Wikipedia lists $O(M(n))$ as the best complexity (out of the algorithms listed) for division on two $n$-digit numbers, where $M(n)$ is the complexity of the multiplication algorithm of choice. This is the complexity of the Newton-Raphson division.

My question is this: what are some of the best known (wrt. running-time complexity as a function of $n$) algorithms for division of two numbers, of m, and $n < m$ digits respectively? That is, how much complexity can be gained when the two numbers are not assumed to be of the same length?

I wouldn't want to treat $n$ as a constant as I'm in particularly interested in the case of $n \in O(\log{m})$. So I'm not looking for answers that treat $n$ as in $O(1)$.

Let $M(m, n)$ and $D(m, n)$, respectively, be the costs of multiplying and dividing an $m$-digit number by an $n$-digit number (with $m \ge n$). Brent and Zimmermann give the following bounds:

$$ (1) \qquad M(m,n) \le \left\lceil \frac{m}{n} \right\rceil  M(n) $$
  $$ (2) \qquad M(m,n) \le M \left( \frac{m+n}{2} \right) (1+ o(1)) $$
  $$ (3) \qquad D(m+n,n) \le O(M(m,n)) $$
where $M(n)$ is the complexity of balanced $n$-digit multiplication.

I am not an expert in this area but I can try to summarize their explanations:

(1) is based on the idea that if $m = kn$, you can cut the larger operand into $k$ pieces, giving $M(kn, n) = k M(n) + O(kn)$.

(2) is based on using an evaluation-interpolation scheme and reducing the unbalanced multiplication to a balanced multiplication of two $(m+n)/2$-digit numbers (I realize this is a bit vague, but they don't give much details in this case).

(3) they also don't give a reference in this case; judging from the bound, it may be based on using Newton to compute the reciprocal of the $n$-digit number and then multiplication. One unbalanced division algorithm they do discuss explicitly is based on computing $n$ digits of the quotient at a time, reducing the division to several $2n$ by $n$ divisions, each of which is implemented with the recursive division algorithm. However, the latter does not seem to fit the bound (3).

For the details, have a look at Sections 1.3.5, 1.4.3, and the table at the end of their monograph.


Recurrence Equation Question I have some difficulty trying to tell which equation to use when I'm given an explanation on how an algorithm operates. Especially divide and conquer.

Normally I see these kind of equations:

C(n) = aC(n/a) + b where a and b are constants

Other times I don't see the a in front of C(n/a) as an answer. That really confuses me.

Can you tell me when I will need to use which?

Thanks!

To use any formula, you need to think about what it means. You can't just blindly apply formulas.

$C(n) = aC(n/b) + c$ (and, yes, I've changed the constants) means that the cost of running the algorithm on an input of size $n$ is $a$ times the cost of running it on an input of size $n/b$, plus some constant overhead $c$.  A typical case of that would be an algorithm that chops its input into $b$ equally sized parts and makes recursive calls on $a$ of those parts. Normally, you'd have $a=b$ (e.g., split the input into three and recurse on each part), which is why the formula you quoted has just two constants.  But you could imagine some sort of average-case analysis where you split into some number of parts and, on average, only need to look at half of them.


Approximate bin-packing? Let $X_1,...X_n$ denote some bins, and $w_1,...w_m$ some positive real numbers, where $m \in \mathbb{N}$, and the order matters, so e.g. we can't switch the position of $w_n$ and $w_1$. The goal is to take a subset of $\{w_1,...w_m\}$ and assign it for each bin, i.e. $\{w_1,...w_{i1}\}$ would go to bin 1, $\{w_{i_1+1},... w_{i_2}\}$ would go to bin 2,...$\{w_{i_{n-1}+1},...w_{m}\}$ would go into bin $n$, such that each bin contains "roughly" an equal sum of $w_i's$, e.g. the sums for $X_1,...X_n$ could approximately equal $100$, so $X_1$ could have a sum of 104, $X_2$ could have a sum of 97,... etc. Let's say this "equal sum" is $Z$.
Letting $Y_i$ be the sum for each $i^{th}$ bin, is there a way to choose Z such that the error is minimized, error being defined as $\sum_i |Y_i-Z|$, where $1 \leq i \leq n$?

I assume you want to put items $w_1$ to $w_{i_1}$ into the first bin, $w_{i_1+1}$ to $w_{i_2}$ into the second bin, etc. etc. The number n of bins is given. This can be done with something similar to dynamic programming.
Examine all possible choices for $_1$ and calculate the error from bin 1 for each of these choices.
Then examine all possible choices for $i_2$. For each $i_2$ pick all possible $i_1$ and pick one where the total error from bin 1 and bin 2 is as small as possible. For each $i_2$, remember which $i_1$ was used with it.
Then examine all possible choices for $i_3$ etc. For $i_n$ there is obviously only one choice, and you have the solution.
You will notice that you make quite a few stupid choices. If you have 10 bins, X = 100, and the sum of weights is 1,000 then puting items with very little weight or total weight over 200 into the first bin is likely stupid. To help with this we find a non-optimal solution with a greedy algorithm. Then we don't accept anything that must be worse than the greedy algorithm. In the example, if the greed algorithm finds a solution with error = 100, then we would never put less than 50 or more than 150 in weight into the first bin.


What are known 3SAT to 2SAT reductions? Is there a way to convert a 3SAT formula into a equisatisfiable 2SAT formula? Each method is of interest, even those that grow exponentially.
(So if, for example, my 3SAT formula has 16 variables and 32 clauses, a transformed 2SAT formula would have 2ˆ16 variables and / or 2ˆ32 clauses)

An example of a 3SAT formula I would like to convert is:

A xor B xor C

Or the same in CNF:

(A or B or C)
and (A or !B or !C)
and (!A or !B or C)
and (!A or B or !C)

Yes, there is.  Test whether the 3SAT formula is satisfiable or not.  If it is, convert it to the formula True.  If it is not, convert it to the formula False.  This can be done in exponential time, e.g., by trying all possible assignments, or by your favorite method for testing satisfiability of a 3SAT formula.

Under the strong exponential-time hypothesis, this is optimal: there is nothing faster.

In particular, any procedure for converting into an equisatisfiable 2SAT formula can be used to test satisfiability of 3SAT: first convert into an equisatisfiable 2SAT formula, then test the satisfiability of the corresponding 2SAT formula (can be done in linear time. This gives a method for testing the satisfiability of a 3SAT formula, whose running time is essentially the same as the running time of the conversion procedure.  Now the strong exponential-time hypothesis says that any method for testing satisfiability of 3SAT formulas requires exponential time.  It follows that any method for conversion also requires exponential time.


Is a zero matrix nilpotent matrix? Let a matrix $A=0$. Can I say $A$ is nilpotent? I am asking if the zero matrix is nilpotent or not.
Nilpotent means that $A^k = 0$ for some $k$ that is a non-negative integer. When $k = 1$, $A^k = A = 0$. Does this idea support that a zero matrix is nilpotent?

Sure, the zero matrix $0$ is nilpotent since any of its powers is again the zero matrix.
Just a side note: This question would be more suitable at the math stackexchange.


Best combination of values pulled from a matrix What is the fastest way to select $n$ values from an $n$ by $n$ matrix such that each value comes from a different row and column and the sum of those n values is minimized?

For example, given the matrix:

$$A=\begin{bmatrix}0 & 1 &5 \\1 & 4 & 3\\2 & 7 & 0\end{bmatrix}$$

The solution is $\{A_{1,2}, A_{2,1}, A_{3,3}\}$, taking 1 from the first row, 1 from the second row, and 0 from the third row.

In the brute-force case, there are $n!$ possible solutions that have to be analyzed, so the ovreall running time is $O(n!)$, although are there any faster algorithms to solve this?

It looks like the assignment problem, and it could be solved in $\mathcal O(n^3)$ using the Hungarian algorithm. In your case the $A$ is the cost matrix and the sum you are looking for is cost in the terms of algorithm.


Introduction to Linear Optimization: Driving the artificial variables out of the basis (case: no entries in the $j$-row are nonzero) Reading the book Introduction to Linear Optimization by Bertsimas and Tsiklisis, I've come across the following subject: Driving the artificial variables out of the basis.

The description is as follows: suppose an artificial variable $x_{B(j)}$ is in the basis, then examining the $j$-row of the simplex tableau there are two cases:

Either the $j$-row of $B^{-1}A$ contains a nonzero element (I understand this case !), otherwise all elements in the row are equal to $0$, which imply that the rows of $A$ are linearly independent and it is shown that the constraint $a_j x = b_j$ is redundant.

The book then suggest we delete the $j$-row of the simplex tableau and continue from there. Why is this possible ? By deleting the $j$-row of the tableau, we remove the $j$-basic variable from the basis. Also, deleting the $j$-row of the simplex tableau corresponds to deleting the $j$-row of $A$, form the basis of the basic variables, not including the $j$'th basic variable (now one dimension smaller), and then forming the simplex tableau corresponding to these ?

Now, how can we be sure the vectors corresponding to the basic variables excluding the $j$'th are linearly independent and form a basis ($j$-element is removed from these vectors) ? How do I know the simplex tableau with the $j$-row removed is actually a real simplex tableau and what vectors and basis matrix does it correspond to ?

Please give me advice and tell me whether I'm wrong and what to do, I've been really thinking over this, but haven't come to a conclusion.

The Proof is on Theorem 2.5 of the section 2.3. If you consider the polyhedron with artificial variables and redundant equality constraints as P and original with no artificial variables and no redundant equality constraints as Q. As you may see, they assumes that the l(th) basic variable is an artificial variable, so remove it will not affect original polyhedron. On the Example 3.8, the last tableau with artificial variables shows a case where a row becomes zero. If this happens with non artificial variable we have a degeneracy case.