# Question
Title: How should I describe the relationships between type expressions?
Lets say I have two type expressions: `Maybe a` (X) and `Maybe Integer` (Y), where `Maybe` is a type constructor, `Integer` is a Type and `a` is a type variable.

What language should I use to describe the relationship between these expressions, and type expressions in general? I've been using the language of sets: X describes a subset of Y, X and Y intersect, and so on. Is this generally accepted, or is there a different, widely accepted language for describing the relationships between type expressions?

In the example provided, I would like to express th at expression X describes many possible types, and that includes all of the types described by Y.

# Answer
The set-theoretic intuitions can make sense in the semantics, especially in the context of realizability semantics (where types are interpreted as sets of terms). In this case, the polymorphic type $\forall \alpha. \mathrm{Maybe}(\alpha)$, written `Maybe a` in Haskell, intuitively corresponds to the intersection over every type $T$ of the elements of $\mathrm{Maybe}(T)$. Or in other words, $⟦\forall \alpha. \mathrm{Maybe}(\alpha)⟧ = \bigcap\_T ⟦\mathrm{Maybe}(T)⟧$, where $T$ ranges over the semantic domain (and elements of the semantics are injected into the syntax).

On the other hand, set-theoretic intuition does not really make sense on the side of the type system, because standard set operations are not allowed. For instance, it is not possible to refer to the intersection of two types in the syntax (at least when you are not working with intersection type systems, and I don't think this is the case in Haskell). However, one operation on types that is primitive in all type systems with polymorphism is instantiation. This corresponds to the elimination rule for the universal quantifier (or polymorphism), and it states that if you have a term $t$ of type $\forall \alpha, \mathrm{Maybe}(\alpha)$ then the term $t$ can be seen as an element of type $\mathrm{Maybe}(T)$ for any type $T$, for example $\mathrm{Integer}$.
> 6 votes

---
Tags: type-theory, haskell
---


# Question
Title: Method for eliminating spent hashes from a large collection?
Consider a DB with a large set of numbers, like hashcash tokens, where new numbers are constantly added(spent). Only numbers that has not been already added can be accepted. Is there a functional way to do this by some sequential operation on the numbers, so that only a single number X is needed to verify that a new number K has not been added before, i.e. a function like: Xn+1 = f(Xn,K) which will return zero if K was previously added? (Or where a small set of numbers can do the same job?)

# Answer
> 4 votes
There is no lossless way to compress a set of arbitrary numbers where the size of the set is unbounded to a fixed number of bits. Cryptography won't help with that.

If you're okay with the storage requirements growing linearly with the number of elements, then use a hash table. This method has no false positives or false negatives. Queries take $O(1)$ time.

If you want a fixed size and are okay with false positives then use a bloom filter. The more elements you add the greater the probability of false positives become.

If you can force the inputs to use a timestamp then you can reject attempts to add records with a timestamp too far into the past. You can then decide to remove all records from a database that are old enough to be rejected and still prevent double spending. (But if you remove the original record you can no longer test for its membership to the set.)

Hashcash rejects headers with dates more than 2 days in the past, so hashes older than 3 days can be deleted to save storage space while still preventing reuse.

---
Tags: hash
---


# Question
Title: Inserting at the head of a linked list is O(1), but this involves moving pointers, and they are not constant size
I don't understand how linked list insertion is constant time. The larger the list gets, the more bits are required to specify memory locations, and then the more bits that must be edited to account for changes in pointers.

Where is my mistake here?

# Answer
We usually analyze algorithms using the *RAM model*, in which basic operations on *machine words* cost $O(1)$. On an input of length $n$ bits, the size of a machine word is $\log n$. In your case, a pointer should fit into one machine word, and so moving a pointer should take $O(1)$ time.

A different issue is how much time is required to maintain the heap. One way around this is to work in the "heap-enabled RAM model", in which heap operations are for free. Probably many papers on algorithms implicitly work in this model.

Finally, a few words on the RAM model. It extends the Turing machine model in two ways. First, it allows indexing. This matches the way actual computers work. Second, it allows constant time arithmetic on machine words, which are usually chosen as indicated above. The size of machine words is chosen so that operations on *indices* take $O(1)$. For example, consider the following program for summing an array $A$:

```
sum = 0
for i from 1 to n:
  sum = sum + A[i]
return sum

```

If we want this algorithm to run in $O(n)$, we need the operation $i \to i + 1$ to run in $O(1)$. Since $i$ could be $\log n$ bits long, we need machine words to be at least $\log n$ bits long. Practice shows that it is not necessary to consider larger machine words. Note that machine words of size $C\log n$ can be simulated using $O(1)$ machine words of size $\log n$ using a multiplicative overhead of $O(1)$; since we don't care about constant factors, increasing the machine word to size $C\log n$ doesn't affect the power of the model.
> 2 votes

# Answer
Existing computers have fixed sized pointers, so this problem is ignored.

Now I design a computer that works as follows: It follows instructions as usual. If it needs more memory than available, then it has a printer and a little robot attached, the printer orders more memory, the robot sends the order to Amazon and puts the memory into the computer. And if it needs so much memory that the pointer size isn't big enough, then the little robot constructs a new computer with doubled pointer size and the new computer continues running the program.

On this computer, it takes O (log n) to insert the nth pointer to a list. Well, not quite, because the size of the universe is limited, so you need a slightly bigger robot that creates bigger universes as needed.
> 0 votes

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


title: Random award question

text:
# Question
Title: Random award question
I'm assisting with the design of an algorithm over the next week to fit the following use case:

A person walking in a store has a tablet and approaches possible customers to notify them of a competition. When a customer enters their details, upon completion of the form - a request is sent to the server, and the customer will be randomly drawn (at that point in time) for a prize.

A maximum of 4 customers are chosen, the number of customers walking into the store is not known. The store is open from 8am until 4pm.

Would there be any other way (other than the ones stipulated) to solve something like this without knowing the average customers visiting the store?

**Solution 1**

I was thinking a normally distributed probability is used, where the parameters could be tweaked over time to fit this allowing customers to be selected (more or less) equally through out the day.

**Solution 2**

Similar to solution 1, but the time throughout the day is partitioned into segments. Between the hours of 8am and 12pm, a maximum of 2 people can be chosen.

I don't quite like the idea of doing this because if a majority of the customers come in the morning, this could lead to less than the 4 prize hand out expected of the day.

# Answer
There is no way to ensure that exactly 4 people win, and that all people have an equal likelihood of being chose.

For instance, suppose you see 100 people during from 8am-3pm, and have given out 3 awards. Then, if 500 people all show up in the last hour, you have at most one more award to give out, so those people will have a much lower chance of winning. Alternatively, suppose you see 100 people from 8am-3pm and have given out 0 awards. Then, if 4 people show up the last hour, the only way to give out exactly 4 awards is to give each of them an award, so those people will have a much higher chance of winning.

As a result, there probably is no perfect solution -- you will just be trading off different kinds of imperfection.

One solution is to not give anyone an award, but that's not very useful.

A practical solution is probably to get some data beforehand on the estimated number of people who show up per day, and use that to choose the probability of winning for each person. Once you've given out 4 awards, stop. For instance, suppose on average 100 people show up per day. Then as each person arrives, with probability $0.04$, given them an award. If you hand out 4 awards, no one else gets one for the rest of that day. That ensures that the expected number of awards handed out is a bit less than 4; that you won't hand out more than 4 awards; and that everyone's probability of winning is close to the same.

If you don't need to determine in real time whether each person has won, you can use reservoir sampling.
> 1 votes

---
Tags: probability-theory, probabilistic-algorithms
---


# Question
Title: Understanding trap and dead state in automata
Well, this sounds somewhat basic definitions, but I feel they needs to be clearly defined.

In book by Hopcroft et. al., there is an excerpt:

> ...a ***dead state***, that is, a nonaccepting state that goes to itself on every possible input symbol...

In book by Peter Linz, there is an excerpt:

> ...the automaton finds itself in state $q\_2$, with the transition $\delta(q\_2,0)$ undefined. We call such a situation a **dead configuration**...

The same book have following excerpt too:

> ... the dfa goes into state $q\_2$, from which it can never escape. The state $q\_2$ is a **trap state**.

So I want to know if following facts are correct:

1. **Trap state** is one from which we cannot escape, that is, it has either no transitions defined or transitions for all symbols goes to itself.
2. I feel, definition on this page for **dead state** is more correct:

> Once the machine enters a dead state, there is no way for it to reach an accepting state.
3. So a trap state can be final or non final, since both can have either no transitions defined or have transitions for every symbol happening to itself.
4. Earlier I felt:

> A final state cannot be a dead state, as we can read $\epsilon$ and stay in the same state, which is final state.

But this, seems incorrect, as epsilon moves are not allowed in DFAs.
5. Thus trap state is always a dead state.
6. It does not makes sense to have non-trap dead state. I mean it makes no sense to show outgoing transition from dead state, if that transition does not lead to some final state further on its path. Thus dead state is always a trap state. Right?
7. As I write these points and think, now, I feel both concepts are one and the same and I am unnecessarily getting confused.
8. This page also has following statement:

> Techincally, this automaton is not a DFA, because it lacks transitions on most symbols from each of its states.

then it says:

> ...add a transition to the dead state from each other state $q$, on all input symbols for which $q$ has no other transition. The result will be a DFA in the strict sense.

I feel DFA (regardless of any attribute attached to it: strict or non strict) can have dead state as it does not eliminates its "deterministic" nature. Right?

# Answer
The concepts you mention are not formal concepts. You can define several notions of a dead state, for example (focusing on DFAs):

1. A dead state is a non-accepting state with self-loops for all symbols.
2. As in definition 1, but we also require the state to be reachable.
3. A dead state is a state from which no accepting state is reachable.
4. As in definition 3, but we also require the state to be reachable.

If we allow some transitions to be "missing" (i.e., our definition of DFA defines the transitions function as a partial function rather than as a function) then we have more possibilities, for example:

1. A dead state is a non-accepting state in which all outgoing transitions are self-loops.
2. As in definition 1, but we also require the state to be reachable.
3. A dead state is a non-accepting state without outgoing transitions.
4. As in definition 3, but we also require the state to be reachable.

If the exact definition used matters, the concept should be explicitly defined. It is usually used in a somewhat informal way, in which the intended meaning is usually obvious from context.
> 4 votes

---
Tags: automata, finite-automata, nondeterminism
---


# Question
Title: Number of states in NFA and DFA accepting strings from length 0 to n with alphabet Σ= {0,1}
The question is in title. Let me repeat:

> What are the number of states in NFA and DFA accepting strings from length 0 to n with alphabet $\Sigma = {0,1}$

I feel both NFA and DFA will take following form:

and thus both have $n+1$ states. Am I correct with this? Or the DFA needs to take following form?

I feel its not necessary to have transitions defined for every symbol for every state, mainly because it does not eliminate "deterministic" nature of the automaton. Am I right?

# Answer
> 2 votes
As mentioned in the other answer, there are two common definitions of DFA. One definition requires the transition function to be total, and the other allows it to be partial. The former one is somewhat more common.

Under the first definition, you need to include the additional state. Under the second definition, you don't have to.

Using Myhill–Nerode theory, it is easy to show that $n+2$ is the minimum number of states in a (total) DFA accepting the words of length between $0$ and $n$. Indeed, consider the words $\epsilon, 0, 0^2, \dots, 0^{n+1}$. These $n+2$ words are pairwise distinguishable. Indeed, if $0 \leq i \< j \leq n+1$ then $0^j0^{n+1-j}$ doesn't belong to the language, but $0^i0^{n+1-j}$ does.

Using the "fooling set" method, it is easy to show likewise that $n+1$ is the minimum number of states in an NFA accepting the same language. Here is a statement of the method:

> Let $L$ be a regular language. Suppose that there are $m$ pairs of words $x\_i,y\_i$ such that $x\_iy\_i \in L$ for all $i$, and for all $i \neq j$, either $x\_iy\_j \notin L$ or $x\_jy\_i \notin L$. Then every NFA for $L$ contains at least $m$ states.

We choose $x\_i = 0^i$ and $y\_i = 0^{n-i}$ for $0 \leq i \leq n$, in total $n+1$ pairs. Clearly $x\_i y\_i = 0^n \in L$ (denoting our language by $L$), whereas for $i \< j$, $x\_j y\_i = 0^{n-i+j} \notin L$.

# Answer
> 2 votes
You can define DFAs in both ways. One can require the transition function to be total, but it is indeed fine to define DFAs without this requirement. You (or your lecturer) just choose one definition and stick with it.

---
Tags: automata, finite-automata, nondeterminism
---


# Question
Title: Solomonoff's theory of induction, Kolmogorov complexity and Bayesian Inference
My motivations for asking this question are philosophical in nature. I'm by no means a computer scientist though, and I feel as though this question should be answered by someone who is since it's one thing to read about a subject second hand and another to understand it first hand. I'm an A-level student of philosophy, physics and mathematics (UK qualification) if that helps you formulate an answer at all.

The question relates to the problem of induction in that, we have little reason to believe the universe is uniform and apply that expectation to science and inference. However, I've seen the claim made that this guy Solomonoff created a theory of induction that uses a Bayesian framework as well as something called 'Kolomogrov complexity' as an objective measure of 'complexity' in a model or hypothesis. For example, if we observe over and over again that all A's are B's, we might be tempted to formulate the hypothesis:

"All A's are B's",

This *would* be afforded the maximum credence from a bayesian framework since it predicts that A's are B's with a probability of 1 and we're attaching ourselves to the likelihood lover's principle. However, you could also formulate the hypothesis:

"All A's are B's until a time t where they are C."

And there are infinitely many of these hypothesis since the 'C' can represent literally anything. This has a bayesian multiplier equal to the previous hypothesis so technically have an equal credence if we don't prefer one of these in our priors. And the only way (it would seem) to decide between the two is to see if hypothesis 2 shows it's prediction at time t. So we would otherwise have to *always* wait until time t to see if hypothesis 1 is correct.

My question can be split up into three parts:

1) Is "Kolmogrov complexity" generally considered a genuine formulation of an objective definition for complexity/simplicity?

