title: GPR registers in computer

text:
# Question
Title: GPR registers in computer
How to ensure data integrity in General Purpose Registers (GPR registers) given their limited number (for x86 their number is 6),and on the other hand that they are used simultaneously by all processes?

# Answer
Their integrity is maintained by several features working in conjunction.

For synchronous code execution, function calls, i.e. invocations, generally require some management. This management is named the calling convention. Both caller and callee must agree on the same convention or else things break. (It is possible for one caller and callee to agree, then have that callee, now play caller to call someone else, using an alternate calling convention they both agree upon. This works but might make stack unwinding more complex for the debugger, or for error handling/exceptions.) The calling convention dictates how parameters are passed (registers & stack), how return values are passed back, and certain registers don't participate in the invocation and are particularly designated for retaining their original caller-defined values across the call — meaning that if the callee want to use those designated registers it has to save them first, and then restore them before returning.

For asynchronous code execution of threads/processes, either the hardware provides multiple CPUs or the software is time-slicing the CPUs, or both.

If the hardware provides multiple CPUs (whether by hyperthreading or full blown CPUs), it provides sufficient register sets for all the CPUs, so it provides a copy of the necessary processor state for each provided processors. Some of the computation units may be shared (e.g. in hyperthreading), but the register state is duplicated.

When software (e.g. operating system) does time-slicing, it uses a clock or other interrupt to suspend one thread's operation, and resume another thread (that had may have been previously suspended in a similar manner).

The interrupt mechanism itself requires cooperation between hardware and software. Generally speaking, the hardware provides the minimal features necessary, and leave the rest up to software — although on more modern processors, some features the software could do are taken over by the hardware so that operating systems don't require as much customization for new CPUs.

The interrupt mechanism was invented around the time of the DEC PDP-1 processor, ~1959, and was then called Sequence Break System. Before that, processors ran mostly batch jobs and did I/O synchronously. With the introduction of the interrupt mechanism, the processor can be signaled by an external connector to take an unscheduled branch to an interrupt handler aka interrupt service routine. At every sequence point in the processors execution where it could service an interrupt, some hardware is checking that external pin to see if an interrupt is being requested. A clock is one device that regularly interrupts, I/O devices also interrupt. When an interrupt handler runs the hardware must preserve, minimally, any (register) state of the thread that it destroys in switching to the interrupt service routine, for example, the PC, since starting interrupt service routine is effected by making the CPU take an (unscheduled) branch. This could be done by having two PC registers (one main one and a shadow one for remembering the old PC at time of interrupt) or by using some prearranged memory location to store the PC of the interrupted code. Depending on the processor architecture some other shadow registers may be provided, like an alternate stack pointer. These things would make the interrupt handler easier to program (though the initial handler still would have to be written in assembly, not even C). Once the handler is running, it will save any other state for the interrupted thread, so that it can do some work using the CPU in a rather normal way, and still resume the interrupted thread later — maybe much later, after first giving some other threads a time slice.

Have a look at this answer for more information on the subject of interrupts.

See also MultiThreading on Single Core, and here Interrupts vs. Exceptions
> 3 votes

---
Tags: computer-architecture
---


# Question
Title: Solving recurrence $T_k(n) = T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$
I am currently solving a problem that I have reduced to computing the following function efficiently.

$$T\_k(n) = T\_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T\_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$$

The base cases are $\forall n \< k: T\_k(n) = 0$ and $\forall k \leq n \< 2k: T\_k(n) = 1$ Note: $n$ and $k$ are non-negative integers.

I need to compute this function for multiple values of $k$ and $n$.
I can compute this function in $\theta(n)$ by a simple recursive function using just the definition and speed up the computation by using memoization. However, this isn't fast enough and I was wondering if there is a closed form expression for it and can be computed in $o(n)$.

I have no idea how to solve this recurrence.

# Answer
> 2 votes
Observe that $T\_k(2^n k) = 2^n$. Furthermore, it is easy to see that either $T\_k(\alpha) = T\_k(\alpha-1)$ or $T\_k(\alpha) = 1+T\_k(\alpha-1)$. Using the previous two results, it can also be shown that $T\_k(2^n k - 2^{n-1}) = T\_k(2^{n-1} k)$.

Now, consider $$\delta\_k(n) = T\_k(2^n k - 2^{n-1} + 1) - T\_k(2^n k - 2^{n-1} )$$

It should be easy to prove by induction that for all $k, n$ it holds that $\delta\_k(n) = 1$. This should be sufficient to uniquely determine the value of $T\_k(n)$ for all $n$.

# Answer
> 2 votes
While working through the equalities that quicksort mentioned, I noticed the generalization $T\_k(2^n j) = 2^n \text{ for } j \in \\{ k \text{..} 2 k-1\\}$

Then I calculated some values for k=3:

$2^n j$ = {3..5; 6..10; 12..20; 24..40; 48..80; 96..160}

$T\_3(...)$ = {1; 2; 4; 8; 16; 32}.

and I noticed that the groups are separated by just enough numbers for the value to increase by at most 1. This leads to the following algorithm (in python3):

```
def Tk(k, n):
    if n < k:
        return 0
    if n < 2 * k:
        return 1
    a = math.floor(math.log(n/k, 2))
    end = pow(2, a) * (2*k-1)
    if n > end:
        return pow(2, a) + (n - end)
    return pow(2, a)

```

# Answer
> 1 votes
The definition leads directly to the (rather) closed formula

$T\_k(n) = 0$ for $0 ≤ n \< k$

$T\_k(n) = 1$ for $k ≤ n \< 2k$

$T\_k(n) = 2^m$ for $2^mk ≤ n ≤ 2·2^mk-2^m$

$T\_k(n) = 2·2^m - j$ for $n = 2·2^mk-j$, $2^m \> j ≥ 1$

Proof: Assume n is the smallest counter example and check it gives the result as proposed.

---
Tags: recurrence-relation, recursion
---


# Question
Title: Avoiding correlated values and reduced collision resistance in multiple hash states
I need to design a hash function that fits this criteria:

1. Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system)
2. Produces an n-bit hash digest, greater or equal to 64-bit, with the expected collision probability of a hash of that size. Effectively combining multiple uncorrelated 32-bit states.

However, it seems care must be taken with this approach. I cannot verify it myself, but computing two 32-bit hashes using the same message but a different seed may cause more collisions than expected from a 64-bit hash, due to the two values being correlated.

This issue also seems to extends to the output of a single hash function that outputs two 32-bit results to form a 64-bit (which is exactly what I am trying to do).

I found MurmurHash64B (link to C++ code) which seemed almost ideal for my purpose. It produces a 64-bit hash using 32-bit operations at no significant performance cost.

But on the SMHasher wiki, the author mentions this about what I suspect to be the same function:

> MurmurHash2\_x86\_64 computes two 32-bit results in parallel and mixes them at the end, which is fast but means that **collision resistance is only as good as a 32-bit hash**. I suggest avoiding this variant.

Then I saw this exchange on the subject:

> * Hacker News comment by martincmartin:
> Computing two 32-bit results in parallel and mixing them at the end does NOT mean collision resistance is only as good as a 32-bit hash. For that, you need to compute ONE 32-bit result, then transform it into a 64-bit result.
>
> + Hacker News comment (reply) by finnw
>     Depends whether the two 32-bit hashes are correlated with each other. If there is no correlation then a pair of 32-bit hashes is no more likely to collide than a single 64-bit hash. But this is difficult to achieve, and you should not assume (for example) running the same algorithm twice with different initial states will produce uncorrelated hashes.

So then, is this function really not as good as a 64-bit hash? A naive test: Searching for a collision in state `h1` doesn't seem to cause collisions in state `h2`. Is it simply not sufficiently mixing the states? It only mixes `h1` and `h2` at the end, not within the input mixing phase.

MD5 for example which also uses 32-bit arithmetic, computes four hash states which I assume must not suffer from this issue. There also exists a `MurmurHash3_x86_128` which computes a 128-bit hash using four 32-bit states and appears to mix it more thoroughly (which has no mention of being weaker by the same author).

**So I am wondering how can it be shown that `MurmurHash64B` (or a similar function) has correlated values that could result in reduced collision resistance than expected of the digest size.**

# Answer
MurmurHash2\_x86\_64 (aka MurmurHash64B) works as follows: it computes a 32-bit value $h\_1$ based on bytes 0-3, 8-11, 16-19, 24-27, etc. of the input; it computes a 32-bit value $h\_2$ based on bytes 4-7, 12-15, 20-23, etc. of the input; and then it mixes and combines these two values to obtain a 64-bit hashcode, computed as a function of $h\_1,h\_2$. (Here by $h\_1$ I mean the value of the variable `h1` at line 180 in the source code you linked to.)

There is a sense in which this has only 32-bits of collision resistance. In particular, if we consider two inputs that are the same in bytes 0-3, 8-11, 16-19, etc., and differ only in the other bytes, then there will be a $1/2^{32}$ chance that they collide. Why? Because there is a $1/2^{32}$ chance that they end up with the same $h\_1$ value just by chance; and they will certainly end up with the same $h\_2$ value (since it depends only on bytes that are the same for both outputs); so there is a $1/2^{32}$ chance they collide. This is the same chance of collision as for a 32-bit hash. For a 64-bit hash, you might expect a collision probability of $1/2^{64}$.

So this is a sense in which MurmurHash2\_x86\_64 is less than ideal, i.e., a sense in which one might say it has only 32 bits of collision resistance. Whether it is relevant in your practical situation is unknown.

The latest version of MurmurHash is MurmurHash3. MurmurHash3 supports a 128-bit output. A reasonable approach would be to compute a 128-bit hash using MurmurHash3, then discard all but the first 64 bits.
> 2 votes

---
Tags: algorithm-analysis, probability-theory, hash, hashing, algorithm-design
---


# Question
Title: Computational Complexity of a special case of Integer Programming
Integer Linear Programming (ILP) is NP-complete. However, there are special instances that can be solved in polynomial time. I am curious about the following integer program (IP) with equations and inequalities in $y\_i, c\_i, x \in \mathbb Z$ of the following form:

$$\begin{align\*} A\_i + B\_i y\_i+ c\_i &= x \\ c\_i^2 &\> 0\\ c\_i^2 &\< B\_i^2\\ y\_i &\geq 0 \end{align\*}$$

where $A\_i, B\_i \in \mathbb N^+$ are given. I wasn't able to find much on this special case. Anyone please?

# Answer
It is NP-hard, by reduction from 3SAT.

Your problem is equivalent to the following: given a system of inequalities of the form $x \not\equiv A\_i \pmod{B\_i}$, where the $A\_i,B\_i$ are given, test whether any solution exists. (Why? If $0 \< c\_i^2 \< B\_i^2$ then $c\_i \not\equiv 0 \pmod{B\_i}$, and vice versa.)

Now 3SAT can be reduced to this problem (satisfiability of a system of inequalities), so it follows that this problem is NP-hard. Here's how the reduction works.

