# Question
Title: Is it NP-hard to fill up bins with minimum moves?
There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a\_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$.

You start with $b\_j$ balls of type $j$. Each ball of type $j$ has weight $w\_j$, and want to put the balls into the bins such that bin $i$ has weight $c\_i$. A distribution of balls such that previous condition holds is called a feasible solution.

Consider a feasible solution with $x\_{i,j}$ balls of type $j$ in bin $i$, then the cost is $\sum\_{i=1}^n \sum\_{j=1}^m |a\_{i,j}-x\_{i,j}|$. We want to find a minimum cost feasible solution.

This problem is clearly NP-hard if there is no restriction on $\\{w\_j\\}$. The subset sum problem reduces to the existence of a feasible solution.

However, if we add the condition that $w\_j$ divides $w\_{j+1}$ for every $j$, then the subset sum reduction no longer works, so it's not clear whether the resulting problem remains NP-hard. Checking for the existence of a feasible solution takes only $O(n\\,m)$ time (attached at the end of the question), but this does not give us the minimum-cost feasible solution.

The problem has an equivalent integer program formulation. Given $a\_{i,j},c\_i,b\_j,w\_j$ for $1\leq i\leq n,1\leq j\leq m$: \begin{align\*} \text{Minimize:} & \sum\_{i=1}^n \sum\_{j=1}^m |a\_{i,j}-x\_{i,j}| \\ \text{subject to:} & \sum\_{j=1}^m x\_{i,j}w\_j = c\_i \text{ for all } 1\leq i\leq n\\ & \sum\_{i=1}^n x\_{i,j} \leq b\_j \text{ for all } 1\leq j \leq m\\ & x\_{i,j}\geq 0 \text{ for all } 1 \leq i\leq n, 1\leq j \leq m\\ \end{align\*}

My question is,

> Is the above integer program NP-hard when $w\_j$ divides $w\_{j+1}$ for all $j$?

**An algorithm to decide if there is a feasible solution in $O(n\\,m)$ time**:

Define $w\_{m+1}=w\_m(\max\_{j} c\_j + 1)$ and $d\_j = w\_{j+1}/w\_j$. Let $a\\%b$ be the remainer when $a$ is divided by $b$.

1. If there exists a $c\_i$ that's not divisible by $w\_1$, return "no feasible solution". (the invariant $c\_i$ divides $w\_j$ will always be maintained in the following loop)
2. for $j$ from $1$ to $m$:

1. $k \gets \sum\_{i=1}^n (c\_i/w\_j)\\%d\_j$. (the minimum of balls of weight $w\_j$ required)
    2. If $b\_j\<k$, return "no feasible solution".
    3. $c\_i \gets c\_i - ((c\_i/w\_j)\\% d\_j)$ for all $i$. (remove the minimum number of required balls of weight $w\_j$)
    4. $b\_{j+1} \gets \lfloor (b\_j-k)/d\_j \rfloor$. (group smaller balls into a larger ball)
3. return "there is a feasible solution".

**A polynomial time solution to the special case where $n=1$, and $w\_j$ are power of $2$s**

It is known that if $n=1$ and all $w\_j$ are powers of $2$, then this special case can be solved in polynomial time. \begin{align\*} \text{Minimize:} & \sum\_{j=1}^m |a\_j-x\_j| \\ \text{subject to:} & \sum\_{j=1}^m w\_j x\_j = c\\ & 0 \leq x\_j \leq b\_j \text{ for all } 1\leq j \leq m\\ \end{align\*}

The solution was hinted at by Yuzhou Gu, and a write up may be found here.

# Answer
> -2 votes
***Some background.*** The above problem is the knapsack problem with restrictions. The most efficient knapsack problem solution with or without restrictions can be solved in pseudopolynomial time, still NP-Hard. For some variations, see *https://en.wikipedia.org/wiki/Knapsack\_problem#Definition*. The first restriction in this variation is that the value of items (balls) to be placed in the knapsack (bins) does not matter. The problem is then restricted to the amount of time it takes to put the items in the knapsack. The original problem requires the most valuable items to be placed in as short amount of time possible. Another restriction with this version is that the weights and all other arguments are integers. And the restriction of interest is that the weights $w\_j$ divide $w\_{j+1}$ for all $j$. Note: the fractional knapsack problem can be solved in polynomial time, but does not present the most practical solutions to the original problem. This problem uses integers that divide evenly (no rational solutions). Perhaps see *What's the big deal with the knapsack problem?*.

The main question perhaps should be "is this problem still NP-Hard when $w\_j$ is unbounded by a polynomial corresponding to $i$, as the problem is less complex (in P) when it is bounded? The reason I say this is because the problem can be shown to be in P when $w\_j$ is bounded and NP-Hard when $w\_j$ does not necessarily divide $w\_{j+1}$ evenly (the weights are simply random), all restrictions limit the complexity of this problem to these two conditions. These conditions (1. the random weight knapsack problem without the item-value restriction and 2. divisible weight knapsack problem without the item-value restriction) negate each other in terms of reducing complexity, as the quotients of the weights may be random themselves (especially when unbounded), thus imposing exponential time calculations (this will be shown in the example below). Additionally, because $w\_j$ divides $w\_{j+1}$, $w\_j$ increases in size exponentially for each $j$. This is because instead of using random weighted items (balls whose unit weight may all be limited to unit weights under 100 or 50 or even 10), the restriction instead causes the time complexity to depend on the number of digits of $w\_j$, the same as trial division, which is exponential.

***So yes, the above integer program remains NP-hard even when $w\_j$ divides $w\_{j+1}$ for all $j$.*** And this is easily observed.

***Example 1:*** let $n = 1$ and $w\_p$ be powers of two. Because of constant two, the entire problem is solved in quadratic time, as your example shows. The weights are not random and therefore the calculation is solved efficiently.

***Example 2:*** let $w\_{j+1}$ be defined as $w\_j * p$, where $p$ is the prime number corresponding to $j$, such that $p=2, j=1: p=3, j=2, p=5, j=3, p=7, j=4,...,P, J$. This is applicable, as $w\_j$ divides $w\_{j+1}$ for all $j$. We get each $w\_j$ is the product of all the primes up to $j$. The values of the unit weights increase as such: $1, 2, 6, 30, 210, 2310, 30030, ...$. Since there is a bound ($p\_j$ ~ $j log (j)$, via the prime number theorem), as the quotients are all primes, we get the complexity NP-Intermediate.

***Example 3:*** let $w\_{j+1}$ be defined as $w\_j * R\_p$, where $R\_p$ is a randomly chosen prime number from two to infinity, corresponding to $j$. This is applicable to this problem, as $w\_j$ divides $w\_{j+1}$ for all $j$. We get the first 5 quotients (randomly falling from two to infinity), as $101, 2657, 7, 3169, 2$. We see that even at the 5th ball, the weight has eleven digits. Fortunately, the fifth quotient was two and not a prime in the order of $10^{100}$ or larger.

Example three above is what happens when $w\_j$ is not bounded (random weights) by a polynomial corresponding to $i$. The time complexity is exponential, NP-Hard. For some perspective, just add up all the weights, see if they fit. But there isn’t a solution to solving it significantly faster by making the weights divisible than trying each subset to see if it works. After a few dozen balls, you are still entering the realm of even the trillions of subsets or trillions of digits.

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


# Question
Title: Conditions for bipartite graph to be planar with no edges going around the vertices
A bipartite graph is planar iff it has no $K\_{3, 3}$ or $K\_5$ minors.

I am looking for a necessary or/and sufficient conditions to allow planar drawings with no edges "going around" sets of vertices. These are drawings satisfying:

1. All vertices of one part are drawn on a single vertical line. Vertices of the other part are drawn on a parallel verticle line.
2. Edges do not intersect except at vertices.
3. Edges are all in the infinite strip between the two vertical lines in point 1.

For example, all drawings here except the bottom right are non-examples. The bottom-left graph can be re-drawn to satisfy the conditions by swapping the positions of Q and R. The tops two graphs cannot be redrawn to satisfy the conditions.

The top two graphs are the only obstructions I could find. My questions are:

1. Does this problem have a name?
2. Any other obstructions that I missed?
3. Any hints on how I can prove that these two obstructions (along with anything I missed), as minors of course, are necessary and sufficient.

Note that this is not the same as being outer-planar, $K\_{2, 2}$ is outer-planar (can be drawn as a square) but it cannot be drawn to satisfy the conditions I mention above.

# Answer
Your graphs are exactly the graphs of path-width $1$ or, equivalently, the forests each of whose components is a caterpillar. Caterpillars have two relevant characterizations:

* they're the trees in which there is a single path containing every vertex of degree more than $1$;
* they're the trees in which every vertex has at most two non-leaf neighbours.

**Lemma 1.** Every caterpillar is in your class.

*Proof.* Let $G$ be a caterpillar and let $P=x\_1\dots x\_\ell$ be a longest path containing every vertex of degree $2$ or more. Note that, by maximality, $d(x\_1)=d(x\_\ell)=1$. We can produce a drawing of $G$ by first drawing $P$ as a zig-zag and then adding the degree-$1$ vertices adjacent to $x\_i$ between $x\_{i-1}$ and $x\_{i+1}$. $\Box$

**Lemma 2.** Every graph $G$ in your class is acyclic.

*Proof.* Suppose $G$ contains the cycle $x\_1y\_1x\_2y\_2\dots x\_ky\_kx\_1$ and suppose it has a drawing of the required form. W.l.o.g., $x\_2$ is above $x\_1$. But then we must have $y\_2$ above $y\_1$ since, otherwise, the lines $x\_1y\_1$ and $x\_2y\_2$ would cross. By induction, $x\_{i+1}$ is above $x\_i$ for all $i\in\\{1, \dots, k-1\\}$ and likewise for the $y$'s. But then any line $y\_kx\_1$ must either leave the region between the two columns of vertices or cross every other edge in the cycle. This contradicts our assumption that the graph has a proper drawing. $\Box$

**Lemma 3.** Every connected non-caterpillar is not in your class.

*Proof.* Let $G$ be a connected graph that is not a caterpillar. If it contains a cycle, it is not in your class by Lemma $2$, so we may assume it is a tree. If it is not a caterpillar, it must contain a vertex $x$ with distinct neighbours $y\_1$, $y\_2$ and $y\_3$, each of which has degree at least $2$.

Suppose we have a drawing of $G$ with the required properties. W.l.o.g., $y\_2$ is above $y\_1$ and $y\_3$ is above $y\_2$. Let $z\neq x$ be a neighbour of $y\_2$. The edge $y\_2z$ must cross $xy\_1$ or $xy\_3$, contradicting our assumption that the graph has a drawing of the required form. $\Box$

**Theorem.** Your class of graphs is exactly the class of forests each of whose components is a caterpillar.

*Proof.* Let $G$ be a graph. Clearly, $G$ is in your class if, and only if, every component is: if any component cannot be drawn as required, the whole graph cannot; if every component can be drawn as required, then the whole graph can be drawn by arranging the components one above the other. The result now follows by Lemmas $1$ and $3$. $\Box$

**Corollary.** Your class of graphs is the class of graphs that do not have $K\_3$ or the subdivision of $K\_{1,3}$ as a minor.

*Proof.* These are the obstructions for path-width $1$. $\Box$

These are essentially the obstructions you found: you need $K\_3$ rather than $K\_4$ because the latter would admit $K\_3$ into the class; the subdivision of $K\_{1,3}$ is exactly your second obstruction.
> 13 votes

# Answer
So, the following answer is what I came up with:

