# Question
Title: Reduction from $L_{nonuniversal}$ to $L_{finite}$
As I'm currently preparing for my Algorithms and Complexity exam, I was facing today an other reduction and I'm not quite sure if I solved it correctly.

Given are two languages $L\_{finite}$ and $L\_{nonuniversal}$:

$L\_{finite} = \\{\langle M \rangle \mid \vert L(M) \vert \< \infty \\}$

$L\_{nonuniversal} = \\{\langle M \rangle \mid L(M) \neq \\{0,1\\}^\* \\} $

I'm trying to proof the following reduction: $ L\_{nonuniversal} \le\_T L\_{finite} $

Given $M$ let $M'$ be the Turing Machine that on input $w$ simulates $w$ on $M$. It then takes $w$ after $M$ halted and removes it from its tape and replaces it with a static word $v$ (let this be "1" for example, anything that is $\neq \\{0,1\\}^\*$).

Give $M$ and $M'$ to the $finite$ oracle and return its answer.

I'm trying to show here that if $w$ can only be a static string, then it's $\in finite$.

# Answer
> 3 votes
For brevity, denote $L\_{finite}, L\_{nonuniversal}$, respectively, as $L\_f, L\_n$. To establish a mapping from $L\_n$ to $L\_f$ we map $\langle\\,M\rangle\rightarrow\langle\\,N\\,\rangle$, where $\langle\\,N\\,\rangle$ is defined by

```
N(x) =
   for s = epsilon, 0, 1, 00, 01, 10, 11, 000, 001, ... //i.e., the standard order
      run M on s
      if M(s) = accept and s = x
         return accept

```

Now look at the behavior of this mapping:

* If $\langle\\,M\\,\rangle\in L\_n$ there will be some string in $\\{0,1\\}^\*$ which is not accepted by $M$. Let $z$ be the first such string in standard order. Then $N$ will accept all and only those strings $y$ which are earlier in order than $z$ so $L(N)$ will consist of only those $y$s and so will be finite, i.e., $\langle\\,N\\,\rangle\in L\_f$.
* Similarly, if $\langle\\,M\\,\rangle\notin L\_n$, then $L(M)=\\{0,1\\}^\*$ so $M$ will accept every string and consequently $L(N)=\\{0,1\\}^\*$, an infinite language, so $\langle\\,N\\,\rangle\notin L\_f$.

These two observations establish the reduction we need.

# Answer
> 2 votes
Just got back from the teachers assistants office and he came up with the following solution.

We are looking for a mapping that fulfills the following conditions:

Given $L\_{non-universal}$ and $L\_{finite}$ we want a mapping so that if $\langle M \rangle \in L\_{non-universal}$ then the mappings ($f(\langle M \rangle)$, $f: \Sigma^\* \rightarrow \Sigma^\*$) output $\langle M' \rangle$ should be $\in L\_{finite}$.

This can be shown by the following:

$M'$ checks on input $x$ for all $|w| \le |x|$ if $w \in T(M)$.

Now if it finds a $w$ $\not\in T(M)$ then we can say that $\langle M \rangle\in L\_{non-universal}$ and $T(f(\langle M \rangle)) = \Sigma^{\<|w|} $. In addition we can say if we don't find such a $w$ then $\langle M \rangle \not\in L\_{non-universal}$ and thereby $f(\langle M \rangle) \not\in L\_{finite}$.

I'm looking forward to comments on this.

# Answer
> 1 votes
Another option would be to use the fact, that $L\_{nonuniversal} \leq L\_{finite} \Leftrightarrow L\_{universal} \leq L\_{infinite}$ (i.e. the reducibility of the complement: $A \leq B \Leftrightarrow \overline A \leq \overline B$) and prove it the other way round:

$L\_{universal} \leq L\_{infinite}$

$L\_{universal} = \lbrace \langle M \rangle \in \lbrace 0,1 \rbrace ^\* \vert ~L(M) = \lbrace 0,1 \rbrace ^\* \rbrace$

$L\_{infinite} = \lbrace \langle M \rangle \in \lbrace 0,1 \rbrace ^\* \vert~ \lvert L(M) \rvert = \infty \rbrace$

The mapping function with input $w'$ could look like this:

> $\forall u \in \Sigma^{\leq \lvert w' \rvert}$
>
> $~~$Run $M$ with input $u$.
>
> accept $w'$

In this case $M'$ would run through all the $u$ checking whether they are accepted by $M$. If all those $u$ have been accepted by $M$, the machine $M'$ accepts. In case there is some $u \notin L(M)$ the machine would loop forever and therefor not accept $w'$.

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


# Question
Title: Are there any paradigms that describe how to save program state checkpoints that can be restored later?
I was wondering if there were any paradigms that describe how to save "state checkpoints" in a program so that a user may go back and reopen a program to the given state.

In my situation I see that there are many ways to do it each with their own drawbacks. I wanted to know if there is a way that has proved to have the best performance over most all cases of the problem?

What I think would be the most popular system is one that saves state changes, then when a user wishes to return to a previous state it walks the changes backwards until it reaches a specified time stamp reversing the changes along the way.

Or is this problem just application specific.

# Answer
In general you cannot do this. The state of your application might depend on the state of external systems, and you won't be able to go back. For example you can't go back to a previous saved value of time if your systems requires that your clock should be within a small value compared to other machines in the network.

So its not always possible, and when it is, it is definitely application specific.
> 2 votes

---
Tags: programming-paradigms
---


# Question
Title: Use of Landau notation for determining bounds
Assume that we have $l \leq \frac{u}{v}$ and assume that $u=O(x^2)$ and $v=\Omega(x)$. Can we say that $l=O(x)$?

Thank you.

# Answer
> 1 votes
Since $u = O(x^2)$, there exist $N\_1,C\_1\>0$ such that $u \leq C\_1x^2$ for all $x \geq N\_1$. Since $v = \Omega(x)$, there exist $N\_2,C\_2\>0$ such that $v \geq C\_2x$ for all $x \geq N\_2$. Therefore for all $x \geq \max(N\_1,N\_2)$ we have $$ l \leq \frac{u}{v} \leq \frac{C\_1x^2}{C\_2x} = \frac{C\_1}{C\_2} x. $$ So $l = O(x)$.

---
Tags: time-complexity, landau-notation
---


# Question
Title: Given an analysis of an algorithm, can we get Big-O, Theta, and Omega from this analysis?
If we are given an analysis of an algorithm to be, for example, $5n^3 + 100n^2 + 32n$, can we therefore say that $T(n) = O(n^3)$, and $T(n) = \Theta(n^2)$, and $T(n) = \Omega(n)$, and all of those be correct for that analysis?

I have read the formal definitions for all of these and it does not help me to understand them.

I understand that Big-Oh is an upper bound but how do you know if the algorithm you analyze is an upper bound? I mean, if I analyze an algorithm and I come up with $5n^3 + 100n^2 + 32n$, how do I know to make this Big-Oh?

# Answer
When we write that an algorithm satisfies $T(n) = O(n^3)$ (and this is not standard notation!), we mean that the *running time* of the algorithm, denote $T(n)$, satisfies $T(n) = O(n^3)$; here $n$ is some complexity measure of the input (in your case, the number of elements in the input). In fact, the function $T(n)$ is usually not the running time of the algorithm on inputs of length $n$, simply because the running time often depends on the input. Rather, usually it is taken as the *worst-case* running time of the algorithm on inputs of length $n$.

In your case, you are given something about the algorithm: the polynomial $5n^3+100n^2+32n$. You didn't say what the significance of this function is, but presumable it is the value of $T(n)$, that is, the worst-case running time of the algorithm on inputs of length $n$. In symbols, $$ T(n) = 5n^3 + 100n^2 + 32n. $$ (This guess is based on your question. It conceivably could have been an average-case running time or a space complexity.) In this case, you can say that $T(n) = \Theta(n^3)$, and in particular $T(n) = O(n^3)$ and $T(n) = \Omega(n^3)$. This follows from the definitions of these various terms ($\Theta,O,\Omega$).

In practice, you almost never analyze algorithms quite in this way:

1. Usually you only give an upper bound on the running time of the algorithm on *any* input of length $n$. This gives, in particular, an upper bound on $T(n)$, but doesn't give an upper bound on the average-case or best-case running time of the algorithm.
2. Usually your analysis doesn't result in an exact quantity, only in an upper bound. This is because the computation models are too complicated to analyze exactly. Exact analyses happen only when you're focusing on a different measure of time complexity, such as the number of comparisons in a sorting algorithm.
> 0 votes

# Answer
The key point is that $O(\cdot)$ and friends describe relationships between functions. Functions are purely mathematical objects and it doesn't matter what they're being used to measure. This is similar to the way that $\<$ and friends describe relationships between numbers and it doesn't matter what those numbers are being used to measure.

So, in particular, it doesn't matter if your function is being used to measure the running time of some algorithm. It doesn't even matter if your function is being used to give, say, an upper bound on the running time of an algorithm. If I want to, I can give you an upper bound on a function that's a lower bound for the running time. It's not very *useful* to do that but, because $O(-)$ doesn't care what the function is measuring, it makes perfect mathematical sense. This is a bit like saying, "Jane is less than 1.75m tall and John is taller than her": I've given you an upper bound for Jane's height and Jane's height is, in turn, being used as a lower bound for John's. OK, John could have any height at all, but the mathematics makes sense.

So, all $T(n)=O(f(n))$ says is that the function $g$ is an upper bound for the function $T$, up to constant factors, for large enough inputs. It says nothing at all about any connection between the function $T$ and the real world: it doesn't say that $T$ is an upper bound for this or a lower bound for that.

With all of that out of the way, we can address the technical part of the question, but that really does just follow from the definitions, as I stated in comments.

Tou have a function $5n^3 + 100n^2 + 32n$ and you want to compare it to some other functions: $n$, $n^2$ and $n^3$. Let's call that function $T(n)$. Apparently, the function $T$ is somehow related to the running time of some algorithm but that doesn't matter for what's about to happen.

1. $T(n) = O(n^3)$ because, for $n\>100$, $T(n) \leq 5n^3 + n\cdot n^2 + n^2\cdot n = 7n^3$.
2. $T(n)\neq O(n^2)$ because, for any constant $c$, and any $n\geq c$, $5n^3 + 100n^2 + 32n \> 5n^3 \geq 5cn^2 \> cn^2$. Similarly, $T(n)\neq O(n)$.
3. $T(n) = \Omega(n^3)$ since, for any $n\>0$, $T(n)\> n^3$. Similarly, $T(n) = \Omega(n^2)$ and $T(n) = \Omega(n)$.
4. $T(n) = \Theta(n^3)$ because $T(n) = O(n^3)$ and $T(n) = \Omega(n^3)$. $T(n)\neq \Theta(n^2)$ because $T(n)\neq O(n^2)$ and $T(n)\neq \Theta(n)$ because $T(n)\neq O(n)$.
> 6 votes

---
Tags: algorithm-analysis, landau-notation
---


title: Greedy algorithm proof

text:
# Question
Title: Greedy algorithm proof
There are `2n` product and their prices: `P={p_1, p_2, ..., p_2n}`. When we buy the products in pairs we get the product with lower price for free.

I'm trying to prove formally that the following algorithm results in optimal solution:

1. Sort P from high to low.
2. Return the sorted prices as pairs.

This solution is pretty straightforward, however I'm having extremely difficult time proving it formally.

# Answer
> 3 votes
Let's assume that optimal answer is $A = \\{(free\_1, paid\_1), ..., (free\_n, paid\_n)\\}$ where $\forall i: free\_i \le paid\_i$, also sort this pairs by $paid$, i.e. $paid\_1 \le paid\_2 \le ... \le paid\_n$.

*I will use pairs to show products grouping - 1st product in pair I get for free, and for 2nd I need to pay.*

If there is such $i$ that $paid\_{i-1} \> free\_i$, take 2 pairs $(free\_{i-1}, paid\_{i-1}), (free\_i, paid\_i)$ (in this case we need to pay $paid\_{i-1} + paid\_{i}$) and swap prices:

1. In case $free\_{i-1} \le free\_i$ we got $(free\_{i-1}, free\_i), (paid\_{i-1}, paid\_i)$ (need to pay $free\_i + paid\_i$);
2. In case $free\_{i-1} \> free\_i$ we got $(free\_{i}, free\_{i-1}), (paid\_{i-1}, paid\_i)$ (need to pay $free\_{i-1} + paid\_i$).

In both cases we don't do solution worse (we can not improve solution because we suppose that $A$ is optimal, but there is case that after swapping solution will not changed, e.g. $free\_i \< free\_{i-1} = paid\_{i-1} \< paid\_i$).

We have:

1. $paid\_1 \le paid\_2 \le ... \le paid\_n$, that gives sorted sequence: $\\{paid\_1, paid\_2, ..., paid\_n\\}$
2. $\forall i: paid\_{i-1} \le free\_i \le paid\_i$ (*more intuition: in sequence from p.1 we insert $free\_i$ on appropriate places*), that gives sorted sequence: $\\{free\_1, paid\_1, free\_2, paid\_2, ..., free\_n, paid\_n\\}$

So we show that optimal answer can be expressed in form of sorted array.

---
Tags: greedy-algorithms
---


title: What is a "geometric rectangle"?

text:
# Question
Title: What is a "geometric rectangle"?
In the \[Kushilevitz and Nisan 2006, P.10\] they give an exercise which says as following:

> **Exercise 1.18:** Let $X=Y=\\{1,\ldots,n\\}$. A geometric rectangle is a set of the form $\\{(x,y)|x\_{\min} \leq x \leq x\_{\max}, y\_{\min} \leq y \leq y\_{\max}\\}$, for some values $x\_{\min},x\_{\max},y\_{\min}$, and $y\_{\max}$ in $\\{1,\ldots,n\\}$. A *comparison protocol* is a one in which at each node $v$, if Alice needs to transmit a bit then this bit is the result of comparing her input $x$ with some value $\theta\_v$ (that is, $a\_v(x)$ is $0$ if $x \< \theta\_v$ and $1$ if $x \geq \theta\_v$). Similarly, at each node $v$ where Bob speaks he sends the result of comparing his input $y$ with some value $\theta\_v$. Prove that every comparison protocol for computing a function $f$ partitions the space $X\times Y$ into $f$-monochromatic geometric rectangles.

My simple question is "What is geometric rectangle" in order to understand the exercise?

Assume that we have 2 bits, then we have four possible ways to represent 2 bits on X and on Y, so total is $ 4 \times 4 = 16$ cells on the matrix. When I try to follow what the definition of "geometric rectangle", I found that all matrix have 1 entry; because it achieves the definition of a "geometric rectangle"; it didn't sounds "reasonable" because there is a comparison between the inputs, so there must be a {0} and {1} entry on the matrix.

I tried to look up for another definition of a "geometric rectangle", it turns out that "geometric rectangle" is "the Euclidean geometric rectangle", I don't understand what is the relation between "Euclidean geometric rectangle" and "combintorial rectangle" on communication complexity, does "geometric rectangle" refer to "Euclidean geometric rectangle" or there is misunderstanding here?

Any hence or reference would be very helpful, Thank You!

# Answer
> 3 votes
*Geometric rectangle* is not a standard term. That's why they define it in the question.

In communication complexity, Alice has an input from the set $X$, and Bob has an input from the set $Y$. Usually we assume that the sets $X,Y$ are unstructured. A *combinatorial rectangle* is a subset of $X \times Y$ of the form $A \times B$, where $A \subseteq X$ and $B \subseteq Y$.

In this question, the sets $X,Y$ are ordered, and the authors defined a *geometric rectangle* to be a subset of $X \times Y$ of the form $A \times B$ where $A$ is a *subinterval* of $X$ and $B$ is a *subinterval* of $Y$. That is, $A = \\{ x \in X : x\_1 \leq x \leq x\_2 \\}$ for some $x\_1,x\_2 \in X$, and $B = \\{ y \in Y : y\_1 \leq y \leq y\_2 \\}$ for some $y\_1,y\_2 \in Y$.

---
Tags: communication-complexity
---


title: Algorithm Design Manual Question

text:
# Question
Title: Algorithm Design Manual Question
In the book, Algorithm Design Manual by Steven S. Skiena, he states "Becoming familiar with many different algorithmic graph problems is more important than understanding the details of particular graph algorithms." Unfortunately, I don't quite understand this phrase, as this is my first experience with Algorithm Designs. Can anyone explain the difference between the two above statements and use a real-world example where this would be true?

# Answer
The author suggests that you become aware of the kinds of problems that graph algorithms can solve, rather than on the details of these algorithms. To give an example from a different field, it is much more useful to know that linear programs can be solved than to understand how the simplex algorithm works. Another example closer to the subject matter is maximum flow – again, it is more important to be familiar with the problem than with any algorithm for solving it.

You can always look up the algorithm that solves a particular problem – and if you're lucky, perhaps somebody already implemented it in some library. But you have first to know *which* known problems to reduce your own problem to.
> 3 votes

---
Tags: algorithms, algorithm-analysis, graphs
---


# Question
Title: Good snapshottable data structure for an in-memory index
I'm designing an in-memory object database for a very specific use case. It is single writer, but must support efficient concurrent reads. Reads must be isolated. There is no query language, the database only supports:

* get object/-s by attribute/set of attributes (there may be support for expressions, e.g. `x.count < 5`)
* get object's attribute

A query is an imperative script composed of an arbitrary number of the above operations. The data size will be \<\< memory, so all the object and indices on most of the attributes should fit comfortably without swapping.

What I need is a data structure for the object's attribute index, which can be O(n) on writes, not support write concurrency, but should support ideally O(1) snapshots (maybe copy on write) and O(logN) access. Ideally it would allow high concurrency on reads with maximal structural sharing between the versions.

I was looking at CTries, Concurrent BSTs and Concurrent Splay Trees but I'm not sure if I'm really looking in the right direction here. The above structures pay a lot of attention to the complexity of inserts which I don't care about.

**The question**: is there a known data structure that is a good fit for my use case out of the box?

**EDIT**: after thinking some more it seems that a persistent BST/Splay tree would work. The writer would update the 'master' copy and the queries would get the tree as of the start of execution and throw it away after they are done. However, I'm still interested if there's a better solution.

# Answer
Use any kind of persistent/immutable (i.e., functional) tree-based data structure. The key is getting the locking right, as @Raphael pointed out in the comments.

The nice thing about functional/persistent tree-based data structures, is that you get "snapshots" for free. Let's suppose you use a *treap* (randomized binary search tree) for your data structure. Here's an example of one written in Go: https://github.com/steveyen/gtreap. The author describes it thusly:

> By immutable, any updates/deletes to a treap will return a new treap which can share internal nodes with the previous treap. All nodes in this implementation are read-only after their creation. This allows concurrent readers to operate safely with concurrent writers as modifications only create new data structures and never modify existing data structures. This is a simple approach to achieving MVCC or multi-version concurrency control.

At any point in time the "current" state of the tree is represented by a pointer to the root of the tree. Insertions are non-mutating. Instead an insertion keeps the previous version of the tree completely intact, creates $O(\log n)$ new nodes for the path from the root to the correct insertion point, with pointers back to the nodes of the previous version that can be shared.

You use a lock to protect the pointer to the root. Since the data structure is immutable reads can be done concurrently, and you can save pointers to old snapshots. A read is:

```
lock
tmp = ptr_to_root
unlock
value = search(tmp, <value to search for>)
return value

```

Even though the search may take a while, you only hold the lock while copying the pointer, so the searches can happen concurrently.

A write is:

```
lock
old_ptr_to_root = ptr_to_root
ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
unlock

```

In this version, writes do need to hold the lock during the entire process of creating the new version of the tree. You can improve read performance (at the cost of sometimes having the write transaction fail) by changing the write to something like this:

```
top:
  lock
  old_ptr_to_root = ptr_to_root
  unlock
  new_ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
  lock
  if (ptr_to_root == old_ptr_to_root)   # make sure no other write happened in the interim
    ptr_to_root = new_ptr_to_root
    unlock
  else                                  # transaction fails, try again
    unlock
    goto top

```

You may be able to do even slightly better (make it "lock free") if your programming language has atomic variables with an atomic compare-and-swap operation. (For example by using C++11's `atomic<T*>`.)
> 5 votes

# Answer
Microsoft has published details on their new in memory database, it has indexes that do not block reads while writes are being done.

For example:

> Justin Levandoski, David Lomet, and Sudipta Sengupta, The Bw-Tree: A B-tree for New Hardware, in 2013 IEEE 29th International Conference on Data Engineering (ICDE), International Conference on Data Engineering, 8 April 2013.

See http://research.microsoft.com/en-us/projects/main-memory\_dbs/ for a list of their publications.
> 1 votes

---
Tags: data-structures, concurrency, databases
---


# Question
Title: How to verify number with Bob without Eve knowing?
You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

*Note:* This question is on a list of "google interview questions". As a result, there are tons of versions of this question on the web, and many of them don't have clear, or even correct answers.

*Note 2:* The snarky answer to this question is that Bob should write "call me". Yes, that's very clever, 'outside the box' and everything, but doesn't use any techniques that field of CS where we call our hero "Bob" and his eavesdropping adversary "Eve".

**Update:**
Bonus points for an algorithm that you and Bob could both reasonably complete by hand.

**Update 2:**
Note that Bob doesn't have to send you any arbitrary message, but only confirm that he has your correct phone number without Eve being able to decode it, which may or may not lead to simpler solutions.

# Answer
First we must assume that Eve is only passive. By this, I mean that she truthfully sends the card to Bob, and whatever she brings back to Alice is indeed Bob's response. If Eve can alter the data in either or both directions (and her action remains undetected) then anything goes.

(To honour long-standing traditions, the two honest parties involved in the conversation are called Alice and Bob. In your text, you said "you". My real name is not "Alice", but I will respond just as if you wrote that *Alice* wants to verify Bob's phone number.)

The simple (but weak) answer is to use a hash function. Alice writes on the card: "return to me the SHA-256 hash of your phone number". SHA-256 is a cryptographic hash function which is believed to be secure, as far as hash functions go. Computing it by hand would be tedious but still doable (that's about 2500 32-bit operations, where each operation is an addition, a word shift or rotate, or a bitwise combination of bits; Bob should be able to do it in a day or so).

Now what's weak about that ? SHA-256, being a cryptographic hash function, is resistant to "preimages": this means that given a hash output, it is very hard to recover a corresponding input (that's the problem that Eve faces). However, "very hard" means "the easiest method is brute force: trying possible inputs until a match is found". Trouble is that brute force is easy here: there are not so many possible phone numbers (in North America, that's 10 digits, i.e. a mere 10 billions). Bob wants to do things by hand, but we cannot assume that Eve is so limited. A basic PC can try a few millions SHA-256 hashes *per second* so Eve will be done in less than one hour (less than 5 minutes if she uses a GPU).

This is a generic issue: if Bob is deterministic (i.e. for a given message from Alice, he would always return the same response), Eve can simulate him. Namely, Eve knows everything about Bob except the phone number, so she virtually runs 10 billions of Bobs, who differ only by their assumed phone number; and she waits for one of the virtual Bobs to return whatever the real Bob actually returned. The flaw affects many kinds of "smart" solutions involving random nonces and symmetric encryption and whatsnot. It is a strong flaw, and its root lies in the huge difference in computing power between Eve and Bob (now, if Bob *also* had a computer as big as Eve's, then he could use a *slow* hash function through the use of many iterations; that's more or less what password hashing is about, with the phone number in lieu of the password; see bcrypt and also this answer).

Hence, a non-weak solution *must* involve some randomness on Bob's part: Bob must flip a coin or throw dice repeatedly, and inject the values in his computations. Moreover, Eve must not be able to unravel what Bob did, but Alice must be able to, so some information is *confidentialy conveyed* from Bob to Alice. This is called asymmetric encryption or, at least, asymmetric key agreement. The simplest algorithm of that class to compute, but still reasonably secure, is then RSA with the PKCS#1 v1.5 padding. RSA can use $e = 3$ as public exponent. So the protocol goes thus:

* Alice generates a big integer $n = pq$ where $p$ and $q$ are similarly-sized prime integer, such that the size of $n$ is sufficient to ensure security (i.e. at least 1024 bits, as of 2012). Also, Alice must arrange for $p-1$ and $q-1$ *not* to be multiples of 3.
* Alice writes $n$ on the card.
* Bob first *pads* his phone number into a byte sequence as long as $n$, as described by PKCS#1 (this means: 00 02 xx xx ... xx 00 bb bb .. bb, where 'bb' are the ten bytes which encode the phone number, and the 'xx' are random non-zero byte values, for a total length of 128 bytes if $n$ is a 1024-bit integer).
* Bob interprets his byte sequence as a big integer value $m$ (big-endian encoding) and computes $m^3 \mathrm{\ mod\ } n$ (so that's a couple of multiplications with very big integers, then a division, the result being the remainder of the division). That's still doable by hand (but, there again, it will probably take the better part of a day). The result is what Bob sends back to Alice.
* Alice uses her knowledge of $p$ and $q$ to recover $m$ from the $m^3 \mathrm{\ mod\ } n$ sent by Bob. The Wikipedia page on RSA has some reasonably clear explanations on that process. Once Alice has $m$, she can remove the padding (the 'xx' are non-zero, so the first 'bb' byte can be unambiguously located) and she then has the phone number, which she can compare with the one she had.

Alice's computation will require a computer (what a computer does is *always* elementary and doable by hand, but a computer is devilishly fast at it, so the "doable" might take too much time to do in practice; RSA *decryption* by hand would take many weeks).

(Actually we could have faster by-hand computation by using McEliece encryption, but then the public key -- what Alice writes on the card -- would be huge, and a card would simply not do; Eve would have to transport a full book of digits.)
> 29 votes

# Answer
Looks like a classic application of Public Key Cryptosystem like RSA.

You send your public key along, BoB encrypts your phone number from his contacts list and sends it back to you.
> 16 votes

# Answer
One of the most basic things you can do is a Diffie-Hellman key exchange. It does not require you to have keys set up before the communication starts as it negotiates one in a way that listeners can not derive the key themselves. See the comprehensive Wikipedia article for details.

You send Bob DH parameters $p$ and $g$ ($p$ being a suitable large prime, and $g$ typically a small number) and your public key $g^{a} \mathop{\mathrm{mod}} p$, where $a$ is a large secret number (it's your private key), as well as instructions for Bob to send back the following:

* his public key $g^{b} \mathop{\mathrm{mod}} p$, where $b$ is a large secret number of his choosing;
* what he believes is your phone number, encrypted using a symmetric encryption algorithm with a key derived from the shared secret $g^{a\\,b} \mathop{\mathrm{mod}} p$.

Eve can see $g^{a} \mathop{\mathrm{mod}} p$ and $g^{b} \mathop{\mathrm{mod}} p$, but effectively cannot calculate $g^{a\\,b} \mathop{\mathrm{mod}} p$.

As long as implemented properly and both communicators and attacker have about the same calculation power at their disposal, this is secure.
> 15 votes

# Answer
Bob doesn't have to send any messages that you can decrypt. He only has to prove to you that he has your phone number. Therefore, Cryptographic Hash Functions, (one-way encryption) offers an alternative to a public key cryptosystem. SHA-2 is currently a popular example of such a function.

In this strategy, you never have to decrypt Bob's message back to you. You tell Bob which hash function you would like him to use, e.g. "Bob, please use SHA-2 to encrypt my phone number and have Eve pass the result back to me". Then you use the same algorithm to hash your phone number, and check if you get the same hash that Bob got. It is extremely unlikely that two different phone numbers would result in the same hash, and so you can determine whether or not Bob has your correct phone number.

If you, Bob, and Eve don't have computers available to compute the hash function (or perform a brute force attack) it may be possible to use hash function that sacrifices some security against brute force attacks but is much easier for you and Bob to calculate.
> 3 votes

# Answer
A simple solution would be:

Both Alice and Bob agree on the same colour. and it's no problem if Eve knows that one, we'll call this P. Let's say it's yellow. Now, Alice and Bob both randomly choose a private colour, say "x". Alice chooses red, and Bob chooses blue. Now they mix them together with the P. Alice now has orange, and Bob has green. Alice sends the orange colour to Bob, and Bob sends his green colour to Alice Eve now knows about yellow, orange, and green but Alice also knows her private colour red, and Bob knows his private colour blue, which nobody else knows. Both Alice and Bob take their original private colours and add them to the ones they just exchanged. Now, if they mix their original private colours, red and blue, into the shared colour, they both end up with the same colour, sort of brown, or brick red.

Instead of mixing colours together, you could use $g^x\pmod{p}$ such that p is a large prime number, and g is a primitive root of p because if you do $g^x\pmod{p}$ for any x, the result (a number between zero and p - 1) is *equally likely* to be any of those, that's why there's a primitive root. if p is a prime number 2n+1 such that n is also prime, then you know that 2 is a primitive root of p (which means you don't have to bother calculating the primitive root, which is kind of hard) thus the shared secret = $A^x\pmod{p}$ for Bob, and $B^y\pmod{p}$ for Alice.

---

I think you can write something like this on the card:

> The number is multiple of 3,5 and 7 (for example).

There are $(10)^n$ ($n$ is the number of digits) possibilities and that idea will just invalidate some few possibilities for the one who has know idea about it. So decryption by Eve will not happen.
> 0 votes

# Answer
Just ask Bob to multiply the number by 2 or 3 or anything else and xor that number with the number itself. It's doable by hand and reversible if the number is known. No sha, rsa or md5. Just plain maths.
> 0 votes

# Answer
Send Bob a codeword encrypted with your phone number; if he sends you the code word back you know he has the correct number.

The weakness is that Eve can simulate Bob, so just try every phone number until she gets the one that gives the some codeword as Bob returned.

So get Bob to append a very large random number to the codeword then encrypt it before sending it back to you. This makes Eves search space as large as you wish.
> 0 votes

# Answer
I will write some 10 phone numbers in the card and among those I'll make sure that ***My number would come next to Bob's number*** and I will mention "Hey Bob, My number is next to your number, please verify" :)
> -1 votes

# Answer
I think the question is a lot simpler than everyone thinks. We are required to verify that the number Bob has is correct (or as it might be, incorrect). Since we are "checking" if the number is correct it can be assumed that Bob already has your number. Therefore there is no need to send Bob your number in some code. My answer would be, "Dear Bob, please phone my number. Thanks, Alice"
> -1 votes

# Answer
try doing a trik play like this

solution1: if the number is 37 the hash map would look like this

01 07

15 12

25 20

**31** 36

49 43

53 50

60 62

72 **72**

85 82

91 94

and do the same for 10 digits or even more just to confuse :P

solution2: or construct a polynomial in which your number becomes some other unique number

solution3: write this in the letter "dude call me"

solution4: write a function in such a way that it does operations on every digit and returns 0 then he send true or false solution5 : if both ends share a common hash function ... it makes life very easy
> -2 votes

# Answer
I think we can do this by using basic bit wise operations or may be customizing it for paper and pencil work. If number of alice is for ex: 663 than she can just convert the number using this methodology. Convert each digit to equivalent binary representation say this as A 663-\> 110 110 011 than reverse the corresponding bits for each individual number say this as B-\> 011 011 110 Now do A and B-\> 010 010 010 Now send this number to bob and ask to do same if result comes same ask him to say yes or else No. In this case eve will not be able to decode the number and there is a very low probability to have different numbers ending up this same representation. Only way eve could guess is by writing all possible combinations and then trying them all but to cater that we can complicate this more by using left or right shift and adding dummy bits.
> -2 votes

# Answer
Please call me (my name is 1001001). If you can't reach me, please write down the phone number that you have and ask Eve to return me.

Explanation: if Bob got my correct #, he can reach me then I know it is a correct #; if Bob didn't get my right #, Eve cannot read my (correct) phone number as well. In this way, I already checked that my friend, Bob, has my correct phone number or not.
> -3 votes

---
Tags: algorithms, cryptography
---


# Question
Title: What's the difference between $a^*+b^*$ and $(a+b)^*$?
What's the difference between the regular expressions $a^\*+b^\*$ and $(a+b)^\*$. Do both of these generate the same language? I was told in a lecture that $(a+b)^\*$ will generate string concatenation of $a$ and $b$. How could this be possible?

# Answer
> 5 votes
1. $a^\*+b^\*$ generates words that either consist of any amount of $a$s or any amount of $b$s, like: $a$, $aaaaa$, $bbbb$
2. $(a+b)^\*$ generates secquences of either $a$ or $b$, for example: $abab$, $aabb$, $bbaa$,...

So, the main difference is, that in 1 you either get strings only containing as or only containing bs. Regex 2 produces a language where you have no order of characters and can put both in.

So, both don't produce the same language, but 1 is a subset of 2.

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Why does this particular hashCode function help decrease collisions?
I just read in *Effective Java* about the `hashCode` method:

> 1. Store some constant nonzero value, say, 17, in an int variable called result.
> 2. For each significant field f in your object (each field taken into account by the equals method, that is), do the following:
>
> **a.** Compute an int hash code c for the field.
>
> **b.** Combine the hash code c computed in step 2.a into result as follows: `result = 31 * result + c;`
>
> A nonzero initial value is used in step 1 so the hash value will be affected by initial fields whose hash value, as computed in step 2.a, is zero.
>
> If zero were used as the initial value in step 1, the overall hash value would be unaffected by any such initial fields, which could increase collisions. The value 17 is arbitrary. The multiplication in step 2.b makes the result depend on the order of the fields, yielding a much better hash function if the class has multiple similar fields.

And that's their implementation of `hashCode`:

```
@Override public int hashCode() {
    result = 17;
    result = 31 * result + areaCode;
    result = 31 * result + prefix;
    result = 31 * result + lineNumber;
    hashCode = result;
    return result;
}

```

My questions are below:

1. How does the initial value 17 help us decrease collisions?
2. How does multiplying by 31 help us decrease collisions?
3. Why do we use 17 and 31? I know they are prime numbers. Is that why we use them?

I tried to come up with an example of a collision using a class with two and three integer fields, but didn't succeed. I'd glad, if you gave me a simple example of a collision.

# Answer
> 5 votes
If the hashed codes are $x\_1,\ldots,x\_n$ (in that order), then the resulting hash value is $$ x\_n + 31 x\_{n-1} + 31^2 x\_{n-2} + \cdots + 31^{n-1} x\_1 + 31^n \cdot 17 \pmod{2^{32}}, $$ assuming `int` is 32 bits, and ignoring signed/unsigned distinctions. In view of this, the integers 17 and 31 should satisfy the following two properties:

1. 17 should be non-zero. This way, the hash depends on the input length. Otherwise it is completely arbitrary.
2. 31 should be relatively prime to $2^{32}$ (i.e., odd) and have a high order modulo $2^{32}$ (that is, the minimal $m$ such that $31^m \equiv 1 \pmod{2^{32}}$); this way the multiplicands $31,31^2,\ldots$ are all different for the longest time possible. It turns out that the order of $31$ modulo $2^{32}$ is only $2^{27}$, so 31 is not an optimal choice. Its being prime makes no difference – we only care about its oddness and order.

In any case, this hash can be improved on – for example, the `python` hash function uses XOR instead of addition, thus making the resulting calculation non-algebraic.

# Answer
> 2 votes
In abstract terms, we are looking at a mapping from triples of numbers to integers. If you unfold what they do there, you get

$\qquad\displaystyle f(a,b,c) = 17 \cdot 31^3 + a \cdot 31^2 + b \cdot 31 + c$.

The idea is to encode everything into one number in a *surjective* way, that is no two triples map to the same number. Since this is impossible in practice because the domains have different sizes, you want to even out values as much as possible.

I don't understand their reasoning about the initial value; shifting all hash values by a constant does not seem to solve any problem I can see. Multiplying the encoded numbers with different powers of a prime makes sure they don't "overlap".

In my opinion, a more reasonable variant would be the rather standard

$\qquad\displaystyle f(a,b,c) = 2^a + 3^b + 5^c \qquad(\\!\mod m)$;

here, we use that every number has a unique prime factorisation. Of course, this creates *huge* numbers (using modulo arithmetic, it's still feasible to compute the values); Cantor's scheme would be the next go-to scheme.

---
Tags: hash
---


title: How do arrays work "under the hood"?

text:
# Question
Title: How do arrays work "under the hood"?
In some languages (such as C), arrays seem very simple to me. When allocating memory for these, all you need to do is pick a starting point in memory and then allocate the next `dataTypeSize * arrayLength` bytes as reserved. Retrieving items just means looking at the memory address `startPoint + (index * dataTypeSize)`.

But in other languages (such as JavaScript and ActionScript), there is no requirement to make them fixed when creating the array. In fact, most often in actual use, an empty array is created, then new items are one by one appended to the array in a `for` loop.

How is the memory managed when you could at any time append add an item to the end, or prepend an item to the beginning? Do you need to redefine space in memory every time the size changes?

# Answer
> 3 votes
There is no single standard implementation of JavaScript, so if you want to know what happens in a particular implementation, you should use your web search skills, focusing your efforts on that particular implementation. That said, a cursory web search reveals two main points:

1. Arrays can be implemented simply as associative arrays (also known as hash tables or, in python, dictionaries). This is appropriate if the array is sparse (contains only few non-zero values).
2. Arrays can be implemented as dynamically sized arrays, which are appropriate for the dense case. These are stored as classical C/Fortran arrays with a certain "extent". Once their length exceeds their extent, they are extended (say by doubling the extent) by allocating a new array the size of the new extent, copying the old values to the new array, freeing the old array, and changing the appropriate pointer to reflect the new location in memory. Arrays can potentially shrink as well according to a similar scheme.

Associative arrays are also dynamically sized, so in any case the second paradigm is being used.

Since the extent of the arrays increases exponentially, the average overhead is bearable, though once in a while, an operation may take a long time to perform (due to an array being resized). So such arrays are not a good choice for real-time systems.

---
Tags: arrays, memory-allocation
---


# Question
Title: Is there an O(n log n) algorithm for 4D line simplification?
The Ramer-Douglas-Peucker algorithm for line simplification has worst-case $O(n^2)$ runtime. For suitably distributed random inputs, it has expected $O(n \log n)$ runtime complexity. In 2D, there are other algorithms with worst case $O(n \log n)$ runtime complexity, which compute exactly the same result as the Ramer-Douglas-Peucker algorithm. Since these algorithms are based on a "path (convex) hull" datastructure, it is not obvious whether they can be generalized to 4D lines.

Is there a (randomized) algorithm which has (expected) $O(n \log n)$ runtime (independent of input) for the case of 4D lines? You may assume Euclidean distances and a global absolute tolerance.

# Answer
The algorithm that works with 4D case is described in the article *Near-Linear Time Approximation Algorithms for Curve Simplification* by four authors: *Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa, and Yusu Wang*.

> Given a polygonal curve $P$ in $\mathcal R^d$ and a parameter $\epsilon \ge 0$, an $\epsilon$-simplification of $P$ with size at most $\mathcal \kappa\_F(\epsilon/2, P)$ can be constructed in $\mathcal O(n\log n)$ time and $\mathcal O(n) $ space.

The algorithm does not depend on monotonicity properties. It covers the original line with disks and seeks the line traversal on the ordered set.

Sidenote:
There is a modification of Douglas-Peucker algorithm with the worst-case in $\mathcal O(n\log n)$ described in the paper *An O(n log n) Implementation of the Douglas-Peucker Algorithm for Line Simplification.* by *John Hershberger and Jack Snoeyink*: improved DP line simplification. Indeed it uses path hull.
> 0 votes

---
Tags: reference-request, computational-geometry, randomized-algorithms
---


# Question
Title: A schedule is not conflict-serializable. Is it serializable?
While reading this solved quiz on concurrency control, I got stuck on exercise 2, which reads as follows:

> 2) Consider the following schedule:
>
> S: r1(X), w2(X), r3(X), r1(Y), w2(Z), r3(Y), w3(Z), w1(Y)
>
> (a) (2 points) Draw the precedence graph.
>
> (b) (1 point) Is S conflict serializable?
>
> No.

After reading that S is not conflict-serializable, my question is: can we say that S is serializable? Any suggestions?

Thanks to anyone who help me.

# Answer
> 1 votes
A schedule is considered serializable if it is equivalent to a serial one. The conflict graph that appears on the answer to item (a) is proof that the schedule is not conflict-serializable, and it is also not *view-serializable*, because there is still a cycle between $T\_1$ and $T\_3$, when considering just the history of the data they visualize. That means the schedule cannot be considered serializable at all.

Conflict-serializability is stronger than view-serializability. It is the criterion used for the implementation of most schedulers, and that is why the quiz emphasizes this point.

---
Tags: concurrency, database-theory, databases
---


# Question
Title: Why does taking a gamma value > 1 make the image darker?
If I've understood gamma correction correctly (and I probably haven't), a gamma transform to an image raises the value of the intensity level of the input pixel to the power of gamma, where gamma can be greater than one or less than one.

Pout = (some\_constant) x Pin^(gamma)

In every example that I've seen, a gamma value \< 1 makes the image lighter (raises intensity of lower intensity pixels) and a gamma value \> 1 makes the image darker. This seems counter intuitive to me since a gamma value \> 1 should **increase** the intensity levels of all the pixels making it lighter and more saturated.

Can someone explain this to me? Where am I going wrong?

# Answer
Because pixel intensity in any professional task is measured between \[0; 1\].

The most representations are 8bit per pixel but there are for example 16bit representations.
So with \[0;1\] intensities there is always good representation device independent.

Another important thing is chaining operations (multiply, add pixels etc.), floating points are better because they store fractional values.
If you have RGB from 0-255 it is one way of representing it, very common, discrete but device dependent.
In such representation operations on pixels like gamma needs normalisation by division: divide by 255, apply operation, then cut to \[0; 1\] and then multiply by 255.
In floating point operation this is not needed.
Also look out for shifted gamma corrections, in colour space conversion for example.

Summing it up \[0; 1\]$^\gamma$ is going counter-intuitive.
> 2 votes

---
Tags: image-processing
---


# Question
Title: What is the relationship between problems and languages?
I want to ask exactly what is the relationship between problems and languages. We know that the set of all languages uncountable. Is the set of problems also uncountable? Can every problem be defined by a language? Can a language solve more than one problem and vice versa? Is there one-to-one correspondence between problem and languages?

# Answer
> 15 votes
Decision problems and languages are just the two sides of the same coin: every problem can be rephrased as the membership problem of some language. The problem of, say, determining whether a number is prime is exactly the membership problem of the language of prime numbers.

Formally, a language is a set of finite strings over some fixed finite alphabet (sometimes, the strings are allowed to be infinite; that's a different but related scenario). Problems that aren't directly questions about strings will need to be encoded as strings so, for example, it would have been more precise to write the last sentence of the previous paragraph as, "If we fix an alphabet and an encoding of natural numbers as strings over that alphabet, the problem of, say, determining whether a number is prime is exactly the membership problem of the language of strings that encode prime numbers."

To quickly run through your subquestions,

> We know that the set of all languages uncountable. Is the set of problems also uncountable?

Yes, since problems and languages are essentially the same thing.

> Can every problem be defined by a language?

Decision problems, yes. Optimization problems (what's the smallest X with property Y) and counting problems (how many X's have property Y) can be rephrased as decision problems (is the Z the smallest X with property Y?; are there N X's with property Y?), though that's usually not the most natural way of treating them.

> Can a language solve more than one problem and vice versa?

Yes and yes, because you have to use encodings to translate between problems and langauges. For example, the languages $\\{10,11,101,111,1011,\dots\\}$ and $\\{2,3,5,7,11, \dots\\}$ both encode the primality problem (in binary and decimal, respectively). Conversely, though perhaps a little artificially, the language $\\{0, 10, 110, 1110, \dots\\}$ encodes the problem of determining whether a binary number is of the form $2^k-2$ for some $k$ and the problem of determining whether a string of 1's and 0's has exactly one 0, which is its final character. (Perhaps somebody can come up with a better example of a language that naturally encodes two problems without one being such a trivial rephrasing of the other.)

> Is there one-to-one correspondence between problem and languages?

No, since this question is just the complement of the previous one. :-)

---
Tags: formal-languages
---


# Question
Title: Are syntax and semantic just 2 structures such that one is a model of the other?
* The syntax of a language is a structure.
* The semantic of a language is a structure.
* The semantic of a language is a model of its syntax.

And that's all ? The duality syntax/semantic is just model theory applied to languages ?

(A short answer could be ok; I have already read the wikipedia pages !)

# Answer
> 7 votes
I am afraid the phrasing of the question misled me (though I did know better) in first seeing model theory as applying to any two arbitrary mathematical structures, and being the study of homomorphisms of mathematical structures.

Actually this is wrong. Model Theory already contains the idea of syntax and semantics, more or less as I define it below. It studies *theories*, which are sets of sentences in a formal language, and *models* which are interpretation of these sentences in abstract mathematical structures. This is close to what I call *language* below, and I guess this is also close to what the author of the question calls *language*.

So the proper answer to the question is that even model theory has a concept of syntax and semantics, where syntax is a *theory*, i.e. a formal representation structure such as a universal algebra, and semantics is an interpretation (i.e. a morphism) in some abstract mathematical domain.

Hence **the "duality syntax/semantic" is already present in model theory**. There is nothing new on that side.

However, **what may make a difference is the understanding of the word language**, as it could be interpreted as going beyond what is usually concerned by the syntactic algebras usually addressed by model theory.

Actually, the question does not define the word language, and it could be formal languages, programming languages, natural languages, with some unsaid understanding of what is intended.

So two possible answers could be:

* model theory is the study of languages with their syntax and semantics, and there is nothing to add, or
* a language can be defined by an arbitrary syntactic definition (meaning a computable structure) and a homomorphic(?) mapping in some abstract mathematical structure. The question mark is because I fear that the definition of the mapping may raise some issues.

The second view is possibly less formal, or less constrained. Whatever the case, I am leaving below my initial answer (which corresponds to the second view), since several of the issues it is addressing may still be relevant and of interest to computer scientist, even though the presentation may be debatable from the point of view of model theory.

It does not bring anything new from a formal point of view, since the study of formal system that are considered in syntax already had to go all the way to Turing computability, in order to address the Entscheidungsproblem, and that is as far as we may hope to go in terms of syntax. I may however help understanding some more practical issues.

*Your comments are welcome, including suggestions to erase my former, more naive, though possibly more intuitive, answer.*

---

---

*The first section is the direct answer to the question. The other two sections may be skipped. They are attempts to explore some examples or consequences, or some practical aspects encountered by computer scientists, in particular in the design of programming languages.*

## Syntax, semantics and languages

The view of the issue as expressed in the question is mainly "OK". My main criticism though is that **the reference to the concept of language is critical**, because directly related to the concept of syntax, not separable from the concept of syntax.

As a consequence, there is something circular, kind of tautological, about your statement. The question is why do we use this specific terminology of "*syntax and semantics*" for some models, for some homomorphically related pairs of structures, and not for others. Where is the difference? And a correlated question is: **what is a language?**

Clearly there is no restriction on semantics: any topic/structure can be the object/content of a discourse. Hence, the fundamental distinction is to be looked for on the syntax side. My own understanding is that what distinguishes such a homomorphic pair is the domain of the homomorphism: **the syntax structure has to be concrete and concretely manipulatable**. Basically a syntactic structure is a finite collection of concrete objects, usually idealized as symbols, and a finitely defined collection of rules to compose in diverse ways any unboundedly finite number of copies of these symbols, and to transform such compositions into others compositions. The word *syntax* comes from 'Ancient Greek: σύνταξις "coordination" from σύν *syn*, "together," and τάξις *táxis*, "an ordering"'.

Fundamentally, syntax is physical. The concept of symbol is only a mean to abstract away the choice of physical instanciation of the symbols as objects such as sounds, gestures, glyphs, objects, stones (which gave us the word *calculus*), electric or magnetic state, presence and absence of a signal, etc., or composition of other symbols.

Hence, the theory of syntax is essentially what is better known as the theory of computation, which is the study of rule based manipulation of symbols. Whatever we express, transmit, receive, compute, memorize, analyze, is processed through some syntactic symbolic representation.

But what we are interested in is not the symbolic representations, but some semantic concepts or objects (possibly themselves physical) that are intended to be represented by the symbolic compositions at hand. And the correspondence is defined by the semantic homomorphism into its semantic codomain.

Then, in the most general acceptation of the word, **a language is the association of a syntax structure and a semantic structure through a homomorphic mapping**. Or to state it in the terms of the question, it is a pair of structures such that one is a model of the other, with the additional requirement that the latter be a syntactic structure. **But, in order to give such a definition, you must first define what is a syntactic structure.** And that definition stands on its own, independently of the concepts of *language* or *semantics*: **Syntax is the study of finitely defined manipulations (including transmission and memorization) of unboundedly finite compositions of copies of a finite set of symbols**. Ot in simpler terms, **syntax concerns the definition, analysis and manipulation of representations**. You may read *computation theory* and *information theory*.

This is in agreement with the concept of homomorphism: the meaning of the whole is derived from the meaning of the parts. But this is a meta-remark. I insist less on defining semantics since it seems that any structure (that makes sense?) can play that role.

## Further remarks

I do not know if the view of linguists on natural language is exactly the same, or as precise regarding the homomorphic relation, but it should not be too far from it. The concepts of syntax and semantics arose from language analysis and logic, which I assume were the same topic at some point in history (actually diverging pretty late, in the 19th century according to Wikipedia page on syntax). Still, it seems that some modern linguists follow somewhat similar views "*since they regard syntax to be the study of an abstract formal system*".

The point is that most mathematical domains, abstract concepts, and other objects of discourse generally elude us, and can only be contemplated and dealt with through mechanisms to represent them and (some of) theirs values, i.e. through syntactic representation. In its simplest form, it can be a pointing finger to represent a direction.

The main characteristic of a syntactic domain is that it is a concrete representation, finitely defined through some formal system such as the formal languages dear to computer scientists. But these syntactic domains, which are very precisely the domain of computation, i.e. of syntactic transformations, are very limited, as we learn from the study of computability. For example, they are denumerable, while many abstract domains we are interested in are not denumerable.

As a consequence, it is often the case that syntax can only represent a small part of the mathematical domains we study. This is typically the case for real numbers, almost all of which do not have a (finite) syntactic representation, the others being the computable reals.

Choosing a data structure to represent the values of some abstract domain we wish to compute with is just finding an appropriate syntax, for your semantic problem, whether to express some conceptual semantic derivation (computation) or to have simpler relation with semantics (semantic morphism), or to optimize some aspect of communication and memorization (space. speed, reliability).

For users who want an example, computing the sum of XXVII and XCII, I mean 11011 and 1011100, is just a manipulation of the digits to get the representation of a number (119) that is the sum of the numbers represented by the initial two representations. The positional notation happens to be easier to manipulate, to be more economical in space (number and variety of symbols), and to have a simpler way to express the homomorphism. The syntax changes, the semantics is the same, and in both correspond to languages to express natural numbers (well, not quite for Roman numerals).

IMHO (but some of this may be a matter of individual perspective), if syntax should be only what can be represented and manipulated, semantics can be any mathematical domain, or more generally any abstract domain of discourse, including the domains used for syntax. Hence you can have a theory of syntax where you study syntactic representation systems. Formal language theory is nothing else.

Note that the the idea of a syntac-semantic *duality* should not induce the idea that there is some sort of symmetry between syntax and semantics.

## Syntax and semantics in computer science practice

It is true that we often pretend to address semantic issues, for example when defining formally the semantics of a programming language $L$. But that may be seen as an abuse. What we really do is use a standard language $S$ that is supposed to have an accepted semantics and define the semantics of $L$ in terms of the semantics of $S$. The difficulty is that we can never access semantics directly, but only through some syntactic proxy, even when the semantics is itself syntactic in nature. This is why we use metalanguages such as Backus-Naur Form (BNF).

There are however various mathematical techniques to define semantic domains. Among these techniques, you have the definition of syntactic models where the syntax (possibly up to quotient by some equivalence relation) is its own model. Actually, one of the major contribution of Dana Scott to computer science was to conceive non-syntactic models of lambda-calculus which is (initially at least) a purely syntactic theory (see for example Continuation Models for the Lambda Calculus With Constructors, B. Petit (2012).

A characteristic of most mathematical theories is that they may have many models, including non-standard models. "*A non-standard model is a model of a theory that is not isomorphic to the intended model (or standard model)*". That also applies to syntactic theories. Actually, non-standard interpretation of languages is a very fruitful area of research in computer science, related to abstract interpretation, type analysis, flow analysis, partial evaluation and many other approaches to program analysis. To take a very trivial, purely syntactic example, a non-standard interpretation of a program can be a pretty-printed version of that program. A type checker is usually an abstract interpretation of the program.

As a consequence, it is clear that the chosen syntax may not capture, express, all the properties of the intended semantic domain. However, anything that is considered as syntactically correct must have some associated semantics through the semantic morphism, even if it is some special error value. But it is improper, though often done, to state that the syntax is defined by a context-free grammars, and then consider programs with undeclared variables as being incorrect. It cannot be syntactically incorrect for such a reason, because CF grammars cannot check variable declarations. And I would not know what it means to be semantically incorrect, other than being possibly a special error value of the semantic structure.

The dream of programming language designers or implementor is that any program that can only fail, or that can fail in some specific way, should be syntactically incorrect. Hence, they have been increasing the descriptive power of syntax to include as much checking as possible, limited only by computability constraints. This did lead to the use of Turing complete formalisms, of which van Wijngaarden's W-grammars are an example. But this is a pipe dream. Computability theory tells us that semantic properties of syntactically expressed functions cannot be checked syntactically, as soon as the language has Turing power, which we usually expected in programming languages.

In practice, this checking for intrinsic correctness (i.e. independent of problem specification), or for properties to be used, is often performed in compilers (or in formal semantic definitions) by what is called static semantics. Being purely computational, static semantics can be as well considered as part of the syntax.

In the case of programming languages, the semantic domain is a computation domain. Given that we allow Turing complete formalisms to express the syntax, it becomes possible for the syntax to express completely the semantics. But developing this angle is getting far away from the original question. Still, this is the main reason why the distinction between syntax and semantics is so difficult to make precise in programming languages. This may also be the reason why universal Turing machines are possible.

A last point is that defining the semantics as a structure that is a model of the syntax may not be enough. It could be a model in several different ways. So it is essential to include the morphism in the description of the semantics. That is typically what is done with denotational semantics of programming languages, and a lot of other formal systems.

<sub> *Note: This was rather complex and hard to write. If you are to criticize it, I would appreciate explicit and precise comments. It would also be useful to other users. Thank you.* </sub>

# Answer
> 4 votes
It all very much depends on how you model these concepts where syntax end and semantics start. When the syntax is described using a context free grammar, then there are aspects of the language not expressed in that model so we say those aspects are the semantics.

However, there are many other ways of expressing (or modelling) the syntax of the language. Take W-grammars for example. You can define the totality of the language in one grammar and the distinction between the semantic and the syntactic component is less clear. The book *Grammars for Programming Languages* by Cleaveland and Uzgalis contains a good introduction and some nice examples, one of which I show here:

```
N :: i ; Ni .
EMPTY :: .
NETY :: N; EMPTY.
RADIX :: iii iii iii i .
EXP :: iiN.

fermat : EXP pr N1, equal symbol,
         EXP pr N2, plus symbol,
         EXP pr N3,
         where N1 is N2N3.

N1 pr N2 : N3 number, power symbol, N1 number,
           where N2 is N3 to the N1 power.

where N1 is N2 to the NETY i power :
           where N3 is N2 to the NETY power,
           where N1 is N3 times N2;
           where N1 is N2, where NETY is EMPTY.

where NETY1 N is N is N time NETY2 i :
           where NETY1 is N times NETY2 ;
           where NETY1 NETY2 is EMPTY.

where NETY is NETY : EMPTY.

N1 number : N1 token; N2 number, NETY token,
          where N3 is N2 times RADIX,
          where N1 is NETY N3.

```

This defines the syntax of equations which obey the proviso of Fermat's last theorem, complete with the definition of arithmetic and the mathematics involved....

---
Tags: programming-languages, semantics, natural-language-processing, syntax
---


title: Name of Bomberman algorithm?

text:
# Question
Title: Name of Bomberman algorithm?
Last couple of days I've been pulling my hair trying to find the name of a *bomberman-esque* algorithm which finds solutions to the question of where to place a single bomb so as to blow all targets up, either directly if all targets are within the blast radius (and axis) of a single bomb (placed in an empty cell) or via a chain-reaction by exploding nearby bombs which share the same x- or y-axis within the blast radius (hence the graph exploration issue).

I can describe the situation as following: given a square cell matrix **S** (the board state) of order *n*, containing symbols which differentiate between different objects(empty cells, rocks, targets and bombs), identify all empty cells **P** where a bomb with blast radius **R** can be placed so that all targets **T** will be destroyed. The other initially untriggered bombs also share the same blast radius.

**Edit:** The objects function as follows:

* Empty cell; The only place where a bomb could be placed. Allows explosions to pass through.
* Rocks; Blocks explosion waves.
* Bombs; Sits passively in a cell until reached by an explosion wave, at which point it explodes and sends an explosion wave outwards in the the x- and y- axis, up to the defined blast radius-length away.
* Targets; If reached by an explosion will be destroyed and counts towards the end goal of finding a solution where all targets are destroyed. Allows explosions to pass through.

I started out with a brute-force variant which simply went through all empty cells and started a search from there, which is quite inefficient if all objects are in one corner of a huge board. I came to the following pre-processing insight:

> Since a solution is only regarded as valid if all targets have been destroyed, I can therefore begin my search from any random **T** and if the path generated from that initial **T** does not destroy all **T** then there is no solution to that particular **S**.

I've made an algorithm which manages to find some solutions, but not for all boardstates I'm testing with. (currently only works if no other target is within a blastradius-length from the starting target).

Is this description ringing any bells for you?

My first instinct was an MST, but I've been unable to merge that algorithm with my description above.

# Answer
> 1 votes
As an example, Yellow denotes a target, red cells indicate the radius of the target such that if a bomb was placed in any of the red cells, it would blow up a target.

We can see from the picture that if we listed all the co-ordinates that are red

```
Pseudocode // Note that this tries to add the centre, or the x,y of the target twice
for target in targets:
    for i in range(-radius, radius):
        set[target].add(target.x + i, target.y)
        set[target].add(target.x, target.y + i)

```

Then compare two sets for overlap, and if there is overlap between all of them, then we have an answer.

---

Pinky Purple is a bomb, and the blue is the radius that if another bomb explodes within, it will detonate too

Note that now we have to do a check before adding the co-ordinate to the set

If it is a blank cell it is easy, just add it.

If it is a bomb, dont add it, but add all the possible co-ordinates that will set off the bomb, and if during our checks, we encounter another bomb, we need to add that list too. I would make a recursive method here

```
def bombLinks(candidate.x, candidate.y, bombSet):
    for i in range(-radius): //0 to the -radius shouldn't be checked for bombs, since thats where we came from
        candidateType = blockAtCell(candidate.x + i, candidate.y)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x + i, candidate.y)
        candidateType = blockAtCell(candidate.x, candidate.y + i)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x, candidate.y + i)

    for j in range(radius):
        candidateType = blockAtCell(candidate.x + j, candidate.y)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x + j, candidate.y)
        else if(candidateType = "Bomb"):
            bombSet.add(bombLinks(candidate.x + j, candidate.y, bombSet))
        candidateType = blockAtCell(candidate.x, candidate.y + j)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x, candidate.y + j)
        else if(candidateType = "Bomb"):
            bombSet.add(bombLinks(candidate.x, candidate.y + j, bombSet))
    return bombSet

```

If it is anything else, we could ignore it, or if we want it so that explosions can't pass through certain blocks, we can do some more checks here

```
for target in targets:
    for i in range(-radius, radius):
        candidate.x, candidate.y = target.x + i, target.y
        candidateType = blockAtCell(candidate.x, candidate.y)
        if(candidateType == "Blank"):
            set[target].add(candidate.x, candidate.y)
        else if(candidateType == "Bomb):
            set[target].add(bombLinks(candidate.x, candidate.y, []))

        candidate.x, candidate.y = target.x, target.y + i
        candidateType = blockAtCell(candidate.x, candidate.y)
        if(candidateType == "Blank"):
            set[target].add(candidate.x, candidate.y)
        else if(candidateType == "Bomb):
            set[target].add(bombLinks(candidate.x, candidate.y, []))

```

Whew, thats a lot of code, and you may have a better way of traversing the list of possible bomb locations, just don't forget that you can end up in an infinite loop if you check for bombs both directions

After all that, check the overlap between the sets. If there is an answer, great, otherwise pick the location that came up the most

Please excuse my terrible pseudo code, especially the loops

---
Tags: algorithms
---


# Question
Title: Why do we say that polynomial time is easy?
For years, I've been told (and I've been advocating) that problems which could be solved in polynomial time are "easy". But now I realize that I don't know the exact reason why this is so.

Intuitively, I can guess what the relation between P problems and easy problems is. Experience tells me that P problems are easy too. However, **using only mathematical terms and theoretical arguments, why is P the class of easy problems?**

# Answer
> 8 votes
I don't think it is possible to argue strictly with only mathematical or theoretical terms. Very much does come down to heuristics.
Of course an algorithm with runtime $O(n^{1000})$ or something similarly ridiculous would not be "easy" and in most practical cases worse than an algorithm of modest exponential growth. Yet such algorithms just don't happen in practice. And if an algorithm initially has a quite high runtime, then more often than not it can be improved dramatically, which means that the problem is a lot less "difficult".
As an example, take the AKS algorithm (which tests whether a given number is prime). It started out as $O(n^{12})$ (if I recall correctly), being one of the polytime-algorithms with the greatest exponent. But it was improved to $O(n^{6+\epsilon})$ in a quite short time. And very fast probabilistic algorithms for the primality problem exist as well, which shows that proving primalty is a lot easier than, say, your favorite NP-complete problem (assuming $P\neq NP$).

Of course the above could all turn out to be completely wrong. Maybe there exists a polytime algorithm for every NP complete problem which does not have a "practical" exponent. Knuth advocates that scenario; you might want to read question 17 here.

# Answer
> 1 votes
I most often see complexity applied to optimization problems. There are then two measures for the "size" of a problem: the number $n$ of variables for which optimal values must be determined, and $L$, the number of bits used to represent the problem instance.

Then a problem in **P** has operation count that is bounded above by a polynomial in $n$ and $L$, in other words, there exist constants $c$, $j$ and $k$ such that, for $n$ and $L$ sufficiently large, the number of operations needed to solve the problem is less than or equal to $cn^jL^k$. On the other hand, there are *provably exponential* problems (this does not, at present, include **NP**), for which there exist problems for which the operation count exceeds $Ce^{L+n}$. If $n$ and $L$ are large enough, this will dominate $cn^jL^k$. Of course, $j$ and $k$ may be large, e.g., $j=1000$, in which case this is a theoretical distinction only.

However, experience has shown that once a problem or problem class was shown to be in **P**, the exponents were quickly lowered. For instance, in 1979 Khachian described an algorithm to solve linear programs that had complexity O($n^6L^2$). Just five years later Karmarkar lowered that to O($n^{3.5}L^2$). Khachian's method is not really useful for computations, but Karmarkar's method is. Hence there is a general expectation that once a problem has been proven to be in **P**, even with a large exponent on $n$, algorithmic improvements and new approaches will lower the exponent. In addition, no problem in **P** has been identified to date where the exponent truly was large. (I seem to remember reading about problems for which $j=12$.)

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


title: Help needed with lesson on recursion

text:
# Question
Title: Help needed with lesson on recursion
I'm studying CS online, and I'm reading this lecture on recursion, see "3.2. A Mathematical Example".

I understood the beginning and I even made a program that calculates $X$ to the power of $N$ using recursion.

Reading on, I quote from the lesson's content:

> Find an algorithm for raising a number $X$ to the power $N$, where $N$ is a positive integer. You may use only two operations: multiplication, subtraction. We would like to multiply $N$ copies of $X$ all at once, but, like the piles of books, we do not have an operation that directly allows us to do that: we can only multiply two numbers at a time. In other words, the problems we can solve directly are these:
>
> Raise $X$ to the power $1$: answer = $X$.
> Raise $X$ to the power $2$: answer = $X \times X$.
> Any other problem we have to solve indirectly, by breaking it down into smaller and smaller problems until we have reduced it to one of these base cases.
> So, if $N \> 2$, we split the original problem into two subproblems:
>
> $P1$: raise $X$ to the power $I$. The answer to this is $S1$.
> $P2$: raise $X$ to the power $N-I$. The answer to this is $S2$.
> To get the final answer, $S$, combine $S1$ and $S2$: $S = S1 \times S2$.
>
> How do we solve $P1$ and $P2$? They are problems of exactly the same type as original problem, so we can apply to them exactly the same strategy that we applied to the original problem. We check to see if we can solve them directly... if $I=1$ or $I=2$ we can solve $P1$ directly; if $N-I=1$ or $N-I=2$ we can solve $P2$ directly. The problems we cannot solve directly, we solve recursively, as just described. An interesting feature of this strategy is that it works no matter how we split up $N$.

What I don't understand is, how I'm supposed to split it up into bigger chunks to achieve greater speed.

1. Since the game rules are that I can only use multiplication and subtraction operators, so how can I divide $X$?
2. If I know that $N-I=2$, how can I solve $P2$ directly, it's $X \times X \times X$, meaning two multiplications?
3. Is each $P$ a separate recursion?

# Answer
> 2 votes
Here are several approaches to compute $x^n$ from smaller powers of $x$:

1. doing $x \times x^{n-1}$. The former is $P(1)$ the latter is $P(n-1)$.
2. doing $x^2 \times x^{n-2}$. The former is $P(2)$, the latter $P(n-2)$.

But we don't need to use $P(1)$ and $P(2)$ at each step, right? we can use any $P(k)$ with $k\<n$. So how about,

3. doing $x^{n/2} \times x^{n/2}$? (or in general $x^{k} \times x^{n-k}$)

Now, assume each multiplication takes $M$ time. Which approach is the fastest?

---

EDT after comments:

the main idea of recursion (somewhat similar to induction), is that we can "solve" some problem by using the solutions of smaller problems.

So $P(n)$ can be easily computed by $P(n/2) \times P(n/2)$ (assuming $n$ is even and above 2). But how do we compute $P(n/2)$? well, that's the magic, the above idea works for any number $n$ and specifically also for the number $n/2$ (as long as it is even and above 2); So how do we compute $P(n/2)$? We recurse!

> $P(n/2) = P( (n/2)/2) \times P( (n/2)/2) $

Why does it work? because eventually ((n/2)/2)...)/2 will be either 1 or 2, and this is $P(1)$ or $P(2)$ that we know how to solve.

To sum up, the recursion will look like this:

```
function P(n):
if n=1 or n=2  return ....
else
   if n is even, return P(n/2) * P(n/2)
   if n is odd, return  ..... (very similar)...

```

I leave you to work out the details.

This is of course the faster way. The slower way, but maybe simpler to understand, is to do the recursion step by step. The function in this case will look like:

```
function P(n):
if n=1 or n=2  return ....
else
   return P(n-1) * x

```

This one works for any number $n$ and returns $x^n$. The last line just instantiates the function again with a smaller parameter.

---
Tags: algorithms, recursion, divide-and-conquer
---


# Question
Title: Query about FP Divide latency and Initiation Interval
Latency is defined as the number of intervening cycles between an instruction that produces a result and an instruction that uses the result. The initiation or repeat interval is the number of cycles that must elapse between issuing two operations of a given type.

In the Appendix C, pages 52-54 of **Computer Architecture: A Quantitative approach 5th edition**, it was mentioned that

1. the FP adder is of 4 stages and pipelined, so latency =3(No. of pipeline stages -1) and initiation interval =1 (as pipelined)
2. the FP multiply is of 7 stages and pipelined, so latency =6(No. of pipeline stages -1) and initiation interval =1 (as pipelined)

So for 3. The FP divide of 24 stages and unpipelined, so latency =23(No. of pipeline stages -1) and initiation interval =24 (as unpipelined). But it was mentioned that the latency was 24 and initiation interval was 25.

latency and initiation interval and FP pipeline

Why is this?

Can anyone explain me? As I missing something

# Answer
You can think latency as the time (# intervening clock cycles here) required to get a result from a producer instruction to a consumer instruction. For FP divider it is required 25 cycles and the unit is unpipelined. So, the #intervening CC = 24. On the other hand, initiation interval is the duration of time that is required to issue two similar type instruction. As FP divider is unpipelined, so you can issue another FP divider after finishing the previous one which requires 25 clock cycles. If it was pipelined, I guess it would be 1.
> 2 votes

---
Tags: terminology, computer-architecture
---


# Question
Title: Clear interrupt instruction in a pipelined CPU
Say you execute a clear interrupt instruction (CLI) in a pipelined CPU. While that instruction is being fetched, an interrupt occurs, so the instruction after the CLI is from the interrupt handler.
You excepted no interrupts because of the CLI instruction but you still got one. How is this problem solved?

# Answer
> 4 votes
Such a control hazard can be handled effectively the same way that a branch misprediction is handled. Either the CLI instruction commits and the interrupt handler fetch is treated as the mispredicted path and fetch is restarted after the CLI or the CLI instruction is not committed and the interrupt handler is treated as the correct path.

# Answer
> 2 votes
External interrupt are usually processed as traps (divide by zero, MMU faults...) in pipelined CPUs, to share resources and simplify the design. They are handled late in the pipeline, which can have some negative effects on interrupt latency.

For traps, the pipeline is flushed, all the partially executed instructions are discarded.

When implementing the CLI/STI instructions, one shall carefully ensure the correct synchronisation between the update of the flags and the detection of the interrupt.

> While that instruction is being *fetched*, an interrupt occurs, so the instruction after the CLI is from the interrupt handler.

The interrupt request must be active before the CLI instruction is *committed*. If it is too late, the CPU will simply ignore it.

The interrupt request signal may need to be frozen when special instructions like CLI, STI, "read the machine-state-register-with-the-interrupt-bits" instructions traverse the pipeline.

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: How are these problem variants that ask about the size of optimal solutions in NP?
I just started reading Vazirani's book "Approximation Algorithms". It is legally available online here.

On page 5 (23 in the pdf), it says that the following decision problems are in NP:

* Is the size of the minimum vertex cover in $G$ at most $k$?
* Is the size of the maximum matching in $G$ at least $l$?

I can't see why this is true. If, say, the first problem is in NP, then each valid instance (graph) has a Yes certificate which proves that the graph has a minimum vertex cover of size at most $k$.

But, how can one deduce from a certificate something regarding the size of the minimum vertex cover?

# Answer
Any vertex cover of size $k$ is a witness that the smallest one has at most size $k$. Hence, the questions

> Is there a vertex cover of size at most $k$?

and

> Does a smallest vertex have size at most $k$?

are equivalent.
> 5 votes

---
Tags: complexity-theory, decision-problem, np
---


title: Memory usage of a BST or hash table?

text:
# Question
Title: Memory usage of a BST or hash table?
I would like to use a data structure allowing fast access, either a balanced binary search tree (BST) for $O(\log n)$ access time or an open hash table for constant access time.

1) What is the exact memory usage of a BST or hash table, for storing $n$ values? For instance, if we consider a BST, are $n$ pointers sufficient for storing it? (We can neglect the size of the stored values. The only thing that interests me is the storage overhead involed by the use of a specific data structure)

2) If the choice has to be determined by the cost in space, subject to the constraint of a fast enough access time, what is the best data structure to use?

For the space cost criteria, I would like a precise description. I'm interested in two types of usage: static and dynamic. I ask this question in the context of a C implementation.

I'm mostly interested in values around $n=100000$.

# Answer
> 9 votes
When you're asking about "exact" memory usage, do consider that all of those pointers may not be necessary. To see why, consider that the number of binary trees with $n$ nodes is $C\_{2n}$, where:

$$C\_i = \frac{1}{i+1} { 2i \choose i }$$

are the Catalan numbers. Using Stirling's approximation, we find:

$$\log C\_{2n} = 2n - O(\log n)$$

So to represent a binary tree with $n$ nodes, it is sufficient to use two *bits* per node. That's a lot less than two *pointers*.

It's not too difficult to work how how to compress a static (i.e. non-updatable) binary search tree down to that size; do a depth-first or breadth-first search, and store a "1" for every branch node and a "0" for every leaf. (It is harder to see how to get $O(\log n)$ access time, and much harder to see how to allow updates to the tree. This is an active research area.)

Incidentally, while different balanced binary tree variants are interesting from a theoretical perspective, the consistent message from decades of experimental algorithmics is that in practice, any balancing scheme is as good as any other. The purpose of balancing a binary search tree is to avoid degenerate behaviour, no more and no less. Stepanov also noted that if he'd designed the STL today, he might consider in-memory B-trees instead of red-black trees, because they use cache more efficiently. They also use $n + o(n)$ extra pointers to store $n$ nodes, compared with $2n$ or $3n$ for most binary search trees.

As for hash tables, there is a similar analysis that you can do. If you are (say) storing $2^n$ integers in a hash table from the range $\[0,2^m)$, and $2^n \ll 2^m$, then it is sufficient to use

$$\log {2^m \choose 2^n} \approx (m-n)2^n$$

bits. It is possible to achieve close to this bound using hash tables.

To give you the basic idea, consider an idealised hash table where you have $2^n$ elements stored in $2^n$ slots (i.e. load factor of one where every "chain" has length one).

If you hash $m$ bits of key into $m$ bits of hash, then store this in a $n$-bit hash table, then $n$ bits of the hash are implied by the position in the hash table, and you therefore only need to store the remaining $m-n$ bits. By using an invertible hash function (e.g. a Feistel network), you can recover the key exactly.

Of course, traditional hash tables have Poisson behaviour, so you would need to use a technique like cuckoo hashing to get close to a load factor of one with no chaining. See *Backyard Cuckoo Hashing* for further details.

So if space usage is a far more important factor than time (subject to time being "good enough"), it may be worth looking into this area of compressed data structures, and succinct data structures in particular.

# Answer
> 2 votes
First of all BST has not $\Omega(logn)$ access, it has $\Omega(n)$. What you really need is AVL or RBT tree, self balancing trees to maintain logarithmic access.

1) BST you have to use two pointers (to left and right child) and one variable for data. This is whole footprint. Additionally you have to assign root to some variable. For AVL you may add height of left and right subtree (so like BST plus two integers), or one small integer to encode balance. In fact you have to choose what is footprint of one node, this is in tradeoff to speed of balancing operation. What auxiliary data you encode (or choose between AVL and RBT) is determined on ratio of insertions to searches. If smaller footprint is needed rebalancing operation will execute more steps. If you have all data in advance, you can construct BST with $\Omega(logn)$ access, if there will be no changes to structure later.

Hash table with open addressing is described here: http://www.algolist.net/Data\_structures/Hash\_table/Open\_addressing Instead of creating linked list in case of collision it searches for free bucket, so there is no linked list needed.

2) Assuming you have everything in advance, and it is simple as search only - perfect hashing will give constant time access and no need for pointers at all, it will be simple array of your type and hashing function as getter. For example: http://cmph.sourceforge.net

BST is 2n pointers + n values. AVL is 2n pointers + n or 2n integers + n values. RBT is 2n pointers + n values + n colors (boolean). As you decided to open hash table (open adressing strategy), you have m pointers (m is \> n, and biger is better) and n values. As open adressing is not degrading into linked lists but moves data to next empty cell. I assume that you create dynamically data structures, so empty node is only null pointer, so are leaves in trees. But even if some node is leaf, it still encodes 0 height to both childs.

# Answer
> 0 votes
As far as I have understood your question, you are asking just about the size requirement for both algorithms.

1. If you are using BST (Binary Search Tree) the size of your array depends on the number of elements you have. If it is a balanced tree, then you may require maximum of **n+2** elements. But if it is unbalanced or skewed tree then you may be in need of **n\*2** elements.
2. If you are using hash table, there is a factor called load factor. If you know the maximum limit of your elements, that is **n**, then you can keep the size of your array as **n** and you'll get maximum efficiency with **LF=1.0**. If you don't know the size of your elements (it may increase in future), you can initialize it with a **L.F.=0.75**. Your final size may be **x=n/0.75**.

One benefit with hash table is that you can fill all the locations available which is not the case with BST. In BST, an element can have only one appropriate place. Whereas, in hash table, you can insert the element in any next free available space.

> For hash table, you can refer to this Chosing a suitable table size for a Hash

---
Tags: data-structures, search-trees, hash-tables, balanced-search-trees, space-analysis
---


# Question
Title: Is the Projection Matrix estimated using least-squares pose specific?
I am calibrating a camera and estimating the projection matrix using the least-squares technique described here.

So far, I thought that the projection matrix that I got with this method was invariant, e.g., I could use it disregarding if the camera was moved or not.

However, I have been doing some additional reading, and I came across a set of slides that led me to believe that, if the camera is moved, then I'd have to estimate the projection matrix all over again.

Can someone please clarify this?

Thank you.

# Answer
> 2 votes
Yes, that is correct. If you move the camera, the projection matrix changes.

However, fortunately you don't have to start from scratch. If you know the new position of the matrix relative to the old one, you can adjust the projection matrix. Or, if you don't know how the camera has moved, you'll need to re-estimate the extrinsic parameters, but the intrinsic parameters will remain unchanged (the projection matrix is the composition of an intrinsic matrix and an extrinsic matrix, and only one depends on the camera's position).

See https://en.wikipedia.org/wiki/Camera\_matrix and https://en.wikipedia.org/wiki/Camera\_resectioning.

---
Tags: computer-vision
---


# Question
Title: How do you determine the number of errors in the Welch-Berlekamp algorithm?
In the Welch-Berlekamp algorithm for decoding Reed-Solomon codes, one is given a list of points $(a\_i, b\_i)$ representing a message with $e$ errors on the $b\_i$ in unknown locations (and $e$ is given to the algorithm). The output is a polynomial passing through all of the given points except those in which errors occurred.

The method involves solving a system of linear equations of the form

$$b\_i E(a\_i) = Q(a\_i)$$

for all $i$ where $E$ has degree $e$ and $Q$ has degree at most $e+k$. The variables are the coefficients of $E$ and $Q$.

To ensure that $E$ has degree $e$ one usually adds the constraint that the coefficient of $x^e$ is 1 to the linear system above. However, in practice one doesn't necessarily know $e$. One inefficient (but still polynomial time) way to deal with this is to try $e$ for all values starting with $(n+k-1)/2 - 1$ going down until a solution is found.

My question is: **is there a more efficient way to determine $e$?** Alternatively, is there a modification to the linear system that allows one to use an upper bound on $e$ instead of the exact value?

In particular I want to use this specific decoder for Reed-Solomon codes, and not a completely different algorithm based on other techniques.

---

In response to DW's answer, here is my working example. Everything is done modulo 7.

```
plain message is: [2, 3, 2]
polynomial is: 2 + 3 t^1 + 2 t^2
encoded message is: [[0, 2], [1, 0], [2, 2], [3, 1], [4, 4]]
corrupted message is: [[0, 2], [1, 0], [2, 3], [3, 1], [4, 4]]

```

So the error is in the third point.

When $e=2$ the polynomial equation in question is

$$b\_i(e\_0 + e\_1x + e\_2x^2) - q\_0 - q\_1x - q\_2 x^2 - q\_3x^3 - q\_4x^4 = 0$$

And plugging in $x = 0,1,2,3,4$ gives the system in matrix form:

```
[2, 0, 0, 6, 0, 0, 0, 0, 0]
[0, 0, 0, 6, 6, 6, 6, 6, 0]
[3, 6, 5, 6, 5, 3, 6, 5, 0]
[1, 3, 2, 6, 4, 5, 1, 3, 0]
[4, 2, 1, 6, 3, 5, 6, 3, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 1]

```

The last row is the constraint that $e\_2 = 1$. Applying Gaussian elimination we get

```
[1, 0, 0, 0, 0, 0, 1, 4, 0]
[0, 1, 0, 0, 0, 0, 3, 3, 1]
[0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 2, 1, 0]
[0, 0, 0, 0, 1, 0, 2, 2, 5]
[0, 0, 0, 0, 0, 1, 4, 5, 2]

```

And picking 1 for both free variables we get a solution vector of

```
[2, 2, 1, 4, 1, 0, 1, 1]

```

Which translates to

```
E is 2 + 2 t^1 + 1 t^2
Q is 4 + 1 t^1 + 0 t^2 + 1 t^3 + 1 t^4

```

And $E$ does not divide $Q$. Note that $Q$ factors as $(t + 6) (t^3 + 2t^2 + 2t + 3) \mod 7$

For $e=1$ I get a good solution:

```
system is:
[2, 0, 6, 0, 0, 0, 0]
[0, 0, 6, 6, 6, 6, 0]
[3, 6, 6, 5, 3, 6, 0]
[1, 3, 6, 4, 5, 1, 0]
[4, 2, 6, 3, 5, 6, 0]
[0, 1, 0, 0, 0, 0, 1]

reduced system is:

[1, 0, 0, 0, 0, 0, 5]
[0, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 3]
[0, 0, 0, 1, 0, 0, 3]
[0, 0, 0, 0, 1, 0, 6]
[0, 0, 0, 0, 0, 1, 2]

solution is [5, 1, 3, 3, 6, 2]
Q is 3 + 3 t^1 + 6 t^2 + 2 t^3
E is 5 + 1 t^1
P(x) = 2 + 3 t^1 + 2 t^2 # this is correct!
r(x) = 0

```

Note that while the counterexample above was generated by code I wrote from scratch (it was basically the first thing I tried), one can check the solutions are valid by hand, so even if my code is buggy it's still a valid counterexample to the claim that using $e=2$ works.

# Answer
> 5 votes
The same procedure actually works to correct any number of errors up to $e$.

The requirement is that the error polynomial $E(x)$ has to be zero at every point $a\_i$ where there was an error. Nothing says it has to be zero at only those points; you can have an $E(x)$ that is zero at other points too, and that's OK, as long as its degree is $e$.

So, if $e$ is an upper bound on the number of errors, there will exist a polynomial $E(x)$ with all the desired properties (i.e., has degree exactly $e$ and is zero at every point where there is an error). For instance, if there are fewer than $e$ errors, then there exists a polynomial $E(x)$ that's zero at every error, and zero at a few more points to get the number of zeros up to exactly $e$.

Finally, the correctness theorem says that if such a polynomial $E(x)$ exists, then the Berlekamp-Welch algorithm will be able to find it. So, even if there are fewer than $e$ errors, the procedure will still work correctly to identify $E(x)$. Once you have $E(x)$, you can identify $n-e$ positions that are error-free, and then you can decode in a straightforward way.

---

To document the result of the conversation about the "counterexample" in the question:

That's actually not a valid counterexample. The flaw was in the calculation of how many errors you should expect Berlekamp-Welch to be able to correct. The distance is $n-k+1$, so you should expect it to be able to correct up to $(n-k)/2$ errors (as Ran G. points out). In your counterexample $n=5$ and $k=3$, so $(n-k)/2=1$, so you should only expect this procedure to be able to correct one error, i.e., $e=1$. So, when you ran the procedure on an example with $e=2$, there's no reason to expect the procedure to work correctly.

So, the counterexample isn't actually a counterexample, and it doesn't contradict my answer above.

---
Tags: algorithms, error-correcting-codes
---