# Question
Title: Why do some architectures use a CMP instruction before branching while others just branch?
My initial guess is that you will have more instruction space for the immediate in your branch instruction when you first use a CMP instruction. However, you have to use 2 instructions each time you want to branch: a CMP and then the branch instruction.

So are there any advantages to using CMP?

# Answer
Every architecture may offer different flags and condition registers. It also may implement operations (e.g. addition) affecting these flags one way or another. Say an architecture A you mention does not need CMP; this means all flags and registers are set predictably in an orthogonal fashion for each operation (or else that particular jump/branch instructions must be enforced). An architecture B could not have this guarantee and use different flags for each operation and/or offer more generic jump/branch - then B offers a CMP instruction that makes sure flags are set as expected by the programmer/compiler.

There are several differences between A and B. For example, an architecture may offer more registers (X, Y not just ACC) which you could directly run operations on (therefore appropriate CMP instructions makes sense to select register etc). Architecture A may have to implement additional logic or even offer more flag registers to accomplish its aforementioned guarantee. Some processors want an instruction to do minimal register transfers/operations to maintain a given command execution cycle/clock.

These are a few things there are of course much more that turn this and other design choices to a successful architecture for compilers and intended users. Each choice reflects on the instruction set. What is important is to take advantage of each instruction the way it is intended in the best way and produce correct and fast code easily even in an automated way (from compiler).

All of the above possible reasons aside, note that you do not always have to use CMP (or have two instructions to branch) if your flags, condition registers are treated as you need them from the previous operation - you use CMP only if previous operation set flags are not set as expected for a subsequent branch.

Indeed sometimes in assembly written by humans (not compiler) we often just add a CMP in there, even if unnecessary, just to make sure because we may not remember the flags each operation affects (so that is a waste and not the way CMP is intended at least not for performance programming)!
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: What's the algorithm for floating points equality test?
I've found that `0.1 + 0.2 == 0.3` is not true in Java (see this demo).

So, I'm interested in how equality testing can be implemented for floats. Is there a standardized algorithm?

# Answer
You cannot meaningfully test floating point values for equality. A floating point value does not represent a real number, it represents a range of real numbers, but it fails to store the width of this interval. All you can do with floating point values is to test them for **approximate** equality, and it's up to you to define the approximation you're willing to make. You can test whether the difference is smaller than a certain constant ($|x-y| \le \epsilon$), or whether it's relatively small ($|x-y| \le \epsilon \min\\{x,y\\}$), or something else; the right method and the value of $\epsilon$ depend on the calculation.

There is a seminal article on this topic: the aptly titled ***What Every Computer Scientist Should Know About Floating Point Arithmetic*** by David Goldberg \[PDF\]. Sure, it's long — that shows how difficult floating point is to use, if you care about things like whether `0.1 + 0.2` equals `0.3`. And no, there is no magic bullet that would let you sweep the difficulties under the carpet. There is a good, more accessible summary called **What Every Programmer Should Know About Floating-Point Arithmetic\*, or, *Why don’t my numbers add up?***

Applications that require exact computations, such as financial computations, do not use floating point. They use integer or fixed-point arithmetic.

Applications that use floating point require a careful, expensive analysis to find out what the uncertainty in the result is. Keep in mind that a floating point value does not really represent a real number $m \cdot 2^e$ nor even a specific interval like $\left\[(m-\frac12) 2^e, (m+\frac12) 2^e\right\]$, but an interval whose width increases as the computation becomes longer as the uncertainty accumulates.

There is a standard for floating point operations, which most (but not all) systems today implement: IEEE 754 (“IEEE floating point”). This standard defines storage formats, rouding rules, denormalized numbers, etc. It tries to arrange for typical computations to be as precise as possible. Arranging for `0.1 + 0.2` to equal `0.3` is beyond its abilities (that would be possible, but then it would cause `0.2 + 0.3` not to equal `0.5` or some similar misfit).

Some threads on Stack Overflow on this topic:
> 7 votes

# Answer
The `==` operator invoke a float point compare instruction, this considers two numbers equal if neither is `NaN`, and they are exactly the same, or if they are positive and negative zero. Notably `Infinity == Infinity`, despite the mathematical dubiety of considering infinities equal, and `Infinity - Infinity` returning `NaN`.

So if the numbers are not exactly equal, for instance because of the inability of IEEE 754 floating point numbers to represent fractions where the denominator is not a power of $2$ exactly, the result will be that the numbers are considered unequal.

Note however that IEEE 754 floating point numbers are capable of representing all integers from $-2^{53}$ to $2^{53}$ exactly, which means that the equality operator can be used reliably with these numbers. This is pretty important in JavaScript (and any other language without integers), as it makes it easy to use floating point numbers in place of integers.
> 5 votes

---
Tags: floating-point
---


# Question
Title: Efficient algorithm to find vertex with paths to every other vertex
$G=\<V,E\>$ is a directed graph. I need to write an efficient algorithm that finds a $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ ($v$ has a path to every other vertex), or "false" if there aren't any. If there are more than one, return one of them.

The obvious and inefficient way would be to run BFS from every vertex, checking after every run of BFS if there are vertices with distance $= \infty$. If not - that vertex has paths to every other vertex. Complexity would be $O(|E||V| + |V|^{2})$.

I can't think of any substantial improvements. If someone could point me in the right direction (pun intended), that would be great!

# Answer
> 4 votes
You'll need to split the graph in to its strongly connected components, and then find a component from which you can reach every other component.

---
Tags: algorithms, graphs, search-algorithms
---


# Question
Title: NLP - Deep belief neural networks or logic?
The NLP progresses seems to me that has split in two big group of thoughts:

1. Deep learning have a neural network with multiple layers that has been trained and learned to represent knowledge and understand the meaning of sentences. However, such system would be difficult to debug and correct
2. Logic and inference, label parts of speech and learn by inference and using tools such as Natural logic.

Can someone point out if anything is wrong in these conclusions? Is there any other stream of thoughts that I should be taking into consideration?

# Answer
Very briefly:

Option 1 faces difficulties since certain connectionist models are incapable of learning natural languages.

Option 2 faces grave difficulties due to many negative results, notably Gold's theorem. There's a nice overview which includes a discussion of probabilistic approaches.

Generally, the response to these difficulties has been to look at other sources of information beyond the linguistic input alone.
> 1 votes

---
Tags: natural-language-processing
---


# Question
Title: How do I efficiently checking if a string matches any substring in a collection
I have a collection of substrings

```
"this" "is" "a" "antelope"

```

I need to look at any given string and answer the question "Are any of the given substrings in this string"

So my input string might be

```
"issue"

```

Which would be a match because "is" is a substring of "issue"

My first stab at this, I incorrectly turned my collection of substrings into a trie. That got me nowhere fast as it answered the inverse "is the input string a substring of the given collection".

Is there some algorithm or data structure I can transform my collection into to efficiently answer this question? I mean, I could do the simple brute force "check the input against every substring" method, but it seems like there is a better way.

In my given example, I would expect that "antelope" would never be checked because "a" covers every case that antelope would. I may even expect that "is" would remove "this" since every case that "this" would find a match "is" would as well. So it seems like eliminating longer substrings with shorter ones would yield some better performance.

I'm rambling... Anything I should be looking into?

# Answer
> 6 votes
I think the Aho-Corasick algorithm is your best bet here. The algorithm is designed to solve the set matching problem (essentially the one you've defined), in which you want to determine which elements of a set of substrings, L, can be found in a longer string, S.

It runs in time $O(n + m + z)$, where $n = \sum \limits\_{l \in L} |l|$ (the total combined length of the substrings in $L$), $m$ is the length of S, and $z$ is the number of matches of $L$ in $S$.

---
Tags: algorithms, strings
---


# Question
Title: Can we build an operating system that can be infected by any virus?
Is it theoretically feasible to engineer a computer (more specifically its operating system) that is simple and primitive enough to be infected with *any* type of virus? That is, this would be a computer that can execute any type of computer virus regardless of what platform the computer virus was initially designed to attack.

# Answer
> 1 votes
It is not theoretically possible.

---

A virus is an executable, and like all executables it consists of instructions in an instruction set for a specific hardware or virtual machine architecture. In addition, an executable depends on libraries and/or syscalls provided by the operating system, and these vary from one OS to the next. For the sake of argument, let us combine the ISA and the OS architecture into a single thing we'll call a "platform"

Normally, an executable for platform "B" won't run on a different (incompatible) platform "A". However, it possible to implement an emulator for platform "B" that runs on platform "A". If you repeat this for all other possible platforms, then you could *in theory* run *any* executable on platform "A". That includes any virus.

(This is all very theoretical / hypothetical. The shear effort involved in implementing emulation layers for all possible platforms is prohibitive ... and pointless.)

---

But then you have the issue that different viruses exploit different vulnerabilities (on their respective target platforms). For a virus to successfully infect our hypothetical platform "A", the respective emulation layer must exhibit the vulnerabilities that the virus uses.

However, in the real world, some vulnerabilities are introduced when earlier vulnerabilities are fixed. So virus V1 and V2 may depend on vulnerabilities that cannot *both* exist on a given platform or platform emulation. In other words, our hypothetical OS cannot be infected by both V1 and V2.

---
Tags: operating-systems
---


# Question
Title: computer organization : finding control word length
A microprogram control unit is required to generate a total of 35 control signals. Assume that during any microinstruction, at most 2 control signals are active. The minimum number of bits required in the control word to generate the required control signal will be

a.2 b.6 c.7 d.8 ?

Please explain how to calculate this?

# Answer
> 0 votes
The options are wrong. The answer is 10.

Check here for proper options (although sadly, the question is wrong :( )

---
Tags: computer-architecture
---


# Question
Title: Different boolean degrees polynomially related?
Let $f$ be a Boolean function.

Let $p$ be the minimum degree real polynomial that represents $f$ with degree $d\_f$.

Let $p\_\epsilon$ be the minimum degree real polynomial with degree $d\_{f,\epsilon}$ such that $$|p\_\epsilon(x)-f(x)|\leq\epsilon.$$

Let $p\_{0,\epsilon}$ be the minimum degree real polynomial with degree $d\_{0,f,\epsilon}$ such that $$f(x)=0\implies p\_{0,\epsilon}(x)=0$$$$f(x)=1\implies|p\_{0,\epsilon}(x)-f(x)|\leq\epsilon.$$

Let $p\_{1,\epsilon}$ be the minimum degree real polynomial with degree $d\_{1,f,\epsilon}$ such that $$f(x)=1\implies p\_{1,\epsilon}(x)=1$$$$f(x)=0\implies|p\_{1,\epsilon}(x)-f(x)|\leq\epsilon.$$

Are $d\_f,d\_{f,\epsilon},d\_{0,f,\epsilon}$ and $d\_{1,f,\epsilon}$ all polynomially related? It is clear $$d\_{f,\epsilon}\leq d\_{0,f,\epsilon},d\_{1,f,\epsilon}\leq d\_f.$$

Does $$d\_{f}\leq (d\_{0,f,\epsilon})^a,(d\_{1,f,\epsilon})^b\leq (d\_{f,\epsilon})^c$$ hold for some $a,b,c\in\Bbb N$?

What is a good reference to understand relations among these four degrees?

# Answer
> 2 votes
It is known that $$ d\_f = O\_\epsilon(d\_{f,\epsilon}^6), $$ for all $\epsilon \< 1/2$. This is described in many lecture notes, for example these quantum lecture notes by Montanaro (Theorem 3). It is suspected that the best exponent is $2$. It is known that the exact value of $\epsilon$ only affects the constant.

Since $d\_{f,\epsilon} \leq d\_{0,f,\epsilon},d\_{1,f,\epsilon} \leq d\_f$, the other measures are also polynomially related.

---
Tags: complexity-theory
---


title: Randomized and deterministic reduction

text:
# Question
Title: Randomized and deterministic reduction
Given a problem $X$, to show it is is $\sf NP$-complete, one usually shows a deterministic reduction from an $\sf NP$-complete problem.

If it is hard to show deterministic reduction, then one shows a randomized reduction.

1. What does a deterministic reduction give about the hardness of the problem that a randomized reduction does not give?
2. What is the consequence if there is a randomized reduction from an $\sf NP$-complete to $X$, however one can show there is no deterministic reduction from an $\sf NP$-complete problem to $X$?
3. If we have only randomized reduction, is $X$ still an $\sf NP$-complete problem or could it have faster algorithms?
4. What does it mean for problem $X$ if there is a randomized reduction from $\sf NP$-complete problems? (Does it mean $X$ is still $\sf NP$-complete?)

# Answer
> 10 votes
Let's answer your questions one by one:

1. A deterministic reduction proves NP-hardness. A randomized reduction doesn't. If a problem is NP-hard with respect to randomized reductions, then it could (potentially) be solvable in polynomial time even if P$\neq$NP. The assumption BPP$\neq$NP does rule out polynomial time algorithms for any such problem, however – even randomized ones.
2. The consequence is that P$\neq$BPP, which is conjectured to be false.
3. NP-hardness is defined with respect to deterministic reductions.
4. We say that the problem is "NP-hard with respect to randomized reductions".

---
Tags: np-complete, reductions
---


# Question
Title: Greedy and backtracking solutions to an arrangement problem with constraints
I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class mates but they all seemed to be confused. One gave me a sample answer of code doing it, whereas another one thought he wants some sort of graph with nodes/edges to represent the answer.

> 1) A group of $n$ teenagers $T\_1,\dots,T\_n$ are to sit in a single row of $n$ chairs watching a particularly boring comedy movie. Some teenagers quarrel with each other all the time. The problem is to devise a seating arrangement for the group in such a way that teenagers sat next to each other do not quarrel.
>
> a) Propose a solution to this problem using the Backtracking approach. Specify clearly the search space and any pruning conditions used. Show how your algorithm would work for 3 teenagers, $T\_1,T\_2,T\_3$, assuming that the only quarrelling teenagers are $T\_2$ and $T\_3$. Note: stop the search after finding a solution. \[12 marks\]
>
> b) Propose a solution to this problem using the Greedy approach. Estimate the complexity of the resulting algorithm. \[8 marks\]

