Synchronous model: is taking steps simultaneously equivalent to having fixed upper bounds for communication/processing delays? I've just started reading about theory of distributed systems and am a bit confused. There seem to be two ways of defining a synchronous distributed system and I'm not sure whether they are equivalent.
Lynch, in her book Distributed Algorithms (p. 5) writes

The synchronous model: This is the simplest model to describe, to program, and to reason about. We assume that components take steps simultaneously, that is, that execution proceeds in synchronous rounds.

Several other sources, in contrast, define the synchronous model in terms of known upper bounds for computation and communication delays. For instance, Cachin et al. in their book Introduction to Reliable and Secure Distributed Programming (pp. 45-46) write

[...] a synchronous system comes down to assuming the following properties:
Synchronous computation. There is a known upper bound on processing delays. That is, the time taken by any process to execute a step is always less than this bound. [...]
Synchronous communication. There is a known upper bound on message transmission delays. That is, the time period between the instant at which a message is sent and the instant at which the message is delivered by the destination process is smaller than this bound.

Even Lynch herself, in a paper she cowrote with Dwork and Stockmeyer (Consensus in the Presence of Partial Synchrony) also uses a definition similar to the one by Cachin et al.:

[...] it might be assumed that there is a fixed upper bound $\Delta$ on the time for messages to be delivered (communication is synchronous) and a fixed upper bound $\Phi$ on the rate at which one processor’s clock can run faster than another’s (processors are synchronous), and that these bounds are known a priori and can be "built into" the protocol.

Are these synchronous models equivalent? For instance, is an impossibility result in one also an impossibility result in the other, and vice versa? And is the minimum number of nodes necessary to tolerate a given failure (e.g., byzantine or crash) the same, whether we define synchronous to mean that processes proceed in synchronized steps or whether we define it as meaning that transmission and computation delays are upper bounded and known?

All of these are, generally speaking, called "synchronous models", they are pretty similar to each other, and especially in the context of fault-tolerant algorithms they are very different from "asynchronous models".

However, please note that there is no such thing as the synchronous model. Even if you define a message-passing model in which all nodes execution proceeds in synchronous rounds and all nodes start simultaneously, this does not yet completely define the model of computing. To have a well-defined model of distributed computing, you will need to specify, e.g., the following aspects:

assumptions on the underlying network topology (complete network? path? cycle? grid? bounded-degree graph? arbitrary graph?)
what kind of local information the nodes have in the beginning (unique identifiers? an upper bound on the network size?)
what is the communication model (maximum message size? can you send different messages to each neighbour in the same round or are you limited to e.g. broadcast operations? can you receive messages from different neighbours in the same round or do you have collisions? how can you address your neighbours?)
what kind of computers you have as your nodes (finite state machines? Turing machines? arbitrary functions? any limitations on time or space used per round? any limitations on space used between rounds? can you use randomness?).

These aspects can be much more important than the specific definitions of "synchrony", especially if you are interested in computability.

But let us put these issues aside, let us assume we have already precisely defined some synchronous model of computing (and let us also assume that it is a fairly strong model, e.g., we have unique identifiers and unlimited local computation). Let us now try to see whether the precise definition of "synchrony" would make any difference.

If you only care about computability, the precise definition of "synchrony" is not important. Also, if you are only interested in the number of communication rounds needed to solve a problem (and you define a "communication round" appropriately so that it makes sense also in the bounded-delay model), the models are also equivalent up to constant factors. In essence, you can simply use the alpha synchroniser: all nodes count rounds from 1, all messages include round counters, and each node proceeds to round $i+1$ once it has received all messages from round $i$ (and you use timeouts to detect nodes that have crashed).

Things get more complicated if you also care about e.g. the total number of bits that you need to transmit. In essence, in the "strict" synchronous model you can easily use silence to send information (e.g., be silent for $x$ rounds and then send a 1-bit message ≈ send number $x$). Here is a simple example of a problem that can be solved this way:

the underlying graph is a path and all nodes need to determine how far they are from the nearest endpoint.

If all nodes start simultaneously and computation proceeds in synchronous rounds, it is sufficient to propagate a 1-bit token from the endpoints towards the middle. All nodes can locally count how many rounds it takes before they receive the token. In total, in a path of length $n$, you will send approximately $n$ messages, each of them containing just one bit.

However, if you have bounded delays, it gets pretty tricky to solve this problem with $O(n)$ 1-bit messages. You can still use periods of silence to send information, but you will need to waste a lot of time to do that (a naive solution has an exponential time complexity).


Guessing the best choice to maximize returns There are $N$ number of people and $X$ amount of objects with different values. Each person will choose an object and will obtain that objects value. If multiple people choose the same object then the value of the object is shared among the people. For example, If there are 2 objects and 3 people, one of the objects will be chosen by at least 2 people, thus the value of the object is divided over 2.

