Solve a problem through reduction I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard).

Let's assume that you have proven that a problem Y is NP-Hard, and you have a problem X which you know is in NP, and you would like to solve.

To solve X, which of the following reductions would be carried out?

X -> Y
Y -> X

Which of the following? i.e. would you reduce X to Y or vice-versa, if you would like to solve X which is in NP, and Y which is NP-Hard?

What do you mean by "solve"?

Do you want to provide an algorithm for the problem? Then you reduce $X$ to $Y$ and use a supposedly known algorithm $A_Y$ to solve it. That is, if you have an instance $x$ of $X$ , you use the reduction $f$ to convert it to some instance $y=f(x)$ of $Y$ and then use the algorithm that solves $Y$ on instance $y$. In that way, you have an algorithm with running time $T_f + T_{A_Y}$ for $X$.
What if by solve you mean to find out the complexity of $X$, in this case prove that $X$ is $\mathbb{NP}$-hard?

Instead of providing a one-time answer, I would like to show you why this answer holds. As it is common in mathematics and science in general, the level of abstraction you are working on might be helpful, yet it covers some fine details. For example, the intuitive measurement of the resources spent, most notably time, has its basis on a complicated scheme with the purpose to define reductions with some desirable properties.

For polynomial-time reductions, like the ones we use to prove $\mathbb{NP}$-completeness, you can treat reductions as the $\leq$ operator (in mathematical terms, polynomial-time reductions define a partial order. In general, reductions define a preorder). That is, the right hand side is always at least as hard as the left hand. At this point of the discussion, I beg you to remember that we compare problems, so in the extreme case that a single instance is hard and the rest easy, this single instance determines the complexity of the entire problem.

Now, we can answer your question. We know that $Y$ is a $\mathbb{NP}$-hard problem and we want to prove that $X$ is at least as hard as $Y$. Therefore, thinking in terms of the $\leq$ operator, it is suffices to reduce $Y$ to $X$, that is $Y \leq _{p} X$. Provided you have that reduction, $X$ is at least as hard as $Y$. And $Y$ is $\mathbb{NP}$-hard, so $X$ must be $\mathbb{NP}$-hard too. By definition, if you can prove that $X \in \mathbb{NP}$, then $X$ is $\mathbb{NP}$-complete.

At the end of this discussion, you might have noticed a problem. The satisfiability problem $SAT$ is $\mathbb{NP}$-complete, yet there exists a simple $O(n)$ nondeterministic time algorithm for it. How can it be as least as hard as any problem in $\mathbb{NP}$? The answer is simple: Polynomial-time differences are not of an interest to us, as we have defined our model. So, the polynomial-time reduction behaves like the $\leq$ operator, though it allows the complexity of the left hand side to be larger up to a polynomial than the running time of the harder problem. This is why we don't use exponential time reductions, since the error margin would be larger than the complexity of the problems themselves (and the definition of the respective classes), making them useless.


Confusion with first condition of Chomsky Normal Form I had a very quick question when it comes to CFG (more specifically the attributes of CNF). I've been browsing over some examples and I've come across a few that confuse me. One such example is this:

$$\begin{align}S&\to XA|BB\\
B&\to b|SB\\
X&\to b\\
A&\to a\\
\end{align}$$

It is stated that this is indeed in CNF, but my confusion lies in the fact that under most rules it is stated that if the starting state $S$ exists in some RHS (in this case $B\to b|SB$) we must create a rule that states $S'\to S$.

Since that doesn't exist in this example, why is this considered to be in CNF? I also understand the rules of CNF, I also see that this example technically satisfies all those rules, so I am wondering if that is the reason?

Rules:
$$\begin{align}A&\to a\\
A&\to BC\\
\end{align}$$

Thank you for the help in advance!

Here is the link to the question for reference ( it deals with CFG TO GNF)
https://www.geeksforgeeks.org/converting-context-free-grammar-greibach-normal-form/

Yes, your context-free grammar is in Chomsky Normal Form.

A grammar is in CNF whenever its rules are of one of two types, either $A\to BC$ or $A\to a$, where $A,B,C$ are nonterminals, and $a$ is a terminal symbol.

This means that every context-free grammar is equivalent to a cf grammar in CNF, up to the empty word.
This means that by conversion into CNF one might loose the empty word. Nobody cares. Wikipedia refers to Hopcroft and Ullman as the source for CNF, and here is what H&U write:

  Theorem 4.5 (Chomsky normal form, or CNF)
  Any context-free language without $\epsilon$ is generated by a
  grammar in which all productions are of the form
  $A\to BC$ or $A\to a$. Here, $A$, $B$, and $C$, are variables and $a$ is a terminal.

Except that some people with a wretched feeling for precision did not like this idea. They came up with a complicated formulation, just to capture the empty string. Probably something like "If the language contains $\epsilon$ then we allow the production $S\to \epsilon$, where $S$ is the axiom, and $S$ does not occur on the right-hand side of productions."

Well, your example grammar does not generate $\epsilon$ anyhow, so I would not bother. Chomsky didn't, Hopcroft and Ullman didn't. However, this is not legal advise. So, if someone is checking your exams, then I would consult that person.

Fun fact, Chomsky called "his" normal form "regular grammars"(!) and added a more restrictive condition: no two rules $A\to \alpha$ and $A\to \beta$ could share a common symbol in their right-hand sides $\alpha$ and $\beta$ (unless of course $\alpha =\beta$). (Definition 8, page 149, in the 1959 Chomsky paper linked at wikipedia).


Can a 32-bit processor work with a 64-bit size word? In a 32-bit byte addressable memory system, each "row" has 4 bytes and each byte has a 32-bit address.

My question is: can I read and/or write word of length 64 bits from/to memory?
In other terms, can my word length be 8 bytes long or is the maximum number of bytes/word 4?

Just what makes a processor a 32-bit processor?
And what would 64-bit word/32-bit halfword mean in the context?
There are processors allowing a single instruction to read more than one "memory cell", with documentation more or less readily available. The DEC VAX is notorious for having quad- and octaword accesses (a word being half the width of the general purpose registers (and data bus of early implementations)…).
There are processors with the width of the data bus smaller than a GPR. The Motorola 68000 was dubbed a 16-bit CPU - with 32 bit GPRs from the start. Then, the were Intel 8088, 68008 with a data bus a quarter in width compared to its GPRs, …
There are (memory) buses that allow locking of consecutive transfers.
There are buses and memory interfaces (on processing units as well as on memory devices) providing for burst transfers.


Understanding CLRS BFT lemma I was reading BFT from CLRS. This is the example given in the book:

(Figure:The operation of BFS on an undirected graph. Tree edges are shown shaded as they are produced by BFS. The value of $u.d$ appears within each vertex $u$. The queue $Q$ is shown at the beginning of each iteration. Vertex distances appear below vertices in the queue.)

Then it gives following lemma:

  Suppose that during the execution of BFS on a graph $G=(V,E)$, the queue $Q$
  contains the vertices $<v_1,v_2,...,v_r>$, where $v_1$ is the head of $Q$ and $v_r$ is the tail. Then, $v_r.d\leq v_1.d+1$ and $v_i.d\leq v_{i+1}.d$ for $I=1,2,...,r-1$.

I am ok with $v_i.d\leq v_{i+1}.d$ for $I=1,2,...,r-1$ as I can observe this in all queue instances above. But I am not able to understand how $v_r.d\leq v_1.d+1$ aligns with above, as $i<i+1$, but $r>1$. How that $+1$ is making whole difference?

Suppose you have a tree like

        a           <-- level = 0
      / | \
     b  c  d        <-- level = 1
   /
  f                 <-- level = 2

    v1, v2, v3
Q : b,  c,  d
    1,  1,  1

v3.d <= v1.d + 1   i.e 1 <= (1+1)

Now, suppose head of Q (i.e b) is removed and its neighbors are inserted in Q

    v1, v2, v3
Q : c,  d,  f
    1,  1,  2

v3.d <= v1.d + 1   i.e 2 <= (1+1)

This, v3.d <= v1.d + 1 can be also be seen as v3.d - v1.d <= 1 which means at any point of time distance between elements of queue will always be less than or equal 1. This can also be seen from the fact that during the execution of BFT only elements from 2 successive levels are present in queue. There cannot be case such that 2 elements A and B are present in queue with A at level x and B at level (x + 2).


The path between any two nodes in cyclic directed graph G{V, E} is directed, cyclic, weighted graph. What is the algorithm of finding all paths between any given two nodes?
Can you suggest any good reading?

If the graph happens to be a DAG, then you can found the number of paths from any vertex to any other vertex using linear algebra. Let $A$ be the adjacency matrix of the graph. Compute
$$ B = \sum_{k=0}^{n-1} A^k. $$
Then $B_{ij}$ is the number of paths (of length at most $n-1$) between vertex $i$ and vertex $j$. This also works for weighted graphs, in which case the weight of each path is the product of the weights on the edges.

It is easy to construct examples where there are exponentially many paths. For example, let the vertices be $x_0,\ldots,x_n,y_1,\ldots,y_n,z_1,\ldots,z_n$, and the edges be $(x_i,y_{i+1}),(x_i,z_{i+1}),(y_i,x_i),(z_i,x_i)$. The number of paths from $x_0$ to $x_n$ is $2^n$.

If the graph is not a DAG, then there can be infinitely many paths from a vertex to another, since any given cycle can be taken an unbounded number of times. In this case it makes sense to ask for the number of simple paths from one vertex to another. In the weighted version (with weights of polynomial length), we expect this to be difficult, since HAM-PATH can be solved this way.


Time complexity of languages that are polynomial time reducible to NP complete languages I am wondering if given the time complexity of an NP-Complete problem or at least some information about it for example if $ SAT\in Time(2^{sqrt(n)})$ (hypothetically) could I assume that all languages in NP (which are clearly polynomial time reducible to SAT) are also $\in Time(2^{sqrt(n)})$

I believe the answer is false because I could basically pick any arbitrary class of exponential time functions and claim that all languages in NP are contained within it while it may actually belong to a class of higher power... but I'm not sure how to formulate this as a proof.

You are right.  You can't draw that inference.  Given the assumption that SAT can be solved in $O(2^{\sqrt{n}})$ time, it does not follow that all NP-complete problems can be solved in $O(2^{\sqrt{n}})$ time.

For instance, the reduction from the NP-complete problem to SAT might transform a problem instance of size $n$ to a SAT instance of size $n^2$, so applying the SAT algorithm to that would take $O(2^n)$ time.  There are some reductions that preserve the size of the problem instance, and for those reductions, you will be able to solve them about as fast as SAT -- but as far as we know, not all NP-complete problems fall into that category.

You might enjoy reading about the exponential time hypothesis, which is the hypothesis that there is no such subexponential-time algorithm for SAT.  Folks have studied the consequences of the exponential time hypothesis in depth (as well as the consequences of the negation of the exponential time hypothesis).


Is it impossible to truly emulate a system if its actual clock speed is the same? As I understand emulation a rule of the thumb says that a computer must be around a order of magnitude more powerful to emulate another system without resorting to tricks. This is because for every clock cycle of the system to be emulated, the host machine must process that cycle in the correct time and also process its own cycles.

