# Question
Title: Will the future quantum computers use the binary, ternary or quaternary numeral system?
Our current computers use bits, so they use the binary numeral system. But I heard that the future quantum computers will use qubits instead of simple bits.

Since in the word "qubit" there is the word "bi" I first thought that this meant that quantum computers would use binary (base 2).

But then I heard that qubits had three possible states: 0, 1, or a superposition of 0 and 1. So I then thought that this must mean that they will use ternary (base 3).

But then I saw that one qubit can hold as much information as two bits. So I thought that this maybe mean that they will use quaternary (base 4).

So which numeral system will the future quantum computers use: binary, ternary or quaternary?

# Answer
> 18 votes
The other answers are nice, but none address the question: what numeric base(s) might quantum computers use? I will answer in two parts: first, the question is a little subtle, and second, you may use any numeric base, and then you work with qutrits or in general with qudits, which lead to qualitatively new intuitions! Or at any rate, I will try to make the case that they do.

A quantum bit isn't just a $0$ or a $1$, it's a bit more complex than that. For example, a quantum bit may be in the state $\sqrt{\frac{1}{4}}|0\rangle+\sqrt{\frac{3}{4}}|1\rangle$. When measured, you will measure the outcome $0$ with probability $\frac{1}{4}$ and the outcome $1$ with probability $\frac{3}{4}$. The 'superposition' you talked about is $\sqrt{\frac{1}{2}}|0\rangle+\sqrt{\frac{1}{2}}|1\rangle$, but in general any pair of complex numbers $a$ and $b$ will do, as long as $a^2+b^2=1$. If you have three qubits, then you can entangle them, and the state will be

$$a\_0|000\rangle + a\_1|001\rangle+a\_2|010\rangle+a\_3|011\rangle+a\_4|100\rangle +a\_5|101\rangle+a\_6|110\rangle +a\_7|111\rangle$$

But when you measure this three-qubit system, your measurement outcome is one out of these 8 states, that is, three bits. This is this really weird dichotomy where on the one hand quantum systems seem to have this exponential state space, but on the other hand we only seem to be able to 'get at' a logarithmic part of the state space. In 'Quantum Computing Since Democritus', Scott Aaronson probes this question by matching off several complexity classes to try and understand how much of this exponential state space we can exploit for computation.

Having said that, there is an obvious complaint to the answer above: all the notation is in binary. Qubits are in a superposition of *two* base states, and entangling them doesn't change that much, because three qubits are in a superposition of $2^3$ base states. It's a legitimate complaint, because one usually thinks of $\texttt{unsigned int}$ as a number, and only remembers that it is implemented as a 32-bit string as an afterthought.

Enter the qutrit. It is a vector in $\mathbb{C}^3$, in other words, it consists of *three* base states rather than two. You operate on this vector with a $3\times 3$ matrix, and all the usual things done in quantum computing don't change much, because any operation expressed in terms of qutrits can be expressed in terms of qudits, so it's really just syntactic sugar. But some problems are much easier to write down and/or think about when expressed as qudits instead of entangled qubits. For example, a variation of the Deutsch-Josza problem might ask, given an oracle for a function $f\colon \\{0,\ldots, kn-1\\}\rightarrow \\{0,\ldots, k-1\\}$, is this function constant or balanced, given that one is promised to be the case? This function naturally takes one $k$-qudit register as input. To solve it, you must apply a Fourier transform to this $k$-qudit, like so: (if this goes over your head, don't worry, it's just for illustration)

$$|a\rangle \mapsto \sum\_{u=0}^{k-1}e^{i2\pi\frac{au}{k}}|u\rangle$$

If you want to express this in binary, you end up with a gate that does this on numbers $0\ldots k-1$ and acts trivially (does nothing) on all numbers $\geq k$, which is slightly less contrived than doing it this way. Similarly, consider a Bernstein-Vazirani variation where the oracle computes an in-product in some radix $r$. If $r=2$, then we know how to do it. But if $r=5$, the problem is much easier to solve by hand using several $5$-qudit registers. Some problems are easier if you have several different qudit registers, e.g. one $5$-qudit register and one $2$-qudit register.

In summary, yes, you are free to consider other numeric bases, and in the right setting that will make your life easier, for the same reason that thinking about numbers in terms other than their binary expansion helps you with normal computers. I felt compelled to answer because while most answers explained that a qubit has something to do with two base states when measuring but infinite in principle, no answer mentioned that the OPs suggestion of using other bases is legitimate and in fact really happens (for example, in Quantum walks on graphs, Aharonov et al. use a subroutine that takes a qubit and an $n$-qudit as input)

# Answer
> 3 votes
Quantum computers use binary. But really, this is a simplification, and there is no simple answer of how quantum algorithms work that don't get into the mathematics of quantum physics and quantum computation. The best way for you to understand this subject area is to start by studying quantum computation. There are many excellent textbooks and tutorials out there.

Whoever told you that qubits have 3 possible states, was wrong. That's not quite how quantum mechanics works. In some sense there are infinitely many possible states... but read about quantum computation to learn the real story.

# Answer
> 2 votes
Bits are bits, i.e. entities that can have only one of two states, usually noted $0$ and $1$.

Quantum computing uses qbits (I suppose it stands for quantum bits). Qbits allows "superposed" bits, i.e. entities that can sort of hold several bits in the same place, theoretically (according to current state of knowledge) an unbounded number of bits.

You can easily infer from this that the number of states of a qbit is actually any power of two. But those states cannot be used exactly the way you use states in usual automata theory (where you can encode states as bit strings when you have more than two). You must see them more as representing several separate but coexisting bits on the same support, that are simultaneously computed on in a parallel computation. So this idea of seeing them as states, or as representing a digit in an alphabet of size $2^n$ is actually misleading. Understanding it as parallel computations executed simultaneously (superposed) on a single piece of hardware (single core CPU, if you will) is probably closer to what happens (as much as I understand it).

So it does stay in a binary system, albeit one that has different physical properties.

But I strongly suggest you follow the advice of D.W. and look at books and tutorials.

# Answer
> 1 votes
The state space of a qubit is described by a column vector $(a\ \ b)^T$ of $\mathbb C^2$ with norm equal to 1. Thus, there are uncountably many different states even a single qubit can have.

However, the above is not very useful for fault-taulerant quantum computing which is what you would need if you actually want to program anything on an existing quantum computer. Under that model, you would not be able to prepare arbitrary qubits (in the above sense), however any qubit state may be approximated with arbitrary precision. Thus, you would still have infinitely many states even for a single qubit, but they will be countably many (compared to the other case).

In both cases, you may consider the basis states to be $|0 \rangle$ and $|1\rangle$ which are just special states in $\mathbb C^2.$ Then, any other single-qubit state may be described as a superposition (simply, a linear combination in the algebraic sense) of these two states (which can be prepared by applying operations which are allowed in your model of computation).

# Answer
> -3 votes
Quantum particles can be in four states. They can spin up, down and be right or left-handed. If you are measuring particles that are entangled, when you measure them they will be in some combination of those four states. If we could some how predict or use a eraser of some kind, it would seem like a good idea to use quarternary rather than binary. As it stands right now, binary is being used but in the future something different will likely take the place of binary. Quantum computers are like classical computers were in the 50s, they are HUGE, expensive and not practical. In fact they are hardly useful at this time. We still struggle with decoherence. The hope it to identify a topological quantum particle that can maintain coherence (is robust) and if that day comes, look out! The revolution with take off like a rocket. To be honest no one can tell you with certainty what Q-computers will be like in the future became when singularity occurs (about 30 years from now) all bets are off. No one can tell you what will happen past that point. Computers could take off in directions we have not even dreamed about.

---
Tags: computer-architecture, quantum-computing, numeral-representations
---


# Question
Title: Does there always exist equivalent (M)(I)LPs with and without objective functions?
For computing pure Nash equilibria (game theory), there exists a MILP method in literature (clicky).

In the proposed MILP, there is no objective function. A solution is a pure Nash equilibrium if it is a feasible solution of the MILP.

Should there, in theory, exist an equivalent MILP **with** an objective function so that a solution is a pure Nash equilibrium if the objective function is minimized/maximized (e.g. equal to 0). Such MILP would be useful in this context as to still have an approximation if there exists no feasible solution in the first 'objective function-less' MILP (i.e. there exists no pure Nash equilibrium).

I gave context to the question but the question is general: for a (M)(I)LP without an objective function, is there always a reduction from and to a (equivalent) (M)(I)LP with an objective function? Can such reduction be done in polynomial time?

# Answer
Yes (assuming you truly did mean "if" rather than "if and only if").

Add any objective function you want (e.g., 1, or the sum of the variables, or anything), then feed it to a MILP solver and see whether it returns 'Feasible' or 'Infeasible'. Then the resulting MILP is feasible if and only if the original MILP was feasible. Any optimal solution to the resulting MILP is feasible and thus also a feasible solution to the original MILP problem, and consequently represents a valid pure Nash equilibrium.
> 2 votes

---
Tags: reductions, linear-programming
---


title: Specific case of a ranking model

text:
# Question
Title: Specific case of a ranking model
So the problem I'm solving is this: I have a list of conversations of 3 messages each (for eg. "hi", " how are you", "remind me to fix this bug" is one conversation, and my problem will have many of these) and need to pick out the message that is most likely to be a task ("remind me to fix this bug" would be the message in the conversation above; "don't forget to commit your code" would be another in some other conversation). What kind of machine learning/NLP model could I use to relatively rank the messages in a conversation and "learn" across conversations? And what would my training data look like?

My thoughts: each data point in the training data is one conversation (a set of 3 messages) along with the message with the highest likelihood of being a "task." I was thinking of using a linear weighted function of features such as TF-IDF score. But how would I learn the weights?

# Answer
Build a boolean classifier that classifies a message as either "task" or "not a task". Choose a classifier that can output a confidence score (many classifiers can, including ensembles like random forests; neural networks and deep learning; logistic regression; and more).

Train the classifier on many messages.

For a collection of 3 messages, apply the classifier to each message and get the confidence score. Then, use the confidence scores to rank the 3 messages: e.g., choose the message that has the highest confidence/probability of being "task" as the one that is most likely to be the task.

This is different from what you had in mind: here each instance is a *message*, not a *conversation*.

Which features to use is a separate question, but you'll probably want to use standard NLP features (bag of words, word2vec, and so on). That belongs in a separate question. As a warning, if each message is very short as indicated in your example, the performance of your classifier might not be great.

Also, you will need a large collection of messages where you know the label (classification) of each.
> 3 votes

---
Tags: machine-learning, natural-language-processing
---