Each round the people make their decisions with new objects and new values, how can a person maximize their expected values accumulated from their choices in Q number of rounds, in order to win(i.e accumulated most value)? ($Q$ belongs to [1, +infinite).

Note that keeping track of other player's decisions and their accumulated values can help in future decision making.

Note: An approximation would be great as well, so far my strategy is to choose a random object at each round, I am looking for ways to maximize this strategy.

One simple way, better than random choice, is to use modification of one step ExpectiMax. Each round you will give each Objects Value some new estimated value V(obj).

V(obj)= $\frac{ObjectValue(obj)}{ ( 1+ \sum\limits_{i=1}^n P_{i}(obj) )}$

where $ P_{i}(obj)$ = probability that person i will chose Object obj

And every round you will chose the one Object with greatest estimated value V.

You can choose at the beginning  $ P_{i}(obj)$ to be some function over the Object Value- the bigger the value the greatest probability that it will be picked.

Learning:

From your question "Note that keeping track of other player's decisions and their accumulated values can help in future decision making." and your comment  "(learning opponent strategy under uncertainty) " I guess that you need to learn the strategies of your opponents.

One way is after each game to see which Object Value was picked by each of your opponents and how the picked value differs from your expectations ($ P_{i}(obj)$). Using this information you can slightly modify the probabilities $ P_{i}(obj)$ (decrease or increase them a little for specific Object Values) and use the improved probabilities for each of the opponent in the next rounds s.


Relationship between inductive families and type-returning functions Dependently typed languages such as Agda support inductive families, also called indexed datatypes, which allow type parameters to vary between constructors. This can be used to define a set of relations between types, which can be used to constrain existentials. For example, we can capture the relation
$$\begin{align*}
\mathsf{Unit} &\longmapsto \mathsf{Bool}\\
\mathsf{Nat} &\longmapsto \mathsf{Int}
\end{align*}$$
in the following Agda type:
data Link : Set → Set → Set where
  link-a : Link ⊤ Bool
  link-b : Link ℕ ℤ

We can then define a type Tie that pairs a value of type Link A B with a function A → B:
data Tie (L : Set → Set → Set) : Set₁ where
  tie : ∀ {A B} → L A B → (A → B) → Tie L

Just for further illustration, here are a few examples of working with these types:
tie₁ : Tie Link
tie₁ = tie link-a λ tt → true

tie₂ : Tie Link
tie₂ = tie link-b λ n → + n

app-tie : Tie Link → ℕ → Bool ⊎ ℤ
app-tie (tie link-a f) _ = inj₁ (f tt)
app-tie (tie link-b f) n = inj₂ (f n)

This is a useful technique, and this pattern is common in languages like Haskell (where inductive families correspond to GADTs). However, in Agda, the construction is somewhat awkward, as Tie belongs to Set₁ rather than Set due to the need to existentially embed A B : Set in the tie constructor.
I find this unsatisfying, as a simple rearranging of our types allows a definition of Tie that belongs to Set. Instead of defining Link as an inductive family, we define it as a combination of an index and a type-returning function:
data LinkI : Set where
  link-a′ : LinkI
  link-b′ : LinkI

Link′ : LinkI → Set × Set
Link′ link-a′ = ⊤ ,′ Bool
Link′ link-b′ = ℕ ,′ ℤ

Now we can define a version of Tie that contains no types and therefore belongs to Set:
data Tie′ {I : Set} (L : I → Set × Set) : Set where
  tie′ : (i : I) → uncurry′ Morphism (L i) → Tie′ L

At first blush, we seem to be able to do all the same things with this formulation:
tie′₁ : Tie′ Link′
tie′₁ = tie′ link-a′ λ tt → true

tie′₂ : Tie′ Link′
tie′₂ = tie′ link-b′ λ n → + n

app-tie′ : Tie′ Link′ → ℕ → Bool ⊎ ℤ
app-tie′ (tie′ link-a′ f) _ = inj₁ (f tt)
app-tie′ (tie′ link-b′ f) n = inj₂ (f n)

However, this indirect encoding is annoying to work with. Seeing as the transformation is entirely mechanical, intuitively it seems we ought to be able to somehow achieve Tie Link : Set while retaining Link as an indexed type, but it isn’t clear to me that this is actually possible.
Given the above context, my question is threefold:

Are Tie and Tie′ meaningfully distinct, in the sense that Tie allows doing things that Tie′ does not? If so, what?

One can argue that tie does in fact contain A B : Set while tie does not, so Tie must surely belong to Set₁. But the types A and B can always be easily reconstructed from Link A B, so surely they don’t need to be stored, in a similar sense to that described in Inductive families need not store their indices. Is this reasoning flawed, or is this simply an implementation infelicity?

Has the relationship between these two constructions been treated explicitly in any existing literature?

As mentioned by Andrej, this is an instance of transporting along an equivalence of families and display maps. In this specific case, we have an equivalence of graphs and relations.
open import Function
open import Data.Product
open import Relation.Binary.PropositionalEquality
open import Level renaming (zero to lzero; suc to lsuc)

-- type of relations on a set
Rel : ∀{i j} → Set i → Set (i ⊔ lsuc j)
Rel {i}{j} V = V → V → Set j

-- type of graphs with set of vertices V
record Graph {i j}(V : Set i) : Set (i ⊔ lsuc j) where
  field
    E   : Set j   -- edges
    src : E → V   -- source vertex
    tgt : E → V   -- target vertex
open Graph

Rel→Graph : ∀ {i j V} → Rel {i}{j} V → Graph {i}{i ⊔ j} V
Rel→Graph R = record {
  E   = ∃₂ λ s t → R s t ;
  src = proj₁ ;
  tgt = proj₁ ∘ proj₂ }

Graph→Rel : ∀ {i j V} → Graph {i}{j} V → Rel {i}{i ⊔ j} V
Graph→Rel {V} G s t = ∃ λ e → (G .src e ≡ s) × (G .tgt e ≡ t)

Note that we can only define the round-tripping functions if i ≤ j, since then the output i ⊔ j level becomes j, and the trip is well-typed. Your Link definition does not fit into this, but it's possible to just redefine it as Link : Set → Set → Set₁ without loss of generality (as the two definitions are equivalent).
If the levels check out, we can show that round-tripping in both directions yields equivalent relations and graphs respectively. We don't need to know anything about the internals of the relations and graphs involved; this equivalence always holds.
Your transformation makes use of the fact that the set of edges for the graph is equivalent to a small set, since the relation only has two possible edges.
open import Data.Unit
open import Data.Bool
open import Data.Integer
open import Data.Nat

data Link : Set → Set → Set where
  link-a : Link ⊤ Bool
  link-b : Link ℕ ℤ

-- the graph of Link
Link' : Graph Set
Link' = Rel→Graph Link

-- an equivalent graph with smaller edges
Link'' : Graph Set
Link'' = record {
  E   = Bool ;
  src = λ {false → ⊤; true → ℕ} ;
  tgt = λ {false → Bool; true → ℤ} }

Now, anything which depends on an edge only needs do depend on a Bool. In particular, Tie' Link'' : Set.
record Tie {j} (R : Rel {_}{j} Set) : Set (lsuc j) where
  field
    E   : ∃₂ λ A B → R A B
    fun : proj₁ E → proj₁ (proj₂ E)

record Tie' {j} (G : Graph {_}{j} Set) : Set j where
  field
    E   : G .E
    fun : G .src E → G .tgt E

The equivalence of graphs and relations generalizes to relations of any arity, and also to multiple relations of arbitrary arities, where relations can be indexed over other relations. In general, the equivalence says that for each telescope of dependent n-ary relations, there is a direct category $C$ such that the telescope is equivalent to the set of functors from $C$ to $\textbf{Set}$.
In the case of graphs, $C$ has two objects and two arrows between them, going in the same direction, so a functor $F : [C,\textbf{Set}]$ consists of two sets $V,E$ and two functions $src, tgt : E \rightarrow V$, so we can see that every $F$ is a graph.

Are Tie and Tie′ meaningfully distinct, in the sense that Tie allows
doing things that Tie′ does not?

They are equivalent, we get one from the other by transporting the parameter along the graph-relation equivalence.

Seeing as the transformation is entirely mechanical, intuitively it
seems we ought to be able to somehow achieve Tie Link : Set while
retaining Link as an indexed type, but it isn’t clear to me that this
is actually possible.

If we're working in cubical Agda, the graph-relation equivalence can be proven using univalence. Then, every possible construction which depends on relation can be transported to another which depends on a graph. Additionally, everything which depends on Link can be transported to depend on Rel→Graph Link. So at least this part works completely automatically.
However, the resizing part is not automatic, i.e. we have to prove that Rel→Graph Link is equivalent to Link'' with the small set of edges. It is not true in general that the set of edges for a relation is smaller than the set of vertices. Probably it's possible to have a conservative algorithm which tries to find such resizings, I don't think it has been researched.

... in a similar sense to that described in Inductive families need
not store their indices. Is this reasoning flawed, or is this simply
an implementation infelicity?

The technique in "Inductive types need not store their indices" is related but not exactly the same thing. In that paper, the transformation is a bit more restricted & specific thing, as there the point is to convert an inductive type family to a purely recursive one. The family-display map translation can be also used to get rid of indices, but that works in a "non-algorithmic" and different way. A classic example is vectors.
Let's have Vec A : ℕ → Set. We have an equivalence between ℕ → Set and Σ Set λ A → (A → ℕ) (as another case of the family-display map equivalence).
open import Data.Vec
-- Vec : Set → ℕ → Set

Vec' : Set → Σ Set λ A → (A → ℕ)
Vec' A = ∃ (Vec A) , proj₁

But now we can notice that ∃ (Vec A), the so-called "total" type (analogous to the type of edges previously) is equivalent to List A.
open import Data.List

Vec'' : Set → (∃ λ A → A → ℕ)
Vec'' A = List A , Data.List.length

Now, we can convert back to the family version with the generic equivalence:
Vec''' : Set → ℕ → Set
Vec''' A n = ∃ λ (l : List A) → Data.List.length l ≡ n

Which is a definition of vectors which does not store indices. But this is more like a hint, and this de-indexing does not work in a mechanical way, unlike the "need not store indices" technique.

Has the relationship between these two constructions been treated
explicitly in any existing literature?

I don't know of any reference which is exclusively about this equivalence, but it's commonly featured in category theory and type theory (or math in general). The two definitions of graphs is a classic example. There's also the equivalence of indexed categories (family version) and fibrations (display map).


CNF: Recursion in CFG How can I deal with recursive terminals in CFG when converting it to CNF? For example,

S -> MN

M -> AM | A

N -> BN | B

A -> a

B -> b

How can I reduce terminals M and N?

In your example the problem is in the so-called chain productions $M\to A$ and $N\to B$. Just look how these single nonterminals can finally be rewritten into terminals: $M \Rightarrow A \rightarrow a$. Remove the $M\to A$ chain production and replace it by $M\to a$.

In general, if we have any sequence of nonterminals $X_1 \Rightarrow X_2 \Rightarrow \dots X_n \Rightarrow c$ add the production $X_1\to c$. Then remove the chain productions of the grammar.

Recursion in general is not a problem. It is the essence of context-free grammars! The only requirement of Chomsky Normal Form is that productions are of the form $A \to BC$ and $A\to a$ with $A,B,C$ nonterminals (=variables) and $a$ terminal (letters).


Algorithm to find individual, closed groups of lines in a large set of connected lines I'm currently trying to write an algorithm that can find individual groups of connected lines within a larger set of lines. The images below should explain this a bit more clearly.

In the first image you can see a set of lines. What I'm trying to do is split those lines into 3 groups, as seen in the second image. The red and green groups share a line.

I can assume that each line has a start and an end coordinate, and each line can belong to one or more groups.

I'm currently trying to write a recursive function that follows each line until it reaches an end point with one or more lines it can follow. At this point the function recalls itself until it's followed the lines back round to the split point. However this is proving unsuccessful.

The output of this example, as shown in the second image, should be 3 separate groups of lines, stored in a list. I'm currently using c#, however I should be able to use a suitable algorithm in any language, including pseudocode. I know there must be an algorithm that can achieve this, however I cannot seem to work it out or find it online.

Assuming you essentially want to partition the 2D space into pieces using the given lines and border where

no two pieces overlap
all pieces sum to the original space
all the pieces primitive i.e. can not be split further

Consequently, there is a nice property that each line that actually border a polygon will be between exactly 2 polygons. This is more apparent when thinking about the notions of dual graph of plane graph

Note the outer partition piece formed with the border of the whole picture.
Algorithm
Initialise
Each line has 2 pointer to be pointed to the partition it borders (red dot).
These pointer are initialised to empty.
Our algorithm terminates when all of these pointers are non empty.
Main

Pick a line with at least one still empty partition pointer.
Walk along the adjacent edge that makes the least angle from the side of the line that still has a free pointer. (do remember the properties of vector's cross product and dot product. These will be your tools in calculating the angle and determining the side.)
[If there is no adjacent line to walk at all, you need to mark the current line as not being part of any polygon and backtrack]
Once you complete a cyclic walk, update all the "sides" used and point them to a newly created "partition" object.
Repeat step (1) until all lines has been assigned 2 pointers to its bordering partition. (except if that line is marked as not a part of any polygon or is the border of whole picture.)


Linear time algorithm for array with distinct element Given an array, if all the elements are distinct, can we find the count of elements which are lesser than an element and present to the left of that element in linear time if we have to do it for every element.

I know this can be solved in O(nlogn) time by using self balancing trees, but I want to know whether we can solve it in O(N)?

You cannot do it in linear time using only comparisons. If you could, then you could do it for the array and its reverse in $O(n)$ and then for each element determine in $O(1)$ its position in the sorting of the array. This gives a comparison-based linear time sorting algorithm, which we know cannot exist.

You have to tell us more about the domain of the elements in the input array if you want to get an $o(n \log n)$ algorithm. For example, do you have a constant upper bound on the value of the maximum element?


Naming facts exported from blocks in Isabelle/HOL I'm using Isabelle/HOL.  Isabelle exports the last fact in a block, allowing the context that contains the block to use it.  Ordinarily when I generate facts, I can give them convenient names.  How do I name facts that are exported from blocks?

Simple example:

lemma mylemma: "i=i"
proof -
  {
      fix j::nat
      have "j=j" by auto
    }

    show ?thesis using ‹⋀j. j = j› by auto
  qed

Right now I use ‹⋀j. j = j› to refer to the exported fact as a proposition literal.  I'd like to be able give it a simple name, though, as when I named the lemma mylemma.  Thanks for any suggestions!

From section 1.1.2 in the document isar-ref: you can reference facts via explicit name, implicit name and literal position. In this case, the explicit name has not been provided. I believe that the canonical method to provide an explicit name is to reference the fact of interest by its implicit name immediately after the end of the block. For example,

lemma mylemma: "i = i"
proof -
  {
    fix j :: nat
    have "j = j" by auto
  }
  note name = this
  show ?thesis using name by auto
qed

As a side remark, I would like to mention that general questions about Isabelle or the syntax of Isar are best posed on Stack Overflow. I believe that this would drastically increase the chances of your questions being answered promptly.


Defining a graph decision problem not in NP I have been doing some research online looking for graph problems that are decidable but not in NP. I have found the concept of succinct graphs, which if I understand properly, consist of making the input small (i.e. supplying the graph structure using a small amount of memory) so that when properties of the graph are checked, the time taken is larger than polynomial on the size of the input (and so taking problems that are in P into NP, and problems that are in NP into NEXP).

What I was wondering is whether you could do something similar but by suppliying the graph in a "standard" way (i.e. adjacency matrix), but then asking a question with a "large" answer. For instance would the following problem not be in NP?

Given a graph G = (V,E), of size n, does it contain 2^n distinct paths of size n?

To me it feels like a a certificate could not be checked in polynomial time, and so this problem cannot be in NP. I was wondering if anyone has thought of something similar, or whether there is something you could check in polynomial time that would answer this question without explicitly listing out 2^n paths.

Any input is greatly appreciated. Thanks!!

Problems of the type "Count the number of [object]", where "[object]" is something that can be verified in polynomial time, are essentially what defines the class $\#P$ ($\textrm{Sharp-}P$). $\#P$ is the counting variant of $NP$.

As pointed out by @D.W., the problem you picked just so happens to be in $P$, but if you had picked some other problem (such as counting simple paths) it would have been $\#P$-complete.

If you take a $\#P$-complete counting problem, then the decision-counting variant ("are there at least $x$ many objects [...]") can not be in $NP$, unless the polynomial hierarchy collapses. This follows by Toda's theorem, which states that $PH\subseteq P^{\#P}$. If such a decision-counting problem would be in $NP$, we could use a polynomial number of calls to an $NP$ oracle to compute the exact number (by binary search). Thus $P^{\#P}$ would be equal to $P^{NP}$ and the polynomial hierarchy collapses.


About the notation of XOR-SAT I am a bit confused by the notation here, http://www.boazbarak.org/sos/files/lec3.pdf

Given 3 Boolean variables $x_i, x_j, x_k$ what is supposed to be the meaning of $x_i \oplus x_j \oplus x_k$?

Is this to be understood as say $((x_i \oplus x_j )\oplus x_k )$? And hence this is true for only $2$ cases $x_i =0, x_j = 1, x_k =0$ and $x_i = 1, x_j = 0, x_k = 0$ ?

But then we could have bracketed it as $(x_i \oplus (x_j \oplus x_k))$ and then the only true assignments would have looked as $x_i = 0, x_j =1, x_k = 0$ and $x_i = 0, x_j =0, x_k = 1$ and these are different.

Also one could have used commutativity to write it in other re-arranged forms and gotten different true selections!
But then the note above seems to claim that if the $x_a$s are coming as coordinates of a vector $x \in \{\pm 1\}^n$ then the product $x_ix_j x_k$ is the same as having a linear equation in those $3$ variables. Why so? (for example an assignment $x_i = x_j = x_k =1$ will evaluate to $1$ for the product but under mod 2 arithmetic $x_i + x_j + x_k = 0$ for this assignment!)

Also it is being claimed that the value of $x_ix_jx_k$ can only be $\pm 1$ (which they denote as $a_{ijk}$) for $x \in \{\pm 1\}^n$ and that is okay only if one ignores the first claim that these are supposed to be linear equations!

This $x_ix_j x_k$ product notation looks more confusing later on when they say that corresponding to two subsets $S, T \subset \{1,..,n\}$ one can take two expressions of the form $x_S = \prod_{i \in S} x_i$ and $x_T = \prod_{i \in T} x_i$ and construct $x_U = x_S x_T$ and that this somehow corresponds to doing ``$U = S \oplus T$" - and I don't know what it means to take a XOR of two subsets!

XOR is an associative operation, so $x_i \oplus x_j \oplus x_k$ is unambiguous. There are in fact four satisfying assignments, given by
$$ (x_i,x_j,x_k) \in \{(0,0,1),(0,1,0),(1,0,0),(1,1,1)\}. $$

XOR satisfies the useful property
$$ (-1)^{x \oplus y} = (-1)^x (-1)^y. $$
Therefore $x_i \oplus x_j \oplus x_k = 1$ is the same as
$$ (-1)^{x_i} (-1)^{x_j} (-1)^{x_k} = (-1)^1.$$
If we think of our variables as $X_i = (-1)^{x_i}$, then the equation $x_i \oplus x_j \oplus x_k = 1$ is completely equivalent to $X_i X_j X_k = -1$. Since XOR is really just addition in the group $\mathbb{Z}_2$, you can think of both formulations as linear equations.

Yet another interpretation of XOR is in terms of sets. Just as AND corresponds to intersection and OR to union, the XOR operation corresponds to symmetric difference, sometimes denoted $\triangle$ or $\Delta$. You can easily check that $x_S x_T = x_{S \triangle T}$, essentially using $x_i^2 = 1$.


Is the following problem decidable in polynomial time? We are given an initial set of tuples $S_0=\{(x_i,y_i)|i\in [n], \forall i:x_i,y_i\in \mathbb{N}\}$ and a number $B\in \mathbb{N}$.

At time $t$ we are allowed to remove ($S_t := S_{t-1} \setminus \{(x_i,y_i)\}$)

a pair $(x_i,y_i)\in S_{t-1}$:  if $$x_i + \Sigma_{j:(x_j,y_j)\in S_{t-1}, j\neq i} y_j \geq B$$.

(That is if the sum of $x_i$ and the rest of the $y_j$'s is at least $B$ we're allowed to remove tuple $i$).

The problem is finding a sequence of tuples which can be legally removed, and leave a minimal cardinality set (i.e. remove as many tuples as possible).

Is this problem in $P$ as it is?

What if we know that $\forall i:y_i\leq x_i$?

Example: Assume $S_0 = \{(5,3),(5,5),(1,1),(6,0),(2,2)\}, B=10$ then $(<1,1>,<6,0>,<2,2>,<5,3>)$ is an example of a maximal output sequence.

This is a nice exercise, such as one might find in an undergrad-level algorithms class.  (Congratulate your professor on selecting such a nice exercise.)  Since it's your exercise, I'm going to let you solve it, but I'll give you a series of hints.

Important: Spend at least an hour exploring each hint, before moving on to the next hint.

Hint #1:

  When given an algorithms problem, it is often very helpful to look at some small examples and work out what's going on by hand.

  So, pick a sample problem instance with 3 items (generate the $x_i,y_i$'s arbitrarily); map out all possible timelines (all possible sequences of item removals); and see what you see.  Do another example with 3 items.  Try one with 4 items.  Do a few such examples, and see if you can build some intuition.  I suspect you'll spot what is going on, and then from that you might be able to figure out how to solve the problem.

Hint #2:

   What chapter of the textbook are you currently in?  This is often a good heuristic to help you select a type of algorithm to try.

Hint #3:

   A natural algorithmic approach is to use a greedy algorithm: if multiple items are currently eligible for removal, select the item whose $y_i$ value is _____.  (You fill in the blank.)  So, see if you can determine whether you can find any way to fill in the blank that provides a correct algorithm for your problem.  This gives you a few candidate algorithms; for each candidate, see if you can prove or disprove its correctness.  To do that, try some small examples.  See if you can find a proof of correctness or a counterexample demonstrating it is incorrect.  Once you've worked out whether there is any algorithm of this form that is correct, you should be able to answer your question.

Hint #4:

   If you've tried all of the above diligently, show us your work and where you got stuck and I'll give you one more hint.


What is the exact relation between programming languages and Turing machines? I don't know much about yacc, bison, flex or lex and please correct me if I'm wrong but a programming language is also a Turing machine and a Turing machine is defined as the tuple $(Q, \Gamma, b, \Sigma, \delta, q_0, F)$ where $Q$, $\Gamma$, $b \in \Gamma$, $\Sigma \subseteq \Gamma \smallsetminus \{ b \}$ as input, $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{ L, R, N \}$ as transition function where $L$ = number of steps to the left, $R$ = number of steps to the right, $N$ = "standby", $q_0 \in Q$ is the initial state and $F \subseteq Q$ is the set of end states.

How similar is implementing a programming language to implementing a Turing machine? Can it be said that what is done when a programming language is implemented is that a Turing machine like the above is defined? If yes, how come we can't just use a model that looks like the definition of a Turing machine when a programming language is defined? Instead something else like BNF seems to be the standard.

Maybe I'm misreading the question, but it sounds like there's some confusion in the comparison between Turing machines and programming languages.

The definition and method of defining a Turing machine constitute a programming language. Turing machines represent programs in that language.

Language syntax and semantics (e.g., in BNF) can constitute a programming language, and artifacts which satisfy those syntactic and semantic constraints are programs in that language.

So it's not really precise (IMHO; of course we can think about what TMs do in different ways, and in some of these ways of looking at TMs, you could think of individual TMs as defining programming languages. Indeed, a classically constructed universal Turing machine defines a very clear programming language, i.e., representations of Turing machines as strings) to compare implementing a programming language to implementing a Turing machine. Implementing a programming language involves defining the rules of the game, much like Turing defined the rules of the game (or whoever it was, whatever) when he defined what it meant for something to be Turing machine.

"Implementing" a programming language, and defining Turing machines, is a very difficult activity. Writing programs in a language, and defining specific Turing machines, is also a difficult activity. But they are quite different activities (except in those exceptional cases where you're writing a Turing machine to act as an interpreter, in which case maybe it makes sense to talk about designing a programming language via writing a TM... but I'm not sure this is what you were after).


Hash function to return only positive number from integer What would be a good hash function that will return a positive integer value, even if the key is an negative integer value? How do I pick a hash function? So what I would want is to associate negative numbers with some positive value so I can use them later.

UPDATE: (summary)
I need to find a bijection $f: \mathbb{Z}\to\mathbb{N}$ which also has the property that:
$$
f(x) + f(y) = f(x + y)
$$

From your comments, it appears all you need a bijection from $\mathbb{Z}$ to $\mathbb{N}$ that is easy to compute.

The simplest one I can think of: $x \mapsto 1/2 + 2 \mid\!(x - 1/4)\mid$.

This isn't really a hash function: it doesn't "hash" (scatter its consecutive function values across their range).


Linear and almost-linear perfect hashing I am trying to understand the sentence from a paper by Patrascu:

  Unfortunately, we do not have linear perfect hashing. Instead, we use a family of hash functions.... with almost-linearity

The context is a reduction between two variants of the 3-SUM problem:

In the usual variant, 3SUM, given an array $A$ we have to find 3 indices $i,j,k$ such that: $A[i]+A[j]=A[k]$.
In the other variant, Conv3SUM, we have to find 2 indices $i,j$ such that: $A[i]+A[j]=A[i+j]$.

Theoretically, we could reduce 3SUM to Conv3SUM if we had a linear hash function - a function $h$ such that: $h(x+y)=h(x)+h(y)$, and that maps all elements of $A$ to the range of indices $\{0,...,n-1\}$

The reduction is by sending every element of $A$ to an index determined by $h$, i.e. create an array $B$ such that for every $x\in A$: $B[h(x)]=x$

Then, if there is a solution to 3SUM on A, $x+y=z$, then on B we will have: $B[h(x)]+B[h(y)]=B[h(z)]$, and by the linearity of $h$ also $h(x)+h(y)=h(z)$, so this is a solution to Conv3SUM on B.

Conversely, every solution to Conv3SUM on B is trivially a solution to 3SUM on A, since every element of B is also an element of A.

Unfortunately, we do not have linear perfect hashing, so we have to use a family of almost-linear hash functions.

MY QUESTION IS: why do we have perfect almost-linear hash functions and not perfect linear hash functions? How does almost-linearity make it easier to find perfect hash functions?

I think there is a constraint that the domain of the hashing function must be {0...n-1}, where n means the number of elements to hash. Only defining in this way , the reduction from 3SUM to Conv3SUM works.

The is an almost-linearity function in wiki. And it is easy to figure out a counter example for the existence of perfect linear hashing function.

Consider the following questions:

Let A = {1,2,3,4}, B={0,1,2,3}

how many triples (x,y,z) satisfy x+y=z, where x,y,z are in A and distinct！
what if x,y,z are in B

The answer of the first question is

1+1=2
1+2=3
1+3=4
2+2=4

But there are only two triples in the second question. You can find out a bijective function, satisfying that linearity property, mapping A onto B .


Possible partitions, for k-means problem(k=2) I have this brute-force algorithm to solve the problem:

Generate all possible partitions of P into two subsets of P1 and P2

For each partition P1, P2 generated in Step 1, compute the cost of the partition

Report the partition with the lowest cost found in Step 2.

How can I analyze the number of possible partitions and use that to determine the running time?

If $(P_1, P_2)$ is a partition of $P$, that means that $P_2 = P\setminus P_1$.
That means that is suffices to count the number of possible choices of $P_1$, which is the cardinal of the powerset of $P$, $|\mathcal{P}(P)| = 2^{|P|}$.
If $P_1$ and $P_2$ have symmetrical roles, you can divide the result by $2$ (but it does not change the asymptotical complexity).


Is P = NP when solutions length is polynomially bounded by instance length? I'm currently reading the book "P, NP, and NP-Completeness" by Oded Goldreich. I'm currently reading a chapter that's concerned with the "search version" of the P-vs-NP-problem, that is if finding solutions is harder than checking the validity of solutions.

First, the book defines "polynomially bounded relations" as relations (between problem instances x and their solutions y) where there exists some polynomial p such that the length of the solution is polynomially bounded by the length of the related problem instance (that is |y| <= p(|x|)).

Both the search problem as well as the checking problem are then defined on such bounded relations.

Now I wonder: Doesn't polynomially bounding the length of possible solutions to a given instance mean that there are only polynomially many possible solution candidates, which, when given an algorithm C that checks a solution for its validity in polynomial time, implies that finding a solution can also be done in polynomial time by simply checking each of the possible solutions for its validity?

This would mean that if I can efficiently check solutions of a problem for validity, then I can also efficiently find solutions to that problem. (So, basically P = NP)

Is this conclusion - when only looking at polynomially bounded relations - true? (The book of course says that it's not. If I'd need to bet I'd also bet on the book and not on me...)

If not, where is the error in my reasoning?

You ask

  Doesn't polynomially bounding the length of possible solutions to a given instance mean that there are only polynomially many possible solution candidates?

In fact, the number of binary strings of length $n^c$ is $2^{n^c}$, which is exponential in $n$.


What are the justifications and historical reasons regarding the choice between the words 'calculus' and 'algebra'? The principles of calculus, historically, are differentials and integrals [1], while those of algebra are operators and equation solving [2]. Contemporary principles are analysis and abstract objects, respectively.

As an example case, why is relational algebra not called a calculus, and why is the π-calculus not called an algebra?

What is in a name? Calculus is called analysis in some  languages
other than English, while the word calculus itself means computation.

The name π-calculus was most likely chosen by Milner because it has
to do with computation, and is intended to be for parallel computation
similar to what $\lambda$-calculus is for classical sequential computation.
Computation is actually the original meaning of calculus,
referring to pebbles used as counters in ancient time.

The word algorithm, as everyone knows, comes from the name
al-Khwarizmi (the man from Khiva, a city formerly called Khwarezm), given to the 9th century Persian
mathematician Abū Ja‘far Muhammad ibn Mūsa. Algebra comes from the
name of the treatise Hisab al-jabr wa'l muqabala, that he wrote about
the resolution of equations.

Al-Khwarizmi systematized the study of equations (algebra), and gave
procedural techniques to solve them (algorithms), which implies some form of computation (calculus). Could this be seen
as a kind of Curry-Howard situation, where the mathematics for proving
go in hand with the corresponding algorithms to actually compute ?

Names may be chosen for strange reasons, and their meaning evolves
along with the objects they initially denote. The internationalization of sciences also leads to different interpretations of words, as the same word (or its local variant) may have a different meaning in different country (and that is also true is other areas of language, possibly creating some awkward situations).

This issue has already been discussed on math.SE.

Further remarks

Actually, according to wikipedia, Analysis is used in all languages,
English included, with the same meaning. English appears to use the
word Calculus which refers only to elementary concepts of Mathematical
Analysis, differential and integral calculus. If you look for the
English Calculus in wikipedia, you find out that translation is
missing for many languages (no equivalent entry in German or French
for example), and when an entry is proposed for another language it
may corresponds to a different meaning (Cálculo in Spanish is for
calculation or computation, as it is in some other languages).

However, Cálculo in Portuguese has the same meaning as in English and
covers the same topics. They actually explain, for Portuguese, the
origin of this use of the word, and the explanation is likely to be
the same in English. Calculus is very simply an abbreviation for
"differential and integral calculus". And indeed, it corresponds to
computations expressed with algorithms, and is, in this sense, close
to Algebra.

I was mislead, in understanding the question and writing the first
part of my answer, because I took Calculus to mean the whole of
Mathematical Analysis, as there is no single word in my own language
to cover specifically differential and integral calculus. Comments
show that I am not the only non-american user to be thus mislead.

Hence there is no linguistic inconsistency. The name λ-calculus
denotes a formalisation of algorithms and computation, and the use of
the word calculus is adequate. From it was derived the name π-calculus
for parallel computations.

Note that initially, calculus just means computation (calculation has
a connotation as pertaining to numbers). When applied to a specific
domain, it is qualified so that the domain is explicit (integral
calculus, π-calculus, ...). The problem comes from the fact that it
has a common use in some languages, including English and Portuguese,
where it is domain specific without making the domain explicit, while also retaining its more general use.


Have non-regular language classes of infinite words been studied? For regular languages we have $\omega$-regular languages which extend them to infinite words.

Are there such extensions for CFG's, CSG's and recursively enumerable languages?

We have the following MSO characterization of regular nested word languages:

  Regular languages over nested words are exactly the set of languages described by Monadic second-order logic with two unary predicates call and return, linear successor and the matching relation ↝.

The recommended reference on Nested Words and Visibly Pushdown Languages treats infinite words in section 8. Nested $\omega$-Words, and shows that the MSO characterization carries over:

  Theorem  8.4 (MSO characterization of $\omega$-languages).
  A language $L$ of nested $\omega$-words over $\Sigma$ is regular iff there is an MSO sentence $\varphi$ over $\Sigma$ that defines $L$.

Because often deterministic CFGs are actually visibly pushdown languages, this covers a huge portion of the practically relevant CFGs. Moreover, this even provides a context where considering $\omega$-languages is practically relevant, as explained in the same section of the reference.


Can there be 'dead states' in a context-free grammar? Can a context-free grammar include "dead states" from an automaton, such as

$$G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,?$$

The production rules $B\to C$ and $C\to cC$ will loop forever and never generate a word. Is this allowed or MUST production rules end with an terminal at some point?

Context-free grammars are allowed to contain unproductive rules. This is accepted, because every CFG generates the same language as some proper CFG which contains no unproductive rules, no empty string productions, and no cycles; so it is safe to assume that a CFG is proper without loss of generality.


Is a Karp–Levin reduction a Levin reduction? My understanding is that Karp many-one reductions are more general than Levin many-one reductions, and that Levin many-one reductions must allow for the number of certificates for a problem $A$ reduced to $B$ to be recovered from a single oracle call giving the number of certificates for $B$.

So, what exactly is a Karp–Levin reduction? Quoting the paper "Witness Encryption and its Applications",

  We now formally describe our encryption systems. For building them we will assume the existence of a witness encryption scheme for an NP-Complete language $L$ for which there exists a Karp–Levin reduction. We focus on presenting the constructions in this section and defer the proofs to Appendix A.

Other instances of "Karp–Levin" reductions can easily be found elsewhere.

From slide 11 of this presentation on PCPs by Mario Szegedy, it seems like a Karp–Levin many-one reduction is just a Levin many-one reduction. Is that correct?

Update: To explain why I am uncertain about Yuval Filmus' answer below, and why I'm asking this question, quoting from page 17-4 of the "Hardness of Approximation" chapter of the Handbook of Approximation Algorithms and Metaheuristics, a chapter written by Mario Szegedy (a Godel prize winner for his contributions to the PCP theorem),

  Reduction is perhaps the most useful concept in algorithm design. Interesting, it also turns out to be the most useful tool in proving computational hardness [21-23]. When a problem $A$ Cook reduces to $B$, the hardness of $B$ follows form the hardness of $A$. Unfortunately, Cook reduction does not ensure that if $A$ is hard to approximate then $B$ is hard to approximate. For reducing hardness of approximation new definitions are necessary.

  Let $F_1(x, y)$ and $F_2(x', y')$ be functions that are optimized for y and y' (maximized or minimized in an arbitrary combination). Let $OPT_1(x)$ and $OPT_2(x')$ be the corresponding optimums. A Karp–Levin reduction involves two maps:

  a polynomial-time map $f$ to transform instances $x$ of $OPT_1$ into instances $x' = f(x)$ of $OPT_2$ [Instance Transformation];
  a polynomial-time map $g$ to transform (input, witness) pairs $(x', y')$ of $OPT_2$ into witnesses $y$ of $OPT_1$ [Witness Transformation];

  Observe that the witness transformation goes from $OPT_2$ to $OPT_1$. Let $opt_1 = OPT_1(x)$, $opt_2 = OPT_2(f(x))$, $appr_1 = F_1(x, g(f(x),y'))$, and $appr_2 = F_2(f(x),y')$.

So Yuval Filmus' answer below appears to only cover the "[Instance Transformation]" part of a Karp–Levin reduction, and not the "[Witness Transformation]" part, which seems to be interpretable as a way to recover certificates from some problem $A$ in $NP$ reduced to $B$ in $NP$ provided the number of certificates for $B$.

Am I off the mark here?  And how is a Karp–Levin reduction different from a Levin reduction?

If there is non-standard terminology, or if definitions are supposed to be "understood" depending on whether one is talking about reductions among perhaps counting problems where witness transformations matter, please understand that this is intimidating for someone coming from outside of computer science!  People's patience here is very much appreciated.

A Karp reduction from a language $A$ to a language $B$ is a function $f$ such that $x \in A$ iff $f(x) \in B$. This is the common meaning of the term.

David Richerby mentions in a comment below that Levin reductions are a more elaborate type of reductions: see this question.

In the present instance, Karp–Levin reduction seems to mean the same as Levin reduction. Indeed, since the common term for the usual notion of many-one reduction is Karp reduction, adding Levin's name might signify something different. The way the term is used in the paper should make it clear which meaning is being used. The paper might also include a definition of this somewhat non-standard term, and I suggest you include such a definition in future papers you may write.


Halting problem vs. automated theorem proving? In the Theory of Computation tutorial offered by Complexity Tree (I just began the 2nd video), it talks about how the Halting problem was developed to show that mathematics could not be automated.  Lately, I've heard quite a bit about automated/automatic theorem proving--some people are even positing that some day mathematicians will be replaced by machines.  My question is: Do we need to find a flaw in the reasoning of the Halting problem to prove that mathematics can be automated?  (Or is the Halting problem, in the age of Machine Learning, reduced to a nice historical account of the past...)

The notion of automating mathematics is a vague one, and that's accounting for the discrepancy here.

One interpretation would be: to automate mathematics would be to produce a machine $M$ which could tell whether or not a given sentence is true (or, more weakly, provable from some agreed-upon set of axioms like $\mathsf{ZFC}$). Even the weaker version is ruled out by the incomputability of the halting problem.

Another interpretation is: to automate mathematics is to produce a machine $M$ which will find proofs of all provable (again, from that agreed-upon set of axioms) sentences. Note that $M$ is not required to determine whether a sentence is provable in the first place, merely to find a proof if such a proof exists at all. This is possible via brute force search.

Of course that second type of automation is highly infeasible - in general, it will take ridiculously long to find proofs of theorems. But that doesn't impact its in-principle-possibility. This is really the starting point of automated theorem proving: trivially brute-force-proof-search is possible, and trivially it's horrible in general - can we find clever proof search strategies in some cases of interest? (And this is where complexity theory enters the picture.)


Is linear-time reduction symmetric? By reduction I mean the following:

  Problem X linear reduces to problem Y if X can be solved with:
  a) Linear number of standard computational steps.
  b) Constant calls to subroutine for Y.

If a problem X reduces to a problem Y, is the opposite reduction also possible? Say

X = Given an array tell if all elements are distinct
Y = Sort an array using comparison sort

Now, X reduces to Y in linear time i.e. if I can solve Y, I can solve X in linear time. Is the reverse always true? Can I solve Y, given I can solve X? If so, how?

No, it is not symmetric.

Here's my counter-example: Consider the language $L_1 = \{A:A'| A'$ is $A$  sorted$\}$
and $L_2 = \{A:a| a$ is the largest element in $A\}$.

We can solve the max-element problem with a constant number of calls to a machine solving sorting. Just sort $A$ then take the first element. But we can't solve sorting with a constant number of calls to a machine solving max-element (otherwise, we could sort in $O(n)$, which is known to be impossible).


What's the advantage of "value restriction" over its alternatives? What is the motivation to pick "value restriction" over other candidates?

Examples of alternatives:

Enclosing pureness into the function type, for example:

pure_function : x -> x
impure_function : x => x

Polymorphism by name (call by name) as in Xavier Leroy, 1993

Xavier Leroy, 1993. Polymorphism by name for references and continuations. In 20th symposium Principles of Programming Languages, pages 220-231. ACM Press, 1993.

I'm sure that this isn't the only advantage, but I think the primary advantage is simplicity. This is even identified in the original paper introducing the value restriction: previous solutions all existed, but the complexity of annotations made them undesirable.

The majority of value that people want to give polymorphic types are functions, which are values, and you can "fake it" with thunks for anything that isn't a value.
The language of types is unchanged, so it's easier for the programmer to use. There is no need for extra annotations or types. The users

In "real world" languages, the solutions falls into two categories. ML-style languages use the value restriction, and Haskell-style language use purity and monadic effects. Rust even uses a more restrictive version of the value restriction, where only top-level functions can be polymorphic.

As is common with PL research, there may be many theoretically sound solutions which don't gain traction in popular languages because of their difficulty or awkwardness of use.


VC Dimension of Origin-Centered Circle Is the VC dimension of an origin-centered circle 1 or 2?

It seems to me that the VC dimension of an origin centered circle should be 1, because for two points with distances from the origin r1 <= r2, r2 will never be able to be labeled 1 without r1 also being labeled 1, so the r1 = 0, r2 = 1 labeling could never be possible.

However, this and this both say that an origin-centered circle has VC dimension of 2.

What you are missing is a definition of origin-centered circles. The definition of the slides (your second link) is wrong, for the reasons you mention. The definition in the lecture notes (your first link) makes it clear that you can choose whether it is the inside or the outside of the circle which gets the value +1, and this shows that any two points whose distance from the origin is not the same can be shattered, and so the VC dimension is at least 2.


Given a λ-term, can I decide which machine model I need to express it? I am having a hard time figuring out the specific relationship, of various things in computability. So we have a hierarchy of machines, with a (real life) upper bound of Turing machines, moving on down to things like deterministic finite automata. We also have a hierarchy of grammars that the machines can implement. These grammars range from recursively enumerable down to things like regular grammars. By implement I mean be configured in such a way that they either accept a string or declare it not part of the language.

The lambda calculus has a grammar. This grammar can be expressed on a low class of machine. The lambda calculus itself though is Turing complete. Clearly the syntax of the lambda calculus has no relationship to the power classification.

While the full lambda calculus is Turing complete you can restrict it in certain ways so that the syntax is the same, but the calculus becomes no longer Turing complete. This is talked about in the Turner paper:

"https://uf-ias-2012.wikispaces.com/file/view/turner.pdf/401400700/turner.pdf".

You could restrict it more, and make it an even weaker machine, until nothing can be expressed. As the version of lambda calculus you are programming in becomes weaker, and weaker, fewer grammars could be implemented.

Noting that the syntax is the same: Given a string representing a lambda expression X. Depending on the content of X only certain classes of restricted lambda calculus (to un-restricted) may be able to execute it. If the expression X requires a Turing machine to implement then a machine restricted to a weaker lambda calculus would not be able to express it.

Is it possible to determine what class of machine is required to express a given lambda expression? Turner in his paper clearly shows that you can restrict the lambda calculus to not require a Turing machine. But just given the expression, can you determine the class of machine?

Paraphrasing, this seems to be your question:

  Given an unrestricted λ-term, can I determine what kind of automaton/machine model I need to express it?

Such properties are inherently undecidable (usually).
Starting with a Turing-complete formalism, Rice's theorem immediately tells you that what you are asking is impossible.

The set of TMs/λ-terms corresponding to any non-empty, non-Turing-complete machine model forms a non-trivial index set and is thus is never decidable.

Of course, if you restrict yourself to a less than Turing-complete base set of terms, Rice's theorem does no longer apply. This is still a tough question to ask, though, even at lower levels of the hierarchy. For instance, it is undecidable if an NPDA accepts a DCFL, if a context-free grammar describes a regular language, or even if a context-free grammar is equivalent to a fixed regular grammar.


Classification of recursively enumerable sets It's quite easy to show that there are only three recursive sets up to m-equivalence, namely $\emptyset,\{1\},\mathbb N.$ Can we state something "similarly short" for recursively enumerable sets, like there are only 4 recursively enumerable sets up to m-equivalence – $\emptyset,\{1\},K,\mathbb N$ (where $K=\{i\mid\varphi_i(i)\text{ is def.}\}$)? More specifically, is every non-recursive recursively enumerable set m-equivalent to $K$?

There are lots of these. Even with respect to Turing reducibility (which extends $m$-reducibility: if $A\not\ge_TB$ then $A\not\ge_mB$), the structure of c.e. sets is extremely rich.
That said, constructing an infinite non-recursive r.e. $A$ with $A<_mK$ is significantly easier than constructing one with $A<_T K$. The former was done by Post in 1944 who introduced the notions of creative and simple sets (each of which are necessarily non-recursive), proved that a simple set exists and that $K$ is creative, and proved that no creative set is $m$-reducibile to any simple set; the latter wasn't achieved until a decade later by Friedberg and Muchnik independently, and required a fundamentally new technique (the priority method).


How many syntax trees can be made by a BNF An example of this would be:
1+2*3+4
Expression = Expression Arithmetic Expression | number
Arithmetic = + | - | * | /
Through just breaking down 1+2*3+4, it was easy to find that the answer was 5 trees.

1+((2*3)+4)

((1+2)*3)+4

1+(2*(3+4))

(1+2)*(3+4)

(1+(2*3))+4
But doing it in this brute force manner wouldn't work on larger more complex BNFs.

I have tried using CYK to get 5 but haven't figured out how, even through they do seem similar enough. Any advice on using any algorithms or strategies to break down larger BNFs to see how many syntax trees they can make would be much appreciated.

The answer is given by the Catalan numbers; if you have $n$ operators, the number of syntax trees is $\frac{1}{n+1}{2n \choose n}$. The problem is equivalent to finding all ways of inserting $n$ parentheses pairs in a word of $n+1$ letters, as mentioned in OEIS:

  Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).

There are several ways to prove this, e.g. via the Dyck language. The Wikipedia article contains several ones.


P-Completeness and Parallel Computation I was recently reading about algorithms for checking bisimilarity and read that the problem is P-complete. Furthermore, a consequence of this is that this problem, or any P-complete problem, is unlikely to have an efficient parallel algorithms.

  What is the intuition behind this last statement?

Any $P$-complete problem, is unlikely to have an efficient parallel algorithm. Why ?

The existence of $P$-complete problems is the most important clue that $(P ∩ POLYLOGSPACE) ≠ P$.
The question then is, why is this conjecture relevant to parallel computing?
Let's start with the resources used in a computation. For sequential computing: time and space; for parallel computing: time and hardware (number of processors).
Is there a relation? Yes!
Sequential space ↔ parallel time; Sequential time ↔ parallel hardware.
The correspondence between sequential space and parallel time seems to be independent from the parallel computing model adopted; this leads to the following,  so called parallel computation thesis which is unproven.

(Chandra and Stockmeyer) Every computation of a TM with space complexity $S(n)$ can be simulated in a parallel computing model in time $T(n) = O(S(n)^{O(1)})$ and every computation of a parallel computing model with time complexity $T’(n)$ can be simulated by a TM with space complexity $S’(n) = O(T’(n)^{O(1)})$.

The class of problems solvable sequentially in polynomial space is $PSPACE$ and the set of problems solvable in polynomial time is $P$.Since $PSPACE$ is thought to be a much larger class of problems than $P$, the thesis quantifies the effective improvement made possible by parallelism. A consequence of this thesis is that a PRAM can solve $NP$-complete problems in polynomial time…
Unfortunately, no!
The parallel computation thesis implies that we can actually deal with problems belonging to $PSPACE$… but this requires an exponential number of processors!
A time-space trade-off is working: The exponential time on the sequential computing model is transformed into an exponential number of processors on the parallel computing model, whereas the polynomial space on the sequential computing model is transformed into a polynomial time on the parallel computing model.

This trade-off is easier to understand if we try to restrict both parallel time and parallel hardware: if the parallel computing model has a polynomial number of processors, then the class of problems solvable in parallel polynomial time is $P$.
If we restrict the number of processors to a polynomial we can improve the performances of a sequential machine, but no more than a polynomial factor.
Thus we can reduce the degree of the polynomial representing the time complexity, but we are not able using parallelism to reduce exponential costs to polynomial costs.

The problems solved in parallel with polynomial time complexity are those problems belonging to $P$. The polynomial constraint on the number of processors leads to a parallel computing model equivalent to TM.
There are two important practical considerations:
which polynomial number of processors is acceptable/affordable ? In practice, the polynomial number of processors is meant to be linear or close. Which subpolynomial time is achievable ? It turned out that almost all highly parallel feasible problems can achieve polylogarithmic parallel time.
In parallel, a time complexity which is logarithmic in the input length represents an efficient parallel computation.
A parallel algorithm is considered efficient if, given a polynomial number of processors, its time complexity is polylogarithmic.

Given a problem $R \in TIME\_SPACE_{TM}(n^k, (log n)^h)$ where $k$ and $h$ are constants, the parallel computation thesis implies the existence of a parallel algorithm for $R$ with time complexity $O((log n)^{k’})$ where $k’$ is a constant. The comparison between sequential and parallel time allows classifying $R$ as a problem highly parallelizable (from a time perspective).

From the parallel computation thesis, it follows that $POLYLOGSPACE$ is the class of problems highly parallelizable. $POLYLOGSPACE$ does not contain problems complete with regard to log-space reductions; this implies $POLYLOGSPACE \neq P$.
It seems that

$POLYLOGSPACE ⊄ P$
$P ⊄ POLYLOGSPACE$

$P ∩ POLYLOGSPACE$ contains the problems that can be solved in polynomial time using polylogarithmic space. $P$-complete problems probably belongs to $P - (P ∩ POLYLOGSPACE)$.

$NC$ (Nick’s class - so called in honour of Nicholas Pippenger, the first to identify and to characterize it in 1979) is the class of problems that can be solved in polylogarithmic time (i.e., with time complexity $O((log n)^k))$ with a polynomial number of processors (I.e., bounded by $O(f(n))$ for some polynomial function $f$ where $n$ is the problem size)
The parallel computation thesis implies $NC ⊂ (P ∩ POLYLOGSPACE)$.

However, unfortunately by definition $NC$ also includes lots of problems which are not efficiently parallelizable. The most infamous example is parallel binary search.
The trouble is that this problem has polylogarithmic time complexity even for $p$ = 1.
Any sequential algorithm requiring at most logarithmic time in the worst case is in $NC$ regardless of its parallel feasibility!

Now, we can finally explain why $P$-complete problems are the hardest parallelizable problems.
Given a $P$-complete problem $Q$, it is very unlikely the existence of an efficient parallel algorithm: if such a parallel algorithm would exist with time complexity $O((log n)^k)$, then the parallel computation thesis will imply the existence of a sequential algorithm with space complexity $O((log n)^{k’})$ for the same problem.
Since $Q$ is a $P$-complete problem this in turn will imply that every problem in $P$ can be solved in poly-log space: $(P ∩ POLYLOGSPACE) = P$.
As you already know, we instead believe that $(P ∩ POLYLOGSPACE) ⊂ P$, even though we are not yet able to prove this.

One final observation, about the polynomial processor requirement. Well, that is a theoretical statement. In practice: a processor requirement that grows faster than the problem size might not really be useful.


need of error control in transport layer I want to know why error control is used in transport layer although it is used in data link layer?While data link layer has all data came from upper layers in its frames so its error control should be sufficient.

There are many types of error controls. The link layer error control that you are referring to is probably to do with ensuring that no bits were flipped in transit i.e. safe guarding against data corruption.

The error control in the transport layer usually refers to the guaranteed delivery mechanism with TCP, which attempts to safe guard against frames/packets getting lost entirely.


Can a language be context free and not have a BNF grammar? Leslie Lamport claims that TLA+ is too complex to be described in BNF.
Does that mean TLA+ is not a context free language?
What is the relationship between the set of context free languages and the set of languages that can be described by BNF grammars?

No. If a language is context-free, it has a BNF grammar, by definition. A context-free language is a language with a context-free grammar, and a context-free grammar is a grammar written in BNF with only one symbol on the left-hand side of each production. That's what "context-free" means.
It might not be convenient to write the grammar. For example, consider the language of words containing characters from some alphabet where no word contains two of the same character. The language is context-free, but the size of the shortest BNF grammar which describes it is exponential in the size of the alphabet. If you chose the set of 95 printable ASCII characters, the grammar would have so many productions that you would need a computer the size of the galaxy to store them.
Even if the language is not so pathological, you might feel that writing down its grammar in BNF is too time-consuming and mundane to make it a worthy use of your superior intellect.
But if the language is context-free, the grammar exists, at least in the mathematical sense of the word "exists".


Reference request: optimizing procedures on lists in dynamic languages by performing safety checks in advance For my science fair project, I implemented an optimization to Python's sort routine. The idea is to move the safety checks that have to be carried out during each comparison, e.g. type checks and character-width checks, outside of the sort loop and just get them all done in one pass. An optimized comparison function is then selected from a portfolio based on the results of the checks. So, for example, if the checks determine that all the objects are of the same type, the selected comparison function can skip the usually-required "are the object types compatible" check. Etc.

I have to write this up as a paper, and am currently working on a literature review. Are there any papers describing similar techniques in other dynamic languages/generally?

I'm not aware of anything exactly like this, but there are some things that are arguably related.

For specifically sorting this is related to the Schwartzian transform, though with a very different goal.  In the Schwartzian transform, you run through the input applying an expensive function and pairing the input and output together, then sorting on the output.  This is in contrast to performing that expensive function on each operation.  In your case, your "expensive function" would be the type checks and the dynamic dispatches.  A bit differently you would be checking a property for the whole list as well and then choosing which comparison operation to use based on that.

In a totally different vein, there's a general technique called polymorphic inline caching (pioneered by the Self team and covered, among many other things, in Craig Chamber's thesis) and more generally adaptive optimization that is used in some virtual machines.  Polymorphic inline caching solves the problem that if we do a dynamic dispatch, then we are jumping to some completely unknown code, and thus we can't inline it and optimize it and the current function.  The solution is simple: just do an if to test if we are in some specific case, and if so, we can inline that code, else we do the dynamic dispatch.  The problem is there is an unbounded, unknown number of possible cases.  This isn't a problem, though, for a Just-In-Time (JIT) compiler which can just do this for the cases actually seen at runtime.

