# Question
Title: Is Morse Code binary, ternary or quinary?
I am reading the book: "Code: The Hidden Language of Computer Hardware and Software" and in Chapter 2 author says:

> Morse code is said to be a binary (literally meaning two by two) code because the components of the code consists of only two things - a dot and a dash.

Wikipedia on the other hand says:

> Strictly speaking it is not binary, as there are five fundamental elements (see quinary). However, this does not mean Morse code cannot be represented as a binary code. In an abstract sense, this is the function that telegraph operators perform when transmitting messages (see quinary).

But then again, another Wikipedia page includes Morse Code in 'List of binary codes.'

I am very confused because I would think Morse Code actually is **ternary**. You have 3 different types of 'possibilities': a silence, a short beep or a long beep.

It is impossible to represent Morse Code in 'stirct binary' isn't it?

By 'strict binary' I mean, think of stream of binary: 1010111101010.. How am I supposed to represent a silence, a short beep and / or a long beep?

Only way I can think of is 'word size' a computer implements. If I (and the CPU / the interpreter of the code) know that it will be reading 8 bits every time, then I can represent Morse Code. I can simply represent a short beep with a 1 or a long beep with a 0 and the silences will be implicitly represented by the word length.(Let's say 8 bits..) So again, I have this 3rd variable/the 3rd asset in my hand: the word size.

My thinking is like this: I can reserve the first 3 bits for how many bits to be read, and last 5 bits for the Morse code in a 8bit word. Like 00110000 will mean 'A'. And I am still in 'binary' BUT I need the word size which makes it ternary isn't it? The first 3 bits say: Read only 1 bit from the following 5 bits.

Instead of binary, if we use trinary, we can show morse code like: 101021110102110222 etc.. where 1 is: dit 0 is: dah and 2 is silence. By using 222 we can code the long silence, so if you have a signal like \*- \*--- \*- you can show it like: 102100022210, but it is not directly possible using only with 1's and 0's UNLESS you come up with something like a 'fixed' word size as I mentioned, but well this is interpreting, not saving the Morse Code as it is in binary. Imagine something like a piano, you have only the piano buttons. You want to leave a message in Morse Code for someone and you can paint buttons to black. There is no way you can leave a clear message, isn't it? You need at least one more color so you can put the silences (the ones between characters and words. This is what I mean by trenary.

*I am not asking if you can represent Morse Code in 57-ary or anything else.*

I have e-mailed the author (Charles Petzold) about this; he says that he demonstrates in Chapter 9 of "Code" that Morse Code can be interpreted as a binary code.

Where am I wrong with my thinking? Is what I am reading in the book, that the Morse Code being a Binary a fact or not? Is it somehow debatable? Why is Morse Code is told be quinary in one Wikipedia page, and it is also listed in **List of Binary Codes** page?

Edit: I have e-mailed the author and got a reply:

-----Original Message-----

From: Koray Tugay Sent: Tuesday, March 3, 2015 3:16 PM

To: cp@charlespetzold.com

Subject: Is Morse Code really binary?

Sir, could you take a look at my question here: Is Morse Code binary, ternary or quinary? quinary ?

Regards, Koray Tugay

From: "Charles Petzold"

To: "'Koray Tugay'"

Subject: RE: Is Morse Code really binary? Date: 3

Mar 2015 23:04:35 EET

Towards the end of Chapter 9 in "Code" I demonstrate that Morse Code can be interpreted as a binary code.

I am not hiding his e-mail address as it is really easy to find on the web anyway.

# Answer
# Morse code is a prefix ternary code (for encoding 58 characters) on top of a prefix binary code encoding the three symbols.

*This was a much shorter answer when accepted. However, considering the considerable misunderstandings between users, and following a request from the OP, I wrote this much longer answer. The first "nutshell" section gives you the gist of it.*

Contents

## In a (big) nutshell

When asking "Is Morse Code binary, ternary or quinary?" there is no comparing possible answers unless one fixes some criteria for an acceptable answer. Indeed, without proper criteria, one can contrive explanations for nearly any kind of structure. The criteria I have chosen are the following:

* it should reflect the three-tiered description of Morse-code with the dot/dash representation in the second tier;
* it should fit the presentation and mathematical tools developed for the theoretical analysis of codes, as much as possible;
* it should be as simple as possible;
* it should clearly make apparent the properties of the Morse code.

This is intended to preclude arbitrary hacking, that ignores basic concepts of code theory as scientifically studied, and which may have some appeal by giving an illusion of systematic analysis, though addressed too informally to be conclusive. This site is supposed to be about *computer science*, not programming. We should use a minimum of established science and accepted concepts to answer a technical question.

A quick analysis of the standard shows that **all symbols used in Morse code are ultimately coded in binary**, since it is transmitted as a string of units of equal length, whith a signal that can be on or off for each unit. This indicates that Morse messages are ultimately coded in a logical alphabet $\Sigma\_1=\\{0,1\\}$.

But that says nothing of the internal structure of the code. The information to be encoded is a string on an alphabet of 58 symbols (according to the standard) including 57 characters and a space. This corresponds to an alphabet $\Sigma\_3=\\{A,B,\dots,Z,0,1,\dots,9,?,=,\dots,\times,@,\[\\;\]\\}\\;$, the last symbl being the space.

However, the standard specifies that there is an intermediate alphabet $\Sigma\_2$, based on `dot` and `dash` and possibly other symbols. It is quite clear

* that strings in $\Sigma\_3^\*$ are to be coded as strings in $\Sigma\_2^\*$, and
* that strings in $\Sigma\_2^\*$ are to be coded as strings in $\Sigma\_1^\*$

So, given that there is no choice for $\Sigma\_1$ and $\Sigma\_3$, the question must be understood as: "**What number of symbols should we consider in the intermediate alphabet $\Sigma\_2$ so as to best axplain the structure and the properties of the whole Morse code,**" which also entails specifying the two encodings between the three levels.

Given the fact that the Morse code is a prefix homomorphic (variable length) code that precludes any ambiguity when decoding a signal, we can explain simply this essential property with a **ternary alphabet** $\Sigma\_2=${`dot`, `dash`, `sep`}, and two coding scheme $C\_{3\to 2}$ from $\Sigma\_3$ to $\Sigma\_2$, and $C\_{2\to 1}$ from $\Sigma\_2$ to $\Sigma\_1$, which are both homomorphic and prefix, thus both unambiguous codes, and thus able to be composed to give an unambiguous prefix encoding of the 58 symbols into binary.

Hence **Morse code is composed of a prefix ternary code expressed in the alphabet** $\\{$ `dot`, `dash`, `sep` $\\}$**, with these three symbols themselves encoded in binary** with the following codewords:

`dot` $\to 10$, `dash` $\to 1110$, and `sep` $\to 00$

Note that what is known as the space between consecutive `dot` or `dash` is actually included in the representation of `dot` and `dash`, as this is the usual mathematical representation for such types of codes, which are usually defined as string homomorphisms from source symbols to codewords expressed with target symbols, as I just did.

This departs a little from some of the presentation given in the standard, which aims more at specifying intuitively the code for users, rather than at analysing it for its structural properties. But the encoding is the same in both cases.

Even without the precise timings of the standard, a decoder of the analog signal could still translate it into the ternary alphabet we suggest, so that the above understanding of the ternary code would still be valid.

## Codes: basic points

This answer is based on the Standard ITU-R M.1677-1, dated October 2009 (thanks to Jason C for the reference). I shall use the terminology `dot` and `dash`, rather than `dit` and `dah`, as it is the terminology used by this standard.

Before we start discussing the Morse code, we need to agree on what a code is. The difficult discussions on this question obviously requires it.

Fundamentally, information needs to be represented in order to be transmitted or otherwise processed. **A code is a system to translate information from one system of representation into another**. This is a very general definition. We must be careful not to confuse the concept of a *representation*, and that of a *code* from one representation (the *source*) to another (the *target*).

A representation can take many forms, such as variable electric voltage, colored dots on paper, string of characters, numerals, binary strings of 0's and 1's, etc. It is important to distinguish between analog and formal (or logical, or abstract) representation.

An analog/physical representation is a drawing, a varying voltage level, a shape (for a letter).

A logical/formal/abstract representation is a mathematical representation with abstract graphs, strings of symbols, or other mathematical entities.

Though some information may originally be analog, we usually convert it to a logical representation so as to be able to define precisely its processing by mathematical means, or by people.

Conversely, we dealing with logical representation using physical devices, such as computer or transmitters, we need to give an analog form to the logical representation.

For the purpose of this analysis, the only analog form we consider is that used for transmission, as described in the standard. But even then, we will consider that the first step is to interpret this analog representation as a direct implementation of an identically structured logical representation, on which we build our analysis of what kind of code Morse code may be. Code theory is a mathematical body of knowledge based on the analysis of logical representations.

However we shall come back on the analog/logical transition in the discussion at the end.

## Codes: definitions

Our logical view is that the code is used to translate sources strings on an source alphabet $S$ to a target alphabet $T$. It is often the case that both alphabets are identical, usually binary, when the purpose is to add some extra property to the representation of information, such as making it more resistant to errors (error detection and correction), or making the representation smaller by removing redundancy (lossless code compression) and possibly with carefully controled loss of some information (lossy compression).

However, the purpose of Morse code is to provide only a way to represent strings on a large alphabet, into strings based on a much smaller alphabet (actually binary), using an intermediate alphabet almost binary (dots and dashes) to better adapted to human perception and manipulative abilities. This is achieved by what is called **variable-length code**:

> Using terms from formal language theory, the precise mathematical definition is as follows: Let $S$ and $T$ be two finite sets, called the source and target alphabets, respectively. A code $C: S \to T^\*$ is a total function mapping each symbol from $S$ to a sequence of symbols over $T$, and the extension of $C$ to a homomorphism of $S^\*$ into $T^\*$, which naturally maps each sequence of source symbols to a sequence of target symbols, is referred to as its extension.

We call **codeword** the image $C(s)\in T^\*$ of a symbol $s\in S$.

A variable-length code $C$ is **uniquely decodable** if the corresponding homomorphism of $S^\*$ into $T^\*$ is *injective*. That means that any string in $T^\*$ can be the image of at most one string in $S^\*$. We also say that the code is **unambiguous**, meaning that any string can be unambiguously decoded, if at all.

A variable-length code is a **prefix code** if no codeword is the prefix of another. It is also alled *instantaneous code*, or *context-free code*. The reason for these names is that, when reading a target string that begins with a codeword $w$ of a prefix code, you recognize the end of the codeword as soon as you read its last symbol, without having to know/read the next symbol. As a consequence, prefix codes are unambiguous and very easy to decode fast.

It is easily shown that unique decodability and the prefix property are closed under composition of codes.

Note that the definition as a homomorphism implies that **there is no special separation between codewords.** It is their structure, such as the prefix property, that allows identifying them unambiguously.

Indeed, if there were such separation symbols, they would have to be part of the target alphabet, since they would be necessary to decode string from the target alphabet. Then it would be quite simple to revert to the theoretical model of variable-length code by appending the separator to the preceding code word. If that were to raise contextual difficulty (due for example to multiple separators), that would only be a hint that the code is more complex than apparent. This is a good reason to stick to the theoretical model described above.

## The Morse code

The Morse code is described in the standard at three levels:

* 3 . it is intended to provide an encoding of natural language text, using 57 characters (27 letters, 10 digits, 20 synbols and ponctuations) and an inter-word space to cut the character string into words. The inter-word space is used like a special character, that can be mixed with the others, which I shall note `SEP`.
* 2 . all of these characters are to be encoded as successions of `dash` and `dot`, using an inter-letter space, which I shall note `sep`, to separate the `dash` and `dot` of one letter from those of the next letter.
* 1 . The `dash` and `dot`, as well as `sep` are to be encoded as signal or absence of signal (called spacing) with length precisely defined in terms of some accepted unit. In particular, the `dash` and `dot` encoding a letter must be separated by an inter-element space, that I shall note *`σ`*.

This already calls for a few conclusions.

The message to be transmitted and received in analog form is a successions of length units (space length or time length), such that a signal is on of off for the whole duration of each unit as specified in the Annex 1, Part I, section 2 of the standard:

```
2   Spacing and length of the signals
2.1 A dash is equal to three dots.
2.2 The space between the signals forming the same letter is equal to one dot.
2.3 The space between two letters is equal to three dots.
2.4 The space between two words is equal to seven dots.

```

This is clearly an analog encoding in what is known as a bit stream, which can be logically represented in binary notation by a string of `0` ans `1`, standing for the analog *off* and *on*.

In order to abstract away issues related to analog representation, we can thus consider that Morse code messages are transmitted as bit strings, that we shall note with `0` and `1`.

Hence the the above excerpt from the standard can be expressed logically as:

* 0 . A `dot` is represented by `1`.
* 1 . A `dash` is represented by `111`.
* 2 . An inter-element space *`σ`* is represented by `0`.
* 3 . An inter-letter space `sep` is represented by `000`.
* 4 . An inter-word space `SEP` is represented by `0000000`.

So we could see Morse code as using 5 code words in binary to encode these 5 symbols. Except for the fact that this is not quite how the system is described, there is some more to it, and it is not the most convenient way it can be thought of, from a naive or a mathematical point of view.

Note also that this description is intended for laymen, not code theory specialists. For that reason it describes more the visible appearance than the internal structure that justifies it. It has no reason to preclude other descriptions that are compatible with this one, though mathematically more structured, to emphasize the properties of the code.

But first, we should note that the complete description of the code involves 3 levels of representation, immediately recognizable:

* 3 . The text, composed of a string of characters, including `SEP`.
* 2 . The encoding of a letter string as a string of `dot`, `dash` and `sep`.
* 1 . The encoding of a level 2 string of these three `symbols` as a binary string.

We may possibly discuss as to what symbols is encoded in what, but it is an essential aspect of Morse code that it has these three levels of representation, with characters at the top, `dot`s and `dash`es in the middle, and bits `0` and `1` at the bottom.

This implies that there are necessarily two codes, one from level 3 to level 2, and the other from level 2 to level 1.

## Analysing the three levels of representation

In order to have a consistent analysis of this 3-tiers coding system, we should first analyse what kind of information is relevant at each level.

* 1 . The bit string, by definition, and by necessity of its analog representation, is composed only of `0` and `1`.
* 3 . At the text level, we need and alphabet of 58 symbols, including the 57 characters and the inter-word space `SEP`. All 58 of them have to have ultimately a binary encoding. But, though the Morse code standard specifies these 57+1 characters, it does not specifies how they should be used to encode information. That is the role of English and other natural languages. The Morse code provides other system with an alphabet of 58 symbols, on which they could build some 58-ary code, but **Morse code is not itself a 58-ary code.**
* 2 . At the `dot` and `dash` level, all we need is these two symbols in order to code the 57 characters, i.e. provide a codeword for each as a string of `dot` and `dash`, together with some separator `sep` to mark when one letter finished, and another start. We also need some means of encoding the inter-word space `SEP`. We might try to provide for it directly at leavel 1, but this would mess-up the otherwise tier-structured organization of the code.

Indeed, the description of the standard might rightly be criticized for doing just that. But the authors may have thought that their presentation would be simpler to grasp for the average user. Also it follows a traditional description of Morse code, that predates this kind of mathematical analysis.

This calls for several remarks:

* at level 3, the letter level, the inter-letter space `sep` is no longer meaningful. This is quite normal, since it has no more meaning in the universe of letters than the space separating two written characters on paper. It is necessary at level 2 to recognize codewords representing the letters, but that is all.
* similarly at level 2, the inter-element space *`σ`* is no longer meaningful. It has no meaning in the world of `dot` and `dash`, but is only necessary at level 1 to identify the binary code words representing `dot`, `dash`. But at level 1, it is not distinguishable from the bit `0`.

So the inter-element space *`σ`* is no longer anything special. It is just one use of `0`.

However, as explained previously, if the code $\Sigma\_2^\*\to\Sigma\_1^\*$ is to be analyzed using knowledge of variable length codes, separators should be appended into the codewords they follow, so as to define the code as a simple string homomorphism.

This implies the following partial specification of the code: `dot`$\to$`10` and `dash`$\to$`1110`

The level 2 alphabet $\Sigma\_2$ needs at least one other symbol, the inter-letter space noted `sep`, which should be `000` according to the letter of the standard. However, the definition of the variable length code as a homomorphism required appending the inter-element space `0` to each codeword for `dot` and `dash`. Hence we must have only `00` as codeword for `sep`, so that toghether with the ending `0` from the preceeding `dot` or `dash`, it makes 3 `0` as required by the standard. This always work since there is no provision in the standard for having two inter-letter separators following each other.

This is enough to encode the alphabet $\Sigma\_2=${`dot`, `dash`, `sep`} with a homomorphic code $C\_{2\to 1} : \Sigma\_2\to\Sigma\_1^\*$ defined as follow:

* `dot`$\to$`10`
* `dash`$\to$`1110`
* `sep`$\to$`00`

And we have the good surprise to discover that no codeword is a prefix of another. Hence we have a prefix code, which is unambiguous and easy to decode.

We can now proceed similarly to define the code $C\_{3\to 2}: \Sigma\_3\to\Sigma\_2^\*$.

The standard uses strings of `dot` and `dash` as codewords for the characters in $\Sigma\_3$, in the way given by the tables of the standard for example `dot` `dot` `dash` `dot` to represent the letter $f$.

Again, these codewords are separated by inter-letter spaces. In order to define the code as a homomorphism, we must include the separator in the codewords, so that the definition of the homomorphism becomes rather: $f\to$ `dot` `dot` `dash` `dot` `sep`

This applies to each of the 57 characters in the alphabet $\Sigma\_3$. But again we also need the word separator `SEP`, which, according to the standard, is `0000000`. We first note that already 3 bits `0` are provided by the code, 2 by the `sep` that ends the last letter of the word, and 1 by the `0` bit that end the last `dot` or `dash` of the encoding of that last letter. Hence `SEP` must ultimately be coded as the remaining `0000`.

But to respect the tiered approach, `SEP` should be encoded in some codeword from $\Sigma\_2^\*$. Since `sep` is binary encoded as `00`, it follow that `SEP` can be encoded as `sep` `sep`.

Hence we can encode the alphabet $\Sigma\_3=\\{A,B,\dots,Z,0,1,\dots,9,?,=,\dots,\times,@,$ `SEP`$\\}$, with a homomorphic code $C\_{3\to 2} : \Sigma\_3\to\Sigma\_2^\*$ defined as follows:

* $A \to$ `dot` `dash` `se`p
* $B \to$ `dash` `do`t `dot` `dot` `sep` ...
* $Z \to$ `dash` `dash` `dot` `dot` `sep` ...
* $7 \to$ `dash` `dash` `dot` `dot` `dot` `sep` ...
* `SEP` $\to$ `sep` `sep` (for the word separator)

And we have the further surprise to see that no codeword is a prefix of another. Hence the code $C\_{3\to 2}$ is a prefix code too.

Since the prefix property is closed under composition of codes, the Morse code $C\_{Morse}= C\_{2\to 1}\circ C\_{3\to 2}$ is a prefix code.

We can thus conclude that the **Morse code can be understood, and easily analyzed, as the composition of a prefix binary encoding of a 3 symbols alphabet {`dot`, `dash`, `sep`} into a binary alphabet, and a prefix encoding of a 58 symbol alphabet (57 characters and one space) into the 3 letters alphabet.**

The composition itself is a prefix encoding of the 58 symbols into a binary representation.

## Remarks on this analysis.

It is always difficult to establish that a presentation of a structure is the best one can come up with. It seems however that the above analysis meets the criteria set up at the beginning of this answer: closeness to the 3-tiered definition, formally presented according to current coding theory, simplicity, and evidencing the main properties of the code.

Note that there is little point in looking for error correction properties. The Morse code may not even detect a single bit error as it may simply change two `dot` into one `dash`. However, it causes only local errors.

Regarding compression, the ternary encoding was designed to approximately reduce the number of dots and dashes, in an approximative kind of Huffman coding. But the two composed codes could easily be made denser.

Regarding the size of alphabets, there is no choice for the binary and the 58 symbols alphabet. The intermediate alphabet could contains more symbols, but what would be the purpose?

However, some people would be inclined to recognize the space `DET` at level 2, thus making the alphabet **quaternary**, then using it directly at level 3, encoded as itself in level 2.

This would meet the standard definition, for `DET` encoded in binary as `0000`. But it would prevent the analysis of the binary encoding $C\_{2\to 1}$ as a prefix code, making it harder to show that $C\_{Morse}$ is a prefix code, hence unambiguous.

Indeed, such a choice would make the binary string `0000` ambiguous, decodable as either `SEP` or as `sep` `sep`. The ambiguity would have to be resolved with a contextual rule that `sep` cannot follow itself, making the formalization more complex.

## The importance of analog to logical transition.

This analysis relies heavily on the fact that the decomposition of the on/off signal into units of equal lengths indicates clearly an analog representation of a binary string. Furthermore, the lengths in units are exactly right for the above analysis, which seems unlikely to have happened by chance (though it is possible).

However, from a (too cursory) look at the original patent 1647, it does not seem to have been that precise, with sentences such as (on top of page 2):

> The sign of a distinct numeral, or of a compound numeral when used in a sentence of words or of numerals, consists of a distance or space of separation between the characters of greater extent than the distance used in separating the characters that compose any such distinct or compound numeral.

People who were later sending by hand or receiving by ear were also unlikely to be that precise either. Indeed, their *fist*, i.e. their timing, was often recognizable. This view is also supported by the fact that spacing lengths are not always respected, particularly when learning Morse code.

These situations correspond to an analog view of the code as short signal (dot), medium signal (dash), and short, medium and long pause. Direct transposition into a logical alphabet would naturally give a *quinary* alphabet, into which the 58 symbols have to be coded. This of course is no longer a 3-tiered presentation of the Morse code.

However, in order to make sense (and possibly avoid ambiguity), this alphabet should be used with the constraint that two signal symbols (`dot` or `dash`) cannot follow each other, and that pause symbols cannot follow each other either. Analysis of the code and its properties would be made more complex, and the natural way to simplify it would be to do what was done: introduce proper timings to turn it into the composition of two codes, leading to the fairly simple analysis given above (remember that it includes showing the code is prefix).

Furthermore, it is not strictly necessary to follow exact timings in the analog representation. Since the decoder of the analog translation can distinguish short, medium and long pauses, by whatever means, it should just mimic what was done in the binary case. Hence short and medium signal (necessarily followed by a pause) are recognized as logical `dot` or `dash`. Short pauses are forgotten, as only serving to mark the end of `dot` or `dash`. Medium pauses are recognized as `sep`, and long pauses are recognized as two `sep` in succession. Hence the analog signal is represented in a ternary alphabet, which can be used as before to encode the 58 symbols alphabet. Our initial analysis can be used even when timings are not strictly respected.

Alternatively, the signal-pause alternance could be used to turn this quinary alphabet into a ternary one, keeping only the three durations as symbols of the alphabet, and using contextual analysis to determine whether a given duration is signal or pause. But this is again a bit complex to analyze.

This just shows that there are many ways to look at things, but they are not necessarily convenient, and may not all lend themselves easily to analysis with the mathematical tools that have been developed to analyze codes.

More references to the patents can be found on the Internet.

# Conclusion

Given the precise timings of the standard, a good answer seems to be to consider Morse code as the composition of a ternary prefix encoding (of 58 characters) into a 3 symbols alphabet, composed with a binary prefix encoding of these three symbol.

Without the precise timing of the standard, the binary level can no longer be considered. Then the analog to logical decoding naturally takes place at the level of the intermediate alphabet of `dot` and `dash`. However, the analog to logical decoder can stil decode to the previous 3 symbols alphabet, thus preserving the applicability of our analysis.
> 23 votes

# Answer
*This answer isn't as long as it looks; this site just puts a lot of spacing between list items! Update: Actually it's getting pretty long...*

Morse Code isn't "officially" binary, ternary, quaternary, quinary, or even 57-ary (if I count correctly). Arguing about which one it is without context is not productive. It is up to *you* to define which of those five it is *based on your application and the encoding requirements for your specific situation*. To that end, there are pros and cons to each symbol set size, which you should consider for your situation before making a decision.

For the basis, M.1677, the international Morse Code standard, section 2, defines timings as:

> **2 Spacing and length of the signals**
> **2.1** A dash is equal to three dots.
> **2.2** The space between the signals forming the same letter is equal to one dot.
> **2.3** The space between two letters is equal to three dots.
> **2.4** The space between two words is equal to seven dots.

Note that that defines timings only, e.g. a dash does not mean the same thing as three dots, it is simply the same length. The base unit of time is a dot.

---

## Binary

We can choose binary if we'd like. It is possible to represent Morse Code with "strict binary", as you call it -- that author's approach was to assign the digits to "dot" and "dash". That approach does not work and I do not think the author has a firm grasp of Morse code. But there is a different approach that works. If we choose binary, we essentially represent whether the signal is high or low with each symbol occupying a single dot-lengthed time slice. Note that this is also the approach described on the List of Binary Codes page you cited.

Other binary codings can be chosen as well (e.g. Bob Jarvis' answer) at the expense of increases in difficulty decoding back to audible Morse Code (Bob's encoding cannot be decoded statelessly, for example, the tradeoff is it provides shorter encoded sequences).

**Symbols:**

* Low, off, etc. (0)
* High, on, etc. (1)

**Encoding Examples:**

* Signal separator: 0
* Letter separator: 000
* Word separator: 0000000
* Three dots: 10101
* Three dashes: 11101110111
* The word "son": 101010001110111011100011101
* The phrase "is a": 10100010101000000010111

**Pros:**

* Minimal symbol set size
* Easily managed with typical digital logic
* Easy to decode into audible Morse Code (presuming no validation is done); stateless decoding and does not require storing information about the timing of symbols (every symbol is the same length).

**Cons:**

* Long encodings.
* Many opportunities for invalid encodings.
* Individual symbol meanings (0, 1) depend on context.

---

## Ternary

With this choice, we define letter and word spacings as rests, and signal spacings are implicit (although you could choose to require dot length rest symbols between signals, if it suits you better).

**Symbols:**

* Dot-length rest (0)
* Dot (1)
* Dash (2)

**Encoding Examples:**

* Letter separator: 000
* Word separator: 0000000
* Three dots: 111
* Three dashes: 222
* The word "son": 11100022200021
* The phrase "is a": 11000111000000012

**Pros:**

* Small symbol set size.
* Signal separator no longer needed.
* Shorter encoding lengths than binary.
* Removes some invalid encodings (e.g. 0110 with the binary choice no longer possible).

**Cons:**

* Still lengthy encodings.
* Still many possibilities for invalid encodings, in particular, the rests.
* Cannot be decoded statelessly unless you choose to place explicit dot length rests between signals.
* Signal separators are implicit unless you choose to place explicit dot length rests between signals.
* Some individual symbol meanings (0) depend on context.

---

## Quaternary

**Symbols:**

* Letter separator (0)
* Word separator (1)
* Dot (2)
* Dash (3)

**Encoding Examples:**

* Three dots: 222
* Three dashes: 333
* The word "son": 2220333032
* The phrase "is a": 220222123

**Pros:**

* Very short encoded length.
* Possibility of invalid encodings is reduced.
* Symbols are semantically accurate.
* Arguably, more human-readable.

**Cons:**

* Large symbol set size.
* Cannot be decoded statelessly.
* Signal separators are implicit.

---

## Quinary

A direct interpretation of Wikipedia's list. Note this is very similar to the binary choice except the various valid combination of binary 0's or 1's are given their own symbols.

**Symbols:**

* Signal separator (0)
* Letter separator (1)
* Word separator (2)
* Dot (3)
* Dash (4)

**Encoding examples:**

* Three dots: 30303
* Three dashes: 40404
* The word "son": 303031404041403
* The phrase "is a": 3031303032304

**Pros (compared to quaternary):**

* Can be decoded statelessly.
* The only symbol set size that unambiguously, directly and concisely represents the five objects mentioned in section 2 of the standard: "dot" (to which all timings are relative to), "dash", "space between the signals", "space between two letters", "space between two words".

**Cons (compared to quaternary):**

* Higher possibility for invalid encodings.
* Increased encoding lengths without adding extra information (tradeoff is decoding ease).
* Not *as* easy to decode as the binary choice, in that each symbol is a different length in time and this association must be maintained somewhere.

---

## 57-ary:

Included for completeness.

**Symbols:**

* 26 letters
* 10 numbers
* 20 punctuation marks and miscellaneous signs
* Word separator (space)

**Encoding Examples:**

* The word "son": `son`
* The phrase "is a": `is a`

**Pros:**

* Shortest encoding
* Human readable
* Invalid encodings are impossible.

**Cons:**

* Largest symbol set
* Difficult to decode into Morse Code; necessary to maintain tables of Morse Code output sequences for each symbol and necessary to detect word boundaries and adjacent letters to determine where to insert various rests.
* Impossible to expand beyond the Morse Code specification without adding new symbols (tradeoff for being immune to invalid encodings).
* Signal and letter separators are implicit.

---

## Termination

For storage as a symbol stream on a device, *if* you need to do that, it's worth noting that M.1677 defines message and transmission termination sequences. From Part II:

> **5** Every telegram shall be terminated with a cross signal (. – . – .)
> **6** The end of the transmission shall be indicated by the cross signal (. – . – .) followed by the *invitation to transmit* signal K (– . –)
> **7** The end of work shall be indicated by the station that transmitted the last telegram. The correct indication is the *end of work* signal (. . . – . –)

Unfortunately, the standard is silent on the ability to distinguish e.g. the string "+K" from the sequence (*end-of-telegram*, *invitation-to-transmit*). However, *end-of-work* is unique. If you are storing morse code, then, you will have to make a choice as to how you want to indicate the end of a stored sequence.

If you are storing an entire conversation, for example, and are using the binary symbol set, you could reasonably consider *end-of-work* to be the end of sequence indicator, represented as the unique bit sequence 101010111010111. You need to consider the type of data you are storing (e.g. message fragments, entire messages, entire conversations) as well as the facilities offered to you by your storage medium (e.g. ability to prefix with message length) before deciding. I suppose you could go so far as to define your own end of sequence indicator. In any case these are all matters of underlying storage and have too many possibilities to list here. The choice is really up to you based on whatever is appropriate for your situation.

---

*Cannot be decoded statelessly:* These encodings require some state to be maintained in order to decode into audible Morse Code. They all require "If preceding symbol was a dot/dash and current symbol is a dot/dash then insert signal separator". While you could try and "cheat" and automatically append a signal separator to all symbols while reducing word separator to 5 rests and letter separator to 1, M.1677 afaict does not explicitly prohibit consecutive word separators, which breaks this kludge.

*Signal separators are implicit:* This is directly related to the above note but more semantically oriented. These encodings have implicit signal separators in their notation. That is "zzz" is intuitively three separate z's, the boundaries are "piggybacked" on whatever it is that separates symbols in the encoding itself. Consider the description "three dots in a row"; intuitively we take this to mean three *separate* dots, but if separators weren't implied this could be taken to be indistinguishable from a dash. Only the Wikipedia-style binary and quinary (or ternary with the explicit signal separator option) representations remove all ambiguity and "shortcuts" here, which can be of great value depending on the situation. It is for this reason that there is a strong argument for the quinary choice.

---

## TL;DR:

As you can see, there are advantages and disadvantages to each, and *it's up to you to decide how you want to treat it based on your requirements*. There is no right answer. You could attempt to argue that one is more appropriate than the other in general, but these arguments would boil down to pedantic preferences, as without context, there is no correct answer.

Now, all that said, in my own opinion, the quinary choice is the representation that feels the most "right" to me for Morse Code itself (originally I had favored quaternary). It is the only choice that provides all of the following:

* Context-free symbols (a symbol on its own contains all information about its meaning without examining adjacent symbols).
* Representation of all primitives defined in M.1667.
* Separators (signal, letter, word) are not implied by notation or underlying encoding (this is important, if I wrote `{ dot, dot, dash }`, those `,`'s are significant and easy to overlook).

However, there are strong arguments for all. The arguments related to encoding are also applicable to the treatment of Morse itself. There is no 100% concrete answer, but it can certainly make a good topic for debate with your friends at the bar.

. . . – . –
> 30 votes

# Answer
Despite my initial thoughts on this, it turns out this question can be formalized in a way that admits a fairly precise answer (modulo a couple of definition issues). The answer turns out to be 3 or 4, i.e. ternary or quaternary. The crowd-pleaser "everything goes from 2 to 57" answer is correct only in the sense that if someone asks you for a characterization of abelian groups, you tell him they are sets.

Let's start by looking at the physical encoding for Morse code. That's actually BASK, i.e. binary amplitude-shift keying, which is just an elaborate way o saying there two physical (electrical/optical etc.) amplitude levels for us to encode our message. So, the immediate question is: doesn't this mean that answer is that Morse code is binary? Well, it's binary only in a rather non-informative way, in the sense that the binary on/off signal sent over the wire doesn't correspond *directly* to either lines or dots. At this vague level of correspondence, we could even send the ASCII code (with the direct, obvious bit encoding) and call it "Morse" and/or "binary"; the same would apply to any Huffman code (instead of ASCII).

So how can we make the correspondence more precise and at the same time formalize our question? Coding theory comes to help. Let $M$ be the set of "morsable" symbols, roughly 66 symbols if I understand the Morse code universe correctly; this includes the 26 Latin letters, the 0-9 digits, and a bunch of ancillaries like some punctuations, "prosigns" etc. It's actually not terribly important what these are. A code is an injective mapping $c:M\to T^\*$ where $T$ (not $T^\*$) is a set of codewords. To be physically representable in our underlying BASK hardware, we require that $T\subset \\{0,1\\}^\*$, i.e. our codewords need to be a strings of bits; note that this entails $c$'s values are strings of codewords, so strings of strings of bits, but ultimately linearized as just strings of bits.

To be a faithful characterization of Morse code, we need $T$ to contain some direct equivalents of lines and dots, in the sense that there must be a bijection between these codewords and the dots and lines representing Morse code on paper. $T$ is also required to be \[almost\] a uniquely decipherable code, meaning that any factoring of an element of $T^\*$ in terms of elements/codewords of $T$ \[ideally\] must be unique. (Note that some authors, e.g. Berstel, don't even call $T$ a code unless it is uniquely decipherable, but others, e.g. Steve Roman have a different terminology where any mapping is a code, but those that are uniquely decipherable are just said so and abbreviated UD codes. Here I'll just the latter terminology. You'll also see a bit later why I said "ideally".)

Since $c$ is only required to be an injection and not a surjection, we can populate $T$ with arbitrary "junk" beyond what's needed to get a UD code, as long as the strings generated by this junk aren't the preimage of anything morsable. For example, a string of exactly 42 dots doesn't correspond to anything in any variant of Morse code I saw. So when when we ask if the Morse code binary, ternary, quaternary, quinary etc., the question should is asking for the *minimal cardinality* of $T$ with the above two properties, i.e.: it is \[almost\] an UD code and we have an obvious bijection between the paper-based "line" and "dot" to some elements of $T$.

There a two ways to proceed in constructing $T$, either top-down by observing that you need a separator between the paper-based, line-dot representation of Morse letters in order to get a UD code, or bottom-up since in the ITU international Morse code we're given the time-lengths of the lines, dots, and various pauses. I'll use the latter approach here because there are numerous ways to get some $T$ otherwise, i.e. you can pick fairly arbitrary time-lengths, e.g. the defunct American Morse code used shorter lines than the ITU version.

Start let's with the ITU signal-length-derived representation which has five basic codewords, generated from the unit-length "on" signal (1) and "off" signal (0): `just-dot` (1), `just-line` (111), `unit-space` (0), `letter-space` (000), and `word-space` \[assumed seven 0's in the International Morse but can vary in practice\]. Immediately note that the `unit-space` can only appear *followed by a 1* only right after `just-dot` and `just-line`; and this $0$-termination of `just-dot` and `just-line` (which is a comma code; more on this later) is actually required otherwise you couldn't even tell apart lines from dots. This gives you the obvious reduction to four codewords with:

* `dit` = `just-dot` `unit-space` = 10 and
* `dah` = `just-line` `unit-space` = 1110.

So that's the quaternary Morse code: `dit`, `dah`, `letter-space`, `word-space`. The next observation is that the `word-space` can be approximated (or even assumed to be) two `letter-space`s, i.e. six zeros. So how that's how you get the ternary codeword set; As references for this line of reasoning see e.g. \[1\] \[2\].

There is also a technical reason to prefer the ternary codewords: $T = \\{10 , 1110, 000\\}$ is a uniquely decipherable code, in fact it is a prefix code. However $\\{10 , 1110, 000, 0^7\\}$ (or the version with just six zeros) is no longer uniquely decipherable because $0^{10}=0^30^7=0^70^3$ so there's a non-unique factorization. While this is theoretically a problem, it is of no practical concern because the human "metronome" has difficulty measuring very long silences anyway, so basically any silence longer than a certain length is assumed (by a human) to be a `word-space` of sorts.

Also note that if you stick $0$ in that set too (i.e. take "quinary" view), it gets "even more wrong", in the sense that even $000$ no longer has unique factorization (as itself is a code word too). Furthermore, $0$ is not in the preimage of any Morse symbol, so it is junk in $T$, much like you can add $1^{42}0$ to $T$; in fact adding the latter is less troublesome as unlike adding $0$ it won't make the code lose the UD property.

The reduction/abstraction from `dit`, `dah`, `letter-space` as binary codewords to three abstract symbols (trits) is useful for showing quickly that the (ternary) Morse code is UD; that's immediately obvious because `letter-space` acts as a comma, i.e. the ternary Morse code is a comma code. (Note that other authors define "comma code" in a more restrictive sense where all symbols other than the comma are the same one; I'm using it here in the wider sense given in D.H. Smith's "Post-modern algebra", which just means using a unique terminating symbol for ever codeword.) Also note that the comma0code technique is used at two levels in the Morse code; the `just-line` and `just-dot` are terminated by the "short comma" `unit-space`=$0$ to make them distinguishable from each other. Once you abstract that construction to the two different (`dit` and `dah`) trits, all the Morse code letters are also comma-coded by terminating them with $000$ which the third trit.

You can also use the trit approach calculate entropy assuming a `dah` and `dit` and `letter-space` are "equivalent" as trits \[3\], in the sense that—for example—'e' takes 2 trits and 'y' takes 5 trits. The abstract trit approach is not so useful if you care about how expensive each symbol is to actually transmit in the real BASK Morse encoding on a line. For the latter, you need to get down to the real bit lengths of the 3 (or 4) symbols, which are seen as just as transitions in an automaton. For instance the letter 'e' takes 5 bits to encode (as `dit` `letter-space`) while 'y' takes 17 bits (three `dah`s, one `dit` and a `letter-space`). This line of thinking goes back to Shannon (see pp. 3-4). More details can be found in Blahut's "Information Theory and Coding", e.g. he calculates "an average of 9.296 units of signaling time per source output letter" for Morse code using the (unconditional) probabilities of letter occurrences in English. For a slightly different exposition (by a zoologist!) you could look at J.P. Hailman's; he gets a different average (10.2) because he assumes slightly different probabilities for English letters, but otherwise his analysis is conceptually the same.

To summarize this: you can take several views of the Morse code, but some are more fruitful than others in saying anything interesting about it. I'm not aware of any analyses using the "quinary" view and in order for this model to *not* be reducible to four symbols you'd have to make some assumptions about the occurrence the unit-space that don't hold in actual Morse, e.g. that you could have two but not necessarily three adjacent unit-spaces (which is invalid Morse). The ternary view buys you a quick analysis of the unique decodability. The most deep/fruitful view is the one which sees the 3 or 4 symbols as actually represented by unequal amounts of bits as they are in the real Morse code (|`dit`|=2, |`dah`|=4, |`letter-space`|=3 and |`word-space`|=6 or 7); it's still insightful at this low-level to consider the ternary/quaternary symbols as transitions in an automaton.

As to why Wikipedia sucks on this... well on some topics it just does. Their main article on http://en.wikipedia.org/wiki/Coding\_theory is not really something I'd recommend reading either. I can't say much about the (Petzold) book you've mentioned other than it doesn't appear written by an expert in information theory. Petzold is correct only in the sense that if Morse-coded messages consisted of only one letter you could reasonably say they are in some binary code; if you want to send words though, you need a letter separator, otherwise the code would be horribly not UD, to the point of impracticality.

---

It's a bit late here for me to revise the entire post, but @babou makes a valid point below that apparently Shannon, Blahut and others have misinterpreted the (current) ITU standard (assuming it hasn't changed since their time) in the following technicality: the unit space is added between dits and dahs *of the same letter*, but only the `letter-space` is added between letters. This reading of the standard seems to check out based on a fairly recent practitioner's book. So we need to borrow one 0 from `letter-space` into each `dit` and `dah` when they are in terminal positions of a letter, leaving only two 0's for the `letter-space`, i.e. $T=\\{10, 1110, 00\\}$. That also means that (for example) the size of 'e' is only 4 bits, not 5.
> 5 votes

# Answer
Originally Morse code was intended to be written marks on a strip of paper, but telegraph operators soon became able to "read" the clicks of the equipment. This version of Morse (American or "land" Morse) had three "mark" elements, the dot, the dash, and the long dash.

The use of International Morse during the last century, via radio transmission, was usually encoded by hand (on a telegraph key) and decoded by ear, by listening to the pattern of beeps produced by the receiver. Skilled operators could receive better than unskilled ones, and some people could produce code that was easier to understand than that of others. A good transmitting operator was said to have a "good fist." An inept operator was called a LID. (For the origin of "lid" -- which I believe comes from a common error in American Morse of sending LID for DD, daaahh, dit dit, dah dit dit instead of dah dit dit, dah dit dit -- see this reference: https://english.stackexchange.com/questions/31818/how-did-the-word-lid-come-to-mean-poor-operator-in-the-context-of-telegraph .)

Thus it follows that the "encoding" of Morse into a binary format depends upon purpose, and thus whether the quality of "good fist" versus "poor fist" is to be retained. Is a string of on-and-off switching to be matched to a clock and "corrected" for difficulties in phase or duration of each portion of the signal? Or is it instead to be sampled at a rate sufficient to retain random or confusing variations, presumably for later inspection or delight?
> -2 votes

---
Tags: information-theory, coding-theory, encoding-scheme
---


# Question
Title: Determine whether a point lies in a convex hull of points in O(logn)
I've researched several algorithms for determining whether a point lies in a convex hull, but I can't seem to find any algorithm which can do the trick in O(log n) time, nor can I come up with one myself. Let a\[\] be an array containing the vertices of the convex hull, can I preprocess this array in anyway, to make it possible to check if a new point lies inside the convex hull in O(log n) time?

# Answer
> 7 votes
This is a classic problem in computational geometry, called Polygon Inclusion Problem. Further, you are considering its special case --- Convex Inclusion.

In chapter 4 of this thesis by Michael lail Shamos 1978, you will find that:

Generally,

> Theorem 4.2 (Page 92): Whether a point is interior to a simple $n$-gon can be determined in $O(n)$ time, without preprocessing.

and for convex polygon,

> Theorem 4.3 (Page 95): The Inclusion question for a convex $n$-gon can be answered in $O(\log n)$ time and $O(n)$ space, given $O(n)$ preprocessing time.

The proofs of these two theorems contain the algorithms you are looking for.

# Answer
> 6 votes
You can

* Find a point that is within the convex hull (find centroid of 3 non-collinear points will do).
* Turn all points into polar coordinate using that one point as origin.
* Now if you have sorted all points using their angle in polar coordinate, you can find 2 points with angle immediately below and above the angle of the point in question.
* Check if the line segment between those 2 points and the line segment connecting the origin and the point in question intersects. If they do, the point is outside the convex hull. If they don't, the point is inside the convex hull

Finding 2 reference points from the sorted list is $O(\log n)$, checking for intersection is $O(1)$, so total time is $O(\log n)$. This does not count the sorting and polarization time just like you allow in the question.

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


# Question
Title: Can there be a strict transaction that is not 2Phase?
I am confused about the definition of a strict transaction. What is the difference between a transaction that is strict and a transaction that is both strict and 2 phase?

# Answer
> 2 votes
Strictness Strictness ($\textsf{ST}$) is related to recoverability. Serializability ($\textsf{SR}$) is one of many consistency conditions of transactions, which is somewhat orthogonal to recoverability. 2PL is a protocol usually used to ensure serializability.

First, I don't think the term "strict transaction" is proper. Strictness, just like serializability, is defined over executions (also called histories or schedules) of transactions.

Secondly, strictness is *incomparable* to serializability (there are various versions of serializability. I suppose you are referring to CSR --- conflict serializability).

Finally, your question "Can there be a strict transaction that is not 2Phase?" should be

> "Is there any execution which is strict but not serializable?"

The answer is "Yes". For example, $e = r\_1(x) \\; w\_2(x) \\; w\_2(y) \\; c\_2 \\; r\_1(y) \\; c\_1$. You can check that $e \in \textsf{ST} \land e \notin \textsf{SR}$.

---
Tags: terminology, database-theory
---


# Question
Title: Are regular languages closed against an intersection that keeps words with the same number of ones?
How can we show that the class of regular languages is closed under the following operation?

Let $L\_1$ and $L\_2$ be laguages over $\Sigma=\\{0, 1\\}$.

The operation is: $$\\{x \in L\_1 \mid \text{ for some } y \in L\_2, \text{ strings } x \text{ and } y \text{ contains equal numbers of } 1s \\}$$

Is the only way to show this to create a NFA of the new language?

I have done the following:

Let $M\_{L\_1}=(Q\_{L\_1},\Sigma ,\delta\_{L\_1},q\_{L\_1},F\_{L\_1})$ the DFA that recognizes $L\_1$ and $M\_{L\_2}=(Q\_{L\_2},\Sigma ,\delta\_{L\_2},q\_{L\_2},F\_{L\_2})$ the DFA that recognizes $L\_2$.

Let $M=(Q,\Sigma ,\delta,q,F)$ the NFA that recognizes the operation.

$Q=Q\_{L\_1}\times Q\_{L\_2}, \ \ q=(q\_{L\_1},q\_{L\_2})$.

Is this correct? Which is the transition function?

# Answer
> 4 votes
Let $$ L = \\{ x \in L\_1 \mid \text{there exists }y \in L\_2 \text{ such that } |x|\_1 = |y|\_1\\} $$ Let $\pi: \Sigma^\* \to a^\*$ be the homomorphism defined by $\pi(u) = a^{|u|\_1}$. I claim that $$ L = L\_1 \cap \pi^{-1}(\pi(L\_2)) $$ Since regular languages are closed under homomorphisms, inverses of homomorphisms and intersection, it will follow that $L$ is regular.

**Proof of the claim.** \begin{align} L\_1 \cap \pi^{-1}(\pi(L\_2)) &= \\{ x \in L\_1 \mid \pi(x) \in \pi(L\_2) \\} \\ &= \\{ x \in L\_1 \mid \text{there exists }y \in L\_2 \text{ such that } \pi(x) = \pi(y)\\}\\ &= \\{ x \in L\_1 \mid \text{there exists }y \in L\_2 \text{ such that } |x|\_1 = |y|\_1\\} \\ &= L \end{align}

# Answer
> 3 votes
Well, you are almost correct so far. But the trick is in the transitions. Cross-product construction, as you suggest, means that you intend to mimic both NFAs. But in this case you do not mimic them exactly in the same way. The part corresponding to the automaton $M\_1$ for $L\_1$ is mimicked for acceptance of the input string, while the part corresponding to the automaton $M\_2$ for $L\_2$ ignores the input and mimicks non-deterministically acceptance of some arbitrarily chosen input (ignoring the real input).

Furthermore, the states are not just $(q\_{L\_1},q\_{L\_2})$, but there is a third component, which is true or false, so that states are of the form $(q\_{L\_1},q\_{L\_2}, eq)$, where $eq$ can be $true$ or $false$.

This third component is true when you have mimicked scanning the same number of $1$'s for $M\_1$ and for $M\_2$.

But remember that the first is scanning the input string, while the second is scanning a non-existent randomly chosen string.

The last point is that you mimick both NFA asynchronously. Either you mimick the first or you mimick the second. Never both at the same time.

So you start mimicking the first on the true input until you scan a 1. Then you start mimicking the second on its non-deterministically chosen input until you scan a 1. Then you resume with the first until you scan a 1. Then you resume the second until ... etc. And you are careful that the $eq$ component of the state triple is $true$ only when both computations have seen the same number of $1$'s. You stop also when computations reach the end of their input (except for empty transitions), whether real input or made-up input.

Accepting states are triple of the form $(q\_{a1},q\_{a2}, true)$ where $q\_{a1}$ and $q\_{a2}$ are accepting states of the two initial automata.

Good luck

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


title: Data structure for a static set of sets

text:
# Question
Title: Data structure for a static set of sets
I have collection $U$ of sets, where each set is of size at most 95 (corresponding to each printable ASCII character). For example, $\\{h,r,l,a\\}$ is one set, and $U = \\{\\{h,r,l,a\\}, \\{l,e,d\\}, \ldots\\}$. The number of sets in $U$ is nearly a million. Also a set in $U$ will mostly contains 8-20 elements.

I am looking for a datastructure for storing collection of sets that support following operations:

1. set matching, e.g. check if set $\\{h,r,l,a\\}$ is present in $U$
2. subset matching e.g. check if set $\\{h,r,l\\}$ is subset of any set in $U$
3. superset matching e.g. check if set $\\{h,r,l,a,s\\}$ is superset of any set in $U$
4. union matching e.g. check if set $\\{h,r,l,a,e,d\\}$ is union of sets in $U$
5. approximate set matching e.g. check if set $\\{h,r,l,e\\}$ is present in $U$, should return true

In particular, we can assume that once the data structure is built, no modifications are made but only queries of the above type (the structure is static).

I was thinking of trie data structure. But, it demands storing data in some order. So I have to store every set as a bit vector, but then the trie becomes binary decision tree. Am I in the right direction? Any pointers will be appreciated.

# Answer
> 8 votes
Generically, these are sometimes called subset/containment dictionaries. The fact that you had partial matching in your question (but deleted it) is actually not a coincidence, because subset/containment queries and partial matching are equivalent problems for sets.

You probably want to use an UBTree (unlimited branching tree) for this; it's basically a modified trie. See Hoffmann and Koehler (1998) for more details.

You could also have a look at the more recent *set-trie* data structure proposed by Savnik (2013) for the same purpose. (If you miss the color in the graphs in that preprint paper and don't have access to the official Springer publication \[in which the colors aren't missing\], there's precursor to that paper which has almost the same graphs/info and no missing colors.)

Both papers (Hoffmann & Koehler, and respectively Savnik) have experimental results, so you can have some idea what they can handle in practice. Both seem to handle data sets with a cardinality of U around 1M.

If you somehow have TCAM hardware (or the money for it), there's a way to leverage that for subset/superset queries. You can actually do both subset/superset queries in parallel assuming you have enough TCAM words (2x |U|). Since TCAM words can be configured to be 144-bit wide, you and you have only 95 bits/letters to test, you wouldn't even need to bother with Bloom/hashing, you'd have an exact test using TCAM; this is trivial enough I'll even say here how: every {0, 1} bit-vector corresponding to every set in your U is simply turned into a {0, \*} vector for subset queries and to a {1, \*} vector for superset queries.

A more general problem tackled in ETI (no free copy, sorry) is finding a set with given similarity measure. For example, the similarity measure can be $J(Q,S)=\frac{|Q\cap S|}{{|Q\cup S|}}$ and the query for a given $Q$ can be to find all $S$ (in the database) with $J(Q,S)\geq 0.3$. Both the constant and the similarity measure are user-definable as a predicate in ETI. (The $J$ given as example here is called the Jaccard index.)

---
Tags: data-structures, sets
---


title: Restricted Integer Programming

text:
# Question
Title: Restricted Integer Programming
The integer feasibility problem is NP-complete:

$Ax=b, x \geq 0, x \mbox{ integer}$

$A$ contains elements in $\mathbb{R}$

If we restrict this:

$A$ contains only elements in:

1. $\\{1,0\\}$
2. $\\{1,0,-1\\}$
3. $\mathbb{N}$
4. $\mathbb{Z}$

Does this change anything in term of hardness?

Can all these problems be reduced to each other?

(Can it be for example that there is polynominaltime-algorithm for 1. but not for 4.?)

# Answer
> 6 votes
All four problems are NP-complete.

Let me start by proving two easy results:

* Your problem #3 is NP-complete, even when the matrix has only a single row, as explained here: Complexity of a subset sum variant.
* This implies that #4 is NP-complete as well, as #3 is a special case of #4.

Now for the strong result: Your problem #1 is NP-complete. The proof of this is a bit more involved, but I'll show a reduction from ZOE to your #1, where ZOE is a problem that is known to be NP-complete.

In particular, here is the definition of ZOE:

ZERO-ONE EQUATIONS (ZOE)
Input: a $m\times n$ matrix $A$, all of whose entries are 0 or 1
Goal: Find a $n$-vector $x$, all of whose entries are 0 or 1, such that $Ax=1$, where $1$ denotes the all-ones vector

The ZOE problem is NP-complete. This is proven in Chapter 8.3 of *Algorithms* (Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani). The proof proceeds by reducing 3SAT to 3D Matching, and then reducing 3D Matching to ZOE.

Now we can reduce ZOE to #1, as follows. If we have an instance of ZOE $A$, we transform it as follows. For each variable $x\_i$ of the ZOE instance, we add another variable $x^\*\_i$ and an equation $x\_i + x^\*\_i = 1$. (This has the effect of forcing $x\_i$ to be either 0 or 1, since we'll require $x\_i \ge 0$ and $x^\*\_i \ge 0$ and $x\_i,x^\*\_i$ are integers.) Thus, if the ZOE instance had a $m\times n$ matrix $A$, we now obtain $m+n$ equations in $2n$ unknowns, corresponding to some matrix $A'$. In other words, we obtain a problem instance $A'x' = b$ where $b=1$ is the all-ones vector, and where every entry of $A'$ is 0 or 1. This is now an instance of your problem #1. This instance of your problem #1 has a feasible solution if and only if the original ZOE instance has a feasible solution. This proves that any efficient algorithm to your #1 in turn yields an efficient algorithm for ZOE -- but since ZOE is NP-complete, it follows that #1 is NP-complete as well.

It follows from this result that #2, #3, and #4 are NP-complete as well, as #1 is a special case of them.

# Answer
> 1 votes
Partial answer: (3) and (4) can be reduced to (2), at the price of increasing the problem size by a factor in $O(\log N)$, where $N$ is the greatest matrix entry in the original problem. One way of doing this (possibly suboptimal) is to have for each original variable $x$ pairs of new variables $x\_i,\bar x\_i$ ($0\le i\le \log N$) representing $2^ix$, which is enforced by the additional constraints $x\_i-\bar x\_i=0$ and $x\_{i+1}-x\_i-\bar x\_i=0$. Now replace each term $mx$ in the linear constraints by the appropriate combination of $x\_i$, and you are done.

---
Tags: complexity-theory, np-complete, reductions, integer-programming
---


# Question
Title: Good data structure for finding all points in one set a distance from each point in another set
Let $X$ and $Y$ be two sets of points in $\mathbb{R}^3$. Assume that the cardinality of $Y$ is larger (much larger if you want) than $X$. For each $x\_i \in X$, I need to find all $y \in Y$ such that the distance between $x\_i$ and $y$ is less than a (fixed) radius $R$. That is, for each $x\_i$, I want the set $E\_i = \\{y \in Y: \\|x\_i-y\\|\ \leq R\\}$.

Now this looks to me like a nearest-neighbors type problem just with two different sets of points. If I'm correct, usually something like an R-tree or kd-tree is good for finding nearest neighbors within a single set $X$. But this seems a bit different. I could naively just iterate through $X$ and find the $y\_j \in Y$ such that $\\|x\_i-y\_j\\| \leq R.$ and I suppose store that in a gigantic array, but this seems like the worst possible method. On the bright side, this is at least embarassingly parallel so there is that at least.

Any suggestions would be greatly appreciated and I apologize if this is a trivial question (I'm not a computer scientist!) Also, if this is the incorrect place to ask such a question, please let me know. If the question is unclear or requires additional information, just let me know. Thanks!

# Answer
> 1 votes
Sort the big set $Y$ into a regular grid, then for any query point $x\_i,$ find its cell and you only have to check the adjacent cells to determine $E\_i$ very quickly. For sorting, indeed, some parallel algorithms are faster than others, see this poster for an overview and example of using fast GPU radix and count sort.

---
Tags: data-structures, computational-geometry, numerical-algorithms
---


# Question
Title: Prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values
How can I prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values ?

It seems obvious to me, since an ill-conditioned problem is that in which exact input values(D) are totally different from error valuesI(D') (judging by something), thus the exact solution(G) differ much from one with error in some sense. This can be applied in case of algorithms: because if D and D' are far from each other somehow, than no one can expect for G(D\*) to get closer to G\*(D), where G\* is the algorithm for implementing the G problem . Can you please show some more precise approach, less "in words" and more in logic ?

Thank you.

# Answer
Let's try to define those terms in math language:

* Denote $x$ as the input, and $f(x)$ is the solution to the problem with input $x$.
* Ill-condition problem: $x'=x + \delta \Rightarrow f(x') \gg f(x) + \delta$
* Stable algorithm $F(x) \simeq f(x')$ (stable algorithm give you result close to result of a nearby input)

So apply stable algorithm on ill-condition problem we get: $F(x) \simeq f(x') \gg f(x) + \delta$

Which says the best you can get can't be smaller than error in the input.

I think you can also prove by contradiction, saying if the stable algorithm can do that, then the changes in input will make only small change in the output which makes the problem well-condition.
> 1 votes

---
Tags: algorithm-analysis
---


# Question
Title: Equivalent Straight Line Embedding of a Planar Graph Drawing on a Grid
An embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:

* the endpoints of the arc associated to an edge e are the points associated to the end vertices of e,
* no arcs include points associated with other vertices,
* two arcs never intersect at a point which is interior to either of the arcs.

Two embeddings of a planar graph in the plane are called equivalent for every vertex of the graph the cyclic order of the incident edges is the same in both embeddings.

I am looking for a reference which shows that any Jordan arc embedding of a planar graph can be equivalently embedded as a straight line drawing with the $n$ vertices of the graph lying on the vertices of an $O(n) \times O(n)$ grid. (Certainly any planar graph can be embedded with its vertices on the vertices of such a grid but I'm looking for an embedding that's equivalent to the originally given one.) Schnyder's algorithm seems to produce an embedding equivalent to the topological embedding given as its input but I've not managed to find a proof of this.

Does anybody know of such a theorem?

# Answer
> 2 votes
"Schnyder's algorithm" computes an embedding on an $O(n)\times O(n)$ grid. See here for a reference, and see here for a more general treatment that is not behind a paywall. Note that if your initial (topological) embedding is not unique, you can just add edges (while preserving planarity) until the graph becomes 3-connected (or even a triangulation) and then apply some drawing algorithm. Once the layout is computed you simply remove the augmentation.

I want to point out that there is also a different drawing algorithm for the $O(n)\times O(n)$ grid by De Fraysseix, Pach and Pollack. It is based on the *canonical order* of the planar graph. See here for the reference if the graph is a triangulation, and here for 3-connected planar graphs.enter link description here. These articles are behind paywalls, but the algorithms are standard and you will find lecture notes if you google the keywords. You might also try to check out the handbook of graph drawing for more information.

---
Tags: graphs, reference-request, graph-drawing
---


# Question
Title: Can one insert non-unique elements into an AVL tree?
Is it possible to insert a sequence of non-unique elements into an AVL tree?

For example, what is the AVL tree result of inserting 3, 3, and 3 into an initially empty AVL tree?

Is it:

```
        3
      /   \
     3     3

```

# Answer
A BST (from which the AVL descends) with duplicate keys can have its rotation make nodes with the same key be on both sides of the parent node, in which case, some ambiguity might result. However, you could make your life a whole lot easier and have each node contain a key and the number of times that key had been inserted into the tree, to therefore keep track of successive inserts of successive keys and disambiguate its structure.

You would still insert a node (first by searching for the expected placement for the node) with respect to its key, initialize its count to 0, and towards the end of completing the insert increment that count).
> 4 votes

# Answer
After consulting with an EECS TA, I have come to the conclusion that if duplicate values are allowed to be entered in an AVL tree, then adding 3 elements of the same value (e.g. 1,1,1) will result in a tree as shown above, with a parent node equal to both its left and right children.
> 0 votes

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


# Question
Title: NXOR for 2 inputs on a turing machine, in P?
**Question:** L is the language of $\langle M,x,y\rangle$ s.t TM $M$ accepts both inputs $x$ and $y$ or doesn't accept either. Prove that given some $M$, finding 2 inputs $x$ and $y$ s.t. $\langle M,x,y\rangle\in L $ can be done in polynomial time.

**Thoughts:** This seems strange to me that this can be done in P time as we have to somehow guess an unbounded amount of inputs for that to be true.

# Answer
Since the problem didn't restrict $x$ or $y$, let $x$ be any string and let $y=x$. Then $M$ either accepts $x$ or it doesn't. If $M$ accepts $x$ (and so accepts $y$) then $\langle M, x, y\rangle\in L$. Similarly, if $M$ doesn't accept $x$, we'll also have $\langle M, x, y\rangle\in L$. The upshot is that we can find $x, y$ in constant time.
> 1 votes

---
Tags: turing-machines, undecidability, polynomial-time
---


# Question
Title: The number of Binary Search Tree that exist with same Postorder and Inorder
how many BST exist with same postorder and inorder traversal?

I know that in binary tree (Not BST), it is one.

but i have a book from that said for BST it is CATALAN number. i become confused.

# Answer
> 1 votes
Your confusion might stem from this: The number of binary trees on $n$ vertices is $C\_n$, the $n$-th Catalan number. Since in a BST, the left-right order of vertices is fixed, the number of BSTs with a given inorder traversal is also $C\_n$. However, with the added restriction that the postorder traversal must be the same as the inorder traversal, the BST can only have left branches.

In more detail, recall that `inorder = left-visit-right` and `postorder = left-right-visit`.

If both traversals must be the same (visit is at the root) there can be no right subtree, and this is then the same at the left child, and so on. This leaves only one form: a tree with only children to the left.

What is your book stating, more precisely? Perhaps we can find the reason for the confusion.

---
Tags: data-structures, combinatorics, binary-trees, search-trees
---


# Question
Title: Algorithm to determine two binary expression trees will give the same result based on associative and commutative properties of some operators
Given *n* different numbers, I would like to find out whether there exists an algebraic expression using all the *n* numbers, with *n*−1 binary operators and unlimited number of parentheses, that evaluates to a certain number *T*. My idea is to make use of binary expression trees, construct all possible trees and then find the result by brute force.

As I have learned, the number of possible combinations will be:

$$\begin{aligned} \frac{(2(n-1))!}{(n-1)!n!} n! s^{n-1}\\ \end{aligned}$$

where *s* is the number of different binary operators that is allowed to be used (e.g. if we allow +, −, × and ÷, then *s*=4), and

$$\begin{aligned} \frac{(2(n-1))!}{(n-1)!n!} \end{aligned}$$

is the number of different types of binary expression trees that can be constructed without considering the content of the nodes.

To speed up the search, I have an idea to make use of the associative and commutative properties of the operators + and ×. An intuitive case will be, if all the *n*−1 operators chosen are all +, then all the trees will evaluate to the same result, regardless of how the *n* numbers are allocated in the leaf nodes. However, this obviously does not apply to operators − and ÷. And, in the general case, the operators chosen will consist of a mixture of +, −, × and ÷, so is there an algorithm to check the trees will evaluate to the same result without actually doing the calculation?

e.g. A binary expression tree that represents (8−5)×(6+3)×(7−4) will give the same result as a binary expression tree that represents (8−5)×((6+3)×(7−4)). Going even further, they will also give the same result as a binary expression tree that represents (3+6)×(7−4)×(8−5). Is there such an algorithm to detect these trees will evaluate to the same result?

# Answer
Note that if you just want to know if two equations without variables have the same result, then just evaluate them already. But it's more tricky with variables:

I assume that you are basically just functionally rearranging lists (ie: like Python/JavaScript/Lisp code). For associative binary operators, it's convenient to make them have n operands to avoid a re-association pattern matching mess. A sum or product of one operand is a redundant parenthesis. Because they happen to be commutative, have the sum and product objects consistently sort their operands if you want them to be efficiently comparable (ie: define a canonical form that everything should reduce to).

It is harder if variables are involved though. The equals sign can be treated as just another binary operator to create new expressions, where you do things like: a, (a=(b\*2)), ((a=(b\*2))+6), ((a+6)=(b\*2)+6), ((a+6)=(2\*b)+6). At that point, you construct new expressions like: equate(expr,expr), add(expr,expr), mul(expr, expr), ldistribute(expr,expr), rdistribute(expr,expr), commute(expr), etc.

Some of the rules are obvious like distributing multiplication over addition, or additive or multiplicative cancellation; and usually go in one direction (like automatic differentiation). But there will be other times where you will need to do a more clever search (like a chess engine), doing things like multiply an expression times 1, and equate it with a new variable divided by itself, etc. One of the more tricky things in an algorithm for solving is that some operations like division add new logical constraints. If you construct div(add(a,b),x), you implicitly construct a logical constraint for x!=0; and you need to work these constraints in so that the search for the solution doesn't generate nonsense.

These kinds of programs are usually written as pattern matching and rewriting, with provisions made to not go in infinite loops.
> 3 votes

---
Tags: algorithms, search-algorithms, binary-trees
---


# Question
Title: Understand the time complexity for this LCS (longest common subsequence) solution
I would appreciate an intuitive way to find the time complexity of dynamic programming problems. Can anyone explain me “#subproblems * time/subproblem”? I am not able to grok it.

Code for LCS -

```
public static String findLCS(String str1, String str2 ) {
    // If either string is empty, return the empty string
    if(null == str1 || null == str2)
        return "";
    if("".equals(str1) || "".equals(str2)) {
        return "";
    }
    // are the last characters identical?
    if(str1.charAt(str1.length()-1) == str2.charAt(str2.length()-1)) {
        // yes, so strip off the last character and recurse
        return findLCS(str1.substring(0, str1.length() -1), str2.substring(0, str2.length()-1)) + str1.substring(str1.length()-1, str1.length());
    } else {
       // no, so recurse independently on (str1_without_last_character, str2)
       // and (str1, str2_without_last_character)
       String opt1 = findLCS(str1.substring(0, str1.length() -1), str2);
       String opt2 = findLCS(str1, str2.substring(0, str2.length()-1));
       // return the longest LCS found
       if(opt1.length() >= opt2.length())
           return opt1;
       else
           return opt2;
    }
}

```

I am just providing the actual code instead of pseudo code (i hope pseudo code or the algo is pretty self explanatory from above)

# Answer
I assume you are interested in worst-case complexity.

A dynamic programming approach (recursively) breaks a problem into "smaller" problems, and records the solution of these subproblems to make sure that subproblems are not computed several times. So when the time required to combine subproblems is constant (it is the case for LCS), you only have to find an upper bound for the number of possible subproblems that will be solved along the program.

* Here the subproblems are of the form findLCS(s1,s2) where s1 is a prefix of str1, and s2 a prefix of str2. There are (1+str1.length()) possible prefixes for str1, and (1+str2.length()) for str2.
* The number of possible subproblems is therefore (1+str1.length()) * (1+str2.length()). Furthermore, a solution is obtained in constant time from its subproblems. Hence complexity O( str1.length()\*str2.length() ).

N.B. on some sequences all subproblems will be indeed computed, e.g., when letters in str1 and str2 are distinct. Consequently, the quadratic bound is "tight".

N.B.2 you may find (short) explanations on the wikipedia page for LCS
> 1 votes

# Answer
The code posted doesn't implement Dynamic Programming, so the time complexity is in fact O(2^n).

See this Wikipedia article and this GeeksforGeeks post for pseudocode and specific implementations.This post also shows how to get the LCS in a recursive/iteratively way using DP.

To implement Dynamic Programming is necessary to implement a cache mechanism to prevent calculating the same sub-results multiple times.
> -1 votes

---
Tags: algorithm-analysis, runtime-analysis, dynamic-programming
---


# Question
Title: Is equivalence of a CFG and an RG undecidable?
I know that the equivalence of two context-free grammars is undecidable, but what about the equivalence of a regular grammar and a context-free grammar?

# Answer
> 7 votes
It is undecidable whether for a given CFG $G$, $L(G)=\Delta^\*$, the set of all strings (over the terminal alphabet of $G$). That answers your question, by chosing the most simple regular grammar.

---
Tags: computability, formal-grammars, decision-problem
---


# Question
Title: Algorithm for a special case of SAT/#SAT
Does anyone know of an algorithm that can solve the following special case of SAT in polynomial time? Are there any algorithms that can solve the counting (#SAT) version of it in polynomial time?

Special case: If clause $a$ and clause $b$ have one or more variables in common, that is, there exists some variable $x$ that is in both $a$ and $b$, at least one of the shared variables is positive in $a$ and negated in $b$ or vice-versa.

Example: $$(a \vee b \vee c) \wedge (\bar{a} \vee c \vee d)$$

Example of an instance that does not fit in the special case: $$(a \vee b \vee c) \wedge (a \vee c \vee d)$$

# Answer
> 2 votes
From Solving #SAT using vertex covers, published at SAT'06 by Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider:

> A cluster formula is a variable-disjoint union of so-called hitting formulas; any two clauses of a hitting formula clash in at least one literal. The known polynomial time algorithm for computing the number of models of a hitting formula can be extended in a straight-forward way to compute the number of models of a cluster formula.

Clash is later clarified/defined as:

> We consider propositional formulas in conjunctive normal form (CNF), represented as sets of clauses. That is, a literal is a (propositional) variable $x$ or a negated variable $\overline{x}$; a clause is a finite set of literals not containing a complementary pair $x$ and $\overline{x}$; a formula is a finite set of clauses. For a literal $ℓ = \overline{x}$ we write $\overline{ℓ} = x$; for a clause $C$ we set $\overline{C} = \\{ \overline{ℓ} : ℓ ∈ C \\}$. We say that two clauses $C$, $D$ overlap if $C ∩ D \neq ∅$; we say that $C$ and $D$ clash if $C$ and $\overline{D}$ overlap. Note that two clauses can clash and overlap at the same time. \[...\] A formula is a hitting formula if any two of its clauses clash (see \[17\]). A cluster formula is the variable-disjoint union of hitting formulas \[...\]
>
> Lemma 3. #SAT can be solved in polynomial time for cluster formulas.

So their cluster formula seems to be exactly what you have defined.

There's also a journal version that paper, it seems; the result is (not surprisingly) also mentioned in a 2011/2012 survey paper "Backdoors to satisfaction" on which Szeider is a co-author, and which was published in some festschrift My first instinct that this was a more suitable question on cstheory.SE was perhaps not wrong. :-)

Also the notion of hitting formulas is cited to \[17\]:

* H. Kleine Buning and X. Zhao. Satisfiable formulas closed under replacement. In H. Kautz and B. Selman, editors, Proceedings for the Workshop on Theory and Applications of Satisfiability, volume 9 of Electronic Notes in Discrete Mathematics. Elsevier Science Publishers, North-Holland, 2001.

In another paper, the fact that

> It is known that for hitting formulas the satisfiability problem can be solved efficiently \[7\].

is cited to an even older paper:

* K. Iwama "CNF satisfiability test by counting and polynomial average time" SIAM J. Comput., 18 (1989), pp. 385–391

---
Tags: algorithms, complexity-theory, satisfiability, polynomial-time, counting
---


# Question
Title: Physically based rendering from theory to implementation
Physically based rendering form theory to implementation - http://www.amazon.ca/Physically-Based-Rendering-Theory-Implementation/dp/0123750792/ref=sr\_1\_1?s=books&ie=UTF8&qid=1425451050&sr=1-1&keywords=physically+based+rendering

has all the information which is in Real time rendering - http://www.amazon.ca/Real-Time-Rendering-Third-Tomas-Akenine-Moller/dp/1568814240/ref=sr\_1\_1?s=books&ie=UTF8&qid=1425451133&sr=1-1&keywords=real+time+rendering

in terms of rendering? And techniques listed in Physically based rendering can be executed using HLSL?

# Answer
> 2 votes
No, and no.

The framework in PBRT is not geared to real-time rendering on current graphics hardware. The goal of PBRT is to solve Kajiya's rendering equation, and it does this using unbiased Monte Carlo integration. This is very much "non-realtime" at the moment.

The state of the art in realtime physically-based rendering is to render static or semi-static scenes (using a lot of precomputation), or to model only some (common) types of light transport path. There's also work in using GPUs to accelerate unbiased rendering of the full rendering equation, but it's not even close to realtime yet. This is an active research area.

Having said all this, both books are excellent, and well worth reading.

---
Tags: books
---


title: How does selection sort sort?

text:
# Question
Title: How does selection sort sort?
I've found the following algorithm for selection sort on the internet.

```
program SelectionSort(input,output);
var
  A : Array[1..80] of Integer;
  n, i, j, k, m, loc, temp : Integer;
begin
  writeln('size of the array?');
  read(n);

  for i := 1 to n do
   read(A[i]);

  for k := 1 to n - 1 do
   begin
    m := A[k];
    loc := k;
     for j := k + 1 to n do
      begin
       if m > A[j] then
        begin
         m := A[j];
         loc := A[j];
         loc := j;
        end;
      end;
     temp := A[k];
     A[k] := A[loc];
     A[loc] := temp;
   end;

  for i := 1 to n do
   begin
    writeln(A[i] : 3);
   end;

  readln();
  readln();
end.

```

I'd like to gain a better understanding of how it actually does the sorting. Could someone please help me with this?

# Answer
Neither the code you have nor the Wikipedia article highlight the concept of selection sort. Therefore, consider this (functional) pseudocode:

```
def selection-sort []         = []
|   selection-sort x::xs as l =
      let m = min l
      in
        m::(selection-sort (delete m l))
      end;

```

Here the idea is more clear

> $\ \ $1. Select the *minimum* from the list and delete it.
> $\ \ $2. Sort the remainder recursively.
> $\ \ $3. Prepend the minimum.
> The same works the other way around with the maximum, obviously.

Iterative code on arrays works slightly differently -- but the idea remains the same.
> 1 votes

---
Tags: algorithms, sorting, intuition
---


# Question
Title: Generating symbol matrices that satisfy regular expressions row- and column-wise
I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one.

For example, say I have $N=3$, regular expression $c^\*ab^\*$ for rows and $b^\*ac^\*$ for columns. A solution would be

$\qquad\displaystyle\begin{pmatrix} a & b & b \\ c & a & b \\ c & c & a \end{pmatrix}$

I'm trying to find an algorithm that is faster than the brute force one. I am further looking for a way to split this algorithm in independent processes so I can use parallelism to decrease the time needed to reach a solution.

# Answer
> 2 votes
Here's one idea that may still take exponential time in $N$ but is polynomial in the (length of) the regular expressions.

Consider strings over the shared alphabet $\Sigma$ of length $N^2$; each such string represents an $N \times N$ matrix stored row-wise. We insert a separation character $\\$ \not\in \Sigma$ between rows.

We will now construct a finite automaton the accepts exactly the set of such strings that fulfill your two regular expressions.

Let $r$ resp. $c$ be the row resp. column regular expression

1. Clearly, $r\_N = (r \cap \Sigma^N\\$)^{N-1}(r \cap \Sigma^N)$ matches all matrices that match $r$ in every row. Transform $r\_N$ into an NFA $A\_{r,N}$.
2. Denote with $A^{(i)}\_{c,N}$ the automaton that matches only every $N$-th input symbol (ignoring $\\$$) against $c$, starting with the $i$-th. I will leave the construction as an exercise; suffice to say that we need at most $N$ copies of $A\_c$.

Now, $A\_{c,N} = A^{(1)}\_{c,N} \cap \dots A^{(N)}\_{c,N}$ accepts the set of all matrices each column of which matches $c$.
3. The automaton $A\_{r,c,N} = A\_{r,N} \cap A\_{c,N}$ accepts all the matrices you want.
4. A simple graph traversal finds an accepting path in $A\_{r,c,N}$ finds a solution matrix, if any.

The blowup in size is mild (i.e. at most a factor $N^2$) for all constructions but the intersections; these multiply sizes, so we may look at a factor $2^N$ for automaton size.

That's still way better than checking all $\Sigma^{N^2}$ possible matrices.

---
Tags: algorithms, formal-languages, regular-expressions, strings, concurrency
---


# Question
Title: What is the best solution to find whether the sum of an array is even or odd
I was asked this question in an interview. I was not able to find a better solution than $O(n)$ which is just going over the array and finding the sum. Can it be done any better? I am not really interested in the actual sum, I just want to know whether it's even or odd.

Or how do I prove that it cannot be done better than $O(n)$?

# Answer
Consider e.g. an array that consists of all zeros except for the last element, which is either an odd integer or an even integer. To decide whether the sum of the $n$ elements is even or odd, you must read the whole input, i.e. check even the last index of the array. So you must perform at least $n$ steps.
> 6 votes

# Answer
By a simple "adversary argument", you have to check each element (in some way): Suppose you have missed some element $x$ and get an answer "The sum is even": the adversary can modify $x$ (if it's odd, make it even; if it's even, make it odd), which will change the correct result but not your computation.

The adversary argument tells that in theory you have to check each element. By the way, it does not mean you have to sum them up. You can simply count the numbers of even numbers and odd numbers (or go through the array by +1 for even and -1 for odd).
> 12 votes

# Answer
Modulo arithmetics is what you want. Here you need only arithmetics modulo 2, i.e. only look at the last bit of each number, if binary encoding of natural numbers is used, or two's complement representation of positive and negative number. It works with one's complement only for positive integers.

Then you can simply use bitwise XOR for addition, which is somewhat cheaper than doing a real addition.

As proved by hengxin, you have to do it for all elements of your array, so that the algorithm is necessarily linear in the size of the array.

This is no better complexity than other answers, but your question title is best solution. So there is more than complexity to the best solution (else we would be doing matrix multiplications much faster).

Bonus: using modulo arithmetics, or XOR, has the advantage that you do not risk arithmetic overflow as you would by computing the actual sum.
> 7 votes

# Answer
Of course, you should check all $n$ input elements. But I suppose that person who asked this question wanted from you to find fastest solution(in terms of the cost of the machine operation). What I mean: in fact you do not need to calculate the sum of all elements. You just need to know if it's odd or even.

Suppose you have processed $k$ first elements. Let's denote their sum like $S\_k$. In fact we don't know it. Now you process $k + 1$ element. There are 4 possibilities:

* $S\_k$ is odd, and $k + 1$ element is odd then $S\_{k+1}$ is even.
* $S\_k$ is odd, and $k + 1$ element is even then $S\_{k+1}$ is odd.
* $S\_k$ is even, and $k + 1$ element is odd then $S\_{k+1}$ is odd.
* $S\_k$ is even, and $k + 1$ element is even then $S\_{k+1}$ is even.

Now we should make a xor operation: $S\_k = S\_k \text{ xor } (k+1)\text{th element}$. Initially, $S\_1$ is equal to the first element. Now if $S\_n$'s first bit is $0$ then the sum is even else is odd.
> 0 votes

# Answer
If you have a usual computer using two's complement arithmetic, just add all the numbers. While you are only interested in the lowest significant bit of the result, the effort of masking out anything else is not going to be worth the trouble.

In theory, you can save time by just fetching and adding (or xoring, which is equivalent for the lowest significant bit) the lowest significant byte of each number. In practice, the memory interface and cache lines will deliver all of them anyway.

Any input number can change the result or not, so you don't get around accessing any element anyway.

In short: this is one task where the simplest brute-force solution cannot be beat. At least while we are talking about a single CPU.
> -2 votes

---
Tags: algorithms, efficiency, arrays
---


# Question
Title: Sorting tuples with respect to multiple criteria
Given $n$ rows with $k$ columns, is there a storage mechanism/data-structure and/or algorithm that enables dynamic restructuring such that I can get the top $t=\mathcal{O}(1)$ results efficiently?

### Example strategy 0

$$k\_0 \le k\_1 \le \cdots \le k\_{n-2} \le k\_{n-1}$$

### Example strategy 1

$$k\_{n-1} \le k\_{n-2} \le \cdots \le k\_1 \le k\_0$$

---

Given `[ [0,1] [2,3] [1,2] ]` strategy 0 returns: `[ [0,1], [1,2] ]`, where $t=2$.

Restructuring with strategy 1 returns: `[ [2,3], [1,2] ]`. New strategies can be provided "at runtime".

---

Given a data-structure solution, here are the methods that it should expose:

* `insert_row (*row) ->` inserts a row of $k$ elements into the structure
* `delete_row (*row) ->` delete the precisely specified row from structure
* `new_strategy(*k_prioritisation) ->` rebalances the structure given the specified strategy
* `top_rows() ->` provides top rows after a strategy has been "installed". Number of rows to return is specified at compile time (as a source-code constant).

---

PS: Bonus points if you can enables strategies like $k\_0 \le \[\text{all other } k \text{ except } k\_0\]$, with embedded strategies of much the same.

# Answer
Multivariate optimisation (a subproblem of sorting) is usually hard, even offline, because there are no longer "optima" but you have to deal with several Pareto-optimal elements.

Luckily, you have specified that such ties should be broken by strict priorities. In that case, lexicographic sorting (w.r.t. your criteria and in order of the priorities) solves the problem.
> 1 votes

---
Tags: algorithms, data-structures, optimization, sorting, partitions
---