title: P vs NP characterization confusion

text:
# Question
Title: P vs NP characterization confusion
I know that $P \subseteq NP$, but for a problem in $P$, e.g. MST in a graph, is it a correct statement to say that:

The MST problem belongs in NP-Class.

(I mean, i think it is correct, but could someone classify that as wrong because he would expect P instead of NP?)

# Answer
> 1 votes
The statement is correct for exactly the reason you started with: $\mathsf P$ is a subset of $\mathsf{NP}$ which means that every problem in $\mathsf P$ is also in $\mathsf{NP}$. You can also go through the definitions and find that a deterministic TM running in polynomial time is merely a special kind of nondeterministic TM running in polynomial time and take it from there.

However, while being true, the statement "MST is in $\mathsf{NP}$" holds less value than the statement "MST is in $\mathsf P$" as complexity theory is, at large, concerned with lower bounds. A decent analogy in my opinion would be that the statement $\pi \geq 3$ is stronger than the statement $\pi \geq 0$ eventhough both are true.

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


# Question
Title: Represent a DNF formula as a multivariate linear formula?
Lets say I have the following DNF: (x or y) and (z or i) / $(x\lor y)\land(z\lor i)$
How do I convert that into a polynomial form?

# Answer
Usually one represents disjunction by addition and conjunction by multiplication, so a suitable polynomial would be $(x + y) \cdot (z + w)$ (I renamed $i$ to $w$ here as to not create confusion w.r.t. the imaginary unit). Note that plugging in $0$ or $1$ depending on the desired truth values yields 0 precisely if the original formula would evaluate to false while any value greater than zero indicates that such an assignment would satisfy the formula.

You mention *linear* in your title, however I do not think that there is a sensible way to represent propositional formulas by linear functions.
> 1 votes

---
Tags: logic, discrete-mathematics, polynomials
---


# Question
Title: What are cases where we cannot perform LR parsing without augmented grammar?
Many standard Compiler Design texts mention constructing augmented grammar as first step of LR parsing.

The reason frequently is

1. It is required in cases where start symbol comes on right hand of any production
2. It is required when start symbol's RHS have multiple production.

I figured that if in the parse table's action part of very first state of DFA, we provide "success" under entry of '$' we would not require augmented grammar. Is that correct or i am missing something?

Edit: Here is how i think we can declare a parse as success:

Consider S -\> .a After we reduce 'a' instead of going to goto(S) from our current state a tTop of stack, we can simply lookahead '$' and output success

# Answer
> 2 votes
Once we have a parsing table, we can parse (or reject) any sentence without any reference to the grammar. So at that point, the fact that the grammar was or was not augmented is essentially moot. (It would be meaningful if there were a user semantic action attached to the augmented start symbol's sole production, but that seems impossible, since the augmented start symbol's production was added automatically, not by the user.)

And it is indeed the case that most parser generators do in fact optimise their parse table by making the *shift* of the end-of-input marker the accept action, rather than waiting for the augmented start symbol's production to be reduced. With that optimisation, the augmented start symbol is never used in a parser action, so the symbol itself need not exist. If the parser generator augmented the grammar, that augmentation has essentially been undone, except for one little mystery: what is this end-of-input symbol which can be shifted? It doesn't appear in any reducible right-hand side.

Anyway, the point is that it's not parsing which requires an augmented grammar; the augmented grammar is necessary to create the parsing table. The cases where it is necessary are essentially the cases in which there is some non-default reduction action associated with an end-of-input symbol lookahead. That reduction action could only have been correctly added to the parsing table through the analysis of a state which includes the augmented start symbol's production.

(Strictly speaking, as alluded to earlier, the end-of-input symbol can't really exist in the parsing table unless it is present in some right-hand-side in the grammar, and it isn't present until the grammar is augmented; the augmentation not only adds an additional non-terminal, it also adds the end-of-input symbol itself.)

---
Tags: compilers, parsers, lr-k
---


# Question
Title: Is there any compiler IR paradigms other than Three Address Code and Static Single Assignment (SSA) Form?
Specifically, I have tried boiling down the operations of a VM into the smallest possible standardized units and arrived at this:

```
allocate_stack(size)
fetch(offset_from_stack_pointer)
store(offset_from_stack_pointer)
call(index)

```

So you might have:

```
allocate_stack 6
fetch -2
store 0
fetch -1
store 1
call 72

```

Basically, the `allocate_stack` would tell you how much space you are allocating for fields in the stack. Then the `fetch` would queue up something relative to the stack to be stored (or `fetch_a` would fetch an absolute address). Then `store` would store the fetched value in the space relative to the stack (or `store_a` for absolute position). And finally, `call <index>` would call that specific function.

So basically these are 2-address codes instead of 3-address codes. Does anything like this exist out there where they've expanded upon the idea to find compiler optimizations and such, like 3-address-code and SSA form? If not like this, does anything else exist outside of 3-address-code and SSA form?

# Answer
> 1 votes
This is an extremely common approach to designing abstract machines for non-imperative languages. See, for example, the G machine or the WAM (which uses the same technique for heap allocation).

---
Tags: compilers
---


# Question
Title: When inserting an element in a priority queue and the heap size is already at max capacity, should you output an error OR increase the array size?
I'm currently learning about how to implement priority queues using heaps, but I've hit a wall while trying to implement the insertion operation. Assume that the size of the array storing the elements of the heap is ***n***, and the size of the heap is also ***n***. Assume further that we try to insert an element 'x' inside the heap. We would have to increment the heap size by 1, but this would now make the heap size greater than the size of the array, which is unacceptable.

So my question is: how do we deal with this problem. Should we **A**: simply throw an error (since heap size == array size), or **B**: increase the size of the array by 1. A huge majority of the programs I've seen online implement A, but I think B would be better. Are there any advantages/disadvantages of using A over B (or vice versa)? Are there any other strategies to solving this problem?

Any help is greatly appreciated.

# Answer
> 0 votes
I decided to go with option B, as it seems like the more practical thing to do.

# Answer
> 0 votes
In array-based heap implementations I'm familiar with, it is typical to use array resizing where the new size is a constant multiple of the previous size (a.k.a. ArrayList) to avoid quadratic performance on repeated insertions. You can see this in the implementation of the Java standard library's PriorityQueue class, for example.

---
Tags: heaps, priority-queues
---


# Question
Title: Are objects appropriate for modeling the real world?
First of all, I know objects are not meant to model the real world, although they have been marketed as such and perhaps that was an intention at some point.

Here I say 'modeling the real world' in a general sense. That includes simulations, modeling of abstract (non-real) concepts and modeling of business support applications, although I'm not sure it is appropriate to develop all of them in a single general-purpose OO language.

Under the assumption that modeling the real world in software development is a desirable and advantageous trait (not considering inappropriate models), I'm inspecting the foundations of object-oriented programming and the Simula languages.

However I'm asking this question in the hope that someone can provide a quick spoiler.

I am under the impression that objects (i.e. endurants) may not be enough to model the real world since a) their classes are static across time, e.g. a Person is always a Person, not a Child who becomes an Adult and thus his/her responsibilities and actions change b) processes (i.e. perdurants) are not first-class citizens as objects are, and c) time also is not a first-class citizen.

Aren't requirements such as these necessary for a language to properly model the real world? Why haven't they been included in the concept?

# Answer
> 3 votes
Object-oriented programming languages are designed to support *programming*. Whether they "properly" model the real world is beside the point and not the primary goal. So, when you ask "why haven't \[these requirements\] been included?", it's likely because those weren't considered relevant or necessary to the goal of supporting programming.

It's like saying "A hammer is no good for driving in a screw; why haven't the requirements of driving screws been included in the design of a hammer?" Well, that's not what hammers are designed for.

Of course you could invent your own language that follows different principles. You'd presumably end up with something that looks different. I'm not sure you'd ever finish such a project; I suspect there would always be some aspect of the real world that isn't incorporated in the language, and at some point you'd have to accept imperfect fidelity to the real world. In any case, that would be a different project, with different design goals, so it's no surprise that it might lead to a different result.

# Answer
> 2 votes
It sounds like you have already answered all of your own questions:

> objects are not meant to model the real world, although they have been marketed as such and perhaps that was an intention at some point.

OOP languages—at least the commonly-used modern ones—are not designed to be databases, and their features are not designed for describing ontologies. The value of OOP is in providing a meta-abstraction (the class) which has a nice balance of record-like and module-like features. These are features that are useful for *programming*, not for describing reality.

If you need a one-to-one mapping of records to ontological objects, start with an RDBMS and branch out if that doesn't work for your use case. (Although, a record in an relational database theoretically represents an element of a relation between values, not a value itself—but at least you are getting closer.)

---
Tags: simulation, modelling, object-oriented, programming-paradigms, philosophy
---


# Question
Title: How to properly name the two types of RAM in a Paper?
How do I name VRAM and RAM properly in a paper?

"Video RAM" is clear but the "normal" RAM? Is it called "CPU RAM" or "Processor RAM" or "Main RAM" or totally different?

# Answer
> 2 votes
I have usually heard "main memory" for the CPU-accessible RAM.

Wikipedia calls it "primary storage", with "main memory" listed as a synonym. Although honestly, I would have guessed that "primary storage" referred to the primary nonvolatile medium (SSD or HDD).

---
Tags: terminology
---


title: Variable size and CPU performance

text:
# Question
Title: Variable size and CPU performance
When you learn programming they tell you choose data types that suffice for the concepts you're expressing, i.e. not too small because then your data won't fit and not too big because you don't want nonsensical values stored.

**Table of unsigned integers**

* 8-bit: 0 to 255
* 16-bit: 0 to 65,535
* 32-bit: 0 to 4,294,967,295
* 64-bit: 0 to 18,446,744,073,709,551,615

According to the table above, an 8-bit unsigned integers can store e.g. the number of weeks in a year (approximately 52) and a 64-bit unsigned integer can store e.g. astronomical values.

To get to the point of my question; how do the different variable sizes affect the performance of a program? I imagine that a 64-bit CPU internally handles all variables as 64-bit and simply ignores the highest bits, so an 8-bit variable, travelling across the system, would be handled as:

```
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx yyyyyyyy

```

Where *y* is either 0/1 and *x* is ignored.

Would it make any difference performance-wise to only use the largest variable size on the platform and use *business logic* to enforce reasonableness in the values being processed and stored? Is there a performance hit when using variable sizes lower than the *native* variable size of the architecture?

# Answer
> 5 votes
> Would it make any difference performance-wise to only use the largest variable size on the platform and use business logic to enforce reasonableness in the values being processed and stored?

Yes, it could make your performance worse.

Memory, memory bandwidth, cache density are primary concerns. Larger data size can:

* result in increased cache and translation lookaside buffer (TLB) misses;
* require more RAM to avoid paging.

E.g. x86 CPUs always load (if not already in cache) a whole cache line from memory.

So, assuming a cache line of 64 bytes, there are 64 8-bit-integers per cache line, yet only eight 64-bit-integers. Thus resulting in eight times as many memory transfers for processing a large array.

