Design PDA or CFG for the following language $L = \{wtw' \mid w,w' \in \{a, b\}^*, \hspace{0.3cm} |w|_a = |w'|_a, \hspace{0.3cm} |w|_b=2|w'|_b, \hspace{0.3cm} t\in\{c\}^* \}$.

  Note : $|w|_a$ means the number of $a$ in substring $w$.

To substring $w$, the number of symbol $a$ and $b$ is not relevant to each other.

It's also applied to substring $w'$.

To make matters worse, order of $a$ and $b$ (in both $w$ and $w'$) is not defined. So order can be anyway... It makes the problem harder for me.

I designed several PDAs but they resulted in contradiction.

So I tried to construct a CFG. But designing a CFG is more difficult for me.

Could you give me some hints to design PDA or CFG for the above language?

There is no such grammar: the language is not context-free.

$L\cap a^*b^*ca^*b^* = \{a^nb^{2m}ca^nb^m\mid m,n\ge 1\}$.


Is the Euclidean TSP weakly NP-hard? So the Euclidean TSP decision problem is NP-complete (see http://dx.doi.org/10.1016/0304-3975(77)90012-3 ) so the TSP optimization problem should be NP-hard.

On the other hand there is a PTAS for the Euclidean TSP (see http://dx.doi.org/10.1145/290179.290180 ).

Wikipedia says that a PTAS is not possible for strongly NP-hard Problems.

So is this a contradiction, or is the Euclidean TSP "only" weakly NP-hard?
Did I miss something else?

You're confusing a polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS).  Euclidean TSP has a PTAS, but it is not an FPTAS because the polynomial increases in degree as 1 / ε decreases.  Only an FPTAS is disallowed for strongly NP-hard problems, assuming P $\neq$ NP.


What these simple rules of logical implications mean Their are many rules of logics, predicate calculus, inferences and syllogisms which haunt me always. It feels better when I find some sensible name to particular rule which also gives me intuition about the meaning of the rule. Recently I came across some simple tautologies:

$((x \rightarrow y)\wedge(x \rightarrow \neg y))\rightarrow \neg x$
$((x \rightarrow y)\vee(x \rightarrow \neg y))$

I am struggling to find intuition or reasonable interpretation of their meaning:

Interpreting  rule 1:
If a first variable $x$ implies both: second variable $y$ and its
negation $\neg y$, then why the negation of first variable $\neg x$
should always hold? Does it mean to imply that no such variable can
exist which can imply both: another variable and its negation?
Interpreting  rule 2:
Why should a first variable $x$ should always imply either (any
given) second variable or its negation?
Finally are there any formal names used to refer these rules?

I must be missing something very basic.

Contradictions can't happen. If $x$ implies a contradiction, then $x$ can't be true.
Either $y$ is true, or it isn't.  That's still the case even if I first tell you that $x$ is true.


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

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

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

Let me write the definition in a little bit more detail.

Suppose that $f(n),g(n)$ are two functions from $\mathbb{N}$ to $\mathbb{R}_+$, that is, they accept as input a natural number, and return as output a positive real number.
We say that $f(n) = O(g(n))$ if there exist $n_0 \in \mathbb{N}$ and $C \in \mathbb{R}_+$ such that for all $n \geq n_0$,
$$ f(n) \leq Cg(n). $$

In order to show that $f(n) = O(g(n))$, you have to find $n_0$ and $C$ such that for all $n \geq n_0$ it holds that $f(n) \leq Cg(n)$. You can choose whatever $n_0,C$ you want as long as the condition holds. It turns out that for this definition, we can always take $n_0 = 1$ (for other variants of the definition, this no longer holds). So you only have to find a positive constant $C > 0$ such that for all $n \geq 1$ it holds that
$$ f(n) \leq Cg(n). $$
(This assumes that the first natural number is 1 rather than 0.)
Now we can answer your question:

$n$ is the argument of the functions $f,g$.
$n_0$ is the point beyond which the inequality $f(n) \leq C g(n)$ should hold. When proving that $f(n) = O(g(n))$, you get to choose $n_0$. In most cases you can just take $n_0 = 1$.

For the curious: why do we need $n_0$? Sometimes we would like to accommodate functions which are not strictly positive, but just eventually positive. For example, if 0 is a natural number (in contrast to the convention used above) then $n^2$ is not strictly positive, since it vanishes at $n = 0$. Therefore $n = O(n^2)$ is only true if we allow to "skip" $n = 0$, which we do by choosing $n_0 = 1$.


Prove that the set of all total functions is countable I'm stuck on a theory/set proof question:

  $S$ is the set of all total functions $f : \{0, 1\} \to \mathbb{N}$ (natural numbers), prove that S is countable.

I have found a sample solution already but I do not understand what is going on.

Quoting from here:

  To show this, we define a mapping $g$ from $S$ to $N × N$ and show the mapping is a bijection.

Why must I prove bijection when the definition of countable (according to wikipedia) states "A set $S$ is called countable if there exists an injective function $f$ from $S$ to the natural numbers"?
Also why a bijection/injection from $S$ to $\mathbb{N} \times \mathbb{N}$ and not just $S$ to $\mathbb{N}$?

ad a) showing that $g$ is injective should suffice.

ad b) because it's easier. or put differently: how would you define an injective mapping $h: S \rightarrow \mathbb{N}$ ? it is feasible (eg. $f \rightarrow 2^{f(0)}\,*\,3^{f(1)}$) but complicates matters unnecessarily ( to prove injectivity you'd have to exploit additional information eg. the unique prime factor decomposition of natural numbers ).


How to convert a centralized algorithm to a distributed algorithm? Is there any algorithm or procedure to convert a centralized algorithm to a distributed algorithm? Is there any theoretical result or relevant complexity analysis?

Sure.  If you have a distributed system with N machines, you can always run the centralized algorithm on machine 1 and let machines 2..N sit idle.

If you're asking whether all sequential algorithms can be parallelized, that's an open question, but it's believed that the answer is no: see the NC complexity class.  As Wikipedia states,

  there are probably some tractable problems that are "inherently sequential" and cannot significantly be sped up by using parallelism.

P-complete problems are good candidates for problems that are likely not amenable to speedup by parallelism.

If you're asking whether all algorithms can be made reliable in a distributed system, that is a subtle question that depends on what kinds of failures you are considering.  You might look into consensus protocols, state machine replication, and the CAP theorem.


proving $IP^\star = NP$ Consider the following complexity class $IP^\star$, a variant of $IP$.
  A language $L$ is in $IP^\star$ if there's a proof system $(P,V)$ s.t.
  $V$ is a verifier runs for a polynomial time and:

  $$x\in L \implies Pr[(P,V)(x) = 1] \ge 3/4 \\ x\not\in L \implies
> Pr[(P,V)(x) = 1] = 0 \\ $$

  Prove that $NP = IP^\star$.

  Note: in this definition as far as I understand, we have a single $P$
  (for both cases).

Now, one side is easy ($NP\subseteq IP^\star$), since by definition $NP$ language has a perfect polynomial-verifier - so we're satisfying the demands.

The other side is the tricky one. Consider a language $L\in IP^\star$. We want to show that $L\in NP$. Obviously we shall utilize $V$ somehow.
The certificate could be the "conversation" between $V$ and $P$. Then our $NP$ TM could simulate the conversation between $P$ to $V$.

Yet, that's alone isn't good enough - we have a $1/4$ probability to make a mistake if $x\in L$.

Amplifying the probability isn't good enough too. We need perfect soundness.

So maybe we shall use the non-determinism of our machine somehow?

If $x \in L$ then the probability that $(P,V)(x,r) = 1$ is positive, where $r$ is the randomness involved; the probability is over the choice of $r$. In particular, there is some $r$ such that $(P,V)(x,r) = 1$.

In contrast, when $x \notin L$, the probability that $(P,V)(x,r) = 0$. That is, there is no $r$ such that $(P,V)(x,r) = 1$.

States differently, when $x \in L$, there is some conversation for which the verifier outputs 1, whereas when $x \notin L$, there is no such conversation. Since the verifier runs in polytime, the conversation has polynomial length, and can be verified to be a valid conversation in polynomial time. This puts $L$ in NP.

What is the difference between IP* and IP? IP* has perfect soundness – when $x \notin L$, the probability of error is 0 – whereas IP has neither perfect soundness nor perfect completeness. This makes IP much stronger.


While proving optimality of the A* algorithm, why can we change graphs? In the original paper of A* algorithm, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, the author proved the optimality of A* in Theorem 2, page 105.

However, I cannot understand the proof. The assumption is that we have a node in $G_s$ which is not expanded by algorithm A, but in the proof we change the graph to $G_{n,\theta}$, isn't it a problem?

No, it isn't a problem.

The whole idea is that the algorithm doesn't operate on a single graph, but rather on a family of graphs (with costs), determined by what the algorithm knows from the heuristic and the explored nodes. That family is denoted by $G_{n,\theta}$ in the paper.

The admissibility of the heuristic basically means that the actual graph is amongst the family $\{G_{n,\theta}\}_\theta$ for some $\theta$.

The proof of Theorem 2 says, that if the other algorithm established that the shortest path form $s$ to $t$ has cost $f(t)$ and $A^*$ expanded the node $n$ which the other hasn't, it means that the estimate of cost of $s \rightarrow t$ path via $n$ was lower than the actual $f(t)$, which means there is some graph in the $\{G_{n,\theta}\}_\theta$ family where the shortest path from $s$ to $t$ passes through $n$. Because the other algorithm didn't expand $n$, it is not admissible for the assumed graph family (because that particular graph would break it).

In other words, if the problem was eg. going from Madrid to Paris, the algorithm might have discovered that (for simplicity) you can get to Barcelona and Valencia in 300 km. Then you know the distance to Paris is $>$1000 km from Valencia, and $>$800 km from Barcelona. If the other algorithm hasn't expanded Valencia and tells you that the shortest path goes through Barcelona with distance 300 km$+$1100 km (for the stretch Madrid-Barca and Barca-Paris), it hasn't ruled out an (alternative universe) situation where the distance between Valencia and Paris was only 1050 km (and would be therefore shorter).

Apologies for distorting Europe a bit


What is minimum cost perfect matching problem for general graph? It does make sense when we talk about perfect matching in bipartite graphs because there are two sets of points, for example, one set may be jobs and other set may contain different machines. But when we talk about minimum cost perfect matching in general graphs, it is not making any sense for me, what are the nodes and edge cost representing, If you can give some real-life example depicting minimum cost perfect matching in general graphs. It will be very helpful to me.

Also, I need a precise definition of the minimum cost perfect matching problem. Thank You.

