Do determinacy of one-step evaluation and uniqueness of normal forms apply to all (or most) languages in TAPL? In Types and Programming Languages by Pierce, when talking about untyped arithmetic expressions in Chapter 3, there are two theorems:

$-→$  is single-step evaluation relation:

  3.5.4 Theorem [Determinacy of one-step evaluation]: If $t -→ t'$ and $t -→ t''$ , then $t' = t''$ .

$-→ ∗$ is multi-step evaluation relation:

  3.5.11 Theorem [Uniqueness of normal forms]: If $t -→ ∗ u$ and $t -→ ∗ u'$ , where $u$ and $u'$ are both normal forms, then $u = u'$.

Do the two theorems also apply to all (or most) the other languages/systems in the book, or only to the untyped arithmetic expressions?

From my limited experiences in a few programming languages, it seems that an expression is always evaluated in exactly one deterministic process, so I wonder if both theorems apply to all the languages.

Thanks.

Uniqueness of normal forms definitely applies. This is still a theorem you have to prove, but if it doesn't hold, what you have isn't really a normal form. The whole point of normal forms is that there's a unique form for each value, that's what makes it "normal".
For determinancy, I think it holds for most languages in the book. Usually when you're defining a small step semantics, you try to do it in such a way that it's deterministic. However, there are notable exceptions to this. First, if you have a general rewrite system, like the untyped lambda calculus, then it's totally valid to have non deterministic reductions. This is what lets us talk about Church Rosser and the diamond property. Secondly, if you have a language with any sort of concurrency, then you probably want to have non deterministic rules, to model the different possible orders of evaluation, so that you can show your language is well behaved regardless of which interleaving is taken.

That said, I want to be clear that these things do not come for free. They hold for the Languages in the book because Pierce has been very careful to ensure they hold. It is easy to accidentally definite a language where these do not hold.


Is the equality of two DFAs a decidable problem? So given two DFAs, is the problem of finding if they generate the same language a Decidable problem?

I already know that Equality of two CFL is not Decidable

but what about Equality of two DFAs? considering most of the problems with DFAs are decidable, is this decidable as well ?

In order to decide whether the languages generated by two DFAs $A_1,A_2$ by the same, construct a DFA $A_\Delta$ for the symmetric difference $L(A_1) \Delta L(A_2) := (L(A_1) \setminus L(A_2)) \cup (L(A_2) \setminus L(A_1))$, and check whether $L(A_\Delta) = \emptyset$.

Here are some more details. You can construct $A_\Delta$ using the product construction: construct a product automaton, and use $(F_1 \times \overline{F_2}) \cup (\overline{F_1} \times F_2)$ as the set of accepting states.

In order to check whether $L(A_\Delta)$ is empty or not, it suffices to check whether some accepting state is reachable from the initial state, and this can be done using BFS/DFS.


Proving decidability Regarding the following languages $L_1$ and $L_2$, I want to prove that $L_1$ is decidable and $L_2$ is undecidable. I want to construct a turing machine which can decide $L_1$ and reduce the halting problem to $L_2$.
$L_1$:
On input $w$ the turing machine $M$ never moves it's reading/writing head left. Where $w \in \{0,1\}^*$ and $\langle M \rangle \in \{0,1\}^*$ is the input of $L_1$.
$L_2$:
On input $w$ the turing machine $M$ moves it's reading/writing head in every step (making no neutral move). Where $w \in \{0,1\}^*$ and $\langle M \rangle \in \{0,1\}^*$ is the input of $L_2$.
For $L_1$: I know that a turing machine which can't move left, has no possibility of memorizing it's progress. It only knows the state it's in, so it's similar to a DFA. The difference is, that it reads and/or writes $\{0,1\}^*$ and the blank symbol $\square$. It's also different to a right-moving turing machine because it can do a neutral move. My idea was to construct a $TM$ having two tapes. So that the original tape would scan the input and 'copy' it to the second one. The problem I came across is that I have no possibility of recognizing any loop cycles, so that if $w$ was finished, the $TM$ would never stop writing blank symbols because the tape is infinitely long. Another idea was to construct a $TM$ in which no state has a self-loop. But in this situation I still wouldn't have prevented this infinite writing and I need a $TM$ which halts on every input to prove $L_1$ is decidable.
For $L_2$:
I want to reduce the halting problem $H = \{w\#x \mid M_{w}$ halts on $x\}$ to $L_2$ so I can prove that $L_2$ is undecidable. I had the idea of this function $f(<M>,x) \mapsto$ $<M'>\#w\#x$ where I put the input of $H$ into the function and get the input for the $TM$ $M_{{L}_{2}}$ which simulates $L_2$. In addition to that I know that the definition of $M_{{L}_{2}}$ states how it never makes a neutral move but always moves and reads either left or right.

For $L_1$, consider a computation $T(w)$ of a Turing machine $T$ that never moves its head to the left with input $w$. Let $\Gamma$ be the tape alphabet (including the blank symbol) and $Q$ be the set of states of $T$.
Notice that, at any given step during the computation, the future behavior of $T(w)$ is completely determined by:

The current state.
The tape symbol in the current cell.
The contents of the (infinitely many) tape cells on the right of the head.

There are $|Q|$ choices for 1, $|\Gamma|$ choices for $2$, and $\max\{|w|,1\}$ choices for 3 (since the contents of the tape to the right of the head are always a suffix of $w$ distinct from $w$, followed by infinitely many blank symbols).
To decide $L_1$ it suffices to simulate $T(w)$ for $\eta = |Q| \cdot |\Gamma| \cdot \max\{|w|,1\} + 1$ steps. If $T(w)$ moves its head to the left during the simulation, then reject. Otherwise accept. To see that accepting is the correct choice notice that if $T(w)$ does not terminate within $\eta$ steps, then a state must be repeated at least twice, implying that $T(w)$ is in some loop. This loop can only involve states that appeared at least once during the first $\eta$ steps, showing that $T$'s head will never move to the left.
For $L_2$ see this question.


Recursive definition of sum of two numbers in terms of the successor function This is a question from the book Data structures using C and C++ by Tenenbaum. Not a homework problem but self-study.

  Recursive definition of a+b, where a and b are non-negative integers, in terms of successor function succ defined as

  succ(int x)
      {
          return(x++);
      }

I have been thinking how is it possible? Can I change the function? I am not sure from the problem definition in the book. So how can this be done?

Here is a hint:

  a + 3 = succ(succ(succ(a)))

Also, by definition, every natural number is either 0 or the successor of some (smaller) natural number.


Hashing by doing modulo $m$ for $m=p^2$ for a prime $p$ instead of using a prime $m$ - is it that bad? I am doing an exercise from a Big Data course I'm taking on Coursera (this exercise is for experimenting with a big-data problem and is not for any credit or homework) , the assignment was described briefly:

  Your task is to quickly find the number of pairs of sentences that are at the word-level edit distance at most 1. Two sentences S1 and S2 they are at edit distance 1 if S1 can be transformed to S2 by: adding, removing or substituting a single word.

I am then given a large txt file that contains about $10^6$ sentences.

The way I tried to attack this problem:

Observation $1$: If the length of two sentences is greater then $1$ then they are not at an edit distance $1$.

Observation $2$: Let $A_1,...,A_5$ be five consecutive words from a sentences and let $B_1,...,B_5$ be another five consecutive words chosen from different indexes (that is if we label the words of a sentence then $B_i$ and $A_j$ does not share an index.

Five is a small arbitrary number I chose

I used something like a curried syntax to get a hashtable that keeps a 3-touple: $(X,Y,Z)$

Where I mapped each sentence as follows:

$X$ is the number of words the sentence have.
$Y$ is obtained by a hash function on the content of the words (I will soon describe this hash function)
$Z$ is a list of integers containing the index of the line in the document [the line number] that was mapped to $(X,Y)$

In C# this corresponds to an object of a type

Dictionary< int, Dictionary< int, List< int>>>

So I kept two Hashtables of the above form, where I took the first five words to hash and get $Y$ and words $6-10$ to hash and get another value of $Y$.

Then given a sentence - compute the two $Y$ values it would of gotten and look at buckets with length that differs at at most $1$ from this sentence length and share one $Y$ value this sentence.

Let me describe the hashing function I used to get $Y$ -

I took the $A_i$ (similarly with the $B_i$) and concatenated them
I looked at this string as a byte array (that is by the bits that takes to represent the numbers) I then applied a the SHA-1 hash function on it (there are no security reasons for this but I wanted something that hashes well)
I took the last $4$ bytes in the SHA-1 hash and I looked at it as a positive integer (by looking at the last $32$ bits and considering it as an integer then applying the absolute value function). Call this result $R$

$Y= R\%p^{2}$

where $p$ was chosen as follows: I counted how many lines of a given length $l$ appear (say $n_l$), for lines of length $l$ I chose $p$ s.t $$\frac{n_l}{p^2}\leq 3$$

the following is a Histogram showing $n_l$ as a function of $l$

which should give some indication of the values chosen for $p$.

However - There are too many collisions - I get about $6$ elements in each bucket.

I took one example of such a bucket and I printed those sentences (I hoped they are similar so they would have a good reason to be mapped to the same bucket) by they are very different from one another. This is a printscreen of those sentences printed to the console.

Question: Why do I get a large number of collisions ?($6$ in average on $10^5$ buckets I considered where if I had even distribution I would expect $3$ from the choice of $p$, some buckets have a few tens of elements in them)

Could the problem be that I used modulo a square of a prime and not a prime ? is it that significant?

There are a lot of things which could have gone wrong, but it is really hard to say, especially since you don't tell us the bad values of $n_l$ and $p^2$. So for now, here are some comments:

SHA1 is slow relative to non-cryptographic hashes. If you are lucky then your programming language already has a fast hash implementation.
There is no need to take the absolute value of the last 32 bits. Instead, consider it as an unsigned integer (unless you're using a language such as Java which doesn't have them).
Since the last 32 bits of the SHA1 hash are very random, you can take them modulo any modulus that you want (assuming it is small compared to $2^{32}$). There is no particular advantage in choosing a prime or a prime power.
Due to the random nature of the hash, you don't expect sentence snippets falling into the same bucket to have anything in common, unless they're exactly equal.
If everything is random and $n_l/p^2$ is very small compared to $n_l$ then you expect the distribution of balls in each bucket to be roughly Poisson with expectation $n_l/p^2$. Assuming this, for $n_l/p^2 = 3$, the probably to get at least 6 balls in some bucket is roughly $0.084$, so you would expect this fraction of buckets to contain at least 6 balls. Assuming a maximum value of roughly $100,000$ buckets (my estimate from your graph), you expect to see 7 buckets having at least 12 balls. You shouldn't be getting buckets with a few tens of elements, though: the probability of having any bucket with at least 20 balls is at most $8 \cdot 10^{-6}$, for example.

In view of this, I suggest you pick some particular experiment and compare the distribution of the number of balls in buckets to the corresponding Poisson distribution. If you find any major discrepancy (an ill-defined concept), let us know the exact values of $n_l$ and $p^2$ you used.


Given a string, is it possible to determine which hashing algorithm has produced it, if any? Given a string, is it possible to determine which hashing algorithm has produced it, if any?

For example, the MD5 hash of "string" is b45cffe084dd3d20d928bee85e7b0f21.

Is it possible to determine whether the above hash is:

1) Indeed a genuine hash in some hashing algorithm, as opposed to a string of characters that is not a hash produced by one of some set of algorithms

2) a definite hash of a specific hashing algorithm?