This doesn't solve your problem since dynamic dispatch is based on the runtime class of an object, not on some arbitrary predicate like "all the elements of this array have the same type".  This is where adaptive optimization comes in and things like tracing JIT compilers.  It's quite conceivable that unrolling a loop a few times or inlining a couple levels of recursion can lead to many type checks being eliminated with simple constant propagation style optimizations, and possibly entirely eliminated by more sophisticated optimizations in some cases.  Nevertheless, it will often not do the same thing as you are suggesting and would need to see a trace first for each use of the sort function.  On the other hand, if it knows all the elements are numbers, say, from earlier code, it can eliminate checking entirely.


Gaussian noise: Image Processing As we all know, Gaussian Noise follows Gaussian or Normal distribution, and that distribution follows a $BELL$ $CURVE$.

As we can see that most of the values are centered around the mean.

Now consider this image

When I add Gaussian noise to this image I get something like this

As we can see that the noise appears to be $UNIFORMLY$ $DISTRIBUTED$ throughout the image. There is no region where we can say that the noises concentrated around the mean value

So how can these be called Gaussian Noise?

The Code that I have used in octave is given below

 pkg load image;

I=imread('C:\Users\Hirak\Desktop\apple.jpg');
I=rgb2gray(I);

J = imnoise(I,'gaussian',0.02);
K = medfilt2(J);
imshow(J);