As you already mentioned, there are only two possible cases which cannot be rearranged.

> The second case is no correct representation if we assume a bipartite graph, since Wikipedia defines a bipartite graph as: every edge connects a vertex in $U$ to one in $V$.

Edit: I misread the graph, sorry for that.

This leaves us only with the $K\_{2,2}$ complete subgraph, which is the condition you want to avoid. Inversely, the sufficient condition is that your bipartite graph has no complete subgraph within itself.

To prove that any other subgraph is valid, you can imagine the following:

First, we assume that we have no edges and start with an arbitrary edge $e$. By adding the next edge, we have three possible cases:

The first case is that we have a node which neither starts nor ends at the same node as the first edge. This leaves us without any problem and we can continue inserting.

The second case is that we have a edge which - on its way - crosses another, already existing, edge. In this case we have to swap the vertex $V\_1$ or $V\_2$ (the one with the already existing edge) with one of the new edges $V\_3$ or $V\_4$, such that we continue fulfilling the criteria.

This assumes that we have no further edges starting or ending at the nodes to swap, which leads us to the following third case: After swapping one of the four Vertices $V1-V4$, we need to trace all other connections from the swapped Vertex.

Once again we can find only three solutions: Either we trace a ending connection, or repeat the step that we already took before (tracing all remaining steps). If we end up on an ending node, we can swap all of the traced nodes.

The last possible case will lead to a node which we already visited, which would leave us with a complete subgraph, which we can then reduce to the mentioned $K\_{2,2}$ condition.

EDIT: To extend this proof to the second case, we have to look at the following conditions:

In general, if we have a subgraph with at least one hub (3 or more connections), it is "rather easy".

We cannot rearrange if we have the displayed case with more than two neighbors of higher degree than one ($\langle k\rangle \> 1$). This is important because it provides is with the knowledge about further neighbors. We don't even have to trace them any further to avoid any circles (like the first case), but it is enought to check the immediate neighbors.

Since I myself have only slight knowledge in this area, but still want to provide you with a possible solution, I linked you one (hopefully) appropriate article

If anyone would name this problem, I'd be interested to learn, especially since I came up with this solution only by following up on thoughts from Fáry's theorem and complete bipartite subgraphs.
> 0 votes

---
Tags: graphs, terminology, graph-drawing
---


title: Program counter format LC-2

text:
# Question
Title: Program counter format LC-2
Not really sure if this is an exact CS question. I'm reading the Patt/Patel Introduction to computing systems Powerpoint presentation and I don't understand about the program counter and instruction register format in LC-2.

On the memory pages section in chapter 5, it writes there: "Direct mode addressing gets page number from PC\[15:9\] and page offset from IR\[8:0\]." My question is, I don't understand why the format of PC and IR is in \[x:y\], can anyone explain it to me? I read on Wikipedia and it says that it should be base + offset, but why does the base and offset both have 2 separate values?

Thanks.

# Answer
The notation is as follows: FROM\[left bit : right bit\], so in your example PC\[15:9\] means take bitfield (number) from PC from fifteenth bit to ninth bit, inclusive, so 15 - 9 + 1 = 7 bits.
The same applies for IR\[8:0\] meaning take bitfield from IR from eight to zeroth bit inclusive.
For example PC\[14:14\] would be exactly one bit long and in such case by convention one would write PC\[14\].
> 1 votes

---
Tags: operating-systems
---


# Question
Title: Confusion over the complexity of parameter passing in merge sort
I'm working through CLRS on problem 4-2, which says the following:

> Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself.
>
> This problem examines the implications of three parameter-passing strategies:
>
> 1. An array is passed by pointer. Time $ = \Theta (1)$.
> 2. An array is passed by copying. Time $\Theta (N)$, where $N$ is the size of the array.
> 3. An array is passed by copying only the subrange that might be accessed by the called procedure. Time $= \Theta(q-p+1)$ if the subarray $A\[p \ldots q\]$ is passed.
>
> Consider the recursive merge sort algorithm. Give recurrences for the worst-case running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. Let $N$ be the size of the original problem and $n$ be the size of a subproblem.

For part (2), one solution I have seen is:

> $$T(n) = 2T(n/2) + cn + \color{red}{2N} = \color{blue}{4N} + cn + 2c(n/2) + 4T(n/4) = 8N + 2cn + 4c(n/4) + 8T(n/8) = \\ \qquad = \sum\_{i=0}^{\lg{n}-1}(cn + 2^iN) = \sum\_{i=0}^{\lg{n}-1}cn + N\sum\_{i=0}^{\lg{n}-1}2^i = cn\lg{n} + N\frac{2^{\lg{n}} - 1}{2-1} = cn\lg{n} + nN - N = \Theta(nN) \\ \qquad = \Theta(n^2)$$

I don't understand where the $\color{red}{2N}$ has come from. The $2T(n/2)$ is the "conquer" part, and the $cn$ is the "combine" part, leaving the $\color{red}{2N}$ to be the "divide" part, but I'm not sure why it's $2N$ rather than just $N$, as you are only copying the $N$-length arrary over once.

Also, I don't understand where the $\color{blue}{4N}$ has come from (following the previous equality). Surely, $$T(n) = 2T(n/2) + cn +2N \\ = 2\underbrace{\[2T(n/4) + c(n/2) + 2N \]}\_{T(n/2)} + cn + 2N \\ = 4T(n/4) +2cn + 6N \ ?$$

Finally, am I right in thinking that the last equality holds because $N$ is some subset of $n$, so $n$ = $k N$ (for some constant $k$), so $T(n) = \Theta(n) \cdot \Theta(N) = n \cdot n = n^2$?

# Answer
> 1 votes
The $N$ is incurred once for every recursive call, since this is the cost of passing a parameter. Since there are two recursive calls, it's $2N$. As for the $4N$, this seems like a mistake. Don't expect solutions you find on the internet to be correct. Finally, $N$ is *not* a subset of $n$. It is the size of the original array. A less confusing way to write the conclusion would be $\Theta(nN) = \Theta(N^2)$. Note that it is always the case that $n \leq N$ (and not the other way around).

# Answer
> 0 votes
I'm not sure how they got the $4N$ term either, but here's a simpler analysis. Let $T(n)$ be the cost of a recursive call of size $n$. We separate the costs of sorting, $S(n)$, and passing parameters, $P(n)$. We have:

* $T(n) = S(n) + P(n)$
* $S(n) = 2S(n/2) + cn$
* $P(n) = 2P(n/2) + N$

Solving by standard methods yields $T(n) \in \Theta(n^2)$.

---
Tags: algorithm-analysis, runtime-analysis, recursion, mergesort
---


# Question
Title: Prove the recursive enumerability of the class of NP-hard context-free languages
I was asked to prove that the next language is recursive enumerable :

$$L= \\{ \langle G \rangle \mid SAT\<L(G) \\} $$

where $G$ is a context free grammar and there is a polynomial reduction from the SAT problem to the language that's accepted by $G$.

I can't seem to understand why this problem is in RE. Isn't determining whether a word is accepted by a certain CFG done in a polynomial time? What am I missing here?

# Answer
You should distinguish between two cases. If $\mathsf{P} \neq \mathsf{NP}$ then $L(G)$ cannot be $\mathsf{NP}$-hard since $L(G) \in \mathsf{P}$. In this case, $L = \emptyset$.

Conversely, if $\mathsf{P} = \mathsf{NP}$, then all non-trivial languages in $\mathsf{P}$ are $\mathsf{NP}$-hard. In this case, $L = \\{ \langle G \rangle : L(G) \neq \emptyset, \Sigma^\* \\}$. It is possible to decide whether $L(G) \neq \emptyset$, and the problem of determining whether $L(G) \neq \Sigma^\*$ is clearly r.e. (in fact, it is $\Sigma\_1$-complete), and so $L$ is r.e. (in fact, $\Sigma\_1$-complete).
> 0 votes

---
Tags: complexity-theory, context-free, np-complete, reductions, decision-problem
---


# Question
Title: How does a computer determine the data type of a byte?
For example, if the computer has `10111100` stored on one particular byte of RAM, how does the computer know to interpret this byte as an integer, ASCII character, or something else? Is type data stored in an adjacent byte? (I don't think this would be the case as this would result in using twice the amount of space for one byte.)

I suspect that perhaps a computer does not even know the type of data, that only the program using it knows. My guess is that because RAM is **R**AM and therefore not read sequentially, that a particular program just tells the CPU to fetch the info from a specific address and the program defines how to treat it. This would seem to fit with programming things such as the need for typecasting.

Am I on the right track?

# Answer
Your suspicion is correct. The CPU doesn't care about the semantics of your data. Sometimes, though, it does make a difference. For example, some arithmetic operations produce different results when the arguments are semantically signed or unsigned. In that case you need to tell the CPU which interpretation you intended.

It is up to the programmer to make sense of her data. The CPU only obeys orders, blissfully unaware of their meaning or goals.
> 42 votes

# Answer
As others have already answered, today's common CPUs do not know what a given memory position contains; the software decides.

However, there are other possibilities. Lisp Machines for example used a tagged architecture which stored the type of each memory position; that way the hardware itself could do some of the work of high-level languages.

And even now, I guess you could consider the NX bit in Intel, AMD, ARM and other architectures to follow the same principle: distinguish at the hardware level whether a given memory zone contains data or instructions.

Also, just for completeness, in Harvard architectures (like some microcontrollers) data and instructions are physically separated, so the CPU does have some idea of what it is reading.

In this Quora question there's some commentary on how the tagged memory worked, its performance implications and demise, and more.
> 14 votes

# Answer
Yes. The program just gets a byte from the memory and it can interpret it however it wants.
> 4 votes

# Answer
There are no type annotations.
RAM stores pure data, and then program defines what to do.

With CPU registers is a bit harder, if you have registers of given type (like FPU), you tell what is inside.
Operations on floating point registers are explicitly using typed data. You or your compiler tell what and when should be put there, so you not have such freedom.
Computer does not make any assumptions on underlying data in RAM, and in registers with one exception - typed registers in CPU are of known type, optimised to deal with it. This is only to show that there are places where data is to be of expected type, but nothing stops you from casting strings to floats and multiply them.

In programming languages you specify type, or in higher level languages data is general and compiler / interpreter / VM encodes what is inside with overhead.
For example in C your pointer type tells what to do with data, how to access it.

Of course you can read string (characters) and treat then as floating point values, integers and mix them.
> 3 votes

# Answer
The CPU doesn't care, it executes assembly code, which justs merely moves data around, shift it, add it or multiply it...

Data Types are a higher level language concept: in C or C++ you need to specify Types for every single piece of data you manipulate; the C/C++ Compiler takes care of transforming these pieces of data into the right commands for the CPU to process (compilers write assembly code)

In some even higher level languages, Types may be inferred: in Python or Javascript, for example, one does not have to specify data types, yet data has a type and you can't add a string with an integer, but you can add a float with an integer: the 'compiler' (which in the case of Javascript is a JIT (Just in Time) Compiler. Javascript is often called an 'interpreted' language because historically browsers interpreted Javascript code, but nowadays Javascript engines are compilers.

Code, always ends up being compiled to machine code, but obviously machine code format depends on the machine you're targeting (x86 64bit code won't work on a x86 32 bits machine or a ARM processor for example)

So there is actually a lot of layers involved in running interpreted code.

Java and C# are other interesting ones, as Java or C# code is technically 'compiled' to a Java binary (bytecode), but that code itself is then interpreted by the Java Runtime, which is specific to the underlying hardware (one needs to install the JRE targeting the right machine to run Java binaries (Jars) )
> 3 votes

