Let L be any non-empty language over an alphabet Σ. Show that $L^2$ ⊆ $L^3$ if and only if λ ∈ L I have this question in my Theoretical Computer Science class on the topic of Automata and Formal Languages.

$$ λ ∈ L \iff L^2 ⊆ L^3$$

I thought of showing it by proving the contrapositive but I was only able to complete half of the proof (since it is a bidirectional proof) and on top of that I am not even sure it is correctly written in a formal form.

I wanted to prove that if

$$λ ∉ L \implies L^2 \nsubseteq L^3$$

But since it is a bidirectional proof, I must also show that

$$L^2 \nsubseteq L^3 \implies λ ∉ L$$

right?

This is what I have so far:

1) $λ ∉ L \implies L^2 \nsubseteq L^3$

$ \lambda \notin L \implies \forall w \in L, n_o(w) \geq 1$
$ L^2 = L * L \implies \forall w_2 \in L^2, n_o(w_2) \geq 2 $
$ L^3 = L * L * L \implies \forall w_3 \in L^3, n_o(w_3) \geq 3 $
$\forall w_3 \in L^3 \land \forall w_2 \in L^2, n_o(w_3) > n_o(w_2)$
$ \therefore L^2 \nsubseteq L^3$

So first of all, is this correct?

Secondly, how would I go about showing the second part of my proof where
$$L^2 \nsubseteq L^3 \implies λ ∉ L$$

Thank you!

I'm assuming by $\lambda$ you mean the empty word and by $n_0(w)$ the length of a word.

The proof for the first part is not correct: You argue that every word in $L^2$ has length at least $2$ and every word in $L^3$ has length at least $3$. From that it does not follow that every word in $L^3$ is longer than every word $L^2$, because there could also be a word of e.g. length $3$ in $L^2$. Consider for example $L = \{a\}^\star \setminus \{ \lambda \}$, that is, the set of all non-empty $a$-sequences. You have $a \in L$ and $aa \in L$, thus $aaa = a \cdot aa \in L^2$, but also $aaa = a \cdot a \cdot a \in L^3$.

Instead, what you want to say is that there is a word of minimal length $n$ in $L^2$, and because every word in $L$ has length at least one, the shortest word in $L^3$ has length at least $n+1$.

More formally: Let $\lambda \notin L$. Thus $\forall w \in L: n_0(w) > 0$. Pick $w \in L^2$ such that $n_0(w)$ is minimal. Assume $w \in L^3$. Since $L^3 = L^2 \cdot L$, it follows that $w = u \cdot v$ for $u \in L^2$ and $v \in L$. Since $n_0(v) > 0$, it follows $n_0(w) > n_0(u)$. But then $n_0(w)$ is not minimal. Contradiction.

For the second part: Assume $L^2 \not \subseteq L^3$ and $\lambda \in L$. Thus there is $w \in L^2$ such that $w \notin L^3$. But since $L^3 = L^2 \cdot L$, it follows $w = w \cdot \lambda \in L^3$. Contradiction.


2-way set associative cache exercise In the exercise I have a 32 bit processor with a 2-way set associative cache. I have 32 bit addresses: 31-14 tag, 13-5 index, 4-0 offset.
Calculate:
1) Cache line size in number of words (1 word = 4 bytes)
2) Total cache size in bits

In the presence of the following sequence of accesses in memory, considering the initially empty cache, indicate for each access if it is hit, miss, or replace:
17920 17948 149024 83488 17952 148998 149012 17964 148648 17848

I think answer at the first part should be:
1) 2^5 = 32byte --> 32/4 = 8words
2) 32byte = 256bit --> size = 256 * (4096 + 18 + 1)

Is it correct? And I'm not sure on how to complete the second part of the exercise

You have 5 bits for the offset. Assuming byte addressed memory, you'll need four memory addresses to construct a word. So take two bits from the offset. Now you are left with 3 bits in the offset, hence a cache line would have 8 words.

9 bits for have been used for the index, therefore 2^9 cache blocks are present. Since its a two way assoc, each block contains 2 cache lines.

data storage =
(2^9 cache blocks
* 2 cache lines in a block
* 8 words per cache line
* 32 bits in a word) bits
= 262,144 bits

Now the rest is bit tricky as the question does not provide what other bits are available. Assuming there is a valid bit present,

per cache line we need 1 bit for valid bit + 18 bits of tag data = 19 bits of "meta" data

512 cache blocks * 2 lines per block * 19 bits = 19,456
So the total size in bits = 262,144+ 19,456 = 281,600

If there is also a dirty bit present, equations changes to

 per cacheline,
 1 bit for valid bit + 1 bit for dirty bit + 18 bits of tag data = 20 bits of "meta"data

For the second part, get the binary representation of the address. Break it into tag, index and the offset. Fill up the cache based on the tag and the index. See what happens.


If xor-ing a one way function with different input, is it still a one way function? Suppose $f(x)$ is a one way function. What about $h(x)=f(x_1) \, \oplus \,f(x_2)$, where $x=x_1 || x_2$ and $\lvert x_1 \rvert = \lvert x_2\rvert$?

$\oplus$ is exclusive disjunction (xor)
$||$ is concatenation
$|u|$ is the length of $u$

The function $h$ may not be one-way anymore.

We construct a counter example—a specific one way $f$ whose $h$ is not one-way anymore—in the following way.
Assume $g$ is a one-way function that preserves size, and define $f$  on input $w=bx_1x_2$ in the following way,
$$f(bx_1x_2) = \begin{cases} g(x_1)\,x_2 & b=0 \\ x_1\, g(x_2) & b=1 \end{cases}$$
(assuming $b\in\{0,1\}$ and $|x_1|=|x_2|$.)
It is easy to see that $f$ is also one-way — to invert it, you need to either invert $g$ on the first half or invert $g$ on the second half.

Now we show how to invert $h$. Assume you are given $h(u,v)=Z$, we write it as $h(u,v)= z_1z_2$ with $|z_1|=|z_2|=n$.
Then a possible preimage of $Z$ is
$$u=0 \,0^n \,\langle g(0^n)\oplus z_2\rangle$$
$$v=1 \, \langle g(0^n)\oplus z_1\rangle \, 0^n$$

because $f(u) = g(0^n)\, \langle g(0^n)\oplus z_2\rangle$ and
$f(v) = \langle g(0^n)\oplus z_1\rangle \, g(0^n)$ thus their XOR gives
exactly $z_1\,z_2$ as required.


denotional semantic for while - fixed points In my book it is written:
$$[[\text{while b do S}]] = \text{FIX F}$$, where $Fg = cond (\beta[[b]], g\circ [[S]], id). $
What is cond ?
$[[\text{if b then S1 else S2}]] = cond (\beta[[b]], [[S1]], [[S2]])$.

I don't understand why we should use $FIX$. What it is FIX ?
For me it is sufficient:
$S[[\text{while b do S}]] = cond(\beta[[b]], [[\text{while b do S}]]\circ [[S]], id)$$

DEFINITIONS

$$S_{ds}[[\text{while b do S}]] = FIX F$$
where $Fg= \text{cond}(\beta[[b]], g\circ S_{ds}[[S]], id)$

$$FIX: ((State\rightarrow State)\rightarrow (State \rightarrow State)) \rightarrow (State \rightarrow State)$$
In brackets functions are partial.

Your proposed alternate definition is no good.  It tries to define $[[\text{while b do S}]]$ in terms of $[[\text{while b do S}]]$.  That's a circular definition: you can't define something in terms of itself.

"FIX" typically refers to the least fixpoint, and is a way of avoiding circularity.  See your textbook for background on fixpoints and the precise definition of the "FIX" operator.


Distributed algorithms - $\alpha, \beta$ synchronizers I experience a difficulty in solving exercises in distributed algorithm. Below is the the exercise I try to solve, it looks like I miss basic idea.

Exercise. Consider a 15-processor asynchronous network with processors 0,…,14. The processors constantly run a synchronizer. Let $v$ and $v'$ be two processors in the network, and suppose that at a certain moment, the pulse counter at $v$ shows $p=27$. What is the range of possible pulse numbers at $v'$ in each of the following cases:

a) The network is a ring, $v$ is processor number 11, $v'$ is processor number 2 and the synchronizer used is $\alpha$.

Idea: if $v'$ hasn't sent any message up to pulse 27 of $v$, pulse of $v'$ is still 0, therefore lower bound of pulse of $v'$ is 0. The model of synchronizer is $\alpha$ it means every node informs all nodes about it's safe(v,p) state, hence I assume that $v'$ might be 11-2=9 pulses before $v$.

b) The network is a full balanced binary tree (4 levels), $v$ is the root, $v'$ is one of the leaves and the synchronizer used $\beta$.

Idea: $v'$ also might have pulse 27, in this case $v$ sends at speed of $v'$.

c) The same as in (b), except both $v$ and $v'$ are leaves.

Honestly, I am completely confused by this exercise, I wrote few ideas, but I don't have any understanding and any intuition behind the answers.

I will appreciate if someone show me the way how to solve such exercises.

Please find solutions of all cases:

For case A ($\alpha$-synchronizer), the pulse at a node can either be more, equal, or less by one (therefore, $\{26,27,28\}$). This is because a node must inform its neighbors about its safeness and not all the other nodes (according to your question).

You can see the rules in the following (copy-pasted from the paper)

A new pulse may be generated at a node whenever it is guaranteed that no
message sent at the previous pulses of the synchronous algorithm may arrive at
that node in the future.
Using the acknowledgment mechanism described above, each
node detects eventually that it is safe and then reports this fact directly to all its neighbors. Whenever a node learns that all its neighbors are safe, a new pulse is generated.

For case B: ($\beta$-synchrnoizer) - if $v$ is the root, then at $v'$ the pulse is either the same or less (therefore, $\{26,27\}$).

For case C: ($\beta$-synchrnoizer) - if both $v$ and $v'$ are leaves, then here we may assume that the broadcast of the root is not received at the same time - since the network is asynchronous (otherwise, why would we need a synchrnoizer). Here, if $v$ is 27 then $v'$ is either 28 if the update of $v'$ is received before $v$ ,, or 26 if the update of $v'$ is received after. Or they both have the same pulse  (therefore, the range is $\{26,27,28\}$.


how does $PATH$ being $NL$-complete help to prove $NL = coNL$ There is a proof in Sipser showing that $NL = coNL$ (theorem 8.27 in the 3rd edition).

In the proof idea, the first sentence is: "We show that $\overline{PATH}$ is in $NL$, and thereby establish that every problem in $coNL$ is also in $NL$, because $PATH$ is $NL$-complete." I'm having trouble understanding this.

Sipser did not elaborate on this, but it sounds like the logic behind this sentence is:

$PATH$ is $NL$-complete
so $\overline{PATH}$ is $coNL$-hard
and $\overline{PATH}$ is in $NL$
so $coNL \subseteq NL$

If so, why can we get 2 from 1?

More generally, since $PATH$ can be decided in $NL$ (Sipser example 8.19), why can't we just flip the result to decide $\overline{PATH}$ directly?

$\mathsf{NL}$ consists of all languages accepted by nondeterministic Turing machines using logarithmic space. One way to think of such machines is as follows:

The input is written on a read-only input tape.
There are one or more work tapes of logarithmic size.
There is a read-only oracle tape on which the head is constrained to only move to the right.

We can think of each such machine as computing a Boolean function on two arguments: $x$, which is the actual input, and $y$, which is the initial contents of the oracle tape. Such a machine $M$ nondeterministically computes the language $L(M)$ given by:
$$
x \in L(M) \Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ accepts}.
$$
In other words, a language $L$ is in $\mathsf{NL}$ if there exists a logspace Turing machine $M$ with an auxiliary oracle input such that
$$
x \in L \Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ accepts}.
$$