Let $\varphi$ be a 3SAT instance, with variables $v\_1,\dots, v\_n$. Let $p\_1,\dots,p\_n$ be the first $n$ primes. Add inequalities of the form $x \not\equiv 2 \pmod{p\_i}$, $x \not\equiv 3 \pmod{p\_i}$, ..., $x \not\equiv p\_i-1 \pmod{p\_i}$ for each $i$, forcing $x$ to be either 0 or 1 modulo each prime. Now, suppose we have a clause $v\_i \lor v\_j \lor v\_k$. This translates to an inequality $x \not\equiv 0 \pmod{p\_i p\_j p\_k}$. The clause $v\_i \lor \neg v\_j \lor v\_k$ translates to $x \not\equiv \alpha \pmod{p\_i p\_j p\_k}$ where $\alpha$ is the unique value such that $\alpha \equiv 0 \pmod{p\_i}$, $\alpha \equiv 1 \pmod{p\_i}$, and $\alpha \equiv 0 \pmod{p\_i}$ (you can find $\alpha$ using the Chinese remainder theorem). And so on -- in this way, each clause can be translated into an inequality.

Finally, there exists a value $x$ that satisfies all of these inequalities if and only if there exists an assignment that satisfies $\varphi$. (Why? $x\equiv 1 \pmod{p\_i}$ corresponds to setting $v\_i$ to true, and $x\equiv 0 \pmod{p\_i}$ corresponds to setting $v\_i$ to false. You can then verify equivalence between clauses and inequalities.) Since the resulting system has size polynomial in $n$, this gives a polynomial-time reduction from 3SAT to your problem.
> 3 votes

---
Tags: complexity-theory, integer-programming
---


title: On NP and PP in RP?

text:
# Question
Title: On NP and PP in RP?
Does $NP\subseteq RP\implies NP=RP$?

Does $PP\subseteq RP\implies \oplus P=NP=RP$?

At least what additional minimal conditions will give truth of above?

# Answer
> 0 votes
To see why the first implication holds, note that you can use the sequence of coin tosses as a witness (if the input is not in the language, no accepting sequence exists).

As for the second implication, note that $\mathsf{\oplus P\subseteq P^{PP}}$, since you can find the exact number of accepting paths using binary search. If $\mathsf{PP=RP}$, then $\mathsf{\oplus P\subseteq P^{RP}}$. Since $\mathsf{PP}$ is closed under complement, you have $\mathsf{RP=coRP=ZPP}$, which means $\mathsf{\oplus P\subseteq P^{ZPP}\subseteq RP}$. I doubt that you can show $\mathsf{RP\subseteq \oplus P}$ in this case, since relativizing techniques won't do here. In "NP Might Not Be As Easy As Detecting Unique Solutions" by Beigel et al. they construct an oracle relative to which $\mathsf{ZPP=EXP}$ (implying $\mathsf{PP=RP}$) and $\mathsf{P = \oplus P}$, which means $\mathsf{RP\nsubseteq \oplus P}$.

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Algorithm to sort n numbers from 0 to $n^m$ in $\mathcal{O}(n)$? where m is a constant
So i came upon this question where:

we have to sort $n$ numbers between $0$ and $n^3$ and the answer of time complexity is $\mathcal{O}(n)$ and the author solved it this way:

first we convert the base of these numbers to $n$ in $\mathcal{O}(n)$, therefore now we have numbers with maximum 3 digits.

now we use radix sort and therefore the time is $\mathcal{O}(n)$

so i have three questions :

1. is this correct? and the best time possible?
2. how is it possible to convert the base of n numbers in $\mathcal{O}(n)$? like $\mathcal{O}(1)$ for each number? because some previous topics in this website said its $\mathcal{O}(M(n) \log(n))$?
3. and if this is true, then it means we can sort any $n$ numbers from $0$ to $n^m$ in $\mathcal{O}(n)$?

# Answer
> 4 votes
The reason of your confusion is that the computational model under which the algorithm is run is not specified.

Assuming you are allowed to perform arithmetic in $\mathcal{O}(1)$ time$^\*$, then the $\mathcal{O}(mn)$ bound is correct. The reason is that you don't need to explicitly make base conversions. Since radix sort only ever compares digits of numbers, it is sufficient to provide a way to compare arbitrary digits in $\mathcal{O}(1)$ time$^{\**}$; it is not hard to convince yourself that given an integer $x$, the $i$-th digit from the right in the base $b$ representation of $x$ is exactly:

$\qquad x/b^{i-1} \ \\% \ b$

where $\\%$ is the modulo operator.

Under more stringent conditions on arithmetic (such as classical random access machines or constantly-bounded Word-RAMs), both taking the modulo and division by a constant are operations that take logarithmic time, changing the running time of radix sort accordingly.

---

$^\*$ For example, with a Word-RAM model with $w \ge \log n$.

$^{\**}$ Notice that this is consistent with practice. If you have any sense, you would set $b$ to be a power of two in an implementation.

---
Tags: algorithms, sorting
---


# Question
Title: monotone min-3-sat polynomial algorithm?
I know that 3SAT is npc but i wonder why my little algorithm won't solve this problem:

given positive 3SAT - meaning: each of the m clauses is a disjunction of 3 literals over the variables $x\_1,\dots,x\_n$ ($n$ variables) and each literal is a positive appearance of a variable (no $~x\_i$).

for example: $(x\_1 \lor x\_3 \lor x\_7) \land (x\_5 \lor x\_4 \lor x\_2)$

What is wrong with this "greedy" algorithm?:

run through all left clauses and find the variable that appears in most of them (can be implemented by counters array..). take this variable, give him truth assignment, remove all clauses which he appeared in, zero the counters array and do again the previous step. stop when no clauses left. it looks like this algo runs in $O(m^2n)$ time.

why isn't it not an optimal algorithm?

UPDATE: Sorry for the vague question, The problem is probably called MIN 3SAT, which every literal is positive but you must find minimum integer k such that there exists a truthful assignment of the variables which sets k variables to TRUE.

UPDATE 2: Can someone give me an example to why the greedy algorithm won't give the optimal solution? I read what rus9348 wrote but I still can't figure why the greedy approch is not good..

# Answer
3SAT is NP-complete. Positive 3SAT (where all literals are positive) is in P, and thus presumably not NP-complete. There is an even simpler algorithm for Positive 3SAT: set all variables to true. That will always provide a satisfying assignment.

I can't comment on your algorithm because it doesn't seem fully specified: you describe what order to make assignments to variables, but you don't describe how to choose a truth assignment for each variable. (Should it be set to true? to false? The question doesn't say.)
> 4 votes

# Answer
answer to update 2: take this example

$(x\_1,x\_2,x\_4), (x\_1,x\_2,x\_5), (x\_1,x\_3,x\_4), (x\_1,x\_3,x\_5), (x\_3), (x\_2)$

By greedy, you will have 3 literals to set to true - $x\_1, x\_2, x\_3$. But optimal answer is - $x\_2, x\_3$.

The greedy approach does not work, because when you removing bigger number of clause, may be you are removing clauses for optimal choices.

If you are trying to derive a heuristic, you can try next level of heuristic as instead of choosing only one maximum variable, you can choose two variables which cover most of the clauses. but it still won't be optimal, because it is not considering three variables which together cover most of the clauses.

If you are considering k literals with most appearance, the complexity would be, $O(m^2\binom{n}{k})$. So if you are trying for each possible $k$, total complexity would be $O(m^2 \sum \binom{n}{k}) = O(2^n)$. So the exponential factor comes!

By the way, this was a very intuitive argument. Formally, one would reduce Dominating Set problem to this one - as described in link provided by @rus9384.
> 0 votes

---
Tags: satisfiability, 3-sat
---


# Question
Title: Is it possible to make a language that can build upon itself perfectly?
First of all, note that I'll have to explain my thoughts in a layman's terms.

There are so many high-level programming languages out there that compete with each other. This means we have to build the same functionality over and over again in each language.

Therefore, I wonder the following:

**Why isn't there one language that has come to dominate because it's the most efficient and the most robust, being built from the bottom up perfectly?**

Of course, 'perfectly' isn't well defined, so let me try to explain what I mean by this.

As far as I'm aware, all operations on computers boil down to working with 1's and 0's. This makes me think that there's a better way to do things.

For example, take ASCII. Why is ASCII the way it is? It's arbitrary that M is `01101101`. This arbitrariness seems like it's the root of the problem; that if M's representation was determined by how and where M's manifested themselves in our data, that the processing language would be a common language, instead of ASCII.

First of all, am I way off base on this intuition? Secondly, let me provide an idea of what I think could at least partially solve this issue.

Imagine I had a functional language that took bits, transformed them in every way possible, and returned bits. I can only think of what this might look like with the constraint that the bits remain the same length. for example, it's functionality (higher level pseudocode) would look something like this:

```
proc get_transform_list(bit_list, desired_bit_list):
    transform_list = []
    current_bit_list = bit_list
    for i in len(bit_list)^2:
        affected_indices = get_list_of_one_indices_from_number(i) // returns list of 'on' indices in binary representation of i
        wrong_indicies = get_list_of_bad_indicies(current_bit_list, desired_bit_list) // returns list of indices in current_bit_list that don't match the desired_bit_list
        if {any wrong_indices match any affected_indices}:
            transform_list.append(1)
            new_bit_list = []
            for x, bit in enumerate(current_bit_list):
                if x in affected_indices:
                    new_bit_list.append(not bit)
                else:
                    new_bit_list.append(bit)
            current_bit_list = new_bit_list
        else:
            transform_list.append(0)
    return transform_list

```

So I know that might be annoying to compile in your head so let me give you an example of what this does:

```
current_bit_list = 1110
desired_bit_list = 0111

we need to get the transform_bit_list for:
1110 -> 0111

| = flip - affected index
. = stay - non-affected index

0 = .... = 1110
1 = ...| = 1111
0 = ..|. = 1111 (corresponding indices are already accurate).
0 = ..|| = 1111 (corresponding indices are already accurate).
0 = .|.. = 1111 (corresponding indices are already accurate).
0 = .|.| = 1111 (corresponding indices are already accurate).
0 = .||. = 1111 (corresponding indices are already accurate).
0 = .||| = 1111 (corresponding indices are already accurate).
1 = |... = 0111
0 = |..| = 0111 (corresponding indices are already accurate).
0 = |.|. = 0111 (corresponding indices are already accurate).
0 = |.|| = 0111 (corresponding indices are already accurate).
0 = ||.. = 0111 (corresponding indices are already accurate).
0 = ||.| = 0111 (corresponding indices are already accurate).
0 = |||. = 0111 (corresponding indices are already accurate).
0 = |||| = 0111 (corresponding indices are already accurate).
||
|| > 0100000010000000
(flipping them all first which would be a reverse path is 0111011001111101)

the transition_bit_list is 0100000010000000

```

Using this method or something like it you can get from one bit representation to any other bit representation and you have an inherent list of representations between them (this inherent list comes from the structure of binary, but it could be something else).

I know the value and use for this kind of thing is so vague and esoteric, so let me get to the point and reiterate my question once again in a different way.

I guess what I'm trying to ask is: ascii is an example of an arbitrary protocol, but **if we made all protocols dependant upon protocols below them wouldn't we have no arbitrary protocols, and therefore wouldn't we have just one universal programming language?**

