Does the 'difference' operation add expressiveness to a query language that already includes 'join'? The set difference operator (e.g., EXCEPT in some SQL variants) is one of the many fundamental operators of relational algebra. However, there are some databases that do not support the set difference operator directly, but which support LEFT JOIN (a kind of outer join), and in practice this can be used instead of a set difference operation to achieve the same effect.

Does this mean that the expressive power of a query language is the same even without the set difference operator, so long as the LEFT JOIN operator is maintained? How would one prove this fact?

In relational algebra, we shall first provide an informal definition of left (outer) join, and proceed to prove that it, renaming, selection, join and projection can construct difference, as well as that difference, selection and union can be used to construct left (outer) join. Actually, we'll end up doing it in the reverse order: we'll show how to construct left joins using differences, and then we'll show how to construct differences using left joins.

Let $R$ and $S$ have schemata $(R', T)$ and $(T, S')$, respectively, where $R'$ and $S'$ are the sets of attributes in one schema but not the other, and $T$ is the set of common attributes.

Let $w = (\epsilon, \epsilon, ..., \epsilon)$ be the null tuple for schema $S'$. That is, it is the tuple consisting of all null values for each attribute of $S'$. Then, we define left outer join as follows: R LEFT JOIN S is the set of all tuples $(r, t, s)$ belonging to schema $(R', T, S')$ where...

$(r, t)$  is a tuple in $R$;
(a) $(t, s)$ is a tuple of $S$ or (b) $s = w$;
If $(r, t, s)$ is in the set for $s \neq w$, then $(r, t, w)$ is not in the set.

Example: $R$'s schema is $(A_{1}, A_{2}, A_{3})$, $S$'s schema is $(A_{2}, A_{3}, A_{4})$, and we have that $R = \{(1, 2, 3), (4, 5, 6)\}$ and $S = \{(2, 3, 4), (2, 3, 6)\}$. By (1) and (2) we get the intermediate result $\{(1, 2, 3, 4),(1, 2, 3, 6), (1, 2, 3, \epsilon),(4, 5, 6, \epsilon)\}$. By (3) we must remove $(1, 2, 3, \epsilon)$, since we have (for instance) $(1, 2, 3, 4)$ and $s = 4 \neq \epsilon = w$. We are thus left with $\{(1, 2, 3, 4), (1, 2, 3, 6), (4, 5, 6, \epsilon)\}$, the expected result for a left join.

Theorem: R LEFT JOIN S is equivalent to (R EQUIJOIN S) UNION ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w).

Proof: (R EQUIJOIN S) gives us everything required by (1) and (2a). We claim that ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) gives us everything of the form (r, t, w) required by (2b) and (3).

To see this, first notice that (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) is the set of all tuples in $R$ for which there is no corresponding tuple in $S$. To see that, it suffices to note that by projecting the common attributes out of $R$ and $S$ (the attribute set $T$) and taking the difference, one is left with all and only those tuples (with schema $T$) which are represented in $R$ but not $S$. By the EQUIJOIN with $R$, we recover all and only those tuples in $R$ which have values for attributes in $T$ which are present in $R$ but not in $S$; namely, precisely the set of tuples we have so far claimed.

Next, notice that the schema of (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) is the same as that of $R$ (namely, $(R', T)$), while the schema of $w$ is $S'$. The JOIN operation is therefore a Cartesian product, we we get all tuples of the form $(r, t, w)$ where there is no $(t, s)$ in $S$ corresponding to $(r, t)$ in $R$.

To see that this is precisely the set of tuples we needed to add to R EQUIJOIN S in order to construct R LEFT JOIN S, consider the following: by construction, (3) is satisfied, since R EQUIJOIN S cannot contain $(r, t, s)$ if ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) contains $(r, t, w)$ (if it did, then the second part's containing $(r, t, w)$ would be a contradiction); if we were to add another $(r, t, w)$ not in ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w), then there would be a $(t, s)$ in $S$ corresponding to $(r, t)$ in $R$, and by the definition of EQUIJOIN, $(r, t, s)$ would also be in R LEFT JOIN S, a contradiction of (3). This completes the proof.

Now we show that left join can be used to construct difference:

Theorem: R DIFFERENCE S is equivalent to PROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))

Proof: Notice that here, $R'$ and $S'$ are empty, since all attributes are shared for DIFFERENCE to make sense. First, we create a new relation from $S$ by duplicating the attribute set in $S$ (handled by RENAME and JOIN) so that it consists of tuples $(t, t')$ on attribute set $(T, T')$ where $t = t'$ (handled by the SELECT). The left join leaves us with tuples of the form $(t, t')$ where $t=t'$ or $t'=w$. Now, to get rid of entries which do also appear in $S$, we must keep only the tuples of the form $(t, w)$, which is handled by the outermost SELECT. The last PROJECT gets rid of the temporary attribute set $T'$ and leaves us with the difference in terms of the original schema.

Example: Let $R = \{(1, 2), (3, 4), (5, 6)\}$ and $S = \{(3, 4), (5, 6), (7, 8)\}$. We first get $S$ with the RENAMEd attribute set $T'$: $\{(3, 4), (5, 6), (7, 8)\}$. The JOIN operation gives us the Cartesian product with all nine possible pairings; this set is not written here for reasons of formatting. The SELECT then pares this down to $\{(3, 4, 3, 4), (5, 6, 5, 6), (7, 8, 7, 8)\}$. The LEFT JOIN with $R$ gives $\{(1, 2, \epsilon, \epsilon), (3, 4, 3, 4), (5, 6, 5, 6)\}$. The SELECT gives $\{(1, 2, \epsilon, \epsilon)\}$. The PROJECT gives $\{(1, 2)\}$, the desired answer.


Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free This is a homework problem I have spent several hours on. A "hint" is given that we may use this fact: If $n,j,k \in \mathbb{N}$ satisfy $ n \geq 2$ and $1 \leq j+k \leq n$, then $n^2+j$ does not evenly divide $n^3+k$.

I cannot find any way to apply this fact. It leads me to believe I should use the string $0^{p^2}1^{p^3}$ or something like that, but I am really just not sure. The pumping lemma has given me trouble since the non regular language version.

Even small hints greatly appreciated at this point.

If you use the pumping lemma on the word $w=0^{p^2} 1^{p^3}$, consider the partition $w=xyzuv$, where $|yzu|\le n$ and $|yu|>0$ ($n$ being the length of $w$).
It is easy to prove that from all the cases (that is, from all the possibilities for $y$ and $u$), the only non-trivial case is when $y=0^i$ and $u=1^j$, in which case the hint you mentioned finishes the job.


Big Omega of 3-Sum Algorithm An optimized algorithm for the 3-sum problem with an input array N has
O(N^2logN) however I read that the Big Omega for this algorithm could be Omega(N) because you have to touch all entries once. But to me this doesn't make sense.

If you have to perform the 3-sum operation on the entire array, wouldn't Big-O and Big-Omega be the same because regardless of the results the algorithm has to perform the same operations on the entire array?

We don't know what the best complexity for the 3SUM problem is. First of all, we can improve on your $O(N^2\log N)$ algorithm to an $O(N^2)$ algorithm by carefully scanning the two arrays in tandem, thus obviating the binary search. Until very recently, it had been conjectured that there is a corresponding $\Omega(N^2)$ lower bound, and on this basis the complexity of many other problems, especially in computational geometry, had been "determined". However, very recently Grønlund and Pettie gave an $O(N^2/(\log N/\log\log N)^{2/3})$ algorithm, so we know that the $O(N^2)$ algorithm is not optimal. It is still conjectured that 3SUM requires $\Omega(N^{2-\epsilon})$ time for every $\epsilon > 0$.


What other implementation styles are there besides compilation, interpretation and transpilation? Obviously there is JIT but it is basically run-time compilation. There is also implementing things in VHDL or ASIC. But my question is more towards software techniques for program building and execution

Fundamentally, there are only the two: compilation and interpretation.
tl;dr: An interpreter runs the program, a compiler translates the program to another language.
An interpreter for language X is a program (or a machine, or just some kind of mechanism in general) that executes any program p written in language X such that it performs the effects and evaluates the results as prescribed by the specification of X. CPUs are usually interpreters for their respective instructions sets, although modern high-performance workstation and server CPUs are actually more complex than that; they may actually have an underlying proprietary private instruction set and either translate (compile) or interpret the externally visible public instruction set.
A compiler from X to Y is a program (or a machine, or just some kind of mechanism in general) that translates any program p from some language X into a semantically equivalent program p′ in some language Y in such a way that the semantics of the program are preserved, i.e. that interpreting p′ with an interpreter for Y will yield the same results and have the same effects as interpreting p with an interpreter for X. (Note that X and Y may be the same language.)
In some cases, we have more specialized names for certain kinds of compilers, depending on what X and Y are, and what the compiler does:

if X is perceived to be assembly language and Y is perceived to be machine language, then we call it an assembler,
if X is perceived to be machine language and Y is perceived to be assembly language, then we call it a disassembler,
if X is perceived to be lower-level than Y, then we call it a decompiler,
if X and Y are the same language, and the resulting program is in some way faster or lighter, then we call it an optimizer,
if X and Y are the same languages, and the resulting program is smaller, then we call it a minifier,
if X and Y are the same languages, and the resulting program is less readable, then we call it an obfuscator,
if X and Y are perceived to be at roughly the same level of abstraction, then we call it a transpiler, and
if X and Y are perceived to be at roughly the same level of abstraction and the resulting program preserves formatting, comments, and programmer intent such that it is possible to maintain the resulting the program in the same fashion as the original program, then we call it a re-engineering tool.

Also, note that older sources may use the terms "translation" and "translator" instead of "compilation" and "compiler". For example, C talks about "translation units".
You may also stumble across the term "language processor". This can mean either a compiler, an interpreter, or both compilers and interpreters depending on the definition.
The terms Ahead-of-Time (AOT) and Just-in-Time (JIT) refer to when compilation takes place: the "time" referred to in those terms is "runtime", i.e. a JIT compiler compiles the program as it is running, an AOT compiler compiles the program before it is running. Note that this requires that a JIT compiler from language X to language Y must somehow work together with an interpreter for language Y, otherwise there wouldn't be any way to run the program. (So, for example, a JIT compiler which compiles JavaScript to x86 machine code doesn't make sense without an x86 CPU; it compiles the program while it is running, but without the x86 CPU the program wouldn't be running.)
So, we have:

AOT compiler: compiles before running
JIT compiler: compiles while running
interpreter: runs