A language is in $\mathsf{coNL}$ if its complement is in $\mathsf{NL}$. Equivalently, a language $L$ is in $\mathsf{coNL}$ if there exists a logspace Turing machine $M$ with an auxiliary oracle input such that
$$
x \notin L \Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ rejects}.
$$
Equivalently,
$$
x \in L \Longleftrightarrow \forall y \text{ $M(x,y)$ accepts}.
$$

Suppose now that $L$ is in $\mathsf{NL}$, say $L = L(M)$, and let $M'$ be obtained from $M$ by complementing the output. Then
$$
x \in L(M') \Longleftrightarrow \exists y \text{ s.t. $M'(x,y)$ accepts}
\Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ rejects}.
$$
As you can see, $L(M')$ isn't necessarily the complement of $L(M)$. Indeed, given any machine $M$, we can come up with another machine $\tilde{M}$ such that $L(M) = L(\tilde{M})$, but $\tilde{M}(x,y_0)$ always rejects, for some fixed $y_0$ (for example, $\tilde{M}(x,0\Sigma^*)$ always rejects, and $\tilde{M}(x,1y) = M(x,y)$). In this case, $L(\tilde{M}') = \Sigma^*$.

Now I can answer your questions:

$\overline{\mathsf{PATH}} \in \mathsf{coNL}$ since $\mathsf{PATH} \in \mathsf{NL}$ and by definition $\mathsf{coNL}$ consists of the complements of all languages in $\mathsf{NL}$.
Furthermore, $\overline{\mathsf{PATH}}$ is $\mathsf{coNL}$-hard because $\mathsf{PATH}$ is $\mathsf{NL}$-hard. Indeed, suppose that $L \in \mathsf{coNL}$. Then $\overline{L} \in \mathsf{NL}$. Since $\mathsf{PATH}$ is $\mathsf{NL}$-hard, there is a logspace reduction $f$ such that $x \in \overline{L}$ iff $f(x) \in \mathsf{PATH}$. Thus $x \in L$ iff $f(x) \in \overline{\mathsf{PATH}}$, and so $f$ also reduces $L$ to $\overline{\mathsf{PATH}}$.
Flipping the output value of a nondeterministic machine does not result in complementing the accepted language.

Elaborating on the second point, for some nondeterministic complexity classes $\mathsf{X}$, it is known that $\mathsf{X} \neq \mathsf{coX}$. The simplest example is $\mathsf{RE} \neq \mathsf{coRE}$: the halting problem is in $\mathsf{RE}$ but not in $\mathsf{coRE}$. Therefore $\mathsf{NL} = \mathsf{coNL}$ is a nontrivial statement.


Is there a language that can be Turing-reduced from all languages? I don't think so, because $A_{TM} = \{<M,w>\mid \text{M accepts w}\}$ is not Turing-decidable. Is this the right way to think about?

I assume you're asking if there's a language $\Omega$ such that, for all $L\subseteq\{0,1\}^*$, $L\leq_T\Omega$.  In that case, the answer is “no.”

For any language $\Omega$, the languages that Turing-reduce to $\Omega$ are those that can be decided by a Turing machine with an oracle for $\Omega$. For brevity, I'll say “$\Omega$-Turing machines” instead of “Turing machines with an oracle for $\Omega$.” $\Omega$-Turing machines are at least as powerful as ordinary Turing machines (exactly as powerful, if $\Omega$ is decidable; strictly more powerful of it isn't).

The same argument that shows the undecidability of the ordinary Turing machine halting problem also shows that any machine model that is at least as powerful as Turing machines can't decide its own halting problem.  So, in particular, no $\Omega$-Turing machine can decide the halting problem for $\Omega$-Turing machines.  In other words, for any language $\Omega$, the halting problem for $\Omega$-Turing machines isn't Turing-reducible to $\Omega$.

This means that there's no “hardest language” (or class of languages) to which all languages are Turing-reducible. This is related to the concept of Turing degrees, which form an infinite hierarchy of ever more difficult languages: start with the decidable languages, then the languages decided by Turing machines with an oracle for the halting problem, and then iterate by making each subsequent level be the languages decided by Turing machines with an oracle for the halting problem corresponding to the previous level.


What is the language generated by a given grammar Given the grammar
  $s \to aSb \mid bSb \mid a \mid b$;
  what is the language generated by the grammar over the alphabet $\{a,b\}$?

When I was solving this question I was a bit confused
about  the language generated by this grammar. Would be set of all palindromes?
Or would the language generated by the above grammar be that of all odd length palindromes?

Is it possible that a palindrome generated by above grammar be of odd length only as there is no rule for $S \to \varepsilon$?

The language of this grammar is all strings of the form $wb^n$  where $w\in \{a,b\}^*$, and $|w| = n+1$. If I abuse the notation a bit, it is $\Sigma^{n+1}b^n$.

If perchance you mean $S \rightarrow aSa \ | \ bSb \ | \ a\ | \ b$, then the language contains all palindromic strings of odd length.


Lambda Calculus Generator I don't know where else to ask this question, I hope this is a good place.

I'm just curious to know if its possible to make a lambda calculus generator; essentially, a loop that will, given infinite time, produce every possible lambda calculus function. (like in the form of a string).

Since lambda calculus is so simple, having only a few elements to its notation I thought it might be possible (though, not very useful) to produce all possible combinations of that notation elements, starting with the simplest combinations, and thereby produce every possible lambda calculus function.

Of course, I know almost nothing about lambda calculus so I have no idea if this is really possible.

Is it? If so, is it pretty straightforward like I've envisioned it, or is it technically possible, but so difficult that it is effectively impossible?

PS. I'm not talking about beta-reduced functions, I'm just talking about every valid notation of every lambda calculus function.

Sure, this is a standard encoding exercise.

First of all, let $p : \mathbb N^2 \to \mathbb N$ any bijective computable function, called a pairing function. A standard choice is

$$
p(n,m) = \dfrac{(n+m)(n+m+1)}{2}+n
$$

One can prove that this is a bijection, so given any natural $k$, we can compute $n,m$ such that $p(n,m)=k$.

To enumerate lambda terms, fix any enumeration for variables names: $x_0,x_1,x_2,\ldots$.

Then, for each natural number $i$, print $lambda(i)$, defined recursively as follows:

if $i$ is even, let $j=i/2$ and return variable $x_j$
if $i$ is odd, let $j=(i-1)/2$

if $j$ is even, let $k=j/2$ and find $n,m$ such that $p(n,m)=k$; compute $N=lambda(n), M=lambda(m)$; return application $(NM)$
if $j$ is odd, let $k=(j-1)/2$ and find $n,m$ such that $p(n,m)=k$; compute $M=lambda(m)$; return abstraction $(\lambda x_n.\ M)$

This program is justified by the following "algebraic" bijection involving the set of all lambda terms $\Lambda$:

$$
\Lambda \simeq \mathbb N + (\Lambda^2 + \mathbb N \times \Lambda)
$$

which is read as "the lambda terms, syntactically, are the disjoint union of 1) variables (represented as a natural), 2) applications (make by two lambda terms), and 3) abstraction (a pair variable/natural + lambda term)".

Given that, we recursively apply computable bijections $\mathbb N^2 \simeq \mathbb N$ ($p$) and $\mathbb N + \mathbb N \simeq \mathbb N$ (the standard even/odd one) to obtain the algorithm above.

This procedure is general, and will work on almost any language generated through a context-free grammar, which will provide a similar isomorphism to the one above.


Intersection between regular language and context-free language In general, context-free algorithm are not closed under intersection but the intersection between a regular language and a CF language is known to be context-free.

My question is: does exist an algorithm to compute intersection in these special cases?

Thanks.

Yes, there does.

The key is to represent your CFL as a pushdown automaton, and the regular language as a DFA. Then compute the product automaton of the CFL's states and the DFA's states, keeping the stack operations from the CFL.

In essence, what you're doing is running your pushdown machine, and keeping track of what state you would be in in the DFA if you were running it in parallel. Then, when you reach the end, you only accept if both machines would accept.


In which pipeline stage are exceptions detected? Do you immediatly handle an exception when it occurs (for example an overflow exception in the EX stage) or do you wait until the final pipeline stage and then check whether any interrupts had occured?

Both.

I'll assume you are talking about pipelined machine organizations with

out-of-order completion (different instructions take different amounts of time to produce their results)
precise interrupts (instructions appear to produce their effects in-order).

An exception might be detected in the instruction fetch stage (if, for example, there is a page fault when trying to access the instruction memory), in the execution stage (like in your example of an overflow) or, for memory instructions, for a page fault when trying to access the data memory.

One important question is what to do with the other instructions in the pipeline.  Instructions that were fetched before the excepting instruction should appear to commit their changes before the interrupt, and instructions that were fetched after the excepting instruction should get cancelled somehow before they commit any changes at all.

Typically you deal with this by having some form of commit stage (called the "write-back" stage in the 5-stage pipeline that is often used in computer organization courses.)  Instructions commit in order, even if they "complete" their execution out-of-order.  At the time the excepting instruction arrives at the commit stage all the previous in-order instructions will have committed, but their will be some number of instructions that were fetched after the excepting instruction still in the pipeline.  Those following instructions need to be cancelled, and this is often done by keeping a cancelled bit with each instruction as it flows down the pipeline.  The commit stage just doesn't write-back the results of any cancelled instructions.

The other question that needs to be answered is when do you redirect the fetch unit to the exception handler.  It would be simplest to signal the fetch unit only from the commit stage, but for longer pipelines that can cause an extremely long bubble between the exception being detected and the exception handler starting to fetch.  In that case you might redirect the fetch unit when you detect the exception.  The Pentium 4 did it this way, for example.


Normal colorings of cubic graphs to SAT This problem is related to ”Normal coloring of cubic graphs (part 1)  - a previous post.  We repeat the definitions, slightly modified so as to get to the point (we define normal edge 5 colorability, rather than the more general normal edge $k$ colorability).

  Definition A normal edge 5 coloring (or normal 5 coloring) of a cubic graph $G$ is a proper coloring of the edges with 5 colors, so that for any edge $e\in E(G)$, the four edges adjacent to $e$ are colored with two colors, or with four colors.

Thus, an edge $e$ and its four adjacent edges might utilize three colors, or five colors.

  If three colors are used, $e$ is called poor, and if five colors are used, $e$ is called rich.

...

  Question I would like to know how to transform an instance of this problem to a CNF formula.  That is, given a graph $G$, produce a CNF formula, such that a satisfying assignment can be translated back to a normal 5 coloring of the graph.

Note that working with the line graph of the cubic graph, as one would in dealing with a typical edge coloring problem, is a bit tricky (and that is all I dare to say).

Please advise if this question would be better off if posted in the theoretical computer science pages. Thanks in advance.

Start with $5|E(G)|$ variables $x_{e,i}$, one for each $e \in E(G)$ and $i \in \{1,2,3,4,5\}$. Intuitively $x_{e,i}$ means that edge $e$ is colored with color $i$.

A CNF formula $\phi$ can be obtained by the logical and of the following sub-formulas.

Each edge must have exactly one color:

At least one color, for each $e \in E(G)$:
$(x_{e,1} \vee x_{e,2} \vee x_{e,3} \vee x_{e,4} \vee x_{e,5})$
At most one color, for each $e \in E$, and $i,j \in \{1,2,3,4,5\}$ with $i<j$:
$(\overline{x_{e,i}} \vee \overline{x_{e,j}})$

The coloring must be proper:

For each pair $e,f \in E(G)$ of adjacent edges and for each $i \in \{1,2,3,4,5\}$:
$(\overline{x_{e,i}} \vee \overline{x_{f,i}} )$

If $e=(u,v)$ is an edge of $G$, let $f^e_1,f^e_2$ be the two edges other than $e$ that are incident to $u$, and $f^e_3,f^e_4$ be the two edges other then $e$ that are incident to $v$.

For each $e \in E(G)$ add a new variable $r_e$. This will encode "if $e$ is not rich, then $r_e$ is true": Notice that if $e$ is rich then $r_e$ can always be set to false.
For every $i \in \{1,2,3,4,5\}$, every $j \in \{1,2\}$, and every $k \in \{3,4\}$:
$(r_e \vee \overline{x_{f^e_j, i}} \vee \overline{x_{f^e_k, i}})$
For each $e \in E(G)$ add a new variable $p_e$. This will encode "if e is not poor, then p_e is true". Notice that if $e$ is poor then $p_e$ can always be set to false.
For every ordered tuple $(j, k, h)$ of $3$ distinct elements from $\{1,2,3,4,5\}$:
$( p_e \vee \overline{x_{f_1,j}} \vee  \overline{x_{f_2,k}} \vee \overline{x_{f_3,h}})
\wedge
( p_e \vee  \overline{x_{f_1,j}} \vee  \overline{x_{f_2,k}} \vee \overline{x_{f_4,h}})
\wedge
( p_e \vee  \overline{x_{f_1,j}} \vee  \overline{x_{f_3,k}} \vee \overline{x_{f_4,h}})
\wedge
( p_e \vee \overline{x_{f_2,j}} \vee  \overline{x_{f_3,k}} \vee \overline{x_{f_4,h}})
$

Finally, this will encode "e is rich or e is poor":

For every $e \in E(G)$: $(\overline{r_e} \vee \overline{p_e})$

If you have a satisfying truth assignment for $\phi$ then you can color edge $e \in E(G)$ with color $i$ iff $x_{e,i}$ is true.

If you have a coloring then let $c(e) \in \{1,2,3,4,5\}$ be the color of edge $e$. You an get a satisfying truth assignment for $\phi$ by setting:

$x_{e,c(e)}= \top$, and $x_{e,j} = \bot$ for $j \in \{1,2,3,4,5\} \setminus \{ c(e) \}$,
$r_e = \bot$ iff edge $e$ is rich,
$p_e = \bot$ iff edge $e$ is poor.


Prove that the upper bound in the Noiseless-coding theorem is strict Given a probability distribution $p$ across an alphabet, we define redundancy as:

Expected Length of codewords - entropy of p = $\ E(S) - h(p)$

Prove that for each $\epsilon$ with $0 \le \epsilon \lt 1$ there exists a $p$ such that the optimal encoding has redundancy $ \epsilon$.

Attempts

I have tried constructing a probability distribution like $p_o = \epsilon, p_1 = 1 - \epsilon $ based on a previous answer, but I can't get it to work.

Any help would be much appreciated.

Edit:

The solution I think I have found is mapped below.

redundancy = $E(S) - h(p) = \sum p_is_i + \sum p_ilogp_i$.
We want to show that for a given $\epsilon$, we can find a $p$ that makes redundancy = $\epsilon$.
So $\sum p_is_i + \sum p_ilogp_i = \epsilon ==> \sum p_is_i = -\sum p_ilogp_i + \epsilon$.

We know the optimal value for $s_i$ will be less than $-logp_i + 1$, so we can write all $s_i$ as $s_i = -logp_i+\alpha_i$.

Now, $\sum p_is_i = -\sum p_ilogp_i + \epsilon ==> \sum p_i(-logp_i + \alpha_i) = -\sum p_ilogp_i + \epsilon ==> \sum p_i\alpha_i = \epsilon$.

Intuitively I feel that you can always find a p so that the above is true for $epsilon$, because the $\alpha$ values are governed by how far away from a power of two your $m$ is, but I am not sure how to prove this last step.

Take the probability distribution that you consider: there are two symbols, one with probability $\delta$, the other with probability $1-\delta$.

Any minimum redundancy code for this distribution has average codeword length $1$. Therefore the redundancy is $1 - h(\delta)$. Since $h(1/2) = 1$, $\lim_{\delta\to0} h(\delta)=0$ and $h$ is continuous, for every $0 < \gamma \leq 1$ you can find $\delta > 0$ such that $h(\delta) = \gamma$. Choosing $\gamma = 1 - \epsilon$, we get a distribution whose redundancy is $1-\gamma = \epsilon$.

It is natural to "outlaw" such distributions by requiring all probabilities to be smaller than some $\kappa$. For small $\kappa$, we can no longer find distributions whose redundancy is close to 1. It is natural to conjecture that as $\kappa$ goes to zero, the maximum redundancy also goes to zero. However, this is not the case: for arbitrarily small $\kappa$, there are distributions whose redundancy is roughly 0.086. See Gallager's Variations on a theme by Huffman, which establishes that the limiting value of the maximum redundancy is (roughly) 0.086.


Virtual Memory: "Page Table or Page Tables?" I am having a bit of a tough time grasping whether a computer system contains several page tables or just one page table.

Some sources speak of page tables in plural others in singular.

Intuitively it makes most sense to me that there is only one Page table containing all the physical addresses especially considered these addresses are to change over time. But I am not sure?

Each process has a different page table (since each process has a different address space). Each processor (or core if you want to be specific) can only have one active page table at a time, but the processor switches which table is used when it switches between processes.

I am also simplifying here because there are more tables used for IOMMU and hardware assisted virtualization.


Example of a boolean function Is there an example of real polynomial representation of a Boolean function with $4$ variables whose polynomial degree is $2$ that depends on $4$ variables?

Yes. Using the convention that inputs and outputs are $\pm 1$, then the function is
$$
\frac{a(x+y)+b(x-y)}{2}.
$$
You could have found this function using exhaustive search – there are only $2^{16}$ functions on $4$ variables.


Why store self and parent links (. and ..) in a directory entry? Consider an filesystem targeted at some embedded devices that does little more than store files in a hierarchical directory structure. This filesystem lacks many of the operations you may be used to in systems such as unix and Windows (for example, its access permissions are completely different and not tied to metadata stored in directories). This filesystem does not allow any kind of hard link or soft link, so every file has a unique name in a strict tree structure.

Is there any benefit to storing a link to the directory itself and to its parent in the on-disk data structure that represents a directory?

Most unix filesystems have . and .. entries on disk. I wonder why they don't handle those at the VFS (generic filesystem driver) layer. Is this a historical artifact? Is there a good reason, and if so, which precisely, so I can determine whether it's relevant to my embedded system?

You get fewer special cases.  In many situations, VFS may handle ".." as it handles any other directory name.


Help designing a Turing Machine I am faced with the following question:

  Design a Turing Machine that recognizes the language $L = \{1^{2n+1}\mid n \text{ is a non-negative integer}\}$. Show the state diagram.

I started doing this using $Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$, and setting up a 7 tuple but I cannot come up with the state diagram.

Hint: $L$ is regular. Draw a DFA accepting $L$, and modify it to a full-fledged Turing machine whose operation is essentially equivalent to that of the DFA.


Divide and conquer algorithm for a gas station problem I never heard about this variation of the gas station problem. The statement is as follows:

There is just one road connecting the n+1 cities c0, …, cn
consecutively. You want to go from c0 to cn stopping at most s times
to fill the tank of the car. There are gas stations at the cities, but
none on the roads. The length of each road is ℓ0, …, ℓn−1. Which is
the minimum range for your car? Suppose that you start with a full
tank.

This has to be done in something like nlogn, because I already tried the n^2 approach and is not good. I don't know how to decide if I should refill at some point or not.
For this inp:
5 0
100 300 500 200 400
5 1
100 300 500 200 400
5 2
100 300 500 200 400
5 3
100 300 500 200 400
5 4
100 300 500 200 400

The output should be:
1500
900
600
500
500
(Consider that the input is a sequence of n and s, followed by n naturals that represents l_i.
Source

You can use binary search on the range of the car. Refill only if needed.

Here is the algorithm in more detail.

Let low = 0 and high = distance from c0 to cn. During the whole algorithm, range high is always big enough for a car to reach cn from c0, while range low is always not.
Repeat the following as long as low + 1 < high

mid = (low + high) /2
If range mid is big enough, set high = mid. Otherwise, set low = mid.

Return high, which must be the minimum range of the car.

How can we check if a given range is big enough?
Simple.
We will try driving a car with that range from c0 to cn. At each city, if the remaining range of the car is not enough for the car to reach the next city, refill the car to its full range. If we have refilled s+1 times before we have reached cn, that given range is not enough. Otherwise, it is enough.

It takes $O(n)$ time to check whether a given range is big enough.
The bisecting loop will run at most $\lceil\log_2 m\rceil$ iterations, where $m$ is the distance from c0 to cn.
So, the algorithm runs in $O(n\log_2 m)$-time.


What is the cardinality of the set of regular grammars? What is the cardinality of the set of regular grammars?  The caveat is that I'm only interested in grammars which are 'structurally' different.  Sorry I don't know how to talk about this in a formal way, but what I mean is that the actual symbols are arbitrary to me.

So for example the grammar with:
{N={α},
Σ={x},
P={α→x},
S=α}

Is equivalent to the grammar:
{N={β},
Σ={y},
P={β→y},
S=β}

Hopefully I am being understood!  I believe this set is countable because for every N and Σ there are only a finite number of production rules which can be formulated.  For example, for:

N={α} and
Σ={x}

The only unique sets of production rules are:

{{α→x}}

{{α→xα}}

{{α→x}, {α→xα}}

There is at least one regular grammar per regular language, and all of them are pairwise inequivalent (for any meaningful equivalence relation). Since there is at least a countably infinite number of regular languages¹, that's a lower bound for the number of regular grammars as well.

Without loss of generality², you can write down every regular grammar as finite string over a finite alphabet. Therefore, there are at most as many regular grammars as binary strings, of which there are countably infinitely many.

Combine the bounds to get your answer.

The lower bounds follows from $\{a\}^n$ being regular for every $n \in \mathbb{N}$.
Encode all symbols using binary numbers.


References for the computational complexity of training neural networks I'm looking for a good review paper or book chapter that offers an accessible introduction to the computational complexity of training neural networks for classification problems.

In particular, I'm trying to study questions like:

How is training complexity related to network topology ?
How is training complexity related to the complexity of the decision boundary?

At present the theory of computational complexity has little useful to say.  This is largely an empirical science: to find out how many epochs of training are needed or is optimal, the only way to know for sure is to try it and see.  While there is some limited amount of theory, the theory isn't very useful in practice.  Ultimately, we don't really understand why deep learning works or how well it works or exactly what conditions are needed for it to work.

Training usually involves a series of epochs.  The time for each epoch is proportional to the time to evaluate the network on each of the training set instances, once.  There's no theory about the number of epochs needed.  However, in many situations the number of epochs is a relatively small number, say, 20-100 -- not always, but fairly often.  So, that gives you some idea.

Ultimately, topology doesn't seem to affect training time much except insofar as it affects the time to evaluate the classifier on an instance.  It could influence the number of epochs too, but on many networks seen in practice, it doesn't seem to have a large influence for many of the architectures we use in practice.  However, this could be a consequence of the fact that we typically select architectures that do perform well with a reasonable amount of training (i.e., the architecture is often selected so a huge number of epochs isn't needed).  In any case, this isn't a   hard-and-fast rule.

Bottom line: ultimately, we understand very little about the complexity of neural networks, the complexity of training, or rigorous/well-founded/provable answers to your questions.


Asymptotic runtime of a nested sum i have to calculate the asymptotic runtime of a nested sum:

Sum $\sum_{n=1}^{log_{4}(n)} \sum_{n=1}^{\sqrt{n}}1$

My solution is $\Theta(log(n) \cdot \sqrt{n})$, which is wrong, because the solution says $\Theta(\sqrt{n})$. I dont understand where my mistake is:

Sum $\sum_{i=1}^{log_{4}(n)} \sum_{j=1}^{\sqrt{n}}1 =  \sum_{i=1}^{log_{4}(n)} \sqrt{n} = \sqrt{n} \sum_{i=1}^{log_{4}(n)}1 = \sqrt{n} \cdot (log(n)+1) =$
 $ log(n) \cdot \sqrt{n} + \sqrt{n} \stackrel{?}{=} \Theta(log(n) \cdot \sqrt{n}) $

Maybe my formula is wrong. Here is the pseudo-code i have to analyse:

someFunc(n)
  i = n
  while (i >= 1)
   i=i/4;
   //we do sqrt(i) operations
   for j=1 to sqrt(i)
     do_some_atomic_op() //O(1)
   end
   //i will reduce in every step!
  end
end

In fact you do change the value of $n$, see $n=n/4$, and so the while-loop results in  $\sum_{i=1}^{\log_4{n}}{\sqrt{i}}$ which is equal to $\sqrt{1} + \sqrt{2} + \dots + \sqrt{\log_4{n}}$.

Upper bound
$\sqrt{1} + \sqrt{2} + \dots +\sqrt{\log{n}} \leq \log{n}\sqrt{\log{n}}$ which is less than $\sqrt{n}$ for sufficiently large $n$s (you may prove it using induction or using some other techniques).


Transformation Function: Gonzalez and Woods I have been reading Image Processing from Gonzalez and Woods and in the chapter Image Transformation I have come across this equation

$$
T \left(u, v\right)
=
\sum_{x=0}^{M-1}
{
  \sum_{y=0}^{N-1}
  {
    f \left(x, y\right)
    \,
    r \left(x, y, u, v\right)
  }
}
\,.
$$

I am unable to understand this mathematical notation. Any help will be highly appreciated. Thanks

Those ${\sum}\text{-signs}$ specify sigma notation.  They're basically like for loops where you keep summing up the value specified in the body.

The equation,
$$
T \left(u, v\right)
=
\sum_{x=0}^{M-1}
{
  \sum_{y=0}^{N-1}
  {
    f \left(x, y\right)
    \,
    r \left(x, y, u, v\right)
  }
}
\,,
$$

translates into:

public double T(double u, double v)
{
    var sum = 0.0;

    for (int x=0; x <= M-1; ++x)
    {
        for (int y=0; y <= N-1; ++y)
        {
            sum = sum + (f(x, y) * r(x, y, u, v));
        }
    }

    return sum;
}

In other words, it defines some function, $T \left(u, v\right) ,$ that takes two input variables: $u$ and $v .$  You also need to know two other functions: $f \left(x, y\right)$ and $r\left(x, y, u, v\right) ,$ which means you'll need at least 2 more equations.

Then:

Start with a starting total value of $0 .$
Set $x$ to $0 .$
Set $y$ to $0 .$
Calculate $f\left(x, y\right) r\left(x, y, u, v\right) ,$ then add this value to the total.

On the first evaluation, $x=0$ and $y=0 ,$ so that's $f\left(0, 0\right) r\left(0, 0, u, v\right) .$

Increment $y .$

If it's still less-than-or-equal-to $N - 1 ,$ then go back to Step (4).

Increment $x .$

If it's still less-than-or-equal-to $M - 1 ,$ then go back to Step (3).

The final total is the calculated value for $T \left(u, v\right) .$


reinforcement learning in gridworld with subgoals Andrew Ng, Daishi Harada, Stuart Russell published a conference paper entitled Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping.

There is a specific example there that I am extremely curious/interested about. It is in Figure 2(a) of the paper:

It is about a 5x5 gridworld with start and goal states in opposite corners. The catch is, the agent must learn to go from start to end BY VISITING specific subgoals 1,2,3,4 IN ORDER.

Has anyone seen/understood the code for this? I want to know how the reward function/shaping is given in this kind of problem.

I am interested to know how the flow of this modification to the grid world is written.

The subgoals are encoded in external rules to determine if a reward is given and in what amount. The creation of the rules and the used features is done manually by experts. There is no algorithm which calculates the reward function by itself.


Extra space of MergeSort Here is my implementation of mergeSort. I need n extra space for the helper array. But what about recursive calls? I call sort log n times. mergeRoutine is a tail call, and it doesn't add to the call stack.

The extra space I need equals to n + log n. How can the extra space be O(n)?

I think we just consider log n negligible.

public class MergeSort {

    private int[] array;
    private int[] helper;

    public MergeSort() {
        this.array = array;
        this.helper = new int[array.length];
    }

    public void sort() {
        sort(0, array.length - 1);
    }

    private void sort(int start, int end) {
        if (end > start) {
            int middle = (start + end) / 2;
            sort(start, middle);
            sort(middle + 1, end);
            mergeRoutine(start, middle, end);
        }
    }

    private void mergeRoutine(int start, int middle, int end) {
        for (int i = start; i <= end; i++) {
            helper[i] = array[i];
        }
        int k = start;
        int i = start;
        int j = middle + 1;
        while (i <= middle && j <= end) {
            if (helper[i] <= helper[j]) {
                array[k] = helper[i];
                i++;
            } else {
                array[k] = helper[j];
                j++;
            }
            k++;
        }

        // Copy the rest. Either of the while loops works, not both.
        while (i <= middle) {
            array[k] = helper[i];
            i++;
            k++;
        }
    }
}

$O(n)$ denotes the set of all functions $f(n)$ that are, for sufficiently large $n$, at most a constant factor larger than $n$. The notation $f(n) = O(n)$ is confusing because it really means $f(n) \in O(n)$.

E.g. $2n+5 \in O(n)$, $n/2 \in O(n)$, $\sqrt{n} \in O(n)$, $n + log\ n \in O(n)$ (the latter, because indeed $log\ n$ is negligible compared to $n$, e.g. $n + log\ n < 2n$ and $2n \in O(n)$).

However, $n^2 \notin O(n)$ because there's no constant $k$ that can make $n^2 < k n$ for all sufficiently large $n$.


How can the local feature size become arbitrarily small? I am stuck at the following exericse:

Let $\rho$ denote the local feature size. Draw an example where the curve C contains the line segment from $(-1, 0)$ to $(1, 0)$, but where $\rho( (0,0) )$ is arbitrarily small.

Here are the definitions that I heard in class:

Let $C$ be a smooth closed curve in the plane, and let $x$ be a
point of $C$. The local feature size $\rho(x)$ of x is the shortest distance from $x$ to the medial axis of C. (The medial axis $M(C)$ of a closed smooth curve $C$ is the locus of the centers of disks that touch $C$ at two or more distinct points.)

I do not understand how it should be possible for the local feature size to become arbitrarily small, since we are looking at smooth plane curves. I have tried to draw some examples, but the ones I found were always non-smooth, like the one below. (The image comes from Wikipedia's article on cusps.)

As you have suspected, it is impossible for a simple smooth closed curve to contain the line segment from (−1,0) to (1,0) such that its local feature size at $(0,0)$ is arbitrarily small.
On other hand, it is easy to draw a self-intersecting smooth curve with that property. Here is an example.

In fact, for every smooth curve that contains the line segment from (−1,0) to (1,0) and intersects itself at $(0,0)$, its local feature size at $(0,0)$ will be arbitrarily small.


Is the empty problem (or its complement) Karp reducible to any problem in NP? I'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement:

If $\textbf{P}=\textbf{NP}$, the following holds:

For every $A \in \textbf{NP}$, there is a $B \in \textbf{NP}$ such that $A \leq B$ (where $\leq$ means Karp reducible).

However, I do not understand how this applies to the empty problem $\emptyset$, and it's complement $\Sigma^*$, as these only have no-instances and yes-instances, respectively.

Are there other problems in NP such that these two are reducible to them?

Of course there is.

Just take any non-trivial language $L$ (i.e., $L \neq \varnothing$ and $L \neq \Sigma^\ast$). Then there are concrete words $x \in L$ and $y \not\in L$.

To reduce $\varnothing$ to $L$, simply map everything to $y$. Then the input is in $\varnothing$ (which is false) if and only if $y \in L$ (which is also false). Hence, the reduction is correct.

For $\Sigma^\ast$, do the same but use $x$ instead.

As a note: I assume you are puzzled about $A$ being reduced to $B$. Obviously, in the statement you cite $B$ should at the very least be a non-trivial set (and it seems $\textbf{P} = \textbf{NP}$ is redundant, as Tom van der Zanden notes in the comments; in fact, the statement is rather fishy, see David Richerby's answer); note you cannot reduce non-trivial sets to $\varnothing$ or $\Sigma^\ast$ (and you cannot reduce either to one another, as David Richerby points out in the comments).


What is the meaning of max() in intro. to algorithms? I'm reading chapter 3(growth functions) of CLRS and in giving an example of proving theta for a standard quadratic function the book gives the following value for $n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a})$ .

I'm confused regarding what "max" means in this context. The quadratic function is $an^2 + bn + c$ and the constants give are $c_1 = a/4, c_2 =7a/4$.

I'm thinking it might mean which ever of the parameters yields a larger value?

Yes, as confirmed by Gokul, $\max(p,q)$ just means the larger one of its two parameters, $p$ and $q$. It can also apply to more parameters such as $\max(p, q, r, s, t)$, where it means the largest of all 5 variables or values.

Its opposite is $\min$, which is used in the same way but means the smaller one of two values or the smallest one of all given values.

You might want to check the list of mathematical abbreviations the next time you get confused by some math abbreviations.


How can the initial "booting" state of a computer be different at different time points? In my experience, sometimes a computer boots normally, and in a time span of days, the computer won't boot, then again, it will boot normally again. I am not a computer science expert so I assume that if a computer boots normally one time and then it doesn't, it must be due to any changes made into the computer between those time points.

My question has the motivation of understanding the booting process of a computer at a basic level as to know how to debug such a behavior.

For a concrete example, I got a new computer with Ubuntu 18.10 that presented this behavior, all the time without access to internet, so no updates/upgrades possible.

Can anything change in a computer without the user modifying something, also while not having internet connection?

Can anything change in a computer without the user modifying something, also while not having internet connection?

Yes, definitely - computers update their own states all the time, and some of these changes will be persistent from one boot cycle to the next.

The computer itself is a complex piece of hardware, and the operating system is a complex piece of software. Both the computer (at a hardware level) and the operating system will carry out a series of self tests during the boot process. The results of some of those self tests will be stored in non-volatile memory (e.g. in some form of registry). When the computer is re-booted, the results of the self-tests from the previous boot attempt may affect the route taken through the boot process the next time around. This might avoid a problem encountered in the previous boot cycle (e.g. by loading a previous version of a corrupted driver), but it may also introduce a new problem not seen before.

In short, part of the boot process will be a check to see if the previous boot cycle was successful. If not, there may be logic in the boot process that tries a different sequence of actions, or boots into a restricted "safe" mode.


Why Halting problem is Recursively Enumerable? If we take this definition as R.E. set definition (Computability, Complexity and Languages book written by Davis in page 79)

$Definition.$The set $B\subseteq N$ is called r.e. if there is partially computable function $g(x)$ such that
$B = \{x \in N | g(x) \downarrow\}$

Halting problem is set of $(x,y)$ which program with number $y$ halts on $x$, I really can't understand when there is no program for Halting problem then what $g(x)$ is going to be applied for it?

If you want to understand Halting Problem is r.e. by Davis Book notation and you are looking for g(x) you can think of universal program! universal program is the function $\phi (x,y)$ that is the program which run program number $y$ on input $x$.
This program is equal to partially computable function g(x) (see page 30 definition of partially computable). As Ran G mentioned, it is possible program y on input x never halt! That's the reason it is partial function not computable function(i.e. it is both partial and total)

+If function g(x) be computable then the set B will be computable or in the other words it is decidable.


Why Study Complexity Theory? I’m an amateur in the study of algorithms. For a while I’ve had a burning question, why  do we study complexity theory in computer science? The reason I ask is because algorithms with better asymptotic complexity are not always faster for practical purposes, in fact they can be absurdly slower. Why not instead develop a theory that better suits the practical needs of scientific research and industry?
As an example, it is known that developing an algorithm to determine a perfect chess game can be done in $O(1)$, as the number of legal chess games on an 8×8 grid is bounded from above. However, I have heard this algorithm would take longer than the age of the universe to terminate. This begs the question, why complexity theory? It seems to me the field is fundamentally flawed, and computer scientists should be using a better approach for the study of algorithms.
(Note: My sincere apologies to researchers in the field. ☻)

This is not a simple question, and you shouldn't expect a simple answer.  There are a range of similar questions in this space: why do we study asymptotic running time?  why do we use asymptotic running time analysis to analyze algorithms?  why do we study complexity theory?  Each of those has multiple answers; there is not just a single reason why we do it, and different people may have different reasons.
Asymptotic running time analysis has advantages and disadvantages.  You've accurately identified one of the disadvantages: a good asymptotic running time doesn't guarantee good running time in practice.  But if you focus on only a single advantage or disadvantage you're not going to get the full picture of the strengths and weaknesses of that style of analysis.  Some of the advantages are that analysis is relatively tractable, it is not specific to a particular architecture, it provides useful information about scalability, and at least some of the time it has useful predictive power at identifying algorithmic bottlenecks.  For instance, the difference between a $O(n^2)$ time algorithm and a $O(n \log n)$ time algorithm can often be significant, even if we are ignoring the constant factors.  Some of the disadvantages are that constant factors can be important, cache and memory hierarchy effects can be very important yet are ignored by asymptotic running time analysis, and (like any metric)  optimizing solely for asymptotic running time can lead to absurd results of little practical utility (see galactic algorithms and Goodhart's law).
I think it's also useful to examine the alternative.  I encourage you to explore the alternative to asymptotic running time analysis and work through what you'd propose in its stead.  If you don't try to come up with a concrete proposal, it's easy to assume that it can't be that hard to find something better... but when you're forced to commit to something specific, you might discover that it's more challenging than you anticipated.  For instance, I encourage you to familiarize yourself with Knuth's analysis of algorithm running time on MIX in his TAOCP series.  There he does concrete running time analysis, with no asymptotics, taking into account the constant factors.  If you force yourself to work through the details of that, you'll quickly discover the disadvantages of that: it's super-tedious, very specific to a particular computer architecture, and often not much more enlightening.
We could similarly discuss each of the other topics - e.g., why or why not to study complexity theory - and you'd find that they too have nuances.
I also want to highlight for you that the theory and algorithms community is a broad one, with a range of different styles of work.  You seem to be lumping it all together into one pile, but there's a spectrum of work: some of it is super-theoretical and far afield from practice, some of it is highly practical and motivated by concrete problems and may have immediate impact, and there is a range of work at various point in between those extremes.  I think it's important to understand that there is some work in the theory community that is of great practical relevance or has had major impact, just as there is work that much more theoretical and not motivated by near-term impact.
Since you asked for theoretical frameworks that are focused on meeting industry's needs, you might also be interested in the Word RAM model, cache-oblivious algorithms, and the parallel external memory model.
I strongly encourage you to read the following resources, as they are closely related to your question: Why polynomial time is called "efficient"?, Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms, Justification for neglecting constant factors in Big O.


What is the difference between an embedded system and dedicated system? To my understanding,

a dedicated system is a computer system capable of performing 1 specific task
an embedded system is a computer system within a larger system that performs a specific task

Is there a difference that i'm missing or is dedicated system just a more generic term for referring to things like 'file server'.

Thanks

An embedded system is embedded in some larger device/system. For example, a computer used to control a car is embedded, or the microprocessor controlling e.g. a washing machine.

A dedicated system is one which is used for one task only, like file serving or running a database.

Most embedded systems are dedicated (to their specific task(s)). There isn't a clear cut definition.


How and which component of an Operating System is responsible for the transition of a process from the blocked state to the ready queue? A process in an Operating System is considered to occupy several states and a process transitions between these states. A scheduler is responsible for assigning CPU time to a process. However, a process that is performing an Input Output Operation and has gone into the blocked state must transition to the ready state or the ready queue to be more precise to be considered for scheduling by the scheduler. Which component of the operating system handles this transition? And does this transition require any CPU time for operation?

When an I/O is started, it will typically have an I/O request structure associated with it that includes items like the process ID that the I/O belonged to.  When the I/O completes the device driver will typically fork into an OS level I/O subsystem in the OS which will queue the IO request packet notification to the process and move the process to a computable queue.  (this may vary a little from one OS to another).   The process then waits for it's turn to become computable.

And yes, anything that executes code requires CPU time... though this is considered "interrupt time" rather than user time.


How do you correctly write this sentence as a CTL formula? Sentence: From every reachable state it is possible to reach a state where $p$ is true.

How do you write this sentence as a CTL formula? So far I only dealt with CTL syntax and trees but maybe it will also be asked in a test how you convert a sentence to a CTL formula..

So I've read that $AX$ means all next.

Then $AXp$ should mean in all next states $p$ is true.

Now I only need the first part of the sentence: From every reachable state it is possible to reach

But how would this be expressed and how do you connect it with the $AXp$ I got?

I hope you can help me because on the internet I couldn't find some example like that? : /

You can learn a lot about CTL at Wikipedia page.

The sentence you need to write, expressed more closely in the vocabulary of CTL operators, would be
Along all paths starting from current state, it always has to hold that there exists at least one path where $p$ eventually is true.

I think you can take it from there, but comment if you have troubles.

hint: The operators you will need to use are $F$, $A$, $E$ and $G$.


Find the minimum set of intervals for given set of numbers For any given set of real numbers, find the minimum set of intervals with length 1 that include all elements. For example, for the set: $${\{1.5,2.3,2.4,2.5,2.8,3.3,3.6,3.8}\}$$
the answer is $${\{[1.5,2.5],[2.8,3.8]\}}$$

On the example above $[1.5,2.5]$ is an interval with length $1$ ($2.5-1.5=1$). And there are 2 sets of intervals ($[1.5,2.5]$ and $[2.8,3.8]$).

I need to find the most efficient greedy algorithm for this problem with $O(n\log n)$ time complexity.

My thought is to sort the elements in ascending order (using merge sort for minimum time complexity) and then, starting from the first element, use the current element as the lowest limit, and (element+1) as the highest limit.

This has a running time of $O(n\log n + n)$. $n\log n$ from mergesort and $n$ for running through the elements to decide the intervals.

But I can't tell whether this is the most efficient greedy algorithm I can use for this problem.

To show that the problem has a lower bound of $\Omega (n\log n)$, you can reduce the Element distinctness problem to your problem.


How to reduce the original partition problem to one of its variation? Here's a statement of the set partition problem:
The set partition problem takes as input a set $S = \{ a_1, a_2, ..., a_n \}$(all positive integers). Can $S$ be partitioned into two sets $A$ and $B$ such that the sum of the numbers in $A$ is
equal to the sum of the numbers in $B$?
Here's a statement of a variation of the set partition problem:
Given an input set $S = \{ a_1, a_2, ..., a_n \}$ (all positive integers), can you partition $S$ into $A$ and $B$ such that $| \sum_{i \in A} a_i - \sum_{i \in B} a_i| < 1000$?
My goal is to show that the variation is NP-complete by reducing the set partition problem to the variation, and here's what I've tried:

Given an instance of the set partition, $S$, let the total sum of its elements be $s$, then create a set $S \cup \{ s + 1000, s \}$ as an instance for the variation. But this doesn't seem to do the trick.
Given an instance of the set partition, $S$, do something to the elements in $S$ (for example, multiply by 2, subtract by 1000). This path feels promising but I'm again stuck.

Thanks to D.W.'s generous help, I managed to figure it out. Given an instance of the Partition problem, $S$, we can just scale every element in $S$ by 1000, and the new $S'$ becomes an instance of the variation. Then the reduction mapping holds, because scaling increases the difference between numbers. If $S$ is a YES instance, $S'$ can also be partitioned into two sets with equal sum, but if $S$ is a NO instance, all of the possible partitions of $S'$ must have difference $\geq 1000$. The reduction is clearly polynomial, and the variation is clearly in NP, so proof is complete.


Is a k counter automata a special kind of PDA? I understand that a 1 counter automata is a special kind of PDA where the stack alphabet consists of one symbol (ignoring the fixed bottom symbol) but what about 2 counter automata? Is it a special kind of PDA where the stack alphabet consists of two symbols? Can we generalize like so: a k-counter automata is a PDA with k many symbols in the stack alphabet where k>0?

A two-counter automaton has two counters, so two push-downs, each with a single stack symbol (agaun ignoring bottom). Such an automaton is not equavalent to push-down automata.

Any PDA can be shown to be equivalent with a PDA with two different stack symbols, so in itself characterize the context-free languages.

Two-counter automata are much more powerful, they can simulate Turing machines, and hance form the recursively enumarable languages.  The special bottom symbol is essential here. In that way the machine is able to do a zero test (i.e., check the contents of the counter is zero). The simulation of TM's by counter automata is explained in the old textbook by Hopcroft and Ullman (Intro to Automata Theory, Languages, ...)  in two steps. First using four counters and coding the contents of (half of) a working tape of a TM by a single number. The result is attributed to Minsky (1961).


Proof of greedy algorithm to minimize cost of job assignment over unlimited number of machines I'm trying to prove a greedy algorithm works for a specific problem:

  You have $n$ jobs and some finite number of machines. (The number of machines doesn't matter; we assume you have enough to run all the jobs.) Each job $j$ has a size $s_j$. Each machine $i$ has a constant associated with its speed, $p_i$. The cost of running job $j$ on machine $i$ is simply $s_j \cdot p_i$. We can only assign at most $k$ jobs to one machine. How should the jobs be assigned to minimize the sum of the costs on all machines (that have been given jobs)? I.e., minimize $\sum_{i,j} s_j \cdot p_i$ over all assignments of a job $j$ to a machine $i$. (Note that there is no penalty for assigning lots of jobs to a specific machine. We aren't trying to balance out the number of jobs assigned to each machine.)

The simple greedy algorithm is to first sort the jobs from greatest size to least size, and the machines from fastest (least $p_i$ in this case) to slowest, and then assign the $k$ largest jobs to the fastest machine, second $k$ largest jobs to the second fastest machine, etc. (So in other words, pair off large $s_j$ with small $p_i$ and vice versa.)

I'm now trying to prove this algorithm is correct. My first try was to show that the greedy algorithm stays ahead. I reasoned that the optimal algorithm must also use the fastest machines (or else it is trivial to show it isn't actually optimal), and therefore if we look at the machines from fastest to slowest, we can consider the first job for which they differ. But then it isn't necessarily true that the greedy algorithm is doing better at this point as the optimal algorithm could minimize cost for that specific slot by putting in a smaller job (even though it actually hurts it later).

I also tried doing an overall induction on the number of jobs. Say we show it it optimal for $n$ jobs. Can we show it is optimal for $n+1$ jobs given the same options for machines? Again, it isn't clear how to make this argument since we can't just slide in job $n+1$; maybe the optimal assignment suddenly follows a wildly different pattern.

Thanks for the help!

I figured it out. Turns out the solution is deceptively simple, but in the details it is somewhat different than proofs I have seen for other greedy algorithms. We basically show that any output besides the one the greedy algorithm returns can be improved further.

To do this, consider two jobs with sizes $s_j$ and $s_i$ such that $s_j > s_i$. Furthermore, consider two machines with constants $p_l, p_k$ such that $p_l > p_k$. We show that the best way of assigning $s_j, s_i$ to $p_l, p_k$ is to assign $s_j$ (the larger job) to $p_k$ (the faster machine) and $s_i$ (the smaller job) to $p_l$ (the slower machine). Since there are only two possible assignments, in other words we want to show $$s_j \cdot p_k + s_i \cdot p_l \le s_j \cdot p_l + s_i \cdot p_k$$

To do so we set $s_i = x, s_j = x+a, p_k = y, p_l = y + b$ for some $x,y,a,b \ge 0$. So equivalently we want to show $$(x+a)\cdot y + x \cdot (y + b) \le (x + a)(y + b) + xy$$

This can be seen simply by simplifying. Thus we have shown that for two jobs and two machines, cost is minimized by assigning the larger job to the faster machine and the smaller job to the slower machine.

It quickly follows that the greedy algorithm is optimal because for any other output, there will be a pair of assignments that don't satisfy the "larger job to faster machine, smaller job to slower machine" rule. And thus by switching the assignments of this pair, we lower the total cost.


Stable marriage problem preferential to asking side Watching this youtube video: https://www.youtube.com/watch?v=w1leqkpDaRw it described the problem with the stable marriage problem, that the asking side get a better deal then the asked site. Meaning that the result may differ if the woman ask the men instead of the men asking the women.
I have test this and found it to be true, but i can not find any scientific papers on this, so i where hoping that some of you guys might know of one or more?

One place to look at is the classic book The stable marriage problem. The link provides a relevant excerpt, showing that the matching produced by the standard Gale–Shapley algorithm is male optimal and female pessimal: any man gets the best possible partner (in his view) he can get in any perfect matching, and any woman gets the worst possible partner (in her view) she can get in any perfect matching. If we switch men and women, we will obtain the female optimal, male pessimal matching.

The quoted book, as well as Knuth's book on the subject, contain other material on stable marriages, including the number of different stable marriages, the lattice structure of stable marriages, sampling a random stable marriage, related problems such as the stable roommate problem, and much more.

From another angle, a distinctly different algorithm for the stable marriage problem has been developed by Subramanian and picked up by Feder; see for example Section 6 of this paper.


How to approach DFA construction with substring constraints? We have to construct a DFA over the alphabet 0 and 1 for:

  Every substring of four symbols has at most two 0's. For example, 001110 and 011001 are in the language, but 10010 is not since one of its substrings, 0010, contains three zeros.

I haven't reached to regular expression in the book which I am using. I am currently in unit 2 and regular expressions is from unit 3.

Use the state of the automaton to "remember" enough information about the string that you've seen so far to allow you to determine whether the string you've read is in the language. This is true essentially independently of the language you're trying to recognize.


Symmetry of IP complexity class Wikipedia defines the IP complexity class as follows:

  A language $L$ belongs to IP if there exists $V,P$ such that for all
  $Q$, $w$,
  $$w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$
  $$w\notin L\Rightarrow Pr[V\leftrightarrow Q\text{ accepts }w]\leq1/3$$

Note that this definition is asymmetric; it says (if we are polynomial-bound) we can be convinced $w\in L$, but says nothing about convincing us that $w\notin L$. We could define a class coIP containing the complements of languages in IP; that is

  A language $L$ belongs to coIP if there exists $V,P$ such that for all
  $Q$, $w$,
  $$w\notin L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$
  $$w\in L\Rightarrow Pr[V\leftrightarrow Q\text{ accepts }w]\leq1/3$$

It turns out IP=PSPACE and clearly PSPACE is symmetric under taking complement. Thus IP=coIP. Is there a direct way to see this? That is,

  Given a proof system $(V,P)$ for proving membership in $L$, can we use
  it to construct a proof system $(V',P')$ for proving membership in
  $\bar L$?

There is no relativizing technique to show that $\mathrm{IP}$ is closed under complement.

Clearly, $\mathrm{NP}\subseteq\mathrm{IP}$.

Fortnow and Sipser gave an oracle relative to which $\mathrm{co}$-$\mathrm{NP}$ does not have interactive proof system.

So, you have to study the arithmetization technique that settles down this conjecture (long ago).

Are there interactive protocols for CO-NP


Is there a universal learning rate for NeuralNetworks? I'm currently creating a NeuralNetwork with backpropagation/gradient descent. There is this hyperparameter introduced called "learning rate" (η). Which has to be chosen to guarantee not overshooting the minimum of the cost function when doing gradient descent. But you also do not want to slow down learning unnecessarily. It's a tradeoff. I've found that for too small or too big η the NeuralNetwork doesn't learn at all.

I've successfully trained the NN on the sin-function with η = 0.1. But for other functions like any linear combination of the inputs, a different η is required (more like η = 0.001). For the quadratic function, I still haven't been able to make the NN converge at all, maybe I just haven't found the right hyperparameters.

My question now is:
Is there any way I can find a η that works for any function, so I don't have to try and search for it manually.

Thanks in advance,
Luis Wirth.

There is no universal learning rate. It depends on your problem space (Are you solving a problem with many local minima or just one? Does your problem’s solution vary dramatically based on a slight change to your input or does the solution gradually shift?, etc.), and it depends on your network architecture (number of layers, number of hidden layers. Do you have a feedback loop etc).

Character recognition is relatively easy for example so you could try a faster learning rate. I once tried to teach a neural network to understand a simple computer machine code, and after a month of training with a dozen computers, it always came close but never solved the problem 100% correctly. No choice of learning rate worked to get me to the solution.

Once I broke down the problem space into a few subcomponents, the entire set of neural networks were trained in under an hour. I used the same choice of training rate in both cases (see below). A good example of how the rate of convergence changes based on the problem being trained.

What I found works best is to start with a fast learning rate to quickly find local minima, but then reduce the rate with each successive training, down to some limit.

All that to say that there is no universal learning rate, and that it worked best for me to reduce it as the training proceeds.


Is the power of a regular language regular? Is the root of a regular language regular? If $A$ is a regular set, then:

$L_1=\{x\mid\exists n \geq0, \exists y \in A: y=x^n\}$,

$L_2=\{x\mid \exists n \geq0, \exists y\in A: x=y^n\}$.

Which one of them is regular?

My reasoning is since in $L_2$ we can have uncountable $x$ from even one value of $y\ (y^0, y^1, y^2,...),\ L_2$ cannot be regular. But that thinking seems wrong.

The language $L_2$ is not necessarily regular. Indeed, consider $A = a^*b$. If $L_2$ were regular, then so would the following language be:
$$L_2 \cap a^*ba^*b = \{ a^nba^nb : n \geq 0 \}.$$
However, this language is not regular (exercise).

In contrast, the language $L_1$ is regular. We can see this by constructing a DFA for it. Let the DFA for $L_1$ have states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$. The states of the new DFA are labeled by functions $Q \to Q$. The idea is that the new DFA is at state $f\colon Q \to Q$ if the original DFA moves from state $q \in Q$ to state $f(q)$ after reading $w$ (i.e., if $\delta(q,w) = f(q)$ for all $q \in Q$). The initial state is the identity function. When at state $f$ and reading $\sigma$, we move to the state $g$ given by $g(q) = \delta(f(q),\sigma)$. A state is accepting if $f^{(n)}(q_0) \in F$ for some $n \geq 0$.


Bellman-Ford algorithm - Why can edges be updated out of order? The Bellman-Ford algorithm determines the shortest path from a source $s$ to all other vertices. Initially the distance between $s$ and all other vertices is set to $\infty$. Then the shortest path from $s$ to each vertex is computed; this goes on for  $|V|-1$ iterations. My questions are:

Why does there need to be $|V|-1$ iterations?
Would it matter if I checked the edges in a different order?
Say, if I first check edges 1,2,3, but then on the second iteration I check 2,3,1.

MIT  Prof. Eric said the order didn't matter, but this confuses me: wouldn't the algorithm incorrectly update a node based on edge $x_2$ if its value was dependent on the edge $x_1$ but $x_1$ is updated after $x_2$?

Consider the shortest path from $s$ to $t$, $s, v_1, v_2, \dots, v_k, t$. This path consists of at most $|V|-1$ edges, because repeating a vertex in a shortest path is always a bad idea (or at least there is a shortest path which does not repeat vertices), if we do not have negative weight cycles.

In round one, we know that the edge $(s, v_1)$ will be relaxed, so the distance estimate for $v_1$ will be correct after this round. Note that we have no idea what $v_1$ is at this point, but as we've relaxed all edges, we must have relaxed this one as well. In round two, we relax $(v_1, v_2)$ at some point. We still have no idea what $v_1$ or $v_2$ are, but we know their distance estimates are correct.

Repeating this, after some round $k+1$, we have relaxed $(v_k, t)$, after which the distance estimate for $t$ is correct. We have no idea what $k$ is until the entire algorithm is over, but we know that it will happen at some point (assuming no negative weight cycles).

So, the crucial observation is that after round $i$, the $i$-th node of the shortest path must have its distance estimate set to the correct value. As the path is at most $|V|-1$ edges long, $|V|-1$ rounds suffices to find this shortest path. If a $|V|$th round still changes something, then something weird is going on: all paths should already be 'settled' to their final values, so we must have the situation that some negative weight cycle exists.


Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials Let's have expressions that are composed of elements of $\mathbb N$ and a limited set of binary operations {$+,\times,-,/$} and functions {$\exp, \ln$}. The expressions are always well-formed and form finite trees, with numbers as leaf nodes and operators as internal nodes, binary operations having two child sub-expressions and the functions one. A value of such an expression is interpreted to mean some number in $\mathbb R$.

There are two limitations on the structure of the expressions: the divisor (the right-hand sub-expression) of $/$ can't be 0 and the argument of $\ln$ must be positive.

I have two questions about these kind of expressions:

Is it possible to ensure "soundness" of such an expression, in the sense that the two limitations can be checked in finite time?
is an equality check between two such expressions decidable?

These questions seem to be connected in the sense that if you're able to check equality of the relevant sub-expression to zero, you can decide whether a division parent expression is sound, and it doesn't seem hard to check whether a sub-expression of $\ln$ is positive or negative if it's known not to be zero.

I know that equality in $\mathbb R$ is generally not decidable, whereas equality in algebraic numbers is. However, I wonder how inclusion of {$\exp, \ln$} changes the result. I suspect that if there exists "pathological cases" where two expressions with dramatically different structure result to the same real number, checking the equality between them might be undecidable, as the $\exp$ and $\ln$ might hinder the normalization of such expressions.

(A side note: I posted an earlier version of a question with similar intent here, but it turned out to have too little thought behind it, and had unnecessary (= not related to the meat of the question) complications with complex logarithms.)

I don't know, but I suspect it's an open question.

If the theory of the reals with exponential function is decidable, then your problem is decidable, too.  It is known that if Shanuel's Conjecture holds, then the former is decidable, so your problem is too.

If I understand correctly, the following paper tackles your problem:

The identity problem for elementary functions and constants.  Dan Richardson, John Fitch.  ISSAC '94.

It appears that they show a procedure that always terminates if Shanuel's Conjecture holds; and if it doesn't terminate for a particular expression, then we can extract from that expression a counterexample to Shanuel's Conjecture.  They then argue that it seems unlikely that we will find a counterexample any time soon, so it seems unlikely we will find inputs on which this procedure fails to terminate any time soon.

See also https://mathoverflow.net/q/118972/37212 and https://mathoverflow.net/q/129563/37212 and https://mathoverflow.net/q/145299/37212.


Is P = {  | M rejects w} the complement to Atm = {  | M accepts w}? As Atm is recognizable, its complement cannot be recognizable, due to being so Atm would be decidable.
I am trying to clarify if the problem P is the complement to Atm.
If so, how could i approach the problem without looking at Atm to prove undecidability?
My first thought was:

H is a machine which solves P:
H halts and accepts when M rejects w.
H halts and rejects when M accepts w.

And from then on contradict the construct like in the proof of Atm.

The answer to the question in the title (is $P$ the complement of $A_{tm}$) depends on several issues. To see why, let's start by computing the complement of $A_{tm}$:
$$
\overline{A_{tm}} = \{ \langle M,w \rangle : M \text{ does not accept } w \} \cup \{ x : x \text{ is not of the form } \langle M,w \rangle \}.
$$
If you choose an encoding for $\langle M,w \rangle$ for which there exist strings which are not of the form $\langle M,w \rangle$, then $P$ is definitely not the complement of $A_{tm}$. However, there do exist encodings in which you can decode any string into a Turing machine and an input string. In that case,
$$
\overline{A_{tm}} = \{ \langle M,w \rangle : M \text{ does not accept } w \}.
$$
You are asking whether this is the same as
$$
P = \{ \langle M,w \rangle : M \text{ rejects } w \}.
$$
The question is how you define acceptance and rejection. Here is one possible definition:

  A Turing machine accepts an input if it halts on an accepting state. It rejects an input if it halts on a non-accepting state.

Under this definition, there is also a third option: the Turing machine never halts. So $P$ and $A_{tm}$ are not complements of each other. Here is another definition:

  A Turing machine accepts an input if it halts on the input. Otherwise it rejects it.

Under this definition, $P$ and $A_{tm}$ are complements of each other. If you define the language of a Turing machine as the set of strings it accepts, then both definitions are equivalent (you can modify a Turing machine to fit either), but the exact choice does matter for your particular question.


How to find an algorithm's complexity from actual running times I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of instances, which grow in size as a function of $n$.

Now, I have collected running times from $n = 1$ up to $n = 5000$, which is as far as my computer can go in a reasonable amount of time.

I have plotted my data using Python and I have made some simple regression (exponential, cuadratic, cubic...), but I still can't get to decide which function best fits the algorithm. Obviously, if I try regression with a polynomial of higher degree, I will get a tighter curve, so in case the running time is a polynomial in $n$, I don't know how I could decide which is the one that really fits.

With instances up to $n = 1000$, it seems like the cubic polynomial is the best approximation. However, when I plot the instances up to $n = 5000$, things become less clear (in the second graph I compare the actual running times against the approximations obtained for up to $n =1000$, while the first one compares against the the approximations up to $n = 500$)

(in addition, I feel there is something off with float point calculations, as two of the curves below get really messy)

Any suggestions?

A bit of context: I am working on a particular class of hard Quantified Boolean Formulas (QBF) and I want to test their running times on different available QBF-solvers. These formulas verify a certain interesting property: they have linear size proofs in the QU-resolution proof system. However, QBF-solvers act as block boxes for me, and, altough I can see from data that they do not have the "predicted" linear running times, I would like to know how is the growth in complexity in these particular instances. Particularly, it would be great to give some approximate bound or even confirm that they do not seem to have an exponential growth. Thanks.

You can do regression on the whole data to get a better fit.


Number of non-XOR gates needed to implement an n-bit boolean function There are $2^{2^n}$ possible functions that have $n$ boolean inputs and a single boolean output. Some of these functions have very short boolean logic circuits. Some have longer circuits.

A classic result in circuit complexity is that, if you count the total number of gates needed to implement $f$, most $f$s take $\Theta(2^n/n)$ 2-to-1 boolean gates. I'm interested in a slightly different metric, where you can use as many XOR gates as you want but you don't count them (ditto for NOT gates, which are just a XOR with one input constant). So your circuit could have $n$ AND gates plus $2^n$ XOR gates, and I'd call that a circuit of non-XOR-size $n$.

I've figured out that it's possible to implement any $n$-input function $f$ using at most $2^{n/2+1}$ gates that aren't XOR or NOT. The strategy works by using $2^{n/2}$ AND gates (with XOR gates interspersed) to prepare a set of $2^{n/2}$ indicator bits that can be XOR'd together to make any function of $n/2$ bits. I then pretend the top $n/2$ bits of the input index register are "choosing" the sub-function to apply with the bottom $n/2$ bits, and use my indicator bits to prepare the $2^{n/2}$ possible sub-function outputs. I then use $2^{n/2}$ AND gates to mux out the desired sub-function output (selected by the top $n/2$ bits of the input index register).

I'm interested in knowing is it possible to do better than $2^{n/2+1}$ AND gates, or is that asymptotically optimal.

By counting circuits, $2^{n/2 + 1}$ appears to be close to asymptotically optimal.

Let $C_{n,k}$ be the number of distinct circuits with $n$ bits and $k$ AND gates.

We lower bound $C_{n,k}$ by noting that we need to choose $k$ such that there is at least as many possible circuits as possible functions, i.e. $2^{2^n} \leq C_{n,k}$.

We upper bound $C_{n,k}$ by noting that every AND gate takes as input a bit which may have had each initial input and each output of a previous AND gate and possibly the constant 1 XOR'd into it. For the first AND gate there are $n + 1$ bits that may or may not be xored into each input of rht AND gate. For the second AND gate there are $n + 2$ bits, for the third $n+3$, and so forth. Then there's $n+k+1$ choices for what to xor into our output bit. Thus $C_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$.

Now we know $2^{2^n} \leq C_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$. By omitting the $C_{n,k}$ in the center we get an inequality in terms of $k$ and $n$ that we can use to bound $k$ in terms of $n$ as follows:

$$\begin{align}
2^{2^n}
&\leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}
\\
&= 2^{n+k+1} \prod_{i=1}^k 4^{n+i}
\\
&= 2^{n+k+1} 4^{\sum_{i=1}^k n+i}
\\
&= 2^{n+k+1} 4^{kn + k(k+1)/2}
\\
&= 2^{2kn + k^2 + 2k + n + 1}
\end{align}$$

Now we start manipulating both sides:

$$\begin{align}
2^{2^n} &\leq 2^{2kn + k^2 + 2k + n + 1}
\\
2^n &\leq 2kn + k^2 + 2k + n + 1
\\
0 &\leq k^2 + k(2n + 2) + (n + 1 - 2^n)
\end{align}$$

Finally, find the quadratic roots where the inequality switches, and focus down to the asymptotically dominant term of the positive root:

$$\begin{align}
k &= \frac{-2n -2 \pm \sqrt{(2n+2)^2 + 4 \cdot (2^n - n - 1)}}{2}
\\
  &= -n - 1 \pm \sqrt{n^2 + 2n + 1 + 2^n - n - 1}
\\
  &= -n - 1 \pm \sqrt{n^2 + n + 2^n}
\\
  &\in \Omega \left(-n -\frac{1}{2} + \sqrt{n^2 + n + 2^n} \right)
\\
  &= \Omega \left(\sqrt{2^n} \right)
\\
\end{align}$$

So it appears that $k$ must be asymptotically at least $\Omega(\sqrt{2^n})$ in order for there to be enough circuits to cover all of the possible functions.


Batch processing in increase-key function using binary heap Is there an algorithm to perform batch processing in the increase-key operation? Let us say, a binary heap (min-heap) is used. In the normal increase-key function, if we perform increase key on one node, then we have to traverse paths from the node towards the children to re balance the heap. If we want to increase the keys of five nodes in the heap, we need to call the increase-key function five times. Is it possible to call only one increase-key function and perform increase-key on five nodes simultaneously?

If $P$ is the number of processing units available, consider $P$-ary heaps¹. When descending to perform some operation on a set of keys, you can fork whenever keys lead to different children. If the heap is balanced, this results in independent taks for a uniformly chosen set of keys (and sufficiently big $n$) after having descended a constant number of levels (claim).

The above can only be expected to work well on shared memory systems. As soon as you have NUMA or distributed memory, you want to assign one subtree to every processing unit (and its memory). I suggest you give the root $P$ children, each of which is an (arbitrary) heap in its own right. All operations are send as messages to the corresponding subtree's processing unit. Operations that need the subtrees to interact block the root.

I think $P$ would be the correct branching degree, but you'd have to do some analysis and/or experiments.


Operations without common elements can not be generated using a finite state automata I heard that some operations involving regexes that do not have common elements can NOT be generated using a finite automata. I do not remember what it was, where it was from, can anyone tell me what that could possibly be?
Edit : I finally managed to find the exact statement. Here it is, below :
A language (like $(00)^n (11)^n$) can not be generated by an FSM since there is no common character in "00" and "11". We need to keep count of both which is not possible with a finite automata as the count can be infinite.

One has to differentiate between regex in computer science and regex in real world programming languages. In compsci regular expressions are defined to only recognize regular languages, which are the same languages DFAs can recognize, thereby making DFAs and regex a descriptions of the same class of languages.
In real world application the recognition of regular languages is somewhat limiting which is the reason why many regex libraries introduce operators which allow you to recognize languages that are not regular. One such operator is recursion (?R) see here for an example using python. Notice that the language in the article is the balanced parentheses language which is a well known context free language that is not regular and thus can not be recognized by a DFA.


Reduction from PARTITION to 3PARTITION I'm considering the problem (a variant of 3-PARTITION, see here) with  description

  Instance: Set of positive integers $A={w_{1},...,w_{n}}$ with $S(A)=\sum\limits_{i=1}^{n}w_{i} = 3m$.

  Question: Is there a partition of $A$ into 3 subsets $A=A_{1}\cup A_{2}\cup A_{3}$ such that $S(A_{1})=S(A_{2})=S(A_{3})$?

I plan to give a reduction from simple PARTITION (into two subsets with equal sum) to this problem that is going like this.

a) Observe that if there is no $A'\subset A$ with $S(A')=2m/3$ then $A$ can't be partitioned into 3 subsets with sum equal to m. (because the premise implies that there's also no subset of A with sum equal to m).

