What is the chance that this code terminates? I wrote this Python code, and wondered if it sometimes simply doesn't terminate (assuming we had infinite memory/time and no recursion depth limit).

Intuitively you'd think it terminates, since at some point you must get lucky, and if it doesn't terminate you have an infinite amount of time to get lucky. On the other hand, as the recursion depth increases you must become exponentially more lucky.

import random

def random_tree():
    if random.random() < 0.5:
        return 0
    return [random_tree() for _ in range(random.randint(1, 5))]

If random_tree doesn't always terminate, why, and what is the chance that it does terminate?

I've tried to calculate it using $P = 1 - (1 - 0.5)(1 - (P + P^2 + P^3 + P^4 + P^5)/5)$, which in it's terrific uselessness either gives the answer ~$0.684124$ or... $1$.

Probably more complicated, but also intriguing to me, what is the termination chance  $P(a, b)$ for:

def random_tree(a, b):
    if random.random() < a:
        return 0
    return [random_tree(a, b) for _ in range(random.randint(1, b))]

Or in pseudo-code:

random_tree(a, b) is a function that either:
    - returns 0 with probability a
    - returns a list containing the results of 1 to b
      (uniformly chosen from this inclusive range) recursive calls

random_tree(a, b):
    if rand() < a # rand() is a random real on [0, 1)
        return 0
    list = []
    len = randint(1, b) # uniform random integer from 1 to b inclusive
    do len times
        append random_tree(a, b) to list
    return list

This is an example of a branching process. The behavior of a branching process depends on the expected number of children, which in your case is $1.25 > 1$. When this number is at most 1, the process gets extinct with probability 1. When the number is more than 1, it has a chance of surviving forever; the extinction probability is just what you calculated — you need to select the root which is smaller than 1.


Dynamic programming VS Greedy Algroithms I have two True or False questions in my practice test that are related but I am unsure about:

1. If an optimization problem can be solved using a greedy algorithm,
there must be a solution for this optimization problem using dynamic programming as well.

2. If an optimization problem can be solved using dynamic programming,
there must be a solution for this problem using a greedy algorithm as well.

I think the answers are 1. True and 2. False is this correct?

Sounds about right, however informal the statement; dynamic programming is more powerful than greedy algorithms so if a problem should require it, a greedy algorithm won't be enough. And in the case in which a greedy algorithm can solve the problem, there will also be a correct dynamic programming solution since dynamic programming involves solving problems by optimizing overlapping subproblems. Suppose a greedy algorithm suffices, then the local optimal decision at each stage leads to the optimal solution and you can construct a dynamic programming solution to find the optimal solution. However, greedy algorithms are generally faster so if a problem can be solved with a greedy algorithm, it will typically be better to use.


Hierarchical Paging memory requirements OS Book written by Galvin et all states that if page size is 4KB and size of virtual space is 32 bits then 2^(32-12) page entries would be required which is too huge to store in memory!!

Therefore it recommends to break it down by paging the inner page table as well. Now my question is how does that reduce memory requirements? Shouldn't inner page table and outer page table both be in memory and just the computational requirements reduce because inner page table can now be indexed quickly with the help of outer page table??

Have you read Wikipedia's article on page tables?

There are two ways that a multi-level page table saves memory. First, you don't need to create parts of the page table for memory that isn't being used by the process: you only create the subtables for the parts of the virtual address space that are in use. Second, if you want to really live by the seat of your pants, you can use your virtual memory system to swap parts of the page table out of physical memory.


Proof that the grammar is LL(2) I am given the following grammar:

$
S \rightarrow AabAba
\\
A \rightarrow a | \epsilon
$

and I have to prove it is LL(2).

I know what LL(k) means - one can choose a production based on k characters from the input.

So consider the input $ababa$. Of course we start with $S$, so we apply the production to $AabAba$. Now we see $ab$ in the input, so we choose the production to $\epsilon$ for the first $A$. We get rid of the $ab$ and we have $aba$.

And what now? A while ago, we've chosen $\epsilon$ for $A$, seeing $ab$ in the input. Now we see the same thing, but are supposed to choose $A \rightarrow a$. But, as I understand, we cannot do this, because that would mean nondeterminism.

Is this a counterexample? How is this grammar LL(2)?

Sippu and Soisalon-Soininen (1982) carefully distinguish between two definitions of LL(k) grammars, one of which -- the one I think you are using -- they call strong LL(k):

A grammar $G$ is $\text{LL}(k)$ if $\text{FIRST}_k(\omega_1\delta)$  and $\text{FIRST}_k(\omega_2\delta)$ are disjoint whenever $xA\delta$ is a left sentential form of $G$ and $A \to \omega_1$ and $A \to \omega_2$ are distinct productions of $G$.
Grammar $G$ is $\text{strong LL}(k)$ if $\text{FIRST}_k(\omega_1\text{FOLLOW}_k(A))$ and $\text{FIRST}_k(\omega_2\text{FOLLOW}_k(A))$ are disjoint whenever $A \to \omega_1$ and $A \to \omega_2$ are distinct productions of $G$.

The difference has to do with the state machine. A grammar is $\text{strong LL}(k)$ if you can use the same procedure to decide which production for a non-terminal to use regardless of the contents of the parser stack. An $\text{LL}(k)$ grammar, on the other hand, can use the contents of the stack ($x$ in the above definition) as well as the lookahead. (For these purposes the contents of the stack can be condensed into a finite state automaton.)
While the two definitions are not equivalent -- the strong condition is much more restrictive -- it can be demonstrated that every $\text{LL}(k)$ grammar can be changed to a $\text{strong LL}(k)$ grammar simply by labelling each usage of a non-terminal. So in the case of your grammar, which is $\text{LL}(k)$ but not $\text{strong LL}(k)$, we can create the equivalent grammar:
$\begin{align}
S &\to A_1abA_2ba \\
A_1 &\to a | \epsilon \\
A_2 &\to a | \epsilon \\
\end{align}$
which is $\text{strong LL}(k)$.
For more details, see the paper linked above.


Transform grammar for repeating characters into LL(1) I have the following simple production rule:

S -> Sa | a

Which is left-recursive, and can recognize strings such as a or aa, etc

I tried to make it right-recursive, but I cannot find a way without creating ambigious grammars
(e.g.
 S -> aS'
S' -> a | aS'
)

Can someone explain how to make this grammar right-recursive and LL(1) form?

Let's construct an LL(1) grammar for the language $\mathscr{L}(a^+)$.

Firstly, observe that all the production rules in this case must have one of two forms:
$$A \to a\Gamma$$
or
$$A \to \epsilon,$$
where $\Gamma$ is a (possibly empty) sequence of non-terminals and the terminal 'a'.

The first step would be adding the rule $S \to aS'$, since it's clear that $S \to aS \mid a$ doesn't give us an LL(1) grammar.
Obviously $S'$ must have a production rule with the empty string as its body $S' \to \epsilon$, which will be used when we get the end of string symbol $\$$ during parsing. We also need a "looping construct" to finish our construction, resulting in the following LL(1) grammar:

$$\begin{align}
S  &\to aS' \\
S' &\to \epsilon \mid aS'
\end{align}$$

From wikipedia:

  A nonterminal is left-recursive if the leftmost symbol in one of its productions is itself (...) or can be made itself by some sequence of substitutions (...).

Since neither $S'$ nor $S$'s left-most non-terminal symbol cannot be 'made itself' by any sequence of substitutions (there are simply no left-most non-terminal symbols there), the resulting grammar is not left-recursive.


Conway's Game Of Life Problem Parallel (OpenMP) I am currently working in solving Conway's Game Of Life problem for a Parallel and Distributed Computing course.

The problem is a little bit different form the original, in the sense that instead of having a 2D representation of the cells we have a 3D one, each cell is represented by three ints. When considering neighbours, only the x + 1, x - 1, y + 1, y - 1, z + 1 and z - 1 are considered (no diagonals).

The input of the problem is constituted by the size of the cube (size) where the cells are present, followed by a list of  positions of live cells.

The number of cells, is in the order of O(size^2), and the space is in the order of O(size^3).

My current implementation uses C++ maps, in which a key is a tuple with x, y and z, and the value is an integer telling in that position the cell is alive or not. My current approach is to just go through every position available in the cube and check the number of neighbours and update that position accordingly, but i believe this is not ideal because the number of live cells is in the order of O(size^2) and not O(size^3).

My question is how would you improve this solution ? Is there a better data structure to use ? Considering that I have to build an OpenMP implementation (shared memory) for very large input cases (size > 10000).

Thank you !

There is a simple solution.  Instead of storing a hashmap of all positions, store the set of only the positions that are currently alive.  Live cells are included in the set; dead cells are not.  When you want to know whether a particular cell is alive or not, look up that position in the set; if it is found, then the cell is alive, otherwise the cell is dead.  You can store the set as a hashtable.

You said that you expect only about O(size^2) cells to be alive.  My proposal reduces the space complexity to O(size^2), instead of O(size^3).  Also, the running time to check whether a particular cell is alive will be O(1).  The running time to enumerate all live cells will be O(size^2).

It follows that the running time to compute the next state of the world will be O(size^2).  Since each cell has only 4 neighbors, you only need to enumerate O(5 * size^2) = O(size^2) many cells (all of the live cells and their neighbors) to see which will be alive in the next iteration.  To tell whether a cell will be alive in the next iteration can be done by examining its state and the state of its 4 neighbors, which can be done in O(1) time.

This approach should also generalize nicely to a parallel/distributed implementation.

This all assumes that the number of live cells is limited to O(size^2) for all iterations.  That might be a dubious assumption in practice: the number of live cells can quickly grow to O(size^3), for some initial configurations (in particular, it might take only O(lg size) iterations to go from O(size^2) to O(size^3) live cells).


An AC$^1$ circuit for 2-SAT We know that $NC^1 \subseteq NL \subseteq AC^1$ and that 2-SAT is complete for $NL$.

  How does one construct an $AC^1$ circuit for 2-SAT?

Recall that $AC^1$ circuits have $O(\log n)$ depth where $n$ is the number of bits in the input.

I have read Herbert Vollmer's book on Circuit Complexity as well as the chapter in Arora-Barak's book.  Still, appears to be very challenging.

For example, we can fix the length of the input for each variable (say $3$ bits).    For each literal, let the first bit indicate whether it is positive or negative.  So each literal is represented by $1+3 = 4$ bits.

Thus the negative literal $\neg x_1 \equiv 0001$ and the positive literal $x_2 \equiv 1010$.

Let FALSE $\equiv 0000$ and let a unit clause (a clause with one literal) ($x_i$) be represented as $(x_i \lor FALSE)$.

Hence a 2SAT formula $\phi = (x_1 \lor \neg x_2) \land (x_5 \lor \neg x_6)$ would be represented as

$11110$-$1001$-$0010$-$1101$-$0110~ $ as input to the circuit
(dashes just added for reading clarity only).