Also consider that many compiler are smart enough to figure out how to perform automatic vectorization1.

Taking advantage of the processor's SIMD capabilities you can pack eight 16-bit integers into the same space as two 64-bit integers and do four times as many operations at once.

> Is there a performance hit when using variable sizes lower than the native variable size of the architecture?

There isn't a general rule.

x86 CPUs can operate on fractions of a register and there will be no slow down at all2.

Other CPUs (e.g. PowerPC) cannot process a fraction of a register. So performing multiple operations on small integers may require masking / cutting back partial results. Anyway it's just a simple `AND` operation and often the compiler can find a way to avoid it entirely.

As a corner case some instructions can be slower when performed with the CPU's "native size" (e.g. multiplication / division of 64-bit quantities vs 32-bit quantities on Intel Pentium IV).

---

Interesting readings are:

---

*1) automatic vectorization is a major research topic in computer science*

*2) x86 processors can suffer a partial register stall if you, say, write to `BX` and then try to read from `EBX` (something to consider mixing integer of different sizes).*

# Answer
> 2 votes
I would say it depends on the application and target architecture.

Usually the x86 is the main target, but practices used there might not transfer well into a embedded domain.

Other architectures (usually RISC) have large amount of registers, AVR has 32 registers 8-bits each and it's possible use finer granularity as some instructions have bit wise manipulation.

For example RISC-V has 32 register 32-bit each (or 64-bit or 128-bit depending on the implementation), there the registers are dedicated to pushing arguments between functions without using stack/memory and using a lot of variables might end up being allocated to registers anyway, forcing it to non-native (smaller) size can cause unecesary modulus and other operation to mimic features which now are not given for free by hardware (as there might not be dedicated instruction using smaller type) because the code insists using using smaller type and expects behavior of a smaller type and can't use the native type. So in some cases you will not save on memory size, nor on memory accesses, you will just force CPU to do awkward things because you think it will make it run faster.

When RISC-V has floating point unit implemented then it gets yet another set of registers to work with, so for example rv32-imaf will have 64 registers. So it can really do a lot without touching a stack/memory.

---
Tags: data-structures, memory-hardware, cpu, performance
---


# Question
Title: Regularity of a language constructed from a know regular language
I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language: $$ \\{x|\exists n \ge 0 \\; \exists y \in A \\; y = x^n\\} $$

I've attempted to show that this is regular by a contradiction using Myhill-Nerode, by assuming it has infinite index, and showing this means that $A$ must have infinite index. However, I cannot seem to get this proof to work, because taking representatives of each class lets me show an infinite number of pairs of elements in $A$ that are not in the same class, but these elements do not uniquely correspond to my representatives, so I cannot show that an element is not in the same class as infinitely many others.

However, the book seems to indicate that the solution should be construction. I can also easily see the construction for a NFA if $n$ was fixed, but this doesn't seem to offer any help, as this makes the states depend on $n$ (by using tuples of states, and simultaneously moving states once).

If anyone could suggest how to go about constructing the required automata, that would be very helpful.

# Answer
> 0 votes
As you mention, if $n$ was fixed, then this is not too difficult to prove. So, the idea would be to show that in fact, $n$ can be bounded a-priori, depending only on $A$, and not on $x$.

To this end, consider some word $x\in \Sigma^\*$, and suppose $x^m\in A$ for some $m$. Let $k$ be the number of states in some DFA $D$ for $A$ (e.g., minimal DFA). Suppose $m\>k$, then there exist $0\le i\<j\le m$ such that the run of $D$ on $x^i$ reaches the same state as on $x^j$. But this implies that $x^{m-{j-i}}$ is also accepted by $D$.

Thus, it's enough to consider $n\le k$. So you can rewrite your language as $$\\{x| \exists n\le k,\ x^n\in A\\}$$ And this is regular.

---
Tags: regular-languages, finite-automata, computation-models, closure-properties
---


# Question
Title: Operating System: Busy waiting is not eliminated with semaphore?
Why the busy waiting is not eliminated even after we put the current process into the process list and "block()"ed it? So even if the process is in waiting state we still call it "busy waiting"?

I'm reading *Operating System Concepts, Silberschatz, 9th ed., pages 215~217.*

# Answer
> 3 votes
> So even if the process is in waiting state we still call it "busy waiting"?

In the book, they are calling the mechanism as Busy Wait not because of the processes waiting in queue but rather for the fact that when multiple processes are trying to execute Wait() or signal() operation concurrently, they will have to busy wait.
Note that the variable "value" in the code of Wait() and signal() is a shared variable and hence critical section. Two processes should not be allowed to modify this variable concurrently. For synchronisation, we prefer the busy wait(spin lock) over non busy wait synchronisation mechanism because the code of Wait() or Signal() is pretty small and so processes which are waiting to execute "Wait()" will not have to spend much time waiting. Moreover, if you choose non busy waiting synchronisation mechanism in situation when the length of critical section is small(as it is here) then context switch overhead will waste more CPU time compared to the CPU time wasted in busy wait. So what we have done is that we limited the busy waiting only to the critical section of Wait() and signal() operation. Earlier busy waiting was present in critical section of our application program.

---
Tags: operating-systems
---


# Question
Title: Search for range in continuous function satisfying some condition
I am attempting to define an optimization for the following problem: given a graph find the largest interval(s) where `S > S_th` (the narrower the interval the smaller `S` will be) and `P < P_th` (the wider the interval the higher `P` will be).

* I am not 100% certain the claims in parenthesis are always correct as, I think, it is affected by the distance between the `R`ed and `G`reen graphs.

The graphs `R` and `G` is KDEs generated with Gaussian functions, therefore continuous.

I already know that the conditions can be true *only* where the `R`ed graph is above the `G`reen one. I, therefore, find the intersections between the graphs (e.g. with brentq) and find relevant intervals by calculation a single point in them.

Below are a few examples of graphs I want to analyze. The blue vertical lines mark graph intersections; blue horizontal lines with the condition results on top are shown only when the conditions were met for the whole interval.

The vertical and horizontal lines in black are generated from an ML algorithm which I want to replace with a numerical calculation. As it can be seen it, usually, finds intervals that are smaller than the whole area where red is on top.

Example 1: ML algo found the better solution on the right section, neither found the left one interesting.

Example 2: On the right, you can see the ML algo suggesting a range not quite between the blue lines. I am OK with the new algo clipping the portion on the left.  Example 3: showing that there may be more than one interesting range per marked section.  Example 4: ML algo missed the leftmost range

# Answer
Let $x\_1,x\_2,\dots,x\_n$ denote the $x$-values where the two curves intersect; you say you know how to find these. Let's add $x\_0=-\infty$ and $x\_{n+1}=+\infty$. Then in each interval $\[x\_i,x\_{i+1}\]$, either the red curve is consistently above the green curve or vice versa, so label that interval with the color of the curve that is on top. This is easy to do by picking an arbitrary $x$-value in $(x\_i,x\_{i+1})$ evaluating the height of both points at that point.

Now your problem reduces to the following: find $x\_i,x\_j$ that maximize $x\_j-x\_i$, such that all of the intervals $\[x\_i,x\_{i+1}\],\[x\_{i+1},x\_{i+2}\],\dots,\[x\_{j-1},x\_j\]$ are labelled red.

This problem can be solved in a straightforward way, in linear time. Iterate through $j:=1,2,\dots,$, scanning from left-to-right, keeping track of the smallest $i$ such that all intervals between $x\_i..x\_j$ are labelled red. Thus, when you encounter a red interval $\[x\_{j-1},x\_j\]$, you do nothing; when you encounter a green interval $\[x\_{j-1},x\_j\]$, you reset $i := j$. Keep track of the longest range you've found so far as you do the linear scan.
> -1 votes

---
Tags: algorithms, optimization
---


# Question
Title: How to improve the CPI and Speed up factor in CPU-OS simulator?
I am using the CPU-OS simulator by Besim Mustafa(https://www.merlot.org/merlot/viewMaterial.htm?id=476196) and I am studying Pipeline Stages. I have written a simple program and captured the metrics like CPU Clocks, CPI, Instruction Count, Speed Factor.

My question is what changes should I make to improve the CPI and Speed Factor.

# Answer
To be able to improve CPI and the speed-up factor you need to enable the pipeline. The programmer can help improve CPI but it is best to leave that to an optimising compiler and clever CPU architecture. The simulator's built-in compiler offers some help in reducing the CPI, for example loop unrolling, constant folding, identifying code dependencies, etc. In pipelined architecture, the goal is to reduce/prevent hazards and the above optimisations help do that. In addition, the pipeline has a means of forwarding operands, i.e. prior to previous instructions updating registers in a later stage, that contributes to reducing the CPI. There is also the technique of jump predictions. All these are available in the simulator which you should explore.
> 1 votes

# Answer
If the simulator is good, the same way as with code running on an ordinary CPU. Read the manual for the CPU, read what increases CPI for example and try to avoid it.
> 0 votes

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


title: big theta prove

text:
# Question
Title: big theta prove
> Prove that $3n^3 - 6n^2 + 9n - 9\log n \in \Theta(n^3)$ using

So, how can I prove this by big theta definition? I don't what I should do with the log function

# Answer
Here’s a simpler approach than those suggested in the comments.

Let $f(n) = 3n^3-6n^2+9n-9\log{n}$. We wish to show $f(n) \in \Theta(n^3)$. It suffices to show $f(n) \in O(n^3)$ and $f(n) \in \Omega(n^3)$.

**Big O**:

We wish to show $\exists c, n\_0 \> 0$ such that:

$f(n) \leq cn^3$ $\forall n \>n\_0$.

Let $n\_0 = 1.$

We have:

$f(n) = 3n^3-6n^2+9n-9\log{n} \leq 3n^3 + 9n^3 = 12n^3$. So take $c = 12$.

**Big Omega**:

We wish to show $\exists c, n\_0 \> 0$ such that:

$f(n) \geq cn^3$ $\forall n \> n\_0$.

Let $n\_0 = 6$.

We have:

$f(n) = 3n^3-6n^2+9n-9\log{n}$

$= 2n^3 + n^2(n - 6) + 9(n - \log{n})$

$\geq 2n^3$. So take $c = 2$.

Hence, it follows $f(n) \in \Theta(n^3)$. $\Box$
> 0 votes

---
Tags: algorithms, big-o-notation
---


title: Why Study Complexity Theory?

text:
# Question
Title: Why Study Complexity Theory?
I’m an amateur in the study of algorithms. For a while I’ve had a burning question, **why** do we study complexity theory in computer science? The reason I ask is because algorithms with better asymptotic complexity are not always faster for practical purposes, in fact they can be absurdly slower. Why not instead develop a theory that better suits the practical needs of scientific research and industry?

As an example, it is known that developing an algorithm to determine a perfect chess game can be done in $O(1)$, as the number of legal chess games on an 8×8 grid is bounded from above. However, I have heard this algorithm would take longer than the age of the universe to terminate. This begs the question, why complexity theory? It seems to me the field is fundamentally flawed, and computer scientists should be using a better approach for the study of algorithms.

(Note: My sincere apologies to researchers in the field. ☻)

# Answer
> 4 votes
This is not a simple question, and you shouldn't expect a simple answer. There are a range of similar questions in this space: why do we study asymptotic running time? why do we use asymptotic running time analysis to analyze algorithms? why do we study complexity theory? Each of those has multiple answers; there is not just a single reason why we do it, and different people may have different reasons.

Asymptotic running time analysis has advantages and disadvantages. You've accurately identified one of the disadvantages: a good asymptotic running time doesn't guarantee good running time in practice. But if you focus on only a single advantage or disadvantage you're not going to get the full picture of the strengths and weaknesses of that style of analysis. Some of the advantages are that analysis is relatively tractable, it is not specific to a particular architecture, it provides useful information about scalability, and at least some of the time it has useful predictive power at identifying algorithmic bottlenecks. For instance, the difference between a $O(n^2)$ time algorithm and a $O(n \log n)$ time algorithm can often be significant, even if we are ignoring the constant factors. Some of the disadvantages are that constant factors can be important, cache and memory hierarchy effects can be very important yet are ignored by asymptotic running time analysis, and (like any metric) optimizing solely for asymptotic running time can lead to absurd results of little practical utility (see galactic algorithms and Goodhart's law).