2) Would the former hypothesis, with such an understanding of complexity be considered more 'simple'?

3) How would this understanding of complexity be used practically when distinguishing between hypotheses? Or is it just obvious that the former type of hypothesis is more simple?

Although this is really a philosophical question, I suppose I would also like to know if anyone here has any ideas about why we should prefer more simple hypotheses. And perhaps, how would you increase your bayesian prior probability given some measure of complexity for a hypothesis?

Thank you in advance for any answers.

# Answer
> 3 votes
Mathematics and computer science doesn't have anything to say about whether simpler hypotheses are more likely. That's a question about reality, not about math / computer science.

What computer science *can* provide is the notion of Kolmogorov complexity. Kolmogorov complexity is one reasonable notion of simplicity: bit-strings with lower Kolmogorov complexity are "simpler" in some sense.

Now we could start with a model of reality, which says that nature randomly picks a process for generating data; the process is obtained by picking a Turing machine at random, with smaller (simpler) Turing machines more likely to be chosen than complex ones; and then nature runs the Turing machine and the data you observe is the output of that Turing machine. That's a sketch of a possible model of reality; basically, it's an assumption about how nature works.

That assumption then implies (if we fill in some details) a particular prior on hypotheses. A hypothesis amounts to a Turing machine. There will be multiple Turing machines that are all consistent with the observations (that could have produced those observations), and Bayes theorem + the prior will let you infer the posterior distribution on which of those hypotheses are most likely.

This is a possible way to obtain a prior, and it seems reasonable to me. Computer science can't tell you whether that model (that assumption) is a good model of reality. But it can help you work out the consequences of making that assumption.

---

Finally, you seem to be asking why simpler explanations are more often correct. Basically, why is Occam's razor useful? I don't know if there is any completely convincing answer to that.

One possible answer is the empirical answer: it seems to work well in practice. In other words, we often find in nature that very simple processes/models suffice to explain a wide range of natural observations. See, e.g., the unreasonable effectiveness of mathematics.

There's lots more that one can say about Occam's razor. See, e.g., https://en.wikipedia.org/wiki/Occam%27s\_razor#Justifications and https://philosophy.stackexchange.com/questions/tagged/occams-razor?sort=votes. I think that gets beyond the scope of this site.

---
Tags: kolmogorov-complexity, bayesian-statistics, philosophy
---


# Question
Title: Where are file-information like "created" or "last edited" actually stored?
I can access some information about the files ("created" or "last edited") on my PC. But where are those information actually stored?

Are they stored by the operation system? Could be possible as if I transfer a file with FTP to an other PC, it has new timestamps for those information.

Or are they stored in the beginning of the file itself?

How does it work?

# Answer
Information like "creation time" is called *metadata*. The filesystem stores both the contents of the file and its associated metadata on the hard drive. It has to -- if you reboot the computer, we need that information to persist, so it has to be stored somewhere that will survive reboots. That place is the hard drive.

See https://en.wikipedia.org/wiki/File\_system, How do Hard Drives Send and Recieve Data?, Reconstructing files from binary, Typical file structure, and a good operating system textbook to learn more about how filesystems work.
> 1 votes

---
Tags: operating-systems, filesystems
---


title: What to prove and how to prove it

text:
# Question
Title: What to prove and how to prove it
In learning about proof theory, I am interested to know how to go about "proving properties of a program". I don't exactly see yet what needs to be proven, nor how to prove it, which leads to this brief discussion followed by some questions.

In some languages (such as TLA+), the program is the specification (I think). If not TLA+, maybe you can do that in Coq, but I've heard of it. So that means roughly that *what you write is automatically proven*. But if that is the case, how do you *prove* that it's proven. It seems that at some point you have to actually *test* both the code and the proofs and **see** that it does what the specification says. Some basic TDD.

In reviewing the Curry-Howard correspondence, programs are proofs, or at least lambda/functional/logic style programs. Not really sure what this means in practice. If simply writing a new function that implements a specification means we have a proof, or what.

So the questions are:

1. What exactly we are proving.
2. How do we prove that the system meets the specification (if the language is or is not the actual specification). If I write code that says "I will always handle this HTTP request error by tracing its output to the console", and that is "specified" in the specification, then how does it get proven. Not sure what I do to say "guaranteed, this behavior will happen". In my head the only way this can be proven is by actually doing tests on the code (i.e. model testing or just brute force simulation testing like you would see in TDD).
3. When writing tests (as in TDD) comes into play when creating these proofs. Wondering if proofs need tests, sorta thing, or at what point you are *done* with your proof being proven.

So it seems that *what* we want to prove is that the system behaves as expected. And given we have defined how we want the system to work, the question is *how to prove it matches the specification*, at a high level. How much do we prove, how do we know the proofs actually prove what we want and the behavior will be what we want (and proven).

# Answer
I think you raise an important point, which is that in a high level language, specifications can be hard to distinguish from implementations. For example, in Coq, the specification of "The sum of the elements of a list of naturals" is probably going to look something like:

```
Fixpoint sum (l : List Nat) : Nat :=
  match l with
   | [] => 0
   | x::xs => x + sum xs

```

It's hard to imagine what the specification of this would be, other than some predicate like

```
 Inductive Is_Sum : Nat -> List Nat -> Prop :=
    | IS_Empty : Is_Sum 0 []
    | IS_Cons : Is_Sum s xs -> Is_Sum (x + s) (x::xs)

```

which really just seems like a re-formulation in terms of logic programming. Indeed it is very easy to show `forall l : List Nat, Is_Sum (sum l) l`.

At this point, it is indeed possible to test the definition of `sum` and make sure it lines up with our intuition, e.g. check `sum [1,2,3] = 6`. However, there is an important other step we can check in terms of "specification checking", that of proving **derived properties**. For `sum`, we could prove

```
Proposition sum_append : forall l1 l2, sum (l1 ++ l2) = sum l1 + sum l2

```

or

```
Proposition sum_leq : forall l x, In x l -> x <= sum l

```

These propositions establish the consistency of our definition against some of our intuitions, and avoid certain silly mistakes, e.g. if we had returned $1$ instead of $0$ for the empty list.

Indeed, often for our purposes the properties we actually are interested are the derived properties! Defining the full specification is only a means to an end, like strengthening the induction hypothesis.

Finally, it's probably useful to note that in real life, our specifications are often **much simpler** than our implementations! Indeed, if our implementations are doing nothing clever, then why do we care so much about proving them correct? (well, actually even the simplest of programs might benefit from proofs.)

One rather simple example is merge sort which while pretty straight forward, is certainly complex enough to warrant a proof of correctness, and at any rate is very different looking than its specification.
> 2 votes

# Answer
It's not correct to say that in TLA+, the program is the specification. I don't know of any system where that is true.

Rather, TLA+ is a way of writing a formal *model* of a system. You could think of that as a program. Then, we want to verify some *property* of that program. The property must be specified separately. For instance, the model might describe how a traffic light changes states (e.g., from green in one direction, to yellow in that direction, to red in that direction and green in another, etc.); the property might describe something we want to be true about that model (e.g., that it never shows green in two opposing directions at the same time). So, no, the program is not the specification; they are two separate things.

I think once you clear up that misconception, the question evaporates. The property describes *what* we want to prove; the program is the thing we want to prove it about.

---

Regarding your comment: executable specifications are executable and as such can be considered as *a* program, but that doesn't mean the program *is* the specification. I suggest doing some more reading. For instance, try reading about refinement and simulation relations (Wikipedia won't be enough; try to find a textbook on model checking and formal verification). Here we might have *two* programs; one is the implementation we want to prove something about, the second is the specification, and we show that the first refines the second. That lets us prove something useful about the first.
> 1 votes

---
Tags: proof-assistants, software-testing
---


title: Proof of non-receipt of the file

text:
# Question
Title: Proof of non-receipt of the file
The condition of the problem and the statement of the problem: Alice pays Bob for the fact that he, at the request of users, gives out files of interest to users. For example, the user is interested in the file #hash1. The user learns from Alice that this file is stored by Bob. The user connects to Bob and asks to start downloading the file #hash1 to his computer. Then there are two possible bad outcomes. Either Bob is dishonest and refuses to transfer the file to the user, or the user is dishonest and, after receiving the file #hash1 from Bob, lies to Alice and tells her that Bob did not send him anything.