JIT Compilers
Within the family of JIT compilers, there are still many differences as to when exactly they compile, how often, and at what granularity.
Some JIT compilers for example only compils code once (when it is loaded) and compiles a whole module at a time. Other compilers may gather information while the program is running and recompile code several times as new information becomes available that allows them to better optimize it. Some JIT compilers are even capable of de-optimizing code. Now, you might ask yourself why one would ever want to do that? De-optimizing allows you to perform very aggressive optimizations that might actually be unsafe: if it turns out you were too aggressive you can just back out again, whereas, with a JIT compiler that cannot de-optimize, the program would crash or return a wrong result; in other words, you simply can't allow yourself to perform the aggressive optimizations in the first place.
JIT compilers may either compile some static unit of code in one go (one module, one class, one function, one method, …; these are typically called method-at-a-time JIT, for example) or they may trace the dynamic execution of code to find dynamic traces (typically loops) that they will then compile (these are called tracing JITs).
Combining Interpreters and Compilers
Interpreters and compilers may be combined into a single language execution engine. There are two typical scenarios where this is done.
Combining an AOT compiler from X to Y with an interpreter for Y. Here, typically X is some higher-level language optimized for readability by humans, whereas Y is a compact language (often some kind of bytecode) optimized for interpretability by machines. For example, the CPython Python execution engine has an AOT compiler that compiles Python sourcecode to CPython bytecode and an interpreter that interprets CPython bytecode. Likewise, the YARV Ruby execution engine has an AOT compiler that compiles Ruby sourcecode to YARV bytecode and an interpreter that interprets YARV bytecode. Why would you want to do that? Ruby and Python are both very high-level and somewhat complex languages, so we first compile them into a language that is easier to parse and easier to interpret, and then interpret that language.
The other way to combine an interpreter and a compiler is a mixed-mode execution engine. Here, we "mix" two "modes" of implementing the same language together, i.e. an interpreter for X and a JIT compiler from X to Y. (So, the difference here is that in the above case, we had multiple "stages" with the compiler compiling the program and then feeding the result into the interpreter, here we have the two working side-by-side on the same language.) Code that has been compiled by a compiler tends to run faster than code that is executed by an interpreter, but actually compiling the code first takes time (and particularly, if you want to heavily optimize the code to run really fast, it takes a lot of time). So, to bridge this time where the JIT compiler is busy compiling the code, the interpreter can already start running the code, and once the JIT is finished compiling, we can switch execution over to the compiled code. This means that we get both the best possible performance of the compiled code, but we don't have to wait for the compilation to finish, and our application starts running straight away (although not as fast as could be).
This is actually just the simplest possible application of a mixed-mode execution engine. More interesting possibilities are, for example, to not start compiling right away, but let the interpreter run for a bit, and collect statistics, profiling information, type information, information about the likelihood of which specific conditional branches are taken, which methods are called most often etc. and then feed this dynamic information to the compiler so that it can generate more optimized code. This is also a way to implement the de-optimization I talked about above: if it turns out that you were too aggressive in optimizing, you can throw away (a part of) the code and revert back to interpreting. The HotSpot JVM does this, for example. It contains both an interpreter for JVM bytecode as well as a compiler for JVM bytecode. (In fact, it actually contains two compilers!)
It is also possible and in fact common to combine those two approaches: two phases with the first being an AOT compiler that compiles X to Y and the second phase being a mixed-mode engine that both interprets Y and compiles Y to Z. The Rubinius Ruby execution engine works this way, for example: it has an AOT compiler that compiles Ruby sourcecode to Rubinius bytecode and a mixed-mode engine that first interprets Rubinius bytecode and once it has gathered some information compiles the most often called methods into native machine code.
Note that the role that the interpreter plays in the case of a mixed-mode execution engine, namely providing fast startup, and also potentially collecting information and providing fallback capability may alternatively also be played by a second JIT compiler.
This is how the second generation of Google's V8 ECMAScript engine worked, for example. This generation of V8 never interprets, it always compiles. The first compiler is a very fast, very slim compiler that starts up very quick. The code it produces isn't very fast, though. This compiler also injects profiling code into the code it generates. The other compiler is slower and uses more memory, but produces much faster code, and it can use the profiling information collected by running the code compiled by the first compiler.


Question on an Algorithm for Longest Increasing Subsequence I have been reading this paper: https://arxiv.org/abs/2011.10874
This paper presented an exact randomized algorithm with update time $\tilde{O}(n^{0.8})$. I will quickly talk about the overall idea of the paper: we first organizes elements by layers $L_i$ described as follows: "We define $b_i$ as the size of the longest increasing subsequence ending at element $a_i$ and divide the sequence into disjoint layers. More precisely, let each layer $L_i = \{a_j | b_j = i\}$ be the set of elements whose corresponding $b_j$ is equal to i. "
We then combine executive layers of equal size into basket (expect for the first and last basket). The baskets are considered light or heavy based on criteria listed in Page 14
I got quite confused with part of the algorithm when they say:
"Throughout our algorithm, we maintain a local data structure for each light basket i that stores the following information: If $i = 1$, then for each element ay of basket 1, we store the size of the longest increasing subsequence that ends at $a_y$. If $i > 1$, then for each boundary element $a_x$ of basket $i−1$ and each element $a_y$ of basket $i$, we store the size of the longest increasing subsequence that starts at $a_x$ and ends at $a_y$. Except for the initial element $a_x$, any element that may contribute to such a subsequence is certainly inside basket i" (Page 14).
The part that I am confused with is weather or not we dynamically change the number of layers in a basket. For example, if I remove the element "14" from the list, $L_8$ will only constitute "15", so should "15" be moved to Basket 3 or "15" is kept in Basket 4? This is pretty important since after the deletion, would "13" be the boundary term of Basket 3 or is it "15"?

Thanks
Update: I have understand the problem and post the resolution. I would like to keep the question for other users

Update:
I have thoroughly read through the paper myself and understand the problem better. So the algorithm fails if I make the above deletion (i.e. removing elements from a boundary layer). Layers $L_i = \{a_j | b_j = i\}$ are only for initialization, and for the duration of the algorithm, only the boundary layers are kept in tact to calculate one of the local data structure (which assumes the boundary layers are unchanged). This is a probabilistic algorithm and the paper show that we can get success rate to $1-n^{-10}$ after $20\log n$ repeats.


About Control Unit in CPU and Clock Cycle I've been studying about CPU and I am trying to implement a small CPU, like MU0.
Control unit gets instruction and generates and gives several control signals to other parts of CPU, such as ALU, PC, ACC, etc. And I know that these works in one clock cycle.
But I have some quetions.

Meaning of Signals (0 or 1) in Clock Cycle

Each one clock cycle has signal 1 first and has 0 next. Since CPU is an electronic equipment, 1 would mean current is flowing (so, "turn on") and 0 would mean no current flow (so, "turn off").
So, does each control signals connected to the clock cycle circuit turn off when the clock cycle is 0 at the same time, if we ignore delays of the circuit?
If not, i.e., if control signals can be 1 although clock cycle is 0, I can state my hypothesis:
Clock signal is only meaningful and only used when signal toggles 1→0 or 0→1. Control unit can not work when its signal stays in the same value since it can not recognize time is going.
Is that true or false?

Timing to Control each Control Signals

(source: tistory.com)
Here is the structure of MU0, one of simple CPUs.
If we want to store data from memory with the address in PC to IR and increase PC by 1 (i.e., PC = PC + 1), the manual says that setting control signals as below would do that.

0 : Asel, Bsel, ACCce, ACCoe
1 : PCce, IRce, MEMrq, RnW
with ALU function B+1.

Note that the value of PC goes in ALU and the output of ALU is PC+1 since Asel(A selector), Bsel are 1.
But, since PCce(PC chip enabler) is 1, PC change the value by the input of PC, which is the output of ALU.
It seems good to make PC as PC+1. But my questions is:
This is an infinite loop theoritically since PC+1 would goes into ALU and PC+2 would save in PC, and then PC+2 would goes into ALU and PC+3 would save in PC, ... so and on until one clock cycle ends.
To avoid this, controlling timings would be different for each control signals. Is this really true, or is there another solution?
Thanks.

1.) (Almost) every component of the CPU needs to be synchronized by the clock, which means they all do their work only if the clock is high (1); never when it's low (0) (or alternatively only during rising edge). This could for example be implemented using an AND-gate, with the input to the component as first and the clock signal as second input. So the component will only get its new input if the clock is currently high, else it does nothing. And because the clock speed is set above the longest time any signal needs to propagate through any circuit in the CPU, this system is preventing signals from arriving before other signals are ready and thus keeps everything safe and synchronized. The control signals can be set at any time, but they will only be accepted during high clock.

2.) This is no loop, since the PC is actually a register which is egde triggered. This means, like mentioned above, that it is changing its state only one time per cycle for a short period of time. At an earlier time, the last output from ALU (PC + 1) is just waiting at the input of the PC. Then, at the next cycle, the PC takes its input. This is when PC = PC + 1 actually happens.


Converting decision problems to grammars? I'm struggling to understand some concepts related to the relationship between language and computability theories.

Can we convert decision problems to the corresponding grammars describing the languages? Can every decidable decision problem be converted to a context-free or context-sensitive grammars?

If it does not make sense at all, what is the relationship between the decision problems and languages?

Yes, every decision problem can be converted into a grammar that generates exactly the "yes"-instances of the problem.

And no, even if the problem is decidable, there is not necessarily a context-sensitive (let alone a context-free) grammar. An example would be the equivalence problem for regular expressions with exponentiation. (reference)


What do you call a DAG with a single root/source? What's the name for a DAG (directed acyclic graph) that has a unique root or source node from which every other node can be reached?

Alternatively, if you change the direction of the arrows, what's the name for a DAG that has some unique sink node that is reachable from every other node?

Here's an example graph:

In a directed graph we do not speak of roots and leaves, but of sources and sinks.

I'm not aware of any term that designates a DAG with only a single source, but you could just call it that: "a DAG with a single source".


Finding rainbow cycle in digraph colored with $\log n$ colors Given a directed graph with $n$ vertices, and $k=\log n$, we are given a coloring of the vertices with $k$ colors.
Describe an algorithm determining if there exists a simple cycle in $G$ of length $k$ visiting exactly one vertex of each color.
Time complexity should be $O(n^3)$.

I couldn't think of any efficient solution.

The idea is to use dynamic programming. For each vertex $v$ and color subset $S$, calculate whether there is a simple path, ending at $v$, and including exactly the colors in $S$. Details left to you.

The main trick here is that we can be sure that the path being constructed is simple since all vertices in it have different colors. We can apply the same idea to uncolored graphs by choosing a random coloring. This is known as color-coding, an idea of Alon, Yuster and Zwick with wide applicability.


How many registers does a computer *need*? I read about Why does a processor have 32 registers?, and others. Currently I am messing around with an OS in JavaScript, and wondering how many registers -- or more specifically, how many temporary variable slots -- you need in a computer. How many do you need? Bare minimum, what is theoretically the lower bound? Is it 2? Or is it 8? I read some CPUs had 8 at one point, why did they switch to 32 or more these days? I wonder if you can get by with only 2 registers for all computation. If so, is it very inefficient or something? These are all aspects of the main question.

As a tangent question as to why they need $X$ number, what is the ideal number of registers and why? Is there even an ideal? If not a specific number, what is a measure of idealness when it comes to figuring out how many registers your OS simulator should have. I want to avoid "unlimited" registers if at all possible, since that isn't realistic in actual hardware.

You need to make your question a bit more precise.