I think it's also useful to examine the alternative. I encourage you to explore the alternative to asymptotic running time analysis and work through what you'd propose in its stead. If you don't try to come up with a concrete proposal, it's easy to assume that it can't be that hard to find something better... but when you're forced to commit to something specific, you might discover that it's more challenging than you anticipated. For instance, I encourage you to familiarize yourself with Knuth's analysis of algorithm running time on MIX in his TAOCP series. There he does concrete running time analysis, with no asymptotics, taking into account the constant factors. If you force yourself to work through the details of that, you'll quickly discover the disadvantages of that: it's super-tedious, very specific to a particular computer architecture, and often not much more enlightening.

We could similarly discuss each of the other topics - e.g., why or why not to study complexity theory - and you'd find that they too have nuances.

I also want to highlight for you that the theory and algorithms community is a broad one, with a range of different styles of work. You seem to be lumping it all together into one pile, but there's a spectrum of work: some of it is super-theoretical and far afield from practice, some of it is highly practical and motivated by concrete problems and may have immediate impact, and there is a range of work at various point in between those extremes. I think it's important to understand that there is some work in the theory community that is of great practical relevance or has had major impact, just as there is work that much more theoretical and not motivated by near-term impact.

Since you asked for theoretical frameworks that are focused on meeting industry's needs, you might also be interested in the Word RAM model, cache-oblivious algorithms, and the parallel external memory model.

I strongly encourage you to read the following resources, as they are closely related to your question: Why polynomial time is called "efficient"?, Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms, Justification for neglecting constant factors in Big O.

---
Tags: complexity-theory, asymptotics
---


# Question
Title: Finding a boolean submatrix isomorphic to a specific fixed set of other boolean matrices
Given a matrix $M$ of certain size $h\times w$, where $h\leq w$, for example $5\times 6$, are also given the following set $B$ of additional all-ones matrices, that I like to call target (b)oxes.

$$ \begin{matrix} Boxes: & \begin{bmatrix} % 2 x 5 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 3 x 4 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 4 x 3 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 5 x 2 1 & 1\\ 1 & 1\\ 1 & 1\\ 1 & 1\\ 1 & 1 \end{bmatrix}\\ Sizes: & 2 \times w - 1 & 3 \times w - 2 & 4\times w - 3 & 5\times w - 4 \end{matrix} $$

As you can see, these specific boxes have sizes starting from $2\times w - 1$ up to $h\times w - h + 1$.

The problem is finding a submatrix of $M$ that is isomorphic with any of the boxes in $B$. In other words, swapping rows between them, and/or columns between them so that any of the boxes of $B$ can be placed, for example, in the top left corner of $M$.

If there is more than one solution, the box of maximal height must be choosen, and if there's more than one solution of maximal height, then the one with maximal height and width.

The problem has the following properties:

* $2 \leq h \leq w$.
* Each row of $M$ has at least one $0$.
* Deduced from the way $B$ is generated, for each $b\in B$ of size $b\_h\times b\_w$, it happens that $b\_h + b\_w - 1 = w$.

Is there a way of solving this problem in polynomial time? Can any technique from lineal algebra or numerical characterization of matrices help to the problem?

# Answer
> 3 votes
The problem is NP-hard; it is at least as hard as the biclique problem.

If you can solve the problem for a single shaped box, you can solve for all boxes by just iterating over all the boxes. So your problem reduces to:

> Given a matrix $M$ and integers $h', w'$, find a $h'\times w'$ submatrix of $M$ that is all ones, or report that none exists.

This problem is NP-hard. In particular, if we take any undirected bipartite graph $G$ with adjacency matrix $M$, then $M$ has an all-ones $k \times k$ submatrix if and only if $G$ has a $k$-biclique. Testing for the presence of a $k$-biclique is NP-hard, so your problem must be, too.

---
Tags: algorithms, np-hard, matrices
---


# Question
Title: Applying Case 3 of Master Theorem to $T(n) = 9T(n/3) + n^3$
Given $T(n) = 9T(n/3) + n^3$,

I know that $a =9$, $b=3$, and $f(n) = n^3$

and $n^{\log\_{3}9} = n^2$

thus Case 3 applies: $n^{\log\_{b}a} \< f(n)$, $n^2 \< n^3$.

Can someone explain how to apply the regularity condition and how to check the regularity condition?

$af(n/b) \le cf(n)$ where $c \< 1$

I appreciate your help!

# Answer
> 0 votes
Your statement of the regularity condition has a typo: it suffices to show that there exists a constant $c \< 1$ such that for large enough $n$, $$ af(n/b) \leq cf(n). $$

Substituting $a,b,f$, we have to show that for some constant $c \< 1$, $$ 9(n/3)^3 \le c n^3. $$ You take it from here.

---
Tags: master-theorem
---


# Question
Title: Using inductive hypothesis on recurrence relation?
I have a recurrence relation as follows

$$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$

Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor operator ($\lfloor\cdot\rfloor$).

# Answer
We can open up the recursion to obtain \begin{align} T(n) &\leq n \log n + 2\lfloor n/2\rfloor \log \lfloor n/2 \rfloor + 4\lfloor \lfloor n/2 \rfloor/2\rfloor \log \lfloor \lfloor n/2 \rfloor/2\rfloor \\ &\leq n\log n + n \log (n/2) + n\log (n/4) + \cdots \\ &\leq n\log n + n\log n + \cdots \\ &= O(n\log^2 n), \end{align} since it takes $\Theta(\log n)$ steps to get to the base case.

If you're more careful, you can show that in fact $T(n) = \Theta(n\log^2 n)$.
> 0 votes

---
Tags: algorithms, recurrence-relation, recursion, master-theorem, induction
---


# Question
Title: Recurrence with a function of n times T()
The master method works well on problems like $T(n)=kT(an)+cn$, but it does not handle problems like $$T(n)=n^{\frac{1}{3}}T(n^{\frac{2}{3}})+n^2$$ With the number of branches for each partition is a function of $n$. I wonder if there's a good solution to this kind of problems, I have no idea how to solve this, any help is appreciated!

# Answer
> 0 votes
You can use the more elementary method in which you expand the recurrence: \begin{align} T(n) &= n^2 + n^{1/3} T(n^{2/3}) \\ &= n^2 + n^{5/3} + n^{5/9} T(n^{4/9}) \\ &= n^2 + n^{5/3} + n^{10/9} + n^{19/27} T(n^{8/27}) \\ &= \cdots \end{align} This suggests that $T(n) = O(n^2)$. Indeed, let us try to prove by induction that $T(n) \leq Cn^2$: $$ T(n) \leq n^2 + n^{1/3} \cdot Cn^{4/3} = n^2 \left(1 + \frac{C}{n^{1/3}}\right), $$ which will be at most $Cn^2$ for any $C\>1$ and large enough $n$ (depending on $C$).

Indeed, defining $S(n) = T(n) - n^2$, we have $$ S(n) = n^{5/3} + n^{1/3}S(n^{2/3}), $$ and so the same argument shows that $S(n) = O(n^{5/3})$ and so $T(n) = n^2 + O(n^{5/3})$. In the same way, we can get $T(n) = n^2 + n^{5/3} + O(n^{10/9})$, and so on.

---
Tags: algorithms, recurrence-relation
---


# Question
Title: Algorithm to build tri-nodes in MapleStory
> This problem is originated from the game MapleStory, where the player needs to build "tri-nodes" to enhance their skills, and each skill should appear in two different tri-nodes. For my character, Kanna, I want to enhance 9 skills with 6 tri-nodes (2x9=3x6). After thinking a while for an optimal strategy, it seems to me that the problem isn't that easy. I henceforth abstracted it into an algorithm problem showing below. Please let me know if there is anything unclear in the problem description. Thanks.

A card is a tuple of three letters in `[a,b,c,d,e,f,g,h,i]`, and the three letters within a card are different. For example, `(a, b, c)` could be a card, but `(a, a, c)` can't be because there are two same elements.

We can take exactly 6 cards to acquire 3x6=18 letters, and we want each letter in `[a..i]`to appear exactly twice. However, we cannot take two cards that share the same first element. For example, the following set of cards satisfy the requirement. Each letter appeared exactly two times, and the first elements of these cards are unique.

`[(a,b,c)(b,c,a)(d,e,f)(e,f,d)(g,h,i)(h,g,i)]`

For a deck of $n$ cards ($n$ can be any integer), if there is a set of 6 cards that satisfies the above requirement, we say that this deck is complete, otherwise, we say it's incomplete.

Given a deck of cards,

* (a) determine if the deck is complete.

if the deck is complete, find an algorithm to

* (b) find a solution.
* (c) find all solutions.

If the given deck is incomplete, the requirement cannot be satisfied with the cards in the deck. In such a case, a randomly generated new card will be added to the deck. The new card is generated randomly, meaning that \[a..i\] are equally probable at each position of the card tuple (but still the three positions will be different). After adding a random card, if the deck is still incomplete, another new random card will be added again. As such, we can expect that as the number of cards -\> $\infty$, the deck will eventually become complete.

* (d) Find an algorithm to take $m$ cards ($m\<6$) from the deck, such that
    1. $m$ is as large as possible;
    2. each letter appears at most twice;
    3. it is possible to take $(6-m)$ new cards that may be added in the future to satisfy the requirement. List these new cards.

For example, the following deck is incomplete: `(a,b,c)(d,a,e)(f,d,c)(b,e,f)(g,c,b)` We cannot take all of them because there will be more than 2 b's and c's.

we can have two solutions:

1. `(a,b,c)(d,a,e)(f,d,c)(b,e,f)`

with the appearance count `[a:2,b:2,c:2,d:2,e:2,f:2,g:0,h:0,i:0]`