# Question
Title: The longest subarray sum divisible by $5$ in $O(n)$ time
> Given an array of non negative integers Find the longest continuous sub array which it's sum is divisible by 5.

For example if the array is: \[1,3,9,2,1,5,0,1\]

A continuous subarray which it's sum is divisible by 5 for example is: \[3,9,2,1\]

The longest one will be: \[3,9,2,1,5, 0\]

So the output will be 6.

It is obvious that a simple algorithm for this will be to just run over all the continuous subarrays and check the one with the biggest size but it will be $O(n^2)$. Is there an algorithm in $O(n)$ time which will solve this one?

# Answer
> 3 votes
As hinted by @Mihai Calancea in the comments, you can

1. Compute prefix sum@wiki of the original array.
2. Mod 5 ($\\%5$) over the new prefix sum array (credited to @EvilJS).

> 3. Find two same remainders that are farthest apart.

Please fill the details and figure out why each step can be done in linear time.

---
Tags: algorithms, arrays, maximum-subarray
---


# Question
Title: How are games like chess provably harder than NP?
From this question, I had the debate about how problems harder than NP are proved.

I said that intuitively I understand it as (from this video explaining that some problems are provably harder than NP):

> Generalized chess is harder than NP, and is EXPTIME-complete for the decision problem "Given an nxn board with a given position, can white force a win?" because the proof would require an exponential amount of steps to show that each branch of the tree eventually leads to a win. Therefore it's not in NP.

And a user replied:

> Your first paragraph is faulty. It has the form "because this one algorithm I thought of takes exponential time, the problem must not be in NP". That's faulty -- maybe there's some other algorithm you haven't thought of that's better.

I'll admit I'm still new at this and the user that wrote the above comment has much more experience in the field than I do. So I trust this user is correct. However, the explanation the video gave seems very intuitive. But can anyone explain why the video's explanation is wrong?

My thought process is as-follows. One of the definitions of NP is "the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes"." So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to do this, the verifier must check every single possible branch of the tree of moves to check that each one leads to a forced win. This cannot be done in less than exponential time and thus is provably harder than NP.

# Answer
> 5 votes
The fault lies in this statement:

> So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to do this, the verifier must check every single possible branch of the tree of moves to check that each one leads to a forced win.

The second sentence *might* be right, but it might not. Perhaps there is a cleverer, faster way that the verifier can check a certificate, or a cleverer format for the certificate that makes it easy to check. How do we know that's impossible? We don't. That would need proof.

The argument has made an assumption about how a verifier "would have to" behave, without substantiating or proving that assumption. This is basically an argument from failure of creativity: "I can't think of any other strategy a verifier could plausibly use, so there must not exist any valid strategy". Needless to say, this is not a persuasive form of argument.

---

For instance, let me give you an example. Suppose we replace "generalized chess" by "generalized tic-tac-toe", which works as follows: we have a nxn game board, and the first person to get three in a row wins. Try working through the same argument. It's tempting to draw the same conclusion, that generalized tic-tac-toe is NP-hard. But there are reasons to doubt that conclusion: for instance, this form of generalized tic-tac-toe is always a first-player win when you start from the empty board, for all $n\>3$.

There are better examples. In particular, there are games where there are in fact polynomial-time algorithms to play optimally, but the algorithm/strategy is not at all obvious, and if you weren't already aware of it, you might be inclined to be persuaded by the above reasoning that the game is NP-hard. Examples include Nim, Brussels Sprouts, and Wythoff's game. This illustrates that the line of reasoning can't possibly be right -- it leads you to draw conclusions that are false.

# Answer
> -3 votes
Usually running time analysis is applied to algorithms, not applications. It is possible there is some as-yet undiscovered algorithm that solves chess in polynomial time.

The reference to chess being "NP complete" assumes a tree-search algorithm, such as minimax, is being used. Brute force minimax runs in exponential time. For example, even if there are only two choices every move, then the size of the tree is a $2^N$ where N is the number of moves. Exponential running time is considered non-polynomial. (a polynomial algorithm has a running time $a\_1N^b + a\_2N^{b-1} + a\_3N^{b-2} + ...$, where a and b are constants).

---
Tags: complexity-theory, time-complexity, np-complete, np, nondeterminism
---


# Question
Title: Can Quantum Computing solve Problems not even a Turing Machine can solve?
In his book "The Fabric of Reality", Penguin Books 1998, p. 218, David Deutsch says that the first quantum computer (built 1989 in the office of Charles Bennet, IBM Reasearch) "*became the first machine ever to perform non-trivial computations that no Turing machine could perform*".

My question: Do we really know that quantum computing is powerful enough to solve problems that not even Turing machines can solve? (Or is this just a personal belief of David Deutsch?)

# Answer
> 40 votes
While it is true that the computation of a quantum Turing machine is vastly different from that of a classical one, nevertheless quantum Turing machines can be simulated on a classical Turing machine, albeit with exponential slowdown. In particular, everything that can be computed on a quantum Turing machine can also be computed on a classical Turing machine.

The main advantage of quantum Turing machines is that they appear to solve some problems much faster than classical Turing machines. As Sasho comments, at the moment we can't quite prove this, yet this advantage is believed to hold by most researchers.

For more, check out this talk by Ashley Montanaro.

# Answer
> 19 votes
**There's no difference in terms of computability**. Classical computers can simulate quantum computers. A Turing machine can compute anything that a quantum computer can compute.

This isn't some hypothetical point, we simulate quantum computations all the time. You can do it with pen and paper! It's a lot more convenient using one of the many software simulators that already exist, though. There's even toy ones that run in your browser.

To me, your David Deutsch quote is referring to the *style* of computation that was used, as opposed to some inaccessible aspect of the problem. He managed to phrase it terribly.

---

All that being said, be aware that **there is a difference in efficiency**. Although a Turing machine can simulate applying Shor's algorithm to a thousand digit number, doing so would take too long to be practical. The universe would die out before you finished.

(There are also other practical uses for quantum computers, like improving the resolution of sensors, but I think mostly people are interested because of the existence of a few key takes-too-long-to-simulate problems and algorithms.)

# Answer
> 5 votes
In terms of computability, quantum computers provide no advantage -- anything which can be computed by a quantum computer may be computed by a classical computer, because as Yuval pointed out, classical computers can simulate quantum computers.

In terms of complexity, there are advantages for some problems. For example, the Deutsch-Josza algorithm is (provably) exponentially faster than any classical algorithm. Grover's algorithm provides a quadratic speedup compared to any classical computer, again this has been proved. However, the precise complexity relationship between classical and quantum computing is not known.

# Answer
> 0 votes
As far as we believe, a quantum Turing machine is able to simulate any quantum computer, and it is also equivalent to classical deterministic Turing machine in terms of computability. In other words, as far as we know the space of problems solvable by quantum computers is the same as space of problems solvable by classical computers.

However, if we consider practical computability, things may look a bit different. Imagine a problem where we have a classical solution which runs with $O(2^n)$ complexity. It is definitely solvable, but for any reasonable data size it will require massive amounts of operations. In practice, it will run for thousands of years, even on the fastest computers. Now imagine we have a quantum algorithm solving the same problem, but with $O(n)$ complexity. Out of a sudden, exact same problem can be solved in minutes, which is very reasonable (especially compared to thousands of years).

I think the original quote could be extended by adding "in any reasonable time", and we get a fair statement.

# Answer
> -1 votes
In the generality that your question is asked, the answer is YES. Quantum computation is a very wide concept. Even in non-quantum computation there are many models that go beyond Turing computability. The field is sometimes called hypercomputation. A (in my opinion) nice model are red-green Turing machines by J. van Leeuwen and J. Wiedermann. With them you can climb up several steps in the arithmetical hierarchy. A more classical model are oracle machines.

You can define the same approches with Quantum Turing Machines, and then they compute more than a Turing machine. So again, the answer is YES, but also non-quantum models can do that.

If you only want to compare TMs to quantum TMs (which both compute only the Turing-computabel) or some other model of quantum computation, then you should refer to that model explicitly.

---
Tags: quantum-computing, computability
---


# Question
Title: Question about set-associative cache mapping
I found a question:

> Let a two-way set-associative cache of 4 memory blocks, each block containing one word.
>
> What is the number of misses and hits considering the following sequence of block addresses: 0, 8, 0, 6, 8 ?
>
> a) 4 misses and 1 hit
> b) 3 misses and 2 hits
> c) 1 miss and 4 hits
> d) 2 misses and 3 hits

Although I understand how set-associative cache mapping works, I don't understand how can you tell if it will be a hit or a miss if you don't know the tags and what is stored on the cache memory.

Can you please point me in the right direction? How should I think about this problem?

# Answer
> 2 votes
You're absolutely right: the question is unanswerable as stated because you don't know what's in the cache at the start of the sequence of memory accesses. You're probably expected to assume that the cache is initially empty but, if this is an exercise you've been set, you should ask your instructor to clarify.

# Answer
> 1 votes
Even I have faced this kind of question in some comparative exams and can be solved with some assumptions.

*Assume:* Cache is empty

**Solution:**

2-way set associative with 4 blocks (empty cache) gives

```
╔═══════════════╗
║     Cache     ║
╠═══════╤═══════╣
║ Set 1 │ Set 2 ║
╟───────┼───────╢
║   -   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╚═══════╧═══════╝

```

Input : 0, 8, 0, 6, 8

Inserting one by one

Inserting : 0 (cache miss)

0 % 4 = 0 (goes to Block 0 Set 1)

```
╔═══════════════╗
║     Cache     ║
╠═══════╤═══════╣
║ Set 1 │ Set 2 ║
╟───────┼───────╢
║   0   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╚═══════╧═══════╝

```

Inserting : 8 (cache miss)

8 % 4 = 0 (goes to Block 0 Set 2)

```
╔═══════════════╗
║     Cache     ║
╠═══════╤═══════╣
║ Set 1 │ Set 2 ║
╟───────┼───────╢
║   0   │   8   ║
╟───────┼───────╢
║   -   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╚═══════╧═══════╝

```

Inserting : 0 (cache hit)

0 % 4 = 0

```
╔═══════════════╗
║     Cache     ║
╠═══════╤═══════╣
║ Set 1 │ Set 2 ║
╟───────┼───────╢
║   0   │   8   ║
╟───────┼───────╢
║   -   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╚═══════╧═══════╝

```

Inserting : 6 (cache miss)

6 % 4 = 2 (goes to Block 2 Set 1)

```
╔═══════════════╗
║     Cache     ║
╠═══════╤═══════╣
║ Set 1 │ Set 2 ║
╟───────┼───────╢
║   0   │   8   ║
╟───────┼───────╢
║   -   │   -   ║
╟───────┼───────╢
║   6   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╚═══════╧═══════╝

```