b) Build an instance for PARTITION by taking a subset $A'$ of A with $S(A')=2m/3$. If it is a correct instance of PARTITION then it can be partitioned into sets $B,C$ which combined with $A\setminus A'$ produce a correct instance for the problem 3PARTITION. The other way round (correct instance for 3PARTITION -->correct instance for PARTITION) can be proved by equally simple arguments.

Is this reduction polynomial? I mean, the choice of $A'$ is arbitrary and itself is a correct instance for the problem of SUBSET-SUM for A with target value equal to $2m/3$ which is hard to compute. If this computation plays a part in the transformation then the latter can't be polynomial, right?

I guess that this question should not be left floating around unanswered.

The reasoning in (b) can't be used to prove that this problem is NP-complete because, at best, it implies the reduction from 3PARTITION to PARTITION which is of no use. Any problem in NP can be reduced to PARTITION.

The proper way of doing this (after showing that the problem is in NP) is to:
i) Start from an arbitrary instance of PARTITION

$A=w_1,...,w_n$ with $S(A)=\sum\limits^{n}_{i=1}w_{i}=2m$

ii) Append $m$ to $A$ and obtain $A'$, an instance of the 3PARTITION problem.
iii) Prove that $A\in PARTITION\Longleftrightarrow A'\in 3PARTITION$
iv) Conclude that $PARTITION \leq_{p}3PARTITION$