I've spent days going through my notes and reading up on greedy/backtracking but I still don't see how it fits with the question. Whenever I look up Backtracking/greedy approach questions the questions are nothing like how college asks them which makes me very confused...

We've covered dynamic programming, backtracking, greedy algorithms knapsack problem, first fit, next fit minimal spanning trees, Kruskal's algorithm, Prim's algorithm, divide and conquer $N$ queens problem for backtracking.

# Answer
> 7 votes
## Overview of the problem

If you takes teenagers as vertices of a graph, and have an edge whenever the two teenagers are compatible. This gives you an undirected graph, and what you need is a **Hamiltonian path** in this graph (a path that contains every node exactly once). Maybe searching the web on this abstract version of the problem will yield more information. Much is said in wikipedia about the Hamiltonian path problem, which is a NP complete problem. I will only try to discuss some apects, with my limited competence on the topic, taking into account the way your question is stated.

Backtracking is just a way of implementing a non-deterministic algorithm. It is usually simpler to describe the non-deterministic algorithm, and just say that it is implemented by backtracking, and possibly explain separately what that is (as I do below)

## The non-deterministic algorithm

In the case of the Hamiltoniam path problem (which you can translate back into your teenagers problem), the non-deterministic algorithm is as follow:

1. Choose a starting node for the path, and mark it used.
2. While there are unmarked nodes do:

Choose a new unmarked node connected to the last node added to the path, add it at the end of the path, and mark it used.

At the end of the loop you have a Hamiltonian path. The `choose` statement is non deterministic, as you have to take one of many possibilities, many (or all) of which may not succeed.

## Backtracking interpretation

Failure may in general occur in different ways. Here you have failure when none of the unmarked nodes is connected to the last node added to the path (i.e. none of the remaining teenagers is compatible with the last one chosen).

The backtracking implementation consist in keeping track, at each occurrence of a `choose` statement, of all the possible choices that have not yet been tried. If you fail, you go back to the previous `choose`, undoing what was done (i.e. node addition to the path and node marking), discard the choice made and make a new choice from those that have not yet been tried at that `choose` statement.

One way of implementing this is to associate a list of remaining alternative choices to each node of the constructed path. Another possibility is to rely on the exception mechanism of the programming language.

## Pruning

I am not sure what is (or should be) considered pruning in this case.

Checking that a node chosen is connected to the previously chosen one is a very trivial form of pruning. No pruning at all would be exploring the complete set of remaining nodes at each `choose` statement, to discover soon after that some fail because the node is not connected to the end of the path.

## Greedy algorithm

The greedy algorithm as described by Yuval Filmus' answer is just the non-deterministic algorithm, except for the fact that you do not backtrack. You just fail. I do not know whether there is more to be said.

He is much more expert than I am on these issues. However, my own feeling is that the very concept of greedy algorithm makes less or little sense in this case. The reason is that I understand greedy algorithms as a way of finding good solutions to quantitative optimization problems, which may not be optimal in some cases.

A greedy algorithm also has to make choices, and does so on the basis of local optimizations that may not be optimal globally. But it is expected to succeed anyway and does not have to backtrack: the price of greediness is that the "cost" (however defined) of the result obtained by the algorithm may be higher than the cost of the optimal solution.

I do not think that is really very meaningful in an all or nothing situation, were you are supposed to succeed or to fail, without any measure of intermediate situations, like placing the largest possible number of teenagers, or placing them all with the smallest number of conflictual sittings. These examples may be seen as optimization variants of the problem where greediness makes sense.

However, we can use heuristics that could possibly increase the chances of success. In the case of our optimization variants, they could e seen as greedy techniques that improve the chances of having near otpimal solution (Though I did not prove anything). But the greedy algorithm remains basically the non-deterministic description. The heuritic comes as a way to choose that improves chances of success, or of approaching the least cost.

One such heuristic, is to always choose one of the unmarked nodes that has the least number of edges connecting to other unmarked nodes. The purpose is to keep in your bag nodes that will be easier to connect to the path, while removing those that are getting hard to use. And if one of these node is disconnected from all others, or has only one connection but cannot be added to the path immediately, you know you have failed and can start backtracking earlier.

We could say that we try to optimize the cost of the search reather than the cost of the solution obtained, and that this "greedy" algorithm does increase the chances of success if there is no backtrack, or reduce the number of search steps if we use backtrack, or improve the solution obtained if we consider one of the two optimization variants I described above (maximum number of non-conflicting teenagers, or minimum number of conflicts).

## A global improvement

A global way to improve the algorithm is to decompose the graph into a a **block tree of the graph**, where each node is a **biconnected components**. This can be done in linear time.

A Hamiltonian path for the whole graph is composed of subpaths in each of the biconnected components, connected by the edges of the block tree.

In practice, you solve the given problem at the level of the block tree, and then you solve it independently for each block, i.e. for each biconnected component.

Since the algorithm is exponential anyway (NO complete), there is much to be gained whenever it can be decomposed, thus reducing the size of the sub-problems.

Actually, if the block tree is not composed of a simple path without branching, there is no solution to the problem. So that may be a way of getting much faster negative answers.

This may also be seen as a form of global pruning of the search space.

# Answer
> 5 votes
The idea of the backtracking algorithm is simple, though somewhat cumbersome to express. Perhaps it's easiest to explain it working through the example in the question. We start by putting $T\_1$ on chair 1. We then put $T\_2$ on chair 2. Then we put $T\_3$ on chair 3, and we discover a conflict. So we backtrack, replacing $T\_3$ with the next available student. In this particular instance, there is no other student, so we also remove $T\_2$ and replace it with the next available student, $T\_3$. The situation now is $T\_1T\_3?$. We put the first available student, namely $T\_2$, on chair 3. Again we discover a conflict, so we backtrack. We attempt to replace $T\_2$ with another student, but there are no such. Then we attempt to replace $T\_3$ with the next student, but there are none. So we backtrack once again, and replace $T\_1$ with $T\_2$. The situation now is $T\_2??$. We then put the first available student, which is $T\_1$, on chair 2, and then $T\_3$ on chair 3. At this point we stop since this is a feasible solution. The entire transcript is:

* ???
* T\_1??
* T\_1T\_2?
* T\_1T\_2T\_3
* T\_1T\_3?
* T\_1T\_3T\_2
* T\_2??
* T\_2T\_1?
* T\_2T\_1T\_3

Hopefully you can now formulate the general algorithm.

As for the greedy approach, I don't really see where they're going. The natural greedy algorithm in this case works as follows:

* Put $T\_!$ on chair 1.
* Put the lowest-indexed student $T\_{i\_2}$ not conflicting with $T\_1$ on chair 2.
* Put the lowest-indexed student not conflicting with $T\_{i\_2}$ on chair 3.
* And so on.

The problem with this algorithm is that it could fail – as it indeed does in the example analyzed in part (a). So the greedy approach fails.

As babou mentions, the problem described in the exercise is Hamiltonian Path in disguise, so (unless P=NP) doesn't have efficient solutions.

---
Tags: algorithms, search-algorithms, greedy-algorithms, hamiltonian-path, backtracking
---


# Question
Title: Mathematical model for a webpage layout?
Getting layout right (even if only a structure is considered) with HTML5/CSS3 is still more like an art or black magic.

On the other hand, there are other GUI systems (like wxWindows and Tcl/Tk) and some GUI research (like The Auckland Layout Model, ALM, and other methods), which hint at the possibility of formalization for the layout managers (geometry managers).