and the needs count `[g:2,h:2,i:2]`

2. `(d,a,e)(f,d,c)(b,e,f)(g,c,b)`

with the appearance count `[a:1,b:2,c:2,d:2,e:2,f:2,g:1,h:0,i:0]`

and the needs count `[a:1,g:1,h:2,i:2]`

For the former solution, we want the new cards, for example, `(g, h, i)(h, g, i)`. For the latter one, we want the new cards, for example, `(h, a, i)(i,g,h)`. The possibilities of getting the needed cards might be different.

* (e) There might be multiple solutions for (d). Find one that has the maximum possibility to satisfy the requirement with the fewest new cards.

# Answer
Problems (a),(b),(c) can be solved in polynomial time; simply enumerate all possible ways of choosing a subset of 6 cards and test each subset to see whether it satisfies all of the constraints.

If you care about a practical algorithm, I would suggest using a SAT solver. It is easy to express this problem as an instance of SAT. Use boolean variable $x\_i$ to represent whether the $i$th card in the deck is chosen or not. Then you can write boolean constraints that express each of your constraints. I suggest using an off-the-shelf solver like Z3 to solve this instance of SAT; they will tell you whether any solution exists, and if so, give you one example. If you want to find all solutions, look up algorithms to find all satisfying instances to SAT.

Problems (d),(e) are more challenging but can also be solved in the same way. Iterate over $m=5,4,3,\dots$ and for each $m$ use a SAT solver to test whether there exists a solution for that value of $m$. There are at most 120 different cards, so you can imagine having a deck and a sidebar of all the other cards not in the deck; let $x\_i$ represent whether the $i$th card in the deck is chosen, and $y\_i$ represent whether the $i$th card in the sidebar is chosen, and express as an instance of SAT.
> 1 votes

# Answer
I have written a python code for (c) find all solutions. (I am not sure but am I doing dynamic programming?).

(d) and (e) may be difficult.. let's see..

```
letters = [
    'a', 'b', 'd', 'f', 'e', 'c', 'h', 'i',
    'g'
]

current_deck = [['c', 'f', 'd'], ['a', 'b', 'h'],
                ['e', 'a', 'f'], ['d', 'h', 'e'],
                ['c', 'i', 'g'], ['i', 'g', 'c'],
                ['a', 'c', 'g'], ['d', 'c', 'b'],
                ['i', 'd', 'h'], ['g', 'b', 'd'],
                ['g', 'a', 'i'], ['c', 'e', 'f'],
                ['b', 'd', 'f'], ['i', 'b', 'g'],
                ['g', 'c', 'i']]

needs_dict = {}
for i in letters:
    needs_dict[i] = 2

count = [0]

def find_all_solutions(current_deck, needs_dict, first_blacklist, cards_taken,
                    sol):
    count[0] += 1
    if all(v == 0 for v in needs_dict.values()):
        sol.append(cards_taken)
        return cards_taken
    if len(current_deck) == 0:
        return False

    card = current_deck.pop()

    # we cannot take it
    if card[0] in first_blacklist or \
    card[0] not in needs_dict or card[1] not in needs_dict or card[2] not in needs_dict or  \
    needs_dict[card[0]] == 0 or needs_dict[card[1]]==0 or needs_dict[card[2]]==0:
        return find_all_solutions(current_deck, needs_dict, first_blacklist,
                               cards_taken, sol)
    else:
        # we can but don't take it
        donttake = find_all_solutions(current_deck[:], needs_dict,
                                   first_blacklist[:], cards_taken[:], sol)
        # we take it, update needs_dict
        dic = needs_dict.copy()
        for i in card:
            dic[i] = dic[i] - 1
        take = find_all_solutions(current_deck[:], dic,
                               first_blacklist + [card[0]],
                               cards_taken + [card], sol)

        return sol

def check_a_solution(sol, needs_dict):
    dic = needs_dict.copy()
    for i in sol:
        for j in i:
            dic[j] -= 1
    return all(v == 0 for v in dic.values())

solutions = find_all_solutions(current_deck, needs_dict, [], [], [])

for i in solutions:
    assert check_a_solution(i,needs_dict)

print(solutions)
print(count)

```
> 1 votes

---
Tags: algorithms
---


# Question
Title: Halting problem for turing machines with one input
My question is:

> Is there a simple construction similar to Turing's 'liar' program that shows that Turing machines plus a halting oracle cannot decide if a given Turing machine halts on all inputs.

When I talk about the liar program I am referring to the standard proof that a Turing machine can't determine the halting of all other Turing machines, since case analysis on the following leads to contradictions

```
def Liar(T):
   if Halts('T(T)'):
      loop()
   else:
      return

```

I can see that having a Halting oracle would allow me to determine if a Turing machine halts on any finite set of inputs (We would just run it all in order).

If we call regular Turing machines level 0, we can call Turing machines plus the halting oracle level 1. I have seen that the proof using the Liar program works just the same to show that level 1 machines have their own Halting problem which is undecidable for them.

# Answer
> 1 votes
What you call a "liar" program is typically called a *diagonalization argument*, since it somehow resembles Cantor's diagonalization argument.

Usually what we mean by that is that if we try to enumerate all elements with a certain property, then we can point out, by construction, an element that is necessarily "incorrect", and we do so by showing that it does not satisfy the property with regards to itself (this is completely hand-wavy, but if you've seen the argument, you'll hopefully understand what I mean).

Now, what you're asking is whether we can do the same in order to show that ALL\_TM (TM universality) is not decidable by a TM with oracle to HALT\_TM.

Well, not really. At least not in a natural way: the argument would have to start by assuming there exists an oracle machine M that decides ALL\_TM, and then constructing from M some other machine N (what you call a "liar" machine), which would yield a contradiction when we run N on N. However, the machine N would have to be an oracle machine, not a standard TM (or you would essentially lose the power of the oracle in M). But since the oracle in N takes as input standard TMs, then the inner working of N would somehow need to create a standard TM to feed to the oracle. This doesn't seem like a natural construction, and it would certainly not be simple.

Now, perhaps there is some convoluted way of giving a direct diagonalization argument for this claim, but it's not well motivated, given that proving the claim directly (namely that ALL\_TM is not decidable by a TM with oracle to HALT) is not difficult using standard tools, such as reductions.

---
Tags: turing-machines, church-turing-thesis
---


# Question
Title: Finding the worst case running time of this piece of code?
I am working with this code:

```
function strange (list a[0..n-1] of integers such that abs(a[i]) ≤ n for every 0 ≤ i ≤ n - 1, list b[0..2n] of zeroes)

for i ← 0 to n - 1 do
       a[i] ← a[i] + n
for i ← 0 to n - 1 do
       for j ← 0 to abs(a[i] - 1) do
              b[j] ← b[j] + 1
return b

```

I am trying to figure out the worst running time for the code above and so far I'm guessing that the first for loop will run n times, but not sure how to prove this. For the second and third for loop, I'm unsure how to approach this. If possible, could someone help me solve this?

# Answer
> 0 votes
$O(n)$ for the first section and $O(n^2)$ for the second, so $O(n^2)$ overall.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: How can we construct a TM with a Halt1 Oracle that decides if a TM halts on all inputs?
> Can we construct an explicit Turing Machine with a Halt1 oracle that decides if a standard Turing Machine halts on all inputs?

By a Halt1 oracle I mean that we have the ability to decide if Turing Machines with a Halting oracle halts or not.

# Answer
> 1 votes
I think that I have an answer to this, putting together my question helped me clarify things enough to come up with this idea

```
def X(T : TM0):
   for n = 0 and up:
      if !Halt0('T(n)')
        return

```

Now if we ask `Halt1('X(T)')` we should get an answer

* yes =\> T diverges on some input
* no =\> T halts on all inputs

Does this all make sense logically?

---
Tags: turing-machines
---


title: Efficient encoding of sudoku puzzles

text:
# Question
Title: Efficient encoding of sudoku puzzles
Specifying any arbitrary 9x9 grid requires giving the position and value of each square. A naïve encoding for this might give 81 (x, y, value) triplets, requiring 4 bits for each x, y, and value (1-9 = 9 values = 4 bits) for a total of 81x4x3 = 972 bits. By numbering each square, one can reduce the positional information to 7 bits, dropping a bit for each square and a total of 891 bits. By specifying a predetermined order, one can reduce this more drastically to just the 4 bits for each value for a total of 324 bits. However, a sudoku can have missing numbers. This provides the potential for reducing the number of numbers that have to be specified, but may require additional bits for indicating positions. Using our 11-bit encoding of (position, value), we can specify a puzzle with $n$ clues with $11n$ bits, e.g. a minimal (17) puzzle requires 187 bits. The best encoding I've thought of so far is to use one bit for each space to indicate whether it's filled and, if so, the following 4 bits encode the number. This requires $81+4n$ bits, 149 for a minimal puzzle ($n=17$). Is there a more efficient encoding, preferably without a database of each valid sudoku setup? (Bonus points for addressing a general $n$ from $N \times N$ puzzle)

It just occurred to me that many puzzles will be a rotation of another, or have a simple permutation of digits. Perhaps that could help reduce the bits required.

According to Wikipedia,

> The number of classic 9×9 Sudoku solution grids is 6,670,903,752,021,072,936,960 (sequence A107739 in OEIS), or approximately $6.67×10^{21}$.

If I did my math right ($\frac{ln{(6,670,903,752,021,072,936,960)}}{ln{(2)}}$), that comes out to 73 (72.498) bits of information for a lookup table.

But:

> The number of essentially different solutions, when symmetries such as rotation, reflection, permutation and relabelling are taken into account, was shown to be just 5,472,730,538\[15\] (sequence A109741 in OEIS).

That gives 33 (32.35) bits, so it's possible that a clever method of indicating which permutation to use could get below the full 73 bits.

# Answer
> 6 votes
> Is there a more efficient encoding, preferably without a database of each valid sudoku setup?

Yes. I can think of an encoding improving your 149-bit encoding of a minimal $9\times 9$ puzzle in 6 or 9 bits, depending on a condition. This is **without** a database or any register of other solutions or partial boards. Here it goes:

First, you use $4$ bits to encode a number $m$ with a minimal number of appearances in the board. The next $4$ bits encode the actual number $\ell$ of times $m$ appears. The next $7\ell$ bits encode each of the positions in which $m$ appears.

The following $81-\ell$ bits are flags indicating whether the **remaining** positions have a number or not (you just skip the positions in which $m$ is). Whenever one of these bits is `1`, then the next **3 bits** indicate which number it is (in the ordered set $\\{1,\ldots,9\\}$ without $m$). For example, if $m=4$ and the 3 bits are `101`, then the number in the corresponding position on the board is the the 5th (counting from 0) in the set $\\{1,2,3,5,6,7,8,9\\}$, so it is $6$. Numbers $j\<m$ will be encoded in binary as $j-1$, while numbers $j\>m$ will be encoded as $j-2$. Since we had already written $\ell$ positions, only $3(n-\ell)$ bits will be added to encode the rest of the board in this step.