# Answer
Datatypes are not a hardware feature. The CPU knows a couple (well, a lot) of different commands. Those are called the *instruction set* of a CPU.

One of the best known ones is the x86 instruction set. If you search for "multiply" on this page, you get 50 results. `MULPD` and `MULSD` for the multiplication of doubles, `FIMUL` for integer multiplication, ...

Those commands work on registers. Registers are memory slots which can contain a fixed number of bits (often 32 or 64, depending on which architecture your CPU uses), no matter what these bits represent. Hence **the CPU instruction interprets the values of the registers in a different way, but the values themselves don't have types.**

An example was given at PyCon 2017 by Stuart Williams:
> 3 votes

# Answer
> ...that a particular program just tells the CPU to fetch the info from a specific address and the program defines how to treat it.

Exactly. But RAM is not read "sequentially", and it stands for *Random Access Memory* which is exactly the opposite.

Besides knowing what a byte *is*, you don't even know if it's a *byte*, or a fragment of a larger item like a floating-point number.

I'd like to add to other answers by giving some specific examples.

Consider `01000001`. The program might copy it from one place to another as part of a large parcel of data without any regard to its meaning. But copying that to the address used by the text-mode video buffer will cause the letter `A` to show in some position on the screen. The exact same action when the card is in a CGA graphics mode will display a red pixel and a blue pixel.

In a register, it could be the number 65 as an integer. Doing arithmetic to set the 32's bit could mean *anything* without context, but might specifically be changing a letter to lower case.

The 8086 CPU (still) has special instructions called DAA that is used when the register holds 2 decimal digits, so if you just used that instruction you are interpreting it as two digits `41`.

Programs *crash* because a memory word is read thinking it is a pointer when something otherwise was stored there.

Using a debugger, inspecting memory, a *map* is used to guide the interpretation for display. Without this symbol information, a low-level debugger lets you specify: show this address as 16-bit words, show this address as long floating point, as strings... whatever. Looking at a network packet dump or unknown file format, puzzling it out is a challenge.

That's a major source of power and flexibility in modern computer architecture: a memory cell can mean *anything*, data or instruction, implicit only in what it "means" to the program by what it does with the value and how that affects subsequent operations. *meaning* is deeper than integer width: are these characters ... characters in ascii or ebcdic? Forming words in English or SQU product codes? The address to send to or the return address it came from? The lowest level interpretation (logical bits; integer-like, signed or unsigned; float; bcd; pointer) is contextual at the instruction-set level, but you see that it's *all* context at some level: the *to* address is what it is because of the location it's printed on the envelope. It is contextual to the rules of the postman, not the CPU. The context is one big continuum, with bits on one end of it.

---

※ Footnote: The DAA instruction is encoded as a byte `00100111`. So that byte is the aforenamed instruction if read in the instruction stream, and the digits `27` if interpreted as bcd digits, and 0x27 = 39 as an integer, which is the numeral *9* in ASCII, and part of the interrupt table (half of INT 13 2-byte address, used for BIOS service routines).
> 2 votes

# Answer
The only way the computer knows that a memory location is an instruction is that a special-purpose register called the instruction pointer points to them at one point or another. If the instruction pointer points to a memory word, it is loaded as an instruction. Other than that, the computer has no way of knowing the difference between programs and other types of data.
> 1 votes

---
Tags: memory-hardware, memory-access, type-checking
---


# Question
Title: strange choice of constant when showing $an + b = O(n^2)$ ("Introduction to Algorithms" book)
In the third edition of Introduction to Algorithms, the authors state:

> ... when $a$ \> 0, any linear function $an+b$ is $O(n^2)$, which is easily verified by taking $c = a + |b|$ and $n\_0 = max(1, -b/a).$

\[In the above, $c$ and $n\_0$ come from the standard definition of big-oh:

$f(n)$ is in $O(g(n))$ if there exist positive constants $c$ and $n\_0$ such that $0 \le f(n) \le cg(n)$ for all $n \ge n\_0$.\]

I have no trouble accepting that $an+b \in O(n^2)$, but I'm questioning the motivation/origin of the weird choice of $n\_0$.

If we assume that $ n \ge 1$, then, since $a \> 0$, we have $an^2 \ge an$ and since $n^2 \ge 1$ we have $|b|n^2 \ge |b| \ge b$, implying that $(a+|b|)n^2 \ge an+b$. So it seems that $n\_0$ could simply have been taken as $1$. Or am I messing up somewhere?

# Answer
Because of the requirement $an+b\>0$. The definition requires $0 \leq f(n)$.
> 1 votes

---
Tags: algorithm-analysis, asymptotics
---


title: Round Robin Scheduling

text:
# Question
Title: Round Robin Scheduling
I understand that a big advantage of round robin scheduling over non-preemptive schedulers is that it dramatically improves average response times. By limiting each task to a certain amount of time, the operating system can ensure that it can cycle through all ready tasks, giving each one a chance to run, and the length of the quantum and the number of processes in the run queue.

How do time slice duration and context switching affect each other in a round robin scheduling algorithm?

# Answer
> 1 votes
You're confusing three aspects of scheduling that can be chosen independently: preemptivity, ordering strategy, and time slice duration.

*Preemptive* vs *non-preemptive* determines when a context switch may happen. With a non-preemptive scheduler, a task¹ keeps executing until it voluntarily yields the processor back to the operating system², and at this point the operating system may schedule another task. With a preemptive scheduler, the operating system interrupts tasks whenever it wants — interrupting a task is called preemption. In practice, preemption happens when a hardware interrupt is triggered, and one of these interrupts is a timer interrupt that the operating system programs in order to limit how long a task will execute without interruption.

*Round-robin* is a *scheduling strategy* (also called *scheduling discipline*), i.e. a way to decide which task gets scheduled once the current task yields control to the operating system. Most scheduling strategies, including round-robin, make sense whether yielding is voluntary (non-preemptive scheduling) or forced (preemptive scheduling).

Round-robin is a simple strategy where the scheduler maintains a queue of tasks. On a context switch, the task that just stopped goes to the back of the queue, and the task at the front of the queue is resumed. In other words, the next task to execute is the one that has been stopped for the longest time. This strategy is *fair*³ in the sense that every task gets to execute eventually (no task is *starved*, waiting forever for CPU time): no task can prevent another task from executing (except in a non-preemptive setting, by never yielding).

Exercise: suppose that tasks can create other tasks. The new task has to be added to the scheduler's queue. Where do you put it?

This description above only considers *ready* tasks, i.e. tasks that have something to do. If a task is *blocked*, i.e if it can't do anything because it's waiting for an external event, then the task is removed from the scheduler's queue until it becomes unblocked because that event happened. Tasks become blocked because they're waiting for I/O — either communication with another task or communication with a peripheral.

Where do you put a task when it becomes unblocked? Even if you try to keep a “pure” round-robin scheme, there are several choices. A simple choice is to put the unblocked task at the back of the queue. This choice preserves the fairness property of round-robin. Another choice is to keep all the tasks in the queue, even the blocked ones, but skip over blocked ones when scheduling. This also preserves fairness.

However, schedulers usually deviate from a simple round-robin when it comes to I/O, because round-robin is bad for latency. Scheduling is often a compromise between throughput (getting as much work done as possible in total) and latency (responding to specific events quickly). Throughput is what matters for computational tasks, but I/O tasks often need low latency. If the CPU needs to read data from a peripheral, or to display the next frame of a video, or to send a signal to the brakes because the brake pedal was pressed, then a fast response is needed, and waiting for the task's next turn through a queue may not be acceptable. In practice, schedulers are often round-robin at the core, but with modifications to schedule tasks earlier when they're involved in I/O, in order to reduce latency.

So far I've discussed when preemption occurs and which task gets scheduled next. *Time slice duration* is another aspect of the scheduling strategy. Time slice duration is another example of a compromise between latency and throughput. Context switching has a cost. If the system performs a lot of context switches, the time spent doing context switches instead of useful work is wasted. To maximize throughput, there must be as few context switches as possible, meaning long time slices. On the other hand, a long time slice means high latency. Scheduling tasks immediately on I/O solves part of the latency aspect, but only part. For example, a video player needs CPU time to prepare for the next frame, even if it doesn't receive many I/O events. Complex schedulers tend to classify tasks as I/O-bound or CPU-bound. CPU-bound tasks get long time slices, but infrequently. I/O-bound get frequent but short time slices. Hardware events can always interrupt a time slice, which makes the interrupted task eligible for a longer time slice later or for an earlier re-schedule. The design space is very large. If you're interested in that, I recommend reading the literature around the Linux kernel in places like LWN, which has several different scheduling strategies (you'd pick a different one for an interactive device, for a networked server or for a number cruncher), with people actively working at improving them and writing up their findings.

¹ <sub> or thread. In this context, *task* and *thread* are synonymous. </sub>
² <sub> In this context, *operating system* and *kernel* are synonymous. </sub>
³ <sub> Note that this is a technical sense of the word “fairness”, which ignores the fact that some tasks may need more time than others. There are many more complex notions of fairness which I won't go into in this answer. </sub>

# Answer
> 0 votes
Ideally we could ignore context switching and say its certain constant C, but generally you would want for the time quanta to be bigger than the context switching time C. This in order for the CPU to keep the process as along as possible compared to the time of the context switch.

# Answer
> 0 votes
if your quantum is longer, your system will be less fair, but if your quantum is to small, the the time used for context switching will become larger and your yield lower.

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Does every computational problem have a decision version?
Is the following claim correct?:

> Every computational problem has a decision version of roughly equal computational difficulty.

If the above claim is correct, please give a reference for it.