A Xbox 360 uses a 3.2GHz PowerPC Tri-Core Xenon processor, would this mean that emulating the console on a 3GHz PC CPU would be impossible, even if the host CPU was more powerful but not faster for clock cycles?

To give a more straightforward example. A i7 that runs at the same clock speed as a Pentium 4 will not be able to emulate the Pentium 4, even though the i7 is many times more powerful.

In addition, does this mean that to emulate the Xbox 360, The host computer must run at a speed of between 9GHz and 3.2GHz to be able to truly emulate a Xbox 360?

If this is the case, surely there must be a way around this limitation? If we had a host computer with 10x3GHz CPU's could this system use parallelzation to somehow emulate a 3 core 3.2GHz system.

Also the emulate should run at the speed that the user expected of the emulated system, I know if you slowed down the Xbox 360 on the emulator by a few times then it would be easier, I want to know if we can emulate a system at the speed it was meant to run.

If this is not possible does that mean that for emulation, clock speed is king? And there is no way around this? Even if your host machine had a thousand CPU's running at 2GHz it could never ever emulate a Xbox 360 at its native speed?

By the way I am sure this is in the domain of computer science. I am not sure exactly what it comes under but the simulation of a system within a system and inherent limitations is certainly applicable to computer science.

What about this: could a 4 core 3GHz i7 CPU emulate in proper time a 3.8GHz single core Pentium 4?

That very much depends on how well the instruction set of the CPU to be emulated maps to the instruction set of the emulating CPU. Certainly, clock speed is not the deciding factor. It might very well be that a slower (clock wise) CPU A can emulate a faster CPU B.

This can be both because of more powerful instructions (e.g. SSE instructions that allow doing the same operation to multiple values at once), or improvements in instruction level parallelism (e.g. more adders, multipliers etc. so that more instructions can be executed simultaniously, smarter recognition of independent instructions). There are also strong contributions from larger caches and smarter branch prediction. All these factors (and probably many more that I don't know about) can be improved to increase the average number of instructions executed without changing the clock speed. Since clock-speed increases stalled some years ago, this kind of improvement has been a major contributor to performance increases in CPUs.

Of course it also strongly depends on the skill of the person writing the emulator. There will always be some overhead involved in translating the instructions for CPU B to instructions that work on A. The larger the difference between the two CPUs, the larger the overhead.


What is the denotation for identifiers? I am trying to understand what is the domain for denotational semantics.

Right now the way I understand denotational semantics is that given some syntax of a program that maps to some mathematical object that represents its meaning. e.g. for example give  some arithmetic expression AExp the denotation $[\_]:AExp \to (State \rightharpoondown Int)$ :

$$ [ 1 + x ]\sigma = 1+x $$

if the state is $\sigma = \{ x:2\}$ then:

$$ [ 1 + x ]\sigma = 3 $$

So indeed given the syntax AExp using the state we can fully determine what the integer should be returned.

I also understand the denotations for statements $[\_]:State \rightharpoondown State $ which makes a lot of sense since that states the state of the program to the next after executing some code in the statement. e.g. $[\{ \}] = 1_{identity}$ the empty statement does not change the state so:

$$ [\{ \}](\sigma) = [\{ \}]\sigma = 1_{identity}(\sigma) = \sigma $$

But I can't figure out what the type should be for the denotation for identifiers. From the notes I am reading CS522 I see this:

$$ x\in Identifier \implies [\sigma] = \sigma(x) $$

which intuitively makes sense but I am having difficulties matching it to the fact that denotaitons should be CPO (Complete Partial Sets). How is the above a CPO? (or the poset, the technicality of existence of LUB/sumpremum is not that important to me). I can't see the POSET.

I guess I am not 100% how the other two are also CPOs...any enlightening comments?

But I can't figure out what the type should be for the denotation for identifiers.

That is because you are implicitly tracing the denotation function $⟦\_⟧$.
It might get easier to see the type if you explicitly trace the denotation
function by tagging them appropriately.
$⟦x + y⟧_{AExp}\sigma = ⟦x⟧_{AExp}\sigma + ⟦y⟧_{AExp}\sigma$.

Similarly, if you have an boolean expression with identifiers, for example:
$$⟦a_1 < a_2⟧_{BExp}\sigma =
\begin{cases}
True &\text{if} ⟦a_1⟧_{AExp}\sigma < ⟦a_2⟧_{AExp}\sigma\\
False  &\text{if} ⟦a_1⟧_{AExp}\sigma \geq ⟦a_2⟧_{AExp}\sigma\\
\bot  &\text{otherwise}
\end{cases}$$

In this case $\sigma : Identifier \rightharpoondown Int$.
The type of $\sigma$ would also be implicitly traced by the denotation function because, the object language construct makes it obvious. You can, if you want to be even more pedantic, carry around a tuple of $\sigma$'s, one for each type of variable lookup.
So, if your language has integer variables and boolean variables, your $\sigma = (\sigma_{Int}, \sigma_{Bool})$ and the correct component would be chosen depending on which $⟦\_⟧$ is being used.

  I guess I am not 100% how the other two are also CPOs...any enlightening comments?

Now, the poset structure is on the co-domain of the denotation function i.e. if you have a denotation $⟦\_⟧_{Stmt}$ the signature of the poset structure will be $(\alpha: State \rightharpoondown State, \preceq, \bot)$ similarly for $⟦\_⟧_{AExp}$ the structure poset structure would be $(\alpha: State \rightharpoondown Int, \preceq, \bot)$, where $\preceq$ allows you to compare the amount of information
contained by the information bearers $\alpha$, as explained on pg 159-160 in the notes you have linked.


Context-free language and undecidable I am working on my midterm sample problems and got stuck on this one. Is this language undecidable?

$\qquad  L = \{\langle G_1, G_2 \rangle: G_1, G_2 \text{  are CFG and have strings that can be parsed in both grammars }\}$

Is this one the same as $L' = \{\langle G_1, G_2 \rangle: L(G_1) \cap L(G_2) \ne \emptyset\}$? My professor said the above problem can be reduced to Post Correspondence Problem but I found it closer to the decidable of $L'$.

Yes, they are the same languages: $L=L'$ (at least the way that I understand the definition of $L$).  We say that the grammar $G_1$ can parse a string $x$ iff $x \in L(G_1)$.  It follows that $L=L'$.  $L$ is defined in a somewhat informal way; good for you for finding a way to provide a more precise formal statement of it.

Indeed, the problem of deciding whether two CFLs have a non-empty intersection is undecidable, so neither $L$ nor $L'$ is decidable.


Deciding whether complement of context-free language is context-free I need to find out if the following problem is decidable:

Given a context-free language $L$, decide whether its complement $\bar{L}$ is also a context-free language.

I am having trouble in defining the $TM$ I need in order to solve this problem. My thinking was to see if it is possible to construct a $TM$ that takes an encoding of a $CFL$ as input and halts in an accept or reject state depending on whether $\bar{L}$ is a $CFL$ or not. Is this line of thinking correct? If so, may I also know how to proceed further.

Your problem can be formalized in several equivalent ways:

Given a context-free grammar $G$ over $\Sigma$, is $\overline{L(G)} := \Sigma^* \setminus L(G)$ context-free?

Given a PDA $M$ over $\Sigma$, is $\overline{L(M)}$ context-free?

Since we can effectively (and efficiently) translate between the two representations, both problems are equivalent. We stick to the first one.
It is well-known that given a context-free grammar $H$ over $\Sigma$, deciding whether $L(H) = \Sigma^*$ is undecidable. We will reduce this problem to Problem 1.
Let us be given a context-free grammar $H$ over $\Sigma$. If $\Sigma$ is a singleton, then $L(H)$ is regular, and so $\Sigma^* \setminus L(H)$ is also regular and context-free. Otherwise, let $a,b \in \Sigma$ be two distinct symbols. Construct a grammar $G$ over $\Sigma \cup \{\#\}$ (where $\#$ is a fresh symbol) for the language
$$
L = (\Sigma^* \setminus \{ww : w \in \Sigma^*\}) \# \Sigma^* \cup \Sigma^* \# L(H).
$$
If $L(H) = \Sigma^*$ then $L = \Sigma^* \# \Sigma^*$ is regular, and so its complement is regular and context-free. Otherwise, let $x \notin L(H)$. If $\overline{L}$ were context-free, then so would the following language be:
$$
\overline{L} \cap \Sigma^* \# x = \{ww : w \in \Sigma^*\} \# x.
$$
This would imply, however, that $\{ww : w \in \Sigma^*\}$ is context-free, which is known to be false.
Summarizing, $\overline{L(G)}$ is context-free iff $L(H) = \Sigma^*$.
Compare Theorems 11–12 in Hendrik Jan's notes.


Confusing method of proving PSPACE-completness I don't understand a way of proving PSPACE-completness. The way was used by my lecturer. I can use reduction, however following method confuse me:

We consider sequence (of polynomial length) of configurations and check if transitions betweens configurations in sequence are legal. We also check if machine accept word $w$. In other words, we analyze run of polynomial-space machine $M$ on word $w$ and check if this run is legal and accepting.

I can't understand why such reasoning work. I don't show exact example because my lecturer use this technique fairly often.

Can you explain me why it work?

This technique is also known as computation history method. Given a Turing machine $M$ you (or another TM $M'$) inspect its computation "flow" or "history" configuration by configuration. You can think of TM configuration as snapshot of the tape content plus machine's state at some particular time. Every step of a TM generates a new configuration. The set of all that configurations is a computation history. If computation halts then that set is finite.

UPDATE: (on David Richerby comment) The following paragraph may be irrelevant to the question since I overlooked "sequence (of polynomial length) of configurations" in OP which is different from "the sequence of configurations where each is of polynomial length".

Polynomial length requirement:  because you want to prove PSPACE membership, maximum number of used tape cells must be polynomial. That's why an accent made on polynomial length.

Transitions betweens configurations in sequence are legal: you want be sure that machine's transitions between states were really made according to the machines's transition rules, otherwise the run is not legal. For example if a configuration $C_i$ differs from the configuration $C_j$ by 3 symbols (assuming a single tape TM) then you can say that transition is not legal, since the TM cannot change 3 symbols in a single step.

Also note that if one TM $M$ simulates another TM $M'$ then if $M'$ uses polynomial space then the whole simulation also uses polynomial space since simulation itself takes polynomial space.

Example of use of configurations:
Assume you know that a certain class of TM machines use no more than, say, $n$ cells of tape where $n$ is input size. Then halting problem for this class of TMs is decidable. Since a TM has finite number of states $|Q|$ and alphabets $|\Sigma|$, and since we that it uses at most $n$ cells, we simply can compute that the TM has at most $n|Q||\Sigma|^n$ configurations. Then you simulate that TM and check if at some point it repeats it's configuration then there must be an infinite loop and so it never halts (since the tape use is bounded!, the TM may not move infinitely move its head to the right and right symbols). The latter class is also known as linear bound automata.


Efficient way to choose set from including conditions on sets Let $m, n \in \mathbb{N}$ and $n \le m$. Given $k$ subsets $X_1, X_2, \dots, X_k$ of $\{ 1, 2, \dots, m \}$ and $k$ nonnegative integers $a_1, a_2, \dots, a_k$, find all subsets $Y$ of $\{ 1, 2, \dots, m \}$ satisfying the following conditions:

The set $Y$ contains exactly $n$ elements: $|Y| = n$
The set $X_i$ has exactly $a_i$ elements with $Y$ in common: $\forall 1 \le i \le k: |X_i \cap Y| = a_i$

EXAMPLE. Let $m = 5$, $n = 2$. We are given the following conditions. Set $Y$ contains...

1 element out of $\{ 2, 3, 4, 5 \}$, $\quad$ ($a_1 = 1$)
2 elements out of $\{ 1, 2, 3, 4 \}$, $\quad$ ($a_2 = 2$)
1 element out of $\{ 1, 3, 4, 5 \}$. $\quad$ ($a_3 = 1$)

$Y = \{ 1, 2 \}$ is a unique solution. It is necessary to have $1 \in Y$, else we must select two elements of $\{ 2, 3, 4 \}$ (2nd set without $1$), which is a subset of the 1st set. Now consider the 3rd set. If we select $3, 4$ or $5$ instead of $2$, $Y$ would contain two elements from 3rd set.

Of course, there may be many solutions, up to $\binom{m}{n}$ to be specific.

QUESTIONS. I have the following two questions:

Are there any algorithms better than trivial brute-force to find all solutions to an instance of this problem? Do these algorithms fulfill known lower bounds?
Given that there exists a unique solution, can we use this extra knowledge to do better than in the general case in terms of time complexity?

MY APPROACHES. Obviously, it is possible to enumerate all $\binom{m}{n}$ subsets and check the conditions. At least for the last step (I know, the first step causes the lack of efficiency) I can think of some improvements. First, we may represent the sets as boolean arrays of size $m$. When iterating over the possible solutions, we may compute $X_i \cap Y$ in time $\mathcal{O}(m)$ resulting in an $\mathcal{O}\left(m\binom{m}{n}\right)$ solution. Additionally, if there is a set $X_i$ with $|X_i| = a_i$ we are lucky. In this case, we know $X_i \subseteq Y$ and may erase all elements of $X_i$ in the other subsets $X_j$ replacing $a_j$ by $a_j - |X_i \cap X_j|$. But in general, this special case does not occur with certainty.

I would appreciate any kind of help and material.

I think it should be straightforward to reduce One-in-3SAT to this problem: For example, you can create a size-2 set $X_i$ for each variable $x_i$ from the One-in-3SAT instance, and set $a_i=1$ to force that either the variable or its negation is chosen.  $n$ will be the number of variables, and you will need additional sets $X_j$ for each clause, with $a_j=1$ (reflecting the constraint that exactly 1 literal in each clause be positive).

Showing this reduction would show that the problem is NP-hard, indicating that a polynomial-time solution is very unlikely.


Finding representatives of equivalence classes I have a table of pairs of objects, which defines an equivalence relation. How can I extract a single object from each of the equivalence classes using relational algebra?

It can easily be done with iteration. For example, associate a unique classId with every object, then for every pair (a, b) set classId(a) = classId(b) = min(classId(a), classId(b)), until all pairs share the same classId on both ends.
I wouldn't know how to do it more efficiently.

The most efficient way known of doing this is the union-find algorithm. The idea is to keep a forest (but with links "upwards", not downwards), and squash long branches. You start with each element in its own forest. To make $a$ and $b$ equivalent, you check it $a$ and $b$ are already in the same class by following their links to the respective roots. If the roots are different, make the smaller tree a subtree of the larger one. And each time you follow a chain to a root, afterwards revisit all nodes on the path and make them point directly to the root, effectively making later searches take one step.

This is rather simple to program with an array for the nodes, and array indices for links.


Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree? Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w_1 \le w_2 \le ... \le w_{n-1}$.

Now let $T'$ be some other spanning tree of $G$ (doesn't have to be minimum) with edge weights: $w'_1 \le w'_2 \le ... \le w'_{n-1}$.

I need to prove\disprove the following claim: for every $i$:  $w_i \le w'_i$.

I've tried to find a counterexample, but I wasn't successful. So I'm quite sure the claim is correct. However, I had trouble to prove it formally.

I assume the contrary, which means there is an $i$ that satisfies $w'_i < w_i$ and I take the first one that does. I tried adding it to the tree $T$ or trying to find a minimum spanning tree with this edge using Kruskal, but no luck.

Here are some hints:

Flesh out your counterexample with quantifiers properly: "There exists a graph $G$, and a minimum spanning tree $T$ for $G$ with edge weights $w_1 \le w_2 \le \dots \le w_{n-1}$, and another spanning tree $T'$ of $G$ with edge weights $w'_1 \le w'_2 \le \dots \le w'_{n-1}$, and an integer $i$ obeying $1 \le i \le n-1$, such that $w'_i < w_i$".  In a situation like this, from the set of all such counterexamples ($(G, T, T', i)$ tuples), you are free to choose one having minimum possible $i$, and it's nearly always useful (and never harmful) to do so.
"I tried adding it to the tree $T$" -- you must first show that it is not already in $T$.  Here you can use minimality of $i$ for edges to the left, and the increasing weight order for edges to the right.
Let's add it to $T$, to make a graph I'll call $G_2$.  What noticeable feature does $G_2$ contain?
What simple modifications could you make to that feature in $G_2$ to turn it back into a tree?  Hint: With this particular feature, there will always be at least 3 ways to do this, and there could be as many as $n$.
Can you choose an option in the previous step that will lead to a tree that is strictly lighter than $T$, and thus a contradiction (since we assumed $T$ to be minimal)?


What does $\overline{L}^*$ signify? Suppose that $L$ is a language.

What does $\overline{L}^*$ signify?
Is $\overline{L^*}$ the same as $(\overline{L})^*$?

For any language $L$ over alphabet $\Sigma$,

$\overline{L} = \Sigma^*\setminus L$ is the complement of $L$: the set of $\Sigma$-strings not in $L$;
$L^*$ is the Kleene closure of $L$: the set of strings $w\in\Sigma^*$ such that we can write $w=w_1\dots w_k$ for some $k\geq 0$ such that each $w_i\in L$.  For example, if $L$ is the set of English words, then correcthorsebatterystaple is in $L^*$.

Now, $\overline{L}^*$ is something-star, where "something" is $\overline{L}$. That is, it's the Kleene closure of the complement of $L$: the set of all strings $w\in\Sigma^*$ that can be written $w_1\dots w_k$ such that each $w_i$ is not in $L$. Essentially, we read left-to-right, so you parse "$\overline{L}$" before you reach the star.

Conversely, $\overline{L^*}$ is something-complement, where "something" is $L^*$, the Kleene closure of $L$. That is, it is the set of all strings that cannot be written $w_1\dots w_k$ where each $w_i\in L$.

These are not necessarily the same languages. For example, consider $\Sigma=\{1\}$ and $L=\{11\}$.  Then $1\in\overline{L}$, so $\overline{L}^*=\Sigma^*$. However, $$\overline{L^*} = \overline{\{1^i\mid i\text{ is even}\}} = \{1^i\mid i\text{ is odd}\}\neq\Sigma^*\,.$$


How can I solve this problem using dynamic programming? I'm stuck in this problem and I would need some help:

Given an array arr, in each step, 1, 2 or 5 units have to be incremented to all but one item of the array. The goal is to find the minimum number of steps to all items to be equal.

First example

arr = [1, 1, 5]

1) [1 (+2), 1 (+2), 5] = [3, 3, 5]
2) [3 (+2), 3 (+2), 5] = [5, 5, 5]

Solution: 2 steps

Second example

arr = [2, 2, 3, 7]

1) [2 (+1), 2 (+1), 3, 7 (+1)] = [3, 3, 3, 8]
2) [3 (+5), 3 (+5), 3 (+5), 8] = [8, 8, 8, 8]