The minimum cost perfect matching problem is formally defined as an optimization problem where:

The set of instances is the set of all edge-weighted undirected graphs $G=(V, E, w)$, where $w : E \to \mathbb{R}$.
Given an instance $G=(V, E, w)$, the set of feasible solutions are the perfect matchings $M$ of $G$, i.e., all the sets $M \subseteq E$ such that, $\forall u \in V \; |M \cap \{ (u, v) \in E : v \in V \}| = 1$.
Given an instance $G=(V, E, w)$ and a feasible solution $M$ for $G$, the is a function called measure defined as $m(G, M) = \sum_{e \in M} w(e)$.
The measure is to be minimized.

As for the problem making sense... the problem is abstract in nature and it can be perfectly well-defined without any need for vertices, edges, weights or the matching itself to represent anything.

Of course it is fairly easy to come up with (mock) scenarios in which you might want to compute a minimum cost perfect matching of a suitable graph that is modelling some real-world entities, e.g., the one that follows.

You are organizing a trip for a (large) group of $n=4k$, $k \in \mathbb{N}^+$, participants that will travel together on a bus with $n$ seats. Bus seats are arranged in rows of $4$, with $2$ adjacent seats on each side and a corridor in the middle.
Not all of the participants enjoy their company equally (indeed, some of them categorically refuse to be close by) and you know, for each pair of people that can sit together, how much they'd happy (or unhappy) to be sat next to each other (say, in a scale from $-1$ to $1$).
Being a thoughtful organizer, you want to arrange seats in order to maximize the social welfare of the participants, i.e., the sum of the happiness of all pairs of neighbors in the arrangement you choose.


Doubt regarding foreign key and referential integrity I am studying database from Database System Concepts.

The author was explaining foreign keys and referential integrity with the help of following schemas:

$$ instructor(\underline{ID},\space name,\space dept\text_name,\space salary)$$
$$ course(\underline{course\text_id},\space title, \space dept\text_name,\space credits) $$
$$ department(\underline{dept\text_name}, \space building,\space budget)$$
$$ section(\underline{course\text_id,\space sec\text_id,\space semester,\space year},\space building,\space room\text_no,\space time\text_slot\text_id) $$
$$ teaches(\underline{ID,\space course\text_id, \space sec\text_id,\space  semester, \space year})$$

The primary keys are underlined.

The relation $section$ is used so that each course could be offered multiple times, across different semesters, or even within a semester.

Foreign key was explained with the help of schemas $instructor$ and $department$. The attribute $dept\text_name$ in in $instructor$ is a foreign key from $instructor$ referencing $department$.

It need not be the case that all $dept\text_name$ values are referenced by $instructor$ relation.

Referential integrity constraint was explained with the help of $section$ and $teaches$ schema.

If a section exists for a course it must be taught by at least one instructor(it could be taught by more than one instructor)

So all the combinations of $(course\text_id,\space sec\text_id,\space semester, \space year)$ that appear in $section$ relation must also appear in $teaches$ relation.

But we cannot declare a foreign key from $section$ to $teaches$ since multiple instructors could teach a single section.

We could define a foreign key from $teaches$ to $section$.

Since we could form a referential integrity constraint from $instructor$ to $department$ by using foreign key but without foreign key we have referential integrity constraint from $section$ to $teaches$.

So how is referential integrity different from foreign key constraints?

Also if you know some free resources that could clear database concepts please share.

In general the “referential integrity constraint” is a constraint that states that a foreign key must always be equal to some primary key of a tuple in the referred relation (so establishing a correspondence between a tuple in the first relation and another (and only one) in the other relation. If the constraint is violated, that is if the value of the foreign key of a tuple is not equal to the value of the primary key of another tuple, this means that the foreign key has lost its integrity, since it “does not refer anything”, like a “dangling reference” in a programming language.

It is a duty of the Database Management System to enforce this constraint, and prevent any violation of it through some policy, that can be specified by the database administrator (“on delete cascade, no action”, etc.)

In the book that you cited, it is in fact said that:

  a referential integrity constraint requires that the values appearing in specified attributes of any tuple in the referencing relation also appear in specified attributes of at least one tuple in the referenced relation.

The comment related to the example explains that, even if, according to the rules of the university, each section should be taught by at least one instructor, it is not possible to express such constraint in the database designed, since it is not possible to define the attributes of section as foreign key for the relation teaches (since they do not form a primary key in such relation).

Note that this depends on the fact that the only way to represent a 1-n relationship between two sets of data in the Relational Data Model is to use a foreign key in the relation where there is only one element (at maximum) in the other relation, not vice-versa. So the foreign key is from teaches to section, since a tuple in teaches can be related only to one tuple in section.


CVRP and removing edges from a graph I am solving a CVRP (Constrained Vehicle Routing Problem) on a connected graph, that is not necessarily complete. Edge weights represent Euclidean distances.
I know that, in general, the complexity of the problem in terms of the number of variables (and computational time) increases with the number of edges in the graph.
I also know that for particular graphs where node degree is fixed (for example 3 or 4), polynomial-time algorithms exist that return the optimal solution.
Therefore, I am playing around with removing the edges with the highest weight from the graph, while ensuring each node retains at least a minimum degree, and seeing how this impacts solution time. As expected, reducing the number of edges in the graph does impact the solution time significantly.
Are there any theoretical results that tie this idea of removing edges from the graph before solving the problem to the optimality of the solution? Is it in some cases possible to conclude, a-priori, that some specific edge will necessarily NOT be part of the optimal solution?

I don't know anything about routing, so take this with a grain of salt.
What you have is a metric graph, in that your graph satisfies the triangle inequality.  If you start removing edges, then  heuristic algorithms might have less to work with, which isn't obviously better.
Take for example a look at these questions:

Bottleneck TSP with MST
For a set of points P, connected by weighted edges (distances) I need a path through all points while minimizing the travel on any edge longer than X

Taking removing edges to the extreme is actually how Christofides algorithm works for approximating Travelling Salesman; Namely by finding a Minimum Spanning Tree and deleting all the remaining edges.


Regular of language of all words of length 3 Consider the language $$L = \{ x \in \{0,1\}^* \mid |x| = 3 \}.$$
I think the above language is regular. A DFA can be used to determine the above language.

Am I correct? Is the above language regular?

If this language $L$ is regular, then it should satisfy the pumping lemma. Then there exist $w = xyz$, where $xy^nz \in L$ for all $n \ge 0$.
But on the other hand, if we pump more letters then the resulting string will not be in the language. The language $L$ only contains words of length 3.
The pumping lemma states that for every regular language there exists an integer $p$, such that string $w$ of length at least $p$ can be written as $w = xyz$ and $y$ can be pumped.
Here are my doubts.

Is this language $L$ regular?
If so, does it satisfy the pumping lemma?
The pumping lemma states that every regular language has a pumping length $p \ge 1$. Does this language not have one?

Every finite language is regular. If $L$ is a finite language and $p$ is larger than the length of all words in $L$, then $L$ satisfies the pumping lemma with the constant $p$. Indeed, every word in $L$ of length at least $p$ can be pumped (vacuously).


Arrange in increasing order of asymptotic complexity I have the following functions that I need to rank in increasing order of Big-O complexity:
$$(\log n)^3, 10\sqrt n, n\log n, n\sqrt n, n^4 + n^3, (2.1)^n \cdot n^2, 3^n, 2^n \cdot n^3, n! + n, n^n. $$
My current ranking is as follows:
$$(\log n)^3 < 10\sqrt n < n\log n < n\sqrt n < n^4 + n^3 < (2.1)^n \cdot n^2 < 2^n \cdot n^3 < 3^n < n! + n < n^n. $$
Is my ranking of the functions in increasing order of complexity correct?

You have mistake in $(2.1)^n \cdot n^2<2^n \cdot n^3$, because it is equivalent $\left(\frac{2.1}{2}\right)^n<n$


Given RSA, why do we not know if public-key cryptography is possible? I was on wikipedia on list of unsolved computer science problems and found this:
Is public-key cryptography possible?

I thought RSA encryption was a form of public-key cryptography? Why is this a problem?

We don't know for sure that RSA is safe. It could be that RSA can be broken in polynomial time, for example if factoring can be done efficiently. What is open is the existence of a a provably secure public-key cryptosystem. We don't know for sure that such a cryptosystem exists at all; for all we know, every cryptosystem could be broken efficiently.

A different, unrelated problem with RSA is that it can be broken by quantum computers. This is an unrelated problem since the definition of a secure public-key cryptosystem only requires that the cryptosystem not be breakable by classical (non-quantum) computers.

Practically speaking, though, RSA seems secure, and it is used all the time. This is due to the gap between theory and practice. While theoretically we don't know for sure that RSA is secure, practically speaking we have to use some public-key cryptosystem, and RSA is a good choice since people have tried to break it and failed. Generally speaking, a known cryptosystem that people care about is more secure than an obscure one, since it has resisted the attempts of cryptographers. This doesn't constitute a proof that it is secure – it might well not be – but it's the best we can do.


Reducing the Hamiltonian cycle to the travelling salesman problem and self loops If this is my adjacency matrix for the hamiltonian cycle:
$$\begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}$$
Then a reduction algorithm to reduce this to a TSP problem is to introduce 1 anywhere an edge is missing and let pre-existing edges have a cost of zero (according to this), applying this yields:
$$\begin{pmatrix}1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\end{pmatrix}$$
Now I see that I have also introduced weighted-loops to my undirected graph, would asking whether this has a zero-cost salesman tour be equivalent to asking whether the unreduced version has a hamiltonian cycle, or should I maybe have something else on the diagonal of the reduced matrix?

Suppose your original graph $G$ has a Hamiltonian cycle $C$.
Then the cost of the tour induced by $C$ in the new graph $G'$ you defined is indeed $0$ and conversely, any TSP tour of cost $0$ can only use edges of cost $0$ as you did not introduce any edges with a negative cost.
Adding the loops does not change this, so the reduction works out if we are willing to allow non-simple graphs which isn't done usually as the definition of the TSP asks for a tour visiting each vertex exactly once, i.e. no valid tour would include loop edges anyways.
Given this, we also see that you can remove the loop edges in $G'$ to make it a simple graph to obtain an equally valid reduction.
From a technical standpoint this doesn't make much of a difference but since people like simple graphs, I would personally prefer the reduction yielding a simple graph.


Is Artificial General Intelligence possible with our current machine learning models? In other words, is artificial human level intelligence not possible yet just because of limitations in processing power and amount of data required to train the models? Or we don't have the knowledge of how to achieve it even in theory?
Suppose that processing power and amount of training data is not a problem, could humanity build AGI with our current machine learning models and knowledge?