(I find this pdf from Prof. E. Demaine, but he doesn't provide any references.)

# Answer
> 7 votes
Here is a "counterexample": sorting. The natural decision version of sorting is deciding whether a given array is sorted. Another natural decision version is given an array and a permutation, decide whether the permutation correctly records the sorted order of the array. In both cases, the "decision versions" can be solved in linear time, while sorting itself (in most models) requires loglinear time.

Here is another "counterexample": consensus. This is a classical problem in distributed computing. I'm not sure it has a "decision version".

The claim you are stating is not a mathematical claim; it's just a comment whose goal is to explain why in introductory classes we only consider decision problems. There are three reasons: First, decision problems can be used to analyze many other types of computational problems (though not all of them). Second, it has become conventional to consider only decision problems (for example P and NP are classes of decision problems). Third, introductory classes are introductory, and so their scope is limited.

In order to make the claim a mathematical claim (and so, potentially, right or wrong), you will need to define all the concepts involved; there might be several ways of doing it, resulting in different interpretations of the claim. Some interpretations will result in valid statements: for example, optimization problems have canonical decision problems, and to some extent the two kinds of problems are equivalent in complexity. Other interpretations might be more problematic, for example if they encompass my first counterexample. Another source of difficulty is computational problems like my second counterexample to which this entire paradigm seems inapplicable.

Lecturers often make such comments, and these are supposed to be helpful for you as a student. If you find one of these comments confusing, I think it's best to just ignore it. If you have access to the professor, you can discuss the matter with them, but otherwise just drop the matter.

# Answer
> 5 votes
> *Decision problems are too limited*. Some computational problems are not easily expressed as decision problems. Indeed, we will introduce several classes in the book to capture tasks such as computing non-Boolean functions, solving search problems, approximating optimization problems, interaction, and more. Yet the framework of decision problems turn out to be surprisingly expressive, and we will often use it in this book.

---

**A.Arora, B. Barak, "Computational Complexity A Modern Approach", 2009, pg. 28.**

# Answer
> 4 votes
*Decision problems* (checking whether an instance of a problem has a solution or not) and *Search problems* (actually finding a solution of an instance of a problem if it has one) are two sides of the same coin.

Suppose that you have a computable function $f : \mathbb{N} \to \mathbb{N}$.

Then you can easily convert it to a decision version using this language:

$L = \\{ (x,n) \mid f(x) \leq n \\}$

Clearly if you can solve the decision problem $(x,n) \in^? L$ you can compute $f(x)$ in $O(\log f(x))$ steps using a binary search.

Usually the equivalent decision problem is formulated in a manner that reflects the structure of the source problem; a well-known example is boolean satisfiability.

"Given a boolean formula $\varphi$ in $n$ variables $x\_1, x\_2, ..., x\_n$ calculate a satisfying assignment if it exists"

This can be solved using the decision version: "Given a boolean formula $\varphi$, is it satisfiable?" (i.e. $\varphi \in^? SAT$)

You can start setting $x\_1 = True$ and checking if $\varphi\_{x\_1=T}$ (the formula $\varphi$ in which all $x\_1$ occurrences have been replace with $True$ is satisfiable). If the answer is $Yes$ ($\varphi\_{x\_1=T} \in SAT$) then set $x\_1 = True$, $x\_1 = False$ otherwise. Then continue with $x\_2, x\_3, ...$ up to $x\_n$ and at the end you'll have a satisfying assignment, or the procedure will stop at some $x\_i$ for which $\varphi\_{...,x\_i=T} \notin SAT$ and $\varphi\_{...,x\_i=F} \notin SAT$ (i.e. the formula is unsatisfiable).

---
Tags: decision-problem
---


# Question
Title: Showing that a language is not recursive
I was given the next function CH(x) that is defined like this:

$CH(\<M\>)$ outputs the computation history of the run of M on epsilon if M halts on epsilon. If it doesn't the function returns epsilon. I was asked to prove that the language

{$ M, CH(\<M\>) |$ M is a turing machine } is in co-RE\R

I can't seem to understand why the language isn't recursive enumerable I do see why it's not in R (The halting problem becomes decidable)

# Answer
In order to prove $L \in coRE$ you could prove that $\overline{L} = \\{\langle M,w \rangle | M \text{ is a TM and } w \neq CH\left( \langle M \rangle \right) \\}$ is r.e.

Given input $\langle M,w \rangle$

* reject if input is not well-formed including $\epsilon$
* if $w \neq \epsilon$. Then $w$ must be a history. If it is not a legal history, just **accept** since $CH(\langle M \rangle) \neq w$. Otherwise inspect the history, and assume it runs for $k$ steps. Then simulate $M$ for $k$ steps and compare its history with $w$. If they are NOT equal then **accept**, otherwise reject/loop forever.
* if $w = \epsilon$. Then run $M$ until it halts. If it halts then **accept** since $CH(M)$ must be a legal history different from $\epsilon$ which means $CH(\langle M \rangle) \neq w = \epsilon$. Otherwise, i.e. $M$ does not halt. But our TM which simulates $M$ also runs forever which means that $CH(M) = \epsilon = w$, but it will never halt and so never accept.
> 1 votes

# Answer
Note that $M$ diverges on $\epsilon$ iff $\langle M, \epsilon \rangle$ belongs to your language. This provides a reduction from a non RE problem to yours.
> 0 votes

---
Tags: computability, turing-machines, undecidability, decision-problem
---


# Question
Title: In counting sort time complexity notation O(n+k), k is number of distinct elements?
Do I get right, that if we say that counting sort time complexity is O(n+k), this notation means that n is number of all elements to sort and **k is number of *distinct* elements**?

For example for array \[ 3, 5, 7, 5, 1, 5\] n = 6 and k = 4 ?

# Answer
> 1 votes
Time complexity of counting sort is $O(n + k)$ where $n$ is the size of array, and $k$ is the maximum element in the array, not the number of distinct elements.

For example if we have the array $A = \text{{1, 2, 3, 3, 3, 4, 5, 8, 8}}$ Let's say that for our array $n = 9$ because we have $9$ elements, and $k =8$ because our biggest element is $8$.

Now we create another array $B$ of size $k$ where for each number in the range $\[1, k\]$ we keep how many times in occurs in the array $A$. $B = \text{{1, 1, 3, 1, 1, 0, 0, 2}}$.

Now we iterate through the array $B$ and for each index $i$ in $B$ we do exactly $B\[i\]$ iterations. We can see that sum of all numbers in $B$ equal $n$ so we do $k$ iterations in the first for and $n$ iterations in the second for.

In total the complexity is $O(n+k)$ where $n$ is the size of array and $k$ is the biggest element in the array.

# Answer
> 1 votes
No k isn't the number of distinct elements, instead it refers to the **range** which is given by **Maximum element** in the array + 1, i.e. 1 to max+1.

**In your case the value of k will be max element( i.e. 7) + 1= 8**

---
Tags: sorting
---


# Question
Title: NFA-epsilon: epsilon loops, and how do I deal with them?
I am currently studying Automatons and have one, albeit simple, question about NFA-epsilon 'loops'
I know that a string can advance using epsilon without having anything read. So my first question would be, if you had a chain of epsilon-arches, would you just jump to the end of the chain instantaneously (Figure 1) ?
My other question is; At the end (Figure 1) at the accept state there is en epsilon-arch going back to a previous state, would this cause a loop and in-turn cause the string to never halt, or would it just create another fork (endlessly?)?

My last question is, how would I approach said NFA-epsilon example with these example strings: 1011100, 0101111?
To me the second string would be accepted, while the first one would be rejected because it has 2 zeroes at the end of the string. I am unsure though!

## (Figure 1)

Thanks in advance! :)

# Answer
> 2 votes
You would not "jump" to the end of the chain immediately. An epsilon transition is a convenience, a "way of modeling the systems whose current states are not precisely known". In fact, you would actually consider your self to be at all reachable (via epsilon transition) states at once. This is part of the non-determinism, you're not necessarily at one state, but rather can be at multiple at the same time.

In your example, starting at $q\_0$, we have epsilon transitions allowing us to be in states: $\\{q\_0, q\_1, q\_2, q\_4, q\_5, q\_6\\}$ at the same time. This means all values that *any* of these states transition on, we can transition on. In your example, from $\\{q\_0, q\_1, q\_2, q\_4, q\_5, q\_6\\}$ we can transition on $\\{1, 0\\}$. In fact, because we're already at state $q\_6$, we don't necessarily *need* to transition at all because we're already accepting.

For your second question, you would not be in an endless loop, similar to my previous explanation, having a loop of epsilon transitions would not affect how many states we're currently at. If we're at $q\_5$, we're also at $q\_6$, looping back to $q\_5$ won't matter because we're already there. The importance of the loop is the fact that $q\_5$ also transitions on $1$, so $q\_6$ epsilon-transitioning to $q\_5$ allows us to accept however many $1$'s we need.

---

I think an *extremely* helpful way to digest NFAs (because they can be confusing sometimes) is to apply the Powerset Construction or at least think about how it would be applied to your example. As fade2black said, the NFA will create many branches of computation, this construction will only create 1, which in my opinion makes it much easier to interpret.

In your example the powerset construction would look like this:

```
Set         \ Transition | 1                        | 0
-------------------------+--------------------------+-----
{q0, q1, q2, q4, q5, q6} | {q0, q1, q2, q4, q5, q6} | {q3}
{q3}                     | {q2, q4, q5, q6}         | N/A
{q2, q4, q5, q6}         | {q5, q6}                 | {q3}
{q5, q6}                 | {q5, q6}                 | N/A

```

We can then define:

$$\begin{align} A & = \\{q\_0, q\_1, q\_2, q\_4, q\_5, q\_6\\}\\ B & = \\{q\_3\\}\\ C & = \\{q\_2, q\_4, q\_5, q\_6\\}\\ D & = \\{q\_5, q\_6\\}\\ \end{align}$$

And get the resulting equivalent DFA:

Then running your input becomes trivial.

# Answer
> 2 votes
> if you had a chain of epsilon-arches, would you just jump to the end of the chain instantaneously

I am not sure for "instantaneously", but I would say it accepts the empty string $\epsilon$.

> would this cause a loop and in-turn cause the string to never halt, or would it just create another fork (endlessly?)?

Your input string will be accepted. On any input, a NFA runs by creating many branches of computation in parallel and if one of them reaches the accept states, after it reads the last symbol of the input, then your string is accepted and the entire computation halts. You kind of choose at least onе fork that leads the NFA to the accept state.

> how would I approach said NFA-epsilon example with these example strings: 1011100, 0101111?

Right the first string is not accepted, the second one is accepted.

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


# Question
Title: Powerset generation using recursion and time complexity
I have a program that generates power set of a given string, the set being the characters of the string.

```
public static Set subsets(String s) {
    Set subsets = new HashSet();
    if (s.length() == 0) {
        subsets.add("");
    } else if (s.length() == 1) {
        subsets.add("");
        subsets.add(s);
    } else {
        for (int i = 0; i < s.length() - 1; i++) {
            Set sets = subsets(s.substring(i + 1));
            for (String st : sets) {
                subsets.add(s.substring(0, 1) + st);
            }
            subsets.addAll(sets);
        }
    }
    return subsets;
}

```

I don't seem to understand how to calculate time complexity of the above implementation.I understand that `String.substring` and `creating Set Objects` are pretty expensive, but if I assume these two operations to take constant time, what would be the overall time complexity?

# Answer
> 3 votes
You should have converted you Java code into pseudo code.

In fact, if your code runs exactly as you describe, namely given a set $S$ as a string it generate all subsets of the symbols of the input string, then the running time is trivial. You just need to count the number of different subsets generated by your algorithm/code. Input size is the length of the input string, i.e., number of characters. So, if the number of characters is $n$ then there are total $2^n$ different subsets. So, the time complexity is $O(2^n)$.

---
Tags: algorithms, time-complexity
---


title: Complement of context free language

text:
# Question
Title: Complement of context free language
If a language X regular, then is the complement of X also a regular language? If yes, then thank you, else can you please explain why

# Answer
> 1 votes
Yes, the complement of a regular language is regular. If $L$ is regular then there is a DFA accepting that language. In particular, its states can be classified as ACCEPTING states and non-ACCEPTING states. Just turn non-ACCEPTING states into ACCEPTING, and ACCEPTING states into non-ACCEPTING states and you will have a DFA accepting $\overline{L}$.

---
Tags: context-free
---


# Question
Title: Show that run time complexity of operations on 2-4 tree is $O(\lg n)$
I just studied about this 2-4 tree which is a self-balanced tree. Various sources and textbook often mentioned that the insertion, deleting and searching of this tree is $O(\lg n)$.

However, none of them explain the detailed reasons for that run-time complexity. Neither of them also explains them mathematically for the reason behind that run-time complexity.

Therefore, I would like to ask how do i basically show that the run time complexity to process a 2-4 with n keys is $O(\lg n)$?

# Answer
The tree is height-balanced, therefore the height of the tree is $O(\log n)$. So any insertion has to travel at most $O(\log n)$ steps deep into the tree to find the proper insertion place. Then it also takes another $O(\log n)$ steps the rebalance the tree. The same idea can be applied to searching and deleting in the tree.