Are there any comprehensible formal models for HTML5/CSS, which provide ultracompact (abstract) way to describe structure, "physics" and "geometry" of resizeable webpages, using language of blocks? Also html/css can be generated from it, which works more or less as described in standard browsers. Also, a model can be derived given HTML/CSS (browsers do it by their algorithms, so this seems to be theoretically possible).

By "ultracompact" and abstract it is understood: much more compact than HTML/CSS and also more domain-oriented, "speaking" the language of webpage's dynamics in response to resizing or changed content, that is, higher level than HTML/CSS constructs.

For an analogy, it is possible to write a program to make a textual search, based on some complex rules, but the same task can be performed by a much more compact regular expression. So, is there similar compact language for HTML/CSS layout?

The goals of such a model could be:

* to verify existing design (model checking)
* to build robust design given higher level specifications
* to check whether a set of requirements is consistent with HTML5/CSS3 engine (e.g., does not require writing javascript to make an adjustment too complex for the declarative languages)
* to be a solid platform for even higher level research on qualities ("to check the harmony with algebra.")

Also it could be a language to use for certain GUI-related abstractions, like is usual in programming language domain, where we do not need to use concrete syntax to express an idea of for-loop and we do have all kinds of nice, proven results about main concepts of algorithmic constructions.

Of course, web-browsers possess algorithmic model for rendering, e.g. popular and simplified description can be found here, but as pointed above it does not have the properties listed above.

# Answer
At the time of writing, I am not aware of any formal (or at least formalized enough) models for layouts in HTML. All the examples (ALM, etc) indicate, that usually the model is created to guide layout manager's creation. In the case of HTML and web-browsers the development is evolutional and while each web engine contains some sort of algorithmic models to be able to render HTML, nobody (I know of) published underlying math, and nobody "reverse engineered" program code to extract the model.

It should also be noted, that the model could have grown very complex, so any effort to build one retrospectively may be quite costly.