My question is: are there any algorithms in cryptography that Alice will be able to determine the truth and not pay money to Bob (if he lies) or not stop cooperating with Bob (if the user lies)? At least partially. Thank you.

Personally, I thought that my problem relates to the topic of fair exchange (when the two sides exchange bit by bit interesting information and if one side begins to behave dishonestly, the second party immediately stops exchanging and the damage for it is minimal). However, this does not solve the problem that the user can simply lie and say that Bob did not send anything. I just want to know if it's possible to control the work of a third-party server for Alice.

# Answer
Some partial idea: You want to avoid a situation where the user receives the file and claims they didn't.

Bob adds some random padding to the file so that the user doesn't know the size. Bob sends part of the data and waits for a receipt, then sends more data and waits for a receipt. When the file is sent completely, the user doesn't know this. So refusing to send the receipt means they might *never* get the complete file. When Bob claims the whole file has been received, the user contacts Alice, who has a key to unlock the file.
> 1 votes

# Answer
Cryptography probably isn't especially useful for enabling *Alice* to tell whether the user got the right file, but it *is* useful for enabling *the user* to tell whether they got the right file. For instance, Alice can give the user a cryptographic hash of the file to download, and the user can check that what he downloaded matches the hash Alice gave him. Alice can also sign her files.

I don't know of any way that cryptography can allow the user to prove he didn't get the right thing from Bob. As a simple case, suppose the user claims he received nothing from Bob. How are we to distinguish the case where the user is honest and Bob didn't send anything, vs the case where the user is lying and Bob did send it? (Or vs the case where Bob did send it but the user turned off their computer first and thus didn't receive anything; or where Bob did send it, but the user's network connection was down and thus the user didn't receive it.) These seem indistinguishable.

You might be able to use fair exchange to let the user pay Bob for sending the correct file, in such a way that Bob gets paid iff he delivers the file to the user; that seems achievable. It would be plausible that Alice could give the user digital currency, which the user then spends with Bob in exchange for receiving the file from Bob. You could arrange so that the currency is only useful for spending at Bob, and perhaps only for spending to download that particular file. Thus the money is coming from Alice and it doesn't cost the user anything, and Bob does get paid. I'm not going to try to work out the details but you could read about fair exchange and if you're still stuck on how exactly to achieve that, ask on Crypto.SE.
> 0 votes

---
Tags: cryptography
---


# Question
Title: Removing and reinserting elements to minimally mimic a changeset
Let's say that there is a tower of blocks labelled from top to bottom $1$ to $n$. Somebody comes along and removes a block and reinserts it somewhere in the tower (making space as needed). As they move these blocks one at a time, they write down in order which index they moved a block to (index starting at 1). For example, they take the block 5 from the 5th index and squeeze it into between the 6th and 7th making it the 7th index. They write down "block 5 to index 7". They can make as many moves as they like and move each block as many times as they like.

Note that the index "moved to" is the index of the block after the removal and insertion are complete.

Someone else finds the changeset the original person created. Knowing the size of the tower and having the list of changes, they must write another changeset that would have the same results as the first but with at most one move per block and the moves must take place in the order that the blocks were originally moved in without latter duplicates. This also means that only blocks of the original changeset can be moved.

I came up with one which is to repeat the steps in order excluding those where the block is moved again later. This seemed to work in some cases but not all.

Is there an algorithm to solve this problem?

# Answer
> 1 votes
Hint #1:

> Suppose you are only given the final configuration of the stack (not the changeset that led to it). Could you find any sequence of moves that would lead to that configuration? Could you find a sequence of moves that would lead to that configuration, and that makes at most one move per block?

Hint #2:

> Where does block 1 go to? Where does block 2 go to?

---
Tags: algorithms
---


# Question
Title: Do "Type-2" Turing machines with infinite length inputs have more computational power?
Certain idealizations of a Turing machine yield an increase in computational power, such as an inductive Turing machine, which can (trivially) solve the halting problem if it has an infinite amount of time to run.

A related variation is the "type-2 Turing machine" defined by Weihrauch, which (if I understand correctly) is basically a Turing machine with an infinite-length input, and a write-only output tape for which previous outputs cannot be changed. Such models are useful for describing real computation.

Does this model of computation have more computational power than a standard Turing machine, similar to the inductive one?

I would naively guess yes, since the theory of "type-2 computability" and "type-2 recursion" seems to be distinct from the ordinary theory of computability, and it seems intuitive that anything which is "type-1 computable" should also be "type-2 computable" (but not the other way around). However, I am unsure of all this.

Burgin (2004) seems to suggest this as a model of hypercomputation in his book on "super-recursive algorithms," but as he does not offer a proof of such, I may be misinterpreting.

# Answer
Type-2 Turing machines are *not* more powerful than ordinary Turing machines in the sense that any map $\mathbb{N} \to \mathbb{N}$ that can be computed by a type-2 machine can also be computed by an ordinary machine. To see this, suppose a type-2 Turing machine $T$ computes a function $f : \mathbb{N} \to \mathbb{N}$. We can convert $T$ to an ordinary machine by modifying it so that it stops as soon as it writes $f(n)$ on the output (and we can tell when this happens because the output is a single finite number, so it cannot take forever for the machine to produce it).

It is far more interesting to go up one level and compare computability of *functionals*, which are maps $$F : \mathbb{N}^\mathbb{N} \to \mathbb{N}$$ that take an infinite sequence of numbers as an input and output a number. Now there *is* a difference between type 1 and type 2.

Say that a functional $F$ is **type-2 computable** if there exists a type-2 Turing machine $T$ such that, for any sequence $\alpha \in \mathbb{N}^\mathbb{N}$, when $\alpha$ is written on the input tape and machine $T$ is run, it writes $F(\alpha)$ on the output tape (and terminates).

Say that a functional $F$ is **type-1 computable** if there exists a type-1 Turing machine $T$ (i.e., an ordinary one), such that, for any *computable* sequence $\alpha \in \mathbb{N}^\mathbb{N}$, if we write onto the input tape the encoding $n$ of a machine that computes $\alpha$, then $T(n)$ writes $F(\alpha)$ on the output tape (and terminates).

Notice that a type-1 computable functional only accepts *computable* inputs, whereas a type-2 computable functional accepts *all* inputs. If we write $\mathcal{R}$ for the set of all *computable* sequences of numbers (i.e., the total computable functions), then a type-1 computable functional is a map $F : \mathcal{R} \to \mathbb{N}$ computed by some type-1 machine, whereas a type-2 computable functional is a map $F : \mathbb{N}^\mathbb{N} \to \mathbb{N}$ computed by some type-2 machine.

Because $\mathcal{R} \subseteq \mathbb{N}^\mathbb{N}$, we can convert any type-2 functional to a type-1 functional by simply feeding it only computable inputs. We have:

> **Theorem:** When a type-2 computable functional is restricted to computable inputs, it becomes a type-1 computable functional.

*Proof.* The theorem is not a complete triviality. The input is presented to a type-2 functional as a sequence, whereas to a type-1 functional it is presented as a description of a Turing machine computing the sequence. So, suppose $F$ is a type-2 functional computed by a type-2 machine~$T$. We convert $T$ to a type-1 machine as follows: when given an input $n$ which described a machine $M$ that computes some $\alpha \in \mathcal{R}$, we *simulate* an input type for $T$ so that whenever $T$ wants the $k$-th cell of the input, we run $M(k)$ to compute $\alpha(k)$ and give $T$ the answer. $\Box$

Can we go in the other direction? Suppose $F : \mathcal{R} \to \mathbb{N}$ is computed by a type-1 machine $T$. Perhaps we can *extend* $F$ to all of $\mathbb{N}^\mathbb{N}$ to get a computable $\overline{F} : \mathbb{N}^\mathbb{N} \to \mathbb{N}$ which agrees with $F$ on $\mathcal{R}$? The anwser is negative! (See Exercise 15-40 in H. Rogers Jr. "Theory of Recursive Functions and Effective Computability".)

The moral of the story is this (as I have often repeated on these forums): all known notions of computability of *functions from numbers to numbers* agree, but notions of computability of *functionals* do not, and they are *incomparable* in general.
> 7 votes

---
Tags: turing-machines, computability, computation-models, real-numbers, hypercomputation
---


# Question
Title: Maximum number of vertices in undirected graph
I'm studying about time complexity of Kruskal's algorithm.

But there are two opinions to express time complexity as $O(|E|\lg|E|), O(|E|\lg|V|)$.

I know $O(|E|\lg|E|)$ is occurred from sorting by non-decreasing order of vertices.

But I don't understand of $O(|E|\lg|V|)$. This answer explains by $|E|\le|V|^2$, however from my knowledge, maximum number of vertices in undirected graph is $|E|\le\frac{|V|(|V|-1)}{2}$.

What is right time complexity for Kruskal's algorithm?

# Answer
Kruskal's algorithm is only applied to connected graphs. These have at least $|V|-1$ edges. On the other hand, the complete graph has $\binom{|V|}{2}$ edges, and so $$ |V|-1 \leq |E| \leq \binom{|V|}{2}. $$ The left-hand side is $\Omega(|V|)$ and the right-hand side is $O(|V|^2)$. Therefore $\log |E| = \Theta(\log |V|)$. For this reason, the two quoted running times $O(|E| \log |E|)$ and $O(|E| \log |V|)$ are completely identical — on connected graphs, an algorithm has running time $O(|E| \log |E|)$ iff it has running time $O(|E| \log |V|)$.
> 3 votes

---
Tags: graphs, time-complexity
---


# Question
Title: Application of lambda function in Simply Typed Lambda Calculus
I'm just getting started with STLC (Simply Typed Lambda Calculus) and I'm trying to understand an evaluation rule I've been given in some lecture notes by my professor. What it says is the following:

```
(λx. x(λx. x)) (u r) evaluates to (u r) (λx. x)

```

I don't really get this at all. Can someone point out which step I'm misunderstanding in my evaluation;

```
(λx. x(λx. x)) (u r) // Start state, not evaluated

(λx. λz. z) (u r) // Replacing occurences of x in first lambda function with the
                  // second lambda function, and then renaming the input variable x
                  // in the second lambda function (this is allowed, right?)

r                 // x gets replaced by u (no occurences) and z gets replaced by r
                  // - resulting in the final result r.

```

# Answer
> 3 votes
(Summary of my explanations in the comments under the questions)

I think that you did not parse the term correctly. It should be read as $(λx.(x\\;(λx.x)))\\;(u\\;r)$, not as $((λx.x)\\;(λx.x))\\;(u\\;r)$. In the former, $(λx.(x\\;(λx.x)))$ corresponds to a function taking as input a function (argument $x$), which is applied to the identity function $λx.x$ (or $α$-equivalently $λy.y$). In the latter, the term $((λx.x)\\;(λx.x))$ has a very different nature because it denote the application of the identity function to the identity function, which reduces to the identity function.