The short answer is, we don't know! This is an open question in AI research.

We know how neurons transmit signals, and can simulate that in a straightforward way: that's how layered perceptron models work. If we had a way to measure all the connections in a human brain, and enough computing power (which would be a LOT of computing power), we could simulate it. Or we could just make a neural network with as many neurons and connections as a human brain has. There's no theoretical missing link, we're just orders and orders of magnitude away in scale.

But it's an unanswered question whether the human mind exists entirely within neurons or not. It's a philosophical question more than a computer science one, and comes down to monism versus dualism.

Those who believe there's no theoretical barrier to AGI (just a problem of scale) tend to call their belief the Strong Church-Turing Thesis, which claims that a universal Turing machine could simulate a human mind, given unbounded resources and time. Or, equivalently, that a human mind is a Turing machine, or that there's nothing a human mind can do that a computer cannot do given time and resources for it.


Removing Null moves from NFA While Learning about removing null moves from NFA , I came across a thought....

To Remove Epsilon moves we follow following steps :

Find Closure of all states which have null moves
Mark these states which have null moves
Make a revised transition table without epsilon column and Find all possible transition for those marked states by using their Closures.
you will get nfa without null moves/epsilon moves

Where is the issue : Actually, Doubt arises when you think of an nfa like this :

If we try to remove epsilon moves out of it...

Initial transition Table :

Now finding closure for q0, q1 and q3.

Which is CL(q0) = {q0,q1,q2}
CL(q1) = {q1,q2}
CL(q3) = {q2,q3}
We find a transition table after following above steps which is :

The question gets quite tricky...

because now this nfa has q1,q2 where there is no way to reach them..

So What do you think we will remove q1 and q2 as they are unreachable or we will draw a nfa with them...