# Answer
> 8 votes
Interesting that you reflect on this issue. This is very similar to the issues that I was reflecting on when I started my Phd research back in 1976.

Back then Extensible Languages were very in vogue. The thesis then was that there must be some core of semantic and syntactic elements that could be used as the basis for all other languages. If we constructed the one *Master Language* it could then be extended to become anything we wanted. All that was needed was some understanding of the atomic units of semantics. All we had to do was start at a language and extend backwards to the atomic indivisible components that could not be further subdivided. This would be the basis of the one universal language which could both express all languages and replace them.

Work on ultimate semantics also led in the of the one machine instruction that could replace all others. The ultimate RISC machine.

As we don't yet have an answer, some are still continuing to reflect.

# Answer
> 4 votes
Although you're question states to be about programming language, it seems to me there are also some questions on encoding that still need answering. Let's start with the ASCII.

As you've said, the encoding is arbitrary. It seems you don't like this and would rather have an 'non-arbitrary' encoding. This hard to do, but more importantly, we don't want to do have 'non-arbitrary' encoding.

Standards like ASCII allow us to have abstraction. When typing this text, I don't *want* to know what the ASCII (or technically, Unicode, I guess) codes are for all characters I type.

The same holds for programming languages, high level programming languages abstract from their compiled assembly code. But even for assembly languages, the encoding to binary is, from the programmer's perspective, arbitrary. However, there may be good reasons for the processor designer to choose a certain encoding. The fact that the programmer doesn't care about the encoding means the processor designer can choose whatever encoding that is convenient.

---

However, all of the above are practical reasons why the current situation is fine. As Brian Tompsett states, a *Master Language* is however something that would be interesting in theory, even if it isn't needed in practice.

# Answer
> 2 votes
Three thoughts for you, and a bonus.

1. In any problem there are tradeoffs: some solutions are better by some measure but worse by another. For example, C usually runs faster than Python, but takes more lines of code to express the same program. So many language designs decisions are not arbitrary, but they are different in different languages due to tradeoffs.
2. Pragmatically, languages work well if they focus and limit expressivity to the most useful areas for problems that language wants to solve. We could have everyone program in machine code or assembly language, which only depend on the underlying hardware. But we abstract common tasks out and build higher-level languages to do them quickly. Which abstractions should we build? If one language tried to hold them all, it would be too impossibly large to understand. Instead, we pick some set of tasks and focus the language toward those.
3. Progress is hard and we do not know everything. Slowly we learn and improve and design new languages, but we don't always know what will work. There are many goals and factors. Your goal may be a good one but we don't know how to do it yet -- each new programming language is an experiment around a few areas of improvement.

Think about image file formats. Why do we have PNG, GIF, JPG, SVG, and so many more? Because there are tradeoffs in how we store images, and each format works well by focusing on what it is good at, and there is progress over time as we learn how to better compress and display images.

Bonus. You may be interested in LISP or different variants of it. LISP is a language with very minimal and consistent syntax: everything is a list and delimited with parentheses, so data and code are written the same way and can be manipulated in the same ways.

---
Tags: programming-languages, functional-programming, mathematical-programming
---


# Question
Title: What is the formal way to prove this is still a minimum spanning tree?
I don't get the formal way of proving the following cases:

Suppose I have a minimum spanning tree $T$ in a graph $G(V, E)$, with positive edge weights $w$, I want to prove the following:

1) If I increase the edge weight of an edge that is not in $T$, then my resulting tree is still the minimum spanning tree.

This obviously makes sense since none of the edges of $T$ have been modified, and even so, the new edges will only have weights higher than $T$. Is there a way I could put this in a formal way?

2) If I decrease the edge weight of an edge that is in $T$, then my resulting tree is still the MST.

Again, this is very intuitive since the minimum weight of my MST is already the minimum, any reduced amount will still make it minimum. Again, the problem is putting this into formal proof.

3) After adding a new edge $e$ with a unique weight $w(e)$ in $G$, the tree will still be an MST.

# Answer
For part (1), denote by $w$ the weight of a tree in the original tree, and by $w'$ its weight in the new tree. Since $T$ is an MST, we have $w(T) \leq w(T')$ for every tree $T'$. Also, $w'(T) = w(T)$ and $w'(T') \geq w(T')$ for all $T'$. Therefore $w'(T) = w(T) \leq w(T') \leq w'(T')$ for all trees $T'$, that is, $T$ is an MST with respect to $w'$ as well.