The noise is Gaussian noise because the values you add to your existing images follow a Gaussian distribution, not the locations of where you add the noise - that is uniform (and not random at all - each pixel gets Gaussian noise added to it).


How to verify Hamilton-Path in log-space? Given an undirected graph $G$ and an undirected path $p$, Is it possible to verify $p$ is a Hamilton path in graph $G$ using logarithmic space? How is it possible to verify the path goes through all vertices without somehow save which one had been already checked?

You can check all vertices in order.

Suppose we are given vertices $v_1, v_2, \cdots, v_n$ and a path $p=(p_1,p_2, \cdots,p_m)$.Check if $m==n$. If not, reject. Otherwise, check if $v_1$ appears in $p$. If not, reject.  Otherwise, check if $v_2$ appears in $p$. If not reject. And so on. Finally check if $v_m$ appears in $p$. If not, reject. Otherwise, accept.


Is it possible to prove thread safety? Given a program consisting of variables and instructions which modify these variables, and a synchronization primitive (a monitor, mutex, java's synchronized or C#'s lock), is it possible to prove that such a program is thread safe?

Is there even a formal model for describing things like thread safety or racing conditions?

Proving that a program is "thread safe" is hard.  It is possible, however, to concretely and formally define the term "data race."   And it is possible to determine whether an execution trace of a specific run of a program does or does not have a data race in time proportional to the size of the trace.  This type of analysis goes back at least to 1988:  Barton P. Miller, Jong-Deok Choi, "A Mechanism for Efficient Debugging of Parallel Programs", Conf. on Prog. Lang. Dsgn. and Impl. (PLDI-1988):135-144.