In your construction you correctly computed the closures of the original states and then made the $a$- and $b$-transitions, but you omitted step (3) of the algorithm: compute the closures of the results again. For example, from $q_0$ on input of $a$ the first step is
$$
q_0\stackrel{CL}{\longrightarrow} \{q_0, q_1, q_2\}
$$
then, on seeing an $a$ we make the transitions, as you did:
$$
\{q_0, q_1, q_2\}\stackrel{a}{\longrightarrow} \{\delta(q_0, a), \delta(q_1, a), \delta(q_2, a)\}=\{q_3, q_4\}
$$
then (here's the step you omitted), you take the closure again:
$$
\{q_3, q_4\}\stackrel{CL}{\longrightarrow} \{q_2, q_3, q_4\}
$$
and thus you'll have the new transition $\delta'(q_0, a) = \{q_2, q_3, q_4\}$.

If you do this for all the state-symbol pairs, you'll find that the transitions of your new NFA are
$$\begin{array}{c|cc}
 & a & b\\ \hline
q_0 & \{q_2, q_3, q_4\} & \{q_2, q_3\} \\
q_1 & \{q_2, q_3, q_4\} & \varnothing \\
q_2 & \{q_4\} & \varnothing \\
q_3 & \{q_4\} & \{q_5\} \\
q_4 & \{q_5\} & \{q_2, q_3\} \\
q_5 & \varnothing & \varnothing \\
\end{array}$$
Since $q_1$ is an unreachable state, it can be eliminated without changing the langauge of the resulting NFA.


What are the major differences between row polymorphism and subtyping I hear often that row-polymorphism is a better approach than subtyping, but I have difficulty finding anything comparing them in detail. I'm especially interested in the perspective of a user of the system.

I did come across this blog post, but it leaves me with more questions than before. For example, it makes a claim that a system with subtyping will assign one type, whereas a system with row typing will assign another; does that mean that if a system that purportedly has subtyping assigns the "row typing" type, that it purports incorrectly?

The one major difference I do see is that row typing makes it possible to align the types of arguments (that is, write a two argument function that concerns itself only with the a field of its arguments, but requires that its arguments have the same fields).

Subtyping says given an expression of one type we can give it also another type.  We say the former is a subtype of the latter and this subtyping relationship induces many other relationships.  In symbols,
$$\frac{\Gamma\vdash E:S\qquad S<:T}{\Gamma\vdash E : T}$$

The key thing here (and the reason I reviewed it) is that the same expression is given two different types.  In parametrically polymorphic languages with implicit type instantiation we have the following subtyping relationship:
$(\forall \alpha.\tau) <: \tau[T/\alpha]$ for all types $T$.  If type instantiation is explicit like in System F, this subtyping relationship doesn't hold.

As a bit of an aside, we could say a language with row types (usually) has  subtyping relationships of the form $\{\ell_1:A,\ell_2:B\} <: \{\ell_2:B,\ell_1:A\}$ giving rise to $\{\ell_1:A,\ell_2:B\} \cong \{\ell_2:B,\ell_1:A\}$ where $S \cong T \iff S <: T \land T <: S$.  However, the way this is actually handled is by changing the notion of equality of types (i.e. unification) so that $\{\ell_1:A,\ell_2:B\} = \{\ell_2:B,\ell_1:A\}$, i.e. they unify.  In this case, the subtype relationship is the trivial $T <: T$ one.

Usually when we talk about a language with subtyping we mean one with a non-trivial subtyping relationship on ground types, i.e. types without free variables (which, of course, can and will generate subtyping relationships for non-ground types).  So a system with row polymorphism like Roy's is not a language with subtyping in this sense, though it does have the non-trivial subtype relationship that comes from any implicitly instantiated parametric polymorphic language.  Structural subtyping, on the other hand, explicitly states non-trivial subtyping relationships for ground types.

By row types, I'll mean having a non-trivial unification as described above or an equivalent.  Without this, row types are little more than nested tuples.  Note, row types are independent of parametric polymorphism; I do not mean to imply row variables.  From the argument about $(\cong)$ above, structural subtyping implies row types but not vice versa.  Parametric polymorphism is orthogonal (in the sense the you can have or not have it, there are definitely interactions) to row types or structural subtyping.  A system with structural subtyping + parametric polymorphism subsumes row type + parametric polymorphism (assuming some kind of "record union") in the sense that every term in the latter can be typed with the same type in the former.   The former is just able to type with additional types as well.  Using Brian's example, in a system with structural subtyping and parametric polymorphism answer would have the same type as in the row typing version, but it would also have the subtyping version's type as well.

So you presumably want to compare row type + parametric polymorphism with structural subtyping without parametric polymorphism.  The key benefit of the former (and sometimes drawback) is that it allows you to propagate information globally.  When $\rho$ gets instantiated to { c : Number }, everything that ever unified with it gets instantiated as well.  This may percolate up to the root of your application.  Carrying around row variables through large sections of code is not uncommon.  Subtyping's approach is to forget information: going from a subtype to a supertype loses (type) information.  This can often be what you want: there's a common type you care about and everything else is irrelevant details.  My bias is toward maintaining as much type information as possible and only discarding it explicitly.  The downsides of subtyping's approach is often evidenced by programs that are type correct but only because types were pushed to a(n informationless) "top" type, e.g. the empty record.  Reiterating, parametric polymorphism (in general) preserves type information, subtyping intentionally loses it.


Algorithm analysis of nested loop so I have this code:

for (int i=1; i < n; i=i*5)
      for (j=i; j < n; j++)
        sum = i+j;

And I'm wondering, what's the time complexity of this for loop?

To start off, I know the first line is logn base 5, with an additional check to exit out of the for loop.

Then, for the second line, I have the following:

i = 1
    j = 1, 2, 3,…, n        (n-5^0)+1
i = 5
    j = 5, 6, 7, …, n       (n-5^1)+1
i = 25
    j = 25, 26, 27,…, n     (n-5^2)+1
…
i = n
    j = n                   (n-5^k)+1

But now, I'm stuck. Any help is appreciated.

If you're interested in knowing the big-oh (O) then :
logn (for first for statement) * (n-logn) times

Therefore, n*logn - log^2(n)

For big oh complexity, the complexity for above mentioned nested loops would be:

n*logn (since big-oh is only interested in larger values)

And as David motioned, that link has detailed explaination.


Cover $n$ points in the plane with $k$ circles of radius $1$ I am studying for an algorithms exam and ran into this example problem.

  A circular disk with radius $2r$ can be covered by $7$ circular disks with
   radius $r$; in the following you can use this statement without proof.

  Suppose that we are given a set $S$ of $n$ points in the plane, and we want
  to cover all points in $S$ by a minimum number of circular disks of radius $1$. Let $k$ be the optimal number of disks needed. Propose a polynomial
  time algorithm to produce a covering with at most $7k$ circular disks of
  radius $1$.

I do understand the question but I have no idea where to begin or how to approach this. Should a reduction be used? Or is there a simple and obvious answer? How do you cover $n$ points that you know nothing about? Maybe calculate the distances between them?

I do realize that if the distance between all points is greater than $2$ units, then $k = n$ since every circle of radius $2$ can only cover a single point.

I mainly want to understand the problem so that I can attempt a solution on my own, but a solution to the problem would also be nice, so that I can check my answer later.

Use a greedy algorithm to cover your points with circular disks of radius 2. In other words, repeatedly choose an uncovered point, and cover it with a circular disk of radius 2 centered at the point. Now cover each of your disks with seven disks of radius 1.

Why does this work? Suppose that you covered the points using $k$ circular disks of radius 2 centered at the points $p_1,\ldots,p_k$. It is not hard to check that the distance between any two different points $p_i,p_j$ is larger than 2 (otherwise $p_j$ would have been covered by the disk around $p_i$, assuming $i < j$), and so no circular disk of radius 1 can cover both $p_i$ and $p_j$. This implies that $k$ circular disks of radius 1 are needed to cover the points $p_1,\ldots,p_k$, and so at least $k$ are needed to cover the original set of points. The solution produced by the algorithm uses $7k$ circular disks.


In an NFA that recognizes L(ab) where ab is a regular expression, what is the point of the empty string transition? I'm reading Introduction to Computational Theory by Michael Sipser. He provides the NFA below as one that recognizes the language of the regular expression $ab$.

What is the purpose of the middle two states and the $\varepsilon$ transition between them? Could this NFA be designed without them and still work as intended?

Here's another example of an NFA that recognizes the language described by $aba$. Again, I'm confused by the addition of the empty string transitions and the extra states.

The example is part of the construction to obtain a finite automaton for each regular expression. This construction is known as Thompson's construction and works recursively. Given automata $A(e_1)$ and $A(e_2)$ for expressions $e_1$ and $e_2$, instructions are given to build new automata for the expressions $e_1 + e_2$, $e_1\cdot e_2$ and $e_1^*$. These new automata contain a lot of $\varepsilon$-edges to connect the original parts.

Hence the purpose of the example is not to give an efficient automaton (that is a no-brainer for $ab$) but to illustrate these constructions.


Why is the precision of floating point numbers worse for smaller numbers? Why is the machine error/epsilon higher between a pair of two lower numbers than a pair of two high numbers? For example, between the two smallest numbers possible in 5 bit mantissa and the two largest numbers possible in a 5 bit mantissa. The error for the smallest pair is nearly twice as much as the largest pair?

Another way to phrase this question is why does the machine error differ across an interval?

The potential error is the same in absolute terms for the same exponent.

But since the smaller numbers are about half the size of the larger numbers, the relative error is about twice as high for the smaller numbers.


How does hash table search scales with number of keys? Say, I have one of the standard implementations of a hash table: chaining or open addressing, and my hash key is a pair of strings. Instead of using the hash table with the pair as a key, I can use the first key to get to a "sub" - hash table, and then use the second key to find the element from it.

How do these strategies compare, e.g. if one assumes the key pairs are more or less uniform?

In principle, they're similar in running time and space complexity.

In practice, the first one might have some modest advantages: possibly half as many accesses, less space overhead if some of the "secondary hashtables" were small (e.g., for a particular value of the first key, there aren't many possible second keys).

I would not expect to see a tremendous difference between the two, nor a difference in asymptotic worst-case running time.  Both have $O(1)$ expected running time for all major hash table operations, under some reasonable assumptions.


Is the number of nodes in an ORBDD 2n + 2? Wikipedia says that the number of nodes in a ORBDD (Order Reduced Binary Decision Diagrams) of order $x_1 < x_2 < \dots < x_{2n}$ is $2n + 2$.

But I can't find proof. Anyone?

It doesn't say that. To quote:

  Let us consider the Boolean function $f(x_1,\ldots, x_{2n}) = x_1x_2 + x_3x_4 + \cdots + x_{2n-1}x_{2n}$. Using the variable ordering $x_1 < x_3 < \cdots < x_{2n-1} < x_2 < x_4 < \cdots < x_{2n}$, the BDD needs $2^{n+1}$ nodes to represent the function. Using the ordering $x_1 < x_2 < x_3 < x_4 < \cdots < x_{2n-1} < x_{2n}$, the BDD consists of $2n + 2$ nodes.

It is only talking about that particular function, and demonstrating the difference that different variable orderings can make.

As it says a few lines later:

  There are functions for which the graph size is always exponential — independent of variable ordering.

Bryant [1] proves several functions have exponentially sized OBDDs, regardless of the variable ordering (see for example Theorems 2 and 4 in the paper).

References

Randal E. Bryant, "On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication", IEEE Trans. on Computers, 40(2):205-226, 1991.


Decidability of Turing machines and misconceptions on the halting problem In an online discussion on Turing machines and decidability recently, I blatantly theorized that any problem about a specific single Turing machine must be decidable, the question of undecidability only arises when we are talking about a class of a problem.
As a rebuttal to the original argument someone replied that if we have a Turing machine and we give it an input w it'll be undecidable to say will it halt or not and was proven by Turing himself.
Is this a correct argument because skimming through wikipedia it looks that's not what Turing actually proved

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist

What he proved was that no general solution exists for all possible program-input pairs and not that we can't have a specific algorithm to solve this on a single machine (e.g if we take a halting Turing machine a simple solution would be to say yes for all inputs).
In support of my original statement look at the PCP, no general solution exists but if we are given two string we can sure brute-force them by looking at all possible subsequences and tell whether a correspondence exists or not.
So what I am asking here does my original statement hold weight and what exactly did Turing proved.
Edit: I've realized this question doesn't make much sense and is just not useful to anyone. But because it has answers it can't be deleted.

The problem of deciding whether, given a Turing machine $T$ and a word $w$, $T(w)$ halts is undecidable.
If a Turing machine $T$ is fixed, the problem of deciding whether, given a word $w$, $T(w)$ halts might or might not be decidable (depending on the choice of $T$).
As an example in which this problem is decidable consider the trivial Turing machine $T$ that immediately halts.
As an example in which this problem is undecidable consider an universal Turing machine $T$ in which $w$ encodes a pair $\langle M, w'\rangle$ where $M$ is some other Turing machine, and $w'$ is $M$'s input. The machine $T$ simply simulates $M'$ on $w'$. Clearly if we could solve the halting problem for this fixed $T$ and any $w$, we could also solve it in the general case.
If a word $w$ is fixed but the machine $T$ is part of the input of the problem, then the problem is undecidable regardless of $w$.
Suppose towards a contradiction that this problem was decidable, then given a Turing machine $M$ and a word $w'$ as input, you could decide whether $M(w')$ halts. To do so you construct a new Turing machine $M'$ that clears its tape, writes $w'$, and then simulates $M$ (an encoding of such a machine $M'$ is computable given $M$ and $w$). Clearly $M'(x)$ halts iff $M(w')$ halts, regardless of $x$. In particular, for $x=w$,  $M'(w)$ halts iff $M(w')$ halts. It then suffices to decide whether $M'(w)$ halts, which we can do by our hypothesis.
If both a Turing machine $T$ and a word $w$ are fixed, then the problem does not make much sense since you do not have a class of instances anymore... Notice that, in this case, either $T(w)$ halts or it does not, meaning that one of the following two Turing machines must answer correctly: 1) Always halt and accept. 2) Always halt and reject.


Multi-agent randomized behavior In Artificial Intelligence: A Modern Approach Edition 3, Page of 43, At Single Vs. Multi-agent section's last line, Writer says,

  In some competitive environments, randomized behavior is rational
  because it avoids the pitfalls of predictability.

Can someone help me understanding this line? Specially, what does he mean by pitfalls of predictability ?

Someone who owns (an abstract of) the book might be able to give you a better contextualized answer, but in general models and simulations are subject to certain 'laws' that the systems they represent usually are not. In the case of multi-agent systems, one of these is the fact that some agent gets to act first on a given time step, even though the designer often assumes and intends for them to act in parallel (this is the result of computers being incapable of truly parallel computation). If the same agent were to consistently act first, that could introduce significant bias into the system. This is probably what the author means with the pitfall of predictability and why randomization is important; so that we can prevent (to some extent) these sorts of issues.


Must the champion of an entire tournament beat the champion of a possible tournament among other players? I have a list of "players" of a "tournament". Any two adjacent players may "compete", which results in the loser being thrown out of the tournament. Winning is not transitive. The winner of a given competition between two players is known, but the order of competitions is not. Suppose that I have some tournament of the form $p_1, p_2, p_3, ..., p_n$ and I know that $p_1$ may win the entire tournament (depending on the order of competitions). Can I show that $p_1$ must beat some possible winner of a tournament on just $p_2, p_3, ..., p_n$?

I originally came to this while proving the correctness of an algorithm to determine the list of possible winners of a general tournament, but this specific subproblem is giving me trouble.

To begin an attempt at a solution, I offer that in the contrary case, $p_1$ must only compete against and beat some sequence of "losers" (players who cannot win the tournament on just $p_2, ..., p_n$ no matter the order played), with no winners losing to $p_1$. This implies that at some point, a loser must defeat a winner. This may be impossible? I can't prove that, and I don't know whether that's even true.

Here is a proof by induction. The base case, $n = 2$, is clear.

Now consider a tournament in which $p_1$ wins. Suppose first that the first competition doesn't involve $p_1$. Let the new set of players be $p_1,P$. By induction, we know that $p_1$ must beat one of the possible winners of the tournament in $P$, say $p_i$. Since the first competition didn't involve $p_1$, $p_i$ can also win the tournament on $p_2,\ldots,p_n$, completing the proof in this case.

Suppose next that the first competition has $p_1$ beating $p_2$. Applying the induction hypothesis, we know that $p_1$ must beat one of the possible winners of the tournament in $p_3,\ldots,p_n$, say $p_i$. If $p_i$ beats $p_2$, then $p_i$ can also win the tournament on $p_2,\ldots,p_n$, and we're done. If $p_2$ beat $p_i$, then $p_2$ can win the tournament on $p_2,\ldots,p_n$, and so we're again done (since in the first competition, $p_1$ beat $p_2$).


HALF CLIQUE - NP Complete Problem Let me start off by noting this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please.  With that said, here is the problem I am looking at:

  Let HALF-CLIQUE = { $\langle G \rangle$ | $G$ is an undirected graph having a complete
  subgraph with at least $n/2$ nodes, where n is the number of nodes in $G$
  }. Show that HALF-CLIQUE is NP-complete.

Also, I know the following:

In terms of this problem a clique, is defined as an undirected subgraph of the input graph, wherein every two nodes are connected by an edge.  A $k$-clique is a clique that contains $k$ nodes.
According to our textbook, Michael Sipser's "Introduction to the Theory of Computation", pg 268, that the problem CLIQUE = {$\langle G,k\rangle$ | $G$ is an undirected graph with a $k$-clique} is in NP
Furthermore, according to the same source (on pg 283) notes that CLIQUE is in NP-Complpete (thus also obviously in NP).

I think I have the kernel of an answer here, however I could use some indication of what is wrong with it or any related points that might be relevant to an answer.  This is the general idea I have so far,

  Ok, I'd first note that a certificate would simply be a HALF-QLIQUE of $\text{size} \geq n/2$.  Now it appears that what I would need to do is to create a verifier that is a polynomial time reduction from CLIQUE (which we know is NP-Complete) to HALF-CLIQUE.  My idea would be that this would be done by creating a Turing machine which runs the turing machine verifier in the book for CLIQUE with the additional constraint for HALF-CLIQUE.

This sounds correct to me, but I don't really trust myself yet in this subject. Once again, I would like to remind everyone this is a HOMEWORK PROBLEM so please try to avoid answering the question.  Any guidance which falls short of this would be most welcome!

Judging by your description and comments, you might be helped the best by an exact description on how reductions can be used to prove NP-completeness:

A problem is NP-complete iff it is in NP and it is NP-hard. This means that any proof of NP-completeness has two parts: a proof that the problem lies in NP and a proof that it is NP-hard.

For the first part, you have to show that YES-instances can be verified in polynomial time using some suitable certificate. Alternatively, you can show the problem can be solved in polynomial time by a non-deterministic Turing machine, but this is not usually done as mistakes are easily made.

In your case, this comes down to proving that for every graph with a $n/2$-clique, you can find some proof that there is indeed such a clique, such that, armed with such a proof, you can check in polynomial time that there is indeed such a clique.

For the second part, you have to show that the problem is NP-hard. This is in nearly all cases shown by proving that your problem is at least as hard as some other NP-hard problem. If HALF-CLIQUE is as least as hard as CLIQUE, it must also be NP-hard.

You do this by proving a reduction FROM CLIQUE, TO HALF-CLIQUE. You 'reduce' the problem, making it 'easier'. You say "Solving CLIQUE is hard, but I have proven that you only need to solve HALF-CLIQUE to solve CLIQUE". (many people, even experts, occasionally say this the wrong way around :))

There are different types of reductions: the reduction that is most commonly used is the one where you map instances of in this case CLIQUE to instances of HALF-CLIQUE whose size is at most polynomially larger, in polynomial time. This means that if we can solve HALF-CLIQUE, then we can also solve CLIQUE by chaining the algorithm and the reduction.

In other words, we must show that we can solve CLIQUE if we can solve HALF-CLIQUE. We do this by showing that for every instance for CLIQUE, we can design an instance of HALF-CLIQUE such that the instance of CLIQUE is a 'yes' instance iff the instance of HALF-CLIQUE is a 'yes' instance.

The proof therefore starts like this: given a graph $G=(V, E)$, I can create some graph $H=(V', E')$ such that $G$ contains a $k$-clique iff $H$ contains a $n/2$-clique. I'll leave this part to you (this is the part that requires creativity, the part that is about the specific problem at hand).


"Low-High" sort divide and conquer with merge... how small to make the subproblems for good efficiency? For a mental exercise, I decided to try out my own simple sorting algorithm which processes an array of integers in any order, and as it passes thru them all, records the highest and the lowest.  So imagine an array of size 10 with elements (9, 2, 4, 1, 6, 8, 5, 3, 7, 0) in that order.  We want the algorithm to sort them into (0, 1, 2, 3, 4, 5, 6, 7, 8, 9).  There are many ways to implement this, but the simplest I found is to use a 2nd array (call it B).  After the first pass thru A, B[0] will become 0 and B[9] will become 9.  Those are the smallest and largest elements in A.  I also have an array of flags telling me which numbers from A I already "plucked" so I will skip over those on any subsequent passes.  For simplicity, I rescan the entire array of 10 elements even on the 2nd, 3rd, 4th... passes to find the lowest and highest remaining pairs from A.  This is obviously a slow algorithm since it is O($n^2$).

So I got this working quickly because it is so simple, however, it is very slow as N (the # of elements in the array to be sorted) becomes large.  For example, if N=1000 vs. N=500, the N=1000 takes 4 times as long.  N=2000 takes 4 times as long as N=1000....

So what I am wondering is why not have the program first break up the array into smaller arrays, sorts those, and then just merge the results into 1 big array.  The question is, what is the optimal final (smallest) size array "chunks" we should work on?  Breaking it up has overhead, but an n squared algorithm can go so much faster operating on small chunks, then merging the results which takes O(N) time.

For example, suppose someone wants to sort 1 million random integers and they pass me an array of those.  I cannot just use my simple algorithm on that, it would take forever and a day.  But is there an optimal way to break it up into pieces, or does that depend on too many things such as the compiler/interpreter, cache memory size...?  Should I just try many different subarray sizes such as 1024, 512, 256... and just pick the best for my computer, timing each one?  I would suspect that if breaking the subarrays too small, the overhead of doing that and merging all the tiny little pieces (such as arrays of size 2) might not be optimal, especially on a slow computer and/or in an interpreted environment (like I am using).

Also I am interested in the time complexity as the big initial array gets chopped into pieces.  For example, with N=1000, I would make 1000 passes on 1000 numbers so 1 million "examinations" (array references) which is O($n^2$), however if I "chop" only once, now I would have 2 * (500$^2$) = 1/2 million + 1 merge, 4 sub-blocks would be 4 * (250$^2$) = 1/4 million but with 3 merges.... What I am thinking is eventually there will be a point of diminishing returns, meaning that chopping any smaller is of no advantage (and may actually slow things down).  Question is, is trial and error the only way to find this point?

My plan of attack is to simply try many different final block sizes such as 1024, 512, 256.... and just time them all. I chose a power of 2 block sizes cuz they can be halved in size easily without any fractions.  For testing purposes, I would force the array sizes to be a perfect power of 2 so they divide perfectly.  My goal is not a generic sorting algorithm but rather more of a divide and conquer optimization speed question.

So in array B, there would be sorted subarrays which I can then merge back into A, so the storage for this algorithm is roughly 2N.

Also regarding the merge part of this (or any sort using merge), why not just start with sorted arrays of size 1 and work your way up?  For example, if we had an array of size 1024, start by merging adjacent pairs of numbers, then merge those pairs into quads...


Halting Problem without self-reference: why does this argument not suffice (or does it)? I'm trying to find a way to explain the idea of the Halting Problem proof in as accessible a manner as possible (to undergrad CS students). The simplest argument I have found is this one; this is precisely the style of treatment I am aiming for. However, the self-reference (in particular, checking if a program halts on itself) is not the most didactic.

What I'm wondering, as a proof sketch, is why we could not simplify even further and say: if we assume a program H(P,I) for the Halting Problem that halts with true if P(I) halts, and halts with false otherwise, then we could create a program of the form:

def Q(J):
  if H(Q,J) then loop forever
  else halt

... which is a valid program if and only if the Halting Problem is a valid program.  We can then ask: what should H(Q,J) return on any arbitrary value for J? We see a contradiction in both possibilities, and we conclude that since the existence of H allows us to construct the contradictory program Q, thus a program of the form H cannot exist.

There is still some self-reference here in that the program Q checks whether or not it halts on the current input (and does the opposite), but for me, this seems much more intuitive than setting up a situation where we need a call of the form P(P) or H(P,P), etc. However, I have not seen this simpler argument used, and I think it would have been were it valid. Hence my questions are:

Is the above argument sufficient as a proof (sketch) of the Halting Problem?

If so, why do so many arguments go with a confusing step of the form P(P) or H(P,P)? (Is it just to remove the unimportant "input" from the equation?)
If not, what's missing?

There are a variety of related questions on this topic, such as:

Halting problem without self-reference
Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

I also found mention of the proof based on Berry's paradox, which is quite appealing. Still, I have not yet managed to convince myself whether or not the specific argument above works (even if just for my own understanding; I feel I am perhaps missing something stupid and would like to know what it is).

I don't think this is a good way to present the halting problem, because it sweeps a critical issue under the covers in a sneaky way.  I suggest sticking with a more standard presentation, such as the one you linked.  If you want to find a way to explain it in a way that minimizes the technical content, the presentation in this video is surprisingly accessible, and remains true to the logic of the standard proof.

On to the difficulties with your proposal.  In your proposal, it's not trivial to write down the code for such a Q.  Think about what it means to have the line

  if H(Q,J) then loop forever

Recall that the first argument to H is a bit-string that contains the code /  algorithm / Turing machine -- it's not a pointer to the function, but a string.  Naively, this seems to mean that we include a hardcoded string that contains the source code for Q, inside the code of Q.  But that's not possible.  Suppose the code for Q takes 100 characters.  Then we need to hardcode a 100-character string constant inside the definition of Q, plus we also need some more characters for the rest of the logic -- and that adds up to more than 100 characters.  If you think about it, it's obvious that we can't have a string constant inside the code of Q that is the code of Q, because it would be too long.

Maybe you're thinking that's not what you had in mind.  Maybe you were thinking that the programming language will have some built-in API to get the code of the current function, so actually the code you were thinking of is something like:

def Q(J):
  if H(get_source_code_of_current_function(),J) then loop forever
  else halt

OK, fine.  This proves that the halting problem can't be solved for code written in any programming language that has a get_source_code_of_current_function() API.  However, my favorite programming language doesn't have such an API.  So, this proof doesn't prove anything about my favorite programming language -- perhaps the halting problem is solvable for my language, who knows?  Similarly, Turing machines don't have such an API, so this doesn't prove that the halting problem for Turing machines is undecidable.

And that's a major flaw in your proof.  And it's a flaw that is subtle and not at all evident.  I don't think it's pedagogically a good idea to present a proof that "looks valid" on the surface but is actually, once you dig into it deeper, flawed.

Now, it is possible to rescue your proposed proof.  It actually is possible to construct a function Q that works the way you said; you basically need it to be a quine.  I suppose in principle you could explain the idea of quines, then present your proof and explain how to implement a function Q using those ideas.  But that seems like a bad idea to me, from a pedagogical perspective.  Quines are mind-bending and mysterious and freaking hard to understand.  A student who doesn't understand quines won't understand your proof.  And it makes the proof of undecidability for the halting problem look a lot more mysterious than it needs to be.  So this does not seem to me like a more accessible way to understand the halting problem.


How to compute the language {ww | w ∈ {0,1}*} within a Multitape Turing Machine? I'm trying to compute a language defined as { ww | w ∈ {0,1}* } in JFlap using a Multitape Turing Machine. It seems a hard problem because there is no delimiter to know when the word w is ended.

I already checked this and this question, but this didn't helped me at all. The answers from "Construct Turing Machine which accepts the language $ww$" talks about deterministic machines and one answer just cite non-deterministic, but dont give details on how this design can be achieved for the given problem.

I've found this algorithm, but this seems very confusing for me (I don't understand the first stage (for example), so I can't reproduce this answer at JFlap).

// Stage 1: Check length is even, change as / bs to As / Bs
while a or b {
    change a to A or b to B & move R
    while a or b move R
    move L
    change a to A or b to B & move L
    while a or b move L
    if A or B move R
}

// Stage 2: Change As and Bs in first half to as and bs
if Blank halt
if A or B move L
while A or B change to a or b & move L
if Blank move R

// Stage 3: Compare first and second halves
while true {
    if a {
        change a to A & move R
        while a or b or Blank move R
        change A to Blank & move L   // fail if B
        while a or b or Blank move L
        if A or B move R
    } else if b {
        ... similarly ...
    }
}
if Blank halt

Can someone clarify this question to me? How can I achieve the first stage in a multitape Turing machine? How can I proceed to solve the problem?

P.S: It must be a multitape Turing machine.

Regarding the first part:

// Stage 1: Check length is even, change as / bs to As / Bs

and

// Stage 2: Change As and Bs in first half to as and bs

Are to find the word middle, then just compare the first half against the second half. Here is a SIMILAR picture for you at JFLAP:

As you can see, at state "q2", I came back to the tape's beginning, to really starts the computation at the state "q3".

After got at the state "q3" you can jump straight to you algorithm part:

"// Stage 3: Compare first and second halves"

And complete your Turing Machine. But this was your question 1.a) and now you want to solve the question 2.a)