Even though it is not done yet, it does not mean it is impossible. As more rigorous approaches are being applied to web programming (e.g., recent release of Ur/Web - typesafe approach spanning from database to client-side interactions), modelling HTML5 layout management may be on the horizon, especially, as we witness more formal approach in the recommendations for new HTML5/CSS features (for example, http://www.w3.org/TR/css3-flexbox/), because having formal model may help proving consistency of the additions (analogously to formal grammar, which greatly facilitates making additions to the programming language syntax).
> 0 votes

---
Tags: modelling, user-interface, hci
---


# Question
Title: Identical register input operands in assembly
The question is not specific to any processor. Can I have an assembly instruction, like:

```
 ADD R1 R0 R0

```

`R1` is the destination.

My understanding is that, if the register file in a processor supports 2 simultaneous reads in a clock cycle (i.e. 2 read ports), two different registers can be read. But for 2 same input registers, this case has to be handled explicitly wherein the input can be duplicated after reading the first operand, and if that is not supported, the register file MUST have 2 read ports in one clock cycle, if not it might lead to a structural hazard.

I would like to know if my understanding is right.

# EDIT:

And also do, any processors (current/old) handle this case, explicitly.

Thanks in advance.

# Answer
`R1 <- R0 + R0` works in every processor that permits three register operands. Nothing special needs to be done to deal with the same register driving multiple read ports.

Each register-file read port is just a multiplexer. If you have $N$ registers driving the $N$ inputs of one $N$-to-$1$ multiplexer and the same $N$ registers driving the $N$ inputs of a different $N$-to-$1$ multiplexer, there's no constraint that says that both multiplexer selects can't be set to the same register.
> 2 votes

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


title: Heapsort for sorted input

text:
# Question
Title: Heapsort for sorted input
What is the running time of heapsort when the input array is in increasing order? How about decreasing order? (I came across these questions in CLRS.)

---

Here is what I have done so far ...

For the increasing order (i.e. the order opposite to the output order) I am completely stuck and haven't been able to make any progress because as I see it as soon as we build the max heap the structure completely changes and I cant reason about what the final heap will look like.

For the decreasing case I feel like I understand what is going on and will try to describe that below, but its also a long way from a proof. A decreasing array is already a max heap so the array is unchanged by building the max heap. WLOG assume a complete binary tree (else just remove some elements until you get one)

Remove the first $n/4$ largest elements. The first element will then be lifted to the top and fall back down a distance of $\log n$ falling to the left each time (the left element is always the largest).

But now the right is larger for each vertex that this last element fell through. So the next vertex will first fall right then fall left the rest of the way. No vertex will fall the same path until this has been rectified. So elements moved to the top of the tree continue to fall the full length of the tree. Rectifying the tree seems like it will take a linear time because it has length logn and it feels like you have to go down a constant fraction of the other routes before it is done. But this is really wordy and sort of garbage.

I apologise if this could be written better but I tried my best to say what I mean.

Note I have read the proof for the general best case but I was looking for something more straightforward due to the extra information.

Thanks

# Answer
> 2 votes
Time complexity of heapsort is $O(n \log n)$ for all types of input. If we have all input we need $O(n)$ time to build the max-heap. Then for sorting the the data, we need to remove the first element of the array then heapify the remaining data and repeat it for $n$ times. Which the act of heapifying for all steps needs $O(n \log n)$ time.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting, heaps
---


# Question
Title: Gyorgy E. ReveszExercise 1.1: Show the grammar $G$ generates the language $L$
The exercise says

"Show that the grammar $G = \langle\\{S\\}, \\{a, b\\}, S, \\{S \to \lambda, S \to aSb\\}\rangle$ generates the language $L = \\{a^i b^i \mid i = 0, 1, 2, \ldots\\}$."

Now, I'm new to this subject although I'm familiar with the theory of Turing machines and automata. I'm teaching myself (not in a class, completely independently) from scratch. Please go easy on me.

Now, two questions:

(1) I suspect the way to do this proof is by induction on $i$, which is to say induction on the iterations of letters in the alphabet or the length of the word formed by iterations of $a, b$. ***Is this assumption correct?***

(2) If the assumption in (1) is not correct, what ***is*** the correct strategy?

# Answer
Generally speaking, you need to do two things:

1. Prove that every word generated by $G$ is in $L$.
2. Prove that every word in $L$ can be generated by $G$.

Hints for (1): Prove by induction on the length of the derivation.

Hints for (2): Prove by induction on $i$.
> 4 votes

# Answer
Ok, so here's my attempt at a solution, after not having looked at the problem since April. I think this is on the right track.

Given Yuval's helpful comment, we are to show (1) that every word $w$ generated by $G$ is in $L$ (2) every word $W$ in $L$ is in $G$

To show (1), we proceed by induction on the length $m$ of a derivation using the rules of $G$. There are two cases: either (i) $m$ = 1 (ii) $m$ $\>$ 1.

Basis: $m$ = 1. Thus we have applied the first rule once, and must be $S$ $\rightarrow$ $\lambda$ and so we have $\lambda$ = $a$$^0$$b$$^0$, which is in $L$.

Induction step: $m$ $\>$ 1. Suppose for inductive hypothesis the claim holds for all $n$ $\<$ $m$ to show $m$, i.e. every stage $n$ $\<$ $m$ in the derivation using rules of $G$ is in $L$ to show that the entire derivation of length $m$ is in $L$. Then the rule applied must be of the form $S$ $\rightarrow$ $a$$S$$b$, and we have a derivation of $a$$^m$$S$$b$$^m$. By inductive hypothesis, we can apply the rule $S$ $\rightarrow$ $\lambda$ once and have $a$$^m$$b$$^m$ which is in $L$.

To show (2): Induction on $i$, which is the number of repetitions symbols $a$, $b$ which is held constant.

Basis: $i$ = 0. Then $a$$^0$$b$$^0$ = $\lambda$, and clearly $\lambda$ $\in$ $G$ by the production rule $S$ $\rightarrow$ $\lambda$.

Induction step: $i$ $+$ 1 $\>$ $i$. Suppose for induction hypothesis that the claim holds for all $i$ $\<$ $i$ + 1 i.e. for all $i$ \< $i$ + 1, words $w$ having $i$ $+$ 1-many repetitions $a$ and $i$ $+$-many repetitions of $b$ (consecutively) are in $G$. We wish to show that a word $w$ with $i$ $+$ 1-many consecutive repetitions of $a$, $b$ is in $G$. To this end, we simply apply the second rule $S$ $\rightarrow$ $a$$S$$b$ Until we get to the desired length.
> 2 votes

---
Tags: formal-languages, formal-grammars
---


title: Prims Algorithm MST

text:
# Question
Title: Prims Algorithm MST
I have this problem :

And here's my attempted solution,

could someone inform on whether it's correct

thanks

Haven't got enough reputation to make them into images so far..

# Answer
> 2 votes
Your MST looks correct.

Prim's algorithm builds the MST as follows:
Start with an empty set of nodes and edges: $V=\\{\\}, E=\\{\\} $.

1. Add node $1$ to the MST (but any other starting node will do).
$V=\\{1\\}, E=\\{\\} $
Now consider all the nodes not in the MST that are connected to it and pick one with the lowest edge weight:
d(1,2) = 3, ***d(1,5) = 1***, d(1,4) = 2
We pick edge $(1,5)$ and add it to our edge set $E$. We add $5$ to $V$.
2. $V = \\{1,5\\}, E = \\{(1,5)\\}$
Proceed the same way. Consider all the nodes not in the MST that are connected to it by an edge and pick an edge with the lowest weight:
d(1,2)=3, **d(5,4)=1**, d(5,3)=2 d(5,6)=4
We pick edge $(5,4)$.
3. $V = \\{1,5,4\\}, E = \\{(1,5), (5,4)\\}$
d(1,2) = 3, **d(5,3) = 2**, d(5,6) = 4
4. $V = \\{1,5,4,3\\}, E = \\{(1,5), (5,4), (5,3)\\}$
d(1,2) = 3, **d(5,6) = 1**
5. $V = \\{1,5,4,3,6\\}, E = \\{(1,5), (5,4), (5,3), (5,6)\\} $
**d(1,2) = 3**
6. $V = \\{1,5,4,3,6,2\\}, E = \\{(1,5), (5,4), (5,3), (5,6), (1,2)\\}$

We stop when $V$ has all the nodes of our graph.

---
Tags: algorithms, spanning-trees
---


# Question
Title: Knight's tour from all starting positions
Is it true that for all $n\geq 5$, there is a knight's tour of an $n\times n$ chessboard beginning at every square?

For example, is it correct, that there is no solution for a $5\times5$ board, with start position $(5,4)$?

# Answer
> 5 votes
The Wikipedia article links to several useful papers. According to the paper Solution of the knight’s Hamiltonian path problem on chessboards, there is no such tour; see Theorem 3.1(ii). They show that a knight's tour on the 5x5 board always starts or ends at a corner. It's also easy to see that both endpoint squares have the same color. Since the (5,4) square has a different color than the corners, no knight's tour starts at (5,4).

---
Tags: graphs
---


title: Lower-bounds of a given problem

text:
# Question
Title: Lower-bounds of a given problem
I have the following problem:

> You have n objects that have identical weight except for one that is a bit heavier than the others. You have a balance scale. You can place objects on each side of the scale and see which collection is heavier.
>
> Goal is to find the heavier object, with the minimum number of weigh.

I know the best algorithm that can solve this problem. Here is the pseudocode:

```
function findDiffWeight(L[1:n]){

   if(L.size == 1) return L[1]

   int x = sum(L[1 : n/2])
   int y = sum(L[n/2+1 : n])

   if(x>y)  call findDiffWeight(L[1 : n/2])
   if(y>x)  call findDiffWeight(L[n/2+1 : n])
}

```

But I am struggling with finding the lower bound for this problem. I don't think that there can be a better algorithm that can solve this in less than `logn` operations.

However how to prove it? Could you give me some idea about finding lower bound for this problem?

# Answer
Your algorithm, which requires $\lceil \log\_2 n \rceil$ weighings, is in fact not optimal. This paper proposes an algorithm which uses $\lceil \log\_3 n \rceil$ weighings, which is optimal by the argument outlined by Tom van der Zanden. Let's assume for simplicity that $n$ is a power of 3, leaving the general case as an exercise. Suppose we are given $3^k$ objects, which we divide into three groups $X,Y,Z$ of size $3^{k-1}$. We weight $X$ against $Y$. If $X \> Y$, we recurse with $X$; if $Y \> X$, we recurse with $Y$; if $X = Y$, we recurse with $Z$. After $k$ such steps, we will have zeroed in on a single object.

For the lower bound, suppose that we only do $k$ weighings. There are $3^k$ possible outcomes of this weighings – each one can be either "left side heavier", "right side heavier", or "both have the same weight" – and each of them causes the algorithm to output a definite answer. Since any of the $n$ objects could be the heavier one, we must have $3^k \geq n$. This argument will make more sense after you review the $\Omega(n\log n)$ comparison lower bound for sorting.
> 3 votes

---
Tags: complexity-theory, lower-bounds
---


title: Direct Cache Mapping Hit Or Miss

text:
# Question
Title: Direct Cache Mapping Hit Or Miss
I am have a difficult time understanding when a direct map cache is a hit or a miss. My understanding is that when and index matches, but a tag doesn't it is still a miss but the new tag then takes over the previous tag on that index.

```
Address  Binary Address   Tag       Index   H/M

3        00000011        0000        011    Miss
180      10110100        1011        100    Miss
43       00101011        0010        011    Miss
2        00000010        0000        010    Miss
191      10111111        1011        111    Miss
88       01011000        0101        000    Miss
190      10111110        1011        110    Miss
14       00001110        0000        110    Miss
181      10110101        1011        101    Miss
44       00101100        0010        100    Miss
186      10111010        1011        010    Miss
253      11111101        1111        101    Miss

```

As such my theory is that all of the mappings are misses, am I correct?

Thank you so much guys!

* The block size is one word; therefore we use no offset bit
* The total size is 8 blocks; therefore we need only 3 index bits

# Answer
> 1 votes
No reps to comment.

@Nathan: The binary address is split as a tag-part and the block size. Basically, the cache is split as many-byte blocks and tag each entry maps to a block and the index, or *offset*, is added to the address to address a byte.

So the binary addresses are 8-bits long. And based on the question the block seems to be 8 bytes long (hence 3 LSB bits for Index, also called *offset*). This leaves 5 additional bits for tag (Remember addresses are 8 bits long).

---
Tags: computer-architecture, cpu-cache, memory-hardware
---


title: Validity of reduction (3-SAT)

text:
# Question
Title: Validity of reduction (3-SAT)
I'm trying to show that a special variant of the common 3-SAT is NP-complete by reducing 3-SAT to this special variant.

This special variant works like the normal 3CNF-SAT, except every other clause is conjunctive instead of disjunctive. For example an instance of this variant could be $(x \vee y \vee z) \wedge (x\wedge w\wedge k) \wedge (y \vee \neg{}z \vee f)$.

EDIT:

Would the following work? If I want to reduce $from$ 3-SAT, I would propose an instance of the 3-SAT variant, and via an algorithm running in polynomial time, transform every other clause (the conjunctive ones) into 3 new disjunctive clauses like the following example.

Instance of 3-Sat Variance $(x \vee y \vee z) \wedge (x\wedge w\wedge k) \wedge (y \vee \neg{}z \vee f)$

Transformation/Reduction $(x \vee y \vee z) \wedge (x\vee x\vee x) \wedge (w \vee w \vee w) \wedge (k \vee k \vee k) \wedge (y \vee \neg{}z \vee f)$

EDIT 2:

Or do you mean I should look at it the other way around?

If I want to prove that this 3-SAT variant is NP-complete, could I for example simply add a new, trival term $z$ not used in the original list of terms (give it TRUE as truth value), and add a clause $(z \wedge z \wedge z)$ inbetween all the original clauses of the original 3-SAT instance?

# Answer
**Hint 1.** If the conjunctive "clauses" are trivially satisfiable, then any unsatisfiability must be due to the ordinary disjunctive clauses.

**Hint 2.** You don't have to change any of the clauses of the original CNF.
> 0 votes

---
Tags: np-complete, reductions, 3-sat
---


title: Divide and Conquer to find a power

text:
# Question
Title: Divide and Conquer to find a power
I understand the concept behind Divide and Conquer, making one problem into sub problems and then merging the solutions together. However, from looking at a past paper a question has occured where it asks how 2^11 can be found using Divide and Conquer, I'm just confused how finding a power can be divided into sub problems =/

pow(2, 11) = 2 * pow(2, 5) * pow(2, 5)

pow(2, 5) = 2 * pow(2, 2) * pow(2,2)

pow(2, 2) = pow(2, 1) * pow(2, 1)

pow(2, 1) = 2

would this be correct?

# Answer
> 3 votes
The algorithm relies on two facts:

* If $n$ is even, $n=2k$, we have $a^n = a^{2k}=a^ka^k = a^{n/2}a^{n/2} = (a^{n/2})^2$
* If $n$ is odd, $n=2k+1$, we have $a^n=a^{2k+1}=a^1a^{2k}=a(a^ka^k)=a(a^{(n-1)/2})^2$

In other words, we have $$ a^n=\begin{cases} (a^{\lfloor n/2 \rfloor})^2 &\text{if $n$ is even}\\ a(a^{\lfloor n/2 \rfloor})^2 &\text{if $n$ is odd} \end{cases} $$ You've computed $pow(a, n)$ by changing it to a problem involving an instance of the half-sized problem $pow(a, n/2)$ along with a squaring and possibly a multiplication by $a$.

---
Tags: algorithms
---


# Question
Title: Given this transition system, for which states are these (very basic) LTL formulas fulfilled?
I missed a lot of lectures for this module due to surgery so I'm trying to teach it to myself now. This is the question I've been working on:

First of all, would I be correct in saying that the LTL formulas are **b**, **c** and **e**? CTL are **a**, **d** and **f**?

For **(b)** I'm guessing the answer is s1 and s3, since those are the only states with b in them.

Looking at **(e)**, this says that the state must always contain *b* or *a*, so the answer is *s1*, *s2*, *s3* and *s4* (all states). Is this correct?

**(c)** is the one I can't get my head round. What exactly is it saying in english?

For now I'll just focus on the LTL stuff, so I just want to get b, e and c 100% correct. Any help is highly appreciated since I'm struggling a bit with this module.

Many thanks in advance!

# Answer
> 0 votes
Note that questions of the form "am I correct" are generally not acceptable on this site. Still, your question shows an effort, so here are some answers:

As for your classification to LTL/CTL - you are correct.

Let's look at (b) - it interprets to "always b", which means that in every path starting from the state, b must always hold. This is not the case for any state in the system (since every path eventually reaches s2, in which b does not hold).

As for (e) - it means that in every path, in every suffix, $bUa$ hold, so in every suffix it is true that b holds until a holds. In this system, you are correct that all states satisfy this.

(c) is perhaps easier than the other two - it reads as "next next a", and a state satisfies it if in every path from it, in two steps you will reach "a". In this system, every path gets within two steps to s2, s3, or s4, all of which have "a", so the formula holds.

---
Tags: logic, model-checking, linear-temporal-logic, temporal-logic
---


# Question
Title: L ={ $a^{m^n}$ | $m$>$n$ } is Regular or not by pumping Lemma
L ={ $a^{m^n}$ | $m$\>$n$ }
I am bit confuse whether to consider this language as L = $(a^{m})^{n}$ OR L = $a^{\left(m^n\right)}$.

If it is considered as L = $(a^m)^{n}$ then want to check it is Regular or not by Pumping Lemma.
I tried by following way.

$m$ \> $n$ so we can take $m's$ value as $n+1$.
So $L$ = $(a^{n+1})^{n}$

Let n be the Pumping Lemma Constant.
Then by pumping Lemma $u$$v^{i}$$w$ in $L$ for every $i$ $\>=$ $0$.

$1\<= |v| \<= n$

$uv \<= n$.

So here $u$ = $(a^{n+1})^{n-1}$

$v$ = $(a^{n+1})^{i}$ and

w = $\epsilon$

By taking $i = 2$ ,
I am getting string as $(a^{n+1})^{n+1}$Which is not possible. Because it means $m=n$.
So above string is not Regular.

But different solutions giving different answers. So confused whether it is Regular or not. And is there any problem in my solution ?

# Answer
> 1 votes
Let $A = \\{ m^n : m \> n \\}$, so that $L = \\{a^k : k \in A\\}$. It is not clear whether $m,n \geq 0$ or $m,n \> 0$. In both cases, every $m \> 2$ is in $A$ and $0 \notin A$. If $m,n \> 0$ then $1 \notin A$, while if $m,n \geq 0$ then $1 \in A$. In the former case, $L = aa^+$, and in the latter, $L = a^+$. In both cases $L$ is actually regular.

We can also consider the other interpretation, $A = \\{mn : m \> n\\}$; this interpretation is wrong, but it can shed light on your proof. Again we find that every $m \> 2$ is in $A$, and that $1 \notin A$. If $m,n$ are allowed to be zero then $0 \in A$, and otherwise $0 \notin A$. In the former case $L = aa^+ + \epsilon$, and in the latter, $L = aa^+$. In both cases $L$ is regular. So something must have been wrong with your proof.

# Answer
> 1 votes
The problem is poorly worded. There are two possible interpretations:

First, if the interpretation was $L=\\{a^{(m^n)}\mid m\>n\ge 0\\}$, then notice that $a^i\in L$ for any $i\>0$, (by choosing $m=i, n=1$ or, if $i=1$ choose $n=0$) so $L=\\{a^i\mid i\ge1\\}$ which is regular. Similarly, if the interpretation was $L=\\{a^{(m^n)}\mid m\>n\> 0\\}$, then we'd have $L=\\{a^i\mid i\>1\\}$, which is also regular.

Having ruled out that reading, the alternative is that $L=\\{(a^m)^n\mid m\>n\\}$ where we might have $n\>0$ or $n\ge 0$. The choice is immaterial. Note that $(a^m)^n=a^{mn}$ and @lucas has noted in the comments, that means that $L=\\{a^{mn}\mid m\ne m\\}$ but this is just the complement of the language $\\{a^{(p^2)}\mid p\text{ is prime}\\}$, which is known to be not regular. The PL proof of this is standard and can be found in lots of places. One could show directly by a PL proof that in this case $L$ is not regular, though as Yuval has noted your proof doesn't quite do it.

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


# Question
Title: Origin of tFAW (Four Activation Window) in DRAM timing constraint
In DRAM timing constraints, tFAW means length of a rolling window that allows up to four row activations in same Rank. This constraint is mainly due to power budget of each rank.

However, I am curious why 4 is the magic number？Would it be wrong if we use Eight Activation Window and double the value or use Two Activation Window and halve the value?

# Answer
> 2 votes
The magic number is just 4 since (within one rank) you have just 8 banks where you can spread your consecutive accesses. The problem lies with the bank activation current drained from the entire array (or bank) of single cells (transistor + capacitor) needed to prepare the memory location to be read. If the consecutive read operations are falling each time in a different ROW within each bank than you have the activation problem kicking in each time. In order to avert a high current drain from the arrays you need to limit the number of consecutive bank activation over a rolling window of time. The reason why you need to prevent the bank from high energy / current drain is because this may cause a Voltage Reference (VR) deterioration. The VR is the standard Voltage level against which earch data read from the bank is compared to verify if what you are reading is 1 or a 0. Risking to alter the VR level may mean that the reliability of what your read or write is compromised.

However these tFAW and tRRD parameters are usually overestimated and a memory tuner may increase system performances by slightly changing these parameters.

---
Tags: computer-architecture
---


title: NP Problem and reduction

text:
# Question
Title: NP Problem and reduction
I've read that "Every problem in NP can be reduced to every NP-complete problem". I want to know why the term "Every" is important.If we have one problem in NP that is reduced to one NP complete problem then what will be the problem.

# Answer
> 0 votes
Since NP-Complete problems can be reduced to each other, If we can reduce a problem to a specific NP-Complete problem. It means that we can reduce it to any NP-Complete problem. The reason is All problems in NP-Complete can be reduced to SAT and SAT to 3-SAT and 3-SAT to CLIQUE and so forth. So reducing to a problem in NP-Complete means reducing to all problems in NP-Complete.

---
Tags: complexity-theory
---


# Question
Title: Algorithm for generating sorting instructions
Let's say I am to sort a bookcase given a certain sorting condition, for instance alphabetically. I am looking for a way to generate a step-by-step guide on how to do this sorting based on the original order, as well as the final order.

Original order:

```
B C A D

```

Final order:

```
A B C D

```

Generated step by step instructions (by index):

```
0 -> 2
0 -> 2

```

The problem is, of course, each step will alter the sorting order, requiring the algorithm to take into account the new state of each order.

Is there such an algorithm readily available?

# Answer
> 1 votes
Generally speaking, you sorting algorithm should involve the following two steps:

1. Sort the books and assign them a numerical order.
2. Generate optimal sorting instructions given the permutation.

In your example, you start with a list of four books. Sorting them, you assign them a numerical order, B C A D (the numbers here are A,B,C,D). Then you figure out instructions for sorting the permutation B C A D. One approach that will always work is to move A to 0, B to 1, C to 2, and so on. However, this is not optimal. Figuring out the optimal sequence of moves seems like the difficult part of your question.

# Answer
> 0 votes
You seem to think that you problem is well stated, but I have some doubts.

Nothing is obvious, unless properly defined. When you move `0 -> 2`, what happens to book 2, is it out, or does it stay next to book formerly 0, probably behind it, in position behind the book formerly 0 you just moved (which happens to still be 2 in this case). It is for you to specify that precisely. I am here assuming that book 0 is placed before book 2, thus becoming book 1, since book 1 becomes book 0.

Then you could use other elementary steps, such as swapping two adjacent books, or more likely transposing two distant books, which is often easier than moving a single one, which may have to go on a shelf that is already full. That may however depend on whether books have the same thickness. Even if the shelf is not full, it is more costly to insert a book at the beginning than at the end of the shelf, since you have to move part of the row to make place for the inserted book. There are probably other considerations of the same kind, so that your one step instruction is by no means a constant cost operation in the real world, as it may seem on the computer. Now, it may be possible to consider an average cost (that depends on shelves fullness and possibly on the size of the collection), but that requires careful analysis.

Another problen is that identifying the book with index $i$ is by no means a simple operation in the real world, since your indexes keep changing. So the books cannot carry the index, and you have to count. Now, it is possible to force counting only on one shelf, if you keep track of shelves content in your algorithm. But that may require that the program knows about book thickness, and also instructs you regarding moving the end of a shelf to another shelf. Indexing is a unit operation on the RAM computer, but may not be in the real world. Actually, your shelves are more like a Turing machine tape.

Then, as already answered by Yuval Filmus, the actual sorting algorithm does not matter, since the cost of computing the final order of books on a computer is irrelevant. You are not concerned at all with testing relative order of books, but only in producing a minimal sequence of moves to get from one permutation (the initial order on the shelves) to another permutation (the sorted order that you have computed).

I do not know what could be the best algorithms to to that.

However, given the cost of indexing and of moving a single book, I would not proceed with the type of instructions you suggest. What may be the right procedure is probably dependent on the density of books to be moved, i.e. on whether the collection is nearly sorted, or in complete disorder.

If your basic instruction was a book transposition (exchange of two distant books), then the is some literature on this. See for example *Minimum number of transpositions to sort a list*. https://cstheory.stackexchange.com/questions/4096/minimum-number-of-transpositions-to-sort-a-list

However, I doubt this literature takes into account the practical problems I describe above.

Also, I do not know where to look for the kind of instructions you are using.

The major costs that I see come more from making room for the books and indexing, and I would rather worry about a physical organization to minimize these costs.

If the density of out-of-order books is low. One possibility would be to extract them, sort them, and merge them back on the shelves. But that is far from the initial problem.

If your question was merely a way to illustrate an bastract problem, you should be more explicit about it, as the reality distorts considerably the abstraction.

# Answer
> 0 votes
Since you didn't ask for the minimal amount of book moves but just the sequence, here's a way that will always work.

**Initial work**. For each book, count the number of books to its left whose titles are alphabetically after its title. Arrange these numbers in a list, starting with the earliest in order. For example, if the initial arrangement was CFABDE, your list will be 2, 2, 0, 1, 1, 0, since

1. Book A had C and F to its left, so the first entry in the list would be 2.
2. Book B had C, F, A to its left, and C and F were alphabetically after B, so the second entry in the list would be 2.
3. Book C had nothing to its left, so the third entry would be 0.
4. Book D had C, F, A, B to its left and F is alphabetically after D, so the fourth entry would be 1.
5. Similarly, book E had C, F, A, B, D to its left, so the fifth entry would be 1.
6. Finally, the sixth entry, for book F, is obviously 0.

In technical terms, you've produced an inversion sequence for the permutation CFABDE: $$\begin{array}{lcccccc} \text{Index:} & 0 & 1 & 2 & 3 & 4 & 5 \\ \text{Entry:} & 2 & 2 & 0 & 1 & 1 & 0 \end{array}$$

**Producing the move sequence**. We'll produce a list of instructions that will sort this initial sequence by repeatedly swapping adjacent books. I'll denote the swap of books in positions $i$ and $i-1$ by the instruction $(i, i-1)$. For every book $i$, in alphabetic order, swap book $i$ with its $b\_i$ left neighbors, starting at the right.

For our example, we'll have the following operations:

1. Book A ($i=0$, currently in position 2): $b\_0 = 2$ so we'll swap book A with its two left neighbors, F and C, in that order: CFABDE $\rightarrow$ CAFBDE $\rightarrow$ ACFBDE, so the first two instructions are $(2, 1), (1, 0)$.
2. Book B ($i=1$, currently in position 3): $b\_1 = 2$ so we'll swap book B with its two left neighbors, F and C, in that order: ACFBDE $\rightarrow$ ACBFDE $\rightarrow$ ABCFDE, so the next instructions are $(3, 2), (2, 1)$.
3. Book C ($i=2$, currently in position 2): $b\_2 = 0$ so make no swaps.
4. Book D ($i=3$, currently in position 4): $b\_3 = 1$ so we'll swap book D with its left neighbor, F: ABCFDE $\rightarrow$ ABCDFE, giving the instruction $(4, 3)$.
5. Book E ($i=4$, currently in position 5): $b\_4 = 1$ so we'll swap book E with its left neighbor, F: ABCDFE $\rightarrow$ ABCDEF, giving the instruction $(5, 4)$.
6. Book F: the last book will always be in its correct position, so we make no swaps.

Finally, we can sort these books by the instructions $(2, 1), (1, 0), (3, 2), (2, 1), (4, 3), (5, 4)$, in that order.

It should be noted that this method won't necessarily produce a minimal-length instruction sequence, but it eliminates the problem you noted of having to keep track of the intermediate rearrangements and it also eliminates some of babou's real-world problems, since you're only swapping adjacent books. It seems at first to be complicated, but I'd guarantee that after the tenth book it would be completely automatic.

---
Tags: algorithms, sorting
---


# Question
Title: How to count bits in cache (direct & 4-way)
Let's say, I have a cache with:

* 2^32 bytes of memory
* 2048 blocks (of 16 bytes each)

Now I'm trying to figure out how much bits each field will contain.

Direct mapped:

One block is 16 bytes (16 * 8 = 128 bits). The block also contains 1 dirty bit and 1 valid bit. I know that since there are 2048 (=2^11) blocks, and the whole block contains 16 bytes (=2^4) the tag-field will be 4 + 11 + 1 (valid) + 1 (dirty) = 17 bits. So the whole size of 1 block will be 17 + 128 bits. Is this right?

And if so, where do I need the given 2^32 bytes of memory, and what is the difference with the direct-mapped cache in comparison to counting the 4-way-set-associative cache fields?

I hope someone can help me, thanks in advance!

# Answer
> 1 votes
Maybe it is easier to look at addresses :

* address range : A\[31:0\]
* block address : A\[3:0\]
* cache line index : A\[14:4\] : 2048 = 11bits

Each tag contains :

* addresses A\[31:15\] : 17bits
* valid bit
* dirty bit, if it is a write-back cache

So 18bits (write-thu) or 19bits (write-back) per tag.

128+18 per block (or 128+19), 2048\*(128+18) bits for the whole cache. (excluding EDC, sub-blocking...)

**The tags contains the part of the address bits not indexed by the cache (not the contrary).**

Way associative caches need replicating both tags and data. Additional bits are also needed in that case for the replacement information (LRU, PLRU...) : Selecting which cache way should be replaced when a cache miss occurs.

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: How can GIF compression be lossless if the maximum # of colors is 256?
I'm reading "Computer Science Made Simple" by V. Anton Spraul, and in the chapter about Graphics, he describes GIF files as follows:

> A GIF file uses lossless compression to store an image with a maximum of 256 different colors.

The way I read this, it sounds like the book is saying it stores the image, but the stored image will have a maximum of 256 colors. If this interpretation is incorrect, and the author means that the GIF format only works with original images that have a max of 256 colors, then let me know since this makes my question redundant.

With that out of the way, let's assume the following scenario:

1) I have an arbitrary image with more than 256 colors.
2) I open the file in Photoshop or some other advanced image editor.
3) I save it as a GIF.