Thus, the total number of bits required to encode a board using this procedure is $$B=4+4+7\ell+(81-\ell)+3(n-\ell)=89+3\ell+3n.$$

For $n=17$, we note that $\ell$ can be 0 or 1 (in general, $\ell\leq\lfloor n/9\rfloor$). Thus, $B$ can be 140 or 143 depending on whether there's a number not appearing on the board.

It's worth pointing out that Kevin's solution is way better in the general case. This encoding uses at most 149 bits only for $n\in\\{17,18,19\\}$, or for $n=20$ provided that $\ell=0$. At least it shows a general idea on how to take advantage of the fact that $N=9$ is very close to $2^{\lfloor\log\_2N\rfloor}$ (which means we tend to "lose memory" by using 4 bits per value, since 4 bits allow us to express $N=16$ numbers as well.

---

**Example.** Consider the following board with $n=17$ clues.

```
.  .  .   .  .  .   .  1  .
4  .  .   .  .  .   .  .  .
.  2  .   .  .  .   .  .  .

.  .  .   .  5  .   4  .  7
.  .  8   .  .  .   3  .  .
.  .  1   .  9  .   .  .  .

3  .  .   4  .  .   2  .  .
.  5  .   1  .  .   .  .  .
.  .  .   8  .  6   .  .  .

```

Here, no number does *not* appear on the board, and numbers 6, 7 and 9 appear only once. We take $m=7$ (`0111`) and $\ell=1$ (`0001`). Reading the positions from left to right and then from top to bottom, $m$ appears in the position $36$ (`0100100`). Thus, our encoding begins with `011100010100100`.

Next, we need seven `0`s, one `1` and the 3-bit encoding of the number $1$, then a `0` followed by a `1` and the 3-bit encoding of $4$, etc. (`0000000100101100`). Eventually, we will skip the position where $m=7$ is, and we will encode 8 as `110` (the 6th number counting from 0 on the list ${1,2,3,4,5,6,8,9}$) and 9 as `111`. The full encoding goes as follows:

```
// m=7, l=1 and its position on the board.
011100010100100
// Numbers 1 and 4 at the beginning. Note that 1 is encoded 000, and 4 is 011.
0000000100001011
// Numbers 2 and 5.
0000000001001000000000001100
// Numbers 4 and 8. We skip the appearance of 7 and encode 8 as 110.
010110001110
// 3, 1 and 9. 9 is encoded as 111.
00010100000100001111
// 3, 4, 2, 5, 1, 8, 6 and the last empty cells.
0000101000101100100100011000100000000000111001101000

```

The complete encoding is `01110001010010000000001001010110000000001001000000000001100010110001110000101000001000011110000101000101100100100011000100000000000111001101000`, and the reader can check the length of that string is indeed 143 :-)

# Answer
> 2 votes
Here's a no-table method that combines a 75-bit encoding of the solution grid with an 81-bit encoding of which cells are clues to give a 156 bit fixed-length encoding for all puzzles (**\[edit\]** also see below for further development of a variable length encoder for the clue positions which needs 73.1 bits on average instead of 81, yielding 148.1 overall with an upper bound of 156).

Consider the pattern below:

```
1 2 3|x x x|x x x
4 5 6|x x x|x x x
7 8 9|x x x|x x x
-----+-----+-----
y y y|. . .|. . .
y y y|. . .|. . .
y y y|. . .|. . .
-----+-----+-----
y y y|. . .|. . .
y y y|. . .|. . .
y y y|. . .|. . .

```

There are 36288^2 = 1316818944 configurations the x's and y's that are essentially different in terms of the constraints they impose on solutions completing the rest of the grid. (There are 1+27+27+1=56 ways to choose unordered sets of three digits to fill the rows of the first box of x's, but this double-counts since the left and right boxes can be exchanged, so it's really 28. Then holding the first row fixed in some canonical order, there are (3!)^4 ways to permute the x digits on the second and third rows, giving 36288 essentially different configurations for the x's with the same logic applying to the y's).

For each of these there are 1881169920 equivalence-preserving transformations arising from (2 * 3! * 3! ways to permute the rightmost 6 columns) X (2 * 3! * 3! ways to permute the bottom 6 rows) X (9! ways to permute all the digits).

Running a backtracking solver for each of the essentially different configurations, we find that none has more than 11664 completed solutions\[1\].

We can therefore uniquely encode a Sudoku solution grid by identifying a starting configuration, an equivalence-preserving transformation, and a solution index (given, say, lexicographical ordering). This requires 75 bits (pretty close to the 73 bit minimum possible) since:

$\small{\mathrm{log\_2}(1316818944) + \mathrm{log\_2}(1881169920) + \mathrm{log\_2}(11664) \approx 74.6}$

Combining this with an 81-bit encoding of which cells are given as clues gives a 156 bit fixed-length encoding overall.

**\[edit\]** Following the encouragement of greybeard below, we can also try to use fewer than 81 bits to encode which cells are clues. One way to do this is to evaluate each cell in turn following some deterministic ordering and emitting the corresponding bit only if its value can not be determined by the clues earlier in the ordering and the constraints of solution uniqueness or puzzle minimality (if this is assumed).

For example, suppose we have a propositional theory, $T$, encoding the exactly-one constraints of Sudoku, where $ x\_{ij} $ represents a candidate for cell $ i \in \\{1..81\\} $ and value $ j \in \\{1..9\\} $, and $c\_i$ represents whether cell $i$ contains a clue. To address a specific puzzle and its solution, let $s\_i$ be an alias for whichever $x\_{ij}$ is the solution for cell $i$, let $S$ be the set of clauses $\land\_i\\{ \lnot c\_i, s\_i \\}$, and let $g\_i$ be alias for either $c\_i$ or $\lnot c\_i$, depending on whether cell $i$ is given.

We can write the clue info as follows:

$\mathrm{for}\\, i\\, \mathrm{in} \\, 1..81 \\ \quad \mathrm{if \\, (satcount}( T \land S \land (\land\_{j\<i} g\_j) \land \lnot s\_i) = 0) \\, continue \\ \quad \mathrm{if \\, (satcount}( T \land S \land (\land\_{j\<i} g\_j)\land (\land\_{j\>i} c\_j)) \> 1) \\, continue \\ \quad \mathrm{emit}(g\_i)$

The first condition skips writing non-clue indicators for cells whose value is implied by prior clues. The second skips writing clue indicators for cells which, given prior clues, must be clues to make the solution unique.

Testing with a million Sudoku generated by a controlled-bias sampler finds that this encoder requires on average 73.8 bits per puzzle, or 76.6 bits per puzzle if we don't assume the puzzles are minimal. Using a knight's move cell ordering instead of the natural ordering brings this down to 73.1 bits per puzzle (assuming minimality), and there is likely room for further improvement by finding heuristic orderings based on the solution grid.

So this gives us a full encoding with expected length of 148.1 bits, with a 156 bit upper bound.

**\[edit2\]**: Another scheme, maybe simpler, but achieving slightly inferior compression is to use 5 bits to encode the clue count (giving a range from 17 to 48, which should include all minimal puzzles), and then to encode the clue positions for n-clue puzzles using position in a ordering of the $81 \choose n$ ways to choose n clues. Assuming the same sample of puzzles as used above, this requires on average 75.6 bits per puzzle.

\[1\] A table of solution counts for the configurations described above can be found here: https://github.com/t-dillon/tdoku/releases/tag/tables in tables.tar.xz

```
$ hexdump -d grid.counts | awk '{for (i=2;i<NF;i++) if ($i>x) x=$i} END {print x}'
11664

```

# Answer
> 0 votes
> it's possible that a clever method of indicating which permutation to use could get below the full 73 bits

No, because encoding the permutation/relabelling/rotation/whatever takes you back to 73 bits.

Off the top of my head, I'm guessing there are 8 possible symmetries. Then assuming that you need two permutations (rows and columns?) and one relabelling:

$$32.35 + 3 \log\_2 9! + \log\_2 8 \approx 73.76$$

I must have overcounted somewhere in counting the permutations and relabellings, but it's very close. Presumably not all permutations result in valid grids.

I do have an encoding that's going to get you extremely close to the minimal 73 bits, and it doesn't use any tables.

You're not going to like it.

Essentially, you encode each cell using your favourite fractional-bit encoder (e.g. arithmetic, range, ANS, whatever), and encode each symbol with probability $\frac{1}{n}$ where $n$ is the number of values that the cell could have *in any valid Sudoku puzzle*.

You determine that set by using a Sudoku solver; ideally one that allows for incremental updates such as DLX. For the cell in question, you try each possible digit as a given value and see if the resulting puzzle has any solution. You don't need the solution, just to know that one exists. If it does, that's a possible value.

If it seems a bit crazy to use a Sudoku solver in the inner loop just to test individual values, do bear in mind that this is how you do "perfect pencilling".

---
Tags: combinatorics, modelling, information-theory, sudoku
---


# Question
Title: Solving recurrence relation $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$
Given the condition: $T(O(1)) = O(1)$ and $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$. I need to solve this recurrence relation. The hardest part for me is the number of subproblems $\sqrt{n}$ is not a constant, it's really difficult to apply tree method and master theorem here. Any hint? My thought is that let $c = \sqrt{n}$ such that $c^2 = n$ so we have $T(c^2) \leq cT(c) + c^2$ but I does not look good.

# Answer
> 1 votes
Let $k=k(n)$ be the smallest positive integer such that $n^{2^{-k}}\<2$. Equivalently $k$ is the smallest positive integer such that $k\>\log\_2(\log\_2(n))$. So, $$k=\lceil \log\_2(\log\_2(n))\rceil$$ Using repeatedly the inequality with $n,n^{2^{-1}},n^{2^{-2}},...,n^{2^{-k}}$ we get $$ \begin{align} T(n)&\leq n^{1/2}T(n^{1/2})+n\\ &\leq n^{1/2+1/4}T(n^{1/4})+2n\\ &\leq n^{1/2+1/4+1/8}T(n^{1/8})+3n\\ &...\\ &\leq n^{1/2+1/4+...+1/2^k}T(n^{2^{-k}})+kn\\ &=n^{1-2^{-k}}O(1)+kn\\ &\leq n^{1-1/\log\_2(n)}O(1)+n\log\_2(\log\_2(n))\\ &=\frac{n}{2}O(1)+n\log\_2(\log\_2(n)) \end{align} $$

So, we get that $$T(n)\in O(n\log\_2(\log\_2(n)))$$

---
Tags: recurrence-relation, divide-and-conquer
---


# Question
Title: Deadlock vs "Progress" requirement of the solution to the critical section problem
I came across following problem:

> Consider following code:
>
> ```
> ()
> {
>     [] = ;
>     ([]);
>     /*   */
>     [] = ;
>     /*  */
> }
>
> ```
>
> Let flag is declared as Boolean `flag[2]` and `Pi` denote one process while `Pj` denotes other process and `i=1-j`. Both processes execute concurrently, then does the progress requirement of the solution to the critical section problem satisfied in the above case?

