# Question
Title: Time complexity of adding a vertex to adjacency list
Multiple sources state that the time complexity of adding a vertex to an adjacency list is O(1) and my understanding right now is that this is because of optimizations with hash tables.

If we use an array of linked lists, then the time complexity is O(V) right? Because to add a new vertex we have to make a new array of size V + 1.

I just wanted to confirm my line of thinking against pre-existing information.

# Answer
In an array of list implementation of adjacency list, the worst-case cost of adding a new vertex is $O(V) $ because in the worst-case the array is full and you need to create a larger array which is say 2 times larger than the current. Then you will then copy the $V$ lists. The cost of copying a list is $O(1)$ assuming we are copying the pointer to a list and not copying each entries of the list.

However, the amortized cost of inserting is $O(1)$. Please refer to the amortized analysis of dynamic arrays (https://en.m.wikipedia.org/wiki/Amortized\_analysis) .

As for the adjacency matrix, you can also dynamically resize but the worst-case cost of insert is $O(V^2)$ since we are to copy individual items. The amortized cost of insert is $O(V) $ applying the same dynamic array analysis.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Why do public key systems involve private keys?
I read up the definition of a public key cryptosystem. It mentions there is a public key and a private key. That's confusing. Why is it called a "public key" system if it involves a private key as well?

# Answer
> 14 votes
Public key cryptography means that the entire communication between both parties is public, including the setup. Contrast this with the case of two parties $A,B$ meeting in secret, agreeing on some keyword, and using this keyword to encrypt future communications.

Clearly, if $A,B$ decide on the encrpyption scheme in public, something has to be kept private (otherwise you could decipher the messages just like the parties involved). This is the private key, so the flow is something along the following lines: $A$ and $B$ publicly discuss and share some information with each other and the world, then they do something in private and send each other encrypted messages. Witnesses to the public exchange alone can't recover what is being said.

The child version of such scheme which I like is the following. Suppose $A$ and $B$ want to agree on some secret color, only known to them, however the entire exchange must be public. Under the assumption that mixing colors is easy, but given a mixture recovering its components is hard, then they could do the following: $A$ and $B$ each choose a secret (private key) color denoted by $a,b$. Then $A$ sends $B$ the color $c$ (public key), and the mixture $(a,c)$. $B$ now creates the mixture $(b,c)$ and sends it to $A$, and also mixes $(a,b,c)$ and keeps this compound to himself. Finally, $A$ adds $a$ to $(b,c)$ and is now also in the possession of the secret mixture $(a,b,c)$, known to $A,B$ but unknown to anyone who solely witnessed the interaction between them.

# Answer
> 7 votes
Security is about protecting yourself from adversaries: it's about achieving something that adversaries can't achieve. Cryptography is a part of security that's about protecting information, to achieve properties such as confidentiality (not letting adversaries know something you didn't intend them to) and integrity (not letting adversaries trick you into believing something you didn't intend to).

It's not surprising that there are cryptosystems that involve secrets. If you want to prevent adversaries from achieving something that's related to information, a pretty obvious way to do it is to know something they don't: you know a secret. A key in a cryptosystem is a fundamental piece of information upon which the security of the system depends. It's natural that a key would need to remain secret: if the adversary knows the key, what can the defender do that the adversary cannot? So it isn't remarkable that a cryptosystem involves a secret key.

It's more surprising that there are cryptosystems involving public keys: keys that the adversary knows. Public keys are still called keys, partly because they are specific to an instance of the cryptosystem and they are pieces of information that make the cryptosystem work, and partly because they do have an associated secret (which is usually called “private key”). Historically, the invention of cryptography involving public keys was a paradigm change. (By the way, the first public-key cryptosystems were not for encryption, but for key exchange: Merkle puzzles and Diffie-Hellman.)

Cryptosystems that don't involve a secret key at all (such as integrity protection through hashes) aren't called “something-key” because they don't involve a key. Cryptosystems that do involve a secret key, but no public key, are sometimes called “secret-key”, but usually they're called “symmetric”. Cryptosystems that involve both a secret key and an associated public key are called “asymmetric” or “public-key” because the existence of the public key is the remarkable thing about them. (The secret key is usually called “private key” for duality with “public key”.)

# Answer
> 4 votes
In a public key cryptosystems, there are operations that everyone in possession of the public key can do, and other operations that only someone possessing the private key can do. For example:

* Suppose Alice wants to send a message to Bob. Alice encrypts the message with Bob's public key, which he makes available publicly. Only Bob can decrypt the message, since he is the only one who has access to Bob's private key.
* Suppose Alice wants to sign a message. Alice encrypts the message with her private key, which only she has. Anybody can verify the signature by decrypting the encrypted message, using Alice's public key, and checking that it matches the actual message.

In contrast, a symmetric cryptosystem uses the same key for encryption and decryption. To demonstrate how these are used, let us see how one actually implements the two scenarios above:

* Suppose Alice wants to send a message to Bob. She chooses a session key at random, and encrypts it using Bob's public key. She then encrypts the message using the session key (and a symmetric cryptosystem). Bob decrypts the session key using his private key, and then decrypts the message using the session key.
* Suppose Alice wants to sign a message. Alice computes a cryptographically secure hash of the message (a third kind of a cryptographic primitive), and encrypts it with her private key. Everybody can decrypt the hash using Alice's public key, and check that it indeed corresponds to the message.

A cryptographically secure hash function is a component of many cryptosystems, and it differs both from public key encryption and from symmetric encryption.

# Answer
> 2 votes
Cryptography and particularly ciphers started out using secret key cryptography. This is cryptography where the participants share a secret key. These systems use symmetric ciphers to encrypt / decrypt and Message Authentication Code to sign / verify messages. For example, AES could be used to encrypt / decrypt messages and HMAC to provide integrity / authenticity for them.

The problem with secret (also called symmetric or private) cryptography is that you need to distribute the secret keys. Furthermore, the parties in the scheme cannot authenticate the messages to come from them, as all participants use the same key. These difficulties mean that key management is hard to do.

Enter asymmetric algorithms such as RSA and DH. These algorithms have both a public key and a private key. Basically these algorithms rely on a mathematical problem where you have two keys. These public key performs a complementary operation to that of the private key:

| Initial Operation | Key | Complementary Operation | Key |
| --- | --- | --- | --- |
| **Encrypt** | Public Key | **Decrypt** | Private Key |
| **Sign** | Private Key | **Verify** | Public Key |
| **Key Establishment at party A** | Public Key of party B & Private Key of party A | **Key Establishment at party B** | Public Key of party A & Private Key of party B |

The advantage for these schemes is that you can distribute the public keys publicly. This allows for much easier key management, as encrypting a symmetric key with another symmetric key doesn't solve the key management problem; it is just shifted the problem to the next key in line. Do note that the public key *does need to be trusted* by the participants, otherwise an adversary might just send their own key. For this a Public Key Infrastructure (PKI) is commonly used. For example the certificate store in your browser to support TLS connections is part of a PKI.

---

Public key cryptography is named after the public key because **the public key is what distinguishes** secret key cryptography based on symmetric algorithms from public / private key cryptography based on asymmetric algorithms. For cryptography you *always* need a secret or private key if you want to make messages confidential - using a cipher - or if you want to authenticate messages - using a MAC or signature algorithm. You are right that it would be more precise to call it a public / private key cryptosystem, but humans like to keep it short... language eh?

---
Tags: cryptography, encryption
---


# Question
Title: What exactly are functions in programming?
Are conditional statements, loops, and basic maths operators are functions? I learn functions as a "specific action". But, I saw in a video from youtube that a guy called loops and math operators "Functions". Was he right? OR, I have to modify my definition of functions?

# Answer
> 1 votes
The guy in your video is correct (and nearly all other programming languages are deficient in this feature). Alphard and Seed7 programming languages do a quite fine job of allowing you to write a new syntax for a conditional statement or loop or various not-so-basic mathematics operators in the form of a function.

See sections 9.6 and 9.7 of http://seed7.sourceforge.net/manual/syntax.htm for melding syntax definition in with functions.

The guy in your video is incorrect if he led you to believe that very many more programming languages other than Alphard and Seed7 have this capability to model statements and loops as functions.

The guy in your video is correct if he was speaking of pure mathematics which nearly all programming languages have failed to capture at all or without so much contortion that it is difficult to recognize the abstract concept amongst all the syntactic machinery that is utilized to express the abstract mathematical concept partially via tangential approximations and kludges.

---
Tags: programming-languages
---


# Question
Title: Tracking / calculating dependencies of nodes
I have a problem regarding dependencies. I'm making a circuit simulator thingy and I stumbled upon the problem of determining which circuit component should be updated first (since updates in my case mean that the output is transformed based on its inputs according to some specified behaviour, the behaviour being irrelevant). How does one efficiently tackle this problem and how does he approach the problem of circular dependencies? (e.g. in counters)

Sources on the topic are much appreciated!

# Answer
If there are no circular dependencies you can just use a topological order of the associated directed graph (that contains edge $(u,v)$ if $v$ uses the output of $u$ as an input).

If there are circular dependencies then you could update the output of each component in discrete time steps, and compute it as a function of its inputs in the *previous* time step. This will work fine unless the circuit output depends on the subtle timing difference, as in some latches.
> 1 votes

---
Tags: algorithms
---


title: Optimal parameters for a Bloom filter

text:
# Question
Title: Optimal parameters for a Bloom filter
My first question here. Please do not judge me much if this is a too simple.

Some text consists of $n=12\\,500$ distinct words. I would like to construct a Bloom filter with $\epsilon=10^{-2}$ probability of false positives. Using well known formulas, the optimal filter size $m$ is computed as

$$m=-\frac{n\log\epsilon}{\log(2)^2}\approx 120\\, 000.$$

The optimal number of hash functions $k$ is computed as

$$k=\frac{m}{n}\log{2}\approx 6.6.$$

It is suggested that suboptimal number, i.e. $k=6$ might even be better for performance reason.

That's all very fine in theory. In practice, we have excellent (and probably too expensive, but let's use them as an illustration) hash functions SHA-256. They have length of only 256 bits. Thus, $m=256$ necessarily! We put $n=12500$ and $m=256$ in the formula for the probability of false positives $$\epsilon=\left(1-e^{-kn/m}\right)^k$$ and get this plot

Thus, no matter what I do, with 256-bits hash functions I cannot reduce the probability even below 99%! What can I do? Is the Bloom filter useless in my case?

I was thinking to "glue" $120000/256\approx 469$ hash functions together. But then I need $469\times6 =2814$ expensive SHA-256 evaluations per one filter operation.

# Answer
When using SHA256, the maximum possible filter size is $m=2^{256}$. A 256-bit value can index into $2^{256}$ possible indices into the array. This is more than adequate.

For instance, a 3-bit hash function could be used to index into an array of length $m=8$.
> 1 votes

---
Tags: hash, bloom-filters
---


# Question
Title: Asymptotic of $\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}$
I'm trying to figure out the asymptotic estimate of $\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}$. I think it is $\omega(2^{\sqrt{n}})$ and am trying to prove it by showing $\lim\_{n \rightarrow \infty} \frac{\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}}{2^{\sqrt{n}}} = \infty$ as wolfram says it should. But can't seem to get it. This is what I've tried so far:

$\frac{1}{2^{\sqrt{n}}}\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!} = \frac{1}{2^n}\frac{\[\prod\_{i=1}^{n-1} (\sqrt{n}+i)\](\sqrt{n})!}{(\sqrt{n})!(n-1)!} \\ = \frac{1}{2^n} \frac{\prod\_{i=1}^{n-1} (\sqrt{n}+i)}{(n-1)!}$

But I'm not sure where to go from here.

# Answer
### Summary

As zkutch points out, $\sqrt n!$ is not a well-defined notation since $\sqrt n$ is not an integer when $n$ is not a square.

