# Question
Title: Proving a value is the result of the execution of an algorithm
Assuming an algorithm $A$ known to both Alice and Bob.

Alice runs the algorithm and gets a result $R$. How can Alice prove to Bob that $R$ is the result of the execution of $A$ and not some random value (without having Bob run the algorithm himself)?

The goal is for Bob to perform less calculations checking Alice proof than running the algorithm itself. A probabilistic scheme for the proof is fine.

Please note that Alice does not have to prove correctness of $R$, just that she ran $A$ to obtain $R$.

The algorithm and its inputs can be modified to build the proof if necessary

Note: from the discussions below. I am happy with heuristics or techniques to obtain the proof. This is *not* a rhetorical question on algorithms.

Note2: @DavidRicherby suggests providing an execution trace, which seems perfectly reasonable. This leads to two sub-questions

1. How does Alice practically build a trace which proves to Bob with high probability that the trace is the one linked to the result ? (Bob should run less calculations checking the trace, than running the calculation himself)
2. Could such a mechanism be generic i.e. work with any algorithm ? For instance by confining execution inside a Virtual Machine which could record all operations.

# Answer
> 5 votes
This is known as verifiable computing or verified computation. There are many protocols for verified computation, with different properties. Some of them rely upon special hardware (e.g., SGX). Many of them don't rely on special hardware and use cryptography. Among the cryptographic solutions, there are some protocols that can be used with any program (but are potentially inefficient), and some that can only be used for specific programs or types of computations (but are much more efficient).

There's an entire line of research papers on the subject, and it is too broad to summarize in a single paragraph or two. I suggest reading about interactive proofs, and about the Pepper, Ginger, Zaatar, Pinocchio, Pantry, and Truebit systems, among others. I also recommend reading the following survey paper for an overview of cryptographic solutions that can handle general computation:

In practice, I suspect that the SGX-based schemes or Truebit are likely to be the most practical for general computation at the moment, though the research literature is progressing rapidly and this could change in the future. For specific computations, it is sometimes possible to design a custom protocol that does much better, but that depends on the particular computation.

# Answer
> 1 votes
Assuming that the algorithm results in an output $R$ that is a deterministic function of its input(s).

Bob asks Alice to run the algorithm on a given input $I$, obtain an output $R\_1$, use that as an input to the algorithm and produce $R\_2$, and to re-run the algorithm $n$ number of times where $n$ is an even number. Bob also asks Alice to send $R\_{n/2}$ and $R\_n$

Now Bob runs the algorithm $\frac{n}{2}$ times on the initial input $I$ (with $p=0.5$) and checks if $A(A(A(..I))) = R\_{n/2}$ or runs it on $R\_{n/2}$ (with $p=0.5$) and sees if $A(A(A(..R\_{n/2}))) = R\_n$.

As suggested by @Draconis, we can also extend this to any $k$ instead of looking at just 2 results. This will allow Bob to potentially do much lesser work.

We can use a probability bound to see what the value of $n$ should be to obtain a given confidence. This way, Bob can be certain that Alice is running algorithm $A$ by using fewer computations that Alice.

Note: This relies on Bob asking Alice to do possibly meaningless extra computations but do let me know if there are specific points in your question that this answer does not address.

---
Tags: proof-techniques
---


# Question
Title: Is Pattern Matching as expressive as Case Expression in Haskell?
### Nomenclature

The term *expressive* in the question shall bear the same meaning as in the following sentence:

> A Turing Machine is as *expressive* as Lambda Calculus.

### Introduction

While learning Haskell, I had noticed that there are 2 ways to achieve the same effect, namely Pattern Matching and Case Expression. For example,

```
-- Pattern Matching
not True  = False
not False = True

-- Case Expression
not x = case x of True  -> False
                  False -> True

```

I am also fully aware that Pattern Matching is actually a form of syntax sugar that will be compiled into Case Expression.

Therefore, we can be very sure that every Pattern Matching expression can be converted to Case Expression.

## Question

So, this is my question: Is the following statement true?

> Every Case Expression can be re-written using Pattern Matching.

Regardless of the truthiness of the statement above, I would be glad if you could provide a formal proof to support your answer.

### P/S

The motivation that drove me to seek answer for this question is because I'm currently designing my own language, which I wish to have as less feature as possible, but not too minimal like Lambda Calculus which only have 3 features.

# Answer
> 4 votes
The expression

```
case e of
  p1 -> e1
  p2 -> e2
  ...

```

can be rewritten as

```
let k p1 = e1
    k p2 = e2
    ...
 in k e

```

where `k` is a fresh identifier.

This translation assumes that the language has some way to define a local function by pattern matching (e.g. `let`).

---

If local functions can not be defined, there's always the possibility of lifting the definition to the top level. Indeed, any local definition

```
let f x1 ... xk = e in e'

```

having free variables `v1 .. vn` can be rewritten written as

```
(\f -> e') (globalF v1 ... vn)

```

provided that we also define a global function

```
globalF v1 ... vn x1 ... xk = e

```

Note that `globalF` has no free variables, by construction. I believe it is sometimes called a "supercombinator".

This naturally extends to the case where `x1 ... xk` are patterns, and we have multiple defining equations for `f` / `globalF`.

---

For example,

```
case x of True  -> False
          False -> True

```

cab be rewritten as

```
let f True  = False
    f False = True
 in f x

```

---
Tags: functional-programming, haskell
---


title: Algorithm Design for Linear Programming

text:
# Question
Title: Algorithm Design for Linear Programming
I am trying to complete question and would like to avoid copying answers, but I do not necessarily understand what I am doing.

I am working on the following problem:

