# Question
Title: Superscalar processors and complex instructions
I read that a supercalar processor has redundant functional units. One can read this e.g. on Wikipedia.

How do such redundant units work?

Is a complex instruction (for accelerating heavy process, for example Instructions used in Intel IPP, Integrated Performance Primitives) decomposed in micro operations befaure being dispatched among these redudant functional units?

What about hardware instructions? Like AES-NI?

I also read the Wikipedia article SMT and did not understand the following sentence:

> Superscalar means executing multiple instructions at the same time while thread-level parallelism (TLP) executes instructions from multiple threads within one processor chip at the same time.

I don't understand very well the distinction between these two things. Can somebody explain the subtleties?

# Answer
You should understand that any program is a sequence of instructions (ok, you an think of it as a collection of threads, where every thread is a sequence of instructions or a virtual process that executes that series of instructions). The instructions are supposed to be executed one after another. Single pipeline processor fetches instruction as they are ought to, every clock cycle and keeps its functional unit executing an instruction per cycle. This is not very true actually because execution takes multiple cycles and you fetch next instruction before previous is complete. But we pretend that instructions are still executed one after another and you still need one FU. Superscalars, however, cheat. They tell to the user that they still execute her program as designed, one instruction after another, yet take a window of neighbor instructions and execute them at once. They introduce extra FUs (Wikipedia called them "redundant") for this technique, called "Instruction Level Parallelism" (ILP).

Superscalars also have to entail a complex dependency detection and maintenance mechanism. As Amdahl has explained), because instructions of the same thread operate on the same data set, you have a lot of dependencies, especially among neighbor instructions and, thus cannot gain a lot of parallelism at ILP. The parallel pipelines are therefore sometimes used to execute different threads. This is full-scale parallelism already (except the synchronization cases and cache contention, which prevents any advantage of TLP over ILP, especially if von Neumann bottleneck is considered). Such TLP is known as *hyperthreading*. Yet, it is true parallelism since now threads are indeed executed in parallel, as if there are multiple cores, rather than parallelism is emulated by periodically switching threads on a single pipeline and, therefore, is also called "simultaneous multithreading".

I do not even see any reason to differentiate between multicore and hyperthreading. Since different pipelines execute different threads, this means that they have separate instruction pointer, set of registers and everything you need for the context, which are switched. Might be the common cache and shared FUs is the only things that distinguishes single core from multiple cores. Yes, shared cache. This may save you from cache incoherence /memory consistence problems that can happen in truly multicore system.
> 2 votes

---
Tags: computer-architecture, parallel-computing, concurrency
---


title: Find missing value in period of LCG

text:
# Question
Title: Find missing value in period of LCG
It's well known that linear congruential generators have a full period only if a few properties are fulfilled.

Now I need a LCG that does *not* generate a full period in 2^32 (easy to find, just violate one requirement) and I need one of those values in the period that's not used.

Is there any clever math trick/algorithm to find such a thing? I can see the obvious bruteforce solution, but that'd take quite some time and tons of memory - also it seems like an interesting math problem. I did check Knuth but he obviously focuses on showing how to get a full period.

PS: For people wondering - I have to trick a compiler into making sure it can't use DCE on some values and this seems like a very performant and hard to figure out way to achieve this.

# Answer
> 6 votes
Actually, bruteforce should work just fine. You can quickly find a set of taps that doesn't have a full period, then find a value that's not in the period. Here's what I'd do:

1. Randomly pick a set of taps (a feedback polynomial).
2. Verify whether this has a single full period of size $2^{32}-1$, as follows. Randomly pick a starting state $s\_0$ (not the all-zeros state). Iterate forward starting from $s\_0$, and see whether you get back to $s\_0$ within at most $2^{32}-1$ steps. In this way, you can compute the period after starting from $s\_0$. If this period is $2^{32}-1$, go back to step 1.
3. Now you have a LFSR and a starting state $s\_0$, such that the full period is less than $2^{32}-1$; next you want to find a state $t$ that is not within the set of states reachable from $s\_0$. Here's one way to do that:

* Randomly pick 10 states $t\_1,t\_2,\dots,t\_{10}$. These will be your 10 candidates for $t$. Initially, each of them is unmarked.
    * Now run the LFSR forward, starting from $s\_0$, until you get back to $s\_0$. At each step compare the current state of the LFSR to $t\_1,t\_2,\dots,t\_{10}$. If the current state of the LFSR is equal to $t\_i$, then mark $t\_i$.
    * At the end, when you get back to $s\_0$, look at which of the $t\_i$ are marked. If one of the $t$'s is unmarked, say $t\_j$, then you are done: you have a LFSR feedback polynomial and a starting state $s\_0$ such that you know $t\_j$ is not within the period of values starting from $s\_0$. If all of the $t\_i$'s are marked, go back to step 1.

How long will this take? Probably about $2^{32}$ operations. I would expect at least $1/2$ of the choices of feedback polynomials to lead to a LFSR with less than full period, so you shouldn't have to repeat steps 1-2 too many times (on average about 2 times). Each repetition takes $2^{32}$ operations.

Now once you find a good LFSR, where $s\_0$ does not lead to a full period, then the period that's reachable from $s\_0$ will be on average about $2^{31}$ or smaller. Thus, step 3 will take about $2^{31}$ operations. Also, this means that about $1/2$ of all possible states will be unreachable. Therefore, with probability $1-1/2^{10}$, at least one of your 10 candidates for the $t$'s will be good, so the chances that you have to repeat step 3 is very low.

So, this is probably good enough. This is easy to code up and will probably finish within a few hours or less.

---

There *are* cleverer things you can do, but they probably don't make sense in practice. You could spend a bunch of hours thinking hard to write tricky code, to save an hour or two of CPU time -- that's not a good tradeoff.

Nonetheless, since it sounds like you appreciate the math and clever tricks, here are the tricks you could use to make this more efficient. Let $p(x)$ be the feedback polynomial for your LFSR. If $p(x)$ is reducible, then the LFSR will certainly not be full period. In other words, if $p(x)$ factors as $p(x)=q(x) r(x)$, the LFSR won't be full period. So, you could start by picking two polynomials $q(x),r(x)$ randomly of suitable degree (their degrees must sum to 32, and neither should be a constant), then use their product as the feedback polynomial.

Now once you have a feedback polynomial, there are efficient algorithms to check whether a state $t$ is reachable from starting state $s\_0$. This basically becomes a discrete logarithm problem in $GF(2^{32})$, which can be solved very efficiently. See, e.g., https://crypto.stackexchange.com/q/17970/351. That said, you wouldn't want to implement those algorithms for this problem. They are overkill, and much harder to implement than the simple bruteforce approach I outlined above.

If you want to make the problem easier, you could use a maximally factored feedback polynomial, such as $p(x)=(x+1)^{32} = x^{32} + 1$. Now the all-ones state has a period of 1, i.e., it repeats forever. So, you can take $s\_0=111\cdots 1$ and $t$ to be anything else. This is a bit of a trivial example, so it might not be what you are looking for.

---
Tags: algorithms, pseudo-random-generators
---


# Question
Title: Learning, understanding and using algorithms
I am a 2nd year computer science student. We all have subjects about Data Structures, Theories, more more theories we all know that i have a subject this semester Design Analysis of Algorithms.

So my question is. How do you guys understand well all the Algorithms? Any technique?

To snap out the confusion about my question, I just want to know your techniques in learning algorithms. We all know that Algorithms is very important aside from the Programming stuffs and some students find it hard to understand and considered me sometimes ..... I don't have problems in Programming subjects (not boasting) but I excel in Programming and I'm very interested to dive deep in learning more about Algorithms. Some people don't think that Data Structures and Design Analysis of Algorithms an important subjects. But i do really think that learning more about Algorithms is a very efficient way in learning in programming too. So any answers will be highly appreciated!

# Answer
There is a 35 years old result in Logic (the Curry-Howard correspondance) that states (simplifying a bit) that algorithms are like (isomophic to) proofs. If you take the *specification* of a program/algorithm such as, `Given a sequence of integer, give a sorted sequence of the same integers in ascending order`. This may be read as the statement of a *theorem* `For any sequence of integer, there is a sequence that contains the same integers in ascending order`. And any algorithm meeting the specification will actually correspond to a proof of the theorem.

Most professionnals will never be asked to use this correspondence (at least in the current state of the technology), but it does provide some understanding of the programming process.

What this indicates is that to understand algorithms, you have to inscribe them in a structured body of systematic knowledge, as much as possible, as you would do for mathematics. And mathematics does also play a role. What matters is understanding the structural underpinnings of the type of entities you are dealing with, so that you have an organized vision of what can or cannot be done, when and how. Note that some algorithms use other algorithms as components, exactly as some theorems are used to prove others.

Or to put it another way, you can work programming and algorithmic design exactly the same way you work on a mathematical problem. In mathematics, you learn a collection of definitions and of theorems that involve these definitions. Given a problem, you try to identify structures or entities that meet the definitions you know, for both hypothesis and conclusion, and you try to apply the theorems to get a proof.

When given a programming problem, you do exactly the same: you try to identify data structures or abstract types and programming structures that would adequately represent the entities you are supposed to deal with, and then you try to compose various algorithms (theorems) to actually get the work done.

In mathematics, what matters in some cases is the proof technique rather than, or as much as, the result. You sometimes have to reuse the same proof technique in a different context. The same goes for algorithms. If you understand how they are designed, you can use a similar design for other algorithms, in situations where known one do not exactly apply. So it is not just knowing algorithms that matters, but much more understanding them, understanding what makes them tick the right way. And that is not always easy. Some research improvements in algorithms result precisely from trying to understand the deep reasons that make some of them work the way they do. And this often involve understanding mathematical structures.

More generally, understanding a mathematical theory is **not** rote learning of a collection of definitions and theorems (though it sometimes help for specific very technical aspects). It is getting an overall, structural mental picture of the various aspects of the theory and the ways they interact. The same goes for algorithms. For example you may want to study and understand in a global way how one can deal with graphs. The various algorithms may have relations. Then, given a problem, you may recognize that part of it may be seen as a graph problem, and deal with it accordingly.

This said, the world may be a somewhat simpler place for most programmers. But the more you understand, the better you do.

I would like to point out that this is not the only facet of programming. Of course, a good program must use good algorithmics. But it often is not enough. Style and architecture matter. Your program must be easy to understand and maintain. From a mathematics point of view, this may correspond to what is called an elegant proof. The choice of the programming language may matter, as the choice of the right notations may matter in mathematics. But that is a bit beyond your question.