To do it, you will only need to use the step "// Stage 3: Compare first and second halves", from you algorithm.

To do it using a Multi-Tape Turing Machine, you are going to need 4 tapes, the word is to be placed at the tape 1 and the others tapes must to be clean, i.e., contain only blank symbols:

First step, if the tape 1 has only the blank symbol, accept the language.

Second step, if  the only symbol not marked at tape 1 is the blank symbol, reject the language.

Third step, is to copy the first symbol not marked from the tape 1 to the tape's 2 end. Then mark it at the tape 1.

Fourth step, is to copy the whole tape 1 to the tape's 3, and the tape 2 to the tape 4.

Fifth step, is to compare both tapes 3 and 4 are equal using yours algorithm step "// Stage 3: Compare first and second halves", but instead of failing to accept the language, go to the step Sixth.

Sixth step, if they are equal accept the language. If they are not, go to the Second step.


Show that checking if there exists word not containg patterns from list is in $PSPACE$ There are given:

alphabet $Σ$ with some symbols $a,b$.
list of forbidden patterns

Result:   Is there exists word of form $a\Sigma^*b$ such that it doesn't contains (as subword) any of word from
list (list contains many words, expressed by patterns).   Show that
this problem is in $PSPACE$.
Example to better understand patterns:
$bbaaacb$ contains a word $a??c$, but $aacba$ doesn't contain $a??c$,
where $?$ is some special symbol in $\Sigma$
So patterns are like words with holes (?)