**Doubt**

The solution says that both processes Pi and Pj can simultaneously execute `flag[i]=true` and then both may busy wait on `while(flag[j])`, thus leading to deadlock and hence progress requirement of the solution to the critical section problem is not satisfied.

I know the normal / day to day meaning of "progress" gives us feeling that if there can be deadlock, then there may not be the progress. But Galvin's book defines "Progress" as this:

> If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.

So I am guessing whether progress has anything to do with deadlock. And whether the code indeed satisfies progress requirement of critical section problem.

# Answer
> 1 votes
> and this selection cannot be postponed indefinitely

In case of deadlock, deciding which process will enter next will be postponed indefinitely. So progress won't happen.

---
Tags: operating-systems, deadlocks, critical-section
---


title: Storage in registers

text:
# Question
Title: Storage in registers
Whenever CPU needs the data, it gives the address of that word to the RAM via bus, then the RAM generated the copy of that word and sends to the registers via bus. Why can't the RAM send the original data instead of the copied data? Are there any disadvantages of storing original data or reference in registers?

# Answer
This question illustrates a lack of understanding of fundamentals. What does moving ***mean***!?

The RAM stores data in transistors. Do you want a little robot to pick up the specific transistors you want out of the RAM chip and deliver them to the CPU? I hope it is obvious why that is not possible.

Instead, an electronic circuit (which those transistors are part of) looks at whether those transistors are on or off. This causes an electrical signal to be sent to the CPU which updates some of its own transistors according to the electrical signal.

The question is akin to: "Whenever I need my friend's phone number, I copy it from my brain into my phone. Why can't my brain send the original data instead of making a copy?"
> 1 votes

# Answer
There are computer memory implementations allowing destructive read-out, only, starting with *(ferromagnetic) core memory* and *(single-transistor)DRAM*: these transfer information from an array of low cost *memory cells* to some *static* circuitry, provide it at the output(s) and usually write it back into that array cell.
Without that write-back, I guess one could claim data was transferred rather than copied - I can't remember a memory interface standard specifying destructive read (allowing lower read *cycle times*).
Not all information has discrete values (and "analogue" computers handle non-discrete values, if not signals):
Information was definitely transferred rather than copied in charge-coupled devices.
> 0 votes

---
Tags: computer-architecture, operating-systems, memory-management, memory-access, memory-allocation
---


# Question
Title: Divide first n square numbers 1^2, 2^2, ....... n^2 into two groups such that absolute difference of the sum of the two groups is minimum
lets say Given input is n = 6 (n is as large as 100000) My task is to divide {1, 4, 9, 16, 25, 36} into two groups and PRINT these two groups

Possible Solution 1: dividing groups as {1, 9, 36} and {4, 16, 25} which gives abs diff as abs(46 - 45) = 1. So the minimum difference is 1 and the two groups are {1, 9, 36} and {4, 16, 25}

Possible Solution 2: Another Possible Solution is dividing groups as {9, 36} and {1, 4, 16, 25} which gives abs diff as abs(45 - 46) = 1. So the minimum difference is 1 and the two groups are {9, 36} and {1, 4, 16, 25}.

If there are multiple solutions we can print any one. Iam trying to solve it using https://www.geeksforgeeks.org/divide-1-n-two-groups-minimum-sum-difference/ but its not working.

I know that min difference is always 0 or 1 for n \>= 6 but how to divide them into two groups.

And can we extend this problem to cubes, fourth powers, so on. if so what is the strategy used

# Answer
> 2 votes
It's quite related to my research work, It would be helpful for me if you post the solution when you get it. But I don't think it can be solved by using pen and paper as the constraints you mentioned is quite huge.

**Solution 1 :**

Your problem statement can be re written as , Expressing a Number(P) as sum of kth Power of distinct numbers.

Now if you want to translate this to your problem Then, P = floor\[(∑N^2)/2\]

As you have already stated that the difference is always 1 or 0. The below links might help you. https://www.sciencedirect.com/science/article/pii/S0012365X03000967?via%3Dihub http://www.math.uchicago.edu/~may/VIGRE/VIGRE2009/REUPapers/Wong.pdf

**Solution 2:**

The other non suggestible solution to solve this is using patterns, for n\>6 The difference will for a pattern 0011 with period 4. Here Diff is dependent on N and the perfect kth power we choose. According to theory of dependent relativity when Diff follows a pattern, The perfect powers must also follow a pattern because they both are dependent. Kindly let us know if you see any patterns there.

**Solution 3:**

Make two sets as odd numbers on one set and even numbers on one set, Now use swaps by using two pointers to make the difference as minimum as possible. It will not take more than two swaps.

**Solution 4:** https://en.wikipedia.org/wiki/Lagrange%27s\_four-square\_theorem Use lagrange four square theorem and evaluate a,b,c,d where s/2 = a^2+b^2+c^2+d^2 but lagrange can give duplicate values. for ex: a=c, b,d are distinct values that you got from lagranges now call a recurrence relation to split a^2 into 4 distinct values or c^2 into distinct values. Run this function till you get all distinct values.

Also please care to post here if you find any solution to this problem or if any above links or any other links works.

# Answer
> 0 votes
The page you linked covers a similar but different problem (they partition the integers between $1$ and $n$ rather than their squares), but the same greedy algorithm of "start with the biggest number and put each one into the list whose sum is currently smaller (plus arbitrary tiebreaking)" works for this problem as well.

To analyze the algorithms, note that at each step we have 2 possible cases:

1. Adding the next number $k$ to the list with the smaller sum makes it so that the list still has a smaller sum than the other one. In this case, the difference between the two sums decreases (by $k$).
2. Adding the next number $k$ to the list with the smaller (after tiebreaking) sum makes it so that this list's sum is now greater. Hence the difference between the two sums might increase, but the difference may not exceed $k$ (which would be the case if the two sums were equal).

Hence the final difference is bounded by the last $k$ for which the second case occurs. However, we can show that both cases alternate by noting that $$ (n + 1)^2 = n^2 + 2n + 1 $$ and exploiting that $n^2 \> 2n + 1$ for all $n \> 1$. This yields that (with the exception of choosing a list for $1$) we will choose the same list to add a number to more than twice in a row.

It follows that after placing $9$ into one of the lists we are in the following scenario:

* The difference of sums is at most 9
* If $4$ and $1$ are placed into the same group, then the final difference is at most $9 - 4 - 1 = 4$.
* If $4$ and $1$ are placed into different groups, the final difference is at most $4 - 1 = 3$.

Note that these are hard limits: in the cases where $n = 3$ we see that a final difference of $4$ cannot be avoided on all inputs.

# Answer
> 0 votes
The sum of the first n squares is $s\_n = n(n+1)(2n+1) / 6$. For n=10, the sum is 385, and the numbers 129 to 256 are the sum of a subset of these squares (found by brute force search). That range is 129 to $s\_n - 129$. Since the range is large enough, containing 127 integers, we can show by induction that every integer from 129 to $s\_n - 129$ is the sum of a subset of the first n squares for every $n ≥ 10$.

If $n ≥ 10$ we can start with two empty sets A and B, then add $n^2$, $(n-1)^2$, ..., $11^2$ to the set with the smaller sum, and we will end up with two sums with a difference of at most 121. Let the difference be d. Assume 0 ≤ d ≤ 121, otherwise exchange the two sets.

$\lfloor (s\_n - d) / 2 \rfloor$ is the sum of a subset S of the squares from $1^2$ to $10^2$, and $\lceil (s\_n + d) / 2 \rceil$ is the sum of the other squares. If we add S to A and the other squares to B, then the difference in the sums is either 0 or 1.

If $s\_n$ is even, that’s it. Otherwise we pick all ways to write $s\_n$ as a product $a \cdot b$ of two odd numbers ≥ 3 and try to distribute the squares into a subsets each with a sum equal to b. This will be hard if the smaller divisor a of the sum is not small, say about n. (I notice the question asks for two groups, but that's boring).

The nine cases $n ≤ 9$ would need to be handled separately.

A reasonably slow growing function other than $f(n) = n^2$ may be handled using the same method. That's just a small programming problem.

However, I just heard this is a question from a coding competition. In that case: Asking here is cheating. If you use this answer in a coding competition, you're a cheat. And I'm glad I left enough out so that at least some minimal competence is needed to get a solution.

---
Tags: algorithms, mathematical-programming
---


title: Subset sum problem with a complication

text:
# Question
Title: Subset sum problem with a complication
I have a sorted list of numbers. I know they can be divided into two parts. I also know the sum of those 2 parts. I want to know what these subsets are. How can i find them? The size of my list can be ~ 10^6. The sum of my subsets can be ~ 10^24. Is there a better way to find my subset with a time complexity of O(n\*sum) or O(2^n \*n) or is it not possible?

# Answer
You are fully in the range of numbers where NP-completeness hits you. If you're lucky dynamic programming can be a bit faster, but not much.

Sort the numbers in ascending order. If you take the first k numbers, there are $2^k$ subsets. With dynamic programming, you determine all possible sums, and they will be less than $k \cdot 10^{18}$. Maybe around k = 100 you will hopefully have large ranges of consecutive integers that are possible sums. Let's say all integers from 1,013,460 to 1,576,390 are possible sums, and the next number is $x\_{k+1}$. Then all integers in the range 1,013,460 to 1,576,390 are possible sums for k+1 integers, and so are all the integers in $1,013,460+x\_{k+1}$ to $1,576,390+x\_{k+1}$. Determined in constant time. So with a bit of luck, adding the next k to your DP table can be very little work. Still, the numbers that you have will make this close to impossible.

The best case is some slowly growing numbers. For example, splitting the first billion cubes into two sets with same sum (if the total sum is even) or almost equal sum (if the total sum is odd) should be not very difficult. Or for example n integers randomly picked, but each close to $k^3$.
> 1 votes

---
Tags: algorithms, data-structures, dynamic-programming, arrays
---


title: Balanced sub-sequence

text:
# Question
Title: Balanced sub-sequence
Consider two strings $S$ and $T$ of length $n$. Here both the strings $S$ and $T$ consists of only `(` and `)` that is made of parenthesis. I need to find a string $w$ which is balanced parenthesis and it should be sub-sequences of both $S$ and $T$ among all those strings $w$ i need the maximum length strings.

This problem is clearly a dynamic programming problem, but i am having hard time in finding states and also their transitions. Could anyone help me.

P.S - Problem E , but it is in Russian

# Answer
> 0 votes
Initially I missed a key part of the question, that is, the subsequence we are looking for must be a common subsequence for two strings $S$ and $T$. I'll keep my initial answer, and will elaborate after that, about how to extend to the case of interest.

---

One way to detect if a sequence forms a valid balanced parenthesis is to change `(` for `+1` and `)` for `-1` and check that the sum of every prefix is non-negative $(P\_i \geq 0)$ and the sum of the entire sequence is $0$ ($P\_n = 0)$. We define $P\_i$ as the balance of the $i$-th prefix.

To compute the largest valid subsequence you can keep track for each prefix $i$ what is the largest valid subsequence of that prefix with a fixed balance $b$: $(Q\_i^b)$. The answer to your problem is $Q\_n^0$.

Fortunately $Q\_i^\*$ only depends on the $i$-th character and $Q\_{i-1}^\*$ so we can use dynamic programming to compute such values. Let's define for the sake of simplicity that for states such that no valid sequences exist the value of $Q\_i^b = -\infty$.

The base case for empty prefix $i = 0$.

* $Q\_0^0 = 0$: The largest valid subsequence for the empty prefix is the empty string (size=$0$) which has balance $0$.
* $Q\_0^b = -\infty$: For all balance different than $0$ there is no such string that is subsequence of the empty prefix with balance $b$, so we use $-\infty$.

Let's define transitions to compute each value given that all previous values (with less $i$) are already computed. On each step we either append that character to the end of the subsequence, or we discard that character:

$$Q\_i^b = \max(Q\_{i - 1}^b, Q\_{i - 1}^{b - s\[i\]} + 1)$$

The first term in the $\max$ expression cover the case that we don't use the last character, so the maximum subsequence with balance $b$ and prefix $i$ is at least as large as the maximum subsequence with balance $b$ and prefix $i - 1$.

The second term in the $\max$ expression cover the case that use the last character, notice that $s\[i\] = +1$ if there is an open parenthesis `(` at position $i$, or $s\[i\] = -1$ otherwise. Then the new balance will be $b$ if in the previous step the balance was $b - s\[i\]$, so after adding the $i$-th character it becomes $b$.

We should only compute $Q\_i^b$ values for $b \geq 0$, to keep the balance of the sequence always non-negative.

In practice we know the balance won't be larger than $n$ (in fact it won't be larger than $\frac{n}{2}$) so we can compute values of $Q\_i^b$ for $0 \leq i \leq n; 0 \leq b \leq n$. Each transition is computed in $O(1)$ so the overall complexity of this solution is $O(n^2)$. Since states $Q\_i^\*$ only depend on states $Q\_{i -1}^\*$ we can use only $O(n)$ memory keeping at each moments two rows of the dynamic programming table.