Given a trace of an execution we first define a happens-before partial-order between events in the trace.  Given two events $a$ and $b$ that occur on the same thread then $a < b$ or $b < a$.  (The events on the same thread form a total order given by the sequential semantics of the programming language.)  Synchronization events (these could be mutex acquires and releases, for example), give an additional inter-thread happens-before partial order.  (If thread $S$ releases a mutex and then thread $T$ acquires that mutex we say that the release happens-before the acquire.)

Then given two data accesses (reads or writes to variables that are not synchronization variables) $a$ and $b$ that are to the same memory location, but by different threads and where either $a$ or $b$ is a write operation we say that there is a data-race between $a$ and $b$ if neither $a < b$ nor $b < a$.

The C++11 standard is a good example.  (The relevant section is 1.10 in the draft specs that are available online.)  C++11 distinguishes between synchronization objects (mutexes, and variables declared with an atomic<> type) and all other data.  The C++11 spec says that the programmer can reason about the data accesses on a trace of a multithreaded program as if it were sequentially consistent if the data accesses are all data-race free.

The Helgrind tool (part of Valgrind) performs this kind of happens-before based data-raced detection as do several commercial tools (e.g., Intel Inspector XE.)  The algorithms in modern tools are based on keeping vector clocks associated with every thread and synchronization object.  I think this technique of using vector clocks for data-race detection was pioneered by Michiel Ronsse; Koen De Bosschere: "RecPlay: a fully integrated practical record/replay system", ACM Trans. Comput. Syst. 17(2):133-152, 1999.


