Prove by induction that the running time of recursive Fibonacci is exponential This example followed from a Fibonacci algorithm in class. The professor showed us how to compute $T(n) = T(n-1) + T(n-2) + 3$, but left this step for us to prove, so I decided to attempt to prove it! But I am finding it difficult to fully understand how to prove things involving lower and upper-bounds. After looking up many resources including some things from Stanford, this is what I have been able to come up with:

Let $T(n) =$ time for $fib1(n)$, where $T(n) = T(n-1) + T(n-2) + 3$

Claim: For $n \ge 6$, the running time of $fib1(n)$ is exponential, i.e $T(n) \ge (1.41)^n$

Base Case: $$T(6) = 8 \ge (1.41)^6 = 7.86$$
               $$T(7) = 13 \ge (1.41)^7 = 11.08$$

Inductive Hypothesis: Assume that for an arbitrary n, $T(n) \ge (1.41)^n$

Prove $T(n+1) \ge (1.41)^{n+1}$:
$$T(n+2) = T(n+1) + T(n) + 3$$
$$\ge 1.41^n + 1.41^{n+1} \text{  [By the I.H]}$$
$$ = (1.41^n)(1+ 1.41) > 1.41(1.41)^n$$

Thus, the running time of $fib1(n)$ is $\Omega{(1.41^n)}$

Edit:

I'm not entirely sure how correct this is, but I'm not as worried about that. My main concern is in the induction step, I feel like there is something I am missing conceptually. Specifically, how exactly can we be sure that $$T(n+2) = T(n+1) + T(n) + 3 \ge 1.41^n + 1.41^{n+1} $$ if we only know that $$T(n) \ge 1.41^n$$

I hope this clarifies my question. Thanks!

Observe that with

$\qquad  T(n) = T(n−1)+T(n−2)+3$

and

$\qquad T'(n) = 2 T'(n-2)$,

you have $T > T'$ assuming similar anchors, in particular because both functions are non-decreasing. $T'$ solves to $T'(n) \approx 2^{n/2} \geq 1.41^n$.

I intentionally provide only a sloppy sketch; I'll leave the formal proof to the interested reader.


How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism? I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem.

Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the Hamiltonian Cycle - Subgraph Isomorphic connection, @Luke Mathieson says that "Hamiltonian Cycle to Subgraph Isomorphism is really just rephrasing what it means for a graph to have a Hamiltonian cycle" - but I don't get it.

How does one transforms from Hamiltonian Cycle to Subgraph Isomorphism?

I read Reducing from Hamiltonian Cycle to Subgraph Isomorphism and https://en.wikipedia.org/wiki/Subgraph_isomorphism_problem and couldn't understand how should a proper reduction look like, how to build one that proves the subgraph problem?

Your help in simplifying the problem(s) will be very appreciated.

Reduction $HC \leq SubgraphIsomorphism$ is done as $G \rightarrow \langle G, C_n \rangle$ where $n$ is the number of vertices in $G$, and $C_n$ is the cycle graph with $n$ vertices. This effectively means that $G$ has a subgraph $C_n$ if and only if $G$ has a Hamiltonian Circuit.

There are mainly three types of common reductions. $A \leq_L B$, $A \leq_P B$ and $A \leq_M B$ i.e. log-space reduction, polynomial-time reduction and turing reduction. If we don't specify, it usually means polynomial-time reduction which is also known as Karp reduction.

Let us take $A \leq_P B$. It means we can transform an input $x$ of problem $A$ to an input $f(x)$ of problem $B$ in polynomial-time such that (and this is important) $x$ is a yes-instance of $A$ if and only if $f(x)$ is a yes-instance of $B$. This effectively gives us a polynomial-time algorithm to check yes-instances of problem $A$ if there is a known polynomial-time algorithm to check yes-instances of problem $B$.

Now if $A$ is known to be a tough problem, like Hamiltonian Circuit problem, then $A \leq B$ will imply that $B$ is also a tough problem. That is, since $HC$ is NP-complete, SubgraphIsomorphism is also NP-complete (as we also know additionally that Subgraph Isomorphism is in NP, otherwise we would have only shown its NP-hardness).


How to get the expected time complexity of while loop? How to get the expected time complexity of while loop below?
While infinity:
  case1: Return 0 with a probability of p(1 - p)
  case2: Return 1 with a probability of p(1 - p)
  case3: otherwise repeat this loop until return 0 or 1

I can understand the probability that this loop runs only one time is $2p(1 - p)$. But I cannot understand how much the expected run time of this is. Can anyone let me know it and why?

You should calculate the probability that the while loop runs exactly $k$ times, for $k\in\mathbb{N}$.
Then the expected number of loops is $\sum\limits_{k=0}^{\infty}k\times\mathbb{P}(\text{loop runs }k\text{ times})$.


How can we design an efficient divide-and-conquer algorithm for constructing a round-robin tournament? Background and main question

I am studying algorithm analysis and design, and have been going through "Algorithm Design and Applications" by Goodrich and Tamassia.

One of the applications problems (A-11.2) poses the following:

  Given a set, P, of n teams in some sport, a round-robin tournament is a collection of games in which each team plays each other team exactly once. Such round-robin tournaments are often used as the first round for establishing the order of teams (and their seedings) for later single- or double-elimination tournaments. Design an efficient algorithm for constructing a round-robin tournament for a set, P, of n teams assuming n is a power of 2.

The chapter is on the divide-and-conquer method, so I am assuming that they intend for us to use a recursive algorithm to solve the problem.

Approach

I assumed that every team would play in every round (i.e. there is no need for "bye weeks").

I tried to tackle this problem via two different approaches:

1) Place each team in a some sort of collection (or, assign each team an integer, and place those into a collection). Pop the head element from the collection, and make pairs with the elements remaining in the collection. Use these pairs to populate an n - 1 rounds * n - 2 matches grid, where n, as in the problem, is the number of teams. Repeat until one element is left in the collection.

This is not a "true" divide-and-conquer approach, and is O((n-1)!), I believe.

2) Use n - 1, n * n binary matrices to plot the matches for each round.

This approach is not divide-and-conquer at all. I know intuitively that it will work, but I'm not sure how I would implement it programmatically.

Conclusion

How can we solve this problem via the divide-and-conquer approach?

What kind of asymptotic behavior can we expect?

Hint. Divide the teams into two sections. Every game that needs to be played is either between two teams in the same section, or between teams in different sections. What is the set of games that must be played between teams in the same section?


How to show two models of computation are equivalent? I'm seeking explanation on how one could prove that two models of computation are equivalent. I have been reading books on the subject except that equivalence proofs are omitted. I have a basic idea about what it means for two models of computation to be equivalent (the automata view: if they accept the same languages). Are there other ways of thinking about equivalence? If you could help me understand how to prove that the Turing-machine model is equivalent to lambda calculus, that would be sufficient.

You show that either model can simulate the other, that is given a machine in model A, show that there is a machine in model B that computes the same function. Note that this simulation does not have to be computable (but usually is).

Consider, for example, pushdown automata with two stacks (2-PDA). In another question, the simulations in both directions are outlined. If you did this formally, you would take a general Turing machine (a tuple) and explicitly construct what the corresponding 2-PDA would be, and vice versa.

Formally, such a simulation may look like this. Let

$\qquad \displaystyle M = (Q,\Sigma_I,\Sigma_O,\delta,q_0,Q_F)$

be a Turing machine (with one tape). Then,

$\qquad \displaystyle A_M = (Q \cup \{q^*_1,q^*_2\},\Sigma_I,\Sigma_O', \delta', q^*_1, Q_F)$

with $\Sigma_O' = \Sigma_O \overset{.}{\cup} \{\$\}$ and $\delta'$ given by