Solution: 2 steps

I have tried some things but I'm really stuck.

I consider a base case when all items are already equal. In another case, I try to find all the possible solutions by incrementing 1, 2 and 5 to every item but one in the array:

def equal(arr):

    if (allElementsIdentical(arr)):
        return 0

    min = sys.maxsize
    for i in [1, 2, 5]:
        for j in range(len(arr)):

            #Increment all items by "i", except item at index "j"
            newArr = arr.copy()
            for k in range(j):
                newArr[k] += i
            for k in range(j + 1, len(newArr)):
                newArr[k] += i

            movements = 1 + equal(newArr)
            if movements < min:
                min = movements
    return min

This solution doesn't work because recursion never ends. E.g.

[1, 1, 5] -> [1, 2, 6] -> [1, 3, 7] -> [1, 4, 8] -> [1, 5, 9] -> ...

Is it my initial approach correct? How can I break it down in subproblems?

Increasing all elements but one is equivalent to decrease only that element. Find minimum value m, now for each element x you need to find minumum number of subtractions to go from x to m (change-making problem), since you can use greedy algorithm for coins (1, 2, 5), you can solve this problem in O(n).


Multi-Path Length Minimization I've been thinking about path planning and am trying to make good heuristics for cases with multiple agents.

Suppose there are sets $S_i$ of coordinates in $\mathbb R^2$ or $\mathbb R^3$, each of the same size n, for each possible value of $i$ where $i \in [0, ... k]$.

A path is defined as k line segments connecting a sequence of k+1 coordinates, made up of one coordinate from each set $S_i$ in consecutive order. I want to find n paths such that (a) no two paths have the same point for a given index i in the sequence, and b) the combined path length of all the paths is minimized. In other words, assign coordinates from each set without replacement to construct paths with the goal of making the total path length as small as possible.

Right now i can do the minimization from some $i$ to $i+1$, but I am not sure if locally minimizing each step will yield a global minimum. I know I could brute force it, but that explodes really quickly.

You can solve this optimally in $O(kn^3)$ time by solving a sequence of $k$ Assignment problems.

Let $f(i)$ be the lowest sum of costs of any set of $n$ paths beginning at step $i$ and continuing to step $k$ (i.e., the end). We would therefore like to compute $f(0)$, as well as a set of paths realising it.

Assume we have already computed $f(i+1)$. (Clearly $f(k) = 0$, so we have a starting point.) Let $A_{i,i+1}$ be the solution to the Assignment problem (minimum-weight bipartite matching) in which one set of vertices are the points in $S_i$ and the other is the points in $S_{i+1}$. I claim that we can compute $f(i)$ as $A_{i,i+1} + f(i+1)$.

Suppose this claim is not correct: then for some $i$, there is a better solution with cost $B_i < f(i)$, which can likewise be decomposed as $B_i = B_{i,i+1} + B_{i+1,k}$. In particular, let $i$ be the maximum possible $i$ for which $B_i < f(i)$. Then at least one of $B_{i,i+1} < A_{i,i+1}$ or $B_{i+1,k} < f(i+1)$ must be true for our assumption $B_i < f(i)$ to be true.

It cannot be that $B_{i,i+1} < A_{i,i+1}$, since $A_{i,i+1}$ is the minimum possible cost by definition of the Assignment problem. So it must be that $B_{i+1,k} < f(i+1)$. But this cannot be true either, since if it were then it would violate our assumption that $i$ is maximum possible. Thus supposing the existence of a solution with a better cost $B_i$ leads to a contradiction, so it cannot be true, meaning that $f(i)$ gives the optimal cost after all.

