# Question
Title: Does the Posix read() system call for FILE* have an internal buffer in the kernel?
Does the answer depend on the number of bytes requested? If it is forced to keep a buffer due to some unknown device/diver, can it optimize and skip the buffer if it's going to be a disk read? I'm looking for any insight beyond "It's implementation dependent".

How I got here:

C++ implementations of POSIX compliant systems can bypass the basic\_streambuf's process local buffers by directly calling the read() system call.

> https://en.cppreference.com/w/cpp/io/basic\_istream/read : When using a non-converting locale (the default locale is non-converting), the overrider of this function in std::basic\_ifstream may be optimized for zero-copy bulk I/O (by means of overriding std::streambuf::xsgetn)

> https://en.cppreference.com/w/cpp/io/basic\_streambuf/sgetn : The rule about "more efficient implementations" permits bulk I/O without intermediate buffering: that's how std::ifstream::read simply passes the pointer to the POSIX read() system call in some implementations of iostreams

But the manual for read() (https://man7.org/linux/man-pages/man2/read.2.html) provides only input/output descriptions and does not say anything about implementation/guarantees provided by the system call. While reasonable for a standard to not be too heavy handed, it still raises the question - how is it actually implemented? And is it even an optimization over not having a buffer in std::basic\_streambuf if the system call has a buffer anyway?

# Answer
> ssize\_t read(int fd, void \*buf, size\_t count);

This asks the OS to copy into `buf`, all available data, but no more than `count` bytes.

For storage devices where seeking isn't practical or possible (e.g. tape drives and punched card readers), it is the caller's responsibility to ensure that the provided buffer is large enough to contain a full physical block from the device. Typically one would provide a buffer that's too large, and consider it an error if the full amount was read (as there might be additional data that was discarded).

Whether the OS, or the filesystem, or the storage device itself decide to use a buffer to read-ahead in order to optimize future requests should be irrelevant as far as the caller is concerned.
> 1 votes

---
Tags: operating-systems, c, c++, os-kernel
---


# Question
Title: Can CYK algorithm be used even if the grammar is ambiguous?
Can CYK algorithm be used for ambiguous context free grammar?

# Answer
> 2 votes
Yes, CYK, and related algorithms such as Earley's and GLR, work for ambiguous grammars. CYK requires converting the grammar into Chomsky Normal Form first; doing so does not affect its ambiguity.

---
Tags: context-free, parsers
---


# Question
Title: Where does the assembler live inside a CPU? If, it indeed does?
Where does the assembler live in the system? I understand that assembly language gets converted to machine code (binary) and that the processor then follows these instructions.

Where does the assembler live? Does it live in some kind of Read Only memory?

# Answer
> 10 votes
A reasonable question when one is unfamiliar with how a computer operates. The answer does depend on what kind of computer one is discussing. Computers range from small systems, like a Raspberry Pi or BBC Micro Bit (or even smaller) up to a large multiprocessor supercomputer.

In a normal typical computer an assembler is just a normal program, like any other application (or App) and it lives in the system in the same places as other Apps. There is nothing special about an assembler. An assembler is just like a compiler. It is a program that translates a sequence of statements described in one language (or notation) to an equivalent sequence in another language (or notation). A Java compiler would convert Java program statements into the equivalent sequence in (Java) Machine Code. An assembler for an ARM processor would convert the assembler statements into ARM machine code.

In a typical computer these programs would reside on the disc.

In something like a smartphone these programs would reside on some other form of persistent storage such as the built-in flash memory or a micro-SD card.

Not all computers need to have the assembler run on them. Very few smartphones would have an assembler App installed (but they could - my phone does have assemblers and compilers installed on its SD card!). For small devices the compilers and assemblers reside on and are run on a large computer and the machine code is generated there. The resulting file of machine code is then downloaded or installed on the computer.

You can thus have machine code without having any assembler on the same computer. The assembly was done somewhere else.

The answer is thus, the assembler could be anywhere!

# Answer
> -1 votes
I think you will get your answer by following some other questions instead of this one.

1- is assembler a system software?

2- is the first assembler written in machine language? (vist here)

3- what happens when we turn on the computer? what is BIOS and how does it work? what is bootloader? etc.

I hope you get your answer.

---
Tags: computer-architecture
---


title: Finding a decider

text:
# Question
Title: Finding a decider
Let $L\in R, L\_2\in RE$ and $n\in N$.
Define $L\_n=${$w|w\in L \vee (w\in L\_2 \wedge |w|\leq )$}
Find a decider for $L\_n$

For the right hand side, I thought I could check the length of and then simulate the recognizer that recognizes $L\_2$ until it accepts. I don't know how many steps it'll take the machine to halt and accept, and it might also never halt.

How do I approach this problem?

# Answer
You do not have to construct the machine, you only have to show one exists. The language $\\{w\in L\_2 \mid |w|\le n\\}$ is finite, even if we do not know any of its elements.
> 0 votes

---
Tags: turing-machines, computability
---


# Question
Title: What is the most efficient way to represent an directed dynamic massive 3D graph?
I know that there are many techniques to represent graphs.

Suppose I have a directed massive 3D graph with 100,000 nodes at maximum.

Suppose the graph looks somewhat like the following:

Suppose each node of the graph has three pieces of information:

1. A 30-character string as a label
2. floating point values as coordinates
3. three integer values

The graph is dynamic. I.e., connections frequently change, and the nodes frequently change their coordinates.

What would be the most efficient way to represent this graph in computer memory so that I can apply mathematical operations on each node?

Should I use data structures, or should I use big-data techniques?

# Answer
50,000 nodes is very small and will fit in memory. Use any standard data structure for representing graphs, e.g., https://en.wikipedia.org/wiki/Adjacency\_list (see also https://en.wikipedia.org/wiki/Adjacency\_matrix).
> 1 votes

---
Tags: graphs, data-structures, simulation
---


# Question
Title: LP Approximation for Vertex Cover Problem
In Cormen's *Introduction to Algorithms*, he states the the LP relaxation for the minimum vertex cover approximation problem is $ \begin{align\*} &\sum\limits\_{v \in V}w(v)x(v) \tag{35.15} \\ x(u) + x(v) &\geq 1 \text{ for each } u, v \in E \tag{35.16} \\ x(v) & \leq 1 \text{ for each } v \in V \tag{35.17} \\ x(v) &\geq 0 \text{ for each } v \in V. \tag{35.18} \end{align\*}$ However, I am wondering why the constraint $x(v) \leq 1$ is even necessary? If it was greater than one, wouldn't the optimal solution still be most optimal? If this isn't the case, could someone please explain why? If it is the case, would you also explain? Thank you.

# Answer
> 1 votes
You could delete this constraint, but it would still be verified in a solution: if there is a solution satisfying all other contraints and $x(v) \> 1$ for a certain $v$, then the same solution with $x(v) = 1$ still satisfy the constraints. Since weights are positive, the sum with $x(v) = 1$ would be lesser than the sum with $x(v) \> 1$.

---
Tags: algorithms, graphs, linear-programming, vertex-cover
---


# Question
Title: Complexity of multiplication when computing product of $m$ integers
I designed an algorithm where, at some point, I need to compute the product of a list of integers $n\_1,\dots,n\_m$ (possibly, there are repetitions in the list). The integers themselves do not depend on $m$ but can be, somehow, arbitrarily large.

EDIT: right now, I'm using a naive for loop:

```
prod=1
for n_i in list:
    prod *= n_i

```

When analyzing this part of the algorithm, I wondered whether I should - or not - consider the multiplication $O(1)$ \- i.e. computing the product would only be $O(m)$.

I still looked at what could happen if I considered non-constant multiplication, and noted $M(n)$ the complexity of multiplying two $n$ bit numbers, the complexity would be something like that:

$$\sum\_{i=1}^m M\left(\sum\_{j=1}^i \log\_2 n\_i\right)$$

Since multiplying two $n$-bits number leads to a $2n$-bits number. With roughs bounds, I can estimate the complexity as $m \cdot M\left( m\cdot \max\_{i=1}^m(\log\_2 n\_i)\right)$ \- as stated in the comment to this question. The bound is tight if I take $m$ copies of the same integer.

I understood that as soon as $n\<k$, with a $k$-bit machine, one can consider $M(n)=O(1)$. Does this mean that as soon as $m\cdot \max\_{i=1}^m(\log\_2 n\_i) \< k$, I can consider the multiplication $O(1)$ ? I surely must have missed something, because it doesn't feel right: with $m=k$ (say, $32$ or $64$), even with $1$-bits integers, I would exceed $k$.

Any help to better understand this problem is welcome; and since this is for academic purpose, I would be happy to receive some literature recommandation.

# Answer
There are two standard ways to compute running time. Both are valid. Each conveys slightly different information, and which one is more useful may depend on the circumstance.

One approach is to compute the running time in terms of the number of bit-operations. For instance, it takes $O(B^2)$ bit operations to multiply two $B$-bit numbers using the classical multiplication algorithm. This is most helpful when computing the size of circuits needed.

A slight variant of this is to compute the running time in terms of the number of word-operations. In other words, we assume that operation can operate on fixed-size (say, 32-bit) words. For instance, you can add or multiply two 32-bit words in a single step. In this model, it takes $O(B^2)$ word operations to multiply two $B$-bit numbers using the classical multiplication algorithm. The constant factor is about $32^2$ lower than if you count the number of bit operations, but this is a constant and hence does not affect the asymptotic analysis. Consequently, if you ignore constant factors, this will often give you the same asymptotic result as counting bit-operations. If you care about real machines and constant factors, this model is probably most appropriate. This model is also sometimes known as the word RAM model.

Closely related is the transdichotomous model, which basically counts the number of word operations, but additionally assumes that the word size is "large enough" to be able to store pointers and indices to the entire input. In particular, if the input length is $L$, then the transdichotomous model lets you assume that the word size is at least $\lg L$. For practical purposes, you can basically ignore this issue and just count the number of word operations. From a pedantic/nitpicky theoretical perspective, the transdichotomous model corrects a problem with the word RAM model, but you probably can safely ignore that.

Finally, there is the RAM model, which assumes that you can do any single operation on two values in a single step. For instance, you can add or multiply two arbitrarily-large integers in a single step. This model is not a good model of reality, because in reality if you have very large integers, there is no way to add or multiply them in a single step. But it has the advantage of being simple, and if all numbers that you operate with are small, then its issues probably don't matter. For your problem, you are dealing with large numbers, so the word RAM is not a good model of real computers.

I hope this answers your question about whether to consider the multiplication as taking $O(1)$ or $M(n)$ time.

TL;DR: no, you can't consider multiply to take $O(1)$ time, as that isn't how things will work in a real computer, if you have to deal with large numbers.
> 1 votes

---
Tags: complexity-theory, time-complexity, integers, multiplication
---


title: Are variables stored again in RAM?

text:
# Question
Title: Are variables stored again in RAM?
Assuming this set of instructions:

1. declare variable 'A' which has value 5
2. declare variable 'B' which has value 2

From what I've understood, those instructions are loaded into RAM an then read by CPU, they are composed by OPCODE + Data. So, lets assume that the opcode to set a value for a specific RAM address is (0001). First instruction is in binary 0001 (opcode) + value (0b101) and the second is 0001 (opcode) + 0b10 (value). Are this values moved in a different memory area where process data will reside?

Hopefully what I asked makes sense, Sorry for the dumb question, I just started to learn CS.

# Answer
> 1 votes
There is no unique answer, that can depend on code optimizations.

If the data that you are considering is constant, it could be used in *immediate* mode, i.e. be inserted in the instruction flow where needed. E.g.

```
Load R0, 5
Load R1, 2
Add R0, R1
...

```

The immediate value would have to be repeated everywhere the variable is used. The variable is never assigned a location in RAM, it just transits through registers.

Another possibility is to have the variable stored in some RAM location, by means of an address. Now it is the address which is used inside the flow of instructions:

```
Load R0, (A)
Load R1, (B)
Add R0, R1
...

```

where (A) could be an explicit memory address such as 0x5F3B0001, and the load is made from this address.

The value contained in the variable can be computed and stored during program execution. If the initial value is known at compile-time, it can also be encoded in the executable file and copied to RAM when the program is loaded.

In some cases, the variables are assigned an address permanently (i.e. throughout program execution). In other cases, for variables with a shorter lifetime, this is done dynamically, for example using a slot in the stack.

# Answer
> 0 votes
Yes and no. Depending on the instruction addressing mode, you may have the data stored in the instruction itself(immediate), no data(implicit), in some register(register), or at a memory location(direct/indirect). There are much more addressing modes available which combine one or more of such addressing modes.

Are these values moved to some different location? If you move the values your program wouldn't be valid anymore(for arguments sake). Yet, it is done by using addressing modes that allow for code relocation. The process data is much more than instructions and data, which is managed by the operating system.

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


# Question
Title: Is the infinite union of decidable languages decidable?
I am currently struggling with figuring out the following problem:

Given decidable languages L1, L2, L3, L4, ...

Is the infinite union of Languages L1, ...... decidable? I have an intution that it is not, but I cannot find an example against that thesis.

Thank you in advance

# Answer
Your intuition is right.

Hint: for any $x$, the language $\\{x\\}$ is decidable. Think how we can use this fact to construct an undecidable language.
> 2 votes

---
Tags: formal-languages, turing-machines, undecidability, decidability, recursively-enumerable
---


# Question
Title: Can an arithmetic circuit have multiple outputs?
An arithmetic circuit relates to calculating the value of a polynomial given some inputs.

But is it still considered a circuit if the DAG corresponds to the evaluation of multiple polynomials that share nodes?

Consider $f(x, y) = 3x^4 * y^3$ and $g(x, y) = 3x^4 * y^2 + x^2$. $f$ and $g$ share the node corresponding to the expression $3\*x^4\*y^2$. Would expressing this relation in a DAG still be considered a circuit?

# Answer
Normally, a circuit has one output: it computes a single function. Therefore, your question does not come up, because we cannot have a circuit that outputs both $f(x,y)$ and $g(x,y)$: that would be two outputs / two functions.

If you had a circuit that outputs a single value, say $h(x,y) = f(x,y) * g(x,y)$, then yes, you could certainly build a DAG with one node for the value $3x^4 * y^2$. This node would would have an edge to the node for $f(x,y)$, and it would also be used in computing $g(x,y)$, so it would also have an edge to the node for $g(x,y)$. That is all legal.

You can of course consider a type of circuit with multiple outputs, even though this is not typical, and then yes, it is fine to have one node for the value $3x^4 * y^2$, which is "shared".
> 1 votes

---
Tags: circuits, polynomials
---


# Question
Title: Why is static recompilation not possible?
I'm researching static recompilation but there doesn't seem to be too much information about the subject. I've heard that dynamic recompilation (emulation) can be up to 6 times slower than native assembly, but I'm curious why we aren't able to translate to a different architecture ahead of time. Even though some instructions wouldn't be 1:1, can't we just shift the rest of the code, and all of the jump instructions with it?

Furthermore, if the problem is a lack of source code, would this mean that Super Mario 64 (which has already been completely reverse engineered, to exactly identical binaries), can be fairly easily recompiled into a different architecture?

# Answer
> 19 votes
Static recompilation from a binary is hard, because it is challenging to reconstruct the structure of the program. It is hard to statically figure out the location of all instructions that will be executed, the starting point of all functions, and the set of all jump targets. This information is needed for natural methods of recompilation: we need to know where all the instructions are, so we can recompile them; we need to know where function prologues and epilogues are, so we can translate them to other function calling conventions; we need to know the set of all jump targets, because all of those locations need to be recompiled. It's not impossible, but it can be extremely challenging to do with 100% fidelity.

Given a binary executable, it is hard to reliably find all of the executable code statically, due to the presence of indirect jumps. In particular, on x86, it is possible to jump into the "middle" of an instruction, which will cause the stream of bytes to be interpreted differently than you might expect. Since we can't predict all possible jump targets of indirect jumps (this is as hard as the halting problem), it is hard to know all locations that might be executed as code, and at what offset. This makes reliable static disassembly hard. And of course, if you can't even disassemble, it's challenging to re-assemble or re-compile.

See, e.g., work on static disassembly to learn about the subject. Here are some sample papers:

1. From Hack to Elaborate Technique—A Survey on Binary Rewriting. Matthias Wenzl, Georg Merzdovnik, Johanna Ullrich, and Edgar Weippl. ACM Computing Surveys (CSUR), 52(3), 1-37
2. An In-Depth Analysis of Disassembly on Full-Scale x86/x64 Binaries. Dennis Andriesse, Xi Chen, Victor van der Veen, Asia Slowinska, Herbert Bos. Usenix Security 2016.
3. SoK: All You Ever Wanted to Know About x86/x64 Binary Disassembly But Were Afraid to Ask. Chengbin Pang, Ruotong Yu, Yaohui Chen, Eric Koskinen, Georgios Portokalidis, Bing Mao, Jun Xu. 2021 IEEE Symposium on Security and Privacy (SP) (pp. 833-851).

See also https://hexterisk.github.io/blog/posts/2020/04/02/disassembly-and-binary-analysis-fundamentals/.

This problem is particularly intractable for obfuscated binaries, but even for normal non-obfuscated binaries, existing methods have difficulty fully recovering 100% of the instructions, function starts, and jump targets with perfect accuracy. This is a problem, because if there is even one mistake, then the entire program might crash.

An additional challenge is that if the program does any kind of runtime code generation or runtime JIT or runtime recompilation, then this only makes the static recompilation problem even harder.

In contrast, runtime (dynamic) methods avoid this problem, because they can observe which instructions and code paths actually get executed and recompile only the ones that are executed, at the time they are executed.

# Answer
> 4 votes
Static recompilation is used, for example it is central in Apple's Rosetta 2 emulator. But there are challenges that make it difficult to apply.

Most importantly, all jump targets are not readily determined from the code. Compilers generate code using methods such as branch tables, virtual method tables and plain old function pointers. All of these take the jump target address from somewhere else than directly from the branch instruction argument. Knowing the compiler helps, but for generic code translation compiler-specific algorithms would involve a lot of work.

If jump targets are not known, the code must be translated so that each source instruction corresponds to a continuous sequence of target instructions. The dynamic target address can then be resolved at runtime. For some instruction sets this is feasible: in Apple's case, ARM64 has more registers than x86-64 and specific extensions to make this possible. For other cases, static recompilation without cross-instruction optimizations would result in very slow code.

And in any case, there are many applications using just-in-time compilation \- including e.g. most JavaScript interpreters. While the JIT compiler could be statically recompiled to a different instruction set, it will still generate code in the original instruction set. Which is why dynamic recompilation is still needed as a fallback.

---
Tags: computer-architecture, assembly
---


title: Intersection of CFL and DCFL

text:
# Question
Title: Intersection of CFL and DCFL
Is **CFL $\cap$ DCFL = CFL**, always true?

CFL - Any Context Free Language

DCFL - Any Deterministic Context Free Language

# Answer
Even the intersection of two deterministic context-free languages may not be context-free.

Consider $L\_1 = \\{a^nb^nc^m\mid n,m\geqslant 0\\}$ and $L\_2 = \\{a^nb^mc^m\mid n,m\geqslant 0\\}$. Both languages are DCFL, but their intersection is $\\{a^nb^nc^n\mid n\geqslant 0\\}$ which is not context-free.
> 2 votes

---
Tags: context-free, pushdown-automata
---


# Question
Title: Algorithm: Optimal selection of subset of nodes in undirected graph to minimize score
Apologies if this question exists somewhere. I'm sure it's been asked, but I don't know how to search for it. This is not a homework question but rather a scientific problem I ran into. If this is a standard CS exercise, just mark it as duplicate and point me where I need to go.

**Problem statement:** Consider an undirected graph with positive integral values on the nodes and negative integral values on the edges. Find the subset of nodes such that the sum of node and edge values is minimized. An edge is only counted if both of its nodes are part of the subset.

In this image, I have two example graphs and their solutions. Red circles indicate that this node is part of the selected subset.

**Notes:**

* Node values may be \>= 0
* In my specific case, the graph is bipartite: nodes are separated into two sets and edges only exist between the sets (I don't think fact is necessary though to create an algorithm)
* The resulting subset does not need to be connected. See the right example.
* It's fine if net-zero nodes are included, also fine if they aren't.

Simple greedy algorithms fail here because if you look at the bottom of the right example. All 3 nodes are required for that subset to become negative. Any two results in a zero/positive score.

# Answer
This problem can be reduced to the maximum flow problem. That is, this problem is as an instance of the closure problem, where we have variables for vertices and edges of the original graph, and has constraints $x\_e \implies x\_u$ and $x\_e \implies v$ for each edge $e = \\{u,v\\}$.

I don't know this particular problem has a specific name. The parametric version of the densest subgraph problem is essentially the same problem.
> 3 votes

# Answer
The problem is solvable in polynomial time.

Let $G = (V, E)$ be any graph with positive weights $w: V \cup E \to \mathbb{N}$ on both edges and vertices. For a subset $S \subseteq V$ let $E(S)$ denote the set of edges in $G$ with both endpoints in $S$.

For such a set $S$, let $$f(S) = \sum\_{e \in E(S)} w(e) - \sum\_{v \in S} w(v).$$ The goal is to find a set $S \subseteq V$ that maximises $f(S)$.

**Definition.** A set function $f: 2^U \to \mathbb{N}$ is *supermodular* if for every $X$ and $Y$, $$f(X) + f(Y) \leq f(X \cup Y) + f(X \cap Y).$$

**Theorem.** Maximizing a supermodular function can be done in polynomial time.

**Claim.** $f$ is supermodular.

**Proof of claim.** There are three cases to consider. When $X$ and $Y$ are disjoint, when one is a subset of the other, and when they overlap. The two former are straightforward to verify, the latter can be shown by writing out the definitions.

1. $X \cap Y = \emptyset$. $f(X) + f(Y) \leq f(X \cup Y) + 0$. In this case, $f(X \cup Y)$ can only be at least as large as the two since we count the vertices exactly once, and potentially add some extra edges (the edges between $X$ and $Y$).
2. $X \subseteq Y$. $f(X \cap Y) = f(X)$, $f(X \cup Y) = f(Y)$, so the sums are equal.
3. $X$ partially overlaps $Y$. Let's expand the definitions.

* $f(X) + f(Y) = \sum\_{e \in E(X)}w(e) + \sum\_{e \in E(Y)}w(e) - \sum\_{v \in X \cup Y}w(v) + \sum\_{v \in X \cap Y}w(v)$
    * $f(X \cup Y) = \sum\_{e \in E(X)}w(e) + \sum\_{e \in E(Y)}w(e) + \sum\_{e \in E(X, Y)}w(e) - \sum\_{v \in X \cup Y}w(v)$
    * $f(X \cap Y) = \sum\_{e \in E(X \cap Y)}w(e) - \sum\_{v \in X \cap Y} w(v)$
    * Let's cancel out. The supermodular objective is true if and only if $\sum\_{e \in E(X)}w(e) + \sum\_{e \in E(Y)} \leq \sum\_{e \in E(X \cup Y)}w(e) + \sum\_{e \in E(X \cap Y)}w(e)$. But this is true because the righthand side can only contain *more* edges than the left-hand side (namely the ones going from $X$ to $Y$).
> 2 votes

# Answer
\[My previous answer contained an incorrect claim about NP-hardness.\]

I don't know whether there is a polynomial-time algorithm.

If you have to solve this in practice, one possible solution would be to use integer linear programming (ILP). Introduce zero-or-one integer variables $x\_v$, where $x\_v$ means that node $v$ is selected to be in the subset. Add zero-or-one integer variables $y\_{u,v}$ (for each edge $(u,v)$) and linear inequalities to model your problem, as follows:

* An edge $(u,v)$ is selected iff both its endpoints are selected: $y\_{u,v} \ge x\_u + x\_v - 1$, $y\_{u,v} \le x\_u$, $y\_{u,v} \le x\_v$.

Then minimize the following objective function

$$\sum\_{v} \text{wt}(v) \\, x\_v + \sum\_{u,v} \text{wt}(u,v) \\, y\_{u,v}.$$

Use an off-the-shelf ILP solver to solve this ILP instance. If your graphs aren't too large, an ILP solver may be able to find the optimal solution. If your graphs are large, then you can terminate search early and hope it finds a good-enough (even if not optimal) solution.
> 1 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: can you write a halting decider that is only wrong about itself by avoiding diagonalization?
in here they claim: "there is an algorithm deciding almost all instances of \[halting problem\]"

so I'm wonder whether there is a computable function $h':\mathbb{N}\to\\{0,1\\}$ such that the following turing machine is a halting decider (for TMs running on blank input) except for itself

$$ \begin{align\*} M(m) &= \begin{cases} \text{loop in state $q\_{accept}$} & \text{if $h'(m)=1$} \\ \text{halt in state $q\_{accept}$} & \text{if $h'(m)=0$} \\ \end{cases} \end{align\*} $$

for me as a programmer $h'$ is very interesting function because it connect arithmetic to turing machines

# Answer
> 3 votes
No, you can't. If you had a procedure $M$ that would correctly solve the Halting problem for all but finitely many instances $p\_0,p\_1,\ldots,p\_k$, then there would exist a computable solution to the Halting problem as follows:

Input $p$

if $p = p\_0$, return $b\_0$

elseif $p = p\_1$, return $b\_1$

...

elseif $p = p\_k$, return $b\_k$

else return M(p)

If the $b\_i$ are correctly chosen, this is solving the Halting problem. (We don't necessarily have a way to figure out the correct choice, but it clearly exists.)

So if we take the usual reading of "almost all" to mean "all but finitely many exceptions", we cannot solve the Halting problem for almost all instances. But that is not what the paper you've linked is claiming. They say that for one natural encoding, we can solve the Halting problem for a set of instances $I$ such that $\frac{|I \cap \\{0,1,\ldots,n-1\\}|}{n}$ tends to $1$ as $n$ goes to infinity.

---
Tags: turing-machines, halting-problem
---


# Question
Title: What is the algorithm where you rotate around a board in a clockwise pattern?
I'm sure this question has been asked before, but I have no clue what I'm trying to achieve is called and couldn't find anything helpful.

I'm trying to find the name of an algorithm that starts at a point and rotates around a "board" in either clockwise or anti-clockwise rotation.

I'll draw some examples to shown what I'm trying to get because I can't really word what I'm after.  The algorithm starts at 1 and moves around in a clockwise rotation moving around the radius from the centre. The algorithm count resets when it goes another layer out. Each number is how many steps of the algorithm it takes to get to this square.

# Answer
> 0 votes
From the starting point $(k,\frac{n-1}2)$, go up $k$ times, right $2k$ times, down $2k$ times and up $k-1$ times.

---
Tags: algorithms
---


# Question
Title: Relationship b/w Circuit and Time Complexity
I am trying to understand Circuit Complexity's relation to classical Time Complexity. Here is what wiki mentions:

"If a certain language, ${\displaystyle A}$, belongs to the time-complexity class ${\displaystyle {\text{TIME}}(t(n))}$ for some function ${\displaystyle t:\mathbb {N} \to \mathbb {N} }$, then ${\displaystyle A}$ has circuit complexity ${\displaystyle {\mathcal {O}}(t(n)\log t(n))}$."

I find it quiet unclear. Here is my doubt:

Let $t(n)$ be a function that represents the exact (worst case) runtime of an optimal algorithm for some language $A$ on a Turing Machine ($n$ being the input size). What is the circuit size upper bound we expect for this program?

The big O notation simply says ${\displaystyle {\mathcal {O}}(t(n)\log t(n))}$ but this doesn't explain anything about the upper bound on the size of the circuit for an $n$ bit input. In bit O notation we have simply don't care about the actual value of the constants so this doesn't seem to be helpful. Can someone please explain?

**Query:** Given the description of the Turing Machine (lets call it $M$ and that can be simulated on a UTM) that decides the language $A$, how can we calculate the actual circuit size upper bound for a $n$ bit input to $M$ and not just the 'rate of growth' as described above?

# Answer
Circuit complexity refers to a family of circuits used to solve different inputs of the same problem. For a problem $A$, it is defined as a function $c : \mathbb{N}\to\mathbb{N}$ such that for any integer $n$, there exists a circuit of size $\leqslant c(n)$ that decides all instances of $A$ of length $n$.

Given a function $t$ such that $A\in \mathsf{TIME}(t(n))$, what "circuit complexity $\mathcal{O}(t(n)\log t(n))$" means is that there exists a constant $\alpha \> 0$ such that $A$ has circuit complexity $\alpha t(n) \log t(n)$.

Now sure you could get an upper bound with a very big constant $\alpha$ here, but what is important here is that $\alpha$ does not depend on the size of the inputs you are trying to decide. That means that even if $\alpha = 10^{100}$, there exists a circuit of size $\leqslant 10^{100}t(10^{10000})\log(t(10^{10000}))$ that decides inputs of length $10^{10000}$.

That is why the big-Oh notation here isn't a problem to link time complexity and circuit complexity.
> 1 votes

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


# Question
Title: Regex: Any pair of zeros is before any pair of ones
Write a regular expression for all the strings in which every pair of adjacent zeros appears before any pair of adjacent ones. The answer given in the book is: $$(0+10)^\*(00)(1+01)^\*(11)(0+10)^\*(1+01)^\*$$ Is that correct? I fail to see how could you get a string like **10011**, but it fits description. I mean even a string like **1** fits a description. So, if this answer is incorrect, then what is a correct answer? My simple guess is: $$(\epsilon+1)(0+10)^\*(1+01)^\*(\epsilon+0)$$

P.S. Does $(0^\*1^\*)^\*$ generate every possible binary number? If not, what does it generate?

# Answer
You are correct: the regexp you quote does not match the string $10011$ and that string has the property that every pair of adjacent $0$s occurs before any pair of adjacent $1$s. But it does match the string $001100$, which fails to have the property!

Your proposed solution matches $11001$ so is also incorrect (the first bracket matches $1$, the second matches $10$, the third matches $01$ and the fourth matches $\epsilon$.

A regexp that does match the required language is $$0^\*(100^\*)^\*(11^\*0)^\*1^\*\\,.$$ It works as follows.

* $0^\*(100^\*)^\*$ matches the empty string and any non-empty string that doesn't contain $11$ and that ends with $0$. The string can't contain $11$ because there must be at least one $0$ between every two $1$s.
* $(11^\*0)^\*1^\*$ matches every string that begins with $1$ and does not contain $00$, since there must be at least one $1$ between any two $0$s.
* Now put the two halves together. If a string has the property that all occurrences of $00$ are before the first $11$, then the section of the string before the first $11$ must either be empty or end in $0$, so it matches the first part of the regexp. The rest of the string contains no occurrences of $00$ so it matches the second part of the regexp.

Note that there are shorter regexps that do the same thing: Yuval Filmus gives $(0+10)^\*(1+10)^\*$ in a comment to the question. That's a tidier version of the same idea.

And, yes, $(0^\*1^\*)^\* \equiv (0+1)^\*$ matches every possible binary string.
> 1 votes

# Answer
(0011)\* ((^ + 0)(1+101+10011)(1+01+0011))\*(^+0) Regex: {0,1} :Every pair of adjacent zeros appears before any pair of adjacent ones('^'-\>null).
> 0 votes

---
Tags: regular-expressions
---


# Question
Title: Reduction from SUBSET SUM to COIN CHANGING
The `COIN-CHANGING` problem is NP-complete, but I am having difficulty finding a proof for its NP-hardness in the form of a reduction from another NP-complete problem to `COIN-CHANGING`. Apparently, a reduction from `SUBSET-SUM` to `COIN-CHANGING` is possible according to this (hopefully old enough) algorithms assignment from Princeton.

Could someone please give a proof of this reducibility?

# Answer
I will use the same notation as the assignment you linked:

> $\texttt{SUBSET-SUM}$:
>
> * Input: $n$ positive integers $w\_1, …, w\_n$ and an integer target $W$.
> * Question: is there a set $I \subseteq \\{1, …, n\\}$ such that $\sum\limits\_{i\in I}w\_i = W$?

> $\texttt{COIN-CHANGING}$:
>
> * Input: $m$ positive integers $1 = c\_0 \< c\_1 \< … \< c\_{m-1}$, an integer target $S$ and a maximum number of coins $T$.
> * Question: is there a **multiset** $I$ such that $\sum\limits\_{i\in I}c\_i = S$ and $|I| \leqslant T$?

Following the indications of the assignment, here is my reduction. Given an input of $\texttt{SUBSET-SUM}$, let $b = \max(n+1, W+1)$. Define $c\_0 = 1$, and for $i\in\\{1, …, n\\}$, define: $$c\_i = w\_i \times b^{n+1} + b^i$$ $$c\_i' = b^i$$ Define also: $$S = W\times b^{n+1} + \sum\limits\_{i=1}^nb^i$$ Finaly, define $T = n$.

Then $((w\_1, …, w\_n), W)$ is a positive instance of $\texttt{SUBSET-SUM}$ if and only if $((c\_0, …, c\_n, c'\_1, …, c'\_n), S, T)$ is a positive instance of $\texttt{COIN-CHANGING}$.

The idea (detailled proof left to you) is that by selecting at most $n$ coins, no carry can exist in the last $n+1$ digits in base $b$. Since the $i$-th (from right to left, $i\in \\{1, …, n\\}$) digit of $S$ is $1$, you are allowed to use at most one of each coin. Since the last digit is $0$, you are not allowed to use the coin $c\_0$. The coin $c'\_i$ is to be picked if the coin $c\_i$ is not picked, to insure that the $i$-th digit of the sum is indeed $1$.

This construction is indeed in polynomial time, because each $c\_i$, $c\_i'$ and $S$ can be written using at most $(n+2)\log\_2 b$ bits.
> 1 votes

# Answer
I think that a reduction from exact cover by 3-sets (X3C) is easier: given a set of $X = \\{x\_1, \dots, x\_{3n}\\}$ of elements and a collection $S = \\{S\_1, \dots, S\_n\\}$ of subsets of $X$ each containing 3 elements, is there a subset $S'$ of $S$ such that each element in $X$ is contained in exactly one set in $S'$?

The reduction is as follows. The amount of change $C$ and each of the coins will be a binary number with $3n + 2\ell$ bits, where $\ell = \lceil \log\_2 (1+n) \rceil$. These bits are logically split into a higher part consisting of the $\ell$ most significant bits, a padding part consisting of the next $\ell$ most significant bits, and a lower part consisting of the $3n$ least significant bits. The padding bits will always be set to $0$.

Create one coin $c\_i$ for each set $S\_i$ by setting the $j$-th least significant bit of the lower part to $1$ if and only if $S\_i$ contains $x\_j$, and setting the least significant bit of the higher part to $1$ and the other bits to $0$.

Pick $C$ by setting all the $3n$ least significant bits to $1$ and the $\ell$ most significant bits to the binary encoding of $n$.

You can give change using at most $n$ coins if an only if the X3C instance is a yes instance.

Given an exact cover $S'$, you can simply select the $n$ coins corresponding to the sets in $S'$.

Consider now a change-giving strategy that uses at most $n$ cons and notice that it must use exactly $n$ coins since at least $n$ coins are needed to properly set the higher part. Since each of these $n$ coins has exactly $3$ bits set in the lower part, which consists of $3n$ bits, the sets corresponding to the selected coins form an exact cover. To see this imagine adding the values of the selected coins one by one in an arbitrary order. If any two (not necessarily distinct) coins shared the same bit set to $1$ in the lower part, adding the second coin would not set $3$ additional bits to $1$ in the lower part contradicting the fact that $n$ coins were used.
> 0 votes

---
Tags: algorithms, complexity-theory, np-complete, reductions, np-hard
---


title: Proving this recurrence is $n \log n$

text:
# Question
Title: Proving this recurrence is $n \log n$
I need to prove that $T(n)$ is $\mathcal O(n\log n)$ with the substitution method. $$ T(n)\leq 3\log n + n + \frac{6}{n}\sum^{2n/3}\_{n/3}T(i).$$

This is my attempt: I assume $T(n) \leq c n \log n$ and then \begin{align\*} T(n) &\leq 3 \log n + n + \frac{6c}{n}\int^{2n/3}\_{n/3}x\log x dx\\ &\leq3 \log n + n + \frac{6c}{n} \left\[ \frac{1}{2}x^2 \log x - \frac{x^2}{4}\right\]\bigg|^{2n/3}\_{n/3}\\ &\leq3\log n +n + \frac{6c}{n}\left( \frac{2n^2}{9}\log (\frac{2n}{3}) - \frac{n^2}{18}\log(\frac{n}{3}) -\frac{n^2}{12}\right). \end{align\*} I'm stuck at that point, what else can I do?

# Answer
Just continue from there:

$$\begin{align\*} & \leqslant 3\log n + n + \frac{6c}n\left(\frac{2n^2}9\log\left(\frac{2n}3\right)-\frac{n^2}{18}\log\left(\frac{n}3\right)-\frac{n^2}{12}\right)\\ & = 3\log n + n + \frac{6c}n\left(\frac{2n^2}9\log n - \frac{n^2}{18}\log n + \frac{2n^2}9\log 2 - \frac{2n^2}9\log3 + \frac{n^2}{18}\log 3 -\frac{n^2}{12}\right)\\ & = 3\log n + n + \frac{6c}n\left(\frac{n^2}6\log n + \frac{2n^2}9\log 2 - \frac{n^2}{6}\log 3 -\frac{n^2}{12}\right)\\ & = cn\log n + 3\log n + n\left(1 + c\frac{4}3\log 2- c\log 3 - \frac{c}2\right)\\ & \leqslant cn\log n \end{align\*}$$ The last inequality holds for $n$ and $c$ big enough, since $\frac43\log 2 - \log 3 - \frac12\<0$
> 1 votes

---
Tags: asymptotics, big-o-notation, upper-bound
---


# Question
Title: Asymptotic Relationship between $\frac{1}{n}$ and $\frac{1}{2^n}$
What is the asymptotic relationship between $\frac{1}{n}$ and $\frac{1}{2^n}$?

The answer here mentions that both functions are $O(1)$ (because they are always $\leq 1$) but not $\Omega(1)$ (because the functions will not be always greater than any constant $c\>0$, as both are eventually 0).

Thinking of it using limits: $\lim\limits\_{n \to \infty}\frac{\tfrac{1}{n}}{\tfrac{1}{2^n}}=\infty$, which implies that $\frac{1}{2^n}=o(\frac{1}{n})$. However, both functions are decreasing (not increasing) and both eventually meet at zero. I.e. no function will always be greater than the other. So I can't wrap my head around it!

I assume this question applies in general to other decreasing functions as well (e.g. $\frac{1}{n}$ and $\frac{1}{n^2}$).

# Answer
You are right in concluding it is $O(1)$ and not $\Omega(1)$ (talking purely about functions). However saying its $O(1)$ because they are always $\leq 1$ is slightly incorrect as it can be seen from the graph below. Since these functions are in the denominator they would approach $0$ very fast. In asymptotic analysis, $n \to \infty $ means ***for sufficiently large value of*** $n$, and it can be seen from the graph that even a small value$(n=1)$ is enough to show the asymptotic relationships between the functions.

The graph of $\frac{1}{n}$(green curve) approaches zero slower than that for $\frac{1}{2^n}$ (violet/purple curve). Clearly, $\frac{1}{2^n}$ is upper bounded by $\frac{1}{n}$ i.e. $\frac{1}{2^n} = O(\frac{1}{n})$ and as you yourself have mentioned in the question $\frac{1}{2^n}=o(\frac{1}{n})$.

Even by using the standard definition of Big-O

for $$\frac{1}{2^n} = O(\frac{1}{n})$$ we need to show

$$\frac{1}{2^n}\leq c\cdot \frac{1}{n}$$ for some positive constant $c$. Putting $c=1$ the equation holds true for all values of $n\>0$. Similarly you can figure out the asymptotic relationships for other decreasing functions as well.
> 1 votes

# Answer
Just like $n=O(2^n)$ (the exponential grows much much faster), $\dfrac1n=\Omega\left(\dfrac1{2^n}\right)$.
> 0 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Why does python's threading library use OS level threads when it can't achieve parallelism?
I was surprised to hear that the threading module from python uses OS level threads. From what I know, OS level threads are more expensive (but can achieve parallelism) meanwhile green threads are user-level, more lightweight, but can only achieve concurrency but not parallelism. Why doesn't the python virtual machine implement a scheduler for user-level threads and replace the threading module OS threads?

If the GIL restricts the number of threads running at once then there is effectively no benefit (other than simplicity of implementation on python's side) to having OS level threads over user level threads, right?

# Answer
> 2 votes
Green threads are ancient stuff and the references you are reading are probably citing reasons that mostly don't apply today. It is more complex than you write, with software engineering and performance tradeoffs that are hard to summarize in just a few sentences, but here is a rough overview:

OS level threads allow taking advantage of multiple cores or multiple processors, which are common today.

Green threads incur an overhead to keep track of the thread states and swap between them. If you only have a limited number of threads, the OS is just as good at that or better.

Green threads handle blocking system calls poorly.

Green threads only have the *potential* to be better if the number of active threads is significantly more than the number of cores/processors. That is not the case for most applications today; for most applications, the number of threads is fewer than the number of cores. Even if it true, there is no guarantee that green threads will be faster; that depends on other factors.

# Answer
> 0 votes
It's not necessarily true that green threads cannot achieve parallelism. Just check out the runtimes for Go, Elixir, and Clojure - they're doing just fine.

While the actual reason as to why Python didn't go for this route is unclear, if I had to guess: it's probably because green threads don't play nice with C.

Python has a closer relation to C than most languages that have their reference implementations written in C. You'll find that many Python primitives map directly to the underlying C implementation. Interfacing with C code from Python already has many costs, having green threads just means appending the extra cost of context switches to that list. So, it should make sense that Python uses OS threads, because C does the same.

Python has many target audiences. While web developers might benefit from getting the same experience in Python as they get in a language like Go, something like this might've broken the scientific community's heart in other, unexpected ways.

That said, the future looks promising in 2022: CPython is getting rid of the GIL, and Python has a better WASM story than most people expected. I'm not sure where my stance will be in the future, but for now, I'd probably use a better language for the job.

---
Tags: operating-systems, python, threads
---


# Question
Title: Interactive ZKP of possession of a signed message
Suppose Alice has a verifiable (message, signature) pair from Cedric, who would not cooperate and routinely uses an algo (ecdsa, eddsa, rsa, or insert yours here) to sign messages.

Alice wants to interactively prove to Bob she has that (message, signature) pair with the valid signature, obviously. It doesn't have to be "zero-knowledge" - she might divulge bits and pieces, but it shouldn't be less hard for Bob to recover complete (message, signature) pair than for Alice to forge the signature altogether.

Obviously, Alice and Bob both have Cedric's public key. I look for an interactive procedure and stochastic proof. Is it even achievable at present point?

# Answer
This is a NP statement, so there is a zero-knowledge proof for it (as there is a zero-knowledge proof for every NP statement). The exact form of the proof will depend on which signature algorithm is chosen, and what is already known to Bob (e.g., does Bob know the message? can it be disclosed to him safely?).

---

If you can choose the signature algorithm, and you can assume Bob knows the message or are willing to disclose the message to Bob, then you can find signature algorithms that allow very efficient and simple zero-knowledge proofs. For instance, you can use RSA with full-domain hashing, and the following ZKP: https://crypto.stackexchange.com/q/16015/351
> 1 votes

---
Tags: cryptography, security, zero-knowledge-proofs
---


title: Best Data Structure For Text Processing

text:
# Question
Title: Best Data Structure For Text Processing
Given a sentence like this, and i have the data structure (dictionary of lists):

`{'cat': ['feline', 'kitten']}`

A feline was recently spotted in the neighborhood protecting her little kitten

How would I efficiently process these set of text to convert the word synonyms of the word cat to the word CAT such that the output is like this:

A cat was recently spotted in the neighborhood protecting her little cat

I would also like to inquire whether my data structure is relevant and efficient for this task

# Answer
You can't. At least not always. That's not a well-defined mapping. The notion of synonyms is subjective and a word might have many synonyms it can be mapped into. Even humans can't do that task (they won't always agree what the sentence should be mapped to), so it's not reasonable to expect computers to do it, either.

Perhaps you want to compare two sentences to determine whether they are saying the same thing. In full generality, that is probably AI-complete (i.e., beyond our state of knowledge right now). You can probably get a pretty good approximation by using existing pre-trained encoders that map text (such as a sentence) to an embedding, followed by some distance measure or similarity measure on those embeddings.
> 1 votes

# Answer
Your data structure is quite inappropriate to turn the first sentence into the second. Because you would have to look-up the entire dictionary in search of "feline".

And if, hoping to fix, you would like to replace cat (rather than feline) by a synonym, you don't really know which to choose.
> 0 votes

# Answer
You can do the other way around; use a HashTable to map the synonyms to the main word:

```
feline -> cat
kitten -> cat

```

Now, you can do the lookup in $O(1)$ time, although this may have some spatial overhead.
> 0 votes

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


# Question
Title: Using the pumping lemma, show that L = {a b^n c^n | n ≥ 0} is not regular
I've encountered many examples which its format is like: a^n b^n. For this I understand that w = 2n and is pretty straightforward, but what happens in my case? Is w = 1 + 2n? And in this case would |xy| be a subword of just a, or a subword of a b^n?

I'm struggling to pump the language in any meaningful way to get my proof going, any help is appreciated. Thanks.

# Answer
Suppose that $L$ is regular and let $p$ be its pumping length. Consider $w = a b^p c^p \in L$. From the pumping lemma you know that $w$ can be written as $w=xyz$ with $|xy| \le p$ and $|y| \ge1$ such that $xy^ip \in L$ for all $i \ge 0$.

Notice that $y$ must contain the initial $a$ or at least one $b$ (possibly both) and cannot contain any $c$. Then $xz = xy^0z \not\in L$ since it either contains no $a$s or it contains less than $p$ $b$s and $p$ $c$s. This provides the sought contradiction.
> 0 votes

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


# Question
Title: Proof that propositional resolution is refutation complete
I am studying theoretical computer science and I am in the part about resolution in propositional calculus. I was reading a theorem (and its proof) that propositional resolution is refutation complete, but I could not fill a particular detail.

The theorem is:

> **Refutational Completeness of Propositional Resolution**. The resolution method in propositional calculus is refutation complete, i.e., a set of propositional clauses $S$ is unsatisfiable **if and only if** the empty clause can be deduced from $S$ by application of the cut rule and the simplification rule.

The sketch of the proof given is:

> **Proof Sketch**.
>
> **($\Leftarrow$)**. By correction we have that if $\square$ is deduced from $S$ then $S$ is unsatisfiable.
>
> **($\Rightarrow$)**. First you need to show that if $S$ is inconsistent and the set of propositional symbols that occur in the clauses of $S$ are $\\{p\_1, \ldots, p\_n \\}$, then it is possible to obtain from $S$ by resolution a set of clauses $S'$ such that only the propositional symbols $\\{p\_1, \ldots, p\_{n-1} \\}$ occur in $S'$. The proof will then follow by induction on the number of propositional symbols that occur in $S$. Details are left as exercise.

The cut rule and the simplification rule were defined previously as:

> **Cut Rule**. Let $p \lor l\_1 \lor \ldots \lor l\_n$ and $\lnot p \lor l'\_1 \lor \ldots \lor l'\_m$ be two propositional clauses. Then the clause $l\_1 \lor \ldots \lor l\_n \lor l'\_1 \lor \ldots l'\_m$ is inferred from the two previous ones by the **cut rule**.
>
> **Simplification Rule**. Let $p \lor p \lor l\_1 \lor \ldots \lor l\_n$ be a propositional clause. Then, the clause $p \lor l\_1 \lor \ldots \lor l\_n$ is inferred from the one before by the **simplification rule**. Equally, $\lnot p \lor l\_1 \lor \ldots \lor l\_n$ is inferred from $\lnot p \lor \lnot p \lor l\_1 \lor \ldots \lor l\_n$ by the simplification rule.

To obtain the set $S'$ from $S$ my idea was to first notice that since $S$ is unsatisfiable, there is at least one propositional symbol $p\_i$ such that both $p\_i$ and $\lnot p\_i$ appear in clauses of $S$. Without loss of generality, we can assume $p\_i = p\_n$. Then, let $p\_n \lor l\_1 \lor \ldots \lor l\_n$ and $\lnot p\_n \lor l'\_1 \lor \ldots \lor l'\_m$ be two clauses of $S$ and notice that we can apply the cut rule to obtain only $l\_1 \lor \ldots l\_n \lor l'\_1 \lor \ldots l'\_m$. We can proceed in this way as many times as necessary and obtain a set $S'$ such that only the propositional symbols $\\{p\_1, \ldots, p\_{n-1}\\}$ appear in $S'$.

However, I could not prove that the set $S'$ obtained this way is inconsistent. For instance, if $S = \\{p\_1 \lor p\_2, p\_1 \lor \lnot p\_2 \\}$, then $S' = \\{p\_1\\}$ and I don't see how I can derive $\square$.

What am I missing? How can I fill the details in this proof? Thanks in advance!

# Answer
There is an error in the example: $S = \\{p\_1 \lor p\_2, p\_1 \lor \lnot p\_2 \\}$ is actually satisfiable. Every interpretation $I$ that sends $p\_1$ to $true$ actually works.

With this in mind, notice that if $S$ is unsatisfiable, then for every proposition symbol $p\_i$ we may have both $p\_i$ and $\lnot p\_i$ occurring in $S$ or only one of them. Construct the unsatisfiable subset $S\_n$ of $S$ that omits the propositional symbols $p\_i$ such that only one of $p\_i$ or $\lnot p\_i$ occur in $S$. For instance, if $S = \\{p\_1 \lor p\_2, p\_1 \lor \lnot p\_2, \lnot p\_1, p\_3 \lor p\_1 \\}$, then $S\_n = \\{p\_1 \lor p\_2, p\_1 \lor \lnot p\_2, \lnot p\_1\\}$.

We can then proceed as you described, using the cut rule to combine every pair $p \lor l\_1 \lor \ldots \lor l\_n$ and $\lnot p \lor l'\_1 \lor \ldots \lor l'\_m$ and replace them by $l\_1 \lor \ldots \lor l\_n \lor l'\_1 \lor \ldots \lor l'\_m$. After that we need to apply the simplification rule to the new rules. We can then form the set $S\_{n-1}$ that only contains the propositional symbols $\\{p\_1, \ldots, p\_{n-1} \\}$ and also satisfies the **property** that we have both $p\_i$ and $\lnot p\_i$ occuring in the clauses of $S\_{n-1}$, for every $1 \leq i \leq n-1$. This **property** will allow us to continue this process of eliminating one propositional symbol at a time until we obtain the empty clause $\square$.
> 1 votes

---
Tags: logic, propositional-logic
---


# Question
Title: In NP-hardness, can any category reduce to itself? How can you intuitively explain which categories reduce to the others?
I'm trying to understand how problems in NP-hardness reduce to one another. As I understand it now, if X reduces to Y, Y is *at least* as hard as X.

What I think that means, and would like confirmed or denied, is the following:

1. Any category can reduce to itself. Ex: P can reduce to P. NP can reduce to NP, NP-Complete can reduce to NP complete, NP-Hard can reduce to NP-hard, etc.
2. Any category can reduce to a greater category. Ex: P can reduce to anything greater than P. NP can reduce to anything greater than NP, etc.

Feel free to brutally rip apart my caveman logic. Enlighten me.

# Answer
While your idea is correct for certain reductions and is a good first intuition, it is quite vague and could be clarified:

1. it depends on the type of reduction: for example, it is unknown if there is a polytime **many-one** (or Karp) reduction from a $\mathsf{NP}$-complete problem to a $\text{co}\mathsf{NP}$-complete problem, but it is known that there is always a polytime **Turing** (or Cook) reduction.
2. it depends on the complexity of the reduction: it is unknown if there is a **logspace** many-one reduction from a $\mathsf{P}$ problem to a $\mathsf{L}$-complete problem, but it is known that there is always a **polytime** many-one reduction.
3. it depends on the complexity class: for example, there is no real notion of completeness for the class $\mathsf{BPP}$, but there exist $\mathsf{PP}$-complete problems (for example $\texttt{MAJSAT}$).
4. you say "NP-Hard can reduce to NP-hard", but this is wrong in the general case: $\mathsf{NP}$-hard problems do not have the same difficulty. For example, $\texttt{SAT}$ is $\mathsf{NP}$-hard, and so is $\texttt{SUCCINCT HAM PATH}$. But since the last is $\mathsf{NEXP}$-complete, there is no polytime many-one reduction from it to $\texttt{SAT}$ which is $\mathsf{NP}$-complete.
5. you say "Any category can reduce to itself." but this wrong for some particular cases: the empty language and the universal language are languages that are in most complexity classes ($\mathsf{P}$ and $\mathsf{NP}$ in particular), but there is no reduction from any other problem to those. Note that the previous counter-example also apply: even if two problems are in the same complexity class, they can have a different difficulty (both problems are in $\mathsf{NEXP}$).

The only "natural" reductions that you can count on are (given $\mathcal{C}$ a complexity class) : from $\mathcal{C}$ or $\mathcal{C}$-complete to $\mathcal{C}$-complete or $\mathcal{C}$-hard (given that the hardness is defined using the same reduction you are considering).
> 2 votes

---
Tags: np-complete, np-hard, np, p-vs-np
---


# Question
Title: How CPU know which process generated an interrupt?
When a computer OS supports multi-program, it needs to have a scheduling algorithm to handle which process will be run by the cpu.

If a process is in state 'blocked' waiting for IO, the scheduling causes another process to be taken by the cpu while the process in state 'blocked' is waiting for a response I/O. In this situation, when the process returns to state 'ready' and then runs, how does the cpu know which process to run and where it was stopped ?

# Answer
> 3 votes
The scheduling algorithm is largely irrelevant. What is relevant is how the Operating System kernel saves information about requests it has made for which it is awaiting replies.

When we say that a process is in state "blocked" we don't really mean that there is a variable somewhere called `state` to which we have assigned the value `running` or `blocked` or `waiting`. Rather we have a bunch of different *lists* or *queues* in the system and we move the process from one queue to another queue to change the state. (Or more technically, we move a pointer to the data structure that represents the information about the process.) The information we record about a process includes all the information we need to resume running the process (the program counter to the last instruction it executed, plus the values of all its registers, plus pointers to its page table.)

There is one queue for all the processes that are `ready-to-run`. When the scheduler (whatever kind of scheduler it is) decides that it is time for a different program to run it moves the pointer to the currently running process on to the `ready-to-run` queue and then pulls some other process off the `ready-to-run` queue, and resumes that process (restore all its registers and then jump to the next instruction in the process.)

If a process makes an i/o request then it gets placed in a queue specific to that i/o device. (So there will be one queue for the keyboard, another for the mouse, another for the disk-drive and yet another for the wireless network.) When the process make the i/o request it gets moved to the correct queue for the kind of i/o it requested, the the operating system selects a different process from the `ready-to-run` queue.

When an i/o device sends the response to a request (for example, you press a key on the keyboard, which causes an interrupt, which causes the processor to jump to the keyboard interrupt handling routine) the resulting data will be put in an appropriate buffer and then the process that was `blocked` waiting for that data will be moved off of the keyboard queue and back on to the `ready-to-run` queue. The os will then return from the interrupt (to the process that was running at the time the interrupt occurred) and then some time later it will decide to schedule in another process (which might or might not be the process that just got the data from the keyboard.)

# Answer
> 2 votes
First of all, different environments need different scheduling algorithms.

This is mainly because different operating systems have different objectives according the needs. Then, what the scheduler is going to optimize will not be the same for every case.

There are Real time systems, batch processing, interactive systems, etc. Let's consider interactive systems because these are the typical desktop computers and servers, offering services for various users. The main concerns for the scheduler is to "quickly" answer users querys.

In general, the scheduler tells the CPU wich process is next (the CPU is driven by the scheduler), and the details depends on the sheduler algorithm.

Consider the following simple and old scheduling algorithm, called *Round-robin*:

Each process is assigned with a pre-fixed quantum of time. There is a list of process. The CPU run process A, when the time is over (or A is blocked before time) it switch's to the next process B in the list. A is moved to the end of the list. The context of A is saved in the Process Control Block, so in the next turn for A the CPU knows where to continue because the IP register was saved in that context. In this case, is like all processes have the same priority. One key thing here is how much time is assigned to the quantum, it must be a reasonabe amount of time.

There are more complex algorithms, based in *priority scheduling*. In general, there are different classes of hierarchys, and each hierarchy may have his own queue of processes waiting to run. The CPU can start running process of the highest priority class, and when that class is empty it move downwards the hierarchy. The time of execution in this case can be a quantum, or the CPU can decrease priority of the current process in each clock interruption to avoid indefinite postponement of the other processes.

# Answer
> 0 votes
Every running process runs on a core. When a process causes an interrupt, there is actually an interrupt on that core, and not on any other core. The operating system will detect which core had an interrupt. And the operating system will know which process is running on which core at any time, so it knows which process. The process can be running threads and will know which thread was running, but that is very often not relevant.

---
Tags: operating-systems
---


# Question
Title: Why is the object destructor paradigm in garbage collected languages pervasively absent?
Looking for insight into decisions around garbage collected language design. Perhaps a language expert could enlighten me? I come from a C++ background, so this area is baffling to me.

It seems nearly all modern garbage collected languages with OOPy object support like Ruby, Javascript/ES6/ES7, Actionscript, Lua, etc. completely omit the destructor/finalize paradigm. Python seems to be the only one with its `class __del__()` method. Why is this? Are there functional/theoretical limitations within languages with automatic garbage collection which prevent effective implementations of a destructor/finalize method on objects?

I find it extremely lacking that these languages consider memory as the ***only*** resource worth managing. What about sockets, file handles, application states? Without the ability to implement custom logic to clean up non-memory resources and states on object finalization, I'm required to litter my application with custom `myObject.destroy()` style calls, placing the cleanup logic outside my "class", breaking attempted encapsulation, and relegating my application to resource leaks due to human error rather than automatically being handled by the gc.

What are the language design decisions which lead to these languages not having any way to execute custom logic on object disposal? I have to imagine there is a good reason. I'd like to better understand the technical and theoretical decisions that resulted in these languages not having support for object destruction/finalization.

**Update:**

Perhaps a better way to phrase my question:

Why would a language have the built-in concept of object instances with class or class-like structures along with custom instantiation (constructors), yet completely omit the destruction/finalize functionality? Languages which offer automatic garbage collection seem to be prime candidates to support object destruction/finalization as they know with 100% certainty when an object is no longer in use. Yet most of those languages do not support it.

I don't think it's a case where the destructor may never get called, as that would be a core memory leak, which gcs are designed to avoid. I could see a possible argument being that the destructor/finalizer may not get called until some indeterminate time in the future, but that didn't stop Java or Python from supporting the functionality.

What are the core language design reasons to not support any form of object finalization?

# Answer
> 10 votes
The pattern you're talking about, where objects know how to clean their resources up, falls into three relevant categories. Let's not conflate *destructors* with *finalizers* \- only one is related to garbage collection:

* The finalizer pattern: cleanup method declared automatically, defined by programmer, called automatically.

Finalizers are called automatically before deallocation by a garbage collector. The term applies if the garbage collection algorithm employed can determine object life cycles.
* The destructor pattern: cleanup method declared automatically, defined by programmer, called automatically only sometimes.

Destructors can be called automatically for stack-allocated objects (because object lifetime is deterministic), but must be explicitly called on all possible execution paths for heap-allocated objects (because object lifetime is nondeterministic).
* The disposer pattern: cleanup method declared, defined, and called by programmer.

Programmers make a disposal method and call it themselves - this is where your custom `myObject.destroy()` method falls. If disposal is absolutely required, then disposers must be called on all possible execution paths.

**Finalizers are the droids you're looking for.**

The finalizer pattern (the pattern your question is asking about) is the mechanism for associating objects with system resources (sockets, file descriptors, etc.) for mutual reclamation by a garbage collector. But, finalizers are fundamentally at the mercy of the garbage collection algorithm in use.

Consider this assumption of yours:

> Languages which offer automatic garbage collection ... know with 100% certainty when an object is no longer in use.

Technically false (thank you, @babou). Garbage collection is fundamentally about memory, not objects. If or when a collection algorithm realizes an object's memory is no longer in use depends on the algorithm and (possibly) how your objects refer to each other. Let's talk about two types of runtime garbage collectors. There are lots of ways to alter and augment these to basic techniques:

1. *Tracing GC.* These trace memory, not objects. Unless augmented to do so, they don't maintain back references to objects from memory. Unless augmented, these GCs won't know when an object can be finalized, even if they know when its memory is unreachable. Hence, finalizer calls aren't guaranteed.
2. *Reference Counting GC*. These use objects to track memory. They model object reachability with a directed graph of references. If there is a cycle in your object reference graph, then all objects in the cycle will never have their finalizer called (until program termination, obviously). Again, finalizer calls are not guaranteed.

# TLDR

Garbage collection is difficult and diverse. A finalizer call cannot be guaranteed before program termination.

# Answer
> 5 votes
## In a nutshell

Finalization is not a simple matter to be handled by garbage collectors. It is easy to use with reference counting GC, but this family of GC is often incomplete, requiring memory leaks to be compensated for by explicit triggering of destruction and finalization of some objects and structures. Tracing garbage collectors are much more effective, but they make it much harder to identify object to be finalized and destroyed, as opposed to just identifying the unused memory, thus requiring more complex management, with a cost in time and space, and in complexity of the implementation.

## Introduction

I assume that what you are asking is why garbage collected languages do not automatically handle destruction/finalization within the garbage collection process, as indicated by the remark:

> I find it extremely lacking that these languages consider memory as the only resource worth managing. What about sockets, file handles, application states?

I disagree with the accepted answer given by kdbanman. While the facts stated there are mostly correct, though strongly biased towards reference counting, I do not believe they properly explain the situation complained about in the question.

I do not believe that the terminology developed in that answer is much of an issue, and it is more likely to confuse things. Indeed, as presented, the terminology is mostly determined by the way the procedures are activated rather than by what they do. The point is that in all cases, there is the need to finalize an object no longer needed with some cleanup process and to free whatever resources it has been using, memory being just one of them. Ideally, all of it should be done automatically when the object is no longer to be used, by means of a garbage collector. In practice, GC may be missing or have deficiencies, and this is compensated for by explicit triggering by the program of finalization and reclamation.

Explicit trigerring by the program is a problem since it can allow for hard to analyze programming errors, when an object still in use is being explicitly terminated.

Hence it is much better to rely on automatic garbage collection to reclaim resources. But there are two issues:

* some garbage collection technique will allow memory leaks that prevent full reclamation of resources. This is well known for reference counting GC, but may appear for other GC techniques when using some data organizations without care (point not discussed here).
* while GC technique may be good at identifying memory resources no longer used, finalizing objects contained therein may not be simple, and that complicates the problem of reclaiming other resources used by these objects, which is often the purpose of finalization.

Finally, an important point often forgotten is that GC cycles can be triggered by anything, not just memory shortage, if the proper hooks are provided and if the cost of a GC cycle is considered worth it. Hence it is perfectly OK to initiate a GC when any kind of resource is missing, in the hope of freeing some.

## Reference counting garbage collectors

**Reference counting is a weak garbage collecting technique**, that will not handle cycles properly. It would indeed be weak on destructing obsolete structures, and reclaiming other resources simply because it is weak on reclaiming memory. But finalizers can be used most easily with a reference counting garbage collector (GC), since a ref-count GC does reclaims a structure when its ref count goes down to 0, at which time its address is know together with its type, either statically or dynamically. Hence it is possible to reclaim the memory precisely after applying the proper finalizer, and calling recursively the process on all pointed objects (possibly via the finalizing procedure).

In a nutshell, finalization is easy to implement with Ref Counting GC, but suffers from the "incompleteness" of that GC, indeed due to circular structures, to precisely the same extent that memory reclamation suffers. In other word, **with reference count, memory is precisely as poorly managed as other resources** such as sockets, file handles, etc.

Indeed, **Ref Count GC inability to reclaim looping structures (in general) may be seen as memory leak**. You cannot expect all GC to avoid memory leaks. It depends on the GC algorithm, and on the type structure information dynamically available (for example in conservative GC).

## Tracing garbage collectors

**The more powerful family of GC, without such leaks, is the tracing family** that explores the live parts of the memory, starting from well identified root pointers. All parts of the memory that are not visited in this tracing process (which can actually be decomposed in various ways, but I have to simplify) are unused parts of the memory that can be thus reclaimed1. These collectors will reclaim all memory parts that can no longer be accessed by the program, no matter what it does. It does reclaim circular structures, and the more advanced GC are based on some variation of this paradigm, sometimes highly sophisticated. It can be combined with reference counting in some cases, and compensate for its weaknesses.

A problem is that **your statement** (at the end of the question):

> Languages which offer automatic garbage collection seem to be prime candidates to support object destruction/finalization as they know with 100% certainty when an object is no longer in use.

**is technically incorrect** for tracing collectors.

What is known with 100% certainty is what parts of memory are *no longer in use*. (More precisely, it should be said that they are *no longer accessible*, because some parts, that can no longer be used according to the logic of the program, are still considered in use if there is still a useless pointer to them in the program data.) But further processing and appropriate structures are needed to know what *unused objects* may have been stored in these now *unused parts of the memory*. This cannot be determined from what is known of the program, since the program is no longer connected to these parts of the memory.

Thus after a pass of garbage collection, you are left with fragments of memory that contain objects which are no longer in use, but there is a priori no way to know what these objects are so as to apply the correct finalization. Furthermore, if the tracing collector is the mark-and-sweep type, it may be that some of the fragments may contain objects that have already been finalized in a previous GC pass, but were not used since for fragmentation reasons. However this can be dealt with using extended explicit typing.

While a simple collector would just reclaim these fragments of memory, without further ado, finalization require a specific pass to explore that unused memory, identify the objects there contained, and apply finalization procedures. But such an exploration requires determination of the type of objects that were stored there, and type determination is also needed to apply the proper finalization, if any.

So that implies extra costs in GC time (the extra pass) and possibly extra memory costs to make proper type information available during that pass by diverse techniques. These costs may be significant as one will often want to finalize only a few objects, while the time and space overhead could concern all objects.

Another point is that the time and space overhead may concern program code execution, and not just the GC execution.

I cannot give a more precise answer, pointing at specific issues, because I do not know the specifics of many of the languages you list. In the case of C, typing is a very difficult issue that lead to the development of conservative collectors. My guess would be that this affects also C++, but I am no expert on C++. This seems to be confirmed by Hans Boehm who did much of the research on conservative GC. Conservative GC cannot reclaim systematically all unused memory precisely because it may lack precise type information on data. For the same reason, it would not be able to systematically apply finalizing procedures.

So, it is possible to do what you are asking, as you know from some languages. But it does not come for free. Depending on the language and its implementation, it may entail a cost even when you do not use the feature. Various techniques and trade-offs can be considered to address these issues, but that is beyond the scope of a reasonably sized answer.

1 - this is an abstract presentation of tracing collection (encompassing both copy and mark-and-sweep GC), things vary according to the type of tracing collector, and exploring the unused part of memory is different, depending on whether copy or mark and sweep is used.

# Answer
> 4 votes
The object destructor pattern is fundamental to error handling in systems programming, but has nothing to do with garbage collection. Rather, it has to do with matching object lifetime to a scope, and can be implemented/used in any language that has first class functions.

Example (pseudocode). Suppose you have a "raw file" type, like the Posix file descriptor type. There are four fundamental operations, `open()`, `close()`, `read()`, `write()`. You would like to implement a "safe" file type that always cleans up after itself. (I.e., that has an automatic constructor and destructor.)

I'll assume our language has exception handling with `throw`, `try` and `finally` (in languages without exception handling you can set up a discipline where the user of your type returns a special value to indicate an error.)

You set up a function that accepts a function that does the work. The worker function accepts one argument (a handle to the "safe" file).

```
with_file_opened_for_read (string:   filename,
                           function: worker_function(safe_file f)):
  raw_file rf = open(filename, O_RDONLY)
  if rf == error:
    throw File_Open_Error

  try:
    worker_function(rf)
  finally:
    close(rf)

```

You also provide implementations of `read()` and `write()` for `safe_file` (that just call the `raw_file` `read()` and `write()`). Now the user uses the `safe_file` type like this:

```
...
with_file_opened_for_read ("myfile.txt",
                           anonymous_function(safe_file f):
                             mytext = read(f)
                             ... (including perhaps throwing an error)
                          )

```

A C++ destructor is really just syntactic sugar for a `try-finally` block. Pretty much all I've done here is convert what a C++ `safe_file` class with a constructor and destructor would compile into. Note that C++ doesn't have `finally` for its exceptions, *specifically* because Stroustrup felt that using an explicit destructor was better syntactically (and he introduced it into the language before the language had anonymous functions).

(This is a simplification of one of the ways that people have been doing error handling in Lisp-like languages for many years. I think I first ran into it in the late 1980s or early 1990s, but I don't remember where.)

# Answer
> 2 votes
This isn't a full answer to the question, but I wanted to add a couple of observations that haven't been covered in the other answers or comments.

1. The question implicitly assumes that we're talking about a Simula-style object oriented language, which is itself limiting. In most languages, even those with objects, not everything is an object. The machinery to implement destructors would impose a cost which not every language implementor is willing to pay.
2. C++ has some implicit guarantees about destruction order. If you have a tree-like data structure, for example, the children will be destroyed before the parent. This is not the case in GC'd languages, so hierarchical resources may be released in an unpredictable order. For non-memory resources, this can matter.

# Answer
> 2 votes
When the of two most popular GC frameworks (Java and .NET) were being designed, I think the authors expected that finalization would work well enough to avoid the need for other forms of resource management. Many aspects of language and framework design can be greatly simplified if there's no need for all features necessary to accommodate 100% reliable and deterministic resource management. In C++, it's necessary to distinguish between the concepts of:

1. Pointer/reference that identifies an object which is exclusively owned by the holder of the reference, and which is not identified by any pointers/references the owner doesn't know about.
2. Pointer/reference that identifies a sharable object which isn't exclusively owned by anyone.
3. Pointer/reference that identifies an object which is exclusively *owned* by the holder of the reference, but to which may be accessible through "views" the owner has no way of tracking.
4. Pointer/reference that identifies an object which is provides a view of an object which is owned by someone else.

If a GC language/framework don't have to worry about resource management, all of the above can be replaced by a single kind of reference.

I would find naïve the idea that finalization would eliminate the need for other forms of resource management, but whether or not such expectation was been reasonable at the time, history has since shown that there are many cases that require more precise resource management than finalization provides. I happen to think that rewards of recognizing ownership at the language/framework level would be sufficient to justify the cost (the complexity has to exist somewhere, and moving it to the language/framework would simplify user code) but do recognize that there are significant design benefits to having a single "kind" of reference--something which only works if the language/framework are agnostic to issues of resource cleanup.

# Answer
> 2 votes
> Why is the object destructor paradigm in garbage collected languages pervasively absent?
>
> I come from a C++ background, so this area is baffling to me.

The destructor in C++ actually does **two** **things** combined. It frees RAM and it frees resource ids.

Other languages separate these concerns by having the GC be in charge of freeing RAM while another language feature take charge of freeing resource ids.

> I find it extremely lacking that these languages consider memory as the only resource worth managing.

That's what GCs are all about. They only dono **one thing** and it is to ensure that you don't run out of memory. If RAM is infinite, all GCs would be retired as there is no longer any real reason for them to exist.

> What about sockets, file handles, application states?

Languages can provide different ways of freeing resource ids by:

* manual `.CloseOrDispose()` scattered across code
* manual `.CloseOrDispose()` scattered within manual "`finally` block"
* manual "resource id blocks" (i.e. `using`, `with`, `try`-with-resources, etc) which automates `.CloseOrDispose()` after the block is *done*
* **guaranteed "resource id blocks" which automates `.CloseOrDispose()`** after the block is *done*

Many languages use manual (as opposed to guaranteed) mechanisms which creates an opportunity for resource mismanagement. Take this simple NodeJS code:

```
require('fs').openSync('file1.txt', 'w');
// forget to .closeSync the opened file

```

..where the programmer has forgotten to close the opened file.

For as long as the program keeps running, the opened file would be stuck in limbo. This is easy to verify by trying to open the file using HxD and verifying that it can't be done:

Freeing resource ids within C++ destructors is also non-guaranteed. You might think RAII operates like guaranteed "resource id blocks", yet unlike "resource id blocks", the C++ language does not stop the object providing the RAII block from being **leaked**, so the RAII block may never be *done*.

---

> It seems nearly all modern garbage collected languages with OOPy object support like Ruby, Javascript/ES6/ES7, Actionscript, Lua, etc. completely omit the destructor/finalize paradigm. Python seems to be the only one with its class `__del__()` method. Why is this?

Because they manage resource ids using other ways, as mentioned above.

> What are the language design decisions which lead to these languages not having any way to execute custom logic on object disposal?

Because they manage resource ids using other ways, as mentioned above.

> Why would a language have the built-in concept of object instances with class or class-like structures along with custom instantiation (constructors), yet completely omit the destruction/finalize functionality?

Because they manage resource ids using other ways, as mentioned above.

> I could see a possible argument being that the destructor/finalizer may not get called until some indeterminate time in the future, but that didn't stop Java or Python from supporting the functionality.

Java doesn't have destructors.

The Java docs mention:

> the usual purpose of finalize, however, is to perform cleanup actions before the object is irrevocably discarded. For example, the finalize method for an object that represents an input/output connection might perform explicit I/O transactions to break the connection before the object is permanently discarded.

..but putting resource-id management code within `Object.finalizer` is largely regarded as an anti-pattern (cf.). Those code should instead be written at the call site.

For people who use the anti-pattern, their justification is that they **might have forgotten** to release the resource-ids at the call site. Thus, they do it *again* in the finalizer, just in case.

> What are the core language design reasons to not support any form of object finalization?

There are not many use cases for finalizers as they are for running a piece of code between the time when there are no longer any strong references to the object, and the time when it's memory is reclaimed by the GC.

A possible use case is when you'd like to keep a log of the time between the object is collected by the GC and the time when there are no longer any strong references to the object, as such:

```
finalize() {
    Log(TimeNow() + ". Obj " + toString() + " is going to be memory-collected soon!"); // "soon"
}

```

# Answer
> 0 votes
The RAII pattern in C++ is very powerful when you have deterministic object lifetime (stack objects go out of scope, heap objects are deleted), it is widely used to manage both memory and other resources (usually more precious, like file handles, sockets, locks, etc.).

However in GC languages where objects have indeterministic lifetime (GC only happens when there is a memory shortage, or not happen at all if program finishes quickly), it becomes necessary to treat memory management and more precious resource management separately. In these GC languages, these precious resources are usually managed through explicit method call (close(), unlock(), etc.), and sometimes with the help from other language constructs like "try...finally (Java)" or "with .... as ... (Python)".

# Answer
> -1 votes
found a ref on this in Dr Dobbs wrt c++ that has more general ideas that argues destructors are problematic in a language where they are implemented. a rough idea here seems to be that a main purpose of destructors is to handle memory deallocation, and that is hard to accomplish correctly. memory is allocated piecewise but different objects get connected and then the deallocation responsibility/ boundaries are not so clear.

so the solution to this of a garbage collector evolved years ago, but garbage collection is not based on objects disappearing from scope at method exits (that is a conceptual idea that is hard to implement), but on a collector running periodically, somewhat nondeterministically, when the app experiences "memory pressure" (ie running out of memory).

in other words the mere human concept of an "newly unused object" is actually in some ways a misleading abstraction in the sense that no object can "instantaneously" become unused. unused objects can only be "discovered" by running a garbage collection algorithm that traverses the object reference graph and the best performing algorithms run intermittently.

it is possible a better garbage collection algorithm lies waiting to be discovered that can near-instantaneously identify unused objects, which could then lead to consistent destructor calling code, but one has not been found after many years of research in the area.

the solution to resource management areas such as files or connections seems to be to have object "managers" that attempt to handle their use.

---
Tags: programming-languages, memory-management, garbage-collection, language-design
---


# Question
Title: K-Maps (Digital Logic, Computer System Architecture)
While i was going thru my course in Computer System Architecture (book taken Morris Mano) , I saw a question on KMaps can be solved in either of the ways but couldn't get which one to use when :-

I’m taking for an example kmaps for 3 var

```
    A’B’    A’B     AB  AB’
C’   0      1       3    2
C    4      5       7    6

```

(probably here we are taking CAB’ = 6

and below like AB’C =5 )

```
    A’B’  A’B    AB     AB’
C’   0     2      6     4
C    1     3      7     5

```

**But how do i know which one to use and when**

# Answer
Both are correct in their own way. The goal of K-map is to aid the minimization of boolean functions, it doesn't impose any rules on how it is created.

With reference to your example, if you are minimizing a function $F(C,A,B)$ then you interpret it as rows first$(MSB = C)$ and then columns $(A,B)$. If you are minimizing $F(A,B,C)$ then you interpret it as columns first $(MSBs = A,B)$ and then rows $(C)$. This is because $F(A,B,C)\neq F(C,B,A)$ for a given truth value assignment i.e. given a truth table for $F(A,B,C)$ you cant use the truth values in the same order for $F(C,B,A)$ and expect the same minimized expression. (You can easily verify this by taking up an example truth table for $(A,B,C)$ and use the same for $(C,B,A)$, and as food for thought, how to make them same).
> 0 votes

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


# Question
Title: Single machine scheduling with profit and deadline constraints
The problem is described as such:

Given $n$ tasks $\\{J\_1, \ldots , J\_n\\}$where each task has a deadline and a ‘profit’.

So for some $i \in \\{1,\ldots , n\\}$, $J\_i=\\{t\_i,p\_i\\}$ where $t\_i$ is the deadline to complete the task, and $p\_i$ is the expected profit.

It is given that:

* starting time is $0$
* each task takes $1$ time to complete.
* you can only work on a single task in every time unit.

The goal is to describe an efficient algorithm to receive a group of n task as input (as described) and finds the maximal profit subseries of tasks.

I know this problem relates to a family of problems where a machine can only perform a single task every time, and since this problem requires to find the maximal subseries, I’m inclined towards a dynamic programming approach, yet I also consider a greedy approach might do the trick.

I was unable to find a solution to the problem with such constraints.

# Answer
> 1 votes
A simple greedy algorithm is known for this problem \[1\].

First, sort jobs by non-decreasing order of deadline. Let $S := \emptyset$ be a variable to denote a set of jobs. Then, for each job $i$,

```
if |S| < t_i then:
  Add job i to S
  # Job i is scheduled at time |S|-1
else if there exists a job k in S such that p_k < p_i:
  Delete job k from S such that p_k is minimal
  Add job i to S
  # Job i is scheduled at the time job k was scheduled

```

By implementing the set $S$ using a priority queue, the algorithm runs in $O(n \log n)$ time. This algorithm can be generalized to the case of identical parallel machines.

The greedy algorithm can be understood as an incremental greedy algorithm for the matroid.

* \[1\] Brucker, Peter. Scheduling Algorithms. 5th ed. Springer, 2007.

---
Tags: dynamic-programming, np-hard, scheduling, maximum-subarray
---


# Question
Title: Minimum number of bits to codify arrays with bounded sums
I have a very big set of non-empty arrays of possibly repeated numbers sorted in a weakly-decreasing order where each number belongs to the interval $\[1, 55\]$ and the sum of the elements of each array is always $\leq 55$. For example, the array $A=\[5, 5, 3, 3, 3, 3, 1, 1, 1\]$ contains 9 elements and its sum is $25$.

I want to codify each possible array on a bitstring that is as short as possible (this codification would be used as a key of a hash-table to know which arrays do or do not occur in my collection).

The most-space efficient way to codify the arrays that I have been able to find requires 109 bits: given an array $A$, each number $x$ from $A$ is codified by storing $x$ consecutive $1$s followed by a $0$ to separate the number from the following one. Consider the array $A$ presented above. I would codify it as (five $1$s, then a $0$, then five $1$s, then a $0$, the three $1$s, then a $0$, etc): $$ 111110111110111011101110111010101 $$

The worst case would be an array containing fifty five $1$s, which would be codified as fifty five $1$s separeted by fifty four $0$s: 109 bits. The number of $1$s on the bitstring equals the sum of the array, and the number of $0$s is the size of the array minus 1.

But, is there way to use it **even less bits** to codify any possible array? I would like to use **64-bits at most**.

**Optimal approach (I guess):**

If I consider all the possible arrays that sum $n$ as all the possible partitions of $n$, the total number of arrays I could have in total is $$P(n) = \sum\_{n = 1}^{55}p(n)$$ where $p(n)$ is the partition function. I have compute this sum and there's in total $2984864$ possible partitions of all numbers $n\in\[1, 55\]$. If given an array $A$ I'm able to compute an unique index $I\_A\in\[1, 2984864\]$ for it (so that any other array $B=A$ computes the same index), I would only need 22 bits to codify each array, because $\log\_2(2984864)=21.509\ldots$

Is there any computationally tractable algorithm to compute such an index?

# Answer
Your question concerns ranking and unranking of integer partitions. Ranking is the process of converting an integer partition into an index, and unranking is the opposite operation.

Let us first consider ranking and unranking of partitions of exactly $n$ with $k$ parts, which are counted by $p(n,k)$. Enumerating over the minimal element $m$ and the number of times $\ell$ it appears, when $k \> 0$ we have $$ p(n,k) = \sum\_{m=1}^{\lfloor n/k \rfloor} \sum\_{\ell=1}^k p(n-km,k-\ell). $$ The base cases are $p(0,0) = 1$ and $p(n,0) = 0$ if $n \> 0$.

We can partition accordingly the interval $\[p(n,k)\]$ into intervals of length $p(n-km,k-\ell)$ in some arbitrary way. The interval corresponding to some $(m,k)$ will be used to index partitions of the corresponding type. This leads to recursive ranking and unranking algorithms which I will let you work out. These algorithms require knowledge of $p(n,k)$, which can be computed using dynamic programming through the recursion above.

Using $p(n) = \sum\_{k=1}^n p(n,k)$, we can similarly rank and unrank partitions of $n$ with an arbitrary number of parts. Using $P(n) = \sum\_{r=0}^n p(r)$, we can similarly rank and unrank partitions of at most $n$.
> 2 votes

---
Tags: partitions
---


# Question
Title: Count number of non-contiguous occurrences in string
Given strings $S,T$ such that $n=|T|\>|S|$ , I'd like an algorithm to count number of occurrences of $S$ in $T$ (as a subsequence), not necessarily contiguous.

Example: if $T=aababc, S=abc$, the algorithm should return $5$.

I've tried taking a suffix tree/ suffix array approach, only to realize that these tools are good for contiguous substrings but not for non-contiguous subsequences.

**a**a**b**ab**c** , a**ab**ab**c** , **a**aba**bc** , a**a**ba**bc** , aab**abc**

A problem that (might) kind of relate to this problem from what I know would be the maximal non-contiguous subarray problem, yet I do not know how to connect between these.

# Answer
> 11 votes
A dynamic programming algorithm in $\mathcal{O}(|S| |T|)$ should do the trick.

Let's denote $S = s\_1…s\_m$ and $T = t\_1…t\_n$. For $0\leqslant i \leqslant m$, $0\leqslant j \leqslant n$, let $N(i, j)$ be the number of occurrences of $s\_1…s\_i$ in $t\_1…t\_j$. We have $N(0, j) = 1$ (by convention, for computation purposes), $N(i, j) = 0$ if $i \> j$ and if $i, j\>0$:

$$N(i, j) = \left\\{\begin{array}{ll} N(i, j-1) & \text{if }s\_i \neq t\_j\\ N(i, j-1) + N(i-1,j-1) & \text{otherwise} \end{array}\right.$$ The idea is that a subsequence $s\_1…s\_i$ appears in $t\_1…t\_j$ if it appears in $t\_1…t\_{j-1}$ or if $s\_1…s\_{i-1}$ is a subsequence of $t\_1…t\_{j-1}$ and $s\_i = t\_j$.

Now you just have to compute $N(m, n)$ to get the answer you want.

# Answer
> 2 votes
I think this should do it (string indexes starts by 1):

```
stack = [1] // start iterating from T[1]
count = 0

while stack.length > 0
   while (stack.last <= T.length and T[stack.last] != S[stack.length])
      ++stack.last;

   if (stack.last <= T.length)
       if (stack.length == S.length)
          ++count
          ++stack.last
       else
          stack.push(stack.last + 1)
   else
       stack.pop()
       ++stack.last

```

The idea is as follow:

* There's a stack where each "level" represents a letter in $S$ in the same order. So level 1 represents letter a in your example, level 2 letter b etc. The content of level $i$ is the index of an ocurrence of $S\_i$ in $T$.
* The index that you store on each level of the stack must be bigger than the index on every lower lever.
* Each time you find an ocurrence of $S\_i$ in $T$, let's call $j\_i$ to its index, you assign $j\_i + 1$ to the level $i + 1$ (you "push" $j\_i + 1$ on the stack) and find the next ocurrence of $S\_{i+1}$ in $T$ starting at position $j\_i + 1$.
* Each time you find a new ocurrence at level $|S|$ you add $1$ to your counter.
* Each time you reach the end of $T$, you pop your stack, increase the index of the level that is now the last, and repeat.

---
Tags: strings, counting, substrings
---