---

To find a subsequence of two strings $S$ and $T$ we can instead use a dynamic programming state with $3$ dimensions: What is the maximum valid parenthesis sequence with balance $b$ which is a subsequence of prefix of length $i$ from $S$ and prefix of length $j$ from $T$ ($R\_{i,j}^b$). The answer is $R\_{|S|, |T|}^0$.

The solution is almost the same but transition should be modified to address the new constraint:

$$R\_{i, j}^b = \max(R\_{i - 1, j}^b, R\_{i, j - 1}^b, R\_{i - 1, j - 1}^{b- S\[i\]} \cdot \[S\[i\] == T\[j\]\])$$

The first two terms inside $\max$, handle the case where the best sequence with balance $b$ of prefixes $i$ and $j$ from $S$ and $T$ don't use the last character for both, so at least one of them is not used, and we cover both situations.

The third case is trickier, it handles the case where we do use the last character, but we can only use that character if both character are the same $S\[i\]$ and $T\[j\]$, since we most find a common subsequence.

Note about complexity: Now complexity is $O(n^3)$ since that is the number of states and each state is computed in $O(1)$. Again, we can apply a trick to use $O(n^2)$ memory, however it is very tricky to do that and also being able to recover the answer.

In practice: The problem have $n=700$ and time limit $3.5$ seconds. Notice that the number of operations you are doing are roughly $\frac{700^3}{2}=171500000$ basic operations. A modern machine should perform roughly $1e8$ basics operations per second, so this solution should fit in time.

However, to recover the answer you should store for each state, the optimal decision. Notice there are only 3 options, so it fits in 2 bits. It requires $\frac{700^3}{2} \cdot 2$ bits which is $~42MB$. However, if instead of bits, a byte is used to store each decision, the the code will use $\frac{700^3}{2}$ bytes which is $171MB$ and is greater than the limit $128MB$.

---
Tags: algorithms, dynamic-programming, combinatorics
---


# Question
Title: What is the difference between "information model" and "conceptual model"?
I am trying to figure out the difference between **information** and **conceptual models**. For me, both terms seem to mean be the same, but I cannot find a reference where this is established. They are never used together; maybe because they are from different domains?

My question is: What is the difference between **information model** and **conceptual model**?

## **Definitions**

**Conceptual model:**

> A domain consists of objects, relationships, and concepts we commit ourselves to a specific way of viewing domains. \[...\] In the field of information systems, this commitment to viewing domains in a particular way is called the conceptual model. \[Antoni Olivé. 2007. Conceptual Modeling of Information Systems. Springer-Verlag, Berlin, Heidelberg.\]

**Information model:**

> An information model is a representation of concepts, relationships, constraints, rules, and operations to specify data semantics for a chosen domain of discourse. The advantage of using an information model is that it can provide shareable, stable, and organized structure of information requirements for the domain context. \[Y. Tina Lee, Charles R. McLean and Yan Luo, Information Modeling and Model Implementation. In: Proceedings of the International Simulation Conference, Italy, 2006\]

# Answer
> 0 votes
Conceptual Modeling, Information Modeling and Data Modeling are all terms that more or less specify the same. I do not believe there is a common consensus about these terms.

When reading the articles of the authors you refer to, I get the impression that (for these authors) Conceptual Modeling is broader than Information Modeling.

A Conceptual Model can contain actors other than only computers (e.g. humans), can contain time aspects (e.g. events, and the required reaction to these events, called *Behavioral Modeling* by Olivé) and can contain concepts that will not necessarily translate into a data model (“we use the name *conceptual modeling* for the activity that elicits and describes the general knowledge a particular information system needs to know”).

An Information Model, as used by Lee et. al., has a more narrow scope (“The initial phase for developing an information model starts with the definition of the scope of the model’s applicability. The scope specifies the domain of discourse and the processes that are to be supported by the information model. It is a bounded collection of processes, information, and constraints that satisfy some industry need”) and his modeling seems to limit itself to a subset of the conceptual model. Lee et. al. also write their article with a particular industry in mind, manufacturing, where Olivé does not limit himself to an industry.

For example, a Conceptual Model could model a company including less tangible processes such as Strategy development an Marketing, and an Information Model could model some key process of the company derived from the conceptual model, for example purchasing and logistics.

I did not read their full article. I just did a scan to find where they apparently seem to differ and, as said, there is to my knowledge no clear consensus about what each term exactly means.

# Answer
> 0 votes
Due to my experience it's quite easy to understand the difference, though for me the difference wasn't obvious for long time.

Let's consider yourself sitting on a chair in your kitchen looking at a table. On the table there are 10 apples of different sizes of two sorts: 3 apples of one sort and 7 for another. Also there are 3 knifes, 2 lemons, and 4 credit cards.

Obviously, we can identify concepts or types like: Apple, Lemon, Knife, Credit Card, Kitchen. We can go from generalized concept "Apple" down to subconcepts of "Apple" of each particular sort, giving definitions to recognize them in real world with our senses. It's obvious that every Apple, every Apple is unique, has identity if we try to compare them precisely, - we'll find they are different. Right?

And this is Conceptual model or Type model or Domain Model where real objects play major role. This model provides structure for natural language used to talk about problem domain . And your above definition is right. We IT guys and analysts require it to be build precisely to get rid of ambiguity, errors, fictions, misunderstanding, slang and etc we normally face on every project where there is no terminology or it's outdated or all the knowledge is in peoples mind and not formalized.

As we are sure with what things/concepts we deal in a problem domain and how they are related, based on the automation task specifics, we can design proper information model. Goal of information model - is to represent structure for collecting information about concepts required for task being automated. Information model can be represented as sheet of paper or database. That's not important. It's just about structure of records about reality required for specific task to be automated.

Can be represented as lines of text on a paper:

* 3 apples of sort X on table #1 in kitchen #1 at location #1
* 4 apples of sort Y on table #1 in kitchen #1 at location #1
* ...

You get rid of each apple identity and record quantities of things of a kind, sort at specific location and etc. Technologically we cannot record every apple as unique, because there is no way to get and record it's identity. Even if we find and record 100 apple characteristics, theoretically there can be two identical with all 100 properties the same. In reality we have an option to find characteristic #101 to differentiate, but information model is mostly static (AI changes this sure. I talk about std information systems). So you have to quantify things.

But with credit cards situation seems different, but generally the same:

* 1 Credit card #1232233 holder DDDD in kitchen #1 at location #1
* 1 Credit card #2334234 holder FFFF in kitchen #1 at location #1

We rely on card number pretending it's unique. However due errors theoretically and practically there can be 2 cards with the same number and holder and other properties at the same location. So in information model you'll also record it's quantity if you really want to record reality.

So, the main difference between conceptual/type model and information model is that in inf. model there is strictly saying no possibility to talk about object identities at all.

PS: And what about Primary Keys, Unique Constrains and so on? They are all artificial. In other words you can constraint your info model/database to have just one credit card of each number. But in case someone will issue the same credit card or duplicate and insert it into the same ATM your where near 10 minutes before with your original card, how will you recognize it in information system? No way.

But if two "identical" credit cards are lying at the table before us, we can try to differentiate them by doing precise and long comparison. We can thing and talk about each card as about different objects even without knowing where they are different. It is de-facto assumed in conceptual/domain/type model.

Hope this will help to understand such tricky difference.

NB:

* Definition of Information model you've given I think is correct, but not the best.
* Axiomatically someone can argue that there is a possibility to create two completely identical objects... Maybe it's possible. Personally I don't know how to employ the same atoms and electrons for two **different** things looking completely identical.

---
Tags: modelling
---


# Question
Title: In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I'm looking at scheduling problems in particular
In what cases is solving Binary Linear Program easy (i.e. **P** complexity)?

The reason I'm asking is to understand if I can reformulate a scheduling problem I'm currently working on in such a way to guarantee finding the global optimum within reasonable time, so any advice in that direction is most welcome.

I was under the impression that when solving a scheduling problem, where a variable value of 1 represents that a particular (timeslot x person) pair is part of the schedule, if the result contains non-integers, that means that there exist multiple valid schedules, and the result is a linear combination of such schedules; to obtain a valid integer solution, one simply needs to re-run the algorithm from the current solution, with an additional constraint for one of the real-valued variables equal to either 0 or 1.

Am I mistaken in this understanding? Is there a **particular** subset of (scheduling) problems where this would be a valid strategy? Any papers / textbook chapter suggestions are most welcome also.

# Answer
It is not true that fractional solutions can necessarily be turned into integral solutions. For example, suppose that 1 requires either slots A and B, or slots D and E; 2 requires either slots B and C, or slots E and F; and 3 requires either slots A and C, or slots D and F. It's easy to check there is no integral solution at all (A,B,C together can accommodate at most one, and D,E,F together can accommodate at most one). However there is a fractional solution of giving everyone 1/2 of every slot that might possibly accommodate them.