My question is, wouldn't this result in a loss of information, or artifacts in the new GIF? I'm capped at 256 colors when using the GIF format, and therefore would lose data, right?

# Answer
> 8 votes
GIF is only capable of storing images with at most 256 different colours. If you have such an image, the compression used by GIF is lossless. If you have an image with more than 256 different colours, you must first reduce the number of colours, which does indeed lose data but that's a preprocessing stage that isn't part of the compression process. Once you've preprocessed, the compression occurs without further loss.

You should parse the sentence quoted in the question as "If you have an image with at most 256 colours, GIF will compress it losslessly", rather than "If you have an image, GIF will losslessly produce a compressed version with at most 256 colours."

---
Tags: image-processing, data-compression
---


# Question
Title: Looking for a paper comparing NLP methods with Data Mining techniques
I've recently attended a conference, where one of the participants mentioned a recent paper published by a Google employee, which showed that using data mining techniques in application to NLP might sometimes give better results than using the NLP methods themselves.

That was the only description he gave and on top of that, he didn't remember author's name.

Is anyone familiar with such paper?

# Answer
> 3 votes
there are probably several papers which fit this criteria and this may not be enough info/ criteria to really narrow it down. however some general bkg: google has pioneered research into the use of statistical algorithms for NLP for years and particularly (somewhat more recently) machine auto language translation. in this research one has a large database (aka "big data") of "translated sentence pairs" between language A and language B and the machine learning algorithm attempts to learn the relationship between the two, and its considered something of a relatively recent paradigm shift in the field because previously it was not considered/ thought possible, but google has achieved very good and improving results in the area, and my understanding is that some of this is now used/ incorporated in their live/ production/ public "translate" feature/ "product" built into the main search engine results.