The $O(\log n)$ height bound may be difficult to see in a 2-3-4 tree, so I will offer an alternative way to come to this realization. Any 2-3-4 tree is *isometric* to a proper Red-Black tree. That is to say, "they are equivalent data structures. In other words, for every 2–3–4 tree, there exists at least one red–black tree with data elements in the same order." A Red-Black tree is a balanced binary search tree whose height is more clearly bounded by $O(\log n)$ and so are all of its operations.
> 2 votes

---
Tags: trees
---


# Question
Title: How to predict the next image in a sequence, or predict the deblurring of an image?
I have 3 versions of an image at lower resolutions - 480p, 720p, and 1080p. Is it possible to use those 3 images to predict the next highest resolution image (the 4k image)?

My first guess was that I could calculate the difference (or momentum or acceleration?) of each pixel between images and use that to predict the new 4th image. I assume this would require me to give all pictures the same number of pixels. I also assume that the differences in each pixel between images would need to be smooth. Would this work?

My other guess was that maybe there is some kind of statistics or machine learning technique that I could use, but I don't know anything about that stuff.

Thanks!

Ps - this man is not my real data. My real images are an intensity map (temperatures over an area) at different resolutions. I suspect that the introduction of colors might complicate things, so should we pretend that the images below are black-and-white images?

Here are the pictures:

# Answer
No. You can't create information out of nothing. There's no magic. There's not enough information in the three lower-res to uniquely determine the high-res image.

Of course, you can always upscale an image, but that won't make it any higher quality or sharper than what you started with.

Note that "4K" is a marketing term, not a precise specification of an image resolution. There are multiple different resolutions that are all marketed as "4K". See https://en.wikipedia.org/wiki/4K\_resolution.
> 1 votes

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


# Question
Title: What is The correct terminology for expressing *this* notion of complexity
Say for example, I have an algorithm $Al\_i$ that produces output from the set $S = \\{s\_i\\}$ for problems from the set $P = \\{p\_i\\}$, and another algorithm $Al\_j$ that also produces output from the set $S = \\{s\_i\\}$ for problems from the set $P = \\{p\_i\\}$. For the purposes of this question, $Al\_j$ and $Al\_i$ are the same.
Or, if I have two systems that produce the same output given the same input, then we can treat these systems as the same.
Generally, if two objects do the same things (produce the same output for identical input, convey the same information as output), then these objects are identical. The processing of the systems are not relevant. We're only concerned with the output of the systems, objects, entities, etc.
Now, there are many such identical systems. Say $T\_i$ is some set of all identical objects/entities/systems that do some same thing. Let $t\_i^\*$ be the object in $T\_i$ with the smallest Kolmogorov complexity.

> Is there a conventional terminology for expressing $t\_i^\*$?

An example of a $T\_i$ may be the set of all proofs for a particular theorem. (Here the Kolmogorov complexity of all theorems includes each intermediate theorem invoked in its proof (so basically each theorem would first be expressed in axioms first and computing the complexity of that expression)). I may be interested in referring to the least complex theorem (using the aforementioned notion of the complexity of the axiomatic expression of the theorem).
Things can be defined by form or by function. I understand that Kolmogorov complexity traditionally considers the former, while I am concerned with the Kolmogorov complexity of the latter. A picture has a defined form, and an algorithm that only produces that picture is no different from the picture itself. What about an algorithm that produces different output. We could look at the form of the algorithm, or look at its function. Looking at function, all correct algorithms for a particular problem are identical. Bogosort is identical to quicksort which is identical to mergesort, heapsort, etc.
I am concerned with the smallest Kolmogorov complexity of any sorting algorithm.

# Answer
> 1 votes
Kolmogorov's complexity is defined relative to a specific representation. It is rather meaningless to ask what is the minimal Kolmogorov complexity of a certain object over all possible representations (obviously, this requires a precise definition for what constitutes a valid representation).

To see why, consider for example the following question: what is the minimal Kolmogorov complexity of the identity function over all admissible numberings? The answer is trivially $1$, since I can encode the identity function as "0" (a single bit string).

---
Tags: information-theory, kolmogorov-complexity
---


# Question
Title: Prove Partition is NP-Complete using that SubsetSum so is it
The *SubsetSum problem* decides whether a set $S = \\{s\_1, s\_2,..., s\_n\\}$ and $k \in \mathbb{N}\_0$ contains a subset of $S$ such that its summation is $k$ or not. This problem is NP-Complete.

The *Partition problem* decides whether a set $S = \\{s\_1, s\_2,..., s\_n\\}$ can be partitionated in two subsets such that the difference between the sums of the both sets are lesser or equal to $K$.

Prove that the partition problem is NP-Complete using that *SubsetSum* so is it.

Any ideas?

# Answer
Define your $\rm P{\small ARTITION}(S, K)$ problem as:

"*Are there partitions $S\_1, S\_2$ of $S$ such that $|\text{sum}(S\_1) - \text{sum}(S\_2)| \leq K$, where $\text{sum}(S\_i)$ is the sum of all elements of $S\_i$?*".

Then $\rm P {\small ARTITION}(S, 0)$ would mean $|\text{sum}(S\_1) - \text{sum}(S\_2)| \leq 0$ which is true only if $\text{sum}(S\_1) = \text{sum}(S\_2)$. Thus, given $S$ we could reduce the $\rm S{\small UBSET}(S,k)$ problem to the problem asking for existence of two partitions of $S$ with equal sums of elements---$\rm P{\small ARTITION}(S, 0)$.

The reduction to the latter can be done as following:
Let $s=\text{sum(S)}$ and define a new set $S\_{new} = S \cup \\{2k − s\\}$. We choose $2k-s$ since the sum of $S\_{new}$ is $2k-s+s = 2k = k+k$, and we want two partitions with equal sizes equal to $k$.

Now call (reduction!) $\rm P{\small ARTITION}(S\_{new},0)$. If it returns YES/TRUE then $S\_{new}$ can be partitioned into two sets $S\_1$ and $S\_2$ with sums equal to $k$. Also notice that either $S\_1$ or $S\_2$ can contain the new element $2k − s$ (since they are partitions) meaning that either $S\_1$ or $S\_2$ is a subset of $S$. Thus we have a subset (without the element $2k − s$) of $S$ with the sum $k$, and we return YES/TRUE. Otherwise, if we get NO/FALSE then return NO/FALSE.
> 2 votes

---
Tags: complexity-theory, np-complete, decision-problem
---


# Question
Title: Solve T(n) = T(n-1)*n with repeated substitution
I'm trying to solve T(n) = T(n-1)\*n using repeated substitution.

I can expand it, but I'm having trouble with geometric sequences for any problem. I find I'm just memorizing solutions to typical problems. It's sometimes hard for me to go from the expanded equation to a general equation that I can simplify.

T(n) = T(n-1)(n)

T(n) = T(n-2)(n-1)(n)

T(n) = T(n- 3)(n-2)(n-1)(n)

I'm not sure how to generalize this to ultimately find the big O. Any tips are appreciated!

# Answer
> 1 votes
This is the rucursive formula for $n$ factorial.

Define the formula $T(n)$ for $n \geq 0$ as $T(n) = nT(n-1)$. By repeated substitutions observe that $$ T(0) = 1$$ $$ T(1) = 1\times T(0)=1 \times 1$$ $$ T(2) = 2 \times T(1)=2\times 1\times 1$$ $$ T(3) = 3\times T(2)=3\times 2\times 1\times 1$$ $$\dots$$ $$T(n) = nT(n-1)=n\times (n-1)(n-2)\dots 1\times 1 $$ Thus by simple observation you can easily guess the pattern of product of the first $n$ positive integers.

For a complete proof you need to prove that $T(n) = n!$. This is easily done by induction. For $n=0$, $T(n)=1 = 0!$. Assume that formula is true for $n-1$. Then $T(n)=nT(n-1)=n(n-1)!=n!$ which completes the proof. So $T(n)$ is $\Theta(n!)$.

There is no a standard method to solve such kind of recurrence relations, but you usually guess the explicit form of the formula and proof it, for example, using induction or other technique or method.

As an exercise try to guess and prove explicit formulas for

* $T(0) = 1, T(n)=2T(n-1)$
* $T(0) = 1, T(n) = nT(n-2)$, for only even $n$s.

---
Tags: complexity-theory, recurrence-relation
---


title: true dependence Question

text:
# Question
Title: true dependence Question
Let's Have

```
i1. lw $s2,0($s1)
i2. lw $s1,40($s6)
i3. sub $s6,$s1,$s2
i4. add $s6,$s2,$s2
i5. or $s3,$s6,$zero
i6. sw $s6,50($s1)

```

> what is the true dependence for register $s2 ?

i find 2
i1 -\> i3 and i1-\>i4

> what is the true dependence for register $s1 ?

i find 1
i2 -\> i3

> what is the true dependence for register $s6 ?

