# Question
Title: Proving that a context-free grammar is unambiguous
I have to find an unambiguous context-free grammar that generates the following language. $$L= \\{ w \in \\{a,b\\}^+ : |w|\_a = |w|\_b\\}$$ I think I have found the context-free one, it should be this one. $$S \to aS'bS'|bS'aS'$$ $$S' \to aS'bS' | bS'aS' | \lambda$$ Now I am stuck with proving whether it is unambiguous or not. I think it is but how should I do that?

# Answer
> 2 votes
Consider the word $abab$. It has two derivation trees (rendered using syntree):

Hence your grammar is ambiguous. In order to make an unambiguous grammar, we have to force the parse to be unique. We identify the word with a path in which $a$ corresponds to $\nearrow$ and $b$ to $\searrow$. We're looking for a non-empty path that ends at level ground.

If the path starts with $\nearrow$, then we can look at the first time at which it returns to level ground, and decompose the path accordingly: $\nearrow x \searrow y$, where $x$ is a path that never goes below level ground, and $y$ is an arbitrary path that ends at level ground. Hence we need a way to capture paths that end at level ground and never go below level ground. Such a path can also be decomposed uniquely as $\nearrow x \searrow y$, where this time both $x$ and $y$ never go below level ground.

The considerations above lead to the following unambiguous grammar: $$ \begin{align\*} &S \to aAbS' \mid bBaS' \\ &S' \to aAbS' \mid bBaS' \mid \lambda \\ &A \to aAbA \mid \lambda \\ &B \to bBaB \mid \lambda \end{align\*} $$

As a somewhat degenerate example, the derivation tree for $abab$ is:

The proof that this grammar is unambiguous goes along the description above, though the formal proof by induction is somewhat challenging.

---
Tags: context-free, formal-grammars
---


# Question
Title: Help with question involving k-regular graphs
In my last test, our teacher gave us this question:

> In an conference with 90 participants, the staff wants to divide all participants in 6 groups of 15 participants each. Each participant of each group must have at least one article with exactly 7 other participants of the same group. Prove using Graph Theory that this division is impossible.

I spent a lot of time thinking about, but couldn't find an definitive answer. I think that this involve bipartite matching somehow, but I have no idea on how to proceed with the proof. I thought that maybe creating a k-regular graph would prove that this don't have a matching, but I couldn't come with the graph representing the problem.

Can I get some help with this?

# Answer
> 1 votes
There is no 7-regular graph on 15 vertices, since $7\times 15$ is odd.

---
Tags: graphs
---


# Question
Title: A restatement of Moore's law that takes into account quantum computing
The first line of the Wikipedia article on Moore's law states that

> Moore's law is the observation that the number of transistors in a dense integrated circuit doubles about every two years

As scientists groan on about running into the physical limits of Moore's law, another bunch of scientists<sup>\[or the media?\]</sup> seems to feel like they can keep up the trend by leveraging characteristics of quantum computers.

However, a quantum computer doesn't use transistors in the same way that a traditional computer does, and adding another qubit, according to my knowledge, can double the computational power of the computer!

For that reason, is it time to restate Moore's law in such a way that it can take into account computational power as an abstract concept, and not necessarily a physical one?

Does it even make sense to ask that question?

# Answer
Quantum computers are interesting, but I don't think the primary motivation for quantum computers has anything to do with Moore's law. You might want to double-check where you got that impression from. Quantum computers -- if possible -- will be faster for some narrow set of problems, but by no means for all problems. See Why and how is a quantum computer faster than a regular computer? and Is it proven that quantum computation is no better at solving NP complete problems than classical computation?.

It's not really accurate to say that adding another qubit doubles the computational power of the computer. I suspect you might be falling for a common misconception about quantum computing (that they "try all possible combinations..."). See The Limits of Quantum by Scott Aaronson for some explanation.

I don't think there is any need to restate Moore's law. It is a rough rule of thumb about *classical* computers. It doesn't claim to say anything about quantum computers or computational power in general.
> 3 votes

---
Tags: complexity-theory, computer-architecture, quantum-computing, cpu
---


# Question
Title: Is there an existing protocol where a sender does not know who he is sending data to?
I was thinking about how the BitTorrent protocol automatically gives every peer a list of IPs of every other user who is currently seeding / leeching off the torrent in question. Is there an existing protocol where, somehow, the destination address is vague enough or unknown to the sender (and perhaps becomes more known as the packet is sent through the routers ?) Or is there research in implementing something like this that could be interesting to read ?

# Answer
If you want strong protections for the identity/anonymity of the participants, you might be interested in systems for anonymous communication, such as Tor.

If you're just interested in systems where the destination's address isn't necessarily known under normal operating conditions (but it's not a critical security goal to ensure it can never be known), you might be interested in peer-to-peer overlay networks, such as Chord and many others.
> 1 votes

---
Tags: communication-protocols, protocols
---


# Question
Title: Bounded Quadratic Congruence Problem Variant (for square Residue)
This is a follow up to the following question: Bounded Quadratic Congruence Problem Variant (for some specific Residue)

As indicated that for square residue the problem is solvable in polynomial time. Let us consider a modified version of the same problem:

Given: 3 positive integers $a,b,L$. Problem: Is there a positive integer $x\<L$ such that $(M\*x)^2≡a(mod\ b)$?

where $M$ is some positive integer constant, $a$ is a residue that is also a square.

Can the same approach be used to solve this slightly modified problem easily? It seems so but I am not sure.

# Answer
The problem is NP-complete. Let $d = \gcd(M,b)$. If $a$ is not a multiple of $d$, then there is no solution. Otherwise, let $a' = a/d$ and $B = b/d$ and $c = M/d$ and $A \equiv a' c^{-2} \pmod B$. Then the original equation has a solution if and only if $x^2 \equiv A \pmod B$ has a solution with $x\<L$. As you previously noted, the latter problem is NP-complete.
> 1 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: 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?

# Answer
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.
> 2 votes

---
Tags: information-theory, entropy
---


title: Proving that a Language is non-Regular

text:
# Question
Title: Proving that a Language is non-Regular
> Prove that $L\_2 = \\{ w \in \\{a,b\\}^\* \mid w = a^ib^j, i \neq j \\}$ is not regular.

I was wondering if my intuition holds for proving this language as not regular:

Let $q = \max(i, j) - \min(i, j)$.

Case 1: $i \> j$

Let $$L\_3 = b^q \Rightarrow L\_2 \cdot L\_3 = \left \\{ a^ib^{j+q} \right \\}=\left \\{ a^ib^i \mid i \ge 0 \right \\}.$$

And then do the same for when $j \> i$.

Is this allowed?

# Answer
> 2 votes
No that's not allowed, since $i$ and $j$ are not fixed.

Here is a solution using pumping lemma:

> The better approach is to apply pumping lemma. Let $x = a^{n!}b^{(n+1)!}$, where $n$ is the pumping constant. Note that $u = a^i$ and $v=a^j$ for some $i\geq 0$ and $j\>0$ plus $i+j\leq n$. Then we let $k = 1+\frac{n\cdot n!}{j}$. After that, $uv^kw = a^mb^{(n+1)!}$ where $m = n!+(k-1)j = n!+n\cdot n! = (n+1)!$. Contradiction.

Here is another solution using closure result (which is less tricky):

> Suppose $L\_2$ is regular. Then $(\Sigma^\* - L)\cap a^\*b^\* = \\{w\in\\{a, b\\}^\*|w=a^ib^j, i=j\\}$ is regular by closure result. Then it's easy to gain a contradiction by applying pumping lemma to $(\Sigma^\* - L)\cap a^\*b^\*$.

---
Tags: formal-languages, regular-languages
---


# Question
Title: Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods
When encoding a a 2D Datamatrix barcode, I want the smallest output size. There are means to encode a compressed a string using some methods like C40. Reference:

Here's a reference: https://en.wikipedia.org/wiki/Data\_Matrix#Text\_modes

Some sections of the string will compress more efficiently than others depending on the encoding method.

To be clear, I'm not trying to make my own compression scheme.

I want to compute the best combination of existing compression schemes. For example, I can individually use Ascii or C40 to encode an entire string. Each scheme has its unique benefits.

BUT I can also compress specific parts of the string with different schemes. So, switching back and forth between Ascii and C40 **can** result in a more efficient compression than C40 or Ascii alone.

**QUESTION:** How do I optimize the *selection* of compression schemes for section of the input string. I would be comfortable narrowing it down to only combining c40 and ascii.

Are there any algorithms for scanning strings and and optimizing the result?

# Answer
> 1 votes
If you want to find the optimal combination, one approach would be to use dynamic programming. Let $f(n,s)$ denote the length of compressing the first $n$ characters via some combination of compression methods, ending with the compression subsystem in state $s$. Here $s$ represents both which compression method is currently being used (Ascii or C40) as well as its internal state (i.e., whether you are currently in set 0, set 1, set 2, or set 3).

Then you can compute $f$ recursively. Applying memoization, we get a dynamic programming algorithm to compute $f$. The resulting algorithm will take $O(n)$ time to compute the best compression.

How do you compute $f$ recursively? Basically, when computing $f(n,s)$, you consider both possible cases for how to encode the $n$th character:

* Case 1: Stick with the same compression method and state you had before, when encoding the $n$th character. The cost of doing so is $f(n-1,s) +$ the number of bits to encode the $n$th character when in state $s$.
* Case 2: Switch compression methods and/or state just before encoding the $n$th character. The cost of doing this is $f(n-1,s') + $ the number of bits to switch from state $s'$ to state $s$ and then encode the $n$th character while in state $s$.

You should choose whichever of those provides a shorter encoding. In other words, $f(n,s)$ is the smaller of these two quantities. This gives a recursive algorithm for computing $f$, which can be memoized, yielding a solution that is essentially dynamic programming.

Since there are only 8 possible states (2 compression methods $\times$ 4 choices of the character set), the running time to compute $f(n,s)$ is $O(n)$. This gives you a linear-time algorithm to find the best combination of compression algorithms for encoding any given string.

---
Tags: algorithms, optimization, strings, data-compression, encoding-scheme
---


# Question
Title: Find longest interval if the intervals can propagate from one to another
Let's say we have given $n$ points on the x-axis, each point described with two integers: $x\_i, a\_i$, $x\_i$ meaning it's position on the x-axis, and $a\_i$ meaning that it can activate all the points that lie in the range $\[x\_i, x\_i + a\_i\]$.

The problem is for each of those n points to find the maximum number of points it will activate (note that the activation propagates for one to another point).

For example we have 4 point: $x = \\{1, 2, 8, 10\\}, a =\\{7, 3, 8, 2\\}$ The first point will activate the second and the third, the third point will then activate the last 4th point. The second point wont activate any points, only itself, the third point will activate the 4th point and the last point wont activate any points rather that itself. So the result should be this array: $\\{4,1,2,1\\}$

I noticed that the activated points will form a subarray starting in each index $i$ and now we might check with binary search, but I don't know how to check if each point is going to be activated or not. Please give me some hints where to start.

# Answer
You asked how to get started, so I will give you advice on how to get started:

> Start by trying each of the algorithm design paradigms you know: divide and conquer, dynamic programming, greedy, etc. One of those will work -- I will let you have the joy of discovering the details.

Another hint, if you get stuck after trying that one:

> Try to work out some small examples by hand. If you were going to fill in the results array in some order, what order would make it easiest to do that? If you were going to process the points in some order, what order would make it easier to figure out the answer for each point as you process it (taking into account the answer for points you've previously processed)? Can you spot a pattern.

This should be enough that you should be able to work out a solution.
> 1 votes

---
Tags: algorithms, binary-search, intervals
---


# Question
Title: Prove EXPTIME \ NP is not a subset of NP-Hard?
If we assume that NP is not equal to co-NP, how do we show that EXPTIME \ NP is not a subset of NP-Hard?

# Answer
Hint: note **co-NP** $\subseteq$ **EXPTIME**, and **co-NP-complete** $\cap$ **NP** = $\emptyset$ since **NP** $\neq$ **co-NP**, it remains to prove **co-NP-complete** $\nsubseteq$ **NP-hard**.

> Further hint: if **co-NP-complete** $\subseteq$ **NP-hard**, try to show for each language $L\in$ **NP**, you can build a NTM deciding $\bar L$, thus **NP** $\subseteq$ **co-NP**, a contradiction.
> 1 votes

---
Tags: complexity-theory, automata, np-hard, np, co-np
---


title: Proving an algorithm wrong

text:
# Question
Title: Proving an algorithm wrong
So I have this algorithm that outputs the largest value of an array:

* Input: $A\[1,\dots,n\]$, $n\geq 1$
* Output: Largest value of an array

```
Maximum (A)
  m = A[1]
  i = 1
  while i < n
    if A[i+1] > A[i]
      m = A[i+1]
    i = i+1
  return m

```

I have to prove this algorithm wrong and I'm confused how to do that, because to me the algorithm seems correct. Any advice on how to do this are very much appreciated.

# Answer
Consider the input $100,0,1$.

As a follow-up, identify the bug, and correct the algorithm.
> 4 votes

# Answer
Two points which will prove the algorithm is wrong

1. Array type starts with the zeroth element, in that case, A\[0\] will be eliminated even if it's the highest number. So, m should start with **A\[0\]**, not A\[1\].
2. The comparison of each element should be made with the maximum number element(m) and not with its previous element. So, it should be **A\[i+1\] \> m**, not A\[i+1\] \> A\[i\]
> -1 votes

---
Tags: algorithms, arrays, correctness-proof
---


# Question
Title: Extended grammar form (backus-naur) and simple grammar forms equivalence
Square braces around a grammar symbol or symbols denote that these constructs are optional. Thus, production A -\> X\[Y\]Z has the same effect as the two productions A -\> XYZ and A -\> XZ.

Curly braces around a grammar symbol or symbols say that these symbols may be repeated any number of times, including zero times. Thus, A -\> X{YZ} has the same effect as the infinite sequence of productions A -\> X, A -\> XYZ, A -\> XYZYZ, and so on.

Show that these two extensions do not add power to grammars; that is, any language that can be generated by a grammar with these extensions can be generated by a grammar without the extensions.

Proof

```
A -> X[Y]Z     --->        A -> XZ | XYZ

A -> X{YZ}     --->        A -> XB
                           B -> YZB | ε

```

How can we prove that both forms will generate the same language?

# Answer
Show that given a derivation in one grammar, there is a corresponding derivation in the other grammar which derives the same word. You might find it easier to work with parse trees instead of just derivations.

In the case of optional brackets, this is rather easy. Let us consider your example of a grammar with derivation rule $A \to X\[Y\]Z$ which is replaced by the derivation rules $A \to XZ$ and $A \to XYZ$. Given a derivation in the original grammar, each application of $A \to X\[Y\]Z$ replaces $A$ by $XZ$ of by $XYZ$. In the former case, we can simulate this in the new grammar using $A \to XZ$, and in the latter by $A \to XYZ$. Conversely, given a derivation in the new grammar, we can replace each application of the rules $A \to XZ$ and $A \to XYZ$ by an application of $A \to X\[Y\]Z$.

The case of braces is more complicated. One direction is easy – given a derivation in the original grammar, you can convert it to an equivalent derivation in the new grammar by replacing an application of $A \to X \\{YZ\\}$ by an equivalent derivation using only the rules $A \to XB$ and $B \to YZB \mid \epsilon$. In the other direction, you have to first show that if $B$ appears in a parse tree, then you can associate with it a path in the tree which corresponds to a derivation of the form $B \to YZB \to (YZ)^2B \to \cdots \to (YZ)^k$ for some $k \geq 0$. Given that, every application of $A \to XB$ can be associated with a path corresponding to a derivation $A \to^\* X(YZ)^k$, which can be implemented in the old grammar by the rule $A \to X \\{YZ\\}$.

In the last paragraph I have been vague about some association of vertices in the parse tree to a path and to a derivation, which really amounts do a decomposition of all legal parse trees. These concepts will have to be formalized in a formal proof of equivalence.
> 2 votes

---
Tags: context-free, compilers
---


# Question
Title: Why do we need to convert binary numbers into hexadecimal, octal and decimal?
Computer reads binary. Now my question is, what is the use of hexadecimal, octal and decimal? Do Computers understand or can read hexadecimal, octal and decimal? This question remains a mystery for me. Why memory locations use hexadecimal, it should be in binary right? Or is it because it is a binary and by time we read its memory location, the computer converts its memory location from binary into hexadecimal for us to make it readable?

# Answer
You got it in one. Hex is easier for humans to read but also trivial to convert to and from binary. The computer itself only uses binary, in the sense that every wire is either on or off. But, at the same time, you can look at the pattern of ons and offs on four adjacent wires and call that a hex digit.
> 2 votes

# Answer
Computers, on the lowest level read and manipulate binary representations. But this does not mean that they can't be programmed to manipulate octal,hex or even any other number base system. The choice of hexadecimal representation is taken because of human readability and ease of conversion.

Note that for a hexadecimal number, for example $7FC3$, in order to convert it to binary we need only take each hex digit and convert it to binary. Each hex digit (0-F) needs 4 binary digits to represent. $$7\_{16} = (0111)\_{2}$$ $$F\_{16} = (1111)\_{2}$$ $$C\_{16} = (1100)\_{2}$$ $$3\_{16} = (0011)\_{2}$$ This also works the other way round so its much easier for big binary numbers (that appear in memory addresses) to convert them into hex and manipulate them with this representations. If it was to convert them to decimal it would require more work (computing the corresponding polynomial) than this almost trivial algorithm.
> 1 votes

# Answer
You are confusing what is there, and how it is displayed. Memory contains bits, the bits are interpreted as integers, floating point numbers, pointers, characters whatever. And they are displayed by software in some way, whatever is most appropriate; in binary, hexadecimal, decimal, interpreted as characters and so on.

The computer doesn't convert anything when reading a memory location. It takes it as it is, and will interpret it according to what it thinks the data means. Conversion into hexadecimal only happens when you run software that is supposed to display memory contents as hexadecimal numbers, and is done by software running on the computer.
> 1 votes

---
Tags: number-formats
---


# Question
Title: For proving that L is in NPC, why do we reduce a known L' into L and not the other way around?
For proving that $L$ is in NPC, why do we reduce a known $L'$ into $L$ and not the other way around i.e. reducing $L$ into $L'$.

# Answer
Saying that a problem is **NP** complete is, approximately, saying that there is no good algorithm for it.

Saying that $L$ reduces to $L'$ means, approximately, that one way of producing an algorithm for $L$ is to use an algorithm for $L'$ as a subroutine.

Now, if $L$ reduces to $L'$ and $L$ is has no good algorithm, then we know that $L'$ also has no good algorithm – if it did, then "use $L'$ as a subroutine" would be a good algorithm for $L$, but no good algorithm exists. However, if $L'$ reduces to $L$ and $L$ has no good algorithm, we know that "use $L$ as a subroutine" isn't a good algorithm for $L'$ but so what? There are infinitely many other algorithms and we know nothing about whether those are good or bad.
> 2 votes

# Answer
A problem $L'$ is NP-hard if for every problem $A$ in NP there is a polytime reduction from $A$ to $L'$. Part of the logic of this definition is that it implies that if $L'$ is in P then all problems in NP are in P, since the algorithm for $L'$ can be used to solve any other problem in NP via the polytime reduction.

Suppose that we already know that $L'$ is NP-hard, and we want to show that $L$ is NP-hard. Intuitively, we want to show that $L'$ can be solved using $L$, and this is formalized by giving a polytime reduction from $L'$ to $L$. Using the definition of NP-hard, you can show that such a reduction implies that $L$ is NP-hard as well – I suggest you work it out.

Conversely, reducing $L$ to $L'$ implies nothing about the hardness of $L$, since it only shows that $L'$ is at least as hard as $L$. Indeed, if your goal it show that $L$ is NP-complete, then presumably you already know that $L$ is in NP, and this already implies that $L$ can be reduced to $L'$, since $L'$ is NP-hard! So reducing $L$ to $L'$ adds absolutely no new information to the picture.
> 1 votes

---
Tags: np-complete, np-hard, np
---


# Question
Title: Why vertices of directed acyclic graph are considered strongly-connected components?
Well the title pretty much says it all, I've heard our professor saying that the smallest strongly-connected components in DAG (directed acyclic graph) are its vertices. Sadly I was unable to ask him for explanation and now this is stuck in my head ever since.

# Answer
> 8 votes
This has to do with the definition of Strongly Connected Component in graph theory.

> A graph to be said to be Strongly Connected if every vertex is reachable from every other vertex.

The smallest possible graph of any type consists of a single vertex. Since that vertex can reach itself (since it is itself), the graph therefore meets the criteria, and can be considered *Strongly Connected*.

In this image, the nodes at the bottom right, and the top middle are examples of smallest possible strongly connected components:

---
Tags: graphs
---


# Question
Title: Sort binary matrix by swapping columns to make subrectangle of ones with maximum size
We have given binary matrix (matrix containing only 1 and 0) of size $n\cdot m$. We want to order the matrix such that the biggest rectangle containing only ones is with maximum size.

For example if the following matrix is given:

```
1000  0010
1101  0111
1101  0111
1101  0111

```

We should output 9 because the biggest rectangle we can get is with size 9. We are allowed to swap any columns infinite number of times and we are only requested to find the maximum size of the subrectangle.

Can we solve this problem faster that trying all possible permutations?

# Answer
Yes, you can solve it faster than trying all possible permutations.

The biggest such rectangle must span consecutive rows. So, for all $i,j$ with $i \le j$, check what is the biggest rectangle you can make that spans rows $i..j$. You can do this check in $O(mn)$ time, by checking which columns have a 1 in all of those rows. There are only $O(m^2)$ possible values of $i,j$.

So, the running time of this simple method is $O(m^3 n)$, which is faster than trying all permutations. (Trying all permutations would take $\Omega(m \cdot n!)$ time, which is far slower -- it is exponential time, rather than polynomial time.) I make no claim that this simple method is optimal -- rather, I merely claim that the answer to your question is "yes".
> 1 votes

---
Tags: algorithms, sorting, matrices
---


# Question
Title: Definitions of: virtual address space, page size
(I can't seem to find actual definitions of these terms anywhere, only hints and guesses).

Is it fair to say, that:

* **Virtual address space** is the amount of bytes that can fit into RAM cells of all virtual addresses belonging to this virtual address space (virtual address space HAS MANY pages HAS MANY virtual addresses).
* Page is a set of virtual addresses (and it maps to the frame - a set of actual physical RAM addresses). **Size of a page** = amount of bits that can fit into this page. So, if the system is byte-addressable (meaning one RAM cell can hold 8 bits), page size is 8 * number of RAM addresses in a page.

# Answer
> 2 votes
Wikipedia defines a virtual address space as follows:

> In computing, a virtual address space (VAS) or address space is the set of ranges of virtual addresses that an operating system makes available to a process.

This definition is OK. However, I'll define the term "virtual address space" one word at a time.

> space

`space` is a mathematical term that generally means a set of things, where these things are potentially related in one or more ways.

> address

An address is generally an identifier for a thing, which is distinct from the thing itself. In this context, an address is a value that potentially identifies a physical device in the computer system. Typically, addresses are non-negative integers that identify memory locations that can hold data, and each address is represented as a constant number of binary digits.

> virtual

Virtualization means to create an interface for something that is different from its actual interface that is built with the thing. This is useful for many reasons such as managing a resource for multiple users or providing protection for a resource from being misused or corrupted.

Now let's put it all together. **A virtual address space is a set of addresses created by the virtualization system (the OS) to allow an application to access system resources indirectly so that the system can control access to its resources.**

> Virtual address space is the amount of bytes that can fit into RAM cells of all virtual addresses belonging to this virtual address space (virtual address space HAS MANY pages HAS MANY virtual addresses).

A VAS is not a single number (although it can be a set that contains a single address). Also a VAS is not memory itself; it does not store anything because it can't. Moreover, given only a VAS, you can only determine how many virtual addresses you have, but not how much memory you can use. you can have a 4 GB VAS, but zero physical memory locations. That's because of virtualization. That's what makes it *virtual*. It's up to the OS that creates it. Also the term "page" is independent from the term "virtual address space" in general. Although the OS can choose to partition the VAS into virtual pages, where each virtual page is a sub-set of the VAS.

> Page is a set of virtual addresses (and it maps to the frame - a set of actual physical RAM addresses).

Yes. Although a virtual page may not map to anything (invalid).

> Size of a page = amount of bits that can fit into this page. So, if the system is byte-addressable (meaning one RAM cell can hold 8 bits), page size is 8 * number of RAM addresses in a page.

Yes. When a virtual address space is said to be byte-addressable it means that each virtual address (an identifier) *can* identify an 8-bit resource (typically, physical memory cells). When a physical address space is said to be byte-addressable it means that each (valid) physical address (an identifier) *does* identify an 8-bit *physical* resource (typically memory cells).

---
Tags: operating-systems, virtual-memory
---


# Question
Title: Defining the polynomial hierarchy using $\Pi_i^p$ instead of $\Sigma_i^p$
From Computational Complexity - A Modern Approach, it is claimed in a remark that the following holds true.

> Remark 5.5
>
> Note that $\mathbf\Sigma\_1^p = \mathbf{NP}$ and $\mathbf\Pi\_1^p = \mathbf{coNP}$. More generally, for every $i \geq 1$, $\mathbf\Pi\_i^p = \mathbf{co\Sigma}\_i^p = \\{ \overline{L} : L \in \mathbf\Sigma\_i^p\\}$. Note also that $\mathbf\Sigma\_i^p \subseteq \mathbf\Pi\_{i+1}^p$, and so we can also define the polynomial hierarchy as $\cup\_{i\>0} \mathbf\Pi\_i^p$.

However, I am having trouble understanding this. Similar claims are made in lecture notes found on the web, but none of them give a proof since they are all left as exercise. Would it be possible to prove this using NTM instead of verifiers?

# Answer
> 2 votes
It is a direct consequence of the definition of $\textsf{PH}$.

Remember:

$\qquad \Sigma\_i^P = \textsf{NP}^{\Sigma\_{i-1}^P}$

$\qquad \Pi\_i^P = \textsf{coNP}^{\Sigma\_{i-1}^P} $

What we want to prove is:

$\qquad \bigcup\_{i\>0}\Sigma\_i^P = \bigcup\_{i\>0}\Pi\_i^P $

We have:

$\qquad \Sigma^P\_i \subseteq \textsf{coNP}^{\Sigma^P\_i} = \Pi\_{i+1}^P$

$\qquad \Pi^P\_i \subseteq \textsf{NP}^{\Pi^P\_i} = \textsf{NP}^{\Sigma\_i^P} = \Sigma^P\_{i+1}$

Taking the union yields:

$\qquad \bigcup\_{i\>0} \Sigma^P\_{i} \subseteq \bigcup\_{i\>0} \Pi^P\_{i} \subseteq \bigcup\_{i\>0} \Sigma^P\_{i}$

which is exactly our goal.

---
Tags: complexity-theory
---


# Question
Title: In Bankers Algorithm, with three processes, in the question of need <= work(aka available). Is the need of 1 0 1 <= 0 0 2 work?
Three processes A B C. When conducting the safety algorithm, no explanation that I've been able to find answers the question of how the processes are being compared. Is it the total processes added up, or every process individually must pass the '\<=' operator, or is it like regular integers where Process A would be the most significant comparison?

https://www.youtube.com/watch?v=2V2FfP\_olaA

TLDR Answer: It's individual based. Each process work/available item in the matrix, must satisfy each need.

# Answer
In Banker's Algorithm,

Every processes are compared individually.

So, In your question

If the Need is `1 0 1` and available matrix is `0 0 2`, then this need can't be satisfied. Because there is no resource available for Process A.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Is L={<M>|M is a TM and L(M) is uncountable} decidable?
Is $L=\\{\langle M\rangle\mid \text{$M$ is a Turing machine and $L(M)$ is uncountable}\\}$ decidable?

My intuition is that it is not, but I'm not sure if Rice's Theorem applies in this case. If it is not decidable, how can I prove that using reducibility?

# Answer
> 10 votes
This is somewhat of a trick question. What you are missing is that there are no uncountable languages over a finite (or even countable) alphabet. This should be enough information to answer it.

(I initially gave the entire answer away, but edited it out after considering a bit.)

---
Tags: turing-machines, computability, undecidability, rice-theorem, uncountability
---


# Question
Title: Solving $T(n)=4T(n/4)+\log n$ using master theorem
$T(n)=4T(n/4)+\log n$

I'm solving this recurrence relation by master theorem.

$a=4, b=4$ , $n^{\log\_b a}=n^{\log\_4 4}=n$

$f(n)=\log n=O(n^{1-\epsilon})$

when $\epsilon\<1$, it is correct. So, $T(n)=\Theta(n)$.

But I'm confused how can $n$ be an asymptotically tight bound of $\log n$?

I'm not sure my solution is correct.

# Answer
Let's use the other method to solve recurrences, namely, repeated substitution, assuming that $n$ is a power of 4: $$ \begin{align\*} T(n) &= \log n + 4T(n/4) \\ &= \log n + 4 \log(n/4) + 16T(n/16) \\ &= \cdots \\ &= \log n + 4 \log(n/4) + 16 \log(n/16) + \cdots + (n/4) \log (n/(n/4)) + n T(1) \\ &= (n/4) \log 4 + (n/16) \log 16 + \cdots + (n/n) \log n + nT(1) \\ &= n \log 4 \left(\frac{1}{4^1} + \frac{2}{4^2} + \cdots + \frac{\log\_4 n}{n}\right) + nT(1) \\ &= \frac{\log 4}{9} (4n - 3\log\_4 n - 4) + nT(1) \\ &= \left(\frac{4\log 4}{9} + T(1)\right)n - \frac{\log n}{3} - \frac{4\log 4}{9}. \end{align\*} $$ In particular, we see that $T(n) = \Theta(n)$.

Intuitively, what happens is that, roughly speaking, the dominant terms are $(n/4)\log(n/(n/4)) = (n/4)\log 4$ and $nT(1)$, which are both $\Theta(n)$; in the former term the logarithm is applied to a *constant*, and so the fact that the recurrence has $\log n$ rather than, say, $\log^2 n$ only affects the resulting hidden constant, but not the asymptotic complexity.
> 3 votes

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: How to find vertices of bounded region made by intersection of lines
Suppose we have random lines made with 2 points. and point has (x,y)

For example:

Now when we draw a random line you will see many lines intersect with each other. This eventually gives rise to bounded regions. How to find the vertex points for each bounded region?

**My approach**: First we find all the intersection points of the various lines. In some cases multiple lines intersect at the same point.

However I am not sure how to pick the points that make up a bounded region.

Thanks in Advance.

# Answer
Finding the all the vertices for *all* of the bounding regions is roughly the same amount of work as creating a *doubly connected edge list* (DCEL) that represents your regions, so I will show how to construct a DCEL from a set of line segments. After that, finding all the boundary points for each region from a DCEL is a simple operation.

First, we find all line segment intersections between the segments we start with. This can be done efficiently with the standard sweepline algorithm for line segment intersection, which is described in various references, such as in these slides. This can be done in $O(n\log n + K)$ time, where $n$ is the number of line segments and $K$ the number of intersections between these lines.

For the next part, we construct a set of endpoints $P$ and a set of line segments $L$, where for each segment $l\in L$, we also store the pair of points $(p,q)$ from $P$ that are the endpoints of segment $l$. First, add all original line segments to $l$ and the corresponding endpoints to $P$.

Then, at every intersection point $p$, split the segments that intersect at that point into two segments 'separated' by $p$, store the point $p$ in the set $P$, remove the old segment from $L$ and add the new segments to $L$, setting their endpoints accordingly.

In the end, we have represented our regions with a graph $G=(P,L)$, where the vertex set $P$ are all points in our 2D space (including the intersection points) and the set of edges $L$ contains all segments connecting these points. Note that the graph $G$ doesn't have any crossing edges by construction, so it is *planar*.

From this planar graph, we can construct a DCEL, as shown in this answer, which is mostly bookkeeping.

In the DCEL, each region is associated with a representative half-edge. From that half-edge, we can find all half-edges that form the border of the region. Then, the vertices of the region are all vertices of those half-edges.

---

It is possible to skip the DCEL and find the vertices directly, but likely you need to do almost the same thing. The main advantage of using a DCEL as an intermediate step is that someone else already has made an algorithm to construct a DCEL.
> 4 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Find path from s to t that goes through another node w
If you have directed and unweighted graph G how could you find a path from node s to node t that also goes through another node w? This could be a non-simple path.

# Answer
If you don't care about simplicity, a path from $s$ to $t$ that goes through $w$ is just a path from $s$ to $w$ concatenated with a path from $w$ to $t$.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Following but not intersecting time segments to detect multiple accounts
In some code I'm currently writing, I'm stuck on the following algorithm to implement. The goal is to find real world users using multiple different accounts.

I've a List of UserData. This list is pretty big (\> 10M entries)

A `UserData` is defined as: `{ userId, List<TimeSegments> }`. A TimeSegment is `{connectionDate, disconnectionDate}`. We can assume here that the average size of the list of timeSegments is 100.

I want do find groups of users such as:

* for each group of users, all timeSegments are non overlapping *(we assume here that a user cannot be connected with multiple accounts at the same time)*
* for each user U1 in a group of users, there is a user U2 in the same group such as at least one, U1 disconnected and then U2 connected in the following 15 minutes (or the opposite) *(we assume here that at least once, a user will disconnect from an account and with another one immediately after)*

Of course, the brute force O(n²) solution (find couples of users and then merge those couples) is not good enough due to the size of data

Any idea of how to start this ?

Thanks !

# Answer
> 1 votes
I would sort all events (logins, logouts) in increasing order by time, then walk through the list. For each logout event from user $u$ starting at time $t$ encountered during this walk, scan forward from that point until hitting time $t+15$, incrementing a counter for the pair $(\min(u, v), \max(u, v))$ in a hashtable whenever a login event for user $v$ occurs. (You could alternatively increment two counters, $(u, v)$ and $(v, u)$, but this uses twice the memory and gains nothing.)

Afterwards, every large count in your hashtable corresponds to a "candidate pair" of users. Walk through the hashtable, and for each counter above a threshold of your choosing, check whether the logged in intervals for this pair of users intersect. If they don't, flag the pair as likely operated by the same human.

(BTW, I'm not confident that mutually exclusivity of login intervals will apply in practice: Users might run their two accounts simultaneously in different browsers, one in a phone, or one in a private window, etc. Depending on your application, maybe a better criterion would be to check whether the two users actually *interfere* with each other to any significant extent -- e.g., for SO, whether the same questions and answers tend to be upvoted/downvoted.)

There will probably be large numbers of pairs in the hashtable with low counts, due simply to chance. If you find that singleton counts are bloating the hashtable, you could reduce memory usage (at the cost of introducing a very small amount of inaccuracy) by using a Bloom filter to store all "first" encounters of any $(u, v)$ pair, and only creating counts in the main hashtable for a pair $(u, v)$ when $(u, v)$ is already in the Bloom filter.

---
Tags: algorithms, optimization
---


# Question
Title: How to prove that language is decidable?
Prove or disprove: The following language $L$ is decidable:

$\\{ \langle M, x\rangle: M \text{ is a Turing machine and } M(x) \text{ halts in less than } |x|^2 \text{ steps} \\}$

So for proving I need to construct a TM $U$ if it accepts $L$, so $L$ is decidable, otherwise not.

My steps are:

$U$ = "On input $ \langle M, x\rangle$:

1. $i:=1$;

$n := |x|^2$
2. Simulate one step of $M$ on $w$.
3. If $M$ accepted $w$ then $U$ accepts.

If $M$ rejected $w$ then $U$ rejects.

If $i ≥ n$ then $U$ rejects.
4. Else $i:=i+1$; goto step 2."

Because $U$ is a decider machine, $L$ is a decidable language.

Is this solution correct? Or I should do it in another way?

# Answer
If you want to prove that a language is decidable, it is sufficient to construct a Turing Machine that accepts if the input is in the language. It MUST reject if the input is not in the language.

Additionally, you are required to argue/prove that the Turing Machine constructed does that. Here's a hint: M must just halt on x, for it to be in L. Consider all possibilities of halting.
> 0 votes

---
Tags: formal-languages, turing-machines
---


title: Count the unique subsequences

text:
# Question
Title: Count the unique subsequences
I'm trying to count the number of subsequences of a long string.

e.g. BANANA -\> B, A, N, BA, BN, AA, NN, NA, BAN, BAA, BNA, BNN, ANA, AAA, NAN, NNA, etc

There's the horribly inefficient way, which is to iterate all of the substrings and keep hash of some sort to keep track of the ones already seen. The size of the hash explodes with any non-trivial length strings, so I need to figure out something more efficient. I tried dynamic programming, but could not find a good recursive formula.

This problem is originally from http://ahslaaks.users.cs.helsinki.fi/oh/, and they don't use the term "subsequences" when describing it.

# Answer
> 1 votes
Let the given string be $S$. For a string $T$ that appears as a subsequence of $S$, we say that the list of positions $(x\_1, \dots, x\_{|T|})$ is an *appearance of $T$ in $S$* if $S\[x\_1\]S\[x\_2\]\dots S\[x\_{|T|}\] = T$. The *leftmost appearance of $T$ in $S$* is the unique one for which each position is minimal over corresponding positions in all appearances -- that is, $X$ is the leftmost appearance of $T$ in $S$ iff for all $1 \le i \le |T|$ and all appearances $Y$ of $T$ in $S$, $X\[i\] \le Y\[i\]$. This leftmost appearance can be calculated with a simple greedy algorithm in which we loop through the characters of $T$, pairing each with the next available matching character in $S$. Define $L(T)$ to be the last (rightmost) position in the leftmost appearance of $T$ in $S$.

Example: $S = abbaba$, $T = ba$. The appearances of $T$ in $S$ are $(2, 4), (2, 6), (3, 4), (3, 6)$ and $(5, 6)$. The unique leftmost appearance is $(2, 4)$, so $L(T) = 4$.

We say a subsequence $T$ of $S$ *requires* position $i$ of $S$ iff $L(T) = i$. What this means is that $T$ is not a subsequence of $S\[1 \dots i-1\]$ -- the only ways to produce $T$ from $S$ involve including either the character at position $i$ in $S$, or some identical character further to the right. **The important thing to notice is that any subsequence $T$ of $S$ requires a *unique* position: the one given by by $L(T)$.** So if for each $1 \le i \le |S|$ we can count the number of subsequences of $T$ that require $i$, we can add these all up to obtain the total number of unique subsequences of $S$.

Let $r(i)$ be the number of subsequences of $S$ that require position $i$. We can compute $r(i)$ by counting the total number of subsequences of $S$ that include position $i$ and end there, and then subtracting off the number of these subsequences that don't require $i$. Calculating the number of subsequences that end at $i$ but don't require it is surprisingly easy to do, thanks to the following observation:

* For every $1 \le j \< i$ such that $S\[j\] = S\[i\]$, every subsequence that requires $j$ can be turned into an appearance of the same subsequence that ends at $i$ but doesn't require $i$ -- and there are no other subsequences that end at $i$ but don't require it. (Specifically, we could remove the final character (taken from position $j$ of $S$) and append position $i$, and the appearance formed this way yields the same subsequence.)

So we have $r(i) = \sum\_{1\le k\<i} r(k) - \sum\_{1\le j\<i, S\[j\]=S\[i\]} r(j)$.

(The first summation is the number of subsequences we get by appending $S\[i\]$ to each of the unique subsequences we have already seen; the second subtracts off subsequences we have seen before.)

The first summation is easy to optimise: It's just a running total. The second summation can also be optimised further by tracking, for each distinct character, the sum so far of unique subsequences ending with that character:

* $r(0) \gets 1, t \gets 1, u\[x\] \gets 0$ for each character $x$ appearing in $S$
* For $i$ from 1 to $|S|$:
    + $r(i) \gets t - u\[S\[i\]\]$
    + $t \gets t + r(i)$
    + $u\[S\[i\]\] \gets u\[S\[i\]\] + r(i)$

Summing $r(i)$ values into $t$ as they are computed allows the answer to be computed in linear time.

# Answer
> 0 votes
One approach is to build a NFA (nondeterministic finite automaton) that describes all subsequences of the long string, then determinize it. Once you have a DFA, you can count the number of strings it accepts (see Why isn't it simple to count the number of words in a regular language? and https://cstheory.stackexchange.com/q/8200/5038).

Whether this is effective depends on how large the resulting DFA turns out to be.

---
Tags: algorithms, strings, subsequences
---


# Question
Title: Why is DTIME(n) not equal to NP, and consequently, DSPACE(n) not equal to NP?
Intuitively it would seem like these equalities are false since DTIME(n) and DSPACE(N) are in terms of deterministic Turing machines and NP is non-deterministic, but I'm struggling to come up with a convicing argument as to why this is. I'm assuming that both the Time and Space Hierarchy Thoerems must be used but I'm just not quite sure how. I'm hoping someone can lead me in the right direction.

# Answer
> 2 votes
$DTIME(n^2) \subseteq \mathcal{P} \subseteq \mathcal{NP}$ and by the Time Hierarchy Theorem $DTIME(n^2) \nsubseteq DTIME(n)$ Therefore $\mathcal{NP} \neq DTIME(n)$

---
Tags: time-complexity, np, space-complexity
---


# Question
Title: The language of non-extendable strings of a regular language is regular
I recently came across this question in my textbook.

> $ \text{Let } L \text{ be a language over an alphabet } \Sigma \text{ that is accepted by some FSA.} $ $ \text{Prove that the language is also accepted by some FSA.} $ $ \operatorname{Max}(L) = \\{x \in L : \forall y \in \Sigma^\* - \\{ \lambda \\}.\ xy \notin L \\}.$

Where $ \lambda $ is the empty string in this case.

It seems that any regular language that *has* any maximal length string must not contain any repetition operators $"{^\*}"$. Hence the regular language only consists of characters, concatenation, and alternation. That means the FSA it generates cannot contain any cycles that contain a final state.

From the above, I decided to go with cases, where the language is generated by a regular expression that contains repetition or does not.

If the regular expression contains repetition, then the FSA that accepts the new language contains only one state, the starting state, and no final states.

If the regular expression does not contain repetition, then the FSA that accepts the new language is a copy of the original FSA with the final states restricted to the final states that were the largest number of edges away from the starting state of all the final states. That means only the longest strings that were accepted will be accepted.

This description intuitively makes sense, however, I cannot see how I might begin to prove any part of this, and I do not even know if this description is fully accurate. Is this description accurate and is there an easier way? If this description is accurate, how would I go about proving it?

# Answer
The definition does not ask for a maximal length string in $L$ but it looks for the strings that cannot be extended into a longer string in the language: $x\in L$, but *no* $xy \in L$ for nonempty $y$.

This means that repetitions are no problem. For $L = a^\*b$ in fact $\mathrm{Max}(L) = L$ as no string can be extended to a longer string in $L$. But for $L = ba^\*$ we have $\mathrm{Max}(L) = \varnothing$,as every string can be extended.

If you start with a (deterministic!) FSA, you can easily see which strings can be extended, and which not. How?
> 3 votes

# Answer
Recall that for languages $A,B$ over the same alphabet $\Sigma$, their quotient $A/B$ is given by $$ A/B = \\{ w \in \Sigma^\* : wx \in A \text{ for some } x \in B \\}. $$ It is not hard to check that $$ \mathrm{Max}(L) = L \setminus (L/\Sigma^+). $$ Since $\Sigma^+$ is regular and the regular languages are closed under quotient and set difference, we see that if $L$ is regular then so is $\mathrm{Max}(L)$.

As Hendrik Jan mentions, it is in fact easy to transform a DFA for $L$ into one for $\mathrm{Max}(L)$ with the same states, by modifying the set of accepting states (exercise). This shows the stronger property that $\mathrm{index}(\mathrm{Max}(L)) \leq \mathrm{index}(L)$, where the index of a language is the number of equivalence classes in the Myhill-Nerode relation.
> 2 votes

---
Tags: regular-languages, automata, finite-automata
---


# Question
Title: Proving that $\{0^i10^i : i \ge 1\}$ is non-regular, using only closure results
I have been stumped on the following question for a few hours now, I feel like I am missing some "aha" moment.

> $\text{Suppose that } \\{ a^nb^n : n \ge 1 \\} \text{ is non-regular.}$ $\text{Prove using closure results that } \\{ 0^i10^i : i \ge 1 \\} \text{ is non-regular.}$

Starting off I assumed for contradiction that the language is regular. Then I took countlessly many compliments and intersections and homomorphisms, none leading me anywhere close.

I understand using Pumping Lemma would quickly solve this problem, but the question restricts the proof technique to not using Pumping Lemma.

How would one go about solving such a question with the given restraints? Is there a methodology as to find the correct closure results to use or is it mostly intuition and luck?

# Answer
> 4 votes
I would say that luck and intuition are improved by experience :)

The trick is also to use inverse morphisms! They can perform nondeterministic letter substitutions.

A related example. Consider the morphism $h: \\{a,b\\}^\*\to \\{0\\}^\*$ with $h(a) = h(b) = 0$, then $h^{-1}$ maps a word $0^n$ to any string $w\in\\{a,b\\}^\*$ with length $n$.

Background. It is easy to write a FSA with output that maps strings $0^i10^j$ to strings $a^ib^j$, and regular languages are closed under finite state transductions (input-output transformation by two-tape finite state automaton). If you are not familiar with this result, by Nivat's Theorem: any finite state transduction can be written as a composition of an inverse morphism, intersection with regular language, and a morphism.

---
Tags: regular-languages, closure-properties
---


title: Complexity of numerical operations

text:
# Question
Title: Complexity of numerical operations
I have written a program which contains a while loop: `while k < sqrt(n)`, so clearly my program evaluates $\sqrt{n}$ at each iteration of the while loop. (Note that $n$ and $k$ can both change throughout the loop, although I do not think that this is relevant to the question.)

I am required to calculate the number of arithmetic operations used by my program in terms of the initial value of $n$ (in terms of the number $n$, not the number of digits of $n$) when it is run, where an arithmetic operation is defined as the addition, subtraction, multiplication or division of any two numbers.

My question is, how many arithmetic operations does $\sqrt{n}$ use? Is it a fixed amount or does it change with $n$ (and if so to what extent)?

# Answer
> 1 votes
If you have a look at this wikipedia page then you will see that there are over tens of algorithms for calculating the square root of a number.

Let's consider the Babylonian method for calculating square roots. This is very similar to Newton's iterative method for finding roots and therefore an approximation algorithm. The pseudocode is as follows:

```
1. Start with an arbitrary positive start value x.
The closer this value is to the actual root, the better the convergence is.

2. Initialize y = 1.
This variable will hold the value for the previous iteration of the root.

3. Initialize e = some arbitrary small value.
This will determine the accuracy of our root.

4. Do following until (x - y) > e :
  a) Set y = (n/x)
  a) Set x = (y + x) / 2

```

This answer gives a good look into how the running time complexity of the above method can be obtained. The TLDR version is $O(log(log(n))$ for $\sqrt(n)$.

A small thing to note is that if n can change throughout the loop, then the square root will be calculated every time the loop is run. However if n does not change at all, it is treated as a loop invariant and the compiler takes steps to optimize the performance internally. In short, the calculation of the square root is taken outside the loop body.

Finally, since there are multiple algorithms for calculating the root of a number there is no single solution to the question:

> how many arithmetic operations does (√n) use?

As for the second question, ie:

> Is it a fixed amount or does it change with n (and if so to what extent)?

You can clearly see that its not a fixed amount, and the number of operations depend on the value of n itself, the initial root chosen and the level of accuracy preferred.

Some related additional reading for iterative algorithms: Gradient Descent.

---
Tags: algorithms, complexity-theory, arithmetic
---


# Question
Title: Why do we try to maximize Lagrangian in SVMs?
I was learning about support vector machines from MIT OpenCourseWare. I figured it out. I understand why we try to minimize $\frac{1}{2} w^2$. I just did not get why we try to maximize Lagrange expression like said at 35:56 in the YouTube video.

Margin (width) of the support vector is $2/\\|w\\|$. We want to maximize width it means that we also want to minimize $\\|w\\|$ from the equation $2/\\|w\\|$. It is true that we also want to minimize $\frac{1}{2}\\|w\\|^2$. Now we use Lagrange expression here, $$L = \frac{1}{2}\\|w\\|^2 + \sum\_i α\_i(y\_i(w \bullet x+b)-1).$$ To find the minimum of $\frac{1}{2}\\|w\\|^2$, we apply gradient; $∇L = 0$. From the $∇L = 0$ equation, we get $Σ\_iα\_iy\_i = 0$ and $w = Σ\_iαi\_iy\_ix\_i$. Then by using $Σ\_iα\_iy\_i = 0$ and $w = Σ\_iα\_iy\_ix\_i$ equations and putting this in the Lagrange expression we end up with $$L(w,b,α) = \sum\_iα\_i-\frac{1}{2}\sum\_{i,j}y\_iy\_jα\_iα\_j(x\_i\bullet x\_j).$$

I really understand up to here, but the professor said that we want to maximize $L$ here, why? I really don't understand. Why are we trying to maximize the Lagrange expression? I thought we were trying to minimize it.

# Answer
I think the answer to this deals with convex functions and duality.

$$L(w, b, \alpha) = \frac{1}{2}\\|w\\|^2 + \sum\_i α\_i(y\_i(w \bullet x+b)-1).$$

When you minimize this, you are minimizing it over $w,b$. As you stated, this will produce the Lagrangian dual function:

$\Theta (\alpha) = inf L(w, b, \alpha) = \sum\_iα\_i-\frac{1}{2}\sum\_{i,j}y\_iy\_jα\_iα\_j(x\_i\bullet x\_j)$

The maximization must be done here, but of the function $\Theta (\alpha)$ (the Lagrangian dual function).

Here is some background on why we are maximizing:

1) Let $p\*$ be the optimal value of the problem of minimizing $\frac{1}{2}\\|w\\|^2$ (the primal). The Lagrangian dual function has the property that $L(w, b, \alpha) \leq p\*$. It is a lower bound on the primal function. Instead of solving the primal problem, we are want to get the maximum lower bound on $p\*$ by maximizing the Lagrangian dual function (the dual problem).

2) The primal problem is a convex function. The Lagrangian dual function is a concave function(can be verified). Maximizing a concave function is equivalent to minimizing a convex function. Therefore it is easy.

3) Why maximizing $\Theta (\alpha)$ is as good as minimizing $\frac{1}{2}\\|w\\|^2$: Let $d\*$ be the value of $max \Theta (\alpha)$. This primal convex optimization problem satisfies Slater's constraint qualification which gives us strong duality ($d\*=p\*$). Therefore, $max \Theta (\alpha)$ is the same as $min \frac{1}{2}\\|w\\|^2$.
> 4 votes

# Answer
I cannot visit YouTube here, maybe you should show the expression.
Anyway, this Lagrange expression is the dual problem of origin expression. Minimizing it will more easy than minimizing the original expression.There is a good algorithm call SMO, which can maximize this Lagrange expression effectively.

---

Well, I refered to my book, found that the dual problem of the original one is
$$\text{max}(\alpha)\text{min}(w, b)L(w,b,\alpha)$$ while $max()$ and $min()$ mean that $argmax \alpha$ and $argmin (w, b)$ . The original expression is $$0.5\times|w|^2-\sum\_{i}α\_iy\_i(w\times x\_i+b)+\sum\_iα\_i$$ As you say we make $∇L = 0$ and we get $$∇(w)L(w,b,\alpha) = w-\sum\_i\alpha\_iy\_ix\_i = 0$$ and $$∇(b)L(w,b,\alpha) = \sum\_i\alpha\_iy\_i = 0$$ so $$L(w,b,\alpha)$$ turns to be $$L(w,b,\alpha) = -0.5\*\sum\_{i}\sum\_{j}\alpha\_i\alpha\_j\times y\_i\times y\_j\times K(x\_i, x\_j)+\sum\_i\alpha\_i$ while $K(x\_i, x\_j)$$ is Kernel Function. yes next we should minimize $$L(w,b,\alpha)$ as $min(w, b) L(w,b,\alpha)= -0.5\times \sum\_i\sum\_j\alpha\_i\alpha\_j\times y\_i\times y\_j\times K(x\_i, x\_j)+\sum\_i\alpha\_i$$ (you see, there is no $w$ and $b$ in this expression at all, so the minimize will be itself).
So at the end we get the final dual problem $$max(\alpha) -0.5\times\sum\_i\sum\_j\alpha\_i\alpha\_j\times y\_i\times y\_j\times K(x\_i, x\_j)+\sum\_i\alpha\_i$$ with s.t $$\sum\_i\alpha\_i\times y\_i = 0$$, $\alpha\_i \geq 0$ for $i = 1$ to $N$

---

I dont know how to prove that $max(\alpha)min(w, b)L(w,b,\alpha)$ is true, after all i don't have a major in mathematics, but it is true that if an original problem is a minimization problem, then its dual one is a maximization problem and vice versa. Maybe you could ask for proof from your professor.
> 0 votes

# Answer
There's a typo in your first equation. It should have a minus in front of the term with $\alpha$s:

$$L = \frac{1}{2}\\|w\\|^2 - \sum\_i α\_i(y\_i(w \bullet x+b)-1).$$

It's understandable where your confusion comes from. Like you say, you do indeed wish to minimise $L(w,b,\alpha)$ with respect to $w,b$.

But because there is a minus sign in front of the $\alpha$s, this is equivalent to maximising with respect to $\alpha$.

And this doesn't change in your second equation, where the $w,b$ terms have been eliminated.
> 0 votes

---
Tags: optimization, machine-learning, os-kernel, svm
---


title: Infix search in millions of strings

text:
# Question
Title: Infix search in millions of strings
Let's say we have millions of strings (each of them \< 100 characters):

```
alpha
allo
blah
hello world
orlando
...

```

I know how a binary search tree or a trie can help to do "prefix search" (example: find all strings that match `al*`, i.e. beginning with `al`).

**Which data structure / algorithm could be used to search patterns *inside* a word** (i.e. not necessarily at the beginning or end), that wouldn't need to do an inefficient O(n) traversal of all the millions of strings?

Example: the pattern `orl` should match "hello world" as well as "orlando"

Notes:

* is that called "infix search"?
* I'm looking for something working on strings even without meaning (the pattern `qys` should allow to find the string `uyiuqysidi` among millions of other strings), on DNA (pattern `ATTG` found in `GGATCATTGAAGG`), on sequences (subsequence `1, 4, 8` found in sequence `7, 2, 1, 4, 8, 19, 32`), etc.

# Answer
> 3 votes
Let $\\$$ be a symbol not in the alphabet, and let $\\{ w\_i \\}\_{i \in \mathbb{N}}$ be the strings you are searching from. Construct the string $S = w\_1 \circ \\$ \circ w\_2 \circ \\$ \circ \dots \circ w\_n$ and use Ukkonen's algorithm to construct a suffix tree for $S$. You are now able to retrieve all $m$ occurrences of a pattern $P$ in time $\Theta(m + |P|)$, with $\sum\_i|w\_i|$ preprocessing time.

# Answer
> 0 votes
Depending on the characteristics of the strings, it might be useful to separate the strings to be searched into equivalence classes in some way. For example, generate a bitmap of characters contained somewhere in the string, so each string in the searchable set would get a 26 bit classification. The actual search would only search strings with matching classifications.

---
Tags: data-structures, trees, search-algorithms, search-trees
---


# Question
Title: What algorithm can I use for a rule based system?
I'm doing research for a system that is based on rules. The goal of the system is to fire when some of the rules are true.

Explanation (requirements/working of the algorithm):
The algorithm will run in the background of an app. There will be a lot of data available about the user. The algorithm will apply the defined Business Rules to the data. When an X amount of the rules result in true, the algorithm should fire. The goal of the algorithm is to fire when the user shows any possible problems (based on data / the business rules that result in true).

Examples of Business Rules:

> IF a user is in the app between 2-5AM more than 5 times in 2 weeks THEN the user is not sleeping at the correct times.
> IF a user moved house twice THEN a user moves house a lot

The Business Rules are in the `If condition(s) then action` format. The condition can be of any type. It would be really nice if it will be "easy" to add new forms of conditions in the future and the algorithm can handle such changes.

I'm looking for an algorithm that can be of use for the goal described above. Preferably without the use of Machine Learning. So I'm looking for an up-to-date/newer version of an Expert System.

When I did research, almost every time I came back to an Expert System. I think it perfectly fits my requirements. However I can't find anything recent on Expert Systems. It looks like it is outdated, as mentioned in this post, four years ago.

I saw something like an Recommendation System in this post. Still I don't think this will solve my problem because it focuses on recommendations...

Does anyone else have ideas for an algorithm?

**EDIT**: Tried to add useful information

# Answer
You don't need an algorithm. Since you already have a set of rules, all you need to do is implement the rules.

---

The simplest implementation strategy is to simply re-evaluate all the rules each time something changes. However, in some cases this might repeat work unnecessarily and there might be more efficient implement the rules.

For instance, if one of your rules is "IF the user has bought more than 1000 items today THEN sound an alarm", then re-evaluating this each time an item is bought might be unnecessarily inefficient. A more efficient approach would be to keep a counter for each user that keeps track of how many items the user has bought today; each time an item is bought, increment the counter and sound an alarm if it is over 1000; and each midnight, reset all counters to zero.

So in some cases optimizations might be possible. However, that is entirely depend on the specific of the rule, and there's not much we can say in general. If you have a question about how to implement a specific rule efficiently, you can ask a new question specifically about that particular rule.
> 1 votes

---
Tags: algorithms, expert-systems
---


# Question
Title: Full circularity vs strong circularity for attribute grammars
Attributes of an attribute grammar can have a circular dependency. In my compiler construction course I learned, that there are two types of circularity for attribute grammars:

* full circularity can be checked in exponential time
* strong circularity can be checked in polynomial time

Full circularity implies strong circularity, but not vice versa, so if there is an attribute grammar that is strong circular, it might still not be full circular. Thus, if I reject all strong circular attribute grammars, I might reject some grammars even though they are not full circular. I tried to come up with a dividing example to better understand this case, that is an attribute grammar that is strong circular but not full circular, but with no luck yet.

### Question

* Is there a dividing example that makes the difference clear?
* Are there well known real-world attribute grammars that are strong circular but not full circular?
* Would it be a real limitation for a tool to accept only strong non-circular grammars?

---

I assume the terms strong circularity and full circularity are well known. If they are not you can find the lecture notes here (lecture 12, 13 and 14).

# Answer
> 4 votes
You are using the terms in a weird way. A grammar can be circular or non-circular. Since FULLY testing this property is EXPTIME, one wants a simpler (easier to test) property. This is where strong NON-circularity comes in. In strong non-circularity, you basically combine the dependencies of all possible sub-trees, even for combinations that can't appear together. So if a grammar is strong non-circular, it particularly rules out the combinations that CAN happen together. I.e. the grammar is non-circular.

So this means that strong NON-circularity implies NON-circularity. Sure you can invert implications by negating both sides of it. I think this is what you did when you say that "Full circularity implies strong circularity". But I don't think it makes sense to call a grammar that is **NOT strongly NON-circular** "strong circular". IMHO that would be a confusing term, because it sounds like such a grammar was "even more circular" than other grammars, but it is the opposite - it only fails the strong-non-circularity test which isn't a necessary condition. So such a grammar would rather be "less circular" than other grammars, because it "looks circular" without necessarily being circular. But that doesn't sound right either (because in the end, it is either circular or not). If anything, I would call it "weakly circular", because that property doesn't guarantee anything - to be certain, you still need to apply the full circularity test.

To adress the question: in practice you usually only work with S-Attribute Grammars, which don't even need to be tested for circularity, because they can't be circular.

I dug out this example (attributes starting with i are inherit attributes, attributes starting with s are synthetic ones):

```
S -> A
    ix.1 = 1        (1)
    iy.1 = 2        (2)
    sx.0 = sz.1     (3)
A -> A a
    ix.1 = sy.1     (4)
    iy.1 = ix.0     (5)
    sy.0 = sz.1     (6)
    sz.0 = 0        (7)
A -> a
    sy.0 = 0        (8)
    sz.0 = ix.0     (9)
A -> b
    sy.0 = iy.0     (10)
    sz.0 = 0        (11)

```

this grammar is non-circular, but it fails the strong-non-circularity test, because in the strong-non-circularity test, you take the **union** of the dependency-sets for the productions of the same nonterminal. So you have the edges for both `A->a` and `A->b` together, although they can't appear together (because you can't apply both productions at the same time).

The production of `A -> A a` then yields the following dependency-graph: let Q and R be the prefixes for the two A's in the production, then you have the nodes

```
{ Qia, Qib, Qsb, Qsc, Ria, Rib, Rsb, Rsc }

```

and the edges

```
{ (Qsb, Qia),     from (4)
  (Qia, Rib),     from (5)
  (Rib, Rsb),     from (10)
  (Rsb, Ria),     from (4)
  (Ria, Rsc),     from (9)
  (Rsc, Qsb)      from (6)
}

```

this is a cycle and therefore the strong-non-circularity test fails. The point why the strong-non-circularity test is wrong here, is because the edges `(Rib, Rsb)` and `(Ria, Rsc)` come from different productions.

---
Tags: formal-languages, formal-grammars, compilers, attribute-grammars
---


title: Is it known that $AC^1 \subseteq L$?

text:
# Question
Title: Is it known that $AC^1 \subseteq L$?
A good exercise is to show $NC^1 \subseteq L$. (According to the complexity zoo page this was first shown by Borodin, 1977.) Although the details must be checked, the proof is simple: take the $NC^1$ circuit and do depth-first-search on the output gate of the circuit. Recursively evaluating the gates in the circuit works because the depth of recursion never goes beyond the depth of the circuit, which is $\log n$.

My question: doesn't the same argument show that $AC^1 \subseteq L$? In this case, with unbounded fan-in, we have to modify the argument slightly, to make sure we are only storing, at each gate, a pointer to the current input gate we are recursing on, and the result (AND or OR) of all input gates up to this point. But it should still be $\log n$.

There must be something wrong with this argument, since I don't see $AC^1 \subseteq L$ referenced anywhere, and the Complexity Zoology inclusion diagram does not list $AC^1$ as a subset of $L$ :( So, what is the error in my thinking?

# Answer
Matrix powering shows that directed reachability is in $\mathsf{AC^1}$, and so $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{AC^1}$. In more detail, suppose that $A$ is the adjacency matrix of a directed graph $G$, with self-loops on all vertices. The matrix $B\_{ij} = \bigvee\_k A\_{ik} \land A\_{kj}$, which can be computed in $\mathsf{AC^0}$, is the adjacency matrix of $G^2$. In other words, $B\_{ij} = 1$ iff there is a path of length at most 2 from $i$ to $j$ in $G$. Iterating this construction $\log n$ times, we obtain an $\mathsf{AC^1}$ circuit computing the adjacency matrix of $G$, that is, which vertex is reachable from which vertex.

---

What goes wrong when using DFS to evaluate $\mathsf{AC^1}$ circuits? The same approach works, only it uses $\log^2 n$ space rather than $\log n$ space. The reason is that at each level, you need $\log n$ space to store which child you are currently in. Multiplied by the number of levels, we obtain $\log^2 n$.
> 4 votes

---
Tags: complexity-theory, complexity-classes, space-complexity, circuits
---


# Question
Title: What defines the interaction between CPU, Memory and I/O parts?
From Wikipedia:

> In computer engineering, microarchitecture, also called computer organization and sometimes abbreviated as µarch or uarch, is the way a given instruction set architecture (ISA), is implemented in a particular processor.
>
> Computer architecture is the combination of microarchitecture and instruction set.

I kept reading some Q&A like this. Definition says that computer microarchitecture is how ISA is implemented in a processor, but tells nothing about how CPU, memory and I/O interact with each other. Does architecture defines this interaction? For example, which term defines this picture?

# Answer
A microarchitecture is a high-level description (in contrast to a hardware-description or circuit-level) of an implementation of an ISA. This includes how instruction bytes get fetched, how many decorders there are and what instructions each can decode, how many functional units there are and for which instructions, the cache hierarchy, how all of these units are connected to each other, and it may also include the number of cores or hardware threads and how they interact with each other and what resources are shared between them.

Main memory and I/O devices are not part of the microarchitecture, but the microarchitecture description includes how it interfaces with components of the system. The term *architecture* is used to either refer to only an ISA or to both an ISA and a microarchitecture that implements it, depending on the context. Therefore, it also specifies how to communicate with memory and I/O devices, but only in terms of instructions and addresses. You can use the term *computer* or *computer system* to refer to the image you've attached. The term *CPU* may refer to either a single core, a multi-core processor design, or a physical processor package (which may include the DMA and interrupt controllers shown in the image).
> 3 votes

---
Tags: computer-architecture
---


title: Efficient traffic allocation

text:
# Question
Title: Efficient traffic allocation
Users can be assigned to one experiment on my site. I have an API that developers use to trigger logic for each experiment. They call ExperimentEngine.run() to trigger the code logic for the experiment.

I would like to allocate users to each experiment, at the point where a user might be exposed to the logic for that experiment. I would like to assign users to experiments such that experiments implemented downstream (on pages that are usually seen last) still get users assigned to them.

For example, if user A is runs into the code logic for experiment A at login and then goes to page B and runs into experiment B, the user A could be assigned to either experiment A or B. That means that they will only see one of the experiments and not both (either A or B) or neither. I would like to figure out the right algorithm so that experiment B (which is downstream and shown to the user after they've seen experiment A) gets users assigned to it. I don't to assign all users to experiment A.

So the flow is as follow

* User visits page A where experiment A is implemented
* We decide whether to assign users to experiment A. If user is assigned to A, user will be able to see experiment A.
* User visits page B where experiment B is implemented, we decide whether to assign users to experiment B
* Users can only see experiments that they are assigned to.
* I want to come up with an algorithm that allows me to assign users to experiments regardless of where on the site they are implemented so that the traffic distribution is efficient and experiments implemented downstream get enough users.

Can someone please point me in the right direction to an algorithm that allows me to do the above?

Each experiment is given X number of people needed per day to reach stats sig. We could factor that into the algorithm to make sure that we assign users to experiments in a way that experiments reach their sample size in two weeks.

A possible algorithm:

* For each experiment, we make a decision of whether to assign based on the experiment's location using coin flip.
* If we get heads, a list of experiments that are implemented for that location are selected.
* An experiment is chosen from that list based on priority system. At every location, a % of users are assigned to one of the experiments implemented at that location.
* When we decide to assign or not to assign to any experiments at that location, that decision is not made again for the user.

The Question: How do I assign users to one experiment at a time so that experiments that they might see last get enough users? Only users assigned to experiments can see them.

# Answer
> 1 votes
I suggest you try a simple solution: randomly decide whether to assign users to an experiment when they visit the corresponding page.

Suppose you want to have 100 users to a particular experiment, call it experiment E. When a user visits the page for experiment E, if that user hasn't been previously assigned to any experiment, flip a biased coin and assign the user to experiment E if that coin comes up heads. How do you decide what the probability of heads should be? If historically you see 2000 visitors per two-week period, and you want 100 users, then the heads probability should be about 1/20. Then after two weeks you should get about the desired number of users.

This assumes you have historical data on the number of visitors to each page, to set the probability appropriately. If you don't have historical data, there are some alternative strategies you could use. For instance, if you want 100 users for experiment E, you could randomly pick 100 different times throughout the two-week period; for each selected time, take the next unassigned user who visits that page (the first one who visits the page after that time) and assign them to experiment E. In this way you are randomly selecting 100 different users.

These techniques treat each experiment independently, which simplifies the assignment process. This is simple and I suspect it might work well enough for running experiments in practice. Only consider something more complicated if you have evidence that this won't work. (How can you tell whether it will work? You could take your historical data and simulate the strategy on historical data and see if it gets you enough users for each experiment.)

---
Tags: algorithms, greedy-algorithms, assignment-problem, experimental-analysis
---


# Question
Title: Advantages (from a mathematical perspective) of representing data as symmetric matrices
From Wikipedia, a **symmetric matrix** is a square matrix that is equal to its transpose. An example of this (I think) is an adjacency matrix with undirected edges, which is a square matrix representing links between elements (undirected in this case).

The thing is, the data is duplicated in this case (looking at it from a computer science perspective). The two halves of the diagonal carry the same information, so you can just use one half of it.

I am new to matrices, so I apologize if this is a basic question. The question is if there is any advantage mathematically or from a computer science perspective to representing data (such as graphs, but more generically any data such as key/value pairs or pointers, etc.) using **symmetric matrices** like this. Wondering if it (for example) makes lookup O(1) in certain cases, or it provides some other significant hidden benefit because of the symmetry.

# Answer
> 1 votes
The main advantages of matrices are in solving linear equations. In fact judging whether there even exists solutions to a system of equations becomes very easy when you represent equations in form of matrices. Matrices form the core of Linear Algebra.

Systems of linear equations pop up everywhere in the real world. Linear Algebra is integral to Machine Learning, Image processing, Computer Graphics, Operations Research.....( the list is inexhaustible).

Using matrices as representation of graphs is in fact one of the less useful facets of Linear Algebra (due to the more space efficient Adjacency List data structures). If we talk about using matrices as datastructures you can look into Bottom Up approach of solving dynamic programming problems.

**Importance of Symmetric Matrices**

If we have a symmetric matrix, then we immediately know a few things about the concerned system of linear equations:

* If each vector is linearly independent, then we have as many pivots as we have rows or columns.
* This is a special case where we say that the matrix has a full rank. Hence the matrix is invertible, and there exists a particular unique solution to this system of linear equations.
* Eigen Values are defined for square matrices.
* This allows us to investigate whether a given matrix is diagonalizable. If the matrix is diagonalizable, then it allows us to perform efficient computations of the powers of A, leading into matrix exponentials.
* Diagonalization is a very common mathematical operation in quantum mechanics. The time-independent Schrödinger equation is broadly speaking, an eigenvalue equation.

Since matrices are nothing but representations of linear equations, we cannot force ourselves to represent data symmetrically (actually we can, and often do). If a particular dataset that we are investigating has the same number of vectors as its attributes (which is definitely coincidental) then we can perform an extended analysis on the dataset owing to the properties of the square matrix.

# Answer
> 0 votes
I will assume that you are talking about real matrices.

> Theorem: Let $T$ be a linear operator on a finite-dimensional real inner product space $V$. Then $T$ is self-adjoint iff there exists an orthonormal basis $\beta$ for $V$ consisting of eigenvectors of T.

And for your information, an operator on a inner product space whose dimension is $n$ can be written as a matrix based on the selection of basis.

Therefore, if we can represents a matrix $M$ in a symmetric form (self-adjoint is in some ways equivalent to symmetric when $F = R$), then this matrix can be diagonalized, which is a nice form for computation, e.g., do "power of the matrix".

But how do we apply the rapid version of "power of the matrix" to computer science? Well, consider the computer graphic area. We know that apply an matrix to a vector can be seen as a linear transformation to something in your screen. With the diagonalized matrix, we can improve the graphic efficiency a lot.

---
Tags: matrices, adjacency-matrix
---


# Question
Title: How a range query works on a simple B+tree
Given a B+tree indexing scheme, wondering how a database actually goes and finds records matching a range query such as the following:

```
CREATE TABLE foo (
  x int,
  y int
)

SELECT * FROM foo
  WHERE x > 10 AND x < 100
    AND y > 20 AND y < 200

```

From my understanding this would require *2 b+trees*, one for each property ($x$ and $y$). Wondering if one could describe how it would go about about querying the different indexes to satisfy this query. I am having difficulty understanding how the B+tree works in practice.

# Answer
> 2 votes
This is up to the individual database system. There are multiple ways one might index the data and support this type of query.

One natural approach is that the system might compute in advance an index over the `x`-values (i.e., a B+ tree that is keyed by the `x` values) and a second index over the `y` values (i.e., a B+ tree that is keyed by the `y` values). Given those indices, you can now implement the search query by doing a range query on the first B+ tree to find all values where `x > 10 AND x < 100`, then iterate through them and keep the ones that also satisfy `y > 20 AND y < 200`.

It is also possible to build multi-dimensional data structures that support 2D range queries, but those are more complex and might not be used in a typical database system.

---
Tags: trees, database-theory
---


# Question
Title: Is the language of TMs running in polytime Turing-recognizable?
Any ideas for proving that $L=\\{\langle T \rangle : \text{ time complexity of $T$ is polynomial}\\}$ is not Turing-recognizable?

# Answer
Hint:

You can reduce the complement of halting problem to this language.

An instance $\langle M,w\rangle$ is reduced to a TM $M\_w$ that works as follows.

On input $x$:

1. Run $M$ on $w$.
2. If $M$ does not halt after $|x|$ steps, *accept*; otherwise, *go into an infinite loop*.

Now it remains for you to show the correctness of this reduction to complete the proof.
> 1 votes

---
Tags: turing-machines, computability
---


# Question
Title: How do I prove that a Turing Machine that accepts a string w in an even number of steps is not decidable?
Let a language **A = {(M,w) : M is a TM and w is a string such that w is accepted by M in an even number of steps}**.

How can I prove that this is undecidable? I have considered trying to build the ATM proof assuming this language. Language A can cover acceptance under even steps but how would I cover acceptance under uneven steps? Language A would reject in that case. How would you go about trying to build the proof via this path?

Another thing I wonder is if Rice's theorem covers this language. Would this be considered a functional property? Could I use it to prove the undecidability of this language?

Thanks

# Answer
This is a bit of a nit-picky question, since you really need to pay attention to the parity of the number of steps you TM does.

We'll show that the problem is undecidable by a reduction from $A\_{TM}$. There are many ways to construct such a reduction. In my opinion, the following is the least technical.

Given input $(M,w)$ for $A\_{TM}$, we will construct a new output $(M',\epsilon)$, such that $M$ accepts $w$ iff $M'$ accepts $\epsilon$ within an even number of steps.

We construct $M'$ as follows: given input $x$, if $x\neq \epsilon$, then $M'$ rejects.

Otherwise, if $x=\epsilon$, $M'$ works as follows: simulates the run of $M$ on $w$. If $M$ accepts, it clears the tape by going to the rightmost non-blank cell, and then writes blanks all the way to the left. It then simulates $M$ again, erases the tape again in *exactly the same manner*, and accepts.

If $M$ rejects, then $M'$ rejects as well.

The idea here is that if $M$ accepts $w$, then the operation of $M'$ on $\epsilon$ is to simulate $M$ on $w$ twice. Therefore, it will take an even number of steps.

Proving the correctness and computability of this procedure is not hard.
> 1 votes

# Answer
In short, if you could decide membership in the language $A$, then you could decide whether a Turing machine accepts a word. Because TM acceptance is undecidable, this proves that a decider for $A$ can't exist.

---

Here's a machine that uses a subroutine for $A$ in order to solve the acceptance problem. Given a machine and word $\langle M, w\rangle$, design a new machine $M^\prime$. The new machine is exactly the same as $M$, except that it has an extra step in the beginning where it does nothing. (e.g. $M^\prime$ has a new starting state $q\_0^\prime$. Initially, the machine reads the tape, prints nothing, doesn't move, and transitions into the start state $q\_0$ of $M$.)

Now, if $M$ rejects $w$ then so does $M^\prime$. Otherwise, they both accept $w$, and $M^\prime$ takes one more step than $M$— so one of the two machines takes an even number of steps to accept.

So, if we could decide whether a TM accepts a word in an even number of steps, we could decide whether $M$ accepts $w$. Just test $\langle M, w\rangle$ and $\langle M^\prime, w\rangle$ and return ACCEPT if either one takes an even number of steps to accept, or else return REJECT.

---

Rice's theorem doesn't apply because "accepting in an even number of steps" is not a property that languages have, but a property that specific Turing machines have. (Two Turing machines can have the same language, but one of them might belong to $A$ and the other one not.) Rice's theorem applies just to languages of the form

$$\\{\langle M\rangle : M\text{ is a TM and }L(M)\text{ has property }p \\}$$
> 0 votes

---
Tags: computability, turing-machines, undecidability
---


# Question
Title: What are the strongest known type systems for which inference is decidable?
It's well known that Hindley–Milner type inference (the simply-typed $\lambda$-calculus with polymorphism) has decidable type inference: you can reconstruct principle types for any programs without any annotations.

Adding Haskell-style typeclasses seem to preserve this decidability, but further additions makes inference without annotations undecidable (type families, GADTs, dependent-types, Rank-N types, System $\omega$, etc.)

I'm wondering: what is the strongest known type system with completely decidable inference? It's going to lie somewhere between Hindley–Milner (completely decidable) and dependent-types (completely undecidable). Are there aspects of DTs which can be added which preserve inference decidability? What research has been done to see how far this can be pushed?

I realize that there is not a single strongest system: that there are likely infinite small, incremental changes that can be added to HM keeping inference. But there are likely a few practical candidates of systems that have been discovered.

Edit: given that there is no "strongest" system, I will accept an answer that outlines the **notable** systems that extend Hindley–Milner with decidable inference. Examples could be Liquid Types, Rank-2, etc.

# Answer
> 7 votes
\[EDIT: Voilà a few words on each\]

There are several ways of extending HM type inference. My answer is based on many, more or less successful, attempts at implementing some of them. The first one I stumbled upon is *parametric polymorphism*. Type systems trying to extend HM in this direction tend toward System F and so require type annotations. Two notable extensions in this direction I came across are :

* HMF, it allows type inference for all System-F types, which means that you can have universal quantification "in the middle" of a type, their appearance is not implicitly situated at the highest scope like for HM polymorphic types. The paper clearly states that no clear rule exists as to how many and where type annotations may be needed. Also the types being those of System F, terms usually don't have a principal type.
* MLF is not only an extension of HM, it's also an extension of System F that regain the principal type property of HM by introducing a kind of bounded quantification over types. A comparison has been made by the authors, MLF is strictly more powerful than HMF and annotations are only required for parameters used polymorphically.

Another way of extending HM is through variation of the constraint domain.

* HM(X) is Hindley-Milner parameterised over a constraint domain X. In this approach, HM algorithm generates the constraints that are sent to a domain solver for X. For the usual HM, the domain solver is the unification procedure and the domain consists of the set of terms build from the types and the type variables.
Another example for X could be constraints expressed in the language of Presburger arithmetic ( in which case type inference / checking is decidable ) or in the language of Peano arithmetic ( no longer decidable ). X varies along a spectrum of theories, each with its own requirements regarding the amount and localisation of type annotations needed and ranging from not at all to all of them.
* Haskell's type classes are also a kind of extension of the constraint domain by adding type predicates of the form `MyClass(MyType)` ( meaning that there exists an instance of MyClass for the type MyType ).
Type classes preserve type inference because they are basically an (almost) orthogonal concepts they implements *adhoc polymorphism*.
As an example, take a symbol `val` of type `val :: MyClass a => a` for which you can have instances `MyClass A`, `MyClass B` etc. When you refer to that symbol in your code, it's actually because type inference is already performed that the compiler can infer which instance of the class to use. This means that the type of `val` depends on the context in which it is used. That's also why running a single `val` statements leads to an `ambiguous type error` : the compiler can't infer any type based on the context.

For more advanced type systems like GADTs, type families, Dependent types, System (F)ω, etc., type are not anymore "types" they become complex computational objects. For example it means that two types not looking the same are not necessarily different. So type equality becomes not trivial ( at all ).

To give you an example of the actual complexity let's consider the dependent type of list : `NList a n` where `a` is the type of objects in the list and `n` is its length.
The append function would have type `append :: NList a n -> NList a m -> NList a (n + m)` and the zip function would be `zip :: NList a n -> NList b n -> NList (a, b) n`.
Imagine now we have the lambda `\a: NList t n, b: NList t m -> zip (append a b) (append b a)`. Here the first argument of zip is of type `NList t (n + m)` and the second of type `NList t (m + n)`.
Almost the same, but unless the type checker knows that "+" commutes on natural numbers, it must reject the function because (n + m) is not literally (m + n). It's no longer about type inference / type checking, it's about theorem proving.

Liquid types seem to be doing some dependent type inference. But as I understand it, it's not really dependent type, more something like usual HM types on which additional inference is made to compute static bounds.

I hope this helps.

---
Tags: undecidability, type-theory, type-inference, dependent-types
---


# Question
Title: Discrepancy between process execution time and CPU speed (lost cycles)
I'm not sure if this is on topic, but I've seen some hardware related questions here so I'll post it here anyway. If it's off topic I'll take it off.

Compile this C code:

```
int main() {
  unsigned long long int i;
  for (i = 0; i < 30000000000ull; ++i){}
  return 0;
}

```

with `gcc cycleTimer.c`. Then run `/usr/bin/time -f "%E %P" ./a.out`.

I get the following output:

```
1:17.04 99%

```

Meaning the process takes 77 seconds to complete and uses 99% of a CPUs time. Running `cpufreq-info` during the process gives

```
current CPU frequency is 2.30 GHz

```

for all four cores. Now create the assembly instructions for `cycleTimer.c` with `gcc cycleTimer.c -S`, and we get the following assembly code:

```
        .file   "cycleTimer.c"
        .text
        .globl  main
        .type   main, @function
main:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movq    $0, -8(%rbp)
        jmp     .L2
.L3:
        addq    $1, -8(%rbp)
.L2:
        movabsq $29999999999, %rax
        cmpq    %rax, -8(%rbp)
        jbe     .L3
        movl    $0, %eax
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   main, .-main
        .ident  "GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
        .section        .note.GNU-stack,"",@progbits

```

From this, we can see that on every iteration of the loop, four assembly instructions are being run. Therefore, to work out the instructions per second, we do `(4*30000000000)/77 = 1558441558` which is 1.6 GHz, much less than `0.99*2.3` which gives 2.28 GHz of the processor that we are actually meant to be using.

Why is there such a big discrepancy? The kernel is saying that 99% of the CPU is being used. Are there any other hidden instructions being computed by the CPU we don't see with `gcc -S`? Have I made a mistake somewhere?

# Answer
> 3 votes
The $2.3\textrm{GHz}$ clock cycle speed of your CPU is something entirely different from the rate at which it executes assembly instructions. Executing a single instruction may take 1, 10 or even more than 100 clock cycles or it might take less than a single cycle (since multiple instructions can sometimes be executed in a single cycle).

An interesting experiment would be to do some work in the loop body, such as an addition or a division. Even though addition and division are both single instructions, the program that does a division will probably take considerably longer than one that does addition since on most architectures division takes many clock cycles.

# Answer
> 1 votes
You didn't calculate the clockspeed. What you calculated was the number of instructions per second, which is about 1.56 billion per second. It seems your code takes 6 cycles per iteration.

Take the first instruction: addq $1, -8(%rbp). What does this instruction actually do? It calculates the memory address %rbp-8. It reads the memory at that location. It adds one to the result. It stores the result at the same memory location. That's four different things that need to be done for one single instruction.

And your code has at least one nasty dependency: You are storing a value at -8(%rbp) and then using the same value. That would normally mean that the store operation has to be completed (which takes a while even in cache), and the compare instruction has to wait reading the data until the store is complete. That will take a while.

But then I think newer Intel CPUs will do some heroic effort to figure out that you are reading from the same address, and therefore reading the memory location will return the value that is being stored right now, and forward the value from the result of the add directly, and not from memory. And the "branch" will be executed speculatively, and not wait for the comparison to finish.

You can't compare an old RISC processor with a current Intel processor. You used complex instructions that will be translated into multiple micro-ops, you had dependencies through memory. Big caches can't be accessed in a single cycle.

---
Tags: computer-architecture
---


# Question
Title: draw DFA with {w|w= Σ*0100}∩{w|w≠Σ*11Σ*}
So i need to draw a DFA for this language, i know i need to separate for 2 DFAs and than combine them both.

What is the approach ? How do i do the $\Sigma^\*$ inside the DFA ? The 0100 condition is kinda easy, also the 11 language.

# Answer
How to draw $\\{w|w≠\Sigma^\*11\Sigma^\*\\}$:

Three states $S\_0, S\_1, S\_2$ are needed. $S\_0$ is both a initial state and an accepted state, $S\_1$ is an accepted state. Whenever you read a $1$, go from $S\_i$ to $S\_{i+1}$. Finally let $S\_2$ be the dead state.

Similarly you can draw the $\\{w|w=\Sigma^\* 0100\\}$.

In the end, we combine these two DFAs with a cartesian product. You can look up here: https://stackoverflow.com/questions/7780521/how-to-use-the-intersection-construction-to-form-a-dfa
> 1 votes

---
Tags: automata, finite-automata
---


title: elevator algorithm

text:
# Question
Title: elevator algorithm
Using the elevator algorithm for processing disk requests, suppose requests arrive in the order: 8, 36, 34, 12.... (These numbers are cylinder numbers). Suppose the direction is UP meaning that the arm is taking on higher requests. Here we can see that both 36 and 34 are higher requests but 36 comes before 34, So, I'm confused if the algorithm addresses shortest distance between consecutive higher requests, because it was not addressed in the algorithm.

# Answer
The idea is that you guarantee that every request will be satisfied eventually by moving in one direction until there are no further requests in the same direction. The arrival order doesn't matter as much as the arrival times - any *first* request to an otherwise empty queue is scheduled immediately and set the direction. When that request is satisfied, look for additional requests in the same direction, then if none, reverse direction.
> 1 votes

---
Tags: algorithms
---