My approach is follwing:
Let $k$ will be max length among all patterns.  There is no sense to consider longer words than $k$ because if exists word longer than $k$ such that it contain none of words from forbidden list then also exists word of length $k$.
So, using the fact that $PSPACE = NPSPACE$ we can guess word of length $i=1...k$ and check if it contains subword from forbidden list. Matching is easy to do in $NPSPACE$.
I am not sure about corectness of using nondeterminism. What do you think ?

i think you are in the right direction, i will try to expand your answer a bit.
first we want to prove that a problem is in PSPACE, which means there exists a TM that solves the problem with a polynomial space tape.

let M be a NTM that receives $w=<Σ,list>$ and does the following algorithm:

1) guess word of length $i=1...k$ given the $Σ$.this can be done in polynomial space depending on our input, since $O(k)=O(|w|)$ space.

2) check if there exists a pattern in the list which matches any of the strings of the word. this phase needs describing how exactly it can to be done, but it can certainly be done in polynomial space of $|w|$. hint: use 2 special characters to check each sub-string at a time.

and now since $PSPACE=NPSPACE$ (as you mentioned) ,if there exists a NTM that solves the problem in Polynomial Space tape we can conclude the problem is in $PSPACE$ and your solution was in a good direction.


Showing that there exists an algorithm, that converts NFA to DFA under some cirumstances We are given NFA $A$, which for every input word $w$ has at most 10 runs over word $w$, beginning at the starting state.
Show that there exists an algorithm, that converts such NFA to DFA in polynomial time. We don't need that algorithm to work if given automata is not such a NFA.

I think we need to construct DFA with $2^{10}$ states, such that every state would correspond to some run in the NFA - but im not sure about the details.

Any ideas?

The main idea is that if the NFA has at most 10 runs over each word, then when reading a word, at any given point the NFA can be in at most 10 states. Therefore in the powerset construction it suffices to consider sets of at most 10 states, of which there are polynomially many.

All remaining details are left to you.


Reduction for the proof that COMBI $:= \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$ is NP complete Given the Language $COMBI := \{\langle G,k \rangle | G$ has Clique  $\geq k$  or Independent Set $\geq k\}$. Proof that Combi is NP-complete.
I tried to reduce Clique <=p Combi. I had two different ideas:

Let $f(\langle G,k\rangle) = \langle G,k\rangle$ so $\langle G,k\rangle \in$ CLIQUE $\Rightarrow  f(\langle G,k\rangle)$ is trivial.
Though I am puzzled with the case $f(\langle G,k\rangle) \in$ COMBI $\Rightarrow \langle G,k\rangle $. What is when I have only an Independent set $\geq k$ within $\langle G,k\rangle$ and no Clique $\geq k$. Then it would be in COMBI but not within CLIQUE.

Let $f(\langle G,k\rangle) = \langle G´,k\rangle$ where $G´= \overline{G} \cup G$ as disjunctive union (two different components) and $\overline{G}$ is the complement graph so $\langle G,k\rangle \in$ CLIQUE $\Rightarrow  f(\langle G,k\rangle) \in$ COMBI is trivial again, but the other case seems to be flawed due to the same reason as in the first try.

Where am I going wrong or do I have to make a completely different reduction $f$?

Let $\langle G=(V,E), k \rangle$ be an instance of CLIQUE with $k \ge 1$, and let $n=|V|$.
Let $S$ be a new set of $n$ additional vertices.
Construct a new graph $G'=(V', E')$ with $V' = V \cup S$ and $E=E' \cup (S \times (E \cup S))$.
Now consider an instance $\langle G', n+k \rangle$ of your problem.
If $G$ has a clique of size $k$ containing the vertices in $C \subseteq V$ then $G'$ has at least one clique of size at least $n+k$. Pick, e.g., the clique induced by $C \cup S$.
If $G'$ has a clique or an independent set of size $n+k$ then let $C$ be the set of vertices that induce such a clique or independent set set.
Since $C \cap S \neq \emptyset$ and $|C| \ge 2$, $C$ cannot be an independent set and therefore it is a clique. Then $C' = C \setminus S$ is a clique of size at least $n+k-n=k$ that is also a subgraph of $G$.


Set of Turing machines that halt after exactly 14 steps Let $M_i$ be the Turing machine with Gödel number $i$. Let
$$A = \{i \mid M_i \text{ with input \(x\) halts after exactly 14 steps}\}$$
Is the set $A$ recursive?

I assume you mean $M_i$ is a TM which is determined by Gödel Number $i$ such that from $i$ one can always construct $M_i$ in finite time and that $A = \{i \mid M_i \text{ halts after exactly 14 steps on \(x\) as input, where $i$ is a G}\ddot{o}\text{del Number}\}$ where $x$ is constant.

$A$ is recursive if there exists a TM for $A$ that always halts.

Such a TM can can be constructed as follows:

If $i$ is a Gödel Number construct $M_i$, else $i \notin A$, halt.
Run $M_i$ on the constant $x$ for 14 steps, if it halts after exactly 14 steps then $i \in A$, else $i \notin A$, halt.

Both 1 & 2 always halt which means that the TM always halts. So $A$ is recursive.


What are the tradeoffs in compiler development effort related to CISC vs. RISC? What advantages and disadvantages does a CISC instruction set have relative to a RISC instruction set with respect to the ease of developing a functioning compiler and the ease of developing a highly optimizing compiler?

CISC vs. RISC is just the wrong distinction.  There are some instruction set design decisions that matter to the compiler writer and others that don't, but this simply isn't one of them.

Variable instruction length vs. fixed instruction length pretty much doesn't matter.  Writing an assembler for variable instruction length requires you to do a little more bookkeeping, but once its done you never have to worry about it again.

You either want a lot of general-purpose registers or just one (e.g. an accumulator).  Register allocation is hard.  So hard it is difficult to even figure out the input parameters you are trying to optimize over (you'd like to minimize the number of spills at runtime, but you usually don't know how often any instruction is going to execute at runtime.)  If you have only one register then where you have to spill is pretty obvious, and if you have more registers than you need then a greedy heuristic will get you something pretty close to optimal.  When you have only half as many or a third as many registers as you need then good heuristics start to matter a lot.

Registers that are special-purpose (used implicitly in a few instructions) are fine, and registers that are general-purpose (can be used for different things in lots of different instructions) are fine, but trying to make a special-purpose register also general purpose is hard for the compiler.  For example the MIPS architecture's jump-and-link instruction uses R31 as the implicit place to store the return address.  R31 can also be used as a general purpose register, but the compiler has to "special case" it, so that's usually an optimization that takes a few years to get into the compiler.

Having more than one way to do the same thing is generally not helpful to the compiler writer.  The internal representation of the compiler is usually a graph where the nodes correspond to operations and the edges correspond to operands.  If there are multiple ways to do something (for example, lots of different addressing modes) then this becomes a graph tiling problem, which is hard.  The result is that most compiler writers just ignore any addressing modes beyond the simple ones.  Given the way modern microarchitectures work the main cost of not using the more complex addressing modes is that the instruction sequence takes up more space than it would in the optimal case.  There's a classic story from the 1980s about the VAX.  If I remember correctly, the VAX had a special call instruction that would also push arguments onto the stack.  It turned out that the longer instruction sequence that individually pushed the arguments and then did the call separately was faster.

Large constants are a pain, so this is a place where fixed-length instructions hurts rather than helps.  Sparc had something like 12 bits for constants, MIPS has 16, which is better (because then you can construct any 32-bit constant with at most two instructions.)  The larger the available constant fields are the less likely it is that you have to construct multi-instruction constant construction sequences.  (This is even more painful for PC-relative jumps and branches where usually you can fit a relative offset into the constant field, but sometimes not, in which case you need to save the PC in a register and manually add and subtract the appropriate constant.  Ick.)