I am sure there is a lot more to say.
> 1 votes

---
Tags: algorithms, data-structures, intuition
---


# Question
Title: Can not understand idea of the KMP algorithm
I am using Sedgewick's Algorithms (4th ed) to learn Knuth-Morris-Pratt substring search algorithm. The key step is construct the DFA array corresponding to a given pattern. The authors say:

> The key observation is that the characters in the text that would need to be rescanned are precisely `pat.charAt(1)` through `pat.charAt(j-1)`: we drop the first character to shift right one position and the last character because of the mismatch.

I can't understand the above, for example. If the pattern is **ABABAC**, and the text string is **ABACABABACA**. and there are two pointers i and j for text string and pattern respectively.

If $i=3$, the character $c$ in the text string is mismatch, where the pattern is $b$. then we need to rescan from the beginning of the pattern. not the second character : `pat.charAt(1)` .

I think I am misunderstanding what the author intended to express. What does the author mean?

# Answer
Sedgewick continues: "*These are pattern characters that we know, so we can ﬁgure out ahead of time, for each possible mismatch position, the state where we need to restart the DFA.*"

What I understand is that this quote tries to explain that if you encounter a mismatch at letter at position $j$ of the pattern you have to shift the patterns by one position against the text and see where that leads us. The point there is that we do not need to know the actual text at that moment, because we know that so far the patterns has matched the text and we can match the pattern to itself (shifted).
> 4 votes

---
Tags: algorithms, strings, substrings
---


# Question
Title: A "triangular" data structure for commutative relationships
A multiplication table is symmetric over a diagonal, so only about $n^2/2$ of the elements in an $n \times n$ multiplication table contain unique information. Same goes for addition tables. In fact, the same is true for any table that represents a commutative relationship. Is there a data structure that can take advantage of commutativity to avoid storing redundant values?

# Answer
Some languages, such as C, support *ragged arrays*: two-dimensional arrays where the rows have different lengths. That lets you avoid the redundancy of representing a symmetric function in a square array.
> 8 votes

# Answer
Sure, you can put all information (of half a table) in a linear array, and use a formula to compute the new position given the original arguments. That formula is quadratic, and you are basically changing space for speed.

The best thing to do however is looking for two tables that are symmetric (commutative operations) and of the same size, and share the space.
> 7 votes

# Answer
I want to expand on the other answers and give a concrete example of the **2-D index map to 1-D index**.

Let $N = \\{0,1,2,3,...\\}$. Call our one-to-one map $f \colon N \times N \rightarrow N$.

First, let us list out some desirable properties $f$ should have.

1. $f$ is commutative. We want `[x][y]` and `[y][x]` to use same position in memory.
2. Small index maps to small index.
3. Since $f$ is a bijection to $N$, it gives an ordering to $N \times N$. We want this ordering to be meaningful. Say, order by the sum. If sum is equal, order by the larger element.
4. There is no gap in the index mapped, all destination index are used.

Or more mathematically:

1. $f(x,y) = f(y,x)$
2. If $x+y \< a+b$ then $f(x,y) \< f(a,b)$
3. If $x+y = a+b$, $x\<y$, $a\<b$ and $y\<b$ then $f(x,y) \< f(a,b)$
4. If $f(x,y) = k$ then $\exists x',y'. f(x',y') = k+1$
5. $f(0,0) = 0$

Here is an implementation in Python:

```
def f(x,y):
    if x > y:
        x,y = y,x
    return ((y+1)*(y))/2 + x

```

Test run:

```
for y in range(5):
    for x in range(y+1):
        print (x,y),'->',f(x,y)

```

gives:

```
(0, 0) -> 0
(0, 1) -> 1
(1, 1) -> 2
(0, 2) -> 3
(1, 2) -> 4
(2, 2) -> 5
(0, 3) -> 6
(1, 3) -> 7
(2, 3) -> 8
(3, 3) -> 9
(0, 4) -> 10
(1, 4) -> 11
(2, 4) -> 12
(3, 4) -> 13
(4, 4) -> 14

```

## Let us show how this saves space:

First we consider the data storage space. Let $n$ be the largest index to be accessed.

If I use $n \times n$ array to store the commutative function, it would need $n^2$ units of space.

If I use 1 dimensional array to store the same data with this index mapping scheme, it would need $\frac{n(n+1)}{2}$ units of space.

Hence the data storage space saved is: $n^2 - \frac{n(n+1)}{2} = \frac{n(n-1)}{2} = O(n^2)$.

The increase in code storage size is $O(1)$ and can be overshadowed by the saving in data storage space. The increase in processing time is also $O(1)$ per access.
> 4 votes

# Answer
If you are willing to trade time for space, there are many ways to represent matrices (or other structures) satisfying specific constraints. Array of arrays, linked lists, etc. The choice of the representation also depends on what operations you intend to perform, with what frequency and statistics, either using the structure or modifying it (the most basic statement about data-structure choice). See for example this question (which I remember because I answered, and because the structure is unusual) : Algorithm: Dimension increase in 1D representation of Square Matrix.

Trading time for space, i.e. making some operations more costly in time in order to save space is not always a winning proposition. More complex access may mean more instructions inline every time the structure is accessed, which may sometimes make you lose more in code space than you gain in data space, while losing in time too.

Hence, if the dimension of you matrix remains small, and if you create few of them, it may be a wiser choice to simply waste the data space. Actually, it occasionally happens in some situations that one will chose to waste a bit of data space in order to simplify the code. One may even choose to waste a bit of space only to make the program more readable and easier to maintain.
> 1 votes

---
Tags: data-structures, storage
---


# Question
Title: Does an Operating System inject its own machine code when you open a program?
I'm studying CPU's and I know how it reads a program from the memory and execute its instructions. I also understand that an OS separates programs in processes, and then alternate between each one so fast that you think that they're running at the same time, but in fact each program runs alone in the CPU. But, if the OS is also a bunch of code running in the CPU, how can it manage the processes?

I've been thinking and the only explanation I could think is: when the OS loads a program from the external memory to RAM, it adds its own instructions in the middle of the original program instructions, so then the program is executed, the program can call the OS and do some things. I believe there's an instruction that the OS will add to the program, that will allow the CPU to return to the OS code some time. And also, I believe that when the OS loads a program, it checks if there's some prohibted instructions (that would jump to forbidden adresses in the memory) and eliminates then.

Am I thinking rigth? I'm not a CS student, but in fact, a math student. If possible, I would want a good book about this, because I did not find anyone that explains how the OS can manage a process if the OS is also a bunch of code running in the CPU, and it can't run at the same time of the program. The books only tell that the OS can manage things, but now how.

# Answer
> 39 votes
No. The operating system does not mess around with the program's code injecting new code into it. That would have a number of disadvantages.

1. It would be time-consuming, as the OS would have to scan through the entire executable making its changes. Normally, part of the executable are only loaded as needed. Also, inserting is expensive as you have to move a load of stuff out of the way.
2. Because of the undecidability of the halting problem, it's impossible to know where to insert your "Jump back to the OS" instructions. For example, if the code includes something like `while (true) {i++;}`, you definitely need to insert a hook inside that loop but the condition on the loop (`true`, here) could be arbitrarily complicated so you can't decide how long it loops for. On the other hand, it would be very inefficient to insert hooks into *every* loop: for example, jumping back out to the OS during `for (i=0; i<3; i++) {j=j+i;}` would slow down the process a lot. And, for the same reason, you can't detect short loops to leave them alone.
3. Because of the undecidability of the halting problem, it's impossible to know if the code injections changed the meaning of the program. For example, suppose you use function pointers in your C program. Injecting new code would move the locations of the functions so, when you called one through the pointer, you'd jump to the wrong place. If the programmer was sick enough to use computed jumps, those would fail, too.
4. It would play merry hell with any anti-virus system, since it would change virus code, too and muck up all your checksums.

You could get around the halting-problem problem by simulating the code and inserting hooks in any loop that executes more than a certain fixed number of times. However, that would require extremely expensive simulation of the whole program before it was allowed to execute.