try this nice list of papers: Natural Language Processing listing most NLP papers/research at google by date. there are 8 papers with the word "statistical" in the title. the most recent paper from 2013 may be close to what is being identified or cite the nearby area your speaker was referring to. other papers are from 2012 or older.

---
Tags: data-mining, natural-language-processing
---


title: Finding a perfect matching using an LP

text:
# Question
Title: Finding a perfect matching using an LP
I have a basic question about the power of Linear Programming that has been bothering me for some time. I believe there is something simple I am missing.

Linear Programming is $\mathsf{P}$-complete, which means that every problem in $\mathsf{P}$ can be reduced to it using an $\mathsf{NC}$ reduction. (See the wiki for some nice background)

However, it has been shown that the perfect matching polytope has exponentially many facets (see this recent STOC paper for example. This shows it even has exponential extension complexity---i.e. even using extra dimensions we require an exponential number of inequalities).

However, the classic Blossom Algorithm can find a perfect matching in polynomial time--determining if a graph has a perfect matching is in $\mathsf{P}$.

This seems like a conflict to me: we can reduce the perfect matching problem to Linear Programming, but its polytope must be exponentially large. What am I mising? Is there processing during the reduction that avoids using the entire matching polytope?

# Answer
> 5 votes
The lower bounds on extended formulations (the one by Rothvoss for example) are lower bounds for a very specific way of using Linear Programming to solve a problem (matching in this case).

In this model, given a graph you would like to write **one** linear program, changing whose objective function gives you the right matching corresponding to any weight function on the given graph. This requirement results in the restriction that the feasible region of such an LP must project down to the matching polytope. The lower bound is not immediately applicable if you provide different LPs for different weights, or you use the objective function in a non-trivial way. (Note that in this model, we use the weights on the edges as the objective function without any modification)

Allowing different LPs for different weights obviously breaks the result: First solve the weighted problem and then produce a trivial LP whose feasible region contains exactly one point (the answer). This LP would trivially have small size.

Now, you can argue similarly that allowing weights to be manipulated arbitrarily allows you to "cheat" and write small LPs too.

The discussion about P-completeness of Linear Programming becomes interesting if you ask the following.

**Q:** Can you use Linear Programming to solve the matching problem in a "black box" fashion "with minimal extra computation"?

The answer in this case is yes, and the extra computation turns out to be just encoding the input graph in a trivial way as the objective function (by essentially taking the characteristic vector of edges with encoding digits +/-1 instead of 0/1). This extra computation seems reasonable and so the LP encoding of the matching problem in this case seems interesting. The LP in this case turns out to be of small size precisely because matching is in P and Linear Programming is P-complete.

---
Tags: reductions, polynomial-time, linear-programming, matching
---


title: How to compute max jump distance

text:
# Question
Title: How to compute max jump distance
I have a BNE-instruction (32 bits), which contains 16 bits for the jump field:

* Opcode A\[31:26\]
* RS A\[25:21\]
* RT A\[20:16\]
* Immed A\[15:0\]

Assuming the BNE-instruction will now be written in 64 bits format, what would be the (new) max jump distance this instruction can make?

I really have no clue, what to do, so I hope someone can help me. Thanks in advance.

# Answer
> 1 votes
Depending on the architecture, the immediate for branches may mean a byte address (x86) or a word address if fixed width instructions are mandated, which means that for a 16bits offset, the range is something like -2^17 to +2^17-1

Having fixed 64bits-wide instructions is quite rare (VLIW domain). If you add 32 bits, and if you keep the same number of registers (hence 5 bits for RS and RT) and the opcode part, I guess these extra bits would end in the offset part, so 16+32bits offset. If instructions are fixed width, you may then have doubleword offsets : -2^-50 to +2^50-1

Practically, it does not make any sense to have such wide immediate offsets. No program is large enough to be several gigabyte long (I'm not counting libraries, which are generally called through indirect or direct branches over the full 32bits or 64bits address range, not conditional branches).

I could imagine that with 64bits instructions, some variants of the conditional branch instructions would offer 16 to 32bits immediate values, like : "BNE R1,#1234, @Somewhere" instead of using 48bits for the offset.

---
Tags: computer-architecture
---


# Question
Title: What is the relation between arithmetic circuits and straight line programs?
One definition of *arithmetic circuits* is as follows:

> An arithmetic circuit $\Phi$ over the field $\mathbb F$ and the set of variables $X$ usually, $X = \\{x\_1, \dots , x\_n\\}$) is a directed acyclic graph as follows. The vertices of $\Phi$ are called gates. Every gate in $\Phi$ of in-degree $0$ is labeled by either a variable from $X$ or a field element from $\mathbb F$. Every other gate in $\Phi$ is labeled by either $\times$ or $+$ and has in-degree $2$.

A straight-line program seems to be a succession of basic operations without any if or while statement. So it seems to be a term from the associated free algebra expressed suitably "compressed" as an acyclic graph. But a (reference to a) nice definition of *straight-line programs* would already help me a bit with respect to this question.

What I really want to know is whether an arithmetic circuit is a special case of a straight-line program? If yes, then why is arithmetic circuit complexity considered so important, while even finding a reference for a proper definition of *straight-line programs* seems to be quite challenging? (I found a definition in The Extraordinary Power of Division in Straight Line Programs, but this is a paper from 2012, and the notion itself seems to be much older.)

# Answer
Straight-line programs and arithmetic circuits are two equivalent ways of describing the same computational model. A straight-line program typically has the following instructions:

1. Reading the input: $t\_i \gets x\_j$.
2. Initialization by constants: $t\_i \gets r$ for all $r$ in the ambient field.
3. Addition, subtraction, multiplication, division: $t\_t \gets t\_j \pm t\_k$ and so on.
4. Output: $o\_i \gets t\_j$.

The input and output instructions aren't really necessary. The inputs are $x\_1,\ldots,x\_n$ and the outputs are $o\_1,\ldots,o\_m$.

Exercise: show that (multiple-output) arithmetic circuits and straight-line programs are equivalent: they compute the same functions with the same size complexity (if you define size in the correct way, and allow the same sets of gates and lines).
> 5 votes

---
Tags: complexity-theory, circuits
---


title: Pushdown Automata: CFG to PDA

text:
# Question
Title: Pushdown Automata: CFG to PDA
I have the following grammar for a context-free language:

$G = (\\{S,A,B\\}, \\{x,y,z\\}, P, S)$ with $P = \\{S \rightarrow A, A \rightarrow xAz, A \rightarrow xBz, B \rightarrow y\\}$

My question is: **How to construct a pushdown automaton associated with the above grammar?**

# Answer
> 2 votes
The language $L$ accepted by the CFG can be written of the form,

$$ L = \\{x^nyz^n | n \gt 0\\}$$

You can verify this, by looking at members of $L$

Now there are various definitions of $PDA$ (accept by final state, accept by empty stack), the most simple definition that is suitable for this problem is to user a $PDA$ that accepts through empty stack.

Now the intuitive idea is to push all $x$'s on to the stack, and when you read a $y$, pop the $x$'s in the stack for every $z$ you read afterwards. (So this can be quite easily achieved by a deterministic $PDA$. Verify.)

The transition table $T$ for a $PDA$, with states $Q = \\{q\_0, q\_1,q\_2,q\_3\\}$ and stack symbols $\\{X,\\$ \\}$ is:

$$ \delta (q\_0,$,x) = (q\_1,$X) $$ $$ \delta (q\_1,\epsilon,x) = (q\_1,X) $$ $$ \delta (q\_1,\epsilon,y) = (q\_2,\epsilon) $$ $$ \delta (q\_2,X,z) = (q\_2,\epsilon) $$ $$ \delta (q\_2,$,\epsilon) = (q\_3,\epsilon) $$

The automaton transitions to state $q\_3$ once an equal number of $x$'s and $z$'s are read

**NOTE**: My first answer. Kindly bear with errors (technical or LaTex related)

# Answer
> 1 votes
Keep pushing every x you read. When a y is read, then start reading z's. For every z you read pop an x. If the letter read is lamda and the letter popped is also lambda, go to accept state, otherwise if letter read is lambda and letter popped is not lambda or vice versa go to reject state.

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