Here are four approaches to interpret the question. We will not only confirm "it" is indeed $\omega(2^\sqrt n)$, but also give tighter or even optimal estimate as well.

### Use $\lfloor x\rfloor!$ instead of x!

The question is about $\displaystyle\frac{\lfloor\sqrt{n}+n-1\rfloor!}{\lfloor\sqrt{n}\rfloor!(n-1)!}$.

Let $k=\lfloor\sqrt n\rfloor$. We have, $$\frac{\lfloor\sqrt{n}+n-1\rfloor!}{\lfloor\sqrt{n}\rfloor!(n-1)!} =\frac{\prod\_{i=1}^{k}(i+n-1)}{\prod\_{i=1}^{k}i} \ge \frac n1\prod\_{i=2}^{k}\frac{n}{i} \ge(\sqrt n)^2\prod\_{i=2}^{k}\sqrt n \ge\sqrt n^{\sqrt n}$$

### Use $\lceil x\rceil!$ instead of x!

As an easy exercise for readers, show that $$\frac{\lceil\sqrt{n}+n-1\rceil!}{\lceil\sqrt{n}\rceil!(n-1)!} \ge\sqrt n^{\sqrt n}$$

### Let $n$ be a square

This is Steven's approach. Let $n = k^2$ for some integer $k$. So, $k = \sqrt n = \lfloor \sqrt n\rfloor$. In the same way as the first approach above, we have,

$$\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}=\frac{\lfloor\sqrt{n}+n-1\rfloor!}{\lfloor\sqrt{n}\rfloor!(n-1)!}\ge\sqrt n^{\sqrt n}.$$

Let us compute a tighter estimate, applying Stirling's formula, $$m!\sim \sqrt{2\pi m}\left(\frac{m}{e}\right)^m,$$ where $\sim$ means the ratio of the two sides converges to 1 when $m$ goes to $+\infty$.

$$\begin{aligned} \frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}&= \frac{(k+k^2-1)!}{k! \cdot (k^2-1)!}\sim \frac{(k+k^2)!}{k! \cdot (k^2)!} \\ &\sim \frac{\sqrt{2\pi (k+k^2)}\left(\frac{k+k^2}{e}\right)^{k+k^2}}{ \sqrt{2\pi k}\left(\frac ke\right)^k \sqrt{2\pi k^2} \left(\frac{k^2}e\right)^{k^2}} \\ &\sim\frac1{ \sqrt{2\pi k} } \left(\frac{k+k^2}k\right)^{k}\left(\frac{k+k^2}{k^2}\right)^{k^2} \\ &= \frac1{ \sqrt{2\pi}}\left(\frac{1+k}{k}\right)^{k^2+k} k^{k-\frac12} \end{aligned}$$

The inequality $\left(\frac{1+k}k\right)^{k+1}\gt e$ tells us that $\left(\frac{1+k}{k}\right)^{k^2+k} \gt e^k.$ So we have $$\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}=\Omega(e^\sqrt n\sqrt n^{\sqrt n-\frac12}).$$

If instead we use the following stronger fact, which can be proved by either l'hospital's rule or Taylor's series for $\ln(1+t)$, $$\left(\frac{1+k}{k}\right)^{k^2+k}\sim e^{k+\frac12},$$ we obtain, $$\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}\sim\frac1{\sqrt{2\pi}} e^{\sqrt n+\frac12}{\sqrt n}^{\sqrt n-\frac12}.$$

### Use $\Gamma(x+1)$ instead of $x!$

The natural extension of factorial to non-integers is $\Gamma$ function. The question is about $$\frac{\Gamma(\sqrt{n}+n)}{\Gamma(\sqrt{n}+1)\Gamma(n)}.$$ Since $\ln(\Gamma(x))$ is convex and increasing for $x\ge2$, we have $$\frac{\Gamma(\sqrt{n}+n)}{\Gamma(\sqrt{n}+1)}\ge \frac{\Gamma(\lfloor\sqrt{n}+n\rfloor)}{\Gamma(\lfloor\sqrt{n}+1\rfloor)}$$ So, $$ \frac{\Gamma(\sqrt{n}+n)}{\Gamma(\sqrt{n}+1)\Gamma(n)} \ge\frac{\Gamma(\lfloor\sqrt{n}+n\rfloor)}{\Gamma(\lfloor\sqrt{n}+1\rfloor)\Gamma(n)} =\displaystyle\frac{\lfloor\sqrt{n}+n-1\rfloor!}{\lfloor\sqrt{n}\rfloor!(n-1)!}\ge \sqrt n^\sqrt n.$$

Since we also have Stirling's formula for $\Gamma$ function, $$\Gamma(x+1)\sim \sqrt{2\pi x}\left(\frac{x}{e}\right)^x,$$ we can proceed in the same way as in the approach above but without requiring $k=\sqrt n$ be an integer. In particular, we can obtain $$\frac{\Gamma(\sqrt{n}+n)}{\Gamma(\sqrt{n}+1)\Gamma(n)}\sim \frac1{\sqrt{2\pi}} e^{\sqrt n + \frac12}{\sqrt n}^{\sqrt n -\frac12}.$$
> 9 votes

# Answer
Letting $n=k^2$, considering only sufficiently large integer values of $k$, and using Stirling's approximation: $$ \lim\_{k \to \infty} \frac{(k+k^2-1)!}{k! \cdot (k^2-1)!} \ge \lim\_{k \to \infty} \frac{(k+k^2)!}{2k^2 \cdot k! \cdot k^2!} \ge \lim\_{k \to \infty} \frac{((k+k^2)/e)^{k+k^2}}{2k^2 \cdot \sqrt{2\pi k} \cdot (k/e)^k \cdot \sqrt{2\pi k^2} \cdot (k^2/e)^{k^2}} \\ = \lim\_{k \to \infty} \frac{(k+k^2)^{k+k^2} }{ 4\pi k^{3.5} \cdot k^k \cdot k^{2k^2}} \ge \lim\_{k \to \infty} \frac{k^{2k} k^{2k^2} }{ 4\pi k^{3.5} \cdot k^k \cdot k^{2k^2}} = \lim\_{k \to \infty} \frac{k^{k} }{ 4\pi k^{3.5}} = +\infty. $$
> 5 votes

# Answer
I’m assuming $\sqrt n$ stands for $\lfloor\sqrt n\rfloor$. Using Stirling approximation,

$$\frac{(\sqrt n+n-1)!}{\sqrt n!\\,(n-1)!}=\frac1{\sqrt n!}\prod\_{i=0}^{\sqrt n-1}(n+i)\ge\frac{n^{\sqrt n}}{\sqrt n!}\ge\left(\frac{ne}{\sqrt n}\right)^{\sqrt n}\frac1{\mathrm{poly}(n)}\>\sqrt n^{\sqrt n}$$ for large enough $n$.
> 5 votes

---
Tags: asymptotics
---


# Question
Title: How to translate a virtual Bitvector B to an integer array W | 32-bit integer array
Can somebody please explain to me, how one can calculate W = 2762827861, 1991065600 from previous representation B? An example calculation would be great.

I am unable to figure out how the translation from the second last to the last row works.

The figure is dealing with elements of fixed size. In the first row you simply see an array of ten (n=10) elements A\[i\] with i=1,...,10 such that A\[2\] = 18, ... In the second row, the respective integers are replaced by their binary representation using 5-bit chunks (l=5). The third row, B, is just a concatenation of the second row. The fourth row partitions W into two chunks with w=32 bits each. Empty slots ($2\*32 - 10\*5= 14$) on the right are filled with zeros until two times 32 bits are represented.

The figure is retrieved from https://doi.org/10.1017/CBO9781316588284, Chapter 3: Arrays, p. 41.

# Answer
The binary representation of `2762827861` is `10100 10010 10110 10110 10000 10101 01` in binary. That exactly the first 32 bit word in W. The second value is `0 1110 11010 10110 10100 00000 00000 00`. I've left padded a single zero bit. So these are just the unsigned, big endian values as displayed, although the rightmost zeros are missing as you've indicated.
> 1 votes

---
Tags: arrays
---


# Question
Title: 'Address Function' example of decision tree complexity is not clear
In Arora and Barak's textbook, page 261-262, in decision model complexity, they states:

> Address Function: Suppose that $n = k + 2^k$ and let $f$ be the function that maps $x\_1, x\_2, \dots, x\_k, y\_1, \dots, y\_{2^k}$ to the input $y\_x$. That is, the function treats the first $k = \log n$ bits as an index to an array specified by the last $n - k$. Clearly, this function has a decision tree of depth k+1 (examine the first k bits, and use that to find out which bit to examine among the last $n - k$ bits), and hence $D(f) \leq \log n + 1$.

I don't see why $k+1$ is enough here, for example, take $n = 6$ and hence, $k=2$. Then, let's say we have the following strings:

A = $00-1100$

B = $00-1010$

Now, both strings A and B are different but depth 3 is not enough to know the different between these two strings. Is there something missing here?

# Answer
The decision tree that Arora and Barak mention gets as input $x,y$ and is only supposed to compute the function $f(x,y) = y\_x$. It is not supposed to recover the entire input.

The decision tree proceeds as follows. First, it reads all $k$ bits of $x$. Second, it reads the single bit $y\_x$. This is all it needs to compute $f$. In total, it only reads $k + 1$ bits.
> 1 votes

---
Tags: complexity-theory, decision-tree
---


# Question
Title: Finding the number of children of the predecessor node of a given node in a Binary Search Tree(BST)
I have some propositions regarding BSTs , please can someone confirm whether they are true or false:

Question :

> 1.Suppose we have a node $n\_1$ with a value $val\_1$ i.e $n\_1(val\_1)$
>
> 2.We wish to find the number of children of the predecessor node of $n\_1$ , with respect to inline traversal (That is the number of children of node $n\_2(val\_2)$ with $val\_2$ being the greatest number $val\_2 \< val\_1$)
>
> 3.Assume for simplicity that the BST dosen't have any repetition

Proposition 1: Let $n\_1$ have two children .Then $n\_2$ has atmost one child i.e the number of children of $n\_2$ can't be two

Proposition 2: Let $n\_1$ have only one child and $n\_1$ is not root ,then also $n\_2$ has atmost one child.

Please ascertain whether these propositions are true , but if false can someone provide a counter example ?

# Answer
They're both false. Simple counterexamples:

```
Proposition 1

  2
 / \
1   4
   / \
  3   5

n1 = 4
n2 = 2
number of children of n2 : 2

```

```
Proposition 2

  2
 / \
1   4
   /
  3

n1 = 4
n2 = 2
number of children of n2 : 2

```

Note how the two counter-examples are almost identical. I only changed the number of children of n1 to satisfy your hypotheses; and it had no impact whatsoever on the number of children of n2.
> 0 votes

# Answer
Let us consider the position of the inorder successor of a node in a binary tree. We need to consider two very symmetric cases

* The node has a right child. Then the successor is the first (in inorder) node of that right subtree. It is the most leftmost node, so succ itself has no left child.
* The node has no right child. Then the node is the last (in inorder) node of the left subtree of succ. Hence succ must have a left child.

The existence of a left child for node, and a right child for succ is unimportant. So it is very well possible that both node and its successor both have only a single child.

Regarding the first proposition: Here $n\_1$ is the successor of node $n\_2$. If $n\_2$ has two children, it has a right child, thus $n\_1$ has no left child (left diagram).
> 0 votes

# Answer
The Q is not clear enough for me, an in-order traversal will get u "n2" as the predecessor of "n1" so what is exactly required???

Regarding ur prepositions:

-P1: if n1 has 2 children, or just a left child, then n2 is the rightmost leaf of n1's left child

So **Proposition 1 is correct**

-P2:
-As stated above, if ***n1 only child is a left child***, ***n2 have atmost only left child***. (meaning not just at most 1, but it must be left)