Can LOOP-Programm stop when its value goes below 0? I am wondering, if in the LOOP programing language, whether instances of the LOOP x DO P END are defined to stop in the case $x < 0$.

The definition only says "Execute $P$, $x$ times" for the above program.

IT is perfectly clear for $x = 0$. However, I believe in order to keep the language simple the definition doesn't extend to the case $x < 0$.

If it were possible, then it would for instance basically shorten a $x_1\ div\ x_2$ operator to just one line:

x_0 = 0;
LOOP x_1 DO x_1 = x_1 - x_2; x_0 = x_0 + 1; END

If it is not possible, is there any other reason except for reasons of convention?

Variables in LOOP programs are non-negative, so the problem never arises; the instruction $x_1 = x_1 - c$ assigns $x_1$ the value of $\max(x_1-c,0)$.

Note that the instruction $x_1 = x_1 - x_2$ isn't allowed: the second operand has to be a constant. However, since $x_1 = x_1 - x_2$ can be implemented in LOOP, the programming language "LOOP with instructions of the form $x_i = x_i - x_j$" has the same power as LOOP.


Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in $\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of polynomials over $\text{GF}(2)$, and (2) reducing the result modulo an irreducible polynomial. We use the "standard" bitstring representation of polynomials, i.e. $x^3+x+1 = [1011]$.