Does cooperative scheduling suspend processes when they perform an  I/O operation? Many operating systems references say that with cooperative (as opposed to preemptive) multitasking, a process keeps the CPU until it explicitly voluntarily suspends itself.  If a running process performs an I/O request that cannot be immediately satisfied (e.g., requests a key stroke that is not yet available), does the scheduler suspend it, or does it really keep the CPU until the request can be serviced?

[Edited to replace "blocks on i/o" with "performs an I/O request that cannot be immediately satisfied."]

In a truly "cooperative" setting, and if there was no hardware protection, a process could certainly block on I/O and not relinquish control until the I/O was done (or never relinquish control at all). For example, Windows 3.1 was this way: if a single user process wanted to take over the entire computer, and prevent anything else from running, it could.

But on a system with multitasking you expect the system API I/O commands to relinquish control of the processor when they are called. So when a running process blocks on I/O, assuming that the process uses the normal system APIs, other processes will be allowed to run until the I/O is complete, and eventually the original process will resume once the I/O is done. In other words, calling a blocking I/O function is one way that a process on a cooperative system can voluntarily suspend itself.


Recurrence Equation upper limit problem I was looking at my teacher's notes and came about the following recurrence equation :

$$
T(n) =
     \begin{cases}
       1 &\quad\text{if } n\leq 1\\
       4T\left(\frac{n}{2}\right) + n^3 &\quad\text{if } n\gt1 \\
     \end{cases}