-if n1 has only a right child, then reverse the argument; i.e., n2 is the node n1 is her left child of a right child (search upward for a node smaller than n1.. its parent if it is a right child **does not make a difference if its parent has another left child or not**, parent of parent,....)

For the bold case inside the brackets, ur **second proposition is wrong.**

I'll try to find an example picture, u may search any data structure text book for a complete tree to exhaust all different cases by ur self

Check the example in the second pic in this Q (My mobile is subject to a Denial of Service attack that prevents attaching it here again)

Ambiguity with the Top View of a binary tree

It is clear that 10 precedes 11, 11 has one right child while 10 has two
> -1 votes

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


# Question
Title: Generalization error bound in case of collaborative learning
I am reading the paper "Collaborative PAC Learning" by Blum et al. So I will try to setup the problem here as to avoid reading the complete section (personalized setting).

Assume there are $k$ agents that are learning a labelling function $f^{\*} \in \mathcal{H}$ of Hypothesis class $\mathcal{H}$ and observe a distinct data distribution $D\_i,\\; i \in \[k\]$.

Now, the idea for cooperative learning is quite intuitive. If you find a good candidate hypothesis that has observed $m\_{\epsilon/4,\delta}$ samples over average distribution $D=(1/k)\Sigma\_{i\in\[k\]}D\_i$ there will be atleast $k/2$ agents that have error less than $\epsilon/2$ which can be seen if you apply markov with expectation being $\epsilon k / 4$.

Now, here is the part where I am stuck. We ask all the agents by passing a set of $O(\frac{1}{\epsilon}log(\frac{|N|}{\epsilon\delta}))$ samples if their error is lower than $3\epsilon/4$. Here $N$ is set of agents at each iteration which are not pruned.

> The authors assert that if the risk $err\_{D\_i}(f)\leq\epsilon/2$ then empirical risk for the test sample cannot be greater than $3\epsilon/4$ and if a agent has empirical risk less than $3\epsilon/4$ then true risk is less than $\epsilon$.

Here is my attempt:

Let $R\_T$ be the true risk and $R\_E$ be the empirical risk then we know from VC theorem.

$$ |R\_T-R\_E| \leq \frac{1}{\delta}\frac{4+\sqrt{dlog(2em/d)}}{\sqrt{2m}} $$ Here $m$ is the number of samples and $d$ is the VCdim.

A further simplification would be $$ |R\_T-R\_E| \leq \frac{1}{\delta}\sqrt{\frac{dlog(2em/d)}{2m}} $$

assuming $\sqrt{d}\>\>4$ which is a fair assumption. Now, following the line of reasoning from "Understanding machine learning" shai-shalev book chapter on VC dimension, I get

$$m\geq O(\frac{1}{\epsilon^2\delta^2})$$ which is much bigger than the sample size of samples we initially used. Where am I going wrong?

# Answer
So, I realized this because these are $\epsilon/4$-representative samples or $$ |R\_E-R\_T| \<= \epsilon/4 $$ by construction. So, if empirical error $3\epsilon/4$ given true error is at most $\epsilon/2$. We can say true error is at most $\epsilon$ if estimated error is $3\epsilon/4$.
> 0 votes

---
Tags: learning-theory
---


# Question
Title: Computing convex hull by triangle point inclusion
In my computational geometry book they present the following $O(n^4)$ algorithm for computing the convex hull of a pointset $P \subset \mathbb{R}^2$ assuming general position on the points in $P$: For all $O(n^3)$ triangles do an inclusion test for every point not yet discarded to see if they lie inside the triangle. If a point lies inside the current triangle discard it.

They mention that this can be improved to $O(n^2)$, but I fail to see how? The only $O(n^2)$ i can think of would be something like: Start at a point $P$ with maximum $y$-coordinate. Compute the angle to all other points in $P$ and choose the next point to be the point furthest to the left. Continue like so until you get to where you started, however this seems almost entirely unrelated to the triangle approach.

EDIT: I am aware of Jarvis march, Graham scan, Marriage before conquest etc, but my question is how specifically this idea of pruning points from triangles can yield a $O(n^2)$ algorithm for finding the convex hull

# Answer
The authors could also mean Quick hull algorithm. It is based on discarding the points that lie inside a triangle. A naive implementation of the algorithm runs in $O(n^2)$ time.
> 1 votes

# Answer
The following algorithm may be what they mean:

Initialize $H\leftarrow \emptyset$.

For each point $p\in P$, test if $p$ lies inside the convex hull of $H$. If it does not lie inside the convex hull, add it to $H$.

After we have visited all points, $H$ will be the convex hull of $P$. Since we can test whether a point lies in a convex hull in $O(|H|)$, the algorithm runs in $O(n^2)$ time.
> 2 votes

---
Tags: algorithms, computational-geometry, convex-hull
---


# Question
Title: variant of assignment problem with overload penalties instead of constraints
I want to assign $m$ tasks to $n$ workers where $m\>n$, so as to minimize assignment costs defined by an $m \times n$ matrix $C$. That is, I want to find Boolean variables $x\_{i,j}$ which minimize $$ \sum\_{i=1}^m \sum\_{j=1}^n C\_{i,j}x\_{i,j}, \\ s.t. \sum\_{j=1}^n x\_{i,j}=1 \text{ for all } i=1,\dots,m $$ Rather than a set of hard constraints, e.g., each worker can only perform a certain number of tasks, I instead want to penalize assigning lots of jobs to a single worker, by adding a second cost term $$\sum\_{i=1}^m f(k\_i)\\,,$$ where $k\_i$ is the number of jobs assigned to worker $i$ and $f$ is some super-linear function such as $f(x) = x^2$.

Is this problem as hard as the generalized assignment problem, i.e. **NP-hard**? I'm asking in the first case about $f(x) = x^2$ though also curious to know how the answer might change for other functions.

# Answer
The complexity depends on the penalty function.

When the penalty function $f(\cdot)$ is non-decreasing and convex i.e. $0 \le f(k+1)-f(k) \le f(l+1)-f(l)$ whenever $k \le l$, then this problem can be solved in polynomial time as a minimum cost flow problem. $f(x) = x^2$ is a convex function in this sense.

Take the standard representation of the assignment problem as a flow network. Instead of adding one edge from the source vertex for each worker, add $m$ parallel edges for each worker. For $k \in \[m\]$, $k$'th edge for a worker has capacity $1$ and cost $f(k)-f(k-1)$. This solution works even if each worker $i \in \[n\]$ has different penalty function $f\_i(\cdot)$.

If the penalty function is merely non-decreasing and not necessary convex, the reduction above breaks down because $k+1$'th edge could be chosen before the $k$'th edge. Indeed, the problem is NP-complete.

There is a simple reduction from the set cover problem. In the reduced problem instance, the sets correspond to the workers, and the elements correspond to the tasks: $$ C\_{i,j} = \begin{cases} 0 & \text{ if } j \in S\_i \\ \infty & \text{ otherwise} \end{cases} \\ f(k) = \begin{cases} 0 & \text{ if } k = 0 \\ 1 & \text{ otherwise} \end{cases} $$

The total cost of the assignment is equal to the number of workers with at least one task assigned. This is equivalent to minimizing the number of sets to cover all elements.

As additional information, the problem can be thought of as a welfare maximization problem of the congestion game. Here, each task corresponds to a player of the game, and the workers are resources. For example, see \[1\] for an overview of the computational complexity in related cases.
> 2 votes

---
Tags: complexity-theory, np-hard, assignment-problem
---


# Question
Title: what does $(1 + (λ, λ))$ Genetic Algorithm mean?
I am discovering the topic of Genetic Algorithms, I read a bit about it on wikipedia and towardsdatascience. When I checked papers some papers, I found them using the notation "$(1 + (λ, λ))$" Genetic Algorithm. What does it mean exactly?

They also use the notation "(1 + 1)" evolutionary algorithm. Any idea what these notations mean?

Example paper: https://arxiv.org/pdf/2004.08664.pdf

Thanks

# Answer
> 1 votes
The very first sentence in the paper you link to says

> The $(1 + (\lambda, \lambda))$ genetic algorithm (GA), proposed in \[12\], is a fairly recent algorithm with very interesting properties.

We search for the given citation, and see that it says in Section 1.3 that

> We use a uniform crossover that takes bits from the parent with probability $1 − c$ and from the winning offspring with probability $c$ for some not too large crossover probability $c$. The outcome of such a crossover step will be close enough to the parent to give us a good chance of keeping the positive aspects of the parent. To give newly found positive genes of the winning offspring a reasonable chance to survive, we create again $\lambda$ offspring by this crossover. We call this algorithm the $(1 + (\lambda, \lambda))$ GA.

You can do a similar lookup for the (1+1) EA algorithm.

---
Tags: notation, genetic-algorithms, evolutionary-computing
---


# Question
Title: How can we assume the asymptotic complexity of 1/2n^2 - 3n
I am trying to understand how asymptotic complexity of the given function is calculated based out of Introduction to algorithms by Thomas Cormen.

In the book we are trying to solve inequality for $f(n) = \frac12n^2-3n$.

It is solved such that $c\_1n^2 \leqslant \frac12n^2 - 3n \leqslant c\_2n^2$.

Dividing both sides by $n^2$ results in $c\_1\leqslant \frac12 - \frac3n\leqslant c\_2$.

In the book I cannot understand the below explanation that the author gives. Can someone help me out here ? evaluating inequality and calculatin n0 as mentioned in the book

Full text as in the book problem description

# Answer
> 1 votes
The author chooses an initial value $n\_0$ of $n$ such that for $n\geqslant n\_0$, $f(n)$ is positive.

The value $n\_0$ is found solving: $$f(n) \> 0\iff\frac12-\frac3n\> 0 \iff \frac12\> \frac3n\iff n\>6$$

That's the reason for $n\_0 = 7$.

Now, note that for $n\geqslant n\_0$, $\frac12-\frac3{n\_0}\leqslant \frac12-\frac3n$. In order to get $c\_1$ such that $c\_1\leqslant \frac12-\frac3n$ foreach $n\geqslant n\_0$, it suffices to solve: $$c\_1\leqslant \frac12-\frac3{n\_0} = \frac12-\frac37 = \frac1{14}$$ That's the reason for $c\_1 = \frac1{14}$.

Now, since for all $n$, $\frac12-\frac3n\leqslant \frac12$, we can choose $c\_2 = \frac12$.

---
Tags: time-complexity, asymptotics, big-o-notation
---


# Question
Title: Splitting the output of a wide hash in lieu of multiple independent hashes
Certain algorithms require two independent hash functions. An optimization I've seen is to split the output of a wide hash function and use the parts instead of the two independent hash functions of shorter output.

For instance, double hashing is often used as a technique to compute the k independent indexes required by a Bloom filter rather than using k independent hashes, but this is often optimized to use a single wide hash and splitting its output. E.g., Google's Guava Bloom filter operates in this way using 128-bit Murmur3.

Alas, I've not been able to find any literature that addresses when it may be safe to do this. I.e., what properties should the wide hash function have for this to be acceptable? Is meeting the bit independence criterion sufficient?

# Answer
This is a heuristic. Any use of hash functions is a heuristic.

Here is a justification why it is a reasonable/plausible thing to do. Suppose our hash function is a uniform random function $h:\\{0,1\\}^m \to \\{0,1\\}^{2b}$. Define $h\_0(x)$ to be the first half of $h(x)$ and $h\_1(x)$ to be the second half of $h(x)$. Then $h\_0,h\_1$ are independent uniform random functions with signature $\\{0,1\\}^m \to \\{0,1\\}^b$. It follows that if our hash function is indistinguishable from a uniform random function, then using its output in this way will be indistinguishable from using two independent smaller hash functions.
> 1 votes

---
Tags: hash, bloom-filters
---