First, regarding your request to avoid "unlimited" registers -- I assume you mean registers that can hold an arbitrary value (e.g., any natural number).

If you a-priori bound your registers, then the possible states your machine can be in is finite. That is, you have a deterministic finite automaton (or transducer, if you allow inputs and outputs). In this case, you don't need any register, but the machine would be huge without them. For example, you can replace 32 binary registers with $2^{32}$ states.

If you do allow arbitrary values, then 2 counters suffice to simulate a Turing Machine using a Minsky Counter Machine, under certain assumptions.


Decidable language that has no finite description? A language is a collection of strings--assuming we have an infinite number of words then concatenating this collection (keeping things simple,  normally you need to at least be able to tell where one word ends and another begins) and viewing the language as the resulting single big string, if the Kolmogorov complexity of this string is infinite can the language still be decidable?
This is asking if a language without a finite description can be decidable...also maybe sort of like asking if a language that is not constructible can still be decidable?
If I were to guess, I would say why not..? For example, a language could be given to you as an infinite table of rules (programs) for membership (that, per our condition above, can't be compressed into a smaller set of rules) paired with all words, but have only a finite number of the them be conditions for any particular word or group of words to be members. It is not your job to build such a table but once given such a table you could, when given a word, seek the rule in the table corresponding to that word (if the table is neatly organized this should be possible as to decide any particular word you ever only need to access a finite position on the table), check that word against that rule (run the program that is there on its word), and if doing so is computable for every rule in the table then the language specified by the infinite table should be decidable but at the same time not necessarily be finitely expressible.
Thanks!

Unless you want to be more rigid in what you allow as a "description", every decidable language has a finite description - precisely the Turing machine that decides it. This Turing machine must exist (otherwise the language would not be decidable).
Although we often thing of automata as machines that do work, mathematically they're just a way of, in a certain sense, compressing the table that says "yes" or "no" for every string (over the given alphabet).


Integer Knapsack Problem - No duplicates Allowed In the bounded Integer Knapsack problem, we are given N items of sizes S1 through SN, having values V1 through VN. The problem requires us to find the maximum value that can be attained for a given capacity C, provided we cannot use an already used item twice.

In their book, Introduction to Algorithms, the authors have mentioned that for Dynamic programming to be applicable we MUST have "independent" subproblems. That is, the solution to one subproblem should not affect another subproblem. They have illustrated this through the "Longest-Path-Problem" in which they mention that once we solve a subproblem of finding the longest path from 'A' to 'B', for solving another subproblem, we would not be able to use the vertices used in the longest path from 'A' to 'B' and hence the subproblems are not independent.

Doesn't the same argument apply here as well - If we solve a subproblem of filling a smaller knapsack of capacity c < C, we cannot use the items used in filling 'c', in solving other subproblems.

I am new to dynamic programming - apologies if my question appears to be stupid.

Thanks.

You are right about "independence" between subproblems. Therefore, you use the new subproblems (wiki) by introducing another variable $i$, meaning using the items up to $i$:

  Define $V[i,s]$ to be the maximum value ($V$) that can be attained with size less than or equal to $s$ using items up to $i$ (the first $i$ items).


Algorithm for generating random incrementing numbers up to a limit I'm trying to write a code to generate incremental sequences of numbers such as:

0 + 1 + 3 + 5 + 1 = 9
0 + 5 + 1 + 1 + 1 = 8
0 + 1 + 1 + 2 + 1 = 5

I have 3 constraints:

1) I need to have limited number of addends (here it is =5)

2) final sum must be smaller than certain limit ( here limit is <9)

3) addends must be random

As for now, I generate sequences randomly and select only suitable ones. For 2-digit numbers and for long sequences (>8) my algorithm takes significant time.

Is there a better algorithm for such problem?

As least could you tell me, what branch of CS is studying such problems?

UPDATE (algorithm):

0) array = [0,]; // initial array
1) if sum(array) > 99, go to 6)
2) generate random number in [1..99], let's say rand = 24
3) rand = array[-1] + rand // add random number to last value of array
4) array.push(rand) // add the random number to array
5) goto 1)
6) if length(array) < 5, goto 0) // 5 is desired sequence length

-- generate ALL sequences of n natural numbers with given sum
-- should be called with n<=sum
gen(n,sum):
  for i in 1..sum-n+1:
    -- next number in sequence is i
    gen(n-1,sum-i)  -- generate ALL possible sequences of remaining numbers


Why is log(n) a space-constructible function? According to "Constructible function", Wikipedia:

  In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f(n) can be constructed from n by a Turing machine in the time of order f(n).

But $\log\left(n\right)$ doesn't map onto natural numbers but to real numbers.

Why is $\log\left(n\right)$ nevertheless a space-constructible function?

Because when we write $\log n$ it's either in a context where it doesn't matter (e.g. Landau bounds) or with the implicit meaning of $\lfloor \log n \rfloor$ or $\lceil \log n \rceil$.

It certainly doesn't make sense to talk about constructible functions with real range, I would assume your source is talking about $\lfloor \log n \rfloor$ or $\lceil \log n \rceil$.


What does "prime" mean in this context? In a lecture video the instructor introduced the quadratic probing method for hash tables. The formula he gave was the following:

$h(k,i) = (h'(k) + c_1 + c_2i^2)$ $\% M$

where $h'$ was h "prime". So, what I am supposed to conclude for $h'(k)$ to be? Is it any different from the value I get by computing $h(k)$

$h'(k)$ is the value returned by the original unmodified hash function when applied to the element $k$. If the $h(k)$ slot is not free then $h(k,i)$ for $i=0,1,2,\dots$ gives a sequence of modified hash values which can be tried in turn until a free slot is found.


CFG to PDA - no empty transitions Working for my exam, this question popped up.

  Given the production rules below, draw a pushdown automaton to recognise the language it generates:
  S → AB
  A → BA
  B → BB
  B → T
  T → b

Questions:
1. Since A has no empty transition, wouldn't this just end up in an infinite loop?
2. What order are the values entered into the stack.
If first you enter S, would it then be B at top of the stack and A at bottom or the other way around?
3. Below is my current interpretation of the PDA. Is it correct? Or does the question ask for the transition table?

This grammar will in fact get into an infinite loop because there is no transition for A to turn into a terminal.


Is there a relationship between visitor pattern and DeMorgan's Law? Visitor Pattern enables mimicking sum types with product types. Where does the "sum"-iness come from?
For example, in OCaml one could define type my_bool = True | False
Or encode with visitor pattern:
type 'a bool_visitor = {
  case_true: unit -> 'a;
  case_false: unit -> 'a;
}

let t visitor = visitor.case_true ()
let f visitor = visitor.case_false ()

let visitor = {
  case_true = (fun () -> "true");
  case_false = (fun () -> "true");
}

let () = print_endline (t visitor) (* prints "true" *)

What's the best way of explaining the sum-type-to-visitor-pattern transformation? Is it:

Of course + and * are interdefinable, what did I expect?
Or is it that the left side of -> is the "negative" position and that this leads to a DeMorgan-law-like flip of sum and product?

I also wonder if this question is related to how one can use universally-quantified types to mimic existential types.

