How to conceive a Turing machine that is the intersection of the languages of two Turing machines? We have $ M = (Q,Σ,Γ,δ,q_0,q_a,q_r) $ and $ M′= (Q′, Σ , Γ′, δ′,q_0′,q_a′,q_r′)$.
We want to construct a standard Tm that recognize L(M) ∩ L(M′). How do I go about it? I don't have much more information than this. Anything to get started would be appreciated.

What you ask might not be possible in general. If $L(T)$ denotes the set of words $x$ for which $T(x)$ accepts, and you do not have the additional assumption that $M$ and $M'$ recognize $L(M)$ and $L(M')$, respectively, then you could choose:

$M$ as a Turing machine that takes another Turing machine $T$ as input and accepts if and only if $T$ halts on empty input. (Notice that such a Turing Machine $M$ exists).
$M'$ as a Turing Machines that recognizes $\Sigma^*$.

Then, there is no Turing Machine $T$ that recognizes $L(M) \cap L(M') = L(M)$ since $T$ would solve the halting problem.
On the other hand, if you are fine with a Turing machine that accepts $L(M) \cap L(M')$ or if you have the additional assumption that $M$ and $M'$ recognize $L(M)$ and $L(M')$, respectively, your problem is solved by a Turing machine that, on input $x$, operates as follows:

Simulate $M(x)$ until it halts (possibly never).
If $M(x)$ rejects, reject.
Simulate $M'(x)$ until it halts (possibly never).
If $M'(x)$ rejects, reject.
Accept.


Are all Integer Linear Programming problems NP-Hard? As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming problem, but the Wikipedia page states that this is NP-Hard. To me, this implies the assignment problem is in NP-Hard.

But surely the assignment problem can't be in both P and NP-Hard, otherwise P would equal NP? Does the Wikipedia page simply mean that the general algorithm for solving all ILP problems is NP-Hard? A few other sources state that ILP is NP-Hard so this is really confusing my understanding of complexity classes in general.

If a problem is NP-Hard it means that there exists a class of instances of that problem whose are NP-Hard.
It is perfectly possible for other specific classes of instances to be solvable in polynomial time.

Consider for example the problem of finding a 3-coloration of a graph. It is a well-known NP-Hard problem. Now imagine that its instances are restricted to graphs that are, for example, trees. Clearly you can easily find a 3-coloration of a tree in polynomial time (indeed you can also find a 2-coloration).

Consider decision problems for a second.
A method of proving the hardness of a decision problem $P$ is devising a polynomial (Karp) reduction from another problem $Q$ that is known to be NP-Hard.
In this reduction you show that there exists a function $f$ that maps each instance $q$ of the problem $Q$ to an instance of the problem $P$ such that:
$q$ is a yes instance for $Q \iff f(q)$ is a yes instance for $P$.
This implies that solving $f(q)$ must be "at least as difficult" as solving $q$ itself.

Notice how it's not required for the image of $f$ to be equal to the set of the instances of $P$ . Therefore it's perfectly possibile for problem $P$ restricted to some subset of instances to not be hard.

To return to your original question:

The assignment problem can be solved in polynomial time, i.e., a solution to each instance of the assignment problem can be computed in polynomial time.
ILP is NP-Hard: in general it might be hard to compute a solution to an ILP problem, i.e. there are instances of ILP that are hard.
Some specific instances of ILP can be solved in polynomial time.


What exactly (and precisely) is "hash?" I have heard the word "hash" being used in different contexts (all within the world of computing) with different meanings. For example, in the book Learn Python the Hard Way, in the chapter on dictionaries it is said "Python calls them "dicts." Other languages call them "hashes."" So, are hashes dictionaries?

The other common usage of the word is in relation to encryption. I have also heard (& read) people using the word "hash" as a specific function within high-level programing.

So, what exactly is it?

Can anyone (with time and who is knowledgeable) kindly explain the nitty-gritties of "hash (or hashes)?"

The Wikipedia article on hash functions is very good,
but I will here give my take.

What is a hash?
"Hash" is really a broad term
with different formal meanings in different contexts.
There is not a single perfect answer to your question.
I will explain the general underlying concept and
mention some of the most common usages of the term.
A "hash" is a function $h$ referred to as hash function
that takes as input objects and outputs a string or number.
The input objects are usually members of basic data types like
strings, integers, or
bigger ones composed of other objects like user defined structures.
The output is a typically a number or a string.
The noun "hash" often refers to this output.
The verb "hash" often means "apply a hash function".
The main properties that a hash function should have are:

It should be easy to compute and
The outputs should be relatively small.

Example:
Say we want to hash numbers in the range from 0 to 999,999,999 to
number between 0 and 99.
One simple hash function can be $h(x) = x \mod 100$.
Common additional properties:
Depending on use case we might want the hash function to
satisfy additional properties.
Here are some common additional properties:

Uniformity:
Often we want the hashes of objects to be distinct.
Moreover we may want the hashes to be "spreading-out".
If I want to hash some objects down into 100 buckets
(so the output of my hash function is a number from 0-99),
then I am usually hoping that about 1/100 objects land in bucket 0,
about 1/100 land in bucket 1, and so on.

Cryptographic collision resistance:
Sometimes this is taken even farther,
for instance, in cryptography
I may want a hash function such that
it is computationally difficult for an adversary
to find two different inputs that map to the same output.

Compression:
I often want to hash arbitrarily-large inputs down into
a constant-size output or fixed number of buckets.

Determinism:
I may want a hash function whose output doesn't change between runs,
i.e. the output of the hash function on the same object will always remain the same.
This may seem to conflict with uniformity above, but
one solution is to choose the hash function randomly once,
and not change it between runs.

Some applications
One common application is in data structures such as a hash table,
which are a way to implement dictionaries.
Here, you allocate some memory, say, 100 "buckets";
then, when asked to store an (key, value) pair in the dictionary,
you hash the key into a number 0-99, and
store the pair in the corresponding bucket in memory.
Then, when you are asked to look up a key,
you hash the key into a number 0-99 with the same hash function and
check that bucket to see if that key is in there.
If so, you return its value.
Note that you could also implement dictionaries in other ways,
such as with a binary search tree (if your objects are comparable).
Another practical application is checksums,
which are ways to check that two files are the same
(for example, the file was not corrupted from its previous version).
Because hash functions are very unlikely to map two inputs to the same output, you compute and store a hash of the first file,
usually represented as a string.
This hash is very small, maybe only a few dozen ASCII characters.
Then, when you get the second file,
you hash that and check that the output is the same.
If so, almost certainly it is the exact same file byte-for-byte.
Another application is in cryptography,
where these hashes should be hard to "invert" --
that is, given the output and the hash function,
it should be computationally hard to figure out the input(s)
that led to that output.
One use of this is for passwords:
Instead of storing the password itself,
you store a cryptographic hash of the password
(maybe with some other ingredients).
Then, when a user enters a password,
you compute its hash and check that it matches the correct hash;
if so, you say the password is correct.
(Now even someone who can look and find out the hash saved on
the server does not have such an easy time pretending to be the user.)
This application can be a case where
the output is just as long or longer than the input,
since the input is so short.


Help With Writing An Algorithm Formally First off - I'm not a Computer Scientist, I'm a Software Developer - so when it comes to presenting an idea in a formal manner to a Computer Scientist, I have no idea how to do so. As such, I'm wondering if someone would be good enough to show me how to write the algorithm/idea I've outlined below in some form of formal alogrithmic notation, please?
Part One:
Say I have a list of 'words' made up from characters of the English alphabet. Essentially, I want to split this list of 'words' up into twenty-six sub-lists, where each sub-list is associated with one letter of the alphabet - a, b, c, etc. Each 'word' should be moved to the sub-list associated with the character that the 'word' begins with - so 'apple' would go in the 'a' sub-list, 'banana' would go in the 'b' sublist, etc. BUT, I only want to divide my original list up into sub-lists provided that there are at least X 'words' in the list that begin with each letter of the alphabet (so if X was 2, there would need to be at least two words beginning with 'a', at least two words beginning with 'b', ..., at least two words beginning with 'z', etc.). In essence, it's either one list with all 'words' in it or 26 sub-lists with at least X 'words' in it.
Part Two:
Assuming I was able to split the list of 'words' up into sub-lists as described in Step One, I then want to further divide each sub-list based on the value of the second character in each 'word'. So there would be an 'aa' sublist, an 'ab' sublist, ..., a 'zz' sublist, etc. Again, I only want to do any further division of the sub-lists provided there are at least X 'words' that begin with every possible two-character combination of English alphabet letters - so at least two 'words' beginning with 'aa', two 'words' beginning with 'ab', ..., two words beginning with 'zz', etc. In essence, it's either 26 sub-lists or 676 sub-lists.
Part Three:
I want this dividing process to continue (character three, character four, etc.) until it is no longer possible to satisfy the criteria that there are at least X 'words' in each sub-list that 'begin' with every possible combination of the number of characters that are currently under consideration.
For argument's sake at this point, it can be assumed that all 'words' are the same length.
Any help is very much appreciated.

Computer scientists are almost people
I think your explanation is pretty good. There is not a single formal way to specify an algorithm, except perhaps for pseudocode but as a software developer you are likely already familiar with that. Apart from that, algorithms that don't rely on intricate math are often best explained through text, as you've done.
Perhaps it could do with a bit more formal language however. First, note that what you're describing is more accurately called a data structure than an algorithm. Indeed, you give no method for creating this structure, but rather give a description of what it looks like.
Furthermore, you could (though I argue this is not mandatory) describe the structure more mathematically if you want, defining the various objects used. For example, say we have some set of words $W$, each of which is a string made up of some set of characters $C = \{a, b, c, \dots\}$. We'll also define $W[s]$ to mean the set of words in $W$ that begin with string $s$. In our case these are English words and characters, but that does not matter for the general case. Now, we can define our data structure recursively as follows (we'll call the structure a "slick" for now, in reference to your username).
A slick $S_s$ for some set of words $W[s]$ denoted $S_s(W[s])$ is defined as a list $[S_{s+a}(W[s+a]), S_{s+b}(W[s + b]), \dots]$. A slick on an entire corpus $W$ is defined as $S_\epsilon(W[\epsilon])$ where $\epsilon$ denotes the empty string.
However, if one of the subsets $W[s+c]$ for $c \in C$ is not of at least some constant size $k$, $S_s$ is instead defined as $S_s(W[s]) = W[s]$.
Note here that we implicitly define every "subslick" $S_s$. That is, the part of the slick where every word already starts with some string $s$. We define the whole slick as a special case of the subslick, namely one where every words starts with nothing, which is true for every word. Finally, we denote the stopping condition that if not every prefix is frequent enough, we stop making slicks.
We might be able to make it shorter and more formal by introducing more notation, but this would in my opinion come at the cost of readability. For example, "if one of the subslicks is not of some constant size $k$, then define it this other way" can be turned into $(\exists_c \, [|W[s+c]| < k]) \rightarrow S_s(W[s]) = W[s]$, but I argue that this does not help most readers.
Of course, this all depends on the audience. If you're submitting a paper in computer science with as its primary purpose the establishment of an algorithm or data structure, I would expect an informal explanation as well as a formal one, with absolutely no ambiguity. I would also expect not just a description of the data structure, but an explanation of its usefulness, and mathematical arguments for its properties.
This is almost exactly a trie
As for the data structure itself, except for the stopping condition this is exactly a trie, a structure that's been around since this paper in 1959. To look for other ideas for formalization, you might want to look for other explanations of the trie on the web.
The difference between the trie (also called prefix tree for obvious reasons) and the slick is that the trie just keeps making tries until there are no more words with a certain prefix. The slick stops significantly earlier, which I'm not sure is a great idea. Indeed, if we're encoding a moderately sized set of English words, we might not find $k$ words that start with an x, and then the data structure collapses entirely. Instead, I'd recommend not collapsing $S_s$ when $W[s+c]$ is small, but rather collapsing $S_s$ only if $W[s]$ is small.


Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true? $\mathsf{3SAT}$ in $n$ variables is an $\mathsf{NP}$ complete problem.

Augment input to $\mathsf{3SAT}$ with constants $\{a_i\}_{i=1}^{n^c}$ where each constant $|a_i|<n^e$ to get an artificial problem ${\mathsf{3SAT}}_{aug}$. There is a direct reduction from $\mathsf{3SAT}$ to ${\mathsf{3SAT}}_{aug}$.

Assume that $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$ where suppose there exists $n^c$ constants for a fixed $c$ that will help solve any $n$-variate $\mathsf{3SAT}$ instance in $n^d$ time for a fixed $d$, however finding those constants offline takes exponential amount of time.

Since by hypothesis of $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$, we have constants that help solve $\mathsf{3SAT}$ in poly time, let augmented input to ${\mathsf{3SAT}}_{aug}$ contain constants that help solve ${\mathsf{3SAT}}_{aug}$ in poly time.

${\mathsf{3SAT}}_{aug}$ is $\mathsf{NP}-\mathsf{complete}$: $\mbox{  }$ Since $\mathsf{3SAT}$ reduces to ${\mathsf{3SAT}}_{aug}$, ${\mathsf{3SAT}}_{aug}$ problem remain $\mathsf{NP}-\mathsf{complete}$.

${\mathsf{3SAT}}_{aug}$ is in $\mathsf{P}$: $\mbox{  }$ Follows from hypothesis of $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$.

So why then is still $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?

Assume $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$. Let $\Pi$ be a NP-complete problem, by assumption, this problem can be solved by some circuit family. It is true that the problem $\hat{\Pi}$ where the input is a pair consisting of input to $\Pi$ and a circuit making an appropriate computation, is in $\mathsf{P}$. However, from this fact you cannot conclude that the original problem $\Pi$ is in $\mathsf{P}$. To obtain a solution to $\Pi$ using $\hat{\Pi}$ you have to guess the circuit - and this is not a priori possible in $\mathsf{P}$. You could guess the circuit nondeterministically, but then the argument would prove that $\mathsf{NP} = \mathsf{NP}$. However, if you start with a $\Sigma_2$ set instead, it is possible to fix this reasoning and obtain $\Sigma_2=\Pi_2$ (Karp-Lipton theorem).


Have any natural complexity classes been proven not to be closed under complement? Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be?

I'm sure one could construct some contrived example, but is there any "natural" complexity class that has this property, by which I mean one that has been studied by theoretical computer scientist for reasons other than its lack of closure under complement?

I know that RE has been proven not to be closed under complement, but I don't know of any examples from complexity theory rather than computability theory - i.e. any classes defined in terms of some kind of resource-constrained Turing machine.

There may be no such natural class, i.e. all natural classes are closed under complement.

Despite that $\mathrm{DTIME(n)\neq NTIME(n)}$ was proven, it is still possible that $\mathrm{NTIME(n^k)=co-NTIME(n^k)}$ for all natural number $k\geq1$.

For other kinds of model,we can similarly say that it is still possible:
$$\mathrm{RTIME(n^k)=co-RTIME(n^k)=ZPTIME_{\geq\frac12}(n)}$$ for all $k\geq1$.

Also, $\mathrm{UP=co-UP}$, etc.

And more importantly, all of these could SIMULTANEOUSLY hold if $\mathrm{L=CH}$ or $\mathrm{P=PP=CH}$ without violating any known complexity result.


Understanding Return Oriented Programming on Harvard Architecture I'm currently reading this paper: Code injection attacks on Harvard-architecture devices (ACM) (pdf)

I understand the basics of what the attack is trying to do, but one thing really bothers me.  If Harvard Architecture is supposed to have a strict separation of code and data, how is the initial buffer overflow allowing the attacker to rewrite return addresses on the stack?  Since the architecture only allows data to be read into instruction memory via the SPM instruction--one that is specially reserved--I just don't get where the ability to rewrite the ret pointers is coming from.  I feel like I'm missing something obvious.

I believe the architecture you're interested in - the AVR - is actually a modified Harvard architecture, whereby instruction memory can be accessed by instructions as if it were data.  (I haven't used the AVR in a while, so I don't recall if you can execute instructions out of RAM.)

The ARM Cortex M processors (perhaps others) are similar.  There aren't too many pure Harvard architectures in new designs these days.

By the way (since you tagged your question with "atmega"), there is a good paper by Francillon and Castelluccia (PDF from ACM Proceedings) regarding code injection attacks on (modified) Harvard architecture devices, including the AVR.


Cost of break statement i am trying find the Cost of an algorithm. it contains break statements. is there any cost of break and Continue statement in a Algorithm?

Depends on how close you want to look.

On face value, break, continue, etc. are implemented by unconditional jumps, which are (under most RAM-/CPU-like models) primitive instructions of the machine. So they certainly have some constant cost; $O(1)$ is a valid bound.

That's not very interesting, though: all primitive instructions have constant cost. If you want to answer questions like, "can I speed up my algorithm by adding/removing break/continue?", the situation becomes more involved.

The true cost of jumps depends on many factors, e.g.

the type of pipeline the CPU uses,
which type of speculative execution happens (if any),

and so on. My guess is that an unconditional jump -- other than conditional jumps -- should behave well in many regards. They are most certainly cheaper than completing the loop would be.

If the true cost matters to you, I recommend you benchmark the alternatives at hand. Be aware that the effect you're trying to measure may be smaller than the noise introduced by benchmarking, and you may have to account for that.


Finite list induction principle and the tail eliminator In Dybjer's Inductive Families the author present a method to derive an eliminator/induction principle for every inductive family of types.

In particular for the type of finite lists, namely
$$List' \colon (A \colon set) (n \colon N) set$$
we get the eliminator
$$\begin{align*}
listrec' \colon &(A \colon set)\\
& (C \colon (a \colon N)(c \colon List'_A n)set) \\
& (e_1 \colon C(0,nil'_A)\\
& (e_2 \colon (b_1  \colon N)(b_2 \colon A)(u \colon List'_A(b_1))(v \colon C(b_1,u))C(s(b_1),cons'_A(b_1,b_2,u)))\\
& (a \colon N) \\
& (c \colon List'_A(a)) \\
& C(a,c)\ .
\end{align*}$$

From what I get from this eliminator we should be able to provide any possible operation using finite lists.

Now my question is

  how do we get the classical destructor $$tail \colon (A \colon set)(n \colon N)(List'_A(s(n))) List'_A n$$
  that from any finite list gets its tail?

I am totally lost on how to approach this problem since the eliminator seems to be able to provide just function defined on the whole family $List'_A(n)$ and not on the sub-family $List'_A(s(n))$.

Thanks in advance.

I am totally lost on how to approach this problem since the eliminator seems to be able to provide just function defined on the whole family List′A(n) and not on the sub-family List′A(s(n)).

The typical trick in this situation is to pick a C such that you can pretend you are defining a function on the whole family when, in fact, you're only focusing on the sub-family you care about thanks to equality constraints.

Let me be more concrete:

If you pick C(n, xs) = (m:N) -> n = s(m) -> List'_A(m) then you can define a generalised gtail by using listrec', and derive tail as a corollary.

gtail : (A:set) (n:N) (xs : List'_A(n)) -> C(n, xs)
gtail A = listrec' A C
          contradiction -- of type: (m:N) -> 0 = s(m) -> List'_A(m)
          (\ _ _ u _ -> u)

tail : (A:set) (n:N) -> List′A (s(n)) -> List′An
tail A n xs = gtailn A (s(n)) xs n refl


Is this a hypergraph? Here is the problem is want to solve:

I want to connect nodes with directed labelled edges, but this two nodes are potentially themselves graphs, hypergraphs or the current structure I don't have a name for.

Here is a simple example with a graph $(v_1,e_1,v_2)$ where nodes $v_1$ and $v_2$ are connected by $e_1$. I want to have the following structure:
$((v_1,e_1,v_2),e_2,(v_3,e_3,v_4))$

in this case, the $v_i$ hold a single value (i.e. classical graph nodes)

What I don't know is:

What is the name of such a structure ?
If it's a well known data structure, are there some efficient implementations ?

No, this isn't a hypergraph.  I don't think it has a standard "name".  Call it whatever you like: as long as you define your terms clearly, you should be fine.

Yes, you can implement this efficiently using any standard data structure for representing graphs: e.g., adjacency lists.  Each node of the "outer" graph will contain a pointer to a data structure that describes the "inner" graph it represents.


Language whose intersection with a CFL is always a CFL Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L \cap L_0$ is context-free, then $L$ is regular.

I haven't managed to prove this, but I'm pretty sure there is no counterexample.

Let $L = \{a^n b^n : n \geq 0\}$, and let $L_0$ be an arbitrary context-free language. Define $L_1 = L_0 \cap a^* b^*$, and note that $L_1$ is context-free and $L \cap L_0 = L \cap L_1$. Let $S = \{(i,j) : a^i b^j \in L_1\}$.

According to Parikh's theorem, the set  $S$ is semilinear. The set $D = \{(n,n) \geq 0\}$ is also semilinear (in fact, it is linear). Since the semilinear sets are closed under intersection, $S \cap D$ is also semilinear. Since $S \cap D$ is (essentially) one-dimensional, it is eventually periodic. This shows that there is a finite language $F$, a modulus $m \geq 1$ and a subset $A \subseteq \{0,\ldots,m-1\}$ such that
$$
L \cap L_1 = F \Delta \{ a^n b^n : n \bmod m \in A \},
$$
where $\Delta$ is symmetric difference. It is easy to check that $\{a^nb^n : n \bmod m \in A\}$ is context-free, and so $L \cap L_1$ is context-free.

Summarizing, we have shown that $L$ is a non-regular language which satisfies your condition.


Manipulating Intersection of oracles Suppose for different classes $A,B,C$ we have that $A\subseteq P^B$ and $A\subseteq P^C$.

We have $A\subseteq P^{B}\cap P^{C}$. Does it also mean $A\subseteq P^{B\cap C}$?
Supposing $A\subseteq P^{B\cap C}$ also holds does it also give $A\subseteq {B\cap C}$?
If $P^B=B$ then does it mean $A\subseteq {B\cap C}$ or $A\subseteq B\cap P^C$?
If $B\subseteq P^{B\cap C}$ then does it mean $A\subseteq {B\cap C}$ or $A\subseteq B\cap P^C$?

Do we know anything else about intersection of oracles?

The answer to all of those questions is no, and not for some especially deep reason, as most of these can be ruled out by forcing the intersection to be simple enough.

Suppose $B$ contains all languages with only even length words, and $C$ contains all languages with odd length words. Clearly $B\cap C =\emptyset$, so $\mathsf{P^{B\cap C}=P}$, but $P^B, P^C$ both contain undecidable problems. This example rules out $1,2$.

To rule out $3$ you can set $\mathsf{B=EXP}$ and $C=\emptyset$. Choosing $B=\emptyset$ rules out $4$. Not allowing the empty set won't change much, as we can always do the same tricks with finite languages (or simple infinite langauges), so it is probably not possible to claim anything interesting in the general case.


Use or Importance of $\Rightarrow^*$ operator Particularly, there are 2 variants of $\Rightarrow$, one is $\Rightarrow^*$ and another is $\Rightarrow^+$ which are used in derivation of strings using the productions of the grammar.

As stated here, when $\Rightarrow^*$ is used, it means derive in 0 or more steps and when $\Rightarrow^+$ is used, it means derive in 1 or more steps.

What I don't understand is what is the use or importance of $\Rightarrow^*$ operator?. It just replaces the head of the production with the head itself.
Is it that the $\Rightarrow^*$ operator is just there to define operators in some standard way or it actually differs in the way it is used as compared to $\Rightarrow^+$?

Also, while deriving strings, to skip some obivious steps(like replacing multiple non-terminals in a string with their respective terminals), should I use $\Rightarrow^*$ or $\Rightarrow^+$?

It is false that $\Rightarrow^*$ " just replaces the head of the production with the head itself". $A \Rightarrow^* B$ means that the sentential form $B$ can be obtained from the sentimental form $A$ by applying any number of productions (which might be $0$ or more than $0$).

For example if your grammar is $S \to a$, then all of the following are true  $S \Rightarrow^* S$, $S \Rightarrow^* a$, and $S \Rightarrow^+ a$, while it is false that $S \Rightarrow^+ S$.

If you are deriving strings and applying at least one production per step then both $\Rightarrow^*$ and $\Rightarrow^+$ are correct. The latter is more specific since it implies the former (but not vice-versa).


Proving a binary tree has at most $\lceil n/2 \rceil$ leaves I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction?

For people who were following in the original question about heaps, it has been moved here.

I assume now that the question is the following:

  Given a binary tree with $n$ nodes, prove that it contains at most $\left\lceil \frac{n}{2} \right\rceil$ leaves.

Let us work with the tree definition $\mathrm{Tree}= \mathrm{Empty}\mid \mathrm{Leaf} \mid  \mathrm{Node}(\mathrm{Tree},\mathrm{Tree})$. For $T$ such a tree, let $n_T$ the number of nodes in $T$ and $l_T$ the number of leaves in $T$.

You are correct to do this by induction, but you will need structural induction that follows the tree structure. For trees, this is often done as complete induction over the height $h(T)$ of the trees.

The induction anchor has two parts. First, for $h(t)=0$ we have $T=\mathrm{Empty}$ with $l_T=n_T=0$; the claim clearly holds for the empty tree. For $h(t)=1$, i.e. $T = \mathrm{Leaf}$, we similarly have $l_T=1=\left\lceil \frac{n_T}{2} \right\rceil$, so the claim holds for leaves.

The induction hypothesis is: Assume that the claim holds for all (binary) trees $T$ with $h(T)\leq k$, $k\geq 1$ arbitrary but fixed.

For the inductive step, consider an arbitrary binary tree $T$ with $h(T)=k+1$. As $k\geq 1$, $T=\mathrm{Node}(L,R)$ and $n_T = n_L+ n_R+1$. As $L$ and $R$ are also binary trees (otherwise $T$ would not be) and $h(L),h(R)\leq k$, the induction hypothesis applies and have

$\qquad \displaystyle l_L \leq \left\lceil \frac{n_L}{2} \right\rceil \text{ and } l_R \leq \left\lceil \frac{n_R}{2} \right\rceil.$

As all leaves of $T$ are either in $L$ or $R$, we have that

$\qquad \begin{align*}
  l_T &= l_L + l_R \\
      &\leq \left\lceil \frac{n_L}{2} \right\rceil + \left\lceil \frac{n_R}{2} \right\rceil \\
      &\leq \left\lceil \frac{n_L + n_R + 1}{2} \right\rceil \qquad (*)\\
      &= \left\lceil \frac{n_T}{2} \right\rceil
\end{align*}$

The inequality marked with $(*)$ can be checked by (four way) case distinction over whether $n_L,n_R\in 2\mathbb{N}$. By the power of induction, this concludes the proof.

As an exercise, you can use the same technique to prove the following statements:

Every perfect binary tree of height $h$ has $2^h-1$ nodes.
Every full binary tree has an odd number of nodes.


How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications? In Strassen's matrix multiplication, we state one strange ( at least to me) fact that matrix multiplication of two 2 x 2 takes 7 multiplication.

Question : How to prove that it is impossible to multiply two 2 x 2 matrices in 6 multiplications?

Please note that matrices are over integers.

This is a classical result of Winograd: On multiplication of 2x2 matrices.

Strassen showed that the exponent of matrix multiplication is the same as the exponent of the tensor rank of matrix multiplication tensors: the algebraic complexity of $n\times n$ matrix multiplication is $O(n^\alpha)$ iff the tensor rank of $\langle n,n,n \rangle$ (the matrix multiplication tensor corresponding to the multiplication of two $n\times n$ matrices) is $O(n^\alpha)$. Strassen's algorithm uses the easy direction to deduce an $O(n^{\log_27})$ from the upper bound $R(\langle 2,2,2 \rangle) \leq 7$.

Winograd's result implies that $R(\langle 2,2,2 \rangle)=7$. Landsberg showed that the border rank of $\langle 2,2,2 \rangle$ is also 7, and Bläser et al. recently extended that to support rank and border support rank. Border rank and support rank are weaker (=smaller) notions of rank that have been used (in the case of border rank) or proposed (in the case of support rank) in the fast matrix multiplication algorithms.


Describing time complexity when internally using a function of unknown complexity Assume that I have some functions $f$ and $g$, both implemented perfectly, where

$$
f(x, g(z)) = \sum_{k=0}^{k=\lfloor{x}\rfloor}g(k)\quad (x > 1)\,.
$$

Function $g$ is of unknown definition. I would like to express the time complexity of $f$ in big-O notation. My initial thought was to do something similar to:

$$
O(\sum_{k=0}^{k=\lfloor{x}\rfloor}T_g(k))\,.
$$

Assume $T_g$ represents the time function of function g. However, this representation feels inadequate and irreducible for asymptotic time complexity; there should be a better way to express $T_f$.

How do I describe, in big-O notation, the time complexity of $f$?

In complete generality there is nothing much you can say. However, in many circumstances it will be the case that $g(n)$ is monotone, and in that case you can say that
$$
\sum_{k=1}^n g(k) \leq ng(n),
$$
a bound which is often quite good.


How exactly is this equation for insertion sort time complexity solved so that it shows it is linear? Background

I am currently taking an Algorithm and Analysis course and doing some extra studying on my own from the text book. This is not a homework question or exercise even. I am just trying to understand completely how the authors are doing the combining of terms in the time/cost equation for Insertion-Sort.

I understand what is being shown up until we get to the actual equation. I understand that each line, barring the comment which is considered to not have a cost, has a constant cost c.

This is how they have broken down the time/cost for the algorithm in psuedo-code:

for j = 2 to A.length
    key = A[j]
//Insert A[j] into the sorted
     sequence A[1..j - 1]
i  = j - 1
while i > 0 and A[i] > key
    A[i + 1] = A[i]
    i = i - 1
A[i + 1] = key

Here's the cost/time for each line according to textbook:

$c_1n$
$c_2(n-1)$
0
0
$c_4(n - 1)$
$c_5 =\sum\nolimits_{j}^{n} 2t$
$c_6=\sum\nolimits_{j}^{n} 2{t - 1}$
$c_7=\sum\nolimits_{j}^{n} =2{t - 1}$
$c_8(n - 1)$

The best case run time of the algorithm is then given by:

  $$
T(n) = \ c_1(n) + c_2(n - 1) + c_4(n - 1) + c_5(n - 1) + c_8(n - 1)
$$

This is where I get confused. Somehow they combine all of these terms to simplify the equation but it's done in one step so I can not follow/reproduce it on my own. This is what they come up with:

  $$
  = (c_1 + c_2 + c_4 + c_5 + c_8)n - (c_2 + c_4 + c_5 + c_8)
$$

According to the author it can be expressed as $an + b$ and thus a linear function of $n$. As mentioned above, I don't know how they simplified the equation nor how it can be expressed as $an + b$. I do understand that it is in linear equation form. How do I make the leap or bridge the gap per say?

So you question is how to go from:

T(n)= c1(n)+c2(n−1)+c4(n−1)+c5(n−1)+c8(n−1)

to

T(n)= (c1+c2+c4+c5+c8)n−(c2+c4+c5+c8)

Step 1 (Expand the statement):

T(n)= c1(n)+c2(n)−c2+c4(n)−c4+c5(n)−c5+c8(n)−c8

Step 2 (Group similar elements):

T(n)= c1(n)+c2(n)+c4(n)+c5(n)+c8(n)−c2-c4-c5-c8

Step 3 (Find the factors):

T(n)= (c1+c2+c4+c5+c8)n−(c2+c4+c5+c8)


A* algorithm example explained I am trying to understand A star algorithm. I am aware that it follows the sum of the current cost and heuristic, therefore f(n) = c(n) + h(n) in order to expand a new node. So every time the code with the smallest f(n) from the root is expanded. However, I am confused about the backtracking of the algorithm when it does not find the best solution. I tried to follow the example explained here. Therefore, by only using the f(n) the algorithm should have expanded: S-B-C-G. Firstly B then C and then G. Then declare that find a solution. How, the backtracking works?

The example is as follows:

In the left, there is the graph and in the table is the heuristic cost. What is going to be the a star expand in this graph?

A* doesn't backtrack. It just keeps expanding the node with the least value of $f$ until it finds a solution. The properties of the heuristic used guarantee that the first solution found is optimal.


Binary Equivalent vs. Computer code(Ascii or UTF) Does computer convert every stuff using Ascii or UTF?
Meaning if there is a mathematical calculation including 65 (as a number) will it convert it into binary (00100001)?
And then how it differentiate it with 'A', whose code point is also 65 with code 00100001?

I am not an expert in the field, but I can try to give an approximately correct answer.

Reading from memory itself, you can not diferentiate between lets say ints and characters.
The compiled program is compiled with locations of where to find the operator that is needed, in this case print for ints and for chars. You must specify how to represent that data in your print command.

Example in c:

printf("ASCII value = %d, Character = %c\n", ch , ch );

This code will first represent data at location ch as a number and than as a char.

Let me give another example:
Let us say that your language can "add" strings, in form of concatenating one onto another. How can computer know which "add" to use, if you cannot learn of data type from memory? The compiler compiled the program with address to the appropriate "add" command, according to data type you specified your operands to be.

Moral of the story: you cannot learn of data type from memory.
Hopefully this clears it out.


Time complexity of a function with while loop What is the time complexity of the following procedure?
for $x \in \{1,\ldots,n\}$:
$\quad$ $i \gets \lfloor n/2 \rfloor$
$\quad$ while $i \neq x$:
$\quad\quad$ if $i > x$ then $i \gets i -1$, otherwise $i \gets i + 1$.
According to me, the time complexity is $O(n^2)$.
The inner while loop starts at $n/2$ and moves towards the value of $x$, worst case it runs $n/2$ times, and best case it runs $0$ times.

What is the exact time complexity of this procedure?


How long does the Collatz recursion run? I have the following Python code.

def collatz(n):
    if n <= 1:
        return True
    elif (n%2==0):
        return collatz(n/2)
    else:
        return collatz(3*n+1)

What is the running-time of this algorithm?

Try:

If $T(n)$ denotes the running time of the function collatz(n). Then I think I have
\begin{cases}
T(n)=1 \text{ for } n\le 1\\
T(n)=T(n/2) \text{ for } n\text{ even}\\
T(n)=T(3n+1) \text{ for } n\text{ odd}\\
\end{cases}

I think $T(n)$ will be $\lg n$ if $n$ is even but how to calculate the recurrence in general?

This is Collatz conjecture - still open problem.
Conjecture is about proof that this sequence stops for any input, since this is unresolved, we do not know how to solve this runtime recurrence relation, moreover it may not halt at all - so until proven, the running time is unknown and may be $\infty$.


Complexity of two-party maximum Given function $\max\colon \{0, 1\}^{n} \times \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$ that returns the maximum of two binary $n$-vectors (interpreted as encoding numbers in the range $0,\ldots,2^n-1$), find a communication protocol for two parties having vectors $x$ and $y$ such that both parties will get the vector $\max(x, y)$.
It's easy to get trivial bounds for the complexity of any protocol for maximum: $n \leq \texttt{CC}(\max) \leq 2n$, but how can we use only $\frac{3n}{2} + c$ bits for some constant $c$?

Write $x = (x_h,x_l)$ and $y = (y_h,y_l)$, where $x_h,y_h$ are the high-order parts.
Alice sends $x_h$ to Bob ($n/2$ bits). Bob sends Alice two bits, indicating which of the following holds: $x_h > y_h$, $x_h = y_h$, $x_h < y_h$. The protocol then proceeds as follows:

If $x_h > y_h$, then Alice sends Bob $x_l$ ($n/2$ bits).
If $x_h < y_h$, then Bob sends Alice $y$ ($n$ bits).
If $x_h = y_h$, then Alice sends Bob $x_l$, and Bob sends Alice $y_l$ ($n$ bits).

In total, at most $\frac{3}{2}n+2$ bits are sent (assuming $n$ is even).


Turing-completeness of Goto language with limited constants This is taken from an old exam of my university that I am using to prepare myself for the coming exam:
Given is a language $\text{Goto}_{17} \subseteq \text{Goto}$. This language includes exactly those $\text{Goto}$ programs in which no constant is ever greater than $17$. Show that every $\text{Goto}$ program can be simulated by a $\text{Goto}_{17}$ program.
$Goto$ here describes the set of all programs written in the $Goto$ language made up of the following elements:
With variables $v_i \in \mathbb{N}$ and constants $c \in \mathbb{N}$
Assignment: $x_i := c, x_i := x_i \pm c$
Conditional Jump: if(Comparison) goto $L_i$
Haltcommand: halt
It seems obvious to me that this would not limit the power of a program, as there are easy ways to just repeat operations to achieve the same thing with limited constants. To add or subtract arbitrary values we can just add or subtract repeatedly. To compare, we can put our value to compare with into a dummy variable and compare, reduce, repeat until we know the value. These dummy variables are guaranteed to be unused and free for this use if we simply map the variables from our Goto program so that any variable $v_i$ from the Goto language maps onto $v_{2i}$ in our new language.
How can the equivalence in power between these to languages be shown? Is a compiler from one to the other the best solution, or are there more elegant ways? Specifically showing how comparisons work seems like it would be rather complicated and this is a question that originally appeared in a written exam with only a few minutes to answer this question if you average it out. If there is no better way, how would an approach to converting the following Goto program into a limited Goto program of this kind look?
v = 99
repeat: v = v + 1
if(v = 100)goto repeat
halt

No, that is not a proof.  "It seems obvious to me" is not a proof.
To obtain a formal proof, describe an algorithm that, given a Goto program $P$, outputs a Goto$_{17}$ program $P'$, and prove that $P'$ simulates $P$.  Basically, you need to construct a compiler that compiles from Goto to Goto$_{17}$, and then prove it correct.


Can an algorithm complexity be lower than its tight low bound / higher than its tight high bound? The worst case time complexity of a given algorithm is $\theta(n^3logn)$.
Is it possible that the worst time complexity is $\Omega(n^2)$?
Is it possible that the worst time complexity is $O(n^4)$?
The average time complexity is $O(n^4)$?
IMO it is possible as long as you control the constant $c$, but then what's the point of mentioning any other bound than the tight bounds?

If $T(n) = \Theta(n^3\log n)$ then it is always the case that $T(n) = \Omega(n^2)$ and $T(n) = O(n^4)$.
If $T(n)$ is the worst-case complexity of an algorithm, then furthermore its average-case complexity is $O(n^4)$, always.


Is every language in PTime also context-sensitive? Context-sensitive languages are exactly those that can be recognised using linearly bounded automata, i.e., those in NSPACE(O($n$)). This subsumes all languages that can be recognised in linear time, i.e., DTIME(O($n$)), since you can only use n memory cells in n steps.

However, this leaves open the possibility that some super-linear polynomial time problems are not context-sensitive. Is this likely or even known? Are there examples?

Here are some general facts that one should be aware of:

There are PSpace-complete problems in NSPACE(O($n$)), e.g., TrueQBF. One might think that this answers my question, since PTime is contained in PSpace.
However, not all PSpace-complete problems are in NSPACE(O($n$)). Indeed, we know that there are strictly more languages in NSPACE(O($n^2$)) than in NSPACE(O($n$)) (space-hierarchy theorem). In other words, PSpace is strictly larger than NSPACE(O($n$)), i.e., some PSpace languages are not context-sensitive.
PTime is subsumed by PSpace, but not necessarily by NSPACE(O(n)) (hence my question). Indeed, it seems unlikely that today's answer to my question is "All PTime languages are context-sensitive." If we would know this for sure, then (using 2.) we would know that PTime is strictly smaller than PSpace, which is an open conjecture today.

However, I don't see an immediate reason why there should not be a known example of a non-context-sensitive language in PTime.

Conclusion after reading the answer: We know very little. Mostly, we know $NL\subseteq NSPACE(O(n))\subseteq PSpace$ and $NL\subseteq P\subseteq NP\subseteq PSpace$. It is unclear how $NSPACE(O(n))$ (CSL) compares to $P$ and $NP$. If we could show that $P\subseteq NSPACE(O(n))$, this would show $P\subsetneq PSpace$ (open); if we could show $P\not\subseteq NSPACE(O(n))$, then this would show $NL\subsetneq P$ (open). Both of these open conjectures are expected to be true, which is not of any help for making a guess regarding the answer to my question.

It is an open question to separate $\mathsf{L}$ (that is, $\mathsf{DSPACE}(\log n)$) and $\mathsf{P}$ (what you call PTime), so in particular we have no example of a polytime language which requires superlogarithmic space.


Converting a 2-SAT formula into an implication graph Both wikipedia and my lecturer explained how the 2 satisfiability problem work. However, I am finding it really hard understanding how this formula:

xvy≡ ¬x-->y ≡ ¬y -->x

Then breaks down the following conjectures :

(¬x v y) & (¬y v z) & (¬z v w) & (¬w v ¬x) &
(x v ¬y) & (y v ¬z) & (z v ¬w) & (w v x)

is converted to an implcation graph.

Heres my attempt:

 (¬x v y) = (¬y-->x)

          = (¬x-->y)

but this cannot be right, as they have diffrent truth tables:

(¬y-->x)

1 0 0 0

1 0   1  1

0 1   1   0

0 1   1   1

(¬ x-->y)

1 0 0 0

0 1 1 1

1 0 0 0

0 1 1 1

I understand once you have the conjectures converted to implication, how to construct the implication graph and find out if its not satisfiable (bad loops).

Could someone please explain clearly how to break down the conjectures to implications?

(¬x v y) = (¬y-->x)

$$\begin{align}
\text{rule: } &A \vee B &=& (\neg A \implies B)\\
& \neg x \vee y &=& (\neg\neg x \implies y)\\
& &=& (x \implies y) &(1)\\
\end{align}
$$

          = (¬x-->y)

So now this becomes:

$$\begin{align}
\text{rule: } &A \implies B &=& (\neg B \implies \neg A)\\
&(x \implies y) &=& (\neg y \implies \neg x) & (2)
\end{align}
$$

And we get:

$$\begin{align}
(x \implies y) & (1)\\
(\neg y \implies \neg x) & (2)
\end{align}
$$

And the truth table:

$$
  \left.\begin{array}{rrrr}
    x & y & (\neg x \vee y) & (x \implies y) & (\neg y \implies \neg x) \\
    0 & 0 &               1 &             1  &                   1 \\
    0 & 1 &               1 &             1  &                   1 \\
    1 & 0 &               0 &             0  &                   0 \\
    1 & 1 &               1 &             1  &                   1 \\
  \end{array}\right.
$$

As you can see they are equivalent.


NFA automata with ϵ moves proof How can I prove that for every NFA with $\epsilon$ moves if $q_0 \in F$ then $\epsilon \in L(A)$? I can't think of any technique since it seems so trivial.

Use the definition of $L(A)$.

There are several different ones, so let me illustrate with the definition I know. We define a function $\hat\delta$ inductively so that $\hat\delta(q_0,w)$ is the set of all states reachable from $q_0$ by reading the word $w$. We then define $L(A)$ as the set of words $w$ such that $\hat\delta(q_0,w)$ intersects $F$.

Given this definition, we argue as follows. First, the definition of $\hat\delta$ (which I haven't specified) easily implies that $q_0 \in \hat\delta(q_0,\epsilon)$. Since $q_0 \in F$, it follows that $\hat\delta(q_0,\epsilon)$ intersects $F$, and so $\epsilon \in L(A)$.


Maximizing a convex function with a linear constraint $$\text{maximize  } f(\mathbf{x}) \quad\text{subject to  } \mathbf{Ax} = \mathbf{b}$$

where

$$f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{\left(\sum_{i=1}^{N}x_i^2\right)^2}},$$

$\mathbf{x} = [x_1,x_2,...,x_N]^T \in \mathbb{R}^{N\times 1}$ and $\mathbf{A} \in \mathbb{R}^{M\times N}$.

We can see that $f$ is convex and of the form $\sqrt{1+y^2}$. It can be also shown that $f$ is bounded in $[\sqrt{2}, 2]$. I know that a convex maximization problem is NP-hard, in general.

However, using the specific nature of the problem, is it possible to solve it using any standard convex optimization software/package?

Yes, Convex Optimization with equality constraint is NP-Hard in general. However, there exist mature techniques that find very nice approximate solutions to convex optimization problems, like Coordinate Descent.

Suppose you use coordinate descent and the matrix A has rank $k$. You can fix n-k-1 coordinates of your feasible solution $x = (x_1, x_2, x_3, ..., x_n)$ and then the solution vectors in the solution space are uniquely determined by one coordinate, for example $x_i$. In that case, you can just take the derivative of $f(\cdot)$ with respect to $x_i$ to find the maximum in this iteration.

Then we iteratively fix n-k-1 coordinate and improve the solution until a approximately optimal one is found.


Big O notation for recursive algorithm In order to find Big O for a recursive algorithm, it is needed to know the stopping criteria of that algorithm. For the recursive algorithm to find Factorial of a number it is very easy to find the stopping criteria.

int fact(int n)
{
    if((n==1)||(n==0)) return 1;
    else retrun n*fact(n-1);
}

And we can make a mathematical definition of this problem as follow:

$
fact(n)=
\begin{cases}
1,& \text{if } n = 1 \vee n=0\\
n*fact(n-1), &{otherwise}
\end{cases} \tag{1}
$

Now my question is how is the correct mathematical definition for this algorithm:

void func(int n)
{
    if(n>0)
    {
        func(n-1);
    }
    else
    {
        print(n)
    }
}

Also, for the same algorithm if I change it as follow what is the stopping criteria and the mathematical definition of it?

int n = 5;
int rnd; // Random number between 0 and n
void func(n)
{
    if(n>rnd)
    {
        func(n-1);
    }
    else
    {
        print(n)
    }
}

Now the stopping criteria is random? So how can I define this in order to find Big O?

Each recursive function should have some initial values to stop the computation. For the last two recursive functions, the program will not be stopped and trapped in an infinite loop or it has no meaning (for case 2, what is the value of $f(1)$?). Also, for the last case, if we have a random initial value, we can compute the complexity in average:
$$\frac{1}{n}(n + (n-1) +\cdots+1)=O(n)$$
As Probability of each random value between $1$ to $n$ is $\frac{1}{n}$, the average complexity is $O(n)$, as shown in the above.


array median transformation using the min number of steps Let $A[1...N]$ be an Array of size $N$ with maximum element $\max$.

I want to transform array $A$ such that after transformations all elements of $A$ contain $\max$, i.e. after transformation $A = [\max,\max,\max,\max,\dots,\max]$.

In one step, I can apply the following operation to any consecutive sub-array $A[x..y]$:

  Assign to all $A[i]$ with $x \leq i \leq y$ the median of subarray $A[x..y]$.

We consider as median always the $\left\lceil \frac{n+1}{2} \right\rceil$-th element in an increasingly sorted version of $A$.

What is the minimum number of steps needed to transform $A$ as desired? If it helps, assume that $N\leq 30$.

Example 1:

Let $A = [1, 2, 3]$. We need to change it to $[3, 3, 3]$. The  minium number of steps is two, first for subarray $A[2..3]$ (after that $A$ equals to $[1, 3, 3]$), then operation to $A[1..3]$.

Example 2:

$A=[2,1,1,2]$.The  min step is  two. The median of subarray $A[1..4]$ is $2$ (3rd element in $[1,1,2,2]$. Apply the operation to $A[1..4]$ once and we get $[2,2,2,2]$.

In the comments, Wu Yin claimed an upper bound of $\lceil \log_2 n \rceil$, although I think this is only true if the position of the maximum is known. In fact, consider the following argument. Assume $A$ is filled with $N-1$ ones and one maximal element $\max$. Any first step on a subarray $A[x,y]$ of more than 2 elements will necessarily set the subarray to all $1$'s. In particular, if we don't know the position of $\max$, we can only apply a step to subarrays of length 2, or otherwise we run the risk of "destroying" our maximum element. Hence, without knowing the position of our maximimal element, we can only probe the array by consecutively applying the operation to $A[i,i+1]$ for all $i$. This will necessarily create a subarray of length 2 that is filled with $\max$. Recurring leads to a linear time algorithm, which I think is optimal.

Algorithm:

Let $step(x,y)$ denote an operation on the subarray $A[x,y]$ as is defined in the question.

Perform $step(i,i+1)$ for all $0\leq i < N$. After that, there is some 2-length subarray containing only $\max$.
Perform $step(i,i+3)$ for all $0\leq i < N-3$. After that, there is some 4-length subarray filled with $\max$.
Generally, we double in each such iteration the array size in each step. After that, the original array $A$ contains only $\max$.

Running Time:

In the first iteration, we perform $N/2$ steps, in the subsequent one, $N/4$, then $N/8$, etc. The sum over all this is smaller than $N$. I think this is optimal, since without looking at all elements (or at least $N/2$ elements), we don't know where $\max$ is, and can not use any step on any subarray larger than $2$.


Paint graph ordered vertices I have the following question:
Given graph $G=(V,E)$ with given order on its vertices, I mean $v_1<v_2<...<v_n$ I need to find minimal colors ordered paining of the graph vertices s.t neighbor vertices don't have the same color, I mean:
$(v_1,v_2,...,v_j)$ - painted in fist color and non of them are neighbors.
$(v_{j+1},...,v_l)$ - painted in second color and non of them are neighbors. and so on.

The complexity needs to be $O(V+E)$. Anyone have an idea?

If understand the question correctly you want to find a $k$-coloring of the given graph, given an ordered list of the vertex such that vertex with the same colors are consecutive in this list.

If that is the case then this problem can be solved greedy.

We should only find maximal independent sets which are contiguous segments in your list starting from the beginning. Start with an empty set. Go for every vertex in the ordered list, if the vertex is not connected to any other node in the set, include it. Otherwise, paint all vertex in the set with the same color, notice they form a consecutive interval in the list, then clear the list and include the current node you are processing. At the end you should paint all nodes remaining in the list with the same color.

Rationale

We should partition the list in minimum amount of intervals such that all vertex within the same interval are not connected to any other vertex (they are an independent set). Since the first vertex in the list belong to an interval, this interval should start at this vertex. The proposed algorithm will find maximal interval containing this vertex. It is impossible to find any bigger interval containing the first vertex (since the one chosen is maximal) and it doesn't make any sense to find any smaller interval, since not taken vertex will only increase our restrictions in the future while taking next intervals.

Pseudocode

Graph := Relations between vertex. Graph[u] is the list of all neighbors of u
List := Order of vertex. List[1] = v1, List[2] = v2, etc...

S := {} (Set with all nodes in the interval we are keeping)
color := 0 (Number of colors used so far)

# Iterate through all vertex
for vertex in List:

   # Check this node is not connected to any other node in S
   ok := True
   for neig in Graph[vertex]:
      if neig in S:
          ok := False
          break

   if ok:
       # If vertex is not neighbor of any other vertex in S, include it in.
       S.add(vertex)
   else:

       # Paint all vertex in S with color
       paint(S, color)

       # Increase color, since an interval of nodes was painted
       color += 1

       # Reset S, starting with current node.
       S := {vertex}

# Don't forget to paint last interval

# Paint all vertex in S with color
paint(S, color)

# Increase color, since an interval of nodes was painted
color += 1

Complexity and details

Notice in the implementation you don't need to maintain the set of taken nodes S explicitly, since all nodes in that set belong to an interval they can be easily represented with two pointer (the begin of the interval and the end of the interval). The overall complexity of this solution is $O(|V| + |E|)$, since every node is visited once in the first loop, and edges are traversed twice, one per endpoint. Regarding paint function, it is potentially linear in the number of vertex it is painting, but that is ok, since we paint each vertex exactly once.


Solving Recurrence Equations containing two Recursion Calls I am trying to find a $\Theta$ bound for the following recurrence equation:

$$ T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42 $$

I figure Master Theorem is inappropriate due to differing amount of subproblems and divisions. Also recursion trees do not work since there is no $T(1)$ or rather $T(0)$.

Yes, recursion trees do still work!  It doesn't matter at all whether the base case occurs at $T(0)$ or $T(1)$ or $T(2)$ or even $T(10^{100})$.  It also doesn't matter what the actual value of the base case is; whatever that value is, it's a constant.

Seen through big-Theta glasses, the recurrence is $T(n) = 2T(n/2)+T(n/3)+n^2$.

The root of the recursion tree has value $n^2$.
The root has three children, with values $(n/2)^2$, $(n/2)^2$, and $(n/3)^2$.  Thus, the total value of all children is $(11/18) n^2$.
Sanity check:  The root has nine grandchildren: four with value $(n/4)^2$, four with value $(n/6)^2$, and one with value $(n/9)^2$.  The sum of those values is $(11/18)^2 n^2$.
An easy induction proof implies that for any integer $\ell\ge 0$, the $3^\ell$ nodes at level $\ell$ have total value $(11/18)^\ell n^2$.
The level sums form a descending geometric series, so only the largest term $\ell=0$ matters.
We conclude that $T(n) = \Theta(n^2)$.


Floating point number fractions excercise During my preparation for an exam, I've come across an exercise that was focused on precision calculation with floating point numbers. It goes like this:

  Consider the expression : $$\frac{1}{1-x}-\frac{1}{1+x}, x\neq \pm1$$
  For what range of values $x$ is it difficult to compute the expression accurately in foating-point arithmetic? Give a re-arrangement of the terms such that, for the range of values from part (a), the computation is more accurate in foating-point arithmetic.

I have some basics covered on floating point number systems, so I've tried to set $\pm x=0.9999...$, with a different number of decimal digits. The calculations are indeed more and more imprecise, however I don't know if this is the only problematic 'range'. Also, I have no idea how to transform this expression to be more accurate. I have tried $\frac{2x}{1-x^{2}}$ and $e^{\ln{2x}-\ln(1-x^{2})}$, but the results were pretty much the same.

Thanks for help!

Actually, floating point arithmetic according to the IEEE 754 standard will calculate 1-x exactly, without any rounding error, if 0.5 ≤ x ≤ 2.0. So for x close to 1, 1-x is calculated exactly, 1 / (1-x) is calculated accurately, and 1 / (1 + x) and the sum will be calculated accurately as well.

What you are likely observing is the rounding error when 0.999999 for example is converted to a floating point number. x will not be equal to 0.999999, but a bit off. And the function itself as a function of real numbers is very sensitive to changes in the argument. That also explains why re-arranging the function can't help, because the function is sensitive to the arguments, and the arguments are not what you think.

The same applies for x close to -1, since f(x) = f(-x).

You will actually have a problem if x is close to 0. 1 / (1-x) and 1 / (1+x) can both be calculated with a very small absolute error, the difference is calculated exactly because both have about the same size, but because the result is close to zero, the small absolute errors turn into a rather large relative error.

When x is close to zero, 1 / (1 - x) = 1 + x + x^2 + x^3 ..., and a / (1 + x) = 1 - x + x^2 - x^3 ..., the mathematical difference is 2x + 2x^3 + 2x^5 ... ≈ 2x.

Let u be the value of the last bit in a number 1 ≤ x < 2, then IEEE arithmetic has rounding errors up to u/2. 1 / (1 - u) ≥ 1 is calculated with an error up to u/2, 1 / (1 + u) has an error up to u/4. If you pick x^2 slightly larger than u/4, then 1 / (1 - x) is rounded to 1+x, 1 / (1 + x) is rounded to 1 - x + u/4, and the difference that is calculated is 2x - u/4, instead of 2x + x^3 + 2x^5 ..., so the absolute error is > u/4, and the relative error about $(u/4)^{1/2}$.

You can fix this easily by subtracting 1 from both sides, giving $x / (1 - x) + x / (1 + x)$.


k-Closest pairs in Delaunay triangulation Assume there is a set of points $S$ in $\mathbb{R^2}$.
In this set of points there is a pair of points which are the nearest neighbors, the second-nearest neighbors and the third-nearest neighbors.

I want to show that the pair of points which represent:

the nearest neighbors,
the second nearest neighbors,
the third nearest neigbors

are also an edge in the corresponding Delaunay Triangulation.

Any hints on how to prove this?

This article [1] shows that this is not always true for the second-nearest neighbour and forth.
It shows that it is indeed the case for the (1st) nearest neighbour, and it's trivial, given the theorem that claims that if the circle defined by 2 points (as its diameter) is empty of other points then these points lie on an edge of the delaunay triangulation.

I didn't find a proper proof for that, and it is definitely not true for the opposite direction (not every edge of the DT defines an empty circle), but I have an idea of why this is true -

Let the points a,b define a circle Cab, having a-b as its diameter, empty of other points. The circle is empty of points, but cannot be empty of edges (the line connecting any pair of points must either be an edge or intersect an edge (by convexity of the map, and the fact that there are no diagonals in triangles).
Suppose a-b is not an edge of the DT, then it intersects an edge c-d, with both c and d out of Cab, that is part of a triangle c-d-e that either has w.l.o.g e=a, or e != a and is also outside of Cab, but this doesn't matter.
Anyway, the angles $\angle acb$ and $\angle adb$  have to be both sharp, as they are supported by the diameter of Cab, a-b, and lie outside of it, so this means $\angle cad + \angle cbd > 180^{\circ}$ (sum of angles in tetragon is 360), but as c-d is a chord in Ccde, so this means that at least one of the points a,b lies in Ccde, so c-d-e is not a legal delaunay triangle - contradiction.

Hope this hand waving is sufficient for your understanding.

All closest neighbors are proper Delaunay edges
generalized, and its application to parallel
algorithms by Arne Maus and Jon Moen Drange (2010)


Is an undirected graph consisting only two connected vertices cyclic? I have two questions:

Does acyclic/cyclic classification only apply to directed graphs?

If not, does the following undirected graph have any cycle?
A --- B

(1.) No, undirected cycles are also natural.

(2.) No, what you describe is a path on two vertices. It does not form a cycle, since by definition, you cannot find a subset of the edges that form a path where the first node of the path corresponds to the last.

To be sure about these type of things, you must always look at the definitions.


Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps The detailed question is:

Is there a word $w$ on which a TM M $M$ halts after a maximum of $|w|$ (word length) steps?

I highly assume, that this problem is not decidable because in the worst case you have to test every word that exists (infinite) to realize, that the TM never holds. However this isn't a proof and I have to proofe this question (without the Rice's theorem).

My idea was to use the subroutine technique to "convert" the problem into the halt-problem, the $\epsilon$-halt-problem or the total halt problem. I have no idea on how to turn this problem into an existing one - could you help me here please?

Let $M$ be a Turing machine and consider the Turing machine $M'$ that simulates $M$ on an empty input (regardless of the input to $M'$).

If $M$ halts on empty input then $M'$ eventually halts too. This means that there is a word $w$ of sufficiently large length $|w|$ such that $M'$ halts after at most $|w|$ steps (actually, there are infinitely many such words).

If $M$ does not halt, then also $M'$ doesn't halt (regardless of the its input).

Therefore your problem cannot be decidable as otherwise there would be a Turing machine capable of solving the halting problem.


Efficient algorithm for finding optimal sum from both arrays I have two arrays(A,B) and a sum M. I need to find one number from each array that makes the sum M. If there is no two elements that form sum M, then nearest and less than M sum is the solution. See examples below. What is the efficient way to find the solution for this?

eg1:
A =[200,300,600,900]
B =[1000,200,300,500]
M = 900
Output : A(2), B(2)
600 from A and 300 from B sums 900.

eg1:
A =[200,300,600,1000]
B =[1000,400,600]
M = 1500
Output : A(3), B(1)
1000 from A and 400 from B sums 1400 which is near to the sum 1500.

There are three ways how you could proceed:

If both arrays are already sorted for example in ascending order, then you start at the beginning of the first array and the end of the last array; if the sum is too small you skip to the next element of the first array, if the sum is too large you skip to the previous element of the second array, and so on.

If one array only is sorted, then you try each element x of the other array, lookup the element closest to M - x using binary search, and use the best pair.

If neither array is sorted, you sort either one or both. Calculate the runtime of either approach; it seems best to sort the smaller array, which then takes O (n log m) where m is the size of the larger array, and m the size of the smaller array.

If the larger array is already sorted, sorting the smaller array as well may be faster, because the sorting is done in O (m log m), and the first method takes only linear time. And if the arrays are of comparable size (say $m = n^{1/2}$) so log m vs. log n doesn't affect asymptotic behaviour, then what is fastest on some implementation will depend on the actual implementation.


Show that $f(n) = O(g(n))$ or $f(n) = \overset{\infty}{\Omega}(g(n))$ Before you downvote, please note that this question is distinct from this similar looking question
I came across the following the problem in "The Introduction to Algorithms" by Cormen et. al.
Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically non negative, either $f(n) = O(g(n))$ or $f(n) = \overset{\infty}{\Omega}(g(n))$ or both.
In this book, $\overset{\infty}{\Omega}(g(n))$ is defined as follows:
$f(n) = \overset{\infty}{\Omega}(g(n))$ if there exists a positive constant $c$ such that $f(n) \geq cg(n) \geq 0$ for infinitely many integers $n$. Please note that here it says integers.
Proof from a solution manual
One approach is to show that if $f(n) \neq O(g(n))$ then $f(n) = \overset{\infty}{\Omega}(g(n))$.
In the book big Oh is defined as follows:
$f(n) = O(g(n))$ if there exists $n_0 > 0$ and $c > 0$, such that $\forall n \geq n_0$, $0 \leq f(n) \leq cg(n)$. Please note these inequalities are valid not just for integer $n$'s but for all $n \geq n_0$.
$f(n) \neq O(g(n)) \implies $ $\forall n_0 > 0$ and $\forall c > 0$ there exists $n \geq n_0$ such that $f(n) > cg(n)$
I am not going into the details but, by choosing different values for $n_0$ we can show that there are infinitely many real $n$ such that $f(n) > cg(n)$. However to prove that $f(n) = \overset{\infty}{\Omega}(g(n))$ we need to show that these infinitely many $n$'s are integers.
My question is could you please show that there are infinitely many integers not just real numbers, that satisfy $f(n) \geq g(n) \geq 0$ when $f(n) \neq O(g(n))$

If you consider the following functions defined for $x\in \mathbb{R}$:
$f(x) = \left\{\begin{array}{rl}1 & \text{if }x\in\mathbb{N}\\x&\text{otherwise}\end{array}\right.$ and $g(x) = \left\{\begin{array}{rl}x & \text{if }x\in\mathbb{N}\\1&\text{otherwise}\end{array}\right.$
Then you have:

neither $f \in O(g)$, because whatever the constant $C$, $x\in]C,+\infty[\setminus \mathbb{N}\Rightarrow f(x)  > Cg(x)$;
nor $f\in \overset{\infty}{\Omega}(g)$ because whatever the constant $C$, $n\in]\frac{1}{C},+\infty[\cap\mathbb{N}\Rightarrow f(n)<Cg(n)$ (so there cannot be infinitely many integers so that $f(x) \geq Cg(n)$).

So the question here implicitly supposes that the big Oh notation considers that $n\in\mathbb{N}$ (and I think that's why the chosen notation is $n$).


Let's take main phrase from your book:
"If you read this sum left to right, it starts with 1 and doubles until it gets to $X$"
This means, that $X=2^k$, for some $k$. So, simply using geometrical progression, we have
$$1+2+4+\cdots+2^k=\frac{X}{2^k} +\frac{X}{2^{k-1}} + \cdots+\frac{X}{2^2}+\frac{X}{2}+ X = \frac{1-2^{k+1}}{1-2}=2^{k+1}-1=2X-1$$


Finding an unambiguous grammar of a language provided by a CFG I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman.

In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar for the language of this Context-Free Grammar (where epsilon is the empty string):

$$S \rightarrow aS | aSbS | \epsilon$$

I'm having difficulty describing this grammar formally, but I realize the number of a's is greater than or equal to the number of b's. And the string will always begin with an a (except for the empty string).

I have attempted to break the grammar into two parts to remove the ambiguity. After a few brute force attempts, I decided to distinctly have a variable generate only a's and the other variable generate an equal amount of a's and b's.

$$S \rightarrow A | B | \epsilon$$
$$A \rightarrow aA | a $$
$$B \rightarrow BB | aAbA | ab$$

The key part is when a re-write of B to a sentential form when an A occurs, only more a's can be generated in the string.

My question is does the new grammar I created generate the same language as the previous grammar? If not, what would be the correct grammar? I realize determining if two CFG are equivalent is undecidable; but I have no method of determining if I am correct.

First, let us show that the original grammar generates the language $L$ of all words in which in every prefix, there are at least as many $a$s as $b$.

A simple induction shows that every word generated by the grammar satisfies the property. In the other direction, let $w$ be a non-empty word in $L$. We consider two cases:

Some prefix of $w$ has exactly as many $a$s as $b$s. Write $w = axby$, where $axb$ is the shortest prefix with this property. This choice guarantees that $x \in L$. Also, $y \in L$. Hence we can generate $w$ using the rule $S \to aSbS$.
In every prefix of $w$, the number of $a$s exceeds the number of $b$s. Hence $w = az$, where $z \in L$, and we can generate $w$ using the rule $S \to aS$.

Every word $w \in L$ can be written (uniquely) as $w_0 a w_1 a \cdots a w_\ell$, where $w_i$ is a word in $L$ in which the number of $a$s is the same as the number of $b$s. Indeed, $w_0$ is the longest prefix of $w$ in which the number of $a$s is the same as the number of $b$s; $w_0 a w_1$ is the longest prefix of $w$ in which the number of $a$s exceeds the number of $b$s by 1; and so on.

Suppose that $T$ generates unambiguously the language $L'$ of all words in $L$ in which the number of $a$s is the same as the number of $b$s. Then we can generate $L$ itself unambiguously using the productions $S \to T a S \mid T$. The language $L'$ can be generated unambiguously using $T \to aTbT \mid \epsilon$.


What is the size of a queue associated with a resource when the resource becomes a bottleneck? In Software Performance and Scalability: A Quantitative Approach - Henry H. Liu, the author is presenting a scenario where the hardware becomes a bottleneck. In one ot the tests, he is checking the number disk (read/write) operations. In particular, the number of disk writes as the number of threads increases (see figure below).

After this, he states that: "A rule of thumb is that a resource is a bottleneck when the queue length associated with it is over 2 per unit. Since the RAID 0 configuration used for this test had four disks, the threshold would be 8. This threshold of 8 had been exceeded with a
write average queue length of 20 with 4 threads. With 16 threads, the associated average write queue length even went up to 132, which was over 16 times the threshold value of 8. It is clear that the system was disk write bottlenecked."

My question is: Why a resource is a bottleneck when its queue length is over 2? Why is not over 1? why is not over 1000000? why 2?

He explicitly says it's a rule of thumb.  That means it's not a hard-and-fast rule; it is just a guideline that is often helpful (but no guarantees).  While I'm not familiar with that textbook, I suspect that justifying this rule of thumb would likely require concepts that are beyond the scope of that book.

If you want to understand where it is coming from, one approach is to try some simulations and see what happens.  That will give you a rough feeling for it.

If you want to understand the mathematics behind it, your next step is to study queuing theory.  There is a relationship between the average queue length and the average utilization of a resource.  When queues get large, that tends to mean that the arrival rate is close to or exceeds the departure rate, and means that the resource is highly utilized.  In the kind of setting talked about in the book, this in turn means that the resource is a good candidate to be a bottleneck.


Spacial access methods and z-order I'm relatively familiar with spacial access methods and related data-structure such as Kd-trees and R-trees, but there is a related issue which I don't remember having seen mentioned when reading on that subject.

I'm concerned with the 2 dimension case.  Programs manipulating shapes often sort overlapping shapes in z-order, giving a predictable behavior.  Querying a data structure for a range access usually provides the shapes in the region in an order not guaranteed to respect the z-order.  It is obviously possible to sort the result, but are there some data-structure allowing to avoid that step? Especially when z-order is considered important only for overlapping shapes.

First of all, Kd-trees are data-structures for a number of points, while your problem is considered with shapes. Although you can (and we will) represent the shapes as points in a higher dimensional space in some way, querying shapes is an important special case over arbitrary points. I don't see why Z-orders would be interesting for points, so we really want a data-structure for shapes. R-trees store rectangles, but if you are interested in finding intersections of query regions with non-rectangular shapes, R-trees probably aren't very helpful.
Since a general shape is not so clearly enough, I will consider searching for a range in a set of $n$ simple polygons, this should be sufficient for most cases. Querying this structure with a 2D range (that is, an orthogonal rectangle) for shapes can mean two different things:

Find all polygons fully contained in an orthogonal query rectangle.
Find all polygons intersecting an orthogonal query rectangle.

Polygons fully contained in an orthogonal query rectangle
For the first query, note that a polygon is fully contained in a rectangle if and only if its rectangular bounding box is fully contained inside the query rectangle. So, we can search for the bounding boxes of the shapes. To do this, we represent the bounding box of every shape $s$ as a tuple of the bottom left and upper right corner $(p_s, q_s)$. I denote the $x$- and $y$-coordinates of a point using brackets, e.g. $p[x]$. We want to find all $s$ such that $p_r \leq p_s$ and $q_r \leq q_s$ for a query rectangle $r$. We can use a 4D version of your favorite point range query data structure (Kd,R,Range,etc.-tree) to find all those rectangles in $O(\log^3 n + k)$ time, were $k$ is the amount of rectangles reported, and use $O(n\log^3 n)$ storage for the data-structure. You can actually reduce the storage to $O(n\log^2 n)$, using a 2D-Range tree on the points $p_s$ and 'linking' this tree to a priority search tree for the $q_s$ coordinate (since we only have to search in positive direction on the second coordinate). However, Range trees tend to have large coefficients in practice, so you should probably stick to the trees you're familiar with.
Polygons intersecting an orthogonal query rectangle
For the second type of query on points, finding all polygons intersecting an orthogonal query rectangle, searching for intersecting bounding boxes may lead to a lot bounding boxes where the polygon does not actually intersect the query rectangle, so we need another representation. If we represent all polygons by the $m$ segments of their boundaries, we use a Windowing query to find the segments in $O(log^2 m + i)$, where $i$ is the amount of segments found, using a $O(m\log m)$ size data-structure.
However, we missed the polygons that contain our query rectangle, as we only looked for boundary intersections. We can check this by storing the bounding boxes of all polygons in 2 'chained' segment trees (similar to creating from 2D-range trees from BST's) and query for the bounding boxes that contain endpoints of the query rectangle. This has a query time of $O(\log n + k)$ and uses $O(n\log n )$ storage, but this is dominated by the other part, as $n\leq m$ and $k \leq i$.
Now, for z-orders...
First, to summarize, we now have algorithms to solve the following problems with the following bounds:

Finding all polygons fully contained in an orthogonal query rectangle takes $O(\log^3 n + k)$ time and $O(n\log^3 n)$ space, where $n$ is the total number of polygons and $k$ is the number of polygons reported.
Finding all polygons intersecting an orthogonal query rectangle takes $O(\log^2 m + i)$ time and $O(m\log m)$ space, where $m$ is the total number of polygon segments and $i$ is the number of segments of the polygons reported.

Now, I feel that I can finally consider the z-order. I will assume we want to query for shapes fully contained in our rectangle, since the reasoning and conclusion is similar for the other case.
I do not know why you need the objects sorted on z-order, but I assume you want to iterate over all reported shapes in their z-order (If this is not what you want, there might be a far better method than sorting)
If we query as discussed and sort the found rectangles, we get a running time of $O(\log^3 n + k\log k)$. Generally, $k$ is small compared to $n$, so the additional log factor does not do that much so you might as well sort. In fact, $n\log n$ is usually the best you can get for an geometric algorithm that is not a variant of point location/range search.
If $k$ is not small compared to $n$, you're probably better of not running all this complicated range searching and just run the trivial $O(n)$-algorithm that traverses all shapes in their z-order, while checking in constant time if it is in your query range. (I ignore sorting all shapes, as you only need to do that once)
Tldr;+Conclusion
If range searching is your problem, sorting probably isn't and if sorting is your problem, range searching probably isn't.
Although there are probably cases where they both are problem (e.g. zooming in maps), getting a good solution for this case could be rather tricky. I hope that if you learned anything from this answer, it is that range searching can already be quite a tricky business, so I'll leave it at this for now. It might be interesting to look if this specific topic has some useful literature.


Complexity of Longest Palindromic Subsequence Algorithm I'm trying to find the longest palindromic subsequence for any string and I've tried two approaches:

Recursive Algoritm
Dynamic Programming

Dynamic programming should be the better option in this case because of the time complexity but the time complexity of both algorithms is $O(n^2)$. My question is if the time complexity is the same for both algorithms, why is the dynamic programming approach considered better than recursive solution? I'm following the algoritms in this post. It says that the time complexity of dynamic programming algorithm is much better than the worst case time complexity of naive recursive implementation. What could be the worst case?

The dynamic programming approach is indeed O(n^2).
However, the recursive solution is exponential in n: any time two characters don't match, a subproblem of size k is converted into 2 subproblems of size k-1 each.
It's easy to see that, with all letters different, this produces a complexity of O(2^n).

Here is the example from the page you mention, modified to count and output the number of calls.
A local copy to prevent link rot:

#include <stdio.h>
#include <string.h>

int max (int x, int y) {return (x > y) ? x : y;}

int count;

int lps (char * seq, int i, int j)
{
   count += 1;
   if (i == j)
      return 1;
   if (seq[i] == seq[j] && i + 1 == j)
      return 2;
   if (seq[i] == seq[j])
      return lps (seq, i + 1, j - 1) + 2;
   return max (lps (seq, i, j - 1), lps(seq, i + 1, j));
}

int main ()
{
    char seq [] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for (int n = 1; n <= 26; n++)
    {
       count = 0;
       printf ("n = %d: answer = %d", n, lps (seq, 0, n - 1));
       printf (", count = %d\n", count);
    }
    return 0;
}

The output is:

n = 1: answer = 1, count = 1
n = 2: answer = 1, count = 3
n = 3: answer = 1, count = 7
n = 4: answer = 1, count = 15
n = 5: answer = 1, count = 31
...
n = 24: answer = 1, count = 16777215
n = 25: answer = 1, count = 33554431
n = 26: answer = 1, count = 67108863


Remove minimum number of vertices to disconnect the graph Consider an undirected graph with a source and a sink vertex. We would like to remove minimum number of vertices in that graph to disconnect any path between source and sink.

Can we do this using say a max-flow, min-cut algorithm?

(This answer was originally given as part of the question, with the goal of it being verified.)

My intuition tells me that we can use max-flow, min-cut algorithm to solve this problem:

Replace each of the undirected edges with a pair of directed edges.
Replace each vertex $v$ with two vertices $v_\text{in}$ and $v_\text{out}$ connected by an edge. all the incoming edges of $v$ will be connected with $v_\text{in}$, all the outgoing edges of $v$ will be connected with $v_\text{out}$.
Try to find a minimum cut $M$. The edges of $M$ refer to the vertices that we need to remove.


Number of nil-links in a binary tree In its section Properties of binary trees Wikipedia states:

  The maximum possible number of null links (i.e., absent children of the nodes) in a complete binary tree of n nodes is (n+1), where only 1 node exists in bottom-most level to the far left.

I wonder about the precise statement used here. In my opinion every binary tree with $n$ nodes has exactly $n+1$ nil links (or missing children). A proof by induction is easy. (In fact that is equivalent to the statement some lines above: "a perfect binary tree with $\ell$ leaves has $n=2\ell-1$ nodes".)

Question: what am I missing here? Has Wikipedia different assumptions on binary trees?

As an illustration, a non-complete binary tree with 12 nodes and 13 nil-pointers, marked as square nodes. It can also been seen as a perfect binary tree with 25 nodes, the squares indicating leafs.

The Wikipedia article defines a null links as "absent children of the nodes", presumably "absent" in the sense of what nodes are missing to obtain a perfect binary tree (i.e., "a binary tree in which all interior nodes have two children and all leaves have the same depth or same level"). Under this definition, leaves (i.e., the nodes in the last level of the tree) do not have links. Hence, because all other levels are filled, to determine the number of null links you need only look at the previous to last level of the tree. This also explains the maximum case (i.e., "where only 1 node exists in bottom-most level")


Relation between Machine code and Von Neumann architecture Since machine language executes instructions on ALU, CPU register and memory, is correct say that machine code abstract the Von Neumann model?

If exists, semantically, what is the relation between machine code and Von Neumann architecture?

Asking whether machine code abstracts the von Neumann model is a category error – it's a statement that doesn't type-check. The von Neumann model is essentially a system architecture: it's a way of designing computers. Machine code is a sequence of instructions: a way of telling a computer what to do. Those are two completely different things.

Machine code arguably doesn't abstract anything. It's the most concrete, specific thing there is: it runs on only one specific kind of CPU (or perhaps a family of very closely related ones).


Creating a PDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n} I didn‘t find a DPDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}, so I guess an NPDA is the only option.

NPDA are not very intuitive to me. The only solution I found online is:

I don‘t really understand how it works and also I‘m not allowed to use final states. The only way an input is accepted is by emptying the Stack (how we do it at my university).

Thanks in advance!

First of all the answer you have provided is DPDA and not NPDA. "Z" denotes that your stack is empty, so you start by taking input i.e., "a" and keep storing them in your stack, as soon as "b" arrives you start removing one "a" for every "b" that arrives (b,a|Epsilon). Now their are two possibilities
(i) m>n :- if so number of "b" are less than "a", so after all the "b" are computed only "E" will be left in the string so we reach the final state i.e., (E,a|a)
(ii) n>m:- in this case all the "a"s will be removed so only "Z" will remain in the stack, so in this case this will be the final state i.e., (b,Z|Z)

Hope this will help.


Immediate positions algorithm? Im studying for the computer science subject GRE test, as an exercise i need to implement the followin algorithm in java, any idea on how to aproach it?.

Given a set $X$ and $z$ not in $X$, indicate between which would be the immediate positions $z$ in $X$

It depends on how $X$ is given. If $X$ is given unsorted, find the minimum element larger than $z$, and the maximum element smaller than $z$. If $X$ is given sorted, use binary search.


What is the lower bound of the following computation I came across this question was I was browsing online

An operation OP has the following characteristics

    OP Latency = 7 clocks
    OP cycles/issue =2

Derive the minimum number of cycles required for the following computation:

 X[0] OP X[1] OP X[2] OP ....... OP X[N-1]

The answer was written as 7 + 2(n-2). But I was not able to achieve the result. Can someone help me to solve this.

My try: As suggested by D.W. to check the value for n=3,4,5
For n=3, I am getting lower bound as 7+2(2)

For n=4, I am getting lower bound as 7+3(2)

For n=5, I am getting lower bound as 2(7)+4(2)

For n=6, I am getting lower bound as 2(7)+5(2)

Am I going correct. But it deviates from the answer given

The attempt in the edited question is almost there.  When you issue the instruction OP, you get the answer back seven cycles later. When you issue an OP instruction, you must wait two more cycles before issuing another. You need to issue $N-1$ OP instructions, so they're issued at times $0, 2, 4, \dots, 2(N-2)$, and the last one completes seven cycles after it's issued, so we get the required answer.

Having said that, the example in the question seems bad. Since OP is an instruction taking two arguments, it's unclear what X[0] OP X[1] OP X[2] even means. If it's supposed to mean S := X[0] OP X[1]; S := S OP X[2]; then there are dependencies between the instructions. The second OP needs to know the value returned by the first, so it can't be issued until the first one has finished.  If the instruction sequence is supposed to mean X[0] OP X[1]; X[1] OP X[2], then it should just be written that way, or even just OP; OP, since the arguments are irrelevant.


nested boxes algorithm I am given a set of 3D boxes {$B_1$, $B_2$...$B_n$} and each box have length, width and height. But these values are interchangeable since I can rotate the box. I need to find out the maximum sequence of nested boxes.

I have tried this problem using sort. But I still get stuck. I used built in sort function to sort all boxes by length in ascending order. I read the reference about this question and learned that people used radix sort. I have know idea how radix sort is applied here because all sorts I am familiar is comparison sort.

One solution that comes to mind is to first build a directed graph where every vertex represents a vertex. An edge goes from Box A to Box B if B fits into A. One can easily verify that this graph contains no cycles. A maximum sequence of nested boxes is equivalent to the longest path in this directed acyclic graph. A longest path in a DAG can be found by using a topological sort on the graph.

This surely is a bit overkill and is probably also not the most efficient solution ($O(n^2)$ for building the graph).


Determine whether two languages are context free (1) $L_1 = \{a^ib^{i+j}c^j|i,j\geq 0\} $

(2) $L_2 = \{xy | x,y \in \{0,1\}^*, x \neq y, |x| = |y| \}$

I doubt that $L_1$ is CFL. I've been trying to go with the string $s$ = $a^pb^{2p}c^p$. Thus, we can write $s$ as $uvxyz$. Now I'm trying to show $uv^2xy^2z$ is not in $L_1$.

I really have no idea how to approach (2). And if it is context free, how in the world would you draw a pda?

For the first one, $$L_1 = \{a^i,b^{i+j}c^j \mid i,j \geq 0 \} $$

Here's an rough idea of the algorithm:

read off the all '$a$'s and push $a$ into the stack
upon seeing a '$b$', pop the '$a$'s till the stack is empty
then again as long as reading '$b$'s keep pushing $b$ into the stack
on seeing a $c$, start popping the stack until empty.

For the second one,

Please see my answer here, The other answer is equally good (perhaps even better and simpler) than mine.


What is an "encoding" of a TM? I'm currently working on a reduction from $A_{TM}$ to another language, and have been reading through some example proofs. I've come across the situation where, for example, we have $L = \{ \langle M,w \rangle | \text{ ...etc} \}$, where obviously this would normally stand for $M$ being a TM and $w$ being a string. However, later in the proofs, we replace the $w$ (a string) with an "encoding of a turing machine". Sometimes it's even "an encoding of the TM, $M$".

I'm rather lost on this idea. How do we pass an "encoding of a TM" into a parameter for a string? How do we run that on a TM? Maybe I'm misunderstanding the definition of an "encoding of a TM", which I assume to be the TM itself somehow converted into a string format.

Would anyone mind explaining this to me? I'm sure truly understanding this concept would immensely help me in writing further reductions.

A Turing machine $M$ can be described as a 7-tuple $(Q,F,q_0,\Sigma,\Gamma,\delta, blank)$. This means that if someone gives you this 7-tuple, then the TM is well-defined, and you can precisely define how it behaves, etc.

The encoding of a TM, usually denoted as $\langle M \rangle$ is a string that encompasses all the information of the 7-tuple describing $M$. You can think of it as "writing the 7-tuple as a binary string" (but this is a simplification). So the encoding of M, is just a string that describes how the TM works.

The last observation is that if you know the encoding - you know everything about the TM; specifically, if $\langle M \rangle$ is given as an input (to a machine $M'$), the TM $M'$ can "run" or "simulate" what $M$ would have done on any given input -- the machine $M'$ knows the states $Q$ of $M$ and the transition $\delta$ of $M$, so it can imitate its actions, step by step.


Count elements in the real world in constant time by weighing them I suppose that counting n elements should be linear time, right? It takes double time to count double number of elements. But in the real world, it is faster and O(1) to weigh elements and find out the total weight so in the real world you can count n elements O(1) just by putting all the elements on a scale and dividing by the weight of one elements.

Is my reasoning correct that physically it is possible to speed up a calculation by this trick, or am I mistaken?

Weighing elements works faster than counting them, because the scale is a fully parallel computing device. It sums the weighs of all elements in constant time. Of course you need an infinitely large scale if you want to talk about asymptotic runtimes. In practice your scale can only weigh a constant number of items at once, so your speedup is only a constant factor.

A related algorithm is Spaghetti sort.


Name of BFS variant with multiple queues with different priorities Is there a name for the following variant of BFS that operates on trees with non-root starting point?:

Instead of a single queue that all neighbor nodes are added to when processing a node, two queues are used ($Q_A$ and $Q_B$).
Children nodes are added to $Q_A$, and parent nodes are added to $Q_B$.
When selecting the next node to process, $Q_A$ is drawn from, and only when $Q_A$ is empty is $Q_B$ drawn from.

One application for this (and the one that made me think of this) is for ranking "close" documents in a folder hierarchy (based on the leaf-node discovery order of the algorithm). For example in the following hierarchy:

- Root Folder
  - Folder 1
    - Document 1.1
    - Folder 1.2
      - Folder 1.2.1
        - Folder 1.2.1.1
          - Document 1.2.1.1.1
    - Folder 1.3
      - Document 1.3.1
  - Folder 2
    - Document 2.1

If we start our search at Document 1.1 we would like to see the following ranking (which the algorithm produces):

Document 1.1
Document 1.3.1
Document 1.2.1.1.1
Document 2.1

Document 1.2.1.1.1 should appear higher than Document 2.1 since there is a closer common ancestor (Folder 1), even though the former is technically further away (distance of 4 vs. 5).

Some other things I considered that don't actually work:

BFS using a single queue but always enqueuing the parent last. This doesn't work as it's still regular BFS and ranks based on shortest path.
DFS, and always pushing the parent onto the stack first so it's discovered last. This could rank Document 1.2.1.1.1 above Document 1.3.1 depending on the order children are enqueued.

This seems like a pretty standard algorithm, but I couldn't find anything when I searched for it, so I was hoping someone might recognize it and know what it's called.

I don't think this particular implementation has a name, but there is a slightly different implementation that achieve the same goal and has a name: BFS 0-1.

Let me briefly describe the algorithm, and then let's solve your problem using this algorithm. For more complete description use previous link or Google about, it has a name.

Suppose you have a general graph (a tree will also work) where each edge has a weight, but the weight can only be 0 or 1. You are given a source node and should find minimal distance to every other node in the graph. This can be easily solved with Dijkstra's algorithm but complexity worsens. Instead of using Dijkstra, let's use BFS, with a deque (in the place of the queue). When we are traversing an edge with weight 0 we add this node to the beginning of the deque, otherwise you add it at the end.

Without going too much into the details of BFS 0-1 I'll apply it to your problem. Suppose that every time you are visiting an unvisited parent you add it to the end of the deque, and when you are visiting an unvisited child you add it to the front of the deque. The order in which you will visit the nodes in your file system will be the one desired. Notice now, that we are treating edges going to a parent as if they have weight 1, and edges going to children as if they have edge 0 (graph is obviously directed, since each edge has different weight when direction changes). The distance to each node from the source will be the distance to the closest common ancestor in the initial tree.

This is not exactly the same algorithm you were proposing, but notice that using the idea of two queues, is the same as having the deque and inserting from the beginning or from the end, so we can say both algorithms are basically equivalent. It can be naturally extended following your idea to support graphs were edges has weight such that they are numbers between $0$ and $k - 1$, using $k$ queues, however it is more tricky and out of the scope of this question.


MIPS: sign extend in I-Type commands My lecturer told me that when I use an arithmetic I-Type command (ADDI,SUBI etc.) , the IMM field gets sign extended, and when I use a logic I-Type command (ORI,ANDI etc.) , the IMM field is just bits.

He also said that if the IMM field contains a negative number, it is represented in 2's complement.

Let's say I have a command, and two binary numbers X Y, so that X's 2's complement representation looks exactly like Y in regular representation.

Note: X is negative and not the same as Y.

Given a question in which I should say what is the value in the IMM field in an arithmetic I-Type command, how do I know if it's X or Y?

In an arithmetic I-type command, the IMM-field is treated as a signed number. So if the first bit is 1, the number will be treated as negative (X in your terms.) The number Y is simply too large to be used as argument of an arithmetic I-type command.