$f(0)$ gives you the cost of the optimal solution. To extract such a solution, just record the matchings produced by the Assignments problems you solved along the way.


Algorithm: given very large file of strings, find lines containing substring I'm not sure if cs.stackexchange.com is correct place to ask this question but it looks like most relevant.

On the job interview I was asked a question: lets say we have a very large file, containing a lot of lines with strings. And lets say that one line is a "document". We are building service which takes some string as input and returns numbers of documents containing this string or substring. Which approach would you use?

And I'm stuck with event trying to find a way to do it. Obviously we can just go through the file with every query and count lines containing substring and it will take O(n) time. But there should be more elegant and fast way to do it, right? I have no CS grad, so my knowledge about algorithms and data structures are not systematic.

My intuition says that it should some very basic question (like knackpack problem, for example) and I just don't know right data structure and algorithm to handle it.

It looks like suffix tree could help somehow but I can't find a way - how? Or, maybe, there is some another approach?

You can construct a suffix tree for that very large file and once generated the same can be used for querying.
For Suffix tree generation use Suffix Array approach, there are many algorithm to generate suffix array.
This is a taxonomy of many suffix array algorithm available today
http://www.cas.mcmaster.ca/~bill/best/algorithms/07Taxonomy.pdf

To starts with I would recommend prefix-doubling which required O(n log(n)) time.
You can then look at DC3 which does the job in O(n) time.


Row Major Vs Column Major Order: 2D arrays access in programming languages Programmers prefer accessing a 2D array in Row-Major Order rather than Column-Major Order, Why?

Are there some advantages/benefits of accessing a 2D array in row-major as compare to column-major?

Like in C programming, programmers prefer row-major rather than column-major due to the way memory is being allocated to a 2D array when defined statically or dynamically.

The way you access the array affects performance.

It depends on how the matrix is represented and stored in memory.  Often a matrix is stored in row-major order, so that consecutive elements of a row are contiguous in memory.  Reading memory in contiguous locations is faster than jumping around among locations.  As a result, if the matrix is stored in row-major order, then iterating through its elements sequentially in row-major order may be faster than iterating through its elements in column-major order.

Of course, if the matrix is stored in column-major order, the reverse will be true.

See https://en.wikipedia.org/wiki/Row-_and_column-major_order for more on the subject.


approximation algorithm for Travelling Salesman Problem: with a different inequality and not triangle inequality I have the following question for the travelling salesman problem:

The TSP algorithm is to find a complete hamilton cycle with minimum cost in a weighted graph G. Instead of the traingle inequality, the weight function satisfies the following inequality:

cost(u,w) < cost(u,v) + 2 x cost(v,w)

Find the approximation ratio if we use the following approximation algorithm:

1. Select any vertex as root vertex
2. Compute a minimum spanning tree T from graph G
3. Let L be the list of vertices visited in a preorder tree walk of T
4. return the hamilton cycle H that visits the vertices in the order L

My work so far

I figured out that it is 2-approximation if it is the triangle inequality, since going directly from one vertex to another has a cost no greater than going to a vertex in between these two vertices, so cost(H) is not greater than the cost of the preorder tree walk and therefore no greater than twice the cost of the optimal tour.

However, inequality cost(u,w) < cost(u,v) + 2 x cost(v,w) would make it different than triangle inequality that going directly from u to w could result in higher cost than from u to v to w (unless cost(v,w)=0). I think the worst case is extra cost of cost(u,v) + 2 x cost(v,w) - (cost(u,v) + cost(v,w))= cost(v,w)

Any advice on this? I need to find the approximation ratio.

Review the standard proof that it's a 2-approximation if the weight function satisfies the triangle inequality.  That suggests a way to upper-bound the total length of the Hamilton cycle $H$ returned by the algorithm.

Adjust that reasoning.  For starters, assume that every edge in $H$ is a "shortcut edge" $(u,w)$ that was taken by skipping a single vertex $v$.  What could you conclude about the cost of $H$, compared to the cost of $T$?  If you do a little bit of algebra you should be able to obtain an expression.

Now generalize to arbitrary $H$.


Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less I am trying to prove that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ such that a DFA accepting $A_k$ has $k$ states but no less.
I thought about proving this in two ways: constructively, or by contradiction.
By Contradiction: For some $k > 1$, suppose there is no language $A_k \subseteq \{0, 1\}^*$ where a DFA accepting $A_k$ exists with exactly $k$ states but no less. Then any language $L \subseteq \{0, 1\}^*$, that has an accepting DFA with $n$ states, also has an accepting DFA with $n - 1$ states. Extending this reasoning downward, this implies that every $L$ has an accepting DFA with $1$ state. This is a contradiction.
By construction: Let $A_k = \{w \in \{0, 1\}^* | w \text{ has } 0^{k - 1} \text{ as a substring}\}$. But now I need to prove that $A_k$ cannot be accepted by a DFA with less than $k$ states. I am unsure of how to do this even though it feels true intuitively.
Is my proof by contradiction valid and is the proof by construction doable? Maybe both are wrong and I need to use some other perspective.
Attempt 2:
We can easily construct a DFA with $k$ states, call it $M_k$, that accepts the language $$A_k = \{w \in \{0, 1\}^* | w \text{ has } 0^{k - 1} \text{ as a substring}\}$$
Suppose for contradiction that there exists a DFA, $M_{k - 1}$, accepting $A_k$ with $k - 1$ states. Consider the string $w = 0^{k - 1} \in A_k$, we can apply the pumping lemma because $|w| \geq k - 1$. Thus, the run of $w$ on $M_{k - 1}$ must contain a cycle of length 1 (since $|w| = k - 1$).
Then $M_{k - 1}$ actually accepts strings of the form
$$w' = 0^x \cdot 0^i \cdot 0^z$$
where $i \geq 0$, $x + 1 \leq k - 1$ and $x + z + 1 = k - 1$. Letting $i = 0$, we see $M_{k - 1}$ accepts $0^{k - 2} \not \in A_k$. A contradiction.
This reasoning is applicable to every $M_i$ with $1 < i < k$, so we are done. Is this a correct attempt?

Your first approach doesn't quite work. If it is not the case that for any $k$ there is some language that requires exactly $k$ states, then all you know is that there exists a single $n$ such that every $n$-state DFA can be reduced to an equivalent DFA with fewer states.
The second approach does work, and requires a lower bound technique such as the pumping lemma (the pumping constant is the number of states) or Myhill–Nerode theory. Try the following language: all words whose length is a multiple of $k$.


Call-by-reference semantics for RPC Does call-by-reference semantics for remote procedure call (RPC) have a real use case?  Why does call-by-reference RPC exist?  Is it useful for anything?  Is there a scenario where call-by-value can't do the job?

In a simple sentence: Do we need to have a (call by reference)-able RPC protocol? if yes, Why?

Background: Call-by-reference can be implemented for RPC.  For instance, one implementation strategy is copy & restore: the value is copied from the client to the server when you make the call, and then copied back afterwards.  There are other ways to implement it as well.

The idea is to be able to modify the argument. FORTRAN used call-by-reference always, Algol-60 used the (mathematically clean, but hard to implement and with surprising corner cases) call-by-name; Pascal distinguishes between call-by-value and call-by-reference ("gets the variable"). But call-by-reference has its surprises, introducing aliasing between variables. Thus Ada offers call-by-value-return too.

If caller and callee reside on different machines, the performance gain of not copying arguments in and out, just using a pointer, is lost. Even worse, doing call-by-reference is quite inefficient (need to copy back and forth each time something changes). If you are defining what to do, I'd just ditch call-by-reference, and fight users tooth and nail to keep it out.


NFA that ends with 0 and doesn't have 11 after the first 0 So as the title says i m trying to find this NFA. So far i thought to make an NFA that "guesses" what comes after the first 0 and i got this:

After some time trying to get rid of all the extra (7 !) states i put in i got to this beauty:

But now i cant figure out how to get rid of the one extra state. Also if you have any tips on how to go to simpler NFA's instead of what i did (like a thought process for this problem) i would appreciate it a lot. Thank you

Simply remove state 2, and make a transition from 1 to 5 directly. This will get rid both of a state (state 2) and a connection (the epsilon connection)


Cut edge and cut vertices If $e = \{u, v\}$ is a cut edge with $\deg(u)$ and $\deg(v)$ both at least 2, then $u$ and $v$ are cut vertices.

I want to prove or disprove this statement, but don't know how to proceed. I do know what goes wrong when one of the degrees is smaller than 2.

Let $G=(V,E)$. By symmetry it suffices to show that $u$ must be a cut-vertex.
Let $C$ be the set of vertices in the connected component of $G-(u,v)$ containing $u$. Clearly $v \not\in C$.
Let $x$ be a neighbor of $u$ distinct from $v$. Since $(x,u) \in E \setminus \{(u,v)\}$, we must have $x \in C$ and hence $x$ is disconnected from $v$ in $G-(u,v)$.
Since $G-u$ is a subgraph of $G-(u,v)$ containing both $u$ and $v$, $x$ must be disconnected from $v$ in $G-(u,v)$. The claim follows by noticing that $x$ was connected to $v$ in $G$.


Writing context free grammar I have the following language:

{0m1n0n1m | m,n ≠ 0}

I was wanting to write Context-free grammar for it. I'm a little confused
because the rule doesn't mention that m and n are not equal to each other, so could we treat them in a case as the same?

So could something like

S --> 0S1S0S1S

or

S --> 0101 | 0S10S1 | ε

For simpler language $\{1^n0^n\ | \ n > 0\}$, we can write grammar as
$S \rightarrow 1S0\ |\ 10$.

Now we can replace the non-terminal $S$ by $A$. And write context free grammar for the language in the question. $A$ is in the center of $0^m$ and $1^m$. Also remember $m,n > 0$.

$A \rightarrow 1A0 \ | \ 10$
$S \rightarrow 0S1 \ | \ 0A1$