There are conditions such as total unimodularity that guarantee that there are optimal integral solutions. In that case, the problem is in P, because all that is needed is to solve the LP relaxation which can be done in polynomial time.
> 2 votes

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


title: Signal translation with Seq2Seq model

text:
# Question
Title: Signal translation with Seq2Seq model
I'm currently doing some research on signal processing and I got a dataset which includes the signal in itself and its "translation".

So I want to use a Many-to-Many RNN to translate the first into the second.

After spending a week reading about the different option I have, I ended up learning about RNN and Seq2Seq models. I believe this is the right solution for the problem (correct me if I'm wrong).

Now, as the input and the output are of the same length, I don't need to add padding and thus I tried a simple LSTM layer and TimeDistributed Dense layer (Keras):

```
model = Sequential([
    LSTM(256, return_sequences=True, input_shape=SHAPE, dropout=0.2),
    TimeDistributed(Dense(units=1, activation="softmax"))
])

model.compile(optimizer='adam', loss='categorical_crossentropy')

```

But the model seems to learn nothing from the sequence and when I plot the "prediction", it nothing but values between 0 and 1.

As you can see, I'm a beginner and the code I wrote might not make sense to you but I need guidance on few questions:

* Does the model make sense for the problem I'm trying to solve ?
* Am I'm using the right loss/activation functions ?
* And finally, please correct/teach me

# Answer
> 0 votes
I am skeptical that machine learning is the right tool for this problem. I would look for a more direct solution, perhaps using peak detection or changepoint detection, or some other form of classical method for time-series analysis.

If you do use machine learning, cross-entropy loss is not the right loss for your problem, and you will definitely need to change that.

---
Tags: machine-learning, neural-networks, signal-processing
---


# Question
Title: Why can't we compile 8086 Assembily for all OSs from any OS?
If Mac OS, Linux, and Windows (mostly) all use Intel's 8086 64 bit instruction set, why can't we compile 8086 64 assembly from any operating system to any other operating system? (e.g. compile a Mac OS executable from assembly in Windows). Surely it would just be a matter of knowing what the machine code is for any given instruction?

# Answer
Porting to a different operating system is about a lot more than the particular assembly language you use. Different operating systems have different system calls, different libraries, and different APIs, and converting from one to another is usually not something that can be done in an automated way -- even if both used exactly the same assembly language. Most programs do need to access the filesystem, the network, display things on the screen, and so forth, and all of those require interaction with the OS and libraries.
> 2 votes

# Answer
While **natively assembled** program on one OS may not run on another OS as system calls and libraries are different, yet it is possible to **cross-compile**, i.e., compile on one platform, say Linux to run on another, say MAC OS. It is something quite often done for micro-controllers.
> 0 votes

---
Tags: operating-systems, assembly
---


# Question
Title: Vectorization vs Asynchronous parallelism
I have taken a course "Programming for Performance" in my college and in the first week of the course, I have come across **vectorization** and **Asynchronous Parallelism**. But I am unable to figure out what is the relation and difference between the 2 of them. In the slides, the professor has provided something like this--\>

What does it actually mean that parallelism is **finer-grained** and **course-grained**?

Also here is another instance where he has tried to point out the difference, here we are given 2 code instance and tried to explain the concept, but I am not able to get that.

What I got is that, in the first one both vectorization and asynchronous parallelism is not possible, since there is a **data dependency**, but in the second one vectorization can be done as there is no dependency, but asynchronous parallelism is not achievable since, say we have this 2 instances

A(1) = A(2) + B(2) | A(2) = A(3) + B(3)

So in this case the A(2) may get overwritten by the second instance even before the 1st instance of the code is executed, hence Asynchronous Parallelism is not possible.

Is my understanding of this right?

# Answer
Vectorization and asynchronous parallelism are not exactly comparable. Its like comparing apple and orange. Have a look at Difference between parallel, concurrent and asynchronous.

Vectorization uses the support for different vector instruction in modern processors. For e.g. Intel support AVX512 and AVX256 instructions. Here 512 and 256 are number of bits. So if the operand are 64 bit double values, the hardware can process 8 or 4 set of operands, **parallelly**. Operation(+,-,\* ...) are applied on vector inputs (8 or 4 set of operands) instead of (8 or 4 times) on scalar (single set of operands) inputs.

for(int i=0;i\<1000;i++)
for(int j=0;j\<8;j++)
c\[i\]\[j\]=a\[i\]\[j\]+b\[i\]\[j\]

On a Intel processor this code fragment will be replaced by vector instructions by the *optimizing compiler* . So it is equivalent to something like:

`for(int i=0;i<1000;i++) { c[i][0]=a[i][0]+b[i][0] , c[i][1]=a[i][1]+b[i][1], ..., c[i][7]=a[i][7]+b[i][7] }`

This require that there should be no dependency among consecutive iteration instructions. All eight addition operation execute in parallel by the vector processing hardware of the processor on eight different operand sets. Granularity in vectorization is at the level of 'instructions'.

Asynchronous operations can happen on even single core systems. For e.g., I/O processing. Yes it is the case that, two or more set of operations happen in parallel, but it is not necessary that both are computation operation. It could a memory operation and computation Or a I/O operation and computation. Granularity in Asynchronous operation is 'set of instructions' like a program or a interrupt vector routine.
> 1 votes

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


# Question
Title: Understanding growth function of closed intervals in $\mathbb{R}$
I as studying VCdimensions and growth functions and found the following example on Wikipedia:

The domain is the real like $\mathbb{R}$. The set H contains all the real intervals, i.e., all sets of form $\\{c \in \[x\_1, x\_2\] | x \in \mathbb{R}\\}$ for some $x\_{0, 1} \in \mathbb{R}$.

For any set C of m real numbers, the intersection $H \cap C$ contains all **runs** of between 0 and m consecutive elements of C. The number of such runs of ${m+1 \choose 2} + 1$, so Growth(H, m) = ${m+1 \choose 2} + 1$.

Can anyone please explain to me what does the term "all runs of between 0 and m" refer to here and why the growth function is ${m+1 \choose 2} + 1$ and not ${m+1 \choose 2}$?

Thank you very much!

# Answer
Let the real numbers be $r\_1 \< \cdots \< r\_m$. The intersection $H \cap C$ could be of the form $\\{r\_i,\ldots,r\_j\\}$ for $1 \leq i \leq j \leq m$, or empty. There are $\binom{m+1}{2}$ of the first type, and $1$ of the second type.

For example, if $m = 1$ then the possible intersections are $$ \emptyset, \\{r\_1\\}, $$ if $m = 2$ then the possible intersections are $$ \emptyset, \\{r\_1\\}, \\{r\_2\\}, \\{r\_1,r\_2\\}, $$ and if $m = 3$ then the possible intersections are $$ \emptyset, \\{r\_1\\}, \\{r\_2\\}, \\{r\_3\\}, \\{r\_1,r\_2\\}, \\{r\_2,r\_3\\}, \\{r\_1,r\_2,r\_3\\}. $$
> 1 votes

---
Tags: vc-dimension
---


title: Conjunctive Query Containment as SAT

text:
# Question
Title: Conjunctive Query Containment as SAT
The problem of conjunctive query containment is known to be NP-Complete (originated at Chandra&Merlin 1977). Typically it's shown by reducing 3SAT or 3-colorability into this problem, and the other direction is typically proven by declaring it "trivial" (as it indeed looks trivial to see that the problem is in NP).

My question is how to practically translate the problem of query containment of two datalog rules (plain, without constraints or equalities) into the boolean satisfiability problem (not necessarily in CNF), and by listing the solutions of that latter problem, to see which variable substitutions would recover the containment? In other words, how to solve this problem using a SAT solver in practice?

# Answer
I will try to answer your question limiting to Datalog without recursive predicates. Indeed, I suspect that recursive predicates are beyond conjunctive queries (conjunctive queries are a subset of FOL, and Datalog with recursion can compute Transitive Closures, which are impossible to express in FOL). Furthermore, I will assume that all derived datalog predicates have been unfolded.

As you probably know, a conjunctive query CQ1 contains CQ2 if you can establish an homomorphism of terms from CQ1 into CQ2. Hence, a possible reduction into SAT can be done by considering a boolean variable v for each pair of terms from Terms(CQ1)xTerms(CQ2). Intuitively, the meaning of such variables would be "we map term t1 to term t2". Then, we must ensure that the set of all variables "v" that evaluates to true encodes a correct homomorphism.

More formally, the reduction can be done as follows:

* For each term $t^1\_i \in Terms(CQ1)$, and for each term $t^2\_j \in Terms(CQ2)$, consider a boolean variable $v\_{t^1\_i, t^2\_j}$. Note that all the boolean variables evaluating to true encodes a mapping.
* The encoded mapping must be functional. That is, for each term $t^1\_i$, we need a constraint to state that $t^1\_i$ is mapped to one term, and only one. Hence, we should add, for each term $t^1\_i$, a constraint $(v\_{t^1\_i, t^2\_1} \lor v\_{t^1\_i, t^2\_2} \lor ... \lor v\_{t^1\_i, t^2\_n})$, and for each triple of terms $t^1\_i$, $t^2\_j$, $t^2\_k$ (with j!=k), $(\neg (v\_{t^1\_i, t^2\_j} \land v\_{t^1\_i, t^2\_k}))$
* The encoded mapping must preserve constants. Hence, for each constant term $t^1\_c$, we add the constraint: $(v\_{t^1\_c t^2\_c})$
* The encoded mapping must be a homomorphism. To do so, for each literal $L^1 \in Literals(CQ1)$, let $\\{L^2\_1 ... L^2\_n\\}$ be the set of all literals from $Literals(CQ2)$ with the same predicate. Then, we must ensure that, when mapping the terms of $L^1$ we obtain one literal from $\\{L^2\_1 ... L^2\_n\\}$. To do so, we build a disjunction where each disjunct $i$ means "$L\_1$ is mapped to $L\_i$". In particular, each one of these disjuncts can be built by iterating all the variables from $L^1$ and mapping them to $L^2\_i$ variables. For instance, consider $L^1$ to be $P(x, x, y)$, and considere $\\{L^2\_1 ... L^2\_n\\}$ to be $\\{P(a, b, a), P(c, c, d)\\}$; in this case we would build the constraint: $(v\_{x a} \land v\_{x b} \land v\_{y a}) \lor (v\_{x c} \land v\_{x c} \land v\_{y d})$

This reduction is polynomial. Indeed, the number of boolean variables is quadratic (w.r.t. the number of terms in CQ1 and CQ2), and all the constraints considered can be built with a several (nested) foreach loops that iterates the conjunctive queries terms and literals.
> 1 votes

# Answer
Probably not the answer you are looking for, but if conjunctive query containment is in $\mathsf{NP}$, then there is a nondeterministic Turing machine which solves it. Hence, given an instance $x$ of CQC, you can use the construction in (the proof of) the Cook-Levin theorem to encode the behavior of said NTM on $x$ as a SAT formula (and decide $x$).
> 0 votes

---
Tags: database-theory, datalog
---