# Question
Title: In Programming data types size are depends upon what?
> In Programming there is different data types (int , cahr , bool , float ) and they have different sizes (1,2,4,8 .. Bytes) , and the size of data type are depends upon hardware or architecture of computer or any thing else? as a beginner give me answer in simple language plz !

# Answer
> 0 votes
In C, C++ and some other languages, char, signed char, and unsigned char are one byte *by definition*. A byte is whatever the type char is. It's like asking "how long is a meter" and I answer "exactly one meter".

The size of these types depends *on the compiler*. First, the language gives a definition what the types are capable of doing. For example, unsigned char is "at least 8 bit, supporting values from 0 to at least 255". A signed integer in C is "at least 16 bits, capable of representing at least values from -32767 to +32767". It could be 16 bits. In that case, a byte is 16 bits. (An "octet" is the name for a byte that is eight bits. A byte isn't required to be an octet). The compiler writer then looks at the hardware, and decides what number of bits would be best for some type. One restriction is the size must be a multiple of a byte - you can't have 8 bit char and 30 bit int. You could have 10 bit char and 30 bit int; that would be unusual but allowed. The size in bytes is obviously less if a byte is bigger, a 32 bit int can be four 8-bit bytes or two 16-bit bytes.

# Answer
> 0 votes
Compiler, if supported by the hardware but it is all based upon architecture and design of the machine.

---
Tags: computer-architecture, programming-languages
---


# Question
Title: What is the relation between reversible circuits and invertible functions?
A reversible circuit, if I understand it correctly, is a circuit where every gate in the circuit is invertible, i.e. can simply be “turned in the opposite direction”, so that the entire circuit can in a sense just be “turned in reverse” without changing the circuit architecture.

An invertible function is not defined in terms of computational models, but in terms of whether the function is injective.

How are these two concepts related? Does an invertible function always have a corresponding reversible circuit?

# Answer
> 1 votes
There is quite a lot of work on the design of reversible programming languages that express total bijective functions operating on finite number of bits, by Amr Sabry and his collaborators.

* Information Effects: This paper describes a language Theseus which is a first-order language that computes reversible functions using type isomorphisms of finite types. The language is presented as a calculus of combinators that express building blocks for reversible circuits, and their operational semantics.
* Computing with Semirings and Weak Rig Groupoids: This paper suggests an equational theory for this language using 2-combinators expressing circuit equivalences.
* Symmetries in Reversible Programming: This paper shows that this equational theory is indeed sound and complete, and every permutation can be expressed as a program in this language. The main result is that this language of finite types, 1-combinators for type isomorphisms, and 2-combinators for program equivalences, presents the free symmetric rig groupoid (on the empty signature), and establishes an equivalence with the groupoid of finite sets and bijections. Using this, the authors derive several meta-theoretic results about the language. The semantics uses the Coxeter presentation of symmetric groups and other techniques from coherence of symmetric monoidal categories.
* Embracing the Laws of Physics: Three Reversible Models of Computation: This paper is a detailed survey of this line of work, and future work.

There are also other extensions to this reversible language by this group of authors and others.

---
Tags: one-way-functions, reversible-computing
---


# Question
Title: Is there a non PSPACE language s.t exponential padding of it is PSPACE?
I've had an exam in computational models a few days ago, and would like to check whether I made a mistake. The question goes like that:

Is there a language $ L \notin PSPACE $ over the alphabet {0,1} such that $$ L\_{pad} = \\{wp^{2^{|w|}-|w|} | w \in L\\} \in PSPACE $$ over tha alphabet {0,1,p}.

On the spot I answered no, because L is poly-space reducible to $L\_{pad}$ so that would contradict $L \notin PSPACE $. I also wrote that a poly-space reduction works because I don't have to write the full reduction result in order to use it, just re-calculate it whenever I need the i'th letter of the result.

In retrospect I think I may be wrong, because padding allows me to use space exponential in |w| while staying polynomial in terms of the padded w length.

Both of these answers seem intuitively reasonable, and I would like your help determining which one is correct and why the other one isn't.

Thanks

# Answer
Yes, there are such languages. Consider a language $L$ that is in e.g., $SPACE\[2^{n/2}\]$, but not in PSPACE. Such a language exists by the space hierarchy theorem.

I claim $L\_{pad}\in PSPACE$. Indeed, given input $wp^k$, it's first easy to verify in PSPACE that $k=2^{|w|}$, by simply computing the length of $w$. Then, it can be decided whether $w\in L$ using $O(2^{n/2})$ space, which is less than $2^k$ for any large enough $k$.

The point is that the addition $p^{2^{|w|}}$ provides you with "free" computation time/space.
> 2 votes

---
Tags: complexity-theory, reductions, space-complexity, computation-models
---


# Question
Title: How to check if a number is a square with deterministic single-tape Turing Machine
I am trying to design a (deterministic) one tape Turing machine that can accepts the following language L = {0^{n^2} | n belongs to N} , but so far i couldn't find a proper solutions, neither in similar questions.

I know it's a pretty general problem, but I'm stacked so far and I'm not having any good idea. Thanks in advance, any hint is welcome!

# Answer
> 0 votes
The basic idea to generate squares iteratively using the formula $(n+1)^2 = n^2 + (2n+1)$ was suggested in answers to earlier questions like

This basic setup can be applied regardless of the Turing Machine model. A nondeterministic approach guesses the value of $n$ and compares the generated number with the input, a deterministic model will check the successive squares until the input size is less than the square.

Also the number of tapes is not an issue. Apart from the input on the tape there is ample space to the neccessary computations. Alternatively one can generate $n^2$ in the same space that is taken by the input. Just "cross out" 1,3,5,7, etc input $0$'s until either all $0$'s are gone (and we accept) or there are not enough $0$'s available (and we reject).

The language of squares is a context-sensitive language. That means it can be accepted by a deterministic Turing Machine that uses no additional space except the space taken by the input.

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


# Question
Title: All nodes reachable from source in residual network of any max flow are included in $S$ for any min-cut $(S,T)$
Let $G = (V,E)$ be a directed graph with source $s$ and sink $t$ and $s \neq t$. For each edge $e \in E$, we have $c(e) \in \Bbb N$.

Also, we are given a max flow function $f$ on that network.

Let $R\_f$ be the residual network of $f$.

I would like to prove that the set formed by all the nodes reachable from $s$ in $R\_f$ is a subset of $S$ from any min-cut $(S,T)$.

I tried to write a proof by contradiction but I'm just getting stuck every time trying to analyze the Min-Cut after removing a certain node.

# Answer
The key idea is to understand max-flow min-cut theorem and its proof. The following observation is a corollary of that theorem basically.

**Lemma**. Let $f$ be a max-flow and $\mathcal C=(S, T)$ be a min-$(s,t)$-cut. Then

* for any edge $(u,v)$ such that $u\in S$ and $v\in T$, $f((u,v))=c((u,v))$.
* for any edge $(u,v)$ such that $u\in T$ and $v\in S$, $f((u,v))=0$.

In plain words, the lemma says that $f$ must use all capacities of all edges crossing $\mathcal C$ without using any capacities of any edge going the other way.

**Proof**. The conservation of flows implies that $|f|=f\_{out}(S)-f\_{in}(S)$. Since $f\_{out}(S)\le c(\mathcal C)=|f|$, where $c(\mathcal C)$ is the capacity of $\mathcal C$ and $f\_{in}(S) \ge0$, we must have $f\_{out}(S)= c(\mathcal C)$ and $f\_{in}(S)=0$. $\checkmark$

---

The lemma above means that given any min-cut $(S, T)$, in the residual network $R\_f$, no edge of positive capacity goes from $S$ to $T$ since

* the capacity of any edge that goes from $S$ to $T$ is reduced to $0$ in $R\_f$, and
* the "pushed-back capacity" of any edge that goes from $T$ to $S$ is $0$ since $f$ is 0 on those edges.

In other words, any path of edges of positive capacity in $R\_f$ cannot cross the cut $(S,T)$. So, any path of edges of positive capacity that starts from $s$, which is a node in $S$, must stay in $S$. $\checkmark$

---

**Exercise (every maximal flow yields the same minimal cut)** Given a flow network $(G,s,t,c)$ and a flow $f$, let $S\_f$ be the set of all vertices that are reachable from $s$ in the residual network of $f$. Given two maximal flows $f\_1$ and $f\_2$, show that $S\_{f\_1}=S\_{f\_2}$.
> 1 votes

---
Tags: graphs, network-flow, minimum-cuts
---


# Question
Title: Problems that are polynomially "hard" to compute but "easy" to verify
In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the degree of the polynomial run time is very large (e.g. $\Omega(n^{10000})$) such that any reasonably large problem is still out of reach for our current computing technology.

My question is: is it possible to find/construct a problem that have a lower-bound polynomial complexity $\Omega(n^p)$ to compute but an upper bound $O(n^q)$ to verify, with $q$ being quite small (e.g. $q=1$) and $p\gg q$. This problem would function essentially the same as current problems for which no known polynomial algorithms exist (e.g. factorization), and thus would still be usable in e.g. security systems in even in the case of $P=NP$.

# Answer
> 34 votes
No such problem is known (not with a known mathematical proof of a lower bound). Of course cryptographers would jump on it if we had one. As a result, cryptography is currently based on assumptions that we hope are true but we cannot prove (these are sometimes called "hardness assumptions"), and then we prove that if the assumption is valid, then the cryptographic scheme will be secure against attack.

Many good cryptosystems offer a reasonable candidate for a problem for which verification is much easier than solving, but we have no mathematical proof that this is necessarily so. For instance, factoring large integers seems like a good candidate for such a problem: it is easy to verify that you have correctly factored a large number, but it seems to be hard to find those factors in the first place. Breaking AES also seems like a good candidate for such a problem: it is easy for a cryptanalyst to verify that they have found the right AES key to decrypt some known plaintext pairs, but it seems to be hard to find the right AES key in the first place. However, we have no mathematical proof for any of these.

You might be shocked to learn that there is no explicitly known function family for which we can prove a super-linear lower bound (i.e., for every explicit function we can think of, we cannot rule out the possibility that it can be computed by a linear-size circuit). See here for a catalog of just how weak our known results are. This highlights just how far we are from being able to prove useful lower bounds.

I have some reading for you that might be helpful:

One early attempt at what you're hoping for are Merkle puzzles. These show a gap of the form you mention, with $O(n^2)$ time for attackers to break (i.e., to solve) but $O(n)$ time for defenders to compute (i.e., to verify). In your notation, this amounts to $p=2$ and $q=1$. This result holds only under the unproven assumption that solving a single puzzle takes $n$ steps of computation, but we have no concise (constant-length) puzzle for which we have a proof that solving will take that long, so even Merkle puzzles don't do what you are hoping for -- they still rely on an unproven assumption. And, there is a proof that the basic approach found in Merkle puzzles doesn't generalize to larger gaps (larger ratios of $p/q$), so they don't seem to lead somewhere that will be practically useful, even if we ignore that they rely on an unproven assumption like every other cryptosystem.

# Answer
> 1 votes
What about problems that cryptocurrencies are using?

The problem is, given a hash function, to find data (of specified length) that has its hash starting with specific number of zeros. Finding it takes a long time, but it can be checked super fast just by calculating hash of this data and verifying it looks as expected.

---
Tags: complexity-theory, time-complexity, polynomial-time
---


# Question
Title: How bits translated into text on the screen?
recently i started studying computer science and computer graphics, and one question really haunts me. Mby someone can explain this. How bit patterns become translated into (for example ) text. I know we have encoding like ascii and unicode but this is also just bit patterns. Main mystery is at what point do the bits turn into what we see on the screen? So maybe you have some resources which can explain it? How bits translated into text? Thanks.

# Answer
> 3 votes
Most often, bits are not translated into text. They are translated to RGB colours pixel by pixel on a framebuffer found into RAM. The colours will be arranged pixel by pixel to make it look like a letter appeared on the screen but it is simply some pixels arranged in a pattern to make it look like a letter.

Today, everything is PCI including graphics cards (and even the integrated graphics card in the CPU). PCI works with MMIO. You write to some conventional position in RAM and it will write to the registers of the PCI device. PCI devices have conventional configuration spaces found in RAM. The beginning of the configuration spaces can be found in the MCFG ACPI table (see https://wiki.osdev.org/ACPI).

Among PCI devices, graphics cards are the least standardized and the hardest to drive. The way they work is often not mentioned anywhere and you are left to either use an existing OS for which the graphics card manufacturer has provided a driver or use the integrated graphics card for which documentation is open. If you want to drive a discrete graphics card from a custom OS, it will be very hard if not impossible.

Most computer comes with firmware which understands the things they need to drive. For example, the UEFI implementation of an x86-64 motherboard can drive the integrated graphics card of your Intel/AMD CPU. It will thus set this integrated graphics card into a framebuffer mode that can be set (the width and the height and other things) using the UEFI system call interface. A framebuffer is where the screen is simply represented in RAM as an array of pixels. You write RGB colors in order in RAM to make things look like letters or to show an image (or a window or anything else).

To drive more complex discrete graphics cards, an existing OS will present a modular driver model. The modular driver model often takes the shape of a virtual filesystem where every device is presented to the upper layer of the OS as a file. For example, Linux will present a virtual character device file called /dev/dri/card0 for the integrated graphics card.

To drive the card, user mode will often communicate through sockets with the X server which is a special process which is started as the "master" and as a privileged (sudo) process. The X server will make system calls in the Linux kernel to write to the screen.

When using more complex graphics card (that aren't in a framebuffer mode), the graphics card vendor doesn't have a choice but to provide a user mode library to drive the card. This is often an OpenGL (or any 3D rendering convention) implementation. The implementation of OpenGL will drive the card by first opening the /dev/dri/card0 file and then make mostly ioctl() system calls on the file. The ioctl() call has a request argument which is an unsigned long and a variable amount of arguments after. The ioctl() call thus allows to implement any number of operations on the file.

Underneath, the kernel driver (often called kernel module) will do complex things like writing to the PCI registers of the graphics card to ask the graphics card to do some complex operations like drawing. PCI devices are DMA so they can directly read/write RAM without involving the CPU.

# Answer
> 4 votes
On machines with a CRT, this was implemented in the display hardware. As the line scanning took place, the value of the character at the row/column position was obtained from RAM, and that value was used to look up on the fly a hard-coded character map (in ROM), storing a binary representation of the characters. This is how the hardware knew if the current dot was to be on or off.

Nowadays, characters are painted in a graphical memory buffer, possibly using sophisticated rendering algorithms to give the characters the best appearance. The characters are described by font files (in a vector form), stored on disk, and the system can paint the characters at the desired sizes on demand, with antialiasing.

# Answer
> 1 votes
What happens on a more modern computer: You start with an abstract character. The character may be an ASCII character, a Cyrillic character, a Japanese character etc. The developer of your software has decided to draw that character using some font, and some font size.

Some software on your computer takes the font, and decides which glyph to use. A glyph is basically "what a character is supposed to look like". For example, a capital Latin A and a capital Greek Alpha are supposed to look exactly the same, they are the same glyph.

Now most likely your computer has a description of the font, for example a Truetype font, which has one or more curves for describing what the glyph looks like, depending on the glyph, the font, and the font size, possibly other attributes like weight (light, bold, extra bold, slanted, or italic).

Some software turns those lines into an image consisting of pixels, and draws the image on the right place on the screen. That's complicated in its own right, because the glyph can also have a colour, it can be opaque or more or less transparent, and it can be cut off if it doesn't fit where it should go on the screen.

---
Tags: computer-architecture, encoding-scheme, bit-manipulation
---


# Question
Title: Picking a pseudo random number generator
I'm looking for what I think is a random number generator, it should have the following properties, but I'm completely uncertain how to look for a suitable algorithm. I'd appreciate either pointers to a specific algorithm, a class of them, places for starting my research, or an explanation of why what I'm looking for isn't feasible.

Given a set of N items (item 1, item 2, … item N) I'm looking for what I presume is a pseudo random number generator that will:

* for a given positive number input (A) return a deterministically chosen item (item B) — `g(A) = B`
* where B is always between 1 and N inclusive
* where two consecutive inputs will never return the same output — `g(A) != g(A+1)`
* where `g(A)` is frequently *not* equal to `g(A+N)` — ie. it's not just a repeating sequence
* any N consecutive outputs have a reasonably high probability of being the full set of 1 to N.
* there's a broadly uniform chance of getting any B for a given A.
* `g(A)` can be calculated without knowing `g(A-1)`

Can anyone help?

# Answer
One possibility which seems to tick most of the boxes is to construct an indexed family of functions $h\_i : N \rightarrow N$ with the property that for all $i$, $h\_i$ is a permutation (i.e. a bijection or isomorphism). Then:

$$g(a) = h\_{\left\lfloor a/N \right\rfloor}(a \bmod N)$$

This has the property that $g(Nk)$ to $g(Nk + N - 1)$ produces all of the numbers from $1$ to $N$, but the next $N$ values are a different permutation.

If $N = 2^{2b}$ for some $b$, constructing permutations is surprisingly easy by using Feistel networks, and by using operations other than exclusive or (e.g. modular arithmetic) and forgoing some symmetry, the construction can be generalised for any $N$ which isn't prime.

The one requirement that this doesn't solve is that it doesn't absolutely guarantee that $g(i+1) \ne g(i)$ if you cross a permutation boundary. But it's unlikely; you can expect it to happen roughly once in every $N^3$ values.

The only other thing I can think of is to perhaps do something clever with de Bruijn sequences, but I don't believe we know a way to pseudo-randomly index them.
> 2 votes

---
Tags: pseudo-random-generators
---


# Question
Title: How can I define programming struct variables as mathematical notation?
My purpose is to write a journal paper related to shared computing more abstractly (simply **cost model**) and I need to refer to these variables in both equation and its corresponding pseudocode.

I want define variables of a `struct` as mathematical notation. I get lost in between programming and mathematical concept. I'm trying to pin down the convention where property $a$ of object $b$, I am not sure which one is correct way to use: $a.b$ , $a\_b$ , $a(b)$.

---

Assume I have following `structs` in C. I want to define those variables and use them in both equation and its corresponding pseudocode.

```
struct Jobs {
   int start_time;
   int completion_time;
   int run_time;
   int requested_cpu;
}

struct Providers {
    int fee;
    int available_cpu;
}

int main( ) {
   struct Jobs j;
   struct Providers p;
}

```

---

The way I define them is: `j.<variable_name>`, `p.<variable_name>`, which is more likely a programming approach. Is it an appected notaition? Here should I define $j$ and $p$ as well?

Example:

```
Symbol   |  Meaning
-------------------------------------------------------
$j$       | Job object
$j.t_s$   | Start time of the job.
$j.t_c$   | Completion time of the job
$j.X^{t}$ | Execution time of the job
$j.R$     | Number of CPU cores requested for job
$p$       | Provider object
$p.F$     | Fee of provider with per CPUminute
$p.A$     | Number of available CPU cores on provider
...

```

Equation example:

$$C(j, p) =\underbrace{p.F \times j.R \times j.X^{t}}\_{computation\ cost}$$

The way I refer them in a pseudocode:

```
if p.A = 0 then
    C = p.F * j.R * j.X^{t}
fi

if j.t_s < j.t_c then
    ....
fi

```

How can I define programming struct variables into mathematical notation concept? Any recommendation or helpful guide as books would be appreciated.

# Answer
Your way of using pseudocode is clear and is very commonly used.

Remember that the goal of pseudocode is to be clear. It is not to provide mathematical formalism. It is intended for a human audience, not for a computer. As long as most readers will understand what you mean, it is fine.

As a stylistic matter, I don't like `j.X^{t}`; I would just use `j.X`. (As it stands, people might wonder whether `t` is a variable and this is representing exponentiation or indexing or something. They won't imagine that `X^{t}` is the name of a field.) Similarly, I don't like `j.t_s` so much; I would like `j.t` or `j.s` or `j.ts` better.
> 2 votes

# Answer
From the perspective of functional programming languages like C, structs are just records - a composite type. You may consider algebraic data types as mentioned by @deepak Gupta.

If you want to be more precise, you might want to delve into abstraction like in OOPS. Structs are essentiallyba simpler form if abstraction than a class. Object calculus as proposed by Abadi, Cardelli might be what you are looking for. The book is not free but some of their course slides are - see e.g. page 49 onwards here http://lucacardelli.name/Talks/1997-06%20A%20Theory%20of%20Object%20(ECOOP%20Tutorial).pdf
> 2 votes

---
Tags: notation, mathematical-analysis
---


# Question
Title: Linear encoding of a feed forward neural network
I was reading \[1\] about reachability analysis of a feed forward neural network (FFNN). The paper encodes a FFNN as a linear programming problem. Suppose $x^{(i)}$ is the vector output of the ith layer, $W^{(i)}$ is the weight matrix corresponding to layer i, and $b^{(i)}$ is the bias vector. So by definition, the output of the ith layer, $x^{(i)}$, should be $x\_j^{(i)} = W\_j^{(i)}x^{(i-1)} + b\_j^{(i)}$.

On page 4, under definition 7, I understand the constraint $x\_j^{(i)} \ge W\_j^{(i)}x^{(i-1)} + b\_j^{(i)}$.

But for the next constraint, I don't get where $\delta^{(i)}$ and M come from? I thought the constraint $x\_j^{(i)} \le W\_j^{(i)}x^{(i-1)} + b\_j^{(i)} + M\delta^{(i)}\_j$ was because the FFNN is considered to have a ReLU activation function, so the $M\delta^{(i)}\_j$ will bring the value upto 0 in case $W\_j^{(i)}x^{(i-1)} + b\_j^{(i)}$ is negative. But how are they chosen and why is $x\_j^{(i)} \le M(1 - \delta^{(i)}\_j$)

References

1. An approach to reachability analysis for feed-forward ReLU neural networks by Alessio Lomuscio, Lalit Maganti (June 2017)

# Answer
> 0 votes
The idea is that $\delta\_j^{(i)}=1$ means that the input to the ReLU was negative (so its output is zero), and $\delta\_j^{(i)}=0$ means that the input to the ReLU was positive (so its output is positive).

You can then verify that both equations make sense. In particular, I suggest you consider separately the case where $\delta\_j^{(i)}=0$ (and thus $W\_j^{(i)}x^{(i-1)}+b\_j^{(i)} \ge 0$ from the case where $\delta\_j^{(i)}=1$ (and thus $W\_j^{(i)}x^{(i-1)}+b\_j^{(i)} \le 0$). You will see that this program correctly captures the constraints for both cases, forcing $x^{(i)}\_j = W\_j^{(i)}x^{(i-1)}+b\_j^{(i)}$ in the former case and forcing $x^{(i)}\_j = 0$ in the latter case, which correctly captures the behavior of the neural network and the ReLU unit.

---
Tags: machine-learning, linear-programming, software-verification
---


# Question
Title: What is the meaning of conservative dynamics in the context of Conway's Game of Life
While reading up about Conway's Game of Life, I often come across the term conservative or non-conservative dynamics. What exactly does these terms mean?

My guess is that a certain quantity (e.g., number of dead cells) always remains the same as the system evolves. Is this what it means? Thank you.

The paper I was looking at is "Phase transitions in a Conservative Game of Life" by Hans J. Herrmann (https://arxiv.org/pdf/2101.07225.pdf)

# Answer
Some relevant quotes from the paper:

> We investigate the dynamics of a conservative version of Conway’s Game of Life, in which a pair consisting of a dead and a living cell can switch their states following Conway’s rules but only by swapping their positions, irrespective of their mutual distance.

> A common feature of these previous studies is that they preserve the nonconservative nature of the dynamical rules. Here, on the other hand, we modify the dynamical rules in order to enforce conservation of the number of cells of both types.

> In contrast to the original version of the Game of Life, we assume a conservative, asynchronous and nonlocal dynamics: at each time step, we randomly select an unsatisfied living cell and an unsatisfied dead cell and we switch their states

In other words, a dynamics is *conservative* if it conserves the number of cells of each type.
> 2 votes

---
Tags: cellular-automata
---


title: Applications of the DGIM algorithm

text:
# Question
Title: Applications of the DGIM algorithm
In the field of mining of data streams the algorithm of Datar-Gionis-Indyk-Motwani (**DGIM**, M. Datar, A. Gionis, P. Indyk, and R. Motwani, “Maintaining stream statistics over sliding windows,” SIAM J. Computing 31, pp. 1794–1813, 2002.) is known. Given is a binary stream with a sliding window of length $N$, where $N$ is larger than the computer memory. It is used to answer the question of how many are there 1s in the sub-window consisting last k bits, where $1\le k\le N$.

I understand the algorithm, but I cannot come up even with a single example, where DGIM would beat the naive counting.

Let me explain. It is claimed that the advantage of the algorithm is reduced storage. The whole window can be represented with just $\mathcal{O}(\log^2N)$ storage, from where the counting question for any $1\le k\le N$ can be answered. Assume that at any instance of time we would like to know how many 1s are in the ranges $\[k\_i,N\]$, where $i=1,N\_q$. The number of queries should not be too large, i.e., $N\_q\ll N$ for, otherwise, $N\_q\>memory$, and we cannot digest the results of the algorithm. But then, it is sufficient to have just $N\_q$ simple counters, which are updated every time step!

The only scenario which would merit the DGIM algorithm is when $k\_i$ are not known in advance, and the calculations need to be adjusted on the fly. But why would it be the case? I suppose that DGIM should be used for plotting time-dependent histograms, but the bin size of the histograms is usually fixed, isn't it?

# Answer
> 3 votes
In the streaming model, old inputs are gone and cannot be read again unless explicitly copied to the memory. Therefore, you cannot use a simple counter: how to determine whether the counter should be decremented when an input element goes out of the window?

In fact, if the window size is $n$ then exact window counting requires $n$ bits of memory. The point of streaming algorithms is to overcome this barrier by clever approximation algorithms.

---
Tags: counting, streaming-algorithm
---


# Question
Title: Is "deterministic non polynomial time" the same as "non deterministic polynomial time"?
I have always though that NP consists of problems solved in a **non polynomial** time by a deterministic Turing machine. Recently I discovered that NP classifies all the problems solved by a **non deterministic** Turing machine in polynomial time.

Do those 2 machines solve the same problems? Meaning, can a deterministic Turing machine solve the problems in NP with non polynomial time, and should I consider them equal?

Thank you in advance for you help!

# Answer
A non-deterministic machine is basically able to make a lucky guess at any time. There are situations where this doesn't actually help, so there are problems that take polynomial time with a non-deterministic Turing machine, but take the same time with a deterministic one.

Plus decision problems in NP cannot be solved in polynomial time on a non-deterministic Turing machine in all cases, but only in cases where the answer is "YES". If the answer is "NO", then the non-deterministic machine doesn't help.
> 0 votes

---
Tags: complexity-theory, turing-machines, time-complexity, np, complexity-classes
---


# Question
Title: Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method
Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log\_2n}$ is $O(n\log\_2\log\_2n)$, where $T(1) = Θ(1)$.

I tried to form the Induction Hypothesis but didn't succeed in choosing the right one.

*Try 1:*

If we assume $0 ≤ ck\log\_2\log\_2k,\forall k \< n$, must show $T(n) ≤ cn\log\_2\log\_2n$.

$$ T(\frac{n}{2}) ≤ c(\frac{n}{2})\log\_2(\log\_2n - 1),\because \frac{n}{2} = k \< n$$ \begin{align} & T(n) ≤ cn\log\_2(\log\_2n - 1) + \frac{n}{\log\_2n}\\ & ≤ cn\log\_2\log\_2n + \frac{n}{\log\_2n}\\ \end{align} but this expression is never less than $cn\log\_2\log\_2n$, due to the positive $\frac{n}{\log\_2n}$ term.

*Try 2:*

Assume $0 ≤ ck\log\_2\log\_2k - \frac{bk}{\log\_2k}, \forall k \< n$, must show $T(n) ≤ cn\log\_2\log\_2n - \frac{bn}{\log\_2n}$.

$$T(\frac{n}{2}) ≤ c(\frac{n}{2})\log\_2(\log\_2n - 1) - \frac{bn}{2(\log\_2n - 1)}, \because \frac{n}{2} = k \< n$$ \begin{align} & T(n) ≤ cn\log\_2(\log\_2n - 1) - \frac{bn}{(\log\_2n - 1)} + \frac{n}{\log\_2n}\\ & ≤ cn\log\_2\log\_2n - \frac{bn}{\log\_2n} + \frac{n}{\log\_2n}\\ \end{align} If we factor the $\frac{-n}{\log\_2n}$ out, we get $cn\log\_2\log\_2n - \frac{n}{\log\_2n}(b - 1)$. Once again, it's never less than $cn\log\_2\log\_2n - \frac{bn}{\log\_2n}$ because its $\frac{n}{\log\_2n}$ negative factor is bigger.

I tried reforming the inductive hypothesis to be $ck\log\_2\log\_2k - \frac{2bk}{\log\_2k}$, $ck\log\_2\log\_2k - \frac{bk}{2\log\_2k}$, $ck\log\_2\log\_2k + \frac{bk}{\log\_2k}$, but I can never get my expression bounded.

Any suggestions?

# Answer
Let $S(n) = T(n)/n$, so that $$ S(n) = \frac{T(n)}{n} = \frac{2T(n/2)}{n} + \frac{1}{\log\_2 n} = S(n/2) + \frac{1}{\log\_2 n}. $$ Suppose now that $n = 2^k$, and suppose $S(1) = T(1) = C$. Then $$ S(2^k) = S(2^{k-1}) + \frac{1}{k}, $$ and so unrolling, we get $$ S(2^k) = \frac{1}{k} + \cdots + \frac{1}{\ell} + S(2^{\ell-1}). $$ In particular, taking $\ell = 1$, this gives $$ S(2^k) = \frac{1}{k} + \cdots + \frac{1}{1} + S(1) = H\_k + C, $$ where $H\_k$ is the harmonic number, well-known to satisfy $H\_k = \ln k + O(1)$. Therefore if $n = 2^k$ then $$ T(n) = nS(n) = n\ln\log\_2 n + O(n). $$ Using more accurate asymptotics of the harmonic number, we can find an even better approximation to $T(n)$, for example $$ T(n) = n\ln\log\_2 n + (\gamma+C) n + \frac{1}{2} + O\left(\frac{1}{n}\right). $$
> 0 votes

---
Tags: complexity-theory, asymptotics, recurrence-relation, big-o-notation
---


# Question
Title: Which abstract machine or language is exactly expressive enough to produce the computable functions?
I'm interested in software verification and therefore only interested in algorithms which always terminate in predictable amount of time and can determine whether the final result is expected or not, hence I think the computable functions are a good place to start as as I understand it these are functions which can be defined using a decidable procedure, i.e. an algorithm which always terminates.

I'm a little familiar with the Chomsky hierarchy, I imagine I would be looking for a language or an abstract machine that is as far up the hierarchy as possible, but does not suffer from the halting problem. However I don't think Linear-bounded Turing machine's are what's needed as these seem to just cut of resources i.e. they are just computers which stop simply because they run out of resources. I think I need something which limits the number of computation steps using logical expressions which can be reasoned with effectively, so by the time the computation finishes we are able to describe something about the final state. I need to be able to reason about cycles too. Could this be pushdown automaton? Are there any other suitable models I've missed?

# Answer
> 2 votes
Your question is a bit unclear, but it seems to me that you are asking for a machine model that gets you exactly the computable total functions. There is no such thing.

The reason is simple: There cannot be an effective enumeration of all computable total functions (because we could diagonalize against it). Any reasonable machine model would give us an effective enumeration, QED. You either need to sacrifice being able to tell whether or not something is a machine in your model, or you need to sacrifice being able to run your machines. Neither are satisfactory.

You might be happy working with the class of primitive recursive functions. There's quite a bit in there, they are all total computable, and you can effectively enumerate them. If you have some specific total computable functions you need in addition (eg the Ackerman function), you can take a finite set of special total computable functions and close it under primitive recursion, and work with that.

---
Tags: turing-machines, computability, automata, halting-problem, chomsky-hierarchy
---


# Question
Title: Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time
I'm struggling with the following question:

> Let $\langle a\_0, a\_1,\dots,a\_n\rangle$ be a sequence of real numbers, and let $ M = \max\\{a\_0, a\_1, .... a\_n\\} $ and $ m = \min\\{a\_0, a\_1, .... a\_n\\} $.
>
> a. Prove that there are two numbers in the sequence $x,y$ such that $ |x-y| \leq \frac{M-m}n$.
>
> b. Write an algorithm that finds those numbers in linear time.

I've manage to prove part a, but am struggling with part b. I've tried to find a way to find the two element in the array that have the smallest difference, but couldn't find a way to do it in $\Theta(n)$. It should be something related to select algorithm and medians.

# Answer
This is an interesting question.

---

**Here is a linear-time algorithm**. Assum $n\ge1$.

1. Compute the minimum $m$ and the maximum $M$. If $m=M$, return $a\_0$ and $a\_1$. Otherwise, let $\delta=\frac{M-m}n$.
2. For $i$ from $0$ to $n$, let $\text{slot}\_i$ be an empty list of numbers.
3. For $i$ from $0$ to $n$, append $a\_i$ to $\text{slot}\_{\lfloor (a\_i-m)/\delta\rfloor}$.
4. For $i$ from $0$ to $n$, check whether there are at least two numbers in $\text{slot}\_i$. If yes, return any two numbers in $\text{slot}\_i$.
5. Otherwise, each $\text{slot}$ contains one number. For $i$ from $1$ to $n$, check whether $b\_{i}-b\_{i-1}\le \delta$, where $b\_{j}$ is the only number in $\text{slot}\_j$. If yes, return $b\_{i-1}$ and $b\_{i}$.

It is easy to see the algorithm is correct with time-complexity $\Theta(n)$.

---

It might be interesting **how I found my initial algorithm**.

I literally recited George Pólya's principle, "do you know a similar problem?". I recalled that finding duplicate elements in an array using hash table takes linear time of $n$. Could I apply that conclusion? Or the way of using hash table? What is a hash table and how can I create a hash here? If I can put nearby numbers in the same slot, I can considered them as the same, then the algorithm might work. The it dawned on me that I could use the location of $a\_j$ as "its hash". However, two numbers that are very close could be mapped to different hashes, which breaks the promise. If one hash is not enough, how about two hashes? I could almost see the light on the other side of the tunnel. After a few minor adjustments, I arrived at my initial algorithm.

(Somehow I missed Yuval's nice algorithm by divide and conquer, which, in hindsight, should not have been difficult to find.)
> 6 votes

# Answer
Let $z$ be the median of $A$, and split $A$ into two subarrays $B,C$: the array $B$ consists of all numbers at most $z$ (including $z$), and the array $C$ consists of all number at least $z$ (including $z$). Assuming for simplicity that $n$ is even and that all elements in $A$ are distinct, we can write $$ B = b\_0,\ldots,b\_{n/2}, \\ C = c\_0,\ldots,c\_{n/2}, $$ where $b\_{n/2} = c\_0 = z$. Define $\delta(X) = \frac{\max(X) - \min(X)}{\mathrm{len}(X)-1}$. Then $$ \delta(B) + \delta(C) = \frac{z-\min(A)}{n/2} + \frac{\max(A)-z}{n/2} = \frac{\max(A)-\min(A)}{n/2} = 2\delta(A), $$ and so $\min(\delta(B),\delta(C)) \leq \delta(A)$. This implies that we can recurse on either $B$ or $C$.

Using a linear time algorithm for finding the median, we obtain an algorithm whose running time satisfies the recurrence $T(n) = T(n/2) + \Theta(n)$, whose solution is $T(n) = \Theta(n)$. Details left to you.

Let me comment that $\min(\delta(B),\delta(C)) \leq \delta(A)$ whatever the sizes of $B,C$ are (this requires a simple adaptation of the above proof). This suggest a randomized algorithm running in expected linear time, which simply chooses $z$ at random. This is possibly more efficient in practice.
> 5 votes

# Answer
Find the minimum m and M; m = M is trivial.

For each i, let yi = (xi - m) * n / (M - m), so 0 \<= yi \<= n. Start with an empty table with entries 0 to n, then for each i record i and yi at entry floor(yi). When you find i and j using the same entry, then xi and xj are close enough together. If you don't find i and j, then all values floor(yi) are unique. Now you just look for table entries that are at most 1 apart, and the corresponding xi, xj are close enough together.

You might improve the average runtime if you check the previous and next slot when you add yi to the table. If the xi are random and linear distributed, then according to the birthday paradox you should find a close pair of numbers after about sqrt(n) operations. Asymptotic runtime won't go down, because finding minimum and maximum of xi, and clearing the table entries will take linear time already.
> 2 votes

---
Tags: algorithms, time-complexity, selection-problem
---


title: LALR(1) grammar for simple math parser

text:
# Question
Title: LALR(1) grammar for simple math parser
I am trying to write a simple parser for a small calculator project, that should be able to parse e.g. the following inputs:

```
5 + 3
5 + f(4)
5 + f(x)
x = 5
f(x) = 3*x

```

so basically, I want to be able to parse expressions (that may contain variables and function calls), variable assignments, and function definitions using the = operator.

The problem is that in function definitions, only identifiers must be allowed in the definition, e.g.

```
f(5+1) = 3*x

```

should not be legal in the grammar. Thus, I need to define two distinct cases for functions, where the first (`bFunc`, containing only ids) could occur on both sides of =, and the second (`func`, can also contain expressions) must not occur on the left side.

This is the grammar so far:

```
stmt -> expr.
stmt -> fdef.
stmt -> vdef.

fdef -> bFunc = expr.
vdef -> id = expr.

bFunc -> id ( idList ).

func -> id ( list ).
func -> id ( ).

list -> expr.
list -> list , expr.

idList -> id.
idList -> idList , id.

expr -> term.
expr -> expr + term.
expr -> expr - term.

term -> atom.
term -> term / atom.
term -> term * atom.

atom -> id.
atom -> num.
atom -> func.
atom -> ( expr ).

```

However, I was not able to figure out how to specify a valid LALR(1) grammar because of this problem. The tool http://mdaines.github.io/grammophone/#/ reports reduce-reduce conflicts. The problem is that the parser would not know whether id should be reduced to `idList` or `atom`.

Surely it would be possible to simply use `func` in both cases and catch invalid left sides later in the program. But my question is now, is it even possible to write a LALR(1) grammar for this problem? How does one decide whether it is possible or not? And may my problem be the reason why programming languages use keywords like `def` or `function` for function definitions?

# Answer
> 3 votes
As modified by your edit, your grammar is unambiguous. Unfortunately, it is not deterministic; no limited lookahead is sufficient to decide whether when the parser reaches a comma: $$\bf{ID}\\;\bf{(}\\;\bf{ID}\\;\bullet\\;\bf{,}\\;\cdots$$ it should predict $\it{bFunc}$ by reducing $\bf{ID}$ to $\it{idList}$ or predict $\it{func}$ by reducing it to $\it{atom}$ (and thus eventually to $\it{expr}$ and $\it{list}$).

One reasonably straightforward solution is to differentiate between $\it{expr}$ and $\bf{ID}$ by creating the non-terminal $\it{expr\_{!ID}}$ which matches $\tt{expr}\setminus\\{\bf{ID}\\}$ and using it in $\it{list}$. (Note that $\it{list}$ is not a simple list of $\it{expr\_{!ID}}$; rather, it is a list in which at least one element is a $\it{expr\_{!ID}}$. See below for sample grammar).

That makes $\it{list}$ and $\it{idList}$ disjoint and the grammar is deterministic. However, the distinction is not strictly related to the semantics of the language. It creates a curious hybrid parse tree node in which some of the nodes in the argument list's parse subtree are $\it{idList}$ and the rest are $\it{list}$. (Look at the parse tree for `f(a,b,c,d+3)`, for example). Indeed, a complete function call might be parsed as a $\it{bFunc}$, which will need to be converted to $\it{bFunc}$ when it turns out that it is not followed by an $\bf{=}$.

A practical parser will need to repair the parse tree for $\it{func}$ by converting the $\it{idList}$ nodes to $\it{list}$. That could be done in a reduction action, or it could be done in a post-parse tree walk, but it will almost certainly need to be done, since the semantic distinction is real: the use of an $\bf{ID}$ in a parameter list is a *binding*, while the use of the same $\bf{ID}$ in a function call is a *use*.

So at the high level, what we end up with is: $$\begin{align} \tt{bFunc}&\to\\;ID\\;\tt{(}\\;\tt{idList}\\;\tt{)}\\ \tt{func}&\to\\;ID\\;\tt{(}\\;\tt{list}\\;\tt{)}\\ \tt{func}&\to\\;ID\\;\tt{(}\\;\tt{)}\\ \tt{func}&\to\\;ID\\;\tt{(}\\;\tt{idList}\\;\tt{)}\\ \\ \tt{list}&\to\\;\tt{expr\_{!ID}}\\ \tt{list}&\to\\;\tt{list}\\;,\\;\tt{expr}\\ \tt{list}&\to\\;\tt{idList}\\;,\\;\tt{expr\_{!ID}}\\ \\ \tt{idList}&\to\\;\tt{ID}\\ \tt{idList}&\to\\;\tt{idList}\\;,\\;\tt{ID}\\ \end{align}$$

We also need to define the non-terminal $\it{expr\_{!ID}}$ which doesn't match $\bf{ID}$ (and its pars at the other chained precedence levels). The straightforward solution is to remove the production $\text{atom}\\;\to\\;ID$, thus removing the token $\bf{ID}$ from the direct unit-production chain. Then we add it back in the non-terminals in which it is permitted (i.e. the ones which are not restricted to $\it{!ID}$). So the expression grammar now looks like this: $$\begin{align} \tt{expr}&\to\\;\tt{expr\_{!ID}}\\ \tt{expr}&\to\\;\tt{ID}\\ \tt{term}&\to\\;\tt{term\_{!ID}}\\ \tt{term}&\to\\;\tt{ID}\\ \tt{atom}&\to\\;\tt{atom\_{!ID}}\\ \tt{atom}&\to\\;\tt{ID}\\ \\ \tt{expr\_{!ID}}&\to\\;\tt{expr}\\;\bf{+}\\;\tt{term}\\ \tt{expr\_{!ID}}&\to\\;\tt{expr}\\;\bf{-}\\;\tt{term}\\ \tt{expr\_{!ID}}&\to\\;\tt{term\_{!ID}}\\ \\ \tt{term\_{!ID}}&\to\\;\tt{term}\\;\bf{/}\\;\tt{atom}\\ \tt{term\_{!ID}}&\to\\;\tt{term}\\;\bf{\*}\\;\tt{atom}\\ \tt{term\_{!ID}}&\to\\;\tt{atom\_{!ID}}\\ \\ \tt{atom\_{!ID}}&\to\\;\tt{NUM}\\ \tt{atom\_{!ID}}&\to\\;\tt{func}\\ \tt{atom\_{!ID}}&\to\\;\bf{(}\\;\tt{expr}\\;\bf{)}\\ \end{align}$$

which is only a little longer than the equivalent lines in your original.

It's interesting to note that the syntax formalism used by ECMAScript (and some other semi-related technologies) uses a macro-enhanced form of BNF in which non-terminals can be given boolean parameters, like the $\tt{!ID}$ subscript I used above. With that feature, the grammar could be written even more compactly (although the macro expansion would be a bit bigger).

As another interesting note, your grammar will work perfectly without the definition of $\it{expr\_{!ID}}$ if processed with Bison or almost any other Yacc-derivative parser generator. (You do need to add the extra productions in the list definitions to convert $\it{idList}$ to $\it{list}$, as indicated above.) The parser generator will signal four reduce-reduce conflicts, since there is an ambiguity. But as long as the list productions come before the expression productions, Yacc/Bison's automatic conflict resolution mechanism will produce the correct resolution. That's probably not the optimal solution, but it is certainly the shortest.

# Answer
> 2 votes
The problem occurs with the parsing prefixes having the form `f(id, id, ...`, so that your grammar cannot determine by any means what do they denote: either the function definition or an expression starting with the function call.

Thinking in terms of PDAs, it is natural to parse such prefixes uniformly until the parse path is revealed. The parse path is always revealed deterministically: if the prefix ends with `) =`, then you parse a definition, otherwise you parse an expression. I have used some simplified form of your grammar to check out the idea, and it seems that there are no SLR(1)-conflicts in the resulting grammar. But yeah, the complete grammar can be *quite* longer, and maybe some good grammar transforming techs (such as introducing new nonterminals for the suffixes of the expressions) would be on hand.

The core idea is introducing `fstrange` nonterminal with the meaning *"for now, we do not know what is it, but keep the both possibilities in mind"*.

```
stmt -> num + expr.
stmt -> num.
stmt -> id.
stmt -> id + expr.
stmt -> id ( fstrange.
stmt -> id = expr.

fstrange -> id , fstrange.
fstrange -> id ) = expr.
fstrange -> id ).
fstrange -> num ).
fstrange -> func ).
fstrange -> num ) + expr.
fstrange -> func ) + expr.
fstrange -> + expr ) + expr.
fstrange -> + expr ).
fstrange -> id ) + expr.
fstrange -> + expr , list ).
fstrange -> num , list ).
fstrange -> func , list ).
fstrange -> + expr , list ) + expr.
fstrange -> num , list ) + expr.
fstrange -> func , list ) + expr.

func -> id ( list ).
func -> id ( ).

list -> expr.
list -> list , expr.

expr -> atom.
expr -> expr + atom.

atom -> id.
atom -> num.
atom -> func.

```

Regarding your second question: your language seems to be deterministic, so it is always possible to construct an SLR(1)-grammar for it (since SLR(1)=LR(k) in terms of the languages, not grammars!). The matter is the grammar size. I do not claim that the example for the simplified grammar given above is perfect, but still you can notice it is much less natural and less intuitive than the one given by you.

---
Tags: regular-languages, formal-grammars, parsers
---


title: how 16 bits address lines address 64KB?

text:
# Question
Title: how 16 bits address lines address 64KB?
" The 8080 was an 8-bit CPU, meaning it processed 8 bits of information at a time. However, it had 16 address lines coming out of it. The ‘‘bitness’’ of a CPU—how many bits wide its general-purpose registers are—is important, but to my view the far more important measure of a CPU’s effectiveness is how many address lines it can muster in one operation. In 1974, 16 address lines was aggressive, because memory was extremely expensive, and most machines had 4K or 8K bytes (remember, that means 4,000 or 8,000) at most—and some had a lot less. Sixteen address lines will address 64K bytes. If you count in binary (which computers always do) and limit yourself to 16 binary columns, you can count from 0 to 65,535. (The colloquial ‘‘64K’’ is shorthand for the number 66,536.) This means that every one of 65,536 separate memory locations can have its own unique address, from 0 up to 65,535."

my questions are how 16 bits address lines can address 64KB?,since 16 bits can only address 64kbps.

and what is segment?

thanks in advance

# Answer
> 5 votes
One address addresses one byte. Using 16 bits, you can write 65536 addresses (from 0 to 65535, that's 65536 different addresses), and address 65536 bytes. 65536 bytes is 64kB. In computer science, b is bit, B is byte. The byte is the smallest amount of memory you can address. The question "what is k ?". k is kilo, in international system of units, a kilo unit is 1000 units, but, when dealing with memory, a kilo unit is 2^10=1024 units, (except when dealing with hard drives, for marketing reasons).

64kbps is 64 kilo bits per second. It is a transfer rate, not an amount of memory.

"What is a segment ?" isn't a precise question, segment is a very generic word used in many contexts. I expect that the 8086 segments are accurate in your context, even if it's some 24-bit addresses with 16-bit CPU instead of 16-bit addresses with 8-bit CPU.

# Answer
> 1 votes
One address addresses one **something**. So 16 bits of address can address $2^{16}$ **something**s.

In the case of memory organised in bytes, this is 64KB (kilobytes). If memory were organised in bits, this would be 64Kb (kilobits). If memory is organised in 16-bit or 20-bit or 32-bit words (as has sometimes been done), the addressable space would be 64K of those words. (You get more memory that way, but you lose the byte-addressability: in some cases, a reasonable tradeoff).

# Answer
> 1 votes
Here, 65,536 address locations are provided for a data word, but each data word consists of 8 bits or 1 byte so effectively 65,536bytes sums to 2^16 bytes = 2^6 * 2^10 bytes = 64KB

# Answer
> 1 votes
The quote appears from "Assembly Language Step By Step" by Jeff Duntrmann, 3rd ed. Earlier (in the section on Random Access), the book describes voltages on the pins of the processor. There is a high value (e.g 5V) and a low (e.g. 0V) value. These correspond to 1 and 0, digitally. Since there are two possible values for each pin and an 8080 processor has 16 pins, 2^16 = 65536 different combinations exist. Each combination corresponds to a memory address.

You might also be wondering, "Why \`\`64K’’ is shorthand for the number 66,536?" That's a great question. The answer: it's not! That was a typo in the book!

> **Errata for the Third Edition**
>
> P. 79, fifth paragraph: 66536 should be \>65536. (Spotter thanks to Jim Whiting.)
>
> http://duntemann.com/assembly.html

Check Duntemann's webpage (or the publisher's) for more errata and other helpful information.

As for why is 64k used for 65,536? It's because 64 x 1024 = 65536. However, people were imprecise with their usage of "kilo", the metric unit for one-thousand. They used kilo in a computer context to mean 1024 instead of 1000. (n.b. Later, language of 'kibbi', as in 'kibbibyte', was introduced to distinuish between base 2 (i.e. 1024) and base 10 (i.e. 1000).)

Read on a few sections in the book for an explanation of segments. :)

---
Tags: computer-architecture
---


# Question
Title: What could be possible NFA for the RegEx "a?"
I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$

I am wondering if I should deconstruct the RegEx as -

1. Concatenation of $a+$, $(b|c?)$ together with $c$ OR
2. Union of $a$ and $(b|c?)$ concatenated with $c$

In either case, I would the need the atomic NFA construction for the $c?$. I am unable to figure it out.

Please help.

# Answer
I would assume that $+$ and $|$ do not both mean union, so the regex is actually (assuming POSIX syntax) $$a^+ (b + c + \varepsilon) c \equiv aa^\ast (b + c + \varepsilon) c.$$ You should be able to figure out the NFA if you know the Thompson construction.
> 0 votes

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


# Question
Title: $k$-Opt TSP Local Search is NOT exact when $k = \lceil |V|/2 \rceil$
I've been self-studying the book *Algorithms* by Papadimitriou, Dasgupta and Vazirani. I am having a hard time with a question about local search involving the traveling salesman problem (TSP).

We'll say a local search algorithm is *exact* if it always returns a globally optimal solution.

Consider a local search algorithm for TSP that uses neighborhoods defined by $k$-change: two tours $T\_0$ and $T\_1$ are neighbors if one can delete $j \leqslant k$ edges from $T\_0$ and add back another $j$ edges to obtain $T\_1$. This is known as the $k$-Opt algorithm.

It's easy to see and the book itself discusses how for low values of $k$ (relative to the number $n$ of vertices), $k$-Opt may get stuck on locally optimal solutions that are not globally optimal. In other words, $k$-Opt is **not** exact for these values of $k$.

The exercise I'm interested in claims that

> $k$-Opt with $k = \lceil n/2 \rceil$ is **not** exact.

I've tried my hand and searched around but couldn't make it.

I found the paper "Some Examples of Difficult Traveling Salesman Problems", available here (and Papadimitriou is one of the authors by the way). It contains a family of examples for which $k$-Opt with $k \< (3n/8)$ is not exact, and uses a particular kind of subgraph (which it calls the diamond) to impose a structure on feasible tours.

I've tried to replicate and extend something like this with little success.

# Answer
> 3 votes
**Answer to the first question:**

Please see the following figure for $n = 8$. All the red and black edges have weight $1$. The green edge $(C,H)$ has weight $2$. And, the blue edges have weight $0$. The edges that are not there have weight $\infty$; I have not drawn these edges for simplicity.

Now, note that the cycle $(A,B,C,D,E,F,G,H)$ is the optimal tour with weight $5$. Also, the tour formed by the colored edges (red, green, and blue) has weight $6$. Note that the tour formed by these colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

*Why colored tour is locally optimal?*

**Proof:** For the sake of contradiction assume that it is not locally optimal. It means that there exist at most four edges in the tour that can be replaced to obtain a smaller weight tour. Observe that to obtain a smaller weight tour, the edge $(C,H)$ must be replaced and the blue edges can not to be replaced. If we replace edge $(C,H)$, then we must add the edges $(C,B)$ and $(A,H)$; otherwise, the weight of the tour will become $\infty$.

After adding these edges, we can not keep edges $(B,D)$ and $(A,G)$ in the tour. Therefore, we must add edges $(D,E)$ and $(G,F)$; otherwise, the weight of the tour will become $\infty$. Now, we must remove edges $(B,E)$ and $(A,F)$.

To complete the tour, we need to add edge $(A,B)$; however, we can not add any more edges since we have already added $4 = n/2$ new edges. Therefore, a tour can only be formed by adding edges $(B,F)$ and $(E,A)$. It makes the weight of the tour $\infty$.

This proves that the tour formed by colored edges is locally optimal.

---

The technique can be easily generalized to the general value of $n$. For example, see the following figure for $n = 14$. Here, again, the tour formed by the colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

---
Tags: algorithms, graphs, traveling-salesman, hamiltonian-circuit
---


# Question
Title: preprocessing or real time for magnification of portions of video
Im new at CS and would like to gather preliminary information to approach an interactive art project.

I want to construct a grid of videos - think about a matrix *M = m x n* where *Mi,j* is a video that cover a certain portion of the screen.

I want to interact with the screen, so that if I trigger a certain action, the video *Mi,j* got magnified.

Magnification of the video could result in any of:

* the magnified video get superimposed on the neighbors (e.g. *M(i+1,j+1)*, etc. )
* the neighbors are shifted to make space for the magnified video

In order to make the grid, I could make use of FFMPEG, but preprocessing the grid as one single video, could make the second option very cumbersome.

I'd like to know:

* would it possible to align a matrix of videos, without merging them in one object ? If so, how to estimate memory issues and limits ?
* which kind of framework would you suggest to learn for this project:
* processing (e.g. tutorials https://timrodenbroeker.de/new-course-copy-and-paste/), pixi.js, openFrameworks, puredata, others ?)

--

settings / requirements

The project aims to be an art installation, made with a computer and a projector. The user can interact in a room and trigger selection of the *i,j* via an arduino, the projector will project the grid on a wall. The videos composing the grids could be pre-processed before; I'd like, indeed, to learn how to estimate the limit for applying effects in real time to a *i,j* videos and to align *m x n* videos in a big canvas, and software to look at for designing a prototype of architecture.

Computing skills: Python, some javascript, absolute begineer in C++

# Answer
> 1 votes
Not knowing your specific usage, I'd use Isadora or TouchDesign for these kind of task. They can help you manipulate realtime feeds based on the events

---
Tags: computer-architecture, image-processing, real-time
---


# Question
Title: Labeling an image mask as data for object detection?
I am new to machine learning but had a question about a labeling method. If I had the following two images:

Is there a way to use the second image as the label for the first one (i.e. anything in white is the object I want to detect)? As I understand it, labels are typically defined by vector points, but in my case, a sort of a raster clipping mask like shown above is much easier for me to generate, as I may have varying shapes of varying complexity. Is there software that can take in an image as the label in this sort of way, or is there no other choice than to turn the raster image into a vector?

If there are any generalizations I'm making then please correct me! I'm not sure if there's an existing tool/method for this out there that I'm completely missing, but any help or direction would be appreciated.

# Answer
This task is called image segmentation. I suggest reading up on existing methods for image segmentation, and then try applying their approach to your task. For instance, you might take a look at the DeepLab architecture and train a DeepLab model; there are many others as well. Labels in image segmentation are normally described by a mask, not by vector points.
> 0 votes

---
Tags: machine-learning
---


# Question
Title: Gadget testing puzzle's efficient solution in Levitin's Introduction to algorithm design
I'm going through the problems of the Brute Force chapter from `Introduction to Analysis and Design of Algorithms` by A.Levitin. One problem solution caught my eye, though.

The problem states as follows:

> A firm wants to determine the highest floor of its n-story headquarters from which a gadget can fall without breaking. The firm has two identical gadgets to experiment with. If one of them gets broken, it cannot be repaired, and the experiment will have to be completed with the remaining gadget. Design an algorithm in the best efficiency class you can to solve this problem.

The brute force approach is quite obvious (try every floor until the first gadget breaks). However, I can't come to terms with the efficient one (which I found googling).

* Throw the first gadget every multiple of $\sqrt{N}$
* If the gadget breaks at $i\*\sqrt N $, then the upper bound will be between $(i-1)\*\sqrt{N}$ and $i\*\sqrt{N} -1$
* Details aside, the overall complexity is $O(\sqrt{N})$

My question is how do you come up with $\sqrt N $? Why is it better than say: trying every even or odd floor?

# Answer
Maybe it would be interesting to start with a restriction of the problem where you have only one gadget.

In order to find the highest floor from which you can drop it, you must do you tries from the lowest floor, increasing the floor you drop the gadget from by one each time. If you try something else, the gadget could break before you identify the highest floor, so it is the only viable strategy. It is clear that this strategy is in $\Theta(N)$ in the worst case.

Now let's look at the strategy you propose for two gadget:

> trying every even or odd floor

Since the number of even (or odd) floors is at least $\left\lfloor \frac{N}2\right\rfloor$ this strategy is also in $\Theta(N)$ in the worst case.

To explain the idea of the $\mathcal{O}(\sqrt{N})$ strategy, think of it this way:

* decompose the $N$ floors into (more or less) $\sqrt{N}$ groups of $\sqrt{N}$ consecutive floors ;
* the first gadget is used to find the highest group from which you can drop it, similarly to the one-gadget-strategy (time $\mathcal{O}(\sqrt{N})$) ;
* the second gadget is used to find the highest floor in the previous group from which you can drop it, similarly to the one-gadget-strategy (time $\mathcal{O}(\sqrt{N})$).

The overall time is indeed $\mathcal{O}(\sqrt{N})$.
> 1 votes

---
Tags: algorithms
---