Alignment can be an issue sometimes.  For example: some early SIMD instruction sets required that source memory operands be aligned at cache-line boundaries, which is almost impossible for the compiler to guarantee without inserting a bunch of extra code.  To be useful a SIMD instruction set needs to allow cache-line-unaligned loads, at least (aligning stores is easier when the loads can be unaligned, so that's less important.)


Unprovable Post correspondence problem instance Since there is no algorithm for the post correspondence problem, there exists an instance of this problem such that we can neither prove that the instance is positive nor prove that the instance is negative, i.e. an unprovable instance of this problem. Otherwise, for each instance, a proof that the instance is positive or a proof that the instance is negative exists and we could just use an algorithm which enumerates all the possible proofs until it finds such a proof, it always terminates and it correctly answers yes/no according to the proof found.

For finding such an instance, I pick a random instance, I try with a semi-decision procedure and, after some time, if this doesn't work, I try to prove that the instance is negative. Since this heuristic has always finished, I have not find such an instance until now, but it should be possible.

This is not specific to the Post correspondence problem, an unprovable instance should exist for all undecidable problems.

The argument you outline doesn't actually work. In fact, for any specific PCP instance, there is an algorithm which produces the right answer; it is either "output 'yes'" or "output 'no'". It is only when you require the algorithm to work for all the infinitely many instances that undecidability enters the picture (since an algorithm needs to be finite, you cannot just cobble together all the individual solutions).

Now it is true that given any particular PCP instance, you could just enumerate the potential solutions. The problem with this is that while for solvable instances, you will eventually find the solution, for (non-trivial) unsolvable ones, you will never get an answer. That is, what you have here is a semi-decision procedure.


Some explanations needed about Negation in Gentzen's Natural Deduction rules I'm beginning to have an understanding thanks to some videos relating to "Proposition as Types". But, I don't come from a theoretical CS background, so maybe I'm blocked probably a bit by notation...

Given that I have understood, Conjunction, Disjunction, Implication,

I'm stumbling on Negation:

intro:
[A]
 /\
---
¬ A

elim:
A ¬A    /\
----   ---- .
 /\     D

It comes from an extract of the Gentzen paper during a P. Wadler talk Proposition as Types, and I'm stuck by the meaning of the symbol resembling /\. What is this symbol called, and what is the meaning ?

Moreover, I have no clue about that D (which was not introduced) and . in:

 /\
---- .
 D

Is it anything related to _|_ bottom in Haskell, or else the Void empty type?

All those missing pieces makes me unable to grasp the meaning and how to apply these rules.

EDIT: I was also having difficulties with the Universal Introduction rule and this video covers the topic.

I'm guessing your first rule is:

  \begin{align*}
&[A]\\
&~~\vdots\\
&~\bot\\
&\overline{\lnot A}\qquad (I\lnot)
\end{align*}

This means that in order to derive $\lnot A$ one must first assume $A$ (that is $[A]$) and derive a contradiction ($\bot$), the dots between mean a finite number of steps.

  $$ \frac{A \quad \lnot A}{D} \qquad (E\lnot) $$

This latter rule with $D$ seems to be ex falso quodlibet, since:

$$ \frac{A \quad \lnot A}{\bot} \qquad (E\lnot) $$

therefore:

$$ \frac{\bot}{D} $$

it says that you can derive anything (some $D$) from a contradiction.

Those $(I\circ)$ and $(E\circ)$, where $\circ$ is some operation mean Introduction-Elimination rules. In Gentzen's formulations all rules come in pairs.


Complexity of Two problems graphs with cycle I want to determine the complexity of these two problems (with a given k):

1) Determine if the graph G has a cycle of length less or equal than k;

2) Determine if the graph G has a cycle of length equal or more than k.

For the first problem, I think it is NP-complete because it is NP (but why?) and because we can reduce the HAM-CYCLE problem to it (but how?)

I don't know what to say about the second problem. Can you help me solving this and can you help me telling me what is a good method to solve these kind of problems?

The first problem can be answered by finding the length of the shortest cycle in $G$, a parameter known as the girth of $G$. Indeed, if $G$ has girth $g$ then $G$ contains a cycle of length at most $k$ iff $g \leq k$. You can use BFS to find the girth efficiently, see for example these course notes. Therefore this problem can be solved in polynomial time.

The second problem is NP-complete by reduction from Hamiltonian cycle, as you mention (just choose $k = n$).


Convert regular expression to DFA How do you construct a DFA from a  language that has a + sign? e.g. $L = \{(a+b)\}*$

In this case + stands for the OR-operation. So the automaton is indifferent using an $a$ transition or a $b$ transition.

It's sufficient to construct an automaton with one state which is initial and final state and having one transition labeled with a, b.


Newbie Random NFA DFA questions Can't seem to answer these questions, I'm sure the answers are out there somewhere but I don't really know what keywords to use to find them. Any answers or good sites/ documentation would be much appreciated. And please don't say wikipedia, the language used is a bit out of my comprehension at this moment.

Is it correct to assume that an NFA can be converted into multiple
versions of a DFA?
Are there different methods for doing so and would they all be
considered correct assuming they give different answers?
If an NFA has the transition relation d{ (q0,e,q1), (q1,e,q1),
(q1,e,q2) } would it be correct to write it out as d(q0,e,q2)?
(e standing for epsilon, q0 being initial state and q2 being final)
Is it correct to assume that every state in an NFA has a "hidden" e
transition? Essentially can you assume that every state in an NFA has an e* transition.
Is it bad practice when converting to have multiple NFA states as one
DFA state?

Alternatively is there some way I can test my conversions out and make sure they are correct either using a program or some other way.

Apologies for the noobiness of the questions.

Answers to your questions in given order: (a) Yes, an NFA could in principle be converted into multiple distinct DFAs for the same language.  Note however: There is always a unique DFA having a minimum number of states; other DFAs would have to be 'redundant' in some sense.  (b) There may be different methods, though I am only aware of one.  As long as the resulting DFA recognizes the same language, I would say the conversion method would be considered correct.  (c) No, the expression d(q0,e,q2) would NOT be correct; however for every transition function $d$ there is a corresponding transitive closure $d^*$ for which that would be a valid expression.  (d) No, it is not correct to assume the existence of 'hidden' e transitions; all defined transitions, e or not, must be given explicitly, but it is permissible to leave some transitions undefined (and any NFA-to-DFA converter must handle that case).  (e) Not only is it NOT 'bad practice' to have multiple NFA states as one DFA state, that is the standard tactic used by the canonical NFA-to-DFA procedure.


Massalin's Synthesis Quajects equivalent to ASM generating macros used in Game Oriented Assembly LISP? Alexia Massalin's Dissertation on Synthesis was a Phd thesis on Operating Systems that contained a concept called 'Quajects' (see Chapter 4).

This is some additional commentary on the Phd Thesis.

Best I can work out - a Quaject is construct that generates Assembler customised for the function being used at the time. (Perhaps like a JIT).

The project that I've seen that came closest to this was Game Oriented Assembly LISP (GOAL), a framework used in Crash Bandicoot that used ASM-generating LISP macros to speed up the development iteration process and generate the production code.

Can we say that the Macros generating ASM in GOAL were quajects? (yes or no question - please explain why if yes, and reasons if no.)

As I see it, a Quaject is a kind of software component in the sense that it has a provided interface (the callentry functions), which contains the functions it offers, and a required interface (the callout functions), which contains the functions it needs  to operate. The callback part of the interface is for call back functions, which are functions that are available to call the caller of a function. (In Java you cannot call the caller unless an explicit reference is passed.)

I don't think it is correct to say that "a Quaject is construct that generates Assembler customised for the function being used at the time." For example, in Section 4.1.4 of the thesis it states that

  Higher-level kernel services are built by composing several basic
  quajects.

So the quajects are the ingredients that are used to build the custom services. They do not build them.

GOAL seems to be a variant of Scheme that allows inline assembly language, which I can image allows quite some flexibility in the programming. The language is compiled to assembly. The assembly language it includes is not in the shape of any sort of component, as far as I can tell.

Based on this, I would say that the answer to your question is no.


Are all DFAs also NFAs? Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?

That depends on how pedantic you are. Morally and semantically speaking, every DFA is an NFA in which there is a unique arrow exiting every state for every character in the alphabet, and there are no $\epsilon$ transitions.

Syntactically speaking, it depends on your definition: the transition function could be encoded differently, so that the transition function of a DFA might not be "legible" for an NFA simulator.

I would not worry too much about the syntactic viewpoint.


If P=NP, are there cryptosystems that would require n^2 time to break? If P does equal NP, will it still be possible do design a cryptosystem where the optimal cryptanalysis algorithm takes, say, the square of the time taken up by the legitimate encryption and decryption algorithms? Do any such algorithms already exist?

Yes — in fact, the very first public-key algorithm that was invented outside an intelligence agency worked like that! The first publication that proposed public-key cryptography was "Secure Communications over Insecure Channels" by Ralph Merkle, where he proposed to use “puzzles”. This is a key agreement protocol.

Alice sends $n$ encrypted messages (called puzzles), each containing a unique identifier $I_i$ and a session key $K_i$, with the keys for each messages chosen among a set of $n$ keys. This takes $O(n)$ time ($O(1)$ per message).
Bob decrypts one of the messages by brute force and sends back $I_i$ encrypted with $K_i$. This takes $O(n)$ time ($O(1)$ per key, times $n$ possible keys).
Alice tries all the keys to decrypt the message. This takes again $O(n)$ time.

Each party requires only $O(n)$ computation, but an eavesdropper who wishes to find $K_i$ needs to try out half the puzzles on average to calculate the right key (the eavesdropper does not know which message Bob chose to decrypt), so the eavesdropper requires $\Theta(n^2)$ computation on average.

After Merkle invented his puzzles, Diffie and Hellman published a key agreement protocol based on the discrete logarithm problem. This protocol is still used today.

The problem with Merkle puzzles, or anything where the amount of work to be done by the attacker only increases as the square of the legitimate party, is that it takes huge key sizes and amounts of computation to achieve a decent security margin.

In any case, it is not clear that merely proving that P=NP will invalidate existing cryptographic algorithms. If the polynomial increase is a high enough power, it might not matter so much in practice. See How will security need to be changed if P=NP?, Can we say that if P=NPP=NP there is no CPA secure public key encryption?, P = NP and current cryptographic systems, …


Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree There is  a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal.

For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).
For each internal node:
if any of its children is not selected, then select this node.

How do I prove that this greedy strategy gives an optimal answer? That there is no vertex cover smaller in size than the one that the above algorithm produces?

We first observe the following: There is an optimal cover $C$, and no leaf is in $C$. This is true since in any optimal cover $X$ you can replace all leaves in $X$ with their parents, and you get a vertex cover which is not larger than $X$.

Now take any optimal cover $C$ that does not contain leaves. Since no leave is selected, all parents of the leaves have to be in $C$. In other words, $C$ coincides with the greedy cover on the leaves and their parents. Next, we take out all edges that have been covered already. We can now apply the same argument again: In the remaining tree, no leaf needs to be selected, but then their parents have to be selected. And this is exactly what the greedy algorithm does. (A vertex becomes a leaf iff all of its children are selected in the previous step.) We repeat this argument we determined a complete vertex cover.


Why there are no approximation algorithms for SAT and other decision problems? I have an NP-complete decision problem. Given an instance of the problem, I would like to design an algorithm that outputs YES, if the problem is feasible, and, NO, otherwise. (Of course, if the algorithm is not optimal, it will make errors.)

I cannot find any approximation algorithms for such problems. I was looking specifically for SAT and I found in Wikipedia page about Approximation Algorithm the following: Another limitation of the approach is that it applies only to optimization problems and not to "pure" decision problems like satisfiability, although it is often possible to ...

Why we do not, for example, define the approximation ratio to be something proportional to the number of mistakes that the algorithm makes? How do we actually solve decision problems in greedy and sub-optimal manner?

Approximation algorithms are only for optimization problems, not for decision problems.