title: Books about old Operating systems

text:
# Question
Title: Books about old Operating systems
where can i find very old books about old operating systems like CP/M and DOS and other OS that worked on the 8086 ??

second question isn't old books 20 year before and older should have an expired patent ?? where in general can i find books of expired patents ...

thanx

# Answer
it's perfectly possible to buy one on amazon: http://www.amazon.co.uk/CP-M-Handbook-Rodnay-Zaks/dp/0895880482/ref=sr\_1\_1?s=books&ie=UTF8&qid=1420360499&sr=1-1&keywords=cp%2Fm
> 2 votes

# Answer
PC Magazine Programmers Technical Reference: The Processor and Coprocessor by Rob Hummel and Microcomputer Architecture and Programming by John F. Wakerly are older books which go into detail about the 6800 family of cpus and their design. The PC Magazine one is more of a reference book though.

These books detail the CPU design and operand calls in machine code that the OS uses to control the computer. This would describe the underlying functionality of a computer, as an OS has many parts (even an old one) there is more than one topic or theory at play to allow an OS to exist.
> 2 votes

---
Tags: operating-systems, books
---


# Question
Title: Why is Computer Architecture in $2^n$ bits?
I have always wondered why is computer architecture in $2^n$ bits. We have **8 / 16 / 32 / 64-bit** microprocessors or for that matter other parts of computer are also in power of 2 bits.

The only logic I could understand from my reasoning is that usually computer design process starts from *lower* amount of bits. **For example :** Say I want to design a *Full adder* to add `16 bit` numbers. So I would first design a digital circuit to add `2 bits` (one from number A and other form number B). Then I would replicate this circuit `16 times`. So this will give me `16-bit` full adder.

Is my reasoning correct ? Is there some other reason also ?

# Answer
> 2 votes
Not necessarily, for instance, look at the memory bus width in modern day GPUs, they would have values of 192, 384, 768(while 128, 256.... are common).

One could argue that 192 is a sum of powers of 2 (2^7+2^6), sure, but what number isn't?

That being said, any memory modules directly associated with a microprocessor or a microcontroller will have capacities in powers of 2. Traditionally registers will be 8,16, 32 or 64 bits long (though 10-bit and other non conventional widths exist).

A processor (or controller) with an n-bit register can address upto 2^n addresses (i.e, 0-(2^n)-1 bytes). Hence without changing the processor, one can extend the memory associated with it although exceeding the addressing space beyond what the processor can manage will be redundant.

In many DSPs, the memory associated with the processor is in 2^n multiples as many of the signal processing algorithms can be made very efficient when calculating this way.

# Answer
> -1 votes
Some say that the IBM STRETCH (1961) introduced 8bits bytes :

http://en.wikipedia.org/wiki/IBM\_7030\_Stretch

Until the late 70s, computers used other sizes and multiples, for example 36bits = 8 characters of 6 bits. Early computers used only uppercase letters and numbers, using 6bits per character was more efficient.

Anyway, ask wikipedia : http://en.wikipedia.org/wiki/12-bit, http://en.wikipedia.org/wiki/18-bit...

There can be several explanations for the fact that all modern computers use 8bits bytes and multiples thereof. All monolithic microprocessors used that (8080, 6502...), 7 or 8bits ASCII was necessary for making text in uppercase and lowercase with internationalisation. Using powers of two all the way down must be appealing for computer designers...

---
Tags: computer-architecture, digital-circuits
---


# Question
Title: What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$
I am struggling to think of the context-free grammar that generates the language $L(G) = \\{a^ib^jc^{2i}d^m\\}$, where $i$, $j$ and $m$ are natural numbers.

Also, in general, are there any good methods or ways of thinking that help one to think of context free grammars that generate a given language. Any tips are much appreciated, thanks.

EDIT: I've tried S →ABCD, A →aA | λ, B →bB | λ, C →ccC | λ, D →dD | λ

However, this doesn't allow for always generating twice the amount of c's as there are a's.

# Answer
> 1 votes
For matching number of a and c you need to do something like this:

$$ S \rightarrow AB \\ A \rightarrow aAcc \\ A \rightarrow C \\ C \rightarrow bC | λ \\ B \rightarrow dB | λ $$

You need to produce them in one rule to be sure the ratio is kept.

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


# Question
Title: What does $\Sigma^0_2$-hard and $\Pi^0_2$-hard for a TM's Acceptance Problem mean?
I'm reading about a Turing Machine $M$ and it says the problem of deciding whether M accepts a string is "$\Sigma^0\_2$-hard and $\Pi^0\_2$-hard".

I haven't seen this kind of notation before and haven't found a good answer from searching. Is this a more specific form of saying NP-hard?

# Answer
No, it's unrelated to **NP**-hardness. $\Sigma\_n^0$ and $\Pi\_n^0$ are the levels of the arithmetical hierarchy. $\Sigma\_2^0$ is the class of problems that can be decide by Turing machines that have an oracle for the halting problem and $\Pi\_2^0$ is the class of problems whose complement is in $\Sigma\_2^0$.

There is the corresponding notion of the polynomial hierarchy, in which $\Sigma\_1^\mathrm{P}$ is **NP** and $\Pi\_1^\mathrm{P}$ is **co-NP**.
> 4 votes

---
Tags: turing-machines, np-complete, np-hard
---


# Question
Title: Sums of all pairs: possible less than quadratic?
Is there an algorithm to prepare all sums of pairs of a list ($L$, size $n$, max value $m$) in $\< O(n^2)$ such that query "*does this sum of pairs exist*" takes $\< O(n)$? In other words, can max value $m$ be used to advantage?

E.g. in $L =\\{1, 2, 4, 8\\}$ and $m = 8$, all (distinct) sums of pairs are $S = \\{2, 3, 4, 5, 6, 8, 9, 10, 12, 16\\}$ (not given, calculate).

This may be possible using a divide-and-conquer on both $L$ and on the bits of each item. (N.B. the constraint keeps $S.size$ to $2m$, no need for size $O(n^2)$)

# Answer
> 7 votes
Yes, it is possible using $O(n \log n)$ preprocessing and $O(\log n)$ query time.

Given the set $S$, construct the polynomial $P(x)=\Sigma\_{s\in S}\textrm{ } x^s$. Then use the FFT multiplication algorithm to compute $P^2(x)=P(x)\*P(x)$ in $O(n \log n)$.

A value $q$ s a sum-of-pairs of $S$ if and only if the coefficient of $x^q$ in $P^2(x)$ is non-zero. Use binary search to look up the coefficient in $O(\log n)$ time ($P^2(x)$ is a polynomial of degree $2m$).

There are also less complicated (and less efficient, but still better than $O(n^2)$) multiplication algorithms that use divide-and-conquer such as Karatsuba multiplication ($O(n^{1.585})$ preprocessing).

# Answer
> 2 votes
The value $m$ can be used to advantage by simply sorting the list, and applying whatever $O(n)$ algorithm you had in mind on the list pruned to exclude items greater than the requested sum (which is $\< 2m$). You get $O(m + log(n))$ complexity then.

---
Tags: divide-and-conquer
---


title: Temporal compression protocol

text:
# Question
Title: Temporal compression protocol
Recently it occurred to me that one could potentially design an interactive "compression" scheme which seems to allow for arbitrarily high compression ratios, at the sole expense of time. This already sounds pretty cranky, I realize that, but here is a formal description of the protocol which I hope makes sense:

> Define a *data store* as a tuple $(\mathcal{O}, n, \delta)$ with $\mathcal{O} : \mathbb{N} \to \\{ 0, 1\\}^n$ a random oracle. We say that the data store "contains" the value $x$ at a (real) time $t \geq 0$ if $\mathcal{O}(\lfloor t \delta^{-1} \rfloor) = x$, such that the contents of the data store randomly change every $\delta$ units of time. A data store could be realized in software using the current time in some agreed-upon representation and any cryptographic hash function.
>
> Alice wants to sends a message to Bob encoded as a bit string as part of an interactive protocol (Alice and Bob are both present and active during the transmission). First they both agree on a suitable $\delta$ such that they can both resolve the current time to within $\delta$ units of time. Then, Alice chooses an integer $n \geq 2$, instantiates a data store $(\mathcal{O}, n, \delta)$, and sends these parameters to Bob, and then breaks up the message into $n$-bit blocks. For each block, Alice then *monitors* the data store *until its contents equal the block*, at which point Alice sends a single bit "1" to Bob. When Bob receives this signal, he looks up the contents of the data store and retrieves the corresponding $n$-bit block (possibly rewinding as needed to account for any transmission delay, this is feasible as long as the transmission delay is fairly constant and known to within $\delta$ units of time). When the last block is sent, Alice sends the bit "0", Bob computes a checksum of the message and sends it to Alice for verification.
>
> If the message contained $m$ $n$-bit blocks, the total amount of data actually sent (outside of protocol overhead) was $m$ bits, achieving a compression ratio of $1 - 1/n$, and it would take an expected $m \delta 2^{n}$ time to successfully send it (that is, $\delta 2^{n} / n$ time per bit). Also note that since this scheme doesn't actually use any structure in the message, it can be given *already compressed data* to compound any already attained compression ratios: the two are not mutually exclusive.
>
> Clearly this doesn't allow for amazingly high transmission rates in general. A realistic usecase could be communication with a space probe, where the light-time transmission delay may be accurately computed allowing for a very low $\delta$, say, $\delta = 10 ~ \text{ns}$. Then we can achieve decent compression ratio/transmission rate tradeoffs, e.g. 94% at 3 KB/s ($n = 16$) or 90% at 122 KB/s ($n = 10$).
>
> It gets exponentially more time-consuming to send data as $n$ increases, so 95% compression ratio is probably about the best one can practically achieve in reasonable time in the general case.

Obviously this only works as an interactive protocol, not as an offline protocol. Also, it doesn't really work "as-is" in real life because you can't just send 1 bit on most channels, as each communication entails a nontrivial amount of overhead (TCP/IP packet, etc..) but in principle I don't see why it couldn't work.

So, does anyone know if this kind of "temporal communication" has been studied before, and can point out any fundamental or practical problems or errors I overlooked that might explain why it isn't used?

# Answer
> 2 votes
There are two flaws in your idea.

First, compression ratio is not the right metric. The right metric for evaluating your scheme is the transmission rate: how long does it take to send a $n$-bit message? The answer is that your scheme fares very poorly under that metric: it takes $\Theta(2^n)$ units of time to send a $n$-bit message. Therefore, your scheme has very poor performance, both theoretically and practically.

Transmission rate is the right metric for a scheme that sends data over a communication channel. Compression ratio would be suitable for a compression scheme of the form $C:\\{0,1\\}^n \to \\{0,1\\}^\*$, but crucially, this requires that the output of the compression scheme can be expressed in bits. Your protocol doesn't have that property: the output is actually trits.

