# Question
Title: What is the point of this lambda expression?
Let's take this lambda expression : $\lambda\\:x \\:\ast\\:x\\:2$ that "computes" `x * 2`.

From what I understand, $\ast$ is a constant operator, but since its nothing else than a symbol, how does that let us compute the multiplication `x * 2`?

I would have thought that we should have defined $\ast$ as some sort of recursive function for instance, but I can't understand why this is a constant and what is the point of using it if it doesn't directly compute the multiplication?

Thank you

# Answer
The “true” lambda calculus is defined by a syntax of terms: $$ M,N ::= x \\;\mid\\; \lambda x.M \\;\mid\\; M\\,N $$ and a reduction rule called beta reduction: $$ (\lambda x.M)\\,N \to M\[x \leftarrow N\] \tag{$\beta$} $$ (Plus context rules, plus the rules for alpha equivalence, but I'll omit them in this post.)

A lambda term is an object defined by the syntax above. What makes lambda terms interesting is the way they can be evaluated using the reduction rules.

It's possible, and common, to define extensions of the lambda calculus: languages that have additional syntactic forms and reduction rules. One common, simple extension is to add *constants* to the syntax of terms, and to add reduction rules called **delta rules** that allow evaluating these constants.

For example, we can define a new calculus which is the lambda calculus plus elementary arithmetic (LCPEA). If $n$ is a non-negative integer, I'll write $(n)\_a$ for a constant in the LCPEA, so the LCPEA has constants $(0)\_a$, $(1)\_a$, $(42)\_a$, etc. Note that what's in the parentheses is an integer, not a string: the constant is the same constant regardless of how the integer is written, so $(0)\_a$, $(3-3)\_a$, $(1+3-2\*2)\_a$, etc. are all the same constant.

$$ M\_a,N\_a ::= x \\;\mid\\; \lambda x.M\_a \\;\mid\\; M\_a\\,N\_a \\;\mid\\; (n)\_a \\;\mid\\; \mathord{+}\_a \\;\mid\\; \mathord{-}\_a \\;\mid\\; \mathord{\*}\_a $$ $$ \begin{align} (\lambda x.M\_a)\\,N\_a &\to M\_a\[x \leftarrow N\_a\] \tag{$\beta$} \\ \mathord{+}\_a (n)\_a \\, (n')\_a &\to (n+n')\_a \tag{$\delta\_+$} \\ \mathord{-}\_a (n)\_a \\, (n')\_a &\to (n-n')\_a \qquad \text{if \\(n \ge n'\\)} \tag{$\delta\_-$} \\ \mathord{\*}\_a (n)\_a \\, (n')\_a &\to (n\*n')\_a \tag{$\delta\_\*$} \\ \end{align} $$

The delta rules directly translate the arithmetic operators into the LCPEA. So the LCPEA effectively contains elementary arithmetic. Note that these delta rules are necessary if we want the new constants we introduced to do anything useful. It would have been possible to define a different set of delta rules that caused $+\_a$ to have nothing to do with addition and so on, but it would have been confusing.

It turns out that it is possible to define pure lambda terms (i.e. terms in the true lambda calculus) that reduce in the same way as corresponding terms in the LCPEA. That is, we can define a lambda term $\langle n\rangle$ for every natural integer $n$, as well as lambda terms $\langle\mathord{+}\rangle$, $\langle\mathord{-}\rangle$ and $\langle\mathord{\*}\rangle$ such that $$ \begin{align} \langle\mathord{+}\rangle \\, \langle n\rangle \\, \langle n'\rangle &\leftrightarrow\_\beta^\* \langle n+n'\rangle \\ \langle\mathord{-}\rangle \\, \langle n\rangle \\, \langle n'\rangle &\leftrightarrow\_\beta^\* (n-n')\_a \qquad \text{if \\(n \ge n'\\)} \\ \langle\mathord{\*}\rangle \\, \langle n\rangle \\, \langle n'\rangle &\leftrightarrow\_\beta^\* (n\*n')\_a \\ \end{align} $$ The Church numerals are a classical example of a set of such terms; there are others.

There are several reasons why we may want to define something like the LCPEA.

* One is that it is closer to how machines behave; this is important when using the lambda calculus to model compilers, but not when doing theory of computation.
* Another reason, applicable even when doing theory of computation, is that we often don't care exactly how the integers are encoded. So we might define things like $\langle 3\rangle$ and $\langle\mathord{+}\rangle$ as lambda terms, and then forget their precise definition and just remember some reduction rules for them. So they're still pure lambda terms, but we treat them as if they were part of an extended language.
* In a typed lambda calculus, encoding everything as functions is problematic, because we'd like to say that something like $1$ is “inert”, not like a function, and to say that $1 \\, 2$ (“1 applied to 2”) is not well-typed and does not reduce to anything. With the pure lambda calculus, $\langle 1\rangle \\, \langle 2\rangle$ does beta-reduce to something, but not to something useful. When we extend the language with constants, we don't define any reduction rule that would reduce $(1)\_a \\, (2)\_a$.
* There are extensions of the language that cannot be encoded as lambda terms at all. If we're interested in studying these, we have to extend the language.
> 5 votes

# Answer
This particular example seems to have been constructed in an extended language w.r.t. the basic lambda calculus.

Probably your book is just pretending the language is extended with a custom $\*$ symbol, which is postulated to perform multiplication.

Usually, arithmetic operators are either postulated (you introduce them as new symbols in the syntax, and you provide an adequate semantics to them) or defined in the language (if numbers are Church-encoded, for instance, one can actually define a $\lambda$-term $\*$ which works as expected).

Without knowing the context it's hard to tell.

It's also fairly common to introduce the lambda calculus pretending, for the sake of illustration, that these operators exist. This is because our previous experience about functions is mostly about functions operating on numbers. So it's (arguably) easier to start from there and then work out higher-order functions, and then finally (if we work with the untyped lambda) self-application. At the beginning it can be hard to understand it's functions all the way down, so a gradual step-by-step approach can be beneficial.
> 4 votes

---
Tags: lambda-calculus
---


# Question
Title: Is this language recursively enumerable?
Let $P=\\{L \mid \exists w\in \Sigma^\* s.t. w\in L \wedge \forall z\>w\colon z\in L\\}$ .

Now denote $L=\\{\langle M \rangle \mid L(M) \in P \\}$.

That is, $L$ is the set of all TMs $M$ s.t. there exists a $w\in \Sigma^\*$ s.t. $w$ is accepted by $M$ and for each $z\>w$, $z$ is accepted by $M$ as well.

I am trying to find out whether $L$ is in $RE$ or not.

I can easily show that $L$'s complement is $\notin RE$ using Rice's Theorem. But here, if using Rice's Theorem, I can only show that $L \notin R$, but I have no guarantee over $RE$.

I thought about using reduction - either to prove $L\in RE$ or to disprove, but none came about. I thought about using $L\_{acc}$ or its complement, $L\_{\Sigma^\*}$, but could not come up with an idea that will work for either direction of the reduction.

Could someone assist?

# Answer
> 1 votes
Thanks to @Yuval and @chi, I've been able to find a working reduction.

The reduction is $\overline{L\_{halt}} \leq L$. For an input $\<M\>\<w\>$ we build the following TM $N\_w$:

1. Runs $M$ on $w$ for $k$ steps, where $k$ is the length of the input for $N\_w$.
2. If $M$ was able to accept or reject $w$ within $k$ steps in the above simulation, $N\_w$ will reject. Otherwise, accept.

This way, if $\<M\>\<w\>\in \overline{L\_{halt}}$ then $M$ does not halt on $w$ for any length $k$, thus $N\_w$ will accept every string. Then, $L(N\_w)=\Sigma^\*\in P$ and $\<N\_w\>\in L$.

Else, if $\<M\>\<w\>\notin \overline{L\_{halt}}$ then a $n\in\mathbb{N}$ exists s.t. $M$ halts on $w$ within $n$ steps. Thus, for all inputs of length $\geq n$ the TM $N\_w$ will reject, and it will only accept inputs of length $ \< n$, and not satisfaying the property $P$. Hence, $\<N\_w\>\notin L$.

And since $\overline{L\_{halt}}\notin RE$, it follows that $L\notin RE$ as well.

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


# Question
Title: Smallest cost in weighted directed graph with combinations
I am trying to develop an algorithm that can traverse a graph with intermediary/all or nothing(?) nodes.

The problem is that there are companies B, C and D that are bidding on projects X, Y and Z. The companies can do individual bids for any of the projects, or they can say that they will complete a combination of projects for a total of x dollars. However this combination is all or nothing and cannot be split. I need to find the path with the least cost for all of X, Y and Z from the initial A (manager) node, that takes into account the combination of costs.

The following graph illustrates the problem that I am trying to solve:

A typical graph traversal algorithm would say that for `A -> X` the path `A -> B -> X` with cost 5, for `A -> Y` the path `A -> C -> Y` with cost 4 and for the path `A -> Z` the path `A -> C -> Z` with cost 6 should be taken. Making the cumulative total be 15.

However, introducing the idea of an intermediary/combination node, would say that for `A -> X` the path that should be taken would be `A -> B -> X` with cost 5. Then for `A -> Y` and `A -> Z` it should share the cost and take `A -> D -> DL -> Y` combined with `A -> D -> DL -> Z` with the lump sum of 8. This would result in the lesser cost of 13.

Some general notes are that this is a very small example of the overall problem that I am trying to solve. At any given time there can be many companies and many projects (100+), and additionally, there can be may bids/edges between the companies and projects and there can be many combinations/lump sum bids.

The could explain the problem best using a graph but it doesn't necessarily mean that it is the best solution. It almost seems to me to be graphing up front, but then introducing the combination nodes makes it seem like a derivative of the knapsack problem. I appreciate any help or direction.

**edit** Typically there will be 20 companies and anywhere from 20-100 categories. Typically the number of bids will be (companies) * (categories) where 20% of the bids are combinations. So if there are 2000 bids approximately 400 could be a combination bid. The number of projects in a combination could make up only min + 1 or all of the categories.

# Answer
> 5 votes
You can formulate problems like this as an integer program and apply off-the-shelf tools to find (near) optimal solutions.

The example is rendered something like this (the exact syntax depends on the tool).

```
minimize 5*BX + 10*BZ + 4*CY + 6*CZ + 10*DX + 7*DYZ
subject to
BX + DX = 1  # project X is done once
CY + DYZ = 1  # project Y is done once
BZ + CZ + DYZ = 1  # project Z is done once
binary variables BX, BZ, CY, CZ, DX, DYZ in {0, 1}

```

The interpretation of, e.g., `DYZ` is that `D` is awarded the package of contracts for `Y` and `Z` if and only if `DYZ` has value `1`.

# Answer
> 2 votes
Your problem is called weighted set cover. Each set corresponds to a bid (a combination bid corresponds to a set of size larger than one; a single bid corresponds to a set of size one). The cost/weight of each set is the dollar amount of that bid. You then want to find a set cover -- a combination of sets whose union covers all of the projects -- i.e., a combination of bids that ensures all projects will be completed.

As a result, your problem is NP-hard, and you should not expect any algorithm that efficiently finds the optimal solution for all possible problem instances. You'll probably have to give up something: either accept that the algorithm might not be fast for arbitrarily-large problem instances; or that it might give incorrect answers for some problem instances; or accept sub-optimal solutions; or find some special structure in your problem instances that you can exploit.

The weighted set cover problem has been studied in some depth. If you want an exact solution, the standard approach is to use integer linear programming. If you want an approximation algorithm (an efficient algorithm to get a solution that probably won't be optimal but will be not-too-far from optimal), you can use the standard greedy algorithm -- though in practice this probably won't be useful, as it means you might pay a $\log n$ factor more than necessary, where $n$ is the total number of projects to be completed.

---
Tags: graphs, np-hard, knapsack-problems
---


# Question
Title: Showing an equivalent definition of $CO-RE$
Let $L\_1$ be a language.

I would like t prove that $L\_1\in CO-RE$ if and only if exists a language $L\_2$ s.t. $L\_1=\\{ u\\,\\, |\\,\\, \forall\_{v\in\Sigma^\*} : \<u,v\>\in L\_2 \\}$ and $L\_2\in R$.

I'm not quite sure on where do I start here from?

I've tried writing down what I know and trying to develop any ideas, but got stuck at the very begining.

Since $L\_1\in CO-RE$ then $\overline{L\_1} \in RE$. That is, exists a TM $M$ s.t. $M$ accepts any $u\in \overline{L\_1}$ (that is $u\notin L\_1$) and either rejects or loops forever for $u\in L\_1$.

But I dont see how does this assist me to construct such a language $L\_2$ that will both be in $R$ and assist me?

And even if I do succeed, how am I to show the other way around - that if such a language $L\_2$ exists that satisfies the above conditions, $L\_1\in CO-RE$?

# Answer
Equivalently: $\overline{L\_1}$ is RE iff there is some $\overline{L\_2}$ that is $R$ so that $\overline{L\_1}=\\{u | \exists v : \<u,v\>\in \overline{L\_2}\\}$ is RE.

* $\Rightarrow$

Take $\overline{L\_2}=\\{\<u,v\> | v\text{ represents an execution accepting u in the MT accepting }\overline{L\_1}\\}$. It's R because you just simulate the MT following v and it'll either work or not. And it vefiries the property $\overline{L\_1}=\\{u | \exists v : \<u,v\>\in \overline{L\_2}\\}$ because a word is accepted iff some execution accepts.

You could also take $\overline{L\_2}=\\{\<u,n\> | u\text{ is accepted by an execution of size} n\\}$.

* $\Leftarrow$

Enumerate all $v$, for each, test is $\<u,v\>\in\overline{L\_2}$ and if it is, accept. If the word is in $\overline{L\_1}$ then some $v$ will work so it'll be accepted. So $\overline{L\_1}$ is indeed RE.

---

Your property says is that being RE is the same thing as being the projection of a R set.
> 2 votes

---
Tags: computability, semi-decidability
---


# Question
Title: Can I prove that I have x such that f(x) < c without revealing x?
I'm interested in applications to verifiable computing. Let's say Alice would like to find an x such that f(x) \< c for some real-valued function f and some c of Alice's choosing, so she hires Bob who has a powerful computer. Bob finds such an x, but he doesn't want to give it away before receiving payment from Alice, but at the same time Alice doesn't want to pay Bob before she is sure he has a sufficient value of x.

Is there a way for Bob to prove to Alice that he has such an x without revealing what the value of x is?

This can be done with a fully homomorphic encryption of f, right? For example Bob can demonstrate the equivalent inequality on the encrypted f and encrypted c for the encrypted x, and Alice can verify the encryption scheme on f and c, but this does not reveal x.

Is there any way that is less computationally expensive - even if for only certain types of functions f? Is there a partially homomorphic encryption scheme that will suffice? Or some other type of zero knowledge proof?

# Answer
> 4 votes
If the function $f$ is publicly known and is efficiently computable, it is possible for Bob to prove that he knows a value $x$ such that $f(x)\<c$. This is known as a zero-knowledge proof of knowledge. There's lots written on zero knowledge proofs; you can go read about them.

In particular, given any predicate $\varphi(x)$ that is computable in polynomial time, there exists a polynomial-time zero-knowledge proof of knowledge that you know $x$ such that $\varphi(x)$. If $f$ can be computed in polynomial time, then the predicate $f(x)\<c$ can certainly be tested in polynomial time, so it can also be proven in zero knowledge in polynomial time.

However, that is not enough to solve the ultimate problem you want to solve. It sounds like what you ultimately want is a fair exchange protocol. Sadly, such protocols typically aren't super-realistic, if you want them to be "all-digital" and avoid any trusted parties; if Alice and Bob know each other and have some kind of relationship, you're probably better off signing a contract. But if you want to read about the topic, you can start with https://crypto.stackexchange.com/q/8333/351 and https://crypto.stackexchange.com/q/8352/351 and continue reading from there.

---
Tags: optimization, distributed-systems, encryption
---


title: Deciding whether a CFG is parity absent

text:
# Question
Title: Deciding whether a CFG is parity absent
Suppose that $\Sigma = \\{c\_1, \dots, c\_m\\}$ is some finite alphabet and supposing $s \in \Sigma^\*$, let $\mathcal{I}\_j(s)$ denote the number of instances of character $c\_j$ in $s$. Call a string $s$ *odd-parity absent* iff $|\\{j : \mathcal{I}\_j(s) = 0\\}|$ is odd. That is, $s$ is odd-parity absent iff an odd number of characters from the alphabet are missing from $s$. Call a language $L \subseteq \Sigma^\*$ odd-parity absent iff every string in $L$ is odd-parity absent.

Now, suppose that $G$ is a CFG. I'd like to come up with an algorithm for deciding whether or not $L(G)$ is odd-parity absent.

I thought it'd make things simpler if we first convert $G$ into an equivalent Chomsky-normal form grammar. Now, If I could determine what types of terminal strings each variable yields in the grammar (e.g., variable $A$ yields strings with a's and strings with a's and b's, etc.) then I could just inspect the right-hand sides of the start variable rules. But $A$ of course can yield a whole bunch of different variables along the way to derive a string of terminals, and each of those variables can yield a whole other bunch of different variables along the way, etc.

# Answer
One option to generate the parse tree of the grammar, and check all the leaf strings if they are *odd-parity absent*. Even if you have recursive rules, one application of each rule is enough, because multiple occurrences of the same element does not affect the result.

However, there might be an easier way. Consider the following grammar on `{a,b,c,d,e}` alphabet with the following rules:

* S -\> A | B
* A -\> Abc | C
* B -\> cd | De
* C -\> aa
* D -\> b

Now you can assign odd-parity variables to each state. For example, a string at state S has `number of missing instances = m` (`m=5` in this case). Let's denote it with `p(S)=5`.

From the first rule, `p(A)=p(B)=p(S)=5`. At the second rule, `p(A)` becomes 3, because at the first branch it eliminates 2 missing characters. Also `p(C)=3`, because `p(A)=p(C)`, all other elements are missing.

At the third rule, `p(B)=3` and `p(D)=4`. Fourth rule indicates `p(C)=2` (2 `a`'s, but the same element). Finally, `p(D)=3`.

Checking all ending states, `p(B)=3`, `p(D)=3`, and `p(C)=2`, which means the grammar has odd-parity. Verbally, there might be strings that end up with 3 elements missing, if they end up in state `B` or `D`.

In this way, you can decide if the grammar is odd-parity absent, just by looking at the grammar. The pseudo-code would be:

```
consumed_elements_set(S)={}
for each rule X with L as left-hand side:
    for each state R on the right hand side:
       consumed_elements_set(R)=consumed_elements_set(L)+terminals(X)
       p(R)=m-size(consumed_elements_set(R))
for each final state F:
    if p(F) is odd:
       print "not odd-parity absent!"

```
> -1 votes

---
Tags: algorithms, context-free, formal-grammars, decision-problem
---


# Question
Title: How to calculate the average of x numbers?
I just started a college course and I'm being asked for a flowchart where I explain how to calculate the average of x quantity of numbers. For this assignment I'm asked to follow the problem solving steps, which are:

1. Identify the problem.
2. Comprehend the problem. (As in, "is it mathematical?")
3. Identify different alternatives to solve the problem.
4. Selecting the best alternative to solve the problem and why.
5. Construct a list of instructions that allows to solve the problem.
6. Evaluate the solution.

After this I need the make a flow chart of the steps of pseudo-code. All of this is for a course called Structured Programming where we are supposed to learn Java.

I want to make clear that I don't want you to do my assignment I just want an explanation on how to do it, what should be the function I use and how to structure the flowchart.

# Answer
Instead of giving an answer, I will try to paraphrase the steps, I hope this will help you solve your homework.

1. Identify the problem: What is the input? What is the output?
2. Comprehend the problem: Can you write a formula for the problem, that relates input to the output? What is the formula for the average of x numbers?
3. Identify different alternatives to solve the problem: How can you implement that formula? As a closed-form function? With an iterator? Solving recursively?
4. Selecting the best alternative to solve the problem and why: Which one did you select in step 3, and why?
5. Construct a list of instructions that allows to solve the problem: Write the pseudo-code about how you can actually implement the solution you selected on step 3.
6. Evaluate the solution: Is it working? How well is it working? Are there any conditions that it is not working? What are they? How long does it take to produce an answer?

I hope that you are actually stuck and these explanations can guide you. Else I will regret my decision to help someone that actually looks for a ready-to-jump-on solution for his homework.
> 3 votes

---
Tags: average-case, java
---


# Question
Title: Programming language semantics prototyping tool
Is there any tool for prototyping a programming language semantics and type system and that also allows for some sort of *model checking* of standard properties, like type soundness?

I'm asking this, because I'm reading a book on Alloy and it provides the exact functionality that I want, but for models expressed using relational logic.

I'm aware of Ott, but it does not have this sort of "model checking" capability, since it is focused on generating code for proof assistant systems.

Any reference on such tool existence would be nice.

# Answer
Although there are frameworks created specifically for the purpose of prototyping programming languages (including their semantics, type systems, evaluation, as well as checking properties about them), the best choice depends on your particular case and specific needs.

Having that said, there are multiple (perhaps not so distinct) alternatives you might take (which includie the ones you've already mentioned):

* using a specific language/framework designed for creating and prototyping new languages: as an example, Redex \[1\], a domain-specific language embedded in Racket for specifying and checking (operational) semantics of programming languages, which, given a definition of a language, provides easy handling of tasks such as typesetting (in Latex), inspecting traces of reduction, unit tests and random testing (e.g. for checking typing)
* using general modelling languages that offer defining and performing certain analyses easily, as long as they can capture the specific language at hand to the needed extent; Alloy \[2\] is an example of such an approach: albeit pretty general and flexible, languages can be modelled as relations between states, while the support for model checking (e.g. evaluation within such language) comes for free after the semantics is expressed with a relation model (e.g. some ideas for modelling semantics of a language can be found in \[3\])
* embedding the language to check its properties using a theorem prover; an example would defining the language as well as its semantics by embedding it in a proof system like Coq \[4\] (more details about this approach, as well as discussion and demonstration of the difference between deep and shallow embedding in Coq is given in \[5\])
* using Ott (as already mentioned, with similar in spirit as Redex, but providing a new definition language rather than being embedded); Ott allows you to define the programming language in a convenient notation, and produce typesetting and definitions in a proof system (usually with deep embedding), where most of the checking (i.e. proof) needs to be performed manually
* developing the language and its semantics, as well as appropriate checks (e.g. as tests) "from scratch" in a general-purpose programming language and translation into other systems if need be, for checking purposes (some languages, like Leon \[6\], include built-in verifiers, which allow automatically proving certain properties and make this approach similar to embedding in a proof system)

Note that there is the trade-off between how easy is to use the framework/tool (e.g. as easy as laying out the definition on paper or in Latex) and how powerful the mechanisms for checking the properties about the language are (e.g. embedding the language in a theorem prover can allow checking very elaborate properties).

\[1\] Casey Klein, John Clements, Christos Dimoulas, Carl Eastlund, Matthias Felleisen, Matthew Flatt, Jay A. McCarthy, Jon Rafkind, Sam Tobin-Hochstadt, and Robert Bruce Findler. Run Your Research: On the Effectiveness of Lightweight Mechanization. POPL, 2012.

\[2\] Daniel Jackson. Alloy: a lightweight object modelling notation. TOSEM, 2002.

\[3\] Greg Dennis, Felix Chang, Daniel Jackson. Modular Verification of Code with SAT. ISSTA, 2006

\[4\] Coq formal proof management system

\[5\] Formal Reasoning About Programs. Adam Chlipala, 2016

\[6\] Leon automated system for verifying, repairing, and synthesizing functional Scala programs
> 8 votes

---
Tags: reference-request, programming-languages, semantics, model-checking
---


title: Ambiguity in choosing the best ER model

text:
# Question
Title: Ambiguity in choosing the best ER model
I am actually little bit confused when I am reading through the text - Database system concepts by Henry F. Korth and others

I won't be able to understand one thing, which one of the following models I have to use when I have to design the ER diagram.

As the textbook says:

> We are going to treat the telephone as an entity when one may want to keep extra information about a telephone such as its location, or its type (like mobile, video phone or a plain telephone etc) or all who share the telephone. Thus, treating telephone as an entity is more general than treating it as an attribute

What I want to clarify is: If I draw the ER diagram by choosing **telephone** as a *composite attribute* having component attributes: **telephone\_number** and **location**. Then I can also define the same way as an entity can do. Is it not correct to do it like this way?

If it is correct then what to use and when? If it is incorrect then why is it so.

**one reason** may be one person cannot have multiple phone numbers but we can design the same by making telephone as multi-valued attribute. So where I am going wrong?

# Answer
**If I draw the ER diagram by choosing telephone as a composite attribute having component attributes: telephone\_number and location.** In this case the DB Table for `Employee` will have 2 more columns `telephone_number` and `telephone_location`. This will lead to repetition which can lead to inconsistency.

Suppose, 2 different Employees (with id 1 and 2 respectively) share

* `telephone(111111, london)` and
* `telephone(222222, paris)`

```
Employee(id, name, street, city, telephone_number, telephone_location)

(1, xyz, abc, pqr, 111111, london)
(1, xyz, abc, pqr, 222222, paris)
(2, qwe, der, vfr, 111111, london)
(2, qwe, der, vfr, 222222, paris)

```

In above instance of table, not only the information is repeated but it creates a dependency `telephone_number -> telephone_location` which can lead to inconsistency , say if `telephone_location` of `111111` is changed from `london` to `austria` then, due to dependency you need to change `telephone_location` value in `(2, qwe, der, vfr, 111111, london)` also. If forgotten then it will lead to inconsistency.

**We are going to treat the telephone as an entity...** In this case there will be a relationship entity which will translate to a independent DB Table (`emp_telephone`) having 2 columns `Employee_id` and `telephone_number`. Therefore, the table instances will look like:

```
Employee(id, name, street, city)
(1, xyz, abc, pqr)
(2, qwe, der, vfr)

telephone(telephone_number, telephone_location)
(111111, london)
(222222, paris)

emp_telephone(Employee_id, telephone_number)
(1, 111111)
(1, 222222)
(2, 111111)
(2, 222222)

```

So, in above table instances no information is repeated and individual attribute/column value in table `Employee` and `telephone` can change independently yet linked via relationship `emp_telephone`.

Lastly, **if `telephone` is kept as multi-valued attribute** then it will lead to creation of a table similar to `emp_telephone(Employee_id, telephone_number)` in which each value of multi-valued attribute `telephone` along with primary-key of Employee will be kept.

That is:

```
Employee(id, name, street, city, telephone)
(1, xyz, abc, pqr, 111111/222222) //<-- note telephone is multi-valued
(2, qwe, der, vfr, 111111/222222) //<-- note telephone is multi-valued

```

will translate to

```
Employee(id, name, street, city)
(1, xyz, abc, pqr)
(2, qwe, der, vfr)

emp_telephone(Employee_id, telephone_number)
(1, 111111)
(1, 222222)
(2, 111111)
(2, 222222)

```

So, from above it seems that the conclusion is, if an entity has a composite attribute which can be shared then such attribute should be kept as separate entity.
> 1 votes

---
Tags: database-theory, databases, modelling
---


title: Understanding CLRS BFT lemma

text:
# Question
Title: Understanding CLRS BFT lemma
I was reading BFT from CLRS. This is the example given in the book:

(Figure:The operation of BFS on an undirected graph. Tree edges are shown shaded as they are produced by BFS. The value of $u.d$ appears within each vertex $u$. The queue $Q$ is shown at the beginning of each iteration. Vertex distances appear below vertices in the queue.)

Then it gives following lemma:

> Suppose that during the execution of BFS on a graph $G=(V,E)$, the queue $Q$ contains the vertices $\<v\_1,v\_2,...,v\_r\>$, where $v\_1$ is the head of $Q$ and $v\_r$ is the tail. Then, $v\_r.d\leq v\_1.d+1$ and $v\_i.d\leq v\_{i+1}.d$ for $I=1,2,...,r-1$.

I am ok with $v\_i.d\leq v\_{i+1}.d$ for $I=1,2,...,r-1$ as I can observe this in all queue instances above. But I am not able to understand how $v\_r.d\leq v\_1.d+1$ aligns with above, as $i\<i+1$, but $r\>1$. How that $+1$ is making whole difference?

# Answer
Suppose you have a tree like

```
        a           <-- level = 0
      / | \
     b  c  d        <-- level = 1
   /
  f                 <-- level = 2

    v1, v2, v3
Q : b,  c,  d
    1,  1,  1

v3.d <= v1.d + 1   i.e 1 <= (1+1)

```

Now, suppose head of Q (i.e `b`) is removed and its neighbors are inserted in Q

```
    v1, v2, v3
Q : c,  d,  f
    1,  1,  2

v3.d <= v1.d + 1   i.e 2 <= (1+1)

```

This, `v3.d <= v1.d + 1` can be also be seen as `v3.d - v1.d <= 1` which means at any point of time distance between elements of queue will always be `less than or equal 1`. This can also be seen from the fact that during the execution of BFT only elements from 2 successive levels are present in queue. There cannot be case such that 2 elements `A` and `B` are present in queue with `A` at `level x` and `B` at `level (x + 2)`.
> 1 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Is there any difference between the terms userland and userspace?
Sometimes I read about the term userland and sometimes userspace.

From Wikipedia, it is said that userland is referring userspace: https://en.wikipedia.org/wiki/Userland

Is there any difference between the terms userland and userspace?

# Answer
Taken from yourdictionary.com

> **Userland:** (computing, informal) A conceptual space outside the kernel in which a user's applications can run without the risk of damage to the operating system.
>
> **Userspace:** (computing) The area of memory used for a user's applications, etc., as opposed to that reserved for the operating system
> 1 votes

---
Tags: terminology
---


# Question
Title: How do you find all integers in a sorted array of size n that appear n/k times, given that 0 < k < n, and in O(k log n) time?
This looks like a typical divide and conquer algorithm, but with a few tricky parts.

It looks like we want to do k operations and divide the array in half at each step because of the O(k log n) restriction, but I'm confused about the specifics. When I try to come up with the algorithm, I think about making k comparisons with varying elements that are ceil(n/k) apart, but I don't see how recursively doing anything like that with broken up halves of the array would do anything beneficial.

Given this sorted array:

A = \[1, 2, 3, 4, 4, 4, 4, 5\]

If k = 1, then we do one comparison between A\[0\] and A\[7\] and we're done.

If k = 2, we can't do much because there's no good way to make 2 meaningful comparisons. And if we're going to split it in half and check again to fulfill the log(n) time requirement, the 4's would get split up.

Any ideas?

# Answer
Let m = ceil \[n/k\], so you want numbers occurring m or more times. Since the array is sorted, if you check array elements a \[m-1\], a\[2m-1\], a\[3m-1\] etc. you find all the integers you want (and some you don't want).

So you start with x = a \[m-1\]. If x == a \[2m-1\] then you found a number, and you can remove a\[3m-1\], a \[4m-1\] etc. as long as they are equal to x.

If x != a \[2m-1\], then you use binary search to find the largest i from m-1 to 2m-2 that is equal to x, and check whether x = a \[i - m + 1\]. That's the idea, you have to be a bit careful to implement it.

Since at most you do k binary searches in subarrays of length m, the time is O (k log m) = O (k log (n / k)) which is quite a bit better than O (k log n) when k is large (and if k is small then the execution time is small anyway).

A bit more careful implementation: You want to find all integers in a sorted array that occur at least m times. Let's call these integers "heavy". Let c = 0; throughout the algorithm you have found all heavy numbers before a \[c\], and there is no array element before a \[c\] that is equal to a \[c\].

If c + m - 1 ≥ n then you are done. Otherwise let i = c + m - 1 and x = a \[i\]. There can be no element in a \[c\] to a \[i - 1\] that is heavy and different from x, so the question is whether x is heavy.

Let j = i; and as long as j + m \< n and a \[j + m\] = x, let j = j + m. Use binary search to replace j with the largest index from j to min (j+m-1,n-1) containing an element equal to x. So now a \[i\] to a \[j\] are all equal to x, and there is no element at a \[j+1\] equal to x.

If j ≥ i + m - 1 or a \[j - m + 1\] == x then x is heavy. In any case, replace c with j + 1 and continue.

We increase c at least by m at the cost of one binary search in an array of length m or less, or we increase c by m again in constant time.

PS. You could improve the execution time slightly as follows: You always check for the last number in an interval of size m-1 which is equal to x. Depending on where that last number is found, the algorithm makes more or less progress. To improve the worst case, you replace binary search by something slightly less balanced that is faster when the result is at the left end of the interval, so that there is less work if there is less progress.
> 1 votes

# Answer
Let ***t = $\frac{n}{k}$***

```
Set counter c = 0

Set variable s = 0

1.Check if A[s] == A[s + t-1]. (Since the array is sorted,
        this means that the first t elements are equal)

    2.1 If yes, check if A[s] != A[t+s]. (This is to ensure that there are
    not more than t copies of A[s])

        3.1 If yes this means that the element A[s] occurs
        exactly t times => Set c = c + 1

        3.2 If no, set s to the index of the first number in A,
        which is greater than A[s] (you can do this using a slightly modified
        binary search in log(n) time)

    2.2 If no, set s to the index of the first occurrence of A[s + t-1]
    (again, you can do this in log(n) time using modified binary search)

```

You can check that the worst case for this algorithm is an array of the type

A = { 1, 2 ... 2, 3, 4 ... 4, 5, 6 ... 6, ... } where the numbers with ... appear **t** times. This is **2k - 1** binary searches so $O(k\log{}n)$
> 1 votes

---
Tags: time-complexity, sorting, arrays, divide-and-conquer
---


# Question
Title: Can the following conditions hold all together?
Let $L\_1, L\_2$ be languages.

Can the following conditions hold:

1. $L\_1,L\_2\notin RE$.
2. $L\_1\cap L\_2\in R$
3. $L\_1\cup L\_2\in R$
4. $\overline{L}\_1, \overline{L}\_2 \in RE / R$

I believe the above cannot hold at the same time. I thought since $L\_1\cap L\_2\in R$ and $L\_1\cup L\_2\in R$ then $\overline{L}\_1\cup \overline{L}\_2\in R$ and $\overline{L}\_1\cap \overline{L}\_2\in R$. Then I know that $L\_2 \ L\_1 = L\_2 \cap \overline{L\_1}$. And now I want to somehow use condition 4 to reach a contradiction, but I don't see how...

Or perhaps I'm wrong and they can hold together?

# Answer
Conditions $2,3,4$ imply $L\_1 \in RE$, contradicting $1$.

Here's how to semi-decide $L\_1$. Take a candidate $x$. If $x \in L\_1 \cap L\_2$ (decidable by $2$), accept. If $x \notin L\_1 \cup L\_2$ (decidable by $3$), diverge (we know $x \notin L\_1$ for sure).

We now know that $$x \in (L\_1\setminus L\_2) \cup (L\_2\setminus L\_1) \qquad (\*)$$

Exploiting $4$, we run semi-deciders for $\overline{L\_1}, \overline{L\_2}$ on $x$ in parallel. By $(\*)$, (exactly) one of these must eventually halt.

If the former halts, we infer $x \notin L\_1$, so we diverge. If the second one halts, we infer $x \notin L\_2$, and by $(\*)$ we obtain $x\in L\_1$, so we accept.
> 6 votes

# Answer
I voted for the answer by chi, as it gives a nice explanation how the algorithm is stringed together.

At the same time I wondered whether there would be an "abstract" solution where one uses basic facts about recursive and recursively enumerable languages. (If you reconsider chi's construction after reading my answer you will recognize the ingredients.)

Now, if I am not mistaken \[but we will not use the fourth fact, thanks to an idea of chi in the comments\],

* $R$ is closed under boolean operations,
* $RE$ is closed under intersection and union,
* $R\subset RE$, and
* if both $L$ and $\overline L$ are in $RE$, then $L$ is in $R$.

Note that, by 2,3 the intersection $L\_1\cap L\_2$ and the union $L\_1 \cup L\_2$ are in $R$, and hence in $RE$.

Then by 4, $L\_1 = ((L\_1\cup L\_2) \cap \overline{L\_2}) \cup (L\_1\cap L\_2)$ is in $RE$.

Now $L\_1$ is in $RE$, contradicting 1.
> 2 votes

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


# Question
Title: NP Problem that cannot be solved by a quantum computer in polynomial time
1. Is there any NP-Problem that can't be (maybe even proven) solved by quantum computers. I'm not talking about quantum NP-Problems (if that's even a thing), but about normal NP.
2. If that NP Problem exists could you also use it for cryptography, since I don't want to buy a quantum computer just to be secure.

EDIT: I'm not talking about NP-complete, because that would have no use (I think) in cryptography and also not about symmetric key encryption.

# Answer
> 4 votes
Nobody really knows whether quantum computers can solve all NP complete problems in polynomial time or not. There is strong evidence that they cannot: Strengths and Weaknesses of Quantum Computing, but no definite proof.

---
Tags: complexity-theory, np, cryptography, quantum-computing
---


# Question
Title: Is this language $\{0^n1^m | (n+m) \text{is even}\}$ regular or not?
$$L=\\{0^n1^m | (n+m) \text{is even}\\}$$

1. Using the pumping lemma , let me choose a valid string $W=0011$ $(n=2,m=2$ and $4$ is even$)$.
2. Let the number of states in the DFA ($C$) be $3$ (I find this step to be fishy)
3. $|W|\ge C$
4. Let $W=XYZ$
5. I choose $X=00,Y=1,Z=1$ such that $|xy| \le C ,|Y| \ge1$
6. So, for all $i$, $00(1)^{i}1$ should be in $L$
7. But when $i=2$,String $00111$ is not in $L$, hence this language is not regular.

But I came across a regular expression for the same language:

$$0(00)^\*1(11)^\*+(00)^\*(11)^\*$$ Is there a flaw in my pumping lemma or the regular expression? Someone please help me out.

# Answer
You seem to have misunderstood the pumping lemma.

Taking the definition from Introduction to the Theory of Computation by Michael Sipser

> If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:
>
> 1. for each $i ≥ 0, xy^i z \in A$,
> 2. $|y| \> 0$, and
> 3. $|xy| \le p$.

A few points:

* The lemma only says that *a pumping length $p$ exists*. You do not get to choose the value of $p$. So, you cannot say that let $p=3$.
* For every string $s$ in the language with length at least $p$, it *may be divided into three pieces, $s=xyz$*. Notice that this again talks only of the *existence of a way* to split $s$ into $xyz$ *given that $A$ is regular*. So, you do not get to choose how the string splits into $x$, $y$, and $z$ in the general case. Finding a split that does not satisfy the conditions does not show that the language is not regular. You need to find such a string that *cannot* be split as stipulated by the definition to show that a language is not regular.
* Finally, the pumping lemma does not say what happens if $A$ is not regular. So, even a non-regular language may satisfy it, and the pumping lemma cannot be used to show that a language is regular.
> 2 votes

# Answer
You pumping lemma is wrong. The pumping lemma only works on strings that are sufficiently long, yours is not. If we have a string that is sufficiently long(longer then the number of states in the corresponding dfa or nfa) we must have repeated some states, which means that there is a loop somewhere in the path through the dfa to generate this string. We can then infinity repeat this loop and the string is still valid. Your string of length 4 is not sufficiently long to use the pumping lemma on. The language is regular. There are only 2 situations regarding valid strings in this language. If the number of 0's is even, the numbers of 1's is even. And if the number of 0's is odd the number of 1's is odd. Your regular expression covers both of these.
> 1 votes

---
Tags: formal-languages, regular-languages, regular-expressions, pumping-lemma
---


# Question
Title: Why is randomness a problem? (i.e. why do we care about derandomization?)
I'm reading Aaronson's survey on P vs. NP, and I've come to understand that in CS theory, people *really* care about derandomization results like P vs. BPP etc. My question is, what's the problem with randomness? If your algorithm is known to only require a polynomial number of random bits, then simply go ask a physicist to get the bits for you, which isn't a problem since you only need a tractable number of them, and then write them on the Turing machine tape and you're good! The goal of complexity theory is to figure out what we can compute in this universe, right? Well, this universe has randomness, right? So why do we care about derandomization? Theoretical and practical answers are both welcome.

# Answer
> 9 votes
Complexity theory is a mathematical theory which aims at addressing one shortcoming of computability theory, namely, it takes into account the use of resources. While it is true that in its early days it aimed to capture the notion of "practical computation" (even particular flavors such as parallel computation, supposedly captured by NC), it has since drifted apart and taken off from reality. As an example you can take higher steps on the polynomial hierarchy, higher complexity classes such as PSPACE, classes defined using alternation, and so on. Indeed, much of this material dates to the early days of complexity theory, showing that it lost touch with reality quite quickly.

Traditionally the two most important resources studied by complexity theory are time and space. However, other resources have also interested complexity theorists, for example alternation and randomness (not to mention the world of circuit complexity). Philosophically speaking, it is a fascinating question whether randomness dramatically reduces the computation time of some problems, or whether the gain is only polynomial (as hinted by the conjecture P=BPP). However, it does not seem to have any practical relevance, though not for the reason you mention. In practice there is no need for actual physical randomness (other than for cryptographic purposes), and pseudorandom number generators work well enough.

# Answer
> 2 votes
I'm not a complexity theory specialist, but I think there are somewhat practical reasons to be interested in this question.

1. As noted by Derek Elkins, actually producing "physical" random numbers is quite difficult, and producing the right distribution with the right amount of entropy at sufficient speed is hard enough to justify web sites and custom hardware. It would be nice to know this can be avoided, at least in theory.
2. In classical physics, there is no "true" randomness, just the (deterministic) physical laws and the initial conditions of the system (or the whole universe, I guess). It's an interesting philosophical question whether this randomness is equivalent to true randomness in some sense. This question finds answers in the fields of chaos theory, the theory of ergodic processes and in computer science, in questions like P vs BPP.
3. The question of whether we can accurately simulate randomness in P vs BPP seems very related to the question of whether we can truly do encryption, say, the existence of trapdoor or one-way functions. In particular, the ability to deterministically produce bits that "look random" enough for any particular algorithm seems like a good prerequisite to finding a cryptographic function which encrypts a given message into a stream of bits indistinguishable from random bits, **if the key is not known**. So solving the very hard question of existence of one-way functions *should* require solving P vs BPP along the way.

---
Tags: complexity-theory, randomized-algorithms, randomness
---


# Question
Title: What is the time complexity for getting the size of a heap?
Assuming the regular Heap ADT.

What is the time complexity of getting its size ?

I tend to think that because insert is O(log(n)), then I always know the last index of my heap. So in order to get its size all I need is to return the last index + 1.

However I have seen in some places that refer to the size of the heap's complexity as O(n), since I need to count all the nodes in my heap.

Why am I wrong ?

# Answer
If you're talking about an ADT, you can't really say. It depends on the implementation. You can certainly do it in O(1) (for example by keeping a counter).
> 7 votes

# Answer
Depends on how you implement your ADT heap. You can expand `size` as a counter of `next` operations. In that manner, if you are using

* an external counter: $O(1)$
* a stack: $O(n)$
* a binary tree: $O(logn)$
* a hash: $O(k)$ ($k$ is the average collisions)
> 4 votes

---
Tags: data-structures, heaps
---


# Question
Title: Is every language in PTime also context-sensitive?
Context-sensitive languages are exactly those that can be recognised using linearly bounded automata, i.e., those in NSPACE(O($n$)). This subsumes all languages that can be recognised in linear time, i.e., DTIME(O($n$)), since you can only use n memory cells in n steps.

However, this leaves open the possibility that some super-linear polynomial time problems are not context-sensitive. Is this likely or even known? Are there examples?

Here are some general facts that one should be aware of:

1. There are PSpace-complete problems in NSPACE(O($n$)), e.g., TrueQBF. One might think that this answers my question, since PTime is contained in PSpace.
2. However, not all PSpace-complete problems are in NSPACE(O($n$)). Indeed, we know that there are strictly more languages in NSPACE(O($n^2$)) than in NSPACE(O($n$)) (space-hierarchy theorem). In other words, PSpace is strictly larger than NSPACE(O($n$)), i.e., some PSpace languages are not context-sensitive.
3. PTime is subsumed by PSpace, but not necessarily by NSPACE(O(n)) (hence my question). Indeed, it seems unlikely that today's answer to my question is "All PTime languages are context-sensitive." If we would know this for sure, then (using 2.) we would know that PTime is strictly smaller than PSpace, which is an open conjecture today.

However, I don't see an immediate reason why there should not be a known example of a non-context-sensitive language in PTime.

**Conclusion after reading the answer:** We know very little. Mostly, we know $NL\subseteq NSPACE(O(n))\subseteq PSpace$ and $NL\subseteq P\subseteq NP\subseteq PSpace$. It is unclear how $NSPACE(O(n))$ (CSL) compares to $P$ and $NP$. If we could show that $P\subseteq NSPACE(O(n))$, this would show $P\subsetneq PSpace$ (open); if we could show $P\not\subseteq NSPACE(O(n))$, then this would show $NL\subsetneq P$ (open). Both of these open conjectures are expected to be true, which is not of any help for making a guess regarding the answer to my question.

# Answer
> 6 votes
It is an open question to separate $\mathsf{L}$ (that is, $\mathsf{DSPACE}(\log n)$) and $\mathsf{P}$ (what you call PTime), so in particular we have no example of a polytime language which requires superlogarithmic space.

---
Tags: complexity-theory, polynomial-time, context-sensitive, linear-bounded-automata
---


# Question
Title: Equivalent expression in English: Set Notation $\{0,1\}^K$
I am overviewing this expression given in set notation. Could someone translate what M "Element of" $\\{{0,1}\\}^k$ stands for? Im looking for an explanation in English like what I did below.

$K\_e = \text{Encryption Key} $
$K\_d = \text{Decryption Key}$
$\mathcal{E}\_K(M)$ = Encryption using Key with Message M

$D\_K(C)$ = Decryption using Key with Ciphertext

$K \oplus M$

Right now I think $K$ is just the word length of the string. Meaning the key could be either $0^k$ or $1^k$ which corresponds to the key being $0$ or $1$ being repeated $k$ times. e.g. $0^3 = 000$ or $1^5 = 11111$. I believe this is wrong though.

# Answer
> 5 votes
In set theory $B^A$ denotes the set of functions from $A$ to $B$. Thus, an element $f\in B^A$ is a function $f:A\rightarrow B$.

In your specific case $\\{0,1\\}^k$ is the set of functions from the natural number $k$ -- a set with $k$ elements -- to $\\{0,1\\}$. An element $M\in\\{0,1\\}^k$ is then a $k$-tuple of zeros and ones, i.e., a binary string of length $k$, as said by Yuval Filmus in a comment.

Note that not any combination of 0's and 1's up to length $k$ is valid, but only those with exact length $k$.

---
Tags: sets, cryptography, notation, encryption
---


# Question
Title: Can we remove unit productions First Before removing Null productions?
My professor have asked me strange question , about converting from Context free grammar to chomsky normal form , Can we remove unit productions first from CFG if possible , before removing null productions , does it effect the Chomsky normal form ?

# Answer
> 0 votes
There is no problem in removing the unit productions first except when in the next step while removing the null productions the grammar might be transformed into one which again has unit productions and you have to repeat the steps again to reach a cnf.

---
Tags: terminology, context-free, formal-grammars, normal-forms
---


# Question
Title: supply a matching data structure that supports MakeEmpty, Insert and DeleteFreq
I've been struggling with solving the following question:

`Supply an ADT that stores members (not necessarily unique) and supports the following functionalities:
1) MakeEmpty - creates an empty data structure - complexity in time Θ(1) worst case
2) Insert - inserts a member into the data structure - complexity Θ(1) in average case
3) DeleteFreq - gets out the most frequent member from the data structure (the member exists the maximal number of times in the data structure) - time complexity Θ(log(n) in worst case`

At the beginning I was thinking about using a hash table (because of the average time of Insert function) and the hash-table based on keys of the members. In addition, for each cell in the hash-table I thought about holding a pointer to AVL/2-3 Search Tree.

But then, I'm thinking it's possibly not correct because only hash-table initialization (all pointers to NULL) gonna cost Θ(hash-table-size). Furthermore, Insert function could be much more expensive if the load factor isn't good.

I would appreciate your advice and guiding

# Answer
"""

This file is both Markdown and Python.

We keep the keys in two data structures. One is a doubly-linked list, like this:

```
| <- [] <-> [] <-> [] <-> [] -> |

```

Here, `[]` is a node and `|` is None. Pointers are one-way (`->`) or two-way (`<->`).

Instead of being terminated by null pointers, the list will be terminated by nodes that point to themselves. An empty list looks like this:

```
[o] <-> [o]

```

Here `[o]` is a node that points to itself. These nodes are called "sentinals".

Nodes keep two other pieces of data. The first is a set of keys. The second is a `frequency`, which represents the number of times each of those keys is in the multiset. For instance, If you insert `a` twice and `b` seven times and `c` seven times, there is a node in the list with `frequency` set to 7 and the set of keys `{b, c}`.

```
[o] <-> [7, {b,c}] <-> [3, {a}] <-> [o]

```

The other invariants that are maintained:

* The nodes are stored in frequency order
* The sentinal at the high-frequency end has frequency None
* The sentinal at the low-frequency end has frequency 0
* No node has negative frequency
* No two nodes have the same frequency
* The sentinals have empty key sets, but no other nodes have empty key sets

So:

```
"""
class FreqBucket(object):
  def __init__(self, lo, hi, freq):
    self.lo = lo
    self.hi = hi
    self.freq = freq
    self.kids = set()

  def __repr__(self):
    return ("FreqBucket({}, {}, {}, {})"
            .format(self.lo.freq, self.hi.freq,
                    self.freq, self.kids))

  def unlink(self, key):
    """Remove key and remove self from the list if necessary"""
    if key in self.kids: self.kids.remove(key)
    if not self.kids:
      self.hi.lo = self.lo
      self.lo.hi = self.hi

  def increase(self, key):
    """Increase the frequency of the given key from this node"""
    result = self.hi
    if self.hi.freq != self.freq + 1:
      # There is no FreqBucket with the right .freq, so we
      # must make a new one:
      old_hi = self.hi
      self.hi = FreqBucket(self, self.hi, self.freq + 1)
      old_hi.lo = self.hi
      result = self.hi
    # Move the key to the next FreqBucket:
    result.kids.add(key)
    self.unlink(key)
    return result
"""

```

TallPoppies uses the list of FreqBuckets described above. It keeps a map in which each key in the structure maps to its corresponding FreqBucket.

```
"""
class TallPoppies(object):
  def __init__(self):
    # The keys of the self.keys dictionary are the inserted
    # objects; the values are FreqBuckets.
    self.keys = {}
    # Make the sentinels and link them to each other and
    # themselves. We need mini for inserts and maxi for
    # deletes.
    self.mini = FreqBucket(None, None, 0)
    self.mini.lo = self.mini
    self.maxi = FreqBucket(None, None, None)
    self.maxi.lo = self.mini
    self.maxi.hi = self.maxi
    self.mini.hi = self.maxi

  def __repr__(self):
    return ("TallPoppies({}, {}, {})"
            .format(self.keys, self.mini, self.maxi))

  def insert(self, key):
    if key in self.keys:
      self.keys[key] = self.keys[key].increase(key)
    else:
      self.keys[key] = self.mini.increase(key)

  def delete_freq(self):
    result = self.maxi.lo.kids.pop()
    self.maxi.lo.unlink(result)
    del self.keys[result]
    return result

```

`insert` and `delete_freq` take expected amortized O(1) time. You need hash tables and linked lists, but not search trees.
> 1 votes

---
Tags: data-structures
---


# Question
Title: Domain and range of recursive functions are recursively enumerable
I want to show the following two propositions:

* The domain of a recursive function is recursively enumerable.
* The range of a recursive function is recursively enumerable.

I have thought the following in order to prove the first proposition.

Suppose that we have a recursive function $f$. Then we know that there is an algorithm $A$ that computes $f$. So if $m \in dom(f)$ then we know that the algorithm $A$ with input $m$ terminates, giving output "yes". Since $m$ is arbitrary, we deduce that the domain of a recursive function is recursively enumerable.

Is my idea right? If so, can't we also deduce from that that the domain of a recursive function is recursive since the algorithm always terminates for the elements of the domain?

Can you give me a hint how we can show the second proposition?

# Answer
The first proof looks ok. (Actually, it depends on the definition you use for RE. Some authors define RE iff it's the domain of a recursive function, making the exercise trivial.)

For the second, here's a hint. Given $x$ you want to check whether $f(0)=x$ or $f(1)=x$ or ... If all of these are false, we can diverge (we must diverge, actually), but if any of these is true, we must halt. We can not proceed with a simple infinite iteration, since $f(1)$ might diverge and $f(2)$ might return $x$, and if so we need to detect that and halt anyway.

So, we need to evaluate *in parallel* all these programs, so that even if one of them diverges does not stop the evaluation of the others.

Think of a fair scheduler among infinitely many processes. Think about running a program for only a given number of steps. Think about doves and their tails. ;-)
> 2 votes

---
Tags: computability
---


# Question
Title: Dynamic Programming, Binary Tree: How to factor in depth to recursion?
I have the following problem.

I have a set of elements $x\_0,\ldots,x\_n$ which must retain their order inside the binary tree: if, given $x\_i, x\_j, i \< j$, $x\_i$ must be to the left of $x\_j$ if $x\_j$ is the root and $x\_i$ is part of $x\_j$'s subtree.

I also have a set of frequencies $f\_0,\ldots,f\_n$. I need to build a binary tree such that the cost of accessing the elements, defined as $depth$\*$f$ is minimized.

I figured this was just like chain matrix multiply, so I wrote that the dynamic table was:

```
T(i,j) = minimum cost tree between i and j

```

And I wrote the following recurrence:

$$ T(i,j) = min \lbrace T(i,k) + T(k,j)\rbrace, i \le k \< j $$

However, I can't figure out if depth is being factored in here--it appears (to me) that it isn't.

How do I construct this recurrence??

# Answer
> 1 votes
Turns out that I had a misunderstanding of the scope of dynamic programming. As I understood it, I was "not allowed" to capture other things outside the recursion besides elementary operations.

So, I just have to literally calculate the sum of values lower than the root on either side to factor in the depth:

$$ T(i,j) = \sum\_{i\leq l \< j}f\_l + min\lbrace + T(i,k-1) + T(k+1,j)\rbrace: i\<k\<j $$

Where I can just calculate the sum outside of the recursion.

# Answer
> 0 votes
If the aim is to build a data-structure that will minimize the access cost, which is defined as $height(tree)\*f$, I would start with thinking about how to minimize this "already defined" cost.

* If you have repeating elements, and if the cost is dependent on the frequency, what should be the structure of the leaves?
* How can you minimize the height? Does the tree need to be binary? Which distribution of elements in the tree ensures easiest access? Which properties should the tree hold, in order to have minimum height?
* After you decide on the leaf and tree structure, how can you improve upon the dependency on $f$? Can you go beyond $f$ (not as in computational complexity, but for practical uses, i.e., $f/2$)?

I hope these questions hints towards the solution.

---
Tags: dynamic-programming, binary-trees
---


title: Boruvka/Sollin's algorithm for MST

text:
# Question
Title: Boruvka/Sollin's algorithm for MST
Please help me regarding following problem-

Let us consider Boruvka/Sollin's algorithm . Note that Boruvka/Sollin algorithm selects several edges for inclusion in T at each stage. It terminates when only one tree at the end of a stage or no edges to be selected.

Algorithm 1: One Step of Boruvka/Sollin's Algorithm 1: Find minimum cost edge incident toevery vertex. 2: Add to tree T. 3: Remove cycle if any. 4: Compress and clean graph (eliminate multiple edges).

(a) Suppose that we run k phases of Algorithm 1, using the output G0 produced by one phase as the input G to the next phase and accumulating edges in T. Argue that the overall running time of the k phases is O(kE).

(b) Suppose that after running k phases of Algorithm 1, as in part (5a), we run Prim's algorithm by calling MST-PRIM (G0; c0; r), where G0, with weight attribute c0, is returned by the last phase and r is any vertex in G0(V). Show how to pick k so that the overall running time is O(E lg lg V ). Argue that your choice of k minimizes the overall asymptotic running time.

(c) For what values of jEj (in terms of jV j) does the above scheme asymptotically beat Prim's algorithm without preprocessing?

# Answer
(a) Suppose that we run k phases of Algorithm 1, using the output G0 produced by one phase as the input G to the next phase and accumulating edges in T. Argue that the overall running time of the k phases is O(kE). Anwser-

Complexity of above algorithm is O(E). There are k number of phases to run.

For each phase, the output of previous phase is input to the next. So, for finding minimum cost edge incident to every vertex (after/before compression of graph), we required to traverse each and every edge.

For each phase time complexity, will be O(E).

Therefore, total time complexity = O(kE)

(b) Suppose that after running k phases of Algorithm 1, as in part (5a), we run Prim's algorithm by calling MST-PRIM (G0; c0; r), where G0, with weight attribute c0, is returned by the last phase and r is any vertex in G0(V). Show how to pick k so that the overall running time is O(E lg lg V ). Argue that your choice of k minimizes the overall asymptotic running time.

Answer - We have time complexity of above Algorithm 1 for running k phases is, O(kE).

Prim’s algorithm complexity is, O(E logV)

But, here the input of Prim’s algorithms if output of k phases of Algorithm 1.

So, for finding minimum edge weight we require log(logV) time. This is because the compression of the graph and we just have to find the minimum edge between given two components (or we can say nodes).

(c) For what values of |E| (in terms of |V |) does the above scheme asymptotically beat Prim's algorithm without preprocessing?

For |E| \>= |V|

Please correct if I am wrong.
> 0 votes

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


# Question
Title: How to solve a recurrence when the master theorem fails?
How do solve the following recurrence?

> $$ T(n) = \frac{1}{2} T\left(\frac{n}{2}\right) + \frac{1}{n}. $$

Master's theorem cannot be applied as $a$ is equal to 0.5 which is less than 1. Hence the theorem fails. How do I solve a recurrence when the theorem fails?

# Answer
You can explicitly unroll the recursion: $$ \begin{align\*} T(n) &= \frac{1}{n} + \frac{1}{2} T\left(\frac{n}{2}\right) \\ &= \frac{1}{n} + \frac{1}{n} + \frac{1}{4} T\left(\frac{n}{4}\right) \\ &= \cdots \\ &= \frac{m}{n} + \frac{1}{2^m} T \left(\frac{n}{2^m}\right). \end{align\*} $$ This easily leads to the solution $$T(n) = \frac{\log\_2 n + T(1)}{n},$$ which is valid for powers of 2.
> 1 votes

---
Tags: recurrence-relation
---


# Question
Title: Enumerating the List of `nPr` (n Permute r) objects
I have been using MATLAB for a particular project, and have seemed to find a function that may or may not exist. This question isn't MATLAB specific, more algorithm specific.

I have a list of 12 items, indexed from 1 to 12. I want to be able to create a list of all possible permutations of these 12 items where I only want to select 6 of them per entry.

Here is a reference to what nPr is for those unfamiliar.

In MATLAB, there is a function called `perms(A)` such that it calculates `nPn` where `n = A.length`. However what I am looking for is `nPr` where `n = 12` and `r = 6`. Is there a way to either

1. Exploit the `perms` function such that it does `nPn` such that `n = 6`, but in a way that it actually calculates `nPr` where `n = 12` and `r = 6`.
2. Write a recursive algorithm to replace the `perms(A)` function and create a `perms(A,r)` function?

Any pointers or tips would be much appreciated and helpful.

# Answer
> 2 votes
This is more of a MATLAB specific answer

> arrayfun(perms,nchoosek(A,r))

<sub>\*Think of this as conceptual answer, because I have have been away from MATLAB and can't test it right now.</sub>

In other words,

1. get unordered combinations of elements in A, taken r at a time. using nchoosek.
2. get ordered combinations (with perms) of each unordered combinations. Applying a function to each element of a list can be done via arrayfun.

# Answer
> 1 votes
Here is pseudocode for the function Generate($k$, $A$), which generates all ordered $k$-tuples of distinct elements from the set $A$:

> Generate($k$, $A$)
>
> * If $k = 0$, output the empty tuple.
> * Otherwise, for each element $x \in A$ and for each $(k-1)$-tuple $\alpha$ in Generate($k-1$, $A \setminus \\{x\\}$), output $x,\alpha$.

More efficient algorithms exist, see Volume 4A of Knuth's Art of Computer Programming.

---
Tags: algorithms, permutations
---


# Question
Title: How to solve recurrences with transcendental terms?
Problem:

> A number is said to be a magic number, if the sum of its digits, taken again and again till it becomes a single digit number, is 1.
> Example: $289 =\> 19 =\> 10 =\> 1 =\> 289$ is a magic number
> but, $20 =\> 2 =\>$ not a magic number.

So the simple algorithm is to keep doing the digit sums till we reach a single digit number. I tried to calculate the time complexity of this algorithm, and came up with the following recurrence:

$$T(n) = T(lg\ n) + O(1)$$

Let us say we have a number $N$ to test for magic number. The number of digits in this number is $O(lg\ n)$, so the sum of its digits is at most $9\*lg\ n$ which is $O(lg\ n)$. So we have one smaller subproblem of size $lg\ n$ and some constant work to return data.

How do I solve this recurrence? The answer would be, ostensibly, the number of times I have to take $log $ of a number to get to 1. Is there a direct equation for this?

# Answer
The function $\log^\ast$ ("log-star", iterated logarithm), which shows up in complexity theory, is exactly the number of applications of $\log$ which reduce a number below some constant.

(Confusingly, in information theory the same notation is used for the function $\log + \log\log + \log\log\log + \cdots$.)
> 7 votes

---
Tags: time-complexity, runtime-analysis, number-theory
---


# Question
Title: One rational interval function and one irrational, will they ever collide?
This question may be a little mathy or hardware-y, so I may have to ask elsewhere.

I've recently learned that if a is a positive rational number and b is a positive irrational number, there exists no common multiple between the two.

A common design consideration in threaded or embedded systems is concurrency control, when two functions or threads share resources.

So if function A runs every sqrt(2) seconds, and function B runs every 1 second, they will never run at the same time.

Is it somehow possible to use very accurate measured numbers, to make this possible? Or is it possible using exact/symbolic programs/tools? Or is it not possible at all in machine/computer computational formats?!

# Answer
> 3 votes
Could you make a theoretical device that could measure an irrational number of seconds? Maybe, but that would be impossibly hard. In the real world the computers clock, which runs the scheduler, is made out of a vibrating piece of quartz creating the ticks. This is vibrating at a few billion times per second. You will never get resolution of time between the vibrations so it provides us with an implicit limit on how accurately we can measure time.

---
Tags: concurrency, threads
---


# Question
Title: Regular expression of a language with two letters, one which number of instances can be divided by three
Let be a language with the following alphabet : $\Sigma=\\{a,b\\}$

I want to write the regular expression of {$w$ | $w$ containing a number of $a$ that we can divide by $3$ }

A friend of mine thought of $(b^\*+ab^\*aa+aab^\*a)^\*$ and it seems alright for me but I said to me today that it wasn't true but I can't see why. I havn't found counter examples.

I rather thought of $(b^\*ab^\*ab^\*ab^\*)^\*$ but I'm not sure. I haven't found counter examples yet.

**Therfore, how to have the regular expression of a language with two letters, one which number of instances can be divided by three ?**

# Answer
> 1 votes
The first regular expression is incorrect. It assumes that for any string containing at least one $a$, it must contain consecutive $a$s. So, a string such as $ababa$ is a counterexample.

The second regular expression is almost correct for the given language, except it doesn't cover the case where there are no $a$s at all. So, you could consider expressing it as $$(b^\*ab^\*ab^\*ab^\*)^\*+b^\*$$ In general, constructing a finite automation for such a language is very easy. From there, you can convert it to a regular expression using methods such as this.

---
Tags: formal-languages, automata, regular-expressions
---


# Question
Title: difference between deadlock avoidance and detection
I know the difference between deadlock prevention and avoidance. But i want to know the difference between deadlock avoidance and detection. ?

# Answer
Simply to put
Deadlock avoidance: you employ some methods to avoid the deadlock ,but prevention is more restrictive than avoidance.

Deadlock detection: Here only the detection only takes place whether the current state is in deadlock or not.
> 3 votes

# Answer
Deadlock avoidance : Suppose you have to satisfy various request for some set of instances of various resources. Currently you have sufficient available resources ,so the system can decide for each request whether or not the process should wait to avoid a possible future deadlock.Simply just to check every request that if you satisfy the request then whether deadlock will occur in future or not? if yes then don't satisfy the request.

Deadlock detection : Examines the state of the system to determine whether a deadlock has occurred.
> 3 votes

---
Tags: operating-systems, deadlocks
---


# Question
Title: Given an array of n unsorted integers, how can you check that any 2 elements within k distance of some element don't vary by a multiple of 2?
In O(n log k) time?

The input is the array of integers n, and some integer k. The output should be a boolean for whether or not the following condition holds for all elements: any two elements within k distance of this element cannot vary by a multiple of two (the maximum cannot be double the minimum).

The brute force solution would be to iterate over every element, and then iterate over all elements within k distance of it, finding the maximum and minimum, and checking to make sure the maximum is less than 2x the minimum.

However, that would take O(nk) time. Is there a way to do this in O(n log k)?

I was thinking about maintaining a min heap and a max heap (as insert and delete operations have a runtime of O(log k)), but it seems like a lot of extra work (you would have to keep a hashtable of element positions in the heap in order to remove them).

Any ideas?

# Answer
Yes, it can be done in $O(n \log k)$ time, using exactly the approach you hinted at.

You're going to do a linear scan over the array, from left to right. At each step, you check whether the max of the last $k$ elements is more than twice the min of the last $k$ elements.

To compute the max and min efficiently, you'll maintain a max-heap of the last $k$ elements, and a min-heap of the last $k$ elements. Each time you move one element to the right, you add an element to each heap (insert $A\[i\]$ into the heap) and remove an element from each heap (delete $A\[i-k\]$ from the heap).

To remove elements from the heap, have two auxiliary arrays, $B$ and $C$. $B\[i\]$ maintains a pointer to where $A\[i\]$ is stored in the max-heap, and $C\[i\]$ maintains a pointer to where $A\[i\]$ is stored in the min-heap. To reduce space consumption, you can arrange that these two auxiliary arrays are of length $k$ rather than length $n$, if that is important.
> 2 votes

# Answer
I'd look at your conditions first. If |a-x| ≤ k, and |b-x| ≤ k, and b = 2a, then |x| ≤ 3k, |a| ≤ 2k, |b| ≤ 4k.

So you make one pass in O (n) keeping only array elements with absolute value ≤ 4k, and elements \> 3k must be even. You can use a hash table to also remove duplicates quickly. This works in practice in O (n). Now obviously the rest relies on how many numbers are left, say m numbers. So the time is O (n) plus some function of m. I actually don't think the size of k is relevant unless you take into account that with *enormous* k basic operations take time in O (log k). (So if you don't have 64 bit numbers, but 64,000 bit numbers, then things will slow down. I'll ignore this).

You sort the array in O (m log m). Then you scan the list using three pointers; you find values a in the list such that b = 2a is also in the list, and then you check whether any x in the intersection of \[a-k, a+k\] and \[2a-k, 2a+k\] is in the list. That should happen in linear time O (m).

(Reading D.W.'s answer, we seem to be interpreting "any two elements within k distance" in a totally different way.)
> 0 votes

---
Tags: algorithms, complexity-theory, arrays, divide-and-conquer
---


title: Reduction from Vertex Cover

text:
# Question
Title: Reduction from Vertex Cover
> The city council would like to place trash bins around the city and has a list of suitable spots (street crossroads, supermarkets etc.) but the number of these spots is greater than the number of available bins. The council's goal is to place the limited number of bins so that the distance from each house to a bin is at most 100 m. Prove that the problem *k containers are sufficient* is NP-hard using reduction from a known NP-hard problem.

I came up with *vertex cover* (could we alternatively use *dominating set*?). We then need to transform an instance of *vertex cover* $(V, E, k)$ to an instance of this problem. It's not clear to me how. This is how I thought I would represent the *k containers are sufficient* problem by a graph:

My first step would be to create a graph where the set of nodes contains both the **spots** for containers and all the **houses**. I would then connect each spot node with all the house nodes that it is close enough to (100 m). This seems quite close to *vertex cover* except that there are 2 types of nodes:

* The house nodes **cannot** be used as a part of the vertex cover set since bins cannot be placed in front of houses but they need to be covered by the vertex cover set.
* The bin spots **can** be used as a part of the vertex cover set but do need to be covered at all by it.

How could I deal with this in the reduction? I thought about using some vertex to edge transformation to represent these relationships but came up short.

# Answer
> 1 votes
This is known as the $k$-center problem or the planar minmax Euclidean facility location problem. It is a special case of the minimax facility location problem for the Euclidean metric.

The $k$-center problem is known to be NP-hard. Wikipedia has references to the literature, where you should be able to find an explicit reduction.

The special case where $k=1$ can be solved in polynomial time.

# Answer
> -1 votes
I have come up with the following solution:

We transform an instance of *vertex cover* $(V, E,k)$ to a specific instance of *k containers are sufficient* in which the the available spots for containers are equivalent to the set $V$ and in which the set of houses that have to be near containers is exactly equal to $V$ (the available spots for containers are exactly where the houses are located). The edges connect houses-spots which are within 100 ms of each other.

It shouldn't then be difficult to see (since the *k containers are sufficient* problem formulated in this way is basically identical to *vertex cover*) that the graph $G=(V,E)$ has a vertex cover of size $k$ exactly when $k$ containers suffices to serve all the houses.

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


# Question
Title: What does "no value is acceptable" in Machine Learning hypothesis representation
I am new to machine learning. I am reading the book, where I have: – Most general hypothesis \< ? ? ? ? ? ? \> – Most specific hypothesis \< Ø Ø Ø Ø Ø Ø \>

in Sky AirTemp Humid Wind Water Forecast \< Sunny ? ? Strong ? Same\>

I understand that for a learning instance, "?" means it can take on any value, so the outcome of the hypothesis would be 1, as long as the specific attribute is met.

I am confused about "Ø". The book says any value is unacceptable.

Does that mean, if a hypothesis is \< ? ? ? ? ? Ø\>, no matter what first 5 attributes are, since the last one is unacceptable, the outcome of the hypothesis will be 0? If so, what is the difference between \< ? ? ? ? ? Ø\>, and \< Ø Ø Ø Ø Ø Ø \>?

# Answer
> 1 votes
Yes, that's right. Those two hypotheses are equivalent, in that they assign the same classification to every possible instance. Sometimes there are two different ways to represent the same thing.

---
Tags: machine-learning
---


# Question
Title: Computer Vision - What is spatial histogram/pyramid feature?
I am trying to re-implement the model in this paper https://arxiv.org/pdf/1511.02917v2.pdf. But the paper omitted some details in feature extraction (Section 4.1). I am new to computer vision so I am confused when the paper just said they got the spatial feature (1440 dimensional) that corresponds to a 32\*32 spatial histogram, combined with a spatial pyramid, to indicate the bounding box location at multiple scales.

I guess a 32\*32 spatial histogram is to divide the image into 32\*32 regions and concatenate histogram for each small region together? But what does it mean to combine with a spatial pyramid, and how to end up with a 1440 dimensional spatial features.

# Answer
**Spatial histogram.** A simple histogram is obtained by taking a region of an image, assigning a label to each pixel (somehow; via some mapping function), and then computing a histogram of the labels. The histogram counts, for each possible label, how many pixels received that label. You obtain a feature vector: a vector of counts, one count per possible label.

Such a histogram doesn't capture any information about where the labels appear. A *spatial histogram* addresses that shortcoming by dividing the image up into several smaller patches, computing a histogram for each patch, and concatenating those histograms. For instance, you could take a 32x32 image and break it up into sixteen 8x8 patches, compute a histogram for each patch, and concatenate them to get a feature vector.

You still have to choose an appropriate matching. You might choose a texture descriptor, or just the pixel RGB value (quantized appropriately), or something about the direction of the gradient (quantized), or something else. For more about spatial histograms, see here and the following paper:

Hongming Zhang, Wen Gao, Xilin Chen, Debin Zhao. Object detection using spatial histogram features. Image and Vision Computing, vol 24 no 4, April 2006.

**Pyramid.** A pyramid allows you to do something at multiple scales. You start with a 32x32 image and compute a feature vector for it. Then, you rescale the image down to a 16x16 image and compute a feature vector for it. Then you rescale down to a 8x8 image and compute a feature vector for that. And so on. Finally, you concatenate all of those feature vectors. This allows you to capture both coarse features (from the highly downscaled images) as well as fine features (from the large images).

For more about pyramids, see https://en.wikipedia.org/wiki/Pyramid\_%28image\_processing%29.
> 7 votes

---
Tags: machine-learning, computer-vision
---


# Question
Title: For a computational problem, can the set of instances be finite?
A computational problem consists of a set of instances. In most cases the set of instances is infinite. Like the set of all graphs, e.g.:

> Given a graph $G$, is there a Hamiltonian circuit in $G$?

Can the set of instances be finite and a problem still be non-trivial?

# Answer
> 5 votes
A finite problem can be decided in O(1) time: we can simply compare the input to a finite (bounded) list of known cases, and emit the output consequently.

Indeed, for that we do not need a Turing powerful system: a finite-state automaton suffices.

So, the problem is indeed trivial.

Co-finite (finite complement) problems are similarly trivial.

# Answer
> 3 votes
Depends on your definition of "trivial". The finite number of instances of a finite problem may be so large that the problem isn't solvable at all in practice. For example, determine the best possible move for every legal chess position...

But of course, you can create a somehow sorted table of all possible instances and their solutions, and then binary search in that table will find the solution of any problem quite quickly and trivially. Except the table may just be too big to create.

---
Tags: complexity-theory
---


# Question
Title: Example of an algorithm that lacks a proof of correctness
We have Hoare logic. Why is it still possible that an algorithm is right but there is no proof that it's correct? Suppose the algorithm is expressed in C. Then we can argue step by step that it's doing what it's supposed to do.

So my question is:

> Give me an example of an algorithm that's right but does not have a proof of correctness.

EDIT: I think a little background can help clarify where I'm going. Let me quote Scott Aaronson:

> Since the 1970s, there's been speculation that P $\ne$ NP might be independent (that is, neither provable nor disprovable) from the standard axiom systems for mathematics, such as Zermelo-Fraenkel set theory. To be clear, this would mean that either
>
> 1. a polynomial-time algorithm for NP-complete problems doesn't exist, but we can never prove it (at least not in our usual formal systems), or else
> 2. a polynomial-time algorithm for NP-complete problems *does* exist, but either we can never prove that it works, or we can never prove that it halts in polynomial time.

I'm referring to the second possibility. Since Aaronson can so confidently list it as a possibility, I think there must be an existing example of type 2. That's why I'm asking this question. But it seems a quick and clear answer is not in view.

# Answer
Here is an algorithm for the identity function:

* Input: $n$
* Check if the $n$th binary string encodes a proof of $0 \> 1$ in ZFC, and if so, output $n+1$
* Otherwise, output $n$

Most people suspect this algorithm computes the identity function, but we don't know, and we can't prove it in the commonly accepted framework for mathematics, ZFC.
> 51 votes

# Answer
Most algorithms have not been proven correct in Hoare logic. The main reason is that such correctness proofs are extremely expensive as of Jan 2017, probably by several orders of magnitude in comparison with 'mere' programming. There is a lot of ongoing work to reduce this cost by automation, but it's an uphill struggle.

Another reason why an algorithm might not have a correctness proof, and one that is more relevant in practise than the incompleteness phenomena that Yuval and chi mentioned, is that we might not know what this specification is. This problem has two dimensions.

* **The customers don't know what they want.** This is a well-known problem in software engineering, and software engineers have developed many approaches to deal with this.
* **The specification is difficult.** A good example is the correctness of cryptographic algorithms. Only recently Micali & Goldwasser won Turing awards for specifying what cryptographic security means. Note however that that definition is (as far as I'm aware) for "theoretical cryptography" where you have a security parameter $n$ ranging over natural numbers, and adversaries are polynomial time probabilistic Turing machines. To the best of my knowledge (please correct me if I'm wrong) there is a mismatch between theory and practise, and concrete algorithms like AES and SHA256 are not quite within the purview of those theoretical specifications. I don't think there is full specification for such algorithms, hence we cannot, in principle verify them in the sense of e.g. Hoare logic.
> 10 votes

# Answer
This is tied to the incompleteness of the underlying logic. Indeed, Hoare logic usually contains a weakening or "pre-post" rule $$ \dfrac{ P \implies P' \qquad \\{P'\\}c\\{Q'\\} \qquad Q' \implies Q' }{ \\{P\\}c\\{Q\\} } $$ where the implications $P\implies P', Q\implies Q'$ need to be proved in an underlying logic, usually First-Order Logic (FOL) with some set-theoretic axiomatization like Zermelo-Fraenkel (ZF).

The tricky part is that we know such logic is incomplete, as proved by Gödel almost one century ago. More concretely, there is a predicate on natural numbers $P(n)$ for which we can prove inside the logic $P(0)$, $P(1)$, $P(2)$ and so on for any given natural constant, but there is no way to prove $\forall n\in \mathbb{N}.\ P(n)$.

From the computer science side, this weird behavior can be exemplified using computability theory. Suppose a Turing Machine $M$ when run on the empty tape does not halt in $n$ steps ($P(n)$). Then, in ZF we can prove such fact by essentially unraveling the execution step-by-step in the proof. However, when $M$ diverges, we can not hope to be able to prove divergence in ZF ($\forall n.\ P(n)$). Indeed, if this were possible for all given $M$, then we could semi-decide divergence by enumerating all the possible proofs for $\forall n.\ P(n)$, and halting when one is found. Since we know that divergence is not RE, this is impossible.
> 5 votes

# Answer
Problem: Print "Yes" if every even number ≥ 4 is the sum of two primes, and "No" if there is an even number ≥ 4 that is not the sum of two primes.

Algorithm: Print "Yes"

Most people think that the algorithm is correct. There is no known proof, and it is quite possible that there *is* no proof.
> 5 votes

# Answer
Any algorithm that is correct but we don't know how long it takes to run can be transformed into an algorithm that stops in a guaranteed amount of time but we aren't sure if it is correct.

For example, to find a prime larger than $n$, start counting up from $n+1$ testing if each number is prime until you find one. Now modify it to give up and return $0$ if we can't find a prime after $\log(n)^2$ tries. If the modified algorithm ever returns $0$, it is incorrect, but nobody knows if that ever happens or not. Even with as many as $\sqrt{n}$ steps we can't prove a prime will always be found.

So, we have an algorithm that is correct but we have no proof that it runs in polynomial time, and an algorithm (the same one, but time-limited) that runs in polynomial time but we have no proof that it is correct. And like with the $P=NP$ problem, for this example it is also plausible that no such proofs exist.
> 3 votes

---
Tags: correctness-proof, hoare-logic
---


# Question
Title: Prove function in little-oh of a big-theta function
I'm having trouble with this homework question.

Prove if $f(n)$ is $o( g(n) )$ and $g(n)$ is $\Theta( h(n) )$, then $f(n)$ is $o(h(n))$.

I know I need to use the precise definition of a limit, but I'm not sure how to apply it to this proof. Any help would be appreciated.

# Answer
$f(n)$ is $o( g(n) )$

This above equation implies the following:

$f(n) \< c \cdot g(n) \ -(1)$

for some $c \in R$ and $\forall n \geq n\_{0}$

$g(n)$ is $\Theta( h(n) )$

The above equation implies following:

$ c\_{1} \cdot h(n) \leq g(n) \leq c\_{2} \cdot h(n) -(2)$

for some $c1, c2 \in R$ and $\forall n \geq n\_{0}'$

Now let's assume $c$ \> 0

Multiplying equation $(2)$ by $c$ gives:

$ c \cdot c\_{1} \cdot h(n) \leq c \cdot g(n) \leq c \cdot c\_{2} \cdot h(n)$

Considering right side of the above inequality:

$c \cdot g(n) \leq c \cdot c\_{2} \cdot h(n) -(3)$

Let $n\_{0}''$ be $max(n\_{0}, n\_{0}')$

We can say $\forall n \geq n\_{0}''$, equation $(1)$, $(2)$ and $(3)$ will hold true. Now by using $(1)$ and $(3)$, we can infer:

$ c \cdot c\_{2} \cdot h(n) \> f(n) -(4)$

Let $c' = c \cdot c\_{2}$

Therefore we can write equation $(4)$ as:

$ f(n) \< c' \cdot h(n)$

$\forall n \geq n\_{0}''$ and since $R$ is closed under multiplication, therefore $c \in R$

which implies $f(n)$ is $o(h(n))$.

Note: For $c \< 0$, you can consider left side of the inequality, which after multiplying by $c$ will actually come to right side (since $c \< 0$).
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: What's relation between Kolmogorov complexity and pseudorandomness?
In a comment on this question, @Kaveh wondered whether the questioner really wanted to ask "is there a relation between strings with high Kolmogorov complexity and pseudorandomness?" This is not the question that was answered, in the end, but I would like to know the answer.

I understand that any pseudorandom sequence can be given a short description, by describing the program that generated it (as Travis M. points out in the question linked above). So in one sense the sequence such a sequence does not have high Kolmogorov complexity.

On the other hand, it seems as if there's some connection between pseudorandomness and Kolmogorov complexity. For *if you didn't know the algorithm*, then sequences generated by a good (passes lots of appropriate statistical tests, etc.) PRNG could not be described more briefly than by giving the sequence--on average, at least. Right? That's implicit in the kind of tests that good PRNGs have to pass: The tests are meant to rule out cycles and other regular patterns. (We can also require that the PRNG be cryptographically secure, if that helps.)

Happy to be told that I'm hopelessly confused. Just point me in the right direction.

# Answer
The standard notion of pseudorandomness is about a *process*. You can say that the process (the pseudorandom generator) is pseudorandom, or not. The notion of pseudorandomness of a single string is not defined; that's not something you can talk about.

Kolmogorov randomness is a property of a *bit-string*. You can say that a particular bit-string (sequence) is Kolmogorov-random, or not. Effectively, a bit-string is Kolmogorov-random if it has high Kolmogorov complexity, i.e., there's no program that outputs that string that's shorter than the string itself.

If you have a pseudorandom generator, then the strings it outputs are never Kolmogorov-random. Any output from the pseudorandom generator can always be generated by a short program (a program that hardcodes the seed to the pseudorandom generator, as well as the code of the pseudorandom generator itself), so isn't Kolmogorov-random.

That's the relationship.

---

Incidentally, Kolmogorov-random is not about *knowledge* of a program to generate the string. Knowledge is irrelevant. What matters is *existence*: whether or not exists a program that generates the string. If there exists a short program that generates the string, then the string is not Kolmogorov-random -- and this remains true even if you don't know the program, or even if it would be difficult to find the program.

---

You asked about compressibility. Let $G$ be a pseudorandom generator (in the standard cryptographic sense, i.e., computationally indistinguishable from true-random). There is a sense in which outputs of $G$ are compressible, and a sense in which they are not.

The outputs of $G$ *are* compressible, if you don't care how long the compression algorithm takes to run. Given $G$, we can construct a compression algorithm $C$ that compresses outputs from $G$ to something much shorter. The catch is that $C$ takes a very long time to run: it takes exponential time. In particular, $C$ works by exhaustively trying all possible seeds to see which is correct, and outputting the correct one. This isn't of much relevance in practice -- an algorithm whose running time exceeds the predicted lifetime of the solar system isn't of much engineering relevance -- but it does demonstrate that the outputs of $G$ are Kolmogorov-compressible and thus aren't Kolmogorov-random.

Outputs of $G$ are *not* compressible (with high probability), if you limit the compression algorithm's running time to something reasonable. For instance, suppose we limit $C$ to run in polynomial time, but allow $C$ to be otherwise unrestricted; then with high probability, running $C$ on the output of $G$ will not lead to any appreciable compression. (Why? Truly random bit-strings are, with high probability, not compressible by $C$. If pseudorandom outputs from $G$ were compressible, then you would obtain a polynomial-time algorithm for distinguishing outputs of $G$ from truly-random strings, which is exactly what the definition of pseudorandomness promises cannot happen.) So in practice, outputs of a pseudorandom generator are not compressible.

Maybe this helps enlighten the connection and contrast between standard pseudorandomness and Kolmogorov-randomness. Standard pseudorandomness is about fooling a *fast* distinguisher (say, one that runs in polynomial time). Kolmogorov-randomness is about fooling a *short* distinguisher (one whose source code is shorter than the pseudorandom string). "Fast" is largely orthogonal to "short"; you can have a short program that is very slow (e.g., exponential running time), and you can have a long program that is still fairly efficient (its source code is longer than the input string, but its running time is at most polynomial in the length of that string).
> 6 votes

---
Tags: pseudo-random-generators, kolmogorov-complexity
---


# Question
Title: Compute how much memory is needed for a two level page table
Im studying operating systems and i found an exercise that i cant solve. It asks to compute the memory space needed for a two level page table. The logical addresses are 32 bit, Page size is 4KB and the page entry size is 4 bytes. from the page size i found out that the offset is 12bits from the 32 of the memory address and that every page has 1024 entries. So the 32 bit memory address is like this: 10 bits | 10 bits | 12 bits for outer table, inner table and offset. How can i calculate the memory size i need? (assume that all inner tables are used)

# Answer
*This is a textbook exercise, maybe answering that exerise is part of your homework, so read your lessons, think about a possible answser, take a sheet of paper and draw rectangles and arrows representing memory, page tables, pointers...*

First, an historical note, this arrangement 10 | 10 | 12 is the one used in 32bits x86 CPUs, which were fairly popular!

> 4GB memory is divided into 1Million 4kB pages ( binary million = 2^20). Each "Page Table Entry" occupies 4 bytes. Total = 4MB. These entries are arranged in 1024 tables of 1024 entries. The indexes for the 1024 tables, "Page Directory Entries" each take 4 bytes (on x86, this is usually the same size as PTEs), so 4KB. Total size is therefore 4MB+4kB = 4100kB

A few remarks :

* This size is only needed for mapping the whole 4GB address space. If there is less memory installed, the page tables can be smaller with "invalid" or "unmapped" entries in the first level page table.
* A multitasking OS need to manage different memory maps for the different running applications, so there can be several copies of the page tables.
> 1 votes

# Answer
If we use just paging then it will contain 4MB to maintain table details because (2^32/2^12) = 2^20 pages. we store this page table in physical memory . So 4MB is just wasted to store the page table and the access rate is very slow because if you are going to search a page in 1 million page is much more difficult task . So we can use two level paging , it makes easy to access and less memory to maintain the table . So there is no concern with the physical memory it will take in this example. It will take same physical memory it has taken in the paging without two level paging
> 0 votes

---
Tags: operating-systems, paging
---