# Answer
> 4 votes
The term

```
(λx. x(λx. x)) (u r)

```

parses as

```
(λx. M) N
where M=(x (λx. x)) and N=(u r)

```

so, we can perform a $\beta$ step and obtain

```
M{N/x}
= (x (λx. x)){(u r) / x}
= (x{(u r) / x}   (λx. x){(u r) / x})
= ((u r)   (λx. x){(u r) / x})
= ((u r)   (λx. x))

```

The last term is also usually written as `(u r) (λx. x)` or even `u r (λx. x)`.

A tricky part of this step is the substitution `(λx. x){(u r) / x} = (λx. x)`. This derives from the general rule stating that for any terms `A,B`:

```
(λx. A){B / x} = (λx. A)

```

Indeed, the intuition here is that a substitution `{B / x}` only substitutes the *free* occurrences of `x`, and there are no *free* occurrences of `x` in `(λx. A)`. This is coherent with the fact that the bound variable `x` in `(λx. A)` could be $\alpha$-converted to any fresh variable name `y`, obtaining `(λy. A{y / x})`, where `x` is no longer present at all (free or bound).

---

By comparison, this step is wrong

```
(λx. x(λx. x)) (u r) --> (λx. λz. z) (u r)

```

First, when you apply a $\beta$ step, the $\lambda x$ disappears. So, we can not have both $\lambda x$ and $\lambda z$ in the residual term. If we change the term, modifying the parentheses, we get

```
((λx. x)(λx. x)) (u r) --> (λz. z) (u r)

```

but the starting term is completely different from the original one, where `(λx. x(λx. x)) (u r)` is read as `((λx. (x(λx. x))) (u r))` instead.

---
Tags: lambda-calculus, evaluation-strategies
---


# Question
Title: Priority data structure supporting operations Insert, Delete, Get in O(log n)
I need a data structure to store priority $p$ for each key $k$ (unique). It must also support the following operations in $O(\log n)$ time:

$\text{Insert}(k,p)$ Inserts a key $k$ with priority $p$ into the structure. If there already is an element with key $k$, it changes its priority instead.

$\text{Delete}(k)$ Delete the element with key $k$.

$\text{Get}(k)$ Return the element with least priority among all elements with key $k' \leq k$.

At first I thought about balanced binary search trees. However I'd need to sort the elements by key and that just ruins the time complexity of the $\text{Get}$ operation.

Having two trees where one is sorted by key and the second one by priority doesn't help either.

Then I thought about using Fibonacci Heap, but here I have exactly the same problem.

# Answer
Store the items in a balanced binary tree, sorted by key. Augment each node of the binary tree to have a pointer to the lowest-priority element within the subtree rooted at that node. This allows you to implement all three operations in $O(\log n)$ time.

Details: Whenever you insert or delete an element, you can follow the path from that element to the root, updating the augmented data inside each node you visit as you go. This enables you to implement Insert and Delete in $O(\log n)$ time. Any interval of keys can be expressed as the union of $O(\log n)$ subtrees, so the Get operation only needs to examine the augmented data inside $O(\log n)$ nodes and thus can be implemented in $O(\log n)$ time.
> 0 votes

---
Tags: data-structures
---


# Question
Title: Why does floating point modulus exactness matters?
Most Smalltalk dialects currently implement a naive inexact floating modulus (fmod/remainder).
I just changed this to improve Squeak/Pharo and eventually other Smalltalk adherence to standards (IEEE 754, ISO/IEC 10967), as I already did for other state of the art floating point operations.

However for adoption of those changes, I anticipate that adhering to standard will not be enough to convince my peers, so explaining in which circumstances this exactness would really matter would help me a lot. I could not find a good example by myself so far.

Does any one here knows why/when/where (IOW in which algorithm) such exactness of modulus would matter?

# Answer
> 2 votes
Note that inexact floating point implementation affect the weather.

There have been tests running weather predictions with the same inputs on different hardware and the predictions diverged. If you are running iterative algorithm then a small rounding difference here or there can result in a butterfly effect changing sunshine into rain.

The rounding rules in standards (IEEE 754, ISO/IEC 10967) have been carefully thought out so numeric algorithms behave predictable with the most accuracy and reproduce the same result every time. By not following the standard numerical algorithms designed for those rounding rules will break and iterative algorithms like weather predictions can even give a random result.

