context free grammar not closed under relative complement using product construction of pda and dfa Hello friends need a bit of help,

I Know that

given: $$L_1 \in L_{cfg}, L_2 \in L_{reg}$$ $$L_2/L_1\notin L_{cfg}$$
because if it was contex free it would imply that $L_{cfg} $ is closed under complement and this is not true.
But at another glance I can build a product construction of pda and dfa that could solve this problem.

Consider this:

product construction of pda and dfa
at any input read the input and at the same time move through the pda and the dfa
the accept states will be all the states where $(q_1, q_2)$ s.t $q_1\notin A_{pda}  $ and $ q_2\in A_{dfa}$

this machine should accept the language of $L_2/L_1$ and this would imply that this language is infect context free.
I know that some-thing is wrong here but it scares me that I cant understand what... please help.

If you forget about the product-part of this construction (or just consider $L_2=\Sigma^*$) then your proposal amounts to swapping the accepting states of the pushdown automaton. The new PDA has an accepting state iff the original one did not have one.

This is similar to the construction for deterministic finite state automata.
The problem here is that the original PDA is not deterministic. Thus for a single input there might be two computations, one which accepts and the other that does not accept. With your construction both the original and the new PDA will accept that input.

Moreover there might be inputs that do not have a full computation (the machine "blocks"). With your construction both of the PDA will not accept.

PS. In his comment Raphael observes complementation for nondeterministic automata in general has the same flaw when one swaps accepting and nonaccepting states. Many of his links relate to Turing machines, but perhaps especially look at his own answer where the problem relates to finite automata: "Language described by inverting accepting states of NFA"


How do you represent basic arithmetic using boolean function? Say you have an arithmetic problem involving two variables, how do you give a Boolean formula for that using standard techniques so that one gets a minimal formula for a given number of quantifiers?

Consider for example a function that decides if $(1)$ $x>y$ or $(2)$ a function that decides $x|y$?

Hint: Use the standard reduction from CircuitSAT to SAT.  Equivalently: Use the Tseitin transform.

I assume you do know how to write a boolean circuit to test whether $x>y$.  If not, consult a textbook.


Is there $L$ such that $L$ and $\bar L$ are context free, but $L$ is not deterministic context free? The usual candidates for context free languages whose complement is also context free, but they are not regular are the Deterministic Context Free Languages ($DCFL$).

For example, $L=\{a^nb^n\mid n\in\mathbb N\}$ is such language.

  Is there a language, $L\in CFL\setminus DCFL$ such that $\bar L\in
 CFL$?

Since $DCFL$ is closed under complement, this is equivalent of asking whether $$CFL\cap co\text{-}CFL = DCFL$$

See here:

  For every finite, non-unary alphabet, the language of all palindromes is not in DCFL, but in the intersection of coCFL and CFL.


Why does Banded Needleman-Wunsch give alignments with no more than d base pairs of indels? A common modification to the Needleman-Wunsch to reduce running time is to only fill in the cells along a diagonal band of the matrix (slides 27/28). Let 2d + 1 represent the width of the band. Then based on the provided text, this ensures that the total number of inserts and deletes does not exceed d.

However, I can't understand the intuition behind the algorithm. If we let L represent a list of the size of each mutation in the alignment in-order (where negative sizes represent deletions), doesn't the band restriction merely say that the sum of values in any prefix slice of L must stay between -d and d? But the total number of mutations could easily exceed d.

E.g. If d = 4, throughout a long alignment, there could be 5 distinct mutations, where L refers to a series of [insertion, deletion, insertion, insertion, deletion] with sizes: [3,-2,2,1,-4]. Visually, such an alignment would represent a wiggly line through the DP matrix that results in plenty of small insertions and deletions, alternating to ensure that the alignment stays within the band.

In other words, the band does not actually restrict the total number of insertions and deletions as claimed? If I'm misunderstanding something, I'd appreciate any clarification. Thanks!

P.S. Was unsure if this post should go under the bioinformatics stackexchange beta.

You are correct, the number of insertions/deletions $d$ is not constrained (only) by the bandwidth.

However, the algorithm only uses the fact that if we know $d$, then the path must stay within the $2d+1$ band. This band does not have to be tight: a zigzag path would indeed fit within a much narrower band.

You may wonder why the smallest bandwidth (which is indeed equal to the maximum sum over prefixes of your list $L$) isn't used as a parameter instead of $d$. Since $d$ is related to the similarity of the strings, it isn't unreasonable that an upper bound of $d$ is known in some applications. The smallest bandwidth doesn't seem to correspond to a 'natural' parameter in the context of similarity as $d$ does, so it doesn't seem reasonable that it is known and can be used in the algorithm.


Why the universal Turing machine simulation in O(TlogT) cannot be applied to transform multi-taped Turing machine into single-taped? Recently, I've read Hennie's Paper. I understood the construction of buffer zones, but why can't it be applied to yield a single-taped Turing machine?

Just because that UTM itself requires $2$ tapes to do its task that efficient. Removing one tape, the magic is gone.

But assuming you have the fantasy power to do efficient $1$-tape simulation, what gains do we have then?

That should be the question rather than your question.


Huffman code optimal substructure property I am learning about Greedy Algorithms and we did an example on Huffman codes. To prove the correctness of our algorithm, we had to have the greedy choice property and the optimal substructure property.

Here is what my professor said about the optimal substructure property:

Let C be an alphabet and x and y characters with the lowest frequency.

Let C' = C-{x,y}U{z} where z.frequency = x.frequency + y.frequency

Let T' (a binary tree) be an optimal prefix code for C'
She then drew these pictures

Let T be constructed from T' by replacing z with an internal node with children x and y.
Then T is an optimal prefix code for C

And I don't really understand what/how this proves anything. All I see that she is doing is like..working backwards. First she replaced x and y with z, and now she is replacing z with x and y. What exactly is this showing? I'm really bad with proofs sometimes so I am just completely lost as to how this showed me anything about anything

Your teacher are proving:

  Lemma: If $T'$ is optimal for $C' = C \setminus \{ x, y \} + \{ z \}$, then $T$ is optimal for $C$.

Once you have this lemma, you can prove the correctness of Huffman algorithm by mathematical induction on the cardinality of the alphabet $|C|$.

Base Case: The base case of $|C| = 2$ is trivial.
Inductive Hypothesis: Suppose Huffman algorithm is correct for any $|C| < n$.
Inductive Step: Consider the case of $|C| = n$. According to Huffman algorithm, you reduce the problem to constructing $T'$ on $C'$ where $|C'| = n -1$. By inductive hypothesis, $T'$ is optimal for $C'$. By the lemma above, $T$ is then optimal for $C$.


Time complexity version of the Church-Turing Thesis There's a lot of debate about what exactly the Church-Turing thesis is, but roughly it's the argument that "undecidable" should be considered equivalent to "undecidable by a universal turing machine."

I'm wondering if there's an analogous statement for time complexity, i.e. an argument that if some language is decided in $\Theta\left(f(n)\right)$ on a universal turing machine, then we should say its time complexity is $\Theta\left(f(n)\right)$.

This isn't equivalent to the CT thesis - e.g. quantum computers decide precisely those languages which are decidable in a non-quantum TM, but they may run that decision procedure more quickly.

Short answer

The thesis that all reasonable models of computation are polynomially-equivalent — that is, in the amount of work that they perform; whether sequentially or in parallel, albeit different by some polynomial scaling factor — is generally known as the Strong Church-Turing thesis or the Extended Church-Turing Thesis.

Details

The idea that all reasonable models of computation are equivalent up to polynomial factors is most important to two groups of researchers:

Those working in quantum computation (who most often believe that it is false, or at least that if it were true that it would have very important implications for physics), and
Those who are specifically skeptical towards the feasibility of quantum computers (who believe that the thesis is true, typically because quantum computers are the only thing which has come close to a 'reasonable' model of computation, and because the feel that quantum computers would somehow requires access to an unreasonable amount of information to carry out computations).

I started doing a bit of a literature search starting from Sid's link to the Computational Complexity blog entry above. That blog entry specifically concerned the Strong Church Turing Thesis, and asked whether anyone actually cared about such an "extended" version of the Church-Turing thesis before quantum computing came along.

It turns out that people have been trying to formulate this notion for a while however. It would seem that at the very least, the Strong Church-Turing Thesis arose naturally from concerns about what "reasonable computational models" could or could not achieve, in the context of sequential versus parallelized computing. There is both a "sequential" and "parallelized" computational thesis, which concern how different either sequential or parallelized models of computing can be with respect to computational power. Here are some quotations showing some of the history of the sequential thesis, which would be the one which quantum computing would be most naturally construed to violate.

  The belief that all reasonable sequential computers which will ever be dreamed of have polynomially related execution times is called the sequential computation thesis.

— Goldschlager, Lister. Computer science: a modern introduction. Prentice/Hall International, 1982 (p. 96).

  [The] sequential computation thesis [10] states that time on all "reasonable" sequential machine models is related by a polynomial.

— Parberry, Parallel speedup of sequential machines: a defense of parallel computation thesis. ACM SIGACT News 18 (pp. 54-67), 1986.

  "Reasonable" machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.

— van Emde Boas, Machine Models and Simulations. Handbook of Theoretical Computer Science A, Elsevier, 1990.


Universal Turing machine and virtualization technology I was wondering if virtualization technologies (VmWare, virtual box) are possible thanks to the theoretical existence, translated into practice, of the concept of universal turing machine or if the two are simply a coincidence. As far as I'm concerned they seem to me to be closely linked but I could be wrong.

Yes and no. Essentially because of the existence of universal Turing machines, you could write a VMWare-like system that used software to simulate the CPU. In reality, though, that would be unbearably slow, so it's not how these products actually work. Instead, they run the code directly on the CPU, in a carefully controlled and hardware-supported environment.


When the heapsort worst case occurs? The best-, average-, and worst case time complexity of Heapsort for $n$ distinct keys are all $\Theta(n \lg n)$.

  What are the worst-case inputs for heapsort?

Please check the paper@arXiv2015: A Complete Worst-Case Analysis of Heapsort by M. A. Suchenek.

This paper gives a rather involved lower bound; see Abstract and Theorem 12.2 on page 94.

To the specific question,

  Example of a 500-node worst-case array for Heapsort, created by my
  Java program, is included in Appendix A.3 page 110.


How to choose a word to apply the Pumping Lemma? I have some questions about the PUMPING LEMMA.
First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes.
And sorry about my English :)

Now my questions.

What is the easiest way to find a word, to start the Pumping Lemma? Are there some tricks I have to know?
For example I wanted to prove the following language is non-regular:
$$A=\{a^nb^mc^k\mid n,m,k \in N \wedge n\ mod\ 2=0=m\ mod\ 2\ \wedge m<k\}$$