The paper gives an algorithm for calculation of the remainder polynomial on page 16 in Algorithm 3. However, I'm having trouble understanding the reduction algorithm on pages 16-17 (Algorithm 4). Essentially, I think we need Algorithm 4 for larger fields when our or partial results don't fit 128 bits anymore. They give an example for multiplication of two polynomials in $\text{GF}(2^{128})$.

  Where do the "magic constants" 63, 62, and 57 for right shifts, and the "magic constants" 1, 2, and 7 for left shifts come from?

For example, how does one generalize the algorithm for smaller fields, say $\text{GF}(2^{32})$? Would the corresponding shift values then be 15, 14, 9 and 1, 2, 7?

  In the final step 4, the algorithm tells you to "XOR $[E_1:E_0]$, $[F_1:F_0]$, and $[G_1:G_0]$ with each other and $[X_3:D]$".

Why do we do this? As far as I can see, the result of this XOR operation is neither stored anywhere nor used anywhere. Is it somehow used for computing $[H_1 : H_0]$?

The Galois field $GF(2^{128})$ has many different "concrete" representations. One popular representation is using polynomials in $GF(2)[x]$ (i.e. with coefficients in $GF(2)$) modulo some irreducible polynomial of degree $128$, say $x^{128}+x^7+x^2+x^1+x^0$. The magic constants $7,2,1,0$ come from this particular irreducible polynomial. You don't see $0$ since there is no need to shift by $0$. Similarly, the magic constants $57,62,63,64$ are the complements of the constants above with respect to $64$. Again, you don't need to shift by $64$ since the registers are $64$ bits wide. If we had used some other irreducible polynomial, the constants would have been different.