Possible methods:

1) For hashes susceptible to rainbow-table attacks, it would be viable to search for the hash in such a rainbow table for various algorithms, to find a match; if a match is found, we know which algorithm produced it.

You will first need to define what you mean by a hashing algorithm. For example, my favorite hashing algorithm is simple: check whether the input is "string", and if so, output "b45cffe084dd3d20d928bee85e7b0f21", otherwise output "error".

In the simplest case, you have one algorithm $A$, and string $w$ and you are wondering, is there an input $x$ (and maybe a seed $s$) such that $A(x,s)=w$? You can try brute force, but if you have the source code, is there something more clever that you can do? If not, then your algorithm is a one-way function. Whether one-way functions exist is an open question. We know that if one-way functions exist, then $P\ne NP$, and therefore if $P=NP$, one-way functions do not exist, but that still leaves three possibilities.


Papadimitrou and standard landau notation This is a homework. I'd appreciate if you didn't give away answer straightaway but instead pointed me to the right direction.

From huge majority of sources the definition of $\mathcal{O}(n)$ is:

$f, g : N \to R^+$

$f \in \mathcal{O}(g) \Leftrightarrow \exists{c,n_0} \in N \> \forall n > n_0 : f(n) \leq c\cdot g(n)$

but in Papadimitriou's book there is a different definition I haven't seen anywhere before:

  The order of $f$, denoted $\mathcal{O}(f)$, is the set of all functions $g:N\rightarrow N$ with the property that there are positive natural numbers $c>0$ and $d>0$ such that, for all $n\in N$, $g(n) \leq c \cdot f(n)+d.$

I assume the first definition evaluates the functions as continuous functions whereas the second definition is concerned only about the points on $n \in N$. Therefore undefined values that asymptotically goes to $\pm\infty$ are not an issue anymore.

For example if we take $f(n)=\frac{1}{n}$ and $g(n)=1$.
We know that $f(n)\in g(n)$ because $\lim_{x\to\infty}\frac{\frac{1}{x}}{1}=0$. We find the value for $f(1)$ and raise the $g(n)$ above this point such as:
$f(n) \leq 6\cdot f(n)$ or $f(n) \leq f(n)+6$

Is my assumption correct? If it is how can I prove this equivalence?

The two definitions are not equivalent. However, the case where they aren't equivalent is one that we aren't interested in for algorithm analysis.

The standard definition implies the Papadimitriou definition. The proof is fairly straightforward, by following the definitions carefully.

   Suppose that $\exists c, n_0 \in \mathbb{N}, \forall n \gt n_0, f(n) \le c \cdot g(n)$. Let $c$ and $n_0$ be such constants. We want to prove that there exist $c',d' \in \mathbb{N}^*$ such that $\forall n \in \mathbb{N}, f(n) \le c' \cdot g(n) + d'$. Take $c' = c$ and $d = \max\{f(x) \mid x \le n_0\}$. If $n \le n_0$ then $f(n) \le d'$; if $n \gt n_0$ then $f(n) \le c \cdot g(n)$. Either way, for any $n \in \mathbb{N}$, $f(n) \le c' \cdot g(n) + d'$.

The converse is not true. Again, unfolding the definition works up to a point, but then one little extra assumption is needed to make the proof go through.

   Suppose that we have $c', d'$ such that $\forall n \in \mathbb{N}, f(n) \le c' \cdot g(n) + d'$. We want to find $c$ and $n_0$ such that $\forall n \ge n_0, f(n) \le c \cdot g(n)$. If there is an $n_0$ such that $\forall n \ge n_0, g(n) \ge 1$, then we can factor $g(n)$: for any $n \ge n_0$, $f(n) \le (c' + d'/g(n)) g(n) \le (c' + d') g(n)$, so we can take $c = c' + d'$.

The case where this proof fails is when there is no $n_0$ such that $\forall n \ge n_0, g(n) \ge 1$, i.e. when there are infinitely many integers $x$ such that $g(x) = 0$. (More generally, for real-valued functions, the problem case is when there is a set of values $(x_k)_{k\in\mathbb{N}}$ such that $\lim_{k\to\infty} x_k = \infty$ and $\lim_{k\to\infty} g(x_k) = 0$. Equivalently, that means that $g$ has no positive infimum.) Under the Papadimitriou definition as quoted here, the order of such a function includes all constants, but under the standard definition, there has to be a cutoff point above which $f$ is zero when $g$ is zero. For example, take the function $g : \mathbb{N} \to \mathbb{N}$ defined by $g(x) = 1$ if $x$ is odd and $g(x) = 0$ if $x$ is even. The function $f(x) = 1$ does not satisfy $f \in O(g)$ under the standard definition, but it does under the Papadimitriou definition.

This corner case isn't important in algorithm analysis because complexity functions are never “really” zero. With space complexity, there's always a bit of stack space just for the function call. With time complexity, it takes a few instructions to call a function even if the function does nothing.


Drawing an implication graph for 2-SAT clauses I am trying to convert the following 2-sat clauses to implications and then draw the implication graph.

The clauses are: {¬xvy}, {¬yvz}, {¬zvw} ,{¬wvu},{¬uv¬x},{xvw},{¬wvx}

I converted the boolean literals into implications so I could construct the implication graph:

{¬xvy}: I have x-->y and ¬x -->¬y

{¬yvz} : I have y-->z and ¬y-->¬z

{¬zvw} : I have z-->w and ¬z-->¬w

{¬wvu} : I have w-->u and ¬w--->¬u

{¬uv¬x} : I have u-->¬x and ¬x-->¬u

{xvw} : I have ¬x-->w and ¬w-->x

{¬wvx} : I have w-->x and ¬w-->¬x

Am I doing this right? If so, I have constructed this implication graph to prove it is not satisfiable.

I would argue that these literals are not satisfiable because of the infinite loops you can have from ¬w ¬x ¬y ¬z ¬w and w x y z w. Is this a sufficient enough explanation?

Thanks in advance!

{¬uv¬x} : I have u-->¬x and ¬x-->¬u

LMFTFY:

$$(\neg u \vee \neg x) = \left[(u \implies \neg x) \wedge (x\implies \neg u)\right]$$

  {¬wvx} : I have w-->x and ¬w-->¬x

LMFTFY:

$$(\neg w \vee x) = \left[(w \implies x) \wedge (\neg x\implies \neg w)\right]$$

From this you get the following graph:

graphviz source

And the strongly connected components (there is only one):

graphviz source

And we get $\left\{u,\neg u,w,\neg w, x,\neg x,y,z,\neg z\right\}$, obviously a contradiction (the elements of this set implies each-other).

  I would argue that these literals are not satisfiable because of the infinite loops you can have from ¬w ¬x ¬y ¬z ¬w and w x y z w. Is this a sufficient enough explanation?

It isn't the "infinite" loops that make it unsatisfiable. "infinite loops" or cycles, make strongly connected components; and a 2sat formula is satisfiable iff (if and only if) there are no contradicting terms in any of its strongly connected components. In this graph there are clearly contradicting terms in the one large strongly connected component, as I demonstrated above, therefore it is unsatisfiable.


How can I quantify the number of swaps required for insertion sort? Based on the Wikipedia implementation of insertion sort:

Given an input array $A$:

for i ← 1 to length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1

is there a way to quantify how many swaps are needed to sort the input list? It's $O(n^2)$, but I want a more precise bound. A perfectly sorted array clearly needs no swaps (so insertion sort is $\Omega(n)$), while a completely reversed array requires something on the order of $n^2$ swaps, but how do we quantify the number of swaps?

It is a classic exercise to relate the running time of insertion sort to the number of inversions in the input. An inversion is a pair of indices $i < j$ such that $A[i] > A[j]$. The number of comparisons made by insertion sort when there are $I$ inversions is always between $I$ and $I+n-1$.


Which kind of branch prediction is more important? I have observed that there are two different types of states in branch prediction.

In superscalar execution, where the branch prediction is very important, and it is mainly in execution delay rather than fetch delay.
In the instruction pipeline, where the fetching is more problem since the instructions do not actually get executed till later.

Which of these is very important (as in which of these really matters in the CPU now-a-days)? If both are equally important or in case the second one is more important then Why do we not have two instruction pipeline (probably of half the length ) and then depending on the branches, just choose one of them and then again start the population from the beginning?

I don't know which case is prevalent, but I would like to offer some thoughts on your proposal of double pipelines.

First of all, you would need double the wire which would consume double the energy and produce double the heat while active. While not needed, on the other hand, it would be completely useless. So one could argue that it is not a good use of resources that are rare on modern processors.

More fundamentally, unless you prefer one branch based on probability, how do you know which version to write through? If none, you might not save anything because other processors might have to wait on your decision, anyways. If you stick with one of them, you have essentially the same rollback probability and cost as you have now.

Let us do a rough calculation. For sake of simplicity, let us assume that handling two pipelines instead of one does not cause additional management overhead. The expected cost (e.g. energy, heat) is $C = c + p(c_r + c)$ with one pipeline ($c$ the cost of executing either alternative, $p$ the probability for rollback and $c_r$ the cost for rollback without the cost for executing the other alternative) but either $2c$ or even $2c + pc_r$ -- either is a lot larger than $C$ if $p$ and $c_r$ are relatively small, and $p$ certainly is (as far as I know, modern branch predictions have accuracies over 90%). And we don't get much for this cost! Expected execution times are $t + p(t_r + t)$ with one pipeline and $t$ resp. $t + pt_r$ with two; as $p$ is small, time savings are negligible.


Bob has to find Alices hidden gold by questioning yes/no questions Suppose that Alice has $n$ places to hide the gold $v_1, ..., v_n$ and that
Bob knows the probability of each place.

Bob has to ask Alice a series of yes/no questions to find the gold.

I have done it this way:

We order the places by probability highest to lowest.
Repeat the following:

Divide them by two so we have two sets High and Low sets
Bob asks whether the gold is in High.
Repeat with the places in the correct set.

My professor told me that we have to get that he questions on average $H(V)$ questions, where $H(V)$ is the entropy.

But with this I have $2.576$, which is close to $H(V)=2.47$ but it's not $H(V)$.

Are there any better ways?