$\sum_{x\ne 000} p(x)$ is the probability of at least one 1 in the word. It's easy to break it according the number of ones ($\#1$) in $x$
$$=3 \Pr[\#1 =1] + 3\Pr[\#1=2] + 1\Pr[\#1=3]= 0.488$$

Which is indeed equal to $(1-(p_0)^3)$ as you wrote yourself.

The entropy is being computed similarly. Just plug in $\Pr(x)$ for any possible $x\in \{0,1\}^3$. BTW, your formula is written incorrectly (I assume it is a typo). Should be
$$ H(X) = -\sum_{a_i} p(a_i) \log_2(p(a_i)).$$


Select minimal rate of growth Suppose we have algorithm that is $\Theta(n(t+n^{1/t}))$, where $t>0$ is some parameter. How to select $t$ such that the running time has a minimum rate of growth?

Source: Combinatorial Optimization by Korte and Vygen (I am going through this book by myself but sadly there are no available solutions anywhere online, it seems).

I am not very proficient with math, but my assumption is that I  need to look for $t$ s.t. the second derivative of $n(t+n^{1/t})$ would be 0 (since we are looking for minimal RATE of growth, not for the minimal value of the function itself, so $n^{1+1/t}ln^2(n) = 0$.

Is that a correct approach, or I completely misunderstood the question/concept of the rate of growth?

Here is the original exercise.

  Suppose we have an algorithm whose running time is $\Theta(n(t + n^{1/t}
))$, where $n$ is the input length and $t$ is a positive parameter we can choose arbitrarily. How should $t$ be chosen (depending on $n$) such that the running time (as a function of $n$) has a minimum rate of growth?

As others have pointed out, you misunderstood the exercise. The phrase "rate of growth" is indeed somewhat misleading.

The rate of growth of the running time of an algorithm refers to the growing behavior of the running time when the input length goes bigger and bigger. It is almost universal trend that the running time of an algorithm becomes longer when the input length becomes bigger. In particular, it is true asymptotically for the current case if we assume $t$ is a constant.

In order for the running time to have a minimum rate of growth everywhere or in average, we need the running time be the minimum when the input length is sufficiently large, since the running time for input length $n$ is the sum of all differences between the running time for input length $i-1$ and $i$, where $i$ ranges through $n_0$, $n_0+1$, $\cdots$, $n$ for some small constant $n_0$ and the running time for input length $n_0$. So, the requirement "the running time (as a function of $n$) has a minimum rate of growth" in general is just "the running time (as a function of $n$) is the minimum", as we ignore the contribution of the usually rather short running time for the small input length $n_0$. The exercise would have been clearer had it said "... such that the running time is the minimum as a function of $n$".

"How to select $t$ such that the running time has a minimum rate of growth?" The definition of $\Theta$ tells us that the running time is proportional to $n(t+n^{\frac 1t})$ within a constant factor. This question requests you to select $t$ as a function of $n$ such that, $n(t+n^{\frac 1t})$ as a function of $n$ is as small as possible. Or, once we have pulled out the factor $n$,
such that, $(t+n^{\frac 1t})$ as a function of $n$ is as small as possible

Now that we have understood the exercise, the real task is how to answer that question.

Note that $t$ increases as $t$ increases. On the other hand, $n^{1/t}$ decreases as $t$ increases, assuming $n>1$.

If we let $t=1$, then $t+n^{\frac 1t} = 1 + n$. If $t=n$, then $t+n^{\frac 1t}=n+n^{\frac 1n}= n+o(1)$. In either case, either $t$ or $n^{\frac 1t}$ is rather substantial. If we select $t$ to be some value between $1$ and $n$, we could possibly make both $t$ and $n^{\frac 1t}$ much less substantial, thus making their sum much smaller. The relevation is that we could choose $t$ such that $t=n^{\frac 1t}$ so that none of the two is particularly large.

Suppose $t_0$ as a function of $n$ satisfies $t_0=n^{\frac1{t_0}}$. Then we have
$$t_0\le\min_{t>0}t+n^{\frac 1t}\le 2t_0$$

It is an easy exercise for the interested readers to prove the above formula.

The above formula indicates that we can use binary search to find or approximate the wanted value of $t$. Fixing $n$, we will start with interval $[1,n]$. Check the middle value $t =(1+n)/2$. If $t<n^{\frac1{t}}$, replace the left endpoint 1 with $(1+n)/2$ so that we will continue with interval $[(1+n)/2,n]$. Otherwise, replace the right endpoint n with $(1+n)/2$ so that we will continue with interval $[1, (1+n)/2]$. Repeating this binary search until the interval becomes small enough. We will use either of its endpoints as the wanted value of $t$.

The above gives a simple algorithmic way to chose $t$ to make $t+n^{\frac1n}$ reach the minimum within a factor of 2. We can do better following the steps given by D.W.

  You want to find $t$ that minimizes $f(t)=t+n^{1/t}$.  This can be done by setting the first derivative to zero.  In particular, $f'(t) = 1 - (n^{1/t} \log n)/t^2$; setting this to zero yields $n^{1/t} \log n = t^2$, i.e., $$(\log n)/t + \log \log n = 2 \log t.$$

Now the problem is how to solve the above equation for $t$. Note the left-hand side is a decreasing function in $t$ and the right-hand side is an increasing function in $t$. If $t=1$, the left-hand side is greater than the right-hand side. If $t=n$, the right-hand side is greater than the left-hand side. So there is a unique solution for $t$, which is between 1 and $n$. We can use binary search to find that solution.

A couple of related results are listed here just for fun.

The selected $t$ is equal to $\frac{\log n}{\log\log n}$ asymptotically..

The minimum running time is $\Theta(\frac{n\log n}{\log\log n}).$


Why computer science papers rarely use advanced mathematics? I am a M.Sc. student in computer science, working on information networks and recommender systems. This days when I went through the top-tier conferences papers in the field I have seen most of them use solely simple machine learning tools such as generalized linear model, Expectation Maximization, Maximum Likelihood, etc.

One may argue that this simple methods work better and We shouldn't take the blame for the sake of simplicity. That is true but I have not even seen an interest to try compare their results with some more advanced mathematical methods.

I am wondering why scientists don't try to explore more mathematics to involve in their research. Because there is not something better in exploding world of mathematics or because of its difficulty, etc?

Edit: I mean the areas that are more related to continuous mathematics than CS theory.

There are many reasons that you may not see a lot of complex mathematics in the papers you are reading.

First, the tools used depend on the task at hand. If a task is simple, a simple tool might be adequate. Also, if the task runs on a simple system, a simple tool is often best.

Second, usually in Computer Science, the goal is usually to make things usable to a layprogrammer; therefore, it would be detrimental to make something depend on an advanced or abstract concept that few people understand. Often, the proofs sections of algorithms papers have much more advanced mathematics than the rest of the paper; the assumption is that anyone who wants to verify the correctness of the algorithm or its complexity can invest the time in understanding the proof, but that that is not essential to use the results.

Finally, some of this has to do with a lack of familiarity; people who spend their lives reading and writing computer science papers might never have the time to learn about new, highly complex mathematics. Actually, a great way to expand the field is to introduce a concept that many mathematicians understand in a way that it is accessible to and usable by computer scientists. (For instance, I have a friend whose PhD work applied known concepts of Control Theory to problems in Motion Planning. He did very little new work, but he did advance Motion Planning.)


Bridges and Edge Disjoint Paths So , Basically assume there is a graph $G$ which has no bridges. Is it always true that there exists two edge disjoint paths between any two vertices in the Graph ?

$\text{My Attempt at the Proof}$:-

Suppose there isn't , then there must be at-least one edge common in both the paths , and if we remove it then it disconnects $G$ and thus is a bridge. As there are no Bridges , Hence Proved !

$\text{Why I feel this Proof is incorrect }$:-

Suppose the exits three paths from u to v.

Path 1 :- $u$ ----> $E_1$ -----> $E_2$ -----> $v$

Path 2 :- $u$ ----> $E_2$ -----> $E_3$ -----> $v$

Path 3 :- $u$ ----> $E_1$ -----> $E_3$ -----> $v$

(here -----> represents some path and $E_1 , E_2 , E_3$ represent Edges.

This is an example which violates the above property. It has no bridges as well as no edge disjoint paths.

Can someone either Prove or disprove this Property ? I am really confused.

Yes, it is true that there exist two edge-disjoint paths between any two vertices in a connected bridgeless graph.

Define a closed trail as a trail whose last vertex is its first vertex. Note, a trail contains two edge-disjoint paths between any two of its vertices.

Trail combining lemma. Let $G$ be a graph.  Suppose a closed trail passes vertex $v$. Another closed trail passes vertex $u$. If those two trails share one vertex, there is a closed trail that passes both $u$ and $v$.

Proof. You can convince yourself easily by drawing a few situations. Done.

Let us prove the following proposition.

A graph is connect and bridgeless if and only if any two vertices are included in a closed trail.

Proof.

"$\Leftarrow$": Obvious.

"$\Rightarrow$": Suppose $G$ is connected and bridgeless. $v$ and $w$ are two vertices.

Let $$T_v=\{u : u \text{ is a vertex of } G \text{ such that there is closed trail that passes }v\text{ and } u\}.$$
Suppose $u\in T_v$ and $s$ be a neighboring vertex of $u$, i.e., $\{u,s\}$ is an edge.

There is a closed trail that passes $v$ and $u$ by the definition of $T_v$.
There is a closed trail that passes $u$ and $s$, since edge $\{u,s\}$ is not a bridge.

Thanks to the lemma, we have a closed trail that passes $v$ and $s$. In other words, $T_v$ contains all neighborhoods of all its vertices. That means $T_v$ (with all edges between its points) is a connected component, which must be $G$ itself. In particular, there is a closed trail that passes $v$ and $w$. Proof is complete.

A very similar characterization of bridgeless connected graphs is Robbins' theorem. If $G$ is connected and bridgeless, that theorem says we can choose a direction for each edge of $G$, turning it into a directed graph that has a path from every vertex to every other vertex.


Inherent ambiguity of the language $L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$ I went through a question asking me to choose the inherently ambiguous language among a set of options.

$$L_1 = \{a^nb^mc^md^n \;|\; m,n \geq 1\}\cup \{a^nb^nc^md^m \;|\; m,n \geq 1\}$$
$$and$$
$$L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$$

The solution said that $L_1$ is ambiguous while $L_2$ isn't. It generated the following grammar for $L_1$

$S \rightarrow S_1\;|\;S_2$

$S_1 \rightarrow AB$

$A \rightarrow aAb\;|\;ab$

$B \rightarrow cBd\;|\;cd$

$S_2 \rightarrow aS_2d\;|\;aCd$

$C \rightarrow bCc\;|\;bc$

Now for the string abcd, it will generate two parse trees; so it is ambiguous.

But a similar grammar can be created for $L_2$ too

$S \rightarrow S_1|S_2$

$S_1 \rightarrow Ac$

$A \rightarrow aAb\;|\;\epsilon$

$S_2 \rightarrow aB$

$B \rightarrow bBc\;|\;\epsilon$

And it will also generate two parse trees for abc. Why isn't it ambiguous then?

If you need,
$L_2$ can be written as $\{a^nb^pc^m\;|\; n=p \;\; or \;\; m=p\}$

The question is wrong. The second language is also inherently ambiguous. The usual way this is proved is as follows. Suppose $L_2$ had an unambiguous grammar. Let $p$ be the constant promised by Ogden's lemma, and consider the word $a^{p!+p} b^p c^p$. Mark the positions of $b^p c^p$ and apply Ogden's lemma to pump this word to the word $a^{p!+p} b^{p!+p} c^{p!+p}$ (Ogden's lemma allows us to pump some $b^q c^q$ for $q\leq p$, and $q|p!$ since $q \leq p$.) Similarly, we can get the same word by pumping $a^p b^p c^{p!+p}$. The two parse trees are different since in the first one most of the $b$s are "closely related" (in terms of least common ancestor) to $c$s, and in the second one it is the other way around.


Finding the $k$-smallest elements in a min-heap Given a min-heap $H$, I am interested in finding the $k$ smallest elements efficiently. The simplest solution would be to call delete-min $k$ times which would give us the solution in $O(k \log n)$ time. This can be improved to $O(k \log k)$ time by maintaining a separate heap $H'$ as follows. Start by inserting the root of $H$ in $H'$. Then when performing a delete-min operation, you add both children of that node in $H'$, and repeat until you have all $k$ elements. Is there a way to do better? I have a feeling that $O(k)$ should be possible, but I can't come up with an algorithm - though certainly you cannot hope to do better than $\Omega(k)$.

Edit: I would just like a hint please.

If you mean the usual binary heap represented in an array, this is answered in "An Optimal Algorithm for Selection in a Min-Heap", by  Frederickson. It is pretty complex.

Other priority queues have easier algorithms. For instance, if you use a threaded AVL tree as priority queue, you can just follow right neighbor pointers from the minimum value.


(operationalizable) Cost measure for small problems For what I know of complexity measures in CS, they are aimed at rather large problems. With today's computing power, most people don't care about comparing the complexity of simple problems as they would all be solved in about the same time.

Yet, I turn out to be interested in some cost measures for small problems. For instance, although both 12 + 14 and 123503 + 589034 can be solved in the blink of an eye by today's computers, there seems to be a sense in which 123503 + 589034 is still more "costly" than 12 + 14.

So my question is : do you know of any such cost measures that would be appropriate for such small size problems?

Note 1 : I am interested in rather general answer for all kinds of problems, the addition one being just an example.

Note 2 : the best I have found so far is Kolmogorov's complexity, but for what I understand of it, it seems awfully hard to operationalize. First it appears to be dependent on the reference language, and second, once a language is chosen, it seems really hard to prove that a description of a string is of minimal length.

Do you know of any measure which would be easier to implement?
Am I missing something about Kolmogorov's complexity and is it easier to implement than I suggest?

When we talk about complexity in computer science we are usually talking about asymptotic complexity. We are interested in characterizing the complexity of a process as the size of its inputs increase. This is useful because it abstracts away implementation-specific characteristics, such as processor speed or architecture or available memory. So while asymptotic analysis does, in this sense, concern itself with "large problems," its intent is not so much to treat large problems as it is to provide a meaningful metric for comparing algorithms in terms of time and space efficiency.

Kolmogorov complexity does not, to my knowledge, find applications in the practical analysis of programs or computational processes. It is an information-theoretic measure concerned with the minimal length of data as represented in a computational system. In so far as using it in any sort of "operational" analysis like those you've proposed, the big roadblock is that the Kolmogorov complexity of an arbitrary string is not, in general, computable!

It's difficult to pin down exactly what you're asking for, but it sounds more akin to counting CPU cycles required to execute a series of instructions. Back in the old days, when assembly language on punch-cards was the state-of-the-art, this was a fairly common technique used for optimization.

As it applies to your example, adding two numbers would involve loading them, bitwise, into registers, performing the addition, and storing the result. If the addends required more bits to represent than the size of the registers, you'd have to do it piecewise, loading and storing intermediate results as needed. You can count the cycles needed to execute tasks of varying 'difficulties' (adding two 1-byte numbers vs. adding two 2-byte numbers, for example) and compare them to give some sense of how much more or less 'complicated' the execution of a given sequence of instructions is.

It's not complexity in the traditional CS sense, but it would be a quantifiable, implementable metric. Donald Knuth has a program here that counts the cycles required to execute MMIX programs, as an example of such an implementation.


Negative simple path NP-Complete Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$

My approach was to reduce this from the Hamiltonian path and I know I should somehow force the solver to go through as many vertices as it can to get a Hamiltonian path but I am not sure how to construct such a reduction

You can reduce from the Hamiltonian path problem. Given an instance of the Hamiltonian path problem with $n$ vertices:

Add a start vertex $s$ and an ending vertex $t$.
For every vertex $v$ that is not $s$ or $t$, add edges $(s, v)$ and $(v, t)$ with weight $n-1$ and $n-2$ respectively.
For every other edge, assign it weight $-2$.

Now the previous graph has an Hamiltonian path if and only if there is a simple path with negative total weight from $s$ to $t$ in the new graph.


Is membership of x in an infinite set decidable? In order to prove a certain function to be partially computable, I need to show an $\mathbb S$-program that computes it. I could really use the predicate $X \in B$ in my program to draw my conclusion. To give you the idea of what I am dealing with here it is one of my problems:

Give an infinite set $B$ such that $\Phi(x,x)\uparrow$ for all $b \in
B$ and such that $$H(x) = \begin{cases}1 \text{ if }
\Phi(x,x)\downarrow \\ 0 \text{ if } x \in B \\ \uparrow \text{
otherwise}\end{cases}$$ show that $H(x)$ is partially computable.

I am wondering if membership for infinite set is decidable and therefore can be used to write $\text{IF } X \in B$ such program. Am I allowed?

Edit: the notation $\Phi(x,x)\uparrow$ means the function is undefined.

No, this is not allowed, in general, if we know nothing about the set $B$.

As Andrej Bauer explains in the comments: if the set $B$ is arbitrary and there are no guarantees about the set $B$ (as you state in the comments), then no, you cannot write "IF $X \in B$" in a program, as the predicate $X \in B$ might not be computable (depending upon the set $B$).

Re-reading your question, I see that you are allowed to choose a set $B$ of your choice (subject to some conditions).  If you're able to choose $B$ in a way that makes $B$ recursively enumerable, then $B$ is no longer completely arbitrary and you now have an additional condition on $B$ which makes this a straightforward homework (as Andrej Bauer also explains in the comments).


Why is Computer Architecture in $2^n$ bits? I have always wondered why is computer architecture in $2^n$ bits. We have 8 / 16 / 32 / 64-bit microprocessors or for that matter other parts of computer are also in power of 2 bits.

The only logic I could understand from my reasoning is that usually computer design process starts from lower amount of bits. For example : Say I want to design a Full adder to add 16 bit numbers. So I would first design a digital circuit to add 2 bits (one from number A and other form number B). Then I would replicate this circuit 16 times. So this will give me 16-bit full adder.

Is my reasoning correct ? Is there some other reason also ?

Not necessarily, for instance, look at the memory bus width in modern day GPUs, they would have values of 192, 384, 768(while 128, 256.... are common).

One could argue that 192 is a sum of powers of 2 (2^7+2^6), sure, but what number isn't?

That being said, any memory modules directly associated with a microprocessor or a microcontroller will have capacities in powers of 2. Traditionally registers will be 8,16, 32 or 64 bits long (though 10-bit and other non conventional widths exist).

A processor (or controller) with an n-bit register can address upto 2^n addresses (i.e, 0-(2^n)-1 bytes). Hence without changing the processor, one can extend the memory associated with it although exceeding the addressing space beyond what the processor can manage will be redundant.

In many DSPs, the memory associated with the processor is in 2^n multiples as many of the signal processing algorithms can be made very efficient when calculating this way.


Why is A(A+B) = A [Absorption Law]? Could you proof it to me that A(A+B) = A?

AA + BA [AA = A]

A + AB

Then what?

I presume you are looking for a way to prove the identity using a calculus. So far you have used distributivity an idempotency.

Recall that A = A1 so you get A1+AB and you can use distributivity again, this time in the other direction. Then two obvious steps.


Algorithm for finding best combination of elements Say I have a very large, arbitrary number of variables, each of which I can assign to be type A, B, or C.

The types come with expenses: Type A's are the least expensive, and C's are the most expensive, but their expense varies from variable to variable.
For example {A, C, C} may actually be more expensive than {C, A, A} if that first variable happens to be worth more, but we won't know how much the total cost is until we assign the types and run the program.

Also we don't want to go below a certain given total expense (can't make all A's), but get as close as possible to it.

I am trying to minimize the total expense while staying above the threshold. The search space (permutations of variable types) is too large to try all combinations.

Someone recommended sampling via Monte Carlo method earlier.
How can the Monte Carlo method, or Markov-Chain Monte Carlo, be applied to such a problem to find the optimal combination of parameters?
Could a genetic algorithm be used effectively?

You normally need to know what heuristic function you have.

Usually, when you use simulated annealing, you don't find a maximum score (or combination that gives the maximum score). What you do is trying to get a score that is better than the current score that you have.

Note that, I find it very strange when you say you want to use simulated annealing for discrete optimization problem like the one you mention. When your problem is discreet, how do you do differential? Thus, how do you know which direction you should proceed with gradient ascent/descent?

There are cases in which a seemingly discreet optimization problem is actually a continuous one in which you can use a customized and modified gradient ascent/descent with an optional simulated annealing. I will refrain from comment further in this particular case.


prove no DPDA accepts language of even-lengthed palindromes How do you prove that the language of even-lengthed palindromes, i.e.,
$L=\left\{ ww^R \mid w\in \left\lbrace 0,1 \right\}^* \right\}$, can not be accepted by a determinsitc Push-Down-Automaton?

Is there any general way to prove that a context-free language can not be accepted by a deterministic PDA? I mean something like pumping lemma maybe?

As Luke notes, there is a Pumping Lemma for deterministic CFL. If there are two strings  $zz_1$ and $zz_2$ in the language with common prefix $z$, then for deterministic devices the computation in both substrings $z$ must be the same. The idea behind that Lemma is that now also the pumping must be the same for both strings. In context-free languages pumping is of the form $uvwxy$. The Lemma states that either $vx$ are inside $z$ for both $zz_1$ and $zz_2$  or $v$ is inside $z$ and there are $x_1$ and $x_2$ inside $z_1$ and $z_2$  so we can pump both words that way.

For full details check the Lemma.

Now consider $K = L \cap ( a^*bba^* \cup a^*bba^*bba^* ) = \{ a^nbba^n \mid n\ge 0 \} \cup \{ a^nbba^{2m}bba^n \mid m,n\ge 0 \} $. If $L$ is DCFL then so is $K$. Can we pump $z_1 = a^{2n}bba^{2n}$ and $z_2 = a^{2n}bba^{2n}bba^{2n}$ in the same way? No. The $v,x$ parts are situated differently when we pump for $z_1,z_2$ which contradicts the DCFL Pumping.

Again, one has to be slightly more precise, and quote the proper parts of the Lemma.


Number of 2-3 trees of depth 4 I have a task to find a number of 2-3 trees... I don't quite know what it means, I'm asked to: find the number of 2-3 trees of depth $4$?
Is there a specific way to find number of 2-3 trees of depth $n$?

Thanks!

Here is one interpretation of this question. We want to count rooted trees with ordered children in which each internal node has either 2 or 3 children.

Denote by $T_d$ the number of 2-3 trees of depth at most $d$, so $T_0 = 1$ (the tree consisting of a single node) and $T_1 = 3$ (the tree consisting of a a single node; a root with two children; a root with three children). More generally, a 2-3 tree of depth at most $d$ is either just a single node or consists of a root with two or three children, each of which is a 2-3 tree of depth at most $d-1$. Therefore $T_d = 1 + T_{d-1}^2 + T_{d-1}^3$.

Finally, the number of 2-3 trees of depth exactly $d$ is $T_d - T_{d-1}$. For example, the number of 2-3 trees of depth exactly 1 is $T_1 - T_0 = 3-1 = 2$.


Which inductive schemes can encode the following Agda definition? Which induction schemes (e.g. induction-recursion by Dybjer and Setzer, "Irish" induction-recursion by McBride or induction-induction by Forsberg and Setzer or perhaps some simpler ones) allow one to encode the following Agda definition

  data A : Set where
    a : Maybe (List A) → A

I can think of some tricks to reformulate List in this definition so that induction-recursion becomes applicable, but are there any schemes that would allow me to first say what a list is and then refer to this information to say what A is the way it's done in Agda?

Edit: As follows from András Kovács's answer, this particular definition can be reformulated as an inductive family. Here is how to do it:

data Three : Set where one two three : Three

data AG : Three → Set where
  a'       : AG three → AG one
  nil'     : AG two
  cons'    : AG one → AG two → AG two
  nothing' : AG three
  just'    : AG two → AG three

A = AG one
ListA = AG two
MaybeListA = AG three

a : MaybeListA → A
a = a'

nil : ListA
nil = nil'

cons : A → ListA → ListA
cons = cons'

nothing : MaybeListA
nothing = nothing'

just : ListA → MaybeListA
just = just'

No scheme that I know of directly encodes that type. Sometimes it's called a "nested" inductive definition. The complication here is that Maybe and List are type constructors which are external to the signature, and we have to formalize strict positivity for external type operators in general, if we want to allow such definitions.

In other words, the consistency of A depends on the definition on Maybe and List. Some external type operators are not positive, as in:

data Neg (A : Set) : Set where
  neg : (A -> Bool) -> Neg A

data B : Set where
  b : Neg B -> B

Agda does look into all the external definitions and tries to determine the variance of type parameters. While I don't know a reference for a direct formal specification of this, an easy way to reformulate nested definitions as non-nested is to include the external type operators into a mutual inductive signature. For example:

data A : Set
data ListA : Set
data MaybeListA : Set

data A where
  a : MaybeListA -> A

data ListA where
  nil : ListA
  cons : A -> ListA -> ListA

data MaybeListA where
  nothing : MaybeListA
  just : ListA -> MaybeListA

This is an ordinary mutual inductive type, which is covered (modulo cosmetic details) by Dybjer's inductive families.


Finding the Range of Solutions for KSum Variation Preface

I asked a question before where I was looking to understand the complexity class of the following problem:

  Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$.

I had found a $O(k)$ algorithm as hinted at by the accepted answer. After playing around with the results of this algorithm, I found that it was not 100% what I was looking for.

Problem

Given a range of integers $\{a,a+1,...,b-1,b\}$, find the range of the $i^{th}$ element of all subsets of size $k$, sorted in increasing order, that sum to $s$:

For example, given $k = 3$, $a = 1$, $b = 8$, and $s = 11$ we get the following list of all possible solutions sorted in increasing order:

{ 1 | 2 | 8 }
{ 1 | 3 | 7 }
{ 1 | 4 | 6 }
{ 2 | 3 | 6 }
{ 2 | 4 | 5 }

By grouping each column, we can see the ranges of values for each of the $i^{th}$ elements in the set:

$\{1,2\}$
$\{2,3,4\}$
$\{5,6,7,8\}$

Question

I would like an algorithm that in constant time could generate the range of values for a $i^{th}$ element for all subsets summing to $s$ for a given $a$ and $b$.

 get_ith_range(int k, int a, int b, int s, int i)
    int lower_bound, upper_bound
    // Some cool O(1) algorithm...
    return (lower_bound, upper_bound)

I do not mind if it is not $O(1)$, but I feel as though there should be a way to get there at least in $O(k)$.

Attempts

Currently, I have a way to generate the smallest for the $1^{st}$ range and the largest for the $k^{th}$ range (not in constant time though). But, I have not been able to even get to where I could generate the full $i^{th}$ range in any case.

Using my solution from my previous question, I can in $O(k)$ time produce the smallest possible value and the largest:

while k:
    k -= 1
    temp = int((k)*(2*a+k-1)/2)
    if s > b+temp:
        yield b
        b -= 1
        s -= b
    else:
        yield s-temp
        while k:
            k -= 1
            yield a+k

The last value generated by the above algorithm will be the smallest possible value. Also, the first value generated is the largest possible value.

Although, the largest can be done trivially (which is how I came up with the above greedy algorithm):

# (number of values)*(smallest + largest)/2 => sum {smallest,...,largest}
temp = int((k-1)*(2*a + k - 2)/2)
if s < b+temp:
    max = b-temp
else:
    max = b

Suppose that the value at location $i$ is $j$. According to the continuity of $k$-sums (mentioned in an answer to the linked question), the range of possible sums of values at locations $1,\ldots,i-1$ is $$(i-1)a + \binom{i-1}{2},\ldots,(i-1)(j-1) - \binom{i-1}{2}.$$
Similarly, the range of possible sums of values at locations $i+1,\ldots,k$ is
$$
(k-i)(j+1) + \binom{k-i}{2}, \ldots, (k-i)b - \binom{k-i}{2}.
$$
Therefore the range of possible sums of all $k$ values is precisely
$$
(i-1)a + \binom{i-1}{2} + j + (k-i)(j+1) + \binom{k-i}{2}, \ldots, \\
(i-1)(j-1) - \binom{i-1}{2} + j + (k-i)b - \binom{k-i}{2}.
$$
We want to find for which values of $j$, the value $s$ is in this range. We get the following inequalities:
$$
(i-1)a + \binom{i-1}{2} + \binom{k-i+1}{2} + (k-i+1)j \leq s, \\
(k-i)b - \binom{i}{2} - \binom{k-i}{2} + ij \geq s.
$$
Therefore the range of $j$ is
$$
\max\left(\left\lceil \frac{s-(k-i)b + \binom{i}{2} + \binom{k-i}{2}}{i} \right \rceil,a+i-1\right) \leq j \leq \\
\min\left(\left\lfloor \frac{s - (i-1)a - \binom{i-1}{2} - \binom{k-i+1}{2}}{k-i+1} \right \rfloor,b-k+i\right).
$$


Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron? The feasible region of a Linear Program (LP) is $\{x \in {\bf R}^n: Ax \le b, x\ge 0 \}$. This is an intersection of halfspaces, a polyhedron. If the LP is bounded and feasible, its optimal value will be attained on some face of the polyhedron, typically a vertex. A vertex is a point determined by the intersection of n hyperplanes bounding the halfspaces with linearly independent normal vectors. There might be more than n hyerplanes through a vertex. A basis is any subset of bounding hyperplanes that determines a vertex. Some inequalities will be the nonnegativity inequalities, the corresponding variables are called nonbasic and the rest basic. Only the basic variables can take nonzero values.

These are some lecture notes that I'm struggling to understand. Why does the optimal value not lie in say, the center of the polyhedron? Why must the optimal value be on the face or on a vertex? It seems arbitrary to me because there are so many points that lie on the faces. The center makes more sense to me.

Could anyone give me an intuition?

Suppose $P = \lbrace x: Ax \leq b \rbrace$ is the polyhedra, where $x \in \mathbb{R}^n$. Further assume $P$ is full dimensional, then let $x_0$ be some interior point in P. Let $c \in \mathbb{R}^n$ (and $c \neq 0$) be the objective function you are interested to minimize (say). Then since $x_0 \in int(P)$, there exists a ball $B$ centered at $x_0$ with radius $\epsilon > 0$ s.t. $B \in int(P)$. Now consider any unit vector say $u \in \mathbb{R}^n$ s.t. $c^t u \neq 0$ (notice that it is always possible to select such a $u$), then both ($x_0 + \epsilon * u$) and ($x_0 - \epsilon * u$) are in  $B$, so by extension also in $P$. Now evaluate the function at 3 points, namely $x_0, x_0 + \epsilon * u, x_0 - \epsilon * u$. The objective you would get are-:
$c^T x_0 , c^T  x_0 + \epsilon (c^T  u) ,  c^T  x_0 - \epsilon (c^T  u) $. Clearly if since $c^T  u \neq 0 $, one of $c^T  x_0 + \epsilon (c^T  u) ,  c^T  x_0 - \epsilon (c^T  u)$ must be lower than $c^T x_0$. This illustrates that the objective at $x_0$ is greater than some other point on the ball, hence $x_0$ cannot be optimum. You can repeat this argument for every other interior point and claim that such an interior point cannot give the optimum. Hopefully this gave you the intuition. More generally, suppose a point $x \in P$, can be represented as convex combination of 2 other points $y, z \in P$, we can repeat the same type of argument and say that the objective at $x$ cannot be strictly lesser than the objectives at both $y$ and $z$. A vertex is an example of a point that cannot be represented as convex combination of 2 other points from the same polyhedron.


Bipartite Graph in a Digraph How do you find a sub-digraph in a digraph such that the in degree and out degree of each vertex is 1. My professor told in the class that an algorithm can be build for it using bipartite matching but I have not able to do so. I am just looking for hints on how to proceed because I am kind of stuck on where to start.

Any simple cycle satisfies the conditions, so you can use any standard algorithm for finding cycles in a directed graph.

For example: decompose into strongly connected components.  Pick one component.  Start following an arbitrary walk through vertices within that component.  As soon as you hit a vertex the second time, you can construct a cycle.


context free grammar to NFA I've been given an exercise to solve which goes as follows:
generate an NFA from the given CFG,

$$\begin{align*}S &\to AB \mid c\\
A &\to aAb \mid c\\
B &\to bBa \mid c\ .
\end{align*}$$

Now correct me if I'm wrong, but if this language has an NFA it means it is regular.
But looking at this grammar the language described is
$L=\{a^n cb^{n+k}ca^k\mid n,k\geq 0\}$.
If so, I can use the pumping lemma by taking the promised number $n$, choose the word $a^ncb^{n+k}ca^k$, for $xyz$ we get $x=a^s$, $y=a^t$ ($t\ge1$), then I can pump for $i=2$ and get $a^{n+t}cb^{n+k}ca^k$ which is not in the language. Hence the language is not regular and that means there can't be an NFA for it.

I might have done something wrong but I cant see it. Any suggestions?

You can use the pumping lemma to show that $L$ is not regular and by definition you can't generate NFA. Maybe the question is wrong and they want you to generate a pushdown automaton (PDA).


Proving program termination in the $\lambda$-calculus Turing's Checking a large routine:

Finally the checker has to verify that the process comes to an end.
Here again he should be assisted by the programmer giving a further
definite assertion to be verified. This may take the form of a
quantity which is asserted to decrease continually and vanish when the
machine stops. To the pure mathematician it is natural to give an
ordinal number.

How do you apply this to a program written in the untyped $\lambda$-calculus?

This may take the form of a quantity which is asserted to decrease continually and vanish when the machine stops.

Lambda calculus evaluation is a sequence of beta reduction steps. So for the lambda calculus (with or without types: types don't affect evaluation), you want a quantity (a positive integer) that decreases at each reduction step.
Such a quantity exists if and only if the lambda-term is normalizable (according to a chosen reduction strategy $\to$). Proof: suppose there is a function $f : \mathbf{\Lambda}(M_0) \to \mathbb{N}$ where $\mathbf{\Lambda}(M_0)$ is the set of lambda-terms $M$ such that $M_0 \to^\star M$, such that if $M \to M'$ then $f(M) \lt f(M')$. Then the length of a reduction chain from $M_0$ is bounded by $f(M_0)$ and in particular cannot be infinite, so $M_0$ is strongly normalizable. Conversely, if $M_0$ is strongly normalizable, define $f(M)$ as the length of the longest reduction starting at $M$.


Counting the number of multiples of number A that perfectly divides the number B What is the best way of counting the number of multiples of number A that perfectly divides the number B.

This is the sub problem for one of the questions I am solving on codechef.
This is the best I could come up with.

int func(int A,int B){
    int res = 0;
    int i = 1;
    while(A * i <= B){
        if(!(B %(A * i))){
            res++;
        }
        i++;
    }
    return res;
}

However,this is timing out for some of the cases. I am told that this can solved in O(sqrt(n)). Any help would be appreciated.

Start by checking whether $A$ divides $B$. If it doesn't, we're done, the answer is $0$. If it does, let $C = \frac{B}{A}$. The numbers you're looking for are all of the form $AM$ where $M$ divides $C$, so all you need is the number of divisors of $C$.

Let $C=p_0^{c_0}...p_n^{c_n}$ be the prime decomposition of $C$. The number of dividers of $C$ is then $\prod\limits_{i}(c_i+1)$, so the problem boils down to the prime decomposition of $C$, which can indeed be done in $O(\sqrt{C})$:

residue = C
divider = 2
number_of_prime_dividers = 0
factors = empty array
while((residue >= divider) and (divider <= sqrt(C))
{
    if(divider divides residue)
    {
        number_of_prime_dividers = number_of_prime_dividers +1
        factors[number_of_prime_dividers] = 0
    }
    while( divider divides residue )
    {
        residue = residue / divider
        factors[number_of_prime_dividers] = factors[number_of_prime_dividers] + 1
    }
    divider = divider + 1
}
if(residue != 1)
{
    number_of_prime_dividers = number_of_prime_dividers +1
    factors[number_of_prime_dividers] = 1
}

This algorithm works because by construction, every time dividerdivides residue, then it means that divideris prime (if divider is composite then all the factors of divider are strictly smaller than divider and thus have already been removed from residue). Once we reach sqrt(C), if residue != 1 we know that residue is prime, which concludes the decomposition.


Is model theory useful for computer scientists It is often stated in the CS folklore that Turing was inspired by Gödel's incompleteness theorem, more specifically the diagonalization proof and the isomorphism between axiomatically generated statements (Gödel numberings).

Are there other such links between model theory and computer science? Should a computer scientist be interested in model theory?

A special case of model theory is finite model theory which is closely related to complexity theory and database theory. However the methods being used in classical model theory (e.g. types, stability theory, forcing, large cardinals etc) are geared towards infinite models and assume compactness. Hence they don't appear to be useful in computer science.

A second connection that is not well-known is with program verification and program logics. Model theoretic techniques like  quantifier elimination and skolemisation come from model theory, but are now at heart of verification tools. Questions of importance in program logics like Hennessy-Milner theorems are in the language of model theory simply model-theoretic characterisations of the elementary equivalence (a model theoretic concept) on models of the logic. In many logics coming from program verification, the elementary equivalence is some variant of bisimulation, a concept invented independently in computer science. More examples along those lines could be given.

In summary, there is a lot of overlap, but the communities have been developing separately, use different terminology and have different focus (model theory: infinite, CS: finite and efficient), so currently both communities don't have much to say to each other.


Constructing all context-free languages from a set of base languages and closure properties? One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining them via a small, fixed set of closure properties. Specifically, if we start with the empty language, the language containing the empty string, and the languages of all single-character strings, we can assemble all possible regular languages using union, concatenation, and Kleene star.

Is there a set of base languages and closure properties that can be used to generate all and only the context-free languages? (To clarify: I'm not asking whether you can write regular expressions for all CFLs, which I know is impossible. Instead, I'm wondering whether there is a way to design a regular-expression-like framework for CFLs based on the same basic principles.)

That is possible, but perhaps not exactly in the way you ask. As a start take the Dyck language $D_2$ of all strings of matching brackets over two pairs of brackets, say $\{ [,], (,) \}$, or more abstractly $a_1,b_1,a_2,b_2$.

Then every context-free language can be obtained from $D_2$ using homomorphisms, inverse homomorphisms and intersection with regular languages. The context-free languages are called "the principal cone generated by $D_2$", in old books denoted $\mathcal{M}(D_2)$. See a related question: "Which languages are recognized by one-counter machines?"

In fact, we need only one of each operations (well-chosen). Each CFL can be written $g(h^{-1}(D_2) \cap R)$, where $g$, $h$ are homomorphisms, and $R$ is a regular language. Intuitively, $R$ is a program of a PDA, $g$ maps each instruction to the letter read, $h$ to the push and pop operations of the stack. Finally $D_2$ codes proper stack behaviour.

This result is related to the Chomsky–Schützenberger Theorem (or as can be seen in wikipedia, one of them). The statement linked here in wikipedia (a) does not need an inverse homomorphism, while (b) it does not restrict to two pairs of brackets.
Theorems of this type are from the area of "Abstract Families of Automata", where Ginsburg and Greibach are important names. A related result by Nivat states that operations of the form $L \mapsto g(h^{-1}(L) \cap R)$ for fixed $g,h,R$ are the finite state transductions.


Is the language of TMs that halt on some string recognizable? I would like to show that the following language is recognizable:
$$L:= \{ \langle M \rangle \mid M \text{ is a TM that halts on some string}\}.$$

How do I go about showing that this language is recognizable? I know that all recognizable languages are reducible to $HALT_\epsilon$, so I figure if I can show that this language reduces to $HALT_\epsilon$, then I am all set. I am defining $HALT_\epsilon$ as follows:

$$HALT_\epsilon:= \{ \langle M \rangle \mid M \text{ is a TM that halts on } \epsilon \},$$

where $\epsilon$ is the empty string. We can reduce $HALT$ on $x$ to $HALT_\epsilon$ by a reduction $F(\langle M, x\rangle) = \langle M' \rangle $, where $M'(y) = M(x)$. For this reduction, we just ignore the input string $y$, which we know will be $\epsilon$ and just run $M$ on $x$ instead. Here, $HALT$ is defined as

$$HALT:= \{ \langle M,x \rangle \mid M \text{ is a TM that halts on } x \}.$$

I tried leveraging a similar technique to show that $L$ is recognizable, but I could not come up with anything better than this (somewhat crazy) TM that has a $HALT_\epsilon$ oracle:

$ D^{HALT_\epsilon} =$ On input $\langle M \rangle:$

Construct $N = $ "On input $x:$

Run $M$ in parallel on all inputs $y\in \Sigma^*$.
If $M$ halts on any $y$ then accept, otherwise loop."

Query the oracle to determine whether $\langle N \rangle \in HALT_\epsilon$.
If the oracle answers YES, accept; if NO, reject.

Note: My notation for TM algorithms is based on "Theory of Computation" by Sipser. Step 2 for the definition of $N$ is a bit redundant, but in this type of context, is it okay to say something like "If $M$ halts on any $y$, then halt?"

I think all I have shown here is that $L$ is decidable relative to $HALT_\epsilon$. I don't know if this implies that $L$ is recognizable. Can a Turing reduction be used in this manner to show that a language is recognizable? I'm confused as to what it means for a language to be recognizable. The task seems obvious if we go back to the definition: If some TM $R$ accepts strings in $L$, then $R$ recognizes $L$. So what if $R=D^{HALT_\epsilon}$, and in the body of $D^{HALT_\epsilon}$ we use some crazy reduction like $N$?

In general, to show recognizability, can we just come up with a reduction like $N$ that may or may not halt? Is it a problem that $N$ will never halt if $\langle M \rangle \notin L$?

You can construct a recognizer following the same principle used for the recognizer for HALT. The only extra bit is how you check "all" inputs without getting stuck in a non-terminating computation.

An important technique you can use here is called dovetailing (expressed with inputs from $\mathbb{N}$):

Simulate one step of $M$ on $1$.
Simulate two steps of $M$ on $1$ and $2$ each.
Simulate three steps on $1$, $2$ and $3$ each.

$\quad\vdots$

Terminate and accept once any of the simulated computations terminates and accepts.

If there is a halting input of $M$, this dovetailed simulation certainly finds it after finite time. If there is none, it loops and is correct in doing so.

This is, in essence, your $N$ (with an explanation why it's actually a computable function). You don't need the rest of the reduction in order to show that $L$ is semi-decidable.


Algorithm for finding 2 missing items in a stream of integers I saw this post and wondered why the approach described in the accepted answer works. The same problem and solution is described a bit nicer here.

So let's say we receive a stream of $n-2$ pairwise different numbers $a_1 + a_2 + \cdots + a_{n-2}$, from the set $\left\{1,\dots,n\right\}$. What I learned from the above post is that for the problem of finding 2 missing numbers $x$ and $y$, given a stream as described above, can be solved by finding the solution to the following system of equations:

\begin{alignat*}{4}
 x+y & {}={} & \dfrac{n(n+1)}{2} - (a_1 + a_2 + \cdots + a_{n-2}) \\
 x^2 + y^2 & {}={} &  \dfrac{n(n+1)(2n+1)}{6} - (a_1^2 + a_2^2 + \cdots + a_{n-2}^2)
\end{alignat*}

Now it is easy to convert this into a single pass algorithm which supposedly returns the two missing numbers for a given stream.

How would one prove this algorithm's correctness?  I think showing that the system must have exactly two solutions would be enough to prove correctness but I'm not sure how to approach this?

How can I convince myself (and others) that the algorithm is correct?

Suppose that $x + y = A$ and $x^2 + y^2 = B$. Then
$$ xy = \frac{(x+y)^2 - (x^2+y^2)}{2} = \frac{A^2-B}{2}. $$
Consider now the polynomial
$$ (t-x)(t-y) = t^2 - (x+y)t + xy = t^2-At + \frac{A^2-B}{2}. $$
The polynomial on the right has the two roots $x,y$.

If $x + y = z + w$ and $x^2 + y^2 = z^2 + w^2$ then both $x,y$ and $z,w$ are the two roots of the same polynomial, and so $\{x,y\} = \{z,w\}$.


How do I find depth and height of all nodes in a bounded semilattice? I'm writing a program where I have a bounded semilattice (it has a root element at the top, all edges point downwards, and a node may have multiple parents). I need to precompute each node's depth (the max number of edges from the root node) and height (the max number of edges to any leaf). I have a naive implementation for just the heights where every node is compared to all it's descendants, so probably O(n^2). What is a faster algorithm that computes both height and depth?

If you do a topological sort and then traverse the nodes in reverse topologically sorted order, you can annotate each node with its height in linear time.  Similarly, you can annotate each node with its depth in linear time by traversing in topologically sorted order.  This achieves linear running  time, which is significantly faster than the quadratic time approach you mention.


Standard or Top Text on Applied Graph Theory I am looking for a reference text on applied graph theory and graph algorithms.  Is there a standard text used in most computer science programs?  If not, what are the most respected texts in the field? I have Cormen et al.

I would take a look at the free book by Bondy and Murty: Graph Theory with Applications. This book is less-algorithmic and more graph-theoretical than other resources recommended here. There is also a newer version of the book, which is not available for free on the net, but is extremely well-written and with updated notation. In comparison to other free books on graph theory (as for example Diestel), Bondy/Murty uses a less formal approach to prove and explain the theory.

The reason I have used it, is because it is the primary text-book in the course on Graph Theory at The Technical University of Denmark, lectured by Carsten Thomassen, in which I have been assistant teacher for 2 years.