Regarding step 4, $[H_1:H_0]$ results from XORing $[E_1:E_0],[F_1:F_0],[G_1:G_0],[X_3:D]$. This implements the operation of MODing by $x^{128} + x^7 + x^2 + x^1 + x^0$. The idea is that modulo this polynomial, $x^{128} = x^7+x^2+x^1+^0$; addition here is XOR. The different summands corresponds to these different monomials – see if you can find the correspondence.


How to prove NP-hardness of a Hamiltonian Path problem by reducing longest-path problem? I know how to prove longest-path problem by reducing Hamiltonian Path problem.
Here I want to prove NP-hardness of a Hamiltonion Path problem by reducing longest-path problem. (pretend we know longest-path problem is NP-hardness, not Hamiltonion Path problem)
I'm wondering if it is possible to reduce Hamiltonian Path problem to longest path problem.
Is there any way I can do that?

Suppose you have a graph $G$ of order $n$. $G$ has a simple path of length $\geq n - 1$ if and only if $G$ has a hamiltonian path.


Is it possible that the diameter of a graph be shorter than the longest shortest path? I used networkx to find the diameter of a graph that I have. It gave a diameter of 4. However, I found that between two particular nodes, using networkx's shortest path function, the path length is 5. I also coded dijkstra's algorithm and BFS from scratch and both returned a shortest path length of 5 too.

Is anything wrong with this? Isn't the diameter of a graph the longest shortest path?

This is what I'm using: http://vlado.fmf.uni-lj.si/pub/networks/data/Erdos/Erdos02.net

The diameter of a graph is, by definition, the length of the longest shortest path, i.e.,

$$\mathrm{diam}(G) = \max_{x,y\in V(G)} \min\, \{\mathrm{len}(P)\mid P\text{ is a path from }x\text{ to }y\}\,.$$

But remember that the length of a path is the number of edges it contains, not the number of vertices. (That is, a single edge is a path of length 1, not 2.)