> Suppose you are consulting for a company that manufactures PC. equipment and ships it to distributors all over the country. For each of the next n weeks, they have a projected supply $s\_i$ of equipment (measured in pounds) that has to be shipped by an air freight carrier. Each weeks supply can be carried by one of two air freight companies, $A$ or $B$.
>
> * Company $A$ charges a fixed rate $r$ per pound (so it costs $r$ x $s$ to ship a week's supply $s\_i$).
> * Company $B$ makes contracts for a fixed amount $c$ per week. independent of the weight. However, contracts with company $B$ must be made in blocks of four consecutive weeks at a time.
>
> A schedule for the PC company is a choice of air freight company ($A$ or $B$) for each of the $n$ weeks with the restriction that company $B$, whenever it is chosen, must be chosen for blocks of four contiguous weeks in time. The cost of the schedule is the total amount paid to company $A$ and $B$, according to the description above.
>
> Give a polynomial-time algorithm that takes a sequence of supply values $s\_1, s\_2, \cdots, s\_n$ and returns a schedule of minimum cost. For example, suppose $r = 1$, $c = 10$, and the sequence of values is $11, 9, 9, 12, 12, 12, 12, 9, 9, 11.$
>
> Then the optimal schedule would be to choose company $A$ for the first three weeks, company $B$ for the next block of four contiguous weeks. and then company $A$ for the final three weeks.

I am trying to write algorithm, in pseudo code, that completed the following steps in order to solve the challenge, but I don't know even where begin this solution. My initial suspect on how to solve this:

* Determine what the "optimal" formula looks like, which is: `MIN((r*s + OPT(i-1), (3c + OPT(i-3))`

This would determine the most optimal between $A$ or $B$ given their restrictions. Therefore I would need to determine the most optimal schedules for the weeks preceding the $i^{\text{th}}$ week. Meaning I would end up running OPT(n-1) for every n, thus resulting in OPT(n) total runs so (n) time complexity.

Any advice on how to generate pseudocode for this would be appreciated...I am trying to learn but am not very effective.

# Answer
The approach you used is called *dynamic programming*.

In dynamic programming, a series of decisions are made in order to maximize some function, where the options available at any given time depend on the decision we have made before. You may want to check a tutorial on TopCoder or some course material at your hand.

You have started to figure out the recurrence relation, the hallmark of dynamic programming. However, it looks like you made an off-by-one error.

You can imitate the pseudocode in that tutorial. Or many other pseudocode such as those in the *Introduction to algorithm* by Corman et al.

Here is my pseudocode for this problem, where you can find the correct recurrence relation. I assume $n\ge4$; otherwise the only choice is to use company $A$ always.

1. Let $OPT$ be an array of size $n$.
2. $OPT\[0\]=0$, $OPT\[1\]=s\_1r$, $OPT\[2\]=(s\_1+s\_2)r$, $OPT\[3\]=(s\_1+s\_2+s\_3)r$
3. For $i$ = 4 to $n$, $OPT\[i\] = \min(OPT\[i-1\] + s\_ir, OPT\[i-4\] + 4c)$
4. Output $OPT\[n\]$
> 3 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Concave Polygon Intersection - Algorithm
I'm trying to develop an Algorithm for Polygon Intersection. Where each polygon is an array of Points, where each Point has X and Y properties.
Algorithm limitations:
\- Algorithm input: 2 Polygons.
\- Algorithm output: Intersection Polygon.
\- Polygons may be convex or concave (angle between 2 neighbor edges my be more than 180).
\- Polygons will **not** have any holes and will **not** be self intersection polygons.

I managed to develop this algorithm this far (given 2 polygons A and B):

---

1. For each vertex in PolygonA:
1.1 If vertex is inside PolygonB then Add this vertex to groupA.
2. For each vertex in PolygonB:
2.1 If vertex is inside PolygonA then Add this vertex to groupB.
3. For each edge {edgeA} in PolygonA:
3.1 For each edge {edgeB} in PolygonB:
3.1.1 If edgeA and edgeB are intersect (in the edgeA and edgeB segment area) then add there intersection point to groupI.
4. marge(groupA, groupB, groupI); // I don't know how to implement this

---

In debug I see that the Intersection area is built from vertexes combined groupA, groupB and groupI. But I don't know how should I merged them together - how to order/sort them???

I have try to sort the clockwise around the center point of the new intersection polygon - but this will only work for convex polygons not for concave.

In this example:
\- The Blue Points are vertexes of PolygonA inside PolygonB (groupA)
\- The Red Points are vertexes of PolygonB inside PolygonA (groupB)
\- The Yellow Points are intersect vertexes of PolygonA with PolygonB (groupI)

# Answer
> 1 votes
OK, so the solution wasn't simple but here it goes:
Given 3 arrays and original shapes:
\- GroupA - all the points of polygonA inside polygonB
\- GroupB - all the points of polygonB inside polygonA
\- GroupI - all the intersection points of both polygons
\- The original Polygons: PolygonA and PolygonB
Step 1:
Create Array: A+ by: merge PolygonA with GroupI:
1.1 Loop over the edges of PolygonA (each 2 neighbor points creating an edge - also the first and the last).
1.2 For each edge create a line equation: "y = mx + b" (given 2 points)
1.3 Collect all the point of GroupI that are placed on the line created at "1.2"
1.4 Sort the collected points by distance from the edge start point.
1.5 Add the sorted collection to PolygonA after the edge start point.
2. Return the new PolygonA as a new array: A+
Step 2:
Repeat step1 but create B+ form PolygonB with groupI.
Step 3:
Create Array A\* by removing points from A+ that not exist of GroupA
Step 4:
Create Array B\* by removing points from B+ that not exist of GroupB
Step 5:
Merge Array A\* with B\*
5.1 - Create a new array Result
5.2 - Loop over A\* and B\* with 2 indexes: iA and iB, for each point:
5.3 - If point is None intersection point - add it to the Result array and increment the active index (iA or iB)
5.4 - If point is intersection point - add it the the result array and switch to the 2nd array (if you where iterating over A\* switch to B\* and vise versa).
5.4.1 - Set the index to the position of the intersection point in the 2nd array (meaning if you are at pointX in A\* and this is intersection point, start running on B\* from the location of pointX at B\*)
Here is an example:

# Answer
> 1 votes
First, order the $Blue \cup Yellow$ points according to a clockwise visit of A, and similarly, order the $Red \cup Yellow$ points according to a clockwise visit of B.

Now start at a blue point (if there is one) and follow A clockwise until you are at a yellow point. Then follow B clockwise until you are at a yellow point again; then follow A clockwise, and so on, switching from following one polygon to the other every time you encounter a yellow point. Continue until you are back at the starting point. See Weiler-Atherton clipping algorithm and the references there.

If there are no blue points, start instead from a red point and follow B initially. If there are only yellow points (with no blue nor red), start from any yellow point and follow the polygon that makes you stay inside the other polygon.

Note that in general the intersection of non-convex polygons may consist of multiple disconnected regions. The procedure above will only give you one of these regions.

---
Tags: computational-geometry
---


# Question
Title: Confused about constructing the "failure table" in Knuth-Morris-Pratt algorithm
I'm trying to learn how the "failure table" is constructed in the Knuth-Morris-Pratt algorithm since it seemed nontrivial to me that you could do it in $O(k)$ time (where $k$ is the length of the pattern, $W$). To be clear, we let the failure table $T$ be a length $k$ array where $T\[i\]$ is the length of the longest proper prefix of $W$ which is also a suffix of $W\[1\]\cdots W\[i\]$.

I was trying to understand it better by reading the following code:

```
    vector<int> T(pattern.size());
    T[0] = 0;
    int j;
    for (int i = 1; i < pattern.size(); i++) {
        j = T[i - 1];
        // Find largest j s.t. T[:j+1] == T[i-j:i+1]
        while (j > 0 && pattern[j] != pattern[i]) {
            j = T[j - 1];
        }
        T[i] = (pattern[j] == pattern[i]) ? j + 1 : j;
    }
    return T;

```

The part I'm confused about is why `pattern[j] == pattern[i]` is enough to guarantee that $T\[i\] = j + 1$. I was trying to prove this inductively but have had no luck. I've phrased the problem as follows:

Suppose $W\[1\]\cdots W\[T\[i - 1\]\] = W\[i - T\[i - 1\]\]\cdots W\[i - 1\]$. If $W\[i\] == W\[j\]$, then is it true that $W\[1\]\cdots W\[j\] == W\[i - j + 1\]\cdots W\[i\]$?

I can't make any headway with this, nor can I see why it should be true. It still seems like we have to check $W\[\ell\] = W\[i - j + \ell\]$ for all $\ell = 1...j$. I can't figure out how to use the inductive hypothesis to prove this result. Do I have to use *strong induction* (where we assume *all* prior steps are true and not just the previous step) to prove this?

# Answer
A proper prefix, which is also a suffix of the same string, is usually called *border*.

The condition you're asking about basically says this:

1. If $W\[1..i-1\]$ has a border of length $j$ and $W\[j+1\] = W\[i\]$, then $W\[1..i\]$ has a border of length $j+1$.
2. If $W\[1..i-1\]$ has no border of length $j$ such that $W\[j+1\] = W\[i\]$, then the length of the maximal border of $W\[1..i\]$ is $0$.

Both points follow directly from definition of string equality and definition of borders.

What you need to prove is that the while-loop indeed enumerates all possible borders in descending order.
> 1 votes

---
Tags: algorithms, string-matching
---


# Question
Title: Find pair of complex numbers with maximal sum
Given two lists of complex numbers, is there an efficient algorithm to choose one element from each list such that the magnitude of their sum is maximal?

# Answer
Observations:

1. The pairing mechanism creates the Minkowski sum of the two sets.
2. The convex hull of the Minkowski sum is the Minkowski sum of the convex hulls. (See e.g. previously linked Wikipedia article).
3. Given a set of points in the plane, the point furthest from the origin must be a vertex of the convex hull.
4. The convex hull of a set of $n$ points can be found in $O(n \lg n)$ time. (In fact in $O(n \lg h)$ time, where $h$ is the number of points on the convex hull).
5. > For two convex polygons P and Q in the plane with $m$ and $n$ vertices, their Minkowski sum is a convex polygon with at most $m + n$ vertices and may be computed in time $O(m + n)$ by a very simple procedure...

given in the Wikipedia article.

Combining these observations gives an $O(n \lg n)$ algorithm.
> 2 votes

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


# Question
Title: how do I simplify this particular boolean expression?
so I have spent nearly 5 hours trying to simplify this particular expression but I keep going round and round in circles. I have my hard copy notes to show you where I scribbled for hours and hours to no end. so please can someone please show me how can this be done?

$$(\overline{A}+\overline{B}+E)(\overline{A}+\overline{C}+D)(C+D+\overline{E})(\overline{B}+D)(A+E)\\,.$$

I tried expansion, common, DeMorgan but I can't find my way out.

# Answer
We can do it by brute force, expanding all 108 product terms and combining like terms carefully. Many of the terms can be eliminated immediately.

In hindsight or by luck or by sharp observation that D and E appear most frequently, we can proceed as follows.

> $(\overline{A}+\overline{B}+E)(\overline{A}+\overline{C}+D)(C+D+\overline{E})(\overline{B}+D)(A+E)$

Let $D=1$ and $E = 1$. The formula becomes 11111 = 1
Let $D=1$ and $E = 0$. The formula becomes $(\overline{A}+\overline{B})1 1 1 A = \overline{B}A$
Let $D=0$ and $E =1$. The formula becomes $1(\overline{A}+\overline{C}) C \overline{B} 1 = \overline{A}C\overline{B}$
Let $D=0$ and $E = 0$. The formula becomes $(\overline{A}+\overline{B})(\overline{A}+\overline{C})1 \overline{B} A = \overline{C}\overline{B}A$

So the original formula is $$DE + (D\overline{E}A + \overline{D}(E\overline{A}C + \overline{E}\overline{C}A))\overline{B}$$

(Computationally, it is debatable which formula is simpler.)
> 1 votes

---
Tags: boolean-algebra
---


title: Does a byte contain 8 bits, or 9?

text:
# Question
Title: Does a byte contain 8 bits, or 9?
I read in this assembly programming tutorial that 8 bits are used for data while 1 bit is for parity, which is then used for detecting parity error (caused by hardware fault or electrical disturbance).

Is this true?

# Answer
A byte of data is eight bits, there may be more bits per byte of data that are used at the OS or even the hardware level for error checking (parity bit, or even a more advanced error detection scheme), but the data is eight bits and any parity bit is usually invisible to the software. A byte has been standardized to mean 'eight bits of data'. The text isn't wrong in saying there may be more bits dedicated to storing a byte of data of than the eight bits of data, but those aren't typically considered part of the byte per se, the text itself points to this fact.

You can see this in the following section of the tutorial:

```
Doubleword: a 4-byte (32 bit) data item

```

4\*8=32, it might actually take up 36 bits on the system but for your intents and purposes it's only 32 bits.
> 78 votes

# Answer
Traditionally, a byte can be any size, and is just the smallest addressable unit of memory. These days, 8 bit bytes have pretty much been standardized for software. As JustAnotherSoul said, the hardware may store more bits than the 8 bits of data.

If you're working on programmable logic devices, like FPGAs, you might see that their internal memory is often addressable as 9-bit chunks, and as the HDL author, you could use that 9th bit for error checking or just to store larger amounts of data per "byte". When buying memory chips for custom hardware, you generally have the choice of 8 or 9 bit addressable units (or 16/18, 32/36, etc), and then it is up to you whether you have 9 bit "bytes" and what you do with that 9th bit if you choose to have it.
> 51 votes

# Answer
That text is extremely poorly worded. He is almost certainly talking about ECC *(error-correcting code)* RAM.

ECC ram will commonly store 8-bits worth of information using 9-bits. The extra bit-per-byte is used to store error correction codes.

*(In both cases, every byte is spread across every chip. Image courtesy of Puget Systems)*

This is all completely invisible to users of the hardware. In both cases, software using this RAM sees 8 bits per byte.

---

As an aside: error-correcting codes in RAM typically aren't actually 1 bit per byte; they're instead 8 bits per 8 bytes. This has the same space overhead, but has some additional advantages. See SECDED for more info.
> 32 votes

# Answer
Generally speaking, the short answer is that a byte is 8 bits. This oversimplifies the matter (sometimes even to the point of inaccuracy), but is the definition most people (including a large number of programmers) are familiar with, and the definition nearly everyone defaults to (regardless of how many differently-sized bytes they've had to work with).

More specifically, a byte is the smallest addressable memory unit for the given architecture, and is generally large enough to hold a single text character. On most modern architectures, a byte is defined as 8 bits; ISO/IEC 80000-13 also specifies that a byte is 8 bits, as does popular consensus (meaning that if you're talking about, say, 9-bit bytes, you're going to run into a *lot* of trouble unless you explicitly state that you don't mean normal bytes).

However, there are exceptions to this rule. For example:

So, in most cases, a byte will generally be 8 bits. If not, it's *probably* 9 bits, and may or may not be part of a 36-bit word.
> 18 votes

# Answer
Note that the term *byte* is not well-defined without context. As far as computer architectures are concerned, you can assume that a byte is 8-bit, at least for modern architectures. This was largely standardised by programming languages such as C, which required bytes to have *at least* 8 bits but didn't provide any guarantees for larger bytes, making 8 bits per byte the only safe assumption.

There are computers with addressable units larger than 8 bits (usually 16 or 32), but those units are usually called machine words, not bytes. For example, a DSP with 32K 32-bit RAM words would be advertised as having 128 KB or RAM, not 32 KB.

Things are not so well-defined when it comes to communication standards. ASCII is still widely used, and it has 7-bit bytes (which nicely fit in 8-bit bytes on computers). UART transceivers are still produced to have configurable byte size (usually, you get to pick at least between 6, 7 and 8 bits per byte, but 5 and 9 are not unheard of).
> 8 votes

# Answer
A byte is usually defined as the smallest individually addressable unit of memory space. It can be any size. There have been architectures with byte sizes anywhere between 6 and 9 bits, maybe even bigger. There are also architectures where the only addressable unit is the size of the bus, on such architectures we can either say that they simply *have no byte*, or the byte is the same size as the word (in one particular case I know of that would be 32 bit); either way, it is definitely not 8 bit. Likewise, there are bit-addressable architectures, on those architectures, we could again argue that bytes simply don't exist, or we could argue that bytes are 1 bit; either way is a sensible definition, but 8 bit is definitely wrong.

On many mainstream general purpose architectures, one byte contains 8 bit. However, that is not guaranteed. The further away you stray from the mainstream and/or from general purpose CPUs, the more likely you will encounter non-8-bit-bytes. This goes so far that some highly-portable software even makes the size configurable. E.g. older versions of GCC contained a macro called `BITS_PER_BYTE` (or something like that), which configured the size of a byte for a particular architecture. I believe some older versions of NetBSD could be made to run on non-8-bit-per-byte architectures.

If you really want to stress that you are talking about an exact amount of 8 bit rather than the smallest addressable amount of memory, however large that may be, you can use the term *octet*, which is for example used in many newer RfCs.
> 6 votes

# Answer
First, the tutorial that you are referencing seems to be quite outdated, and seems to be directed at outdated versions of x86 processors, without stating it, so lots of the things you read there will not be understood by others (for example if you claim that a WORD is 2 bytes, people will either not know what you are talking about, or they will know that you have been taught based on very outdated x86 processors and will know what to expect).

A byte is whatever number of bits someone decides it should be. It could be 8 bit, or 9 bit, or 16 bit, anything. In 2016, in most cases a byte will be eight bit. To be safe you can use the term octet - an octet is always, always, eight bits.

The real confusion here is confusing two questions: 1. What is the number of bits in a byte? 2. If I wanted to transfer one byte from one place to another, or if I wanted to store a byte, using practical physical means, how would I do that? The second question is usually of little interest to you, unless you work at a company making modems, or hard drives, or SSD drives. In practice you are interested in the first question, and for the second one you just say "well, someone looks after that".

The parity bit that was mentioned is a primitive mechanism that helps detecting that when a byte is stored in memory, and later the byte is read, the memory has changed by some accident. It's not very good at that, because it won't find that two bits have been changed so a change is likely to go undetected, and it cannot recover from the problem because there is no way to find out which of the 8 bits have changed, or even if the parity bit has changed.

Parity bits are practically not used in that primitive form. Data that is stored permanently is usually protected in more complicated ways, for example by adding a 32 bit or longer checksum to a block of 1024 bytes - which takes much less extra space (0.4% in this example instead of 12.5%) and is much less likely to not find out when something is wrong.
> 3 votes

# Answer
When I started programming in 1960, we had 48 bit words with 6 bit bytes - they ware not called that name then, they were called characters. Then I worked on the Golem computer with 75 bit words and 15 bit bytes. Later, 6 bit bytes were the norm, until IBM came out with the 360, and nowadays a byte is commonly equivalent to an octet, i.e. 8 bits of data. Some hardware had additional bits for error detection and possibly for error correction, but these were not accessible by the software.
> 3 votes

# Answer
A byte is 8 bits.

In the distant past, there were different definitions of a memory word and of a byte. The suggestion that this ambiguity is widespread or is prevalent in today's life is false.

Since at least the late 1970's, a byte has been 8 bits. The mass populace of home computers and PCs have all unambiguously used a byte as an 8-bit value in their documentation, as have all of the data sheets and documentation for floppy disk drives, hard disk drives and PROM/EPROM/EEPROM/Flash EPROM/SRAM/SDRAM memory chips that I have read in that time period. (And I have personally read a great deal of them right across that time period.) Ethernet and a couple of other communications protocols stand out to me as unusual in talking about octets.

The ambiguity of the term byte is itself a rare and obscure thing. Very, very few of the population of programmers, design engineers, test engineers, salespeople, service engineers or average punters in the last 30 years or more would think it meant something other than an 8-bit value, if they recognised the word at all.

When a byte is handled by hardware, such as when stored in memory chips or communicated along wire, the hardware may add redundant data to the byte. This may later assist in detecting hardware errors so that unreliable data can be recognised and discarded (e.g. parity, checksum, CRC). Or it may allow errors in the data to be corrected and the data recovered (e.g. ECC). Either way, the redundant data will be discarded when the byte has been retrieved or received for further processing. The byte remains the central 8-bit value and the redundant data remains redundant data.
> 2 votes

# Answer
Despite the really excellent answers given here, I'm surprised that no one has pointed that **parity bits** or **error correction bits** are by definition 'metadata' and so not part of the byte itself.

**A byte has 8 bits**!
> 2 votes

# Answer
In modern usage, a byte is 8 bits, period (although it has historically had other definitions). On the other hand, a data word is whatever the hardware in question handles as an atomic unit - could be 8 bits, 9 bits, 10 bits, 12 bits, 16 bits, 20 bits, 24 bits, 32 bits, etc. Various computer systems over the years have had all sorts of different word sizes.

To implement a memory system or a transmission protocol, it is beneficial to add error detection/correction which involves additional bits. They don't make for a 9-bit byte because, as stated above, a byte is 8 bits.

Various schemes add error detection and/or correction in various ways.

The typical use of parity is to add an extra bit to the transmission word so that the receiver can detect a single bit of error.

A scheme which can provide single-bit error correction involves the addition of 4 ECC bits per 32 bit data word. This just happens to be arithmetically equivalent to 1 bit per byte, but it cannot/does not work that way. One 36-bit data word can carry enough information to recover from a single bit error for a 32-bit data space.
> 0 votes

# Answer
8 bits. Inside the cpu and keyboard, it is 9 and 11 bit. User data is represented in 8 bits though. Keys on keyboard send sings which is devided into 11 bits. 1 starting bit, 1 ending bit, 1 parity bit and 8 bits representing a key pressed.
> 0 votes

---
Tags: computer-architecture, numeral-representations
---


# Question
Title: algorithm for correctly rounded floating point radix conversion
Is there any generic algorithm which implements a floating point radix conversion?

Lets say we have a $p$-digit FP number

$A = \sum\_{i=0}^{p-1} A\_i \beta^{e-i}$

in radix $\beta$ and with $0 \leq A\_i \< \beta$.

How do we find the $A'\_i$, $e'$ values for the $p'$-digit base $\gamma$ FP number

$A' = \sum\_{i=0}^{p'-1} A'\_i \gamma^{e'-i}$

closest to $A$?

There is one question which explicitly asks about radix 2 to radix 10 conversion, but unfortunately the answers seem to be specific for these radix combination. Here I ask about the general case.

Also is an intermediate arbitrary precision FP calculation really necessary? (as in the function `strtod` in David Gay's dtoa.c)

# Answer
> 1 votes
In the worst case, you may need very high precision intermediate results. If your problem is limited, for example p ≤ 50 and e ≤ 1,000, it will be possible to prove how much precision is needed at most - with $1000 \cdot 10^{50}$ possible values to convert, 200 bits precision are likely enough.

In practice, some values can be calculated with correct rounding by calculating them with a single floating point operation with exact operands. Many other values can be calculated rounded correctly (including proof) with just a bit of extra precision. So you can do the calculation with relatively few extra bits of precision, check if you have a proven correctly rounded result, and do the same calculation with more bits if needed.

Example: 10.00073 = 1,000,073 / 100,000 Is the quotient of two exact numbers and therefore correctly rounded. 1e30 = 1e15 x 1e15 = product of two exact numbers. 1,000,000,000,000,000,123,456,789,012,345 = FMA (1e15,1e15, 123,456,789,012,344) = fused multiply-add of there exact numbers.

---
Tags: algorithms, floating-point
---


# Question
Title: Big O space complexity of this isAnagram method
I'm currently debating with some friends what is the Big O space complexity of this isAnagram method:

```
public boolean isAnagram(String firstWord, String secondWord) {
    if(firstWord == null || secondWord == null || firstWord.length() != secondWord.length()) {
        return false;
    }

    Map<Character, Integer> charCounts = new HashMap<>();
    for(char c1 : firstWord.toCharArray()) {
        if(charCounts.containsKey(c1)) {
            int currentCount = charCounts.get(c1);
            charCounts.put(c1, currentCount + 1);
        } else {
            charCounts.put(c1, 1);
        }
    }

    for(char c2 : secondWord.toCharArray()) {
        if(charCounts.containsKey(c2)) {
            int currentCount = charCounts.get(c2);
            if(currentCount == 0) {
                return false; // not an anagram if it has more of one character than the first word
            }
            charCounts.put(c2, currentCount - 1);
        } else {
            return false; // not an anagram if it contains another character
        }
    }
    return true;
}

```

It's a point of contention because the space used by the method doesn't exactly depend on the input, but a characteristic of the input, namely the number of unique characters in the firstWord.

Let's say m is the length of the first word, and n is the length of the second word. Let's say that k is the number of unique characters in firstWord.

Some of us think that the space complexity is O(k), essentially the number of entries in the map. That is: k is the upper bound on the space used, because k will be the number of entries created in the map, one entry for each unique character.

Some think, it's basically just an O(1) space complexity, because even though the map is dynamically sized in reality, we could also think of it as O(1) and actually just pre-populate the map with counts of 0 for all possible alphabet. The argument against this is that you don't know "all possible alphabet" when latin alphabet is 26 characters, but ascii has 128, and unicode has \> 137,000, and other character sets, who knows?

Others argue that we should take into account only m, the length of the first word. In some cases m \< k, because it is shorter than k. In the worst case, m \> k (because of duplicate characters) and, in very long strings, m will determine the choice of the type of the map's values. e.g. The code given uses "Integer" or 2^32 size counts, but you may need to go to 2^64 or even larger on very long strings. At any rate, this argument contends that m is a factor in how the algorithm scales and so it should be O(m).

A derivative of this last argument is that, on average, for any given character, there are m/k occurrences of that character in the string and the size of a value m/k in computer space is log(m/k), therefore a tighter Big O is O(k * log(m/k)).

Does anyone have any thoughts?

# Answer
> 1 votes
You probably expected the following answer.

**Everyone of your friends is correct from her/his own perspective.**

All you need to realize is that complexity analysis depends on lots of assumptions. In many cases, those assumptions have been defined beforehand or different assumptions will not not affect the end result of time-complexity analysis and space-complexity analysis. So people usually do not even mention those assumptions, especially in situations where the assumptions are stated or illustrated beforehand such as at the start of a chapter or a course. However, from time to time, situations arise where those assumptions are unclear, debatable, missing or even plainly invalid. Once you have made it clear what are the assumptions, including the **model of computation** used, there should be no real conflict.

Let us check each perspective raised in the question.

"The space complexity is $O(k)$", where "$k$ is the number of unique characters in firstWord". This observation points out the basic quantity in space usage.

"It's basically just an $O(1)$ space complexity", which make sense if we assume the input come from a vocabulary with a bounded number of characters. This is consistent with (almost?) all natural languages, whose number of characters are bounded while words or strings can be created as long and as many as we wanted, if only for the purpose of playing IsAnagram. Note this proposition can be seen as the previous proposition applied to refined but very common situations.

"It should be $O(m)$", where "$m$ is the length of the first word". There is hardly any argument against the correctness of this more relaxed bound, although it may seem not as tight as other bounds.

"On average, for any given character, there are $m/k$ occurrences of that character in the string and the size of a value $m/k$ in computer space is log(m/k) therefore, a tighter big $O$ is $O(k\log(m/k))$". This bound is based on the sharper observation that a number consists of many bits. Instead of counting the number of numbers used, it counts the number of bits used. (To prove that bound is correct, a dose of non-trivial math is needed.) The positional number system is about the optimal system to represent integers in term of space usage in this world, a fact that is reflected in the $\log$ factor. It can hardly considered anywhere near the physical truth without that factor. This line of reasoning is interesting as it indicates a more realistic model of computation than the more-commonly-used models of computations as implied in virtually every tutorial for elementary complexity analysis (\[1\], \[2\], \[3\]), where any integer is considered occupying a unit of space for the sake of simplicity and uniformity. Those common models include the family of register machines that includes counter machine and random-access machine. That is why we rarely see that $\log$ factor showing up in most complexity analysis. Unless required explicitly, we usually ignore that factor in space-complexity analysis and time-complexity analysis on our daily programming. On the other hand, that factor has to be taken into consideration, for example, in the bit by bit analysis of the Turing machines (Why do we reject Turing machines that use space less than the log of the length of the input?).

You might insist asking, which answer makes sense most? Well, even though I might have my personal preference, a single choice will appear opposite to the whole point of this answer. Each and every one of them is valid under their respective assumptions and useful in different situations. Of course, if you are in an exam, do remember the default assumptions in your course!

---

As you must have noticed, I have inserted time-complexity in this answer. That is because we could have similar contention over the time-complexity of many algorithms. The usual resolution will be the same: state the assumptions clearly and we can happily accept each other's view, even though we might feel less comfortable with others' perspectives.

---
Tags: algorithm-analysis, asymptotics, space-analysis
---


# Question
Title: In ISGCI, unit interval graphs are denoted as ($C_{n+4}$,$S_3$,claw,net)-free. Is this an accurate notation?
When I search unit interval graphs in ISGCI, it says that the unit interval graphs (**UIG**) are equivalent to ($C\_{n+4}$,$S\_3$,claw,net)-free graphs.

I am confused about the definition of an $S\_3$ graph. I am aware that in some resources, $S\_n$ means $K\_{1,n}$, and in others $S\_{n-1}$ means $K\_{1,n}$.

However, in both cases, ($C\_{n+4}$,$S\_3$,claw,net)-free $\equiv$ **UIG** seems like a wrong notation.

If $S\_3$ is $K\_{1,3}$, then $S\_3$ is also a claw graph. Thus, ($S\_3$,claw)-free is a redundant notation. On the other hand, if $S\_3$ is $K\_{1,2}$, then it is wrong because a path of length 3 is realizable as a unit interval graph.

If this notation is true, then can I also write **UIG** $\equiv$ ($C\_{n+4}$,$S\_3$,$K\_{1,2}$,$P\_2$,claw,net)-free?
If not, then is it correct to write that **UIG** $\equiv$ ($C\_{n+4}$,claw,net)-free?

# Answer
You can look up the small graphs that ISGCI uses to define classes. Specifically, $S\_3$ is the following "sun" graph:

ISGCI defines sun graphs as

> a chordal graph on $2n$ nodes ($n\geq3$) whose vertex set can be partitioned into $W = \\{w\_1,\dots,w\_n\\}$ and $U = \\{u\_1, \dots,u\_n\\}$ such that $W$ is independent and $u\_i$ is adjacent to $w\_j$ iff $i=j$ or $i=j+1\pmod{n}$.

Implicitly, the subgraph induced by $U$ can be anything. Wolfram Mathworld also talks about "complete sun graphs", which is the special case where $U$ is a clique.
> 3 votes

---
Tags: graphs, notation
---


# Question
Title: Prove that $L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$ not recursively enumerable
Past year paper question:

Let $M\_i$ denote the Turing machine with code $i$ using the alphabet $\Sigma=\\{a,b\\}$.

Show that the following language is not recursively enumerable:

$L = \\{a^i \\;:\\; (\exists x \in \mathrm{Lang}(M\_i))\\;\[ xx \notin \mathrm{Lang}(M\_i) \] \\}$

I tried to show that we can reduce $L\_e$, the set of Turing machines that accept no strings, to $L$. To do this, I need to find a transformation $f$ such that is $\mathrm{Lang}(M)$ is empty, then the machine represented by $f(M)$ has some string $x$ but not $xx$, and if $\mathrm{Lang}(M)$ is not empty, then the machine represented by $f(M)$ contains $xx$ if it contains $x$.

But I am not sure how to find such a transformation. Can someone show a transformation to solve this problem?

# Answer
First, recall that the problem "$L(M)\neq\emptyset$" is semidecidable.

Define $f(M)$ as $a^i$ where $M\_i$ is a TM such that

* it accepts $aa$ iff $L(M)\neq\emptyset$,
* it accepts any other string (including $a$).

For the first step: when $M\_i$ receives $aa$ as input, it semi-decides $L(M)\neq\emptyset$. If that holds, the semi-decider halts in finite time, so $M\_i$ can accept. If that does not hold, the semi-decider diverges, making $M\_i$ diverge. This is fine, since $aa$ is not accepted.

Note that we never reject $aa$, because we do not have a full decider for $L(M)\neq\emptyset$. This however does not matter: we do not have to reject $aa$, we only have to avoid accepting it, and diverging suffices.
> 0 votes

---
Tags: computability, reductions, undecidability
---


# Question
Title: How could a formal system ever be non-obviously unsound?
When reading discussions of Gödel's theorems one is always heeded that just because formal system $F$ proves a theorem $T$ that doesn't necessarily mean that when one applies the intended interpretation the theorem is actually true. After all, even if one assumes that $F$ is consistent, it might still be unsound.

But this puzzles me. When setting up $F$ one always makes sure that all the axioms are true under the intended interpretation. Presumably, one would also make sure that all the rules of inference are valid. That is, if all the theorems proven so far are true, then the rules of inference only produce further true theorems. Is that too much to ask?
However, this straightforward construction immediately implies that I can't prove falsehoods under the intended interpretation. Further, I'd be hesitant to even call something for which the rules of inference aren't truth preserving an "interpretation".
But then it seems that unsound formal systems couldn't even exist. So where's the problem with this view?

# Answer
You jumped to a conclusion when you said that "when setting up $F$ one always makes sure that all the axioms are true under the intended interpretation". This is not the case at all. Using theories and formal systems as devices with which we reliably discover thruths is only one possible application.

Insisting that a formal system must be sound with respect to an "intended interpretation" can have the unfortunate effect of holding back development. For example, in order to discover non-Euclidean geometry someone had to contradict the dogma that Euclid's geometry was obviously true, and suggesting a theory which was non-Euclidean (which was considered obviously unsound) amounted to taking a professional career risk.

Sometimes there is no intended interpretation because we are exploring a new mathematical theory with which we have very little experience. In such a situation we will attempt to identify possible axioms and hope that their consequences will inform us about what is going on.

Sometimes we simply do not know what the intended interpretation is, and so we have to make a choice about accepting or rejecting an axiom based on other criteria than truth. Or better, we do not make a choice and study several options, without obsessing about "intended model". The most famous example of this is the axiom of choice in set theory. We know that set theory with choice is consistent if, and only if, set theory without choice is consistent. Which one is sound? On what grounds do we decide whether the axiom of choice is "true in the intended interpretation"?

So what is wrong with your view? I don't think much is wrong, except that it can hinder mathematical development. I advocate the position that the so called "intended interpretation" is in general an unknowable and uncommunicable entity whose existence is grounded in history and collective social norms. Of course, this does not imply that the "intended interpretation" is completely useless. On the contrary, it binds mathematicians together and allows them to share intuitions, and give coherence to mathematical development. But let us not confound an informal mathematical idea of "intended interpetation" with its mathematical ideal of a model.
> 5 votes

# Answer
Yes, that's too much to ask.

It is not trivial to define an interpretation, i.e. a model where $F$ is true, in the general case.

Consider Frege's naive set theory. To most people, it looks extremely natural. It basically "only" says that:

* (comprehension) for any property $p$ there exists a set $\\{x | p(x)\\}$,
* (membership) $y \in \\{x|p(x)\\}$ iff $p(y)$

Yet, it is inconsistent because of Russel's paradox. If we take $p(x) = (x\notin x)$, and $A = \\{x|p(x)\\}$, we get

$$ A \in A \iff p(A) \iff A \notin A $$

which is contradiction.

Other famous paradoxes are famous because they start from "seemingly true" axioms.

Burali-Forti proves that the class of ordinals can not be a set, which may seem counterintuitive at first.

Contradictions like Girard's paradox are more involved, but are surprising since they start from quite reasonable assumptions. If we consider, in type theory, an axiom like $\*:\*$ stating that the universe of types is one of its types, one might still expect that some paradox will arise, because the "circularity" of the universe could allow something similar to Russell's paradox. However, Girard's paradox even works in $\lambda U$ where we only have $\*:\square:\Delta$ without any circularity! The issue comes, roughly, from the impredicativity of such universes. It is not at all obvious that impredicativity alone, without circularity, is inconsistency.
> 3 votes

---
Tags: logic
---


# Question
Title: Minimal representation of an AND with two-input NOR
Let $x\_1,x\_2,x\_3,x\_4$ be boolean variables (i.e $x\_i \in \\{0,1\\}$)

Consider $f(x\_1,x\_2,x\_3,x\_4) = x\_1 \wedge x\_2 \wedge x\_3 \wedge x\_4 $

I want to write $f$ in terms of two-input NOR gates. I.e, $\mbox{NR}(x,y)= \neg ( x \vee y ) $.

What is the minimum number of NOR gates to write it?

I found that it can be done with 9. Can it be done with less.

# Answer
Rather than describing the answer, I'm going to describe how you could write a program to find the answer.

Write a program to exhaustively check all functions that can be computed by circuits with 1 NOR gate, all functions that can be computed by circuits with 2 NOR gates, all functions that can be computed by circuits with 3 NOR gates, etc. This would give you the answer.

Here is more detail on how to do that. Represent a function by its truth table (i.e., a 16-bit vector). To find all function representable by $k$ NOR gates, enumerate all functions $f,g$ representable by $i,k-i$ NOR gates, respectively, and then compute the function $\neg (f \lor g)$, for all $0 \le i \< k$. Representing $f,g$ as a 16-bit bitvector, you can compute $\neg (f \lor g)$ in two instructions, then you add it to the set of achievable functions. If you represent that set of achievable functions as a bitvector of length $2^{16}$, adding a new function to the set can be done in a few instructions. So, each individual step will be very fast.

Overall, this computation should be feasible. In particular, this computation requires at most $(k-1) \times 2^{16} \times 2^{16} \le 2^{35}$ simple operations, and you are going to do this 8 times, for a total of at most $2^{38}$ simple operations. That should be doable in a few minutes or a few hours on a typical computer.

I leave it to you to implement this and discover the minimal representation you are seeking.
> 1 votes

---
Tags: boolean-algebra
---


# Question
Title: Linear Regression using a Neural Network
I am trying to create a regression model using a Neural Network. I am currently learning how to work with neural networks (deeplearning.ai) and so the model is not implemented using any existing frameworks like keras.

Based on what I have learned,

* the model is configured to use no activation function in the output layer (which, obviously, has only one node).
* Input is images of fashion articles (shirt, jackets etc).
* output predicts prices for input article images.
* Hidden layers all use ReLU.
* Random initialization is done for all weights.
* Cost function is Mean Squared Error: $$J = \frac{1}{2m}\sum\_{i=1}^m (a^{(i)} - y^{(i)})^2$$

Based on the formula for backpropogation, the last layer should get the error based on cost function. For a single example, we have: $$ \mathcal L = \frac{1}{2}(a - y)^2 $$ $$ error = \frac{d\mathcal L}{da} = (a - y) $$

where `L` is the loss function, `a` is the predicted value and `y` is the actual price of the article.

For the entire training set, we have (vectorized): $$ error = \frac{d\mathcal L}{dA} = (A - Y) $$ where `m` is the number of examples, `A, Y` are `(1 * m)` vectors where each value corresponds to each single example. `A` contains `m` predictions and `Y` has all the `m` prices.

Is this `error` value correct?

My problem is that the model converges to a what appears to be a local minima. The error after a few 100 iterations gets stuck. The error is also not very small (~ 0.0005). I am not sure if I have the equations right.

# Answer
> 1 votes
No. This is not the correct way to train such a network. To update the network, we want to update the weights of the network. Thus instead of using $\frac{d\mathcal L}{dA}$ to update the weights, you should be using $\frac{d\mathcal L}{dW}$, where $W$ are the weights. This could be computed as

$$\frac{d\mathcal L}{dW} = \frac{d\mathcal L}{dA} \times \frac{d\mathcal A}{dW},$$

where $\frac{d\mathcal L}{dA}$ is computed using the formula you obtained ($\frac{d\mathcal L}{dA} = A-Y$ is correct), and where $\frac{d\mathcal A}{dW}$ is computed using backpropagation through the network.

Or, better yet, use an existing framework that performs automatic differentiation for you (e.g., Keiras, Tensorflow), and save yourself a lot of effort.

---
Tags: neural-networks
---


# Question
Title: Find an asymptotic bound for $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$
Given is the following recurrence relation:

$T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$

where $k$ is some constant and $n = 2^t$ for some $t\in \mathbb{Z}$.

I'm trying to find an asymptotic bound for $T(n)$.

**My work so far:**

First, I've tried to guess and prove by induction. Then, I tried to solve using a recursion tree, but I couldn't find any obvious pattern to follow.

# Answer
Assuming an appropriate base case, you can prove that $T(n) \leq \frac{3}{2} n^2$. (If this doesn't work for the base case, just increase $3/2$ to a large enough constant.)

Indeed, assuming this holds for $m \< n$, we have $$ \begin{align\*} T(n) &= n^2 + T(\tfrac{n}{2}) + T(\tfrac{n}{4}) + \cdots + T(\tfrac{n}{2^k}) \\ &\leq n^2 + \frac{3}{2} \frac{n^2}{4} + \frac{3}{2} \frac{n^2}{4^2} + \cdots + \frac{3}{2} \frac{n^2}{4^k} \\ &= n^2 \left(1 + \frac{3}{2} \left(\frac{1}{4} + \frac{1}{4^2} + \cdots + \cdots + \frac{1}{4^k}\right)\right) \\ &\< n^2 \left(1 + \frac{3}{2} \cdot \frac{1}{3}\right) \\ &= \frac{3}{2} n^2. \end{align\*} $$
> 1 votes

---
Tags: asymptotics, recurrence-relation
---


title: Short pipeline or long pipeline

text:
# Question
Title: Short pipeline or long pipeline
What is meant by a short pipeline?

Does that mean the instructions are split into small number of pieces OR length of a piece is short?

# Answer
If by *pieces* one means possible *stages* that the *instruction* can be split into. For example, like this "short" *Classic RISC pipeline* with *five stages*:

* **Fetch Instruction Stage**: *Fetch* the *instruction*.
* **Decode Instruction Stage**: *Decode* the *instruction*.
* **Execute Stage**: *Execute* the *instruction*.
* **Memory Access Stage**: Access (read/write from/to) the *memory*.
* **Writeback Stage**: Write results to the *CPU registers*.

Then a **short pipeline** means that the *instruction* is split into **a low amount** of these *stages* (*pieces*), but the *amount of hardware* and *time spent* in each *stage* will actually **increase** (*length of the pieces*) compared to if there were more *stages*.
> 3 votes

---
Tags: cpu-pipelines
---


# Question
Title: Would hypercomputation machines be capable of simulating/computing/programming everything?
If uncomputable numbers existed, could this hypercomputation machines compute them? Could hypercomputation compute all types of uncomputable things? Even truly inconsistent things? Even things that cannot be described by any type of information (like a way of factorizing number 181 using classical mathematics, the mathematics we usually use, without changing nothing (without changing conditions, axioms, definitions...) of it, which it is clearly impossible)?

(I ask this because I was told by an important user in Physics Stack Exchange that this was possible for hypercomputation (if it existed), but later I spoke with other computer scientists and physicists and they told me that in no way this could happen. I can't contact the original scientist that told me that this was possible for hypercomputation, so maybe you can clear my doubts)

# Answer
I think you have an important misunderstanding about what "uncomputable" means. It doesn't mean "doing something mathematically impossible", such as producing a non-trivial factorization of a prime number. There simply are no integers other than $1$ and $181$ that divide $181$ and it doesn't matter what method of computation you use, you will never find these non-existent factors because they just don't exist. The factoring problem is not uncomputable: you can write a computer program that will correctly factorize any number that you give it. In the case of $181$, the program will just say, "The factors are $1$ and $181$ and that's all."

A problem is uncomputable if there is no Turing machine ("computer program") that can solve it. The standard example is what's called the halting problem: you have a computer program and you want to know if it will terminate, or get stuck in an infinite loop. Turing's famous result is that there is no Turing machine that will take the description of another Turing machine as input and correctly say either "this terminates" or "this loops forever".

Some models of hypercomputation can solve this problem. That is, the "hypercomputer" can decide whether given Turing machine will terminate. However, Turing's proof is very general and applies to any sufficiently powerful model of computation. So, although the hypercomputation model might be able to solve the halting problem for Turing machines, Turing's proof can be easily adapted to show that the hypercomputer cannot solve its own halting problem. That is, there is no hypercomputer program which takes as input the source code of another hypercomputer program and correctly determines whether that program will halt.

In summary, every sufficiently powerful model of computation has uncomputable problems, so no model of hypercomputation can compute everything.
> 4 votes

---
Tags: computability, logic, programming-languages, hypercomputation
---


# Question
Title: $O(n \log n)$ simple polygon triangulation via divide and conquer
I am looking for the simplest possible $O(n \log n)$ algorithm for triangulating a simple polygon. It seems like there should be a simple divide and conquer variant that would fit the bill, ideally one avoiding auxiliary data structures such as trapezoidal decompositions. Indeed, all that would be required is an $O(n)$ algorithm for finding a roughly balanced diagonal. However, I am unable to find any algorithms that are as simple as I (perhaps naively) imagine should exist; nearly all the research is focused on $o(n \log n)$ algorithms, nearly all of which operate via trapezoidal decomposition.

# Answer
Garey, Johnson, Preparata and Tarjan came up with a simple $O(n\log n)$ algorithm back in 1978. It is described in many lecture notes, for example these lecture notes of Piotr Indyk.
> 2 votes

# Answer
I was looking for such a diagonal as well. As I could not find a simple way to obtain it we applied a linear time cutting of the polygon (Sutherland–Hodgman approach). Given a simple polygon $P$ we take a vertical line $\ell$ and cut through $P$. This can be done if $O(n)$ time by simply iterating over the boundary list of $P$ and verify if $\ell$ is crossed. This produces a set of sub-polygons. Clearly the number of vertices of the polygons to the left of $\ell$ is equal to the number of vertices on the right side of $\ell$, up to a constant at least. Then we triangulated each sub-polygon. Since there are vertices in the sub-polygons due to the cutting we had to also add a repair step to get rid of these additional vertices. For more details look directly at our work.
> 1 votes

---
Tags: computational-geometry, divide-and-conquer
---


# Question
Title: What to do with empty set during NFA to DFA conversion?
I am currently converting this NFA to a DFA

I have come up with the following DFA:

```
        0      1
->A    {A}    {B}
  B    {CA}
*CA    {A}    {AB}
 AB    {CA}   {B}

```

Although, I have no idea what to put for B. In the NFA, upon the B receiving 1 input, it goes nowhere - assumable unaccepted by the NFA. Do I send the DFA to a new, dead state upon receiving input 1 whilst in B?

I can try it:

```
        0      1
->A    {A}    {B}
  B    {CA}   {}
*CA    {A}    {AB}
 AB    {CA}   {B}
 {}    {}     {}

```

But is this correct by the rules of DFA?

# Answer
> 3 votes
Creating a new sink state is perfectly fine. The empty set is also a subset of all states.

In most DFA diagrams this state is omitted for simplicity.

# Answer
> 1 votes
According to the subset construction, the state you go to from state $\\{B\\}$ when you read character $1$ is the set of all states that the original NFA can go to when it's in one of the states in $\\{B\\}$ (i.e., it's in state $B$) reads $1$. This set of states is $\emptyset$, since the NFA has no transitions from $B$ for symbol $1$.

So this actually answers both of your questions at once: it's what you do with $\emptyset$ and it's the dead state you need (you can check from the definition that $\emptyset$ really is a dead state in the DFA.

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


# Question
Title: Why does the concatenation operation imply the empty string?
I'm a noob reading Michael Sipser's Introduction to the Theory of Computation, and I'm at a part where he's demonstrating how to construct finite automata that accept languages described by regular expressions. He does this by giving regular expressions, breaking them down into simpler regular expressions that represent the constituent pieces of the whole expression, creating a finite automata for each piece of the expression, and finally connecting them with the finite automata at the bottom that accepts the language described by the regular expression.

One of his examples is the sequence of finite automata in the picture attached, meant to illustrate how one might work through creating a finite automata that accepts the regular expression $(a\cup b)^\* aba$.

With his definitions of union, concatenation, and star below.

Concatenation: $A+B=\\{xy\mid x\in A\wedge y \in B\\}$

Star: $A\* = \\{x\_1x\_2...x\_k \mid k\geq 0 \wedge x\_i \in A\\}$

Union: $A\cup B = \\{x\mid x\in A\vee x\in B\\}$

At one point in the book he explains that two characters next to one another with no symbol between can imply concatenation so I am interpreting the "$aba$" piece as $a+b+a$.

I would think a finite automata that accepts $aba$ would have four states, with an "$a$" transition arrow between the first and second states, a "$b$" transition arrow between the second and third states, and an "$a$" transition arrow between the third state and the accept (fourth) state. The diagram instead is similar to what I imagined but adding a state with an empty string transition arrow between each state I described. See the 5th diagram, given for expression $aba $below $(a \cup b)^\*aba$ illustrating how one might go about constructing a finite automaton that accepts the language described by that regular expression."\>

These states with associated empty string transition arrows appear in both of the regular expression examples with concatenation he gives, so I must be misunderstanding something. There's a section in the book when he introduces nondeterministic finite automata in part of an effort to prove that regular languages are closed under the concatenation operation and mentions that "In general, an NFA may have arrows labeled with members of the alphabet or $\varepsilon$", and I figure the answer must have something to do with that, but I still don't understand why.

# Answer
> 1 votes
An $\varepsilon$ transition (called the empty transition from here on out) from $A$ to $B$ means that if you end up in $A$ after a transition you can go to $B$ for free *without* consuming a character from the input.

When concatenating $a$ and $b$, $a$ may have multiple end states so it is easier to add an empty transition from every end state of $a$ to the start state of $b$.

You can make the rule so when you concatenate all outgoing transitions of the start state of $b$ is copied to every end state of $a$ and if the start state of $b$ is not an end state then the end states of $a$ are not end states of the concatenated NFA.

This is a much more complicated rule than: every end state of $a$ is no longer an end state and gets a new empty transition to the start state of $b$.

Adding the empty transitions does not change the language being accepted and you can do a minimization/optimization pass after constructing the NFA to eliminate the excess empty transitions.

This is actually a common practice in compilers, the early code generation is dumb and does the obvious, easy and non-optimal but correct thing. Then optimization passes look for patterns that can be simplified or optimized. This means that the pattern can be optimized everywhere even when it wasn't generated by the construct that commonly creates it.

---
Tags: finite-automata, regular-expressions
---


title: what is the meaning of hit time?

text:
# Question
Title: what is the meaning of hit time?
```
Average memory access time = Hit time + Miss rate * miss penalty

```

Assume a computer with only one cache level. What is the exact meaning of hit time? Is it the number of clock cycles to access data from cache? OR Clock cycles to execute an instruction? How does the number of clock cycle per instruction come into this equation?

# Answer
> 1 votes
First of all your equation is for the hierarchical cache where you have to search entire cache in any case irrespective of hit or miss.
For simultaneous cache the first term in right hand side will be multiplied by hit time as well. Hit time is nothing but the time taken to sense the presence of data in cache if there is.

# Answer
> 2 votes
It's back to the mechanism of cache. When the cpu wants a data in cache, try to read data from cache. If there is the data in cache, It will fetch data from cache. This time of reading data from cache (the different between the speed of cache memory and register!) will be denoted by `Hit time`.

If the wanted memory in the related instruction does not exist in the cache memory, it should be read from RAM, hence, it takes more cpu clock to read the specified address and this time is calculated by the multiplication of the `miss rate` and the penalty of this miss in time of reading data from RAM which is denoted by `miss penalty`.

---
Tags: cpu-cache, memory-access
---


# Question
Title: Determining cycle time and and hold time in logic circuits
First I have general question. In a circuit with both logic and D edge flip flop does hold time have to satisfy $t\_{hold} \< t\_{setup}($D-FF$) + t\_{pd-min}$(Logic),

or is it enough that $t\_{hold} \le t\_{setup}($D-FF$) + t\_{pd-min}$(Logic) ?

Also i have a question about a specific circuit:

with the following times:

the question is how much time at least, before and after the fall of the clock does the Input have to be steady? when it is given that $t\_{hold}=8ns$

Now, from what I know, the input has to be kept steady for at least $t \< t\_{pd-min}$(Logic) +$t\_{setup}$ time. So I don't understand how $t\_{hold}$ comes into consideration here. I'll be glad if could explain.

# Answer
Well if someone is interested I have solved the question myself.

First of all, it indeed is possible that $t\_{hold} = t\_{setup} + t\_{pd-min}$.

And about the input time, it has to satisfy: $$t\_{hold} \le t\_{pd-min}(logic) + t\_{input-valid-min}$$

since $t\_{hold} = 8ns$ and $t\_{pd-min}(Logic) = 10ns$ , even $t\_{input-valid-min} = 0$ satisfies this.
> 0 votes

---
Tags: algorithms, optimization, computer-architecture, logic
---


# Question
Title: DFA that rejects $a^{23}$ but accepts $\{a^i|i\geq 24\}$
Construct a DFA $M$ with $\Sigma = \\{a\\}$ and max. 11 states so that $a^{23}\not\in L(M)$ but $\\{a^i|i\geq 24\\}\subset L(M)$.

I don't see how it is possible? Because it's a DFA and the alphabet only contains $a$, shouldn't I only be able to look at modulo 11? I could make 1 mod 11 not accepting but then $a^{34}$ would not be accepted as well.

EDIT: The prof confirmed it was a typo. We are looking for a NFA. Thanks everyone!

# Answer
> 6 votes
This is not possible. A DFA on a one symbol alphabet is a directed graph with out-degree 1. The walk one follows from the start state consists of a (possibly zero length) path followed by a cycle. As all sufficiently long strings are accepted, all states in the cycle must accept. If the DFA has at most 11 states, a walk of length 23 must be in the cycle, so it must accept.

More generally, if a DFA on one symbol rejects $a^n$ but accepts all $a^m$, $m\>n$, then it must have at least $n+1$ symbols and start with a path of length $\ge n$, the $n$th state rejecting, followed by a cycle of accepting states of length $\ge 1$.

# Answer
> 4 votes
Solomonoff's answer points out that no such DFA exists.

This answer shows that we can build a nondeterministic finite automaton (NFA) that satisfies the requirement, indicating that the original problem might be intended for NFA instead of DFA.

The following nondeterministic finite automaton (NFA) has 7 states whose only accepting state is its start state. The language it accepts is $\\{a^{5m+7n}\mid m,n\ge0\\}=\\{\epsilon,a^5, a^7, a^{10}, a^{12}, a^{14}, a^{15}, a^{17}, a^{19}, a^{20}, a^{21}, a^{22}\\}\cup\\{a^n\mid n\gt 23\\}$. $(23 = 5\*7-5-7)$ In other words, it rejects $a^{23}$ and accepts all $a^n$ for $n\>23$.

The above image is made using automatonsimulator.com. This answer is motivated by Hendrik Jan's comment.

---

Interested readers can further prove that 7 is the minimal number of states in an NFA that rejects $a^{23}$ and accepts all $a^n$ for $n\>23$.

# Answer
> 0 votes
Even stronger: Let L be any language containing a^{24} but not a^{23}.

After n a’s, 0 \<= n \< 24, we are in a state where we accept a^{24-n} but not a^{23-n}, so these 24 states are all different.

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: Survivors classes in the extremely unlikely scenario of P = PSPACE
If its proven today that $P=PSPACE$ the whole polynomial hierarchy collapses. Moreover since $BQP \subseteq PSPACE$, it will also result in $P=BQP$.

However unlikely the above scenario is, hypothetically if this were the case what are the complexity classes (the most important ones) that will survive this collapse into $P$. The classes we are talking about:

1. Should be above $P$ (thus $L, NC, NL$ etc. could be temporarily ignored)
2. Are interesting and open enough to be studied (thus $E, EE, ALL$ etc. can be ignored)

We are concerned about both the traditional as well as Quantum Complexity classes.

# Answer
The time hierarchy theorem still tells us that $$\mathrm{P}\subsetneq \mathrm{EXP}\subsetneq\mathrm{2\text{-}EXP} \subsetneq \dots\\,,$$ and likewise for the analogous space classes and nondeterministic time and space classes.
> 1 votes

---
Tags: complexity-theory
---


title: Prove that a language is in co-NP

text:
# Question
Title: Prove that a language is in co-NP
For a homework assignment, I have to prove that a given language $L \in coNP$.

I understand that one way of doing so, would be to prove that $\bar{L} \in NP$, i.e. give a polynomial time verifier for $\bar{L}$.

I am having trouble understanding what the complement of the language would be. eg: if

$$L = \\{ (a, b, c) \in Z^{+} | \nexists \text{ } x \in Z^{+} \text{ s.t. } x \< a \\} $$

Then, is

$$\bar{L} = \\{ (a, b, c) \in Z^{+} | \exists \text{ } x \in Z^{+} \text{ s.t. } x \< a \\} $$

Or is $\bar{L}$ a different language? Do I take the complement of the left hand side of the pipe operator? That is, can $\bar{L}$ contain strings from $Z^{-}$ now?

# Answer
> 1 votes
Languages are defines with respect to a finite alphabet. Thus, integers cannot be represents just by giving a triplet as you suggest, you need to *encode* it.

For convenience, let's assume a decimal encoding, with the "$-$" sign for negation, and the character $\\#$ separating the numbers. Thus, for example, the word $8\\#12\\#-3$ represents the triplet $(8,12,-3)$ (note that usually we would use a binary encoding, but it doesn't really matter). Call our alphabet $\Sigma$.

Now, a word $w$ is in the language you describe iff the following hold:

1. $w=a\\#b\\#c$ where $a,b,c$ are either words in {0,...,9}^*$\setminus {0}^*. That is, they represent positive numbers (we allow leading 0's here, but we could also formulate without them).
2. There does not exist $x\in \mathbb{Z}\_+$ such that $x\<a$.

Note that we did not do anything yet, just wrote down the language. In particular, we purposely ignore the fact that condition 2 simply means that $a\le 1$.

The formal complement of your language is the set of words that either don't satisfy condition 1, or don't satisfy condition 2 (or both).

You could write this more succinctly or more explicitly, as words that are either not of the form $a\\#b\\#c$ with the condition 1 above, or words that are of that form, but where $a$ is not of the form $0^\*1$.

It should be mentioned that once you are familiar with the notion of languages, we usually don't dig down to this level of formality, and in fact we would ignore the encoding somewhat. Then, you might see things such as $\overline{L}=\\{(a,b,c)\in \mathbb{Z}: \exists x\in \mathbb{Z}\_+ \wedge x\<a\\}$.

Also note that throughout this answer we do not distinguish between a word and its numeric value, but if you really want to nitpick, then such a distinction should be made.

# Answer
> 0 votes
NP and co-NP are classes of problems where every instance of the problem has an answer that is either "yes" or "no".

A problem is in NP if for every instance where the answer is "yes", there is a hint that can be used to prove the answer is "yes" in polynomial time. (The hint can be extremely difficult to find, but you don't need to find it, you just need to show that if the answer is "yes" then such a hint exists).

A problem is in co-NP if for every instance where the answer is "no", there is a hint that can be used to prove the answer is "no" in polynomial time. (The hint can be extremely difficult to find, but you don't need to find it, you just need to show that if the answer is "no" then such a hint exists).

There are equivalent formulations: For NP: Whenever the answer is "yes", there is a proof that the answer is "yes" which can be checked in polynomial time. For co-NP: The same with "yes" replaced by "no".

---
Tags: complexity-theory, formal-languages
---


# Question
Title: Why don't we use quick sort on a linked list?
Quick sort algorithm can be divided into following steps

1. Identify pivot.
2. Partition the linked list based on pivot.
3. Divide the linked list recursively into 2 parts.

Now, if I always choose last element as pivot, then identifying the pivot element (1st step) takes $\mathcal O(n)$ time.

After identifying the pivot element, we can store its data and compare it with all other elements to identify the correct partition point (2nd step). Each comparison will take $\mathcal O(1)$ time as we store the pivot data and each swap takes $\mathcal O(1)$ time. So in total it takes $\mathcal O(n)$ time for $n$ elements.

So the recurrence relation is:

$T(n) = 2T(n/2) + n$ which is $\mathcal O(n \log n)$ which is the same as in merge sort with a linked list.

So why is merge sort preferred over quick sort for linked lists?

# Answer
> 22 votes
The memory access pattern in Quicksort is random, also the out-of-the-box implementation is in-place, so it uses many swaps if cells to achieve ordered result.
At the same time the merge sort is external, it requires additional array to return ordered result. In array it means additional space overhead, in the case if linked list, it is possible to pull value out and start merging nodes. The access is more sequential in nature.

Because of this, the quicksort is not natural choice for linked list while merge sort takes great advantage.

The Landau notation might (more or less, because Quicksort is still $\mathcal O(n^2)$) agree, but the constant is far higher.

In the average case both algorithms are in $\mathcal O(n\log n)$ so the asymptotic case is the same, but preference is strictly due to hidden constant and sometimes the stability is the issue (quicksort is inherently unstable, mergsort is stable).

# Answer
> 5 votes
You can quick sort linked lists however you will be very limited in terms of pivot selection, restricting you to pivots near the front of the list which is bad for nearly sorted inputs, unless you want to loop over each segment twice (once for pivot and once for partition). And you will need to keep a stack of the partition boundaries for the lists you still need to sort. That stack can grow to $O(n)$ when pivot selection is bad along with the time complexity growing to $O(n^2)$.

Merge sort on linked lists can be executed using only $O(1)$ extra space if you take a bottom-up approach by counting where the boundaries of the partitions are and merging accordingly.

However adding a single 64 element array of pointers you can avoid that extra iteration and sort lists of up to $2^{64}$ elements in $O(1)$ additional extra space.

```
head = list.head;
head_array = array of 64 nulls

while head is not null
    current = head;
    head = head.next;
    current.next = null;
    for(i from 0 to 64)
        if head_array[i] is null
            head_array[i] = current;
            break from for loop;
        end if
        current = merge_lists(current, array[i]);
        head_array[i] = null;
     end for
end while

current = null;
for(i from 0 to 64)
    if head_array[i] is not null
        if current is not null
            current = merge_lists(current, head_array[i]);
        else
            current = head_array[i];
        end if
     end if
 end for

 list.head = current;

```

This is the algorithm that the linux kernel uses for sorting its linked lists. Though with some extra optimizations like ignoring the `previous` pointer during all but the last merge operation.

# Answer
> -2 votes
You can write merge sort , partition sort , tree sort and compare results
It is quite easy to write tree sort if you allow some extra space
For tree sort each node of linked list must have two pointers even if we sort singly linked list
In linked list i prefer inserting and deleting instead of swapping
Hoare partition can be done only for doubly linked list

```
program untitled;

type TData = longint;
     PNode = ^TNode;
     TNode = record
                data:TData;
                prev:PNode;
                next:PNode;
             end;

procedure ListInit(var head:PNode);
begin
  head := NIL;
end;

function ListIsEmpty(head:PNode):boolean;
begin
  ListIsEmpty := head = NIL;
end;

function ListSearch(var head:PNode;k:TData):PNode;
var x:PNode;
begin
  x := head;
  while (x <> NIL)and(x^.data <> k)do
     x := x^.next;
  ListSearch := x;
end;

procedure ListInsert(var head:PNode;k:TData);
var x:PNode;
begin
  new(x);
  x^.data := k;
  x^.next := head;
  if head <> NIL then
     head^.prev := x;
   head := x;
   x^.prev := NIL;
end;

procedure ListDelete(var head:PNode;k:TData);
var x:PNode;
begin
   x := ListSearch(head,k);
   if x <> NIL then
   begin
     if x^.prev <> NIL then
        x^.prev^.next := x^.next
      else
        head := x^.next;
     if x^.next <> NIL then
        x^.next^.prev := x^.prev;
     dispose(x);
   end;
end;

procedure ListPrint(head:PNode);
var x:PNode;
    counter:longint;
begin
  x := head;
  counter := 0;
  while x <> NIL do
  begin
    write(x^.data,' -> ');
    x := x^.next;
    counter := counter + 1;
  end;
  writeln('NIL');
  writeln('Liczba elementow listy : ',counter);
end;

procedure BSTinsert(x:PNode;var t:PNode);
begin
  if t = NIL then
    t := x
  else
    if t^.data = x^.data then
            BSTinsert(x,t^.prev)
        else if t^.data < x^.data then
            BSTinsert(x,t^.next)
        else
            BSTinsert(x,t^.prev);
end;

procedure BSTtoDLL(t:PNode;var L:PNode);
begin
   if t <> NIL then
   begin
     BSTtoDLL(t^.next,L);
     ListInsert(L,t^.data);
     BSTtoDLL(t^.prev,L);
   end;
end;

procedure BSTdispose(t:PNode);
begin
   if t <> NIL then
   begin
    BSTdispose(t^.prev);
    BSTdispose(t^.next);
    dispose(t);
   end;
end;

procedure BSTsort(var L:PNode);
var T,S:PNode;
    x,xs:PNode;
begin
  T := NIL;
  S := NIL;
  x := L;
  while x <> NIL do
  begin
    xs := x^.next;
    x^.prev := NIL;
    x^.next := NIL;
    BSTinsert(x,t);
    x := xs;
  end;
  BSTtoDLL(T,S);
  BSTdispose(T);
  L := S;
end;

var i : byte;
    head:PNode;
    k:TData;
BEGIN
  ListInit(head);
  repeat
     writeln('0. Wyjscie');
     writeln('1. Wstaw element na poczatek listy');
     writeln('2. Usun element listy');
     writeln('3. Posortuj elementy drzewem binarnym');
     writeln('4. Wypisz elementy  listy');
     readln(i);
     case i of
     0:
     begin
       while not ListIsEmpty(head) do
            ListDelete(head,head^.data);
     end;
     1:
     begin
       writeln('Podaj element jaki chcesz wstawic');
       readln(k);
       ListInsert(head,k);
     end;
     2:
     begin
       writeln('Podaj element jaki chcesz usunac');
       readln(k);
       ListDelete(head,k);
     end;
     3:
     begin
       BSTsort(head);
     end;
     4:
     begin
        ListPrint(head);
     end
     else
        writeln('Brak operacji podaj inny numer');
     end;
  until i = 0;
END.

```

This code needs some improvements
Firstly we should limit extra storage to the recursion needs
then we should try to replace recursion with iteration
If we want to improve algorithm further we should use self balancing tree

# Answer
> -2 votes
Quicksort
Maybe I will show steps for quicksort

If list contains more than one node

1. Pivot selection
2. Partition list into three sublists
first sublist contains nodes with keys less than pivot key
second sublist contains nodes with keys equal to pivot key
third sublist contains nodes with keys greater than pivot key
3. Recursive calls for sublists which contain nodes not equal to pivot node
4. Concatenate sorted sublists into one sorted list

Ad 1.
If we want to choose pivot fast the choice is limited
We can choose head node or tail node
Our list have to have poiner to the node if we want our pivot
be accessible fast otherwise we have to search for node

Ad 2.
We can use queue operations for this step
Fist we dequeue node from original linked list
compare its key with pivot key and enqueue node to the correct sublist
Sublists are created from existing nodes and there is no need to
allocate memory for new nodes

Pointer to the tail node will be useful because queue operations
and concatenation run faster with presence of this pointer

---
Tags: algorithms, algorithm-analysis, sorting, quicksort
---


# Question
Title: Handling epsilon productions in recursive descent parsing
I am working on a recursive descent parser for lambda calculus. In my grammar, after removing left-recursion, I am left with the following two productions:

```
# APPLICATION  -> ATOM APPLICATION'
# APPLICATION' -> ATOM APPLICATION' | ε

```

Both APPLICATION and APPLICATION' correspond to the same type of node in the AST. How should I handle parsing the second production? I know that choosing between two alternatives for a production is performed by looking up the next token in buffer, but the epsilon production confuses me.

EDIT:

Here is current implementation (Ruby) that fails to left-associate applications.

```
require_relative 'token.rb'
require_relative 'ast.rb'

class Parser
    def self.call(tokens)
        new(tokens).send(:parse_expr)
    end

    def self.to_proc
        method(:call).to_proc
    end

    private
        def initialize(tokens)
            @tokens = tokens
            @l = -1
        end

        def parse_expr
            if lookahead.type == :tklambda
                return ExprNode.new([parse_abstraction], @l)
            else
                return ExprNode.new([parse_application], @l)
            end
        end

        def parse_abstraction
            match_token(:tklambda)
            id = parse_identifier
            match_token(:tkdot)
            expr = parse_expr
            return AbstrNode.new([id, expr], @l)
        end

        def parse_identifier
            id_token = match_token(:tkid)
            val = id_token.value
            return IdNode.new(nil, @l, val)
        end

        def parse_application
            left_child = parse_atom
            first_atom = [:tklparen, :tkid] # FIRST(ATOM)
            # application -> atom application'
            while !lookahead.nil? and first_atom.include?(lookahead.type)
                return AppNode.new([left_child, parse_application], @l)
            end
            # application' -> atom application' | ε
            return left_child
        end

        def parse_atom
            if lookahead.type == :tklparen
                match_token(:tklparen)
                expr = parse_expr
                match_token(:tkrparen)
                return AtomNode.new([expr], @l)
            else
                return AtomNode.new([parse_identifier], @l)
            end
        end

        def match_token(type = nil)
            if !type.nil? and lookahead.type != type
                raise "Unexpected token at #{@l + 1}. Expected: #{type}, "\
                      "got: #{lookahead.type}."
            end
            @l += 1
            return @tokens[@l]
        end

        def lookahead
            return @tokens[@l + 1]
        end
end

```

# Answer
> 0 votes
You need to know FOLLOW(APPLICATION'), and it has to be disjoint to FIRST (ATOM).

Actually, you only have to know that the sets are disjoint, in which case the epsilon action becomes the default.

Personally, I wouldn't bother with two functions:

```
Application:
    v := Atom()
    if lookahead token in FIRST(ATOM):
        return ApplyNode(v, Application())
    else:  (* default case *)
        return v

```

That corresponds with your grammar, but it might not correspond with your intended language. Normally, lambda application is left-associative, not right-associative, but of course it is impossible to express left-associative expressions with an LL(k) grammar. Fortunately, it is easy to write a recursive descent parser which left-associates. That's usually done with a local variable and a `while` loop: (Technically, the parser is doing a tree-rewrite in order to fix the associativity, but the mechanism is so simple that hardly anyone sees that it is even there.)

```
  Application:
     v := Atom()
     while lookahead token is in FIRST(Atom):
         v := ApplyNode(v, Atom())
     return v

```

---
Tags: formal-grammars, lambda-calculus, recursion, parsers
---


# Question
Title: Algorithm for minimizing the number of "inversions" in a graph
## Given the **following graph**:

With the assumptions below:

* A node on the left is linked to **several nodes** on the right
* Nodes on the right are **paired together**: one is black, one is white
* Each pair of nodes on the right can be **swapped** (black becomes white and white becomes black)
* A node on the left is **green** if linked to **only white** or **only black**; **red** if linked to **two colors**.

The idea is to **minimize the amount of red nodes**, by flipping some black and white nodes. **What is the best algorithm to do that?**

(I think this problem has something to do with some sort of cycle detection? This problem is probably well-known on some equivalent form.)

Of course it will be often impossible to make all nodes green; here node V can never be (it is linked to B0 and B1). Some cycles also make all green impossible.

**Extra question** — same as above, but with a weight associated to each edge. Minimize the sum (for each node) of absolutes delta between white and black (difference between the sums of weights for white and black for each left node).

---

## Where does this problem comes from?

A transit network is composed of *stops*, *routes* and *trips*.

* Each trip belongs to one route
* Each trip has one natural direction (0 or 1, inbound/outbound)
* Each trip goes through a list of stops.
* The direction of all trips within a route is arbitrary; so it is possible to invert the direction of all trips of a given route (but all trips together).

If all trips passing through a stop do have the same direction (all 0 or all 1) we can compute a "natural" direction for the stop. Otherwise we cannot. The idea is to flip route trips direction to minimize the number of stops where we cannot compute this "natural" direction.

Here the nodes on the left are stops, pair of nodes on the right routes, with black/white all trips for each route direction.

# Answer
You can reduce MAX-2-SAT to your problem. Therefore, your problem is NP-complete.

In MAX-2-SAT we have $n$ boolean variables $x\_1, \dots, x\_n$ and $m$ clauses of the form $a\vee b$ where $a$ and $b$ are $x\_i$ or $\bar{x\_i}$ (its complement). The goal is to assign $0$, and $1$ values to $x\_i$'s such that the number of true clauses is maximized. This problem is NP-complete. For an arbitrary instance of MAX-2-SAT, we build an instance of your problems as follows. Hence, your problem is also NP-complete, *i.e.*, kind of no chance for a polynomial-time algorithm for all cases.

We put $n+m$ pair of nodes ($x\_i$ and $\bar{x\_i}$ for $1\leq i\leq n$, and $y\_k$ and $\bar{y\_k}$ for $1\leq k\leq m$) on the right side and $3m$ node on the left (three nodes $v\_{k,1}, v\_{k,2}, v\_{k,3}$ for $k$'th clause where $1\leq k\leq m$). Let $(x\_i\vee x\_j)$ be the $k$'th clause in our instance (other cases are similar). We put three nodes $v\_{k,1}, v\_{k,2}, v\_{k,3}$ in the left side of our graph. We then connect

* $v\_{k,1}$ to $x\_i$ and $x\_j$,
* $v\_{k,2}$ to $x\_i$, $\bar{x\_j}$, and $y\_k$,
* $v\_{k,3}$ to $\bar{x\_i}$, $x\_j$, and $y\_k$.

At most one of the $v\_{k,1}, v\_{k,2}, v\_{k,3}$ can gets a green color. Moreover, this happens if and only if the clause gets a true value. Therefore, the maximum number of green nodes in the instance of your problem is equal to the solution to MAX-2-SAT.

Your bonus problem is harder than the original version and is also NP-complete.
> 1 votes

---
Tags: algorithms, graphs, weighted-graphs
---


# Question
Title: Listing all prime numbers less than an integer N
I am trying to solve this problem listing all prime numbers less than an integer but using the smallest amount of memory.

Is it possible to solve this problem using a smaller amount of memory?

```
int main ()
{
    int n = 10000;
    for (int i=2; i<n; i++)
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0)
                break;
            else if (j+1 > sqrt(i)) {
                cout << i << " ";
            }
        }
    return 0;
}

```

# Answer
Yes, but only after we have stated what is considered memory used by an algorithm or program.

For this particular problem, I would like to use one of the simplest choices. The memory used by the program is the extra or temporary space used excluding the input and output. Furthermore, each variable (that does not share its storage with others) uses a unit of space. One might argue the output should count towards memory usage. My point is to let us choose a usage model so that we can concentrate on the most relevant and interesting part, although in another situation, how to reduce the memory used by the output might be the more significant part.

Here is the snippet that use 3 units of memory, where I remove the call to `sqrt(i)`. Each of $n$, $i$, $j$ uses 1 unit of memory. I comment out the output code to make it clear that its memory usage is not considered.

```
int n = N; // N should be given elsewhere
for (int i=2; i<n; i++)
    for (int j=2;; j++)
    {
        if ( j*j > i) {
            // cout << i << " ";
        }  else if (i % j == 0)
            break;
    }

```

But wait, how can we check `j*j > i`? Even if we assume the computing machine can compute `j*j` magically without using extra memory, it still needs to store the result of `j*j` so as to compare with `i`. So it is only reasonable that we add 1 or more unit of memory usage here. Then how about `i % j`? We would like add 1 or more unit of memory usage here.

If we dig deeper, we will ask whether those `2` and `0` in the program count towards memory or not. We may have to ask during the program execution, doesn't it need to use some space to remember where it is executing and how to jump around? If those memory are needed, can we reuse them during different execution time?

The more we study this way, the more uncertain the answer becomes. This is, in fact, the truth. It is almost impossible to get an accurate usage of memory theoretically unless we have an accurate model of storage and computation specified down to the bit. When we do have that accurate model, an accurate analysis to the bit may become so tedious and distracting we might lose the big picture.

The way out to get a healthy picture is the big $O$ or $\Theta$ notation. We will simply say that this program use $O(1)$ or $\Theta(1)$ memory. That is, for a reasonable model of storage and computation, there is a constant $C$, for any give $N$, the program will use less than $C$ units of memory. In practice, we usually mean a small or reasonable $C$.

---

By the way, the program in the question misses primes 2 and 3.
> 0 votes

---
Tags: algorithms, primes
---


# Question
Title: Multiple inputs in lambda calculus (Confusing example)
In a programming class I take, we briefly (very briefly) touched lambda calculus. I think I have a pretty good grasp of the basics now, but one example given I just don't understand. Am I missing something or is the example possibly false?

$\lambda x.x \\; (\lambda y.2\*y) \\; square \\; 3$

The solution to this was $6$, because $\lambda x.x$ (the first function) is applied to $square$ (the first input) which just "disappears" and $\lambda y.2\*y$ is applied to $3$, which gives us $6$:

$\lambda x.x \ (\lambda y.2\*y) \ square \ 3 \implies (\lambda y.2\*y) \ 3 \implies 2 * 3 \implies 6$

***EDIT***

Regardless of whether the "disappearance" of $square$ is correct, why would the first step be to apply $\lambda x.x$ to $square$ ? Instead of the whole expression, or just the part in parenthesis (which would, afaict, give the same result). I.e., what way of parenthesising is implied from the way it's written above?

***/EDIT***

The way I understand it, it should be either 18, because:

$\lambda x.x \\; (\lambda y.2\*y) \\; square \\; 3$ with parenthesis should be:

$(((\lambda x.x \\; (\lambda y.2\*y)) \\; square) \\; 3)$ which gives me:

$(((\lambda y.2\*y) \\; square) \\; 3) \implies ((2\*square) \\; 3) \implies 2 * square(3) \implies 2 * 9 \implies 18$

or nothing at all, i.e. $((2\*square) \\; 3)$ doesn't make sense.

Another example that was given:

$(\lambda f.(\lambda x.f(f \\; x))) \\; square \\; 3 \implies (\lambda x.square(square \\;x)) \\;3 \implies square(square \\; 3) \implies square(9) \implies 81$

This second example seems clear to me, I'm just adding it to show something similar.

How would one properly solve $\lambda x.x \\; (\lambda y.2\*y) \\; square \\; 3$ ?

# Answer
The problem is in (most likely wrongly) parenthesising expressions.

$\lambda$ abstraction goes as far right as it can, so your whole example is **just one abstraction** with body $x\ (\lambda y. 2 \cdot y)\ \texttt{square}\ 3$, meaning that there is nothing to be applied to $\lambda x$, thus no "level-0" redexes. ~~There is just one redex in here, namely $\require{enclose} \enclose{horizontalstrike}{(\lambda y. 2\cdot y)\ \texttt{square}}$, reducing to $\require{enclose} \enclose{horizontalstrike}{(2\cdot \texttt{square})}$.~~ There is also no redexes within the body because if we fully parenthesise the original expression (having in mind that $\lambda$ applications (within the body) are left associative) we get $$\lambda x. \biggl(\Bigl(\bigl(x\ (\lambda y. 2 \cdot y)\bigr)\ \texttt{square}\Bigr)\ 3\biggr)$$

---

If we want to make it reduce to $6$, we must completely ignore $\texttt{square}$, because no natural number squared gives $6$. We can do that by making it an input to abstraction that doesn’t use it. $$\bigl(\lambda x.(\lambda y.\ 2 \cdot y)\bigr)\ \texttt{square}\ 3$$
> 1 votes

# Answer
In $\lambda$-calculus, every abstraction (= function) is unary.

For this reason, $square$ is the argument replacing $x$ and once it only remains the body of the function, 3 can be supplied as argument, replacing $y$.

Let's follow each step:

1. $\lambda x.x (\lambda y.2 * y) \ square \ 3$
2. $\beta$-reducing the first redex $\lambda x.x (\lambda y.2 * y) \ square$ gives the following result:

$square (\lambda y.2 * y) \ 3$

From here on, we would need the $\lambda$-definition of $square$, but I would imagine it would only accept a single argument, the base.

The problem is that the argument 3 would then be passed to the result of this redex $square (\lambda y.2 * y)$, differently from the hint that 3 would be passed to $(\lambda y.2 * y)$ and afterwards the $square$ would be executed.

If instead, the $\lambda$-term would have been defined in the following ways, it would have had much more sense; I still cannot understand how $square$ can completely disappear from the computation.

1. $\lambda xy.x (2 * y) \ square \ 3 \implies square(2\*3) \implies 36 $
2. $\lambda xy.2 * x y \ square \ 3 \implies 2\*square(3) \implies 2 * 9 \implies 18$
3. $\lambda xyz.x(yz) \ square \ (\lambda y.2 * y) \ 3 \implies square((\lambda y.2 * y) \ 3) \implies square(2\*3) \implies square(6) \implies 36$

The second example is perfectly fine to me.
> 0 votes

---
Tags: lambda-calculus, functional-programming
---