Consider any strategy for Bob. For each item $v_i$, let $x_i$ be binary string composed of the answers that Alice gives to all questions (0 is No, 1 is Yes). You can check that $x_i$ is a prefix code. If $p_i$ is the probability of item $v_i$, then the optimal strategy is the one that minimizes
$$ \sum_i p_i |x_i| $$
over all prefix codes $x_i$ (every prefix code can be translated back to a strategy).

Huffman gave an algorithm which finds the best strategy. The cost $T(V)$ of this strategy satisfies
$$ H(V) \leq T(V) < H(V) + 1. $$
If all $p_i$ are of the form $1/2^j$, then $T(V) = H(V)$, and otherwise $T(V) > H(V)$.

Huffman's strategy is "bottom-up", whereas the strategy that you describe is "top-down". It is not optimal in general, but (if you implement halving properly) it is guaranteed to have cost at most $T(V) + 1$, even with an arbitrary ordering of the weights.

(Since you haven't described your halving strategy, I cannot describe an example in which Huffman coding beats your strategy.)

While prefix codes cannot in general reach the entropy exactly, they do reach the entropy in the limit when solving many instances at once. That is, suppose that Alice is actually hiding $N$ items, each chosen according to $V$. Huffman's algorithm produces a strategy whose cost per item is less than $H(V) + 1/N$. In the limit $N\to\infty$, you do get $H(V)$.


CFG to CNF conversion steps I could find that different texts follow different steps in the conversion of CFG to Chomsky Normal Form. I couldn't find any presumptions they made in the conversion steps. I have some questions regarding the conversion.

Most text books tell us about only two rules $A \rightarrow BC$ and $A \rightarrow a$. But some texts say that starting productions should not be in the right hand side. Why some stress on that rule and others not?
When talking about the rules some don't stress much on the condition of removing useless symbols. Is this condition mandatory or not?
Which is the best rule? Remove useless production, remove $\epsilon$ production, remove unit production, adjust the resulting productions so as to reflect the CNF rules.
Converting a grammar to Greibach normal form requires first converting the productions to Chomsky Normal Form?

1.-The definition that my teacher told me about CNF: It is a context-free language whose productions are from two types:

Type 1: A−>a|A∈N,a∈Σ

Type 2: A−>BC|A,B,C∈N

Nothing less and nothing more.

2.-You can always simplify a CFL but that is not necessary. At least from a theorycal point of view.

3.-    There isn't best rule. Remove useless production is just a way you can polish your CFL.

It is important to notice that when you have ϵ productions you don't meet the requirements for a context-free grammar so you can't make the conversion to CNF. If you eliminate those productions you are generating a CFG very similar to the original grammar but not equivalent . They denote different languajes although the differences can be considered trivial.

Then you mention "remove unit productions" and "adjust resulting productions" this are the steps of the algorithm to convert a CFG in a CNF.

Polish the grammar could be mandatory in a practical context.

4.- I still don't know anything about Greibach normal form so good luck!


Floating point operations; Exception, Flags, and Trap Handlers I am reading over the article found here specifically §D.4.4 Exceptions, Flags and Trap Handlers and am confused by the table D-4 in that section.

Specifically the arguments sent to the trap handler for the overflow and and underflow exceptions.

It shows round(x2-α) as the argument for both the over and underflow conditions (EDIT: It is not). I am not sure what x2 is at all, I see no reference to it in the section.

As for α footnote says:

  *xis the exact result of the operation,  α= 192 for single precision, 1536 for double, and xmax= 1.11 …11 ×2^e_max.

So it says  "α = 192 for single precision, 1536 for double" which is also confusing. Where do these values come from?

I am not looking for anything super in-depth, just something succinct.

Your problem is typographical. Look at a well-formatted copy and it should all make sense. So for example, the argument to the trap handler on overflow is $\hbox{round}(x 2^{-\alpha})$, where $x$ is the exact value.

The value of $\alpha$ comes from the fact that the exponent is 8 bits in binary32 (previously called "single") and 11 bits in binary64 (previously called "double"). You can think of $\alpha$ as an unsigned integer the size of the exponent field, with the two most significant bits set. Why it would be that number in particular is left as an exercise; think the possible range of an overflowing operation and what would be required to rescale it back into a representable range.


What is the difference between consensus and mutual exclusion in Distributed Systems? If we can achieve consensus, does it imply we can achieve mutual exclusion? Is there a difference?

Example : Paxos solves the consensus problem, can it also be used to solve mutual exclusion?

If you have a consensus mechanism, then you can achieve consensus on who owns a critical section, and thus solve mutual exclusion. This is exactly what happens in, say, single-master distributed database systems when they are doing leader election to decide which machine will accept writes (this has to be mutually exclusive).

However, different algorithms for mutual exclusion provide different guarantees of progress in the presence of failures; those that are fully fault-tolerant are essentially equivalent to consensus; those that aren't, are weaker.


Round-robin scheduling: allow listing a process multiple times? In a round-robin scheduler, adding a process multiple times to the process list is a cheap way to give it higher priority.

I wonder how practical an approach this might be. What benefit does it have over other techniques such as giving the process a longer time slice (benefit: less switching time) or maintaining a separate list of high-priority processes. In particular, how does listing a process multiple times influence fairness and reactivity?

(From exercise 2.16 in Andrew Tanenbaum's Operating Systems: Design and Implementation 1st ed.)

The advantage of this approach is that round robin scheduling is very efficient, so you don't need to rely on a more complex scheduler, which would steal cycles. Introducing longer time slices for higher priority processes would decrease the responsiveness of other threads and make it harder for the OS to jump in to deal with an interrupt and so forth. Maintaining separate lists of processes would require a much more complex scheduler, which would be more expensive in terms of cycles. I don't see how there would be any problem with fairness, though. I guess the problem is that the granularity is fairly course: processes can only have integer multiples of the basic time-slice.

One negative point is that removing a process would be more costly, as each occurrence of the process would have to be removed from the queue. Perhaps this can be done lazily, though.


What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute If I were to pose the question: "Given a program $P$ containing statement $X$, will $X$ be executed (given enough runs with all possible inputs)?"

This strikes me of being a relative of the Halting Problem, but I just don't know the taxonomy here.

What is the name of this problem, or does it not have a name because it is solved/uninteresting?

This is called the reachability problem -- is it possible for a given system to enter a given state?

Techniques that attempt to answer this problem fall under reachability analysis, which is one of the main goals of (finite / symbolic) model checking.

As the other answer suggests, this is one of the many instances covered by Rice's theorem. Answering questions about the runtime behavior of programs from only their source code is almost always undecidable. Nonetheless, there are many attempts to solve these problems that can be fairly effective in "real world" code (e.g., Microsoft's 2002 project SLAM), because human programmers tend to try to make their code easy to understand (for other humans; we hope incidentally also for mechanical analysis)


How does a Turing machine compute when its head is at the right-hand end of its configuration? I'm reading Sipser's Introduction to the Theory of Computation (2nd ed.), and I am having trouble understanding one of the cases of Turing machine computation. Sipser describes the cases in terms of how one configuration yields another after a step of computation. For example, if the head is not at either end of the configuration and is moving leftward:

  Suppose that we have $a$, $b$, and $c$ in $\Gamma$, as well as $u$ and $v$ in $\Gamma^*$ and states $q_i$ and $q_j$. In that case $uaq_ibv$ and $uq_jacv$ are two configurations. ... $uaq_ibv$ yields $uq_jacv$ if the transition function $\delta(q_i,b)=(q_j,c,L)$.

where $\Gamma$ is the tape alphabet and $L$ means the head is moving leftward.

I understand this case, as well as the case where the head moves rightward without being at either end and the cases where the head is at the left-hand end. However, I don't understand the cases where the head is at the right-hand end. Here's how Sipser explains the end cases:

  Special cases occur when the head is at one of the ends of the configuration. For the left-hand end, the configuration $q_ibv$ yields $q_jcv$ if the transition is left-moving (because we prevent the machine from going off the left-hand end of the tape), and it yields $cq_jv$ for the right-moving transition. For the right-hand end, the configuration $uaq_i$ is equivalent to $uaq_i⌴$ because we assume that blanks follow the part of the tape represented in the configuration. Thus we can handle this case as before, with the head no longer at the right-hand end.

where ⌴ is the blank symbol.

I'm not sure how to handle this case as I don't know where "as before" refers to. I conceptualize the head like a text cursor stuck in overtype mode, and so my initial guess would be that $uaq_i⌴$ yields something like $uacq_j⌴$ when moving rightward and $uq_iac⌴$ when moving leftward, but I worry that I've missed something. Am I on the right track or am I way off base?


Why does Dijkstra's algorithm fail on a negative weighted graphs? I know this is probably very basic, I just can't wrap my head around it.
We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph.

My professor said this algorithm will not work on a graph with negative edges, so I tried to figure out what could be wrong with shifting all the edges weights by a positive number, so that they all be positive, when the input graph has negative edges in it.

For example, let's consider the following input graph:

Now if I'll add 3 to all edges, it's obvious that the shortest path (between $s$ and $t$) has changed:

Thus this kind of operation might result in wrong output.

And this, basically, what I don't get. Why does this happen? Why is shifting the values has such a dramatic effect on the shortest path? This is totally counter-intuitive, at least for me.

Your thoughts?

Dijkstra relies on one "simple" fact: if all weights are non-negative, adding an edge can never make a path shorter. That's why picking the shortest candidate edge (local optimality) always ends up being correct (global optimality).

If that is not the case, the "frontier" of candidate edges does not send the right signals; a cheap edge might lure you down a path with positive weights while an expensive one hides a path with negative weights.

For details, I recommend you check out a correctness proof and try to do it with negative weights; observe where it breaks.


How to classify a 3D "Knapsack" problem where the only limitation is space, i.e. there is no weight constraint? The problem is defined as: pack a 3D space with a given list of 3 types of cuboids which are each assigned a value, trying to either completely fill the space or to achieve the highest total value of the packing.
When researching knapsack problems all of the different variations I came across
had a weight constraint and most didn't consider geometrical 3D space as a constraint. So my question is: is my problem considered a knapsack problem and/or is there a different term for these kind of problems which I could look into further?

In the standard Knapsack problem (solvable by DP) when we are packing objects we do not care about how we put objects in the knapsack, i.e., what only matters is a subset of objects and the sum of weights of these objects. But, in cuboid/rectangle packing problem the configuration of the cubes/rectangle is important to achieve the optimal packing. So, from this point of view these problems are different. I googled and found this heuristic approach and this article.


How many decision problems do exist? Are there countable infinte decision problems or uncountable infinite?

Thank you

Uncountable. In fact you can see a decision problem P as a language L (the words corresponds with the inputs that are accepted by P) on alphabet Σ. A language can be encoded by an infinite binary string generating all the strings in Σ* in lexical order and associating 1 if the current string belongs to L, 0 otherwise.

The set of infinite binary strings S is uncountable infinite. Let's assume it is countable infinite. Then we can find an association between natural numbers and the strings in S, and list them. But if we take the string composed of the complement of the bits on the diagonal, then we obtain a new infinite binary string which belongs to S but is not in the list. Contraddiction.

So the set of languages (and the set of decision problems) is uncountable infinite.


weight balanced binary tree vs height balanced binary tree What are advantages and disadvantages of weight balanced binary tree over the height balanced binary tree?

The way to answer your question is to find the peer-reviewed papers that first described the trees (or that later chose to reference them) and read their explanations of why the authors felt the need to invent a new tree.

Generally speaking, weight-balanced trees have the property that restructuring operations on a node with $n$ descendants happen every $O(1/n)$ operations. This is good because sometimes these trees are used in an augmented way so that restructuring operations take $\omega(1)$ time. In some height-balanced trees, restructuring operations can happen every operation, while in others they happen every $2^{-O(\lg n)}$ operations, which is slightly weaker than $O(1/n)$.


Arithmetic network to compute floor of binary logarithm I wonder how to build efficient arithmetic network (using logical gates only) to compute floor of binary logarithm of the given input number. I have read some articles on stackoverflow.com about this problem, respectively its implementation in C/C++ using bitwise operations only.

Stackoverflow: Computing the floor of log_2(x) using only bitwise operators in C
Stackoverflow: Computing the floor log of a binary number
Bit Twiddling Hacks
I am pretty sure there's a simpler way to get this done. Using De Bruijn sequences seems to be a magic for me.

It can be done with a fairly simple log-depth circuit without resorting to such hacks that only really make sense in software.

The "position of most significant set bit" function pmsb can be defined recursively:

$\begin{split}pmsb(``0") &= Nil \\
pmsb(``1") &= Nil \\
pmsb(a:b) &= ``0":pmsb(b) \text{ if a=0}\\
&= ``1":pmsb(a) \text{ otherwise}
\end{split}$

Where : divides a power-of-two string down the middle or concatenates two strings, depending on its context.

This can already be implemented as a circuit, but it includes some annoying wide comparisons. They can be removed by returning a tuple with an extra bit that tracks the zero-ness of the whole string (it is applied to the halves so you get the result from the halves in the recursion):

$\begin{split}pmsb(``0") &= (Nil, T) \\
pmsb(``1") &= (Nil, F) \\
pmsb(a:b) &= \text{let } (pa, za) = pmsb(a) \\
&\phantom{=}\quad\quad (pb, zb) = pmsb(b) \\
&\phantom{=}\;\; \text{in if } za \text{ then } (``0":pb, zb)\\
&\phantom{=}\quad\quad\quad\quad\text{else } (``1":pa, F)
\end{split}$

This can then be evaluated bottom-up by a circuit of depth O(log n) and size O(n) where n is the length of the bit-string at the top level, which must be a power of two and not one. The zeroness bit circuit has the structure of an AND-reduction, but it is used at the intermediate nodes instead of only at the end. The main result is computed by a similar tree of MUXes that take those bits as control input.


PRNG for generating numbers with n set bits exactly I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some $0 < n < 64$ and return a pseudo-random 64-bit number with exactly $n$ bits set to $1$, and the rest set to 0.

My current approach involves something like this:

Generate a pseudorandom 64-bit number $k$.
Count the bits in $k$, storing the result in $b$.
If $b = n$, output $k$; otherwise go to 1.

This works, but it seems inelegant. Is there some kind of PRNG algorithm which can generate numbers with $n$ set bits more elegantly than this?

What you need is a random number between 0 and ${ 64 \choose n } - 1$. The problem then is to turn this into the bit pattern.

This is known as enumerative coding, and it's one of the oldest deployed compression algorithms. Probably the simplest algorithm is from Thomas Cover. It's based on the simple observation that if you have a word that is $n$ bits long, where the set bits are $x_k \ldots x_1$ in most-significant bit order, then the position of this word in the lexicographic ordering of all words with this property is:

$$\sum_{1 \le i \le k} { x_i \choose i}$$

So, for example, for a 7-bit word:

$$i(0000111) = { 2 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 0$$
$$i(0001011) = { 3 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 1$$
$$i(0001101) = { 3 \choose 3 } + {2 \choose 2 } + {0 \choose 1} = 2$$

...and so on.

To get the bit pattern from the ordinal, you just decode each bit in turn. Something like this, in a C-like language:

uint64_t decode(uint64_t ones, uint64_t ordinal)
{
    uint64_t bits = 0;
    for (uint64_t bit = 63; ones > 0; --bit)
    {
        uint64_t nCk = choose(bit, ones);
        if (ordinal >= nCk)
        {
            ordinal -= nCk;
            bits |= 1 << bit;
            --ones;
        }
    }
    return bits;
}

Note that since you only need binomial coefficients up to 64, you can precompute them.

Cover, T., Enumerative Source Encoding. IEEE Transactions on Information Theory, Vol IT-19, No 1, Jan 1973.


Quantum Computing Superposition Disclaimer:
By asking this question i'm assuming that "memory" on a quantum computer works similarly compared to a regular computer in the sense that you can store information deterministically and when needed, retrieve it in the same way.
I'm also assuming that n qubit has 2^n "states" that can be set/read independently/concurrently

Question:

Let's suppose that in a 3 qubits quantum machine, at a certain point in time, after a bunch of other operations, I have set my 3 qBit to "111". In another words, those 3 qubits have a state that says "111" and other 7 states of irrelevant information.
At a later moment, given the superposition effect, how does one guarantee that reading those 3 men addrs will yield me my "111"s? In another words, how can I be sure that I'm reading the state that i set previously?

Your assumptions are wrong, and I suggest picking up a textbook on quantum computing.

The state of $n$ qubits can be described by $2^n$ complex numbers $\varphi_x$ whose squared magnitudes sum to 1. You can think of these $2^n$ complex numbers as indexed by $\{0,1\}^n$. When you "read" the $i$th qubit (the technical term is "measure"), what happens is that with probability $p_b := \sum_{x\colon x_i=b} |\varphi_x|^2$ you see the value $b$. Moreover, from now on the value of this qubit will always be $b$ (unless you apply quantum operations to it). The rest of the state is updated accordingly: $\varphi_x := 0$ if $x_i \neq b$ and $\varphi_x := \varphi_x/\sqrt{p_b}$ if $x_i = b$.


For AVL trees, how do we know if a RL or a LR rotation is needed? Suppose I am trying to construct a simple AVL tree:

Upon inserting 'B' the tree becomes imbalanced. How do I exactly know that I need a LR or RL rotation without making any guesses?

From what I heard is that if you insert at right side of tree and it becomes imbalanced then you need a LR rotation and vice-versa. I want to make sure that it is true.

In this case the tree is right-left unbalanced. That's because when you insert $B$ it causes the root node to become unbalanced. You can tell its right-left unbalanced from the path that goes from the newly inserted node to the root node i.e. $B$ is the right child of $A$ and $A$ is the left child of $C$. Therefore, it needs a left-right rotation.


How can solutions of a Diophantine equation be expressed as a language? I was given the question

  Where does the following language fit in the Chomsky hierarchy?

  Nonnegative solutions $(x,y)$ to the Diophantine equation $3x-y=1$.

I understand languages like $L = \{ 0^n1^n \mid n \ge 1\}$, but this language confuses me. What do the words in the language look like? How could I represent it using a grammar or regular expression?

The first thing you'll want to do is look at the phrase itself, and ignore all the references to languages for a moment.

So, what are the non-negative solutions to the diophantine equation $3x-y=1$? If we fix some $x$, then $y = 3x-1$. This means that the set of solutions is $\{ (x, 3x-1)\ |\ x > 0 \}$ (note that $x=0$ yields a negative $y$, and a positive $x$ yields a positive $y$).

Now, we can associate a string with any non-negative number pair $(x, y)$: for instance, $(100, 299)$ can be associated with the string (100, 299). If we apply this to every pair in the set, the resulting set of strings is the language of this set. Note that the question does not really make it clear how to associate a string with a solution, but I'm pretty sure they mean the above.

Now all you have to do is figure out in which level of the Chomsky Hierarchy this language falls. As I have a mild suspicion that this is a homework question, I'll not immediately spill the beans. If you can confirm this is not a homework question and you still need help, I'll edit the answer in.


why not just one header in TCP/IP? I was reading through the computer network fundamentals. I noticed that there are headers added at each layer in the OSI model. However, can we not have just one header above the App layer that defines the header details of every layer ?

I would think answer would be No. But any reasons why ?

Thanks

First thing is that OSI model is a reference and theoretical model which breaks down the functionality in different layers although the real implementation of network might differ.

It is better to have abstractions over abstractions. It is good to have multiple layers with different functions rather than a monolithic implementation. If every layer would have its own concern then it will be easy to find the root cause of failure if it occurs.

Also a network for e.g. Internet is a very complex structure which requires different protocols to actually implement it. If the headers would be constructed all at once then it will not be distinguishable how the protocols are actually applied. A protocol which applies to the physical medium (e.g. Ethernet protocol) cannot be applied before actually producing reasonable and transmittable chunks of the data (which is done at an upper layer).

So it is a good practice to do it progressively and this generally applies to entire Computer Science because it is never recommended to have one monolithic chunk rather than multiple small understandable chunks.


How can a user process even try to access a memory location its not allowed to when it doesn't have access to page table? So is it even possible for a user process to even try to access a physical memory location that does not belong to it and therefore getting an error by operating system?

because for example with a 32 bit cpu the user process has an illusion of having a 32 bit memory all for it self (correct me if I'm wrong) and each page of this virtual memory has a corresponding entry in the page table that says whether this page exists in the real memory or not

but considering user process does not have access to the page table to modify it, how can a process even try to access a memory location in physical memory that doesn't belong to it considering the page table won't let that happen?

does this scenario ever happen? (because i remember reading something about operating systems using exceptions when a process tries to access something that does not belong to it but I'm not sure)

Yes, this typically happens on modern operating systems such as Linux and Windows because they implement demand-paging. That is, whenever a process requests from the OS to allocate a chunk of memory, the OS by default only allocates virtual pages that are not actually mapped to physical pages. The OS satisfies the allocation request by simply modifying its internal data structures to remember that those virtual pages have been allocated and it's OK for the process to access them. This enables the OS to distinguish between virtual pages that have been allocated and those that have not. The OS does not update the corresponding page table entry and leave it invalid.

When an allocated virtual page is accessed for the first time, the CPU sees that the page table entry that describes that virtual page does not map to a physical page and so it will raise an exception known as a page fault. The OS handles the exception by allocating a physical page and updating the page table entry. Then it lets the CPU re-execute the instruction that attempted to access the page and caused the fault. When the instruction is executed again, it will be able to successfully access the page since it's now backed by physical main memory.

The alternative to demand-paging is anticipatory paging where the OS allocates a physical page and updates the page table immediately whenever it allocates a virtual page.


Is ambiguity in Programming Language always bad? Suppose we have a token and our language allows the compiler to build two different derivation trees. However, it can happen that there exists two semantic ways to interpret our token. So ambiguity is not a problem in this case.
Am I correct?

There are computer languages with ambiguous grammars. They decide how to compile ambiguous code by applying rules outside the grammar (there’s no law saying that a language has to be defined by a grammar only). The problem is if your language is ambiguous - if you have code and cannot tell how it should be compiled, that’s quite useless.


Cache memory temporal locality and spatial locality principles How does cache memory take advantage of both temporal locality and spatial locality principles?

It loads data in "blocks". Hence, data close together will be loaded together - space locality
It gets rid only of the most unused data - temporal locality


As @D.W. is suggesting, you can use the binary search technique which takes $O(\log n)$ time, where $n$ is the number of elements in the list.
Furthermore, if you want to know the corresponding period, there are many ways to it.
For example, You can make a separate array of periods and then perform a binary search on it.

Furthermore, you can improve the query time to $O(1)$ by maintaining an array of size 1440 = 24x60 as follows:
The $i^{th}$ entry of the array corresponds to the time $a:b$ where $a = i /60$ and $b = i \mod 60$. And, the value at $i^{th}$ entry is $1$ if time $a:b$ is in the list else it is $0$. Therefore, you can check in $O(1)$ time if an entry exist in the array.
To know the period in $O(1)$ time, you can maintain additional information in the array about the period in which the time lies. For example: an $i^{th}$ entry lies in $2^{nd}$ period. So basically it would be a two-dimensional array.


Subtracting an integer from an ASCII number Theoretically, if I were to subtract the number 10 from the ASCII character 10 (which is really 00110001 00110000), what would I get?

Does the computer add both ASCII characters and subtract?

It depends how exactly you do the subtraction. Depending on the processor, the string 10 is either 0x3031 (little endian) or 0x3130 (big endian). Most modern processors are little endian. That's assuming you regard 10 as a 16-bit integer, i.e. a C short on modern computers. If you're regarding it as a C char, then only the first digit 1 will be affected.


Algorithm for guessing a word in a dictionary with weighted operators Suppose I am given a dictionary of words which contains no more than 100 words, and each word has a maximum length of 50 characters. I want to write a program to guess an unknown word, call it S, that is in the dictionary using 2 weighted operators:

int getOccurrences(char x): return the frequency of the character 'x' in S. This operator costs 1 for each query.
char getChar(int k): return the character at the position 'k' of S. If the length of S is less than k, it will return '#'. This operator costs 10 for each query.

(those functions will give me feedback when I call them)

It is preferred that the average cost to guess S is minimal.

I completely have no idea with this problem. My thought is that given a list of strings, which operator I should use to divide the set by half like in binary search, but I have no luck yet.

Thank you.

PS: Assume that the words in the dictionary are only containing  a-z.

A good heuristic: greedy choice

Here is a greedy algorithm.  It might not be optimal, but I suspect will yield a solution that is good enough.  It is basically an instantiation of your thought, but taking into account a bit of information theory.  The idea will be to greedily choose which operator to query at each iteration; to tell which operator is best, we'll simulate all possibilities for the choice of operator and see which gives us the best gain.

Basically, we're building a decision tree on the fly, via greedy choice at each step.

Keep a set $T$ of all possibilities for the unknown word.  (Initially this is $S$, but you'll narrow down the possibilities as you go.)  In each iteration:

For each possible operator $f$ you could possibly try, compute the "information gain" of using that operator,
$$I(f) = H(X) - H(X | f(X)),$$
where $X$ is a random variable that is uniformly distributed on the current set $T$.  This tells you the expected number of bits of reduction of the entropy -- roughly speaking, the reduction in uncertainty about the word.
For each possible operator $f$, compute the cost of that operator, $\text{cost}(f)$.  Also compute the gain-per-unit-cost, $I(f)/\text{cost}(f)$.
Pick the operator $f$ with the largest value of $I(f)/\text{cost}(f)$, and query that operator.  Use the response to reduce the set of possible words, i.e., remove from $T$ each word that is inconsistent with the response you got.

Repeat until you are left with only one possibility.

Notice that there are only $26+50=76$ different possible operators, so it is easy to enumerate over them all in each iteration.  This algorithm will be pretty fast.

Information gain

How do you compute the information gain of an operator $f$?  Well, you know the set $T$.  Also, given any word $w \in T$, you can compute the result $f(w)$ of applying $f$ to word $w$.

It's easy to compute the entropy $H(X)$: that is just $\lg |T|$.  The entropy of a uniform distribution on some set is the base-2 logarithm of the size of that set.

To compute $H(X|f(X))$, we partition $T$ into subsets $T_1,T_2,\dots,T_k$ according to what the operator returns (all word that return the same value in response to this operator are grouped into the same subset).  Now $H(X|f(X)=y)$ is just $\lg |T_i|$, where $T_i$ is the subset corresponding to words that yield response $y$.  The conditional entropy $H(X|f(X))$ is the average of $H(X|f(X)=y)$ over all possible values of $y$, weighted by the probability of getting $y$.  Thus,

$$H(X|f(X)) = \sum_i {|T_i| \over |T|} \cdot \lg |T_i|.$$

It follows that

$$I(f) = \lg |T| - \sum_i {|T_i| \over |T|} \cdot \lg |T_i|.$$

Optimal sequence

The algorithm above doesn't guarantee to output the optimal solution.  What if we want the optimal sequence of queries?  Well, basically this corresponds to building a decision tree, where each node of the tree applies one operator and then branches upon the result.

We can evaluate the "cost" of a decision tree according to the expected cost spent by the decision tree to narrow down the word to a single possibility, with the expectation taken over the random choice of the unknown word.  Given a decision tree, it is easy to compute its expected cost.  For each of the 100 words, you can simulate what path it will take through the decision tree and the total cost before it hits a leaf; averaging those 100 costs yields the expected cost.

You could now enumerate over all decision trees, and take the one whose expected cost is minimal.  Of course, this will be highly inefficient, as there are exponentially many trees, but it does find the optimal solution.

It should be possible to make this more efficient using branch-and-bound.  Explore the space of decision trees, by building them up in a top-down fashion (from the root downwards).  At any point, you have a partial decision tree (the top of some decision tree, with bottom parts yet to be filled in).

You can get an upper bound for the cost of the best way to complete a partial decision tree to a full decision tree, by applying the greedy heuristic above to complete it to a tree and seeing what the result costs.

Also, you can get a lower bound as follows.  Suppose we have any set $U$ of words.  Find the letterx such that the number $b$ of different possible results of getOccurrences(x) [taken over all words of $U$] is as large as possible.  Then the cost of any decision tree for $U$ will necessarily be at least $\lceil \log_b U \rceil$.  For each bottom node in a partial decision tree, find the set $U$ of words that reach that node, compute a lower bound on the cost of the best decision tree to put as a subtree of that node, and average these up over all the bottom nodes of the partial decision tree (together with the cost of reaching that node).

Now use these lower and upper bounds to prune your exploration, following standard branch-and-bound techniques: if the lower bound for a partial decision tree is at least as large as the expected cost of the best complete decision tree seen so far, then you can prune that partial decision tree (there is no need to explore any of the candidate ways to complete it to a complete decision tree).

Whether this algorithm will be efficient enough to use, I don't know.  You could implement it and give it a try.


Does the host operating system know the content of your messages in a messaging applications? Let's say you are using a messaging application (Microsoft Team, Skype, Telegram,..) on an operating system (Windows, MacOS, Linux). Does the OS know what you are sending or receiving? If yes, how? Assuming that the computer can be setup for monitoring (e.g. company's computer).

If the OS is malicious or compromised, it can monitor everything you're sending or receiving.  As one simple example, it can monitor every key press, every mouse event, and everything displayed on the screen.  Why?  Because the OS runs at ring 0, it has control over everything else.


What does detection stability mean? I am reading the paper "A new approach to intrusion detection using Artificial Neural Networks and fuzzy clustering" by Gang Wang, Jinxing Hao, Jian Ma and Lihua Huang (Expert Systems with Applications, 37(9):6225–6232, 2010, available at Science Direct). I don't understand the term "detection stability". What does that mean?

The context is that existing intrusion detection systems are claimed to have poor "detection stability" when it comes to rare attacks.

Detection stability is about consistency of detection, in this case rare events are classified independent of small changes. One might think of detector having smooth function when it is stable and chaos-like, heavily discontinous when it is not.

Detection stability in the case of rare events (rare attacks) is about consistency and fluctuation. The lack of stability means that similar events, that differ marginaly will not be detected, becase the techniques are very prone to fluctuations - that is a very bad property, malicious query with e.g. $99\%$ classification when changed slightly might drop below detection threshold. Another outcome is that slight changes to the rest of population will influence rare queries.


What is the difference in 'logical array blocked' and array list B, and what do they represent? In Johnson's 1975 Paper 'Finding All the Elementary Circuits of a Directed Graph', his psuedocode refers to two separate data structures, logical array blocked and list array B. What is the difference in them and what do they represent? Moreover, what does 'Vk' mean?

In the pseudocode, T array means an array where each element has type T.  Logical is the type of a boolean (i.e., it can hold the value true or false).  Integer list is the type of a list of integers.

Thus, in the pseudocode, logical array blocked(n) is the declaration of an array called blocked containing n elements, where each element is a boolean.  integer list array B(n) is the declaration of an array called B containing n elements, where each element is a list of integers.

$V_K$ isn't clearly defined, but from context, I'd guess it is the set of vertices in $A_K$.


Approximating all independent sets of size k in a graph Given an undirected graph, I need an algorithm that outputs all the independent sets of size >= k (constant) in the graph. I know the problem is NPC, and I do not want to use the exponential brute-force solution. What I am looking for is to hear about the best solutions currently known to this problem. If someone can refer me to some known polynomial approximation algorithms that achieve good results, that would be very helpful.

In general, the maximum independent set problem cannot be approximated to within a constant factor in polynomial time unless $P = NP$. You can do better, however, if you restrict yourself to special graph classes. For example, in interval graphs, the maximum independent set problem can be solved in polynomial time. As another example, in planar graphs, the maximum independent set problem can be approximated to within any ratio $r < 1$ in polynomial time.

There is a lot more information provided here: https://cstheory.stackexchange.com/questions/2503/maximal-classes-for-which-largest-independent-set-can-be-found-in-polynomial-tim
http://www.graphclasses.org/classes/problem_Independent_set.html

If you're interested in actual implementations, the Wikipedia page has a few references: https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Software_for_searching_maximum_independent_set


Detecting a cycle in an undirected graph and printing the vertices if there is a cycle, printing no cycle otherwise Problem: Find an O(E + V) time algorithm that outputs the vertices of a cycle of G, if it exists. If G has no cycles, the algorithm outputs no cycle. So if there is a cycle 1, ... 3, 1, it would print 1, ..., 3, 1.

So I was thinking of doing a BFS, and if the currently examined vertex's neighbor v has been visited prior, then there is a cycle. However, I am not sure how I might go about tracking the vertices in order to print. I believe I would have to view the BFS-Tree, but unsure.

You've basically got it!

The usual way to record the cycle is to mark the predecessor or parent of each node: that is, the node from which it was first visited. Then you can follow the trail of parents to print out the cycle.


4-color to 3-color polynomial reduction I know a simple reduction from 3-color to 4-color. But how do you reduce 4-color to 3-color ?

I have been searching for the right way to make this reduction for a while now. I would love some pointers.

For a more general reduction, László Lovász [1] proved that

COLORABILITY reduces to 3-COLORABILITY

The COLORABILITY problem is defined as follows:

Input: A graph $G$ and a positive integer $k$.
Problem: Is $G$ $k$-colorable?

That is, the reduction given by László Lovász is applicable to any $k$ ($k \ge 4$).
However, this reduction is quite intricate. You can find an excellent explanation by Vašek Chvátal here. Please free feel to ask if you have some difficulty in understanding this reduction.

[1] Coverings and coloring of hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man., 1973.


Why double error correction and quadruple error detection cannot occur at the same time? What does [ we cannot both correct double errors and detect quadruple errors because this would require us to interpret a received codeword in two different ways] means? I understand how double error correction works but I cannot imagine quadruple error detection. Can anybody show me example why double error correction and quadruple error detection cannot occur at the same time because it requires different interpretation?

For example, if double error correction occur,

will be something like this. How about quadruple error detection?

This is an excerpt from Computer Network Book by Andrew S. Tanenbaum

The data link layer(chapter 3), Page 208, Fifth edition.

With a hamming distance of five, you can make one of two assumptions:

A. No word has more than four errors. Since you need five changes to get from one valid word to another valid word, and five errors don’t happen, every invalid word has 1 to 4 errors.

B. No word has more than two errors. If you find an invalid word, then it has at most two changes from a valid word. To reach any different valid word would take at least 3 more changes, so there is only one valid word within two changes, so you can fix the errors.

But you can’t assume both at the same time. If you find an invalid word, it could have two or four errors, and trying error correction would give you a totally wrong result.

If you have a hamming-distance of 7, you can indeed detect up to four errors and fix up to two errors at the same time. A word with four or three errors cannot be made valid with 1 or 2 changes, so you can detect 3 or 4 errors without being able to fix them, and you can fix 1 or 2 errors.


Does Floyd–Warshall work on all graphs? Floyd–Warshall calculates minimum distance between any two vertices in the graph.

for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
        }
    }
}

So, it basically calculates distance between every two nodes i,j having 1 intermediate node in the shortest path, then having 2 intermediate nodes in the shortest path and so on until there are N intermediate nodes in the shortest path.

So, basically this algorithm uses the previous computed distances to compute the new shortest distances.

But, for a graph like 0->2->3->1. It wouldn't be able to compute the shortest between 0 and 1 because in starting it doesn't know the shortest distances from 0 to 3 or 2 to 1 in the distance matrix.

In dynamic algorithms, we start from shorter problems and then use them to compute solution to larger problems. But, here we don't know which one are our shorter problems.

So, how are we able to use this algorithm here?

The way to answer this kind of question is to simulate the algorithm with pencil and paper to see what it actually does.

Initially, we have dist[i][i] = 0 for all i, dist[0][2] = dist[2][3] = dist[3][1] = 1 and every other entry is infinite.

When we consider k = 0, nothing changes, since dist[i][k] = ∞ for all i except i = 0.

When we consider k = 1, nothing changes, since dist[k][j] = ∞ for all j except j = 1.

When we consider k = 2, we have dist[0][2] + dist[2][3] = 2 < dist[0,3] = ∞, so we set dist[0,3] = 2; nothing else changes.

When we consider k = 3, we have dist[0][3] + dist[3][1] = 3 < dist[0,1] = ∞, so we set dist[0,1] = 3; nothing else changes.

So the algorithm has correctly computed the shortest path from 0 to 1.

The point is that we're not really using dynamic programming based on the length of the intermediate path but on the highest-numbered vertex along that path.  Suppose you want to compute the shortest path from a to b. That path must pass through some highest-numbered vertex – call it c. Because that's the highest-numbered vertex on the path, we know that all the vertices on the paths a-c and c-b have lower numbers. So, in particular, by the time we reach the k = c iteration of the outer loop, we've already calculated all shortest paths between all vertices that use only vertices 0...c-1 as intermediate vertices. And that's enough information to calculate the shortest paths a-c and c-b and, hence, the shortest path a-b.


Express boolean logic operations in zero-one integer linear programming (ILP) I have an integer linear program (ILP) with some variables $x_i$ that are intended to represent boolean values.  The $x_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x_i \le 1$).

I want to express boolean operations on these 0/1-valued variables, using linear constraints.  How can I do this?

More specifically, I want to set $y_1 = x_1 \land x_2$ (boolean AND), $y_2 = x_1 \lor x_2$ (boolean OR), and $y_3 = \neg x_1$ (boolean NOT).  I am using the obvious interpretation of 0/1 as Boolean values: 0 = false, 1 = true.  How do I write ILP constraints to ensure that the $y_i$'s are related to the $x_i$'s as desired?

(This could be viewed as asking for a reduction from CircuitSAT to ILP, or asking for a way to express SAT as an ILP, but here I want to see an explicit way to encode the logical operations shown above.)

Logical AND: Use the linear constraints $y_1 \ge x_1 + x_2 - 1$, $y_1 \le x_1$, $y_1 \le x_2$, $0 \le y_1 \le 1$, where $y_1$ is constrained to be an integer.  This enforces the desired relationship.  (Pretty neat that you can do it with just linear inequalities, huh?)

Logical OR: Use the linear constraints $y_2 \le x_1 + x_2$, $y_2 \ge x_1$, $y_2 \ge x_2$, $0 \le y_2 \le 1$, where $y_2$ is constrained to be an integer.

Logical NOT: Use $y_3 = 1-x_1$.

Logical implication: To express $y_4 = (x_1 \Rightarrow x_2)$ (i.e., $y_4 = \neg x_1 \lor x_2$), we can adapt the construction for logical OR.  In particular, use the linear constraints $y_4 \le 1-x_1 + x_2$, $y_4 \ge 1-x_1$, $y_4 \ge x_2$, $0 \le y_4 \le 1$, where $y_4$ is constrained to be an integer.

Forced logical implication: To express that $x_1 \Rightarrow x_2$ must hold, simply use the linear constraint $x_1 \le x_2$ (assuming that $x_1$ and $x_2$ are already constrained to boolean values).

XOR: To express $y_5 = x_1 \oplus x_2$ (the exclusive-or of $x_1$ and $x_2$), use linear inequalities $y_5 \le x_1 + x_2$, $y_5 \ge x_1-x_2$, $y_5 \ge x_2-x_1$, $y_5 \le 2-x_1-x_2$, $0 \le y_5 \le 1$, where $y_5$ is constrained to be an integer.

And, as a bonus, one more technique that often helps when formulating problems that contain a mixture of zero-one (boolean) variables and integer variables:

Cast to boolean (version 1): Suppose you have an integer variable $x$, and you want to define $y$ so that $y=1$ if $x \ne 0$ and $y=0$ if $x=0$.  If you additionally know that $0 \le x \le U$, then you can use the linear inequalities $0 \le y \le 1$, $y \le x$, $x \le Uy$; however, this only works if you know an upper and lower bound on $x$.

Alternatively, if you know that $|x| \le U$ (that is, $-U \le x \le U$) for some constant $U$, then you can use the method described here.  This is only applicable if you know an upper bound on $|x|$.

Cast to boolean (version 2): Let's consider the same goal, but now we don't know an upper bound on $x$.  However, assume we do know that $x \ge 0$.  Here's how you might be able to express that constraint in a linear system.  First, introduce a new integer variable $t$.  Add inequalities $0 \le y \le 1$, $y \le x$, $t=x-y$.  Then, choose the objective function so that you minimize $t$.  This only works if you didn't already have an objective function.  If you have $n$ non-negative integer variables $x_1,\dots,x_n$ and you want to cast all of them to booleans, so that $y_i=1$ if $x_i\ge 1$ and $y_i=0$ if $x_i=0$, then you can introduce $n$ variables $t_1,\dots,t_n$ with inequalities $0 \le y_i \le 1$, $y_i \le x_i$, $t_i=x_i-y_i$ and define the objective function to minimize $t_1+\dots + t_n$.  Again, this only works nothing else needs to define an objective function (if, apart from the casts to boolean, you were planning to just check the feasibility of the resulting ILP, not try to minimize/maximize some function of the variables).

For some excellent practice problems and worked examples, I recommend Formulating Integer Linear Programs:
A Rogues' Gallery.


Reduction from TSP to ATSP does not imply constant factor approximation algorithm As I understand there is a constant factor approximation algorithm (e.g Christofides algorithm) for the symmetric TSP problem. This is however not the case for the asymmetric TSP problem (I am assuming we are talking about the metric case for both).
According to Wikipedia there is a reduction from ATSP to TSP, which then can be solved to obtain a solution for the ATSP instance - so why does a solution on this reduction not imply that there is a constant factor approximation for ATSP?

I think the reduction they showed is incorrect. Where it falls is when you connect a node to its "ghost" with 0 cost and add a positive $w$ to all other edges. We will take a look why such a behavior can change the optimal path.
Indeed, take a look at a graph with nodes $v_0,\dots,v_{10}$ where we want to find the shortest path between $v_0$ and $v_{10}$.
The graph's edges will connect $v_i$ to $v_{i+1}$ with weight $1$, and will additionally connect $v_0$ to $v_{10}$ with weight $15$.
Clearly, the path between $v_0$ to $v_1$ and so on until $v_{10}$ has the lowest cost, of $10$.
But now assume we added to all edges a weight $w=1$. Then, this path's value will double to $20$, and the edge between $v_1$ and $v_{10}$ will have weight $16$.
Obviously, the shortest path now is the direct path $v_0,v_{10}$ with cost $16$, hence the optimal path changed.
Important note: Its possible to find a small enough $w$ that will not change the optimal path, but I believe finding one is NP-hard.


Assign few binary variables to make all polynomials identically zero I have 50 polynomials $f_i$ over binary variables $(x_1,\ldots,x_{100})$. Also $f_i(0,0,\ldots,0)=0$
for any $i \in [1,50]$. I want to assign few variables so that all  $f_i$ will be
identically zero. I want to assign number of variables as small as possible.
Here assign means we will fix some variable either 0 or 1. Other will be binary variables. All are binary polynomial ring.
If we fix all are zero, all polynomials will be zero identically. I want to reduce number of such assignment.
Is there
any way for this like using SMT etc? Kindly give your idea.

I'll propose two algorithms.
SAT
Every binary multivariate polynomial $f$ can be represented in the form
$$f(x) = \sum_{S \in \mathcal{F}} \prod_{i \in S} x_i,$$
where $\mathcal{F}$ has one set per monomial of $f$, representing the variables included in that monomial.  A multivariate function is identically zero iff all monomials have coefficient 0.  So, we can express your problem as follows.
Let us represent the partial assignment by sets $M$,  where $M$ indicates the set of variables that are are assigned and $v$ their values, and $\overline{M} = \{1,2,\dots,100\}\setminus M$ the complement of $M$.  Then the condition is that after we make the partial assignment and simplify by collecting monomials, all monomials must have coefficient zero.  This can be represented as
$$\Phi(M,v) = \bigwedge_{R \subseteq \overline{M}} \bigg[ \sum_{\substack{S \in F,\\S\cap \overline{M}=R}} \prod_{i \in S \cap M} v_i = 0 \bigg].$$
That's a huge logical formula, but it can be equivalently expressed with fewer clauses as
$$\Phi(M,v) = \bigwedge_{S \in \mathcal{F}} \bigg[ \sum_{\substack{T \in \mathcal{F},\\S\cap \overline{M}=T \cap \overline{M}}} \prod_{i \in S \cap M} v_i = 0 \bigg].$$
If $f$ has $n$ monomials, $\Psi(M,v)$ can thus be expressed as a sum of $n^2$ products of subsets of $v$.  This can be expressed as a SAT formula of size $O(n^2)$, by introducing boolean variables to represent $M,v$ and applying the Tseitin transform.
Now your problem can be expressed as checking whether there exist $M,v$ such that
$$\Phi_1(M,v) \land \dots \land \Phi_{100}(M,v) \land |M| \le k,$$
where $\Phi_i(M,v)$ is the formula corresponding to requiring $f_i$ be identically zero.  This can be checked with a SAT solver, and you can use binary search over $k$ to find the smallest $k$ for which this is satisfiable.
Unfortunately, if each $f_i$ has $n$ monomials, I suspect this will lead to a SAT instance with a small constant times $5000n^2$ CNF clauses, which sounds awfully large for existing SAT solvers to handle.
There are some optimizations that might make this more practical:

If we know that we are looking for an assignment to $k$ variables, the size of the formula for $\Phi(M,v)$ can be further reduced by additionally adding the constraint $|S \triangle T|\le k$ to the $T$'s we sum over, where $\triangle$ denotes the symmetric difference of sets.)

It might be helpful to use CryptoMiniSAT or some other SAT solver with built-in support for XOR (as each sum is a large XOR of boolean variables).

I'm not sure whether this will be enough to make your problem practically solvable in this way, though.
2QBF
We can formulate your problem as an instance of 2QBF as
$$\exists m, v . \text{wt}(m) \le k \land \forall w . f_1(m \;?\; v : w)=0 \land \dots \land f_{50}(m \;?\; v : w)=0,$$
where $m,v,w$ range over $\{0,1\}^{100}$, $k$ is a parameter, $\text{wt}(m)$ represents the Hamming weight of $m$ (the number of 1's in it), $m$ is a mask indicating which variables are assigned, $v$ indicates the values of the assigned variables, $w$ represents an assignment to the other variables, and
$$(m \;?\; v : w)_i = \begin{cases}v_i &\text{if }m_i=1\\
w_i &\text{if }m_i=0,\end{cases}$$
i.e., $m \;?\; v : w = (m \land v) \lor (\neg m \land w)$.  If you can test satisfiability of this kind of 2QBF formula, you can use binary search over $k$ to find the minimum number of variables to assign to.
So, you could try applying standard algorithms for 2QBF to your problem.  See https://cstheory.stackexchange.com/q/11022/5038.  I don't know whether to expect that to be successful -- the problem size might be a bit large for this to work.
2QBF is harder than SAT and unlikely to be solvable with multiple queries to a SAT solver (see Is 2QBF in P^NP?).


Turing machine with k-tape, tape of output Consider a Turing machine with input alphabet $\{a,b\}$ that computes the following function:

$$
f(w, v) =
\begin{cases}
w & \text{if } \operatorname{length}(w) > \operatorname{length}(v), \\
v & \text{otherwise}.
\end{cases}
$$

I wish to use a TM with two tapes, the first of which contains the input string, say encoded as $*w*v*$. I'm not sure, having read several books, which tape is the output tape in this case. For example, the output tape for a TM of two tapes is the input tape or the second tape? If I use three tapes, is it correct that one of them contains the input, another is a working tape, and the third is the output tape?

There is no generally accepted definition of Turing machine. Various authors use various models. One author's definition might specify the output tape, another's might leave the choice to the Turing machine designer.

The reason that we don't care about this "calling convention" is that it doesn't matter from the point of view of computability (and, to a large extent, from the point of view of complexity). All of the different variants of Turing machine are Turing-equivalent; the languages they decide are the computable languages, and the languages they recognize are the recursively enumerable languages.

If you're writing a paper, the choice of which model to use is up to you. But this hardly ever comes up, since Turing machines are usually described very informally. The informal description can be implemented in any reasonable variant of the Turing machine model.


Why is $A_{TM}$ reducible to $HALT_{TM}$? In Sipser, there is a proof I don't understand.

First he established the undecidability of $A_\mathrm{TM}$, the problem of determining
whether a Turing machine accepts a given input.

$$A_\mathrm{TM}=\left\{\left \langle M,w \right \rangle\mid M \text{ is a TM and }M \text{ accepts }w\right\}\,.$$

Then defined $\mathrm{HALT_{TM}} = \left\{\left \langle M,w \right \rangle\mid M \text{ is a TM and }M \text{ halts on input }w\right\}$, he assume that $\mathrm{HALT_{TM}}$ is decidable and use that assumption to show that $A_\mathrm{TM}$ is decidable, contradicting.

He assume that we have a TM $R$ that decides $\mathrm{HALT_{TM}}$. Then he uses $R$ to
construct $S$:

$S$ = "On input $\left \langle M,w \right \rangle$, an encoding of a TM $M$ and a string $w$:

Run TM $R$ on input $\left \langle M,w \right \rangle$.
If $R$ rejects, reject
If $R$ accepts, simulate $M$ on $w$ until it halts.
If $M$ has accepted, accept; if $M$ has rejected, reject."

He says "Clearly, if $R$ decides $\mathrm{HALT_{TM}}$, then $S$ decides $A_\mathrm{TM}$. Because $A_\mathrm{TM}$is undecidable,
$\mathrm{HALT_{TM}}$ also must be undecidable."

I don't understand why is so obvious the problem is $R$. I mean, I don't understand why if $R$ exists, then inevitably we can simulate $M$.  We know that the step number 4 is not possible because $H(\left \langle M,w \right \rangle)$ = "accept if $M$ accepts $w$ OR reject if $M$ rejects $w$" is not possible, so why is $R$ guilty?

Step one, don't try to argue why this TM can not work: under the assumption it does work. But then, since everything else $S$ does is possible (you have to accept that separately), the existence of $R$ certainly is "the problem".

As for understanding, the proof, there are two facts you have to check (under the assumption that $R$ exists):

$S$ is a Turing machine (i.e. its function is computable)
$S$ decides $A_{TM}$.

Arguably, 1) is clear; simulating other TMs given their indices/encodings is something TMs can do (thanks to the existence of a universal TM, which you should have seen a proof of already) and $S$ does little more. This is as close to a proof as you'll get with this form of "definition" of $S$; it's more of an idea, really.

For the second, note that $S$ always halts because $R$ always halts and

$\qquad\begin{align*}
  S\langle M,w \rangle) = 1 &\iff R(M,W) = 1 \land M(w) = 1 \\
             &\iff M(w)\downarrow \land M(w) = 1 \\
             &\iff w \in L_M \\
             &\iff \langle M,w \rangle \in A_{TM} \;.
\end{align*}$

By definition, that means that $S$ decides $A_{TM}$.

Similar arguments usually works for this kind of proof; check our reference questions and other questions tagged computability+reductions.


shortest path from start to end in a grid but with a twist i am trying to solve a graph based problem , this is the statement:
i have to find shortest route from position marked (s) to position marked (S) [Note : i marked S and E just for ease of understanding]. here is the catch in problem i can go only through cells marked 0 and cells marked 1 represents walls which are impassable.also i have the option to remove only one wall if it fetches me a shorter route to exit. Moves can only be made in cardinal directions; no diagonal moves are allowed.

sample 2d grid:

[
    [0(S) 1  1  1  1   ],
    [0    0  1  1  1   ],
    [1    0  1  0  1   ],
    [1    1  0  0  0(E)],
]

if the option of removing walls were not present i could usebfs or dijkstra to find the shortest route. this question has been asked here:
here - they use full exhaustive search which is very bad for large matrices and they focus on language based optimisations which is not a good approach to a problem.

someone asked it here - the accepted answer has the following approach to it:

Run a breadth-first search starting at the prison door, to find the
distance of each passable space from the prison door.
Run another breadth-first search starting at the escape pod, to find
the distanceof each passable space from the escape pod.
Now iterate over the walls, and consider removing each wall in turn.
You know the distance of each passable space from the prison    door
and the escape pod, so you can immediately work out the length    of
the shortest route that passes through the space left by the wall
you just removed.

but i am not clear what does this(so you can immediately work out the length of the shortest route that passes through the space left by the wall ) mean in 3rd step above.

also is there any better way to approach it?

Use any search algorithm, where your state space is the set of tuples $(x,y,d)$ where $(x,y)$ are your co-ordinates and $d$ is a Boolean flag that says whether or not you've already dug through a wall. If $d=\mathrm{true}$, then your available moves are just to move to a vacant adjacent square; if $d=\mathrm{false}$, then your available moves are to move to a vacant adjacent square, or to move into a wall and set $d\leftarrow\mathrm{true}$.


Automated theorem proving with SAT If you had a polynomial time algorithm for determining boolean satisfiability how would you prove/disprove a conjecture like the Reimann-Zeta hypothesis (or the Pythagorean theorem for that matter) from axioms?

If you believe that a proof or disproof has reasonable length, you could come up with one SAT instance which states $x_1,\ldots,x_n$ encodes a proof of the Riemann Hypothesis, and another one stating $x_1,\ldots,x_n$ encodes a refutation of the Riemann hypothesis. The formula will have size polynomial in $n$, though probably not linear; if you're careful, maybe quasilinear ($n\log^{O(1)}n$). You can then apply your magic SAT solver to find out which, if any, of these options is correct. Don't hold your breath, though – as mentioned in the comments, it is hard to imagine an algorithm which would be efficient enough to handle the required value of $n$ in a realistic amount of time.


Maximal cliques in a multipartite graph - efficient? I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class.
Now I am looking for the optimal subset such that each of the N classes is represented exactly once. Not all objects can be combined with each other, e.g. object (N=1,k=1) might not be compatible with (N=2, k=4).
I can formulate this problem as looking for the maximal clique on a N-partite graph (but maybe there are other formulations that I'm not aware of). My question is whether an efficient algorithm exists for solving this problem.
From https://stackoverflow.com/questions/2801138/find-all-complete-sub-graphs-within-a-graph:

This is known as the clique problem; it's hard and is in NP-complete in general, and yes there are many algorithms to do this.
If the graph has additional properties (e.g. it's bipartite), then the problem becomes considerably easier and is solvable in polynomial time

This implies that an efficient algorithm might exist for my problem, but I can't find it...

A maximal clique and a maximum clique are in general different. A set of vertices $S$ is a maximal clique if $S$ is a clique and you cannot add any vertex to $S$ such that the resulting set would form a clique. The set $S$ forms a maximum clique when there is no other set of vertices that forms a clique that is larger than $S$.

You mention bipartite graphs, but the complete $k$-partite graph is not bipartite if $k \geq 3$ (but it is for $k=2$). A bipartite graph contains no triangles, so in such a graph a maximum clique has size (at most) 2, so an efficient algorithm can just return a single edge.

Let $G = K_{n_1,\ldots,n_q}$ for positive integers $n_1,n_2,\ldots,n_q \geq 2$. You can verify that $G$ has maximum clique size $q$, and a total of $n_1 \cdot n_2 \cdots \cdot n_q$ such cliques. An algorithm for enumerating all of them reduces to basic combinatorics (pick one vertex, then how many choices for the remaining vertices do you have when forming a clique?)


Optimality of a Greedy Algorithm If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you prove it is optimality?

For example you have a set of numbers $\mathcal{M}=\{1,2,3,4\}$ and you want to design an algorithm to obtain the minimum number of integers required to obtain a sum 5. In this case, $1,4$ or $2,3$ can produce 5 and both are optimal solutions as the minimum number required is two.

How to prove the optimality of the algorithm ?

I tried by contradiction an assume that there is an optimal solution $P^*$ and my algorithm doesnot produce an optimal solution $P$ so $P \neq P^*$. but I donot know how to continue the argument.

If a greedy algorithm is not always optimal then a counterexample is sufficient proof of this.

In this case, take $\mathcal{M} = \{1,2,4,5,6\}$. Then for a sum of $9$ the greedy algorithm produces $6+2+1$ but this is not optimal because $5+4$ has fewer summands.


How to handle the repeat until convergence condition in time complexity and summarize the time complexity? I am a novice in complexity calculation. I need to calculate the overall time complexity.
My attempt is given below:
Here, N = number of data points (N>300), C = Number of clusters (2<C<30)

For line 3 to 10, time complexity, TC1 = O(NC)

For line 11 to 12, time complexity, TC2 = O(C)

For line 18 to 22, time complexity, TC3 = O(N*N)

For line 24 to 26, time complexity, TC4 = (how to handle the repeat until convergence- the highlighted section?) (Here, I think TC4 = O(N*N))

For line 16 to 29, the overall time complexity, TC5 = C(TC3+ TC4) = O(N*N*C)// not sure about it due to the lacking confidence in the value of TC4.

For line 31 to 35, time complexity, TC6 = O(N*C*C)

For line 38 to 40, time complexity, TC7 = O(NC)

So, finally, the overall time complexity TC = TC1 + TC2 + TC5 + TC6 + TC7 = O(NC) + O(C) + O(N*N*C) + O(N*C*C) + O(NC) = O(?) //How can I summarize this time complexity using Big-O.

My Questions are:
a) How to handle the highlighted portion when calculating the time complexity?
b) How to summarize the overall time complexity?

Please help.

First of all, repeat until convergence isn't quite a well-defined command. Typically, such instructions are implemented by checking the "progress" of some performance measure, stopping once progress drops below a certain threshold.

In order to estimate the running time ("big O") of such an algorithm, all you need to do is to estimate the number of iterations until convergence. The running time of a simple "repeat until convergence" loop is simply the running time of the loop body times the number of iterations. This is a good upper bound if each loop iteration takes roughly the same time. In more complicated cases, in which the iterations have greatly varying running times, you can use a more accurate measure, namely the total running time of the loop body (across all iterations).

This is the theory. How do you apply it in your particular case? In the loop highlighted in yellow, the loop body has unvarying running time, so you need to figure out how many iterations it takes the loop to converge, and then you multiply that by the time it takes to run a single iteration. Estimating the number of iterations until convergence is beyond the scope of this answer.


If L is regular, show that even(L) is also regular I am stuck on the following question.

  If $L$ is regular show that $\mathrm{even}(L)$ is also regular, where $\mathrm{even}(L) = \{ even(w) : w \in L \}$, $w$ is a string in $L$ and $\mathrm{even}(w)$ is the string obtained by extracting from $w$ the letters in even numbered positions.

How can I prove that $\mathrm{even}(L)$ is also regular?

1) Since $L$ is regular we can build a DFA $M = (Q,\Sigma,\delta,q_0,F)$ accepting it.

2) Next we build a DFA $C = (\{c_0,c_1\},\Sigma,\delta_c,c_0,\{c_0\})$ that accepts all strings of even length -- it will help us "count". I'll let you figure out $\delta_c$.

3) Make a product $\epsilon$-DFA $P = (Q_p,\Sigma,\delta_p,(q_0,c_0),F_p)$ from $M$ and $C$, where

$$Q_p = Q \times \{c_0,c_1\}$$

Accepting states are just all state pairs, with an accepting state from the original DFA $M$:
$$
F_p = \{(q_i,c_j) \mid (q_i,c_j) \in Q_p \wedge ~q_i \in F \}
$$
And the transition function looks like this:

all transitions from the "even" state pairs $(q_i,c_0)$ are replaced by $\epsilon$-transitions:
$$
\begin{array}{ll}
\delta_p((q, c_0),~a) = \emptyset,~\forall a \in \Sigma,~\forall q \in Q\\
\delta_p((q, c_0),~\epsilon) = \{(\delta(q,a),~c_1) \mid a \in \Sigma\},~\forall q \in Q
\end{array}
$$
all transitions from the "odd" state pairs $(q_i,c_1)$ mimic the original DFA $M$ (or more precisely, unmodified product automaton):
\begin{array}{ll}
\delta_p((q, c_1),~a) = \{(\delta(q,a),~c_0)\},~\forall a \in \Sigma,~\forall q \in Q \\
\delta_p((q, c_1),~\epsilon) = \emptyset,~\forall q \in Q
\end{array}

Intuitively, the $\epsilon$-NFA $P$ works as follows: it guesses (or skips) all the odd-numbered symbols in the input string.

We have got an $\epsilon$-NFA accepting even(L), thus even(L) is regular.

Example. Let our original automaton be a DFA which accepts the same language L as the regular expression $(001)^*$ (dead states are not shown):

Here is our product $\epsilon$-NFA accepting even(L):


What is the Big Theta of $(\log n)^2-9\log n+7$? How can I find the Big Theta of $(\log n)^2-9\log n+7$?

I thought of $(\log n)^2-9\log(n)+7 < c_1(\log n)^2 +7$ or something like this and can't find the right way.

There is no such thing as "the" big $\Theta$ of a function. For a given function $f(n)$, many functions $g(n)$ satisfy $f(n) = \Theta(g(n))$. For example, every function satisfied $f(n) = \Theta(f(n))$.

However, usually we are interested in a "succinct", "canonical" or "simple" expression $g(n)$, for example of the form $c^n n^a (\log n)^b$, for some $c \geq 1$. In your case $g(n) = (\log n)^2$: your function is $\Theta((\log n)^2)$, which is not too hard to show.

Setting the proof apart, how do I know that your function is $\Theta((\log n)^2)$? Since $(\log n)^2$ is the dominant term: all other terms ($\log n$ and $1$) grow slower than $(\log n)^2$. The constants in front of them don't matter asymptotically.


Polynomial Time Algorithm for Steiner Tree Problem I know about Steiner Tree Problem. It is stated as

  Input to Steiner Tree Problem is a weighted graph G and a subset T of the nodes (called terminal nodes) and goal is to find a minimum weight tree that spans all the nodes in T.

Can we give a polynomial time algorithm to solve the Steiner Tree Problem such that |T| ≥ n−1 where n is the number of nodes in the original graph. I've done a lot of RnD on it but it is still confusing. Can any one help me out?

Yes, given a weighted graph $G$ with $n$ nodes and a subset $T$ of nodes whose cardinality is no less than $n−1$, there is a polynomial time algorithm that finds a minimum weight tree that spans all nodes in $T$.

Here is a simple algorithm.

Find a minimum-weight spanning tree $M$ of $G$. This is can be done by Kruskal's algorithm in $O(E\log E)$ time-complexity.
If $|T|=n$, return $M$.
Otherwise, $|T|=n-1$. There is exactly one node of $G$ that is not in $T$. Let it be node $v$. Removing node $v$ and all edges incident to $v$ from $G$, we obtain a graph $G'$. Note that $T$ is the set of all nodes of $G'$. Find a minimum-weight spanning tree $M'$ of $G'$,  using Kruskal's algorithm again. If the weight of $M$ is smaller than that of $M'$, return $M$; otherwise, return $M'$.

I will let you check that the above algorithm is correct with polynomial time complexity. It should be easy enough.

Exercise. When $|T|=n-1$, what does it mean if $M$ is returned instead of $M'$?

Exercise. Show that if $|T|\ge n-k$ for some constant $k$ instead of $|T|\ge n-1$, the same conclusion holds.


How to find an IP in overlapping ranges of IPs? I have a large number (millions) of IP ranges which might overlap. An IP range should contain the start IP, stop IP and an range id. How can I efficiently find which ranges contain a given IP?

I could iterate over all the ranges and check for every range if it contains the IP, but I'm looking for a complexity better than O(n).

Store your IP address as an integer or long depending on whether it is 32 or 64 bit. Then put the ranges into an interval tree or similar data structure that will allow you to find all ranges that intersect with a given range or point (in this case the IP address you want to check against). This will have a query time of O(lg N) after a preprocessing time of O(N lgN). For K queries this is thus O((N+K)*lg N) which should be fast enough.


Proving GCD algorithm terminates I'm reading this article on a GCD algorithm described by Dijkstra:
https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD316.4.html

I'm looking at program 1.  In particular I'm trying to understand the proof that the loop terminates.  Here is program 1 (my notation is slightly different than the one in the article):

function GCD(a,b)

while a != b
    if a > b
        a = a - b
    else
        b = b - a

return a

I get that max(a,b) at loop n is strictly greater than max(a,b) at loop n+1.  Since a and b are integers greater than 0 it follows that max(a,b) is always greater than 0.  This implies a lower bound.  Therefore the while loop must terminate.

Is my understanding correct?

If you just care about termination of the algorithm not the tight analysis then you can say that it will terminates within $a+b$ steps as inside the while loop you are decreasing either $a$ or $b$ depending on some condition, so your while loop have to terminate within $a+b$ iterations.