Inserting : 8 (cache hit)

8 % 4 = 0

```
╔═══════════════╗
║     Cache     ║
╠═══════╤═══════╣
║ Set 1 │ Set 2 ║
╟───────┼───────╢
║   0   │   8   ║
╟───────┼───────╢
║   -   │   -   ║
╟───────┼───────╢
║   6   │   -   ║
╟───────┼───────╢
║   -   │   -   ║
╚═══════╧═══════╝

```

**Answer** : 3 misses and 2 hits (option B)

---
Tags: cpu-cache
---


# Question
Title: Where does the process reside in memory?
When a program runs in CPU, it turns into a process. In what kind of data structure is the **process** stored in a system memory?

In *Heap* or *Tree* or some other data structures?

# Answer
> 3 votes
A process is not a single data structure. In the Windows operating system, for example, a running process has a number of different structures in its memory including a copy of its PE header and its environment variables. Here is a table from a debugger showing the layout of one process after it has been loaded into memory:

The various pieces of data have different structures. For example, the PE header is a record, but the heap is usually some kind of tree or list.

---
Tags: data-structures, operating-systems, memory-management
---


title: L1 and L2 cache

text:
# Question
Title: L1 and L2 cache
I cannot find a to-the-point reference for my question. Am I correct in assuming that if you have an L1 and an L2 cache, typically the L2 cache linesize is larger?

For the following, let's assume a word size of 1 byte, an array 'a'of one byte words, an L2 cache with blocksize of 8 bytes, and an L1 cache of 4 bytes.

So, if you try to access an element a\[2\] in an array, given that both caches are cold, then a\[0\] - a\[7\] will be transferred to L2, and then a\[0\] - a\[3\] will be transferred to L1, and then a\[2\] can be sent to the register?

# Answer
> *The cache line size is 64 Bytes. The size of the last-level cache varies a lot: 4MB per 2 Cores for Intel Core2 processor QX6850 and Intel Xeon processor 5300 series, 6MB per 2 Cores for Intel Core2 processor QX9770 and Intel Xeon processor 5400 series, 8MB per 4 cores for Intel Core i7-965 and Intel Xeon processor 5500 series.*
>
> Source: Intel forums

You can also find few details here about Intel processors cache line size.
> -2 votes

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


title: Algorithm for antialiasing thin lines

text:
# Question
Title: Algorithm for antialiasing thin lines
A very tricky problem in graphics rendering is drawing thin lines ($1px$ width) that do not look jaggy. The only implementation I have seen that is very good is that in Mathematica, but their algorithm is proprietary.

Is there a well known algorithm for anti-aliasing thin lines?

# Answer
> 4 votes
You can use Xiaolin Wu algorithm, but the concept is not restricted to straight lines, it handles circles, ellipses, any kind of functions. Moreover this is concept of fast antialiasing, if you need some polyline you have to apply it for every segment. If you meant curves, these are locally flat segments, so this concept is still applicable.

The *thin line* might described $1px$ lines, but if you need thinner width (less than $1px$) the common algorithm that comes to mind is Gupta-Sproull, which is not that common due to computation time. The same is applicable here like in the Wu case, it is not limited to straight lines.

The idea of drawing lines (probably with Bresenham) and then blurring is more computationally expensive and weights are not normalised, which gives feeling of thicker lines.

The concepts described can easily be extended to thicker lines (using Bresenham and applying antialiasing to the outter layer) or even varying width lines (with Bresenham extension - the Murphy algorithm).

Techniques like MSAA or FXAA are too expensive, unless implemented on GPU with a lots of lines and no concern about perceptible width. *After reading about Mathematica, it uses MLAA (Morphological Anti-Aliasing), graphics is rendered on GPU, also Mathematica's reference supports this statement merely by looking at de Moiré patterns.*

# Answer
> 2 votes
Not really an answer, but I've had an ongoing similar problem with my gpl'ed program http://www.forkosh.com/mimetex.html and tried several solutions, all of them variations on low-pass filter antialiasing or supersampling. My code's buried in the 20K lines of mimetex.c, which you can see by clicking the "mimeTeX listing" link under "Related Pages" on the top left-hand side of the preceding link. In particular, line 16060 starts a switch() that currently selects case 3.

That case is loosely based on http://netpbm.sourceforge.net/doc/pnmalias.html which is netpbm's antialiasing algorithm. But I messed with it, more or less as follows. Any pixel of a jaggy pixelized line image is surrounded by nearest neighbor pixels: by eight immediately nearest neighbors (it's the center pixel of a 3x3 grid), and by 15 two-deep nearest neighbors (near center of a 4x4 grid). If those nearest neighbors are either black or white, then that's $2^8$ or $2^{15}$ possible cases. I'd have preferred the 4x4 case, but that was too many cases to enumerate.

However, you don't even need $2^8$ since rotations and reflections of the grid yield self-similar patterns that you want to treat all the same way. And for the 3x3 grid, that left me 51 unique nearest neighbor patterns. And I just carefully tested the various ways of treating the center pixel of each such pattern (separate treatment depending on whether the center pixel started out black or white), and ad hoc selected what looked best to my eyes.

Then long lines of any shape just work themselves out as you antialias the overall image pixel-by-pixel. Note that I started out with jaggy-looking thin lines that were originally black&white, and turned them into somewhat less jaggy grayscale lines. But they're still jaggier than I'd hoped for, despite some non-trivial (to me) amount of effort.

Anyway, please let me know if you come across anything really good. And I'll keep watching this thread for a better answer than mine.

---
Tags: algorithms, graphics
---


title: Finding nfa or dfa for a language

text:
# Question
Title: Finding nfa or dfa for a language
I'm trying to study for the summer ahead of class I saw this question, please how do I go about it?

Find NFA/DFA for the language $L = \\{0^n1^n : n \in N\\}$

# Answer
> 4 votes
That language is not regular, thus no finite automaton, be it a DFA, NFA or εNFA, is sufficiently powerful to express it.

To express this language, you'll need a context-free grammar, a push down automaton, or a Turing machine.

# Answer
> 1 votes
This language has infinite index, thus needs an infinite number of states according to the Myhill–Nerode theorem. You can't have a finite state automaton for it.

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


# Question
Title: In a $k$-way set associative cache,main memory block mapping in range?
> In a $k$-way set associative cache, the cache is divided into $v$ sets, each of which consists of $k$ lines. The lines of a set are placed in sequence one after another. The lines in set $s$ are sequenced before the lines in set $(s+1)$. The main memory blocks are numbered 0 onwards. The main memory block numbered $j$ must be mapped to any one of the cache lines from:
>
> 1. $(j\text{ mod }v) * k \text{ to } (j \text{ mod } v) * k + (k-1) $
> 2. $(j \text{ mod } v) \text{ to } (j \text{ mod } v) + (k-1) $
> 3. $(j \text{ mod } k) \text{ to } (j \text{ mod } k) + (v-1) $
> 4. $(j \text{ mod } k) * v \text{ to } (j \text{ mod } k) * v + (v-1) $

---

My attempt:

Somewhere it explained as : Number of sets in cache = v. So, main memory block j will be mapped to set (j mod v), which will be any one of the cache lines from (j mod v) * k to (j mod v) * k + (k-1). (Associativity plays no role in mapping- k-way associativity means there are k spaces for a block and hence reduces the chances of replacement.)

> > Can you explain it in a formal way, please?

# Answer
> Number of sets in cache = v. So, main memory block j will be mapped to set (j mod v), which will be any one of the cache lines from ***(j mod v) * k to (j mod v) * k + (k-1)***. (Associativity plays no role in mapping- k-way associativity means there are k spaces for a block and hence reduces the chances of replacement.)

This is a simple concept of k-way set associate mapping.

To understand it better I would like to take an example:

**Example:**

* 2-way set associative
* 4 blocks
* Lines of a set are placed in sequence one after another (as in the
question)
* The main memory blocks are numbered **0** onwards (as in the question)

Empty 2-way set associative Cache Memory :

```
╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   -   │   -   ║
╟───┼───────┼───────╢
║ 1 │   -   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

```

Memory reference (data asked for processing) in the order:

4, 5, 9, 7

Reference 4:

4 % 4 = 0 (goes to Block 0 Set 1) **Cache miss** as it doesn't already present in the cache

As it had 4 blocks, we mod it the reference address to know which location of cache should I put it.

```
╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   -   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

```

Reference 5:

4 % 5 = 1 (goes to Block 1 Set 1) **Cache miss**

```
╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

```

Reference 9:

4 % 9 = 1 (goes to Block 1 Set 2) **Cache miss**

```
╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   9   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

```

Reference 4:

4 % 7 = 3 (goes to Block 3 Set 1) **Cache miss**

```
╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   9   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   7   │   -   ║
╚═══╧═══════╧═══════╝

```

Visualization of Cache memory for you undersatnding:

```
╔═════════════════════════════════════════════════════╗
║                    Cache Memory                     ║
╠════════════════╤════════════╤═══════════════════════╣
║ Memory address │ References │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       0        │     4      │                       ║
╟────────────────┼────────────┤ Cache line 0 elements ║
║       1        │     -      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       2        │     5      │                       ║
╟────────────────┼────────────┤ Cache line 1 elements ║
║       3        │     9      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       4        │     -      │                       ║
╟────────────────┼────────────┤ Cache line 2 elements ║
║       5        │     -      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       6        │     7      │                       ║
╟────────────────┼────────────┤ Cache line 3 elements ║
║       7        │     -      │                       ║
╚════════════════╧════════════╧═══════════════════════╝

```

Both of the two set of cache line 1 is full, therefore calculation the location of first and last element of line gives us the answer.

Lets now check if the answer is option (1) as you mentioned

> 1. ***(j mod v) ∗ k*** to ***(j mod v) ∗ k + (k − 1)***

Given:

v = 4 (four blocks)

k = 2 (two-way)

First element of cache line 1 = **(j mod v) ∗ k** = (5 mod 4) ∗ 2 = **2** yes, its located at memory location 2.

Last element of cache line 1 = **(j mod v) ∗ k + (k − 1)** = (9 mod 4) ∗ 2 + (2 - 1) = **3** yes, its located at memory location 3.

Done.

**Answer:** (j mod v) ∗ k to (j mod v) ∗ k + (k − 1)
> 2 votes

---
Tags: computer-architecture, operating-systems, memory-management, cpu-cache
---


# Question
Title: Computing the hit and miss ratio of a cache organized as either direct mapped or two-way associative
This is an example problem in a computer organization and architecture course that's giving me some trouble. It goes as follows:

> Consider a cache of 4 lines of 16 bytes each. Main memory is divided into blocks of 16 bytes each. That is, block 0 has bytes with addresses 0 through 15, and so on. Now consider a program that accesses memory in the following sequence of addresses:
>
> Once: 63-70
>
> Loop 10 times: 15-32; 80-95
>
> a. Suppose the cache is organized as direct mapped. Memory blocks 0, 4, and so on are assigned to line 1; blocks 1, 5, and so on to line 2; and so on. Compute the hit ratio.
>
> b. Suppose the cache is organized as two-way set associative, with two sets of two lines each. Even-numbered blocks are assigned to set 0 and odd-numbered blocks are assigned to set 1. Compute the hit ratio using the least recently used replacement scheme.

I know that the formula for finding the hit ratio is:

`hit ratio = hits / (hits + misses)`

and that the LRU replacement scheme should be used for both **a** and **b**, since it's the most efficient. I know how to find and compute addresses in a cache, but this has me stumped.

Any help in understanding this is greatly appreciated!

# Answer
> Consider a cache of 4 lines of 16 bytes each. Main memory is divided into blocks of 16 bytes each. That is, block 0 has bytes with addresses 0 through 15, and so on.

Number of cache lines = 4

Each cache line = 16 bytes

Main memory block size = 16 bytes

Block 0 holds address 0 to 15,Block 1 holds address 16 to 31,Block 2 holds address 32 to 47, etc as below

```
╔══════════════════════════╗
║       Main Memory        ║
╠════════════════╤═════════╣
║ Memory address │         ║
╟────────────────┼─────────╢
║       0        │ Block 0 ║
╟────────────────┤         ║
║       1        │         ║
╟────────────────┤         ║
║       2        │         ║
╟────────────────┤         ║
║       3        │         ║
╟────────────────┤         ║
║       4        │         ║
╟────────────────┤         ║
║       5        │         ║
╟────────────────┤         ║
║       6        │         ║
╟────────────────┤         ║
║       7        │         ║
╟────────────────┤         ║
║       8        │         ║
╟────────────────┤         ║
║       9        │         ║
╟────────────────┤         ║
║       10       │         ║
╟────────────────┤         ║
║       11       │         ║
╟────────────────┤         ║
║       12       │         ║
╟────────────────┤         ║
║       13       │         ║
╟────────────────┤         ║
║       14       │         ║
╟────────────────┤         ║
║       15       │         ║
╟────────────────┼─────────╢
║       16       │ Block 1 ║
╟────────────────┤         ║
║       17       │         ║
╟────────────────┤         ║
║       18       │         ║
╟────────────────┤         ║
║   and so on    │         ║
╚════════════════╧═════════╝

```

> Now consider a program that accesses memory in the following sequence of addresses:
>
> Once: 63-70
>
> Loop 10 times: 15-32; 80-95

Here its not correctly specified that-

**Case 1 :** looped 15-32 ten times and then looped 80-95 ten times

**Case 2 :** 15-32 and 80-95 are looped one after another ten times

anyway we'll solve both cases.

> **a.** Suppose the cache is organized as direct mapped. Memory blocks 0, 4, and so on are assigned to line 1; blocks 1, 5, and so on to line 2; and so on. Compute the hit ratio.

Direct mapped Cache :

```
╔═════════════╤═══════════════════╤═════════════════════════╗
║ Cache lines │ Main memory block │ Addresses in each block ║
╠═════════════╪═══════════════════╪═════════════════════════╣
║      0      │      Block 0      │          0-15           ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      1      │      Block 1      │          16-31          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      2      │      Block 2      │          32-47          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      3      │      Block 3      │          48-63          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      0      │      Block 4      │          64-79          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      1      │      Block 5      │          80-95          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      2      │      Block 6      │         96-111          ║
╚═════════════╧═══════════════════╧═════════════════════════╝

```

Accessing memory:

(1) once: 63-70

63 falls in Block 3 - Miss on 63 (Block 3 is bought to cache)

64 falls in Block 4 - Miss on 64 (Block 4 is bought to cache)

```
╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║      0      │      Block 4      │  64-79  ║
╟─────────────┼───────────────────┼─────────╢
║      1      │         -         │    -    ║
╟─────────────┼───────────────────┼─────────╢
║      2      │         -         │    -    ║
╟─────────────┼───────────────────┼─────────╢
║      3      │      Block 3      │  48-63  ║
╚═════════════╧═══════════════════╧═════════╝

```

therefore, 2 miss and 6 hit.

(2) loop: 15-32,80-95

Case 1:

15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache, replacing Block 4)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache)

```
╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║      0      │      Block 0      │  0-15   ║
╟─────────────┼───────────────────┼─────────╢
║      1      │      Block 1      │  16-31  ║
╟─────────────┼───────────────────┼─────────╢
║      2      │      Block 2      │  32-47  ║
╟─────────────┼───────────────────┼─────────╢
║      3      │      Block 3      │  48-63  ║
╚═════════════╧═══════════════════╧═════════╝

```

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1)

```
╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║      0      │      Block 0      │  0-15   ║
╟─────────────┼───────────────────┼─────────╢
║      1      │      Block 5      │  80-95  ║
╟─────────────┼───────────────────┼─────────╢
║      2      │      Block 2      │  32-47  ║
╟─────────────┼───────────────────┼─────────╢
║      3      │      Block 3      │  48-63  ║
╚═════════════╧═══════════════════╧═════════╝

```

therefore, 4 miss and 29 hit.

Case 2 : loop: 15-32,80-95

**{{** 15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache, replacing Block 4)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache)

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1) **}} x 1 times**

**{{** 16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache, replacing Block 5)

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1) **}} x 9 times**

therefore, 22 miss and 11 hit.

> **b.** Suppose the cache is organized as two-way set associative, with two sets of two lines each. Even-numbered blocks are assigned to set 0 and odd-numbered blocks are assigned to set 1. Compute the hit ratio using the least recently used replacement scheme.

Two-way set associative mapping:

```
╔═════════════════════════════╗
║            Cache            ║
╠═════════════╤═══════╤═══════╣
║ Cache lines │ Set 1 │ Set 2 ║
╟─────────────┼───────┼───────╢
║      0      │   -   │   -   ║
╟─────────────┼───────┼───────╢
║      1      │   -   │   -   ║
╚═════════════╧═══════╧═══════╝

```

Block allocation to cache lines:

```
╔═════════════╤═══════════════════╗
║ Cache lines │ Main memory Block ║
╠═════════════╪═══════════════════╣
║      0      │  Block 0,2,4,..   ║
╟─────────────┼───────────────────╢
║      1      │  Block 1,3,5,..   ║
╚═════════════╧═══════════════════╝

```

Accessing memory:

(1) once: 63-70

63 falls in Block 3 - Miss on 63 (Block 3 is bought to cache)

64 falls in Block 4 - Miss on 64 (Block 4 is bought to cache)

```
╔═══════════════════════════════╗
║             Cache             ║
╠═════════════╤═════════╤═══════╣
║ Cache lines │  Set 1  │ Set 2 ║
╟─────────────┼─────────┼───────╢
║      0      │ Block 4 │   -   ║
╟─────────────┼─────────┼───────╢
║      1      │ Block 3 │   -   ║
╚═════════════╧═════════╧═══════╝

```

therefore, 2 miss and 6 hit.

(2) loop: 15-32,80-95

Case 1:

15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache, replacing Block 4)

```
╔═════════════════════════════════╗
║              Cache              ║
╠═════════════╤═════════╤═════════╣
║ Cache lines │  Set 1  │  Set 2  ║
╟─────────────┼─────────┼─────────╢
║      0      │ Block 2 │ Block 0 ║
╟─────────────┼─────────┼─────────╢
║      1      │ Block 3 │ Block 1 ║
╚═════════════╧═════════╧═════════╝

```

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 3)

```
╔═════════════════════════════════╗
║              Cache              ║
╠═════════════╤═════════╤═════════╣
║ Cache lines │  Set 1  │  Set 2  ║
╟─────────────┼─────────┼─────────╢
║      0      │ Block 2 │ Block 0 ║
╟─────────────┼─────────┼─────────╢
║      1      │ Block 5 │ Block 1 ║
╚═════════════╧═════════╧═════════╝

```

therefore, 4 miss and 29 hit.

Case 2 : loop: 15-32,80-95

15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache,, replacing Block 2)

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 5)

therefore, 4 miss and 29 hit.

**Answer:**

**a.**

**Case 1:** hit ratio = (6+29)/(8+18+15) * 100 = 85.3%

**Case 2:** hit ratio = (6+11)/(8+18+15) * 100 = 41.1%

**b.**

**Case 1:** hit ratio = (6+29)/(8+18+15) * 100 = 85.3%

**Case 2:** hit ratio = (6+29)/(8+18+15) * 100 = 85.3%
> 2 votes

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


# Question
Title: Does the Halting Problem have practical relevance? I can calculate all outputs for a finite number of states and inputs
Coming from a digital functional hardware verification background, I don’t really understand the Halting Problem. I can represent the program as a state machine and show whether all inputs in all states generate a valid output or lead to an infinite loop.

The only requirement is that the inputs and states are finite. E.g. an infinite counter would lead to an infinite number of states.

Since infinite counters or infinite inputs are impossible in reality, does the Halting Problem really have a practical relevance?

# Answer
> 0 votes
Indeed, if states and inputs are finite (and the tape is finite, which is quite reasonable), then you can easily reduce the Turing machine to a Finite State Machine. However, this is completely impractical, since it doesn't yield any reasonably effective algorithms. I.e. your solution for the halting problem will be to explode the states of the TM with all possible input combinations of size N, and then find a path that reaches a stop state, right? Probably don't want to implement such a check in your compiler.

# Answer
> -1 votes
No, your reasoning is wrong. Building a state machine and checking for cycles works only if the memory of the Turing machine is finite and *bounded* in length. However, the working state of the Turing machine (the tape) is *unbounded* in length, so there is no upper limit on the set of possible states. In other words, while the size of the state is finite at any specific time, the total number of possible states that might ultimately be reachable is infinite.

Yes, the Halting problem is important and has practical relevance: see Why, really, is the Halting Problem so important?

---
Tags: halting-problem
---


title: Red-blue intersection requirements

text:
# Question
Title: Red-blue intersection requirements
In the red-blue line segments intersection problem, what does it mean that the red-red (and blue-blue) lines cannot intersect? Does mean mean that the algorithms wont work correctly or does it mean that these kind of intersections will be simply ignored?

In other words, do the fast intersection algorithms require that the are no single-color intersections? Or they can work with such intersections but will find only bi-chromatic intersections?

The red-blue line segments intersection problem can be stated as: "Given a disjoint set of red line segments and a disjoint set of blue line segments in the plane, with a total of n segments, report all k intersections of red segments with blue segments." (From "A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections", Timothy M. Chan).