The best way to explain it is
$$\mathsf{Bool} \to C \cong C \times C,$$
which is a special case of
$$(A + B) \to C \cong (A \to C) \times (B \to C).$$
Read the above as follows: as sum is equivalent to a pair of visitors.
(By the way, this is not the de Morgan law. It does not have a name, as far as I know. It's a general consequence of the definition of the concepts involved.)


Distribution algorithm according to weighted parameters (with a min-max constraint) I'm trying to solve the following problem related to distribution-

I have a list L of items (I1, I2,....In) sorted in order of importance, I1 being the most important. Each item has multiple tags assigned to it and the combination of these tags can be different on each item, so I1 may have tags T1 and T2, I2 can have tags t2, t3 and t4, and I3 can have tag T1, and so on.

Now, I have to make batches from this list L, with a distribution of items (according to the tags) subject to the following constraints-

Each batch has a fixed size B
Each tag has a range of items in the batch distribution, ranging from a minimum to maximum. So, B should contain minimum x1 items with tag t1, x2 items with tag t2, and maximum y1 items of t1, y2 items of t2 and so on.
We start picking items from the top of L and keep filling the batch until we reach the final distribution that satisfies the constraints. If, say, L has 300 items, and we have to make a batch size of 50, we can go until any number of items in the list and pick the items to make the desired distribution.
Remember that if an item is picked from the list, count of all the tags assigned to it goes up by 1.
I was thinking of a solution where in first, I make lists of items corresponding to each specific tag. I pick the minimum desired items for a particular tag from its list. So, I'd pick x1 items with tag t1 from the list of items with tags t1, irrespective of whether the items contain any other tag. This way I'd ensure that the 'minimum' criteria of all the tags are satisfied. But for the max part, each tag will most definitely go overboard. How do I recursively keep replacing items from the batch with the remaining items in L to make the final desired distribution?

Any other solution would be great. Or any existing algorithm that can get me in the right direction to approach this problem.

I know the question is a bit too wordy, and probably a bit confusing, but I'v tried to explain it as well as I can, and of course, the problem might be a lot interesting I suppose.

Let me repeat my understanding of the problem (as I understand it), then sketch a candidate solution approach.  If I've misunderstood the problem, you might need to revise the question to clarify.

The problem: You have $n$ items, and want to divide them into $n/B$ batches of $B$ items.  Presumably, $n$ is a multiple of $B$.  Each item has some set of tags (a subset of $\mathcal{T}$, where $\mathcal{T}$ denotes the set of all possible tags).  For each batch, we're given a function $f:\mathcal{T}\to \mathbb{N}$; we want to ensure that, for each candidate tag $t \in \mathcal{T}$, there are at least $f(t)$ items in the batch with tag $t$.  The question is to identify a valid division into batches, if one exists.

One candidate solution: we can formulate this as an integer linear programming problem.  Let $x_{i,j}$ denote a 0/1-valued variable that is $1$ if item $i$ is placed into batch $j$, and 0 otherwise.  Now we can write down some constraints on the $x$'s that correspond to the problem description.  We get

$$0 \le x_{i,j} \le 1$$

$$\sum_j x_{i,j} = 1$$

$$\sum_i x_{i,j} = B$$

$$\sum_{i \in S_t} x_{i,j} \ge f(t)$$

for all $i,j,t$.  Here $S_t$ denotes the set of items with tag $t$.  You can now use an off-the-shelf integer linear programming solver to search for a solution to this problem.

If I didn't understand your problem quite right, I hope you see the basic idea of my solution and hopefully you'll be able to come up with the appropriate tweaks to address any misunderstandings I might have had about what problem you were looking to solve.


Dijkstra algorithm vs breadth first search for shortest path in graph I have asked this question in StackOverflow. I was asked to move in here. so here it is:

I need some clarifications and inputs regarding Dijkstra's algorithm vs breadth first search in directed graphs, if these are correct.

Dijkstra's algorithm finds the shortest path from Node A to Node F in a weighted graph regardless of if there is a cycle or not (as long as there are no negative weights)

but for that, All paths from A to all other Nodes in the graph are calculated and we grab the path from A to F by reversing the sequences of nodes in prev.

BFS: finds the shortest path from node A to node F in a non-weighted graph, but if fails if  a cycle detected.

however, BFS just calculates the path from Node A to Node F and not necessarily all path from Node A.
if Node F is reached early, it just returns the path.

BFS does not fail if a cycle is detected. http://en.wikipedia.org/wiki/Breadth-first_search
Dijkstra's doesn't calculate all paths from A to F either. It stops when it finds the shortest path from A to F.
In an unweighted graph, you can use BFS to search for the shortest path from A to all other nodes in the same run too! (just don't make it stop as soon as it finds F)
You can use a BFS type algorithm to find the shortest path if you know all lengths are integers less than a 'small' number k in O(k(v+e)) time by replacing every edge (u,w) of length n with a path of n-1 nodes between u and w, the length of each edge in the path is 1.

Hope this helps.


Calculating force between n points placed on the x-axis There are $n$ charges placed on the x-axis at points $1,2,3,\dots,n$.
We need to calculate the force on each charge by every other charge.
I need the exact force. Charges can be arbitrary. Inputs are the charges possibly in the form of an array.
Force is defined in the usual physical way.

I know an $O(n^2)$ algorithm to do the task. However, it can be done in $O(n\log n)$.

I have read about FFT, but I don't know how to apply it here. I know that we can multiply two degree $n$ polynomials in $O(n\log n)$. This problem is similar to that problem. Any help will be appreciated.

Suppose that the charges are $q_1,\ldots,q_n$. You need to calculate, for all $i$,
$$
F_i = q_i \sum_{j>i} \frac{q_j}{(i-j)^2} - q_i \sum_{j<i} \frac{q_j}{(i-j)^2}.
$$
In matrix form, we get
$$
\begin{bmatrix}
F_1/q_1 \\ F_2/q_2 \\ \vdots \\ F_n/q_n
\end{bmatrix} =
\begin{bmatrix}
0 & 1 & \frac{1}{4} & \frac{1}{9} & \cdots & \frac{1}{(n-1)^2} \\
-1 & 0 & 1 & \frac{1}{4} & \cdots & \frac{1}{(n-2)^2} \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
\frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \frac{-1}{(n-4)^2} & \cdots & 0
\end{bmatrix}
\begin{bmatrix}
q_1 \\ q_2 \\ \vdots \\ q_n
\end{bmatrix}
$$
What the FFT allows us to do is to quickly multiply by a circulant matrix. In order to obtain a circulant matrix, all you have to do is add $n-1$ dummy coordinates:
$$
\begin{bmatrix}
F_1/q_1 \\ F_2/q_2 \\ \vdots \\ F_n/q_n \\ \ast \\ \vdots \\ \ast
\end{bmatrix} =
\begin{bmatrix}
0 & 1 & \frac{1}{4} & \frac{1}{9} & \cdots & \frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \cdots & -1 \\
-1 & 0 & 1 & \frac{1}{4} & \cdots & \frac{1}{(n-2)^2}  & \frac{1}{(n-1)^2} & \cdots & \frac{-1}{4} \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
\frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \frac{-1}{(n-4)^2} & \cdots & 0 & 1 & \cdots & \frac{1}{(n-1)^2} \\
\frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2}  & \cdots & -1 & 0 & \cdots & \frac{1}{(n-2)^2} \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
1 & \frac{1}{4} & \frac{1}{9} & \frac{1}{16} & \cdots & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \cdots & 0
\end{bmatrix}
\begin{bmatrix}
q_1 \\ q_2 \\ \vdots \\ q_n \\ 0 \\ \vdots \\ 0
\end{bmatrix}
$$
We don't really care about the $n-1$ asterisked entries. The new matrix is $(2n-1)\times(2n-1)$, and so FFT still runs in $O(n\log n)$. Of course, if your FFT works only for powers of 2, you need an extra padding step.


Complexity of multiplication I've been reading around the area of complexity and arithmetic operations using logic gates; one thing that is confusing me is that
\begin{equation}
\Theta (n^{2})
\end{equation}
is quoted as being the complexity for multiplication for iterative adition. But addition of a number requires \begin{equation}
log_2(n)
\end{equation}
operations, 1 for each bit or 8 times that for each nand gate involved in doing this. So it strikes me as obvious that adding that number n times will have a complexity of
\begin{equation}
n \log_2(n)
\end{equation}
Which is definitely less than
\begin{equation}
\Theta (n^{2})
\end{equation}
So where is this additional factor of
\begin{equation}
\frac{n}{\log_2(n)}
\end{equation}
coming from?

Addition of a number of size $n$ takes time $O(n)$. Don't confuse a number and its encoding size, which is logarithmically smaller.

When multiplying an $n$-bit integer $a$ by an $n$-bit integer $b$ using the iterative addition algorithm, you are adding up to $n$ shifted copies of $a$. Each addition costs you $O(n)$ rather than $O(\log n)$. The numbers $a,b$ itself could be as large as $2^n$.


What is the exact definition of undirected graph, directed graph, unidirectional graph, bidirectional graph? I've read many literature papers, but I still cannot understand their exact formalization definitions. Is their any difference among them or is there any relationship among them?

I've only ever heard of directed and undirected graphs, whose definitions can be found in Wikipedia. Rudimentary search reveals the following interpretations of unidirectional and bidirectional graphs; it is possible that these terms also have different interpretations:

A unidirectional graph is another name for an undirected graph.
A bidirectional graph is a directed graph obtained from an undirected graph by replacing each edge $\{x,y\}$ by a pair of edges $(x,y),(y,x)$.


Fast multiplication with a full binary $n \times 2^n$ matrix Let $A$ a $n\times n$ matrix, and X the full matrix of $n\times 2^n$ binary vectors (you can choose the order of the columns of X).

What is the fastest way to compute the product AX?

Suppose that $A$ were a $1 \times n$ matrix, let $X_n$ denote your matrix for a given value of $n$, and let $A_{<n}$ consist of all but the last entry $A_n$ of $A$. Then up to rearrangement,
$$
AX_n = \begin{bmatrix} A_{<n} X_{n-1} & A_{<n} X_{n-1} + A_n \end{bmatrix},
$$
where $+A_n$ means adding $A_n$ to all entries. The running time of this procedure satisfies the recurrence
$$
T(n) = T(n-1) + O(2^{n-1}),
$$
whose solution is $T(n) = O(2^n)$, which is linear in the size of the output. This should be compared to the trivial $O(n2^n)$ solution.

You can save a factor of $n$ in your case in the same way. The resulting algorithm is asymptotically optimal.


"Applicative order" and "Normal order" in lambda-calculus Applicative order: Always fully evaluate the arguments of a function
  before evaluating the function itself , like -

  $(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x.
 x^2(2+1))\rightarrow \  (\lambda x. x^2(3)) \rightarrow \  3^2 \
 \rightarrow \ 9$

  Normal order: The expression would be reduced from the outside in ,
  like  -

  $(\lambda x.x^2 (\lambda x.(x+1) \  2)) \rightarrow \ (\lambda x.(x+1)
 \ \ \   2)^  2 \rightarrow\ (2+1)^2 \ \rightarrow 3^2 \ \rightarrow \
 9 $

Let $M = (\lambda x.y \  (\lambda x.(x \  \ x) \  \lambda x.(x \ \  x)))$

Why is it that under applicative order, $M \rightarrow$  infinite loop,
but under normal order, $M \rightarrow y$?

The term you are reducing is $(K_y \Omega)$ where $K_y$ is the constant function $\lambda x. y$ (it always returns $y$, ignoring its argument) and $\Omega = (\lambda x. (x \, x) \: \lambda x. (x \, x))$ is a non-terminating term. In some sense $\Omega$ is the ultimate non-terminating term: it beta-reduces to itself, i.e. $\Omega \to \Omega$. (Make sure to work it out on paper at least once in your life.)

Applicative order reduction must reduce the argument of the function to a normal form, before it can evaluate the top-level redex. Since the argument $\Omega$ has no normal form, applicative order reduction loops infinitely. More generally, for any term $M$, $M \Omega \to M \Omega$, and this is the reduction chosen by the applicative order strategy.

Normal order reduction starts by reducing the top-level redex (because the function $K_y$ is already in normal form). Since $K_y$ ignores its argument, $(K_y \Omega) \to y$ in one step. More generally, $K_y N \to y$ for any term $N$, and this is the reduction chosen by the normal order strategy.

This case illustrates a more general phenomenon: applicative order reduction only ever finds a normal form if the term is strongly normalizing, whereas normal order reduction always finds the normal form if there is one. This happens because applicative order always evaluates fully arguments first, and so misses the opportunity for an argument to turn out to be unused; whereas normal order evaluates arguments as late as possible, and so always wins if the argument turns out to be unused.

(The flip side is that applicative order tends to be faster in practice, because it's relatively rare for an argument to be unused; whereas it's common for an argument to be used multiple times, and under applicative order the argument is only evaluated once. Normal order evaluates the argument as often as it's used, be it 0, 1 or many times.)


Proving that $ (a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$? How would I prove that these two regexes are equal to one another? $$ (a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$$

I'm permitted to use the following regular expression identities.

One of the equalities 12 tell us that now
$(u\cup v)^* = u^*(vu^*)^*$.
Applying this to the last expression we obtain
$(b\cup (a\cup\lambda))^*$.

Also $(u\cup \lambda)^* = (u^*\lambda^*)^* =
(u^* \lambda)^* = (u^*)^* = u^*$.

Do you have associativity of $\cup$ so that $(b\cup (a\cup\lambda))^* = ((b\cup a)\cup\lambda))^*$? It should be a basic property.


Big O notation for Sorting Algorithm I am interested to know whether the time complexity of following algorithm is  $O(n^2)$ or $O(n\log n)$.

Here is the implementation:

public class HelloWorld
{

 public static void main(String[] args)
 {

    Hello hw = new Hello();
    int[] n = {2,3,4,52,5,63,0,664,2,2,56,68,8};
    hw.sortUsingDLLWODup(n);
 }
}

public class Node
{
   public int value;
public Node next;
public Node prev;
public Node(int v) {
    value = v;
}
}

public class Hello
{

public void sortUsingDLLWODup(int[] n) {

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0;i<n.length;i++) {
if(max<n[i])max = n[i];
if(min>n[i])min = n[i];
}

Node root = new Node(min);
Node end = new Node(max);
root.next = end;
end.prev = root;

for(int i = 0;i<n.length;i++)
{
    Node current = root;
    while(n[i]>current.value && current!=null) {
        current = current.next;
    }
    if(current!=null&&current.value>n[i]) {
        Node temp = current.prev;
        Node newNode = new Node(n[i]);
        temp.next = newNode;
        newNode.prev = temp;
        newNode.next = current;
        current.prev = newNode;
    }
}
Node test = root;
while(test!=null){

System.out.println(test.value);
test = test.next;
  }
}
}

You will have $O(n^2)$ in worst case. Actually what you do is really close to insertion sort. Worst case is attained when you got the array in decreasing order.

\begin{align}
T(n) &= T(n-1) + n\\
&=T(n-2) + n-1 + n \\
&= \vdots \\
&=T(n-k) + \sum_{i=0}^k (n - i)
\end{align}
Algorithm terminates at $k = n$, i.e. we shall get
$$T(n) = T(0) + \sum_{i=0}^n (n - i)$$
where $T(0) = O(1)$. So, upon a change of variable, we get
 $$T(n) = \sum_{i=0}^n i = \frac{n(n+1)}{2} = O(n^2)$$


Why is the set of all regular expressions classified as context-free, instead of regular? As I understand regular languages can be closed under concatenation, so can I concatenate the set of all regular expressions to classify them as regular?

Going by the OP's comments, the real question here is not the one in the title, but "Why is the set of regular expressions a context-free (rather than regular) language?"

The reason is simply the occurrence of parentheses in more complex regular expressions like $(a+b)^*b(a+c)^*$. In order for such an expression to be well-formed, the parentheses must be balanced properly; this is one of the classical conditions which make a language non-regular (because a r.e. which begins with sufficiently many opening parentheses can always be pumped such that it becomes unbalanced).


Sum of unique elements in all sub-arrays of an array Given an array $A$, sum the number of unique elements for each sub-array of $A$.  If $A = \{1, 2, 1, 3\}$ the desired sum is $18$.

Subarrays:

{1} - 1 unique element
{2} - 1
{1} - 1
{3} - 1
{1, 2} - 2
{2, 1} - 2
{1, 3} - 2
{1, 2, 1} - 2
{2, 1, 3} - 3
{1, 2, 1, 3} - 3

I have a working solution which sums the unique elements for all sub-arrays starting at index $0$, then repeats that process at index $1$, etc. I have noticed that for an array of size $n$ consisting of only unique elements, the sum I desire can be found by summing $i(i + 1) / 2$ from $i = 1$ to $n$, but I haven't been able to extend that to cases where there are non-unique elements.  I thought I could use that fact on each sub-array, but my control logic becomes unwieldy.  I've spent considerable time trying to devise a solution better than $O(n^2)$ to no avail.  Is there one?

Secondary question:  if there is no better solution, are there any general guidelines or hints to recognize that fact?

Hint: Use an extra $O(n)$-spaced array of pointer to the last (biggest) index of each distinct value. Then, this array is very helpful when you do your above algorithm.

Lastly, we should have an $O(n)$ algorithm.


Find optimal local alignment of two strings with restrictions I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.
The problem:
We want to find an optimal local alignment of two strings S1 and S2, we know that there exists such an alignment
with the two aligned substrings of S1 and S2 both of length at most q.
Besides, we know that the number of the table cells with the maximal value, opt, is at most r.
Describe an algorithm solving the problem in time O(mn+r*q^2) using working space of at most
O(n+r+q^2).
Restrictions: run the algorithm of finding the optimal local alignment value, with
additions to your choice (like the list of index pairs), only once. Besides, you can run any variant of the algorithm for solving the global optimal alignment problem as many times as you wish
I know the solution to this problem with running the local alignment many times and the global alignment only once, but not the opposite.
the global alignment algorithm:

the local alignment algorithm:

Any help would be appreciated.

Compute the optimal local alignment score OPT of both strings in $O(mn)$ time and $O(n)$ space by maintaining just a single row of the DP matrix. (Since we are only computing the score and don't need to perform traceback to build the full solution, we don't need to keep the full DP matrix.) As you do so, keep track of the highest cell value seen so far, as well as a list of the coordinates $(i, j)$ of cells having this value. Whenever a new maximum is seen, clear the list and update the maximum. Whenever a cell $\ge$ the current maximum is seen (including in the case where we just saw a new maximum), add the coordinates of the current cell to the list. At the end, we have a list of endpoints of all optimal local alignments; by assumption, there are at most $r$ of these.
For each entry $(i, j)$ in the list:

Set $R1$ to the reverse of the substring $S1[i-q+1..i]$, and $R2$ to the reverse of $S2[j-q+1..j]$.
Perform optimal global alignment of $R1$ and $R2$ in $O(q^2)$ time, maintaining the full $O(q^2)$ DP matrix this time.
Search for the highest entry in the matrix (also $O(q^2)$ time; or you can perform this during the previous step).
If this entry is OPT, we have found a solution: Trace back towards the top-left corner from this cell to find the full solution, reverse it, and output it, and stop.

By assumption, at least one of the alignments performed in the previous step reaches a score of OPT. (Note that reversing both strings does not change the score of an alignment.)
Step 2 iterates at most $r$ times, and does $O(q^2)$ work each time, using at most $O(q^2)$ space, so overall the time and space bounds are met.
(A simpler way, that avoids reversing strings, would be to simply perform local alignments of the length-$q$ substrings, but the restrictions appear to forbid this.)


A problem similar to bin packing Let's say we have $n$ items of size $si_i$ and $m$ containers, each has a capacity $sc_i$. Every container can have at most one item at a time, provided its size is less than or equal its capacity.

Now we add time axis to this problem, because otherwise it would be trivial. Every item $i$ starts to exist at time $t_{i1}$ and ceases to exists at $t_{i2}$. You could visualize this with Gant diagram. There are no limitations of how many items may exist simultaneously, or anything like that. All we know that every item has its birth and death time. Also $t_{i1}, t_{i2} \in \{0,1,2,...,59\}$ and $t_{i2}>t_{i1}$. These are all constraints on $t_{i1}$ and $t_{i2}$

How to assign containers to all items, assuming the solution exists? The naive approach is to assign the smallest possible container to every item, but the order does matter:

If the are two avaliable containers $c_1$ and $c_2$ of capacity $sc_1=10$ and $sc_2=12$, if $c_1$ is assigned to the 1st item (because it's the smallest available container), and $c_2$ to the 2nd item (again, the smallest available container), the 3rd item won't have any available container. However if you assign the smallest container to 2nd and then 1st item, there will also be a container of capacity $12$ for the 3rd item, because it won't be blocked by the 2nd item.

Does this problem as a name already? And is there any simple algorithm to solve it, except brute force?

Your problem belongs to the family of problems known as fixed interval scheduling. For a recent survey, see Kovalyov et al. A classical paper of Arkin and Silverberg solves the problem when all sizes or capacities are the same, and shows that if you generalize the notion of size then the problem of deciding whether all jobs (i.e., items) can be scheduled (i.e., stored) is NP-complete, though it has an $O(n^{k+1})$ solution, where $n$ is the number of jobs and $k$ is the number of machines (i.e., containers).

Your problem is easier than the NP-complete variant considered by Arkin and Silverberg:

Your constraints on which jobs can be scheduled on which machines are not arbitrary – they depend on the notion of size.
Your timeframe is short.
You are guaranteed a solution. (Though this doesn't usually make the problem any easier.)

The literature on the problem is probably vast, so perhaps someone already considered your particular variant.


Formalization of the shortest path algorithm to a linear program I'm trying to understand a formalization of the shortest path algorithm to a linear programming problem:

For a graph $G=(E,V)$, we defined  $F(v)=\{e \in E \mid t(e)=v \}$ and $B(v)=\{ e \in E \mid h(e)=v\}$ where $t(e)$ is a tail of a node, and  $h(e)$ is a head of a node.

Also the solutions for the conditions for the linear problem was defined as $b_v=1$ for every node $v$ except of the root $r$ which from it we find all the shortest paths in the graph where $b_r=-(n-1)$. It is written here "We associate a flow (primal variable) $x_e$ with each arc $e \in E$.

The main linear program is to minimize $\sum\limits_{e\in E }c_ex_e$, subject to $\sum\limits_{e\in B(v)}x_e-\sum\limits_{e\in F(v)}x_e=b_v$ for all $v \in V$ and $x_e \geq 0$ for all $e \in E$, where $c_e$ is the length of arc $e$.

I'd really love your help with understanding what does $x_e$ represent. Is it the number of times I use $e$ in order to find all the shortest paths in the graph?

I don't understand why does the above condition for this linear program is as at it, why does  $\sum\limits_{e\in B(v)}x_e-\sum\limits_{e\in F(v)}x_e=b_v$ for all $v \in V$ should  be $1$ for every node and $-(n-1)$ for the all the root? If I think of a $3$ nodes tree for a graph,for  the middle node we get that the condition equals to $1$, which makes me think that I might be misunderstood what $x_e$ stands for.

This formalization takes Dijkstra's algorithm and formalizes it as a network flow problem.

In the network flow problem, $b_i$ represents the amount of flow that enters or leaves a network at vertex $i\in V$. If $b_i > 0$ we say that $i$ is a source supplying $b_i$ units of flow. If $b_i < 0$ we say that $i$ is a sink with a demand of $|b_i|$ units of flow. Here $B(v)$ are $v$'s outgoing edges and $F(v)$ are $v$'s incoming edges. So the condition $\sum_{e\in B(v)} x_e - \sum_{e \in F(v)}x_e = b_v = 1$ means that I'm allowed to supply $1$ more unit of flow coming out of $v$ than going into $v$.

Now in the network flow algorithm I'm pushing flow into the sink node, in this case the root $r$. Since each node can supply only $1$ unit of flow, the amount of flow going into $b_r$ is $n-1$. So these equations are satisfied when each node pushes it's one unit of flow down to the sink node, enforcing that we find the shortest path from every node to $r$. Now you can see that $b_r=-(n-1)$ means that it expects the $1$ unit of flow from every node.

From this it should be easy to see that $x_e$ represents the number of times you've travelled along the edge $e$ in every shortest path. The minimum cost flow problem asks for flows $x_e \in \mathbb{R}^{n\times n}$ that conserve the flow at each vertex and minimize your objective function $\sum_{e\in E} c_e x_e$. So if $x_e$ is the number of times you've used the edge $e$ in all the shortest paths and $c_e$ is the cost of pushing $1$ unit of flow across $e$ (i.e. the length of $e$), then $\sum_{e\in E} c_e x_e$ is summing the cost of every edge used across all the shortest paths.

Let's take an example with three nodes and a graph that looks like 0--1--2.

Assume that 2 is the root and each edge is unit length. So the shortest path for vertex 0  is 0--1--2 and the shortest path for vertex 1 is 1--2. So I used 0--1 once and 1--2 twice. This satisfies the equations that the units of flow going into a vertex must be one less than those going out. Additionally we have $-2$ units of flow going into vertex $2$, so that equation is satisfied as well. The objective function then sums to $3$ which is our minimum flow cost.


Difference between BTSP and TSP I am wondering what is the difference between Bottleneck Travelling Salesman Problem and normal Travelling Salesman Problem?

Thank you

BTSP asks to find a Hamiltonian cycle in a weighted graph, which minimizes the weight of its most weighty edge.

TSP asks to find a Hamiltonian cycle in a weighted graph, which minimizes the sum of weights of its edges.


Notation for asymptotic bounds on both sides I am writing my first paper, and one of the results can be written as follows:

  For any $W,\epsilon$ such that $\epsilon = o\left(\frac{\log^4 W}{W\log\log W}\right)$ and $\epsilon=\omega\left(\frac{\log\log W}{W}\right)$, we obtain a $o(\min \{W, \frac{1}{\epsilon}{\log^2 W}\})$ space algorithm, improving the state of the art.

Is there some standard notation, say $\Gamma$, so I could write:

  For any $W$ and $\epsilon=\Gamma\left(\frac{\log\log W}{W}, \frac{\log^4 W}{W\log\log W}\right)$, ...

?

Will appreciate any help !

I'm also not aware of any specific notation for the concept you want. In the example theorem statement in the question, there's nothing wrong with what you already have ("$\epsilon$ such that $\epsilon=o(\cdots)$ and $\epsilon=\omega(\cdots)$"). In other situations, it might be more convenient to say something like, "For any $\epsilon\in o(\cdots)\cap\omega(\cdots)$".


Why is this not recognized by a DFA? I am still confused over my professor's explanation on why this problem is not a DFA.

The Problem: Explain why $L = \{p^kq^k \mid k>0\}$ cannot be recognized by a DFA

My professor explained it as that it was because the DFA could not store the $k$ iterations in memory. But I still don't get it. In my mind, you just draw states $k$ number of times for $p$ and then $q$.

What's wrong with my logic?

The actual claim is that there is no DFA for the language $\{p^kq^k\mid k\geq 0\}$. Such an automaton would have to accept every string of the form $p^kq^k$ for any $k$, and reject every other string.

For any one fixed value of $k$, you're absolutely right that you can use $2k$ states to count off the $p$'s and the $q$'s. However, to recognize the language, the automaton would have to be able to do this for infinitely many different values of $k$, which would require infinitely many states by this method. Of course, that's not allowed in a deterministic finite automaton.

Note that this isn't a formal proof that no DFA can accept this language; rather it's just an intuition about why you should expect there to be no DFA. To formally prove the claim, you'd have to use something like the pumping lemma or Myhill–Nerode; we have a reference question about how to do that.


Running time of algorithm (effect of j*j in for loops) - Theta Runtime In Theta notation what are the running times of these algorithms?
Algorithm 1
for i=1..n
    j=1
    while j*j <= i:
        j = j + 1

Since the outer loop is going to n and the inner loop is going to sqrt(n). My guess is that it is Θ(n^2)
$$
\sum_{i=1}^{n} O(1) \sum_{j=1}^{\sqrt n}O(1)
= \sum_{i=1}^{n} \sqrt j*\sqrt j
= \theta(n^2)
$$
Thought process for the summations: number of terms * max term
Algorithm 2.
for i=1..n
    j=2
    while j <= i
        j = j * j

j performs similar to a log function. Since the outer loop is n. My guess is $Θ(n\log n)$
$$
\sum_{i=1}^{n} O(1) \sum_{j=2}^{\log n}O(1)
= \sum_{i=1}^{n} (\log n -2) * O(1)
= \theta (n * (\log n -2))
= \theta (n\log n)
$$

1
For the first case, you had the right idea, but just had some algebra mistakes.
for i=1..n
    j=1
    while j*j <= i:
        j = j + 1

Let $T(n)$ be the time complexity.
$$T(n) = \sum_{i=1}^n\sum_{j=1}^\sqrt{i}1\leq  \sum_{i=1}^n\sqrt{n}=\leq n^{3/2}$$
$$= O(n^{3/2})$$
2
I'm assuming you meant the pseudocode below since it is more analogous to your first case (I believe the pseudocode you posted has the same complexity). You are correct though, it is $O(n\log n)$ for the reason you described.
for i=1..n
    j=2
    while j <= i
        j = j * j


Sorting an "almost sorted" array in sub linear time I am given an "almost sorted" array with the condition that each element is no more than $k$ places away from its position in the sorted array. I need to show that it is impossible to sort this array in sublinear time asymptotically.

My proof is to suppose a sorted array of length $n$.
Now assume that every second element is swapped with the element on its left.
The new array is almost sorted. To sort it would require a minimum of $n/2$ swaps - asymptotically linear amount of operations. Therefore, no sublinear sorting algorithm exists.

Is this proof correct?

It is correct, but you should be careful to stipulate that the swaps are performed in a non overlapping fashion; if the swaps overlap then one element can be carried across the array breaking the guarantee.


Deriving from a terminal word in a context free grammar Just to make it clear.
(since my book doesn't mention anything like this)

Suppose we have a context free grammar $G=(V,T,P,S)$.
where $T=\{a,b\}$ (The other sets doesn't really matter).

Since $\Rightarrow^*$ is the reflexive transitive closure of the relation $\Rightarrow$ on the set $(V\cup T)^*$, I see no problem in writing a thing like $ab \Rightarrow^* ab$ (where $ab\in T^*$ and there are no variables on the left hand side of the arrow) since the $\Rightarrow^*$ relation is reflexive.

Now I want to ask wether it common to write a thing like $ab \Rightarrow^* ab$?

By definition I see no problem.

Thanks.

There is absolutely no problem writing $ab \Rightarrow^* ab$. It definitely happens in proofs.


Bottom up chart parser adding active arc step I am following Bottom up chart parsing algorithm from  Natural Language Understanding book by James Allen. It is

I couldn't understand the 3rd step. I thought that when active arc is added the dot is advanced. But dot is indroduced in the third step. The example says that

This example shows dot is advanced. But step 3 says otherwise

You have spotted a typo in that book.

The dot $\circ$ in step 3 of figure 3.11 should be after constituency C. To be explicit and precise, step 3 should be stated as the following.

  For each rule in the grammar of form X $\to$ C X$_1$ ... X$_n$, add an active arc of form X $\to$ C $\circ$ X $_1$ ... X$_n$ from position P$_1$ to P$_2$.

As you have observed, all examples following figure 3.11 show clearly that the dot $\circ$ are placed after constituency C.

This can also be verified by the statement a few lines below.

  Notice that active arcs are never removed from the chart.

We can check that we cannot, indeed, find any instance of an active arc in all of section 3, chapter 3 of the book that starts with a $\circ$.

There is also a rule that for each active arc from position $a$ to $b$, the symbols before the $\circ$ should correspond to the terminals between those positions inclusively. That rule also implies that a dot $\circ$ cannot be at the very front of an active arc.

By the way, that books is written so clearly that I have to say that glaring typo is an almost reverse testimonial.


Higher-ranked polymorphism without explicit application or subtyping? So, I'm familiar with two main strategies of having higher-ranked polymorphism in a language:

System-F style polymorphism, where functions are explicitly typed, and instantiation happens explicitly though type application. These systems can be impredicative.
Subtyping-based polymorphism, where a polymorphic type is a subtype of all of its instantiations. To have decidable subtyping, polymorphism must be predicative. This paper provides an example of such a system.

However, some languages, like Haskell, have impredicative higher-ranked polymorphism without explicit type applications.

How is this possible? How can type-checking "know" when to instantiate a type without an explicit instantiation or cast, and without a notion of subtyping?

Or, is typechecking even decidable in such a system? Is this a case where language like Haskell implement something undecidable that happens to work for most peoples' use cases.

EDIT:

To be clear, I'm interested in the uses, not definitions, of polymorphically-typed values.

For example, suppose we have:

f : forall a . a -> a
g : (forall a . a -> a) -> Int
val = (g f, f True, f 'a')

How can we know that we need to instantiate f when it's applied, but not when it's given as an argument?

Or, to separate ourselves from function types:

f : forall a . a
g : (forall a . a) -> Int
val = (g f, f && True, f + 0)

Here, we can't even distinguish the use of f as applying it versus passing it: it's instantiated when passed as an argument to && and +, but not g.

How can a theoretical system distinguish these two cases without a magical "you can convert any polymorphic type to its instance" rule? Or with a rule like that, can we know when to apply it, to keep decidability?

The Dunfield & Krishnaswami paper's introduction refers to Practical type inference for arbitrary-rank types

  As can be seen, it scales well to advanced type systems; moreover,
  it is easy to implement, and yields relatively high-quality error messages
  (Peyton Jones et al. 2007)

In System F-ish approach there is also a "subtyping" relation. See section 3.3 Subsumption.

I'd also emphasize that Haskell doesn't have impredicative types (or inference for them). See: https://mail.haskell.org/pipermail/ghc-devs/2016-September/012940.html for pointers.

  You can write a polytype in a visible type argument; eg.  f @(forall a. a->a)
  You can write a polytype as an argument of a type in a signature  e.g.  f :: [forall a. a->a] -> Int

  And that’s all.  A unification variable STILL CANNOT be unified with a polytype.  The only way you can call a polymorphic function at a polytype is to use Visible Type Application.

  In short, if you call a function at a polytype, you must use VTA.  Simple, easy, predictable; and doubtless annoying.  But possible.

I.e. id id will always be elaborated as

forall a. id @(a -> a) (id @a)

not

id @(forall a. a -> a) id

Yet, you can write the latter explictly, if you enable ImpredicativeTypes.


Question about labeling in Dijkstra's Proof of Correctness I am trying to understand the proof of correctness for Dijkstra's algorithm (shown below) and also at the following link: CS Auskland

  Proof by contradiction

  Suppose that $u$ is the first vertex added to $S$ for which $d[u] \ne \delta(s,u)$. We note:

  $u$ cannot be $s$, because $d[s] = 0$.

  There must be a path from $s$ to $u$. If there were not, $d[u]$ would be infinity.

  Since there is a path, there must be a shortest path.

  When $x$ was inserted into $S$, $d[x] = \delta(s,x)$ (since we hypothesise that u was the first vertex for which this was not true).

  Edge $(x,y)$ was relaxed at that time, so that
      $$d[y] = \delta(s,y)
\le \delta(s,u)
\le d[u]$$

  Now both $y$ and $u$ were in $V-S$ when u was chosen, so $d[u] \le d[y]$.

How can we say that $d[u] \le d[y]$?  And why aren't we saying that $d[u] \ge d[y]$?  Wouldn't the label on $u$ be larger if it is further down the path from $y$?

  Thus the two inequalities must be equalities,
      $$d[y] = \delta(s,y) = \delta(s,u) = d[u]$$

  So $d[u] = \delta(s,u)$ contradicting our hypothesis.

  Thus when each $u$ was inserted, $d[u] = \delta(s,u)$.

Since the algorithm at each step adds to $S$ the vertex with the lowest "d" value, and $y$ is not in $S$, $d[u] \leq d[y]$.


What are thin-core and fat-core processors I am reading a paper called Back to Thin-Core Massively
Parallel Processors by Ami Marowka (Computer, 44(12):49–54, 2011; IEEE Xplore).

However I have a question about the title of the article: what does "thin core" (and for that matter, "fat core") mean?

Thank you!

Thin-core is a simple processing unit, slower with less registers, for example GPU core or small, low-energy core.
Fat-core is full-fledged CPU core. The mobile version of CPU is still fat-core

From article:

  The IBM Blue Gene/P supercomputer (1 Pflop) is an example of a contemporary large-scale system design (294,912 processors) based on a many-thin (850 MHz, 1 Gbyte) processing-core approach.


Do these answers work even when we change the values? So I know that these are both true, but if I change the values would they still be true? Do these statements hold for any value?

A) Suppose f is a flow of value 50 from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to 50.

Suppose we were using 100 or maybe 75 instead of 50. Is this still true?

B) Suppose f is a flow of value 100 from s to t in a flow network G and there is an s-t cut of capacity 100. Then there are no s --> t paths in the residual graph Gf.

If we use 80, 60, 20 and so on is this still true? What about for odd numbers?

The value of any $st$-flow is at most the value of any $st$-cut, and they are equal if and only if the flow value is maximized and the cut value is minimized. Thus, statement (A) is false since $f$ isn't necessarily a maximum flow (since you claim (A) is true, maybe you forgot to mention that $f$ is a maximum flow, or you meant to say that the value of the cut is at least 50?).
Statement (B) is true, since if there is a flow and cut of equal value, then the flow is a maximum flow and the residual graph has no path from $s$ to $t$.

Of course, the actual values don't matter. Only the relationship between the flow value and cut value is relevant.


How do computers remember where they store things? When a computer stores a variable, when a program needs to get the variable's value, how does the computer know where to look in memory for that variable's value?

I'd suggest you look into the wonderful world of Compiler Construction! The answer is that it's a bit of a complicated process.

To try to give you an intuition, remember that variable names are purely there for the programmer's sake. The computer will ultimately turn everything into addresses at the end.

Local variables are (generally) stored on the stack: that is, they're part of the data structure that represents a function call. We can determine the complete list of variables that a function will (maybe) use by looking at that function, so the compiler can see how many variables it needs for this function and how much space each variable takes.

There's a little bit of magic called the stack pointer, which is a register which always stores the address of where the current stack starts.

Each variable is given a "stack offset", which is where in the stack it's stored. Then, when the program needs to access a variable x, the compiler replaces x with STACK_POINTER + x_offset, to get the actual physical place it's stored in memory.

Note that, this is why you get a pointer back when you use malloc or new in C or C++. You can't determine where exactly in memory a heap-allocated value is, so you have to keep a pointer to it. That pointer will be on the stack, but it will point to the heap.

The details of updating stacks for function calls and returns are complicated, so I'd reccomend The Dragon Book or The Tiger Book if you're interested.


Reduce Clique to Vertex Cover I read on the internet that it's possible to reduce clique to vertex cover. Almost everyone use this theorem:

  if a graph $G$ has a clique of size $k$ then the complement of $G$ has a vertex cover of size $n-k$, where $n$ is the number of vertices.

Consider the graph on five vertices and the following edges: a clique on $\{1,2,3,4\}$ and $(1,5),(2,5),(3,5)$. The complement of this graph has only one edge, and it does not cover the set of vertices.

Is the statement I quoted correct?

You're misunderstanding what Vertex Cover is: the task is to find a set of vertices which "cover" or "touch" all edges. Each of the vertices $4,5$ covers the unique edge $(4,5)$ in the complement of your graph.

The theorem states that the size of the maximum clique in a graph equals the size of a minimum vertex cover in its complement. This is because a set $A$ of vertices is a clique in a graph $G$ if and only if its complement $\overline{A}$ is a vertex cover in the complement graph $\overline{G}$.

Indeed, $A$ is a clique in $G$ if any two $x,y \in A$ are connected in $G$; $\overline{A}$ is a vertex cover in $\overline{G}$ if for every edge $(x,y) \in \overline{G}$, one of $x,y$ is in $\overline{A}$. So $\overline{A}$ is not a vertex cover in $\overline{G}$ if there exists an edge $(x,y) \in \overline{G}$ such that $x,y \notin \overline{A}$, i.e. if for some $x,y \in A$, $(x,y) \notin G$; this is exactly the condition that $A$ is not a clique in $G$.


DFA for words with $a$s not a multiple of 3 and at least one $c$ Consider this language: $$L = \{w \in \{a,c\}^* \mid 3\nmid\#a(w)\land\#c(w)>0\}$$.

Here is an automaton for the first part of language, but I do not know how to devise and attach the second part of the condition $\#c(w) > 0$. Because $C$ can come in any state.

The product construction is a way of taking two DFAs for languages $L_1,L_2$, and constructing a new DFA for the language $L_1 \cup L_2$ or $L_1 \cap L_2$. In your case, $L_1$ consists of all words in which the number of $a$s is not a multiple of 3, and $L_2$ consists of all words containing at least one $c$. You have already constructed a DFA for $L_1$. Construct one for $L_2$, and use the product construction to construct one for $L_1 \cap L_2$.


When does kernel accessing virtual memory cause problems I'm working with the CPU Pintos and have a question that is:

In which situations can the kernel accessing the data in virtual memory via a pointer lead to problems? And how do you avoid them?

I know that the kernel can access the virtual memory via pointers to the stack, but don't understand when errors may occur.

Same as with any program that uses pointers: dereferencing one that points nowhere sane will give grief. If in the kernel of the system, with little or no protection against accidents (and nobody who can clean up the mess afterwards), it is much worse.


What is the difference between $AC^2$ and $FO (\log \log n)$ complexity classes? $FOLL$ or $FO (\log \log n)$ is a complexity class of all problems solvable by uniform poly-size circuit families of unbounded fan-in and depth $O(\log \log n)$.

$AC^2$ is a complexity class of all problems recognized by boolean circuits with depth $O(\log ^{2}n)$ and polynomial number of unlimited fan in AND and OR gate.

  Question. : What is a difference between $FOLL$ and $AC^2$?

In the definition of $FOLL$  they have used "uniform " poly-size and in the definition of $AC^2$ they are saying boolean circuits.

The functions $\log \log n$ and $\log^2 n = (\log n)^2$ are quite different. The latter grows much faster than the former: $\log \log n = o(\log^2 n)$. This shows that FOLL is a subset of AC2 (and even of the smaller class AC1).

Uniformity is a different aspect in which the two classes differ: FOLL is a class of uniform circuits, whereas the AC hierarchy captures non-uniform circuits. As such, even AC0 circuits can compute uncomputable functions, something that FOLL cannot do.


Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular Suppose we define an operation such that

$$A \text{ avoiding } B = \{w \in A \mid w\text{ has no substring in }B\}\,.$$

How can I prove that, if $A$ and $B$ are regular then $A\text{ avoiding }B$ is regular too?
I know I should either construct a DFA/NFA or use closure properties, but where to start?

What I come up with is that $A = (A\text{ avoiding } B) \cup \{w \mid w\text{ has a substring in }B\}$ and then I've tried to prove that $\{w \mid w \text{ has a substring in }B\}$
 is regular by constructing a DFA for it. That would show that $A \text{ avoiding } B$ is also regular.

Yes you are on right track.

We can first define ($A$ avoids $B$) as ($A$ - ($A$ has $B$)), where ($A$ has $B$) are strings of $A$ which contain strings of $B$ as substrings. Then ($A$ avoids $B$) will be strings of $A$ that do not contain strings of $B$ as substrings.

We can define ($A$ has $B$) as $A \cap (\Sigma^* B \Sigma^*)$. Then ($A$ has $B$) are strings of $A$ which contain strings of $B$ as substrings.

Thus you have ($A$ avoids $B$)  = ($A - (A \cap (\Sigma^* B \Sigma^*))$). Since regular languages are closed under concatenation, intersection, and subtraction they are also closed under operaion avoid.

Above relation also gives ($A$ avoids $B$)  = $A -  \Sigma^* B \Sigma^*$ as pointed out by Hendrik Jan.


Bulk-loading R-tree with data with extent When bulk-loading R-tree with points one can simply sort the elements by some coordinate and split to equal-sized chunks. But if the elements have some extent, sorting them by their coordinate value (whether minimum, average or maximum) can still lead to large overlap if there are some large elements involved.

(Update) I am already building the tree top-down. It was the obvious option, especially since I don't have 100% utilization requirement. The leaves are compressed, so they won't end up page-aligned on disk anyway. My concern is really splitting the individual elements in a better way than simply sorting by coordinate, because the elements have very different extents (from couple of metres to several kilometres, so three orders of magnitude) and also different sizes (in bytes). It is even worth unbalancing the tree a bit, because the high-level nodes easily fit in memory, so they are not critical. The decompression and parsing the leaf data is.

Is there some technique for splitting so that overlap is minimized?

Yes, there is. It's called OMT, for Overlap Minimizing Top-down, and the first description of the algorithm can be found here: http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-74/files/FORUM_18.pdf


Planarity conditions for Planar 1-in-3 SAT Planar 3SAT is NP-complete. A planar 3SAT instance is a 3SAT instance for which the graph built using the following rules is planar:

add a vertex for every $x_i$ and $\bar{x_i}$
add a vertex for every clause $C_j$
add an edge for every $(x_i,\bar{x_i})$ pair
add an edge from vertex $x_i$ (or $\bar{x_i}$) to each vertex that represent a clause that contains it
add edges between two consecutive variables  $(x_1,x_2),(x_2,x_3),...,(x_n,x_1)$

In particular, rule 5 builds a "backbone" that splits the clauses in two distinct regions.

Planar 1-in-3 SAT is NP-complete, too.

But for planar 1-in-3 SAT are the planarity conditions defined in the same way as in Planar 3SAT ? In particular, can we assume that there is a backbone that links the variables $(x_i,x_{i+1})$  ?

Yes you can. Actually you can even show that something stronger is true. The problem know as Positive Planar 1-in-3-SAT is NP-complete as shown by Mulzer and Rote.

In this version of 1-in-3-SAT, you require for every input formula that

you have three variables per clause, none of them negated
the graph of the formula is planar, even if you add the "backbone" between the variable vertices

The reduction is from Planar 3-SAT.


Using a computer algebra system to optimize mathematical expressions This is something I've been wondering for years. Software like Mathematica is great at manipulating expressions into simplified, factorized, and other forms. I'm wondering if there's a way, theoretically and/or practically, to find the form that has the fewest operations. The next step would be to prefer operations that are faster (ie. multiply instead of divide). Lastly, to find a form that maximizes extraction of repetitive subexpressions, so that the subexpressions can be evaluated once and substituted for potentially significant performance gains. Has any research been done in this area? Thanks.

This doesn't completely answer your question, but you ask if research has been done on this.

This is an area called Symbolic Algebra. I'm sure there are many such research groups, but here is one:

https://www.scg.uwaterloo.ca/

They're the group at Waterloo which developed the Maple software (similar to Mathematica).


What is the difference between a Standardization and a Specification? While asking this question on "what exactly is standardization", I remebered that another related term that always came up while reading about C libraries was the term "specification".
To avoid asking more than one question in a single post, I decided to open another post that I hope will clarify what is the difference between this two "popular" terms.
The C POSIX library is defined as a specification of the C standard library, for POSIX systems. Anyway, is Posix usually considered standardized as well, isn't it?
Well, I'm a little bit confused by the use of this words.
I'd love to see reference and examples about other langauges, as much as clarification in the C case.

You ask for the definition of "specification".  Here's one: https://en.wikipedia.org/wiki/Specification_(technical_standard).  You asked for the definition of a standard.  Here's one: https://en.wikipedia.org/wiki/Technical_standard.


Does every 3CNF propositional formula has an equivalent 2CNF propositional formula? Does every 3CNF propositional formula has an equivalent 2CNF propositional formula?

Definitions:

3CNF propositional formula is conjunctive normal form propositional formula, which is just conjunction $\land$ of clauses, where each clause is disjunction $\lor$ of at most 3 literals, where each literal is just boolean variable either with or without not $\lnot$ operator/connective.

2CNF propositional formula is conjunctive normal form propositional formula, which is just conjunction $\land$ of clauses, where each clause is disjunction $\lor$ of at most 2 literals, where each literal is just boolean variable either with or without not $\lnot$ operator/connective.

The single clause 3CNF:

$\varphi = a\lor b\lor c$

does not have an equivalent 2CNF. Suppose $\psi=\bigwedge\limits_{i=1}^m \psi_i$ is an equivalent 2CNF. Let $\psi_i$ be one of its clauses, and assume it involves the variables $a,b$. An assignment which sets $c=1$, but does not satisfy $\psi_i$, satisfies $\varphi$ but not $\psi$, hence they are not equivalent.


How to draw a DFA for given language? Give a finite state diagram for a DFA that accepts any word in the language $L = \{w \mid w \in \{a, b\}^* \text{ and }w \text{ alternates } a\text{'s and }b\text{’s and has an even number of }b\text{’s}\}$.

My attempt: I am having problem on how to deal with the even part of b.

Since the strings must be of the form $ababab\dotsm$, and also there must be 0, 2, 4, 6, ... $b$s, begin with four states, each of which "remembers" the input so far:

$q_0$: just saw an $a$ and have seen an even number of $b$s so far,
$r_0$: just saw a $b$ and have seen an odd number of $b$s so far,
$q_1$: just saw an $a$ and have seen an odd number of $b$s so far,
$r_1$: just saw a $b$ and have seen an even number of $b$s so far.

Then, it's clear that these states will have transitions in a cycle, with transitions:

$\delta(q_0, b) = r_0$
$\delta(r_0, a) = q_1$
$\delta(q_1, b) = r_1$
$\delta(r_1, a) = q_0$

and the other possibilities will either be undefined or lead to a trap state, depending on what model of a DFA you're accustomed to using. Now make a new start state $s$, with $\delta(s, a) = q_0$ (since you've just seen an $a$ and have no $b$s yet), and, for similar reasons, define $\delta(s, b) = r_0$. I'll leave it to you to decide which (two) of the states in the cycle of four states should be final.

There are systematic ways to do this kind of product DFA, but in this case, it's no simpler than this ad hoc construction.


How to tackle Big O proofs that involve multiple parameters I am getting more and more familiar with the whole concept of time complexity but I have never encountered an example where more than one parameter is involved. Therefore, is it possible(well, I am sure it is :")) and how to prove

  a^n = Θ(logn)

or any other, similar-looking expression?

  c1 * logn ≤ a^n ≤ c2 * logn

where, e.g. c1 = 1 and c2 = 2,

  logn ≤ a^n ≤2 * logn.

Can I go one step further and set n, to be equal e.g. 2? This way I will get

  log(2) ≤ a^2 ≤ log(4)

Which is surely true(for a between ~ 0.55 and 0.77)...

...but isn't that too specific and interfere with the inequality too much? Sorry if the answer is trivial but Google is not helping and I have nobody to ask for explanation.

That isn't true. As you say, it implies there are $c_2$ and $N$ so that for all $n \ge N$ you have $a^n \le c_2 \log n$. Consider:

$\begin{align*}
  \lim_{n \to \infty} \frac{a^n}{\log n}
      &= \lim_{n \to \infty}
                \frac{a^n \log a}{1 / n}
      = \infty
\end{align*}$

Here we used l'Hôpital. But that the limit is infinite means that eventually the ratio is larger than any given $c_2$. In fact, it proves $a^n = \Omega(\log n)$.


Converting CFG to PDA I have the following CFG,

$S \rightarrow CB$
$C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$
$B \rightarrow AB \text{ }|\text{ } \varepsilon$
$A \rightarrow a\text{ }|\text{ }b$

This is the CFG for the following language:

$$L= \left\{w \text{#} x\mid w^R \text{ is a substring of }\ x \text{, where }  x,w\in \{a, b\}^*\right \}$$

I have a problem with constructing PDA for this CFG.

My attempt

My idea was to store characters in stack until "#" character, then as soon as the sequence of reversed characters go, pop from the stack. If at the end of input stack is empty, then we are done.

The problem is that for the following string, for example:

abbaa#aabbbbbbb(aabba)bbbbbb

when we read characters after "#", PDA will pop 4 characters, the it will see that the sequence is not valid and proceed with input. How can I return these 4 characters back so that I can check sequence again because I need full stack to proceed with accepted reversed substring that I have showed in brackets?

There is a general method to convert any CFG into a PDA. That's what jmite meant. You can find more details on that in wikipedia, or by searching this site.

But once you realized the language is $L=\{w\#x \mid w^R \text{ is a substring of }x\}$, you can forget about the grammar and directly construct a PDA.

The PDA works like what you describe in your question - it begins by putting $w$ into the stack. Then it needs to pop it out and compare it to $x$. But it might be that the substring $w^R$ is not a prefix of $x$, which causes your confusion.

The idea you are missing is the power of non-determinism: allowing the PDA to "magically" select the right way out of many possible ways to proceed.

In more details, the PDA will do the following. It will read some letters from the $x$ part of the input and just ignore them. Then, at some point which will be chosen "non-deterministically" (or, "magically", if you prefer), it will start comparing the input to the stack (and accept if there is a match; reject otherwise).

If indeed $w^R$ is a substring of $x$, there is a way for the PDA to make the right choice and start comparing the input to the stack exactly at the right position. This is enough to show that the PDA accepts (at least) $L$.

The concept of non-determinism is very strange, but think about it that way: the construction above defines infinitely many possibly (deterministic) PDAs: each one starts to pop the stack at a different time. "Accepting" a word in a non-deterministic way is defined as the event that at least one of the above  machines accepts. The case of "Rejecting" a word is defined to be the event in which all the above machines reject.


Why do we have to make variables unique when evaluating $\lambda$-calculus? I'm studying $\lambda$-calculus and came across a problem that I'm not sure how to understand. More specifically, it's about evaluating $\lambda$-calculus expressions using $\beta$-reduction.
I was taught that the basic steps for performing $\beta$-reduction are to

Find reducible expressions in the form of ($\lambda x.$$e_1$) $e_2$.

Rewrite the expression by substituting every free occurrence of $x$ in $e_1$ with $e_2$.

I've solved some exercise problems which seemed fairly simple to understand, but came across one that I couldn't understand the answer.
The expression in question is ($\lambda x.$($\lambda y.x$)) $y$, and after following the rules above I ended up with the result of $\lambda y.y$ after replacing the free occurrence of $x$ with $y$ in $\lambda y.x$. However, the correct answer seems to be $\lambda y.x$.
The rationale that I've been able to find is that before applying $\beta$-reduction, we have to change variables to be "unique."
Could someone explain the reasoning behind this for me please?

When performing a $\beta$-reduction, there are cases in which an $\alpha$-conversion is needed first; otherwise, the $\beta$-reduction fails to preserve semantics. This is here the case: you are replacing the free variable $x$ with $e_2$ and $e_2$ contains free variables which are bound within $e_1$.

You can easily see why the semantics are not preserved: $(\lambda y.y)$ and $(\lambda y.x)$ are not equivalent expressions because $(\lambda y.y)z = z$ but $(\lambda y.x)z = x$. In order to preserve the semantics, you first need to perform an $\alpha$-conversion on $(\lambda y.x)$ so as to replace $y$ with something else which is not free in $e_2$ (thus achieving "uniqueness"—though IMO such a term should be frowned upon here).


Convert a non-deterministic Turing machine into a deterministic Turing machine How can we systematically convert a non-deterministic Turing machine into a deterministic Turing machine that recognizes the same language?

The deterministic machine simulates all possible computations of a nondeterministic machine, basically in parallel. Whenever there are two choices, the deterministic machine spawns two computations. This proces is sometimes called dovetailing. The tape of the deterministic simulator contains a list of configurations of the nondeterministic one, and performs a step on each of these in turn. This requires quite some administration, and the capability to move aroud data when one of the simulated configurations extends its allotted space.


What is the usage of a decision problem for an optimization problem like the longest path problem? I just read this definition for the longest path problem:

  LONGEST PATH
  Input: A graph $G=(V,E)$, an integer $k$.
  Question: Is there a path with at least $k$ vertices in $G$

This seems a decision problem and a certificate can be verified easily. But, what is the usage of such a problem? Isn't the main concern finding the longest path in the graph? I guess that would be an optimization problem, and verifying a given certificate can't be done in polynomial time, so that is not $NP$. right?

If yes, then what is the usage of the decision problem (which is $NP$) and what is its relation to the main problem?

My question is different from  "NP-complete" optimization problems because I also asked about the relationship between a decision problem and a relevant optimization problem, and how a decision problem may help us in solving the optimization problem, and basically what is their usage in such cases.

In complexity theory, we tend to focus on decision problems. They're conceptually simpler and the corresponding function and optimization problems can be reduced to them with only a polynomial loss of efficiency. From a theoretical point of view, polynomial factors are considered "efficient".

Let's take your example of Longest Path.  We know that the longest path has length between 1 and $n$ (where $n$ is the number of vertices), so we can find the actual length of the longest path by doing binary search using a series of queries of the form "Is there a path of length at least $n/2$?", "... $3n/4$?", ... That tells us that the longest path has some length $\ell$.  Now, we can loop through the edges one by one.  Delete the $i$th edge and ask, "Is there still a path of length at least $\ell$?" If there is, go on to the next edge; if there isn't, undelete edge $i$ and go on to the next one.  When this algorithm terminates, we'll be left with a graph that is exactly a path of length $\ell$. We used $\Theta(\log n$) calls to Longest Path to find the length of the longest path, and $O(n^2)$ calls to find the actual path.

The decision problem isn't necessarily "useful" per se: as you observe, the function problem ("Give me a solution", rather than "Is there a solution?") is the one we usually want to solve, practically speaking.


What is an example of a weakly universal hash function that is not pairwise independent? A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :

$$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$

Here the function $h:U \rightarrow [m]$ is chosen uniformly from the family $H$ and we assume $|U| > m$.

A family of hash functions $H_s$ is said to be strongly universal if for all $x \ne y$ and $k, \ell \in [m]$:

$$P_{h \in H_s}(h(x) = k \land h(y) = \ell) = 1/m^2$$

What is a concrete example of a hash function family which is weakly universal but not strongly universal?

Let $U = [m]$, and let $h$ be the identity function.

If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by
$$
h_i(x) = \begin{cases}
x & \text{if } x \neq m+1, \\
i & \text{if } x = m+1.
\end{cases}
$$
The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.