$\quad \displaystyle (q^*_1,a,h_l,h_r) \to_{\delta'} (q^*_1,ah_l,h_r)$ for all $a \in \Sigma_I$ and $h_r,h_l \in \Sigma_O$,
$\quad \displaystyle (q^*_1,\varepsilon,h_l,h_r) \to_{\delta'} (q^*_2,h_l,h_r)$ for all $h_r,h_l \in \Sigma_O$,
$\quad \displaystyle (q^*_2,\varepsilon,h_l,h_r) \to_{\delta'} (q^*_2,\varepsilon,h_lh_r)$ for all $h_r,h_l \in \Sigma_O$ with $h_l \neq \$$,
$\quad \displaystyle (q^*_2,\varepsilon,\$,h_r) \to_{\delta'} (q_0,\$,h_r)$ for all $h_r \in \Sigma_O$,
$\quad \displaystyle (q,\varepsilon,h_l,h_r) \to_{\delta'} (q',\varepsilon,h_la) \iff (q,h_r) \to_\delta (q',a,L)$ for all $q \in Q$ and $h_l \in \Sigma_O$,
$\quad \displaystyle (q,\varepsilon,\$,h_r) \to_{\delta'} (q',\$,\square a) \iff (q,h_r) \to_\delta (q',a,L)$ for all $q \in Q$,
$\quad \displaystyle (q,\varepsilon,h_l,h_r) \to_{\delta'} (q',ah_l,\varepsilon) \iff (q,h_r) \to_\delta (q',a,R)$ for all $q \in Q, h_l \in \Sigma_O'$,
$\quad \displaystyle (q,\varepsilon,h_l,\$) \to_{\delta'} (q,h_l,\square\$)$ for all $q \in Q$ and $h_l \in \Sigma_O'$, and
$\quad \displaystyle (q,\varepsilon,h_l,h_r) \to_{\delta'} (q',h_l,a) \iff (q,h_r) \to_\delta (q',a,N)$ for all $q \in Q,h_l\in\Sigma_O'$

is an equivalent 2-PDA. Here, we assume that the Turing machine uses $\square \in \Sigma_O$ as blank symbol, both stacks start with a marker $\$\notin \Sigma_O$ (which is never removed) and $(q,a,h_l,h_r) \to_{\delta'} (q',l_1\dots l_i,r_1\dots r_j)$ means that $A_M$ consumes input $a$, switches states from $q$ to $q'$ and updates the stacks like so:

[source]

It remains to show that $A_M$ enters a final state on $x \in \Sigma_I^*$ if and only if $M$ does so. This is quite clear by construction; formally, you have to translate accepting runs on $M$ into accepting runs on $A_M$ and vice versa.


Does polynomial time reduction from CNFFAL to CNFSAT is also polynomial time reduction from CNFSAT to CNFFAL? CNFSAT is the language of all strings that are encoding of satisfiable boolean formula in conjunctive normal form while CNFFAL is the language of all strings that are encoding of falsifiable boolean formula in conjunctive normal form.

Any boolean formula is satisfiable if and only if exists an truth assignment of True and False to the boolean variables so that the boolean formula evaluates to true.

Any boolean formula is falsifiable if and only if exists an truth assignment of True and False to the boolean variables so that the boolean formula evaluates to false.

CNFFAL is in $\Bbb{P}$, because the deterministic Turing machine that decides CNFFAL in polynomial time only needs to find falsifiable clause and deciding whether or not disjunction of literals is falsifiable is as hard as deciding 1SAT that is deciding the satisfiability of conjunction of unit clauses, where each unit clause is single literal, and it is also in $\Bbb{P}$.

Because of the fact that $\Bbb{P\subseteq NP}$ CNFFAL is also in $\Bbb{NP}$ and also non deterministic Turing machine to decide CNFFAL is to guess and choose an truth assignment non deterministically and accept if the input boolean formula evaluates to false, reject otherwise.

According to the fact that $CNFFAL\in\Bbb{NP}$ and to the paper of Cook, Levin and Karp that was submitted in 1971, it is also true that $CNFFAL\le_PCNFSAT$.

I want to know if $CNFFAL\le_PCNFSAT\implies CNFSAT\le_PCNFFAL$.

In other words I want to know if it is also true that $CNFSAT\le_PCNFFAL$, because I read the 1971 paper of Cook, Levin and Karp and as I understood, the deterministic polynomial time reduction from an arbitrary NP language to satisfiability problem is done by first describing the non deterministic Turing machine that decides the arbitrary NP language in polynomial time and then there is polynomial time deterministic algorithm to generate the boolean formula that is true on every accept path/route of the non deterministic Turing machine for the input string and it is false on every reject path/route of the non deterministic Turing machine for the input string.

Therefore the string is in the arbitrary NP language if and only if the non deterministic Turing machine that decides the arbitrary NP language in polynomial time accepts the string and the non deterministic Turing machine accepts the string if and only if there exists an accept path/route, i.e. the non deterministic Turing machine has an accept path/route for the input string and there exists an accept path/route or the non deterministic Turing machine has an accept path/route for the input string if and only if the boolean formula is satisfiable.

Let $NTM_{CNFFAL}$ be the non deterministic Turing machine that decides CNFFAL in polynomial time as described above.

Therefore if the input boolean formula $\alpha$ is falsifiable then there exists an accept path/route, i.e. $NTM_{CNFFAL}$ for $\alpha$ as input has accept path/route, but if $\alpha$ is also satisfiable then there also exists reject path/route, i.e. $NTM_{CNFFAL}$ also has reject path/route for $\alpha$, but if $\alpha$ is unsatisfiable then all paths/routes of $NTM_{CNFFAL}$ are accept and therefore the boolean formula $\beta$ generated from $NTM_{CNFFAL}$ is tautology and not falsifiable.

Therefore $\alpha$ is unsatisfiable if and only if $\beta$ is tautology.

Therefore $\alpha$ is satisfiable if and only if $\beta$ is falsifiable.

So my question is does $CNFSAT\equiv_PCNFFAL$?

No, $CNFFAL\le_P CNFSAT$ doesn't appear to imply $CNFSAT\le_P CNFFAL$, as far as we know.

As you say, we know that $CNFFAL\le_P CNFSAT$ is true.  However, $CNFSAT\le_P CNFFAL$ is true if and only if $P = NP$.

Consequently, the claim $CNFFAL\le_PCNFSAT\implies CNFSAT\le_PCNFFAL$ is logically equivalent to the claim that $P=NP$.  There is no known proof that $P=NP$ (and many would consider it surprising if that is true).

I didn't understand why you think the implication does hold.  I couldn't quite follow your reasoning.  The notation $\beta$ is never explained clearly (I don't know what you mean by "the boolean formulated generated by a NTM"; NTMs don't generate boolean formulas, so that would need to be defined more clearly). It's hard to know what you might be thinking, but if I were forced to speculated, I'd guess that the flaw in your reasoning might have something to do with the situation where $\alpha$ is both satisfiable and falsifiable.  Then it's true that $NTM_{CNFFAL}$ has both an accept path and a reject route, but so what?  It's not clear why that would imply anything interesting.


What is the relation between syntax and type theory? Type theory and syntax are similar, in that they are inductive rules that determine whether a  particular string of symbols is "correctly specified" in some sense.

There is a difference between syntax and type theory. Syntax in programming languages for example, concerns things that do not concern type theory, such as the fact that the statement if import microsoft.(false ==== 5) then import is "syntactically nonsense". This is not a type error, but a syntax error.

But I'm unsure what the relation is.

I normally think of syntax and type systems as follows: Let $L$ be the set of possible strings of some symbol set $S$. A particular syntax inductively specifies a subset $T\subseteq L$ of "terms" in $L$. e.g. a program is not well-specified if it is not in $T$. A particular type system then makes an additional restriction, by inductively specifying a subset $W\subseteq T$ of "well-typed terms".

But given such a syntax and type system, we can always consider a new syntax which is simply the old syntax plus also has the inductive rules of the type system as an additional restriction.

Therefore it is not clear to me why there is a fundamental difference between a syntax and a type system.

Is my intuition correct? Can we see type checking a particular form of syntax checking?

The division line between syntax and additional type checking can indeed be blurred, if so desired, but usually we make a distinction as follows:

the syntax is described using a formal grammar, preferrably one that is not very complex, such as a context-free gramar, or one that is even simpler than that.
the typing rules are described using inference rules whose complexity tyically exceeds that of a context-free formal grammar.

In general, a programming language might stratify the task of getting from the source code to the compiled code as follows:

Parsing converts the input string to an abstract syntax which represents the input as a tree.
Elaboration performs certain simple transformation of input syntax, such as getting rid of syntactic sugar.
Type-checking and inference verifies that the program is well-typed, thereby guaranteeing that later stages will not get stuck. It may also augment the input source with extra information about types.
Several phases of compilation may follow, each translating from its input to a simpler language. The final language may be machine code, or byte code, or in general some intermediate code.
The program is executed.

While you may consider merging some of these phases together, and sometimes that is a good idea, it is in general better to keep them separate. From a conceptual point of view parsing is very different from type checking. After all, these two phases serve different purposes: one is just a translation from strings to trees, while the other one statically analyzes the structure of the program in order to detect possible errors and to aid further compilation.

An example of merging different phases is "just in time" compilation: we run a program in an "interpreted" mode so that there is no delay because of compilation, and at the same time we perform on-the-fly compilation of those parts of the code in which the program is spending most of the time. I believe some browsers do that with Javascript.


How do I "apply" a loop invariant? A homework problem I have asks that I "state" a loop invariant, then "prove" it, then "apply" it. I get state and prove, but my textbook doesn't explicitly state how to "apply" a loop invariant.

You “state” a loop invariant - that’s an educated guess.

You “prove” a loop invariant - you show it’s true before the loop is first entered, and you show that if it’s true before an iteration, then it is true after the iteration.

You apply the loop invariant - you take the fact that the loop invariant is proven, and the fact that the loop stopped iterating, to prove facts that hold after the loop is finished.


Contradiction in regularity of a language Lets say we have $L_1$ which contains all binary numbers divisivle by 2 but not by 4. I would say this language contains all words with a 10 at the end. Ive found a regular grammar $G$ with $L(G) = L_1$ so that $L_1$ must be regular.

Now I have the problem that my teacher told me that $L_2 = \{ww| w \in \{0,1\}*$  and $w$ ends with 10$\}$ is not context free.

But if $L_1$ is regular or context-free, so should $L_1L_1=L_2$ be also regular and context free.

Where is the mistake?

There is a difference between $L_2 = \{ww\mid w \in L_1\}$ and $L_3 = L_1 L_1$. $L_3$ is $\{wx\mid w, x \in L_1\}$; in, other words all strings consisting of two sentences from $L_1$, which is regular / context-free if $L_1$ is regular / context-free.

$L_2$ is the set of all strings consisting of one repeated string from $L_1$, which is not in general context-free. (It is regular if $L_1$ is finite or is a regular language over a singleton alphabet. But your example does not fall into either of these categories.)


Relationship between Higher Kinded Polymorphism, type inference, and Currying On Hacker News there is an interesting exchange about the async\await RFC for Rust.

The author of the proposal withoutboats is responding to a comment about the usage of async-await construct vs a monadic implementation in Rust. He notes three problems, the first one I am having some trouble parsing:

  Higher kinded polymorphism results in trivially undecidable type inferences without something like currying; the restrictions needed to support it would be arbitrary and weird given that Rust does not have currying (essentially some rules to reconstruct the restrictions of currying in type operator context).

I have a decent understanding of higher-kinded polymorphism, type inference, and currying (or so I naively assert), and I even see why currying is useful for higher-kinded polymorphism, i.e. type constructors of the form * -> * -> *, a type which takes a type and produces a third.

But what I don't understand is why currying is necessary to avoid "trivially undecideable type inferences." Can someone provide an example of a such an undecideable inference, and why currying helps?

I imagine what the comment writer is referring to is this...

Consider type inference in Haskell. At some point, we may be asked to solve the unification problem f a = Maybe Int. This is very easy to solve (f = Maybe, a = Int), but only because we have restricted the allowable solutions. The solution to f may only be built out of (partial) applications of type 'constructors' (like Maybe) and variables. Another example is f a = (b, a) with solution f = (,) b. I suspect this partial application is what is meant by "currying". Note that f Int = (Int, Double) just fails.

Now consider (until somewhat recently) Scala. For one, there was no inherent notion of left-to-right partial application like the above. To even write a partially applied type required giving it a name via some rather baroque syntax. But more importantly, it made no commitment to the restrictions that made things easy in the last paragraph. This has the 'advantage' that you can make f Int = (Int, Double) work. A solution is f = λa. (a, Double). However, note that we had to solve for f with a lambda term. This means inference must solve a problem called, "higher-order unification," which is bad, because it's undecidable.

Another (related, I think) problem is that my last solution above wasn't actually unique. Another solution is f = λ_. (Int, Double). Neither of these solutions is more general than the other, they're simply different. So, I suspect it's also the case that higher-order unification doesn't have most-general solutions. This means (I think) that even if it were a solvable problem, the 'right' solution would not be a local property, and would depend on the rest of the program (because some of the multiple possible solutions might not be compatible with other parts of the program where the solution is used).

So, to avoid these problems, it is much easier to restrict the solution space the way Haskell does. It isn't terribly inconvenient to organize things according to this discipline such that you get good inference most of the time. And when unification fails, it's obvious what the problem was, whereas it can get complicated to figure out how to guide the system using higher-order unification with the right annotations.

However, I've heard that newer versions of Scala actually have adopted this type inference methodology. But I still don't think their type functions look "curried" exactly like Haskell's do (i.e. they still look like F[A,B]). So it's probably not essential to do that. The left-to-right partial application rule is the essential part.


Why use binary search trees when hash tables exist? Hash tables perform lookup, insertion, and deletion in O(1) time (expected and amortized) while the different variants of binary search tree (BST) - treap, splay, AVL, red-black - offer at best O(log n).

So, in a course on data structures, is the study of BST's of any value except as a historical note?

The most obvious answer is that trees can be traversed in their natural order very efficiently.  If you need to visit every element of a dictionary in alphabetical order, a tree can support this directly, where a hash table cannot.

Another answer is that trees can be made immutable - where insertion and deletion only involve recreating a small number of elements back to the root, whereas hash tables can only be completely duplicated.

A related answer for mutable data is that trees can be modified concurrently, only requiring locking single nodes, whereas hash tables have to be locked as a whole if concurrent processes are to get consistent results.


Is a language of some deciders decidable? Is

$$L = \{ \langle M \rangle \mid M = (\{Q_1, Q_2, . . . , Q_{100}\}, \{0, 1\}, \{0, 1, \_\}, δ, Q_1, Q_2, Q_3) \text{ is a decider}\}$$

decidable?

I know

$$HALT_{TM}= \{ \langle M \rangle \mid M \text{ is a decider}\}$$

is not decidable, but in the case we are given a specific Turing Machine that has 100 states, alphabet $\{0,1\}$, tape alphabet $\{0, 1, \_\}$ (where _ is space), a transition function $\delta$, a start state $Q_1$, an accept state $Q_2$ and a reject state $Q_3$.

Checking that M is in the correct format is easy but is it possible to build a Turing Machine that decides $L$? I assume I can use the fact that $HALT_{TM}$ is undecidable to show that $L$ also is, but I am not sure how to proceed.

And I don't see how I could reduce $L$ to $A_{TM}$ to prove by contradiction that it is not decidable?

How should I proceed?

I don't fully understand the details of your question (especially the notation that you've used).

However, the language you're asking about appears to be finite (something like the language of descriptions of all Turing machines that halt for all inputs and have at most 100 states), and every finite language is decidable.  You could, in principle, produce a list of all the strings in your language, and then just design a Turing machine that accepts exactly that list of strings.

Note also that reducing $L$ to the halting problem wouldn't prove that $L$ is undecidable, since every recursively enumerable language reduces to the halting problem. You'd just be showing "If I could solve the halting problem, I could solve $L$, too." That's a bit like saying, "If I was the world's strongest man, I could lift an apple." Maybe you don't need to be so strong to do such a simple thing? If you want to prove that $L$ is undecidable by reductions, you need to reduce an undecidable language to $L$: then, you're saying, "If I could decide $L$, I'd be able to decide this undecidable language, and I know I can't do that."


Why does the denotational semantics for a while loop have a existence quantifier? I was going through these notes and they have the following operator on partial functions:

$$
\mathcal F^{k}(\bot)(\sigma) =
\left\{
 \begin{array}{ll}
  \alpha(  [\![s]\!]\sigma )  & [\![b]\!]\sigma=true \\
     \sigma & [\![b]\!]\sigma=false \\
        \bot & [\![b]\!]\sigma=\bot
 \end{array}
\right.
$$

and supposedly it gives the following definition somehow (which ends up being the right denotation for while loops)

$$
\mathcal F^{k}(\bot)(\sigma) =
\left\{
 \begin{array}{ll}
    [\![s]\!]^i  & \mbox{if $ \exists i \in [0,k)$  s.t. $ [\![b]\!] [\![s]\!]^i \sigma = false,\ [\![b]\!] [\![s]\!]^j \sigma = true,\ j \in [0,i) $}\\
     \bot & \mbox{ o.w. }
 \end{array}
\right.
$$

the proof by induction is shouldn't be hard. However, it feels that it doesn't really answer the question for me intuitively because I could do the induction mechanically without understanding what is going on. Why isn't the definition something like:

$$ f(\sigma,i) = [\![s]\!]^i\sigma$$

then the induction is easy:

$$ f(\sigma,0) = [\![s]\!]^0\sigma =  \sigma$$

then the inductive step:

$$ f(\sigma,k+1) = f \circ f{\circ}^k(\sigma)= f \circ[\![s]\!]^{k}\sigma$$

but also notice $f = [\![s]\!]^1\sigma$ by strong induction:

$$ f(\sigma,k+1) = [\![s]\!]^{k+1}\sigma$$

as required. But that doesn't seem at all to be the sort of argument being used (assuming what I wrote is right). Did I miss something?

The existential quantifier is misplaced. This is due to lack of reasonable notation for what needs to be expressed, namely: "if there is $i$ safisfying condition $C$, then use that $i$", where we make sure that at most one such $i$ exists. It would be better to write (and by the way, you might appreciate LaTeX's cases environment):
$$
\mathcal F^{k}(\bot)(\sigma) =
\begin{cases}
    [\![s]\!]^i  & \text{if $i < k$ and $[\![b]\!] [\![s]\!]^i \sigma = \text{false}$ and, for all $j < i$, $[\![b]\!] [\![s]\!]^j \sigma = true$}\\
     \bot & \text{otherwise}
\end{cases}
$$
It may be helpful to look at a simpler definition. Suppose we want a function $f : \mathbb{N} \to \mathbb{N}$ which maps an odd number to zero and an even number to half of itself. The following is a reasonable definition:
\begin{align*}
f(2 n) &= n\\
f(2 n + 1) &= 0
\end{align*}
as is the following (where $m$ and $n$ range over natural numbers):
$$
f(m) =
\begin{cases}
n & \text{if $m = 2 n$,}\\
0 & \text{otherwise.}
\end{cases}$$
The point is that precisely one branch applies, and in a unique way, as there can be at most one $n$ satisfying the condition $m = 2 n$. However, the following is not a reasonable definition:
$$
f(m) =
\begin{cases}
n & \text{if $\exists n \in \mathbb{N} \,.\, m = 2 n$,}\\
0 & \text{otherwise.}
\end{cases}$$
The problem is that the $n$ outside the $\exists$ quantifier is completely unspecified. This is so because the $n$ inside the $\exists$ quantifier is bound and can therefore be renamed at will:
$$
f(m) =
\begin{cases}
n & \text{if $\exists k \in \mathbb{N} \,.\, m = 2 k$,}\\
0 & \text{otherwise.}
\end{cases}$$
(And we do not rename the outer $n$ because it is not in the scope of $\exists$.) This makes it clear that the existential quantifier has no place there. It is important to understand variable bindings. In the above definition of $f$, the variable $n$ is bound in the entire case, not just in the condition.

From a very formal point of view, the map $f$ is defined here as a relation explaining how an argument of $f$ is related to its value.
A definition of the form
$$f(m) =
\begin{cases}
e_1(m,n) & \text{if $\phi_1(m,n)$} \\
e_2(m,n) & \text{if $\phi_2(m,n)$}
\end{cases}
$$
is equivalent to
$$f(m) = \text{the $v$ such that $\psi(m,v)$}
$$
where
$$\psi(m,v) \iff
(\exists n \,.\, \phi_1(m,n) \land v = e_1(m,n)) \lor
(\exists n \,.\, \phi_2(m,n) \land v = e_2(m,n))$$
Now the quantifiers are justified. By the way, we could have used $\forall$ instead:
$$\psi(m,v) \iff
(\forall n \,.\, \phi_1(m,n) \Rightarrow v = e_1(m,n)) \land
(\forall n \,.\, \phi_2(m,n) \Rightarrow v = e_2(m,n)).$$


Deadlock not possible? System is in safe state if there exists a safe sequence of all processes.
Sequence $[P_1, P_2 …P_n]$ is safe, if for each $P_i$ the resources that  can still request can be satisfied by $P_i$ currently available resources + resources held by $P_j$ with $j \lt i$

The above is from a presentation distributed by my OS II teacher. Assuming it is true, then doesn't this mean that the system is always in a safe state?
I conjecture that $\forall$ set of processes $X = [P_1 ... P_n]$ requesting for a set of resources $[R_1 ... R_n]$ $\exists$ a safe sequence $S = \{P_i ... P_k\}, S: S$ is a permutation of $X$.
Reasoning behind my conjecture. Suppose I had $n$ processes and $1$ resource(each process requesting it.) I could order these processes in order of priority, or ascending order of size and run them. If resources were increased to $k$, there will still be a sequence such that every process completes in finite time. The challenge merely finding it.
Am I wrong?

Lets say for the sake of argument we have 6 units of memory available and three processes in a current state where each holds 2 resources. Each process needs 3 resources to finish and release its memory units to use by the others. This state is not safe, in fact this state is deadlock. Each needs one extra memory unit to finish, but this would require another process to release its units. No ordering of these 3 processes will be safe.

You are not looking at the state of the program, but the entirety of the program, in which case, with no new resource creation and single threading, every state is safe.

Edit for clarity: From the definition of a state: "In computer science and automata theory, the state of a digital logic circuit or computer program is a technical term for all the stored information, at a given instant in time, to which the circuit or program has access".

The import point is "given instant". The state could be at the initial state as your argument would require, or it is at some arbitrary point in execution


Why isn't Busy Beaver Infinite for n < trivial k? I am clearly not understanding the Busy Beaver function. Why wouldn't it be infinite for n > k,
while(true)
{
  print("1");
}

Busy Beaver function considers only terminating TMs, that is only those that execute for some finite number of steps.


Sphere, triangle, and other primitive shape intersection In a three dimensional Cartesian space, given a ray in its parametric form:
$r(t) = [1, 1, 1] + t[-1, -1, -1]$ find the intersection points between the ray and the following primitives.

a) A sphere centered at the origin with a radius of $1$, and

b) a triangle with vertices $\{[1,0,0]^T , [0,1,0]^T , [0,0,1]^T \}$.

Represent the intersections in their Cartesian coordinates as well as the ray parameters. Write down the intermediate steps of your derivations clearly.

The next part asks me to choose another primitive 3D shape, decide on implicit or parametric surface functions, then make an equation for ray-surface intersection and derive the analytic solution.

I am a little confused on this assignment because I haven't had a physics class before and I don't understand the basics of 3D shapes' geometry or vectors. It's not entirely clear to me what I am supposed to find as an answer or in what form the answers should be written. I looked up the formulas for sphere and triangle intersection, but I can't find a similar example, so I don't know how to solve the problems.

A sphere centered at the origin with a radius $1$ consists of all points whose distance from the origin is at most $1$. The distance between two points $(x_1,y_1,z_1),(x_2,y_2,z_2)$ is $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$. This gives you enough information to describe the sphere: $\{ (x,y,z) : x^2+y^2+z^2 \leq 1 \}$.

A triangle with vertices $p_1,p_2,p_3$ is (by definition) the convex hull of $p_1,p_2,p_3$, which is the set of all points $a_1 p_1 + a_2 p_2 + a_3 p_3$ for $a_1,a_2,a_3 \geq 0$ satisfying $a_1 + a_2 + a_3 \leq 1$. In our case, the triangle is defined by $\{ (x,y,z) : x+y+z = 1, \; x,y,z \geq 0 \}$.

The intersection of a shape $S$ and the ray $r$ is just the set of points which belong to both $S$ and $r$. You can find these points by solving a system of equations: every point $(x,y,z)$ on the ray is of the form $x = 1-t,y = 1-t, z=1-t$ for some $t$. You can simplify this by making the substitution $s = 1-t$ to get $(s,s,s)$ instead of $(1-t,1-t,1-t)$. Now you can find the set of points in the intersection by solving a system of inequalities (I'll leave that to you). Having found the solution, the ray parameter is just the corresponding value of $t$, namely $t = 1-s$.

That should be enough to get you started.


Keywords/terminology for using "extra" information in search problems? I am trying to find references on a particular idea, but I don't know which keywords to use in a google search.

the idea is: as an example, consider graph search. maybe the problem is: find a path from node $X$ to node $Y$. We can consider two versions of this problem:

For any node $n$, we can query only the information: which other nodes are connected to it?
For any node $n$, we can additionally query the information: what is the "airplane distance" between $n$ and $Y$.

Clearly, if we have the additional information from (2), we can construct a larger set of possible search algorithms, in particular, ones that are faster.

My question is: What terminology/keywords do I need to search to read about this phenomenon that some search algorithms have more "heuristic" information at their disposal than others, and can therefore employ better search heuristics?

Such search algorithms would generally be called informed search algorithms (or methods, techniques, etc.), or simply heuristic search algorithms. We might also call them guided search algorithms.

An example would be A* search, which uses precisely what you call "airplane distance" (more commonly referred to as the straight-line distance) as a heuristic.

Best-first search techniques would be somewhat closely-related, but they may have a slightly different meaning (they may, for example, use statistics / information gathered earlier during the same process for guidance during a later part of the search process, rather than heuristic domain knowledge given a priori).


Can we show that non-determinism adds no power, for some specific running time? $NP = \cup_{k \in \mathbb{N}} NTIME(n^k)$

$P = \cup_{k \in \mathbb{N}} TIME(n^k)$

Can we show that $NTIME(n^k) = TIME(n^k)$ for a specific $k$?

For how large of a $k$ can we show the above statement to be true?

If $\mathsf{NTIME}(n^k) \subseteq \mathsf{TIME}(n^\ell)$ for any $k,\ell$ then $\mathsf{P} = \mathsf{NP}$. Indeed, any problem $L \in \mathsf{NP}$ can be solved in non-deterministic time $O(n^r)$ for some $r$. Consider now the problem $L' = \{0^{|x|^{r/k}}1x : x \in L\}$. Clearly this problem is still in $\mathsf{NP}$, and furthermore the previous algorithm solves it in non-deterministic time $O(n^k)$. Therefore $L'$ has a deterministic algorithm running in time $O(n^\ell)$, implying that $L$ has a deterministic algorithm running in time $O(n^{r(\ell/k)})$.

This trick is known as padding.


Linear-time algorithm to find an odd-length cycle in a directed graph Problem: Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. (Exercise 3.21 of Algorithms by  S. Dasgupta, C. Papadimitriou, and U. Vazirani.)

The related post@cs.stackexchange asks for the existence of an odd-length directed cycle in a digraph, which is solved by the following theorem@algs4.cs.princeton.edu.

  Theorem: A directed graph has an odd-length directed cycle if and only if one (or more) of its strong components is non-bipartite (when treated as an undirected graph).

Thus, we can assume that the digraph is strongly connected.

Let $G$ be strongly connected. Run BFS (!) from an arbitrary vertex $s$. BFS creates a leveled tree where level of a vertex $v$ is it's directed distance from $s$. If while running BFS you have never seen an edge $(u,v)$ that goes between levels of the same parity then $G$ is bipartite. The parity of the level of $u$ defines the partition that $u$ belongs to. Note that since every vertex is reachable from $s$, BFS will explore all the edges, so all of the edges would be going between the two blocks of the partition. Otherwise, you find an edge $(u,v)$ that goes between levels of the same parity. Suppose level of $u$ is even and level of $v$ is even. Then run DFS (or BFS) from $v$ to get a path to $s$. If this path is of even length then you get an odd directed cycle $s \rightsquigarrow u \rightarrow v \rightsquigarrow s$. If this path is of odd length then you get an odd directed cycle $s \rightsquigarrow v \rightsquigarrow s$. Analogous thing holds when level of $u$ is odd and level of $v$ is odd. Since this algorithm simply does 2 runs of BFS/DFS, it runs in linear time.


How to count stores in cache analysis of matrix multiplication I'm trying to understand cache misses/iter and came across this that I couldn't understand or reason out.

For ijk iteration, my slides say that there are 2 loads and 0 stores.

for (i=0; i<n; i++) {
  for (j=0; j<n; j++) {
   sum = 0.0;
   for (k=0; k<n; k++)
     sum += a[i][k] * b[k][j];
   c[i][j] = sum;
  }
}

Similarly, for kij iteration, my slides say that there are 2 loads and 1 store.

for (k=0; k<n; k++) {
 for (i=0; i<n; i++) {
  r = a[i][k];
  for (j=0; j<n; j++)
   c[i][j] += r * b[k][j];
 }
}

And for jki iteration, my slides say that there are 2 loads and 1 store.

for (j=0; j<n; j++) {
 for (k=0; k<n; k++) {
   r = b[k][j];
   for (i=0; i<n; i++)
    c[i][j] += a[i][k] * r;
 }
}

I believe the loads are counted in each case when data is referred to by calling arr[x][x] on the right hand side of the arithmetic evaluation, which would make two in each case. But how are the stores counted?

It appears that the analysis assumes that integer variables are stored in registers, whereas array elements have to be loaded from and stored to memory. The point you've missed is that the statemnt X += Y requires reading X and then writing the new value of X.

sum += a[i][k] * b[k][j];

This loads a[i][k], loads b[k][j], multiplies them, reads sum, adds sum and the product and writes the result to sum. Two loads, no stores.

c[i][j] += r * b[k][j];

This loads b[k][j], reads r, multiplies them, loads c[i][j], adds the product to it and stores the new value of c[i][j]. Two loads, one store.

c[i][j] += a[i][k] * r;

This is essentially the same as the previous case.


Determine in which class $L=\big\{\langle M_1,M_2,w\rangle\mid M_1,M_2\text{ are TM and }L(M_1)\cap L(M_2)=\{w\}\big\}$ my solution is that $L\in co-RE$ by showing that $\overline{L}\in RE$

TM $M$ on input:$\langle M_1,M_2,w\rangle$

Build TM $M_1,M_2$
Simulate $M_1$ on $x\in\Sigma^*$, before that check if $x\neq w$
If $M_1$ accepts some $x$, than Simulate $M_2$ on $x$
If $M_2$ accepts than $M$ accepts. If $M_2$ reject, that we back at $M_1$ on the next $x$

$* $ $M_1$ and $M_2$ will run on each $x$ at the most $|x|$ steps.

Is that correct?

Thanks.

No. It is not correct.

For example, suppose that $x=0$, $w=00$, $L(M_1)\bigcap L(M_2)=\{x,w\}$.  If $M_1(x)$ or $M_2(x)$ takes more than $|x|=1$ steps to answer "yes", then your proposed algorithm will failed.


Is the union of infinitely many regular languages always regular? Prove or disprove or this statement:

The union of an infinite number of regular languages is regular.

Can someone help?

Every language is a union of infinitely many regular languages:
$$
L = \bigcup_{w \in L} \{w\}.
$$


How to use homomophism in closure proofs? I am having a hard time understanding homomorphism. All I seem to understand is that it is a substitution. When I look at examples of proving closure of a particular operation over a regular language, I don't understand how people come up with the substitution strings that they choose, and how they use them to produce a regular expression. Getting from the starting language to the final regular expression bewilders me.

For example, the following closure proof of an operation 'Quotient' written $L/R$, where $L$ and $R$ are regular languages:

$L/R = \{ x \mid \exists ~y \in R, \text{ where } xy \in L \}$
Define $\Sigma' = \{a' \mid a \in \Sigma\}$
Let $h(a) = a$
Let $h(a') = \lambda$
Let $g(a) = a'$
Let $f(a) = \{a, a'\}$
Then $L/R = h(f(L) ~\cap~ (\Sigma^* \cdot g(R)))$

What is the $a'$? Just another symbol? Why is that useful?
I don't understand the $f(a)$.
I don't understand what concatenating with $\Sigma^*$ yields.
I really don't understand much of it...

Can someone explain this to me in English, so I can better understand how to approach closure proofs of other operations?

Prerequisite: you have to understand the basic techniques beforehand (or imagine/search/develop them on the fly).

A string homomorphism or simply a homomorphism maps each character to a single string (possibly in a different alphabet). For example, let $f(a)=ab$ and $f(b)=ba$. Then $f(ab)=abba$ and $(\{a, ab^2\})=\{ab, abbaba\}$.

A string substitution or simply a substitution is a mapping that maps each character to a language (possibly in a different alphabet). For example, let $f(a)=\{x\}$ and $f(b)=\{y, xz\}$. Then $f(ab)=\{xy,xxz\}$ and $f(\{a^2, b^2\})=\{x^2, y^2, yxz, xzy, xzxz\}$. The effect of substitution is not only changing the characters, but also including more variations. A substitution can be considered as the "union" of many homomorphisms.

Instead of explaining the formula $L/R = h(f(L) \cap (\Sigma^*\cdot g(R)))$, let
us discover that formula by trial and error, starting from examining the target, $L/R$.

$L/R$ is made up by words each of which is the prefix of a word in $L$ whose remaining part is in $R$.

So, as a first step, given a word $w\in L$, we want to chop off a part of it. How to chop off a part? Mapping the letters to the empty string! Letting $h(a)=\lambda$, the empty word for all $a\in\Sigma$, we get $h(L)$.

Oh no! We just mapped every word in $L$ to the empty string! That is useless. What we want is to map a suffix that is in $R$ to empty string. For a word that looks like $xy\in L$, we want to chop off $y\in R$. How to carve out the suffixes? That means we should use intersection to target the remaining part. All words that end with a $y\in R$ are $\Sigma^*\cdot R$.

Now $L\cap \Sigma^*\cdot R$ are all the words in $L$ that end with a word in $R$.

Let us apply $h$ to it. Still, all of them are mapped to the empty string. We have to modify $h$ so that it will only map the letters in $R$ to empty string. Well, that is absurd since the letters in $R$ are the same as the letters used by $L$!

Wait. Let us suppose $R$ does use a different set of alphabet. For example, if $abc\in R$, we can imagine that actually means $a'b'c'\in R$. In other words, let us replace $R$ by $g(R)$, where $g(a)=a'$ for all $a\in\Sigma$.

Darn! Now $L\cap (\Sigma^*\cdot g(R))$ is empty. We need to change $L$ the the same way as $g$. Well then, it will not make any improvement. Is there a way to change $L$ to include the result of changing by $g$ as well as keeping itself intact?

String substitution comes to the rescue. We can let each letter in $L$ be itself or itself prime. This last ingenious touch almost concludes our journey. We have
$h(f(L)\cap (\Sigma^*\cdot g(R))$.

What we got are all those suffixes in $g(R)$. However, we should become cautiously confident the solution is within reach since we get something non-trivial and strongly related.

In fact, all we need is letting $h$ preserve $a$ while erasing $a'$ instead. That is, $h(a)=a$ for all $a\in\Sigma$ and $h(a')=\lambda$. There remains some verification to do, but we have gone through the hard part of the journey.

Hopefully, you could gain some understanding if you have followed the above journey.

Here are two related exercises.

Exercise 1. Show that the left quotient $L\backslash R = \{ y \mid \exists x \in L \text{ such that } xy \in R \}$ is regular where $L$ and $R$ are regular. (In fact, the condition $L$ is regular is not necessary.)

Exercise 2. Let $L = \{ w \mid \text{odd}(w) \in L_1 \text{ and } \text{even}(w) \in L_2 \}$, where odd$(w)$ is the string of all letters of $w$ in odd positions and even$(w)$ is the string of all letters of $w$ in even positions. Show that $L$ is regular iff $L_1$ and $L_2$ are regular.


How to partition a set in order to minimize the number of the elements and their interactions? Given two sets $S_1$ and $S_2$ of $n$ elements each. Each set $S_1$ (resp. $S_2$) has a revenue $R_1$ (resp. $R_2$). Each element $i$ of $S_1$ (resp. $S_2$) has a gain $g_{i1}$ (resp. $g_{i2}$). From set $S_1$ (resp. $S_2$), choose a subset of elements $O_1$ (and $O_2$) such that:

$\sum_{i\in O_1}g_{i1}\geqslant R_1$;
$\sum_{i\in O_2}g_{i2}\geqslant R_2$;
$|O_1|+|O_2|+|O_1\cap O_2|$ is minimized.

Can we solve this problem in polynomial-time?

I started by a greedy approach which chooses the elements by increasing order of their gains. I tried few examples but this does not provide optimal results.

I am now trying to prove that it is NP-hard using a reduction from PARTITION. Any hints?

Consider the following two variants of subset sum problem:
Variant 1

Given a set of $2n$ positive integer elements and a positive integer target $W$, is there a subset with size $n$, whose sum is $W$?

Variant 2

Given a set of $n$ positive integer elements and a positive integer target $W$, where $(\text{the maximum element})< 2\times(\text{the minimum element})$, is there a subset whose sum is $W$?

Variant 1 is NP-hard by a reduction from one-in-three 3-SAT (almost the same reduction from 3SAT to the normal subset sum problem, except that we do not need the $s$ and $t$ values, and the target is always $111\ldots1$).
Variant 2 is also NP-hard by a reduction from Variant 1. Given an instance of Variant 1, we add a large enough integer $M$ to each element so that the new elements satisfy the constraint in Variant 2. Now the answer to Variant 1 is "yes" if and only if there is a subset of the new elements whose sum is $W+nM$ (since $M$ is large enough, the subset must have size $n$).
Now we show a reduction from Variant 2 to (the decision version of) your problem, so your problem is NP-hard.
Given an instance of Variant 2, we construct $S_1=S_2$ as the same set as the given instance. Let $s$ denote the sum of all elements. We set $R_1=W$ and $R_2=s-W$. The gain of each element is the same as itself.
Now if there is a subset $O\subseteq S_1=S_2$ whose sum is $W$, then we can choose $O_1=O$ and $O_2=S_2\backslash O$, meaning there is a solution to your problem with $|O_1|+|O_2|+|O_1\cap O_2|\le n$.
On the other hand, if there is a solution to your problem with $|O_1|+|O_2|+|O_1\cap O_2|\le n$, then $2|O_1\cap O_2|\le n-|O_1\cup O_2|$. Let $\min$ and $\max$ be the minimum and maximum elements respectively. We have
$$\sum_{e\in O_1\cap O_2}e\le |O_1\cap O_2|\max\le 2|O_1\cap O_2|\min\le(n-|O_1\cup O_2|)\min\le\sum_{e\notin O_1\cup O_2}e.$$
This means
$$
\sum_{e\notin O_1}e=\sum_{e\in O_2}e-\sum_{e\in O_1\cap O_2}e+\sum_{e\notin O_1\cup O_2}e\ge \sum_{e\in O_2}e\ge s-W.
$$
Note $\sum_{e\in O_1}e\ge W$ and $\sum_{e\notin O_1}e+\sum_{e\in O_1}e=s$, we have $\sum_{e\in O_1}e=W$ and $\sum_{e\notin O_1}e =s-W$, which means there is a subset $O\subseteq S_1=S_2$ whose sum is $W$.


why should I go for logistic regression? I am a student working on a Database management project with a bit of Python coding involved. The project is about Review Analysis.Basically I am trying to read a review and determine how good or bad it is.

I have a file of good and bad words with its scores like :: good = 2, better =3,best=4;

By this , I have written a code for sentiment analysis of the review which gives me the score of the review considering every single word.

Since the range varied from - infinity to + infinity, I had to scale it down to a range of 0 to 1.
A graphical representation must be done on this data; i.e. the score of review ,may it be from -infinity to +infinity or 0 to 1.

I was advised to go for logistic regression plot by my guide.
Why logistic regression? Is there a better way?

If you want to know why your advisor advised you with that advise, you should ask your advisor why he advised you thus, as Yuval points out.

If you want to know what makes logistical regression a good method, it is because it takes as input a data set such as the one you have and it outputs a probability (distribution), which is precisely the input-output format you were looking forit; it is simple, widely available, easy to implement, and in practice, it turns out that they do a markedly good job at predicting real-world data. It is also the last step before curve-fitting turns into AI, because neural networks are really just logistic regression on steroids.

There are other methods because world of data analysis is big. You are looking for a classification model. For example, you can use a Bayesian learning algorithm, such as Naive Bayes or Pearl's algorithm. Weka is a freely available software toolkit with 100 (+/- 50) different classification algorithms. It is quite user-friendly. If your data set is large and complex enough, you can consider letting loose a true AI, such as a neural network, or a Deep Learning machine. All these things are freely available.


Deterministic pushdown automaton for a given language I am trying to make a deterministic pushdown automaton from this language but without success.
Here is the language definition:

$\ L=\{0^n 1^m a^i b^j \ /\  m,n,i,j > 0 \ and \ m+n=i+j \} $

Thanks!

Let us start with an automaton for ${2^rc^r}$ for the alphabet $\{2, c\}$. This is quite a standard example. As long as you are reading $2$ add a letter to the stack until you read the first $c$. Then for each $c$ pop a letter from the stack. The word and the stack should finish at the same time.

Now using this automaton we should be able to build one for you language, where the string of $c$s should turn to any concatenation of a staring of $a$s and a string of $b$s and the string of $2$s turns into a concatenation of a string of ones and a string of twos. This means for each zero you read push a letter to the stack until you read the first one. Then for each one push a letter to the stack until you read the first $a$ then for each $a$ pop a letter until you find the first $b$ and then pop for each $b$. The stack should turn empty upon reading the last letter in the world. Note that the DPA should rejects the string if at any point it reads an unexpected letter (a $0$ after an $a$ for example).

Note that one of the substrings might be empty, so you should consider the case of starting with $a$s directly after zeroes for example.


Formulating a constraint to exclude a single point from the feasible region of an IP? Consider a basic integer program such as:

$$\begin{align}
\min_x & \quad c^Tx \\
\text{s.t.} & \quad Ax \leq b \\
&\quad x_i \in \{-100,\ldots,100\}
\end{align}
$$

where $x \in \mathbb{Z}^n, A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R^m}$.

Say that I have a point $y \in \mathbb{Z}^n \cap [-100,100]^n$ that I would like to exclude from the feasible region.

I am wondering if there is an elegant way to do this without introducing new variables to the formulation? If there is no way to exclude $y$ from the feasible region without adding new variables to the formulation, then is an approach that allows me to do this by adding the fewest possible variables?

I should add that this question is loosely related to a different question that I posted here a few months ago (though there was no concrete answer given to that one either).

You need to add an integer cut of the form:
$$
 \sum_i |x_i - y_i| \ge 1
$$
where $y_i$ is your point your want to exclude.

We can rewrite this as:
$$
  \begin{align}
     &\sum_i z_i \ge 1 \\
      &z_i \le |x_i - y_i|
  \end{align}
$$
The last inequality is identical to $z_i \le \max\{x_i-y_i, -(x_i-y_i)\}$. This again can be implemented using additional binary variables:
$$
 \begin{align}
    &z_i\le x_i-y_i+M_i\delta_i \\
    &z_i\le -(x_i-y_i)+M_i(1-\delta_i) \\
    &\delta_i \in \{0,1\} \\
    &M_i = U_i - L_i = 200
 \end{align}
$$
There are two special cases we can handle more efficiently. If $y_i=L_i=-100$ then we can write $z_i = x_i - y_i$. If $y_i=U_i=100$ then we can write $z_i=-(x_i-y_i)$.


Time complexity of sum of $2^n$ values of polynomials First a simpler question: let $q_{1}(k),\dots,q_{n}(k)$ be $n$ polynomials of degree smaller or equal to $n$.

Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = \sum_{i=1}^{n}q_{i}(n)$.

Assume also $0\leq f_{i}(n)\leq n$.

What is the time complexity as a function of the input size for calculating $f(n)$ by the above definition?

I'm not quite sure how to approach this, but my current guess is as follows:

I know evaluating a polynomial is $O(n)$ time, where $n$ is the degree of the polynomial.

I know adding two integers is $O(n)$ where $n$ is the number of bits of the larger integer.

Every try to calculate this seems to get stuck, as i'm getting confused between the time complexity by input size and by actual size (the number itself).

after understanding this, i would like to understand the calculation for time complexity as a function of the input size for a similar problem:

Let $q_{1}(k),\dots,q_{2^n}(k)$ be $2^n$ polynomials of degree smaller or equal to $2^n$.

Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = \sum_{i=1}^{2^n}q_{i}(n)$.

Assume also $0\leq f_{i}(n)\leq 2^n$.

Thanks for any help, i hope this is well enough defined.

It takes $O(n^2)$ time.  A polynomial can be represented as the list of its coefficients.  Since it has degree $n$, it can be represented by a list of $n+1$ numbers.  Now adding polynomials can be done by adding their corresponding coefficients.  There are $n+1$ coefficients of $f(n)$, and each takes $O(n)$ time to compute (you have to add up $n$ numbers), for a total of $O(n \times (n+1)) = O(n^2)$.

There's no possibility to do anything faster, as the input contains $n(n+1)$ numbers, and any correct solution will have to read all the input.  It takes $\Theta(n^2)$ time even to read the input, let alone to do any processing, so any correct algorithm will have to take time at least $\Theta(n^2)$.

With this, you should now be able to do a similar analysis for the variant you list near the end of your question.


How To Best Learn About Algorithms In Depth I have been reading this site with a great deal of interest, but I find a lot of it goes over my head. This has made me wish to learn a lot more about algorithms and CS in general. As far as I can tell from my research, there are 2 main ways of doing this.

I can by a nice thick heavy book and work my way through it slowly but surely.
I can "learn by doing" and by a nice book, but instead of reading it cover to cover, move to parts that interest me and work on implementing and applying algorithms I like.
?

My question is, which of the above did the you use and would you recommend the same approach to someone else?

I learned about algorithms in a university course years ago. But if you are to do algorithms using a book, then you need a good one. Two books stand out for me as the way to get into algorithms:

The Algorithm Design Manual by Steven S. Skiena
Introduction to Algorithms by T Cormen, C Leiserson, R Rivest and C Stein

The first is perhaps more of a hands-on manual, whereas the latter is more like the bible, but with proof.

The strategy you could follow would consist of reading, doing the theoretical exercises, and then implementing as much as you can, focusing on algorithms/problems you find interesting or challenging or both.  Thus, try to cover all aspects of algorithms, not just implementing them. This will include studying their time and space complexity and proving their correctness. The study of algorithms is more than just implementing algorithms.

After you've gained enough experience, start specializing. If you become interested in Computational Geometry or non-blocking algorithms, for example, then start exploring books and research papers in this area.

Specialization is good, but it is also good to sample techniques from other areas, so reading broadly about algorithms (and implementing such algorithms) is a good way of maintaining a broad skill set.

EDIT:
After going through the introductory algorithms, you may consult books like Randomized Algorithms by Motwani & Raghavan or Approximation Algorithms by Vazirani. These books are a survey (and to some extent, a good learning exercise in mathematical techniques) in more advanced algorithm design techniques. They also broaden your insight into many other fields in CS like Graphs and Networks, Data Structure design and Optimization.


Recurrence $T(n) = 2T(\sqrt{n}) + \log n$ So I have a question for the recurrence $T(n) = 2T(\sqrt{n}) + \log n$. We are to use substitution method to figure out the solution. This is an example problem (not a exercise problem) in my book (Introduction to Algorithms, Third Edition pg. 86). I'm having a hard time understanding how they rename $m = \log n$.

They then get the new equation $T(2^m) = 2T(2^{m/2}) + m$. I see that turning the $m = \log n$ into $2^m = 2^{\log n}$ and using the property $a^{\log b} = b^{\log a}$ so you get $2^m = n^{\log 2}$ which goes to $2^m = n$ and hence $\sqrt{n} = 2^{m/2}$.

My question is, how do you know to guess to substitute $m$ for $\log n$?

Since you know how to solve recurrence equations of the form $S(n) = \alpha S(n/\beta) + f(n)$, you want to transform the given recurrence into this form. You notice that $\log \sqrt{n} = \frac{1}{2}\log n$, so $m = \log n$ is a good substitution.

More generally, there are no rules on how to solve recurrence relations (or anything in mathematics). Having seen the Master theorem, you know what to do when you have a recurrence of the form $S(n) = \alpha S(n/\beta) + f(n)$. Having seen this example, you know (a) what to do when you have a recurrence $T(n) = \alpha T(n^\beta) + f(n)$, and (b) it is a good idea to try to reduce a general recurrence to one of the form $S(n) = \alpha S(n/\beta) + f(n)$ by using an appropriate substitution.

As you get deeper into the subject (if you choose to do so), you will learn more tricks that will help you solve problems. Yet sometimes a new trick will be necessary. When all else fails, you just try a lot of things with your recurrence. Hopefully, after a while a winning direction will emerge. This is called (mathematical) research.


What's the name of this tree-like data structure? I'm currently experimenting with some tree-like data structures and came up with a structure that has the following properties:

It consists of nodes and leaves
It has a single root element
Both nodes and leaves each hold a single element
Each node can have a non empty list of subtrees (a leaf could be considered a node with an empty list of children)
All elements inside the tree are of the same type and can be compared against each other
There are no duplicated elements inside a tree (this is especially interesting when it comes to inserting elements)

An implementation of this in Haskell could look like this (without the Eq constraint on a that would be required to compare the elements):

data Tree a = Node a (NonEmpty (Tree a)) | Leaf a

From my (rather limited) theoretical knowledge about data structures like this I think that it is some kind of unordered, unique tree.
I guess that there is a well-known data structure somewhere out there and I'm hoping that someone can point me to the name as well as some resources about it.

I'm especially interested in algorithms for typical operations on this data structure:

Traversing the tree
Adding a single element to a tree
Removing a single element from a tree
Adding a tree to another tree (if the root element is already contained in the target tree, the tree should become a subtree to this element)
Removing an element (including its children) from a tree

To summarize: Is this data strucure well known? If so, what is the name for it and where can I find more information about efficient algorithms for operations on this data structure?

This is simply a tree, where all elements are unique.  I'm not aware of any special name.


Maximum number of different substrings in big string I'm trying to find the maximum number of different substrings of string consisting only of lowercase letters 'a' - 'z', if the length of string can be up to $5000$

Firstly, I was thinking that the number of substrings is $\frac{n\cdot(n-1)}{2}$ but then I noticed that a lot of the substrings will be the same, and also because of the length of the string of most $5000$ we cannot put all the possible strings with length 3 for example.

What is the maximum number of different substrings we can get in one string of length $5000$

Here is a general solution for an alphabet of size $d \geq 3$ and a string of length $n$.

Every string of length $n$ has $n-\ell+1$ substrings of length $\ell$. Hence the number of different substrings, of any length, is at most
$$
\sum_{\ell=1}^n \min(n-\ell+1,d^\ell).
$$
Consider now an infinite de Bruijn sequence, in which each prefix of size $d^r + r - 1$ is a non-cyclic de Bruijn sequence for length $r$. When $d \geq 3$, such sequences exist, as shown by Becher and Heiber, On extending de Bruijn sequences. Truncate such a sequence to length $n$. We leave the reader to show that the truncated sequence achieves the bound stated above.


Is there a simple argument why graph isomorphism is not NP-complete? I need to provide one simple evidence that graph isomorphism (GI) is not NP-complete.
I saw a number of papers on google scholar and answers on StackExchange. However, I have very limited knowledge of graph isomorphism, and I would like to just provide one simple evidence which I both understand and can explain clearly.

Below is what I can think of. Is this a valid argument?
Currently, we can solve GI in Quasipolynomial Time. If GI is NP-complete, then we should be able to solve other NP-complete problems in Quasipolynomial Time as well. However, right now, we are unable to solve any NP-complete problem in Quasipolynomial Time. Therefore, GI cannot be in np-complete.

The type of argument you are looking for is as follows:

If graph isomorphism were NP-complete, then some widely believed complexity assumption fails.

There are at least two such arguments:

Schöning showed that if graph isomorphism is NP-complete then the polynomial hierarchy collapses to the second level (equivalently, $\Sigma_2^P = \Pi_2^P$).

Babai's quasipolynomial time algorithm implies that if graph isomorphism is NP-complete then the exponential time hypothesis fails.

Whether such arguments are "valid" or not is a sociological question, not a mathematical one.


Finding nearest of a list of points on Euclidian plane to a given reference point Problem formulation: Given a list $L$ of $n$ points in the Euclidian plane and a reference point $R$ also in that plane, find a closest point $P\in L$ such that, for all $X\in L$, $|PR|\le|XR|$.

Aditional constrains: Trivial algorithm will just iterate all candidate points in $L$, compute their distance to $R$ and select the closest. Complexity of that is $O(n)$, but the number of points may be huge – I need an algorithm that runs in time $O(\log n)$.

Any preprocesing (building data structures etc.) can be done with $L$ but it should run in $O(n\log n)$ time.

Problem extensions: In case that there are multiple closest points $P$ with the same distance from $R$ it would be nice if the algorithm identified that and returned all of them.

I will actually need to detect $m$ nearest points ($m$ is much smaller then $n$). I can do that by running algorithm to find single closest point $m$ times, each time excluding previously found points from search. However it would be nice it the algorithm could be extended to find $m$ closest points in one call.

You can build a 2d binary search tree for the points in $L$ and then have closes-point queries done in expected $O(\log n)$ time: (see this presentation by Robert Sedgewick, pp.26-27). However, the worst-case time is still $O(n)$. An example of the worst-case input is the situation when all the points from $L$ lie on a circle and $R$ is the center of that circle.


minimum vertex set removal for edge-free graph I'd like to know the name and the algorithm for the following problem which I'm guessing is a classic, but is slightly different from graph connectivity.

Consider a undirected graph G=(V,E). What is the minimum number of vertices which removal (vertices and their adjacent edges) makes the resulting sub-graph empty of any edge?

For example:
If A - B - C, then just need to remove B.
If A - B - C and A - C, then need to remove at two vertices (any pair).

For an algo, intuitively I'd proceed by removing first the vertex of highest degree and proceed the same on the remaining graph until there are no edges. Not sure if it gives the min number. For sure, in the worst case I can always go through all possible |V|! removal possibilities and take the min.

The problem you describe is called minimum vertex cover. It is a well-known NP-complete problem, so there is no known algorithm that will always be fast (as in polynomial runtime) and give the optimal solution. However, fast approximation solutions are known, as well as algorithms that, while slow in the worst case on general graphs, are fast on significant classes of graphs. See the linked Wikipedia article for details and links to even more details.


Are there any known lower-bounds for complexity on Non-determinsitic machines For some problems, like sorting, we know that on a deterministic RAM Machine, any comparison sort must take at least $\Omega(n\log n)$ time.

Are they any problems where we have known lower bounds for the complexity of a problem when using non-deterministic machines?

$NP$-hard or -intermediate problems are probably the most interesting, but others would be interesting (for example, an $\Omega(n)$ lower bound on non-deterministic sorting).

Obviously, there are no known exponential lower-bounds for $NP$ problems, since that would imply $P\neq NP$, but are they any known polynomial bounds?

No.  There are no known polynomial bounds.  The best lower bounds known are merely linear.

As described here, the situation for circuits at least is "quite depressing": there are no known lower bounds that are better than $\sim 4n$.  That's the case even when you pick the problem.  There is no explicitly known problem where we can prove a lower bound better than $4n$.

Of course, for many problems it is easy to get a lower bound of $n$, by noting that for some functions it is necessary to read all of the input bits.  So we can do only a constant factor better than the trivial lower bound.

Moreover, it is easy to prove (by a counting argument) that there exist functions that require at least $2^n/\text{poly}(n)$ gates to compute.  The catch is that this proof is non-constructive: we don't know an explicit example of such a function.  So there is an exponential gap between the best lower bound we know how to prove, and what we know must be the actual best lower bounds (even though we don't know how to prove it for any specific problem).

I don't expect anything fundamental to change if you replace circuits with RAM machine algorithms.  Moreover, this shows that we don't know how to prove useful/non-trivial lower bounds for deterministic algorithms.  Proving useful/non-trivial lower bounds for non-deterministic algorithms is even harder.

(The situation might be slightly different with Turing machines, as they're a bit slower/less powerful than RAM machine algorithms -- but you asked about the latter, so I assume we can ignore this.)

You might enjoy perusing the lower-bounds tag on CSTheory.SE.


Can polynomial many-to-one reduction be done to a specific problem instance? Let's say I reduce the problem $A \in L$ to $B \in K$ , with a function $f: \Sigma^{*} \rightarrow \Gamma^{*}$ such that $w \in L \Leftrightarrow f(w) \in K$ . I know if I want to solve $A$, given some polynomial time algorithm for $B$, I just have to transform $A$ to $B$ and solve $B$. So it can be thought as:

  The reduction must be done from arbitrary instance of $A$ to a legal instance of $B$

My question is, do I have to reduce to arbitrary instance of $B$ or some instance of $B$? I.e. reduction from TQBNF to Generalized Geography is done to some valid graph instance, but there exist many more valid instances of Generalized Geography.

The mapping does not have to be surjective (onto) nor injective (one-to-one). In fact, any problem that can be solved in polynomial time can be polynomial time many-one reduced to any problem that has at least one accepting instance and at least one rejecting instance: just solve the original problem in polynomial time, then return the accepting instance if the original problem was an accepting instance, or the rejecting instance if the original problem was a rejecting instance.

That said, the Berman–Hartmanis conjecture states that all NP-complete problems are polynomial time isomorphic, meaning that there is a bijective polynomial-time many-one reduction between them with a polynomial-time inverse. This is currently an unproven conjecture, and only refers to NP-complete problems.


Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items Assume for the regular knapsack problem we have additional information - maximal weight of every item - lets denote it as P. Using this information, I want to solve the problem using dynamic programming in $O(n^2P)$.
Anyone have an idea how to solve it?

If $W \ge n \cdot P$ you can add all elements in the knapsack.
Otherwise $W < n \cdot P$ in which case any algorithm with complexity $O(n W)$ will also have complexity $O(n \cdot (nP)) = O(n^2P)$. In particular the pseudo-polynomial dynamic programming solution described in Wikipedia works in $O(n W)$.


What is the possible number of states in the DFA of intersection of two given FA? Consider a DFA over $a,b$  accepting all strings having number of $a$ 's divible by 6 and number of $b$ 's divisble by 8. What is the minimum number of states in the resultant DFA ?

This problem can be solved by assuming 2 DFAs. One accepting the number of $a$ 's divible by 6 and the other accepting with number of $b$ 's divisble by 8. And then taking intersection of them. So what will be the number of states in the resultant DFA?

I tried drawing the DFA accepting all strings having number of $a$ 's divible by 3 and number of $b$ 's divisble by 3, and found it to have 3x3 (9) states. Can I asssume the reuslt to be 48 states for this case? Can it be inferred that the for string accepting number of $a$ 's divible by $m$  and number of $b$ 's divisble by $n$ , there will be $mn$  states? Or I need to draw it by hand? Or anything other? Any subtle hint will be very helpful.

The product construction shows that if $L_1$ is accepted by a DFA having $n_1$ states and $L_2$ is accepted by a DFA having $n_2$ states then $L_1 \cap L_2$ is accepted by a DFA having $n_1n_2$ states; browse back to the product construction to understand why. The resulting DFA need not be minimal even if the DFAs for $L_1$ and $L_2$ were (a trivial example is given by $L_1 = L_2$, assuming $n_1>1$). In your case, this means that if you can find a DFA for $\{w : 6\mid \#_a(w)\}$ having six states and one for $\{w : 8\mid \#_b(w)\}$ having eight states, then you can find a DFA for the intersection having 48 states.

Is this DFA minimal? You can use the Myhill–Nerode criterion to show that indeed it is: the 48 words $\{ a^i b^j : 0 \leq i < 6, \; 0 \leq j < 8 \}$ are pairwise incomparable.


Can a language have $\Sigma^{*}$ as its syntactic monoid? As per the title I was wondering if it's possible for a language $L \subseteq \Sigma^{*}$ to have $\Sigma^{*}$ as its syntactic monoid and if so could one give an example of such a language? I first thought that this was probably an easy question with a simple answer but I haven't been able to make much progress with it, maybe it has a simple answer and I am just overlooking it?

If we look at the syntactic congruence $\sigma_L = \{(w,z) \in \Sigma^{*} \times \Sigma^{*}: (\forall u, v \in \Sigma^{*}) \; uwv \in L \Leftrightarrow uzv \in L\}$ we see that in order to have $w \cong_{\sigma_{L}} z \Leftrightarrow w = z$ we must have that $(\forall w, z \in \Sigma^{*} \; w \not = z) \; (\exists u, v \in \Sigma^{*})\; uwv \in L \Leftrightarrow uzv \notin L$. Which seems like quite a strong condition. It's also clear that such a language couldn't be regular as it is known that a language is regular if and only if it has a finite syntactic monoid.

It seems to work to take $L=\{ww: w\in\Sigma^* \text{and $|ww|$ is a power of $2$}\}$.

First, we can show that if $|u|>|v|$ then they are not equivalent.
Indeed, there is $x$ such that $|uxux|$ is a big power of $2$, say $2^{|u|+|v|}$.
Therefore, $uxux\in L$.

But then the length of $vxux$ cannot be power of $2$, because its difference to $2^{|u|+|v|}$ is only $|u|-|v|$. Therefore, if we take $y=xux$, we have $uy\in L$ and $vy\notin L$.

Now it suffices to show that words of the same length are not equivalent.
Let $u\neq v$ with $|u|=|v|$, and let $x$ such that $|ux|$ is a power of $2$ (and then so is $|uxux|$). Then you can see that $(u,v)\notin\sigma_L$ because $uxux\in L$ and $uxvx\notin L$.


Property testing of a complete multipartite graph Propose and prove an $\epsilon$-test for the following property in the dense graph model: $G=(V,E)$ is a complete multipartite graph. That is, there exists a partition $V=V_1\cup\ldots\cup V_\ell$ such that $uw\in E$ if and only if there are $i\neq j$ such that $u\in V_i$ and $w\in V_j$.

I have been stuck at trying to solve this question for a few days. I tried to devise an algorithm along the lines GGR98 for bipartiteness testing (such as here), where we sample a sets $U$ and $S$ of size $\mathrm{poly}(1/\epsilon)$ and try to "self-correct" $S$ based on a small number of "partitions" induced by $U$. In particular, I am not sure how to define "violating edges with respect to $U$" for the above mentioned property. Any help?
EDIT: The number $\ell$ is not given to the algorithm as input. In other words, the task is to determine if there exists an $\ell$ such that the graph is complete $\ell$-partite.

The following answer construct a tester for a graph being complete $\ell$-partite for a fixed value of $\ell$.
Consider the following tester:

Choose $\ell+1$ vertices at random.
Verify that the edges between them are consistent with a complete $\ell$-partite graph, that is, there is a way to color the vertices using $\ell$ colors such that there is an edge between two vertices iff they have different colors.

We claim that for every $\epsilon>0$ there exists $\delta>0$ such that if the test succeeds with probability at least $1-\delta$, then the graph is $\epsilon$-close to complete $\ell$-partite. To show this, we assume that the test succeeds with probability at least $1-\delta$, and show that the graph is $\epsilon(\delta)$-close to complete $\ell$-partite, where $\epsilon(\delta) \to 0$ as $\delta \to 0$. Moreover, the proof is by induction on $\delta$, the case $\ell = 1$ being trivial.
Let $\gamma$ be the probability that $\ell-1$ randomly chosen points form a clique. If $\gamma \leq \sqrt{\delta}$ then the graph passes the test for being complete $(\ell-2)$-partite with probability at least $1-\sqrt{\delta}-\delta$, and we complete the proof by induction. Assume, therefore, that $\gamma \ge \sqrt{\delta}$.
The expected failure probability of the test given that the first $\ell-1$ points form a clique is at most $\delta/\gamma \leq \sqrt{\delta}$. In particular, we can find a clique $x_1,\ldots,x_{\ell-1}$ such that with probability $1-\sqrt{\delta}$ over the choice of $x_\ell,x_{\ell+1}$, the graph induced by $x_1,\ldots,x_{\ell+1}$ is consistent with a complete $\ell$-partite graph.
Define the color $c(x)$ of a point $x \neq x_1,\ldots,x_{\ell-1}$ as follows. If $x$ is connected to all but $x_i$, then $c(x) = i$. If $x$ is connected to all, then $c(x) = \ell$. Otherwise, $c(x) = \bot$. Then with probability $1-\sqrt{\delta}$, the following holds:

Either $c(x_\ell) = c(x_{\ell+1}) \neq \bot$ and $(x_\ell,x_{\ell+1})$ is not an edge,
Or $c(x_\ell) \neq c(x_{\ell+1})$, $c(x_\ell),c(x_{\ell+1}) \neq \bot$, and $(x_\ell,x_{\ell+1})$ is an edge.

This shows that we can partition all but $\sqrt{\delta} n$ of the vertices into $\ell$ sets, such that the induced graph differs from the corresponding complete $\ell$-partite one in an $O(\sqrt{\delta})$-fraction of edges.


Three phase commit : study case Consider a group of five processors implementing three-phase commit protocol. During the execution of the protocol, the coordinator and one other process crash. Two of the remaining processes are waiting in "READY" state for the coordinator while the third process is in "PREPARE COMMIT" state. Can they continue and complete the protocol without waiting for recovery of the crashed processes? Do they COMMIT or ABORT? Which state can the crashed process be in?

In my opinion, the crashed processor maybe was in the "ABORT" state, so how can the other processors know the "global decision"?

I found the answer consulting the book "Distributed System : Principles and Paradigms" (Andrew S. Tanenbaum - Maarten Van Steen). First of all it is possible to continue just because 3PC is non-blocking protocol by definition. A processor can reach the state “PRE-COMMIT” only if the coordinator was in state “PRE-COMMIT” (thus each processor sent a COMMIT request), so the crashed processor could not be for sure in state “INIT” nor in "ABORT", but at least in the state “READY”. Anyway, all the “alive” processors, after seeing the “PRE-COMMIT”, will go in “COMMIT” state.


Source and Destination IP of TCP connection Five Tuple Identifier of TCP connection is (TCP, local IP, local port, remote IP, remote port).

I have made 3 computers in virtual box and set BOX1 for client, BOX2 for median, and BOX3 for server. And made interfaces between them to communicate.

So I have executed the server program on BOX3 and client program in BOX1. The client program calls 10.0.2.2.

When I captured packets from BOX1 and BOX3, the IP Source and Destination IP address was like this.

BOX1's SYN
Src : 10.0.1.2
Dest : 10.0.2.2

BOX3's SYN
Src : 10.0.1.2
Dest : 10.0.2.2

What I have thought is that in BOX1, Src must be 10.0.1.2 and Dest must be 10.0.1.1. And in BOX3, it must be 10.0.2.1 for Src and 10.0.2.2 for Dest. Because BOX1 communicates with BOX2 and BOX3 commuicates with BOX2.

Why does IP is like that?

Thanks for your help.

If you consider the format of the TCP-IP datagram.

Source Address: The 32-bit IP address of the originator of the datagram. Note that even though intermediate devices such as routers may handle the datagram, they do not normally put their address into this field—it is always the device that originally sent the datagram.

Destination Address: The 32-bit IP address of the intended recipient of the datagram. Again, even though devices such as routers may be the intermediate targets of the datagram, this field is always for the ultimate destination.

You can get more understanding here.


What is the name of the word problem for free groups under straight line program encoding? I believe that the word problem is the problem to decide whether two different expressions denote the same element of a suitably defined algebraic structure. For simplicity, let us focus on free groups here. (Because I'm only interested in free algebras, and for groups one might indeed call this a word problem.) The expressions $(b^{-1}c)^{-1}b^{-1}(ab^{-1})^{-1}$, $(ab^{-1}c)^{-1}$, and $a^{-1}bc^{-1}$ are examples of such expressions. The first and second expression denote the same element of the free group, while the third expression denotes a different element.

The straight line program encoding is basically the same concept as arithmetic circuits, without implicit commutativity. It is one of the natural encodings of elements for a free algebra. One way to define the straight line program encoding is like in definition 1.1 from one of the google results for straight line program: The straight line program encoding of $f$ is an evaluation circuit $\gamma$ for $f$, where the only operations allowed belong to $\{()^{-1},\cdot\}$. More precisely: $\gamma=(\gamma_{1-n},\dots,\gamma_0,\gamma_1,\dots,\gamma_L)$ where $f=\gamma_L$, $\gamma_{1-n}:=x_1,\dots,\gamma_0:=x_n$ and for $k>0$, $\gamma_k$ is one of the following forms: $\gamma_k=(\gamma_j)^{-1}$ or $\gamma_k=\gamma_i\cdot\gamma_j$ where $i,j<k$.

The application of the operation $()^{-1}$ can easily be restricted to $\gamma_k=(\gamma_j)^{-1}$ for $j\leq 0$ without increasing $L$ to more than $2L+n$. This means that we are basically talking about words over the alphabet $\{x_1,\dots,x_n,(x_1)^{-1},\dots,(x_n)^{-1}\}$, hence the name "word problem" makes sense. But it seems a bad name for the general problem to decide whether two elements of a free algebra given by straight line programs are identical. It might be called identity testing.

  Does the problem (to decide whether two elements of a free algebra given by straight line programs are identical) already has an established name, or is there a good name for this problem?

Maybe a better idea would be to give a name to the complementary problem, i.e. the problem to distinguish two different elements of a free algebra. So calling it slp distinction problem for free groups (commutative rings, commutative inverse rings, Boolean rings, ...) could work, because straight line program (slp) is a long name (but good and descriptive nevertheless). The advantage of naming the complementary problem is that we get problems in RP and NP, instead of problems in co-RP and co-NP.

The computational complexity of this problem is not worse than that of identity testing of constant polynomials over $\mathbb Z$ in straight line program encoding (no variables, i.e. $n=0$, but the straight line programs allow to compactly encode huge numbers): Using the same approach as in the dlog-space algorithm for the normal word problem, the problem can be reduced to deciding whether the product of integer 2x2 matrices equals the identity matrix. (The word problem over $n$ letters easily embeds into the word problem over $2$ letters, for example you can replace $a$, $b$, $c$, $d$ by $aa$, $ab$, $ba$, and $bb$.) So the problem is in randomized polynomial time (RP) (or rather co-RP). However, I didn't manage to show that it is actually equivalent (in complexity) to identity testing of (constant) polynomials over $\mathbb Z$, as I initially hoped. (This is unrelated to the answer by D.W., which rather shows that the significance of straight line encoding is currently not widely appreciated.)

The blog post you link to already gives a deterministic polynomial-time (in fact, linear-time) algorithm for the word problem over a free group with 2 letters.

In contrast, no deterministic polynomial-time algorithm for identity testing for polynomials is currently known (this is a famous open problem).

Therefore, it's not likely to be easy to prove that the word problem over the free group is equivalent in complexity to identity testing of polynomials.

The "straight-line encoding" doesn't seem to change the complexity of the word problem in any interesting way.  It seems equivalent to simply specifying the input as an expression (i.e., a sequence of symbols, where each symbol is either $x_i$ or $x_i^{-1}$).


Should crossover operation in a genetic algorithm modify individuals in order to be "valid"? I'm working in a project to create levels for a videogame using genetic algorithms.

I'm using a undirected graph to represent the level, each node represent a room and each room have a maximum of four possible connections (north, south, east, west). Also each connection just have one compatible connection (North <=> South , East <=> West), this mean you can't connect North with East for example, or North with North (Also a room can't be connected with itself).

Anyway, I already have a way to create the initial population with thoses restrictions, but now I'm thinking about the crossover function.

Let's say I crossover two graphs by cutting them in half and merging those halves, there are chances for a room to have more than four connection or using the same connection to connect two differents rooms.

So my question is, Should I create a crossover method to respect thoses restrictions or just to lower the score of thoses individuals?

In my experience, a well crafted operator that avoids or repairs constraint violations is nearly always far preferable to one that relies on selection alone to find feasible solutions.


Temporal logic for interface invariants I am looking for some sort of temporal logic for expressing invariants in interfaces. Since interfaces do not specify data representation, the invariants must rely solely on the publicly available functions of the interface.

For example, suppose we have a simple interface (Java style) Sum:

interface Sum {
    public void add (int a);
    public int getSum();
}

I want to express in an invariant that getSum returns the summation of a in all calls to add(a), without using any data representation of this sum.

The only way I can think of doing this is by using some form of temporal logic. Is there any literature on this subject available I can read? Any pointers would be much appreciated.

Whatever you do, your specification will turn out to have internal state reflecting the accumulator inside your object. For a class this simple, the specification won't be any simpler than the implementation. The point is that for much more complex cases the specification is simpler. Consider a dictionary, where you add data under a key and must be able to retrieve it later. Your specification can very well be the equivalent of a linear array of key/value pairs, and the search a simple linear search. Your implementation would perhaps be a scheme based on hashing or balanced binary trees. The specification is easy to reason with, you prove your implementation behaves the same as the specification, and you are set. Tomorrow you rip out the implementation, and replace it by some fancier structure, prove again that it complies with the specification. No changes elsewhere.

Specifications are essentially writing the same program again in another (hopefully easier to handle) programming language, probably foregoing any performance considerations, and reasoning that both programs do the same. The specification languages up to date have turned out much harder to use than the regular programming languages (and specifications can have bugs too...), and the proof that they behave the same isn't for the faint of heart. And if I come up with an idea of how my program should behave, and program that, it stands to reason that the specification and the final program will share the same misconceptions and missed corner cases. There have been spectacular failures of the "program verification" movement. Look at Berry's "Academic Legitimacy of the Software Engineering Discipline" (CMU/SEI-92-TR-34) for an example of a program of a couple dozen lines, written and "proved correct", then fixed and again verified for publication in academic journals by some of the maximal experts in the area several times, and which was wrong each round.


DES encryption - what happens if all sub-keys are the same? What will happen if we change the DES encryrption algorithm to use the same key in each round ?

How will it affect the encryption - will it only make the encryption same as decryption or are the more effects ? I couldn't find any other possible effects in the DES standard description.

Thanks

It will make the algorithm insecure.

It will be become vulnerable to slide attacks.

It will make encryption become equivalent to decryption, which is a weakness.  This is sometimes called a "weak key"; with your scheme, every key will be "weak".

It will also reduce the keyspace to 48 bits, which is too small to be secure.


CLRS closest-pair $L_m$ distances I am studying algorithms and datastructures, and in CLRS chapter 33.4, the exercise 33.4-4 states the following:

We can define the distance between two points in ways other than euclidean. In the plan, the $L_m$ distance between points $p_1$ and $p_2$ are given by the expression $(|x_1-x_2|^m+|y_1-y_2|^m)^{1/m}$. euclidean distance, there, is $L_2$-distance. Modify the closest pair algorithm to use the $L_1$-distance, which is also known as the Manhattan distance.

I understand its an easy modification, however when I've been comparing my intuition with that of solutions provided online (e.g. https://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html), all I can find is that they all point to the number of points in the $\delta$ x $2\delta$ is increased to 10 (from 8), adding one point to the middle of both squares formed by the rectangle (here marked with red below):

Can anyone explain to my why this is the case? Intuitively I cannot see why it should be the case that the number of points in the rectange should increase, when switching to another $L_m$-distance?

The Manhatten distance $\geq$ Euclidean distance from what I can see in all instances, but why should this infer, an increase in points found in the $\delta$ x $2\delta$ space.

What am I missing?

One approach to see what is going on here is via the notion of an open ball under a given distance. Given a distance $d$, the open ball of radius $r$ around a point $p$ is given by $B_r(p):=\{q\mid d(p,q)<r\}$, i.e. the set of all points with distance less than $r$ to the center of the ball, $p$. In the plane and under the Euclidean distance, a ball is an open disk (a disk with the boundary removed) of radius $r$.

Since $\delta$ is the minimum distance between any pair of points in the left half, any pair of points in the left $\delta\times\delta$ square has a distance of at least $\delta$. This is equivalent to saying that the open ball of radius $r$ centered at a point $p\in P_L$ contains no other point $q\in P_L$. So, the maximum number of points from $P_L$ that can be in the $\delta\times \delta$ square is the largest number of points you can 'fit' into the square such that the ball surrounding each of those points contains no other point from $P_L$.

An open ball under the Euclidean distance is an open disk. If you place four points at the corners of the $\delta\times \delta$ square, the open disks of radius $\delta$ centered at those points together cover the entire square, so there is no position in the square to place for a fifth point.

However, under the Manhattan distance, an open ball of radius $\delta$ is an open square with diagonal length $\delta$, rotated by $45$ degrees (an "open diamond"). If we place such an open diamond at each corner of the $\delta\times \delta$ square, then there is exactly one position in the square not covered by an open diamond: the center of the square. This is the location where you can place a fifth point under the Manhattan distance.

As for the $L_m$-distance with $m>2$, note that the balls under these metrics all strictly contain the ball under the $L_2$-distance. I'll leave it up to you to use this fact to determine the maximum amount of points that can be in the $\delta\times\delta$-square.


Is it possible to write an HTML compiler with no mutable state? That's probably a vague question but allow me to try and give an example:

My compiler does transformations on HTML (from HTML to HTML). It scans a flattened DOM tree, and relies on lookbehinds (on elements pushed onto a stack) to decide what transformation to apply. I can give more detail if necessary but I don't want to lose the reader.

Can such logic be alternatively implemented with no mutable state? I have become a big believer in functional programming and have made it a point to make my code as functional-style as possible. I don't like loops that perform actions based on the content of a previous iteration, by saving the information from a previous iteration in stacks or booleans. I need to augment the functionality of this routine and will probably tip the code from being "just about understandable" to "only the author will understand this, everyone else don't touch".

But I have little background in compiler theory & development so am wondering if the problem domain necessitates mutable state in practice.

In theory, any program can be treated as functional by treating every operation as "replace the world with a world this piece of state replaced by a different value". In practice ... this actually works pretty well.

Your code will look something like:

root_node = parse_html()

for each operation:
    root_node = root_node.replace_using_operation(operation)

For a leaf or node that you know won't be affected by this operation, replace_using_operation looks like:

fn replace_using_operation(self, op):
    return self

For the typical non-leaf case, replace_using_operation will look like:

fn replace_using_operation(self, op):
    children = new List<Node>();
    # pedantically, this is not "functional", but realistically it is.
    # if your language has generators or a iterator map function you can
    # make it purely functional, but most people find this easier to read.
    for each ch in self.children:
        children.append(ch.replace_using_operation(op))
    new_self = new Node(children)
    delete self
    return new_self

Of course, depending on what knowledge you have of the operation, you might want to perform different operations on some children. Also note that you're perfectly free to pass additional arguments (including snapshots of other branches of the tree - just remember you don't own them) or to have entirely separate replace_* functions instead of passing operation as an argument.

This code is only a very rough skeleton, after all.


On the language of Turing machines not accepting their own encoding Let $\text{NOT-SELF} = \{\langle M \rangle : M \text{ is a TM that does not accept } \langle M \rangle \}$. How do you prove the following claim?

  If $Q$ is a TM so that $L(Q) \subseteq \text{NOT-SELF}$, prove that $\langle Q \rangle \in \text{NOT-SELF}$.

In general, this problem is undecidable: that is, there is no general algorithmic solution.

Yuval gives a good answer for the specific question. Here are some general tips for showing the subset relation, that is, that $L_1 \subseteq L_2$:

Induction on word length. Show that the smallest string in $L_1$ is in $L_2$ and that having one string. This is most effective when there's some sort of inductive structure to the languages you are looking at.
Paths to accepting states. Look at how a word is actually accepted by your first machine, the states it travels through and what your tape looks like. For each step, show that you can do an equivalent step in the second machine which won't fail. The hard part is doing this abstractly enough so that it works for all words. This will usually break into a massive proof-by-cases.
Forget about Turing Machines. Look at the machines, find out what languages they accept as sets, and perform pure logic on those sets. This isn't very useful if you are given a random TM, but is handy if you know what one TM figures out. For example, if you realize that $L_1$ is the set of all primes larger than 10, and $L_2$ is the set of all odd positive integers, then it's pretty easy to show that $L_1 \subseteq L_2$


Are these REs equivalent? I have to implement a compiler for a given language as part of an assignment.
The language is kept simple enough such that it can be fully expressed through REs.
My question lies with two of the REs provided:

DIGIT := [0-9]?
INTEGER_LITERAL := DIGIT DIGIT*

When I saw the RE for INTEGER_LITERAL I sort of thought to myself:

"Well that's just DIGIT+"

Am I right to think so?

Any regular expression satisfies $r^+ = rr^* = r^*r$. In fact, one often defines $r^+$ using one of these formulas, usually $r^+ := rr^*$.