Actually, if you wanted to inject code, the compiler would be the natural place to do it. That way, you'd only have to do it once but it still wouldn't work for the second and third reasons given above. (And somebody could write a compiler that didn't play along.)

There are three main ways that the OS regains control from processes.

1. In co-operative (or non-preemptive) systems, there's a `yield` function that a process can call to give control back to the OS. Of course, if that's your only mechanism, you're reliant on the processes behaving nicely and a process that doesn't yield will hog the CPU until it terminates.
2. To avoid that problem, a timer interrupt is used. CPUs allow the OS to register callbacks for all the different types of interrupts that the CPU implements. The OS uses this mechanism to register a callback for a timer interrupt that is fired periodically, which allows it to execute its own code.
3. Every time a process tries to read from a file or interact with the hardware in any other way, it's asking the OS to do work for it. When the OS is asked to do something by a process, it can decide to put that process on hold and start running a different one. This might sound a bit Machiavellian but it's the right thing to do: disk I/O is slow so you may as well let process B run while process A is waiting for the spinning lumps of metal to move to the right place. Network I/O is even slower. Keyboard I/O is glacial because people are not gigahertz beings.

# Answer
> 13 votes
While David Richerby's answer is a good one, it does sort of glaze over how modern operating systems halt existing programs. My answer should be accurate for the x86 or x86\_64 architecture, which is the only one commonly in use for desktops and laptops. Other architectures should have similar methods of achieving this.

When the operating system is starting up, it sets up an interrupt table. Each entry of the table points to a bit of code inside the operating system. When interrupts happen, which is controlled by the CPU, it looks at this table and calls the code. There are various interrupts, such as dividing by zero, invalid code, and some operating system defined ones.

This is how the user process talks to the kernel, such as if it wants to read/write to the disk or something else that the operating system kernel controls. An operating system will also set up a timer that calls an interrupt when it finishes, so the running code is forcibly changed from the user program to the operating system kernel, and the kernel can do other things such as queue up other programs to run.

From memory, when this happens the operating system kernel has to save where the code was, and when the kernel has finished doing what it needs to do it restores the previous state of the program. Thus the program doesn't even know that it was interrupted.

The process can't change the interrupt table for two reasons, the first is that it is running in a protected environment so if it tries to call certain protected assembly code then the cpu will trigger another interrupt. The second reason is virtual memory. The location of the interrupt table is at 0x0 to 0x3FF in real memory, but with user processes that location is usually not mapped, and trying to read unmapped memory will trigger another interrupt, so without the protected function and the ability to write to real RAM, the user process can't change it.

# Answer
> 5 votes
The OS kernel gets control back from the running process due to CPU clock interrupt handler, not by injecting code into the process.

You should read about interrupts to get more clarification about how they work and how OS kernels handle them and implement different features.

# Answer
> 3 votes
There *is* a method similar to what you describe: *co-operative multitasking*. The OS does not insert instructions, but each program must be written to call OS functions which may choose to run another of the cooperative processes. This has the disadvantages you describe: one program crashing takes out the whole system. Windows up to and including 3.0 worked like this; 3.0 in "protected mode" and above did not.

Pre-emptive multitasking (the normal kind these days) relies on an external source of interrupts. Interrupts override the normal flow of control and usually save the registers out somewhere, so the CPU can do something else and then transparently resume the program. Of course, the operating system can change the "when you leave interrupts resume here" register, so it resumes inside a different process.

(Some systems *do* rewrite instructions in a limited way on program load, called "thunking", and the Transmeta processor dynamically recompiled to its own instruction set)

# Answer
> 3 votes
Multi-tasking does not require anything like code injection. In an operating system like Windows, there is a component of operating system code called the scheduler which relies on a hardware interrupt triggered by a hardware timer. This is used by the operating system to switch between different programs and itself, making it all seem to our human perception to happen concurrently.

Basically, the operating system programs the hardware timer to go off every so often... perhaps 100 times a second. When the timer goes off, it generates a hardware interrupt - a signal which tells the CPU to stop what it's doing, save its state on the stack, change its mode to something more privileged, and execute the code it will find in a specially designated place in memory. That code happens to be part of the scheduler, which decides what should be done next. It might be to resume some other process, in which case it will have to perform what is known as a "context switch" - replacing the entirety of its current state (including virtual memory tables) with that of the other process. In returning to a process, it has to restore all of the context of that process, and then return from the interrupt - restoring its privilege mode and execution state from the stack, and continuing that process.

The "specially designated" place in memory does not have to be known by anything but the operating system. Implementations vary, but the gist of it is that the CPU will respond to various interrupts by performing a table lookup; the table's location is at a specific place in memory (determined by the hardware design of the CPU), the contents of the table is set by the operating system (generally at boot time), and the "type" of interrupt will determine which entry in the table is to be used as the "interrupt service routine".

None of this involves "code injection"... it is based on code contained in the operating system in co-operation with hardware features of the CPU and its supporting circuitry.

# Answer
> 2 votes
I think the closest real-world example to what you describe is one of the techniques used by VMware, Full virtualization using binary translation.

VMware acts as a layer underneath one or more simultaneously executing operating systems on the same hardware.

Most of the instructions being executed (e.g. in ordinary applications) can be virtualized using the hardware, but an OS kernel itself makes use of instructions that cannot be virtualized, because if the machine code of the guess OS were executed unmodified it would "break out" of the control of the VMware host. For example, a guest OS would need to run in the most privileged protection ring, and set up the interrupt table. If it were allowed to do that, VMware would have lost control of the hardware.

VMware rewrites those instructions in the OS code before executing it, replacing them with jumps into VMware code that simulates the desired effect.

So this technique is somewhat analogous to what you describe.

# Answer
> 2 votes
There are a variety of cases in which an operating system might "inject code" into a program. The 68000-based versions of the Apple Macintosh system builds a table of all segment entry points (located immediately preceding the static global variables, IIRC). When a program starts, each entry in the table consists of a trap instruction followed by the segment number and offset into the segment. If the trap is executed, the system will look at the words after the trap instruction to see what segment and offset is required, load the segment (if it isn't already), add the start address of the segment to the offset, and then replace the trap with a jump to that newly-computed address.

On older PC software, although this wasn't technically done by the "OS", it was common for code to be built with trap instructions instead of coprocessor math instructions. If no math coprocessor was installed, the trap handler would emulate it. If a coprocessor was installed, the first time a trap is taken the handler will replace the trap instruction with a coprocessor instruction; future executions of the same code will use the coprocessor instruction directly.

---
Tags: operating-systems
---


title: Computing the complement of a set

text:
# Question
Title: Computing the complement of a set
Suppose I have a set $A$ of elements in $\\{1, \ldots, n\\}$, given as an unordered list. I would like to compute the complement of $A$, i.e., I would like to produce an unordered list of entries in $\\{1, \ldots, n\\}$ but not in $A$.

One way to do this is to sort the entries of $A$ and then go through them and list all the entries I do not see. This takes $O(n \log n)$ in the unit cost RAM model. My question is whether there exists a linear time $O(n)$ algorithm in the same model.

# Answer
Since you have both lists, even if not both at the same time, your space cost is at least that of the longest, thus at least $n/2$. This corresponds to a $O(n)$ space complexity.

So, unless you exclude it for some reason, it makes sense to use a bit array $M\[1:n\]$ to represent the set A by its characteristic function, i.e. $M\[i\]=0$ iff $i\notin A$, and $1$ otherwise. The space complexity is unchanged, and the array $M$ is actually much smaller than one of the two lists (initial or final).

Initializing the array $M$ from the initial list is linear.

Then you can take the logical complement of the array $M$ in linear time.

Then you scan the array in linear time to get all the element of the complement of your initial list in linear time $O(n)$

Of course, by now you have noticed your mistake: sorting is in time $O(n \log n)$ (or better according to comment) when $n$ is the number of element to be sorted. But it is trivially linear if $n$ is the size of the finite ordered set they come from.

Using an array, as I just did is one way of sorting in linear time with respect to the size of the referance set.

**Your own answer was good** because of that. Only your complexity assessment was wrong.
> 7 votes

---
Tags: algorithms, algorithm-analysis, time-complexity, sorting, finite-sets
---


title: number encoding effect on complexity

text:
# Question
Title: number encoding effect on complexity
I started reading the book "Data Structures and Network Algorithms" by Robert Tarjan, which is a classic (but a bit outdated - 1983) and I am a bit perplexed by the paragraph in the first chapter, Page 3, first paragraph. I have attached the paragraph below:

> An important caveat concerning random-access and pointer machines is that if the machine can manipulate numbers of arbitrary size in constant time, it can perform hidden parallel computation by encoding several numbers into one. There are two ways to prevent this. Instead of counting each operation as one step (the *uniform cost measure*), we can charge for an operation a time proportional to the number of bits needed to represent the operands (the *logarithmic cost measure*). Alternatively we can limit the size of the integers we allow to those representable in a constant times log *n* bits, where *n* is a measure of the input size, and restrict the operations we allow on real numbers. We shall generally use the latter approach; all our algorithms are implementable on a random-access or pointer machine with integers of size at most *n* for some small constant *c* with only comparison, addition, and sometimes multiplication of input values allowed as operations on real numbers, with no clever encoding.

Would somebody be able to explain this paragraph or point me to some references that elaborates it better?

# Answer
If we allow numbers to be unbounded while keeping the unit cost model (each operation costs one unit), we get a very powerful machine. For example, here is how to solve 3SAT in this model. Recall that a 3CNF is a formula of the form

$$ (x\_1 \lor \lnot x\_2 \lor x\_3) \land (x\_1 \lor x\_4 \lor \lnot x\_5) \land \cdots. $$

Here $\lor$ is logical OR, $\land$ is logical AND, and $\lnot$ is logical NOT. The 3CNF is an AND of *clauses*, each of which is the OR of three *literals*; a literal is either a variable or its negation. The 3SAT problem asks whether a given 3CNF is *satisfiable*, that is, whether there is a truth assignment to the variables under which the formula evaluates to TRUE.

Suppose the given 3CNF has $n$ variables. For a formula $\varphi$, let $T(\varphi)$ be a "bit-vector" of length $2^n$, indexed by truth assignments to the variables, such that the bit at position $x$ is the truth value of $\varphi$ evaluated at the assignment $x$ (i.e. 1 if $\varphi$ is TRUE and 0 if $\varphi$ is FALSE). We order the truth assignments in lexicographic order; for example, if $n=2$ then the truth assignments are $(F,F),(F,T),(T,F),(T,T)$, given in the format $(x\_2,x\_1)$. Continuing the example, $T(x\_1) = 1010$ and $T(x\_2) = 1100$ (we read the bits from right to left), both in binary notation.

Consider now the following operations:

1. For each $i$, we can compute $T(x\_i)$ as follows: $$ \begin{align\*} T(x\_i) &= \sum\_{a=0}^{2^{i-1}-1} \sum\_{b=0}^{2^{n-i}-1} 2^{2^i b + 2^{i-1} + a} \\ &= 2^{2^{i-1}} \sum\_{a=0}^{2^{i-1}-1} 2^a \sum\_{b=0}^{2^{n-i}-1} (2^{2^i})^b \\ &= 2^{2^{i-1}} (2^{2^{i-1}}-1) \frac{(2^{2^i})^{2^{n-i}}-1}{2^{2^i}-1} \\ &= \frac{2^{2^{i-1}} (2^{2^{i-1}}-1)(2^{2^n}-1)}{2^{2^i}-1}. \end{align\*} $$
2. Given $T(\alpha),T(\beta)$, we can compute $T(\lnot \alpha), T(\alpha\land\beta), T(\alpha\lor\beta)$ using bitwise NOT, AND, OR.

In this way, we can efficiently compute $T(\varphi)$, where $\varphi$ is the given 3CNF. The formula $\varphi$ is satisfiable iff $T(\varphi) \neq 0$. This gives a polynomial time algorithm for 3SAT in the unit cost model. Obviously something is wrong and needs fixing, which is what Tarjan is getting at.
> 6 votes

# Answer
This is a way to say that the complexity analysis will break down if assuming that a RAM machine can handle numbers of arbitrary length as 1 unit (think of a quantum computer which can solve np-complete problems using the superposition principle, what the author states as doing parallel computations on multiple numbers encoded as 1 unit). So the author states that the RAM machine does not handle arbitraty numbers but only those of certain length (the O(logN) cost).

UPDATE:

In a paper by Hartmanis and Simon on the power of multiplication in RAM machines (circa 1974), a result is derived where if a RAM machine can handle multiple opertions in parallel (or as one unit), then it is equivalent to a Non-deterministic Tuing machine, thus can solve NP-complete problems (in polynomial time). This is related to this question
> 2 votes

# Answer
You may be distracted by purely theoretical appproach of explanation.

This is a proof that you can implement every algorithm with integer numbers stored in RAM without asymptotic distortions. I mean $O(N)$ will be $O(N)$ on your computer.

It's true because every operation on integer number of limited (constant) size is $O(1)$. He say $n^c, c-small$ instead of $1$ just to show that, for example 32-bit type is the same as 64-bit type, and it's size do not change algorithm asymptotic (but it works slower on some part of computers, just because of resulting constant values defference).

I think author will give a proof for real numbers on next pages (by induction from integers), or even more - for every possible data type with "no clever encoding" (:D, but it really make sense).
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: Additional clarification about Simultaneous Multithreading
I was looking for comments about SMT and got several responses. The last one looks strange:

> Simultaneous multithreading, which can only be implemented on a multicore system, executes the different threads on different cores, or on different processing units on the same core ("superscalarity").

Why can SMT be implemented only on a multicore system? Hyperthreading is normally used to improve performances by filling the most possible the functional units? Not? So, it seems to me that we could have only one core with hyperthreading..

What have I not understood ? Is the term 'processing unit' referred to as 'functional unit'?

# Answer
> 5 votes
The confusion seems to be different terminology used in different sub-communities of computer science. To most computer scientists, *simultaneous multithreading*, is thought of as any situation in which two threads seem, to the operating system, to be physically executing in parallel. When computer *architects* (including the well-known textbooks by Hennessy and Patterson) use the term they are referring specifically to the technique described in the paper: Tullsen, Dean M; Eggers, Susan J; Levy, Henry M: Simultaneous Multithreading: Maximizing On-chip Parallelism, *Int'l Symp Comp Arch*, (ISCA-22):392-403, 1995.

That is, computer architects are specifically referring to providing two or more hardware thread contexts on the same super-scalar core, and not to simultaneously executing threads on different cores.

*Hyperthreading* is typically used, by computer architects, as a synonym for the same thing: providing two or more hardware thread contexts on the same physical super-scalar core. As pointed out by @PaulA.Clayton the term "Hyper-Threading" was invented by Intel as a marketing term, but Intel has sometimes used it to refer to hardware simultaneous multithreding, and sometimes to refer to coarse-grained hardware multithreading on the Itanium 2, but then does *not* use Hyper-Threading to describe the fine-grained hardware multithreading on the Xeon Phi.

# Answer
> 2 votes
Hyperthreading provides multiple logical cores on a single physical core. For SMT the view of the software is important, i.e. the logical cores. Thus a single core with HT is considered a multicore system in this context.

# Answer
> 0 votes
Hyperthreading and SMT are not the same thing, so I'm not sure why other people seem to be saying that they are.

Hyperthreading is when one core tries to intelligently context switch back and forth between two processes to increase throughput, banking on the latency of the one process being longer than the cost of context-switching twice. Imagine you had two processes, each with some I/O component - while one is waiting for input to be read from disk, it can switch to the other process in hopes of getting some work done while waiting. This is helpful in I/O bound processes, and is decidedly unhelpful in highly-performant code. If you're actually using your core at or near its maximum capability (arithmetic-intensive code, for example), then Hyperthreading doesn't help you, and in fact can slow you down, since context-switching between processes even once is more wasteful than just doing them in serial. The reason Hyperthreading is beneficial to 'normal computer users' is that they are rarely if ever writing/running highly-performant code without any I/O or other latency concerns.

SMT, on the otherhand, is *multi*-threading, where multi implies more than one. You need multiple threads to actually implement multi-threading, and they are truly running simultaneously because you have multiple cores, both of which are in use at the same time. SMT is always a win, because you're doing 2 (or more) calculations at the same time, which has got to be better than the single calculation you would get from a single core. Even a Hyperthreaded single core - it's still just one processor, doing one operation at a time.

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


title: Matrix usage in CS

text:
# Question
Title: Matrix usage in CS
I'm studying a major in CS. I'm interested in taking a few extra courses, specifically math to improve my knowledge as future computer scientist.

Right now I'm thinking to take Matrix Fundamentals but I'm not sure if it is going to help me in my CS career. What are its uses apart from arrays in programming?

# Answer
Just like you might model real-world things with a set, you model some other real-world things with a matrix. Things that you might model as a matrix ranges includes:

* product-user rating table
* between places distance table
* bitmap images

Modelling things with matrix allow you to see the problem in different perspective. And allow you to see what it might actually mean to apply some matrix operations to it.

For example, you might notice that matrix multiplication on 'distance table' actually gives you a transitive distances.

Or that rank-factorization of product-user rating table actually provides a mean to categorize users into groups that have the same taste.

Or that know eigen vectors helps in understanding the eigen faces that one corner stone in face recognition.
> 1 votes

---
Tags: matrices, mathematical-foundations
---


# Question
Title: Calculating miss rates of word-addressable and direct-mapped cache
This a problem in a computer architecture course that's giving me some trouble:

You have an application whose memory access pattern is a stream and its entire data set is 128kB. The data cache in your machine has a capacity of 64kB. It is word-addressable and direct-mapped with 32B lines. It is able to fetch one line at a time.

Given the access pattern: 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, …, 32768, where each access is a 4B word.

1. What is the miss rate?
2. Can the miss rate be reduced by using a larger cache?
3. Can the miss rate be reduced if the size of the data set were reduced?

Here's what I think is going on: The cache is initially empty, meaning each access will result in a compulsory miss. So would this mean the miss rate is 100%, since no data is initially loaded and the pattern doesn't hit any address twice?

Any help understanding this would be much appreciated!

# Answer
> 4 votes
It seems you don't understand how cache lines work. A cache line is a contiguous chunk of memory. In this example, the cache line size is 32 bytes. This means that 32 contiguous bytes are always loaded into the cache at a time, namely whenever a miss occurs.

So if we initially assume the cache is empty (or "cold"), then the first access will be a miss. However, the first 28 bytes will be loaded in. This means that in addition to loading word 0 into the cache, the words at addresses 4, 8, 12, 16, 20, 24, and 28 will also get loaded into the cache. Conveniently, this is how your example program accesses data (linearly), so we will get a cache hit for all of those words. When we hit the word at address 32 we will again get a miss and the process repeats. Thus, our miss rate is 1/8, once for every 32 byte block.

Since we are never accessing the same data more than once, the size of the cache itself is irrelevant, i.e. all we need is for the cache to be able to hold a single line. Thus, we can not reduce our miss rate with a larger cache.

And finally, as shown from the analysis, the size of the data set is irrelevant. It doesn't matter if we're reading in 1 Kilobyte or 1 Gigabyte, the miss rate is the same.

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


# Question
Title: Sum of all binary numbers matching a pattern
Given $a\_1, a\_2, a\_3, \dots,a\_7$ where $a\_i \in \\{0,1\\}$. How to calculate sum of all binary number of the form $$\over {1a\_1a\_2\*a\_3\**a\_4\***a\_5a\_6a\_7}$$

where $\*$ represent the position of running digits.

I am thinking about a dynamic programming solution.

# Answer
For any such pattern with $i$ stars we have to add $2^i$ numbers. Thus for the contribution of the fixed digits, we can replace the stars by $0$'s and append $i$ $0$'s at the right. For the contribution of the stars, we can replace the fixed digits by $0$'s and the stars by $1$'s and append $i-1$ $0$'s at the right.

For the specific example this gives $$~~~~1a\_1a\_2~0~~a\_30~0\\,~a\_4~0~~0~~0~a\_5a\_6a\_7000000~\\ \+ ~~~~~~~~~~~~~~~~1~0~1~\\,1\\,~~0~~1\\,~\\,1\\,~1~~0~~0~000000~\\ = 1a\_1a\_2a\_3\overline{a\_3}a\_4\overline{a\_4}\overline{a\_4}a\_5\overline{a\_5a\_5a\_5}a\_6a\_7000000.$$
> 2 votes

# Answer
If $\*$ mean $0, 1$ or no digit: I write a very simple program (sorry, I have trouble with `SHIFT` \+ `8` and don't want `Crtl` \+ `V` too much :) )

```
int main(){
    string s;
    int res = 1, pos = 1;
    cin >> s;
    for(int i = 1; i < (int) s.length(); ++i){
        if (s[i] == '0'){
            res <<= 1; // res = 2 x res;
        } else if (s[i] == '1'){
            res <<= 1;
            res += pos;
        } else {
            (res <<= 2) += (res >> 2) + pos;
            (pos <<= 1) += (pos >> 1);
        }
    }
    cout << res;
}

```

I will post the proof later. I need to sleep first.
> -2 votes

---
Tags: algorithms, binary-arithmetic
---


# Question
Title: Example for an unsatisfiable formula that can be made satisfiable by reordering quantifiers
Please give me an example of an unsatisfiable quantified 2 CNF formula. I need it in my proof and I am unable to think of one.

I am looking for such an unsatisfiable quantified 2 CNF formula which gets satisfiable if the ordering of prefix is changed.

# Answer
> 3 votes
A very simple example is

$$ \exists x \forall y (x \> y) $$

where the universe is the natural numbers.

If you want just literals (i.e. universe is booleans), then another example would be

$$ \exists x \forall y ((x \land y) \lor (\neg x \land \neg y)) $$

# Answer
> 1 votes
This

$\qquad \forall x \exists z \space (x = z)$

is a true QBF. Whatever Boolean value $x$ is set to, $z$ can be set to match. Translated to quantified CNF:

$\qquad \forall x \exists z \space (x \lor \lnot z) \land (\lnot x \lor z)$

Reordering the quantified variables produces

$\qquad \exists z \forall x \space (x \lor \lnot z) \land (\lnot x \lor z)$

which is a false formula because there is no value for $z$ that can be equal to both true and false at the same time.

---
Tags: logic, satisfiability
---


# Question
Title: Can not follow the example for max-flow-min-cut on Wikipedia
This Wikipedia example is very confusing. Its saying the max flow = min cut. But I see the max flow = 9 and the min cut = 7. If not, how does the capacity =min cut here? Which is the max flow min cut theorem.

# Answer
Okay, really sorry. I got confused with maximal and max flow in the graph. Obviously, the maximal is what is at most the capacity, and max flow is how much at most can flow though this network. The answer to the former is of course 9, where at the latter is 7.

In this case the max flow from s to t through 1 is 4 and from s to t through 2 (as first node) is 3 which equals the min cut, which is the dashed arrow.

I hope this helps anyone who had the same confusion.
> 0 votes

# Answer
Max flow isn't 9 it is 7. 4 from s to 1 and 3 from s to 2.It cannot have more than that.You can see that it is also equal to min-cut.
> 1 votes

# Answer
The flow depicted in the diagram has value 7. This is the total amount of flow out of the source node $s$, as well as the total amount of flow into the sink node $t$. Since the total capacity out of the source node $s$ is 7, this flow is maximum, i.e., no flow has larger value. This is also the value of the cut which separates $s$ from the rest of the graph. The existence of a flow of value 7 shows that this cut is minimum (if there was a cut of smaller value then there couldn't be a flow of value 7 since it could not cross the cut).

While the total capacity of edges incoming at $t$ is 9, no flow saturates these edges. Consider the thought experiment in which we changed the capacity of these edges to be infinite. Would you then say that the max flow is $\infty$?

That the max flow is at most the min cut is not hard to see: basically, each cut constrains each flow, and in particular the max flow is at most the min cut. The non-trivial part of the max flow min cut theorem is that the it is possible to achieve a flow whose value is the min cut, or conversely that there exists a cut whose value is the max flow.
> 1 votes

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Quantum Computing - Relationship between Hamiltonian and Unitary model
When developing algorithms in quantum computing, I've noticed that there are two primary models in which this is done. Some algorithms - such as for the Hamiltonian NAND tree problem (Farhi, Goldstone, Guttman) - work by designing a Hamiltonian and some initial state, and then letting the system evolve according to the Schrödinger equation for some time $t$ before performing a measurement.

Other algorithms - such as Shor's Algorithm for factoring - work by designing a sequence of Unitary transformations (analogous to gates) and applying these transformations one at a time to some initial state before performing a measurement.

My question is, as a novice in quantum computing, what is the relationship between the Hamiltonian model and the Unitary transformation model? Some algorithms, like for the NAND tree problem, have since been adapted to work with a sequence of Unitary transformations (Childs, Cleve, Jordan, Yonge-Mallo). Can every algorithm in one model be transformed into a corresponding algorithm in the other? For example, given a sequence of Unitary transformations to solve a particular problem, is it possible to design a Hamiltonian and solve the problem in that model instead? What about the other direction? If so, what is the relationship between the time in which the system must evolve and the number of unitary transformations (gates) required to solve the problem?

I have found several other problems for which this seems to be the case, but no clear cut argument or proof that would indicate that this is always possible or even true. Perhaps it's because I don't know what this problem is called, so I am unsure what to search for.

# Answer
> 11 votes
To show that Hamiltonian evolution can simulate the circuit model, one can use the paper Universal computation by multi-particle quantum walk, which shows that a very specific kind of Hamiltonian evolution (multi-particle quantum walks) is BQP complete, and thus can simulate the circuit model.

Here is a survey paper on simulating quantum evolution on a quantum computer. One can use the techniques in this paper to simulate the Hamiltonian evolution model of quantum computers. To do this, one needs to use "Trotterization", which substantially decreases the efficiency of the simulation (although it only introduces a polynomial blowup in computation time).

---
Tags: algorithms, quantum-computing, computation-models
---


# Question
Title: Monotone boolean satisfiability with at most k 1s is NP-Complete
I am to prove that monotone boolean formula satisfiability checking when at most k variables are set to 1 is an NP-Complete problem. Proving that it is in NP is easy, but I'm having difficulty showing that it is in NP-Hard. I have seen this, but I would rather not use its solution, as the textbook for the course I am self studying does not present Dominating Sets as an NP-Complete problem. The NP-Complete problems presented in my book(Dasgupta, Papadimitriou, and Vazirani) are the following: 3SAT, Traveling Salesman, Longest Path, 3D-Matching, Knapsack, Independent Set (related to Dominating Set from what I understand), Vertex Cover, Clique, Integer Linear Programming, Rudrata Path, and Balanced Cut.

From my understanding of the problem, if you restrict the clauses to 2 literals each, then this directly parallels the vertex cover problem, and is thus NP-hard. I was wondering if there was any way that I could use this fact to say that the unrestricted problem is also NP-Hard. I intuitively feel that this should work, because the restricted version is a subset of the restricted version, so in at least some cases the problem is NP-hard. Since you always take the worst case scenario, could you extend this to NP-hardness for the unrestricted problem? If so, how would I word that (this is for a self study, not to be turned in), in the proper form? Because my above explanation has a roundabout method of showing the point.

tl;dr Can you prove that something is np-hard by showing that a subproblem is np-hard? I intuitively feel like you should, but want to confirm.

# Answer
Let $L'$ be a restriction of $L$, say $L' = L \cap D$. Here $D$ is a restriction on the inputs such as "all clauses have two literals each".

Suppose that $L'$ is NP-hard. Then for every language $M$ in NP, there is a polytime reduction $\varphi$ from $M$ to $L'$ such that $x \in M$ iff $\varphi(x) \in L'$. If $\varphi(x) \in D$ for *all* $x$, then $\varphi(x) \in L'$ iff $\varphi(x) \in L$, and so $\varphi$ is also a reduction from $M$ to $L$.

Usually NP-hardness proofs go by reduction from some specific NP-complete problem $M$. If the polytime reduction $\varphi$ from $M$ to $L'$ showing that $L'$ is NP-hard satisfies the property $\varphi(x) \in D$ for all $x$ (in other words, its range is \[contained in\] $D$), then the reasoning in the preceding paragraph shows that $\varphi$ also proves that $L$ itself is NP-hard.

For example, in your case $L$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone Boolean formula that can be satisfies by setting at most $k$ of the literals to TRUE; $D$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone 2CNF; and $L' = L \cap D$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone 2CNF that can be satisfied by setting at most $k$ of the literals to TRUE. Any reduction $\varphi$ showing that $L'$ is NP-complete whose range is $D$ also shows that $L$ is NP-complete.

To check that you understand the argument, try to see what goes wrong when we take $L'$ to be, say, 3SAT, and $L$ to be the language of all 3CNFs.

Finally, here is a trick that you can use to emulate SAT in your setting. Suppose that some CNF $\varphi$ has variables $x\_1,\ldots,x\_n$, some of them possibly appearing negated. Consider $\psi = \varphi' \land (x\_1 \lor y\_1) \land \cdots \land (x\_n \lor y\_n)$, where $\varphi'$ results from replacing $\lnot x\_i$ by $y\_i$. Then $\varphi$ is satisfiable iff $\psi$ is satisfiable by a truth assignment in which at most (or exactly) $n$ variables are TRUE.
> 4 votes

---
Tags: np-complete, np-hard, satisfiability
---


# Question
Title: First Order interpretation of arbitrary structures as a graph
I am currently trying to get some intuition on the concept of First Order reductions, and have come across this exercise question by Immerman, dubbed "Everything is a Graph".

Given some arbitrary relational structure $S$ of some vocabulary $\sigma$, show that there are first-order queries $I$ and $I^{-1}$, such that $G:=I(S)$ is a directed graph, and $I^{-1}(G)$ is isomorphic to $S$.

I would be grateful for some hints and proof ideas, as I struggle a bit with seeing how the encoding would work.

# Answer
> 3 votes
The following is, as requested, a hint rather than a full answer. I'll hint at one way of doing the coding; I'll not touch on how to define the queries but those formulas will always be horrible and you'd probably end up describing them in words anyway. We'll code a structure $\cal{A}$ that has universe $A$ as a graph $G\_\cal{A}$. The will contain one vertex for each element of $A$, plus a whole bunch of other vertices that encode the relations and so on.

1. You can assume a purely relational vocabulary by using standard codings of constants and functions as relations.
2. Coding is done by adding "gadgets": small graphs that you can recognize. Remember that, for every graph $H$ on $k$ vertices, there is a formula $\varphi\_H(x\_1, \dots, x\_k)$ such that $(G, v\_1, \dots, v\_k)\vDash \varphi\_H$ iff the subgraph of $G$ induced by $v\_1, \dots, v\_k$ is $H$.
3. You probably need a way to say "This vertex is an element of $A$." Come up with a gadget, make a copy of the gadget for each element of $A$ and add an edge between the gadget and the vertex coding that element. (You might not need to do this but it's normally easier to just do it than to prove that it's unnecessary.)
4. You definitely need a way to say "This tuple $a\_1\dots a\_r$ is in the $r$-ary relation $R$." Come up with a gadget for each relation and a way to attach each tuple in $R$ to its own copy of the gadget. Remember that the tuple $a\_1a\_2a\_3$ is different from $a\_2a\_3a\_1$ so your coding needs to make those different.

If you don't understand what I mean about gadgets, mouse-over the following for a concrete example. However, the example gives away a lot of the answer, so try not to look at it.

> You could mark a vertex $v\in G\_\cal{A}$ as coding an element of $A$ by adding a $k$-clique to your graph, along with an edge from one vertex of the clique to $v$. So, being adjacent to a $k$-clique means a vertex codes an element of $A$. Make $k$ big enough so there are no other $k$-cliques in $G\_\cal{A}$.

If you still don't understand, leave a comment and I'll try to explain it better.

---
Tags: complexity-theory, graphs, logic, descriptive-complexity
---


title: Does this mean $P = NP$

text:
# Question
Title: Does this mean $P = NP$
I am not a formally trained guy on Complexity theory, but due to interest I am learning it. Based on different feedbacks, I have started my journey with Micheal Sipser's "Theory of Computation" (2013 edition). My question is based upon some statements from the book. My sincere apologies if the question is meaningless.

Here it goes:

1. On page 298, it is written as "We are unable to prove the existence of a single language in NP that is not in P". That implies all the NP languages are also in P.
2. Theorem 7.27 says $SAT\in P$ iff $P=NP$, and it's an implication in both directions.
3. From cook's theorem, $SAT$ is NP-complete. Hence, from the NP-complete definition $SAT \in NP$.
4. Now, from the point 3 and 1, as $SAT \in NP$ it should also be $SAT \in P$, and therefore from point 2 it should be $P=NP$.

I got stuck here, I know there is some flaw in this logical deduction (because it is not that easy to prove), but I am unable to find it. Please help me in understanding this concept, so that I can proceed further. Thanks in advance.

# Answer
> 7 votes
The important point is the iff, it means if and only if. Point 2 should be read as SAT is an element of $P$ if and only if $P=NP$, and we do not know if $SAT$ is in $P$.

Also, point one does not say all languages in $NP$ are in $P$, just that we have not proven that one is not. So Just because $SAT$ is in $NP$ does not mean it is necessarily in $P$. A proof of a language as he describes would prove $P \neq NP$

# Answer
> 10 votes
You are misinterpreting the statement quoted at point 1. *We are unable to prove the existence of a single language in NP that is not in P*, but we suspect that there are infinitely many, in fact, we suspect that all NP-complete languages are not in P.

---
Tags: complexity-theory, p-vs-np
---


title: Why are computers so complicated?

text:
# Question
Title: Why are computers so complicated?
I'm not sure this is on-topic or even the right website, please point me in the right direction if not.

I was wondering why computers are so incredibly complex. This question is as naive as it sounds, I'm really just looking for a nice explanation of why computers can't be like the airplane from Blyton's The Faraway Tree, where you push a button to go up, down, left or right.

# Answer
> 5 votes
This is actually an excellent question.

The fast answer is that we are not good enough yet to make them simple.

As Pascal said in his 16th Provincial Letter : "*Je n'ai fait celle-ci plus longue que parce que je n'ai pas eu le loisir de la faire plus court*". In English: "*I wrote a longer letter, because I did not have time to make it shorter*".

Similarly, computer scientists did not yet have time to make computer easier to use. Though they have done much better than you think.

But there are really many ways to understand your question:

* one concerns the complexity computer hardware, and that was answered previously by Vitalij Zadneprovskij.
* why is it so hard to use computers as a programmer?
* why are computers complicated to run my favorite game, or to use such and such application?

The second question is easy to answer: you just look at the kind of task that you expect from computers. Some of them require considerable work that can be incredibly complex, like running a nuclear power-plant, or like flying an airplane so that you have simple commands even for complex and unstable situations (some unstable planes cannot be flown without a computer), or driving a car automatically, and many other problems that you most likely would not be familiar with, some of them being purely mathematical. Computer can manage tasks that would swamp any human mind by their complexity.

We are tranferring to computers all sorts of complex tasks that were suppose to require (more than) human intelligence and abilities. It is not surprising that you end up with very complex devices, very complex machines, complex at least for the people who make them and are responsible for setting them to these complex tasks, whether through hardware or through software.

The point that was made by Vitalij Zadneprovskij is that the hardware, the physical part of the machine could be actually very simple, but that complexity comes from the need to make if efficient at a great variety of tasks, and to connect them to sensors and effectors, which are physical devices. This means that much of the ability to handle complex tasks comes from the software. Very elementary models of computers have been devised by mathematicians and logicians. They are all able to perform the same computational tasks as highly sophisticated modern computers ... but not necessarily with the same performance.

So we have two kinds of complexities at work. One complexity is due to the efficiency requirements of the hardware, and the need to connect to various devices. The other comes from the very complexity of the tasks we set them to, which is largely to be found in the software.

But you want simplicity of use.

For example, you do not need to know much about the inner working of your car: no mechanics, no thermodynamics, no chemistry of combustion engines, no differential gears (that helps taking turns), etc. Most people do not know any of these things, and yet they can drive their cars.

So you would expect the same for lots of other machines, including the computer. But your home computer is complex.

Well, the problem is that a computer is not analogous to your car, but to the engine of your car. The engine in your car is a very complex machine, but it is under the hood, and you do not really have to know about it when you drive.

As it turns out, you can very easily use a lot of computers with two or three buttons as you are asking. When you drive your car, you have a brake pedal (that is just one button) that runs a computer that does the braking, much better that you would, using the ABS technology, giving better braking by relaxing the brakes for tiny periods. Then, when you accelerate, I guess that another computer will increase the fuel input in just the right way. Then, on my car, I have a *no button computer* (well there is a button to turn it on) that will chide me if my wheels step on a line without the car lights blinking to indicate the move.

I also have a computer in my washing machine, but I find it a bit harder to use. Then there are computers in the TV. Well to be honest, we are surrounded by computers that are so easy to use that we do not even know there are there. That is why you are not even aware that computer are so easy to use. It is so easy you no longer notice them.

So why is it that you still have a home computer that is hard to use? The main reason is that you have closer access to various functions, so that you can put it to a wide variety of tasks. We are not yet very good at preserving the flexibility while making it easy to use, though that is improving all the time. See for example how easy it has become (well, most of the time) to use a tablet. Smartphones are more complex than phones, but do so many things.

We are not yet good enough to make computers very simple, while preserving their innate flexibility, though we made enormous progress. But many computers have become (at the expense of flexibility) so simple to use as to be invisible.

You are right to ask for simplicity. But as Pascal might say today: *simplicity requires considerable work that can be very complex*. The same Blaise Pascal who invented one of the first arithmetic machines, and gave his name to a programming language.

# Answer
> 8 votes
The main reason why computers are complicated is because they are really optimized to deliver the maximum speed. There are a lot of places in a computer where information is stored:

* processor registers: here the speed of memorization is really high, but this memory is very expensive;
* random access memory: slower and cheaper then processor registers, but more expensive and faster then hard disk memory
* hard disk: one of the cheapest and slowest kinds of computer memory

There are also cache mechanisms in between of these levels.

The first definition of computer is that of a person computing some arithmetical operation. So a person could be seen as a very familiar kind of computer, or a biologically very complex one.

Not all computer models are complicated. It has been proved that the following models can compute the same types of problems:

* Turing machines: just a tape and a finite state automata;
* lambda calculus: few definitions are enough to achieve a system to manipulate symbols;
* Godel's general recursive functions

---
Tags: computer-architecture, software-engineering
---


# Question
Title: Easy infinite subclass of cubic graphs for Hamiltonian cycle problem
I know that Hamiltonian cycle problem is $NP$-complete for 2-connected planar bipartite cubic graphs.

I'm interested in non-trivial infinite subclass of cubic graphs where the Hamiltonian cycle (path) problem is efficiently solvable. I tried the graph class database but could not find any such class graph.

> Is there any easy infinite subclass of 2-connected cubic graphs for Hamiltonian cycle problem?

**Motivation**: Barnette's conjecture states that every 3-connected planar bipartite cubic graphs is Hamiltonian which implies that HC is in $P$ (if it is true). However, Feder and Subi proved if there is any non-Hamiltonian 3-connected planar bipartite cubic graph then HC is $NP$-complete for this graph class.

# Answer
Yes, there is an infinite class of 2-connected cubic graphs on which Hamilton Cycle has a polynomial-time algorithm. Further, there is a such a class that contains infinitely many Hamiltonian graphs and infinitely many non-Hamiltonian graphs, which I think is a decent definition of "non-trivial".

First, let $H\_n$ be the union of a $2n$-cycle on vertices $\\{1, \dots, 2n\\}$ and the edges $\\{(i, i+n)\mid 1\leq i\leq n\\}$. $H\_n$ is 3-regular, 2-connected and has an obvious Hamiltonian cycle.

Now, let $G$ be a 2-connected cubic graph that has no Hamiltonian cycle. Such a graph must exist, since the Hamiltonian Cycle problem is **NP**-complete on 2-connected cubic graphs, so must have both "yes" and "no" instances. Fix an edge $xx'\in G$. For any graph $H\_n$ pick any edge $yy'\in H\_n$ and let $H'\_n$ be the graph made by taking $G\cup H\_n$, deleting the edges $xx'$ and $yy'$ and adding edges $xy$ and $x'y'\\!$.

$H'\_n$ is 3-regular and 2-connected but I claim that it has no Hamiltonian cycle. Any Hamiltonian cycle $C$ in $H'\_n$ must enter the copy of $G-xx'$ at $x$ and leave at $x'$ (or vice-versa). But then $C$ must contain a Hamiltonian path $P$ of $G-xx'$ that begins at $x$ and ends at $x'\\!$. However, no such Hamiltonian path can exist, since $P\cup\\{xx'\\}$ would be a Hamiltonian cycle of $G$, but $G$ was chosen to have no Hamiltonian cycles.

So the desired class of graphs is $\mathcal{H} = \\{H\_n\mid n\>1\\}\cup\\{H'\_n\mid n\>1\\}$. It remains to show that the Hamiltonian Cycle problem can be solved in polynomial time for graphs in $\mathcal{H}$. Observe that, for every $n$, every edge of $H\_n$ is on a 4-cycle (there are 4-cycles of the form $i$, $i+1$, $i+n+1$, $i+n$, $i$). However, the edges $xy$ and $x'y'$ are not on any 4-cycle of $H'\_n$. We can test that every edge of a graph is in a 4-cycle in time $\mathcal{O}(n^4)$.

---

I edited to changed the construction slightly, with two benefits. First, the algorithm runs in time $\mathcal{O}(n^4)$ instead of $\mathcal{O}(n^{|V(G)|})$. Second, there's an actual correctness proof; the old algorithm relied on the assumption that $G-xx'$ is not a subgraph of any $H\_n$, which was probably true but really needed to be proven.
> 4 votes

---
Tags: complexity-theory, graphs, hamiltonian-path
---


title: Arrangement of numbers in a grid

text:
# Question
Title: Arrangement of numbers in a grid
I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$.

I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the function $f(i) \> 0.5$ where:

$f(i)$ is the probability that a number chosen randomly from row $i$ will be greater than a number chosen randomly from row $P\[i\]$. ($i$'s corresponding row according to permutation.)

For an example, let $n=3$,$m=3$,$P=\[3, 1, 2\]$ and $M=$

```
2 6 7
3 4 8
1 5 9

```

According to the given permutation, you will have to compare the number chosen from 1st row with 3rd row and similarly.

In the given matrix number are arranged in such a way that $f(1) = f(2) = f(3) = 5/9$. Observe that there are 5 pairs in the Cartesian product $\\{2,6,7\\}\times\\{1,5,9\\}$ which the first element is larger than the second.

My question is how to construct such a matrix provided $n,m,P$ as input?

# Answer
> 2 votes
Here are some ideas for you to start thinking.

First of all, the problem isn't always solvable. For example, if $P$ contains a fixed point or a cycle of length 2, there is no solution (why?).

More generally, For each $m,k$, either there is a $k \ldots m$ solution for a cycle of length $k$, or there isn't. Let $L\_m$ be the set of $k$ such that a solution exists (so $1,2 \not\in L\_m$ for all $m$, and $3 \in L\_3$). Then for given $m,P$, there is a solution iff the sizes of all cycles in $P$ lie in $L\_m$ (why?).

It remains to determine $L\_m$. Let us know if you get stuck doing that. You can start with small $m$ such as $1,2,3$.

---
Tags: combinatorics, dynamic-programming, probability-theory
---


# Question
Title: What is the time complexity of the Bailey–Borwein–Plouffe formula?
How can I assess and derive the time complexity of the BBP formula? $$ BBP(n)=4S(1,n) - 2S(4,n) - S(5,n) - S(6,n) $$ where

$$ S(j,n) = \sum\_{k=0}^n{\frac{16^{n-k}mod(8k+j)}{8k+j}}+\sum\_{k=n+1}^{\infty}{\frac{16^{n-k}}{8k+j}} $$

Note that the modulo is evaluated using the binary modular exponentiation algorithm (which is supposedly O(log N)) and the second sum iterates only over a few elements, i.e. up to a certain $\epsilon$.

I got O(N log N), but even if it is correct, I can't derive it.

# Answer
A good place to start is the BBP paper. In Section 3 (1st paragraph of page 8) they state that the running time for $n$ digits is $O(n\log nM(\log n))$, where $M(m)$ is the complexity of integer multiplication; currently the best known algorithms give $M(m) = O(m\log m 2^{O(\log^\* m)})$ bit complexity, though Fürer himself (inventor of the first algorithm with that complexity) argues that this is not the correct complexity measure.
> 4 votes

---
Tags: time-complexity
---


# Question
Title: what's the meaning of LOC(X[j]) = $L_0$ + cj in TAOCP's 5.4.1R?
in TAOCP vol3 2nd Edtion's 5.4.1R Replacement Selection, there is a paragraph describing a data structure and example for Replacement Selection as follows:

the algorithm below uses a data structure containing $P$ nodes to represent the selection tree; the $jth$ node $X\[j\]$ is assumed to contain $c$ words beginning in $LOC(X\[j\]) = L\_0 + cj$, for $0$ $\le$ $j \< P$, and it represents both internal node number $j$ and external node number $P + j$ in Fig.63. There are several named fields in each node:

$KEY$ = the key stored in this external node;

$RECORD$ = the record stored in this external node (including $KEY$ as a subfield)

$LOSER$ = pointer to the "loser" stored in this internal node;

$RN$ = run number of the record pointed to by $LOSER$;

$PE$ = pointer to internal node above this external node in the tree;

$PI$ = pointer to internal node above this internal node in the tree.

For example, when P = 12, internal node number 5 and external node number 17 of Fig.63 would both be represented in $X\[5\]$, by the fields $KEY = 170, LOSER = L\_0 + 9c$ (the address of external node number 21), $PE = L\_0 + 8c, PI = L\_0 + 2c $

for $LOC(X\[j\]) = L\_0 + cj$, 4 questions:

1. I need TAOCP's $MIX$ machine knowledge for understand this formula?
2. it seems that $LOC(X\[j\])$ is not meaning of the array or pointer, its goal is to find $X\[j\]$'s beginning addrss?
3. $cj$ is equal to $c * j$?
4. what's the meaning of $L\_0$ ?
5. $LOC(X\[5\] = L\_0 + 5c, LOSER = L\_0 + 9c = LOC(X\[9\]), PE = L\_0 + 8c = LOC(X\[8\]), PI = L\_0 + 2c = LOC(X\[2\]) $,
what's the meanings about them $LOC(X\[9\]),LOC(X\[8\]), LOC(X\[2\])$?
6. according to $LOSER = L\_0 + 9c$ indicates that the address of external node number $21$, so that $PE = L\_0 + 8c$ indicates the address of external node number $20$, and $PI$'s address of external node number $14$, but int this case of internal number 5 and external number $17$, $20$ and $14$ are unrelated to them?

# Answer
> 1 votes
The key observation may be each array element of X (regrettably called node by DEK, just as the nodes of fig. 63) representing one internal (round) and one external (rectangular) node of figure 63 with no discernible relation.
1&2) Don't think so, for this formula it should suffice to take LOC(X(j)) as the location in MIX's linear memory of (the first word of) the jth element of array X of records of c words each (see 2nd paragraph above), a natural number from 0 to 3999. (Then, there is en.wikipedia.org/wiki/MIX)
3) yes, $cj$ is consise for $c * j$
4) $L\_0$ seems to be the location of the first word of all the consecutive words representing Algoritm R's data structure
5) Those LOC()-expressions denote the locations of X's elements 9, 8, and 2, resp.
6) no relation I can see: $17$ happens to be $5 + P = 5 + 12$, the parent (external, PE) of which is (internal) node 8, coincidentally represented by the same element as (external) node 20, parent (internal, PI, used to be FI(/FE) in 1st ed.) of node 5 is 2, $14 = 2 + P$ happens to share the same element of X.

---
Tags: algorithms, data-structures
---


# Question
Title: Why don't hard drives actually delete data?
As far as I understand it, when you delete a file from trash/recycle bin the file isn't actually erased from memory but is instead marked as being okay to be over written.

So, my question is as to why this is the case. Is it simply for speed/convenience reasons or is actually deleting data just a much harder (or impossible) thing to do?

I ask because of the potential security vulnerabilities, such as reselling older hardware and etc.

# Answer
> 5 votes
There are two possible criticisms here, which should actually be leveled at the operating system, more accurately the file system:

1. Why does the OS not superficially erase data when a file is erased?
2. Why does the OS not thoroughly erase data when a file is erased?

Regarding point 1, historically speaking, you don't want to do this, since you might change your mind later on, and this way the data is still there. Of course, modern operating systems which have a recycle bin (some of them, say Linux and OS X, only implement this on their GUI) don't really benefit from this advantage. Rather, one reason you don't want to erase data superficially is that it is still possible to recover the data, say using lab analysis. Perhaps this is even feasible by reading the location many times and measuring the amount of errors. However, there is still something to gain here: malicious software would have a much harder time reading your data even if it is just erased superficially.

Regarding point 2, if you rigorously erased the data each time a file is erased, then you will probably shorten your hard drive's life. In addition, deletion would become a slow operation, which may hurt performance when many temporary files are created, a technique which had been common in the past.

If you really care about erasing your data before reselling older hardware, you can obtain software that will thoroughly erase the data and thus make it much harder to recover. If you're afraid that your hard drive, containing sensitive information, could be stolen at any point, then you should erase your sensitive data using the same kind of software.

It remains to consider the casual user who is worried about malicious software reading erased files. Such a user could benefit from superficial erasure of files. I am not aware of any file system providing this service.

If you're not using an actual hard drive but some other storage device, you might encounter other difficulties, check out this question on askubuntu.

As a workaround, and as suggested by the answers to the aforementioned question, you can encrypt your hard drive instead.

# Answer
> 2 votes
Because the process of actually erasing a file so that it cannot be recovered may be time consuming depending on the size of the file. Every space in which the file exists needs to be rewritten, either randomly or with a consistent pattern. It is much easier for the computer to "forget" the address of the given file and allow that space in memory to be overwritten. Also you may want to recover the data at a later point at this process, at least for a time, facilitates this.

---
Tags: operating-systems, storage
---


# Question
Title: Tag-free garbage collection for object oriented languages
I'm looking around for a good garbage collection technique for my language and found this paper, where Benjamin Goldberg describes a garbage collection technique for strongly typed languages, which removes the need for type information during runtime.

Briefly, this is done by placing a pointer to a garbage collection function right after a function call, directly in the compiled code. They then extend this to support ML-like parametric polymorphism.

**Now my question**: Has there been any work on how this technique could be implemented in an object oriented language, where much functionality is implemented through indirect calls using pointers in a virtual table?

# Answer
> 7 votes
Like Häagen-Dazs ice-cream, Object Orientation comes in many flavor, though with more nuts and bananas. Hence it is hazardous to answer your question stated in very general terms. Specific OO languages could have unexpected features that might raise problems with virtual methods. I fear that trying to imagine what kind of features could make things go wrong is a bit of a fruitless exercise. It is better to try answering precise questions.

The basic principle of tag-free GC is that, at any time, you should be able to inspect the memory starting from the stack, and know the actual type of all chunks of live allocated memory (because that is precisely what the GC will need to work). This implies also to know, at each call point of a function/method, the current state of activation block of the caller, whether on the stack or on the heap, i.e. the current variables of the block and their state of initialisation. The necessary structural information can be stored as data descriptors to be interpreted, or as executable *gc-routines* for better GC efficiency. The important point of tag-free GC is that this information can be determined statically, in order to be stored once with the code rather than with each instance of a type or class or of function activation. When this information can change dynamically, as is the case with polymorphic types, it must be possible to compute it by tracing and compounding static type information through the dynamic call sequence.

The fact that a method is virtual and called through a virtual table is not in itself a problem. **A caller does not need to know what it is calling as it has no importance regarding GC for its own activation record**. The callee is supposed to know itself (the compiler sees to it), and carry whatever information it need. The information may be incomplete as in the case of polymorphism, and must be completed from other type information available in the call sequence. Actually, in a language like ML, where functions can be passed as parameters, or put in tuples, the caller may not know what function it is actually calling.

**What matters is that the caller knows where in its code it calls the callee, so as to determine the state of its activation block during the call. This is statically dependent on the call point, and can thus be inferred from the callee return address**,(in various ways depending on technical variations used by different authors). The corresponding `gc-routine` can thus be found in some way from that return address. For example, it can be in the code right after the call, but other equivalent techniques could be considered. So if the callee is interupted by GC, it will be possible to do the GC for the callers activation record. **The caller does no GC work for the callee, only for its own activation record.**

*What may be a problem* is making sure that the callee does know the actual type of all the values that are passed to it (as in polymorphism). More precisely, it must be possible to find that information when the GC occurs and must deal with the activation record of the actual method that is access through a virtual.

I believe that being more precise on this last issue is dependent on the actual features and classe/objects structures of the OO language, on its typing organization.

But, as the caller does not need to know the callee, I do not see that indirect calls can be a problem.

Another point (answering the OP's comment) is that the issue here is not whether GC is performed from compiled code or interpreted from descriptors, but whether it needs dynamic tag for type information.

**Suggestion**: to find more work on this, take your favorite search engines (and other web resources) and look for papers citing the Goldberg papers or its mains references. Apply the procedure recursively, adding occasional keywords such as *object oriented* or *virtual*.

---
Tags: programming-languages, compilers, memory-management, empirical-research, garbage-collection
---


# Question
Title: Doubt regarding Maximum Bipartite Matching
I was given this question by a friend:

"*You are given 3 sets of size n, X,Y and Z. Devise an algorithm to find maximum number of different pairings (u,v,w,x) such that u,v,w,x belong to X,Y,Z and X respectively (u is not equal to x) and gcd(u,v,w,x)\>1.*"

My approach is to create new sets S and T, such that S contains pair (u,v) (create a node A) with gcd(u,v)\>1 and T contains (w,x) with gcd(w,x)\>1 (node B). If gcd(u,v,w,x)\>1 add an edge between A and B. Now find maximum matching in this bipartite graph.

But he isn't satisfied and says I didn't use the gcd property and the problem can be reduced significantly. Can this algorithm be improved?

# Answer
Here's one possible hint:

$$\gcd(u,v,w,x) = \gcd(\gcd(u,v),\gcd(w,x)).$$

I expect your problem can also be solved using the techniques in the following paper:

---

A maximal matching doesn't seem like the right approach. The maximal matching algorithm you list will never choose two 4-tuples $(u,v,w,x),(u',v',w',x')$ such that $(u,v)=(u',v')$. Thus, it won't produce the correct answer to the problem: it won't output the maximum number of different 4-tuples.
> 4 votes

---
Tags: graphs
---


# Question
Title: Does the performance of matrix multiplication depend on the storage of the array?
Two matrices can be stored in either row major or column major order in contiguous memory. Does the time complexity of computing their multiplication vary depending on the storage scheme? That is, I want to know whether it will work faster if stored in row major or column major order.

# Answer
> 6 votes
The *asymptotic complexity* will not change with relation to how the matrices are laid out in memory, but the actual running time of the matrix multiplication will be *very* dependent upon the memory layout. There are two papers that I know of that go into detail about this, one by McKellar in 1969 and another by Prokop in 1999. Prokop's paper defines the concept of *cache complexity* which is related to the number of cache misses the algorithm will incur.

The two papers can be found here: http://supertech.csail.mit.edu/papers/Prokop99.pdf and here: http://dl.acm.org/citation.cfm?id=362879

The short version is, an $O(n^3)$ algorithm will still be an $O(n^3)$ algorithm (assuming you are using the straightforward matrix-multiply). However, by taking into account the memory hierarchy of the system, you can significantly speed up that $O(n^3)$ algorithm.

# Answer
> 5 votes
No, the complexity remains the same.

The main difference between row-major and column-major order is memory access patterns - for example if you iterate by column then row-major order would be jumping around memory, which is bad for CPUs because they cannot read-ahead/cache memory.

This is because transferring data from RAM to the CPU on modern processors is relatively very slow, compared with the speed of the processors. Thus most of the time would be spent on waiting for the memory to arrive.

To solve this problem, memory accesses are answered in in bunches, with a lot of extra data coming to the CPU's caches. This makes it important to use "good" memory access patterns, so that the machine can try and predict what you will use next, and therefore cache it, and thus eliminate the transfer-wait-times as much as possible. But if you jump around memory instead of going in order, the machine will potentially have to wait for each access.

The wait time is bounded by a constant however, so the complexity remains the same. And of course, doing it in the correct order does not decrease the complexity.

# Answer
> 2 votes
It depends on the machine model you're using.

In the RAM model, which is probably the most commonly used one, the complexity is the same regardless of the layout being row-major or column-major.

In the IO model, where you're counting how many times the algorithm must read a block of size `B` into a cache of size `M`, it does matter. (For example, in the IO model sorting is not `N lg N`; it's `N/B lg_M N/B`.) For matrices that don't fit into the cache, iterating the entries in the wrong order costs `n^2` instead of `n^2/B`.

Algorithms that perform well in the IO model, without relying on the specific values of `B` or `M`, are called cache oblivious.

---
Tags: algorithms, time-complexity, storage, multiplication
---


title: Efficient algorithm to find subgraph

text:
# Question
Title: Efficient algorithm to find subgraph
I have a really nasty problem (for me) at hand and I was wishing some of you may know an efficient algorithm to solve it. Thanks to all of you in advance.

---

## My problem

I have a set of elements (that I would describe as a graph) that may be of three categories:

* Provider nodes
* Consumer nodes
* Interconnections between nodes

Each node can have one or more interconnections tied to it.

My goal is to correlate each consumer to a set of providers to whom is connected, both directly through an interconnection or indirectly through multiple hops from one consumer to the other. Indirect interconnections can't go through a provider, only a consumer.

Our current approach is to analyze this graph starting with providers, hopping through interconnections recursively until a all unvisited consumers are hit. We then take this "island" of consumers bordered by a set of producers and assign these producers to each consumer we visited.

The approach gave us the right results but at a very high cost, in terms of time spent analyzing the graph.

Do you have any suggestion for an algorithm that can come in handy to solve this problem? I would also consider alternative data structures to hold our input (right now they are a set of tuples in a relational database describing the correlation between nodes and interconnections).

# Answer
OK, it sounds like your problem is the following:

> You have an undirected graph. Each vertex is either a consumer or a producer. Say that a consumer $c$ is connected to a producer $p$ if there is a path from $c$ to $p$ where all intermediate nodes are consumer nodes. You want to output a list of pairs $(c,p)$ where $c$ is connected to $p$.

This problem can be solved in a straightforward, clean, and efficient manner, using an algorithm for connected components. Here is the algorithm:

1. Remove all of the producer nodes, keeping only the consumer nodes and the edges from a consumer node to a consumer node.
2. Compute connected components on this smaller graph. Let the connected components be $C\_1,\dots,C\_k$.
3. Now, back in the original graph, shrink all of the consumer nodes in the same connected component into a single node. Thus, we get an edge from connected component $C\_i$ to producer $p$ if there is any consumer $c$ in $C\_i$ that has an edge to $p$.
4. This resulting graph now describes the connectivity relationship. In particular, for each consumer $c$ and each producer $p$, $c$ is connected to $p$ if and only $C\_i$ has an edge to $p$, where $C\_i$ is the connected component containing $c$.

For instance, to output the list of all pairs $(c,p)$ that are connected, you can do the following:

* For each connected component $C\_i$, for each provider $p$ that has an edge from $C\_i$ to $p$, for each consumer $c$ in $C\_i$, output the pair $(c,p)$.

This algorithm runs in linear time. The running time to compute the connectivity graph (produced in steps 1-3) is $O(m+n)$, where $n$ is the number of nodes and $m$ is the number of edges (interconnections) in the original graph. The running time in step 4 could be as large as $\Theta(n^2)$, since there might be as many as $\Theta(n^2)$ such pairs. However, here's what we can say. If the correct output has length $\ell$ (i.e., there are $\ell$ pairs $(p,c)$ that are connected), then step 4 will have running time $O(\ell)$.

Therefore, the total running time is $O(m+n+\ell)$, i.e., linear in the sum of the size of the input and the size of the output. This is as fast as you could possibly hope for.

If you don't need to output the set of all pairs $(c,p)$ explicitly, but you just want a compact representation of this connectivity information, you can use the graph computed in steps 1-3 as that compact representation. Then the running time is $O(m+n)$.
> 5 votes

# Answer
I can't tell if my answer will be applicable because the question is not precisely defined. But let me make some guesses here:

**Input** graphs with 2 types of vertex.

1. Provider node (P)
2. Consumer node (C)

The edges are **constrained** by:

1. (P) can connect to (C)
2. (C) can connect to (C)
3. (P) can not connect to (P) (or we just don't care if they're connected)

We say that a producer $p \in P$ **can reach** $c\_\* \in C$ denoted with $p \rightarrow c\_\*$ if:

> there is a path starting from $p$ then going through **customers only** $c\_1,c\_2,\ldots,c\_\* \in C$ ending at $c\_\*$.

You **might be interested** in the questions:

1. Given a $p \in P$, find $C\_p = \\{c \mid c \in C \text{ and } p \rightarrow c\\}$. (The set of consumers reachable from $p$)
2. Given a $c \in C$, find $P\_c = \\{p \mid p \in P \text{ and } p \rightarrow c\\}$. (The set of providers that can provide for $c$)

EDIT: see D.W.'s answer for calculation.
> 3 votes

# Answer
(am going to take a stab at this with the partial information at this point & possibly modify it on further clarification by questioner.) the Djikstra shortest path algorithm (which basically adds the shortest weighted new edges in the "frontier set") can be run in parallel across multiple starting nodes (but havent seen a ref to this). it sounds like that would give you close to what you want. the starting nodes in your case are the providers. as the edge/vertex set expands, this will eventually "touch" all consumers, and the shortest path to any provider from any consumer can be calculated.
> -1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Why doesn't Knuth's linear-time multiplication algorithm "count"?
The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. Basically, it involves combining fourier-transform multiplication with a precomputed table of logarithmically-sized multiplications. It runs in linear time.

The article acts like this algorithm somehow doesn't count as a "true" multiplication algorithm. More significantly, it's considered to be an open question whether multiplication can be done in even `O(n lg n)` time!

What details of this algorithm disqualify it from counting as a "true" multiplication algorithm?

My guesses are:

* Precomputing the table takes more than linear time. On the other hand, it can still be done in `n lg n` time so that would still seem to be impressive.
* Random access is somehow not allowed. But then why can other algorithms use things like hash tables and pointers?
* It somehow scales wrong as you increase a machine's word size, like if you have a 256 bit machine that does 256 bit multiplications in a single instruction then there's no point to this algorithm until you have more than 2^256 elements. On the other hand, we bother with the inverse-ackermann factor in union-find.
* The "is there a linear time multiplication algorithm?" question is secretly in terms of some weaker machine, but this only gets hinted at.

# Answer
While the algorithm you mention appears in Knuth's TAOCP, it is certainly not due to Knuth, and is more widely known as the Schönhage–Strassen algorithm; Knuth even attributes this algorithm to them in the text. This algorithm indeed runs in linear time in the so-called *RAM machine*, in which variables are allowed to hold integers of size $O(\log n)$, where $n$ is the size of the input. The bit complexity is, however, $O(n\log n\log\log n)$, and for this model, Fürer's algorithm is faster.

The quest for fast integer multiplication algorithms in the literature has concentrated on bit complexity as the complexity measure; this is like allowing your registers to hold only one bit (or only $C$ bits for some arbitrary constant $C$). It is expected that integer multiplication takes $\Omega(n\log n)$, though it's not clear whether this should be tight, and no non-trivial lower bounds are known (so this $\Omega(n\log n)$ is just a conjecture).

For a discussion of the "correct" model for practical multiplication of large integers, check Fürer's recent paper. His conclusion is in favor of the "practical" Schönhage–Strassen algorithm (there are two of them, and the other one has better bit complexity but performs worse in practice; Fürer addresses this issue in the paper).
> 18 votes

---
Tags: algorithms, runtime-analysis, multiplication
---