(and doesn't that say something about weather predictions? :)

---
Tags: arithmetic, floating-point
---


# Question
Title: Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$?
In the CLRS, time complexity of Prim's algorithm is $O(|V|lg|V|+|E|lg|V|)=O(|E|lg|V|)$.

But, for my understanding, Prim's algorithm iterates $|E|$ times for DECREASE-KEY operation which takes $O(lg|V|)$ times and it leads to $O(|E|lg|V|)$.

So, it iterates $|V|$ times then, I think $O(|E||V|lg|V|)$ is right because whole time complexity is like below.

1. Initialization of key and predecessor + making a binary heap = $O(|V|)$
2. EXTRACT-MIN operation = $O(|V|lg|V|)$
3. DECREASE-KEY operation is iterated for $|V|$ times = $O(|E||V|lg|V|)$

Consequently, $O(|V|+|V|lg|V|+|E||V|lg|V|)=O(|E||V|lg|V|)$.
Why is it $O(|E|lg|V|)$?

---

From 2 answers, first while loop iterates $|V|$ times and $DECREASE-KEY$ operation iterates $|E|$ times and time complexity of that operation is $O(lg|V|)$ because min heap has to be reconstructed.

From this, I got a $O(|V||E|lg|V|)$ because for loop is in while loop. What your answers are saying is that I don't know $DECREASE-KEY$ operation iterates $|E|$ times, but I know that.

# Answer
DECREASE-KEY is called at most $2|E|$ times: it is called at most twice per edge (i.e., for each edge $(u,v)$, we call DECREASE-KEY on $v$ when $u$ leaves the queue, and DECREASE-KEY on $u$ when $v$ leaves the queue). DECREASE-KEY costs $O(\log |V|)$ time per call to DECREASE-KEY.

Therefore, the total cost from all of the DECREASE-KEYs is $O(|E| \log |V|)$, not $O(|E| |V| \log |V|)$.

I can see why you might be thinking $O(|E| |V| \log |V|)$: you might be thinking that the outer loop can iterate $|V|$ times, and you might be thinking that the inner loop might iterate up to $|E|$ times, for a total of $|E| |V|$ calls to DECREASE-KEY. But that is too conversative. The number of times the inner loop iterates is not $|E|$, but rather the degree of the current node. The sum of the degrees of the nodes is $2|E|$, not $|E| |V|$. (Why is the sum of the degrees $2|E|$? It's because each edge contributes twice to this sum, once for each endpoint of the edge. See Christofides algorithm: why must an MST have even number of odd-degree vertices?.)
> 3 votes

# Answer
The pseudocode for Prim's algorithm, as stated in CLRS, is as follows:

```
MST-PRIM(G,w,r)
1   for each u ∈ G.V
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)

```

The loop in line 6 will execute exactly $|V|$ times, since $Q$ starts with $|V|$ elements and we remove one each iteration. For each node $u$, the loop in line 8 will execute $\text{deg}(u)$ times, so the `DECREASE-KEY` operation (lines 10 and 11) will execute at most $\text{deg}(u)$ times.

In total, the loop in line 8 will be executed $2|E| = \sum\_{u \in G.V} \deg(u)$ times, and `DECREASE-KEY` $O(|E|)$ times.

---

I would suggest you to grab a piece of paper, draw a graph, and run the algorithm on it while counting how many times you do the `DECREASE-KEY` operation.
> 4 votes

---
Tags: graphs, time-complexity, prims-algorithm
---


# Question
Title: Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit
I have such a task at university: we have $n$ tasks, the $i$-th of them can be done between moment $b(i)$ and $e(i)$. If we decide to perform a task in moment $x$, we finish performing it in moment $x+1$. We can perform at most 1 task at a time and we cannot interrupt performing it. Create an algorithm to check if it is possible to perform all the tasks. $b(i)$ and $e(i)$ may not be integers.

I have done some research online, but I haven't found anything concerning this problem.

Actually I think the following algorithm would work (I haven't found a counterexample yet):

iterate over all the tasks ordered by increasing $e(i)$ and for each of them try performing it the earliest possible. If cannot, return false. If all tasks are added, return true.

If this algorithm works, how could I prove it?

# Answer
I have proved that my algorithm works, so here's the algorithm, just to remind:

> Iterate over all the tasks ordered by increasing $e(i)$ and for each of them try performing it the earliest possible. If cannot, return false. If all tasks are added, return true.

And the proof follows:

Suppose the algorithm is not correct and there exist such data, that it returns false, while it is possible to perform a plan (mapping: task -\> time) in which each task is performed.

Now let's find the first task (chronologically), which is performed at different time in plan created by my algorithm (further called my plan) and the optimal plan.

Then, this task is performed earlier in my plan (because of how the algorithm works) and this is the task we must most hurry with (compared to the rest of tasks performed later in my plan) (because of the order of tasks list processed by the algorithm).

So, we can safely reschedule this task (call it $t$) (in optimal plan) to the time when it is performed in my plan.

If this rescheduling bears any conflict with another task (call it $t'$) in the optimal plan, we can also safely move $t'$ to the time of, when $t$ was performed originally in the optimal plan (because $e(t) \< e(t')$).

So we see that we can safely rearrange the optimal plan, so it becomes my plan. Hence my plan is optimal and the algorithm works.
> 1 votes

---
Tags: algorithms, correctness-proof, greedy-algorithms, scheduling
---


# Question
Title: In LPA*, how are predecessors/successors of a vertex defined?
While trying to implement LPA\* (mostly based on its description in the same authors’ paper on its derivative D\*Lite), I noticed it mentions *predecessors* and *successors* of a vertex without giving a full explanation.

I understand that $Pred(u)$ is the set of all vertices from which an edge leads towards $u$, and $Succ(u)$ is the set of all vertices towards which an edge leads from $u$. Predecessors and successors must be immediate neighbors (thus e.g. a predecessor of a predecessor of $u$ is not necessarily a predecessor of $u$).

In practice, however, it is quite common to have edges that are not directional, i.e. can be traversed both ways (which is equivalent to the same two nodes being connected by two antiparallel directional edges). I infer that for two vertices $u$ and $v$ connected in this way, $u$ would be both a predecessor and a successor of $v$ (and vice versa). In other words, $Pred(u) \cap Succ(u)$ is not necessarily empty.

Am I correct to assume that predecessor and successor are defined only by the existence of an edge traversable in a given direction, and are specifically not related to start cost?

# Answer
If you have an undirected graph, you can convert it to a directed graph by including edges in both directions: for each undirected edge $(u,v)$, add directed edges $u \to v$ and $v \to u$. So, if you have undirected edges, imagine applying this transformation and then running LPA\* on the resulting graph. That should make it clear what to do.

Alternatively: in an undirected graph, Pred(u) is the set of all edges incident on $u$, and so is Succ(u) (there is no distinction between them in an undirected graph). So, yes, they can overlap.

The cost of the edges are irrelevant.
> 2 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: A "packing" optimisation problem with application in dynamic programming
I'm interested in the following problem :

**Input** : an integer $n$, and $k$ *increasing* functions $f\_i:\mathbb{N}\rightarrow\mathbb{R}$, such that $f\_i(0)=0$ for all $1\le i \le k$

**Output** : $k$ integers $n\_1,\dots,n\_k$, such that $n\_1+\dots+n\_k=n$, with $0\le n\_i\le n$

**Goal** : Maximize $\sum\_{i}f\_i(n\_i)$

*My question is* : If we suppose that $k=n$, or simply $k=\Omega(n^\delta)$ for some $\delta\>0$, is it possible to find the optimal solution in polynomial time (in $n$) ?

What if we first consider very simple functions like : $\forall i,m, f\_i(m+1)-f\_i(m)\in\\{0,1\\}$ ?

Such a result could possibly have interesting applications for dynamic programming

# Answer
> 2 votes
Yes. This can be solved in polynomial time using a straightforward dynamic programming algorithm. You build a table $A\[\cdot,\cdot\]$ where $A\[i,m\]$ denotes the maximal value of $f\_1(n\_1)+\dots+f\_1(n\_i)$ subject to the requirement that $n\_1,\dots,n\_i$ be a partition of $m$, i.e., $n\_1 + \dots + n\_i = m$. The entries satisfy the following recursive relation:

$$A\[i,m\] = \max \\{A\[i-1,m-t\] + f\_i(t) : 0 \le t \le m\\}.$$

You can fill in this array using the recursive relation in $O(kn^2)$ time, which is polynomial in $n$. Then, $A\[k,n\]$ contains the answer to your problem.

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Can an algorithm be truly non-deterministic?
I read the term "non-deterministic algorithm" in many places but I don't see how an algorithm can be truly non-deterministic. Typically, there is some source of randomness in these algorithms. If the output of the randomness source is considered an input, the algorithm reduces to a deterministic algorithm. So the only non-deterministic algorithm possible is one that produces truly random numbers with no input or the same input. I have read that this is not possible.

Refer: Can a computer generate a truly random number?

So why are certain algorithms called "non-deterministic algorithms"?

# Answer
There are two meanings of non-deterministic.

Meaning #1: nondeterministic means the algorithm uses non-determinism, in the sense of a non-deterministic Turing machine: in other words, at each step the algorithm can branch into multiple execution paths, and the algorithm accepts if any of these paths accepts. Or, equivalently, you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess. Such an algorithm can't actually be implemented in practice (except by simulating it in an inefficient way), so it is more of a thought experiment.

Meaning #2: non-deterministic means "it is not a deterministic algorithm". For instance, such an algorithm might be randomized.

An algorithm that uses random numbers would be considered non-deterministic in the sense of Meaning #2 but not in the sense of Meaning #1.

Usually when you see the phrase "nondeterminism" in complexity theory or algorithms, it will typically mean the former meaning, but no guarantees. You might have to infer which was meant from context.

See also Differences and relationships between randomized and nondeterministic algorithms?.
> 5 votes

---
Tags: algorithms, randomized-algorithms, nondeterminism
---


# Question
Title: Question on "Hitting the memory wall, implications of the obvious"
I'm reading through a short paper about hitting the memory wall and I'm struggling to understand how exactly said wall will be hit.

The equation for average access time is fairly simple `Tavg = p x Tc + (1-p) x Tm`. (Tc = time for cache, Tm = time for DRAM mem, P = probability of cache hit)

What I don't understand is how as Tc and Tm diverge, we hit a wall. I recognize that Tc grows exponentially faster than Tm eventually Tm will play little to no role in access time, but it seems like me that average access time would then just continually increase. I can't seem to understand how a wall is hit.

Would anyone with a sharper mind or keener eye than mine help me to understand this concept?

# Answer
You have it backwards. $t\_m$ is what's growing exponentially relative to $t\_c$. Or rather, $t\_c$ is decreasing exponentially at a rate faster than $t\_m$. $t\_c$ and $t\_m$ are the times the accesses take which gets *smaller* as the speeds improve. So, as the paper states, eventually memory performance, i.e. $t\_m$ comes to dominate.

The "wall" is the point where having a faster processor, i.e. reducing $t\_c$, makes essentially no difference to overall performance. The situation is an example of Amdahl's law. You are correct that things would improve as $t\_m$ improves but look at the extreme scenario. Choose $t\_c=0$, i.e. computation takes no time at all which is to say we have "infinitely fast" processors. Even with these magical processors, our programs would still run at some multiple of the memory bandwidth. In other words, at some point, if you have a slow program, buying a faster processor will not help. Or, put a different way, at some point, the exponential improvement in processor speeds will be meaningless. It will make no actual difference in program speeds.

And by "at some point", I mean a point we seemingly reached five or ten years ago. Modern (and not so modern) high-performance software design is *significantly* about, in the terms of this paper, reducing $1-p$. Many of the ideas suggested at the end of that paper have been adopted in some form. Multi-level memory hierarchies make even single processors look like non-uniform memory access architectures. Prefetching and careful data layout help increase cache hits, i.e. increase $p$. We're definitely much happier using designs that waste space if they can reduce cache misses. For example, if we have an object that optionally contains another object, we might store this as a dense array of pairs of the objects with a dummy object as the second when it doesn't exist. This is likely to reduce cache misses as compared to chasing pointers. (However, filling cache and/or cache lines with dummy data *also* can increase cache misses which is why this kind of design needs a lot of care.) Another way to decrease the effective $t\_m$ and benefit from the extra computation speed is to store data compressed. When this saga unfolded with respect to disk v. RAM, it was faster to store inverted indexes for full-text databases utilizing compression and decompress them because the time spent decompressing the indexes was more than made up in the time saved in disk traffic. I can easily imagine a near future where RAM stores a compressed representation of, say, a cache line which gets decompressed transparently by the CPU.
> 4 votes

---
Tags: memory-access
---


# Question
Title: Subset Sum problem with many divisibility conditions
How does the computational complexity of the Subset Sum problem depend on the parameter $\alpha(S)$ of the input $(S, t)$, defined as follows?

Considering $S$ under the divisibility partial order, i.e. $s\_1 \prec s\_2 \iff s\_1 \mid s\_2$, define

$\qquad\qquad \displaystyle \alpha(S) = \max \\{|V| \mid V\subseteq S, V$ an antichain$\\}$

to be the maximum size of any subset of $S$ whose elements are pairwise relatively prime.

Subset Sum instances with $\alpha(S)=1$ are solvable in polynomial time. For example, if $S$ contains only powers of two, then $\alpha(S) = 1$, and an instance with set $S$ and any target $t$ is solvable in polynomial time.

In fact, when $\alpha(S)=1$, even the (harder) Knapsack problem is known to be solvable in polynomial time.<sup>$\dagger$</sup>

Are all Subset Sum instances with, say, $\alpha(S) = O(1)$ solvable in polynomial time?

---

$\dagger$ Solving sequential knapsack problems by M. Hartmann and T. Olmstead (1993)

---

# Answer
> 4 votes
This problem can be **solved in polynomial time** using linear programming, and this is actually true for any partial order $(S,\le)$. By the way, we can prove by induction that for any finite partial order set $(S,\le)$, there exists a finite set $S'\subseteq\mathbb{N}$ and a bijection $f:S\rightarrow S'$, such that for all $s\_1,s\_2\in S, s\_1\le s\_2 \Leftrightarrow f(s\_1) | f(s\_2)$.

Let $\mathcal{C}$ be the set formed by the chains in $S$. Remind that $C$ is a *chain* iff for all $v,v'$ in $C$, $v\le v'$ or $v'\le v$

Now create a boolean variable $x\_v$ for each $v\in S$, and a boolean variable $y\_C$ for each chain $C$. We can write the following linear program $(P)$ for our problem : $$ \begin{split} \text{Max} \displaystyle\sum\limits\_{v\in S} x\_v \\ \text{subject to} \displaystyle\sum\limits\_{v\in C} &x\_v \le 1, \forall C\in\mathcal{C}\\ &x\_v \in \\{0,1\\}, v\in S \end{split} $$

and its dual $(D)$ :

$$ \begin{split} \text{Min} \displaystyle\sum\limits\_{C\in \mathcal{C}} y\_C\\ \text{subject to} \displaystyle\sum\limits\_{C:v\in C} &y\_C \ge 1, \forall v\in S\\ &y\_C \in \\{0,1\\}, C\in \mathcal{C} \end{split} $$

Then the problem of finding the minimum cover of an ordered set by chains is the dual of our problem. Dilworth's theorem states that

*There exists an antichain A, and a partition of the order into a family P of chains, such that the number of chains in the partition equals the cardinality of A*

which means that the optimal solution of these two problems match : $Opt(P)=Opt(D)$

Let $(P^\*)$ (*resp.* $(D^\*)$) be the relaxation of $(P)$ (*resp.* $(D)$) *i.e.* the same linear program where all constraints $x\_v\in\\{0,1\\}$ (*resp.* $y\_C\in\\{0,1\\}$) are replaced by $x\_v\in \[0,1\]$ (*resp.* $y\_C\in \[0,1\]$). Let $Opt(P^\*)$ and $Opt(D^\*)$ be their optimal solutions. Since $\\{0,1\\}\subseteq \[0,1\]$ we have : $$ Opt(P)\le Opt(P^\*) \text{ and } Opt(D^\*)\le Opt(D) $$ and weak duality theorem establishes that $Opt(P^\*)\le Opt(D^\*)$ then by putting everything together we have : $$ Opt(P)= Opt(P^\*)=Opt(D^\*)=Opt(D) $$

Then, using Ellipsoid method, we can compute $Opt(P^\*)$ ( $=Opt(P)$) in polynomial time. There are an exponential number of constraints but there exists a polynomial time separation oracle. Indeed given a solution $X$, we can enumerate all couples $s\_1,s\_2\in X$ and check if $s\_1\le s\_2$ or $s\_2\le s\_1$, and therefore decide in polynomial time whether $X$ is feasible or otherwise the constraint associated to the chain $\\{v\_1,v\_2\\}$ is violated.

---
Tags: complexity-theory, number-theory, knapsack-problems
---


# Question
Title: do the ram lose what it remembers when the power if cut off?
after shutting down the computer do the ram loses what it remember ? if yes is there some technics that are used to get what is stocked into the ram after shutting down the computer ?

# Answer
> 1 votes
yes **RAM** chips remember things only while a computer is powered on, so they're used for storing whatever a computer is working on in the very short term.

In today's technology, random-access memory takes the form of integrated circuits. RAM is normally associated with volatile types of memory (such as DRAM modules), where stored information is lost if power is removed, although non-volatile RAM has also been developed. \[1\] Other types of non-volatile memories exist that allow random access for read operations, but either do not allow write operations or have other kinds of limitations on them. These include most types of ROM and a type of flash memory called NOR-Flash.

for more information

```
https://en.wikipedia.org/wiki/Random-access_memory

```

# Answer
> 1 votes
The main bulk of DRAM is made up of capacitors storing a charge to store the bit. This needs to be refreshed regularly otherwise the capacitor will lose charge due to parasitic drain and electromagnetic effects from accessing neighbouring rows.

When the power is cut the DRAM controller will no longer be refreshing rows so eventually all the capacitors will drain. If you cool the ram module down this will take longer. This property is used in the cold boot attack

---
Tags: computation-models
---


title: Big-O complexity upon taking exponent

text:
# Question
Title: Big-O complexity upon taking exponent
If $X \sim \mathcal{O}(\log n)$, then $e^{-X} \sim \mathcal{O} (?)$

Is this a valid question to ask?

# Answer
> 1 votes
The statement $X = O(\log n)$ gives an upper bound on $X$, which implies a *lower bound* on $e^{-X}$ (which is a monotone decreasing function). You can say $$ e^{-X} = e^{-O(\log n)} = n^{-O(1)}. $$ In other words, there exists a constant $C \> 0$ such that for large $n$, $$ e^{-X} \geq \frac{1}{n^C}. $$

---
Tags: complexity-theory, asymptotics
---


# Question
Title: Dijkstra's Notes on Structured Programming - concerning the program to compute first 1000 prime numbers
In his "Notes on Structured Programming" essay, E. W. Dijkstra gives an example of a program that computes the first 1000 primes (Section 9. "A First Example of Step-Wise Program Composition").

The idea is to iterate all the numbers from 1 to 1000 in increasing order, to test each one and if found to be prime save it into an array *p*. The test consists of giving an answer to the question of whether the number *j* is divided by one of the primes found earlier: if it is divided - the number is *not* prime; otherwise - it is prime.

* *j* is the number under test and here it is assumed to be incremented by 1 at each iteration (in the original paper an optimization has been introduced where *j* is odd and incremented by 2).
* The smallest array index is 1.

Next is an excerpt from the paper followed by the question proper:

> We use the facts that
> (1) \[...\] the smallest potential factor to be tried is *p\[1\]*
> (2) the largest prime number to be tried is *p\[ord - 1\]* where *p\[ord\]* is the smallest prime number whose square exceeds *j*.
>
> (Here I have also used the fact that the smallest prime number whose square exceeds *j* can already be found in the table *p*. In all humility I quote Don Knuth's comment on an earlier version of this program, where I took this fact for granted:
> "Here you are guilty of a serious omission! Your program makes use of a deep result of number theory, namely that if $p\_n$ denotes the $n$-th prime number, we *always* have $$ p\_{n+1} \< (p\_{n})^2 $$ " Peccavi.)

**In my analysis I have arrived at the conclusion that the program does *not* depend on this result; that is - the program will work correctly even if the inequality above were not true.<br>Help is needed in finding the error in my line of reasoning, or to identify the misunderstanding of the source material, if that were the case.**

---

The program makes use of a lemma

> If a natural number $n \> 1$ is composite, then $n$ is divisible by some prime number $p \leq \sqrt{n}$.

(A proof can be found in "Discrete Mathematics" 2nd ed., by Edgar G. Goodaire, page 116)

Thus when we test number *j* for primality we only need to consider those primes whose squares are less than or equal to *j*.

Suppose that we have computed the first $n \> 1$ primes and all of them are in the array *p*. We next initiate the process of computing the next prime $p\_{n+1}$ by incrementing *j* and testing it for primality.
In the case where $p\_{n} \< j \< (p\_{n})^2$, there exists a prime $p\_{k}$ such that $$(p\_{k-1})^2 \leq j \< (p\_{k})^2$$ The potential factors of *j* are $p\_{1},p\_{2},..,p\_{k-1}$ and all of them are in the array *p*, thus if the next prime lies in the interval $p\_{n} \< j \< (p\_{n})^2$ we are guaranteed to find it.
This is the case which corresponds to the theorem pointed by Don Knuth, and since we know it to be true, we could stop here as far as program correctness is concerned.

But for the sake of argument, let's continue and consider the case $j \> (p\_{n})^2$. All of the numbers $p\_{n} \< i \< j$ are composite, so the largest prime less than *j* is $p\_{n}$ and, by our assumption $(p\_{n})^2 \< j$. Thus the potential factors of *j* are $p\_{1},p\_{2},..,p\_{n}$ and all of them are in the array *p*.

Given that in both cases the entire list of primes whose square is less than or equal to *j* is in the table *p*, and that's the necessary and sufficient condition for the primality test, we conclude that the relation $p\_{n+1} \< (p\_{n})^2$ plays no role in the operation of the program.

# Answer
Statement (2) requires that the smallest prime number whose square exceeds $j$ is in the list. If $j=p\_{n+1} \> (p\_n)^2$, then the smallest prime number whose square exceeds $p\_{n+1}$ is $p\_{n+1}$ itself. As $p\_{n+1}$ is not in the list while tested, (2) no longer holds.

You indeed show that all primes that are divisors of $j$ are in the list. So, an algorithm that tests all divisors in the list would be correct. However, this isn't what the algorithm in the text does, it first looks for a prime of which the square exceeds $j$, but *doesn't have to be a proper divisor of $j$*.

So, the algorithm as stated in the text does require property (2), which relies on the fact that $j=p\_{n+1} \> (p\_n)^2$. In your analysis, you made the change that only the primes that divide $j$ properly need be in the list. This is a valid algorithm, but it is a different algorithm than the one in the text.

In other words, while having all primes that are proper divisors of $j$ in the list is nessecary, it isn't sufficient to run the algorithm as stated in the text.
> 1 votes

# Answer
From memory: His algorithm looked for the next prime in the sieve, and exited if that prime squared was too large. The way the code was written, it assumed the next prime is in the sieve, and would go wrong if it wasn’t.

There may not be a p\[ord\] in the sieve with a square large enough.
> 0 votes

---
Tags: algorithms, algorithm-analysis, primes
---


# Question
Title: Removing lambda-productions when it's at the start symbol
I had a question regarding removing lambda-productions from context-free grammars.

I understand that the basic theorem or process for removing lambda-productions is to find nullable productions and replace them with the version of the same production when we use lambda. However, I had a question regarding special cases.

For example:

$$S \rightarrow aSSS$$ $$S \rightarrow bb\ |\ \lambda$$

How do I remove the lambda-production here? Is it even allowed to be removed? If we remove this, then we're fundamentally changing the grammar from one that accepts the empty string to one that doesn't.

This question has been really confusing me, and any help would be greatly appreciated.

thank you!

# Answer
You cannot, in general, remove all $\lambda$ productions. Indeed, if you grammar produces the empty string, then somewhere in the grammar there must be a $\lambda$ production.

There are two ways to handle this problem:

* Consider only grammars not producing the empty string. Such a grammar won't contain the product $S \to \lambda$.
* Allow arbitrary context-free grammars, and also allow the production $S \to \lambda$ (but not $A \to \lambda$ for $A \neq S$). If the grammar does contain the rule $S \to \lambda$, then we also ask $S$ not to be on the right-hand side of any production. Such grammars behave very similarly to grammars without $\lambda$ productions, since the production $S \to \lambda$ can only be used in the derivation $S \Rightarrow \lambda$.
> 5 votes

---
Tags: context-free, formal-grammars
---


# Question
Title: What would be the time complexity for following recurrence?
T (n) = T (n/2) + 2^n

I am solving this using master theorem and I calculated it to be big theta(log2 n) (log n to the base 2). But answer state it to be 2^n.

Any help would be appreciated.

# Answer
> 1 votes
You asked for a solution with the Master Theorem, so let's have a look;

Define your Function as $T(n) = a \cdot{} T \left( \frac{n}{b} \right) + f(n)$. Here you have $a = 1$, $b = 2$ and $f(n) = 2^n$.

Master Theorem has 3 main cases (e.g. shown here):

Case 1 - $f(n) \in \mathcal{O} \left( n^{\log\_b(a)-\epsilon{}} \right)$ with $\epsilon \> 0$

Case 2 - $f(n) \in \Theta \left( n^{\log\_b(a)} \log^k n \right)$ with $k \geq 0 $

Case 3 - $f(n) \in \Omega \left( n^{\log\_b(a) + \epsilon} \right)$ **and** $a \cdot f \left( \frac{a}{b} \right) \leq c \cdot f(n) $ for large $n$ and some constant $c \< 1$

Let's check, which one applies: Inserting $a$ and $b$ into $\log\_b(a)$ gives $\log\_2(1) = 0$ we get $n^{\log\_b(a)} = n^0 = 1$ resulting into $f(n) \in \Omega \left( n^{\log\_b(a) + \epsilon} \right)$.

The other precondition also holds obviously (just put in the numbers for $a$ and $b$ and find a $c$ for yourself).

This results in the 3rd case of the Master Theorem, giving $T(n) \in \Theta (f(n)) = \Theta (2^n) $.

# Answer
> 0 votes
You mention applying the master theorem and obtaining the solution $T(n) = \Theta(\log\_2 n)$. However, assuming that $T(1) \geq 0$, it is clearly the case that $T(n) \geq 2^n$. So you must have applied the master theorem in the wrong way.

In your particular case, you can also just expand the recurrence. Assuming that $n$ is a power of 2 and a base case $T(1) = C \geq 0$, we get $$ T(n) = 2^n + 2^{n/2} + 2^{n/4} + \cdots + 2^2 + C. $$ This is clearly at least $2^n$. If $m \geq 2$ then $m/2 \leq m-1$. Applying this inductively, we see that $$ \begin{align\*} T(n) &\leq 2^n + 2^{n-1} + 2^{n-2} + \cdots + 2^{n-\log\_2 n + 1} + C \\ &\leq 2^n + 2^{n-1} + \cdots + 2^0 + C \\ &= 2^{n+1} - 1 + C \\ &= O(2^n). \end{align\*} $$ Therefore $T(n) = \Theta(2^n)$. With only a little more effort, we can get $$ \begin{align\*} T(n) &\leq 2^n + 2^{n/2} + 2^{n/2-1} + \cdots + 2^{n/2 - \log\_2 n + 2} + C \\ &\leq 2^n + 2^{n/2} + 2^{n/2-1} + \cdots + 2^0 + C \\ &= 2^n + 2^{n/2+1} - 1 + C = 2^n + O(2^{n/2}), \end{align\*} $$ implying the stronger estimate $T(n) \sim 2^n$.

---
Tags: algorithms, time-complexity, recurrence-relation, master-theorem
---


# Question
Title: Is Phong shading a pixel-first computational model?
Wikipedia says that:

> If a mesh covers more pixels in screen space than it has vertices, interpolating colour values from samples of expensive lighting calculations at vertices is less processor intensive than performing the lighting calculation for each pixel as in Phong shading.

Why does it matter that there are more pixels than there are vertices? In the quote it also says that Gourand shading performs lighting calculation "at vertices" while Phong does it in pixels.

I have always thought that both shading schemes are the same, just that Gourand interpolate colours along vertices, while phong creates a reflection vector to interact with the light sources for specular reflection. Is this correct?

# Answer
> 3 votes
I agree that it is a bit superfluous to have the "\[i\]f a mesh covers more pixels in screen space than it has vertices". Basically, if it doesn't then no interpolation is needed since the color of a pixel can be determined by the vertices it contains. But this is just a degenerate case of interpolation and there isn't much reason to call it out.

Your final paragraph is roughly correct, but it does imply that you need to calculate the Phong reflection model at each pixel using the interpolated normal in the Phong shading case while you don't in the Gouraud shading case. In the latter case, you are linearly interpolating colors calculated using the Phong reflection model at the vertices to produce pixel color values. In the former case, you are linearly interpolating normal vectors calculated at the vertices to produce pixel normals which you then use in the Phong reflection model per pixel.

The Phong reflection model is the "lighting calculation".

---
Tags: graphics
---


title: Find all local minima in a big 2d array

text:
# Question
Title: Find all local minima in a big 2d array
Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all local minima in the array?

# Answer
Scan the entire array to check each cell to see whether it is a local minimum.

There's no algorithm that is asymptotically better; this is optimal to within a constant factor. (Proof: if there is any 3x3 region that you haven't looked at, it might contain a local minimum. So any correct algorithm will need to examine at least one cell out of each 3x3 region, i.e., must examine at least 1/9th of the array.)
> 3 votes

---
Tags: optimization, search-algorithms, arrays, matrices
---


# Question
Title: Finding constrained random time intervals with a constrain also on their sum
I'm searching to devise an algorithm that finds a set of *n* time intervals with a random duration between *min* and *max*. On top of that, the total duration is also given (*tot*).

For example:

> n = 15
>
> min = 30 s
>
> max = 90 s
>
> tot = 15 minutes

means: "Find 15 time intervals, each of a duration between 30 and 90 seconds, which, when summed together, produce a total time interval of 15 minutes"

To check whether there is a solution to the problem I would just make sure that
`min * n <= tot <= max * n`.

To make sure that the total duration is equal to *tot* I would apply a found ratio to all the time intervals.

However, how to make sure that the *min* and *max* constrains are met even after the ratio is applied? Am I on the right track?

# Answer
> 0 votes
Let’s consider general parameters $n$, $\min$, $\max$, with $0\<\min\<\max$ and $tot=1$ (you can transform your problem to this form simply by considering 15 minutes as the measure unit for time). What you are trying to do is to sample from the intersection of the following two set:

1. the set $S=\left\\{(x\_i)\_{i=1}^{n}|\Sigma\_{i=1}^{n}x\_i=tot=1\right\\}$, the canonical n-dimensional simplex, and
2. the set $C=\left\\{(x\_i)\_{i=1}^{n}|\forall i\\, x\_i \in \[\min,\max\]\right\\}=\[\min,\max\]^n$ which is a n-dimensional hypercube in the first octant.

To see the shape of this set let’s fix $n=3$, so we now are in a $3$-dimensional space and the hypercube is an actual cube. The cube depends on the parameters $\min$ and $\max$. If you keep the radius $R=\frac{\min-\max}{2}$ constant and change the mid-point $m=\frac{\min +\max}{2}$ of the interval $\[\min,\max\]$ you are translating the cube with direction $\left(1,1,1\right)$. Instead if you change radius $R$ but keep the mid-point $m$ constant you get are expansion (the edge of) the cube.

The intersection of the simplex and the cube is a hexagon, whose regularity depends on the value of $R$. Moreover, it may happen that the hexagon collapses to a triangle, or to a point or to the emptyset (in these two cases you can sample only one point or none at all, so the problem is trivially solved). So, if we know how to compute the vertices of the hexagon, the problem reduces to a sampling from a hexagon.

To compute the vertices notice that they lie only on those edges of the cube such that one end-point lies “above” the simplex and the other “below”. So you could search all the couple of adjacent vertices of the cube such that one end-point satisfy the constraint $x+y+z\geq1$ and the other satisfy the constraint $x+y+z\leq1$. For all these couples $\left(e\_1,e\_2\right)$ you can parametrize the segment $e\_1e\_2$ in the form $Le\_1+(1-L)e\_2$ for all $L$ in $\left\[0,1\right\]$ and then find that particular $L$ such that the point on the segment lies on the simplex, i.e. find L such that $x\_L +y\_L + z\_L=1$ where $(x\_L,y\_L,z\_L)= Le\_1+(1-L)e\_2$.

Once you have computed the six vertices of the hexagon you should be able to decide if it is really a hexagon -if all vertices are distinct- or a triangle -if there are only three distinct vertices- or something trivial.

To sample from a triangle you can, for example, find a transformation $\varphi$ from the canonical simplex to the triangle, sample from the simplex (for example as in cs.stackexchange.com/q/3227/755 as suggested by D.W.) and then transform the sample using $\varphi$. To ensure uniformity you should sample uniformly in the simplex and normalize $\varphi$ with the norm of the determinant $d$ of its jacobian matrix (when $d\neq 0$), i.e. use the transformation $\psi =\begin{cases}\varphi & \text{if } d=0\\\frac{\varphi}{d} &\text{if } d\neq 0 \end{cases}$.

To sample from a hexagon you can divide the hexagon in six triangles drawing the edges from the vertices to an inner point of the hexagon (for example $\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)$; infact, this point is a possible sample if and only if there is at least one sample), choose randomly one of them, and then sample from that triangle. In this case to get uniformity, on top of sampling uniformly from triangles, you should choose the triangles using a probability distribution $\left(p\_i\right)\_1^6$ of the form $p\_i =\frac{\text{area of the }i\text{-th triangle}}{\text{area of the hexagon}}$ (with this choiche you cover also the case of a collapsed hexagon). However, I suppose there are much more refined methods to sample from a triangle or from a hexagon.

Generalizing to grater values of $n$, instead of a hexagon divided in six triangles, you should get a $n-1$ dimensional convex surface whose vertices can be computed as above. This surface can be divided in some $n-1$ dimensional simplicial polytopes. So you select randomly one of these polytopes accordingly to their volume, find a transformation from the $n-1$ canonical simplex to this polytope and use it to transform a sample from the $n-1$ dimensional simplex.

---
Tags: algorithms
---


# Question
Title: Assertion of Type Inference Rules/Type Checking
I have a problem in a book I am trying to accomplish.

I understand the overall type of the expression is boolean and how it derives. (y * x) will be rule 4 (counting from top right). (y * x) + x when evaluated will be rule 3 and the overall expression when evaluated will be rule 5.

What I want to figure out is what is the correct way to illustrate the my working? Can someone give or link an example of the correct way to answer a question like this?

---

**Question 2**

Proposed solution:

# Answer
> 5 votes
Well, you need to construct a typing derivation which has what you want to prove as a conclusion, and no open premise (i.e., leaves must be axioms, or rules with no premises). In the case of your example, the conclusion will be

$$ int\\;x,\\,int\\;y\\;\vdash\\;(x \< (x \times y) + x) : bool $$

so the proof will start by

$$ {int\\;x,\\,int\\;y\\;\vdash\\;x : int \quad\quad\quad int\\;x,\\,int\\;y\\;\vdash\\;((x \times y) + x) : int} \over {int\\;x,\\,int\\;y\\;\vdash\\;(x \< ((x \times y) + x)) : bool} $$

and then you continue building up the tree until you reach leaves (i.e., rules with no premises). This will immediately be the case in the left branch since you only have a variable.

---

Here is the full proof (as an image):

---
Tags: compilers, type-theory, type-checking, type-inference
---


# Question
Title: Variant of nim game with particular rules
Let's say we have the following rule for that particular Nim game: You have multiple heaps, and you have to remove 1,2 or 3 sticks (not more) from a SINGLE choosen heap. The player who pick up the last stick LOSES. (misere game). Is there an algorithm which solves this variant of Nim game ?

Thanks in advance!

# Answer
The following answer solves your game under *normal* play when there is a *single* heap. You can accommodate multiple heaps using Sprague–Grundy theory. Using a very similar approach, you can also handle *misère* rules.

You can solve combinatorial games by calculating the winning and losing positions recursively, using the following algorithm (for your special case):

```
for n from 0 to infinity:
   set Win[n] to True if n ≥ 1 and Win[n-1] is False
   set Win[n] to True if n ≥ 2 and Win[n-2] is False
   set Win[n] to True if n ≥ 3 and Win[n-3] is False
   otherwise, set Win[n] to False

```

Here are some empirical results, starting at $n=0$:

```
False, True, True, True, False, True, True, True, False, True, True, True

```

The pattern repeats, so one can conjecture that $Win\[n\]$ is true iff $n$ is not a multiple of 4. It is not hard to prove this guess by induction. Clearly 0 is a losing position, and 1,2,3 are winning positions since we can remove 1,2,3 (respectively) to get to 0. Now 4 is a losing position, since whatever we remove gets us to one of the winning positions 1,2,3. As before, 5,6,7 are winning positions, since we can get down to 4. And so on.

In the same way, you can compute the Sprague–Grundy function, which is $g(n) = n \bmod 4$. This allows you to solve the multiple heap version of this game.
> 1 votes

---
Tags: algorithms, complexity-theory, search-algorithms, game-theory
---


# Question
Title: Is it NP hard to decide whether there exists a subset of V of size at most $k$ hitting all maximal bicliques of G?
The following problem is from my algorithms class:

> Given a graph $G(V, E)$, a set $C \subseteq V$ is called a *biclique* iff $G\[C\]$ is a complete bipartite graph, where $G(C)$ is the subgraph induced by $C$. A biclique is called **maximal** if it is not a subset of a larger biclique. Then our problem asks whether there exists a subset of $V$ of size at most $k$ hitting all maximal bicliques of $G$, i.e., can we find $k$ vertices in $V$ such that every maximal bicliques of $G$ cantains at least one vertex of these $k$ vertices. Prove the problem is NP hard.

I'm trying to prove $$\text{Vertex-Cover} \le\_p \text{This-Problem}$$ but haven't came up with a solution until now. Could anyone help me out here?

# Answer
## Is an independent set a biclique?

After figuring out the first reduction from Vertex Cover (VC) described below, I realised that I had assumed that a biclique has at least one vertex in each part (and thus at least one edge). But in many ways it makes more sense to consider an independent set (IS) to be a biclique too: it *is* a complete bipartite subgraph induced by two disjoint vertex subsets $A$ and $B$ -- it just happens that one of the subsets is empty -- so it (vacuously) meets the criteria. (Similarly, a one-vertex graph is still considered a bipartite graph, and still considered a clique.) I could not quickly find a "standard" definition to confirm either possibility, so I'll first give a reduction that considers only complete induced bipartite subgraphs with both vertex sets nonempty to be bicliques, and then describe how to modify the construction when independent sets are also considered to be bicliques (which turned out to be much trickier).

I'll call the problem in question "Maximal Biclique Hitting Set" (MBHS). A biclique that contains at least one edge (i.e., is not an IS) is an "edgy" biclique.

## Reduction from Vertex Cover for "edgy" bicliques

The following construction builds a MBHS instance $(G' = (V', E'), k')$ that replaces every edge in the input graph $G = (V, E)$ with a "rectangle" in which the two pairs of diagonally opposite vertices form a 4-vertex maximal biclique.

Add all vertices and edges in $G$ to $G'$. For every edge $uv$ in $E$, create two new vertices $x\_{uv}$ and $y\_{uv}$ in $G'$, and the three edges $x\_{uv}y\_{uv}$, $uy\_{uv}$ and $vx\_{uv}$. Set $A\_{uv} = \\{u, x\_{uv}\\}$ and $B\_{uv} = \\{v, y\_{uv}\\}$ and observe that $(A\_{uv}, B\_{uv})$ forms a biclique with 2 vertices in each part.

To see that this biclique is maximal, consider any other vertex $z \in V' \setminus \\{u, v, x\_{uv}, y\_{uv}\\}$. To be able to add $z$ to $A\_{uv}$ to form a larger biclique $(A\_{uv}', B\_{uv})$, $z$ must be adjacent to both $v$ and $y\_{uv}$ -- but by construction, the only vertices adjacent to $y\_{uv}$ are $x\_{uv}$ and $u$, and $z$ is not either of those. Similar reasoning shows that $z$ cannot be added to the other side ($B\_{uv}$) either. Since $z$ was arbitrary, $(A\_{uv}, B\_{uv})$ must be a maximal biclique.

Finally, set the threshold parameter $k'$ for the MBHS instance to $k$. This concludes the construction. I'll now show that the constructed MBHS instance is a YES-instance if and only if the original VC instance is a YES-instance:

**If there is a solution to the VC instance of size at most $k$, then there is a solution to the constructed MBHS instance of size at most $k'$.** The VC directly gives a solution to the MBHS instance, since every maximal biclique in $G'$ (both the rectangle bicliques that we created, and any bicliques already present in $G$) contains some edge of $G$, and every edge of $G$ contains at least one vertex in the VC solution.

**If there is a solution to the constructed MBHS instance of size at most $k'$, then there is a solution to the original VC instance of size at most $k$.** Assume there is an edge $uv$ in $G$ whose corresponding edge in $G'$ is not covered (i.e., neither of its endpoint vertices is in the MBHS solution), since otherwise we are already done. Let $(\\{u, x\_{uv}\\}, \\{v, y\_{uv}\\})$ be the unique rectangle maximal biclique that contains $uv$ in $G'$: then it must be that at least one of $x\_{uv}$ or $y\_{uv}$ is in the MBHS solution, since there is no other way to hit this biclique. Replace whichever one of these two vertices is in the solution (choose arbitrarily if both are) with either $u$ or $v$ (again, choose arbitrarily) to create a new MBHS solution of the same size (at most $k$) with one more $G$-edge covered. This can be repeated until every edge in $G$ is covered by a vertex in the MBHS solution, which remains of size at most $k$. Finally, discard any remaining "rectangle vertices" (vertices not in $V$) from the solution, leaving a VC of size at most $k$.

## When independent sets are considered bicliques too

If independent sets are also bicliques, the construction above can fail, most obviously on a graph containing vertices but no edges (which has a single maximal biclique, but an empty VC).

Create $|V|+1$ copies of $G'$ (that is, of the graph constructed for the reduction for edgy maximal bicliques). Call this new graph $G''$. The key observation is that in $G''$, **there are $|V|+1$ copies of each maximal edgy biclique in $G'$ that all need to be hit separately, but a set of vertices that hits every maximal IS in a single copy of $G'$ suffices to hit every maximal IS in $G''$.** (There are actually vastly more maximal ISes in $G''$ than in $G'$, since to form a maximal IS in $G''$, we may independently choose a maximal IS from each copy of $G'$. But an IS in $G''$ cannot be maximal unless it includes *some* $G''$-IS in each copy -- so it suffices to choose a particular copy and hit every maximal IS in that copy.)

Let $k''$ be the threshold parameter that together with $G''$ forms the constructed instance of MBHS. Set $k'' = k(|V|+1) + |V|$. Essentially this allows us to spend $k$ vertices hitting edgy maximal bicliques in each of the $|V|+1$ copies of $G'$, plus up to $|V|$ vertices to hit maximal ISes.

That ends the description of the construction. I'll now show that the constructed MBHS instance is a YES-instance if and only if the original VC instance is a YES-instance:

**If there is a solution to the VC instance of size at most $k$, then there is a solution to the constructed MBHS instance of size at most $k''$.** To see this, first replicate the VC solution across all $|V|+1$ copies of $G'$ in $G''$: these vertices hit every *edgy* maximal biclique for a cost of $k(|V|+1)$. Now add every remaining vertex from the first copy of $G'$ to the solution, ensuring that we hit every maximal IS in that copy of $G'$, and thus every maximal IS in $G''$ overall, for at most $|V|$ more vertices. Every maximal biclique is now hit and we have used at most $k(|V|+1) + |V| = k''$ vertices.

**If there is a solution to the constructed MBHS instance of size at most $k''$, then there is a solution to the original VC instance of size at most $k$.** By the pigeonhole principle, at least one of the $|V|+1$ copies of $G'$ has at most $k$ vertices in the solution. These $k$ vertices necessarily hit all edgy maximal bicliques in that copy, since there is no other way to hit these bicliques, and so can be transformed into a solution to the original VC instance of size at most $k$ in the same way as described earlier for the "edgy bicliques" version of the reduction.

Obviously all steps can be carried out in polynomial time, so the MBHS problem is NP-hard. (It's not clear to me that it is in NP though -- there could be exponentially many maximal ISes (consider a $3n$-vertex graph consisting of $n$ vertex-disjoint triangles), so checking that each one is hit takes too long. Does anyone have thoughts on a certificate that can be checked in poly-time?)

## Bonus material: A failed reduction attempt

My first attempt at dealing with non-edgy bicliques was to add one new vertex $p$ to $G'$, and connect it to every other vertex in $G'$: Now every maximal independent set originally in $G'$ becomes a maximal biclique with $p$ on one side, and intuitively it seems that it would be a good idea to include $p$ in the MBHS solution, as it would hit every such biclique for the cost of just 1 vertex. The problem is that it could be that every maximal IS in $G'$ is already hit by some vertex in the VC, meaning that it is not actually necessary to include $p$, and that doing so would therefore yield a suboptimal solution. (This can happen when the given threshold $k$ is loose; in particular, it will always happen for $k=|V|$. *If* OTOH $k$ is the minimal threshold for which the answer to the VC problem is YES, then at least one maximal IS misses every vertex in the VC solution, and we would be justified in forcing $p$ into the solution -- but we don't know whether this is the case at the point when we are mapping the VC instance to the MBHS instance, and it is NP-hard to find out!) The general approach here, of trying to design a gadget that will cause all ISes in $G'$ to become edgy bicliques, can be expressed precisely as: Find a small graph that has an optimal MBHS solution with the additional property that every maximal IS in the graph is hit by some vertex in the solution. But after trying several examples with 2, 3 or 4 vertices, I wasn't able to come up with such a gadget.
> 3 votes

# Answer
Transformation from *Hitting Set* to this problem. In the *Hitting Set* problem, we are given a collection $C=\\{S\_i\\}$ of subsets of a universal set $U$ and an integer $k$, the question is that if one can choose $k$ elements of $U$ to hit all the subsets. The *Hitting Set* problem can be described as a bipartite graph $B=(U\cup C,E)$. We may add the following constraint without affecting its NP-completeness: $S\_i \not\subseteq S\_j$ for any $S\_i, S\_j\in C$. By this constraint, each $S\_i$ and its members form a maximal biclique. On the other hand, a vertex subset hitting all $S\_i$ clearly hits all the maximal bicliques. That is, a vertex subset $H$ hits every maximal biclique if and only if $H$ hits every $S\_i$ in $C$. To complete the reduction from *Hitting Set* to this problem, it is easy to show that if there are $k$ vertices in $U\cup C$ hitting all $S\_i$, then there are $k$ vertices in $U$ hitting all $S\_i$.
> -1 votes

---
Tags: complexity-theory, graphs, reductions, np-hard
---


# Question
Title: Can one quickly update CRC codes based on small change and previous CRC code?
I asked this on StackOverflow, but, alas, no answers.

I'd like to use CRC or similar codes to check whether certain very large objects are likely to be identical. The trouble is, small parts of these objects are sometimes modified, and it would be very inefficient to re-compute CRC code from the entire object. Think of multiple large images, pre-signed with CRC, and of a software the changes single pixels of some of those images and updating those images' CRCs.

Is it possible to re-compute CRC based on: previous CRC value, location of the changed byte, old value of that byte, and the new value of that byte?

If not, what signature scheme would allow that?

# Answer
Yes, this is possible. The new CRC value can be computed very efficiently.

To see how, you need to know some math and about how CRCs can be viewed as polynomials. The CRC checksum of the bit-string $c\_0,\dots,c\_n$ can be viewed as the value of $c(x) \bmod p(x)$, where $p(x)$ is the CRC polynomial and $c(x) = c\_n x^n + \dots + c\_0$ and all arithmetic is done modulo 2. Let $r(x)$ denote the checksum, i.e., $c(x) \bmod p(x)$. Now if you change the $i$th bit $c\_i$ to $c'\_i$, then the new checksum will be given by $c'(x) \pmod{p(x)}$ where we define the polynomial $c'(x) = c(x) - c\_i x^i + c'\_i x^i$. The checksum will be $c'(x) \bmod p(x)$, which has the form

$$c'(x) \equiv c(x) - c\_i x^i + c'\_i x^i \equiv r(x) + (c'\_i-c\_i) x^i \pmod{p(x)}$$

Since we already know $r(x)$ (it's the checksum of the original file), all we need is to compute the value of $(c'\_i-c\_i) x^i \bmod p(x)$. Naively, you might think this takes $O(i)$ time -- potentially slow. But in fact this can be done very efficiently using fast modular exponentiation, so we compute $x^i \pmod{p(x)}$, then multiply by $c'\_i-c\_i$, and we get $(c'\_i-c\_i) x^i \bmod p(x)$. Then we add that to the original checksum $r(x)$. (All arithmetic is done modulo 2, so here "addition" really means xor.) That gives us the new checksum for the modified file.

If the modification changes multiple bits, there is a natural extension of the move to show how to compute the updated checksum as well.
> 5 votes

---
Tags: crc
---


# Question
Title: What is the range of possible IP addresses when expressed as decimal and hexadecimal?
I know that there are $2^{32}$ different combinations of IPv4 addresses possible , if expressed in binary.

In decimal notation, they range from $0.0.0.0$ to $255.255.255.255$.

So are there $256^{4}$ possibilities if expressed in decimal?

And $16^{4}$ in hexadecimal?

Thank you.

# Answer
The number of possible addresses is unaffected by the base you are using to write the addresses. The base is irrelevant to the problem of counting how many possible addresses there are.

Note that the $256^4$ figure you obtained is equal to $2^{32}$. In hexadecimal, the addresses range from $00.00.00.00$ to $\text{FF}.\text{FF}.\text{FF}.\text{FF}$, which gives $16^8 = 2^{32}$ possible addresses. To reiterate: the base only determines how you write the addresses, not the numerical values the address has. There are always $2^{32}$ distinct addresses.
> 1 votes

---
Tags: number-formats
---