Why don't we define the approximation ratio to be the fraction of mistakes an algorithm makes, when trying to solve some decision problem?  Because "the approximation ratio" is a term with a well-defined, standard meaning, one that means something else, and it would be confusing to use the same term for two different things.

OK, could we define some other ratio (let's call it something else -- e.g., "the det-ratio") that quantifies the number of mistakes an algorithm makes, for some decision problem?  Well, it's not clear how to do that.  What would be the denominator for that fraction?  Or, to put it another way: there are going to be an infinite number of problem instances, and for some of them the algorithm will give the right answer and others it will give the wrong answer, so you end up with a ratio that is "something divided by infinity", and that ends up being meaningless or not defined.

Alternatively, we could define $r_n$ to be the fraction of mistakes the algorithm mistakes, on problem instances of size $n$.  Then, we could compute the limit of $r_n$ as $n \to \infty$, if such a limit exists.  This would be well-defined (if the limit exists).  However, in most cases, this might not be terribly useful.  In particular, it implicitly assumes a uniform distribution on problem instances.  However, in the real world, the actual distribution on problem instances may not be uniform -- it is often very far from uniform.  Consequently, the number you get in this way is often not as useful as you might hope: it often gives a misleading impression of how good the algorithm is.

To learn more about how people deal with intractability (NP-hardness), take a look at Dealing with intractability: NP-complete problems.


Which "entity" is working at more deeper level than Characters of a program? It is commonly told that, while we write a program, we input with our language (A, B, C, D etc), whom computer translates into machine language into machine language made up of Zero (0) or switch off and One (1) or switch on, a.k.a. ASCII code.

Letter  ... ASCII Code  .... Binary

A ...........   065 ............  01000001

B ...........   066 ............  01000010

But I don't think it is that simple.

When I type A on the keyboard, the programming prompt (say C-programing) screen shows me a letter A or a (depending upon caps lock or not) that have a definite geometric shape and orientation. There are other factors, like which part on screen the letter will be shown.

Even if A=01000001 I don't think just turning off 6 pixels (Six ZEROS) and turning on 2 pixels (two ONES) it is possible to render  triangular capital-letter A.

Now my question is; What is the "Entity" (maybe a software) which is rendering a small 0-1 code into a geometric figure (glyph)? Such as 01000001 into a triangular shape (A) or rendering 01000010 into a vertical line with two bulge at right hand side (B) etc.

There are many pieces of software involved in rendering an "A" when you type it in to a program like a text editor.

First, the key press is handled by the hardware of the keyboard, which sends a signal to the OS's keyboard driver. This is where stuff like the
state of the shift key and caps lock get noted (though the
information about which modifier keys are pressed will usually just
be passed along with the information about the key pressed, rather
than "a" turning into "A" just yet).
The key press information next gets passed to the window manager
(which is usually part of the OS), to determine which program has
"keyboard focus" at the moment. If nothing has focus, the window
manager might discard the key press here (though it might also
intercept other presses, like ALT+Tab).
Next the active program likely gets a key-press event. Often the
program's event processing happens in a library provided by the
window system, though what it will do with the events after they
happen is up to the application itself.
An editor program will likely interpret a key press like "A" as input
for a file you have open. It will add the character to its memory
buffer representing the file's contents. This may be the first place
where the ASCII representation for "A" becomes relevant, as keyboards
and windowing systems often use their own codes for key presses. (Note though that a modern editor will probably use some encoding of Unicode, rather than ASCII to represent text. This adds some extra complication, but makes it possible to handle text in any language, not only English.)
Now the program has to draw the "A" to the screen. First it will
probably have to do a bunch of calculations to determine how it wants
to lay out all its text. Many editors wrap long lines of text, for
instance, which can be pretty complicated to get right.
Once the program has decided exactly where on the screen it wants to
put each part of its text, it will render them using a font. The font
describes what each glyph should look like (this is also very
complicated). The font render (which is often part of a library
provided by the OS or window manager, though an application can do
its own rendering if it really wants to) transforms the "A" to a
specific set of pixels.
Next, the pixels for the "A" (along with those for the other text,
and the rest of the editor's UI) get sent to the graphics driver.
Other programs may also be sending their own pixels if other windows
are visible alongside the editor. The window manager will usually
also have some parts of the screen that it manages itself (like the
taskbar, but sometimes also the borders of the windows).
The graphics driver sends on all the data to the hardware graphics
card in the machine. Some PCs these days (especially laptops) don't
have a dedicated graphics card, but they'll have a chip on the
motherboard that does essentially the same thing. The graphics card
will assemble all the graphics into a buffer representing all the
pixels of the screen. It will send the contents of that buffer to the
monitor every time it needs to redraw the screen (usually 60 times
per second, though other refresh rates are becoming more common).

The steps above are intended to be fairly general. Typing a key into a specific program on your computer may not have exactly the steps I describe (it could have more or fewer). For instance, if your editor is a console application rather than a graphical one, you may not have any window manager involved, and very basic fixed-width font rendering might be done directly by the hardware of the graphics card.

The exact boundaries between some of the layers may also be hard to distinguish in some cases, especially when the application is using libraries provided by the OS, window manager or graphics driver for some of the steps (like the event loop and font rendering).


Why should I use Huffman enoding if it makes my data longer? I have a requirement to reduce the size of the request / response XML by compressing repetitive productID data in compatible tag.

My request / response xml looks something like below

<products>
   <id>
     2XZ
   </id>
   <compatible>
   2TR,07N,2TS,082,084,2TT,2TU,2TV,2TW,2TX,2TY,2TZ,2U0,2U1,2U2,2U3,2U4,081,083,2U5,2U6,2U7,2U8,2U9,2UA,2UB,2UC,2UD,2UE,2UF,2UG,2UH,2UI,012,014,015,016,2UJ,2UK,2UL,2UM,2UN,2UO,2UP,2UQ,2UR,2US,2UT,2UU,2UV,2UW,2UX,2UY,2UZ,2V0,2V1,2V2,2V3,2V4,2V5,2V6,2V7,2V8,2V9,2VA,2VB,2VC,2VD,2VE,2VF,2VG,2VH,2VI,2VJ,2VK,2VL,2VM,2VN,2VO,2VP,2VQ,2VR,2VS,2VT,2VU,2VV,2VW,2VX
   </compatible>
</products>

I was given a suggestion to use Huffman code to compress compatible list data.

What I am confused about is how would Huffman encoded data in the XML reduce the size of the request / response XML as the resulting stream of binary data in the compatible tag might just increase the length and size of XML.

Example: Huffman encoding first 2 product IDs generates a longer binary string
Original String: 2TR,07N
Encoded binary String: 11101100110100010101

So my XML will change from

<products>
   <id>
     2XZ
   </id>
   <compatible>
   2TR,07N
   </compatible>
</products>

TO:

<products>
   <id>
     2XZ
   </id>
   <compatible>
   11101100110100010101
   </compatible>
</products>

Am I missing something obvious here?

I cannot see the benefit of Huffman coding in XML. First, the coding dictionary of each symbol has to be known on the receiving end, i.e.

<dictionary>0111....</dictionary>

Second, the Huffman coded data should be represented as 8-bit data to be space efficient. For example, your Huffman code for 2TR,07N becomes &xECD1;&x50;. However, 8-bit data is incompatible to XML because a lot of symbols are reserved for tags "<>" or attributes ":=".

If you are free to use any compression technique, I would suggest gzipping your data and then encoding the 8-bit data as base64. In this case, the string
 (264 characters without comma)

2TR,07N,2TS,082,084,2TT,2TU,2TV,2TW,2TX,2TY,2TZ,2U0,2U1,2U2,2U3,2U4,081,083,2U5,2U6,2U7,2U8,2U9,2UA,2UB,2UC,2UD,2UE,2UF,2UG,2UH,2UI,012,014,015,016,2UJ,2UK,2UL,2UM,2UN,2UO,2UP,2UQ,2UR,2US,2UT,2UU,2UV,2UW,2UX,2UY,2UZ,2V0,2V1,2V2,2V3,2V4,2V5,2V6,2V7,2V8,2V9,2VA,2VB,2VC,2VD,2VE,2VF,2VG,2VH,2VI,2VJ,2VK,2VL,2VM,2VN,2VO,2VP,2VQ,2VR,2VS,2VT,2VU,2VV,2VW,2VX

will be encoded as (232 characters)

H4sIACSf+1YAAxXPS1ZCMRBF0b5jSeMlgmDTDyAKfuDVFZ3/QNg0zlrVqcrOmE9tWn22MZ/btB5a
mGeVol9d9Kf/NmpS19C9Fna6bvNSD1pprUc96VkvetVGW+30pn2bune7O32p2/67PnTQUXz1pW/9
6KSzOIuzOIuzOIuzOMMZznCGLf4VvrgfvvCFL3zhC1/4whe+8IUve/GEJzzhCU94whOe8IQnPOEJ
T3hyubsCdDvGCWABAAA=

It is worth noting that gzip has Huffman coding in design, and the base64 encoding is a common practice for embedding PNG images in HTML.

References:

https://stackoverflow.com/questions/1091945/what-characters-do-i-need-to-escape-in-xml-documents
https://stackoverflow.com/questions/7849067/how-can-i-convert-a-string-into-a-gzip-base64-string


Are there dynamic programming examples that run in exponential time? Are there dynamic programming examples that run in exponential time? Every example that I've seen so far constructs the top half of a matrix in a bottom-up fashion ($n^2$) from the base case and evaluates $n$ expressions to optimize each entry.

A well-known example is the Held-Karp dynamic programming approach to solving the traveling salesman problem (TSP), running in $O(n^22^n)$ time and $O(n2^n)$ space. For more, see these notes.


A greedy algorithm for the bottle filling problem (There’s no need to write the algorithm, I just need help with the greedy choice).

Problem: you are given bottles numbered 1 to n. Each bottle i has a capacity of Ci and currently contains Li. We want to poor water between the bottles so that as many bottles as possible will be filled (Li = Ci) but doing so while moving a minimal amount of water.
Write a greedy algorithm that will print instructions on how to do so (poor x liters from bottle i into bottle j). Prove correctness of your algorithm, and give its time complexity.

I’m having trouble solving this problem. We need to write a greedy algorithm, and so the solution is of the type:
 “take bottle with certain property x and poor as much as you can (until it’s empty or until the other bottle is full) into bottle with certain property y”.
But putting in all of the simple properties don’t seem to work and can be refuted with a counter example.
Any ideas?

Here is the "greedy" idea.

Suppose you need to choose one bottle to fill completely with minimal amount of water. Which bottle will you choose?

Once you have chosen one bottle and fill it completely with water, the situation you are in now is just as before but one bottle less. You can apply the "greedy" choice again. And so on.