$$
In order to solve it I proceeded as follows :
$$
T(n) = n^3 + 4T\left(\frac{n}{2}\right) = n^3 + 4\big( 4T\left(\frac{n}{4}\right) + \left(\frac{n}{2}\right)^3 \big) = \\
n^3 + 4\left(\frac{n}{2}\right)^3 + 16T(\frac{n}{4})
 = \cdots
$$
I'll spare some latex and state that we can see from unwrapping the equation that at the generic level $i$ the incurred price is :
$$
T_i = 4^i\left(\frac{n}{2^i}\right)^3
$$
In order to compute the overall price we can sum all the prices incurred at all levels, obtaining :
$$
T(n) = \sum_{i=0}^{log^n -1}{\big(4^i\left(\frac{n}{2^i}\right)^3\big)} + 4^{log^n}T(1) = \\
n^3 \sum_{i=0}^{log^n-1}{\big(2^{2i}\frac{1}{2^{3i}}\big)} + n^2 = \\
n^3 \sum_{i=0}^{log^n-1}{\big(\frac{1}{2^{i}}\big)} + n^2
$$
My problem begins here. In order to solve it I'd say that the series in questions can be solved as :
$$
 {\displaystyle \sum _{k=m}^{n}x^{k}={\frac {x^{m}-x^{n+1}}{1-x}}\quad {\text{with }}x\neq 1.}
$$
which applied to my scenario would yield
$$
n^3 \left(\frac{1 - (\frac{1}{2})^{log^n}}{1 - \frac{1}{2}}\right) + n^2 = \\
2n^3 - 2n^2 + n^2 = 2n^3 - n^2 = \Theta(n^3)
$$
But my professor says :
$$
n^3 \sum_{i=0}^{log^n-1}{\big(\frac{1}{2^{i}}\big)} + n^2 \leq n^3 \sum_{i=0}^{\infty}{\big(\frac{1}{2^{i}}\big)} + n^2 = \\
n^3 \frac{1}{1 - \frac{1}{2}} + n^2 = 2n^3 + n^2
$$
And thus $T(n) = O(n^3)$ instead of $\Theta(n^3)$ since we proved only an upper limit.

My question is thus, why can't I solve the summation as I did instead of extending it to infinity?

Yes, you could solve the summation in exact formula. Yes, you could obtain $T(n)=\Theta(n^3)$, a tighter asymptotic bound. Your professor would and should not forbid you to do  that.

The message from your professor could be that an upper bound such as $O(n^3)$ is as good as $\Theta(n^3)$ more often than not. For example, once we know an algorithm runs in $O(n^3)$ time without a huge constant multiplier on a problem of input size $n$ less than 1000, then we can be comfortable starting implementing the algorithm,  without worrying much that the code may take hours to run. A tighter asymptotic bound such as  $\Theta(n^3)$ will not help us move ahead significantly further. On the other hand, such a tighter asymptotic usually comes with a heavier price, which is not much heavier in this particular problem, though.


Is there a similar categorization to Elementary Cellular Automata? Elementary cellular automata show different systems and fractals like rule 30, rule 90, and rule 110. I want to know if there is another classification or type which shows similar structures just like in elementary cellular automata (ECA).

For example what other systems can show structures similar to Sierpinski triangle (which is the same as rule 90 in ECA)?

Is there a method to build rule 30 or 60 using other system than ECA?

You might take a look at Lindenmayer Systems.

From Wikipedia:

  An L-system consists of an alphabet of symbols that can be used to
  make strings, a collection of production rules that expand each symbol
  into some larger string of symbols, an initial "axiom" string from
  which to begin construction, and a mechanism for translating the
  generated strings into geometric structures.

L-systems can be used to generate a Sierpinski triangle.


What is 'K' in the Bounded Post Correspondence Problem? I'm only just starting to learn about the PCP, and I'm especially interested in the Bounded version. From Wikipedia:

  One of the most important variants of PCP is the bounded Post
  correspondence problem, which asks if we can find a match using no
  more than k tiles, including repeated tiles.

I am not sure I understand what Wiki means by a 'tile' in this context.

I do understand that a typical PCP problem takes as input two equal-length lists of nonempty strings, each of which contains some number of words. An example is this:

M = (abb, aa, aaa) and N = (bba, aaa, aa)

In terms of the Bounded PCP, what would the integer K be here? Is it the length an individual word can be (which in this case is maxed at 3)? Is it the length of a single list?

Hope this is clear. I appreciate any help profusely in advance.

Suppose your list is M=(bba,ab,bba,a) N=(bb,aa,bb,baa) Then its equivalent tile representation is as follows

Now your pcp problem is equivalent to finding a sequence of tiles(repetition allowed) such that concatenating all upper halves and concatenating all lower halves gives you same string.
K here is nothing but number of tiles that can be used

Edit : As Yuval Filmus subtly mentions in his comment, there are many other interpretations of K. In an another formulation K can also be the maximum length of concatenated string, in which case the bounded PCP problem is Pspace complete. But usually many books refer to K as being number of tiles that are allowed.Please refer to Sipser book for more.


Is there an Interval Tree which supports O(1) dynamic space requirements for queries? I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key).

In general when visiting a node in an (common) interval tree you are required to visit multiple child nodes and check for results there and recurse.
This requires you to (dynamically) allocate memory upon lookup.

In contrast, f.e. consider a simple binary search tree. You can easily unroll the recursion because you will only ever visit a single child node.

Is it possible to achieve a similar algorithm for intervals?
To clarify I would like to know whether there exists an interval tree which supports finding any overlapping interval in constant required space.

Short answer yes, you can achieve this in any type of tree, if there is a pointer from child to parent node.

The purpose of the stack is to remember you have to go back and visit another branch. Without the stack, but with the ability to go back to parent nodes, you can check if there is another branch that you should have visited.

Then the only space you need is 1 node. The query time might be slightly longer, although still log(n). The stack is an optimization, and after you remove it, you need an extra while loop to go back and check the latest other branch.


Reason for finding partial order of a graph In a recent algorithms course we had to form a condensation graph and compute its reflexive-transitive closure to get a partial order. But it was never really explained why we would want to do that in a graph. I understand the gist of a condensation graph in that it highlights the strongly connected components, but what does the partial order give us that the original graph did not?

The algorithm implemented went like this:

Find strongly connected components (I used Tarjan)
Create condensation graph for the SCCs
Form reflexive-transitive closure of adjacency matrix (I used Warshall)

Doing that forms the partial order, but.... what advantage does finding the partial order give us?

One possible use: It lets you answer the question "is vertex $y$ reachable from vertex $x$?" in $O(1)$ time.