The idea, if I understood correctly, is that the problem should be easier to solve than the problem of reporting all intersections between line segments in general. So I'm trying to understand how hard the requirements are...

# Answer
I guess it depends on the particular algorithm you have in mind. However, the red/blue segment intersection algorithms that I'm aware of require that there are no monochromatic (red/red or blue/blue) intersections. For example, Chans red/blue intersection algorithm builds a trapezoidal decomposition on the blue segments. That does not really work if there are blue/blue intersections as well.

By the way, note that both red/blue segment intersection, as well as general (monochromatic) segment intersection can be solved in optimal $O(n \log n + k)$ time.
> 2 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Suggest a data-structure that supports the following operations with time complexity of $ O(log(n)) $
Iv'e been struggling a lot with this one. I am looking for a data-structure (could be a modification of an existing type of data-structure, or a combination of more than one data-structure), which supports the following methods, all with time complexity (at worst-case) of $O(log(n))$:

1. Insert(v) - insert v to the structure
2. search(v) - search for v
3. delete(v) - delete node with value v
4. updateKeys(x,v) - for each node with a value greater then x, add v to it's value, **where v is a positive number**.

For example, if I had the following set of elements: ${1,2,5,8,10,15,20}$ , using `updateKeys` the following way: $ updateKeys(10,5) $ would change the set to : $ {1,2,5,8,15,20,25} $.

Well, I had a lot in my mind. Basically, my assignment is on the following data-structures:

1. **Hash tables** \- which sounded good at first, but I couldn't think of a way to find all elements larger than or equal to x.
2. **AVL tree** \- it does support the basic methods with this complexity, but in order to find which elements are larger, I need to search through all tree which can cost more than $ log(n) $. Further more, I can mess the tree up if I for instance make a left son be larger than it's parent.
3. **A combination of the two above** \- looked promising at first, but again, I couldn't find a way to find those elements.
4. **Heap** \- for some reason it sounds like a good direction since I have some sort of order, but update the values with log(n) time? seems impossible.
5. **Skip list** \- here I thought about using skip list since the most bottom layer is sorted in increasing order, so I thought about finding the minimum value larger than x, and then update all of it's followers from the right. Sounds good, but it is definitely not within $ O(log(n)) $, since for the following set ${1,2,3,4...10}$, and for $ x=1 $, I need to iterate 10 numbers, which is $ O(n) $

We also studied **B-trees, ADT structures**...

Then, almost hopeless, I started reading about data structures that weren't even taught in our course, such as range trees, BIT trees and so on.For some reason, some of them seemed suitable for this purpose, but since it's not in our syllabus, I don't think we are even allowed to use them.

Thanks in advance.

# Answer
> 3 votes
> AVL tree - it does support the basic methods with this complexity, but in order to find which elements are larger, I need to search through all tree which can cost more than log(n).

Not quite. In order to *change* all those entries, yes; but by searching for $x$ you can identify all nodes that have greater values: all nodes you visit and have key $\> x$, namely those where you go left, and their right subtrees.

> Further more, I can mess the tree up if I for instance make a left son be larger than it's parent.

No, and that may be the key insight. If we increase *all* keys $\>x$ by some constant we maintain the search-tree property! In particular, you *never* increase a left son and not its parent!

These two observations lead us to the idea: use AVL-trees (or any balanced search tree, I daresay) and execute key increments *lazily*. For that, add to every node an integer `inc` that is initially $0$.

Now, a call `updateKeys(x,v)` proceeds as follows.

1. Search for `x` using usual BST search.
2. Whenever you go left at some node `y`,

1. increase `y.key` by `v` and
    2. increase `y.right.inc` by `v`.

This adds at most constant overhead per visited node, so it has the same $\Theta$-running-time as search.

We execute the updates whenever we traverse the tree anyway. That is, augment all four operations so that when they access some `y.key` they execute this first (if `y.inc > 0`):

```
y.left.inc  += y.inc
y.right.inc += y.inc
y.key       += y.inc
y.inc        = 0

```

This adds at most a constant amount of effort per visited node for all the operations, so it does not change their $\Theta$-bounds on time. We do need a linear amount of extra memory, but that seems to be allowed.

Detailed pseudocode and proofs of correctness are good exercises.

---
Tags: data-structures, dictionaries
---


title: Why isn't selection sort O(n log n)?

text:
# Question
Title: Why isn't selection sort O(n log n)?
We make $n$ insertions and each insertion targets a list of size $k\le n$, so we can make a binary search which takes maximum $\log k\le \log n$. So why isn't the running time of selection sort $O(n \log n)?$

# Answer
> 5 votes
Selection sort proceeds by finding the smallest *unsorted* element and adding it to the end of the sorted section of the array. You can't use binary search to find the smallest unsorted element, because binary search only works on sorted lists.

Your question seems to be based on the mistaken understanding that selection sort takes the first unsorted element and inserts it into the correct place in the sorted list. The correct place could then be found by binary search but the problem with that attempt at an algorithm is that you need array-like access to the sorted portion for binary searching it, and list-like access for inserting in the middle.

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


title: phrase searches and vector space model

text:
# Question
Title: phrase searches and vector space model
Consider a system that indexes documents based on vector space model and a simple query, such as `qwe asd`. When searching we assign weights to both words `qwe` and `asd` based on how often they appear in the index. The idea being that if word exists in larger number of documents then it should have smaller impact on relevance. This works well because for each word we usually store statistics: number of occurrences of a given word in the whole index and number of occurrences of a given word in each document (possibly after normalization).

Now consider another query: `"qwe asd" zxcrty`. We have two parts here: a phrase and a simple word. For the word we have the above mentioned statistics, but for the phrase we do not. This poses a question: how to rank documents against phrase searches? If we find a one document that contains the phrase (`qwe asd`) and another that contains the single word (`zxcrty`) which one should be ranked higher?

I somehow doubt that there is one and ultimate solution to this question but would like to know about what approaches are used in existing search engines, whether other models solve the issue and other information that can be useful in analysing the problem.

# Answer
As you state in your comment, you could use a variety of different approaches. Your question isn't limited to the vector space model. Various language models rely on these concepts as well. Here are two approaches:

## N-Grams

One popular approach is the use of n-grams. This approach involves treating adjacent words as one word. For instance, "big house" would be stored in your controlled vocabulary as "big," "house," and "big house" if you chose to use 2-grams (bigrams). Probabilities would be computed per n-gram

Pros: accurately keep track of probabilities of n-grams occuring, easy to extend from unigram model (just follow same ranking functions for unigrams such as tf-idf or Okapi BM25)

Cons: exponentially larger memory usage, many bigrams will only occur once

## Inverted Index per Document

This approach requires storing an inverted index within each document in addition to an inverted index of the whole corpus. This would mean that you wouldn't need to store n-grams. Of course, you wouldn't have important information such as the term frequency or document frequency of an n-gram. The idea is that you look up the first word in the n-gram and find it in the document. You compare succeeding words to see if there is an n-gram present there.