My idea is to choose the word $w=c^n$. But it seems like a bad idea, because if I choose the decomposition $w=xyz$ with $y\not= \lambda$ than I can not pump it up, so that it isn't in A anymore.
With the decomposition we get $x=c^i$,$y=c^j$ and ${c}^{n-i-j}$.
Now I have to choose an $k$ to pump it up, but there is no $k$, were $w$ is not in $A$ anymore, or am I wrong?

For example let $k$ be $0$.
Then we get $xy^0z = {c}^{n-j}. But $ m < k $ \Longleftrightarrow 0<n-j$ for $ j > 0 $ is not wrong, so its not working.

My goal is to find a smart word, so that I do not need a case distinction.

I hope my problem is understandable. If not just ask.

You are on the right track. You just need to continue observing and trying. The trials and errors you have done might have been done by many experienced users more or less in different ways.

As you have found $w=c^n$ does not work. That word is too simple to be pumped outside of $A$, whether we will pump it down or pump it up.

Let us continue your preference/acumen to ignore the $a^n$ part. Let us choose word $b^mc^k$, where $m<k$. If we can pump substring of $b^m$ enough time, the number of $b$'s in $w$ will become larger than $k$ eventually. To ensure what will be pumped is a substring of $b^m$, we can let $m\ge p$, where $p$ is the pumping length.

So let us try $b^{p}c^{p+1}$. I will let you check that this word, if pumped up, will be no longer in $A$.

However, the number of $b$'s in $w\in A$ must be even. If $p$ is odd, $b^pc^{p+1}$ is not in $A$ in the first place. Well, in that case, we can choose $b^{p+1}c^{p+2}$.

In general, how to choose the right word so that it could pump down or up out of the language might feel like a bit of black magic without much pattern initially. However, there is actually not much  choices involved. You may learn from this answer and this answer.

Exercise. Prove the following language is not regular.
$B=\{a^nb^mc^k\mid n,m,k \in N \wedge n\operatorname{mod}2=1=m\operatorname{mod 2}\ \wedge m<k\}$


How many Turing Machines are there that run in time $t$ or in space $s$ on inputs of length $k$? I think half the battle in answering this question lies in formulating it precisely! A search engine doesn't turn up much, so I was wondering if this is a well-known or well-studied question.

My thoughts: I think the most straightforward way to formulate this question is as in my title: Given constants $t,s,k \in \mathbb{N}$, how many TMs are there that run in $t$ steps or fewer on all inputs of size $k$, and how many TMs are there that use $s$ tape squares or fewer on all inputs of size $k$? This seems like the most direct and simple way to ask the question, but we might want to restate it in a different way -- for example, given a function $p(k)$, how many TMs are there that run in time $p(k)$ on inputs of size $k$ for all $k$ (or how "dense" are these TMs)? This seems harder to me.

We should probably fix a tape alphabet (or a Godel numbering??). We could consider two TMs with different but isomorphic state diagrams to be the same or different, either way.

The immediate problem is that there are an infinite number: Take any TM that satisfies the criteria and add "dead states". I can think of two ways to deal with this. The first (which I don't like) is to add an additional parameter: how many TMs whose description has length $\leq L$ satisfy the criteria? The second (which I prefer) is to consider two TMs equivalent on inputs of size $\leq k$ if, for all such inputs, the TMs have exactly the same behavior (enter the same states and write/move on the tape identically). Then we would restrict to the minimal TM in each equivalence class, or just ask how many equivalence classes satisfy the criteria.

Edit: As pointed out by Vor in the comments, the problem with the second approach is that it's basically the same as a circuit at that point. So how about the first one? Or is there a nicer way to formalize this question?

Any references/literature, thoughts, or answers would be very interesting and appreciated!

Given $k$, consider the set of $\mathcal{M}_k = \{ M_i \mid i \in \mathbb{N} \}$ with $M_i$ defined by

if |x| = k
  accept
else
  simulate TM i on x

The set $\mathcal{M}_k$ is a subset of the Turing machines you want to count for all $s,t$. Since it is infinite, the set you want to count is infinite, too.

As far as I can tell, this result is stable against all restrictions you impose as long as you don't restrict the set of all feasible Turing machines to be finite.


Why does a processor have 32 registers? I've always wondered why processors stopped at 32 registers. It's by far the fastest piece of the machine, why not just make bigger processors with more registers? Wouldn't that mean less going to the RAM?

First, not all processor architectures stopped at 32 registers. Almost all the RISC architectures that have 32 registers exposed in the instruction set actually have 32 integer registers and 32 more floating point registers (so 64).  (Floating point "add" uses different registers than integer "add".)  The SPARC architecture has register windows.  On the SPARC you can only access 32 integer registers at a time, but the registers act like a stack and you can push and pop new registers 16 at a time.  The Itanium architecture from HP/Intel had 128 integer and 128 floating point registers exposed in the instruction set.  Modern GPUs from NVidia, AMD, Intel, ARM and Imagination Technologies, all expose massive numbers of registers in their register files.  (I know this to be true of the NVidia and Intel architectures, I am not very familiar with the AMD, ARM and Imagination instruction sets, but I think the register files are large there too.)

Second, most modern microprocessors implement register renaming to eliminate unnecessary serialization caused by needing to reuse resources, so the underlying physical register files can be larger (96, 128 or 192 registers on some machines.)  This (and dynamic scheduling) eliminates some of the need for the compiler to generate so many unique register names, while still providing a larger register file to the scheduler.

There are two reasons why it might be difficult to further increase the number of registers exposed in the instruction set.  First, you need to be able to specify the register identifiers in each instruction.  32 registers require a 5 bit register specifier, so 3-address instructions (common on RISC architectures) spend 15 of the 32 instruction bits just to specify the registers.  If you increased that to 6 or 7 bits, then you would have less space to specify opcodes and constants.  GPUs and Itanium have much larger instructions.  Larger instructions come at a cost: you need to use more instruction memory, so your instruction cache behavior is less ideal.

The second reason is access time.  The larger you make a memory the slower it is to access data from it.  (Just in terms of basic physics: the data is stored in 2-dimensional space, so if you are storing $n$ bits, the average distance to a specific bit is $O(\sqrt{n})$.)  A register file is just a small multi-ported memory, and one of the constraints on making it larger is that eventually you would need to start clocking your machine slower to accommodate the larger register file.  Usually in terms of total performance this is a lose.


What's the decoding time complexity of LT codes? LT codes are practical fountain codes that are near-optimal erasure correcting codes.

Simply stated, for encoding a $n$-block message, each packet first chooses a degree $d\in\{1,\ldots,n\}$ according to a specific distribution, and then $d$ random blocks are xor-ed to create the packet's message.

The analysis shows that $O(n)$ packets that make to the receiver are enough for decoding, by allowing finding degree-one packets and xoring its content from all other packets that contain the same block (decreasing their degree by one).

What I haven't found in Luby's paper, or anywhere else, is the runtime complexity of the decoding. That is, what's the overall time spend on computing the original message.

A simple argument shows that $O(n^2)$ time is enough. Can we do better?

The approach you describe can be implemented to run in linear time.

Build a bipartite graph where left-vertices are blocks and right-vertices are packets, and with an edge from block $b$ to packet $p$ if $b$ is one of the blocks xor-ed to create $p$'s message.  Store the bipartite graph in adjacency list format.  Also keep track of the degree of each packet, so given a packet $p$ you can compute its degree in $O(1)$ time.

Then it's easy to implement the algorithm you describe in $O(n)$ time, using a worklist algorithm.  The worklist is a list of all packets of degree one.  In each iteration, you remove a degree-one packet $p$ from the worklist, then process it as follows.  Find the corresponding block $b$, then find all other packets $p'$ containing the block.  Xor $b$ into $p'$, and delete the edge $(b,p')$ (and update the degree of $p'$).  This can be done in $O(1)$ time.  If the new degree of $p'$ is 1, add $p'$ to the worklist.  Repeat until the worklist is empty.

The running time is $O(1)$ per edge in the bipartite graph, i.e., $O(m)$ time where $m$ counts the number of edges in the graph (the sum of degrees of all of the packets).


LZW with dictionary clearing How does LZW decompress data with dictionary clearing/flushing? I understand that a space is reserved in the dictionary that represents a clear code (usually 256), but how is this code actually used when compressing and decompressing data? My thoughts for compression are that it checks the table size, and if the table size has reached the maximum size it appends the flush character to the output before resetting the dictionary. I'm not sure what it does for decompression though.

When the compressor clears the dictionary, it emits the clear code.  This enables the decompressor to stay in sync: when it sees the clear code, the decompressor clears its own dictionary.  In this way, the decompressor can reconstruct/infer the state of the encoder's dictionary at each step.
Wikipedia says:

Smart encoders can monitor the compression efficiency and clear the table whenever the existing table no longer matches the input well.


Is path induction constructive? I'm reading through the HoTT book and I have a hard time with path induction.

When I look at the type in the section 1.12.1:
$$\text{ind}_{=_A}:\prod_{C:\prod\limits_{x,y:A}(x=_Ay)\to \mathcal{U}}
\left(
\left(\prod_{x:A}C(x,x,\text{refl}_x)\right) \to
\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p)
\right),$$
I have no issue understanding what that means (I just have written the type from memory, to check that).

What I have issue with is the next very statement:
$$\text{with the equality}\quad \text{ind}_{=_A}(C,c,x,x,\text{refl}_x):\equiv c(x)$$
my first impression was that this last expression does not define the resulting function $$f:\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p),$$
but just states its property.

That is in contrast to previous examples of the induction principles $\text{ind}_{A\times B}$,$\text{ind}_{A+B}$ or $\text{ind}_\mathbb{N}$ -- there are defining equations for those elements -- we actually know how to construct the resulting function, given the premises. Which is in agreement with the "constructiveness" of type theory adverted throughout the chapter.

Going back to $\text{ind}_{=_A}$, I was suspicious about the fact that (looks like) it is not defined. Stating that the element $f$ just exists seemed out of tune with the rest of the chapter. And indeed, the   section 1.12.1 seems to stress that my impression is wrong and we in fact have defined

  ... the function  $f:\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p),$ defined by
  path induction from $c:\prod_{x:A}C(x,x,\text{refl}_x)$, which moreover
  satisfies $f(x,x,\text{refl}_x):\equiv c(x)$ ...

That leaves me utterly confused, but I have a feeling that this point is very important for all the further developments. So which of the two readings for $\text{ind}_{=_A}$ should I go with? Or, probably, I'm missing some important subtlety and the answer is "neither"?