This leads me to the second flaw in your idea. Your protocol requires a communication channel that has three states (i.e., can convey one of three symbols at any point in time): "1", "0", or "I have nothing to send right now". In other words, you need a communication channel that can send trits (0, 1, or 2), not just bits (0 or 1). But if we had a communication channel like that, we could already achieve higher transmission rate than your scheme. So, you're not comparing to the right baseline.

For these reasons, your scheme does not beat any information-theoretic bound and does not contradict any theoretical barrier. It also probably won't be effective or useful in practice.

---
Tags: data-compression, communication-protocols
---


# Question
Title: To detect isomorphic graphs Is it enough to check if they have the same number of same degree vertices?
Given two lists of non directional graph edges e.g. \[(1,3),(3,5),(5,1),(5,7)\] \[(4,5),(2,3),(3,4),(4,2)\] In order to check if the two graphs are isomorphic is it enough to count the vertices with the same degree between them?

```
e.g. Vertice   1: 2    1: 0
               2: 0    2: 2
               3: 2    3: 2
             4,6: 0    4: 3
               5: 3    5: 1
               7: 1    6,7: 0

```

So in our example: both graphs have 2 vertices with 2 edges 1 with 3, one with one and 3 with 0

# Answer
> 5 votes
No. If two graphs have different degree sequences, they are definitely not isomorphic, so the algorithm "half-works". But consider a six cycle versus two three-cycles. Both graphs have six vertices, all of degree two; they are not isomorphic. Indeed, this counterexample shows that nothing based solely on degrees can work.

---
Tags: graphs
---


# Question
Title: Reductions where the number of certificates from one problem can be computed for another to varying degrees
Let $A$ and $B$ be two decision problems in $NP$. Consider three cases:

(1) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having exactly the same number of solutions as $A$.

(2) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having a fixed number of solutions for every solution of problem $A$. We can, in polynomial time, calculate the number of solutions for $A$ provided an oracle that gives the number of solutions to $B$, and vice versa. What if we can guarantee that the number of solutions for an instance of $A$ will be greater than the number of solutions for the corresponding instance of $B$ or vice versa?

(3) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having a solution if and only if $A$ has a solution. However, we do not have a polynomial time algorithm to compute the number of solutions for $A$ provided some number of solutions for $B$. We also cannot guarantee that such a polynomial time algorithm does not exist.

What formal names and notation for the above sort of reductions? When is a Levin reduction called parsimonious? Instances one and two only? Is the third example necessarily worth anything?

# Answer
1. Parsimonious reduction.
2. Polynomial-time Turing reduction (a.k.a. Cook reduction).
3. Polynomial-time many-one reduction (a.k.a. Karp reduction).

I've not come across cardinality restrictions of the form you mention in (2) so I don't know any name for them. If you find there isn't a name already, "monotone" would be a good one to choose. In the case where the number of solutions to $B$ is less than $A$, you need "less than or equal to" since, if $A$ has exactly one solution, you still need to reduct it to a "yes" instance of $B$.
> 0 votes

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


# Question
Title: Relations among different boolean approximations
Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$).

Let $p$ be the minimum degree (of degree $d\_f$) real polynomial that represents boolean function $f$ such that $f(x)=p(x)$.

Let $p\_{0,\epsilon}$ be the minimum degree (of degree $d\_{0,f,\epsilon}$) real polynomial that represents boolean function $f$ such that $$f(x)=0\implies p\_{0,\epsilon}(x)=0$$$$f(x)=1\implies|p\_{0,\epsilon}(x)-f(x)|\leq\epsilon.$$

Let $p\_{1,\epsilon}$ be the minimum degree (of degree $d\_{1,f,\epsilon}$) real polynomial that represents boolean function $f$ such that $$f(x)=1\implies p\_{1,\epsilon}(x)=1$$$$f(x)=0\implies|p\_{1,\epsilon}(x)-f(x)|\leq\epsilon.$$

Is $d\_{f}\leq d\_{0,f,\epsilon}^{c\_0}$ and $d\_{f}\leq d\_{1,f,\epsilon}^{c\_1}$ for some $c\_0$ and $c\_1$?

Above holds if $\epsilon\in(0,\frac{1}{2})$ as mentioned here in link Different boolean degrees polynomially related?.

However what happens if $\epsilon\in(0,1)$ instead of $(0,\frac{1}{2})$ (does polynomial relation still hold)?

That is we consider $0\<\epsilon\<\frac{1}{2}\leq\delta\<1$.

Note that defining $p\_\delta$ makes little sense if $\delta\in\[\frac{1}{2},1)$.

I am most interested in $\delta=1-\frac{1}{h(n)}$ with some function of $n$ (logarithmic/polynomial/exponential).

# Answer
The new parameters are polynomially related to the old parameters. In fact, for every $0\<\delta,\epsilon\<1$ it is the case that $d\_{0,f,\epsilon} = \Theta\_{\delta,\epsilon}(d\_{0,f,\delta})$. This is proved in the same way that the usual relation regarding $d\_{f,\epsilon}$ is proved, as detailed below.

Suppose we are given $0\<\delta,\epsilon\<1$. Let $g$ be some continuous function satisfying $g(0) = 0$ and $g(x) = 1$ for $1-\delta \leq x \leq 1+\delta$. The Weierstrass approximation theorem shows that there is some polynomial $G$ such that $|G(0)| \leq \epsilon/2$ and $|G(x)-1| \leq \epsilon/2$ for all $1-\delta \leq x \leq 1+\delta$. Let $G\_0(x) = G(x) - G(0)$, so that $G\_0(0) = 0$ and $|G\_0(x)-1| \leq \epsilon$ for all $1-\delta \leq x \leq 1+\delta$. The polynomial $P = G\_0(p\_{0,\delta})$ has degree $(\deg G\_0)d\_{0,f,\delta}$ and satisfies $P(x) = 0$ whenever $f(x) = 0$, and $|P(x)-1| \leq \epsilon$ whenever $f(x) = 1$. This shows that $d\_{0,f,\epsilon} \leq (\deg G\_0) d\_{0,f,\delta}$. Since $G\_0$ only depends on $\delta,\epsilon$, this proves that $d\_{0,f,\epsilon} = O\_{\delta,\epsilon}(d\_{0,f,\delta})$.
> 1 votes

---
Tags: complexity-theory, polynomials
---


# Question
Title: What sort of theoretical machine would be needed to solve the tiling problem?
So theoretically, what sort of machine would we need to solve the *tiling problem?*

(Given a set of tiles, decide if they will tile the plane or not.)

I know we could have a Turing machine plus a "tiling oracle", but do we know what, specifically a Turing machine *isn't* able to do that keeps us from being able to compute the answer?

# Answer
> 2 votes
According to Wikipedia, the halting problem reduces to the tiling problem. This means that one thing that prevents Turing machines from solving the tiling problem is their inability of deciding whether a given procedure ever halts. The tiling problem might be even more difficult that the halting problem, but unfortunately I wasn't able to confirm or disprove this.

---
Tags: computability
---


# Question
Title: Is a Karp–Levin reduction a Levin reduction?
My understanding is that Karp many-one reductions are more general than Levin many-one reductions, and that Levin many-one reductions must allow for the number of certificates for a problem $A$ reduced to $B$ to be recovered from a single oracle call giving the number of certificates for $B$.

So, what exactly is a Karp–Levin reduction? Quoting the paper "Witness Encryption and its Applications",

> We now formally describe our encryption systems. For building them we will assume the existence of a witness encryption scheme for an NP-Complete language $L$ for which there exists a Karp–Levin reduction. We focus on presenting the constructions in this section and defer the proofs to Appendix A.

Other instances of "Karp–Levin" reductions can easily be found elsewhere.

From slide 11 of this presentation on PCPs by Mario Szegedy, it seems like a Karp–Levin many-one reduction is just a Levin many-one reduction. Is that correct?

*Update*: To explain why I am uncertain about Yuval Filmus' answer below, and why I'm asking this question, quoting from page 17-4 of the "Hardness of Approximation" chapter of the *Handbook of Approximation Algorithms and Metaheuristics*, a chapter written by Mario Szegedy (a Godel prize winner for his contributions to the PCP theorem),

> Reduction is perhaps the most useful concept in algorithm design. Interesting, it also turns out to be the most useful tool in proving computational hardness \[21-23\]. When a problem $A$ Cook reduces to $B$, the hardness of $B$ follows form the hardness of $A$. Unfortunately, Cook reduction does not ensure that if $A$ is hard to approximate then $B$ is hard to approximate. For reducing hardness of approximation new definitions are necessary.
>
> Let $F\_1(x, y)$ and $F\_2(x', y')$ be functions that are optimized for y and y' (maximized or minimized in an arbitrary combination). Let $OPT\_1(x)$ and $OPT\_2(x')$ be the corresponding optimums. A Karp–Levin reduction involves two maps:
>
> 1. a polynomial-time map $f$ to transform instances $x$ of $OPT\_1$ into instances $x' = f(x)$ of $OPT\_2$ \[Instance Transformation\];
> 2. a polynomial-time map $g$ to transform (input, witness) pairs $(x', y')$ of $OPT\_2$ into witnesses $y$ of $OPT\_1$ \[Witness Transformation\];
>
> Observe that the witness transformation goes from $OPT\_2$ to $OPT\_1$. Let $opt\_1 = OPT\_1(x)$, $opt\_2 = OPT\_2(f(x))$, $appr\_1 = F\_1(x, g(f(x),y'))$, and $appr\_2 = F\_2(f(x),y')$.

So Yuval Filmus' answer below appears to only cover the "\[Instance Transformation\]" part of a Karp–Levin reduction, and not the "\[Witness Transformation\]" part, which seems to be interpretable as a way to recover certificates from some problem $A$ in $NP$ reduced to $B$ in $NP$ provided the number of certificates for $B$.

Am I off the mark here? And how is a Karp–Levin reduction different from a Levin reduction?

If there is non-standard terminology, or if definitions are supposed to be "understood" depending on whether one is talking about reductions among perhaps counting problems where witness transformations matter, please understand that this is intimidating for someone coming from outside of computer science! People's patience here is very much appreciated.

# Answer
> 1 votes
A Karp reduction from a language $A$ to a language $B$ is a function $f$ such that $x \in A$ iff $f(x) \in B$. This is the common meaning of the term.

David Richerby mentions in a comment below that Levin reductions are a more elaborate type of reductions: see this question.

In the present instance, Karp–Levin reduction seems to mean the same as Levin reduction. Indeed, since the common term for the usual notion of many-one reduction is Karp reduction, adding Levin's name might signify something different. The way the term is used in the paper should make it clear which meaning is being used. The paper might also include a definition of this somewhat non-standard term, and I suggest you include such a definition in future papers you may write.

---
Tags: complexity-theory, terminology
---