The first $4$ bits $1111$ mean that each literal is represented by $4$ bits --- the fifth bit ($0$) is just a separator before the actual input $\phi$ begins.

And then we have to implement an algorithm in the (C $\log n$) levels above the input level, for some constant $C$, using $AND$, $OR$ and $NOT$ gates, allowing unbounded fan-in.

Is this going in the right direction?

The proof that $\mathsf{NL} \subseteq \mathsf{AC}^1$ is constructive, giving an $\mathsf{AC}^1$ circuit for directed reachability. Since directed reachability is $\mathsf{NL}$-complete and 2SAT is in $\mathsf{NL}$, there is an $\mathsf{AC}^0$ reduction from 2SAT to directed reachability. Combining the $\mathsf{AC}^1$ circuit for directed reachability with the $\mathsf{AC}^0$ reduction from 2SAT to directed reachability, we obtain an $\mathsf{AC}^1$ circuit for 2SAT.

It might be better, however, to construct such a circuit directly using ideas from the proof of $\mathsf{NL} \subseteq \mathsf{AC}^1$. This could result is a smaller and simpler circuit.

The OP also asks whether HornSAT has $\mathsf{AC}^1$ circuits. Since HornSAT is $\mathsf{P}$-complete and we believe that $\mathsf{AC}^1 \neq \mathsf{P}$, the answer is probably no. The OP suggests using the switching lemma to prove this. However, the switching lemma only works for circuits of depth $O(\log n/\log\log n)$.


Exponential separation between NFAs and DFAs in the presence of unions For a regular language $L$, its DFA complexity is the size of the minimal DFA accepting it, and its NFA complexity is the size of the minimal NFA accepting it. It is well-known that there is an exponential separation between the two complexities, at least when the size of the alphabet is unbounded. Indeed, consider the language $L_n$ over the alphabet $\{1,\ldots,n\}$ consisting of all words not containing all symbols. Using the Myhill-Nerode theorem it is easy to calculate the DFA complexity $2^n$. On the other hand, the NFA complexity is only $n$ (if multiple initial states are allowed; otherwise it is $n+1$).
Problem 1.65 of Sipser's Theory of Computation concerns the DFA covering complexity of a language, which is the minimal $C$ such that $L$ can be written as the (not necessarily disjoint) union of languages of DFA complexity at most $C$. The DFA covering complexity of $L_n$ is only $2$.

Is there an exponential separation between NFA complexity and DFA covering complexity?