Prove that Weighted Independent Set is NP Complete using Independent Set? $k$-Weight Independent Set
  Input: A vertex weighted graph $G=(V,E,w)$ and an integer $k$.
  Question: Is the a set $V'\subset V$ such that $V'$ is an independent set and $\sum_{v\in V'} w(v) \geq k$?

Showing that this problem is in NP is trivial, but I'm suck on showing that $X \Longleftrightarrow Y$. The forward direction is simple I think.

$\Longrightarrow$ If you have a $k$-Independent Set, then we know that each node has a weight that is a natural number ( $\ge 1$ ), so the graph has weighted independent set of at least $k$.

But how would you show the reverse direction $\Longleftarrow$?

You reduce to this problem quite easily from the Independent Set problem.

Given a graph $G=(V,E)$ and a natural number $k$ define a simple weight function $w:V\to\mathbb{R}$ by

$$\forall v\in V:w(v)=1$$

The output of the reduction is $\langle G'=(V,E,w),k\rangle$.

If $G$ has an Independent set $S$ of size at least $k$ then $S$ is an independent set in $G'$ and

$$\sum\limits_{v\in S}w(v)=\sum\limits_{v\in S}1=|S|\geq k$$

So, $G'$ has an independent set of weight at least $k$, as needed.

If $G'$ has an Independent set $S'$ such that

$$\sum\limits_{v\in S'}w(v)\geq k$$

Then, observe that $S'$ is an independent set in $G$ also and

$$|S'|=\sum\limits_{v\in S'}1=\sum\limits_{v\in S'}w(v)\geq k$$

So, $G$ has an Independent set of size at least $k$, as needed.


PDA and CFG of language of regular expressions I am stuck on a problem involving PDA's and CFG's. The problem is as stated:

  Give a CFG and a PDA for the language of regular expressions over the
  alphabet $\{a, b, c\}$. Give the formal tuple definition of each. You may use the
  shorthand for pushing a string in the state diagram of your PDA, but not in the
  tuple form. It will help if you expand out the shorthand in the state diagram.
  To avoid ambiguity, use the symbols $($, $)$, $λ$ for the language.  The alphabet should
  be $\{a, b, c,(,), +, λ,∗ \}$. For brevity, you can define $δ$ by giving its output on
  the inputs that don’t return $∅$. Something like $δ(x_1) = y_1; δ(x_2) = y_2;$

My first attempt at it got me stuck after defining the Context Free Grammar and the PDA. I am having trouble understanding how this grammar could, for instance,

Derive $(a + b)^*(c + λ)a^*$
Make a PDA for this.

How can I make a PDA for this? How can I make a CFG for this?

Hint:  Let us assume an alphabet $\Sigma$. Now, the following are regular expressions (at least according to some textbooks):

$a$ is a regular expression, if $a \in \Sigma$
$\emptyset$ is a regular expression
$r_1 \cup r_2$ is a regular expression, if $r_1$ and $r_2$ are regular expressions
$r_1 \circ r_2$ is a regular expression, if $r_1$ and $r_2$ are regular expressions
Nothing else is a regular expression.

How can you summarize these formation rules as a collection of context-free production rules where $r$ is a nonterminal?


CURE algorithm: what does moving the representative points towards the centroid do? The CURE algorithm is a method of clustering data. An outline of it can be found here on slide 5: https://www.slideshare.net/ellepiu/cure-clustering-algorithm. I personally learnt it from this video: https://www.youtube.com/watch?v=JrOJspZ1CUw, where the algorithm is explained at 7 minutes.

This is my understanding of the process of CURE. Let's assume that the data set is large enough such that we have to store a portion of the data on disk.

Take an amount of the data set that fits onto the computer, and cluster (perhaps hierarchically) to initialise clusters.
For each cluster: pick k representative points, and move each a fixed distance, $\alpha$, towards the cluster centroid.
For each data point on disk, assign it to the cluster with the representative point it is closest to.

To me, this selection of representative points seems like a really arbitrary thing to do, and I don't really see the logical process behind choosing to do this.

For any two data sets representing the same thing, it could be possible (even likely) that one set of clusters pre-representative-point-moving for one data set would be the same as the set of clusters post-representative-point-moving for the other.

Could someone please help explain in more detail the reasoning behind doing this? (Beyond just the basic pseudo-algorithm I have seen.)

My thoughts

I think that when moving the representative points towards the centroid of each cluster, this is equivalent to shrinking the boundary of the cluster. Once this is done, the data points that remain outside of the boundary are eliminated as clusters. But I'm not sure if this is correct.

If I'm understanding your question correctly, you are interested in why the representative points are chosen as such, why they are merged and why this works. I'll first go over some background for CURE, then I focus on this particular question.

Background: why CURE?

I think we should start with the intention of CURE. To see that, we look at slide 14:

Here, CURE is compared with BIRCH and MST. We see that BIRCH succeeds in identifying the top ellipsoid pair as different, but fails to detect the large disk as a single cluster. BIRCH seems to only support same-sized clusters, So BIRCH doesn't make some clusters big enough and others too big. MST successfully classifies the disk as a single cluster, but fails to separate the ellipsoids on top. MST makes the clusters too big.

So, BIRCH is an attempt at trying to 'hit' the sweet spot between BIRCH and MST, in the hope of creating better clusters. In this example, it seems to be working pretty well.

Alright, back to the main question, why are the representative points handled as such? Suppose CURE would output the BIRCH result as an intermediate step. It then looks at the representative points of the light-blue and black half-disks. As the representative points are close, CURE would decide to merge these two half-disks into a full disk, which is good.

Okay, that's nice and all, but what prevents CURE from merging the two ellipsoids above, as BIRCH does? CURE doesn't do this (or is at least unlikely to do so), as the representation points are well scattered. This means that it is only likely that two clusters that are touching each-other on a location with high density get merged (as otherwise many representatives being close has low probability). As the two ellipsoids only touch each-other at points with low density, CURE (with carefully chosen parameters, no doubt) detects them as different.

How to merge?

We've seen that CURE sometimes has to merge two smaller clusters into a bigger one. The question is how to handle the representative points. The simplest way to do this is to simply add them to the new cluster. But this isn't a good idea. For their original clusters, the representation points were well scattered. But if we simply use the same points for our merged cluster, this is no longer the case.

To see this, consider the example of the two half-disks in the clustering provided by BIRCH. Suppose that the representation points form the outline of a half-disk slightly smaller than the ones given. Now, if we merge the clusters, the representation points lie a bit far away from the center. They are no longer well scattered.

This is a problem, because if there were another disk-like cluster nearby ('connected by a chain of outliers', as the authors would say), the fact that the representation points are too far to the edge of our newly merged disk means we're likely to put the two disks in a single cluster. Note that this process can occur many times at different hierarchical levels, so if we don't solve this, we won't get nice results.

So, the solution is to move the representation points a bit closer to the center, as this makes them more well-scattered and therefore decreases the probability that we make a bad merge.


Why is binary subtraction referred to as the invert-add-shift-add method? I'm being asked this question for my computer conceptes class, can't find anything about this in my text book, and have only been able to find half-baked answers googling it.

Why is binary subtraction referred to as the invert-add-shift-add method?

I found an excellent answer here, which I summarize below.

Given two number $A,B$ in binary notation, we calculate $A-B$ by adding to $A$ the two's complement of $B$. Since the two's complement of $B$ is formed by inverting all bits of $B$ and adding $1$, one way to implement this idea is invert $B$, add the result to $A$, shift the carry $1$ bit (which will appear if $A\geq B$), and add it (i.e. $1$) to the result.


-4 as floating point How would one represent the number -4 as an 8-bit normalised, 2's complement, floating point, with 4 bits dedicated to the exponent?

As a normal 4-bit 2's complement number, it would be represented as 1100.

How would this be normalised, with the start of the mantissa being 1.0?

Would it be 1.000 0010, with the extra 1 on the left (after evaluation to a normal 2's compliment number) being filled in?

If so, how would you know to fill it with a 1, because it starts with a 1?

AFAIK, there is no standard with that format.

You can nevertheless try to imitate the old MIL-STD-1750A floating point format, which had two's complement mantissas and exponents.

The two's complement mantissa range is -1.0 to 0.999999....

Something like that :

                     Mantissa Exponent
'   0 =                  0000 0000
'0.25 =  0.5 * 2**-1 =   0100 1111
' 0.5 =   0.5 * 2**0 =   0100 0000
'  +1 =   0.5 * 2**1 =   0100 0001
'  +2 =   0.5 * 2**2 =   0100 0010
'  +4 =   0.5 * 2**3 =   0100 0011
'  -1 =  -1.0 * 2**0 =   1000 0000
'  -2 =  -1.0 * 2**1 =   1000 0001
'  -4 =  -1.0 * 2**2 =   1000 0010

Note the asymmetry between +1 and -1.

etc...


Definitions of an algorithm running in polynomial time and in strongly polynomial time Wikipedia defines it to be

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $T(n) = O(n^k)$ for some constant k.
The algorithm runs in strongly polynomial time if [8]

the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input
instance; and

the space used by the algorithm is bounded by a polynomial in the size of the input.

In Bernhard Korte, Jens Vygen, Combinatorial Optimization:

Definition 1.4.
An algorithm with rational input is said to run in polynomial time if

there is an integer k such that it runs in $O(n^k)$ time, where n is the input size, and
all numbers in intermediate computations can be stored with $O(n^k)$ bits.

An algorithm with arbitrary input is said to run in strongly
polynomial time if

there is an integer k such that it runs in $O(n^k)$ time for any input consisting of n numbers and
it runs in polynomial time for rational input.

Please correct me if I am wrong. Following are the literal differences I noticed:

For polynomial time algorithms, Korte and Vygen's definition is "the Wikipedia's definition + polynomial storage space".

For strongly polynomial time algorithms, Korte and Vygen's definition and Wikipedia's definition both require polynomial time in the input storage size. But K and V's additionally requires polynomial time in the number of numbers in any input, while Wikipedia's additionally requires polynomial storage space in the input size.

So are K and V's and Wikipedia's definitions for these two concepts equivalent, respectively? What other differences and relations are between them?
Thanks and regards!

Before formal definitions, consider what the "strongly/weakly" classification aims to distinguish.

First, consider running either one on a Turing Machine. Both will run in a number of steps polynomial in the length of binary-encoded input. Consequently, the number of arithmetic operations performed by both would have to be polynomial in the length of binary-encoded input. Hence, for both Turing Machine running time would grow polynomially as the number of input values or their magnitudes grows. To emphasize the latter, note that even the strong one will take more TM steps on larger magnitudes (it needs to at least read the extra bits). Under no circumstance does one become exponential (as is the case with the unrelated pseudo-polynomial time). With a Turing machine alone, a fundamental difference doesn't seem detectable.

Now consider running each on an arithmetic machine where any operation is an arithmetic operation on whole numbers and arithmetic operations are $O(1)$. As you increase the magnitudes of the input numbers, the length of the binary-encoded input grows, and the running time of the weak algorithm would grow, however the running time of the strong algorithm would not change, because can be bound by the number of input numbers, which you are not changing (e.g. matrix multiplication vs. Euclid's GCD).

The set of algorithms that run in number of arithmetic operations polynomial in the number of input numbers is well-defined, but overlaps with the class of algorithms that take number of TM steps exponential in the length of binary-encoded input (see examples). Hence, for this set, the properties in the second paragraph would not hold. To exclude the unwanted intersection, we add a condition for a polynomial TM space [*].

In [1] this is stated in two ways:

The algorithm runs in strongly polynomial time if the algorithm is a polynmomial space algorithm and performs a number of elementary arithmetic operations which is bounded by a polynomial in the number of input numbers.
A polynomial algorithm is a polynomial space algorithm (in our standard Turing machine model) and polynomial time algorithm in the arithmetic model (see this question for a clarification).

This sub-classification of what are already "efficient" algorithms might be  be useful since physical computers resemble arithmetic machines more than Turing machines, so the sub-class might identify the algorithm that would run faster on a physical machine if their polynomial bounds in length of binary-encoded input are otherwise comparable (which is not the case in e.g. strong $O(n^3)$ vs. weak $O(n^2)$)

[*] The second condition is stated everywhere as polynomial space, whereas requiring polynomial time makes more sense to me. The former is more inclusive, but strange. Are there strongly-polynomial algorithms that take more than polynomial time? Note that repeated-squaring example takes neither polynomial time nor polynomial space.

[1] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.