Pros: less memory usage (no need to keep track of n-grams in documents), more flexibility (such as ignoring words that don't match)

Cons: less information stored (no TF, DF, etc.), more space needed per document (for inverted index), additional lookup needed, ranking this may be difficult

> If we find a one document that contains the phrase (qwe asd) and another that contains the single word (zxcrty) which one should be ranked higher?

This completely depends on the ranking function and how you choose to weight each thing. How common are qwe and asd? How common is zxcrty? Would you want to give additional weight to larger n-grams? These are all important considerations.
> 1 votes

---
Tags: information-retrieval
---


# Question
Title: How to compute the TF-IDF scores for a handful of documents, but without my own corpus?
I have a small number of documents (I could probably get 4 or 5 documents) and want to assign terms in these documents a score based on its importance to the document. I want to find which terms are simultaneously important to all of these documents.

These documents have different authors but are written about the same topic, and I want to filter out keywords that are artifacts of the authors' writing styles.

TF-IDF seems like a well-established scoring function. However, the documents I have do not belong to a large corpus of documents, prohibiting the computation of IDF-values.

**Q**: How can I compute the TF-IDF score of terms within a handful of documents, but without my own corpus?

I'm open to alternative suggests that do not involve TF-IDF.

# Answer
## Answer

What do you value in a ranking function? If you don't value TF or IDF, then it'll be difficult for you to achieve what you want to achieve.

Without a corpus however, you could use a frequency chart as a substitute for TF:

http://www.wordfrequency.info/free.asp?s=y

I had trouble finding a similar list for IDF online. However, you could just remove the IDF term from the TF-IDF equation. Finding an alternative for IDF is difficult.

## Your Situation

4-5 documents isn't much, but it's still a corpus. Of course, it'll likely have more error than a larger corpus, but I see no reason why you can't use it. Also, why can't you use IDF? If the term exists in one document, then IDF can be computed, otherwise it shouldn't be in your controlled vocabulary anyway. Although if you're worried about error, then you could probably just discard it at this point.

If you just use your documents as the corpus, you can take advantage their context, which seems to be what you want here. Basically, many words will be more/less common in your subset than in the English language in general due to the specific domain and small sample size.
> 2 votes

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


# Question
Title: Scheduling a sequence of queue operations that push and pop items at specified times
What is the time complexity of the following problem?

## Definitions

A **FIFO** is a queue functional unit supporting four commands: PUSH (data to back of queue), POP (the head of the queue), PNP (POP the head of queue and PUSH it to the back), NOP (do nothing). Each command takes one unit of time to execute.

**FIFO code** (or a schedule of commands) is a sequence of commands to execute.

## Problem Description

We are given $n$ items of data $T\_1,\dots,T\_n$, and $n$ triplets $(T\_1,t^{in}\_1,t^{out}\_1),\dots,(T\_n,t^{in}\_n,t^{out}\_n)$. $t^{in}\_i$ and $t^{out}\_i$ identify the time when $T\_i$ is PUSHed and POPed respectively. We're guaranteed that $t^{in}\_i\<t^{out}\_i$ for every $i$ and $t^{in}\_i,t^{out}\_i$ are all unique.

The goal is to produce FIFO code (a schedule of commands) that push each $T\_i$ at time $t^{in}\_i$ and pop it at time $t^{out}\_i$, by adding NOP and PNP commands between the PUSH and POP commands given. No extra PUSH or POP commands can be added: the resulting code must contain exactly $n$ PUSHes and $n$ POPs.

## Example

Input: $(T\_1,2,4)$, $(T\_2,1,5)$

Solution:

1. PUSH $T\_2$
2. PUSH $T\_1$
3. **PNP**
4. POP // T\_1
5. POP // T\_2

# Answer
> 1 votes
## Initial Direction

Solving this problem is equivalent to solving a set of equations with constraints.

Denote the number of time units in an interval between consecutive input $t^{in}\_i$/$t^{out}\_i$ by $K\_i$.

In the above example in the question there are three intervals:

|PUSH($T\_2$) | PUSH($T\_1$)|---------------|POP($T\_1$) |POP($T\_2$)|

|---------------|---------------|---------------|---------------|---------------|

1. $K\_1=0$.
2. $K\_2=1$.
3. $K\_3=0$.

The depth of the FIFO at the beginning and end of each such interval is the number of PUSHs minus POPs made before it, denote it by $d\_i$.

In the above example:

1. $d\_0=0$.
2. $d\_1=1$.
3. $d\_2=2$.
4. $d\_3=1$.

Denote by $x\_i\in \mathbb{N}\cup\\{0\\}$ the number of PNP assigned in interval $K\_i$, then $x\_i\leq K\_i$.

In the above example:

1. $x\_1\leq 0$.
2. $x\_2\leq 1$.
3. $x\_3\leq 0$.

Per data unit $T\_i$ add an equation asserting it is available at the head of the FIFO at time $t^{out}\_i$ by adding $d\_i+x\_{i+1}$ modulo the depth, $d\_{i+1}$ of the FIFO per interval. In the above example:

1. For $T\_1$: $(1+x\_2)\bmod 2=0$.
2. For $T\_2$: $((( (0+x\_1)\bmod 1+x\_2 ) \bmod 2)+x\_3) \bmod 1 =0$.

And the solution is $x\_1=0, x\_2=1, x\_3=0$ corresponding with the solution above.

But I'm not sure how to use this information to understand the complexity of the problem.

# Answer
> -1 votes
In the **worst case**,

The element at the tail of the queue need to be popped i.e.,

> Given n units of data and n triplets

If n = 4 (number of element in the queue and number of triplets are four)

**Input:** (T1, 1, 14), (T2, 2, 13), (T3, 3, 11), (T4, 4 ,8)

At **time 4** the state of the queue:

```
╔══════════════════════════════╗
║            QUEUE             ║
╠══════╤══════╤════╤════╤══════╣
║      │ Head │    │    │ Tail ║
╟──────┼──────┼────┼────┼──────╢
║ DATA │  T1  │ T2 │ T3 │  T4  ║
╚══════╧══════╧════╧════╧══════╝

```

At **time 5**, T4 should be popped and to do that all the element left to T4 should be PNP (here, three PNP).

> PNP (POP the head of queue and PUSH it to the back)

That is, **(n-1) elements** of the queue should be PNP to pop **nth element** from the queue.

At **time 7** the state of the queue:

```
╔══════════════════════════════╗
║            QUEUE             ║
╠══════╤══════╤════╤════╤══════╣
║      │ Head │    │    │ Tail ║
╟──────┼──────┼────┼────┼──────╢
║ DATA │  T4  │ T1 │ T2 │  T3  ║
╚══════╧══════╧════╧════╧══════╝

```

At **time 8** the state of the queue (pop T4):

```
╔═════════════════════════════╗
║            QUEUE            ║
╠══════╤═══╤══════╤════╤══════╣
║      │   │ Head │    │ Tail ║
╟──────┼───┼──────┼────┼──────╢
║ DATA │ - │  T1  │ T2 │  T3  ║
╚══════╧═══╧══════╧════╧══════╝

```

As we go on, we can see for popping one element at the tail requires to PNP all the element right of it.

Gives,

```
╔══════════════════════╤════════════════════════╗
║ Element to be popped │ Number of NPN required ║
╠══════════════════════╪════════════════════════╣
║          n           │          n-1           ║
╟──────────────────────┼────────────────────────╢
║         n-1          │          n-2           ║
╟──────────────────────┼────────────────────────╢
║          .           │           .            ║
╟──────────────────────┼────────────────────────╢
║          .           │           .            ║
╟──────────────────────┼────────────────────────╢
║          2           │           1            ║
╟──────────────────────┼────────────────────────╢
║          1           │           0            ║
╚══════════════════════╧════════════════════════╝

```

Thus, in worst case we have a total

= *n-1 + n-2 + n-3 + ... + 2 + 1*

= \[ n ( n + 1 ) \] / 2 - n

= n2 \+ n

= O( n2 )

**Answer :**

Worst case time complexity of the problem = **O( n2 )**

Best case time complexity of the problem = O( 1 ) // when an element is requested to pop, it is found at the head of the queue.

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Using Queues for a Stack and Stacks for a Queue
I was asked a question on how to use a pair of Queues to create a Stack and how to use a pair of Stacks to create a Queue. Any thoughts on how I would do this? Right now I don't even know where to start.

# Answer
To answer the question in the comment above-

Two queues to implement a stack(Assume Queue A is filled with elements in LIFO order and Queue B is empty):

PUSH: Empty Queue A into Queue B. LIFO order will be persisted in Queue B. Now insert the new element into Queue A. Now empty Queue B into Queue A.

POP: Dequeue from Queue A
> 4 votes

# Answer
> how to use a pair of Queues to create a Stack

Two regular (FIFO) Queues will be sufficient to implement a regular (LIFO) stack.

I'll show you the process with an **example** below:

The operation that should be done on our newly constructed Stack using two queues are:

*Push A , B , C*

*Pop C*

*Push D*

Lets start:

1. Push A , B , C

Enqueue A , B , C to Queue 1

```
╔═════════╤═════════════╤═══╤══════╗
║ Queue 1 │      A      │ B │  C   ║
╠═════════╪═════════════╪═══╪══════╣
║         │    Head     │   │ Tail ║
╟─────────┼─────────────┼───┼──────╢
║ Queue 2 │      -      │ - │  -   ║
╟─────────┼─────────────┼───┼──────╢
║         │ Head & Tail │   │      ║
╚═════════╧═════════════╧═══╧══════╝

```
2. Pop C

Dequeue all element for Queue 1 expect tail element

Enqueue those elements (Dequeued from Queue 1) to Queue 2

Dequeue Tail from Queue 1

```
╔═════════╤══════╤══════╤═════════════╗
║ Queue 1 │  -   │  -   │      C      ║
╠═════════╪══════╪══════╪═════════════╣
║         │      │      │ Head & Tail ║
╟─────────┼──────┼──────┼─────────────╢
║ Queue 2 │  A   │  B   │             ║
╟─────────┼──────┼──────┼─────────────╢
║         │ Head │ Tail │             ║
╚═════════╧══════╧══════╧═════════════╝

```
3. Push D

Enqueue element to Queue 2

```
╔═════════╤═════════════╤═══╤══════╗
║ Queue 1 │      -      │ - │  -   ║
╠═════════╪═════════════╪═══╪══════╣
║         │ Head & Tail │   │      ║
╟─────────┼─────────────┼───┼──────╢
║ Queue 2 │      A      │ B │  D   ║
╟─────────┼─────────────┼───┼──────╢
║         │    Head     │   │ Tail ║
╚═════════╧═════════════╧═══╧══════╝

```

**PUSH :**

*Case 1 - empty stack*

Enqueue into any Queue (1 or 2)

*Case 2 - non empty stack*

Enqueue into non empty Queue

**POP :**

Dequeue all element except tail of the non empty Queue (say Queue 1)

Enqueue all those element to the other empty Queue (say Queue 2)

Dequeue from Queue 1

> how to use a pair of Stacks to create a Queue

Two regular (LIFO) stacks will be sufficient to implement a regular (LIFO) Queue.

Exmaple:

The operation that should be done on our newly constructed Queue using two stacks are:

Enqueue A , B , C

Dequeue C

Enqueue D

Lets start:

1. Enqueue A , B , C

Push A , B , C to Stack 1

```
╔═════╤═════════╤═════╤═════════╗
║     │ Stack 1 │     │ Stack 2 ║
╠═════╪═════════╪═════╪═════════╣
║ Top │    C    │ Top │    -    ║
╟─────┼─────────┼─────┼─────────╢
║     │    B    │     │         ║
╟─────┼─────────┼─────┼─────────╢
║     │    A    │     │         ║
╚═════╧═════════╧═════╧═════════╝

```
2. Dequeue C

Pop all elements from Stack 1

Push all these elements (popped from stack 1) to Stack 2

Pop from Stack 2

```
╔═════╤═════════╤═════╤═════════╗
║     │ Stack 1 │     │ Stack 2 ║
╠═════╪═════════╪═════╪═════════╣
║ Top │    -    │ Top │    A    ║
╟─────┼─────────┼─────┼─────────╢
║     │         │     │    B    ║
╟─────┼─────────┼─────┼─────────╢
║     │         │     │    C    ║
╚═════╧═════════╧═════╧═════════╝

```
3. Enqueue D

Push D into Stack 2

```
╔═════╤═════════╤═════╤═════════╗
║     │ Stack 1 │     │ Stack 2 ║
╠═════╪═════════╪═════╪═════════╣
║ Top │    -    │ Top │    D    ║
╟─────┼─────────┼─────┼─────────╢
║     │         │     │    B    ║
╟─────┼─────────┼─────┼─────────╢
║     │         │     │    C    ║
╚═════╧═════════╧═════╧═════════╝

```

**Enqueue:**

*Case 1 : Empty queue*

Push into any stack (1 or 2)

*Case 2 : Non empty queue*

Push into non empty stack

**Dequeue:**

Pop all the elements from the non empty stack

Push all those elements (popped from non empty stack) to the empty stack

Pop top of non empty stack.
> 0 votes

# Answer
Two stacks to implements a queue -- always fill the stack A in stack B: the last element in stack A is popped (now you got FIFO) -- return elements from stack B to stack A.

Same idea is applied to queues.
> -1 votes

---
Tags: data-structures, queues, stacks
---


title: Convert regular expression to FA?

text:
# Question
Title: Convert regular expression to FA?
I am trying to solve a practice problem from my textbook which is to draw an FA from this language: L(ab\* a\*) U L((ab)\*ba)

I need help to draw the second part L((ab)\*ba). I know the shortest string is ba, then it is abba, ababba, abababba, etc.

I started off with this to show the shortest string:

However, now I need to add the (ab)\* part in the front of this which I am unsure how to approach this.

Any help would be great, and sorry if this seems obvious to some of you... I just don't see it right now!

EDIT: If it were (a\*)ba I know how I would approach it, but the (ab)\* is confusing me.

# Answer
> $L = (ab)^\*ba$

Divide $L$ into two part for easy construct the FA as

1. $(ab)^\*$
2. $ba$

Draw 1 and 2, end all undesired path to a dead state.
> 0 votes

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


# Question
Title: Will $L = \{a^* b^*\}$ be classified as a regular language?
Will $L = \\{a^\* b^\*\\}$ be classified as a regular language?

I am confused because I know that $L = \\{a^n b^n\\}$ is not regular. What difference does the kleene star make?

# Answer
> 20 votes
A language is regular, by definition, if it is accepted by some DFA. (This is at least one common definition.) Can you think of a DFA accepting the language?

A well-known result (that is proved in many textbooks) states that the language of a regular expression is regular. Since $a^\* b^\*$ is a regular expression, its language must be regular (if you believe this result).

Finally, to answer your question (what difference does the Kleene star make): in the language $\\{a^n b^n : n \geq 0\\}$, we need to *count* the number of $a$s and $b$s; in the language $a^\*b^\*$ we don't.

# Answer
> 14 votes
$\\{a^\* b^\*\\}$ is a regular language, since it's generated by a regular expression.

The key difference between $L\_\* = \\{a^\* b^\*\\}$ and $L\_= = \\{a^n b^n\\}$ is that $L\_=$ requires counting the $a$'s and $b$'s to check whether there's the same number of them, whereas $L\_\*$ doesn't require any counting. Counting requires unbounded memory as the number grows larger, but finite automata only have a finite amount of memory, so a finite automaton cannot recognize $L\_=$. On the other hand, a finite automaton can recognize $L\_\*$ since that merely requires checking that the $a$'s (any number) come before the $b$'s (any number).

That's why the Kleene star doesn't define languages that require unbounded memory to recognize — it means “any number”, and each time the star is encountered, the number can be different.

# Answer
> 0 votes
Any language for which you can develop a DFA.

Just check if you can draw a DFA for both of those languages.

> $L\_1={a^∗b^∗}$

$x^\*$ denote all occurance of the alphabet $x$

Strings: $\epsilon$, a, b, aa, ab, bb, ..

To generate set of string belonging to $L\_1$, machine need not to keep track of the number of a's and b's. As FA can remember only the last alphabet processed, DFA can be developed.

DFA exist.

Therefore regular.

> $L\_2={a^nb^n}$

Strings: $\epsilon$, aa, bb, aaa, bbb, ..

To generate set of string belonging to $L\_2$, machine needs to keep track of the number of a's printed so as to print same number of b's. But FA can remember only the last alphabet processed.

To construct a machine that accept $L\_2$ we need to add one more memory such a machine is called PDA (Push Down Automate).

No DFA exist.

Therefore not regular.

---
Tags: formal-languages, regular-languages, kleene-star
---


# Question
Title: With Memoization Are Time Complexity & Space Complexity Always the Same?
I am studying Dynamic Programming using both iterative and recursive functions. With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of the problem.

When evaluating the space complexity of the problem, I keep seeing that time O() = space O(). This is because we will have to cache all the results, but once we cache them it is O(1) to retrieve

Examples of this are

My question is, with Memoization, will the space & time complexity always be the same ? If not, why not ?

**Edit - Clarification**

This question is regarding the Space complexity of the recursive solution. I have solved the iterative solution using smaller space complexity before, i.e. keeping only a single row in the matrix. However for the recursive solution, I have never seen a recursive approach where items are deleted from the memoization table. I suppose you could combine recursion + iteration to only keep a single row in the memoization, but I have not seen an example where you start at the pure end, and only keep limited space.

# Answer
There are plenty examples for which you

* need $\omega(1)$ time to compute each table entry or
* do not need to keep all table entries.

An example for the former would be CYK; for the latter memoized Fibonacci and Bellman-Ford.
> 3 votes

# Answer
This is not a general rule. It is very possible for a dynamic programming algorithm to have greater time complexity than space complexity (but obviously not the other way around, since we spend at least $O(1)$ time per instance).

For instance, you mention that the dice sum problem can be solved in $O(D\*T)$ time and space (if we let $D$ be the number of dice and $T$ be the target sum). It can *also* be solved in $O(D\*T)$ time and $O(T)$ space, simply by noting that the computation of the values follows a specific pattern and that to compute the answer for $n$ dice, you only need the answers for $n$ and $n-1$ dice (and you can forget the answers for $n-2,n-3,\ldots$ dice).
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis, dynamic-programming, space-analysis, memoization
---


# Question
Title: 0/1 Knapsack problem with overlapping items
Here's a doozy:

Given a knapsack with a capacity W, and n overlapping items (definition of overlapping to follow), which items should we take to maximize the value of the knapsack?

In this problem, you can think of an "item" as a bag of coins with the following properties:

* There are many, many different types of coins (1M+)
* Every coin is worth the same amount
* Each bag has at most one of any type of coin

For example, bag 1 might have two coins, one of type A and another of type B. And bag 2 might have two coins, one type B and one type C.

We can only take one of each type of coin. So picking bag 1 and bag 2 would mean that we have 3 total coins (one A, one B, and one C).

How can we figure out which bags to take to maximize the number of coins you can take?

The subproblems aren't independent, so I don't think we can use dynamic programming.

For extra credit:

How can we get within a certain threshold, say 10%, of the capacity W as fast as possible?

# Answer
Calling this a variant of Knapsack is a bit confusing, since it's more like maximum-weight independent set. Bags are nodes, bags that share a type of coin have an edge between them, and the number of coins in each bag is the weight of the node. Going the other way is annoying, translating unweighted MIS into this problem is easy though.

Anyway here's a direct ILP formulation of the coins/bags thing:

```
maximize sum of take_bag[i] * size[i]
s.t.
∀c: sum[i | c ∈ bag[i]] of take_bag[i] ≤ 1
take_bag[i] ∈ { 0, 1 }

```

You could use the linear relaxation of that to do branch & bound, which you can stop early when you're happy enough with the gap between the best found solution and the objective value of the linear relaxation. Or check the literature for MWIS solving. There are many approximation algorithms as well.

---

Taking into account the capacity constraint, the ILP model becomes

```
maximize sum of take_bag[i] * size[i]
s.t.
∀c: sum[i | c ∈ bag[i]] of take_bag[i] ≤ 1
sum of take_bag[i] * size[i] ≤ W
take_bag[i] ∈ { 0, 1 }

```
> 1 votes

---
Tags: algorithms, optimization, knapsack-problems
---


# Question
Title: Extreme instancing for computer graphics
Instancing in GPU's, from my little knowledge, simply draw the same object at multiple locations. Each "instance" is just a copy of the same model at a different location. Any local effects, such as animation, would effect all instances. The performance improvement comes from gpu being able to deal with virtually all the instance aspects.

One could create several variations of the same object and instance each one. This would be very useful to create variations(say for leaves on a tree) but, while allowing for rather large number of instances(basically limited by the gpu) and variation increases the the cpu's involvement by the number of variations(from the previous case).

If we could send the changes to the gpu then we could get back to the first case(or very close) and achieve very high levels of variations with limited cpu involvement.

For example,

Suppose we wanted to populate a jungle with a lot of animals. Each animal object will have many instances(many tigers and birds but all using the same template). If we had one long animation containing all the possible animations of each animal and send it to the gpu we then would simply have to tell the gpu which part of the animation each instance was in(and we could have a default animation to limit cpu-gpu communications).

This would effectively let us control all the instances with just a animation position indicator(and possible a few other parameters such as scale) and coordinate position. The gpu would take care of all the rest.

The problem, of course, is that that each instance would not have any logic associated with it. This is not a big deal though for most computer objects. The cpu generally has to take care of the logic anyways but in this case, instead to tell send all that information to the gpu we can just send it a few bytes for each instance.

For example, suppose in our jungle we have a few cheetahs and on our cpu we are keeping track of which ones are doing what and simply sending which animation we want them to use to the cpu(instead of sending all the vertex data and/or telling it how to transform them).

This seems like it would be much faster and essentially just boils down to moving some of the code from the cpu to the gpu(which as been what is happening all along).

Using such a method is not ideal because of the lack of physical modeling per instance but for far enough away objects were intersecting objects won't be seen it won't matter.

We could have thousands of birds, for example, all seemingly moving individually but generated from one model with a few animations.... the cpu doing very little but sending which animations to use to the gpu. (and of course deciding what each bird should do)

Anyways, this is a thought but it seems to me the goal of future gpu's is to deal with all the visual aspects while the cpu deals with the logic(and the communication between the too is to be minimized).

Is my interpretation of instancing with animation's flawed or could it be implemented and be useful to 3d games?

# Answer
> 1 votes
Yes, you are correct. What you suggest is a viable approach in 3D games. Popular game engines already do this, and have been doing this for some time. If you choose to do this through the vertex shader, you can improve performance in many situations.

For more information about animation: How animation works in realtime graphics

---
Tags: graphics, computer-games
---


title: Maximum cost path in integer matrix

text:
# Question
Title: Maximum cost path in integer matrix
In preparation for my design and algorithms exam, I encountered the following problem.

> Given a $2 \times N$ integer matrix $(a\[i\]\[j\] \in \[-1000, 1000\])$ and an unsigned integer $k$, find the maximum cost path from the top left corner $(a\[1\]\[1\])$ and the bottom right corner $a\[2\]\[N\]$, given the following:

---

$\bullet$ The path may not go through the same element more than once

$\bullet$ You can move from one cell to the other vertically or horizontally

$\bullet$ The path may not contain more than $k$ consecutive elements from the same line

$\bullet$ The cost of the path is determined by the sum of all the values stored within the cells it passes through

---

I've been thinking of a simple greedy approach that seems to work for the test cases I've tried, but I'm not sure if it's always optimal. Namely, while traversing the matrix, I select a the maximum cost cell on the vertical or horizontal and then go from there. I've got a counter I only increment if the current cell is on the same line with the previously examined one and reset it otherwise. If at some point the selected element happens to be one that makes the counter go over the given value of $k$, I simply go with the other option that's left.

However, I feel that I'm missing out on something terribly important here, but I just can't see what. Is there some known algorithm or approach that may be used here?

Also, the problem asks for an optimal solution (regarding temporal complexity).

# Answer
> 1 votes
This problem was basically made for dynamic programming (DP). Just review it and follow a couple of examples and solving this problem is straight-forward.

Your simple greedy approach does not always work. Consider:

```
[ begin ] [  2 ]
[ 3 ]     [ 10 ]
[ 1 ]     [ -1000 ]
[ 1 ]     [ end ]

```

The optimal solution would be to go right, down, left, down, down, right.

# Answer
> 1 votes
We shall approach this using dynamic programming -- the greedy algorithm is 'myopic' in that it only considers immediate neighbors and not the path that follows those neighbors.

Let $C(i, \ j, \ m)$ be the cost of the max-cost path starting from $a\[i\]\[j\]$ going towards $a\[2\]\[n\]$, where $i$ is either $1$ or $2$, $\ j \in \[1, n\]$ and $m \in \[0, k\]$.

* $m$ here denotes that we have $m$ remaining consecutive steps that could be taken along row $i$.
* The additional constraint we enforce here is that when we are calculating $a\[1\]\[i\]$, we have *not* yet visited $a\[2\]\[i\]$, and similarly when we're calculating $a\[2\]\[i\]$, we have not yet visited $a\[1\]\[i\]$.

With this constraint in place, what recurrence can we come up with? Well,

1. $C(1, \ j, \ m) = a\[1\]\[j\] + \max \\{ M(1, j+1, m-1), \ a\[2\]\[j\] + M(2, j+1, k)\\} \ $ and similarly,
2. $C(2, \ j, \ m) = a\[2\]\[j\] + \max \\{ M(2, j+1, m-1), \ a\[1\]\[j\] + M(1, j+1, k)\\} \ $

Now, what's the rationale here? If we started at $a\[1\]\[j\]$, we have two choices:

* **continue along row $1$ :** we then go to $a\[1\]\[j+1\]$ with $m-1$ remaining consecutive steps that we can take along row $1$. *(note here that $a\[2\]\[j+1\]$ is not yet visited, maintaining the invariant).*
* **switch to row $2$ :** we go to $a\[2\]\[j\]$, incurring a cost of $a\[2\]\[j\]$, and then have only one choice from there - to go to $a\[1\]\[j+1\]$. Because we have switched rows, we can now refresh our count and take $k$ consecutive steps along row $2$. *(note again that we haven't visited $a\[1\]\[j+1\]$ yet).*

Now if we calculate our subproblems starting from $j = n$ towards $j=1$ for every value of $m$, you shall have your answer in $C(1, \ 1, \ k)$.

I shall leave the base cases and runtime analysis to you. Note that my solution calculates the cost of the path and not the path itself; can you extend my solution to calculate the path too?

---
Tags: algorithms
---


# Question
Title: How does recursion works when there are 2 or more consecutive recursive calls?
I was learning about recursion and i came across the following pseudo code for quicksort.

```
QUICKSORT(A,p,r)
1   if p < r
2      then q := PARTITION(A,p,r)
3           QUICKSORT(A,p,q-1)
4           QUICKSORT(A,q+1,r)

```

In this code there are two consecutive statements that recursively call quicksort function. It confuses me. I want to know how these statements gets executed. Does the partition of left half of the array happens recursively or does both left and right of the array gets partitioned at the same time?

# Answer
> 5 votes
Just like any other two consecutive statements in an ordinary programming language, they're executed one after the other.

However, since the two recursive calls operate on disjoint sections of the array, you could, in principal, execute them in parallel.

---
Tags: programming-languages, recursion, semantics
---


# Question
Title: Does a shift operation distribute over XOR
*In this question, we abuse the mathematical notation to express bitwise operations in the following way:*

* *$\ll$ is a binary left shift*
* *$\oplus$ is a bitwise XOR*
* *$0b1, 0b110, 0b10 \ldots$ are used to denote raw bits*
* *$repr$ is a function associating to a number a given bit representation*
* *$\mathbb{B}$ is the set of natural numbers to which $repr$ associates a two's complement bit representation*
* *$\mathbb{G}$ is the set of natural numbers to which $repr$ associates a Gray code bit representation*

---

I was trying to prove that the binary representation of a power of $2$ in binary reflected Gray code was always two ones followed by zero or more zeroes, except for $2^0$. The demonstration is roughly as follows:

> We know that the two's representation of powers of $2$ can be expressed as follows:
>
> $$ \forall n \in \mathbb{N} : repr(2\_\mathbb{B}^n) = 0b1 \ll n $$
>
> And the function $to\\\_gray$ can be expressed as follows:
>
> $$ \forall n \in \mathbb{B} : to\\\_gray(n) = n \oplus (n \gg 1) $$
>
> Therefore, we have the following equivalence (ignoring the special case when $n = 0$):
>
> $$\begin{align\*} \forall n \in \mathbb{N} : repr(to\\\_gray(2\_\mathbb{B}^n)) &= (0b1 \ll n) \oplus ((0b1 \ll n) \gg 1)\\ &= (0b1 \ll n) \oplus (0b1 \ll (n - 1))\\ &= (0b10 \ll (n - 1)) \oplus (0b1 \ll (n - 1))\\ &= 0b11 \ll (n - 1) \end{align\*}$$

However, the last line of the demonstration assumes that $\ll$ distributes over $\oplus$. Is this assumption true or does it only work for my specific use case?

# Answer
> 5 votes
Yes, bit shifts distribute over all bitwise logical operations $\odot$ for which $0 \odot 0 = 0$,\* in the sense that: $$(a \odot b) \ll n = (a \ll n) \odot (b \ll n)$$ and: $$(a \odot b) \gg n = (a \gg n) \odot (b \gg n).$$ In particular, these identities hold true for bitwise AND, OR and XOR.

To show this, let $x\_k$ denote the $k$-th bit of the number $x$.\* Then, for each bit $k$, we have (by definition) the following identities:

$$\begin{aligned} (x \ll n)\_k &= x\_{k-n} \\ (x \gg n)\_k &= x\_{k+n} \\ (x \odot y)\_k &= x\_{k} \odot y\_k \\ \end{aligned}$$

and thus:

$$\begin{aligned} ((a \odot b) \ll n)\_k &= (a \odot b)\_{k-n} \\ &= a\_{k-n} \odot b\_{k-n} \\ &= (a \ll n)\_k \odot (b \ll n)\_k \\ &= ((a \ll n) \odot (b \ll n))\_k \\ \end{aligned}$$

(and correspondingly for right shifts). Since this identity holds for all bits $k$, it also holds for the entire bitstrings.

The key observation here is that bit shifts just renumber the bits of the bitstring (and possibly discard and/or introduce some new bits at the ends), while bitwise logical operations like XOR, by definition, operate identically and independently on each bit position. Thus, the two types of operations are effectively orthogonal in their effects.

---

<sup>\*) By convention, for out-of-range bit indexes, we define $x\_k = 0$ when $k \< 0$, and either $x\_k = 0$ (for logical shifts) or $x\_k = x\_{k\_{\max}}$ (for arithmetic shifts) when $k \> k\_{\max}$, where $k\_{\max}$ is the highest valid bit index of the bitstring $x$. This corresponds to the convention that the lowest bits of a left-shifted number are set to $0$, and the highest bits of a right-shifted number are either set to $0$ or set to equal the highest bit of the original number, depending on the type of right shift used.
As a consequence, for operations where $0 \odot 0 \ne 0$, such as NAND and NOR, the identity $(x \odot y)\_k = x\_{k} \odot y\_k$ may not hold when $k$ is out of range. Thus, for such operations, the distributive properties given above may not hold for the lowest $n$ bits (for $\ll n$) and the highest $n$ bits (for $\gg n$, where $\gg$ is a logical shift). However, *arithmetic* right shifts with sign extension (as well as right shifts on arbitrary-length numbers with implicit sign extension) do fully distribute over all bitwise logical operations.</sup>

# Answer
> 5 votes
Shift is right-distributive over XOR, and over many other operations as well (AND, OR, addition, min, max)

As for why, informally for the bitwise operations I'd explain it as: bitwise operations are like pointwise operations (if you view a number as a function from bit index to the bit at that index), translating (or permuting, etc) the positions distributes over doing the operation. Eg if we have two numbers $f$ and $g$ as such functions, then $(f ⊕ g)(k) = f(k) ⊕ g(k)$ so $(f ⊕ g)(k + j) = f(k + j) ⊕ g(k + j)$, here $f(k + j)$ is just $f$ shifted by $j$ so this showed that it didn't matter whether the shift is done after the XOR or on both of its operands. In general this applies to any remapping of the coordinates, ie $(f ⊕ g)(r(k)) = f(r(k)) ⊕ g(r(k))$ where $r$ is any function from $\mathbb{N}$ to $\mathbb{N}$.

As pointed out in the comments, this also relies on the operator to map two zeroes to an other zero, ie $0 ⊕ 0 = 0$.

Or simpler but less general, using string notation, let's say we have two number $a$ and $b$ and let their XOR be $c$, then $a0^k ⊕ b0^k = c0^k$ and $(a⊕b)0^k = c0^k$ (by substitution).

# Answer
> 4 votes
The following doesn't answer the question, since shifts aren't permutations, as pointed out by user2357112 in the comments.

---

Any permutation operator is right-distributive over any bitwise operator. It clearly makes no difference whether you combine the bits and then permute their order, or permute the bits and then combine them.

More formally, let $\pi$ is any permutation of $\\{1, \dots, n\\}$ and write $\Pi$ for the operator that maps $(x\_1, \dots, x\_n)$ to $(x\_{\pi(1)}, \dots, x\_{\pi(n))}$. Let $\odot$ be any bitwise operator. We have \begin{align\*} \Pi((x\_1, \dots, x\_n)\odot(y\_1, \dots, y\_n)) &= \Pi((x\_1\odot y\_1), \dots, (x\_n\odot y\_n)) \\ &= ((x\_{\pi(1)}\odot y\_{\pi(1)}), \dots, (x\_{\pi(n)}\odot y\_{\pi(n)}))\\ &= (x\_{\pi(1)}, \dots, x\_{\pi(n)}) \odot (y\_{\pi(1)}, \dots, y\_{\pi(n)})\\ &= \Pi(x\_1, \dots, x\_n)\odot \Pi(y\_1, \dots, y\_n)\\,. \end{align\*}

# Answer
> 2 votes
Left- and right-shifts right-associate with any bitwise binary operator $\odot$ that has $0\odot0=0$:

\begin{align\*} (\langle x\_1, \dots, x\_n\rangle\odot\langle y\_1, \dots, y\_n\rangle)\ll1 &=\langle x\_1\odot y\_1, \dots, x\_n\odot y\_n\rangle \ll1\\ &=\langle x\_2\odot y\_2, \dots, x\_n\odot y\_n, 0\rangle\\ &=\langle x\_2\odot y\_2, \dots, x\_n\odot y\_n, 0\odot0\rangle\\ &=\langle x\_2, \dots, x\_n, 0\rangle \odot \langle y\_2, \dots, u\_n, 0\rangle\\ &=(\langle x\_1, \dots, x\_n\rangle\ll1)\odot(\langle y\_1, \dots, y\_n\rangle\ll1)\\,. \end{align\*}

The case of right-shifts and shifts of more than one bit are similar. For cyclic shifts, see my other answer; in that case, it's not required that $0\odot0=0$.

---
Tags: arithmetic
---