Consider the language $M_n = (L_n \#)^*L_n$, where $\#$ is a new symbol.
The NFA complexity of $M_n$ is $n$ (allowing for multiple initial states). Indeed, here is one NFA having $n$ states accepting $M_n$. The states are $q_1,\ldots,q_n$, all both initial and final. There is a self-loop around $q_i$ for each $j \neq i$. Furthermore, there are transitions from each $q_i$ to each $q_j$ labeled $\#$. The matching lower bound follows from the DFA complexity of $L_n = M_n \cap \{1,\ldots,n\}^*$ being $2^n$.
In contrast, we will show that the DFA covering complexity of $M_n$ is $2^n$. For the upper bound, consider a DFA whose states are $q_S$ for $S \subseteq \{1,\ldots,n\}$. The states keep track of the letters seen so far: the initial state is $q_\emptyset$, and $\delta(q_S,i) = q_{S \cup \{i\}}$. All states other than $q_{\{1,\ldots,n\}}$ are accepting. When seeing $\#$, if we're in $q_{\{1,\ldots,n\}}$ then we stay put, and otherwise we move to $q_\emptyset$.

Let $[n] = \{1,\ldots,n\}$. For $S \subseteq [n]$, let $w_S$ consist of all letters in $S$ in order. Let $P$ denote all words over $[n]$ containing each letter at most twice, and missing at least one letter.
Suppose that $M_n = \bigcup_{i=1}^N L(A_i)$, where the $A_i$ are DFAs. We can identify $L_i := L(A_i) \cap (P\#)^*P$ with a language over the alphabet $P$ in the natural way ($p_1\#\ldots\#p_\ell$ corresponds to the word of length $\ell$ whose letters are $p_1,\ldots,p_\ell$). Say that $x \in P^*$ is good for $L_i$ if for all $p \in P$ there exists $y_p \in P^*$ such that $xpy_p \in L_i$.
Suppose that no $x$ is good for $L_i$. Let $\ell \geq 0$. For $0 \leq r \leq \ell$, let $S_r$ be the set of length $r$ prefixes of words in $L_i \cap P^\ell$. If $|S_{r+1}| > (|P|-1)|S_r|$ for some $r < \ell$, then by the pigeonhole principle there is some $x \in S_r$ such that $xp \in S_{r+1}$ for all $p \in P$; but then $x$ is good. It follows that $|L_i \cap P^\ell| = |S_\ell| \leq (|P|-1)^\ell |S_0| = (|P|-1)^\ell$.
If no $x$ is good for any $A_i$, then for all $\ell \geq 0$ we have
$$
|P|^\ell \leq \sum_{i=1}^N |L_i \cap P^\ell| \leq N(|P|-1)^\ell,
$$
which is contradictory for large enough $\ell$. Therefore some $x$ is good for some $A_i$.
Let us identify $x \in P^*$ with the corresponding word over $[n] \cup \{\#\}$. Thus for each $p \in P$ there is $y_p \in M_n$ such that
$$
x\# p\# y_p \in L(A_i).
$$
We claim that the $2^n$ words $x \# w_S$ (we allow $S = [n]$) are pairwise inequivalent in the Myhill–Nerode relation of $L(A_i)$, and so $A_i$ has at least $2^n$ states.
Indeed, let $S,T$ be two different subsets of $[n]$. Assume without loss of generality that $j \in T \setminus S$. Since $w_S w_{[n] \setminus \{j\}} \in P$, by assumption $x \# w_S w_{[n] \setminus \{j\}} \# y_p \in L(A_i)$, where $p = w_S w_{[n] \setminus \{j\}}$. In contrast, $w_T w_{[n] \setminus \{j\}}$ contains all letters, hence $x \# w_T w_{[n] \setminus \{j\}} \# y_p \notin M_n$, and so $x \# w_T w_{[n] \setminus \{j\}} \# y_p \notin L(A_i)$. This shows that the two words $x \# w_S, x \# w_T$ are inequivalent.


What is the notation for bounding running time in worst case with concrete example resulting in that worst case running time I know that Big O is used to bound worst case running time. So an algorithm with running time $O(n^5)$ means its running time in worse case is less than $n^5$ asymptotically.

Similarly, one can say that for example merge sort's running time is $O(n^2)$  which is correct. But we know that there is a better bound for it: $O(n\log n)$. Technically speaking, one can say that every polytime algorithm has running time $O(2^n)$. This is correct, but not useful.

So my question is: what is the notation used for the case of worst case running time such that there exists an input in which the worst case running time happens.

In the merge sort example, one cannot construct an input example so that merge sort would take $n^2$ comparisons, but one can construct an example that requires the number of comparisons being about $n\log n$.

In words, such a bound is called a tight bound. In the specific case of Landau notation, $\Theta$ can be used to indicate a tight bound.
You have to be somewhat careful about your wording, though:

"The runtime of quicksort is in $O(n^2)$," is a correct statement (but somewhat imprecise).
"The runtime of quicksort is in $O(n^2)$, and this bound is tight," is correct and expresses, what you want to express.
"The worst-case runtime of quicksort is in $\Theta(n^2)$," is equivalent to the previous statement.
But "The runtime of quicksort is in $\Theta(n^2)$," is not correct, since this statement implies that quicksort takes quadratic time on every input.


How to find the optimum solution of Weighted set cover in O(2^n) A weighted set cover problem is:

  Given a universe $U=\{1,2,...,n\}$ and a collection of subsets of $U$, $\mathcal S=\{S_1,S_2,...,S_m\}$, and a cost function $c:\mathcal S\to Q^+$ , find a minimum cost subcollection of $\mathcal S$ that covers all elements of $U$.

How to design a deterministic algorithm to solve weighted set cover in $O(2^n)$ (just find the optimum solution)?

If I simply use exhaust searching to look through all possible cover (which is actually equals to $2^m$) and find the one with minimum weight, it will cost $O(2^m)$ but not $O(2^n)$.

Use dynamic programming. For every $i \in [m]$ and every $V \subseteq U$, compute the minimal weight of sets among $S_1,\ldots,S_i$ needed to cover $V$.

Here is pseudocode, which uses $w_i$ for the weight of $S_i$:

Set $T[V][0] \gets \infty$ for all $\emptyset \neq V \subseteq U$, and $T[\emptyset][0] = 0$.
For $i = 1,\ldots,m$:

Set $T[V][i] \gets T[V][i-1]$ for all $V \subseteq U$.
Set $T[V \cup S_i][i] \gets \min(T[V \cup S_i][i], T[V][i-1] + w_i)$ for all $V \subseteq U$.

Return $T[U][m]$.


Turing machine enumerator As the number of Turing Machines is countably, we can create some list of them and number them 1, 2, 3,... Suppose turing machine k
 computes some function $f_k$.
Is there a turing machine S
 that can computer $f_k(k)$?

It seems like there should be, as I am fairly confident that you can write such a program in a turing-complete language. However, I am having a hard time seeing how an
$n$ state turing machine (if S
 is n states) could compute every function computed by an $n^2$ state turing machine, for example.

Indeed, there is such a Turing Machine. First, realize that it's computable to convert any integer $k$ into the $k$th Turing Machine description, just by enumerating them. Then, once we have the Turing Machine description, we can use a Universal Turing Machine to compute the function described.

The key is that, while there are less states in the $n$-state machine than in one with $n^2$, any number of additional states can be encoded on the tape of the Turing Machine. So there's no limit to the amount of information we have when computing the $k$th function, since an arbitrary amount of information can be encoded on the tape.


Grammar for describing boolean expressions with AND, OR and NOT I wrote the following LL(1) grammar to describe the set of boolean expressions involving AND ,OR  an NOT only. This, as can be seen, also reflects the precedence of the operators (ie., 'AND' is done before 'OR', etc).

Is it correct?

    1.  E   ::=  T E’
    2.  E’  ::= OR T E’
    3.  E’  ::=  ε
    4.  T   ::=  F T’
    5.  T’  ::= AND F T’
    6.  T’  ::= ε
    7.  F   ::= NF'
    8.  N   ::= NOT
    9.  N   ::= ε
   10.  F'  ::= (E)
   11.  F'  ::= id

It is an almost copy of the grammar Wirth gives for arithmetic expressions in "Algorithms + data structures = programs" (as far as I can remember it; I might be wrong with the source, though). So I strongly believe it is correct.

Write the corresponding recursive descent parser, and try it on some correct strings, and some badly built ones. Get somebody else, without coaching on your part, come up with examples and broken cases. Also generate some random combinations to try.


Could min cut be easier than network flow? Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut.  Therefore, the complexity of computing a minimum $(s,t)$-cut is no more than the complexity of computing a maximum $(s,t)$-flow.

Could it be less?  Could there be an algorithm for computing a minimum $(s,t)$-cut that is faster than any max-flow algorithm?

I tried finding a reduction to reduce the $(s,t$)-max-flow problem to the $(s,t)$-min-cut problem, but I wasn't able to find one.  My first thought was to use a divide-and-conquer algorithm: first find a min-cut, which separates the graph into two parts; now recursively find a max-flow for the left part and a max-flow for the right part, and combine them together with all of the edges crossing the cut.  This would indeed work to produce a maximum flow, but its worst-case running time might be as much as $O(|V|)$ times as large as the running time of the min-cut algorithm.  Is there a better reduction?

I realize the max-flow min-cut theorem shows that the complexity of computing the value of a max-flow is the same as the complexity of computing the capacity of a min-cut, but that's not what I'm asking about.  I'm asking about the problem of finding a max-flow and finding a min-cut (explicitly).

This is very closely related to Compute a max-flow from a min-cut, except: (1) I'm willing to allow Cook reductions (Turing reductions), not just Karp reductions (many-one reductions), and (2) perhaps given $G$ we can find some graph $G'$ such that the min-cut of $G'$ makes it easy to compute the max-flow of $G$, which is something that's out of scope for that other question.

Here is a possible approach:

Suppose you know the cut S, then finding the flow from $S$ to $t$ is a min cost network flow problem with zero cost, since you know exactly the outflow at each vertex in $V\setminus S$ and in the inflow at $t$. Suppose $f$ denotes an $S-t$ flow and $A$ the node-arc matrix (i.e. row $i$, col $j$ has 1 if $i$ is the tail of $j$, -1 if its the head, zero otherwise), and let $b$ be such that $Af = b$ if $f$ satistfies the supply/demand, and the flow conservation. Then with gaussian elimination we can find a feasible solution in $|V|^3$ operations.

To find a cut from a flow we need to construct the residual graph which takes at most $|E|$ time, and then potentially traverse $|V|$ vertices.

So for complete graphs and the minimum cut being just the source or just the sink, the reduction takes equal time in both directions worst case. However, I would think that finding a feasible solution to $Af =b$ can be done faster than $|V|^3$ given the special structure. I am not sure how to prove that though.


What are the differences between Oracle Turing Machine and PAC? I am having difficulty understanding the difference between PAC and Oracle Machines.  I cannot compare these two in terms of uncertainty and physical effort.
The degree of uncertainty we can tolerate in a system has been discussed ever since Turing. His oracle machines
answer questions with maximal uncertainty, and zero physical work, because they are oracles. They don't have to justify their answers.
His automatic machines, or a-machines, are what we now call standard TM. In the probabilistic
version, there is no new class of functions that we can compute which we cannot compute with deterministic TM.
The Probabilistic TM can decide which route to take depending on probabilities assigned to its transitions. In the simplest case of binary branching at every state and total random choice, it flips a coin about which route to take.
We know that in doing so we don't get anymore computable function than what we get with nondeterministic TM, but we might get to some answers more quickly.
PAC idea, however, changes things. 1-epsilon is the amount of uncertainty a PAC problem solver can tolerate in calling a solution 'approximately' correct. If epsilon=0, then you get maximal tolerance.
How this idea can be related to Turing's oracle, and to relation between certainty and amount of physical effort.

An oracle access to a random oracle can simulate the effect probabilistic TM's have. However, oracle machines aren't limited to using a random oracle, you can specify whatever oracle you would like, to any problem - no matter how hard the problem is, and a TM with an oracle access to it would solve it in constant time.
So, in this line of thinking - an oracle machine can be thought of as a really general extension of the probabilistic case.
I don't know if this answered your question, but I hope I managed to help a little!


AVL Tree rotations : How to balance below AVL Tree with imbalance at root node How to balance this AVL tree after inserting node 5, using left/right rotations as indicated in the AVL tree tutorial. I have tried applying both double rotations but with no luck. Either of the double rotations still ends up producing a tree with imbalance as indicated above.

Do you mean the below solution?

Oh, my goodness. That AVL tree tutorial at tutorialspoint is so misleading that it is the reason why you became confused. Please ignore that tutorial.

Please study the AVL tree insertion article at GeeksForGeeks instead. Or check some textbook such as Introduction to Algorithms by By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. This recommendation should be one of the best help you can get from asking a question.

In the graph you last uploaded, https://i.stack.imgur.com/0HivT.png, the change from the first tree directly to the last tree is called a right rotation by almost every textbook, tutorial and articles I have seen. The tree in the middle never appears. The tree in the middle is just an extra unnecessary distracting step.


Find rectangle of minimum area where dimensions are larger than minimum Problem: Given a collection $S$ containing $|S|=n$ rectangles defined by dimensions $(x,y)\in R^2$ (width and height of rectangles are real numbers), find the rectangles with the minimum area ($A_i = x_i * y_i$) where $(x_i \geq a)$ and $(y_i \geq b$) for any $(a,b) \in R^2$.

The naive solution $F(S,a,b)$ will solve this with $O(n)$ runtime complexity and $O(1)$ memory complexity: loop through all the rectangles that are larger than the minimum required values $(a,b)$ for $(x,y)$, remember the one with the smallest area $x*y$ and return that. This requires no preparation or indexing of any kind, just a simple loop (sorting according to area beforehand won't improve the $O(n)$ worst-case runtime complexity).

Can this problem be solved with an algorithm with faster than $O(n)$ runtime complexity and up to O(n) memory complexity?

One simple solution uses k-d trees. In preprocessing, prepare a sorted list $L$ of $x_i y_i$ as well as a three dimensional k-d tree $T$ storing the points $(x_i,y_i,x_iy_i)$; this can be done in time $O(n\log n)$ and takes up space $O(n)$. Given $a,b$, we do binary search on $L$ to find the least $c$ such that $T$ contains a point $(x_i,y_i,x_iy_i)$ with $x_i \geq a,y_i \geq b,x_iy_i \leq c$; each such query takes time $O(n^{2/3})$, for a total query time of $O(n^{2/3}\log n)$.

It's not clear whether we actually need a three dimensional k-d tree; if a two dimensional one suffices, then the running time could get down to $\tilde{O}(n^{1/2})$.


Why is the assumption in the max heapify procedure crucial to its implementation? While watching MIT's 6.006 Lecture # 4 which is on heaps and heapsort, the professor was explaining why the time complexity of the max_heapify procedure is $O(\lg n)$. It's quite intuitive that it's bounded by $\log n$. But there's a lurking reason also, that affects the implementation, and that reason was the key assumption which has imposed to the procedure, namely the trees rooted at left(i) and right(i) are max heaps. Why is that? Why the assumption plays a role in its implementation? Is it even necessary?

Heaps support several operations. Among them is the operation of extracting the maximal element. Heaps are constructed so that all supported operations have low complexity. In particular, in order for us to maintain the property that the maximal element is at the root after extracting the maximum, we need the left and right subtrees to be max-heaps as well.

There are other data structures which handle this differently, such as self-balancing binary trees, but these tend to be more complicated, and as a result slower in practice (even though they have the same asymptotic complexity).


Can choice function in SHA algorithm be used in a simplied way? While going through the official documentation SHA algorithms from NIST here.
There is a choice and Majority function used.
Maj(,,)=(∧)⊕(∧)⊕(∧)
Ch(,,)=(∧)⊕(¬∧)
Can I use Ch (or Maj) function in a simplified version?
eg:
(x^y)⊕(¬∧)
=(x^y)^ ¬(¬∧) + ¬(x^y)^ (¬∧)
=(x^y)^(x + ¬z) + (¬x + ¬y)^ (¬∧)
can be further simplified as
(x^y) + (¬x ^z)
can above simplified version be used ??

I'm not familiar with the details of SHA but
if we interpret $0$ as false and $1$ as true, then $a+b$ and $a \oplus b$ only differ when $a=b=1$.
In your specific case $(x \wedge y)$ and $(\neg x \wedge z)$ cannot both be true.
This is easy to see since you would need to simultaneously have $x=1$ and $x=0$.
It follows that  $(x \wedge y) \oplus (\neg x \wedge z)$  and $(x \wedge y) + (\neg x \wedge z)$ are equivalent. The same holds true if $x$, $y$, and $z$ are binary numbers and $\neg$, $\wedge$, and $\oplus$ are interpreted as bitwise operators.
This equality does not hold for the case of $\text{Maj}(x,y,z)$, as you can check by setting $x=y=z=1$.


How to find all paths of length up to k between two nodes in a directed graph? Let's say I have a directed graph represented as an adjacency matrix, and I'm given two nodes $u,v$ and a parameter $k$. Let's also say that the maximal degree of a node in the graph is $d$.

What is the most efficient algorithm to find all paths of length $<=k$ from $u$ to $v$?

I know the number of such paths can be calculated efficiently using Dynamic Programming approach, but I'm looking for an algorithm that allows to get a set of actual paths.

It's clear that such algorithm would have a factor of the number of paths in its time complexity, which has $k$ in the exponent, but still, I would like to know what is the best approach for such a problem.

I'm not sure whether "best" is answerable, but I will describe one simple strategy that appears reasonable.  Let $S(u,v,d)$ be the set of all such paths of length $d$.  Then

$$S(u,w,d+1) = \{u \leadsto v \to w \mid u \leadsto v \in S(u,v,d), v \to w \in E\}$$

Also $S(u,u,0) = \{u \to u\}$. This gives a dynamic programming algorithm for computing the set of all such paths, if you evaluate these sets in order of increasing $d$.

As an optimization, you can delete all vertices that aren't reachable from $u$ or that can't reach $v$ before beginning this computation.  As another optimization, you can precompute the matrices $A^k$, where $A^k_{uv}=1$ if there is a path of length $k$ from $u$ to $v$ (these can be obtained from the adjacency matrix by repeated multiplication); then you only evaluate $S(u,w,d)$ for $u,w$ such that $A^d_{uw}=1$ and $A^{k-d}_{wv}=1$.

With these optimizations, if there are a total of $Q$ such paths that you want to output, then the running time will be at most $O(kQ \cdot |E|)$.  There's not much opportunity to do much better than that; obviously any algorithm must take at least $\Omega(Q)$ time, and since $Q$ will typically be exponentially large compared to $k|E|$, the gap between the upper and lower bounds will typically be a small factor compared to the total running time.


Is the language of Roman numerals ambiguous? An ambiguous Language is a formal language for which there exists a string that can have more than one meaning (several possible meanings or interpretations). Multiple synthesis structures for a string.

[Question]
Are Roman numbers an example of an ambiguous language?

Because there can be more then one representation for some number such as 1999, which
can be written as MDCCCCLXXXXVIIII, MCMXCIX, or MIM.

I am confused. Sometimes I feel not, some time yes!

EDIT
[ANSWER]

Although there can be more than one representation of same magnitude in Roman Number System. That is basically Non-Positional Number System. But its possible to write Unambiguous Grammar for that can generate all possible/valid pattern in Roman Number System.

Here is again a beautiful link that describe symbol table, rule  , Grammar for Roman number.

I am not sure about this but some authors says that: "Roman numbers can be recognized by a regular expression, so you don't really need a context-free grammar." and a regular language can't be ambiguous.

A grammar (not a language!) is ambiguous if there is a word with two "essentially different" parses. Roman numerals are unambiguous - given a roman numeral, it has an unambiguous numerical value. The fact that this correspondence is not one-to-one is beside the point.


Is there a strictly non-deterministic one-counter language whose complement is one-counter? Let
$A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$

Clearly, $\text{Deterministic one-counter} \subseteq A$

Is it the case that $ A = \text{Deterministic one-counter}$?

I know that for context-free languages the analogue is not the case. For example,
let $P =\{ ww^r\}$.
Then both $P$ and $\bar{P}$ are context-free but $P$ is not deterministic.
Hence $A$ defines a (strict) subset of the context-free languages.

The question is: can we construct a similar one-counter example for which the same holds?

In response to Shaull's comment above :

The first one is an image of 1-counter accepting $a^ib^j$ s.t. $j<i$

The secong one is an image of 1-counter accepting $a^ib^j$ s.t. $j>i,\ j<2i$

The third one is an image of 1-counter accepting $a^ib^j$ s.t. $j>2i$

Here a/-/plus means on seeing a, irrespective of the counter value, increment the counter.
b/>1?/sub means on seeing b, if counter value is greater than 1, then decrement the counter.

nop =>  no operation

$\lambda $ => empty string


What are some problems in the class P which we used to think were in the class of NP? I was recently watching a video on the classes of P and NP, in which it was claimed that there have been 'several' problems that were presumed to be in the class of NP, which have since been shown to be in the class of P. Unfortunately, no examples of such problems were given. Could anyone verify this statement by providing an example of such a problem?

Consider the following problem $A$: given $n$, is $n$ a composite integer (i.e., not a prime)?

It is easy to prove that $A$ is in NP: any nontrivial divisor acts as a certificate.

Proving that $A$ is also in P is much harder, and it is equivalent to proving that its complement, i.e. primality, is in P as well. Still, this has now been proved.


Do all programming languages adhere to the IEEE 754-2008 standard? I am well aware that the float data type's maximum value is approximately 1.8E308, which means that across the various programming languages such as dearly beloved Java, the maximum factorial we can compute with this primitive data type is that of 170. Trying to compute the factorial of 171 and beyond gives errors. Here, PHP behaves the same way. In one of the answers from here, JavaScript also poses problems with factorials greater than 170. I understand that all this happens because that is what the de facto standard defines. My question is, are there non-esoteric programming languages that don't adhere to the IEEE 754-2008 standard? If there are, it would be interesting to see how they deal with factorials.

For example, C and C++ don’t adhere to it. They don’t define the details of floating point arithmetic. An implementation may adhere to that standard, and there is a standard way to inform the user about it.

I used one compiler with ieee compliant 32 and 64 bit floating point, and totally non-compliant 128 bit fp with roughly 105 bit mantissa.


Is there a way to test "Turing completeness"? I asked my algorithms teacher today the very same question that is stated in the title, but he seemed a bit unsure, either on the question or on the concept, so I thought I'd try here too.

Is there a minimal test that could determine whether a language or instruction set is Turing compete, or does a test of that sort fall into the domain of undecidability?

It might seem like a trivial or stupid question, but the reason I ask is that it would be a good way to test whether the instructions of a cellular automaton is Turing complete, and if there is such a test, maybe it could help when generating cellular automata.

I'm quite new to both cellular automata and undecidability problems, so go easy on me.

I don't know about specific models. It's pretty easy to become Turing Complete, since all you need is infinite search. So I can imagine a model where searching for finite vs. infiniteness boils down to Turing Completeness, but I don't know if any actually exist.

But a general algorithm "look at an arbitrary systems and tell if it's Turing Complete" can't exist. Otherwise we could do this:

RunTuringMachine = lambda (M1) . lambda (x). lambda (M2) .
  run M1 on x and discard the result
  run M2 //we only get to this line if M1 halts on x

Then, for any inputs M1, x, RunTuringMachine M1 x is a Turing-complete system if and only if M1 halts on input x, and we've solved the halting problem.

We could also prove this by Rice's theorem: if we can decide if any system is Turing Complete, then we can decide of a Turing Machine is a Universal Turing Machine, which is impossible by Rice's Theorem.


Canonical representation of programs I'm working on some compiler software, and I'm looking for information on canonical forms for expressing software, algorithms, mathematical expressions (including predicate logic), etc. I assume canonicalization is generally intractable, but NP algorithms and more-constrained problems (e.g. pure functions) are also interesting. Normal forms may be useful too. My goal is not to be able to represent and manipulate all programs, but some of them (the trivial ones).

The brief survey contained in this paper might be of interest:

J. Swan, Z. A. Kocsis, and A. Lisitsa. 2014. The 'representative' metaheuristic design pattern. In Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO Comp '14). ACM, New York, NY, USA, 1435-1436. DOI=http://dx.doi.org/10.1145/2598394.2609842.

It discusses the existence of canonical forms for various forms of representation (groups, rings, boolean functions etc) and in particular normal forms for the lambda calculus using $\beta$-reduction as a rewrite rule.


Finding the smallest string that contains a given set of substrings The algorithm I am looking for has the following requirements: Input is a set of strings. You are looking for a string containing all input strings. The resulting string should be as short as possible. At least shorter than just concatenating all input strings if possible.

Examples:

Input: a ab bc
Output: abc

Input: abcd bcde ef
Output: abcdef

Is there a name for this problem with which it is better to search for solutions?

This problem is called shortest superstring problem. John Gallant, David Maier and James Astorer proved it is NP-hard in 19791.

Given two strings $A$ and $B$, let $|A|$ denote the length of $A$, and let $S(A,B)$ denote the shortest superstring of $A$ and $B$ where $A$ occurs before $B$. It is easy to reduce this problem to travelling salesman problem, where nodes represent strings, and the distance from string $A$ to $B$ is $|S(A,B)|-|A|-|B|$. So you can use known algorithms for travelling salesman problem to solve this problem.

There are several polynomial approximation algorithms. The best known approximation factor is $2\frac{11}{23}$, and the corresponding algorithm is proposed by Marcin Mucha in 20132.

1Gallant, J., Maier, D., & Astorer, J. (1980). On finding minimal length superstrings. Journal of Computer and System Sciences, 20(1), 50-58.

2Mucha, M. (2013, January). Lyndon words and short superstrings. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms (pp. 958-972). Society for Industrial and Applied Mathematics.


Why can't configuration counting decide undecideable problems? I know it might sound like a silly question, I just can't get my head around it...

I just read that $DSPACE(f(n))\subseteq DTIME(n\cdot 2^{O(f(n))})$.
The proof for it relies heavily on the fact that for a given $L\in DSPACE(f(n))$, the turing machine $M_L$ (which decides $L$ while consuming no more than $p(|x|)$ memory space for some polynomial $p$ and input $x$), under the assumption that it decides $L$, cannot have the same exact configuration twice (otherwise it's stuck in an infinite loop), and therefore, we can bound the runtime of $M_L$ by counting the number of possible configurations, which is $n\cdot 2^{O(f(n))}$.
The thing is this;
If ($M_L$ decides $L$) $\Rightarrow$ (There are no two similar configurations in $M_L$)
Why doesn't (There are two similar configurations in $M_L$) $\Rightarrow$ ($M_L$ won't decide $L$)?
Why can't configuration counting decide $A_{TM}$, for example? ($A_{TM}=\left\{(M,w)|M(w)=ACCEPT \right\}$)

Configuration counting can certainly detect infinite loops. But only if space is bounded. A TM could write non-repeating nonsense on the tape and never get caught.


How can ships in Battleship be partitioned into B subsets, each with a capacity C? I have been doing some research on the reduction of Battleship to bin-packing, but I do not completely understand the input to the problem from this academic paper: http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf
The paper states that the input would be an array of positive integers (the items), C (an integer capacity), and B (an integer number of subsets). The question that is posed then becomes: can the items be partitioned into B subsets, each of which has total capacity C? How is this even guaranteed to be possible? For example, if the total size of 6 ships is 19, it seems actually impossible to partition them according to the requirements of the problem? Maybe I am just understanding the reduction wrong. Any ideas?

The idea is to reduce the bin packing problem to battleship, not the other way around.

The variant of bin packing they use in the paper is to decide if it is possible to partition $n$ numbers into $B$ subsets (the bins) so that the numbers into each subset add to a quantity $C$.

Example:

Input:

The set $\{2,3,5\}$ , $B=2$ and $C=5$

Possible solution:

Two subsets $1$ and $2$:

$1 = \{2,3\}$

$2 = \{5\}$

This problem can be reduced to battleships  in the following way:

Create a board of width $B \times 2$ and height $S + n$ , where $n$ is the cardinality of the subset we are going to partition and $S$ is the sum of all the elements of the multiset we want to partition.

Then for each pair of columns that belong to each bin, we set the number that the  first column should ammount to $0$ and the other one to $C$. These numbers are the number of pieces of a ship that there should be in each column.

For the rows:
For each number $a_i$ that belongs to the multiset that we want to partition, we have a separator row with a value of $0$ and $a_i$ rows with a value of $1$. These numbers make reference to the number of boat pieces that there should be in each row.
For each row that belongs to a number, we have only a ship piece because we want each of the $a_i$ numbers to be covered by a single ship of that size.

So in one column of each column pair we will have a separator row and a vertical strip of $a_i$ rows of height for each number of the multiset we have to partition. We can cover that strip with a ship or not, but we have to cover enough strips of a column so that the number of ship pieces of that column adds to exactly $C$.

Because a picture is worth a thousand words i made a picture of a solved example board that we obtain by reducing an instance of bin packing to battleship

The instance of bin packing that i'm going to use as an example is:

The set $\{2,3,5\}$.

$B=2$

$C=5$

The shaded squares are squares that are occupied by a boat.

Thanks for bringing my attention to this problem, i didn't know it.

Hope this is helpful.


Maximum One Third Cut I want to solve the following problem (This is a homework problem. Not looking for definite or complete answers):
Maximum One Third Cut:

Input: An undirected graph G=(V,E) where V={1,2,...,n}, such that |V| is divisible by 3, and a positive integral weight function w:E to N (on edges).
Goal: Fin a subset of vertices U subset of V such that |U|=|V|/3.
Objective: Maximize the total weight of the edges between U and its complement.

Of course, you can do that using a full search of all the possiblities. I want a more efficient algorithm though.
I'm thinking about some sort of Local Search algorithm, like Steepest Ascent Hill Climbing (SAHC), or a variation thereof (Simulated Annealing, Random Restart etc.).

States:
Could be a binary vector, where the i-th element represents whether the vertex i is in U or not (0: not in U, 1: in U), where the number 1-s is |V|/3.
Successors:
Turn one bit off, turn another on.
Heuristic Function:
Sum of all weights of edges between U and V\U. Could be computed when generating a successor, you only need to check the vertex removed and added. Perhaps states can contain a list of edges that are relevant.
Other Parameters:
Like Temprature or amount of restarts allowed could be set by testing the algorithm on graphs of varying in size, weight function and edges, and choosing the best values.

I was also thinking about Evolutionary Search.
Am I on the right track here? Are there better options perhaps?
Any suggestions would be much appreciated.Thanks!

Great project!  There are many possibilities.  I suggest reviewing the approaches listed in Dealing with intractability: NP-complete problems and trying as  many of them as possible to see which tends to work best on the kinds of graphs you have to handle in your class.  It will be a fun learning experience, where you get to learn about multiple techniques and get some experience with them.

At minimum, I'd recommend trying some form of local search, such as hill climbing and/or simulated annealing. I have rarely seen situations where genetic algorithms outperform other forms of local search.  I'd also recommend trying integer linear programming (ILP) or possibly MaxSAT.


Bytes addressable processor In MIPS processor, address bus is of 32 bits. So on addressing an instruction, a whole 32 bit instruction is fetched. How is it byte addressable then? I mean if on addressing a particular address, the memory sends 32 bits as a wholesome, how is it byte addressable?

"Byte addressable" means that a 32-bit address points to a single byte of memory, so if you increment that address, it points one byte further.

"Word addressable" means that (on a 32-bit processor) every 32-bit address points to a 32-bit word, so if you increment that address, it points four bytes further in memory.

Some machines can support both byte addressable and word addressable modes of operation.  But for the naming, we're concerned with the smallest unit they can address.


adding an edge, Is T still a MST to the new graph? Suppose I have a minimum spanning tree $T$ in a graph $G=(V,E)$ with positive edge weights $w$. Provide an algorithm that after adding a new edge $e$ with a unique weight $w(e)$ to $G$, returns true if $T$ will still be an MST.

Let $n=|V|$ and $e=(x,y)$ be the new edge. Let $P$ be the unique path between $x$ and $y$ in $T$. Clearly $C = P + e$ is a cycle in $G+e$.

Let $f^* = \arg\max_{f \in P}{w(f)}$. $T$ is an MST of $G+e \iff w(e) \ge w(f^*)$.

The $\Rightarrow$ part:
If $w(e) < w(f^*)$ then $T - f^* + e$ is a spanning tree of $G+e$ of cost $w(T) - w(f^*) + w(e) < w(T)$, showing that $T$ cannot be a MST of $G+e$.

The $\Leftarrow$ part:
If $w(e) \ge w(f^*)$ then $e$ is one of the heaviest edges of $C$ and, by the cycle rule, there exists a MST of $G+e$ that does not include $e$. In particular, any MST of $G$ will also be an MST of $G+e$ (the converse is not true in general, but it is in your case since you also know that $w(e) > w(f^*)$ and hence no MST of $G+e$ can contain $e$).

A reasonable representation of $T$ will allow you to find $P$ (and hence $w(f^*)$ in time proportional to $|P| = O(n)$).

If you can preprocess $T$, then you can do better. For example you can build a lowest common ancestor (LCA) oracle in $O(n)$ time to find in constant time the LCA $z$ between $x$ and $y$. Then $w(f^*)$ will be the maximum weight between the two heaviest edges in the unique paths in $T$ from $x$ and $y$ to $z$, respectively.
These edges can be found in $O(\log n)$ time after a $O(n \log n)$ time preprocessing. For each vertex $v$ of the tree, and for each $i=1,\dots,\lceil \log n\rceil$ store:

the farthest vertex $u_v^{i}$ in the path from $v$ to the root of $T$, such that $u$ is at a distance of at most $2^i$ from $v$ in $T$; and
the heaviest edge $e_v^{i}$ in the unique path from $v$ to $u_v^{i}$ in $T$.

To report the edge $M(x,z)$ of maximum weight between a vertex $x$ and an ancestor $z$ of $x$, let $\ell$ be the largest power of $2$ that is smaller than or equal to the distance in $T$ between $x$ and $z$. Return the heaviest edge between $e_v^i$ and $M(u_v^{i}, z)$ (if $u_v^{i} \neq z$). Notice that the distance between $u_v^{i}$ and $z$ is at most half the distance between $v$ and $z$, meaning that you will only need to look at $O(\log n)$ edges.


Can we understand SVM without knowledge of Machine Learning I was told by my adviser (future one) to look into libsvm library or any other and try to get familiar with it.. to work on a programming project (on Machine Learning) (will start in a month).

my background: Programming knowledge in Python, C.. doing Java now.

So, where should I probably start? and How long it takes me to get into ML, SVM etc.. and be productive? Would I probably fit for this project? --considering my programming background (I so far have been much into Web development, wanted to take a change and have fun)

I don't think there is anything that should stop you. A couple of tips to set you on the right path:

The basic principles of Machine Learning are very simple. They are often formalized in a way that makes it look very complicated, but this is only necessary if you want to get into the details of why things work. The general framework of what makes a classifier or what makes a clustering algorithm is very simple. Make sure you understand things on that level, before you dig into the details.
The title question (can SVMs be understood without ML knowledge) is slightly non-sensical. Understanding the basic ideas of ML is a minor investment and understanding SMVs takes much longer. There's no reason not to get a basic idea of what machine learning is before you dig into SVMs.
Make sure you have a good intuitive undertanding of the following principles and distinctions: features and instances, clustering and classification, supervised and unsupervised learning. After that, SVMs are just one particular way of solving a particular problem.
If you understand what a classifier is, you can start using SVMs without knowing anything about how they work or what they do. This may not give you the best result, but it's a good way to start learning by doing.

I can't really give you any references to start reading, since most of what's out there is far to formal for the level you'd want to start with. I recommend browsing around. If something is easy to read, then continue on, if it's too full of math, try something else first.


Does the state of a cell in cellular automata has to be from a finite set? In most (all I have seen) work on cellular automata, the state of a cell is from a finite set. Such as a cell can take value from a binary set, or from among few colors. Can we define the state to be something more complicated such as a function of the coordinates of the neighbor cells? (assuming there is a initial coordinate value give to at least one cell) So for example in 2-D if my neighbor to the left has coordinate $(x,y)$ my state will take a value $f(x,y)$ where $f$ is same for all cells.

Although Wikipedia mentions a finite set of states (http://en.wikipedia.org/wiki/Cellular_automaton), I'm sure you could find some interesting models that use infinitely many states. As you suggested, each cell could contain an integer, a continuous value between 0 & 1 (shade of grey), etc.

The idea of basing cell contents upon cell coordinates is interesting and unfamiliar. Of course, you'd have to also include some other inputs in the transition function if you want the pattern to change from step to step. This would create patterns that vary based on their location, which sounds fun to explore.


Give an example of a language whose Myhill-Nerode equivalence relation is such that if $x,y \in \{0,1\}^*$ with $x \neq y$, then $[x] \neq [y]$ Suppose $\Sigma = \{0,1\}$.  Provide an example of a language $L \subseteq \Sigma^*$ with the property that its associated Myhill-Nerode equivalence relation, $R_L$, is such that every one of its equivalence classes is a singleton set; that is, if $x,y \in \Sigma^*$ with $x \neq y$, then $[x] \neq [y]$, where $[x]$ and $[y]$ are equivalence classes with representative elements $x$ and $y$, respectively.

I suspect that this language cannot be regular, since the index of $R_L$ is infinite.

Consider the language $L$ consisting of words $w a 0 1^n$ where $w$ is an arbitrary word, $a$ is either 0 or 1, $w$ has at least $n$ letters and the $n$-th letter of $w$ is $a$. Clearly, given a word in $L$ there exists exactly one decomposition to this form (define $n$ to be the number of trailing ones in the string).

If $w \neq u$ then without loss of generality $w_i = 0, u_i = 1$ for some $i$. But then $w 0 0 1^i \in L$ while $u 0 0 1^i \notin L$. If $w$ is a prefix of $u$, then you can take $n$ which is larger than the length of $w$ but smaller than length of $u$.

In other words $L=\{v a u a 0 1^n : |v| = n-1, |a| = 1\}$; clearly this is a CFL.

(This is a variant of my answer from Can a language have $\Sigma^{*}$ as its syntactic monoid?)


Which fingerprinting/hashing algorithms support compounding? The definition of fingerprinting algorithms in Wikipedia describe a property called compounding as you can see here as:

  Some fingerprinting algorithms allow the fingerprint of a composite file to be computed from the fingerprints of its constituent parts.

I suspect compounding is not a commonly used term for describing this capability. I have failed to find any other algorithm that allows

hash(x + y) = hash(x) + hash(y)

Wikipedia is not always the most reliable source of information but the article for fingerprinting seems to imply that there are algorithms other than Rabin's fingerprinting method that support compounding. I'm probably not using the right terms for search but I could not find any.

So are there any hash functions (or fingerprinting algorithms) out there that supports this property?

This falls into a general class of hash functions known as homomorphic hash functions.

Your question is not entirely clear about what definition you are using for $+$.  If you want the hash function to satisfy $h(x+y)=h(x)+h(y)$ where both instances of the $+$ operator refers to addition in a suitable group (e.g., addition of integers, xor), then such a hash is called linear.  A CRC hash is an example of a linear hash function.

It's important to distinguish concatenation from addition.  If you are looking for a hash that satisfies

$h(x||y) = h(x)+ h(y)$,

where $||$ denotes concatenation and $+$ denotes addition, then that's a different beast.  I don't know of any standard name for it.  This is a very restrictive property.  Such hash function will always necessarily have the form

$h(x) = \sum_i h(x_i),$

where $x_i$ is the $i$th character of the string $x$.  Consequently, the only way to achieve such a property is as follows: you choose some lookup table that maps from a single character to an integer; then you apply this to all the characters in the string and sum them up.  Unfortunately, such a hash is less than ideal, as a hash function, as any two strings that have the same characters in a different will yield the same hash value.  Thus if you use this as a hash function for a hash table, you might find an increased rate of collisions.  However, it would be easy to construct such a hash function.

There are other generalizations.  For instance, maybe you want a hash function with the property that

$h(x||y) = F(h(x), h(y))$

where $F$ is some associative function.  There are standard constructions of such a hash.  For instance, CRCs achieve this (though here $F$ depends on the length of $x$).

I suggest you also look at rolling hashes, the Rabin-karp rolling hash, Buzhash, AdHash, and MulHash.  See also the following resources:

https://crypto.stackexchange.com/q/17935/351
https://crypto.stackexchange.com/q/11420/351
the answers to https://crypto.stackexchange.com/q/1558/351


What kind of languages can be recognized by a restricted one-tape deterministic Turing Machine? During a lesson, our TA asked:

  What kind of languages can be recognized by a deterministic Turing
  Machine such that we can use only a tape portion that contains the input?

My thoughts:
my Theory of Computation book says that there is a special TM called linear bounded automaton (LBA) that corresponds to a non-deterministic Turing Machine that has a limited tape. Such machine recognize Context Sensitive languages.

So if i simulate the LBA behavior starting from a deterministc TM, may I recognize "deterministic"-Context Sensitive Languages?

It's famously unknown whether deterministic and non-deterministic LBA accept the same set of languages.


Analysis of Algorithms: Applying Concepts I believe I understand the concepts of algorithm analysis. However, I'm not fully confident in applying those concepts. I'd appreciate help in bridging the gap between concept and application.

I understand that if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$ then $f(n) \in \Theta(g(n))$

Essentially, when Big-O and Big-Omega form the upper and lower bounds of algorithmic performance, Big-Theta represents the optimal solution. But how does one determine those bounds and thus optimal performance?

How does/should one determine Big-O, Big-Omega, Big-Theta for the following algorithm?

int summation(int[] values)
{
  int sum = 0;
  for(int i = 0; i < values.length; i++)
  {
    sum += values[i];
  }
}

Typically, when presented with a piece of code, your first step is to come up with a formula which gives the running time $T$ of your code as a function of the input size. In your example, the function takes an array, so a natural way to represent the input size is the number of elements in the array, values.length, which we can call $n$.

So, we now want an expression for $T(n)$. To get this, we should assign a "cost" to each statement, and then determine how many times each statement is executed. The costs are somewhat arbitrary and may vary across real computer hardware, but some assumptions can reasonably be made; in particular, we usually assume simple statements have a constant cost with respect to the input size. In your example, we might assign costs like this:

int summation(int[] values)
{
  int sum = 0;                       // cost = A, executed once
  for(int i = 0;                     // cost = B, executed once
      i < values.length);            // cost = C, executed n + 1 times
      i++)                           // cost = D, executed n times
  {
    sum += values[i];                // cost = E, executed n times
  }
}

Now, to get the expression for $T(n)$, multiply each statement's cost by the number of times it's executed. Here, we get $T(n) = A \times 1 + B \times 1 + C \times (n + 1) + D \times n + E \times n$. This comes out to $T(n) = (A + B + C) + (C + D + E) \times n = c_0 + c_1n$ for constants $c_0, c_1$.

In this example, happily, we have a closed-form expression for $T(n)$. As such, we can make an educated guess that this function is $\Theta(n)$, since $T(n)$ is a linear function. To prove this is true, we can try to prove it's both $\Omega(n)$ and $O(n)$.

By definition, $T(n) = \Omega(n) \iff \exists c > 0, n_0 \ge 0 \mid n \ge n_0 \rightarrow T(n) \ge cn$. Our job now is to demonstrate that there is an $n_0$ and $c$ such that $T(n) \ge cn$ for all $n \ge n_0$. We have $c_0 + c_1n \ge cn$ for fixed constants $c_0, c_1$. We can solve this for $c$: $c \le c_0/n + c_1$. As long as we choose $c$ less than $c_0/n + c_1$, we have a valid choice for $c$; in particular, if we choose $c = c_1$, we satisfy the inequality for all natural numbers, and can choose $n_0 = 0$.

You can make a very similar argument for $O$; try choosing $c = c_0 + c_1$ in this case and complete the argument yourself. Once you know it's both $\Omega(n)$ and $O(n)$, you can conclude that it's $\Theta(n)$.

Of course, you don't really need to find the constants every time, but it can make an argument pretty convincing. If your $T(n)$ comes out to a expression which is the sum of powers of $n$, then you will always have that $T(n) = \Theta(n^x)$, where $x$ is the highest power to which $n$ is raised.

This gets significantly harder when $T(n)$ is recursive, i.e., when the expression for $T(n)$ involves $T$ itself; to solve problems like that, you'll often need to avail yourself of the Master Theorem or inductive proofs on the input size. Cross that bridge when you come to it, though.


Why is this n^2 growth? I am attempting to understand the growth of the following algorithm, which is described as $n^2$ growth in the book I am reading:

"... performs of the order of $n^2$ steps on a sequence of length $n$."

Could someone please explain how this is calculated in the following code, which is also taken from the book?

If I print out the statements when the lines are executed, it first executes $n$ steps, then decreases $n-1$ steps for each loop iteration until it reaches $0$. This does not seem like exponential growth to me. Why does this grow at $n^2$?

dataset = [3,1,2,7,5]
product = 0

# algorithm begins here
for i in range(len(dataset)):
  for j in range(i + 1, len(dataset)):
    product = max(product, dataset[i]* dataset[j])

Because $n + (n-1) + (n-2) + \cdots + 2 + 1 = \frac{n(n+1)}{2} \in \mathcal{O}(n^2)$.

Note that $n^2$ is polynomial, not exponential (that would be $2^n$ for example).


How did it happen that Algol 60 was an improvement on its successors? The original statement referred to by this question is:

  The more I ponder the principles of language design, and the techniques which put them into practice, the more is my amazement and admiration of ALGOL 60. Here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors.

(From the appendix of a very readable report on programming language design by C. A. R. Hoare. I read that report because I wanted to ask this question, not the other way round. Reading that report made it clear to me that the original statement is even more true than I thought when I decided to ask this question.)

The intention of this question is to better understand the sociological and political aspects of the events, not the detailed technical merits. The politically accepted successors of Algol 60 (at the time) like Algol 68, PL/I or Ada were badly feature bloated, while really improved successors like Algol W or Simula were never widely used. The surviving members of the Algol language family seem to prefer naming Pascal as their great-grandfather instead of Algol, even so Pascal seems to be just another descendant of Algol. (C or Smalltalk are not descendants of Algol, because their syntax and underlying principles are too different. C++ on the other hand might be considered as a legitimate descendant of Simula, embodying many of the same underlying principles, adopting the C syntax and legacy only for political reasons to avoid the fate of the Algol like languages.)

An account of the history of types in programming languages made me realize that even the type system of Algol 60 was still quite unfinished. It seems that it would have been easy to just finish the type system and fix some other minor annoying details for the next revision of the language. But instead... ???
Most of my math books use Algol for their pseudocode, and it looks much nicer than the C pseudocode in the few books that don't use Algol. So I always wondered why Algol actually died.

I always felt like the reason is expressed by Alan Kay in his OOPSLA 1997 keynote, when he talks about Dijkstra's paper. I am not taking sides here but the tension expressed there seems to be prevalent in politics of CS, when it comes to Europe vs America. Algol represents European way of doing CS, and really most of the code was written in America. So no one really wrote any big system in Algol, thus it died.

But, I am an outsider to both cultures so, take this with a huge grain of salt. Also I know that Algol 60 designers included American computer scientists as well. All in all, this is just how I feel about it, no strong arguments here.


Difference between free and global variables Is there any difference between free variable and global variable? Or they are just  synonyms? In which situations I should use one or another?

They don't play in the same category.

The notion of free variable is relative to a scope. If a variable is present in a term (i.e. a subprogram) and its scope is larger than this term, then the variable is said to be free in that term.

A global variable is one whose scope is the whole program, or the whole file, or the whole module, or whatever scope is called “global” in the programming language you're considering.


Check if two graphs are edge-disjoint Two undirected graphs $G$ and $H$ on the vertices $1,2,\ldots,n$ are disjoint if the intersection of
their edge sets is empty.
Assume  both  $G$  and  $H$  are  represented  by  adjacency  matrices.
Describe  an  efficient
algorithm that decides if $G$ and $H$ are disjoint.  What is the complexity of your algorithm?
Justify the correctness of your algorithm and your complexity claim.

What I am thinking is just picking an arbitrary vertex on either graph like $G$ and checking if we can reach a vertex from the other graph $H$ by running some simple traversal like DFS. Is there a better way? I am thinking what if we go through the adjacency matrix of one graph and check if any edge connects a vertex from one graph to the other.

The adjacency matrix $A_G$ of an undirected graph $G=(V,E)$ is defined as follows: $A_G$ is a $V \times V$ matrix, $A_G(v,v) = 0$ for all $v \in V$, and $A_G(u,v) = 1$ if $\{u,v\} \in E$ and $A_G(u,v) = 0$ if $\{u,v\} \notin E$.
Two graphs $G,H$ are edge-disjoint if there doesn't exist an edge $\{u,v\}$ which belongs to both of them. That is, $G,H$ are edges-disjoint if there do no exist $u,v$ such that $A_G(u,v) = A_H(u,v) = 1$.
You take it from here.


Quicksort T(n)=2T(n/2)+n In Quicksort we devide the array in to about an half (not worst case) and we have left and right sides so it is 2T(n/2), now why in the end it is T(n)=2T(n/2)+n as we may need to go over all the array to arrange it to left and right sides?

$T(n)$ is number of comparisons done when quicksort sorts an array of length $n$.

To sort an array of length $n$, we must split it into two halves and sort the halves.  To split the array, we must compare each element of the array against the pivot, which is $n$ comparisons.  (Perhaps $n-1$ if the pivot is an actual array value rather than, say, an estimate of the median.) Then, we must recursively sort the two halves, which requires $T(n/2)$ comparisons each.


Distribution of IEEE 754 single precision floating point over number line "What is the maximum and minimum difference between two successive
  real numbers representable in IEEE 754 Single Precision and Double
  Precision Floating Point Representations respectively?"

In order to answer this question, I am unable to visualise how Floating Points are spread over the real number line, assuming the precision of real numbers is same as that of IEEE 754 single precision & double precision respectively.
So I am looking for graphs of the following two functions based on IEEE 754 single precision representations.
$f\left ( x \right ) = \left\{\begin{matrix}
 0 & ,\text{if x can't be represented in IEEE 754 single precision.}  \\
 1 & ,\text{if x can be represented in IEEE 754 single precision.}
\end{matrix}\right.$
$f\left ( n \right ) = \left\{\begin{matrix}
d, & \text{where d is the diffrence between n-th and (n-1)th floating points representable in IEEE 754 single precision. }\\
0, & \text{if n-th or (n-1)th floating point number does  not exists in IEEE 754 single precision representations.}
\end{matrix}\right.$
Considering only normalised values and zero.
and not considering Infinities, NaN and denormalised numbers.

Could anybody please help me out with these graphs so that I can understand floating points properly.

The idea is that a (not denormalized) floating point number is stored as
$2^x \times 1.m_0 \ldots m_{k-1}$ (in binary),
where $x$ is the exponent and $m_0 \ldots m_{k-1}$ is the mantissa of length $k$. Two successive numbers with this exponent differ by $2^{x-k}$, since this minimal difference is $2^x \times 0.0\ldots01$, with $k-1$ zeroes after the dot. The minimal and maximal differences (among not denormalized numbers) are attained for the minimal and maximal $x$.


ε-NFA to DFA - initial state with only epsilon transitions I am having trouble discovering how to convert a ε-NFA to DFA (image below) when all transitions in the initial state are epsilon transitions. I already know how to convert ε-NFA to DFA (common cases), but this case I never saw before.

Thank you guys!

Here is an algorithm to convert an $\epsilon$-NFA to an equivalent DFA.

Let the $\epsilon$-NFA consist of a set of states $Q$, an initial state $q_0$, a set of accepting states $F$, and a transition function. We construct a DFA on the set of states $2^Q$ (the power set of $Q$). The initial state is the $\epsilon$-closure of $q_0$ (the set of all states in $Q$ reachable from $q_0$ by a path of $\epsilon$-transitions). A state is accepting if it intersects $F$. We define the transition function $\delta$ as follows: given a state $S \in 2^Q$ and a letter $a$, $\delta(S,a)$ consists of all states in $Q$ reachable from a state in $S$ by taking an $a$-transition followed by a path of $\epsilon$-transitions.


Is the language A decidable? Is the language $A$ decidable ?  Please help me get the proof right !!

$A = \{ \langle  M \rangle | M \text{ is } TM \text{ such that } L(M) \neq \Sigma^*  \}$

My proof is by contradiction. Assume $A$ is decidable and let $R$ be decider for it. I will construct decider $S$ for $A_{tm}$, using $R$ as a subroutine.

S = on input <M,w>
constructs M_w = on input x
 if x!=w accept
 else run M on w
  if M accepts => accept
  else => reject
run R on M_w
 if R accepts => reject
 if R rejects => accept

Note : If $M$ accepts $w$ then $L(M_w) = \Sigma^*$ , then $R$ ran on $M_w$ will reject it, and $S$ will accept.
If $M$ rejects or loops on $w$, $L(M_w) \neq \Sigma^*$, then $R$ ran on $M_w$ will accept, and $S$ will reject.
Therefore, we created a decider for $A_{tm}$, but we know that $A_{tm}$ is undecidable, our assumption was wrong => $A$ is undecidable .

I don't understand how you call $R$ from $S$. The following is a possible solution.

Let's reduce $A_{TM}$ (halting problem) to  $\overline{A} = \{ \langle  M \rangle | M \text{ is } TM \text{ such that } L(M) = \Sigma^*  \}$ instead of $A$, since decidability of $\overline{A}$ would imply decidability of $A$.

First note that $M_\emptyset (\text{ TM accepting nothing )} \notin$ $\overline{A}$ and it is clearly that $\overline{A}$ is not empty since a TM machine simply accepting any string is in $\overline{A}$, so let's choose $M_1$ from the set $\overline{A}$ and let $L_1$ be the language recognizable by $M_1$.

For any $\langle M, w \rangle$ construct a new TM $M'$

  M'(x)
   Simulate M on w
   If M accepts w then run M_1 on x
   If M_1 accepts x then ACCEPT

Now let's show the reduction:
$\langle M,w \rangle \in A_{TM} \Rightarrow M \text{ accepts } w \Rightarrow M'$ accepts $x$ exactly when $M_1$ accepts $x \Rightarrow L(M') = L_1$ which implies $\langle M_1 \rangle \in \overline{A}$. So we have obtained

$$\langle M,w \rangle \in A_{TM} \Rightarrow \langle M' \rangle \in \overline{A}$$

Similarly, $\langle M,w \rangle \notin A_{TM} \Rightarrow M \text{ does not accepts } w \Rightarrow M' \text{ accepts no string } \Rightarrow L(M') = \emptyset $ which implies $\langle M' \rangle \notin \overline{A}$. So we have obtained
$$\langle M,w \rangle \notin A_{TM} \Rightarrow \langle  M' \rangle \notin \overline{A}$$

Now if $\overline{A}$ were decidable then on any input $\langle M, w \rangle$ we could construct $M'$ as above and decide if $M$ halts on $w$ by checking $\langle M' \rangle \in \overline{A}$.

Finally, the general case of the proof above is known as the Rice's theorem, which you could apply directly to prove that $A$ is not decidable.


What is the point of delimiters and whitespace handling I see that language specifies reserved words, delimiters and whitespaces in the lexer section. Are delimiters just like reserved identifiers in the punctuation space or they have additioinal function regarding skipping the whitespace?

Namely, spec says

  Each lexical element is either a delimiter, an identifier (which may
  be a reserved word), an abstract literal, a character literal, a
  string literal, a bit string literal or comment. In some cases an
  explicit separator is required to separate adjacent lexical elements
  (namely when, without separation, interpretation as a single lexical
  element is possible). A separator is either a space character (SPACE
  or NBSP), a format effector, or the end of a line.

I also see a definition

relative_pathname ::= { ^ . } partial_pathname

where . is a delimiter but ^ is not. I do not understand why the difference. Moreover, ^ is a special character that can be only a part of "string literal", 'char literal' or /extended identifier/ and I don't understand how to deliver this character to the path parser.

Anyway, I wonder what to do with pieces of text smashed to each other like 11'c' or "this is string litral"with_some_identifier. Mine current lexer produces string_literal followed by identifier. However, I feel that others don't do that. What is the common practice for lexing and whitespace skipping -- when whitespace is it mandatory and when is it optional? How do you specify that to the parser/lexer?
I ask because do not see that parsers/lexers specify a lot of whitespace or separators in the production rules. Despite this stuff must be ubequitos, in practice, I do not see it at all. In JavaCC, for instance, you just specify whitespace chars in SKIP and it does the rest itself. What is the convention? I see that parser combinators support lexical.reserved words and lexical.delimiters. What is the purpose?

I guess that I can supplement every definition of identifier, delimiter and literal with optional whitespace prefix. Now, is it right that only identifiers and literals have to be separated by delimiters or whitespace? How do I ensure that?

Now, is it right that only identifiers and literals have to be separated by delimiters or whitespace? How do I ensure that?

If by "right" you mean it is the case in every programming language, then no, it is not right, and probably no non-trivial lexical statement would be either.
In many languages, integer literals do not have to be separated from a following identifier; in other languages, they do. In most languages, <= is different from < =, so identifiers and numbers are not the only classes of tokens which require explicit separation. (If you don't consider < and = to be "delimiters", then you cannot say that identifiers need to be separated by whitespace or delimiters, either, since a<b is normally valid.)
Maximal munch is a very common lexical algorithm. This views the input to be a sequence of lexemes where each lexeme starts precisely following the previous lexeme and continues as far as possible (so that if two lexemes are possible at a given point in the source code, the longest one is chosen regardless of whether the rest of the input would be valid or not). Not all lexemes are tokens; the set of lexemes includes ignorable whitespace, for example, which is recognized by the tokeniser but does not otherwise participate in syntactic analysis.
However, most languages have idiosyncratic exceptions. Consider the handling of <:: in C++ or 1..2 in D; both of these require an explicit exception to the maximal-munch rule. A different issue is the handling of regular-expression literals in ECMAscript (and other languages), in which / and /= could be tokenised as a simple operator token, or they could be the first part of a regular expression literal. Which option is chosen depends on the immediate syntactic context. Yet another deviation from the above model is found in languages like Python and Haskell where layout (whitespace used as indententation) is sometimes syntactic.
To the extent that a language specification uses the maximal munch algorithm, whitespace is mandatory precisely in those contexts where maximal-munch would produce a different tokenisation. In such languages, whitespace is always discarded (after tokenisation) and there is no need to ensure it is supplied.
There is no global institution which regulates computer language designers. Each language community develops according to its own philosophy, customs, eccentricities and equivocations, and there is no higher truth to which one can appeal.

Particular languages may be based on a different tokenisation model, so you cannot make general language-independent statements based on the behaviour of a single language. In the comments streams, it has been suggested that this question actually applies to VHDL and that VHDL does not conform to the maximal munch model. The text cited in the OP apparently comes from section 13.2 of the VHDL Reference Manual. However, it seems clear (even from the text quoted in the OP), that the design is not much different from maximal-munch. I repeat, with emphasis added:

The text of each design unit is a sequence of separate lexical elements. Each lexical element is either a delimiter, an identifier (which may be a reserved word), an abstract literal, a character literal, a string literal, a bit string literal, or a comment.
In some cases an explicit separator is required to separate adjacent lexical elements (namely when, without separation, interpretation as a single lexical element is possible). A separator is either a space character (SPACE or NBSP), a format effector, or the end of a line. A space character (SPACE or NBSP) is a separator except within a comment, a string literal, or a space character literal.

So that makes it clear that the only case in which separation is obligatory is where the concatenated tokens could be tokenised as a (longer) combined token, which is essentially the maximal-munch rule.


Any evidence that one way functions exist? There is no known proof that one way functions exist. But what is the heuristic evidence that they exist?

I sometimes read that the existence of cryptography is heuristic evidence that they exist. E.g. the ciphertext from a block cipher like AES is easily computable if you know the plaintext and key, but the key is not easily computable if you know the plaintext and ciphertext.

This is seen as evidence that AES might be a one way function, but to me it simply suggests that we don't know how to invert AES. In other words, it seems like this is an algorithm-search problem that is very hard (finding the key inversion algorithm), not that that algorithm doesn't exist.

Is my reasoning correct? Whether it is or not, what is the heuristic evidence that one way functions exist?

AES is widely believed to be secure: many smart people have tried to break it and haven't been able.  This is not a proof, and it is arguable exactly how strong this evidence is, but it does count as heuristic evidence of some sort.  The fact that we haven't been able to find an algorithm to break AES does seem to count as some sort of heuristic evidence that no such algorithm exists -- again, not ironclad, not a proof, arguable how strong the evidence is, some might even call it weak evidence, but still evidence of some sort.

Moreover, it is easy to prove that if AES is secure, then the function $F$ defined by

$$F(k) = \text{AES}_K(0)$$

is one-way, where $0$ represents the block of 128 zero bits.  To be precise, if AES is a secure PRP, then $F$ is a secure one-way function -- this latter statement can be mathematically proven in a 100% rigorous way.  Here by "security" I refer to concrete security rather than asymptotic security.  If you're interested in asymptotic security, you'll need something more.

Thus, this is heuristic evidence that one-way functions exist: in particular, we have heuristic evidence that the $F$ defined above is one-way.  You can form your own judgement about how persuasive or how strong this evidence is; that probably comes down to a personal judgement.


Time complexity of a vertical sweep algorithm with histogram computations In the paper

Quick Detection of Brain Tumors and Edemas: A Bounding Box Method
Using Symmetry, Saha et al

the authors claim that the running time of the algorithm (Matlab implementation) is $O(h)$. I don't understand how they arrive at this.

The algorithm works as follows:
The algorithm does a vertical sweep of a whole image of size $h\times w$.
For every $l$ between $0$ and $h$, a score function $s$ is computed.
To compute $s$ we we calculate histogram computation of the four parts of the whole image : $[0:l,1:w/2]$, $[l:h,1:w/2]$, $[0:l,w/2:end]$ and $[l:end,w/2:end]$.

How do they arrive at $O(h)$ time complexity for the algorithm? Do they consider histogram computation to be $O(1)$?

PS: This question is related to What is the time-complexity of histogram computation? but I hope to get the exact answer in concrete case this time ...

$O(h)$ sounds hard to believe, unless there's some pre computation that's not counted here, as it takes $\Theta(hw)$ time just to read every pixel of the image.

Computing a histogram from scratch can't be done in $O(1)$ time.  But updating a histogram can be done efficiently.  If you already have a histogram for some set of pixels, and then you add or delete one pixel, you can update the histogram in $O(1)$ time.  This kind of idea can be used to speed up the sort of thing you're talking about, because all of the histograms we want are closely related.

In particular, when we increment $l$, we add or delete a row from a histogram.  Thus you can update the histogram more efficiently than computing it from scratch.


Cost of partitioning in quicksort I'm reading "Algorithms Fourth Edition" by Sedgewick & Wayne and am wondering if I have spotted an error in the book or if I just can't wrap my head around something so simple.

When talking about the complexity of quicksort, the book says that the cost of partitioning, measured in the number of compares, is equal to N + 1, where N is equal to the number of elements in the collection to sort. We are assuming here that we just choose the first element in the collection to serve as the partition.

My question is would the cost of partitioning not really be equal to N - 1? That is, that you choose an element to serve as the partition and you compare it with every other element in the array.

--

As requested, the partitioning process is defined as follows:

The entry which will serve as partition is in its final place in the array.
No entries in positions before the partition are greater than the partition value.
No entries in positions after the partition are less than the partition value.

At this point I'm guessing it is in fact a typo...

--

The partitioning algorithm is outlined as follows

Take the leftmost array element as the "partitioning item"
Scan the array from the left until an element greater than or equal to the partitioning item is found
Scan from the right until an entry less than or equal to the partitioning item is found
When both a right and left item are found, exchange them
Repeat until the scan indexes cross
Once the scan indexes cross, exchange the partitioning item with the rightmost entry in the lower side of the array.

Note that the "cost" of the partitioning is being calculated in compares and not array accesses.

This is a pretty common version of partition and in this case you need N+1 comparisons.

For example consider an array containing ${1,2,\ldots,N}$.

Now, 1 is your pivot (partitioning item). pivot 1 is compared with first element 1 and it is greater than or equal it, so you got the left item. Here you need 1 comparison.

Then, pivot 1 is compared with $N,N-1,\ldots$. Note that the right item will be 1 as we want a number less than or equal to the pivot. Hence you need to compare 1 with all the elements $N,N-1,\ldots,1$. Thus here you need $N$ comparisons.

In total you need $N+1$ comparison.

In general we have two pointers one from left and one from right. pivot is compared with elements pointed by these two pointers. Left pointers moves towards right, right pointer moves towards left. Thus all the elements are compared with pivot at least once. But, one element is compared twice where the two pointers meet and cross. Thus we need $N+1$ comparisons.


Is this a proper Max Heap Data Structure I was trying to understand the concept of Max-Heap. And to my understanding its a complete binary tree and each parent has a value greater than its children.The example I was going though had the following array which it said was a Max-Heap.

BookArray [] = {45,10,11,3,2,7,9,1,0}

I then decided to shuffle the elements (so they are no longer in binary heap) and got this.

Shuffled[] = {11,1,0,7,9,3,2,10,45}

I then decided to write a program that would sort the elements in the array in Min-Heap
so I got this array

Sorted[] = {45,11,3,10,7,0,2,1,9}

My question is if my sorted array is also a valid max-heap ? since my array does not match the bookArray

The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree, the tree is completely filled on all levels except possibly the lowest.

Min Heap has the property:for every node i (except root node) Array[parent(i)]<=Array[i]. So the smallest element in a min-heap is at the root.

Max Heap is organized in opposite way, i,e. it has the property: for every node i (except root node) Array[parent(i)]>=Array[i]. So the largest element in a Max-heap is at the root.

You can check if the array is maintaining the heap property by the following algorithms.

Algorithm 1

Parent(i)
    return floor(i/2)

Algorithm 2

Left(i)
    return 2*i

Algorithm 3

Right(i)
   return 2*i+1

Now you can check on your own that if your array maintaining Max heap property or not.

It is not mandatory that two heaps with same elements have same arrangement.The thing you have to be conform that if all elements are maintaining the heap property or not.


Lambda Calculus Evaluation I know this is a simple question but can someone show me how
$(\lambda y. \lambda x. \lambda y.y) (\lambda x. \lambda y. y)$ reduces to $\lambda x. \lambda y. y$.

The reason that $(\lambda y. \lambda x. \lambda y.y) (\lambda x. \lambda y. y)$ reduces to $\lambda x. \lambda y. y$ and not to $\lambda x. \lambda y.\lambda x.\lambda y.y$ is that the $y$ in the body of $\lambda y.\lambda x.\lambda y.y$ refers to the argument of the third lambda, not the first.

If you rename the arguments to have distinct names, $\lambda y.\lambda x.\lambda y.y$ would be written as $\lambda y_1.\lambda x.\lambda y_2.y_2$. So if you apply that function to the argument, that means that every occurrence of $y_1$ in $\lambda x.\lambda y_2.y_2$ should be replaced with the argument. However $y_1$ does not appear at all in that expression, so the argument is simply ignored and the result is just $\lambda x.\lambda y_2.y_2$.


Proof that dead code cannot be detected by compilers I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the quarter, but it has me stumped so I might use it as an example instead.

public class DeadCode {
  public static void main(String[] args) {
     return;
     System.out.println("This line won't print.");
  }
}

In the program above, it's obvious that the print statement will never execute because of the return. Compilers sometimes give warnings or errors about dead code. For example, the above code will not compile in Java. The javac compiler, however, will not detect all instances of dead code in every program. How would I prove that no compiler can do so?

It all comes from undecidability of the halting problem. Suppose we have a "perfect" dead code function, some Turing Machine M, and some input string x, and a procedure that looks something like this:

Run M on input x;
print "Finished running input";

If M runs forever, then we delete the print statement, since we will never reach it. If M doesn't run forever, then we need to keep the print statement. Thus, if we have a dead-code remover, it also lets us solve the Halting Problem, so we know there can be no such dead-code remover.

The way we get around this is by "conservative approximation." So, in my Turing Machine example above, we can assume that running M on x might finish, so we play it safe and don't remove the print statement. In your example, we know that no matter which functions do or don't halt, that there's no way we will reach that print statement.

Usually, this is done by constructing a "control-flow graph". We make simplifying assumptions, such as "the end of a while loop is connected to the beginning and the statement after", even if it runs forever or runs only once and doesn't visit both. Similarly, we assume that an if-statement can reach all of its branches, even if in reality some are never used. These kinds of simplifications allow us to remove "obviously dead code" like the example you give, while remaining decidable.

To clarify a few confusions from the comments:

  Nitpick: for fixed M, this is always decidable. M has to be the input

As Raphael says, in my example, we consider the Turing Machine as an input. The idea is that, if we had a perfect DCE algorithm, we would be able to construct the code snippet I give for any Turing Machine, and having a DCE would solve the halting problem.

  not convinced. return as a blunt statement in a no-branch straight forward execution is not hard to decide. (and my compiler tells me it is capable of figuring this out)

For the issue njzk2 raises: you are absolutely right, in this case you can determine that there is no way a statement after the return can be reached. This is because it's simple enough that we can describe its unreachability using control-flow graph constraints (i.e. there are no outgoing edges out of a return statement). But there is no perfect dead code eliminator, which eliminates all unused code.

  I don't take input-dependent proof for a proof. If there exists such kind of user input that can allow the code to be finite, it's correct for the compiler to assume that following branch is not dead. I can't see what are all these upvotes for, it's both obvious (eg. endless stdin) and wrong.

For TomášZato: it's not really an input dependent proof. Rather, interpret it as a "forall". It works as follows: assume we have a perfect DCE algorithm. If you give me an arbitrary Turing Machine M and input x, I can use my DCE algorithm to determine whether M halts, by constructing the code snippet above and seeing if the print-statement is removed. This technique, of leaving a parameter arbitrary to prove a forall-statement, is common in math and logic.

I don't fully understand TomášZato's point about code being finite. Surely the code is finite, but a perfect DCE algorithm must apply to all code, which is an infinte set. Likewise, while the code-itself is finite, the potential sets of input are infinte, as is the potential running-time of the code.

As for considering the final branch not-dead: it is safe in terms of the "conservative approximation" I talk about, but it's not enough to detect all instances of dead code as the OP asks for.

Consider code like this:

while (true)
  print "Hello"
print "goodbye"

Clearly we can remove print "goodbye" without changing the behavior of the program. Thus, it is dead code. But if there's a different function call instead of (true) in the while condition, then we don't know if we can remove it or not, leading to the undecidability.

Note that I am not coming up with this on my own. It is a well known result in the theory of compilers. It's discussed in The Tiger Book. (You might be able to see where they talk about in in Google books.


Is the language of rectangular matrices in MATLAB-style syntax context free? Consider the language $L$ of rectangular matrices written down as a comma separated list of integers where each list represents a row of the matrix and rows are separated by a semicolon. There may be an
arbitrary number of rows, but each row must contain the same number of integers.

For example: $[3, 5, 6; 8, 9, 10; 7, 3, 6] \in L$ and
$[3, 5, 6; 7, 8, 10, 12; 7] \notin L$, because each row contains a different number of integers and so the matrix is not rectangular.

Is this language context-free? I have a very strong hunch that it isn't, given that not even the language $A^{n}B^{n}C^{n}$ is context free, but I don't have much experience with proofs using the pumping lemma for context-free languages and I'm hoping there is a simpler way to prove that $L$ is not context free.

Delete all numbers from your language $L$, and replace $,$ with $a$ and $;$ as $b$.  Then intersect it with the regular language $a^*ba^*ba^*$.  You obtain a new language $L' = \{a^n b a^n b a^n : n \in \mathbb{N}\}$.  If $L$ is context-free, then $L'$ will be context-free too, as it has been obtained by applying a homomorphism and then intersecting with a regular language, both of which preserve context-freeness.  However, $L'$ is a standard example of a non-context-free language, so $L$ must be non-context-free as well.