Part (2) is similar to part (1), though slightly more challenging. Suppose that we decreased the weight on an edge in $T$ by an amount $\delta$. Then $w'(T) = w(T) - \delta$, and $w'(T') \geq w(T') - \delta$ for every tree $T'$. Therefore $w'(T) = w(T) - \delta \leq w(T') - \delta \leq w'(T')$ for every tree $T'$, and so $T$ is an MST with respect to $w'$ as well.

I couldn't quite understand part (3), but I think you've seen enough examples of how these proofs go.
> 3 votes

---
Tags: algorithms, graphs, data-structures, minimum-spanning-tree
---


# Question
Title: How to actually implement universal hashing?
I sort of get what it is, but I don't understand how its actually supposed to be used in algorithms. Suppose the hash function is $h\_{ab}(x) = ((ax+b) \mod p ) \mod m$ where $a$ not equal to 0. If I wanted to insert something into the table, would I calculate the bucket to place it in using the hash function and then place it in that bucket? How would I go about retrieving that data later on?

# Answer
One example of universal hashing's application is perfect hashing. If you know all the keys beforehand, we can obtain $O(1)$ time for search, insert, delete (dynamic perfect hashing exists but is difficult to implement). More concretely we hash all of our values with an initial hash function into our table and keep track of where collisions occurred. For wherever $d\>1$ collisions occurred, you build another hash table of size $d^2$. You obtain a hash function for this ($d^2$ size) table by applying universal hashing until you get no collisions.

Universal hashing guarantees that the probability of getting collisions with any two distinct keys is $\leq \frac{1}m$ where $m$ is our table size. Following your universal hash functions $h\_{a,b}$ defined above (which is proved to be universal using number theory), we can try various $a,b$ in each $d^2$ size table until we get no collisions.

So to answer your question you just try a bunch of times (usually not too many as shown by probabilistic analysis and universal hashing) until you get a hash function that works for your problem setting and then save that hash function to use later for retrieval, insertion...

To be clear, the cost of utilizing this data structure is $O(1)$ because we only need to compute the first hash function and then the second hash function (we obtained via universal hashing).
> 1 votes

---
Tags: algorithms, hash, hash-tables, hashing
---


title: Union of fixed and floating point types

text:
# Question
Title: Union of fixed and floating point types
Say I have two real number types. They may be floating or fixed point. How can I construct a new type whose values are at least the union of the two with the minimal number of bits?

There are 3 cases to consider:

**Fixed (Qa.x) $\cup$ Fixed (Qb.y)** \- I think the best here is to use Qmax(a,b).max(x,y). I think this is optimal since I can't come up with anything smaller that will accurately represent the type.

**Float (FaEx) $\cup$ Float (FbEy)** \- I think the best here is to use Fmax(a,b)Emax(x,y). Again I can't think of a more optimal solution.

I am using Q notation for representing fixed point types. I don't know how floating point types are typically represented; I'm using an analogous representation where FaEx means a bits of mantissa and x bits of exponent.

The difficult case is:

**Fixed (Qa.x) $\cup$ Float (FbEy)** \- The best I can come up with is Qmax(a,n).max(x,m) where n is the minimal bits to represent the biggest number the float can be and m is the minimal number of bits to represent the smallest positive fraction the float can be. This seems extremely inefficient as it extends the floating point's most accurate precision to its entire range. Thus for any decent sized floating point type the resulting union type will be extremely large.

Here are some ASCII diagrams of the three cases (simplified), and why I think I'm wrong:

```
     0/4     1/4     2/4     3/4     4/4     5/4     6/4     7/4     8/4     9/4    10/4    11/4    12/4    13/4    14/4    15/4    16/4
      | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Q1.2  |.......|.......|.......|.......|.......|.......|.......|........................................................................
U     .................................................................................................................................
Q0.3  |...|...|...|...|...|...|...|....................................................................................................
=     .................................................................................................................................
Q1.3  |...|...|...|...|...|...|...|...|...|...|...|...|...|...|........................................................................

     0/4     1/4     2/4     3/4     4/4     5/4     6/4     7/4     8/4     9/4    10/4    11/4    12/4    13/4    14/4    15/4    16/4
      | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
F1E2  ........|...|...|.......|.......|...............|...............|...............................|................................
U     .................................................................................................................................
F2E1  ................|...|...|...|...|.......|.......|.......|........................................................................
=     .................................................................................................................................
F2E2  ................................|.......|.......|.......|.......|...............|...............|...............|................

     0/4     1/4     2/4     3/4     4/4     5/4     6/4     7/4     8/4     9/4    10/4    11/4    12/4    13/4    14/4    15/4    16/4
      | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . | . v . |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Q0.3  |...|...|...|...|...|...|...|....................................................................................................
U     .................................................................................................................................
F1E2  ........|...|...|.......|.......|...............|...............|...............................|................................
=     .................................................................................................................................
Q2.3  |...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|...|........
F?E?  |...|...|...|...|...|...|...|...|.......|.......|.......|.......|...............................|...............................|

```

From my math the best I could do would be Q2.3, but it is fairly obvious that there should exist some floating point type that stops having the necessary accuracy once the floating point part's accuracy is no longer needed. Of course I have to be careful if the fixed point type is more accurate than even the most accurate range of the floating point type, but I still feel like I'm missing a nice solution.

Any idea what binary type will be the smallest superset of the union between a fixed and floating point type?

NOTE: I know that this also emphasizes the benefits and drawbacks of fixed and floating types, but I feel like it should be possible to do at least a little bit better. Especially in the situation where the types have known range boundaries.

# Answer
Fixed (Qa.x) $\cup$ Float (FbEy) can be represented as Float (FcEz) where $c = a+x$ and $z = \max(\lceil \lg(x) \rceil,y)$. This is significantly more efficient than what you propose in the question.

In particular, Fixed (Qa.x) can always be coerced to Float (FcEw) where $c = a+x$ and $w = \lceil \lg(x) \rceil$. Then, once you've coerced Fixed (QaX) to Float (FcEw), you then reduce to the case of Float (FcEw) $\cup$ Float (FbEy), which you already described how to handle.
> 2 votes

# Answer
I actually think the simplest scheme would just to prepend a signal bit that says that the rest of the bits are either a floating point or fixed point value.

This always comes with a fixed cost of 1 bit. In your notation, $\max(a + x, b + y) + 1$.

I believe the only way you can do better (you can't save fractional bits without going into entropy coding in a larger context, which is a whole other story) is if one of the types fully contains the other, in which case you can simply ignore the other type.
> 2 votes

---
Tags: floating-point, numerical-algorithms, dependent-types, typing
---


# Question
Title: Randomly filling an $n$-length array with values from $0$ to $k$ that total to $0 < m < nk$ - is a linear-time algorithm possible?
Let $n, k \> 0$ and $0 \< m \< nk$. I want to fill an $n$-length array $A$ with random integer values in the range $\[0,k\]$ such that $\sum\_{i=0}^{n -1} A\[i\] = m$. Furthermore, all such arrays should be equally likely (that is, any valid array should occur with equal probability to any other). For example, if $n = 3, k = 2, m = 3$, any of these results should be equally likely:

$$\[0,1,2\]$$ $$\[0,2,1\]$$ $$\[1,1,1\]$$ $$\[2,1,0\]$$ $$\[1,2,0\]$$ $$\[1,0,2\]$$ $$\[2,0,1\]$$

The closest solution I could find was this, which is $O(n)$ assuming that we use a linear-time sort and shuffle (such as radix sort and Fisher-Yates respectively). However, this approach does not limit what the integers in each array position can be. Is there a $O(n)$ algorithm which solves the version of this problem described above?

# Answer
Once you know how to *count* the number of such arrays, you can turn that into a procedure to generate a random such array, using ranking/unranking procedures.

Let's see how to count them. Let $f(k,m,n)$ denote the number of such arrays. Note that we have

$$f(k,m,n) = \sum\_{x=0}^k f(k,m-x,n-1)$$

by enumerating all possibilities for $A\[0\]$. So, this gives a dynamic programming algorithm to count the number of such arrays.

How does this lead to a way to generate a random array? Well, in counting such arrays, we've implicitly established a bijection $\varphi$ from the set of such arrays to the set of integers $\\{0,1,2,\dots,f(k,m,n)-1\\}$. So, we just need a way to compute $\varphi^{-1}$, and then we have a way to pick a random array: we pick a random number between $0$ and $f(k,m,n)-1$, then apply $\varphi^{-1}$ to obtain the corresponding array.

Now the recurrence above establishes such a bijection. In particular, the arrays that start with $A\[0\]=0$ correspond to integers in the range $0 .. f(k,m,n-1)-1$, the arrays that start with $A\[0\]=1$ correspond to integers in the range $f(k,m,n-1)..f(k,m,n-1)+f(k,m-1,n-1)-1$, and so on. So, given a random integer $y$, we find the smallest $x\_0$ such that

$$y \< \sum\_{x=0}^{x\_0} f(k,m-x,n-1),$$

and then set $A\[0\]=x\_0$ and continue recursively to fill in the rest of the array (replacing $y$ with $y' = y - \sum\_{x=0}^{x\_0-1} f(k,m-x,n-1)$ and using $y'$ to fill in the array $A\[1..n-1\]$).
> 4 votes

---
Tags: algorithms, arrays, randomized-algorithms
---


# Question
Title: All finite languages can be decribed using a regular expression?
I have a question. All finite languages can be decribed using a regular expression?

# Answer
Suppose that a finite language consists of words $w\_1, w\_2, \dots, w\_n$.

Then what do you think the regular expression `^(w1 | w2 | ... | wn)$` matches?
> 1 votes

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


# Question
Title: Among a number of sets, how to find the one that includes the highest number of other sets?
I have a large number of sets, `A, B, C, ...` where each set includes a few integers. I would like to find the set that includes the highest number of other sets.

A brute-force solution is to compare each set with all other sets and count the number of sets that are included in this set. Finally, pick the set with the highest count. This brute-force solution has a quadratic complexity and is very slow for my large number of sets. Is there a better solution with lower complexity?

# Answer
> 1 votes
From the answer linked in D.W.'s comments, you wont be able to do this in less than quadratic time without more information. The problem you are trying to solve is more difficult than the Subset Containment problem, which is quadratic with the number of sets. We can, however, explore ways to make the average case better.

The first step is to identify if there is any pattern to the data which can be leveraged. For example, if the sets are random, then you can leverage that to find better runtimes with some partitioning tricks. If the values all happen to be less than 64, you could encode each set as a 64-bit numbers and do comparisons that way.

The most generic approach, however, is to try to minimize comparison time. The first step would be to sort the elements in each set. That makes it so you can always determine if one set is a subset of the other in linear time by scanning it.

Beyond that, you could look at bloom filters. A bloom filter is basically an array of bits, and each bit corresponds to the result of hashing the data differently. What is nice about bloom filters is that they allow you to combine values using OR logic. Use a bloom filter to hash each of the elements in a set, and OR the results together. Now it is easy to see that if you have a set $S\_1$ and $S\_2$ such that $S\_1\subseteq S\_2$ and you have their corresponding bloom filter arrays $B\_1$ and $B\_2$, then every bit in $B\_1$ must also be set in $B\_2$ (i.e. $B\_2\land B\_1=B\_1$).

Thus, you will have to do $O(n^2)$ comparisons of the bloom filter arrays (which are bit-fields, so you can process them 32 or 64 bits at a time natively). If $B\_i\land B\_j=B\_j$ for any $i, j$, then you have a *potential* subset. It's possible that you just had a bloom filter collision, so we have to test the arrays, which is linear with the size of each array.

Thus in the worst case, we don't save any time, but in the average case, we may be able to dramatically reduce the cost of comparing the sets.

There's a few more steps involved to make sure we don't saturate the bloom filters, but those can only be worked out when you know a little about the sizes of your sets, which I do not.

---
Tags: sets
---


# Question
Title: Are too many function calls bad(as in slows speed performance) for programs written using interpretor-based scripting language(JavaScript, Perl)?
The interpreters used for running scripting language (i.e., JavaScript, Perl, PHP, etc. ) programs go line-by-line. Isn't it better to Avoid too many function invocations for programs written in said scripting languages? However, Avoiding writing functions would be really a pain because you would have huge blocks of code that go continuously (basically No modularity)

@d-w Sorry, I should have mentioned that since interpreters for scripting languages go line-by-line, I thought it would be slower with more function calls. In compiler-based languages, it would be faster because the compiler's optimizing features could substitute the actual code within the function where the function is actually invoked. Basically, I thought compilers are more sophisticated, while interpreters just go line-by-line. Is the aforementioned belief correct?

# Answer
Practically speaking, function calls have a cost. They have a cost if your language is interpreted. They have a cost of your language is compiled. Some compilers can substitute the code for *some* functions (it's called inlining), but in the vast majority of cases, one does not do that.

However, the cost of a function call is low. If you have a 50 line function with a reasonable amount of work done on each line, you'll find function calls account for less than 1% of your total runtime. Their value in organization typically far exceeds their cost.

You don't want to be excessive with function calls unless you can inline them. Some styles of code depend on inlining, such as some C++ code which may have 10+ function calls nested and do perhaps 3 lines worth of work. That kind of a situation demands inlining. However, for the vast majority of the cases, don't worry about it.

You will eventually learn how to profile your code, which is a way to find hotspots where you spend a lot of your time. Always profile before you optimize. You will find that most of your function calls don't have a significant effect on runtime at all, and if you're unlucky, 3-4 functions might have too much overhead. Then you remove *those* functions, inlining the code manually, and you leave all of the other functions.

If you're interested in numbers, it is estimated that a function call in Python (an interpreted language) costs between 150ns and 350ns. In C++, the cost is on the order of 15-30 instructions, which is on par with a L1 cache miss (if that term doesn't mean anything to you, it's a good indicator of just how fast these function calls are). On a 4GHz processor, that's 4-8ns.
> 1 votes

---
Tags: interpreters
---


# Question
Title: Is every decidable language a deterministic context free language?
I'm trying to get a better understanding for the relationship between decidability and a few other things so that I can get a better grasp of the topic. Any info helps!

Is every decidable language a deterministic context free language? Are there any decidable languages that are not recognizable? Is the question "Does a given PDA accept a given input?" decidable? Under what operations are decidable languages not closed?

# Answer
You are asking several disparate questions:

* **Is every decidable language a deterministic context-free language?** No. There are even context-free languages which are not deterministic context-free. Furthermore, membership in a context-free language (deterministic or not) can be decided in polynomial time, whereas the time hierarchy theorem shows that there are languages decidable in time $O(n^{\log n})$ (say) but not in time $O(n^{\log\log n})$, and in particular not in polynomial time.
* **Are there any decidable languages that are not recognizable?** A language is decidable iff both the language and its complement are recognizable.
* **Is the question "Does a given PDA accept a given input?" decidable?** Yes, though the algorithm isn't obvious. One way is to convert the PDA to an equivalent context-free grammar in Chomsky normal form, and then use the CYK algorithm.
* **Under what operations are decidable languages not closed?** Decidable languages are not closed under taking prefixes. The language of pairs $M,n$ such that $M$ halts within $n$ steps is decidable. But the language of all prefixes ending with $,$ is the halting problem, which is not decidable. (I'm skipping a few steps here.)
> 4 votes

---
Tags: turing-machines, context-free, finite-automata, nondeterminism
---


title: Best set of orders

text:
# Question
Title: Best set of orders
I have the ambition to build an application that determents the best set of orders.

Let's say I'm an postage-stamp collector. And I have certain postage-stamps on my wish list. On the secondhand-market are many sellers selling my desired stamps. The sellers originate from around the world. Some offer the postage-stamp for an extremely low price, but since they are selling from (for example) India, the shipping cost on the one stamp is enormous. Others offer the stamp for an average price, but are close-by and have less shipping costs. The interesting thing about postage-stamps is that they are extremely lightweight. A lot of them fit together in one shipment without increasing the price of the shipment (until some point). Last but not least, not every seller is selling all possible stamps. Since they are collectors them selfs, they can only sell what they own.

Shipment costs are based on weight, but since all postage-stamps weigh the same (roughly) we price them by amount:

* 0-3 stamps cost \\$1.10 to ship.
* 3-4 stamps costs \\$2.00 to ship.
* 5+ stamps costs \\$3.00 to ship.

I want to buy the following stamps (wish list):

* SuperRareStamp
* NotSoRareStamp
* ThisIsAnOldStamp
* MyFirstPostHereStamp
* ExampleStamp

The following sellers are active on the secondhand-market:

*Freddy the big Seller*, who is selling:

* SuperRareStamp for \\$5.00
* NotSoRareStamp for \\$1.00
* ThisIsAnOldStamp for \\$3.00
* MyFirstPostHereStamp for \\$0.50
* ExampleStamp for \\$2.00

*Annick*, who is selling:

* NotSoRareStamp for \\$1.00
* MyFirstPostHereStamp for \\$0.50

*Eddy*, who is selling:

* SuperRareStamp for \\$5.50
* NotSoRareStamp for \\$1.00
* ThisIsAnOldStamp for \\$2.00
* ExampleStamp for \\$1.50

Results:

* Buying everything at Freddy the big Seller costs: \\$11.50 + \\$3.00 shipping = \\$14.50
* Buying both stamps at Annick, and fill the rest with Eddy costs: \\$1.50 + \\$1.10 Shipping (Annick) + \\$10.00 + \\$1.10 Shipping (Freddy) = \\$13.70
* Buying everything at Eddy, and the MyFirstPostHereStamp from Annick costs: \\$10.00 + \\$2.00 Shipping (Eddy) + \\$0.50 + \\$1.10 Shipping (Annick) = \\$13.60

Output: Although Eddy is selling the **SuperRareStamp** for the highest price, it's still the smarter choice to buy the stamp from him.

Sidenote: Different sellers can (in the real world) have different shipping price tiers. I'm interested in how would that be used in a formula.

Problem sizes (as requested): Items on the wishlist: never more than 100, Number of sellers 20000, Number of distinct stamps sold per seller range (1-120000).

# Answer
> 1 votes
Your problem is NP-hard (and so NP-complete), by reduction from vertex cover. Given a graph, we associate with each edge 10 stamps, and with each vertex a seller who sells all stamps for some fixed price which is the same for all sellers and stamps.

Since there are 10 stamps per edge, for every solution there is an equivalent solution (having the same cost) in which all stamps are bought from the same seller. Minimizing the price is thus the same as minimizing the number of sellers, which is the same as finding a vertex cover of minimum size for the original graph.

---

What this means is that you'll have to use a heuristic algorithm. Which heuristic to use depends on the problem size and other properties. For example, if there is only a small number of stamps or sellers, then it might be feasible to "try out all options", pruning away options which are strictly worse than others.

One simple heuristic is local search. Start with the solution which completely ignores shipping costs. Then try to find small modifications which reduce the total price. This could perhaps be feasible if implemented in a smart way.

---
Tags: algorithms, optimization
---


# Question
Title: Number of words in $\{pi,po\}^*$ of length at most 9
I have a language $L^\*$ for $L = \\{pi,po\\}$ (I think pi counts as one letter and po also as one letter otherwise a max length of 9 is not possible).

The question is how many words I can make with $L^\*$ where the maximum length is 9.

The answer is 31, but I do not know how it got calculated. How is this calculated?

# Answer
Here are all words in $L^\*$ of length at most 9: $$ \epsilon, \\ pi, po, \\ pipi, pipo, popi, popo, \\ pipipi, pipipo, pipopi, pipopo, popipi, popipo, popopi, popopo, \\ pipipipi, pipipipo, pipipopi, pipipopo, pipopipi, pipopipo, pipopopi, pipopopo, popipipi, popipipo, popipopi, popipopo, popopipi, popopipo, popopopi, popopopo. $$ In total, there are 31 words.

More generally, suppose that we have $m$ distinct words of length $\ell$. Then the total number of words of length at most $n$ is $$ \sum\_{r=0}^{\lfloor n/\ell \rfloor} m^r = \frac{m^{\lfloor n/\ell \rfloor+1}-1}{m-1}. $$ In our case, we get $\frac{2^{\lfloor 9/2 \rfloor + 1}-1}{2-1} = 2^{4+1}-1 = 31$.
> 1 votes

---
Tags: combinatorics, word-combinatorics
---


# Question
Title: Applications of the LU factorization in computer science
I have been searching for the applications of the LU factorization/decomposition in computer science. From Wikipedia, I have found some of the applications, but these don't seem to be relevant to computer science.

Applications I found are

* Solving linear equations
* Inverting a matrix
* Computing the determinant

Is there any application of LU factorization/decomposition in computer science?

# Answer
LU decomposition is a basic technique in numerical linear algebra, which is "numerical analysis for linear algebra", or (roughly speaking) the study of numerical algorithms for matrices. Numerical linear algebra has many applications, since many numerical algorithms reduce to linear algebra, which is at the heart of multivariate calculus. You can find a list of areas of application on the Wikipedia article.
> 1 votes

---
Tags: reference-request, linear-algebra
---


# Question
Title: Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \} $
So i know that $L =$ { $ {w\_1 w\_2 : |w\_1| =|w\_2| , w\_1 \neq w\_2} $ }

is a CFL, but i cannot make a PDA for it because it doesn't make any sense to me why this is CFL

i even know the grammar for it but i cannot draw the PDA because :

even if we determine the middle of the string, if we push every word of w1 to the stack, then how can we compare it to w2 when we can only POP??? how is that even possible?

i mean how can i compare two strings and determine if they are the same if i can only compare the last word of first string to the first word of the second??!

also it would help me a lot to understand if you could say which of these are CFL and which are not :

$L\_1 = \\{ w\_1 w\_2 : |w\_1| =|w\_2| , w\_1 = w\_2 \\} $

$L\_2 = \\{ w\_1 w\_2 : |w\_1| \neq |w\_2| , w\_1 \neq w\_2 \\} $

$L\_3 = \\{w\_1 w\_2 : |w\_1| \neq |w\_2| , w\_1 = w\_2 \\} $

there was a post about this but nobody answered how can we construct such a PDA? i don't want to just convert the grammar to PDA with algorithms, i want to understand how the PDA is comparing two strings?

PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it

# Answer
The three languages you ask about are not very interesting:

* $L\_1$ is famously not context-free; it's usually written as $\\{ ww \mid w \in \Sigma^\* \\}$. Note that the condition $|w\_1| = |w\_2|$ is obsolete. Standard entry-level proof techniques work.
* $L\_2 = \Sigma^+$ since every word $w$ (except $\varepsilon$) can be split into $w\_1 = \varepsilon$ and $w\_2 = w$; hence it's regular.
* $L\_3 = \emptyset$ since the two conditions are contradictory; hence it's regular.

As you see, neither gives you any insight into $L$. The languages discussed here are more helpful in this regard.

---

As for an NPDA for $L$, the answer you link already mentions that there are algorithms to get you from a grammar to an automaton; check a proof that NPDAs and CFGs are equally powerful.

That said, an idea for constructing an automaton from scratch is the same as for the grammar, even though it's a little messier to implement. Let $w$ be the whole input word, and rename $(w\_1,w\_2)$ to $(u,v)$ to avoid syntax overload. Then:

* Note that if $u \neq v$ with $|u| = |v|$, there must be $i$ so that $u\_i \neq v\_i$. And, importantly, if there is no such $i$ if $u=v$.
* Non-deterministically guess two input indices $j, l$ to compare.
* Non-deterministicaly guess the middle index $k$ of the input.
* Use states to verify that $w\_j \neq w\_l$.
* Use states to verify that $|w|$ is even.
* Use the stack to verify that $k = |w|/2$.
* Use the stack to verify that $j = l - k$.
* Reject if any of the verifications fail.

The main trick left is how to use the stack for the two checks at once; I'll leave that as an exercise. Proving that the resulting automaton does indeed accept the language is instructive about the nature of non-determinism.
> 3 votes

---
Tags: formal-languages, context-free, pushdown-automata
---


title: Find All possible Pairs in given Array

text:
# Question
Title: Find All possible Pairs in given Array
It is required to count number of unordered pairs in an *array of size n* ,

**l\[i\]+l\[j\] = 2\*l\[k\]** , where *1\<=i\< j\<=n and 1\<=k\<= n*

My Approach:

```
l = [1,3,5,4,2,5]
l.sort()
l2 = []
for i in l:
    l2.append(2*i)
count = 0
for combo in combinations(l, 2):
    if sum(combo) in l2:
        count+=1

print(count) # count comes out to be 7

```

Please help in reducing Time Complexity O(n^2) to less if possible. Space Complexity is not a problem.

# Answer
> 2 votes
Your problem (more accurately, the problem of deciding whether there is *any* solution) is 3SUM-complete. This can be shown in essentially the same way that the two main variants 3SUM and 3SUM' are shown to be equivalent (check the original paper of Gajentaan and Overmars, for example). Therefore it has an $O(n^2)$ algorithm, but it is conjectured that there is no $O(n^{2-\delta})$ algorithm for any $\delta \> 0$.

---
Tags: arrays
---


# Question
Title: Efficient alternatives to inclusion-exclusion
Say you've got a number of sets $S\_1,...,S\_n$ given and are supposed to calculate $\\,\\,\displaystyle\big|\bigcup\_{i=1}^n S\_i\big|$ .

The basic approach probably would be to use the classic inclusion-exclusion principle $\displaystyle\sum\_{\emptyset \not= I \subseteq \\{1, \dotsc, n\\}} \left(-1\right)^{|I|+1}|A\_I|$ , where $A\_I = \\,\\,\displaystyle\bigcap\_{i\in I}^n S\_i$ .

However, inclusion-exclusion feels like it's terribly inefficient - after all, we need to sum over $\displaystyle\sum\_{i=1}^n\binom{n}{i} = 2^n-1$ possible sets.

While I guess that there's no algorithm with polynomial complexity for this problem, I'm curious about alternatives that are more efficient (i.e. have polynomial run time in most cases), or are simply largely different.

I'd be thankful if you could name alternative algorithms or optimizations to inclusion-exclusion.

---

The particular problem I'm trying to write an algorithm for is unsatisfiability in Propositional logic for formulas in CNF. I.e. we have a finite set of atomic formulas $\\{p\_1,...,p\_m\\}$. Over these atomic formulas, the clauses of the CNF of the formula are built after these rules:
For ever atomic formula $p$, there may either appear $p$, $\lnot p$ or none of the two in the clause.

As the whole problem was either $NP$ or $co-NP$, there most likely isn't a polynomial algorithm, but I am struggling to just make it anyhow just a little bit more efficient than inclusion-exclusion (besides using ideas that have little to do with the algorithm itself like pure-literals or pure-clauses).

---

Yes, each set itself is discrete with each element in the set being specified. One example would be $\\{ \\{\bar A, B \\},\\{B,C \\},\\{ A,B \\} \\}$. However, to fit the example, the initially given inclusion-exclusion algorithm would need to be modified.

This is the case as every clause in the CNF is a representative for a bigger clause, e.g. in the above example $\\{\bar A, B \\}$ stands for
$ \\{\bar A, B ,C \\} \\{\bar A, B ,\bar C \\} $
and $\\{B,C \\}$ stands for
$ \\{B,C, A \\} \\{B,C ,\bar A \\} $

You get the actual set the representative represents by the following algorithm:

Be $M$ a set of the clause, and $S$ our output set. Add $M$ to $S$. Now repeat as long as possible:

> Find an atomic formula $A$ so that $A\notin K$ and $\bar A \notin K$ for some $K\in S$.
> Remove $K$ from $S$.
> Add $K\cup \\{A\\}$ and $K\cup \\{\bar A\\}$ to $S$.

Finally, delete all sets in $S$ where $A,\bar A \in S$ for some $A$ and return $S$.

(An atomic formula in this case is simply any letter somewhere in $M$ without the bar (i.e. $A$ for $\bar A$))

This version of the algorithm however is at this point pretty dumb. You can improve it by not explicitly generating the actual sets and calculate it with the representants and applying some arithmetic instead.

It goes like this: Let $A\_1,...,A\_n$ be our atomic formulas that appear in a set of clauses $\mathcal{K}$. For every $K\in\mathcal{K}$ you can calculate how many sets $K$ actually represents by counting the elements of $K$, let's name it $c$, and calculate $2^{n-c}$.
So, we calculate the sum all the way above, i.e. $$\displaystyle\sum\_{\emptyset \not= I \subseteq \\{1, \dotsc, n\\}} \left(-1\right)^{|I|+1}|A\_I|\text{ , where }A\_I = \\,\\,\displaystyle\bigcap\_{i\in I}^n S\_i$$ just that we calculate $|A\_I|$ not by $\big|\\,\\,\displaystyle\bigcap\_{i\in I}^n S\_i\big|$, but by calculating how many sets $\\,\\,\displaystyle\bigcup\_{i\in I}^n S\_i$ represents (with special case $|A\_I|=0$, if $A\_I$ contains $A$ and $\bar A$ for some atomic formula).

# Answer
Unfortunately, if the only reasonable method to solve a problem is via inclusion/exclusion, it's going to take $\Omega(2^n)$ time. The reason for this is simple, there are $2^{n}-1$ sets we must inspect (if we don't, then we wouldn't have to do inclusion/exclusion!) So, there are no significant general improvements on inclusion/exclusion.

Asking for an algorithm to "have polynomial run time in most cases" is a rather vague empirical claim that is unfortunately hard to answer precisely and could have little value. A way to make this precise is a probabilistic algorithm. I'm not aware of any probabilistic variants of inclusion/exclusion, but I think that using another method than inclusion/exclusion would be better to create a probabilistic variant.

However, is inclusion/exclusion worthless? No. Often, inclusion/exclusion is used to obtain an algorithm that takes exponential time, but has only polynomial space usage. (sometimes, exponential space is a bigger problem in practice than exponential time!) For instance, the Hamiltonian cycle problem can be solved in $O^\*(2^n)$ time but only polynomial space by inclusion/exclusion.

---

It could be the case that your specific problem has a more efficient solution, but that solution method then is likely very different from inclusion/exclusion.
> 3 votes

---
Tags: combinatorics
---


# Question
Title: Given an array $A$, find all quadruples $(i,j,k,\ell)$ such that $i<j<k<\ell$ and $A[i]=A[k]$ and $A[j]=A[\ell]$?
I have an array $A$ of $n$ integers. I need to find all quadruples $(i,j,k,\ell)$ such that $i\<j\<k\<\ell$ and $A\[i\]=A\[k\]$ and $A\[j\]=A\[\ell\]$. What is the best way to do this?

My attempt is an exhaustive search algorithm that works as follows:

* Generate all quadruples $Q=\\{(i,j,k,\ell): i\<j\<k\<\ell\\}$.
* For each quadruple $(i,j,k,\ell)\in Q$, verify $A\[i\]=A\[k\]$ and $A\[j\]=A\[\ell\]$.

This algorithm requires $$O\left(\binom{n}{4}\right)=O(n^4),$$ steps in the worst case. Can we do better? (Is this problem known somewhere?)

EDIT: I was using **greedy** instead of **exhaustive search** as Yuval mentioned.

# Answer
> 3 votes
Consider the absolute worst case, where every element is equal to every other element. This means that the algorithm has to output $n(n-1)(n-2)(n-3) \in O(n^4)$ quadruples. So in the worst case we can't do better. But often for problems like this it's useful to also consider cases where we don't have to output as much.

So let's do better. If you sort the data in $O(n \log n)$ (making sure to store the original indices) you can then in an $O(n)$ step find all equivalence classes. Then you can output all quadruples by first iterating over all possible pairs of equivalence classes and then iterate over all possible combinations of elements from those two equivalence classes.

Those last two steps are in theory $O(n^4)$, but are a lot smaller when the equivalence classes get smaller.

# Answer
> 2 votes
As orlp mentions in their answer, you can't do better than $O(n^4)$ in the worst case, since there could be $\binom{n}{4}$ many solutions (i.e., quadruples). We can improve on that in two regards:

1. Find a faster algorithm for determining whether there is any solution.
2. Find an algorithm whose running time depends gracefully on the number of solutions.

Here is an $O(n\log n)$ algorithm for finding out whether there is any solution at all. It also gives a good starting point for designing an "output-sensitive" algorithm (one whose running time depends on the number of solutions in a nice way).

The algorithm maintains two data structures:

* The set $S$ of elements seen so far, initially empty.
* A tree with labels on the vertices. One vertex, called the *current vertex*, is unlabeled. Initially the tree consists of an unlabeled root (which is the current vertex).

At each step we read one integer $x$. There are three possibilities:

1. If $x \notin S$, we label the current vertex by $x$, add a new unlabeled child to this vertex (this is the new current vertex), and add $x$ to $S$.
2. If $x \in S$, we delete the current vertex and start going up the tree. If we reach a vertex labeled $x$, we add to it a new unlabeled child, which is the new current vertex.
3. If we don't find $x$, we halt, declaring "there is a solution".

After reading all integers, we halt, declaring "there is no solution".

**Correctness.** Let us suppose first that the algorithm announces that there is a solution. This happens after reading some element $x$ which is already in $S$, and so appears somewhere in the tree, say at node $v$. Let $p$ be the most common ancestor of $v$ and the current node, and suppose that $p$ is labeled $y$. The reader can check that the input array contains occurrences of $y,x,y,x$ (in that order).

Conversely, suppose that there is some solution, and consider the shortest prefix of the array in which there is a solution. Suppose that this prefix ends with the integer $x$, and that one of the solutions in this prefix is $y,x,y,x$ (there could be several, for example in the case $y,z,x,z,y,x$). Upon reading the final $x$, the set $S$ already contains $x$. However, $x$ cannot be an ancestor of the current node, due to the intervening $y$. Therefore a solution would be announced.

**Running time.** If we implement the set using a balanced binary tree, checking whether an integer is in $S$ takes time $O(\log n)$. If the read element is in $S$, then we go up the tree looking for it. Suppose first that we always find $x$ at an ancestor of the current node. Then we are traversing each edge of the final tree at most twice, and so overall these lookups together take $O(n)$. It can only happen once that $x$ is not found, and this lookup will also take $O(n)$.

All other actions take $O(1)$ per read value, so the total running time is $O(n\log n)$.

---
Tags: algorithms
---


# Question
Title: Fastest way to search a word in a word list?
I have a word list like "English Open Word List" used to create word games. The list is in txt file with space between words, like; aa aah aahed .........and so on. I want to search it while typing the letters in the word, like google suggestions in the search bar. What is the fastest algorithm to do it? In any language?

# Answer
> 5 votes
Trie might help, it stores your "word list" like this:

```
              a
             / \
           [a]   a
           /      \
         [a]       h
                    \
                     e
                      \
                      [d]

```

And you can query by some operation like `trie['a']['a']['h']['e']`, which is just array index operation. It takes large memory but it's very efficient. The complexity of the query operation is $ O(n) $, n is the length of the queried string.

---
Tags: algorithms, search-algorithms, databases, lists
---


# Question
Title: Is it possible to create a CFG with succesive palindromes?
In one of my homework I am requested to find a Context-free-grammar (CFG) and a push down automaton (PDA) for the following language:

$L = \\{x\_1\\#x\_2\\#...\\#x\_k | k \geq 2, \text{ each } x\_i \in \\{a, b\\}^\*, \text{ and for some } i \text{ and } j, x\_i=x\_j^\mathcal{R}\\}$

My problem is that the statement

$\text{ ... and for some } i \text{ and } j, x\_i=x\_j^\mathcal{R}\\}$,

i.e. any two pairs in the sequence must be each others reverses, forces us to make all $x\_i$'s palindromes, as that is the only way any two are guaranteed reverses of each other.

If that interpretation is correct, I think the problem is impossible to solve with a Context free grammar, or not? This leads me to believe I interpreted the statement wrong and it means something else, but I can't figure out what.

# Answer
> 1 votes
A reference to $j$ is missing. My guess is that it should read $x\_i=x\_j^{\mathcal R}$. This means that some pair $x\_i$, $x\_j$ should be each others reverse, or one string should be a palindrome. This can be done with a CFG.

(after correction) It does not say that for each $i$ there should be a $j$, it just states that *some* $i,j$ exist. One pair will do. If the word "any" would have been used then this would probably change the meaning, although "any" sometimes is ambiguous.

# Answer
> 1 votes
I'm trying to answer my own question as I found a grammar that should work based on the help given by the top answer.

$S \to MCN$

$M \to \epsilon \ | \ A\\#$

$N \to \epsilon \ | \ \\#A$

$A \to \epsilon \ | \ aA \ | \ bA \ | \ A\\#A$

$C \to aOa \ | \ bOb \ | \ \\# \ | \ aCa \ | \ bCb \ | \ \\#O\\#$

$O \to \\# \ | \ \\#A\\#$

I think this grammar should work. It is based on my (hopefully) correct assumption that $... \text{ each } x\_i \in \\{a,b\\}^\*$ means that $x$ can also be $\epsilon$, as $\epsilon \in \\{a,b\\}^\*$. Thus the language created with $\epsilon\\#\epsilon$, which is in fact just $\\#$, should be accepted. If that is wrong, please feel free to correct me.

---
Tags: formal-languages, context-free
---


title: Extend reachability to total ordering

text:
# Question
Title: Extend reachability to total ordering
Given a finite DAG $G = (V, E)$ with $|E| \in \mathcal{O}(|V|)$, I want to compute a total ordering $\<$ over $V$ that is compatible to reachability: If there is a transition $(u, v) \in E$, then $u \< v$.

The only way I could think of was to use Floyd-Warshall to compute a reachability matrix and then somehow extend that to be total. This would require cubic time, which is too slow for my needs. I require a quadratic time algorithm at most. In a publication I read that this is actually possible in linear time but no procedure or further explanation was provided.

# Answer
> 2 votes
You can compute a topological ordering of the vertices in linear time.

---
Tags: algorithms, graphs, dag, ordering
---


title: What's a bank memory?

text:
# Question
Title: What's a bank memory?
I've search on Google but still don't understand. I've read about it into arm book, but they don't define it.

Could you explain me what is it, where is it used, what's the point to have it and, if you can, its used into arm chips.

Thanks.

# Answer
> 1 votes
Memory banks were an abstraction paired with a hardware implementation to extend the amount of memory normally available to a particular architecture.

For example, the PDP-8 had a "page" size of 128 12-bit words, and most instructions could only address memory on the same page as itself. Other instructions could access the full memory complement of 2^12 (4K!) 12-bit words. To go beyond 4K, special techniques could address memory outside the normal 4K. When implemented, the original 4K became (memory) bank 0 and other memory banks numbers 1, 2 etc might exist.

The details varied, as computers worked their way up to today's standard of 64 bit address space.

---
Tags: virtual-memory
---


# Question
Title: How can a 16-bit or more processor store a byte in a byte-addressed memory
I am confused as to how a 16-bit (or 32, 64) processor can store multiple adjacent bytes at once without supplying multiple addresses

For example say we have (16-bit processor) 0xABCD starting at address 0x0000. For loading, the processor would just supply 0x0000 on the address bus and the way the bytes are laid out physically would produce 0xABCD on the data bus, then the processor would just do some neat bit-shifting to get the correct byte of the word

But for storing a byte, lets say 0xCD at address 0x01, what would the processor do about the other byte? (i.e. what would it do about location 0x00)

Thanks

EDIT: I am asking about big-endian architecures

# Answer
For a one-byte read to address 0x01, the CPU can read a 16-bit value and discard half of it.

For a one-byte write to address 0x01, if the memory architecture doesn't support that directly, the CPU needs to read the 16-bit value at 0x00, then replace the second byte with 0xCD, then write a 16-bit value to 0x00.
> 1 votes

# Answer
These are hardware details that vary, historically a lot, maybe not so much these days. Unless you're designing hardware, or are tweaking software performance at a very low level, it hardly matters.

When the processor presents an address and a fetch/store request, the memory subsystem is a black box that does what's needed. A 1-byte store might or might not involve fetching a larger number of bytes, slotting the stored bits into the required position, and then storing all the modified data back to the original place. Fetching or storing multiple bytes to an unaligned address might require more memory operations than to an aligned address.

Some architectures even forbade the kind of operations you're thinking of, where it wouldn't be "easy" for the hardware to do what is required.
> 1 votes

---
Tags: cpu, memory-access
---


title: Float multiplication

text:
# Question
Title: Float multiplication
While doing the multiplication **`1.4*0.8`** in a python program, I got the result as **`1.1199999999999999`**.

Why didn't I get **`1.12`** exactly?

In C programming language, the same expression gives **`1.1200`**.

# Answer
$1.4$ and $0.8$ cannot be represented exactly in a IEEE floating point number.

This means that the actual number stored and operated on is really $1.4+\epsilon$ and $0.8+\epsilon$ where $\epsilon$ is the rounding error and when you multiply those two ends up as $1.12 + 2.2\epsilon+\epsilon^2$.

This rounding error propagation can bite you in the \*** at the weirdest times (like making a platform drift slowly upwards enough to allow niche players to shave off a specific button press) and make the results at the end completely wrong if enough operations align to make the error significant enough to matter. One of the major operations to watch out for in this regard is subtraction of nearly equal numbers so the mathematical result becomes close to the error on the inputs.
> 1 votes

# Answer
The other answers explain why you're not getting 1.12 exactly (in brief, this is because floating point numbers can only exactly represent rationals whose denominator is a power of 2).

The result of the multiplication is probably the same in both languages. What is different is how these results are printed. The C routine seems to round the result more aggressively.
> 1 votes

# Answer
This is a known issue that people have struggled with for a while, (I used to struggle with it too). Here's some python documentation on the subject 14. Floating Point Arithmetic

"It’s easy to forget that the stored value is an approximation to the original decimal fraction, because of the way that floats are displayed at the interpreter prompt. Python only prints a decimal approximation to the true decimal value of the binary approximation stored by the machine. If Python were to print the true decimal value of the binary approximation stored for 0.1, it would have to display"

But to actually solve this issue, you can use the round function to prevent this from happening.

```
round(1.1199999999999999, 2)

```

This should give you the same number rounded to 2 decimal places. While this isn't very good for certain situations using floating point variables, it at least gets the job done. I recommend rounding to 5 decimal places.
> 0 votes

# Answer
The broader answer is to consider the suitability of floating point numbers for your purpose. As the other answers have said, floating point calculations are inherently inexact. If you need an exact answer (for example, if you're writing a financial balance sheet) you shouldn't use them. If you don't need an exact answer, you shouldn't be complaining about the difference between 1.2 and 1.1999999...
> 0 votes

---
Tags: floating-point, number-formats, multiplication
---


# Question
Title: Would using mouse position in the below scenario generate true random numbers?
I'm having trouble wrapping my head around random number generation so I figure it would be better to ask now, rather than screw up later.

Let's say I want to write a function that generates a random lucky number from 0-9 when the user clicks on a button.

I'm thinking of using the last digit of the multiple of the x and y coordinates of the click position as the output.

Assuming that the user have no intention of gaming the output, would this be true randomness because there's no way for a 3rd party to predict where on the button the user will click next?

# Answer
Usually, mouse click position is highly correlated. Just as an example, take a look to a typical mouse interaction with a browser:

So, the use of raw mouse click positions without pre-whitening is discouraged.
> 4 votes

# Answer
Using the system clock is better than mouse position. Use the exact time (as high precision as is available) as the seed for a random number generator, not the system time itself. Something like

```
int lucky = new Random(System.currentTime()).nextInt(10);

```
> 0 votes

---
Tags: randomness, random-number-generator
---


# Question
Title: Is there any language that can be Turing-reduced to all languages?
I suppose not, but I do not have a clear way to prove it. Right now, I am trying to find a counter example that there exists a language that cannot be reduced from the language, but I am not sure if there is the right direction.

# Answer
Every Turing-decidable language is Turing-reducable to every language.

According to the definition in Wikipedia,

> Given two sets $A,B \subseteq \mathbb{N}$ of natural numbers, we say $A$ is Turing reducible to $B$ and write
>
> $$A \leq\_T B$$
>
> if there is an oracle machine that computes the characteristic function of $A$ when run with oracle $B$.

Now if $A$ is decidable, the oracle machine can decide $A$ even without the use of the oracle, so $A$ is Turing-reducible to every language.
> 4 votes

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


# Question
Title: Why can we assume an algorithm can be represented as a bit string?
I am starting read a book about Computational Complexity and Turing Machines. Here is quote:

> An algorithm (i.e., a machine) can be represented as a bit string once we decide on some canonical encoding.

This assertion is provided as a simple fact, but I can't understand it.

For example, if I have an algorithm which takes $x$ as input and computes $(x+1)^2$ or:

```
int function (int x){
   x = x + 1;
   return x**2;
}

```

How that can this be represented as string using alphabet $\\{0, 1\\}^\*$?

# Answer
> 45 votes
The most naive and simple answer to your question is that the code provided (and compiled machine code) are in-fact represented as syntactic strings of {0,1}\*. Additionally, since you are talking about turing machines, the programs they run are a linear list of operations/instructions, there is no reason these cannot be represented as bits/bytes.

# Answer
> 52 votes
You already have a representation of that function as text. Convert each character to a one-byte value using the ASCII encoding. Then the result is a sequence of bytes, i.e., a sequence of bits, i.e., a string over the alphabet $\\{0,1\\}^\*$. That's one example encoding.

# Answer
> 34 votes
I can't resist...

```
⡂⡀⣀⢀⣄⡀⣰⡉⡀⠀⡀⡀⣀⠀⢀⣀⢀⣄⡀⡂⢀⣀⡀⢀⢀⡀⠀⡰⣀⠀⣀⠀⡂⡀⣀⢀⣄⡰⡀⢠⠂
⡇⡏⠀⡇⡇⠀⢸⠀⡇⢀⡇⡏⠀⡇⣏⠀⠀⡇⠀⡇⣏⠀⣹⢸⠁⢸⠀⡇⢈⠷⡁⠀⡇⡏⠀⡇⡇⠀⡇⢼
⠁⠁⠀⠁⠈⠁⠈⠀⠈⠁⠁⠁⠀⠁⠈⠉⠀⠈⠁⠁⠈⠉⠁⠈⠀⠈⠀⠱⠉⠀⠉⠀⠁⠁⠀⠁⠈⠱⠁⠘⠄

⠀⠀⠀⢤⡀⡤⠀⣀⣀⣀⠀⢤⡀⡤⠀⠀⢰⠀⠀⢹⠠
⠀⠀⠀⣠⠛⣄⠀⠒⠒⠒⠀⣠⠛⣄⠀⠉⢹⠉⠁⢸⢀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘
⠀⠀⠀⣄⢄⠤⢄⢴⠤⢠⠀⢠⢠⡠⢠⡠⢄⠀⢤⡀⡤⢺⡖⠐⣷⠂⠊⢉⡆
⠀⠀⠀⡇⠸⣍⣉⠸⣀⠸⣀⢼⢸⠀⢸⠀⢸⠀⣠⠛⣄⠀⠀⠀⠀⠀⣴⣋⡀

⢱
⢸⠁
⠊

```

(The dots above represent ones, the blanks zeroes).

# Answer
> 13 votes
Your computer stores everything as sequences of `0` and `1`, including the question you typed to ask how it does it. For instance, each letter and symbol is represented by 8-bits (I am talking about how things used to be, nowadays it's 16-bits, and more complicated). You can see them here. Well, they are not showing the bits, but rather the hexadecimal and octal codes. Do you know how to convert a number to its digital representation?

# Answer
> 8 votes
The fundamental hypothesis behind this concept is the Church-Turing thesis. It may be hard to see that any algorithm can be represented as a string of bits, because the term "algorithm" may be thought of in very informal terms. In the Church-Turing thesis, they use a very rigorously defined concept of what an algorithm is (and even then there have been a few questions about words). However, their terminology has gotten so much sway that it is sometimes argued that these definitions for words like "algorithm" are so effective that we simply accept them as *the* definition.

Church-Turing states that every algorithm can be implemented as a computation on a Turing Machine. Given that the description of a Turing Machine is a finite set of values, it is trivial to see how to map this description into a sequence of numbers, and then into a sequence of 0's and 1s.

As the other answers have mentioned, it's trivial to represent your example algorithm by using ASCII encoding or other encodings.

I think the reason why your book gives this statement as a *fact* stems from the fact that many simply use the Church-Turing thesis as the basis for their definition of an algorithm. If you use such a definition, it is as obvious of a fact as is "5 is a number" because you basically defined it as such.

# Answer
> 4 votes
This statement is based on the existence of universal TMs. These are basically programmable TMs that can simulate any other TM with at most poly overhead. Therefore, your program is simply part of the input encoded as zeros and ones.

# Answer
> 4 votes
Well, let's talk about algorithms that cannot be represented as a finite bit-string for any kind of encoding.

Let me type out such an algorithm for you... Ah, but if I do that, I can represent that algorithm with the encoding of my typed text.

How about representing my algorithm using some 'analog means', say by the position of a few coins on my desk. Although the position of those coins can be modeled by some real numbers (which could in *some* encodings be impossible to finitely represent), this entire description can again be considered an representation of my algorithm and can be encoded to a bit-string again!

I hope that these examples make it clear that if some algorithm cannot be represented by a finite bit-string we have no means of describing this algorithm at all!

So, why would we consider the existence of something we cannot speak of? Perhaps interesting for philosophy, but not for science. Hence, we define the notion of *algorithm* such that it can be represented by a bit-string, as then we at least know that we are able to talk about all algorithms.

---

Although the above answer the question asked, I think the confusion about the example given is mostly due to the fact that a representation only needs to uniquely represent some algorithm. The manner of representation doesn't need to involve the *actual computations* invoked by the algorithm! This is very useful, as it means we can also represent *uncomputable* algorithms!

# Answer
> 2 votes
Another way to see this is through information theory. All encodings of meaningful/useful information/questions can be made into binary 'sequences'.

Much of the field goes to the question, "what is the way to ask the least average number of questions to communicate a meaningful piece of information?" In practice, this is the same as "what is the optimal approach to asking the least number of yes/no questions to understand what was communicated or said?"

---
Tags: algorithms, turing-machines, computability, computation-models
---


# Question
Title: Which of the following languages is accepted by this Pushdown Automaton?
This is a question from a past paper. I am struggling to get my head around the concept of a PDA. I understand that it is a Finite Automaton with a stack but am stuck as far as answering questions like this one. Thanks.

# Answer
I think the answer is a, $\\{a^n b^{2n} | n \> 0\\}$.

First, the machine pushes $a$'s onto the stack until the first $b$. Then, for every two $b$'s in the string, it pops off one $a$. Then, if the machine is at the end of the string and the stack is empty, it accepts.

If the stack of $a$'s runs out while the machine is still popping pairs of $b$'s or there are $a$'s left in the stack when the last $b$ is popped, then the machine rejects.

> I am struggling to get my head around the concept of a PDA.

Notation varies, but in the diagram you provided, I think `nop` means "read the thing on top of the stack and leave it there" and `pop` means "read and remove the thing on top of the stack".

For more info, you could read the chapter on PDA's in Michael Sipser's book *Introduction to the Theory of Computation*.
> 1 votes

# Answer
the ans is C push all a's and pop each a for each b, if the stack is empty when all b's are scanned. Then this CFG.
> 0 votes

---
Tags: pushdown-automata
---


# Question
Title: n mod 4 asymptotic analysis best case and worst case
if 0==(n mod 4) then do somthing ϴ(n^2)

else if 1==(n mod 4) then do somthing ϴ(n^3)

else if 2==(n mod 4) then do somthing ϴ(n^4)

else if 3==(n mod 4) then do somthing ϴ(n^5)

what is best case and worst case for this algorithm?

# Answer
*Best case* and *worst case* are about the complexity for a *fixed* input length. As an example, suppose we are sorting an array of length $n$. There are many possible arrays of length $n$. On some of them the algorithm will be faster, on some it will be slower.

In your case, in contrast, the running time doesn't depend on the input, but only on its length. Therefore the best case and the worst case are both $$ \begin{cases} \Theta(n^2) & \text{if } n \equiv 0 \pmod{4}, \\ \Theta(n^3) & \text{if } n \equiv 1 \pmod{4}, \\ \Theta(n^4) & \text{if } n \equiv 2 \pmod{4}, \\ \Theta(n^5) & \text{if } n \equiv 3 \pmod{4}. \end{cases} $$
> 1 votes

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


# Question
Title: How is the difficulty of any problem (not just decition problems) classified?
I have been studying Integer Programming and I find out that some optimization problems are referred to as P or NP-Hard, however, as I started to read about it, it turns out that those classes are just for decision problem. Thus:

1. What does it mean that an optimization problem ($\max\\{f(c)\mid x\in X\\}$) is NP or NP-Hard if they are not (necessarily) decision problems?
2. If an optimization problem ($\max\\{f(c)\mid x\in X\\}$) is not a decision problem, then, how is its difficulty classified?

# Answer
> 2 votes
When we say that the optimization problem $\max \\{ f(x) : x \in X \\}$ is NP-hard, what we really mean is that the following decision problem is NP-hard:

> Is there an $x \in X$ such that $f(x) \geq y$?

This turns optimization into a decision problem that can be analyzed using the complexity classes you know of.

There are also complexity classes specifically for functions or for optimization problems. Some examples are:

* FP, the class of functions computable in polynomial time;
* APX, the class of problems that can be approximated in polynomial time, and the associated classes APX-hard and MaxSNP;
* PPAD and its friends, classes of problems of the general form "given $x$, find $y$ such that $P(x,y)$", where for each $x$ we are guaranteed that such a $y$ exists.

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


# Question
Title: Algorithm for this problem on generating all permutations
I am trying to come up with an efficient algorithm to solve the following problem but not able to design anything nice. I am encountering this problem for a project I am pursuing. Following is an abstracted version of the problem so that I don't confuse anyone with the specifics.

The problem is like this:

I have a list of groups. each group might have an arbitrary number of elements with some weight in it. A valid vector comprises of exactly one member from each group and has members from each group in the list. The weight of a vector is the product of weights of the members in the vector. I want to find the sum of weights of all valid vectors.

for example:

Group 1: Member 1, Member 2

Group 2: Member 3

Valid Vector 1: Member 1, Member 3

Valid Vector 2: Member 2, Member 3

We need to find: (Member 1 * Member 3) + (Member 2 * Member 3)

The groups don't intersect. Which means a member can belong to only one group. What I am doing currently is a brute force like solution, where I start with creating a global list and populating it with the members of group 1. I then go to the next group (group 2) and extend the global list by multiplying each member of group 2 with each member in the global list. Thus completely replacing global list with all pairs of members from group 1 and group 2. In this manner, I keep extending the global list till I have processed all groups.

# Answer
Suppose that there are $n$ groups, that group $i$ has the $m\_i$ elements $x\_{ij}$. It is a nice exercise to show that the sum of weights of all valid vectors is $$ \prod\_{i=1}^n \sum\_{j=1}^{m\_i} x\_{ij}. $$ (In you example, you can factor your formula as (Member 1 + Member 2) * Member 3.)
> 1 votes

---
Tags: algorithms, permutations, subset-sum
---


# Question
Title: How would one use "BUT" logic in a ternary logic computer in a practical way?
Using three valued logic one can define a multitude of ternary operations. When dealing with `5:3:1`\[1\] operations, its very easy to see how `OR` and `AND` work, but I'm confused as to how ternary `BUT` is supposed to be useful. As mentioned here in TriINTERCAL's\[4\] docs the truth table for ternary `BUT` is as follows:

```
BUT(True, True) = True
BUT(False, True) = False
BUT(False, False) = False
BUT(True, False) = False
BUT(Unknown, x) = Unknown   for all x

```

This is a 5:3:1 operation, as out of the 9 possible cases, 1 of those leads to True, 3 lead to False, and 5 to Unknown.

How could such an operation be used in practice (either on single trits\[2\] or multiple trytes\[3\])?

The individual who created the Tunguska ternary computer emulator claims that *other people* found `BUT` a useful operation coming from TriINTERCAL, even though the author of TriINTERCAL mentions that they don't seem to be useful.

---

\[1\] `5:3:1` operations are what you call binary ternary operations where the 9 possible values of the operations are split up like so among True, False, and Unknown, but not necisarily in that order.

\[2\] A trit is a ternary bit. A trit holds the value 0,1,2, or False, Unknown, True.

\[3\] A tryte is a ternary byte. Though the value can vary, it is typically 6 trits (3^6 possible values = 729, so more than a byte).

\[4\] TriINTERCAL is a programming language based off of INTERCAL that utilizes ternary logic instead of binary.

# Answer
> 2 votes
In the article "The A-Z of Programming Languages: INTERCAL" Naomi Hamilton (Techworld Australia) interviews Don Woods, one of the authors of INTERCAL. More about INTERCAL.

On page 3 of the article the last question is:

> **Naomi:** "Is there anything else you'd like to add?"
>
> **Don:** "... Much of the fun of INTERCAL comes from figuring out how it can be used to do something that would be trivial in other languages. More fun is had by extending the language with weird new features and then figuring out what can be done by creative use of those features."

Apparently the authors of TriINTERCAL took the spirit of the language to heart, yet avoided adding an entirely useless operation.

TriINTERCAL differs from INTERCAL only in the width of the data types (one-spot data types are 10 trits wide and two-spot data types are 20 trits wide), and in the operators available in expressions. "AND" and "OR" are generalizations of the INTERCAL binary versions, "BUT" is new, and "Sharkfin" and "What" are two different interpretations of "XOR" (both of which are available in TriINTERCAL). "Mingle" mingles trits, rather than bits, whereas "Select" ANDs the two original numbers, then sorts all the bits in the first number corresponding to 2's in the second number to the least significant end, 0's in the second number to the most significant end, and 1's in between them.

"AND", "OR", "Mingle", and "Select" operate just like their binary counterparts if no trits with the value 2 are present.

$$ \begin{array}{cc|cc} \text{AND}\quad\qquad & \\& & 0 & 1 & 2 \\ \hline & 0 & 0 & 0 & 0 \\ & 1 & 0 & 1 & 2 \\ & 2 & 0 & 2 & 2 \\ \end{array} $$

$$ \begin{array}{cc|cc} \text{OR}\quad\qquad\\;\\;\\; & \lor & 0 & 1 & 2 \\ \hline & 0 & 0 & 1 & 2 \\ & 1 & 1 & 1 & 2 \\ & 2 & 2 & 2 & 2 \\ \end{array} $$

$$ \begin{array}{cc|cc} \text{BUT} \quad\qquad & @ & 0 & 1 & 2 \\ \hline & 0 & 0 & 1 & 0 \\ & 1 & 1 & 1 & 1 \\ & 2 & 0 & 1 & 2 \\ \end{array} $$

$$ \begin{array}{cc|cc} \text{SHARKFIN} & \land & 0 & 1 & 2 \\ \hline & 0 & 0 & 1 & 2 \\ & 1 & 1 & 2 & 0 \\ & 2 & 2 & 0 & 1 \\ \end{array} $$

$$ \begin{array}{cc|cc} \text{WHAT} \\, \qquad & ? & 0 & 1 & 2 \\ \hline & 0 & 0 & 1 & 2 \\ & 1 & 2 & 0 & 1 \\ & 2 & 1 & 2 & 0 \\ \end{array} $$

> **Question:** "How would one use “BUT” logic in a ternary logic computer in a practical way?"

Taking some liberty with the English language and the meaning of the TRiINTERCAL operators I'll explain it thusly:

The "**AND**" operator: Max(True), unless one is false.

The "**OR**" operator: Max(True), unless both are false.

The "**BUT**" operator: Find the 'middle ground' if allowed; if both sides fully agree then sway that way. Put another way: Always "1" unless one input is "0" or "2", then choose that instead; with "0" overriding "2".

The "**SHARKFIN**" operator: Addition (Mod 3). Put another way: Add and wrap, never exceeding two.

The "**WHAT**" operator: If both sides agree it's false, prefer "1" over "2"; oops, disregard that ... \[But you weren't asking about what\] ;)

> **Question:** "How could such an operation be used in practice (either on single trits or multiple trytes)?"

The webpage "MuppetLabs" website describes it this way:

> "In TriINTERCAL programs the whirlpool (@) denotes the unary tritwise BUT operation. You can think of the whirlpool as drawing values preferentially towards the central value 1. Alternatively, you can think of it as drawing your soul and your sanity inexorably down....".
>
> "As for operators, ? is always subtract without borrow, and ^ is always add without carry. V is the OR operation and always returns the max of its inputs. & is the AND operation, which chooses 0 if possible but otherwise returns the max of the inputs. @ is BUT, which prefers 1, then 0, then the max of the remaining possibilities. Rather than add more special symbols forever, a numeric modifier may be placed directly before the @ to indicate the operation that prefers one of the digits not already represented. Thus in files ending in .5i, the permitted unary operators are ?, ^, &, @, 2@, 3@, and V. Use of such barbarisms as 0@ to represent & are not permitted, nor is the use of @ or ^ in files with either of the extensions .i or .2i. Why not? You just can't, that's why. Don't ask so many questions.".

\[**NOTE:** In my opinion the Truth table provided by Esolangs (for "WHAT") is incorrect, it should be this:\]

$$ \begin{array}{cc|cc} \text{WHAT} \\, \qquad & ? & 0 & 1 & 2 \\ \hline & 0 & 0 & 1 & 2 \\ & 1 & 1 & 0 & 1 \\ & 2 & 2 & 1 & 0 \\ \end{array} $$

Please see Esoteric Programming Languages for less information.

---
Tags: computer-architecture, logic, discrete-mathematics, arithmetic
---