Definition of liveness property in model checking A property $P$ is simply a set of sequences of states and a certain program is characterized by its set of sequences of states, let's call it $T$. A program is compliant to a specific property P if $T\subseteq P$.

Intuitively, a specific liveness property LP1 is the set of traces (sequences of states ) in each of which "something good" will happen, based on the specific property LP1 (for example "termination"). This means that if a program it's compliant with LP1 in each of its traces the "good thing" will happen, that is the program will terminate.

However, I don't understand how the formal definition of liveness property contains what was said, can you explain me? This definition to me makes no sense (i know all the terminology)...

$\forall t\in S^{*}\,(\exists t'\in S^{\omega }:t\leq t^{'}\wedge t^{'}\in LP1)$

I'm not sure where the particular liveness definition you wrote comes from, but the definition given in Defining Liveness (Schneider, Alpern, 1985) is as follows.
A property $P$ is a liveness property if and only if:
$$
\forall \alpha \in S^* : (\exists \beta \in S^\omega : \alpha\beta \vDash P)
$$
where $S^*$ is the set of all partial executions and $S^\omega$ is the set of all infinite executions.
This definition captures the intuition that the "good thing" (the "something good" that you mentioned) specified by a liveness property can always occur in the future. That is, no matter the finite prefix $\alpha$ you choose, you can always find an infinite suffix $\beta$ to extend it with that will satisfy a liveness property $P$. I am assuming that the $\leq$ symbol in the definition you gave is used to express a prefix relationship between traces, which makes it analogous to the definition from the paper.
You might make an argument for defining liveness in some alternative way. Indeed, two slightly different characterizations of liveness are given in that same paper (see uniform liveness and absolute liveness). The definition given above, though, provides a basis for the topological characterization of safety and liveness properties which they use to prove the decomposition theorem i.e. that any property can be expressed as a conjunction of a safety and liveness property. So, it would seem that the definition is relatively "natural".
As they remark in the final paragraph of that paper:

It seems naive to hope for a proof that a formal definition for liveness (or safety) is correct, because "good things" and "bad things" are not well-defined concepts. However, the simple topological characterization of the definitions suggests that they do indeed capture fundamental distinctions.


Can a language be the one recognized by more than one automatons? The language recognized by an automaton is defined as the set of strings that are accepted by the automaton.

I wonder if it is possible that the languages recognized by two automatons are the same? Note, if I am correct, the most general automatons are the Turing machines, and the languages recognized by an automaton are exactly the recursively enumerable languages.

The same question if restricted to the commonly-known subfamilies of languages and their corresponding automatons (e.g. regular languages, context-free languages, context-sensitive languages)?

Thanks.

Yes, of course, it is possible.  For instance, the process of DFA minimization works as follows: given a DFA $M$, produce another DFA $M'$ that recognizes the same language but is as small as possible.  That tells you that it is possible to have two DFAs (deterministic finite-state automata) that recognize the same language.

If you want an explicit example: Let $M_1$ be a DFA with a single state (which is accepting) and self-loops on inputs $0$ and $1$.  Let $M_2$ be a DFA with two states (which are both accepting) and edges from state $s_0$ to $s_1$ on inputs $0$ and $1$, and edges from state $s_1$ to $s_0$ on inputs $0$ and $1$.  They both recognize the language $\{0,1\}^*$, i.e., they are two different DFA that recognize the same language.

The same holds for other common families of languages, e.g., context-free languages and pushdown automata; context-sensitive languages and context-sensitive grammars.


Can a propositional threshold connective be expressed by standard connectives? We are given a finite set of propositional atoms $\{x_1, \dots, x_n\}$ and an integer $k$.
Can we capture through a propositional formula $\varphi$ (built from the standard connectives $\neg, \wedge, \vee$ only) the set of all models having at most $k$ atoms valued at $1$, such that the size of $\varphi$ is polynomial w.r.t. $n$? If yes, how?

The only way I see is to define $\varphi$ as an exponential-sized DNF formula containing $\binom{n}{k}$ conjunctions of literals. For instance, for n=5 and k=2, the corresponding formula would be $(\neg x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge \neg x_2 \wedge \neg x_4) \vee (\neg x_1 \wedge \neg x_2 \wedge \neg x_5) \vee (\neg x_2 \wedge \neg x_3 \wedge \neg x_4) \vee (\neg x_2 \wedge \neg x_3 \wedge \neg x_5) \vee \dots$

I got the following comment for the same question on https://cstheory.stackexchange.com/ but I do not have the level to understand it. I googled all keywords but I still cannot find the answer.

  $d_H(\omega, \omega')$ equals the number of 1 bits in the pointwise XOR of $\omega$ and $\omega'$. So, compute the XORs, count the number of 1 bits, and compare the result to k. It is well known that one can count bits with log-depth circuits (hence polynomial-size formulas), and one easy way to do that is to sum the individual bits using repeated 3-to-2 carry-save addition. See en.wikipedia.org/wiki/Carry-save_adder if you don’t know what that is. The choice of the basis of connectives is immaterial in all this, as long as it is complete

The idea is to use the following steps:

Construct an NC1 circuit computing the binary representation of $x_1+\cdots+x_n$, see for example these lecture notes (Theorem 7). This circuit implements carry-save addition.
Convert the NC1 circuit to a polynomial size formula, see for example these lecture notes (Proposition 1).
For each $k$, it is now easy to construct a polynomial size formula that tests whether $x_1+\cdots+x_n=k$.
Use up to $n$ of the formulas from the previous step to come up with your desired formula.

You can in fact implement the last two steps more efficiently, using $\log n$ rather $n$ copies of the preceding formula, by using a comparison gadget; details left to you.


Is there an asymptotically optimal algorithm for unbounded search? Suppose you have files with size $1,2,3,4\dots$ (which can be arbitrarily large and which have and can have any value that you want) and a USB-stick whose memory size $s$ you don't know, where $s$ is a positive integer and can be arbitrarily large. If $s$ is not smaller than your current file you get a message that it would be possible to write the file on the USB-stick. If your current file is larger than $s$ then you get no message. In each time unit one file can be tested. My question is, is there an algorithm which finds $s$ in as few time units as possible and would this algorithm asymptotically optimal?

The basic observation is:

  Lemma. Suppose $a_s$ is a nondecreasing sequence of integers. There exists a strategy which uses $a_s$ queries when the answer is $s$ if and only if
  $$ \sum_{s=1}^\infty 2^{-a_s} \leq 1. $$

In one direction, consider any strategy. For each $s$, let $w_s$ be the sequence of answers to queries made by the strategy. No word in the collection $\{w_s\}$ is a prefix of another, and so the collection forms a prefix code. The lengths $a_s = |w_s|$ therefore satisfy Kraft's inequality, $\sum_{s=1}^\infty 2^{-a_s} \leq 1$.

In the other direction, let us suppose that $\sum_{s=1}^\infty 2^{-a_s} \leq 1$. Decrease the $a_s$ if need be (while keeping them nondecreasing) so that $\sum_{s=1}^\infty 2^{-a_s} = 1$ (this is always possible); we can restore the original values later by asking dummy questions. Since the $a_s$ are nondecreasing, there is an index $S$ such that
$$ \sum_{s=1}^S 2^{-a_s} = \sum_{s=S+1}^\infty 2^{-a_s} = \frac{1}{2}. $$
The first question asked by the strategy is "$s \leq S$?". If the answer is affirmative, recurse on $a_1-1,\ldots,a_S-1$; otherwise, recurse on $a_{S+1}-1,\ldots$. The left recursion is different from the right recursion, since $a_1-1,\ldots,a_S-1$ is finite; but a similar argument works, with a base case of $a_1 = 0$, in which case no more questions need be asked. $\quad \square$

Given the lemma, we have reduced the question to the topic of the paper universal codes of the natural numbers, in which it is shown that no optimal strategy exists (in a certain reasonable sense formalized in the paper).


What aspects of linguistics are necessary or good for natural language processing? What aspects of linguistics are necessary or good to know for natural language processing? What references do you recommend for studying those aspects? Thanks!

NLP is a big place, you might want to be more specific.

Within information retrieval, stemming is a linguistic idea that has become useful as a heuristic means of reducing vocabulary size.  As a practitioner I learned about it from An Introduction to Information Retrieval.


Why isn't DIV necessarily in P? In my formal languages class, we discussed DIV, defined as following:

$\mathrm{DIV} = \{\langle a,b\rangle : \text{$a, b \in N$ and $a$ has a divisor $d$ for some $1 < d \leq b$ }\}$

($\langle\cdot\rangle$ means encoded, let's say as binary)

We were told that it isn't known whether DIV is in P and were tasked to prove it was in NP. I naively and mistakenly assumed that DIV was in P because of the following algorithm:

   On input <a,b>
   For all 1<d<=b
       check if d divides a.
       If so, accept.
   reject.

I thought that this algorithm would run in polynomial time because we do $b$ many divisions at worst. Division is polynomial time, therefore, $b$ many divisions is also polynomial time. (also note, $b < a$, or DIV is trivially true, where $d = a$).

However, i was told that this algorithm is not polynomial time with respect to the input. I don't really understand this part. Something along the lines of since $a$ and $b$ are encoded in binary, the input is of order $O(\log n)$. And that means our b many divisions is actually $O(b) \cdot O(\text{divisions})$, and that $O(b)$ is $O(2^{\log b})$. However, isn't $2^{\text{log base $2$ of $b$}}$ the same as $b$? How is that not polynomial time?

When we say that an algorithm runs in polynomial time, we mean polynomial in the length of the input to the algorithm, i.e., the number of bits needed to represent the input.  Suppose both $a$ and $b$ are at most $n$; then the pair $\langle a,b\rangle$ takes $\lg n$ bits to represent.  So, an algorithm whose running time is $O(n)$ takes exponential time (exponential in $\lg n$).  In particular, your algorithm is an exponential time algorithm.

The problem DIV is basically equivalent to the integer factoring problem.  It is an open question whether there exists any polynomial-time algorithm for it, but many believe that there probably is no polynomial time algorithm for it.


Two labelled transition systems feeding each other Assume we have two LTSs, say DFA with labels over the transitions (though the question can be generalized to more sophisticated automatons), define the input to each system to be as usual just the input word, and define the output of each system to be the sequence of labels of visited transitions.

Now assume that the two systems are wired directly to each other: every output letter (i.e. non-epsilon transition) in system A becomes instantly an input letter to system B, and output of B becomes input of A.

I'm looking for some analysis of this construction. Maybe anyone happen to be familiar with research topic that discuss such?

EDIT: Special case - if we have labelled pushdown automatons (context free grammars), then is the combined system as powerful as a two-pushdown machine (Turing powerful)? Or is strictly weaker?

Transducers, or finite automata with output, are very powerful when they can be iterated. After all a step of a Turing machine on a tape (or better a instantaneous description, with the state assumed to be marked on the tape) is just a simple local rewrite, and iterating that is a computation.

With two transducers $T_M$ and $T_e$ we can mimick that iteration. Assume $T_e$ just echos what it reads. $T_M$ starts on empty input by writing the initial configuration and marker $\#w_0$, which it then gets as input via $T_e$. Then $T_M$ computes the next configuration of TM $M$ and writes $\#w_2$, etcetera. In that way $T_M$ writes a complete computation of $M$ in the form $\#w_1\#w_2\#w_3\dots$. If TM $M$ cleans its tape before halting, and if $T_M$ stops (and accepts) when it reads empty tape with halting state of $M$, the system has a halting computation iff the TM has one. Quite powerful.

In a simpler example $T$ gets a string $a^n\#$ as input. If $n$ is even it halves $n$ and outputs $a^{n/2}\#$, if $n$ is odd $T$ blocks (halts in a negative state, or runs off in a never halting sequence of epsilon moves), except when $n$ equals $1$, then it will accept and halt. Observe that when the output if $T$ is fed back as input, the system will only halt when the initial value of $n$ was a power of two.

In fact, what is obtained is a so-called fixed point language of the transducer $T$: strings $w$ such that $T$ writes $T$ on input $w$.
If I recall well, the fixed point languages of `rational functions' (finite state transducers that are not necessarily deterministic, but have only one output on a given string) are co-context-free, complements of context-free languages.
Prefix and equality languages of rational functions are co-context-free, Information Processing Letters, 1988,
doi:10.1016/0020-0190(88)90167-6,


Difference between Dependent type , refinement type and Hoare Logic I know little dependent type theory. From wikipedia :

  A dependent type is a type whose definition depends on a value.

And from my Type theory course i recall that a dependent type is :

  Family of types indexed by a type.

But i have a confusion regarding dependent types and refinement types and hoare logic.

Because from Depenedent vs refinement type the refinement types looks like a Hoare logic. What more power refinement types gives besides just allowing to state predicated that has to be satisfied (Which looks like nearly same as Hoare Logic)?

What additional thing that dependent type gives in comparison to refinement types ? And is Dependent type more powerful than Refinement types + Sat/Constraint solver.

can anyone clear the air with examples.

There is recent work by Paul-André Melliès and Noam Zeilberger that explores this.  In particular the papers Functors are Type Refinement Systems and An Isbell Duality Theorem for Type Refinement Systems.  There's also a video of a talk on the first one.

I think there is a lot of confusion around refinement types due to people thinking of particular systems as representative which causes goals and details of those particular systems to be attributed to the general idea.  The short of it is type refinement systems classify terms that exist independently whereas (non-refinement) types, dependent or otherwise, are part of terms.  This may sound familiar and possibly even a bit contradictory.

The potentially familiar and possibly contradictory seeming part comes about if you view types à la Curry (extrinsically) versus types à la Church (intrinsically).  When we think of types à la Curry, we think of types as classifying untyped terms that already have meaning.  In types à la Church, the only terms that exist are well-typed terms, i.e. the type constraints are part of our syntax.  So what I'm saying is that a Curry-style type system is actually a type refinement system refining untyped terms, while a Church-style type system is not a type refinement system.  This means that, for example, we can think of the simply typed lambda calculus as either a type refinement system or as a non-refinement type system.

Of course, no one says that our terms have to be untyped terms.  We could just as well apply a type refinement system to typed terms, and, historically, this is the context in which refinement types (by that name) arose.  However, applications to soft typing illustrate something closer to the situation described above.

So far I haven't said anything about dependent types.  The reason is that it is a completely orthogonal concern.  I would say the archetypal dependent type systems are usually presented in a Church-style, and thus are not type refinement systems, but NuPRL (based on Computational Type Theory, a variant of the most archetypal dependent type theory, Martin-Löf type theory) is blatantly a type refinement system as I've described.  Terms in NuPRL may not even have types!  Admittedly, the fact that "PRL" stands for "Program Refinement Logic" might be a tip-off too.  On the flip side, Refinement Types for ML describes a refinement type system, possibly the origin of the term, which is not a dependent type system in any way.

As for Hoare triples, they are a type refinement system.  They are actually used as an example of a type refinement system in the first paper.  However, Hoare Type Theory gives something which can be viewed as a non-refinement type system for a language having Hoare triples.

To have an answer about the "power" of different systems, you need to specify a particular (family of) dependent type system(s) and a particular (family of) refinement type system(s).  The term "dependent type system" covers a very broad class of type systems, and "type refinement systems" is even broader.  Even then, the terms aren't mutually exclusive, so it would not be a comparison between "dependent type systems" and "refinement type systems".  However, if by "dependent type system" you are thinking of something like Coq, and for "refinement type system" something like Liquid Types then it is pretty one-sided.  Coq is generally viewed as powerful enough to handle virtually all of mathematics in practice; you could literally implement and prove correct a SMT solver within Coq and then use it; and a very close analog to the subset type can be formulated. (NuPRL literally has subset types.)  On the other side, SMT solvers are usually restricted to decidable theories where Coq has no such limitation; and many systems like Liquid Types have a limited and non-extensible language for specifying predicates.  (Of course, by "dependent type system" you could mean Dependent ML, and by "type refinement system" NuPRL [which is also a dependent type system] which would be one-sided in the other way.)


Dynamic array updated by adding arithmetic progressions I have an array $a_1, a_2, \dots, a_n$. After $O(n)$ preprocessing, I want to be able to compute each of the following in amortized $O(\log n)$:

Given $l,r,b,d$, for each $i \in \{l,\ldots,r\}$, increase $a_i$ by $b + (i-l)d$.
Given $l,r$, compute $\sum_{i=l}^r a_i$.

Hint: find a data structure that supports these three basic operations:

Given $l,r,b$, for each $i \in \{l,\dots,r\}$, increase $a_i$ by $b$.
Given $l,r,d$, for each $i \in \{l,\dots,r\}$, increase $a_i$ by $id$.
Given $l,r$, compute $\sum_{i=l}^r a_i$.

You can then use those basic operations to implement your operation 1.

Can you think of any way to support basic operations 1+3?  Can you think of any way to support basic operations 2+3?  If you can answer both of those questions with a "yes", you will probably then be able to solve your problem.


Polynomial size Boolean circuit for counting number of bits Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes it true verifies

$$\sum_{i = 1}^{i = n} (x_i + y_i) \not\equiv n \bmod 3$$

I should specify that this I am looking for a Boolean circuit, not necessarily a Boolean formula as it is usually written in Conjunctive Normal Form (CNF). This is because when written in CNF, a formula like the one before has a trivial representation where the number of clauses is approximately $\frac{4^n}{3}$, as it contains a clause for every assignment $(x_1, y_1, \dots, x_n, y_n)$ whose bits sum to a value which is congruent with $n \bmod 3$. Constructing such a formula would therefore take exponential time.

I have been told that a Boolean circuit can be found for this formula that accepts a representation of size polynomial in $n$. However, so far I have been unable to find it. I would use some help; thanks.

You can write a straight-line program (an equivalent way to define a circuit) that computes the Boolean variables $z_{i,j}=[x_1+y_1+\cdots+x_i+y_i \equiv j \pmod{3}]$ (where $i=1,\ldots,n$ and $j=0,1,2$) as follows:

$z_{1,0} = \lnot x_1 \land \lnot y_1$.
$z_{1,1} = (x_1 \land \lnot y_1) \lor (\lnot x_1 \land y_1)$.
$z_{1,2} = x_1 \land y_1$.
$z_{i+1,j} = (z_{i,j} \land \lnot x_{i+1} \land  \lnot y_{i+1}) \lor (z_{i,j-1} \land ((x_{i+1} \land \lnot y_{i+1}) \lor (\lnot x_{i+1} \land y_{i+1})) \lor (z_{i,j-2} \land x_{i+1} \land y_{i+1})$

The output of the circuit is $o = \lnot z_{n,n \bmod 3}$.

The circuit has size $O(n)$.


Is this NP-hard? I cannot prove it. I have a problem and I guess it NP-hard, but I cannot prove it.

Here is a layer graph, where layer 0 is the hignest layer and layer L the lowest.

there are some directed edge between layers, where an edge (A, B) indicates that node A can [cover] node B. And when A can cover B, every node on any path from A to B can cover B, B can cover itself.

Finally here comes a set of node S. I need to choose another set of node ANS, and ensure that for each node q in S, there exists a node p in ANS and p covers q.

For every node there is a cost, and I need to make the total cost of set ANS minimal.

Is this a NP-hard problem? I think so but I cannot prove it.

Could you help me?

Thank you very much.

Yes this problem is definitely NP hard. I am posting this answer since you require proof.

If you follow this link http://en.wikipedia.org/wiki/Set_cover_problem, it says that the optimization version of minimal set cover problem is NP-Hard.

The problem in the link:

  Given a set of elements {1,2,...,m} (called the universe) and a set
  S of n sets whose union equals the universe, the set cover problem is
  to identify the smallest subset of S whose union equals the universe.
  For example, consider the universe U = {1, 2, 3, 4, 5} and the set
  of sets S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Clearly the
  union of S is U. However, we can cover all of the elements with the
  following, smaller number of sets: {{1, 2, 3}, {4, 5}}

You can relate this to your problem as follows:

S is the set of nodes that cover at least one node in your input set. This can be found by conducting a DFS on the nodes of input set with the direction of edges reversed.

Now the problem described in the link is a special case of your problem, where the cost of each node is equal and you just want to minimize the number of nodes (sets).

Hence your problem is even more difficult to solve in the general case and hence it is NP Hard.


In determining whether any segments intersect, why there must be some sweep where segments $a$ and $b$ are consecutive? In CLRS, Section 33.1, we are given the any-two-segments-intersect algorithm. It's a cool algorithm for sure but going through the correctness proof, I don't know how they arrived at the following conclusion:

"Given that we have two segments (call them $a$ and $b$) that intersect at some point $p$, then there must be some sweep line $x$ for which the intersecting segments $a$ and $b$ are consecutive in the total preorder."

Why must $a$ and $b$ be consecutive at some sweep line?

I do see why visually using the figure 33.4 (page 1023) but I don't know how to prove this statement. How can I prove it?

If anyone had read that section, please enlighten me.
Thank you

Note that the statement you want prove is equivalent to showing that the shaded triangles in figure 33.4b are non-empty, or more precisely (for the left triangle) that there exists a vertical line $x$ with x-coordinate strictly less1 than $p$ such that the triangle enclosed by segments $a,b$ and line $x$ does not contain a point of any other segment.

To show this, take a vertical line $x'$ to the left of $p$ that intersects both $a$ and $b$. The triangle enclosed by segments $a, b$ and line $x'$ may contain or intersect with a number of other segments. Of those segments, consider the segment with the rightmost point of intersection with the triangle, call this point $q$. Note that $p\neq q$, since the assumption was made that no three input segments intersect at a single point. Since $q$ lies in the triangle, its x-coordinate $q.x$ is strictly less than $p.x$. Now take a line $x$ with an x-coordinate in the open interval $(q.x,p.x)$, then no other segments intersect with the triangle enclosed by $a,b,x$.

Note that this proof also shows that line $x$ can be taken arbitrarily close to the right endpoint of some segment, which are the lines that the algorithm considers.

Although this proof fails when a third segment intersects at $p$, you can still show that for any intersection point $p$, there exists a pair of segments $a,b$ that intersect at that point such that they are consecutive in the partial order, using similar ideas.

1: Depending on the definition of "consecutive", a line with x-coordinate equal to that of $p$ would do, but this is not useful for the algorithm.


Unusual applications of regular expressions? I am looking for some interesting applications of regular expressions.

Can you name any unusual, or unobvious, cases where regexes find their application?

I don't know if this question belongs here (the answer could be subjective and depend on your definition of "unusual") but here is my favorite unusual application of regex:

  converting T9 input (2-9) to English text.

For example if the user wants to write hello they presses 42556. Convert the input to [ghi][def][jkl][jkl][mno] and test this regex against the whole vocabulary: the word hello will match.


Method of communication in Distributed Systems Why the method of communication used in DS is message passing and not shared memory ?

Because in a distributed system, nodes do not have access to shared memory that is shared between all nodes.  Shared memory is only typically feasible when the nodes are on a common memory bus, e.g., for multiple core within a parallel processing machine.


What is a disequality path in the context of equality graphs? A path consisting of a number of disequality edges and a single equality edge

A path consisting of equality edges

A path consisting of a number of equality edges and a single disequality edge

A path consisting of disequality edges

The answer is number three, right? Who has any reasonable doubts or general short references?

Suppose we have a bunch of variables $v_i$ and a bunch of equations $v_i = v_j$ and disequalities $v_i \neq v_j$. We can describe out knowledge as a graph whose vertices are the variables and whose edges are the equations (equality edges) and disequalities (disequality edges).
An equality path is a proof that $v_i = v_j$. Such a proof consists of a path from $v_i$ to $v_j$ using only equality edges. A disequality path is a proof that $v_i \neq v_j$. Such a proof consists of a path from $v_i$ to $v_j$ in which exactly one edge is a disequality edge.
When the domain of the variables is larger than 2, then equality paths are the only way to deduce equality from the givens, and disequality paths are the only way to deduce disequality from the givens. This is a nice exercise. In the binary case, however, a path with an even number of disequality edges is a proof of equality, and a path with an odd number of disequality edges is a proof of disequality.


Undecidable languages I'm confused on the definition of undecidable languages.

Definition: For an undecidable language, there is no Turing Machine which accepts the language and makes a decision for every input string w.

Can you say a language that isn't recognizable as undecidable?

If given a language like

$L = \{\langle M \rangle \mid M$ is a turing machine with more than 50 states i.e. $|Q| > 50 \}$

I have to give an undecidable language T such that $T \subseteq L$.

A language that is a subset I think would be

$L_2 = \{\langle M \rangle \mid M$ is a turing machine with more than 60 states i.e. $|Q| > 60 \}$
because if $\langle M \rangle \in L_2$, then $\langle M \rangle \in L$. Hence, $L_2 \subseteq L$

But I'm confused on the undecidable part. How do I justify if this language is undecidable or if it even is?

Here is a more general statement:

  A language $L$ has an undecidable subset iff $L$ is infinite.

For the proof, note first that if $L$ is finite then all its subsets are finite and so decidable. Conversely, if $L$ is infinite then it has uncountably many subsets. Since there are only countably many decidable languages, some subset of $L$ (indeed, most subsets of $L$) must be undecidable.


Is there a dual concept to "Turing Complete" in logic? Two computing models can be shown to be co complete if each can encode a universal simulator for the other.  Two logics can be shown to be co complete if an encoding of the rules of inferences (and maybe axioms if present) of each be shown to be theorems of the other.  In computability this has led to a natural idea of Turing completeness and the Church Turing Thesis.  However, I have not seen where the logical co completenesses has led to any naturally induced idea of total completeness of similar quality.

Since Provability and Computability are so closely related, so I think it isn't too much to consider that there could be a concept in logic that is a natural dual to Turing Completeness.  Speculatively, something like: there is a "true" theorem that isn't provable in a logic if and only if there is a computable function that isn't describable by a computing model.  My question is, has anyone studied this?  A reference or some keywords would be helpful.

By "true" and "computable" in the previous paragraph I'm referring to the intuitive but ultimately undefinable ideas.  For example, someone could show that the finiteness of Goodstein sequences is "true" but not provable in Peano arithmetic without fully defining the concept of "true".  Similarly, by diagonalization it can be shown that there are computable functions that are not primitive recursive without actually fully defining the concept of computable.  I was wondering, even though they tend to ultimately be empirical concepts, perhaps the concepts could be related to each other well enough to relate the concepts of completeness.

I'm not sure why you say "true" is ultimately undefinable, as there is a precise definition for what it means for a first order formula to be true.

What's unique in the case of computability, is that for any definition (as wild as your dreams) for a "computational model", you can finally associate it with a set of functions (the functions it can compute). Thus, you can naturally compare different models, and upon fixing one (based on some empirical justification such as "it is a good representation of computation in the real world") you can call any other model complete if it computes exactly the same set of functions.

However, how do you compare different logics? It seems there is no natural property you can attach to an arbitrary logic, and use it to compare it to other systems. You can perhaps, fix the logic, e.g. first order predicate logic, and ask about completeness of an axiomatic system. Suppose you work in ZFC, and believe it consists of the natural axioms that represent the world. Now, when given a different axiomatic system, you can ask whether they have the same theory, and call this system complete in the case the answer is yes. I think the difference from the computability case, is that for computability, there is a stronger consensus on what the "base model" should be. The reason for this consensus is that many independent models of computation were later shown to be equivalent, so this seems like a very strong empirical evidence for what our "base model" should be.


Should one limit the maximum level of a skip list node? In Skip Lists: A Probabilistic Alternative to Balanced Trees by Pugh he suggests different strategies for choosing the level of an inserted node. One such strategy, called fix the dice, limits the level to our previous highest level plus one if a higher level was randomly chosen.
What are the practical implications of choosing this strategy, especially for large skip lists and those with p < 1/2?
I imagine it could lead to a higher than usual fanout, but without all too dramatic effects, especially if deletions are as common as insertions after some growth (since that would minimize the effect of lower than usual levels after that initial growth).
Any educated speculation or hints to already existing analyses are welcome.

Contrary to what Pugh says in that paper, I don't believe the "fix the dice" strategy has any impact on the stochastic analysis of skip list performance.

The strategy demotes (reduces the level) of a newly-created item to one more than the current maximum level in the skip list, if the random level assignment would have produced a higher level. Let's call such an item a demoted item.

Observe that the skip list cannot contain two demoted items at the same level. One of them would have to have been created first, and that would prevent the other one from having been demoted to that level. (Items are never demoted after they are created, so even if deletions entirely empty some level, higher-level items continue to have the same level. One could imagine a strategy which also demoted existing items in such a case, but even then it would be impossible to have two demoted items at the same level.)

The level of an item is limited to $MaxLevel$ (using Pugh's terminology), which means that there are at most $MaxLevel$ demoted items in the skip list. Pugh suggests choosing $MaxLevel$ as $log_{p^{-1}}N$ where $N$ is the expected maximum number of elements in the skip list. In practice, we might use a fixed constant, or we might use $log_{p^{-1}}M$ where $M$ is the maximum size that the skip list has ever reached (assuming we use an implementation where $MaxLevel$ can be incremented). In any case, we expect that $MaxLevel$ is $O(\log n)$.

Now, let's say that $\mathscr{E}(l)$ is the expected number of items at level $l$ without die-fixing and $\mathscr{E}'(l)$ is the expected number in the die-fixed skip list. Die-fixing could cause at most $l-1$ items at level $l$ to be demoted to another level (because there are only $l-1$ lower levels, each of which can have at most one demoted item) and it could cause at most $1$ item at a higher level to be demoted to $l$. So:

$$\mathscr{E}'(l) \in [\mathscr{E}(l)-l-1, \mathscr{E}(l)+1]$$

Since $\mathscr{E}(l) = n\mathscr{P}(l)$, where $\mathscr{P}(l)$ is the probability for a random item to be at level l (analogue $\mathscr{P}'(l)$ for the die-fixed list), we can estimate

$$\mathscr{P}'(l) \in [\mathscr{P}(l)-{{l-1} \over n}, \mathscr{P}(l)+{1\over n}]$$

But as noted above, the maximum value of $l$ is $O(\log n)$, so both ends of that range are asymptotically $\mathscr{P}(l)$.

In other words, the "fix the dice" strategy does not significantly change the probability that a random node is at a given level. Therefore, it does not "totally destroy" (or even affect) our ability to analyse the algorithms, and there is no reason why even a purist should avoid it.


Closest k points - performance on large lists Very similar to this

Problem formulation: Given a list $L$
of n points with GPS coordinates and a second list $Q$ of $m$ points, find the $k$ (let's say 3) closest points on $L$ for each element on $Q$.

Aditional constrains: Assuming that both $L$ and $Q$ are very large, and performance is an issue. We can also assume that $Q$ is much larger thant $L$. Preprocessing can be performed, but has to be robust to updates on lists $L$ and $Q$ (ergo, it can't be be very performance heavy).

Problem extensions: If we can't have preprocessing, because the updates on $L$ and $Q$ are very common, what would be the solution?

If you can also point me out to implemented solutions on R or Python it would be great!

I think what you are trying to do is a kind of SPATIAL JOIN. A similar question has been answered here, albeit with a fixed size radius for returned points instead of asking for $k$ closest points.

I would suggest using a spatial index $L$. Then you can perform $k$-nearest neighbor queries on the index for each point. The complexity would be about or $O(|Q| * k * log |L|)$.
I did some performance test of different spatial indexes here (Figure 28) with 2D and 3D datasets, you should be able to get around 100,000 $k$-nearest neighbor searches per second (on an index with 10,000,000 points). Some of these spatial indexes have updates rates of up to 1,000,000 updates per second, see Figure 40 in the same document. Especially quadtrees and the PH-Tree have high updates rates.

Not sure that it matters, but the PH-Tree uses internally z-curves (Morten order), which means that the ordering of elements uses z-order and is independent of insertion/deletion order. However, also note that the PH-Tree does not support duplicates, there can be only one point at any given coordinate.


Can abstract syntax trees be unparsed in subexponential time? Abstract problem description

The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. parse(unparse(AST)) = AST should hold.

This is the equal to finding a valid parse tree which would produce the same AST.

The language is described by a context free S-attributed grammar using a eBNF variant.

So the unparser has to find a valid 'path' through the traversed nodes in which all grammar constraints hold. This bascially means to find a valid allocation of AST nodes to grammar production rules. This is a constraint satisfaction problem (CSP) in general and could be solved, like parsing, by backtracking in $O(e^n)$.

Fortunately for parsing, this can be done in $O(n^3)$ using GLR (or better restricting the grammar). Because the AST structure is so close to the grammar production rule structure, I was really surprised seeing an implementation where the runtime is worse than parsing: XText uses ANTLR for parsing and backtracking for unparsing.

Questions

Is a context free S-attribute grammar everything a parser and unparser need to share or are there further constraints, e.g. on the parsing technique / parser implementation?
I've got the feeling this problem isn't $O(e^n)$ in general -- could some genius help me with this?

I didn't receive an answer for this question on StackOverflow. It was suggested to ask here, but I hate redundancy, so I hope you forgive me for asking you to answer here.

There is a version of your question for which unparsing is easy and can be done in linear time. However, I'm not entirely sure if your question pertains to this specific version of unparsing, so I'll look at that first.

You say in your question over at StackOverflow that your AST looks like "AnyObject -> AnyObject -> Vehicle [name="Car"]". Your question would be a lot easier if your AST looks like "Area -> Highway -> Car", that is, that we know which productions were taken when your AST was constructed/parsed. In ordinary context-free parsers, you (almost) always get this information: you might decide to throw it away, but (nearly) all parsing algorithms can also give you this information.

If you don't have this information, I'm pretty sure exponential time is the best you can do, unless you know something about your S-expressions. The problem then is simply recovering the "Area -> Highway -> Car" AST, the unparsing after that is the easy part.

If you do have this information, then we can just look at context-free grammars and try to unparse them. Consider this grammar:

  1: $S \to a$
  2: $S \to a S a$

An AST for this grammar may look like $S \to a (S \to a) a$, on input "aaa". Unparsing this AST is easy: perform a postorder walk of the tree and output all terminals found in this walk. The result is "aaa" again.

Things become a bit more complicated when you look at ambiguous context-free grammars. On one hand, things are still easy: you just pick any parse tree of your input and do the above: you can reconstruct all other parse trees from the result.

However, in the presence of disambiguation rules, you have to do something clever. In particular, the input "(1+2)*3" may be unparsed as "1+2*3", which is different from the original. It is possible to do this in linear time on $LR(1)$ grammars (where precedence and associativity are enforced like in Yacc) by doing a reverse $LR$ parse at unparse time. I'll skip the details, as this was not part of your question, but it can be done.


Selecting optimal order of questions to minimize total time Suppose there is a tutorial session at a university.
We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$
students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a certain subset of questions, i.e. for each student $s_j$, let $Q_j \subseteq Q$ be
the set of questions that a student has a doubt it. Assume that
$\forall 1 \leq j \leq n: Q_j \neq \phi$ and
$\bigcup_{1\leq j\leq n}Q_j = Q$.

Now, a student leaves the tutorial session as soon as all the questions in which he has a doubt in have been discussed. Suppose that the time
taken to discuss each question is equal, say 1 unit$^*$. Let $t_j$ be the
time spent by $s_j$ in the tutorial session. We want to find out an
optimal permutation $\sigma$ in which questions are discussed
$(q_{\sigma(1)} \ldots q_{\sigma(n)})$ such the the quantity $\Sigma_{1\leq j \leq n}t_j$ is minimized.

Intuitively it seems that we can greedily discuss the question that the
most number of students (in the current iteration) have a doubt in.  Is the greedy algorithm correct?

Sidenote: By the way, I thought of this question after an actual tutorial
session, in which the TA discussed the questions in the normal order $q_1 \ldots q_n$ because of which many students had to wait until the end.

Example
Let $k=3$ and $n=2$. $Q_1 = \{q_3\}$ and $Q_2 = \{q_1, q_2, q_3\}$. We can see that an optimal $\sigma = \langle 3, 1, 2 \rangle$ because in that case, $s_1$ leaves after $t_1 = 1$ and $s_2$ leaves after $t_2 = 3$, so sum is 4.
However, if we discuss the questions in the order $\langle 1, 2, 3\rangle$, then $s_1$ and $s_2$ both have to wait till the end and $t_1 = t_2 = 3$, so sum is 6.

$^*$You are free to solve the more general case where each question $q_i$ takes $x_i$ units to discuss!

Counterexample: Students are $x_1\dots x_n$ and $y_1\dots y_m$ and questions are $Q_0, \dots Q_m$. Students $x_i$ only want $Q_0$ to be answered while the $y_i$ students want question $Q_1,\dots, Q_m$ to be answered.

Let's say you place $Q_0$ as the $k^{th}$ question. Then the total time waited by students is:

$L(n,m)=n(m+1)+m^2$ if $Q_0$ is last
$nk + m(m+1)$ if $Q_0$ is $k^{th}$

Clearly, if you want to not put $Q_0$ last, then you might as well put it first so that the cost is $F(n,m)=n + m(m+1)$.

Now $L(n,m)-F(n,m)=nm+n+mm-n-mm-m=nm-m=(n-1)m$ so that whenever $n>1$ and $m>0$, we'll have $L(n,m)>F(n,m)$. So placing it first is better.

But your greedy algorithm would put it last if we take $m>n$.


Why not polynomial-space reductions for $PSPACE$-hardness? A language $L'$ is $PSPACE$-hard if for every $L \in PSPACE$ we have $L \le_p L'$.

Here $L \le_p L'$ means that $L$ is polynomial-time reducible to $L'$.

Why does we use time reductions instead of space reductions in this situation?

It's never interesting to use reductions that are as powerful as the complexity class you're talking about.  With the exception of $\emptyset$ and $\Sigma^*$, every problem in $\mathbf{PSPACE}$ is $\mathbf{PSPACE}$-complete under poly-space reductions.

To see this, let $X\in \mathbf{PSPACE}\setminus\{\emptyset,\Sigma^*\}$, and choose any fixed pair of strings strings $y\in X$ and $n\notin X$. Now, for any language $L\in\mathbf{PSPACE}$, we can reduce $L$ to $X$ using the function
$$f(w)=\begin{cases}\ y&\text{if }w\in L\\
                    \ n&\text{if }w\notin L.\end{cases}$$
Since $L\in\mathbf{PSPACE}$, we can compute $f$ in polynomial space.

This argument applies for any reasonable complexity class and it's the reason why, for example, we don't talk about problems being $\mathbf{P}$-complete under poly-time reductions: instead, we use something like log-space reductions, there.

In general, hardness or completeness results are "more impressive" using weaker reductions, since the reduction is able to do less of the work. In the case of $\mathbf{PSPACE}$-completeness under poly-space reductions, the reduction is actually doing all the work.


Is there a difference between type safety and type soundness? I've been trying to tease apart the definitions of type safety and type soundness and I'm having a heck of a time of it. I asked a professor recently and after a bit of thought he said that there really wasn't any difference. However after reading this
it seems like:

Type Safety is a property of the language that says that the application of functions (and operators) to data is meaningful (i.e. 1 / "Hello" is nonsense and is disallowed)
Type Soundness is a property of a type checking system that guarantees that its static type predictions are accurate at run time.

This is clearly just a single persons notes and I'm wondering if there is some standard within the PL community. I've done some searching and I haven't found a satisfying answer.

Type safety and type soundness are synonyms in most theoretical work. Type soundness is often formulated with respect to an operational semantics as (type) preservation and progress. Preservation states that if an expression has some type, then after a step of evaluation (via the operational semantics), the resulting expression can be given the same type. Progress states that if an expression is not a value, i.e. it is not fully evaluated, and it is well-typed, then it can be further evaluated.

"Type safety" and "soundness", but particularly "type safety", are also widely used by the (non-theoretical) programming community often in vague, ambiguous, or outright incorrect ways. For example, an API that uses enumeration types instead of allowing arbitrary strings when only a subset are meaningful, say, might be referred to as being "more type safe", but this statement doesn't make sense using the theoretical definition of "type safe" which is a binary property of the language as a whole.


Finding the language of a context-free grammar? Given following question:

Let $G$ be a context-free grammar, $G=(V, \Sigma, R, S)$, that has start
variable $S$, set of variables $V = \{S\}$, set of terminals $\Sigma = \{0, 1\}$, and set of rules $R = \{S \rightarrow \epsilon , S \rightarrow 0 , S \rightarrow 1 , S → 0S0 , S \rightarrow 1S1\}$. Describe $L(G)$,
the language of the grammar $G$.

I know that $\epsilon, 0, 1, 00, 11, 010, 101, 01010, 10101, 10001, 01110$ all fit the grammar, but I can't find a formal way to express what I want to say. Perhaps I don't know the symbols or something, but I would express it as

$L(G) = \{(0\ or\ 1)^n(0\ or\ 1)^{(0\ or\ 1)}(0\ or\ 1)^n,\ n \ge 0\}$

Is this right? Is there a more formal way to express this?

Your grammar generates the language of all palindromes. It can be described in the following ways:

$L(G)$ is the language of all palindromes over $\{0,1\}$.
$L(G) = \{ x \in \{0,1\}^* : x \text{ is a palindrome} \}$.
$L(G) = \{ x \in \{0,1\}^* : x^R = x \}$.

The first option is really the best, but unfortunately your TAs are expecting the third option.


Language that fulfills pumping lemma but is not in RE I am supposed to find a language $$L\subseteq \Sigma ^*, \Sigma \subseteq \mathbb{N}$$ that fullfills the pumping lemma and is not in RE and not in coRE. I've never constructed a language with a given constraint, I've only shown that a certain language satisfies a given one. Not wanting to waste a bunch of time guessing some languages and prooving that they meet my criteria, I am looking for a hint on how to start.

Usual pumping lemma

Here is an answer when we are talking about the usual pumping lemma for regular languages that is taught in most introductory courses of computation theory.

Let alphabet $\Sigma=\{0,1\}$.
Let $L$ be a non-recursively enumerable language over $\Sigma$. For example, $L$ can be the complement language of a semi-decidable but not decidable language such as $\overline{\{ \langle M \rangle \mid \text{ $M$ halt on empty input}\}}.$

Let $L'=\{00w\mid w\in L\}\cup\{01w\mid w\not\in L\} $. Then both $L'$ and $\overline {L'}$ are non-recursively enumerable languages.

Let $F=\{ 1w \mid w\in L' \} \cup \{ 1^kw \mid k\neq 1, w\in \Sigma^* \}$, following the construction in an answer by Hendrik Jan. Then $F$ is not in RE and not in coRE since its first part is not in RE and not in coRE while its second part is regular. It satisfies the usual pumping lemma for regular languages, since its second part is regular while its first part can be pumped down and up "into" its second part by choosing the first 1 to pump.

General pumping lemma

Here is an answer when we are talking about the general (or generalized) pumping lemma for regular languages.

Let alphabet $\Sigma_4=\{0,1,2,3\}$. Let $D$ be the finite language whose words are of length 3 and having a duplicate character. (In fact, $D$ has $4+4\times3\times3=40$ words.) Let $P=\Sigma_4^*\bullet D\bullet\Sigma_4^*$, the languages of all words that contain a substring in $D$. $P$ is a regular language. Any language over $\Sigma_4$ that contains $P$ satisfies the general pumping lemma.

Let $N$ be a language that is not in RE and not in coRE. For example, we can select language $L'$ constructed in previous section. Then $G=P\cup N$ is a language not in RE and not in coRE that satisfies the general pumping lemma.

Here are several exercises that readers can do so as to fill the gaps in the above sections.

Exercise 1. Show the class of non-recursively enumerable languages is closed under concatenation with a fixed string at the front.

Exercise 2. Show the class of non-recursively enumerable languages is closed under union with a regular language.

Exercise 3. Show any language over $\Sigma_4$ that contains $P$ satisfies the general pumping lemma.


Why do we need "Bloom Filters" if we can use hash tables? A Bloom filter is a probabilistic data structure designed to tell, rapidly and memory-efficiently, whether an element is in the set or no.

If we can use hash tables where we have O(1) in best time, O(n) in a very bad situations. Why do we need a new abstract data structure that look-up for an element with less certainty.
What are the scenarios where HashTables fails and demands the use of bloom filters?

When should bloom filters be used over hashtables and vice-versa?

The second paragraph of the Wikipedia article on Bloom filters says the following, with a citation to Bloom's original 1970 paper.

  Bloom proposed the technique for applications where the amount of source data would require an impracticably large hash area in memory if "conventional" error-free hashing techniques were applied. He gave the example of a hyphenation algorithm for a dictionary of 500,000 words, out of which 90% follow simple hyphenation rules, but the remaining 10% require expensive disk accesses to retrieve specific hyphenation patterns. With sufficient core memory, an error-free hash could be used to eliminate all unnecessary disk accesses; on the other hand, with limited core memory, Bloom's technique uses a smaller hash area but still eliminates most unnecessary accesses. For example, a hash area only 15% of the size needed by an ideal error-free hash still eliminates 85% of the disk accesses.

Burton H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM 13(7): 422–426, 1970. (DOI)


which Pipelining architecture, should i use and how to distinguish them! Is there any specific architecture to pipelining that we must follow to perform "operand-forwarding" inorder to avoid its harzards?

My tutor seem to have, there are different architecture. And he taught us 3 different, and i am not even sure how to know which one to use.

In computer architecture, there is absolutely nothing that you must do. There are always compromises, everything has advantages and disadvantages, and advantages and disadvantages change over time.

If you learned about three different architectures to achieve the same goal, you first check how each architecture fits in with the overall design, and then you invent a fourth one that works better. Your tutor can only tell you how things were done in the past; you'll have to find yourself how things will be done in the future.


Probability that a random hash from a universal family is injective This is a homework question, I don't want an actual answer, but rather guidance on how to obtain the correct answer. The question is as follows:

In class we saw universal hashing as the solution to processing N elements in the range {0,1,...u-1}, arriving
one at a time. Using universal hashing we can get O(1) processing time for each request, but in expectation. Hence
sometimes we might get unlucky and processing time might be longer. Consider another scenario where we are given
the N requests in advance. Can we process them together and store in a hash table so that any future lookup request for
any of these items can be processed in worst case O(1) time (so no uncertainty or expectation here)? In this problem
you will design a solution for this, again using universal hashing.

You are given a set S of N items in the range {0,1,...u-1) in advance. Consider the following algorithm
that stores these items into a table of size N*N.

SquareHash(S, u)
Input: A set S of N items, an integer u such that
each item is in {0,1, ... , u-1}
Output: A hash table of size N*N and a corresponding hash function
1. Initialize a table T of size N*N
2. While true
        3. Pick a function h uniformly at random from a universal family H
        that maps {0,1, ... , u-1} to {0,1, ... , N*N-1}
        // Assume that this can be done in O(1) time
        4. Insert all the elements of S into T using h as the hash function
        5. If T has no collisions, return (T,h). Otherwise empty T

Clearly if the above algorithm terminates then it will produce a table with no collisions and hence any future
lookup will be in O(1) time guaranteed. However in the worst case the algorithm might run forever. Show that
this is unlikely. In particular, compute the expected running time of the algorithm above.
[Hint: Each time a function h is picked, compute the probability (or a lower bound on it) that the resulting table
will have no collisions. Then use the fact that if a coin of bias p is flipped until it turns up Heads, the expected
number of flips is 1/p]

I understand intuitively this is unlikely to run forever. If a hash function causes a collision, it will pick another one until it finds one that does not cause any collisions. However, I am unsure of how exactly to prove this formally and how to compute the expected running time. I know that the probability of two elements colliding is 1/m, where m is the expected range of outputs.

By definition, a family of hash functions $H$ with range of size $m$ is universal if for all $x \neq y$ in the domain of $H$,
$$
\Pr_{h \sim H} [h(x) = h(y)] \leq \frac{1}{m}.
$$
In your case, $m = N^2$. Let the $N$ elements in $S$ be $x_1,\ldots,x_N$. Using the union bound,
$$
\Pr_{h \sim H} [h(x_1),\ldots,h(x_N) \text{ not all distinct}] \leq
\sum_{1 \leq i < j \leq N} \Pr_{h \sim H}[h(x_i) = h(x_j)] \leq \frac{\binom{N}{2}}{N^2} \leq \frac{1}{2}.
$$
In other words, a random $h$ is successful with probability at least $1/2$. Therefore the expected number of times until a successful $h$ is chosen is at most $2$.


can't quit understand one step of the recurrence time complexity calculation I solved the question T(n) = T(sqrt(n)) + 1 but can't quit understand one step of the solution
I don't understand the transition in (1).
how did we conclude that T(m) = T(m/2) + 1 from the previous step that m is in the power?

It obviously is not correct. To fix it, define $S(m)=T(2^m)$, and then we would have $S(m)=S(m/2)+1$. Now, continue with the proof replacing everywhere $T(m)$ with $S(m)$. After you solve what $S(m)$ is, substitute $m=\log(n)$ in the solution to get what $T(n)=T(2^m)=S(m)$ is.


How to show that there are $\binom{M+K}{M}$ different number of type bins? In textbook by Vazirani's textbook, chapter 9 about Bin Packing. He give the following lemma.

  Lemma 9.4 Let $\epsilon >1$ be fixed, and let K be a fixed nonnegative integer. Consider the restriction of the bin packing problem to instances in which each item is of size at least $\epsilon$ and the number of distinct item sizes is K. There is a polynomial time algorithm that optimally solves this restricted problem.

Proof. The number of items in a bin is bounded by $1/\epsilon$. Denote this by M. Therefore, the number of different bin types is bounded by $R = \binom{M+K}{M}$. Which is a large constant. Clearly, the total number of bins used is at most n. Therefore, the number of possible feasible packings is bouned by $P=\binom{n+R}{R}$, which is polynomial in n. Enumerating them and picking the best packing gives the optimal answer.

Question: We know a fact which is: $\binom{n+k-1}{n}$, now in order to find the number of different bin types we it should be something like $\binom{M+K-1}{M}$ why in the proof it is different?!!

The bins contain at most $M$ elements rather than exactly $M$ elements. This is why your formula doesn't work. In order to use your formula, we need to allow for one more type of element, a dummy type, and then we get $\binom{M+(K+1)-1}{M} = \binom{M+K}{M}$.

As an example, suppose that there is one type of element (so $K=1$). In that case, a bin can contain $0,\ldots,M$ elements, in total $M+1 = \binom{M+K}{M}$ choices.


Efficient algorithms for dealing with linear algebra over the rationals I'm an academic mathematician.  While trying to verify a counterexample to something in my research, the following computational problem has arisen:

Fix a vector space $V = \mathbb{Q}^n$.  Here $n$ is something on the order of $20,000$.  I have a procedure that spits out a sequence of vectors $\vec{v}_1,\vec{v}_2,\ldots$ in $V$.  The vectors $\vec{v}_i$ all have integer entries; these entries are bounded in size (by something on the order of 20 or 30).  For each $k \geq 2$, I need to decide if $\vec{v}_k$ is in the $\mathbb{Q}$-span of the set $\{\vec{v}_1,\ldots,\vec{v}_{k-1}\}$.

What algorithm should I use for this?  The naive thing to do would be to just use Gauss-Jordan elimination (or, if I want to mostly stick with integers, compute the Hermite normal form).  However, experiments I have done show that the size of the numbers that arise when you do this explode in complexity even for much smaller problems.  This accords with stuff I have found while searching the literature, though I don't know the computer science literature very well and have trouble determining the state of the art in stuff like this.

One trick I've seen elsewhere is to pick a random prime $p$, reduce everything modulo $p$, and check whether the vectors are linearly independent over $(\mathbb{Z}/p\mathbb{Z})^n$.  If $p$ is not a divisor of any of the entries of the vectors, and if $v_k$ is not in the $(\mathbb{Z}/p\mathbb{Z})^n$-span of $v_1,\dots,v_{k-1}$, then $v_k$ isn't in the $\mathbb{Q}$-span of $v_1,\dots,v_{k-1}$, either.  By picking $p$ to be large enough (larger than the largest of the vector-entries), you can be sure $p$ won't be a divisor of any of the entries.

So, this provides a pre-test you can use.  You run the pre-test first (working modulo $p$), and if it outputs "linearly independent", then you don't need to run the expensive $\mathbb{Q}$-span test; on the other hand, if it outputs "linearly dependent", then you do need to do the expensive $\mathbb{Q}$-span test (e.g., Gaussian elimination).

And, I think there's a heuristic argument that if $p$ is random and large enough, then if it's $\mathbb{Q}$-independence then with high probability (over the choice of $p$) it'll be $(\mathbb{Z}/p\mathbb{Z})^n$-independent, too.  Or something like that.  But it's just a heuristic and no guarantee that it'll work for all situations.

I hope I have this right.  I'm going from memory so I might have something backwards.  Check my logic, and try it on your situation, and see if it helps in your application or not.


Efficient N-Ary GCD Algorithm Are any algorithms known that can compute the greatest common denominator of multiple (more than two) input values more efficiently than just an iterative application of the fastest GCD algorithm for exactly two input values?  E.g. gcd(a, b, c, ...) vs. gcd(a, gcd(b, gcd(c, ...)))

If so, then what is such an algorithm?

If not, then is it known whether there cannot exist such an algorithm?

As Wikipedia reports, the fastest currently known algorithm for the gcd of two $n$-bit numbers runs in $O(n f(n))$ time where $f(n)$ is a slow-growing function of $n$ (roughly $\log n \cdot \log \log n$).  It is not known whether the gcd of two $n$-bit numbers can be computed in $O(n)$ time.

This means that the iterative algorithm for computing the gcd of $k$ $n$-bit numbers (as described in the question) runs in $O(kn f(n))$ time.  Obviously, any algorithm needs at least $\Omega(kn)$ time -- this lower bound follows from the fact that any algorithm needs to read the entire input.  This doesn't leave much of a gap between the trivial lower bound and the running time of the iterative algorithm.  In other words, it doesn't leave much room for improvement in running time.

That's the theoretical answer.  From a pragmatic perspective, the $O(n f(n))$-time algorithms only become faster than (asymptotically slower) alternatives once $n$ is fairly large.  As a result, if $n$ is not too large, these results might not mean much.

Also, from a pragmatic perspective, we can expect that $\gcd(a,\gcd(b,\gcd(c,d)))$ might be faster than $\gcd(\gcd(a,b),\gcd(c,d))$.  They both yield the same answer, but the former might often be faster, because typically one of the two arguments to the gcd will be small.  Computing $\gcd(x,y)$ might be faster in practice if $y$ is much smaller than $x$ (because the first step is to replace $y$ with $y \bmod x$) than when $x,y$ are about the same size.  So, you might benefit by performing the gcd's in an order that gets you down to a small number as soon as possible.


Array of overlaping ranges Consider that I have an array of ranges and I want to transform it to the new array that represents the ranges that any range is in.

Example:

Ranges:
[red: [1,11], black: [15,16],yellow: [5,9], green: [7,8]]

Result:

[1,4] - red
[5,7] - red & yellow
[7,8] - red & yellow & green
[8,9] - red & yellow
[10,11] - red
[15,16] - black

My first thought was to use interval tree but the most implementations I found  want to ask tree by range and I want to explicitly list groups as shown in example.

Sort all coordinates of intervals (annotated with their significance), and scan them in order.

As an example, in your case you would get
$$
1^{+red},5^{+yellow},7^{+green},8^{-green},9^{-yellow},11^{-red},15^{+black},16^{-black}
$$
This immediately gives the decomposition into intervals $$(1,5),(5,7),(7,8),(8,9),(9,11),(11,15),(15,16)$$
with associated colors.

Note that this list differs from your output, since you sometimes move the endpoint back by 1 point for some unspecified reason.


Predicate Logic Paradox Possible Duplicate:
  Negation of nested quantifiers

The problem is:

∃x∀y(x ≥ y)

With a domain of all real positive integers.

The negation is:

∀x∃y(x < y)

so, if y = x + 1

the negation is true.

That means the negation of the negation (or, the original problem) is false.

My question is, that if the original problem is ∃x∀y(x ≥ y), why can't x = y and prove the problem true?

Your base predicate states that there exists some real number that's larger than or equal to all other real numbers (i.e that there is a highest real number).

The inverse states that every real number has a number larger than it (i.e. that there is no highest real number).

Your test cases don't produce a paradox because feeding x=y into the first predicate means that you're no longer working with R+. If all you have in your test set is a single number, then of course there's a maximum value. All you show with this test is that:

In a set containing a single real number, there exists a highest value

All that having been said, I'm sure you'll get a better answer on math.stackexchange.com!


What is the minimum pumping length of the union of two languages? If I have two languages L1 and L2 that are pumpable, what is the minimum pumping length for the union of them?
Does it differ if either of them contains just one string like 001?

Consider the following two languages:
$$
L_0 = 1(0+1)^* + 0^{n_0}, \\
L_1 = 0(0+1)^* + 1^{n_1}.
$$
The minimum pumping length of $L_0$ is $n_0 + 1$, and that of $L_1$ is $n_1 + 1$. Yet $L_0 \cup L_1 = (0+1)^+$ has a minimum pumping length of 1.

What does hold is that the pumping length of $L_0 \cup L_1$ is at most the maximum of the pumping lengths of $L_0,L_1$. In fact, it can be any number between 1 and that maximum. Indeed, suppose that $1 \leq a,b \leq c$, and consider the languages
$$
\begin{align*}
L_0 &= 1(0+1)^* + 0^{a-1}, \\
L_1 &= 0(0+1)^* + 1^{c-1} + 2^{b-1}.
\end{align*}
$$
The maximum pumping length of $L_0$ is $a$, that of $L_1$ is $c$, and that of $L_0 \cup L_1 = (0+1)^+ + 2^{b-1}$ is $b$.


If a non-deterministic Turing machine runs in f(n) space, then why does it run in 2^O(f(n)) time? Assuming that f(n) >= n.

If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, but in Turing machines a tape cell could hold any number of symbols. I'm having trouble why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape.

why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape?

Because it does not matter in the sense that $2^{O(f(n))} = b^{O(f(n))}$ for any positive $b > 1$.

Using the popular set-theoretic understanding of the big $O$-notation, we have
$$\begin{align}
2^{O(f(n))}&=\{2^{g(n)}\mid g(n)\in O(f(n))\} \\
&=\{\left(b^{\log_b2}\right)^{g(n)}\mid g(n)\in O(f(n))\} \\
&=\{b^{h(n)}\mid \exists g(n),\ h(n)= (\log_b2)g(n),\ g(n)\in O(f(n))\} \\
&=\{b^{h(n)}\mid h(n)\in O(f(n))\} \\
&=b^{O(f(n))}\end{align}$$

By the way, there is no need to assume $f(n)\ge n$. For example, all above hold when $f(n) = \lceil\sqrt n\rceil$ or $f(n) = \lceil\log_2n\rceil$.


Find similar vector by Locality Sensitive Hashing I have many vectors in my database. They are in high dimensions such as:

$v_1$ : $\langle 23, 23, 1, 33, 103, 219, \dots \rangle$
$v_2$ : $\langle 92, 83, 1, 33, 239, 192, \dots \rangle$
...

I will use Hamming distance to calculate their difference: The
difference between $v_1$ and $v_2$ is $4$ because elements $3$
and $4$ are the same and others are difference.

Now, I want to use Locality Sensitive Hashing (LSH) to put those
vectors into different bins.

  What kind of hash function can I use for this case?

I have read some article about universal hash function, but I am
not sure can I use it and how to ensure that the probability for
the similar vectors going to the same bin is higher than those
non-similar one.

Here is the way that I think how should I use the universal hash
function for my task.

I will first divide those high dimensions vectors into sub-vectors:
$$x : 23, 23 \; | \; 1, 33 \;  | \; 103, 219 \; | \; \dots$$

sub1-x : 23 23
sub2-x : 1 33
sub3-x : 103 219

The following function will be used for each sub-vector:
$$sum_{i=0}^{r} a_{i}x_{i} \mod m$$

Basically this is a dot product, a = {a_1, a_2, ... a_i}, x =
{23, 23, 1, 33, 103, 219 ...}, m is a prime.

Different combination of {a} will form a different hash table, one hash table is used for one sub-vector.
I can now hash the data into bins, but the question is

  Is this an LSH method?  I don't know that two similar vectors  will go into the same bin with a high probability.

Yes.  This is one plausible method, if you want to find pairs of vectors that are very close to each other.  Two vectors that are close in Hamming distance are likely to end up in the same bin at some point.

Suppose two vectors $v,w$ agree in fraction $p$ of their coordinates (where $0\le p \le 1$).  Then, heuristically, if we look at a pair of coordinates, the probability that $v,w$ agree on those coordinates is $p^2$; and if we choose those two coordinates for hashing, then $v,w$ will end up in the same bin.  If you hash each vector $n$ times, choosing a random pair of coordinates each time, then with probability $1-(1-p^2)^n$, there will be at least one time when they show up in the same bin.

For instance, if two vectors agree on half of their coordinates, and if you hash them 10 times, then 94% of the time they will end up in the same bin for at least one of those 10 hashes.

To know how well it will work on your particular application, you may need to try it (or at least work out the parameters of how close vectors will be, when they are close; how many dimensions they have; how many times you will hash them; etc.).


Traveling salesman problem with disconnected cities / infinite length edge I am looking to solve a variant of the traveling salesman problem with a certain set of constraints:

the graph is not complete, i.e. some nodes are not connected to each other
the weight of an edge between any pair of connected nodes is always 1

What is the best way to model and solve this problem?

AFAIK the Concorde TSP solver, for example, requires real numbers for edge weights. And it seems like because all the edges have the same weight, there could be more than one valid solution.

You're just trying to find Hamiltonian cycles in unweighted graphs. That's still NP-complete.

If you want to do it with a TSP solver, do it as follows. Suppose you have a graph on $n$ vertices. These are your $n$ cities. If there's an edge between two vertices, set the distance between the corresponding cities to $1$. If there's no edge, set the distance to $2$. If a minimum-weight TSP solution has total weight $n$, it's a Hamiltonian cycle of the original graph; if it has weight $n+1$ or more, then every cycle that visits all cities must include at least one non-edge of the graph, so the graph has no Hamiltonian cycle.


Enumerating all ways of pairing odd nodes Can someone provide a brute force pseudocode for finding best connections between odd-degree nodes in the Chinese postman problem mentioned here?

For example, if the odd nodes are $B,C,D,E$, the program should output the three pairings

  BC,DE; BD,CE; BE,CD.

Your question doesn't have much to do with the route inspection problem. You are looking for all perfect matchings of $K_{2n}$ (the complete graph on $2n$ vertices), or equivalently, for an algorithm that enumerates all partitions of $\{1,\ldots,2n\}$ into pairs. A simple recursive approach is quite efficient:

Input: A non-empty list $L$ of even size.
Output: All possible partitions of $L$ into pairs.
Algorithm:

If $L = \{a,b\}$, return $(a,b)$.

Otherwise, let $a$ be an arbitrary element of $L$. Go over all elements $b \in L \setminus \{a\}$. For each $b$, generate (recursively) all perfect matchings of $L \setminus \{a,b\}$, and add $(a,b)$ to all of them.

The number of perfect matchings is quite large:
$$
(2n-1) (2n-3) \cdots (1) = \frac{(2n!)}{2^nn!} \sim \frac{\sqrt{4\pi n} (2n/e)^{2n}}{2^n\sqrt{2\pi n}(n/e)^n} = \sqrt{2} \cdot (2n/e)^n.
$$


Lower bound for maxima on 2D plane Given $n$ points $(x_1, y_1), \ldots, (x_n, y_n)$ on a 2-dimensional plane.
  A point $(x_1, y_1)$ dominates $(x_2, y_2)$ if $x_1 > x_2 \land y_1 > y_2$.
  A point is called a maxima if no other points dominate it.

I can come up with an $O(n \log n)$ algorithm to find all the maxima. However, I failed to solve:

  Problem: What is the lower bound for the "finding all 2D maxima" problem (say, on the comparison model)? And how to prove it?

When asking for a lower bound, you should let us know what computation model you're interested in. A good first model to prove lower bounds on is the comparison model. In this case, usually you use the fact that given $n$ values $x_1,\ldots,x_n$, determining whether all of them are unique takes $\Omega(n\log n)$ comparisons. This problem is known as element distinctness or element uniqueness.

In your case, the natural candidate reduction is to map $x_i$ to $(x_i,-x_i)$. Note that no pair dominates each other, but if $x_i = x_j$ then $(x_i,-x_i)$ "weakly dominates" $(x_j,-x_j)$. Therefore any algorithm outputting the number of "weak maxima" can be used to decide element uniqueness, and so requires $\Omega(n\log n)$ comparisons.

You are interested in maxima rather than weak maxima, so you need to tweak this idea a bit. Suppose that all $x_i$ were integers. Then you map $x_i$ to $p_i = (x_i+i/(2n),-x_i+i/(2n))$. Now $p_i$ dominates $p_j$ iff $x_i = x_j$ and $i > j$. So the number of maxima again allows you to decide element uniqueness.

While you can't really assume that the $x_i$ are integers in the comparison model, you can tweak the reduction even further to implement the same effect: you map $x_i$ to $p_i = ((x_i,i),(-x_i,i))$, and you compare pairs of the form $(x,i)$ according to the following rule: $(x,i) > (y,j)$ if $x > y$ or $x=y$ and $i > j$. Every algorithm for computing the number of maximas in the comparison model using $m$ comparisons can be converted to an algorithm for deciding element uniqueness using $O(m)$ comparisons, hence requires $\Omega(n\log n)$ comparisons.


Enumerating all the walks in a graph between a start vertex and a terminal vertex? I was reading something about the concept of walks in a graph b/w a start vertex and a terminating vertex in a graph and then suddenly a problem struck me, is there any algorithm or a method that can be used to enumerate all the distinct walks from a start vertex to a terminal vertex in a graph, if so can you all point me to some relevant links to study this problem and what are some applications of solving this problem?

If the input graph is undirected:

If the source vertex $s$ and target vertex $t$ are in different components of the graph, then there are no walks from $s$ to $t$.
If $s$ and $t$ are in the same component, and that component has only one vertex (so in particular, $s=t$), then there is exactly one walk from $s$ to $t$, namely the unique walk that starts at $s$ and has length $0$.
Otherwise, there are infinitely many walks from $s$ to $t$.

If the input graph is directed:

Let $S$ be the subset of vertices reachable from $s$, and let $T$ be the set of vertices from which $t$ is reachable.  Finally, let $H$ be the induced subgraph of the input graph $G$ with vertices $S\cap T$.  Every walk in $G$ from $s$ to $t$ is actually a walk in the subgraph $H$.

If $H$ is empty, there are no walks from $s$ to $t$.
If $H$ is a non-empty directed acyclic graph, then $s$ is the unique source, $t$ is the unique sink, and every walk from $s$ to $t$ is actually a simple path.  The number of paths in a dag from a source to a sink can be computed in $O(m)$ time by dynamic programming.  Remaining details are left as a homework exercise.
Otherwise, there are infinitely many walk from $s$ to $t$.


What's the difference between a binary search tree and a binary heap? These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?

Heap just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels, whereas BST guarantees order (from "left" to "right"). If you want sorted elements, go with BST.by Dante is not a geek

  Heap is better at findMin/findMax (O(1)), while BST is good at all finds (O(logN)). Insert is O(logN) for both structures. If you only care about findMin/findMax (e.g. priority-related), go with heap. If you want everything sorted, go with BST.

by xysun


Non consant size alphabet Sometimes I read that an algorithm works on constant size alphabet and it is clear for me but what means that an algorithm works with a non constant size alphabet? I would like to see an example.

The classical example is sorting. For any constant-size alphabet, you can sort a string of length $n$ in time $O(n)$. However, for unbounded alphabets, the best you can do (under the comparison model, as well as some of its generalizations) is $\Theta(n\log n)$.


Compression algorithm using key value mapping Would it be possible to do better than standard compression if you fed a bunch of zipped files through a machine learning algorithm that kept track of the most common bit sequences and produced a lookup map, with a heuristic for giving the longest / most commonly used sequences the shortest key values?
The compression algorithm would then go through a zip file and replace sequences from the map with their lookup key.  If the map was big enough (both compress / decompress parties would have access to it) could you reliably get a smaller file than the original?
Some doubts I have about this method:

Files your learning algorithm had never seen before wouldn't contain
many sequences that had been seen before
The keys would have to be smaller than the sequence of bits it
replaces in order to save space, maybe it quickly runs out of keys
smaller than common sequences
Zip files don't repeat bit sequences very often so we wouldn't be
able to find large pieces to replace

All of your doubts are correct.
What you're describing is called static-dictionary compression. It works well for short text strings (see smaz, for example, though I doubt that its fixed dictionary was obtained by machine learning).
It would probably not accomplish much when applied to zip files because deflate doesn't tend to produce common bit sequences that are long enough to be further compressed – because eliminating those sorts of sequences is essentially its job.
A weakness of deflate is that its maximum copy length is 258, which means that long repeating sequences of bytes will tend to produce repeating (offset,length) pairs in the output, which can be further compressed by another pass. But the encoding of the repeated (offset,length) pair varies from file to file (even the length part, because the bit pattern used to represent a length of 258 isn't fixed), so you would need a dynamic dictionary to benefit from this.


Diffie-Hellman and its disadvantage with large primes I was reading our university slide on the Diffie-Hellman where it is mentioned that one of the disadvantages of D-H is that For large prime, $p-1$ is an even number so, $\mathbb{Z}^*_p$ will have a subgroup of order 2

What does this statement mean?

Let $p$ be a prime number and denote by $\mathbb{Z}_p$ the ring of integers modulo $p$.
The set $\mathbb{Z}_p^*$ typically denotes the units of $\mathbb{Z}_p$.
This set is defined as $$\mathbb{Z}_p^* = \{n \in \mathbb{Z}_p : \exists m \in \mathbb{Z}_p, nm = 1\},$$ where arithmetic is done modulo $p$.
An important fact about $\mathbb{Z}_p$ is that it is a field.
This means that we can simplify the above to $\mathbb{Z}_p^* = \{1, 2, \ldots, p-1\}$.
This set forms a group under multiplication, and it is a standard fact that this is a cyclic group, i.e., it is isomorphic to $\mathbb{Z}_{p-1}$ where the group operation is addition.
In symbols, $(\mathbb{Z}_p^*,\times) \cong (\mathbb{Z}_{p-1},+)$.

Since $p-1$ is even, consider the two-element subset of $\mathbb{Z}_{p-1}$ given by $\left\{0,\frac{p-1}{2}\right\}$.
As $\frac{p-1}{2} + \frac{p-1}{2} = p-1 = 0$ in $\mathbb{Z}_{p-1}$, this set forms a subgroup of $\mathbb{Z}_{p-1}$.
The order of a subgroup is its cardinality as a set, so this is a subgroup of order two.

Via the isomorphism between $(\mathbb{Z}_{p-1},+)$ and $(\mathbb{Z}_p^*,\times)$, this corresponds to a subgroup of $\mathbb{Z}^*_p$ of order two.


UInt128 - Compute the product of two UInt128's that are each represented by two UInt64's? I have a struct like this:

struct UInt128 {
    UInt64 s1;
    UInt64 s2;
}

In this struct, s1 represents the highest 64-bits of my 128 bit integer, and s2 represents the lowest 64-bits of my 128 bit integer.

I'm attempting to implement a method that produces the product of two UInt128's.

My current thought process is that the solution is similar to FOIL, the technique used to expand brackets in algebra e.g. $(a+b)(c+d)$ where we give the result as $ac + ad + bc + ad$, but my issue comes from the fact that I don't understand how to break the result back into two UInt64's.

How can I compute the product of two UInt128's as defined by the struct above?

It depends what operations are available to you for 64 bit integers.

The product of two 64 bit integers is a 128 bit integer. Many programming languages don't provide such a product, for example in C you will likely have an operation that produces the 64 bit (x * y) modulo $2^{64}$, but not an operation that produces the 128 bit number x * y.

On the other hand, given two 64 bit numbers x, y, many processors have instructions that produce 64 bit integers a and b such that mathematically x * y = a * $2^{64}$ + b.

If such an operation is available to you, you would calculate the 128 bit product x.s2 * y.s2, and the two 64 bit products x.s1 * y.s2 and x.s2 * y.s1 and use these to calculate the 128 bit product. If you want a 256 bit product, then you need to calculate four 128 bit products.

If you have no easy means to calculate the 128 bit product of two 64 bit numbers, then hopefully you can calculate the 64 bit product of two 32 bit integers, so you can use the same operations with half the number of bits.


Double ended queue data abstraction and axioms I am trying to show the data abstraction for a double ended queue along with the axioms. A double ended queue is a queue where items can be added to and remove from either end of the queue.  I have already got the abstraction and axioms for a normal queue but looking at it, it looks to me like it would also work for a double ended queue. If this isn't the case what changes need to be made to make it work for a double ended queue?

Specification Queue:
Provides: Queue
Other abstractions used: Item, Boolean

Operations: NewQ: -> Queue
AddQ: Queue, Item -> Queue
RearQ: Queue -> Queue
FrontQ: Queue -> Item
IsEmptyQ: Queue -> Boolean

Axioms:
RearQ(NewQ) := NewQ
RearQ(AddQ(q, i)) := If IsEmptyQ(q) then NewQ
           otherwise AddQ(RearQ(q), i)
FrontQ(NewQ) := Error
FrontQ(AddQ(q, i)) := If IsEmptyQ(q) then i
           otherwise FrontQ(q)
IsEmptyQ(NewQ) :- True
IsEmptyQ(AddQ(q, i)) := False

Where:
   i is of type Item,
   q is of type Queue

Like you say items can be added to a double ended queue on both sides, yet you have only a single AddQ operator. More substantial is the change to the axioms. An item added at the end can (after several operations) be retrieved from the front.


Choose a "middle" point from a set I read a post which talks about pretty much the same problem. But here I simplify the problem hoping that a concrete proof can be offered.

There is a set $A$ which contains some discrete points (one-dimensional), like $\{1, 3, 37, 59\}$. I want to pick one point from $A$ which minimizes the sum of distances between this point and others.

There may be lot of posts out there, and my problem is just the one-dimensional version of those. I know how to prove it if $A$ is not discrete, but I fail when $A$ is discrete like above.

Please answer with a concrete proof.

For a point $x$, let $d(x)$ be the sum of distances between $x$ and points in $A$. For $x \notin A$, the derivative $d'(x)$ has the nice formula
$$ d'(x) = |\{y \in A : y < x\}| - |\{y \in A : y > x\}|. $$
This shows why the median is the best answer when you don't have to select a point from $A$. For a point $x \in A$, $d(x)$ is the same as your objective function, hence the solution is to choose the median. You can find the median in linear time, as described in Wikipedia and various other resources.


how to convert any fraction to decimal So for a project I am working on. I need to take a string representation of a floating point number, lets say "1.5" and do arithmetic on it with another floating point number. The catch is I cannot use floats to do this, since it specifically says in the requirements for my homework that I can't do this. How I am supposed to do something like add or subtract these numbers is break the string apart into it's characteristic (1) and it's mantissa(5). so in the program, the program will be represented as 1/2. However, if I wanted to add 1.5 with 1.3, 1/3 goes on forever. Thus making it impossible to convert 1/3 to 1/(some power of 10) and figure out how to add everything together. Is there an algorithm that can deal with cases of division like 1/3?

You should implement rational numbers yourself. Store number as two integers. Use the greatest common divisor to factor out superflous representation. Literally write school algorithms for rational numbers - find common denominator for addition and then normalize number. At the end convert it to decimal representation with fixed precision. Namely use symbolic calculation as long as you can.

From your example:
$\frac{1}{3} + \frac{1}{5} = \frac{5}{15} + \frac{3}{15} = \frac{8}{15} \approx 0.5333$

If your task really requires to convert it to string at the first step, then you have to assume some precision, e.g. four numbers in decimal expansion, and then write your own code to operate on numbers. The exact decimal expansion is not always possible, as you have already realized, so $\frac{1}{3}$ would expand to "0.3333" (arbitrary length from my example. It may seem weird at first, but the floats are also inexact, with precision given by fixed length representation (e.g. 64, 80, 128 bits).

$\frac{1}{3} \approx 0.333; \frac{1}{5} \approx 0.2000$
So
$0.3333 + 0.2000 = 0.5333$
It gives the same approximate result.


Enumeration of a class of languages Can you enumerate a class of languages in such a way that the description of every language/ machine enumerated encodes where it was in the enumeration?

Ex:if you are given the description of the bth machine/language enumerated you could quickly check, by some tag or marker in the description of the bth machine / language, that it was indeed the bth machine/language in the enumeration by an enumerator E.

Can you modify any enumerator for a class of languages so that it does this? Or can such an enumerator E be rigged up to do this for any enumerable class of languages?

To give context, my goal is for a verifier to accept, as one part of its input, the machine/language enumerated, and be able to see, quickly, what position that machine/language was in the enumeration by the enumerator E.

Thank you!

Given any enumeration $E$ of the language, here is a way to describe a language: "the 5th language in the enumeration".

If you use that as the description, then yes, your condition is trivially true.  Given the description of a language ("the 5th language in $E$"), you can quickly find its position in $E$ (5).


Unique property of a full binary tree I read a statement that was unclear to me, and was hoping to get some clarification.

It said that given a full binary tree with $n > 2$ leaves, there exists some internal node such that one third to two thirds of all $n$ leaves in the tree are its descendants.

From my understanding, I know each internal node in a full binary tree has 2 children. That said, the whole tree has $2n - 1$ nodes, which means $n - 1$ of them are internal nodes (not leaves).

I can come up with drawn examples where this is always the case, but I am not sure how to formally reason it. Any help would be greatly appreciated.

Let $T$ be a tree rooted at $r$ with $n > 2$ leaves, and let $\ell(u)$ denote the number of leaves in the subtree of $T$ rooted at node $u$.

Initially let $v=r$, then proceeds as follows:

If $\ell(v) \le \frac{2n}{3}$ then return $v$.
Otherwise, let $u$ be one of the children of $v$ with the largest $\ell(u)$, set $v=u$ and repeat from the first step.

Notice that, for every $v$ considered by the algorithm:

$v$ is not a leaf (hence step 2 is well-defined). If $v$ were a leaf, then the parent $w$ of $v$ (which always exists) would satisfy: $2 \le \frac{2n}{3} < \ell(w) = 2 \ell(v) = 2$, a contradiction.
$\ell(v) > \frac{n}{3}$. This is clearly true when $v=r$. For $v \neq r$, let $w$ be the parent of $v$. Since $\ell(w) > \frac{2n}{3}$, we must have $\ell(v) \ge \frac{\ell(w)}{2} > \frac{2n/3}{2} = \frac{n}{3}$.

The algorithm must terminate (at each iteration the depth of $v$ increases), therefore the returned vertex $v$ is not a leaf and satisfies both $\ell(v) > \frac{n}{3}$ (by the above property) and $\ell(v) \le \frac{2n}{3}$ (by the condition of step 1).

This proof is constructive and shows that $v$ can be found in $O(n)$ time (you can find all the values $\ell(v)$ with a postorder visit).


Why the pointer in linked list is of structure type? Since any node points to a memory location is there any specific need in using it's pointer as structure type.Why couldn't we use integer as the pointer type in linked list rather than structure?

The nodes in a linked list need to hold two things:

the node's value
a (possibly null) pointer to the next node

That makes them structs, so a pointer to a node is a pointer to a struct.


Confused about NP-Complete Proof Using Reduction Consider a job schedule decision problem with only one machine takes input $\{(r_1,p_1,d_1),(r_2,p_2,d_2),...,(r_n,p_n,d_n),K\}$; where $r_i$ is the start time for the ith triple, and $p_i$ is the process time of the triple; and $d_i$ is the deadline.Require for each $i$, schedule a job at time $t_i$ such that $r_i≤t_i≤d_i−p_i$. Goals to decide whether we can schedule $K$ number of compatible jobs.

I try to show that this problem is at least as hard as SubsetSum problem.

Consider a instance of input to SubsetSum. $\{a_1,a_2,..a_n;T\}$

Assume that $∃ I⊆\{1,2,..n\}$
such that $∑_{i∈I}a_i=T$; then we can design a transformation such that assigns a subset $\{r_i,p_i,d_i\}$ some value, and show that taking this set as input to schedule problem will also return True. For example, assign start value to each of job to be 0, process time for each job to be $a_i$, deadline for each job to be $\sum_{i\in I} a_i$. I have prove the $\implies$ direction

However, my problem here is about doing converse proof. We have to show that schedule decision problem taking an instance return true implies that SubsetSum taking kind of "inverse transformation" of that instance also returns true.

My understanding of prove converse direction is that we need some sort of inverse transformation. For example, given any arbitrary set of triple $\{(r_i,p_i,d_i)\}$, if this set accepted by schedule problem, then we need to find some "inverse transformation" transform the triples into some array, and a target value that can be accepted by SubsetSum. And this "inverse transformation" compose with our original transformation (designed for ($\implies$) direction proof) should be some identify transformation.

OR

Can we only give the input that has start value to each of job is 0, process time for each job is $p_i$, deadline for each job to be $\sum_{i\in I} p_i$. Basically, use the transformed input from the direction of ($\implies$)

And assume that this set of input accepted by schedule decision problem, we want to show that using the sum over process time and the deadline time as input to SubsetSum can also return true.

I don't which approach is correct here

Your solution is a far way off from being correct. It seems that you are trying to use different transformations for both directions of the proof, while you should actually be using a single transformation from subset sum to the scheduling problem.

  I try to show that this problem [scheduling] is at least as hard as SubsetSum problem.

Subset Sum is a hard problem; we don't think it's likely that it can be solved in polynomial time. If you want to show that scheduling is hard, then you need to show that if we could solve scheduling in polynomial time, then we can also solve subset sum in polynomial time.

What you are given is an instance of subset sum $\{a_1,a_2,\ldots, a_n; T\}$ and a magic machine that somehow solves the scheduling problem in polynomial time. We want to show that it is unlikely that this magic machine could exist, therefore we will show that using this magic machine we can solve subset sum in polynomial time (which we think is probably not possible).

For this, you need a transformation that takes an instance $A$ of subset sum as input, and gives as output an instance $B$ of the scheduling problem, such that $A$ has a feasible solution if and only if $B$ does. That is, being able to find a solution for $B$ (in polynomial time) will also let you find one for $A$ (in polynomial time).

  Assume that $∃ I⊆\{1,2,..n\}$
  such that $∑_{i∈I}a_i=T$; then we can design a transformation such that assigns a subset $\{r_i,p_i,d_i\}$ some value, and show that taking this set as input to schedule problem will also return True. For example, assign start value to each of job to be 0, process time for each job to be $a_i$, deadline for each job to be $\sum_{i\in I} a_i$.

You can't do this. You can't base the transformation on the assumption that the subset sum instance is solvable. You don't know $I$ (because this is the hard-to-compute thing you're trying to compute), so you can't use it to construct the transformation. You can only use $I$ to show that, the transformed instance - which you constructed without knowledge of $I$ - has a solution.

Hint: you need to design an instance of the scheduling problem that is forced to split the jobs into two groups (one summing up to $T$, one to $\Sigma a_i - T$). For this, it might be useful to have one or two additional jobs that must be scheduled at a fixed point in time (by setting $r_i+p_i=d_i$).

To summarize: a correct NP-hardness proof consists of the following steps:

Take an NP-hard problem (e.g., subset sum) and design a transformation $f$ that maps an instance $A$ of this problem to an instance $B=f(A)$ of the problem you want to show NP-hard (e.g., scheduling).
Show that, if $A$ has a solution (is a yes-instance), then $B$ is a yes-instance
Show that, if $B$ is a yes-instance, then $A$ is a yes-instance (or show the converse: if $A$ is a no-instance (has no solution) then $B$ is a no-instance as well.


Determining if an undirected connected graph is minimally connected I'm trying to solve a practice problem in Elements of Programming Interviews (19.4) and I am a bit confused.  The question is to determine if an undirected connected graph is minimally connected.

The authors define minimally connected as "it is connected and there is no edge that can be removed while still leaving the graph connected."

This question is equivalent to asking if there are any cycles in the graph.

They authors' solution runs the white-gray-black variant of recursive DFS, and return false if a grey node is visited twice.

It seems to me though, that since you know the graph is connected you can just count the number of edges.  Any minimally connected graph, like a binary tree, will have (V - 1) edges.

return num_edges/2 == num_vertices - 1;

So, long story short, is this solution correct for the case of an undirected, connected graph?  I checked the books errata and it doesn't mention it.

If $G$ is an undirected graph, it's a standard lemma that the following are equivalent:

$G$ is a tree.
$G$ is connected and has no cycles.
$G$ is connected and the number of edges is one less than the number of vertices.

Therefore, yes, your solution is also correct.

(The authors' solution does have the benefit of giving you a relatively simple setting where you can think through the properties of depth-first search in a deep way.  There are other problems that aren't solved so easily, and where the best solution involves some other sort of modification to depth-first search.)


recursive function as circular funciton I recently learnt that a recursive function is also referred to as a circular function.

See, the recursive function cannot be a circular function because even if there is a call to function itself, it does not happen indefinitely. There is always a base case (or condition) from where the function is supposed to exit in one way or the other (either by displaying some message or returning some value).

So, is calling recursive function, a circular function not a misnomer ?

I agree that it's a misnomer. Consensus from the comments seems to be that "circular function" is not a commonly used term for a recursive function. I think the person you saw using the term was using the wrong word, perhaps because of translation issues.


a regular language so that $unary(L) \notin $Context Free Languages I need a regular language $ L\subseteq \{0,1\}^{*} $ so that $unary(L)$ is not context free.

unary of $L$ is defined by:
$$unary(L) = \{0^{1x}  : x \in L  \}$$

Example $L = \{0, 11\} $ $\rightarrow  unary(L) = \{00, 0000000\}$

Any help would be great.

Let $L = 10^*$ and observe that $$\text{unary}(L) = \{ 1, 11, 1111, 11111111, \dots\} = \{1^{2^i} \mid i \in \mathbb{N} \}.$$

Can you prove the rest yourself?