It is an illusion that the computation rules "define" or "construct" the objects they speak about. You correctly observed that the equation for $\mathrm{ind}_{=_A}$ does not "define" it, but failed to observe that the same is true in other cases as well. Let us consider the induction principle for the unit type $1$, which seems particularly obviously "determined". According to Section 1.5 of the HoTT book we have
$$\mathrm{ind}_1 : \prod_{C : 1 \to \mathtt{Type}} C(\star) \to \prod_{x : 1} P(x)$$
with the equation
$$\mathrm{ind}_1 (C, c, \star) = c.$$
Does this "define" or "construct" $\mathrm{ind}_1$ in the sense that it leaves no doubt as to what $\mathrm{ind}_1$ "does"? For instance, set $C(x) = \mathbb{N}$ and $a = 42$, and consider what we could say about
$$\mathrm{ind}_1(C, 42, e)$$
for a given expression $e$ of type $1$. Your first thought might be that we can reduce this to $42$ because "$\star$ is the only element of $1$". But to be quite precise, the equation for $\mathrm{ind}_1$ is applicable only if we show $e \equiv \star$, which is impossible when $e$ is a variable, for example. We can try to wiggle out of this and say that we are only interested in computation with closed terms, so $e$ should be closed.

Is it not the case that every closed term $e$ of type $1$ is judgmentally equal to $\star$? That depends on nasty details and complicated proofs of normalization, actually. In the case of HoTT the answer is "no" because $e$ could contain instances of the Univalence Axiom, and it is not clear what do to about that (this is the open problem in HoTT).

We can circumvent the trouble with univalance by considering a version of type theory which does have good properties so that every closed term of type $1$ is judgmentally equal to $\star$. In that case it is fair to say that we do know how to compute with $\mathrm{ind}_1$, but:

The same will hold for the identity type, because every closed term of an identity type will be judgmentally equal to some $\mathrm{refl}(a)$, and so then the equation for $\mathrm{ind}_{=_A}$ will tell us how to compute.
Just because we know how to compute with closed terms of a type, that does not mean we have actually defined anything because there is more to a type than its closed terms, as I tried to explain once.

For example, Martin-Löf type theory (without the identity types) can be interpreted domain-theoretically in such a way that $1$ contains two elements $\bot$ and $\top$, where $\top$ corresponds to $\star$ and $\bot$ to non-termination. Alas, since there is no way to write down a non-terminating expression in type theory, $\bot$ cannot be named. Consequently, the equation for $\mathrm{ind}_1$ does not tell us how to compute on $\bot$ (the two obvious choices being "eagerly" and "lazily").

In software engineering terms, I would say we have a confusion between specification and implementation. The HoTT axioms for the identity types are a specification. The equation $\mathrm{ind}_{=_C}(C,c,x,x,\mathrm{refl}(x)) \equiv c(x)$ is not telling us how to compute with, or how to construct $\mathrm{ind}_{=_C}$, but rather that however $\mathrm{ind}_{=_C}$ is "implemented", we require that it satisfy the equation. It is a separate question whether such $\mathrm{ind}_{=_C}$ can be obtained in a constructive fashion.

Lastly, I am a bit weary of how you use the word "constructive". It looks as if you think that "constructive" is the same as "defined". Under that interpretation the Halting oracle is constructive, because its behavior is defined by the requirement we impose on it (namely that it output 1 or 0 according to whether the given machine halts). It is prefectly possible to describe objects which only exist in a non-constructive setting. Conversely, it is perfectly possible to speak constructively about properties and other things that cannot actually be computed. Here is one: the relation $H \subseteq \mathbb{N} \times \{0,1\}$ defined by
$$H(n,d) \iff (d = 1 \Rightarrow \text{$n$-th machine halts}) \land (d = 0 \Rightarrow \text{$n$-th machine diverges})$$
is constructive, i.e., there is nothing wrong with this definition from a constructive point of view. It just so happens that constructively one cannot show that $H$ is a total relation, and its characteristic map $\chi_H : \mathbb{N} \times \{0,1\} \to \mathsf{Prop}$  does not factor through $\mathtt{bool}$, so we cannot "compute" its values.

Addendum: The title of your question is "Is path induction constructive?" After having cleared up the difference between "constructive" and "defined", we can answer the question. Yes, path induction is known to be constructive in certain cases:

If we restrict to type theory without Univalence so that we can show strong normalization, then path induction and everything else is constructive because there are algorithms that perform the normalization procedure.
There are realizability models of type theory, which explain how every closed term in type theory corresponds to a Turing machine. However, these models satisfy Streicher's Axiom K, which rules out Univalence.
There is a translation of type theory (again without Univalence) into constructive set theory CZF. Once again, this validates Streicher's axiom K.
There is a groupoid model inside realizability models which allows us to interpret type theory without Streicher's K. This is preliminary work by Steve Awodey and myself.

We really need to sort out the constructive status of Univalence.


Why do derivation tree not make sense for context-sensitive grammars? I don't understand the line in the paper "Mappings and Grammars on Trees" by William C. Rounds, the passage:

  Transformational theory, as developed by Chomsky
  [7] and many others, deals with the notion of phrase-structure grammar, and with certain mappings defined on derivation trees associated with the grammar. Derivation trees do not make much sense for context-sensitive grammars, because they depend on the order of carrying out a derivation. We will therefore assume that mappings are to be defined on context-free derivation trees.

Thank you.

For context-free grammars, the order in which you execute rules does not matter. Formally, let

$\qquad \gamma = w_1 A_1 w_2 \dots w_{n-1} A_{n-1} w_n$

with $A_i \in N$ and $w_i \in T^*$ for all $i$. Then, any order of applying rules $A_i \to \alpha_i$ yields the same sentential form. Thus, it makes sense to identify $\gamma$ with a level in a syntax tree -- the children of all the nodes (if any) are independent of each other.

For context-sensitive grammars, this is not true. Consider this grammar¹:

$\qquad\begin{align*} S\ \ &\to AS \mid A \\ AS &\to a \\ SA &\to b \\ A\ \ \ &\to c \end{align*}$

Observe how the set of applicable rules changes as soon as you start applying them! Therefore, while you can still imagine a tree structure here, the children are no longer independent.

Also, you'd have to connect two nodes from higher levels each node -- and arbitrarily many for general CSGs. Since any symbol may influence the picking of many rules, this will give you a DAG, but no tree.

As has been aptly noted by commentes chi and fade2black, this grammar is not context-sensitive in the strict sense of the definition. I find it clearer to illustrate the issue; but still, this is a clearly context-sensitive variant:

$\qquad\begin{align*}
  S\ \ &\to AS \mid AB \\
  AS &\to CC \\
  SA &\to DD \\
  A\ \ \ &\to c \\
  B \ \ \ &\to d \\
  C \ \ \ &\to a \\
  D \ \ \ &\to b
\end{align*}$


Is 0-1 integer linear programming with only equality constraints NP-Hard? We know that 0-1 integer linear programming is NP-Hard. What about 0-1 integer linear programming with only equality constraints? If so, how to prove it

$$\min c^T x \text{ s.t. } Ax = b \quad x_i \in \{0,1\}\quad (i=1,2,...,n)$$

Consider the Maximum Independent Set problem ($\mathcal{NP}$-hard): given a graph $G=(V,E)$, find the maximum independent set in $G$, i.e., the subset of vertices $I \subseteq V$ such that every two vertices in $I$ are not adjacent $\forall v_1,v_2 \in I, (v_1,v_2) \notin E$.

This problem has a well known Integer programming formulation:
let $x_i$ be a binary variable for every $i \in V$ and equal one if $i \in I$.
\begin{align}
\max & \sum\limits_{i=1}^n x_i \\
\text{subject to} & \\
& x_i + x_j \leq 1 \text{ for all } (i,j) \in E \\
& x_i \in \{0,1\} \text{ for all } i \in V
\end{align}

If $|V| = n$, this problem has $n$ variables and $O(n^2)$ constraints.

To transform it to equality form (a.k.a. standard form) one might introduce slack variables for every constraint. Generally, if you have $Ax <= b$ you can write $Ax + x_s = b$ where $x_s \geq 0$ and $x_s$ are called slack variables.

It appears that for Independent Set slack variables are actually binary!
Thus, you have the formulation
\begin{align}
\max & \sum\limits_{i=1}^n x_i \\
\text{subject to} & \\
& x_i + x_j +y_{ij} = 1 \text{ for all } (i,j) \in E \\
& x_i \in \{0,1\} \text{ for all } i \in V \\
& y_{ij} \in \{0,1\} \text{ for all } i,j \in V
\end{align}

This formulation exactly satisfies yours

  0-1 integer linear programming with only equality constraints (ILPEQ)

Now, you have a basic reduction argument. Suppose, you can solve ILPEQ fast, that means you can solve independent set fast, but it is known to be $\mathcal{NP}$-hard, so ILPEQ is also $\mathcal{NP}$-hard. The formal argument as well as checking that this is in fact a polynomial reduction I leave to the reader.


Two way communication using asymmetric encryption According to image 1, for two way communication, each person needs to generate a pair of keys. However, according to image 2, only one pair of keys is required for two way communication. Thanks to anyone who can settle my confusion.

Source 1

  If a two-way communication is required between all five workers, then they all need to generate their own matching public and private keys. Once this is done, all users then need to swap public keys so that they can send encrypted documents, files or messages between each other. Each worker will then use their own private key to decrypt information being sent to them.

Source 2

  the other key is known as the private key. Data encrypted with the public key can only be decrypted with the private key, and data encrypted with the private key can only be decrypted with the public key. Public key encryption is also known as asymmetric encryption. It is widely used, especially for TLS/SSL, which makes HTTPS possible.

The first source is being imprecise when they say "need".  What they mean is that this is one way to accomplish it.

The second source doesn't say what you claim it says.

I suggest studying key exchange protocols and learning how SSL works.


Definition of extensional and propositional equality in Martin-Lof extensional type theory Martin Hofmann states in Extensional Concepts in Intensional Type Theory (§1.1 p.[4-5]) that:

  A similar situation occurs in extensional Martin-Lof type theory where propositional and definitional equality are forcefully identified by the equality reflection rule $\frac{\Gamma \vdash P:Id_\sigma(M,N)}{\Gamma \vdash M=N: \sigma}\text{(Id-DefEq)}$

Does the above mean that we purposefully drop the proof that M and N are equal and just consider them to be equal definitionally (like a presumption)?

Then it goes on and says:

  This rule makes definitional equality extensional and undecidable.

How does it become extensional and what does it mean by becoming extensional in the first place?

And then it states:

  Moreover, type checking becomes undecidable because $Refl(M):Id_\sigma (M,N)$ holds iff $M$ and $N$ are definitionally equal.

Why would $Refl(M)$ hold only if $M$ and $N$ are definitionally equal? And why would it make it undecidable?

what does it mean by becoming extensional in the first place?

The axiom of extensionality relates to what it means for two functions to be equal. Specifically, extensionality says:

$f = g \iff \forall x \ldotp f(x) = g(x)$

That is, functions are equal if they map equal inputs to equal outputs. By this definition, quicksort and mergesort are equal, even if they don't have the same implementations, because they behave the same as functions.

  How does it become extensional

What's missing is the rule of definitional equality for functions. It usually looks like this:

$\frac{\Gamma, (x : U) \vdash (f x) = (g x):V}{\Gamma \vdash f = g: (x : U) \to V}\text{(Fun-DefEq)}$

That is, two functions are definitionally equal when they produce equal results when applied to an abstract variable. This is similar in spirit to the way we typecheck polymorphic functions: you make sure it holds for all values by making sure it holds for an abstract value.

We get extensionality when we combine the two: if two functions always produce the same result, we should be able to find some equality proof $P$ such that $\Gamma,(x: U) \vdash P:Id_V(f x, g x)$ i.e. the proof that the two functions always produce the same result. But, if we combine this with the rule $\text{(Id-DefEq)}$, then any time two functions are extensionally equal (i.e. we can find the proof term $P$, then they are also definitionally equal.

This is in stark contrast to an intensional system, where two functions are equal if and only if their bodies are syntactically identical. So mergesort and quicksort are intensionally different, but extensionally the same.

The $\text{(Id-DefEq)}$ means that extensional equality is baked into the type system: if you have a type constructor $T : ((x : U) \to V) \to \mathsf{Set}$, then you can use a value of type $T\ f$ in a context expecting $T\ g$ if $f$ and $g$ map equal inputs to equal outputs. Again this is not true in an intensional system, where $f$ and $g$ might be incompatible if they're syntactically different.

  Does the above mean that we purposefully drop the proof that M and N are equal and just consider them to be equal definitionally (like a presumption)?

It's even a bit stronger than that. It's saying that $M$ and $N$ are definitionally equal any time there exists some proof that they are propositionally equal. So on the one hand, if you have a propositional proof that two values are equal, you can forget that proof and say that they are definitionally equal. But on the other hand, if you are trying to prove that two values are definitionally equal (as a dependent type checking algorithm would), then you cannot say that they are not equal unless you are certain that no proof $P$ exists. This is why it is undecidable.


Regular language properties For regular languages $R, S$ and $T$, which of the following are true?

$R \cup S = S \cup R$
$(R \cup S) \cdot T = RT \cup ST  $
$R^* \cdot S^* = (R \cup S)^*$

True
True
False

To find the proofs, proceed as follows:

Show that any string $x \in R \cup S$ belongs to $S \cup R$, and vice versa.
Ditto 1.
Find a string $x$ that is in $(R \cup S)^*$ but not the LHS. Hint: what about $rsr$ where $r \in R, s \in S$?


Title matching against human input I am attempting to match human input of titles to a list of titles, and also show likely candidates when a human enters a title not known.  Ideally I'd also have some way to suggest the human input of a truly novel title matches no known title as well.
As an example, I have a list of titles like this:
The Conspirators
The Count of Monte Cristo
The Three Musketeers
The Fencing Master

Only, my real list of titles is on the order of tens of millions long, and includes titles in different languages, including non Latin based languages.
And, as a human enters titles like these, I am attempt to find the proper name, here are examples of what humans might enter for The Three Musketeers:
The Three Musketeers
The 3 Musketeers
Three Musketeers, The
The.Three.Musketeers
the-three-musketeers
thethreemusketeers
The Three Musketeers-1844
Three Musketeers
THE THREE MUSKETEERS

For lack of a better term, at present, I'm attempting to "normalize" the titles.  For instance, that means I:

Convert input to a known case
Remove why whitespace (or characters acting like whitespace, like the - and . above)
Remove extraneous information (like 1844 above)
Fix up common issues, like replace and with &
Other domain specific fix-ups

This is done once on the known good titles, and whenever a user enters a title, a simple database lookup is done.  In the case of multiple titles matching, domain specific guesses are made (for instance, a book with more reviews wins over other options).
This works, but it requires a lot of custom logic in the string normalization, and what's worse, it requires knowledge of multiple languages.  And if users suddenly start following a new trend, like as a made up example, use = instead of spaces, then there needs to be a feedback loop where someone reviews common "misses" in the search and updates the string normalization logic.
Some other options I've briefly looked into:

Phonetic matching algorithms, like Soundex.  These sometimes work, but some of the human input doesn't sound like the target word, and these systems tend to require I know the target language, which I don't always know.
Machine Learning.  I'm at a loss here, most of the systems I've read about require cleaning of human input, which if I can do, I can match without any ML systems.
n-gram based fuzzy matching.  Much like the phonetic matching systems, this requires knowing the language, and cleaning up the text to some degree beforehand.  Also, most of the systems seem to require a lot of compute power to perform the lookup, which is a concern.

Are there better techniques to apply to this problem to find the real title from the human input?

One plausible approach is to use edit distance to measure the similarity of two titles.  You might want to adjust it to reduce the penalty for capitalization (e.g., changing x to X might cost 0, or some very small amount).
Then, given a human-entered title, you need a way to find the closest match in the database.  There are various data structures and techniques for this.  See, e.g., shingling, BK trees, metric trees, Efficient map data structure supporting approximate lookup, Efficient data structures for building a fast spell checker, https://cstheory.stackexchange.com/q/4165/5038, http://norvig.com/spell-correct.html.
Another heuristic might be to extract each word from the human-entered title, canonicalize it (e.g., spelling correction, lower-case it, etc.), then look it up to find the first 1000 titles in the database that contain this word.  Take the union of those titles from the database, compare each to the human-entered title using edit distance, and keep the closest match.


Compact mapping from an involuted set Let $S$ be a set (say positive integers $\leq$ N) and $f$ an involution ($f$ is bijective, $f\cdot f=id$, e.g. xor with a constant). $g$ is a idempotent mapping choosing an arbitrary representative element in each $f$ mapped pairs. For example $g(x)=\min (x,f(x))$ $$g: S \rightarrow \tilde S \subseteq S$$

I want to build a compact lookup table from $g$'s codomain $\tilde S$ to any problem data, taking $|\tilde S| \leq |S|$ cells in memory. Ideally I wish to construct a bijective mapping $\tilde S \rightarrow \left[0, |\tilde S| \right[$.

Can it be done efficiently in general (without hash map or scanning) ? What properties of the involution $f$ could help with that ?

Edit: I formulated the problem in the more general/formalized, hoping for a generic solution. Following D.W.'s comment, I'll give a concrete application:

I work with DNA words of $k$ nucleotides bases called $k$-mers. Since there is four bases, $k$-mer are represented as elements of $S=[0,2^{2k}[$

However DNA can be read on both strands, with opposite orientations and complementary bases ($A \leftrightarrow T$, $G \leftrightarrow C$). Going from one strand to the other can be represented by this involution (reverse-complement, here for 5-mers): $$ f(x) = \text{reverse}_2(x) \oplus 0\text b1010101010 $$ where $\text{reverse}_2(abcdefghij)=ijghefcdab$ inverse the order of 2-bits blocks and $\oplus$ is the bitwise XOR.

Since many applications don't distinguish between a $k$-mers and its reverse-complement, a canonical $k$-mer is picked with $g(x)=\min (x,f(x))$. The cardinality of $g$'s co-domain is: $$
\left|\tilde{S}\right|=\begin{cases}
2^{2k-1} & \text{if }k\text{ is odd}\\
2^{k-1}\left(2^{k}+1\right) & \text{if }k\text{ is even}
\end{cases}
 $$

In practice saving less than one addressing bit is not worth a complex solution. But cache locality is a good thing to have. $g$ can be chosen differently if it help with that.

I can give two candidate solutions for your specific situation.

Approach #1: parity

This only works if $k$ is odd.  Notice that if $k$ is odd, the parity of $f(x)$ is the reverse of the parity of $x$.  In other words, the xor of the bits of $f(x)$ is the complement of the xor of the bits of $x$.

This suggests an encoding.  Define $g(x)$ to choose between $x$ and $f(x)$ by always  choosing the one with even parity.  In other words, $g(x)=x$ if the  the bits of $x$ xor to zero, otherwise $g(x)=f(x)$.  Now we have $y \in \{0,1\}^{2k}$ with even parity, and we want to map it to a $2k-1$ bit index/offset.  We can do that by simply truncating the last bit of $y$ (since we know $y$ has even parity, the  last bit of $y$ is uniquely determined by all the other bits).

This scheme is simple, easy to implement, efficient, and achieves perfect compression of your table.  Unfortunately this doesn't work if $k$ is even.  I don't know if there is a simple generalization of this idea to the case where $k$ is even.

Approach #2: multiple tables

This scheme works for arbitrary $k$.  Instead of having a single lookup table, we will have $k/2$ lookup tables $T_1,T_2,\dots,T_{k/2}$, each of which stores a different subset of the space of $k$-mers.  The mapping will have the property that $x$ and $f(x)$ map to the same table and same offset/index within the table.

Define $h(x)$ to be the smallest $i$ such that $f(x_i x_{k+1-i}) \ne x_i x_{k+1-i}$  (here by $x_i$ I mean the $i$th base in $x$, where $i \in \{1,2,\dots,k\}$; so $x_i$ is two bits).   Now we will store $x$ in the table $T_j$ where $j=h(x)$.  For instance, if $h(x)=1$, we'll store $x$ in $T_1$; if $h(x)=2$, we'll store $x$ in $T_2$; and so on.  Conveniently, we have $h(x)=h(f(x))$.  So, we'll define $g(x)$ to compute $j=h(x)$ and then choose between $x$ and $f(x)$ by choosing the value $y$ such that $y_j < f(y_j)$.  In other words, if $x_{h(x)}$ is lexicographically smaller than $f(x)_{h(x)}$, then $g(x)=x$, otherwise $g(x)=f(x)$.

How do we determine the index into the table?  Suppose $h(x)=1$.  Then there are 12 possibilities for $x_1,x_k$ such that $h(x)=1$ (the other 4 possibilities yield $h(x)>1$), and our definition of $g$ picks out 6 of them as canonical.  So, in total there are $6 \times 2^{2k-4}$ possible values of $x$.  Thus $x$ can be easily converted into an index into $T_1$ by mapping $x_1,x_k$ to $\{0,1,2,3,4,5\}$, say $i_1$, and mapping $x_2,\dots,x_{k-1}$ to an integer in the range $0..2^{2k-4}-1$, say $i_2$, and then using $2^{2k-4} i_1 + i_2$ as our index.  You can generalize to the cases $h(x)=2$, $h(x)=3$, etc.  For example, suppose $h(x)=2$.  Then there are 4 possibilities for $x_1,x_k$; 12 possibilities for $x_2,x_{k-1}$, but $g$ picks out 6 of them as canonical; and $2^{2k-8}$ possibilities for $x_3,\dots,x_{k-2}$.  So you can map $x_1,x_k$ to an integer in the range $0..3$, map $x_2,x_{k-1}$ to an integer in the range $0..5$, and map $x_3,\dots,x_{k-2}$ to an integer in the range $0..2^{2k-8}-1$; then map those to an index in the range $0..4 \times 6 \times 2^{2k-8}-1$.  And so on for larger values of $h(x)$.

This strategy works for any value of $k$.  It achieves perfect compression.  It's not too difficult to implement and should be pretty fast.


Normalizing the mantissa in floating point representation How to represent $0.148 * 2^{14}$ in normalized floating point arithmetic with the format

1 - Sign bit
7 - Exponent in Excess-64 form
8 - Mantissa

$(0.148)_{10} = (0.00100101\;111...)_2$

We shift it 3 bits to left to make it normalized $(1.00101\;111)_2 * 2^{11}$.

Exponent = $11+64 = (75)_{10} = (1001011)_2$ and Mantissa = $(01001\;111)_2$.

So floating point representation is $(0\;1001011\;00101111)_2 = (4B2F)_{16}$ Representation A

But if we store the denormalized mantissa into 8 bit register, then it won't have stored the last three $1$s and then the mantissa would have normalized from $(0.00100101)_2$ to $(1.00101\;000)_2$ by inserting 3 $0$s instead of $1$s.

The representation would have been $(0\;1001011\;00101000)_2 = (4B28)_{16}$ Representation B

So while normalizing, does the processor takes into account the denormalized mantissa bits beyond 8 bits too? Or just rounds it off? Which one is correct: A or B?

Does it store the mantissa in fixed point representation? How does it all work?

The correct binary representation of $0.145$ is $0.00100101000111...$

Normalized: $1.00101000111...$

The 8 bit mantissa is $00101000 = 0\mbox{x}28$


What is the lower bound for the following equation f(n) = 32n^2 + 17n + 1.

The lecture slide says that lower bound can be Omega(n^2) or Omega(n).

Some body please guide me why the lower bound can be Omega (n). i know the upper bound which is O(n^2).

Zulfi.

This is a quadratic function; therefore $f$ is big-Theta of $n^2$. Therefore, it is both Big-O and Big-Omega of $n^2$.

However, when a function $f$ is big-Omega of another function $g$, then $f$'s growth is of greater or equal order than $g$. However, since a quadratic grows strictly faster than a linear in the long run, $n^2$ is big-Omega of $n$. Think of as if big-Omega means "greater or equal than".

Also note when $f$ is big-Omega of $g$, then $g$ is big-O of $f$. Obviously, $n$ is big-O of both $n$ and $n^2$.


Prime factorization for compressing streams of random numbers We covered compression/encoding/decoding of data streams very briefly last lecture and I had an odd idea:
Let's say I have a stream of random 8-Bit numbers. Now the probabilty to encounter each number is 1/256.
If I prime factorize each number though I get a stream of prime numbers where I can calculate the probabilty of encountering a specific prime number by looking at how often it appears in all prime factorizations of all 8-Bit numbers.
Here's a couple of issues straight away:

0 and 1 are special cases, they dont have a prime factorization
per-se
the transform is not invertible, you'd have to use seperation
symbols

One way to "solve" both issues is to include 1 as a prime number and encode a number x as a prime factorization of number (x + 1) which allows for 0 and 1 and still fits into 8-Bits because the largest 8-Bit prime is 251. The 1 at the beginning of each prime factorization also serves as a separation symbol.
Could I use this way to somehow ("efficiently") encode a random stream of data?

No.  If it is a stream of random bytes, where each byte is independently and uniformly distributed, it cannot be compressed.  It doesn't matter what method you're using.  You're trying to do something analogous to inventing a perpetual motion device; we don't have to look at the detailed blueprint to know that it won't work.


Voronoi Cell and Voronoi Diagram Consider a set R of n red points and B of n blue points in the plane. Let x∈R and y∈B be the shortest edge xy. Let P = R ∪ B. Let Vor(P) be the Voronoi diagram of P. Let V(x) be the Voronoi cell of x and V(y) be the Voronoi cell of y. Prove or disprove that V(x) and V(y) share an edge in Vor(P ).

Here,as per my understanding, the shortest edge xy means that no other edge with one red endpoint and one blue endpoint is shorter. However, there may be edges with both red endpoints or both blue endpoints that are much shorter.

Let us assume that $P$ is in general position (no three points colinear, no four points cocircular) to make things easier.

As the Voronoi diagram is the dual of the Delaunay triangulation, this is the same as asking if the edge $xy$ is in the Delaunay triangulation of $P$.

You might know the following characterisation:

  An edge $(a,b)$ is in the Delaunay triangulation of $P$ if and only if there is a disk whose boundary passes through $a$ et $b$ containing no other point of $P$ on its boundary or in its interior.

So let us take a look at the edge $(x,y)$ and let us draw the circle/disk whose diagonal is $(x,y)$.

Notice that if any point other than $x$ or $y$ is in the disk, then it is closer to both $x$ and $y$ then they are to each-other. Thus there is no such point in $P$, as it can't be red nor blue by definition of $(x,y)$. So this disk contains no other point of $P$, which means $(x,y)$ is an edge of the Delaunay triangulation, thus it is an edge of the Voronoi Diagram.

(There was no real need to make a detour through Delaunay triangulations as by duality the characterisation works just as well for Voronoi diagrams but I have always seen that characterisation stated in terms of Delaunay triangulations)


Can a recurrence relation be translated to a composite function of itself? Perhaps this is a question for stackoverflow because its practical nature, but I am not aware of any general method to relate recurrence relations and recursive functions.

Having as an example this recurrence relation:

$\qquad \begin{align}a_0 &= a_1 = 1 \\ 2a_n &= 3a_{n-1}-2a_{n-2}\end{align}$

I would like to transform it into a recursive function $f$, able to be called to itself a number of times (composite), i.e.  $f \circ f \circ f \circ \dots \circ f$  ($n$ times), getting the same result as with the $a_n$ relation.

Any ideas about it?

static float f(int n,int m)
      {
         if((n==1)||(m==0)) return (1,1);
         return ((3*n - 2*m)/2,n);
      }

That way $\underbrace{f\circ f\circ \dots \circ f}_{\text{n times}} (1,0)=(a_n,a_{n-1})$.

Is that what you wanted?


3✕n chessboard with holes - maximum number of knights not attacking each other I'm trying to to create an algorithm (working in polynomial time) to solve the following problem:

What maximum number of knights that any two of them don't attack each other can be placed on a 3✕n chessboard with holes (knight can't be placed on a hole).
Width of the chessboard (n) and positions of holes are given. Besides the maximum number of knights that can be placed, the algorithm should return their positions.

I think some dynamic programming techniques can be used here but I have no idea how to get a solution for bigger chessboard having a solution for a smaller one. What I make out about the problem so far is:

the chessboard is a bipartite graph, where nodes are the normal (not holes) fields and edges are legal knight moves (white fields in the "left" set and the black ones in the "right" set)
the maximum degree of a node is 4 (knight can move to maximum 4 fields because the width of chessboard equals 3).

Use dynamic programming to calculate the maximum number of non-attacking knights on the left $3\times m$ part of your board with holes, given the placement of knights in the last two columns of this part of the board.


What does Godels Incompleteness theorem "true but unprovable" mean? I have asked this on the "computer science chat" ( vzn tried to explain me ) . I even watched a couple a videos to understand the theorem but still cannot convince myself. The following is the way the Godel's Incompleteness theorem is proved in Sipsers, where it is shown not all true statements are provable:

Notations, assumptions and preliminaries

The statements being considered are assumed to be in prenex form ( with boolean operations $\neg,\vee,\wedge$ ). The model is $(\mathbb{N},+,*)$ ie. variables can take values from the set of natural numbers and relations are addition and multiplication. The set of true statements in this model is denoted by $Th(\mathbb{N},+,*)$. $Th(\mathbb{N},+,*)$ is shown to be undecidable by reducing $A_{TM}$ to it. The reduction is given as, on input $\langle M,w\rangle$ construct statement $\psi=\exists c [ \phi_{\langle M,w \rangle}]$, where,
$\psi$ is true if and only if $c$ is an accepting computation history of string $w$ given as input to turing machine $M$.
Proof of a statement $\phi$ is ( loosely speaking ), a sequence of statements, $S_1, S_2, . .. ,S_i$, where $S_i = \phi$. Each $S_i$ follows from the preceding statements and certain basic axioms about numbers, using simple and precise rules of implication. The proof a statement is denoted by $\pi$.
The language $L=\{\langle \pi,\phi \rangle | \; \pi \text{ is a proof for } \phi \}$ is decidable ie. I can check the correctness of a proof for a statement. The Turing machine deciding $L$ is denoted by $D$.
All provable statements are true.
$P$ is a Turing machine that takes as input a statement $\phi$ tries to find a proof for it by giving $\langle \pi,\phi\rangle$ as input to $D$ for all proofs $\pi$ and accepting if $D$ accepts $\langle \pi,\phi\rangle$ for some $\pi$  ( if proof does not exist for $\phi$ $P$ does not halt ).

Proof

Construct the Turing machine $S$ such that
$S$ = "On input any input

Obtain own description $\langle S \rangle $.
Construct the statement $\psi=\neg \exists  c [ \phi_{\langle S,0\rangle} ]$ ( $0$ is some specific input string ).
Give statement $\psi$ as input to $P$.
If preceding step accepts, accept. If it rejects reject. "

The reasoning given by Sipsers is if $P$ is able to find a proof for $\psi$ it means $S$ will accept $0$, but then statement $\psi$ will be false and a false statement can't have a proof which is a contradiction. The only option is that $P$ does not find a proof for $\psi$, but then $S$ won't halt on $0$ and $\psi$ becomes true. Thus $\psi$ is a true but unprovable statement.
My doubt is, isn't the reasoning given above  that $\psi$ is true  a proof in itself ? I expected the proof would be of sort where I am able to construct a statement $s$ and prove that neither $s$ nor $\neg s$ is provable. Am I misunderstanding something ?
I can improve if my explanation of the problem is incorrect or vague.

EDIT

In the proof $\phi_{\langle S,0 \rangle}$ is a formula with a single free variable
$c$, such that the sentence $\exists c [\phi_{\langle S,0 \rangle}]$  is true if and only if there is an accepting computation history $c$ of input $0$ to Turing machine $S$.

Your difficulties are hinting toward Gödel's second incompleteness theorem. The proof system $\Pi$ can formalize most steps in the proof, other than its own consistency – the fact that $\Pi$ cannot prove a statement and its negation. Following exactly this train of though, Gödel showed that a sufficiently strong proof system cannot prove its own consistency.

For more information, I suggest looking up resources on Gödel's second incompleteness theorem.


Complexity class for concurrent algorithms We have the big O notations for sequential algorithms , but is there a notation to represent parallel algorithms in  a similar way?

Motivation:

A sequential algorithm may be O(n7) but its parallel implementation might make it O(1) so what is the motivation and tradeoff between spending time to design lower complexity algorithms then simply paralyzing it to achieve an even better performance? How this fact could be incorporated in the complexity theory notations?

Note:

Writing a parallel version is also a challenge but many times its a low hanging fruit which can be quickly solved without much creativity.

Parallel complexity uses the same Landau notation but a different machine model, usually the PRAM which allows polynomially many processors (in the input size). This gives rise to complexity classes like NC.

If you are into algorithms outside of massively-parallel settings, this is all quite useless: the existence of PRAM algorithms does not tell you anything about algorithms on "real" computers, i.e. such with finitely many processors.


What data structure would help find nearby coordinates quickly? I need to write a program that does the following:

Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places
Store them in a data structure once
Provide a "nearby" lookup function that can efficiently return the N closest objects for a given lat/long

Currently, I'm doing the following, which is suboptimal:

Store all objects in a hash, with array keys like [integer_latitude, integer_longitude]
At search time, find all objects in an arbitrary-sized circle around the target. Eg, if the search is at [0,0], I can get all objects within 1 degree by pulling [-1,0], then [0,0], then [1,0], then [0,-1], etc.
Order the found objects by actual distance to the target and take the top N

This is obviously inefficient, because often there are many more matches than N.

One improvement could be to examine locations in concentric squares outward from the center: all points 0 degrees from the center, all points 1 degree from the center, 2 degrees, etc, and stop after the first square when I have at least the number of objects needed. Then I could sort those by actual, fine-grained distance and take the top N.

Is there some well-established way of doing this search efficiently?

Yes, you could you could do better than a naive approach - you could use a k-d tree data structure.

Clever implementations, such as sklearn k-d tree do the nearest neighbour lookup in O(log(n)) which, unless you have a high dimensional and sparse dataset, will work significantly faster than a naive O(n) approach.


How do set partitions get mapped by restricted growth functions I am reading Skiena but do not have a formal background in Computer Science. On page 457 he discusses generating set partitions via restricted growth functions. Here's specifically what he says:

    Set partitions can be generated using techniques akin to integer partitions. Each set partition is encoded as a restricted growth function a1,...,an where a1 = 0 and ai <= 1 + max(a1, ..., ai). Each distinct digit identifies a subset, or block, of the partition, while the growth condition ensures that the blocks are sorted into canonical order based on the smallest element in each block. For example, the restricted growth function 0, 1, 1, 2, 0, 3, 1 defines the set partition {{1, 5}, {2, 3, 7}, {4}, {6}}.

Can someone walk me through how this mapping works? It seems to me that a2 should be less than 1 + max(0, a2). But how does that determine a2? How do I get from 0, 1, 1, 2, 0, 3, 1 to that set of partitions? I don't see it at all and would appreciate any explanation or hints.

We want to define a sequence of nonnegative integers $[a_1, a_2,\dotsc, a_n]$ with $a_1=0$ such that for each $1\le i\le n$ we'll have $a_i\le 1+\max\{a_1,\dotsc, a_{i-1}\}$ (Note the last index; the definition you gave would allow $a_i$ to be anything). This condition doesn't uniquely determine $a_i$, rather it gives several possibilities in general.

Let's generate some of these sequences.

The shortest is just $[0]$
To set $a_2$ we must have $a_2\le1+\max\{0\}=1$ so $a_2$ could be either $0$ or $1$, giving us the length-2 sequences $[0,0]$ and $[0,1]$
To set $a_3$ we either start from $[0,0]$ or $[0,1]$. From $[0,0]$ we see that $a_3$ could be either $0$ or $1$, giving us $[0,0,0]$ and $[0,0,1]$. From $[0,1]$ we could have $a_3=0,1,2$, giving us $[0,1,0], [0,1,1],[0,1,2]$.

Let's look at the length-3 sequences, $[0,0,0],[0,0,1],[0,1,0],[0,1,1],[0,1,2]$, and see how they give rise to partitions of the 3-element set $\{a,b,c\}$.

$[0,0,0]$ tells us that each element lives in set 0, giving us the partition $\{a,b,c\}$.
$[0,0,1]$ tells us that elements $a,b$ live in set 0 and $c$ lives in set 1, giving us the partition $\{a,b\},\{c\}$.
Similarly, $[0,1,0]$ gives rise to the partition $\{a,c\},\{b\}$.
Similarly, $[0,1,1]$ gives us $\{a\},\{b,c\}$.
Finally, $[0,1,2]$ gives us $\{a\},\{b\},\{c\}$.

By inspection, these five growth functions give rise to all the five possible partitions of the set $\{a,b,c\}$.


A genetic algorithm modified for a specific problem I have a problem whose solution can be written as a binary string with a given length $N$, where $N$ is a given parameter. Standard GA works well on this problem. From runs of small values $N$, I found that optimal solutions are binary strings that contain only 01 or 011. For example, the optimal solution for $N=16$ is 0101011010101101. So I think it would be a good idea to only search the solutions space where all solutions/chromosomes only contain 01 or 011. But clearly the standard GA cannot restrict the search in the subspace I desire. One mutation or one crossover will make the new solution go into the larger solution space.

My question is: is there a way to adapt the standard GA to restrict its solution space to one where the chromosomes contain only 01 or 011?

Start with a population, where every candidate is "good", where "good" means they contain at least one occurrence of substrings "01" and "011".

For the mutation operator, flip a coin. If the result is heads, choose a random substring of length 2 and change it to "01". If the result is tails, choose a random substring of length 3 and change it to "011".

For the crossover operator, let $A$ and $B$ be two parents. Find say the first occurrence of substring "01" or "011" from $A$, that occurs starting from index $i$. Check if in $B$ there is an occurrence of "01" or "011" before $i$. If so, choose $i$ as your crossover point. If not, find the next occurrence from $A$, and repeat. This process will terminate at some point, because you start out with individuals containing "good" substrings, and your operators maintain an invariant that all individuals are "good".

Please note that this only really answers your question of "how do I modify my GA", and does not address whether this works performance-wise. However, this should give you ideas as to what kind of operators you can experiment with.


Is DFA and Regular Expression equivalent? The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that?

If Regular Expression cannot do that, does it mean that DFA and Regular Expression are not equivalent (in at least some cases)?

According to Wikipedia:

Given a finite alphabet $\Sigma$, the following constants are defined as regular expressions:

(empty set) $\emptyset$ denoting the set $\emptyset$.

...

... a string that contains only an empty-set symbol is a regular expression, which represents the empty language.


Optional prefix code for the naturals The naturals $\mathbb{N}$ can be encoded with a binary unary code such as

$$
\begin{align}
    1&=0_b\\
    2&=10_b\\
    3&=110_b\\
    &...
\end{align}
$$
The length this the encoding grows linearly with the natural number it represents. For example the length of $110_b$ is 3 and it also represents the number 3.

I am looking for an upper bound on the optimality of the prefix free encoding. For example, can we design a prefix coding of $\mathbb{N}$ such that the length of the encoding grows according to ~$\sqrt{n}$, instead of $n$. Is there an upper bound on the optimality that we can prove?

I wrote a paper on this. The short answer is that there is no optimal encoding, nor even an optimal sequence of better and better encodings.

Kraft's inequality states that there is a prefix code with word lengths $k_0,k_1,\ldots$ if and only if
$$
\sum_{n=0}^\infty 2^{-k_i} \leq 1.
$$
This gives a positive answer to your question. Concretely, Elias gamma coding has code word length $O(\log n)$. The idea is simple: first you encode the bit-length of the integer using your method (using roughly $\log_2 n + 1$ bits), then you encode the number itself (using another roughly $\log_2 n$ bits), for a total of roughly $2\log_2n + 1$ bits.


Anatomy of a production rule Production is said to be of the form $u \to v$. I want to know if you distinguish $u$ from $v$ giving them some distinguishing names, like LHS/RHS or something alike.

$u$ can be called the 'head' (or left-hand side)

$v$ can be called the 'body' (or right-hand-side)

sources: source-1, source-2


Universal One-Way Functions The Berman-Hartmanis conjecture discusses one-way functions (functions with hard to compute inverse functions).

As a step to solving the conjecture, if one-way functions could be reduced to a canonical or universal one-way function from which all one-way functions could be derived, this would be a major plus...

In a similar way, Turing devised a universal machine and Cook NP-completeness.

The question is then, are there universal one-way functions (discussed in the literature)? Can they be defined through NP-completeness?

That is an interesting question since there is no proof that one way functions exist. There is a lecture about this from Cornell's Cryptography course by Rafael Pass  which can be found here

To summarize the lecture:

If one way functions exist then $P\neq NP$.
There exists a function $f_{UNIV}$ such that if there exists any one-way function, then $f_{UNIV}$ is a one-way function.  Thus $f_{UNIV}$ can be considered a universal one-way function.
$f_{UNIV}$ works by acting on all Turing machines after $n^2$ steps of execution.  It is defined as

$$f_{UNIV}=M_1^{(|x|^2)}(x)||M_2^{(|x|^2)}(x)||\dots M_{|x|}^{(|x|^2)}(x)$$

where $M_{i}^{(|x|^2)}(x)$ denotes the output of Turing machine $M_i$ on input $x$ right after $|x|^2$ steps of computation.
If a one way function $f$ exists it can be solved by a Turing machine $M$, which will be polynomial solvable by $f_{UNIV}$.

Caution: the construction of $f_{UNIV}$ is in no way practical.  This is about asymptotic complexity, not practical security.


Showing that carbon is not a complexity measure per Blum In Computational Complexity by Papadimitriou, there is an exercise about Blum's axioms where it asks to prove that several measures for the complexity of a Turing machine satisfy them.

7.4.12 Blum complexity. Time and space are only two examples of "complexity
measures" for computations. In general, suppose that we have a function $\Phi$, possibly
undefined on many arguments, mapping Turing machine-input pairs to the nonnegative integers. Suppose $\Phi$ is such that the following two axioms hold:

Axiom 1: $\Phi(M, x)$ is defined if and only if $M (x)$ is defined.

Axiom 2: It is decidable, given $M$, $x$, and $k$, whether $\Phi(M, x) = k$.

Then $\Phi$ is called a complexity measure. This elegant formulation of complexity was
developed in

M. Blum "A machine-independent theory of the complexity of recursive functions," J.ACM 14, 2, pp. 322–336, 1967.

(a) Show that space and time are complexity measures. (Notice that in this context
we do not maximize space and time over all strings of the same length, but leave the
dependence on individual strings.) Repeat for nondeterministic space and time.

(b) Show that ink (the number of times during a computation that a symbol has to
be overwritten by a different symbol) is a complexity measure.

(c) Show that reversals (the number of times during a computation that the cursor
must change direction of motion) is a complexity measure.

(d) Show that carbon (the number of times during a computation that a symbol has
to be overwritten with the same symbol) is not a complexity measure.

I am interested in the answer of (d) which I don't know how to approach.

Papadimitriou is being extremely sloppy here. Let us consider part (b) first. What does Papadimitriou mean by "ink"? Suppose that he really means what he wrote: the number of times during computation that a symbol is overwritten by a different symbol. Consider a Turing machine which repeatedly goes right one step, then left one step, in an infinite loop. Then ink is 0, but the machine never halts, and so Axiom 1 seems to be violated. We conclude therefore that ink (and carbon) should be undefined if the machine doesn't halt.
The more challenging bit is proving Axiom 2. Given $M$, $x$, and $k$, we need to decide whether (1) $M$ halts on $x$ and (2) during this halting computation, a symbol is overwritten with a new symbol exactly $k$ times. It might seem at first that this shouldn't be decidable, since we are in some sense trying to solve the halting problem. However, we are given the crucial advice $k$. Let us see how it helps us. We simulate $M$ on $x$ until it either halts (in which case we declare No) or we have reached ink $k$. In the latter case, it remains to check whether $M$ halts on $x$, given the additional promise that the tape doesn't change any more.
The additional promise allows us to continue the simulation until one of the following happens: (1) carbon increases, (2) computation halts, (3) a configuration repeats, (4) we have determined that the machine is off on a tangent on one of the infinite ends of the tape. I leave further details to you.
A similar trick doesn't work for part (d). Indeed, we can arrange for a Turing machine to never overwrite a tape symbol with itself. The idea is that for each original tape symbol we will have two new ones, treated in exactly the same way, that are alternated if needed to insure that carbon is zero. It follows that the halting problem can be reduced to the problem of deciding whether carbon is zero or not.


Applying Shannon Entropy to data storage I know Shannon Entropy is defined for messages. When it's said the size of a file stored in a HDD is 1 MB, are we talking about the Shannon Entropy? If so, how do we extend the definition to static information (not flowing like messages)? If not, how come they have the same unit, i.e. bits?

No.  That is telling you the size of the file, i.e., that's a statement about its length, not its entropy.

Of course, the length gives an upper bound on the entropy, but it is not itself a value for the entropy.  The actual entropy could be smaller.

No, compressing the file does not tell you its entropy.  The length after compression is, on average, a reasonable upper bound for the entropy -- but the true entropy could be much smaller.

Beware that it only makes sense to talk about the entropy of a random process or the entropy of a distribution (e.g., the entropy of a process used to generate a file), not the entropy of a single file.  As an analogy, consider this old joke:

It doesn't make sense to say that "the number nine is random"; that's a property of the process used to generate the number, not the number itself.  You could get a 9 by rolling a ten-sided die (which is a random process), or you could get a 9 by writing the largest single-digit decimal number (that's not a random process).  Similarly, it doesn't make sense to ask what is the entropy of the number nine; that is not well-defined.  We can talk about the entropy of the random process that was used to generate it, though.

See a good textbook to learn more about the subject of entropy.


Algorithm to convert undirected connected graph with no bridges to strongly connected directed graph I am not sure how to go about this exactly. My attempt is find the pick an arbitrary node and run DFS, ordering each node by order of discovery. After this, You can orient each of edges so it pointing from lower order to higher order. Now I know this will create a path from one node to another, but doesn't guarantee a path from the other back to the initial. Is there any way to modify my algorithm so that it it would strongly connected and not just connected.

Well the idea of dfs is quite good all you need to orient all edges away from the vertex that discovered them.

You will have a path from the root to each  vertex since the graph is connected and the dfs will visit all vertices.

Claim. From each vertex you can reach the root.

Proof. Let $\mathcal{C}$ be the strongly connected components of the resulting graph. Let $\mathcal{G}$ be the DAG resulting from contracting the vertices in each component in $\mathcal{C}$. Also, let $C_0 \in \mathcal{C}$ be the strongly connected component containing $r$. We have to prove that $C_0$ is the only component in $\mathcal{C}$ and hence, it contains all the vertices in the graph. Assuming otherwise, all components must be reachable from $C_0$ in $\mathcal{G}$, since all vertices are reachable from $r$ in $G$. choose $C$ to be a component in $\mathcal{C}$ that is the end of a longest path $P$ from $C_0$ in $\mathcal{G}$. Let $C'$ be the component previous to $C$ on that path. There is an edge from a vertex in $C'$ to a vertex in $C$. But this edge is not a bridge, hence, there must be an edge leaving $C$ and directed from $C$ to outside $C$ (since such an edge must have been discovered the first time we visited $C$). If this edge goes to a component $C''$ not on $P$, we could have extended $P$ to $C''$ resulting in a longer path wich is a contradiction. On the other hand, if it goes to a component on $P$, it forms a cycle, which contradicts the assumption that $\mathcal{G}$ is the DAG over the SCCs of the graph we build from $G$ and hence cannot have cycles. Hence, $\mathcal{C}$ cannot have more than one component, namely $C_0$.


Question about big O notation for function I'm just starting to learn Big O Notation and I was trying to understand how this function would scale:

$\frac{n(n-3)}{4}$

If the function was $n^2$, it would be quadratic, so O(n^2). However, the denominator gives me pause. Is this still a O(n^2) function? This is not homework. Thanks in advance for the help and clarification.

The denominator is just a constant so $O(\cdot)$ doesn't care about it.  For all $n\geq 0$, $\tfrac14n(n-3)\leq 1\cdot n^2$ so $\tfrac14n(n-3)\in O(n^2)$.


What are Lambda productions I'm taking a computational structures course and we just started going over context free grammars. I was confused when I started seeing lambda productions. What are they? Can't seem to find an answer anywhere.

$\lambda$ (lambda) is sometimes used to denote the empty string.  Thus, a "lambda production" is a production like $A \to \lambda$, i.e., a production that allows a non-terminal to generate the empty string.

Other sources will use $\epsilon$ (epsilon) to denote the empty string.  They might refer to them as epsilon productions.  They're the same thing.  It's just a difference in notation.


For a Turing Machine $M_1$, how is the set of machines $M_2$ which are "shorter" than $M_1$ and which accept the same language decidable? I wonder how come that the following language is in $\mathrm R$.

$L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a TM, and } L(M_1)=L(M_2), \text{ and } |\langle M_1\rangle| > | \langle M_2 \rangle| \Bigr\} $

(I know that it's in $\mathrm R$ since there's an answer for this multi-choice question, but without explanation).

I immediately thought that the $L_{M_1} \notin \textrm{co-RE} \cup \textrm{RE}$  since we know that checking if two machines accept the same language is really not decidable, I came to think: is it immediate "False", but it can't be since there's a lot of Turing machines who accepts the same answer and have different codings.

Thanks!

$L_{M_1}$ is in $R$ simply because the number of machine descriptions smaller than a given machine description is finite and any finite language is in $R$.


Priority data structure supporting operations Insert, Delete, Get in O(log n) I need a data structure to store priority $p$ for each key $k$ (unique). It must also support the following operations in $O(\log n)$ time:

$\text{Insert}(k,p)$ Inserts a key $k$ with priority $p$ into the structure. If there already is an element with key $k$, it changes its priority instead.

$\text{Delete}(k)$ Delete the element with key $k$.

$\text{Get}(k)$ Return the element with least priority among all elements with key $k' \leq k$.

At first I thought about balanced binary search trees. However I'd need to sort the elements by key and that just ruins the time complexity of the $\text{Get}$ operation.

Having two trees where one is sorted by key and the second one by priority doesn't help either.

Then I thought about using Fibonacci Heap, but here I have exactly the same problem.

Store the items in a balanced binary tree, sorted by key.  Augment each node of the binary tree to have a pointer to the lowest-priority element within the subtree rooted at that node.  This allows you to implement all three operations in $O(\log n)$ time.

Details: Whenever you insert or delete an element, you can follow the path from that element to the root, updating the augmented data inside each node you visit as you go.  This enables you to implement Insert and Delete in $O(\log n)$ time.  Any interval of keys can be expressed as the union of $O(\log n)$ subtrees, so the Get operation only needs to examine the augmented data inside $O(\log n)$ nodes and thus can be implemented in $O(\log n)$ time.


Why are some games np-complete? I read the Wikipedia entry about "List of NP-complete problems" and found that games like super mario, pokemon, tetris or candy crush saga are np-complete. How can I imagine np-completeness of a game?  Answers don't need to be too precise. I just want to get an overview what it means that games can be np-complete.

It just means that you can create levels or puzzles within these games that encode NP-Hard problems. You can take a graph coloring problem, create an associated Super Mario Bros. level, and that level is beatable if and only if the graph is 3-colorable.

If you want to see the specific way the NP-Complete problems are translated into the games, I recommend the paper "Classic Nintendo Games are (Computationally) Hard". It's well written and easy to follow.

An important caveat to keep in mind is that the NP-hardness requires generalizing the games in "obvious" ways. For example, Tetris normally has a fixed size board but the hardness proof requires the game to allow arbitrarily large boards. Another example is off-screen enemies in Super Mario Bros: the proof is for a variant of the game where off-screen enemies continue moving as if they were onscreen, instead of ceasing to exist and being reset to their starting position when Mario comes back.


Finding largest farthest increasing pairs in array? Is there a simple linear algorithm for finding in an array A two such elements that $A[i] > A[j]$ and $i - j$ is as large as possible? If one wants to actually return the indices, then linear memory usage seems impossible to avoid. If the only result needed is the value $i - j$, i.e. the distance, can we get away with less than linear memory?

Obviously, one can use constant memory if one is willing to loop over all pairs (i, j).

I'm going to assume that in your question, $i > j$ holds as well (if there is no such pair of values, then you have a nonincreasing array and the problem is trivial).

The two alternatives you've pointed out in your post are

$O(n)$ additional memory and $O(n)$ time
$O(1)$ additional memory and $O(n^2)$ time

An "intermediate" solution, for example, is to pick $O(\frac{n}{B} + B)$ additional memory and $O(n \cdot \left(\frac{n}{B} + B)\right)$ time. To do this, divide the array into continguous blocks of size $O(B)$, and so the number of blocks is $O(\frac{n}{B})$. For each block, store only the minimum value of the block in an array block_minimum.

Say you're at the $i$-th index. The goal is to find the first index in the array where the value of the corresponding element is greater than A[i].

First, for all preceding blocks, find the first block $j$ for which block_minimum[j] < A[i]. If such a block exists, scan that block and find the first index $k$ belonging to the block for which A[k] < A[i]. The index $k$ is the first index of the array for which A. There are $O(\frac{n}{B})$ preceding blocks.

However, if such a block doesn't exist, then second, iterate on preceding elements in the current block (there are $O(B)$ of them).

The combination of the two steps consumes $O(\frac{n}{B} + B)$ time for an index $i$. So the overall time usage is $O\left(n \cdot \left(\frac{n}{B} + B\right)\right)$ and the extra memory usage is $O\left(\frac{n}{B}\right)$ (the number of blocks).

If we choose $B = O(\sqrt n)$, we obtain a solution that uses $O(\sqrt n)$ memory and $O(n \sqrt n)$ time. This technique is commonly known as square-root decomposition.


Minimal Number of Fixed Size Sets to contain all Sets My problem is very similar to the one posted here. Instead of finding one set covering the maximum of subsets, I need to find the minimal number of sets to cover all subsets.

I have $U = \{1, 2, ..., 1000\}$ and $S \subseteq \{A \subset U |\space|A| \leq 15\} $. I know that $|S| < 1000$. I need to find a minimal number of sets of fixed size (e.g. 25) such that each set in $S$ is a subset of at least one of the fixed size sets.

It is not necessary that I have the minimum number of sets, a minimal number is sufficient.

I guess the problem can be split in those two steps:

Remove all sets that are subsets of other sets
Find minimal number of sets (of fixed size) that
contain all given sets

It doesn't make the problem easier. How would I go about it? What are good algorithms for the two steps?

If the sets are chosen randomly, then for the parameters you chose, the problem can be solved efficiently.  In particular, the following trivial algorithm will output the correct answer with high probability: take each set of $S$, pad it by adding 10 random elements, and output the result (all sets of $S$, padded).

This might sound wasteful, but for the parameters you mentioned, if the sets are chosen randomly, it's unlikely you can do better.  You can only do better if there exist two sets $s,t \in S$ that can be covered by a 25-element set, i.e., such that $|s \cup t| \le 25$.  This happens only if $s,t$ have at least 5 elements in common (i.e., $|s \cap t| \ge 5$).

Now when $s,t$ are chosen uniformly at random from all possible sets of size 15, the probability that they have two elements at random is very small.  It is approximately ${15 \choose 5}^2/1000^5 \approx 9 \times 10^{-9}$.  Also, there are ${1000 \choose 2}^2$ possible pairs $s,t$, so by a union bound, the probability that there exist two such sets $s,t$ is about $0.0045$.  This means there is only a small probability that you can cover two sets from $S$ by a single set of size 25, if the sets of $S$ are chosen randomly.

In general, for your problem, one approach would be to find all pairs of sets $s,t \in S$ that overlap in at least 5 elements.  Build a graph where $S$ is the vertex set and you add an edge between $s,t$ if $|s \cap t| \ge 5$.  Find a maximum matching in this graph.  Then you can use this to build a set of 25-size sets (one 25-size set per edge in the matching, plus one set per vertex not touched by the matching).  However, if the sets are generated randomly, this is unnecessary as it is unlikely  to find any pair of sets that overlap in at least 5 elements.

Anyway, if the sets are chosen uniformly at random, the problem is uninteresting for the parameters you gave.  If the sets aren't chosen uniformly at random and have some structure, I recommend that you edit the question to describe this structure.


Does every r.e. set containing the set of total recursive functions contain all partial recursive functions? Any r.e. subset of $A\subseteq\mathbb{N}$ which contains the set $$\mathrm{Tot}=\{i\mid i\ \mbox{is an index of a total function } f\}$$ must, by a standard argument (of Post?) contain some partial recursive function indices.

Given a partial function index (and every total function), it's pretty easy to construct many others, e.g. an index for the function which returns $0$ on prime inputs and is undefined otherwise.

But must $A$ contain all partial functions? This seems like a simple question, but I can't find an argument one way or the other.

Edit: I'm equally (more, actually) interested in the case where $A$ is recursive, e.g., represents the programs from some programing language.

Take $A = \{i\ |\ \phi_i(0) \downarrow \}$. It is obviously r.e., and includes $\mathrm{Tot}$.

Yet, it does not contain any index of, say, the always-undefined function $u$. Nor indices for any recursive partial function which is undefined at $0$.

The Kleene set also works: $K = \{i\ |\ \phi_i(i) \downarrow \} \supset \mathrm{Tot}$, yet it does not contain any index for $u$. (And it is r.e.)


Unambiguous grammar for regular expressions How to define a non ambiguous grammar for regular expressions on the $\Sigma =
 \{a,b\}$ alphabet?

Given that:

If $\Theta = \{+, ^*, (,),\cdot, \emptyset\}$ is a set of symbols

A regular expression on $\Sigma$ is a string such that one of the following condition applies

$r = \emptyset$
$r \in \Sigma $
$r = (s+t)$ or $ r = (s\cdot t)$ or $r = s^*$

I need to define a context free grammar to recognize regular expression. I know also that CF grammars are used to recognize mathematical expressions. so the grammar $G$ should recognize regular expressions.

$G:$

$ E \rightarrow E + T \mid T $

$ T \rightarrow  T \cdot F \mid F $

$ F \rightarrow(E) \mid E^* \mid a\mid b\mid\emptyset$


Logarithmic run time for calculating prime numbers? Here's the function I'm currently analyzing. I know it's not the most optimal but I'm not understanding the $\theta()$ of this algorithm. I've been told that it's not actually $\theta(n)$ but instead a logarithmic run-time and it had something to do with the bits of the value passed in. I'm not understanding how the bits are causing the logarithmic so if someone can explain that it'd be great.

   function isPrime(n):
1  if n = 2 return true
2  for i from 2 to n
3      if n % i = 0 return false
4  return true

Let's use a different parameter for your input, $m$. The number of instructions that your algorithm executes in the worst case is $O(m)$.

We often measure the running time of algorithms in terms of the length of their input (measured either in bits or in words), often denoted by $n$. The length of your input is $n \approx \log_2 m$, since this is how long it takes to encode the integer $m$ in binary. Therefore your algorithm actually performs an exponential number of instructions $O(2^n)$.

A different issue is the cost of arithmetic operations, such as the modulo operation on line 3. In most models of computation (and in real life), the cost of such an operation depends on the length of the numbers being operated on. Therefore your algorithm runs in time which is worse than $2^n$ by a polynomial factor $n^{O(1)}$ (the exact polynomial factor depends on the algorithm you use to perform the division). Such a running time is usually denoted $\tilde{O}(2^n)$.


In a set of sentences, how could I determine the fewest sentences that contains all characters? So, for the sake of simplicity, I am going to use English characters for this example. Let's say I have a set of strings of characters in English ranked by difficulty: Easy, Intermediate, Advanced.
So it would look like:
Easy
1. APQ
2. DL
3. RTE

Intermediate
1. FSMG
2. NDA
3. LOXCW

Advanced
1. GEW
2. ZAY
3. IVK

My question is: How could I go about finding the smallest set of strings that contain all the characters?
In this example, I would not need Easy 2 or Advanced 1 because their characters appear elsewhere in the set and they don't offer any characters not found elsewhere. Is there a type of algorithm best suited for this?
I can't just do a map lookup to see if I have come across a character before because I am looking for the smallest set. Also, I want to make sure, for instance, if I skip Easy 2 that I don't skip Intermediate 2 and Intermediate 3 since that's where I found the D and L that allowed me to skip Easy 2.
As for my real-world application, I have 4135 strings (about 100-200 characters long) split into 6 levels of difficulty, and these strings are sentences in Chinese. These strings have about 4000 unique characters combined. I'm basically looking for which sentences are worth learning and discard the ones that don't offer much/any new characters. Difficulty is mostly irrelevant, but I may run the algorithm within difficulties, then across the board.
Any help would be greatly appreciated.

This is an instance of set cover.  It is NP-hard, so there is no efficient algorithm to find the absolute optimal solution.  The problem has been studied and there are many techniques out there, which you can find by searching on set cover.
One approach is to use a heuristic to select a subset of strings that might be a little larger than absolutely necessary, but which can be found efficiently.  See, e.g., the greedy heuristic and others derived from it.
Another approach is to use a SAT solver or ILP solver to find the optimal solution.  This is not guaranteed to terminate within your lifetime; it might, or it might not.  Some solvers will let you run for a fixed amount of time and output the best solution found so far.


Weighted subset sum problem Given an integer sequence $\{ a_1, a_2, \ldots, a_N  \}$ that has length $N$ and a fixed integer $M\leq N$, the problem is to find a subset $A =\{i_1, \dots, i_M\} \subseteq [N]$ with $1 \leq i_1 \lt i_1 \lt \dots \lt i_M \leq N$ such that

$\qquad \displaystyle \sum_{j=1}^M j \cdot a_{i_j}$

is maximized.

For instance, if the given sequence is $-50; 100; -20; 40; 30$ and $M = 2$, the best weighted sum arises when we choose positions 2 and 4.

So that we get a value $1 \cdot 100 + 2 \cdot 40 = 180$.

On the other hand, if the given sequence is $10; 50; 20$ and $M$ is again 2, the best option is to choose positions 1 and 2 that we get a value $1 \cdot 10 + 2 \cdot 50 = 110$.

To me it looks similar to the maximum subarray problem, but I can think of many examples in which the maximum subarray is not the best solution.

Is this problem an instance of a well studied problem? What is the best algorithm to solve it?

This question was inspired by this StackOverflow question.

This problem can be solved by means of dynamic programming. One of the best known dynamic programming algorithms is for the knapsack problem. It may be instructive to compare the two problems.

Let $C(n,m)$ denote the solution to the maximal weighted sum problem
for the sequence $a_1, a_2, \ldots a_n$ with a subsequence of length $m$ where $1\leq n\leq N$ and $1\leq m\leq M$.

Then $C(n,m+1) = \mathop{max}(C(n-1,m+1), C(n-1,m) + (m+1) \cdot a_n)$.

To compute $C(N,M)$ this algorithm can be implemented in $O(N M)$ time and $O(N)$ space.


How can i compute tag-index-displacement bits of an address if cache size is not a power of two? How can i compute tag-index-displacement bits from an address if cache size is not a power of two?
Intuitively, i would be inclined to think that i can not directly indicate which bits of the address are used to tag, index blocks and displacement. Instead, i think that i should do some conversion such that it appears that the sum of the bits of tag, index and displacement must be greater than the bits of address. This because for the index i need a number i of bits such that i ≥ log_2(number of blocks), for displacement i need a number d of bits such that d ≥ log_2(dimension of each block in bytes) if i suppose a byte addressable cache. Some suggestions?

As suggested by maverick1989, i explicate the data of the part of the exercise that give me trouble. I have a cache direct-mapped of 5256KB with 32B blocks. Assume a 32-bit addressing mode. This mean that i have (5256*1024)/32 = 168192 blocks. Thus, i need log_2(32)=5 bits of displacement to address a single byte in a block and log_2(168192)=17.3597... bits of index to address a block in the cache. Obviously i have to use 18 bits instead of 17.35.... Now i have some trouble to find the value of these 18 bits, given the address. And after that, what about tag bits?

One way is by having multiple cache banks, each of which is a power of two in size. For example, 3 banks of 16kB each. The first 3 (bank_num) bits can be used with one-hot encoding to decide which bank would need to be checked to access the requested data (or to write to).

The rest of the cache access would proceed as usual (look up TLB to get tag bits, index into cache in parallel, etc.)

However, usually non-powers of two caches are not used because the IPC to cache size curve is such that it you find the sweet spot very close to a number that is a power of two (or you don't lose significantly in IPC by moving to a power of two).