i find 2
i4 -\> i5
i4 -\> i6 ( i know that store instruction read register before store in it ! or i'm wrong ? )

---

Question 2 : if we have some thing like that

```
i1. add $s6,$s3,$s4
i2. add $s5,$s1,$s2
i3. add $s6,$s5,$s7
i4. add $s8,$s6,$s9

```

> and we want to calculate true dependence for register $s6

it just 1 ? i3 -\> i4 ?
or 2 ? i1 -\> i4 and i3 -\> i4 ?
in other words ? we calculate just the last write on register or all ?

# Answer
Only the most recent write counts.

For example in Q2, i4 cannot directly depend on the result of i1 because \\$s6 was overwritten between them, so the result of i1 is not available. When a register is overwritten, from then on no instruction can depend on its old value, in the sense that instructions decoded later than the write necessarily refer to values at least as old as the write.

That is indeed the core principle that register renaming is based on, registers can be renamed on write precisely because it is only the most recent value that can be referred to by newer instructions. The name-relationship between i1 and i4 does not survive renaming, i3 would give \\$s6 a new name and it is that name which i4 would see, not the old name allocated by i1. In fact when i3 retires, the name allocated by i1 can be freed and reused, because it is known that no newer instruction could refer to the result of i1 anymore and since i3 is the oldest instruction in the machine (it's retiring) that means that no instruction currently in the machine is referring to it either.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Run time of recurrence with five uneven calls
I am trying to figure how to find an upper bound for the running time of a given recurrence relation (without proving the bound) using the Iteration method. The recurrence is:

$$T(n)=2T\left(\frac{n}{5}\right)+3T\left(\frac{n}{10}\right)+n$$

I tried to iterate over it and got:

$$\begin{align} T(n)& =2T\left(\frac{n}{5}\right)+3T\left(\frac{n}{10}\right)+n\\\\[0.5em\] & =2\left(2T\left(\frac{n}{25}\right)+3T\left(\frac{n}{50}\right)+\frac{n}{5}\right)+3\left(2T\left(\frac{n}{50}\right)+3T\left(\frac{n}{100}\right) + \frac{n}{10}\right)+n\\\\[0.5em\] & =10T\left(\frac{n}{25}\right) + 6T\left(\frac{n}{50}\right) +9T\left(\frac{n}{100}\right)+\frac{7n}{10} \end{align}$$

And couldn't know how to continue from here, any hints?

# Answer
I'll offer up a more general claim and a proof, you can apply it to your scenario as needed.

# The Uneven Split Theorem

Let $c$ and $k$ be positive constants.

Then let $\\{a\_1, a\_2, \dots a\_k\\}$ be positive constants such that $\sum\_1^k a\_i \< 1$.

We also must have a recurrence of the form:

$$\begin{align} T(n) & \leq c & 0 \< n \< max\\{a\_1^{-1}, a\_2^{-1}, \dots a\_k^{-1}\\}\\ T(n) & \leq cn + T(a\_1 n) + T(a\_2 n) + \dots T(a\_k n) & n \geq max\\{a\_1^{-1}, a\_2^{-1}, \dots a\_k^{-1}\\} \end{align}$$

## Claim

Then I claim $T(n) \leq bn$ where:

$$b = \frac{c}{1 - \left(\sum\_1^k a\_i\right)}$$

## Proof by Induction

**Basis**: $n \< max\\{a\_1^{-1}, a\_2^{-1}, \dots a\_k^{-1}\\} \implies T(n) \leq c \< b \< bn$

**Induction**: Assume true for any $n' \< n$, we then have

$$\begin{align} T(n) & \leq cn + T(\lfloor a\_1 n \rfloor) + T(\lfloor a\_2 n \rfloor) + \dots + T(\lfloor a\_k n \rfloor)\\ & \leq cn + b \lfloor a\_1 n \rfloor + b \lfloor a\_2 n \rfloor + \dots + b \lfloor a\_k n \rfloor\\ & \leq cn + b a\_1 n + b a\_2 n + \dots + b a\_k n\\ & = cn + bn \sum\_1^k a\_i\\\\[0.5em\] & = \frac{cn - cn \sum\_1^k a\_i }{1 - \left(\sum\_1^k a\_i\right)} + \frac{cn \sum\_1^k a\_i}{1 - \left(\sum\_1^k a\_i\right)}\\\\[0.5em\] & = \frac{cn}{1 - \left(\sum\_1^k a\_i\right)}\\ & = bn & \square \end{align}$$

Then we have $T(n) \< bn \implies T(n) = O(n)$.

We also know $T(n) = \Omega(n)$ by the recurrence definition, therefore $T(n) = \Theta(n)$.

---

Next apply it to your recurrence of the form:

$$T(n)=cn + T\left(\frac{n}{5}\right) + T\left(\frac{n}{5}\right) +T\left(\frac{n}{10}\right) + T\left(\frac{n}{10}\right) + T\left(\frac{n}{10}\right)$$

I'll leave this for you to figure out the $a\_k$'s and $b$.

---

A pretty quick rule of thumb if the work done per recursion is linear $(cn)$:

* If the constants in the recursion calls sum to less than $1$, it's $O(n)$.
* If the constants sum to exactly $1$, it's $O(n \log n)$.
> 4 votes

# Answer
We could roughly tight-bound as

$$ 2T(\frac{n}{10})+3T(\frac{n}{10})+n \leq 2T(\frac{n}{5})+3T(\frac{n}{10})+n \leq 2T(\frac{n}{5})+3T(\frac{n}{5})+n$$

$$ 5T(\frac{n}{10})+n \leq 2T(\frac{n}{5})+3T(\frac{n}{10})+n \leq 5T(\frac{n}{5})+n$$

Then solve separately $T(n) = 5T(\frac{n}{10})+n$ for the lower bound and $T(n) = 5T(\frac{n}{5})+n$ for the upper bound. In both cases we could take $T(0)= 1$.
> 0 votes

# Answer
For what it's worth, here is a very simple inductive proof that does not reference more general theorems (since you may or may not be willing to use such a theorem).

I show that $2T(\frac{n}{5}) \geq 3T(\frac{n}{10})$ for all $n \geq 5$.

With that, it becomes clear that $T(n) \leq n + 4T(n/5) \in \Theta(n)$.

**Base Case:** For $n = 5$,

$$2T(5/5) = 2T(1) = 2(1 + 2T(0) + 3T(0)) = 2(1 + 2 + 3) = 12$$ $$3T(5/10) = 3T(0) = 3$$

**Inductive Case:** Pick arbitrary $n \> 5$. Assume the claim is correct for all relevant $m \< n$.

We have,

$$ 2T(\frac{n}{5}) = 2\[\frac{n}{5} + 2T(\frac{n/5}{5}) + 3T(\frac{n/5}{10})\] = \frac{2n}{5} + 4T(\frac{n/5}{5}) + 6T(\frac{n/10}{5})$$

And,

$$ 3T(\frac{n}{10}) = 3\[\frac{n}{10} + 2T(\frac{n/10}{5}) + 3T(\frac{n/10}{10})\] = \frac{3n}{10} + 6T(\frac{n/5}{10}) + 9T(\frac{n/10}{10}) $$

We immediately see that,

$$ \frac{2n}{5} \geq \frac{3n}{10} $$

And that, letting $m = \frac{n}{5}$ and $m' = \frac{n}{10}$, using the Inductive Hypothesis, we have

$$ 4T(\frac{m}{5}) \geq 6T(\frac{m}{10}) \iff 2T(\frac{m}{5}) \geq 3T(\frac{m}{10}) $$

$$ 6T(\frac{m'}{5}) \geq 9T(\frac{m'}{10}) \iff 2T(\frac{m'}{5}) \geq 3T(\frac{m'}{10}) $$

Thus, $ 2T(\frac{n}{5}) \geq 3T(\frac{n}{10}) $ as required.

Major as well as minor corrections and comments are very welcome.
> 0 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Convert conjunctive normal form to equivalent boolean formula with only NAND gates
Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NAND gates with fan-in 2, without introducing any new dummy boolean variables. I'm wondering how much this will increase the size of the formula. If $\varphi$ has size $n$, how large does the resulting formula need to be? Can I convert $\varphi$ to an equivalent formula with only NAND gates that has size $O(n)$? If $O(n)$ isn't achievable, what's the best that is?

# Answer
Yes, it can be converted to such a formula of size $O(n)$ (i.e., only a constant-factor increase in formula size). The conversion simply recursively applies the following rules:

$$\begin{align\*} \neg a &\equiv NAND(a,\text{True})\\ a \lor b &\equiv NAND(\neg a, \neg b)\\ a \land b &\equiv \neg NAND(a,b) \end{align\*}$$

It is easy to check that the resulting formula has linear size.

For instance, the clause $x\_1 \lor \neg x\_2 \lor \neg x\_3$ represents $(x\_1 \lor \neg x\_2) \lor \neg x\_3$, so applying the above rules we obtain the boolean formula

$$NAND(NAND(NAND(NAND(x\_1,\text{True}),x\_2),\text{True}),x\_3).$$

In this way, each clause can be converted to a boolean formula of size $O(1)$. All that remains is to convert the conjunction of these clauses, and that can be done by expressing $c\_1 \land \cdots \land c\_m$ as $((c\_1 \land c\_2) \land \cdots) \land c\_m$ and then applying the rule for $a \land b$ repeatedly.
> 2 votes

---
Tags: logic, space-complexity, first-order-logic, propositional-logic
---


title: DFS - Checking if a graph is bipartite

text:
# Question
Title: DFS - Checking if a graph is bipartite
I wonder what will be the complexity of this algorithm of mine and why, used to check whether a graph (given in the form of neighbors list) is bipartite or not using DFS.

The algorithm works as following:

We will use edges classification, and look for back edges.

If we found one, it means there is a circle in the graph.

We will now check whether the cycle is odd cycle or not, using the the pi attribute added to each vertex, counting the number of edges participating in the cycle.

If the cycle is an odd one, return false. Else, continue the process.

Initially I thought the complexity will be O(|V| + |E|) as |V| stands for the number of vertices in the graph, and |E| stands for the number of edges in the graph, but I am afraid it might take O(|V| + |E|^2), and I wonder which option is correct and why (it may not be any of the above as well). Amortized or expected run times may also be different, and I wonder how can I check them as well. Please help me figure!

***pseudo code***

```
DFS(G=(V,E))
// π[u] – Parent of u in the DFS tree
1 for each vertex u ∈ V {
2 color[u] ← WHITE
3 π[u]← NULL
4 time ← 0}
5 for each vertex u ∈ V {
6 if color[u] = WHITE
7 DFS-VISIT(u)}

```

and for the DFS-Visit:

```
DFS-Visit(u)
// white vertex u has just been discovered
1 color[u] ← GRAY
2 time ← time+1
3 d[u] ← time
4 for each v ∈ Adj[u] { // going over all edges {u, v}
5 if color[v] = WHITE {
6 π[v] ← u
7 DFS-VISIT(v) }
8 else if color[v] = GRAY // there is a cycle in the graph
9 CheckIfOddCycle (u, v);
10 color[u] ← BLACK
// change the color of vertex u to black as we finished going over it
11 f[u] ← time ← time+1

```

and as for deciding what type of cycle is it:

```
CheckIfOddCycle(u, v)
1 int count  ← 1;
2 vertex p = u;
3 while (p! = v) {
4 p ← π[p]
5 count++ }
6 if count is an odd number {
7 S.O.P (“The graph is not bipartite!”);
8 stop the search, as the result is now concluded!

```

Thanks!

# Answer
> 1 votes
While your algorithm is visiting a node $v$, if it detects a back edge $(v,u)$ then it backtracks until it reaches $u$, using the parent information stored in pi, counts the number of edges, and then decides if it is bipartite or not. In this case your edges and nodes are visited at most two times (once when you move forward and once when you backtrack) which is still linear, i.e. is $O(V + E)$.

As for average and amortized case analysis I have never done such a thorough analysis of dfs but my guess is both are $O(V+E)$.

---
Tags: algorithms, complexity-theory, graphs
---


# Question
Title: Calculating greatest common divisor and least common multiple modulo prime number
I'm trying to solve pretty complex problem with number theory and set of numbers.

To make the problem more clear we are going to define $GCD(a, b)$ as the greates number that divides both $a$ and $b$ and $LCM(a, b)$ as least common multiple of $a$ and $b$. For my problem I want to calculate both $GCD(x\_1,\dots, x\_n)$ and $LCM(x\_1,\dots, x\_n)$ for set of numbers $x\_{i}\leq 300000$. But because we may have up to $10^5$ numbers I need to calculate this number modulo $p = 10^9 + 7$

My question is: If we are using Euclidean algorithm is it true that $$GCD(A, B) \text{ mod } p = GCD(A\text{ mod }p, B\text{ mod } p ) \text{ mod }p$$ $$\text{and}$$ $$LCM(A, B) \text{ mod } p = LCM(A\text{ mod }p, B\text{ mod } p ) \text{ mod }p$$

If we show that this is correct we can easily calculate those values in fast timing using the euclidean fast-gcd algorithm.

# Answer
> 3 votes
$GCD$ and $LCM$ do not depend on an algorithm, they are mathematical functions on pair of integers.

The first statement is false. A counterexample: $$GCD(10, 17)\bmod{7} = 1 \bmod 7 = 1$$ but $$GCD(10 \bmod{7}, 17\bmod{7}) \bmod{7} = GCD(3, 3) \bmod 7 = 3 \bmod 7 = 3$$

The second is also false $$ LCM(12, 18) \bmod 7 = 36 \bmod 7 = 1$$ but $$ LCM(12 \bmod 7, 18 \bmod 7) \bmod 7 = LCM(5, 4) \bmod 7 = 20 \bmod 7 = 6$$

---
Tags: number-theory, modular-arithmetic
---


# Question
Title: Generalization of Horn clauses in logic programming?
As far as I understand, Prolog and related languages are restricted to inference rules of the form $$ p\_1 \land \dots \land p\_n \rightarrow q$$ which is equivalent to the Horn clause $$ \neg p\_1 \lor \dots \lor \neg p\_n \lor q$$ I'm wondering if there are languages that relax this constraint to allow arbitrary disjuctions as clauses in the knowledgebase, and if so what the downsides of this would be. For example, the rule $$ p \rightarrow q\_1 \lor q\_2 \equiv \neg p \lor q\_1 \lor q\_2$$ is not a Horn clause and is not allowed in Prolog, but it seems to me that it would be possible to run a resolution algorithm for such clauses as well. For example, if $p = \top$, then we can prove $q\_1 \lor q\_2$ by contradiction: we assume the converse $\neg(q\_1 \lor q\_2) = \neg q\_1 \land \neg q\_2$ and resolve $$ (\neg p \lor q\_1 \lor q\_2) \land (\neg q\_1 \land \neg q\_2) = \neg p$$ which then yields a contradiction $p \land \neg p$.

Why should such arbitraty disjuctions not be permitted? Is it somehow related to the satisfiability problem (HORNSAT) ? Or is it due to the closed world assumption (where the statement $q\_1 \lor q\_2 = \top$ is paradoxical) ?

p.s. I am a hobbyist in logic programming, so simple informal explanations are appreciated :)

# Answer
> 6 votes
$\lambda$Prolog is a logic programming language based on a much richer logic than Prolog. In particular, the formulas that constitute its language are (higher-order) hereditary Harrop formulas. Horn clauses are a pallid fragment of that. The enabling concept for $\lambda$Prolog is the notion of a uniform proof, and additionally switching to an intuitionistic perspective on the logic. That last paper introduces the notion of an abstract logic programming language based on the notion of uniform proof and shows that classical first-order and higher-order Horn clauses form an abstract logic programming language.

Basically, a uniform proof is one where the rules used can be given an operational interpretation based on goal-directed search. This isn't the actual definition of a uniform proof, but the motivation behind the actual definition. An abstract logic programming language is one where uniform proofs suffice to prove any formula in the language with respect to a given notion notion of provability that is contained by the usual classical one.

Even the class of higher-order hereditary Harrop formulas doesn't allow $P \to Q\_1\lor Q\_2$ as a program clause. (It is allowable as a goal.) Why not? Obviously, $P, P\to Q\_1\lor Q\_2 \vdash Q\_1\lor Q\_2$, that is, if we know $P$ holds, and we know $P \to Q\_1 \lor Q\_2$ holds, then we can prove $Q\_1 \lor Q\_2$. However, this proof succeeds without ever specifying which of $Q\_1$ or $Q\_2$ holds. Indeed, neither $P, P\to Q\_1\lor Q\_2 \vdash Q\_1$ nor $P, P\to Q\_1\lor Q\_2 \vdash Q\_2$ is true. Formally, the proof of $Q\_1\lor Q\_2$ from $P$ and $P\to Q\_1\lor Q\_2$ is not a uniform proof. Informally, the operational interpretation we'd like to give to proving $Q\_1 \lor Q\_2$, is that we search for a proof of $Q\_1$ and a proof of $Q\_2$, and if either search succeeds we've established $Q\_1 \lor Q\_2$. Obviously this search approach will fail in the above example since neither $Q\_1$ nor $Q\_2$ can be individually established.

Finally, why do we need to "retreat" to intuitionistic logic in the hereditary Harrop formula case (we don't for Horn clauses)? This is because $P\lor(P\to Q)$ is a goal in the class of hereditary Harrop formulas, and it's classically true. However, if we again apply our operational interpretation, the search would proceed as follows: First try to prove $P$, this fails. Next, try to prove $P\to Q$ which reduces to proving $Q$ given $P$ which fails. $P\lor(P\to Q)$ isn't true intuitionistically since when $Q$ is false, this is just the law of the excluded middle. Of course, it requires a more involved proof (which is in the paper) to show that there isn't a similar failure with respect to intuitionistic logic for the class of higher-order hereditary Harrop formulas.

Since 1991, the notion of an abstract logic programming language has been extended. The most notable extension is the generalization of uniform proofs to focusing proofs, and the idea has been applied primarily in the context of linear logics. In many ways disjunction and negation are more tractable in linear logic. However, the idea has also been applied to Disjunctive Logic Programming. The idea was (first?) applied in Uniform Proofs and Disjunctive Logic Programming, but it didn't provide any guidance on how to handle quantifier elimination. That is, the idealized interpreter of an abstract logic programming language assumes you can "magically" guess the term to use in existential quantifier elimination. Normally this is accomplished with unification, but unification interacts with proof search. For example, higher order unification generates extra backtracking and the universal quantifiers in hereditary Harrop formulas lead to eigenvariables. Unification interacts with disjunction as well. The later paper A New Abstract Logic Programming Language and its Quantifier Elimination Method for Disjunctive Logic Programming gives a story not just for the abstract logic programming part of Disjunctive Logic Programming, but also how unification needs to be modified in this context.

To my knowledge, DLV seems to be the only serious implementation of any form of disjunctive logic programming.

---
Tags: logic, logic-programming, prolog
---


# Question
Title: max, min gradient and other terms in Neural Network
This link contains a demo that trains a Convolutional Neural Network on the MNIST digits dataset in browser.

I am not getting below terms- 1. max, min gradient in each layer. 2.max, min activation in layers

3.Forward time per example

4.Backprop time per example

5. Classification loss
6. L2 (a pooling mechanism??! but what this means?) Weight decay loss

***What are the meanings of above terms according to given context (webpage demo)?***

# Answer
I suggest you to read an introduction to neural networks. I like neuralnetworksanddeeplearning.com, but I can also recommend chapter 4.3 of my bachelors thesis.

> 1. max, min gradient in each layer

The gradient is like the derivative for high-dimensional functions. Imagine it as an arrow on a landscape. The arrow points into the direction of the steepest ascent, we want to go into the other direction (where the error becomes smallest).

> 2.max, min activation in layers

The activation is $\sum w\_i x\_i$ (details and my BS thesis). Hence it is what each neuron returns, before the activation function is applied. Now you have many neurons per layer and hence a set of activations $A$. Hence you can take the min / max of it. I don't know why you would take the min, but the maximum might give you an indicator which neurons are "responsible" for which feature.

For CNNs, a complete feature map is usually considered to be one neuron (see my MS thesis for some more details). In your case, it simply seems to be the maximum feature returned (hence the brightest pixel; see input layer)

> 3.Forward time per example

Measure how long it takes to process the input of a neural network. (There is also the backward pass for the gradient)
> 3 votes

---
Tags: terminology, machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: Proving that language $ L = \{ a^{2n}: n \geq 1\}$ is regular
I was asked to prove that language described by $$ L =\\{ a^{2n}: n\ge1\\}$$ is regular using pumping lemma. Pumping Lemma states that for regular language we can break down language described by language into $xyz$ where pumping length $p \ge 1$ such that

1. $|y|\>0$
2. $|x.y| \le p$
3. $x.y^{i}.z$ is in L for $i \ge 0$

taking pumping length $n = 3$ , my language becomes $L = \\{ aaaaaa\\}$ and then let $$x = aaa$$ $$y = aa$$ $$z= a$$

clearly this violates condition 2 because $|xy| \> p$ where $p=3$ and it also violates condition 3 for many values of $i$ thus this language cannot be regular but in the question I was asked to prove it to be regular, am I missing something?

# Answer
> 5 votes
The pumping lemma states that if a language $L$ is regular then there exists an integer $p$ such that every word $w \in L$ of length at least $p$ has a decomposition $w = xyz$ such that $|xy| \leq p$, $|y| \geq 1$, and $xy^iz \in L$ for all $i \geq 0$.

Your language satisfies the pumping lemma, with $p = 3$ (as it must, since the minimal DFA contains 3 states). Indeed, let $w \in L$ be a word of length at least 3, so that $w = a^{2n}$ for some $n \geq 2$. Then $w$ can be decomposed as follows: $w = xyz$, where $x = \epsilon$, $y = a^2$, $z = a^{2n-2}$. Note that $|xy| = 2 \leq p$, $|y| = 2 \geq 1$, and for all $i \geq 0$, $xy^iz = a^{2n-2+2i} = a^{2(n-1+i)} \in L$ since $n \geq 2$.

The pumping lemma states that every long enough word $w \in L$ has *some* decomposition $w = xyz$ satisfying the requirements in the lemma. It doesn't claim that *all* decompositions satisfy the requirements.

# Answer
> 3 votes
Your language is regular. It is a set of even length $a$s expressed by the regular expression $r=aa(aa)^\*$. The pumping lemma is used usually to prove that a language is not regular.

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


# Question
Title: How to use Bitmasking to solve this problem?
http://codeforces.com/problemset/problem/535/B

The problem is:

> You are given a lucky number n. Lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.
>
> If we sort all lucky numbers in increasing order, what's the 1-based index of n?
>
> Input: a lucky number n (1 ≤ n ≤ 109).
>
> Output: index of n among all lucky numbers.

Examples:

* input: 4, output: 1
* input: 7, output: 2
* input: 77, output: 6

> The Editorial solutions says,
>
> 1 : Consider n has x digits, f(i) = decimal representation of binary string i, m is a binary string of size x and its i - th digit is 0 if and only if the i - th digit of n is 4. Finally, answer equals to 21 + 22 + … + 2x - 1 + f(m) + 1.
>
> 2 : Count the number of lucky numbers less than or equal to n using bitmask (assign a binary string to each lucky number by replacing 4s with 0 and 7s with 1).

My question is ,how the Binary representations are used to calculate the position of the string?I am just not understanding this.

# Answer
I think you have a mistake in formula for answer. Answer is

$$ index = \sum\_{i=1}^{(x-1)} 2^i + f(m) + 1 = 2^1 + 2^2 + ... + 2^{x-1} + f(m) + 1 $$

And how it is:

Because lucky numbers are only two digit 4 and 7 so you can map each lucky number to a binary string by converting each 4 to 0 and each 7 to 1. For example: $74474 \to 10010$. By this way you can calculate index of each lucky number by computing decimal value of related binary string. But there is a problem in this way. All following lucky numbers have same index: $4, 44, 444, 4444, ...$ or $ 47, 447, 4447, ...$. To fix this problem you should compute number of all these situations lesser than lucky number which you want compute its index, and add this number to decimal value of binary representation of lucky number plus one.

Main problem is occurred when left most digit/digits is 4. You could find that for an lucky number with x digit, number of this situations is $\sum\_{i=1}^{(x-1)} 2^i$.
> 0 votes

---
Tags: algorithms, counting
---


# Question
Title: Does this A-Star heuristic already exist?
I've been thinking about the A\* algorithm recently. For context, A\* is a graph-navigating algorithm most often used to solve problems that go "What is the shortest path from point A to point B?". It's based on a distance-estimating heuristic you provide to it. The heuristic you provide must be able to tell the program, for any given position: 'This position is *at least* this far away from the destination'. The most simple heuristic being to use Pythagoras's theorem to get the distance "as the crow flies" between said point and a destination.

Now, the thing that interested me is that A\* efficiency is tied to the preciseness of your 'getMinDistance' function. If it returns a value too low, the algorithm takes longer. If it returns a value too high, A\* may return a non-optimal path. If it always returns 0, you have Dijkstra's algorithm. (also the heuristic must be monotonic, read the wikipedia articles for more details)

---

The heuristic I thought about goes like this:

* Using any method of your choosing, split the graph into regions. Designate a node of each region as the region's center (ideally, its centroid). The graph traversal distance between any node and its region's center should be trivially computable (or cached).
* Store the exact graph traversal distance between the centers of every single region. If you have N regions, you should end up with N² distances.
* For any two points A and B, and their respective region's centers Ra and Rb, the graph traversal distance AB is superior or equal to `RaRb - (RaA+RbB)`

The smaller the regions are, the closer this heuristic gets to the actual traversal distance AB.

---

My questions are:

* Is this algorithm actually admissible? I have no idea how to formally prove it.
* How efficient is this heuristic? My guess would be "Very if you have a lot of small groups, because A\* only examines nodes within the groups that include the optimal path", but again, I'm not sure it's true and I don't know how to prove it.
* Was this idea ever published before? If so, what is it called and where can I read about it?
* In the same vein, are there video games which are known to use this heuristic?

# Answer
> 3 votes
This idea is called ***True Distance Heuristics*** and as you suspected, it can be very efficient.

## True Distance Heuristics

True Distance Heuristics (as well as *"Pattern Database"*) is a technique that utilizes the memory to help with the search. The general idea is "let us pre-compute a few important **accurate** distances, to save a lot of time during the search". This is also sometimes referred to as "Memory Based Heuristics".

Each technique has different memory requirements and require a different heuristic function (that, of course, may utilize the original heuristic function). Also, some of course might be more beneficial in specific domains.

### Differential

This technique suggests to choose `k` "pivot" states and store the shortest path from every state to each pivot

### Canonical

This consists of 2 different data-sets:

Primary data: choose `k` pivot states and calculate all pairs shortest path among all of these k states. Secondary data: From every node (out of all possible nodes), store distance to the closest canonical node.

### Others

There are many other memory based techniques that uses this concept. Many prove themselves to be very beneficial, for a relatively small price to pay (in terms of space).

## Food For Thought

As you suspected, these techniques can have admissible heuristics. Since it seems that you are interested in this field, I'll let you figure out the right heuristic functions on your on. I'll give you a hint that the formal proof uses simple math. Feel free to ask for these functions in the comments, and I'll answer.

I strongly suggest to draw these out in a simple drawing, it will make everything very clear.

---
Tags: algorithms, heuristics, searching
---


# Question
Title: How does size of a number in an array affect time complexity algorithm analysis?
This question stems from this question and this answer. I also want to preface this question by stating that this question is done from the perspective of a RAM (or PRAM if it's more accurate term) model.

From the comments in the answer, it seems like when doing algorithm analysis for the solution:

> * $O(n)$ solution (guaranteed): sum up the elements of the first array. Then, sum up the elements of the second array. Finally, perform the substraction.

for the problem of:

> finding the number that is different between two arrays (I'm assuming a fixed size structure, if it matters) of unsorted numbers **(paraphrased by me)**

that it isn't as black and white as just coming to the conclusion as $2n$ (1 pass for each array), because you have to take into account the size of the number too. That is the part I am confused about. I've asked one of the commenters to elaborate a bit more for me:

> My idea is that while the time to add two numbers is proportional to their length, but there are $O(\log n)$ extra bits that the partial sums have over the longest input. Now, there are two things that complicate things. First, the inputs need not have the same length, but we'd like complexity in terms of their total length. If your addition is proportional to the longer number, you might rack up $O(n^2)$ quite easily. The solution is to add in place, which means the addition is proportional to the addend length - if not for carry. Now you just need to find how many carries you can have.

Despite this pretty detailed comment, I'm still having difficulty understanding **why** it's different. (I suspect the reason is due to my ignorance of the lower level ongoings of a computer and numerical representations). Not wanting to test their patience, I googled it and asked here, but unable to properly articulate the question, the most I found was this answer, which seems to echo the quote above (I think), thus didn't help me further.

Is it possible to simplify the explanation by perhaps illustrating it or elaborating further? Or is this as simple as it can get (and I just need to get the prerequisite knowledge)?

# Answer
Runtime analysis as it is done in practice is not terribly rigorous. This is why you can have different answers that are equally correct, they just differ in their assumptions.

To do a formally correct runtime analysis you first have to define a machine model. Almost nobody does this explicitly, usually some variant of the RAM is used. Then you write your algorithm using only operations your machine supports. This is not typically done either, usually some form of pseudo-code is used and the mapping to the machine instructions is assumed to be obvious. Only after doing these steps you can start counting how many instructions you use to solve an instance.

In the question you linked, the proposed algorithm summed a list of $n$ numbers. In a casual runtime analysis one typically assumes that adding two numbers takes constant time. This is true for the RAM, but it's not true in the more realistic Word-RAM model. In the Word-RAM (and in real computers), you can only operate on $k$ bits at once. If the numbers you want to add are too big to fit in $k$ bits you need more than one operation. This is the same if you add numbers by hand: For small numbers (say with only 1 digit) you know the result by heart, for large numbers you have to manually add each digit and take care of the carry and so on.

So if you run with the assumption that additions take constant time, summing a list of numbers takes linear time. If you want to be more precise, the length of the list alone is not sufficient to determine the runtime. You need to know how many bits your numbers have and a more reasonable $n$ for your runtime bound is the number of bits you need to encode your list. You should also think about the exact algorithm you use for adding two numbers and the order in which you add the numbers of your list, as this can have an influence on the runtime.

If you want to see examples of very rigorous runtime analysis, I recommend Knuth's TAOCP. He defines his own machine and writes his algorithms using only simple machine instructions.
> 3 votes

# Answer
Actually, you can avoid any higher precision calculations.

Assume you are adding n k-bit numbers in one array, and adding n+1 k-bit numbers in the other array. The difference is a k-bit number (the one extra number that was added to the other array).

So you can perform the addition, and just ignore anything beyond k bits. Instead of getting the sum, you get the sum modulo $2^k$, but that is enough to get the correct result.
> 3 votes

# Answer
I am new to this site so don't really have a feel for what is scope

First you need to assume the array elements are unique and not sorted

Let's assume positive integers

Size of the array and size of the elements is not the same. Size of the elements must be \>= the size of the array.

The maximum sum would be max element size * number of elements / 2.

A trick to keep the sum down would be to iterate both at once
Also using the 2k from gnasher (+1)

```
int k = number of bits;
int modK = power(2,k);
int count = smallerArray.Count;
for(int i = 0; i < count ; i++)
{
    sum += (laregerArray[i] - smallerArray[i]);
    if(abs(sum) >= modK)
       sum = sum%modK;
}
sum += laregerArray[count];

```
> 0 votes

# Answer
Remember "Rolling hash", the value of hash after applying hash function on key could be a very long integer but it is explicitly multiplied by mod P (as X mod P), where X is the final hash value and P is a prime number, say 31. With multiplication by (mod P), the final value is restrained to 1 word size only. The final value is a small integer.

that is, 38269540 mod 31 is 9 only where 9 is a small hash value as compared to 38269540.
> 0 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, search-algorithms, computation-models
---


title: Are grandparent classes also parents?

text:
# Question
Title: Are grandparent classes also parents?
Let's say I have three classes, `Animal`, `Bird` and `Pigeon`. If `Bird` extends `Animal` and `Pigeon` extends `Bird`, is `Animal` the parent class for both or is `Bird`?

So, for instance, if the constructor for `Animal` said "hi I am animal" and the constructor for `Bird` said "hi am I bird", which will it say in class `Pigeon` if I call the `super` constructor?

# Answer
You cannot answer this question unambiguously. Different OOP languages implement OOP paradigm differently.

In **Ruby** **you will get only** "Hi, I am bird!"

```
class Animal
  def initialize
    puts "Hi, I am animal!"
  end
end

class Bird < Animal
  def initialize
    puts "Hi, I am bird!"
  end
end

class Pigeon < Bird
  def initialize
    super # <= call to the superclass
  end
end

pg = Pigeon.new

```

In **PHP** **we get only** "Hi, I am bird!"

```
<?php

   class Animal {

      public function __construct()
      {
        echo "I'm Animal";
      }

    }

    class Bird extends Animal {

       public function __construct()
       {
         echo "I'm Bird";
       }

    }

   class Pigeon extends Bird {

      public function __construct()
      {
         parent::__construct();
      }

    }

   $Pigeon = new Pigeon();

  ?>

```

While in **C++** you will get both "Hi I am animal!" and "Hi I am Bird!"

```
#include <iostream>
using namespace std;

class Animal
{
   public:
   Animal()
   {
     cout << "Hi I am animal!" << endl;
   }
};

class Bird : public Animal
{
  public:
  Bird()
  {
    cout << "Hi I am Bird!" << endl;
  }
};

class Pigeon : public Bird
{
  public:
  Pigeon():Bird(){} // <= call to the base constructor
};

int main()
{
  Pigeon pg;
}

```

In **Swift (Apple) we get both**, too

```
class Animal {
  public init() {
    print("I'm Animal")
  }
}

class Bird: Animal {
   public override init() {
     print("I'm Bird")
   }
}

class Pigeon: Bird {
   public override init() {
    super.init()
   }
}

var pigeon = Pigeon()

```

To understand why, you should get into details of how C++ implements OOP (**vtables** and etc.) and **how Ruby classes lookup its methods** and constants in the hierarchy, and other languages.

In addition if you want to see Object Oriented "Nightmare" then have a look at Lua, though I like it.

As to your question in the title: "Are grandparent classes also parents", of course subclasses are related to all super-classes up in the hierarchy chain, but that relationship are implemented differently in different programming languages.
> 2 votes

# Answer
You have a type *hierarchy* here. `Animal` is parent for `Bird` and `Bird` is for `Pigeon`. Since the inheritance relation is transitive, `Animal` is a "parent" for `Pigeon` as well.

In real-world language, of course, lots of watering down and extension of core principles happen. For instance, which behaviour overrides which can be different due to different method dispatching rules.

Specifically for constructors, *conceptually* `Pigeon()` should call `Bird()`, and `Bird()` should call `Animal()`; otherwise we don't know that the object is set up correctly. Hence, `Pidgeon()` will "say" both! (Which it says first depends on where in the constructors the `super()` calls happen in relation to the "saying".)

Note that some programming languages may allow you to leave out calls to the super constructor at your own risk (specifically breaking Liskov's substitution principle if you're not careful).
> 0 votes

---
Tags: terminology, programming-languages, object-oriented
---


title: How 2-QCNF algorithm works?

text:
# Question
Title: How 2-QCNF algorithm works?
Suppose we have following 2-QCNF problem:

$$\forall x\_1...\forall x\_m\exists y\_1...\exists y\_k:\varphi(x\_1,...,y\_k)$$

where $\varphi$ is 2-CNF.

When the formula is false?

Rules that I found:

1. $\exists y\_i:(y\_i\rightarrow \overline{y\_i})\land(\overline{y\_i}\rightarrow y\_i).$ Existentially quantified variable and it's negation are strongly connected.
2. $\exists\\{x\_i,x\_j\\}:(x\_i\rightarrow x\_j)\lor(\overline{x\_i}\rightarrow x\_j)\lor(x\_i\rightarrow \overline{x\_j})\lor(\overline{x\_i}\rightarrow \overline{x\_j}).$ Two (or one and it's negation) totally quantified variables are connected.
3. $\exists\\{x\_i,y\_j\\}:((y\_j\rightarrow x\_i)\land(\overline{y\_j}\rightarrow x\_i))\lor((y\_j\rightarrow \overline{x\_i})\land(\overline{y\_j}\rightarrow \overline{x\_i})).$ Totally quantified variable is reachable from existentially quantified variable and it's negation.

Is there any other rule to solve 2-QCNF or, maybe, there is better way to solve it?

# Answer
Aspvall, Plass and Tarjan describe a linear time algorithm determining the truth value of quantified 2CNFs in their paper A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Their algorithm is an extension of the well-known algorithm for solving 2SAT using directed reachability; their initial step is computing the strongly connected components of the implication graph.
> 2 votes

---
Tags: graphs, satisfiability, 2-sat
---