Theoretical CS and Math - self-study recommendations I am a non-CS grad and my field of study is unrelated to CS. However, as part of a larger plan to become a computer scientist, I want to obtain a solid background in theoretical computer science and math as it relates to CS. I did a plenty of research and selected the following best/really good books on the topic of CS and math and would like to ask for your opinions on:

Completeness of topics covered (please recommend anything I've missed)
Overlap of material covered / overkill area (please recommend books that should be removed from the list)
Order to study the books (I listed in the order that I think they should be studied)

The list feels excessively long, so I would appreciate recommendations to remove some books, without the loss of the core knowledge require for CS.

So, the books are:

Mathematician's Delight by W. W. Sawyer
How to Prove It: A Structured Approach by Daniel J. Velleman
How to Solve It: A New Aspect of Mathematical Method by G. Polya
An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson
Foundations of Computer Science by Al Aho and Jeff Ullman (http://i.stanford.edu/~ullman/focs.html)
Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth, and Patashnik
Introduction to the Theory of Computation by Michael Sipser
Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
Computational Complexity: A Conceptual Perspective by Oded Goldreich
Computational Complexity: A Modern Approach by Sanjeev Arora, Boaz Barak
A Course in Combinatorics by J. H. van Lint, R. M. Wilson
Computability: An Introduction to Recursive Function Theory by Nigel Cutland
Computers and Intractability: A Guide to the Theory of NP-Completeness by M.R. Garey, D.S. Johnson
Theory of Recursive Functions and Effective Computability by Hartley Rogers
Inequalities by G.H. Hardy, J. E. Littlewood, G. Polya
Mathematical Logic: A Course With Exercises (Part I): Propositional Calculus, Bookean Algebras, Predicate Calculus by René Cori, Daniel Lascar
Mathematical Logic: A Course With Exercises (Part II): Recursion Theory, Godel's Theorems, Set Theory, Model Theory by René Cori, Daniel Lascar

Your list is extremely problematic.

To start with, I would flatly skip books 6,11,12,14,15,16,17: Books 6, 11 and 15 are general mathematics which is not really needed unless you become a theoretical researcher. Books 12 and 14 cover recursion theory which is not computer science (even though it deals with computability!). Books 16 and 17 cover advanced topics in logic, whereas you only need to know very basic logic.

Out of books 1,2,3, I would choose just one to serve as a general introduction to mathematics and proofs.

Books 5,7,8,9,10,13 cover several subjects: automata theory, algorithms, and complexity theory. Let me suggest that you follow Sipser (Book 7) for automata theory and complexity theory, and Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein ("CLRS") for algorithms.

Book 4 deals with functional programming. While my computer science education has never included any courses on this subject, it is fair to say that many researchers in theoretical computer science count functional programming as part of the essential foundations.

Summarizing: what you remain with is

One of books 1-3 (or any comparable "introduction to proof" text)
CLRS
Book 4 (functional programming)
Book 7 (automata theory and complexity theory)


What is a limitation of using an array concerning capacity? Is it that you need a separate method to expand the array whenever it goes over the capacity?

Array is defined to have continous memory, so there is a need to extend it by finding continous block that fit it in.
Also the array size is given in advance.
The limit is the largest available continous block and possibility to index it.

For example C defines $malloc$ and $realloc$, which seeks such block (it may start in the same place as original array).
$realloc$ when finds larger region in different place rewrites the content of the array.

If there is no constraint about continous regions - there are lists of arrays used - smaller blocks connected in linked list, easier to grow, but a bit slower to operate on.

Some languages provides growing arrays, but internally it could be stack, list or anything else, so definition of "what is array" is crucial.


LZW decoding process I'm trying to understand how LZW decodes a string.
For example suppose that we have a dictionary where:

a=0
b=1

and we have to encode the string "aabbabaabb", so the output of the encoding process (if I have not made mistakes) produces the string "0011324" and the dictionary became(using a tree representation):

(source: f.cl.ly)
The decoder will just know "0011324" and the starting dictionary where there are just a=0 and b=1.

How does it work the decoding process with just these 2 informations?

Short answer: the decoding algorithm follows the same steps as the coder: it actually builds the tree. E.g., in your example the first two 0's mean two a's have been read, This then implies the code for aa was added to the tree as number 2. This continues, but necessarily the decoder always is one step behind the coder. In most cases all information is present to make decisions in the next move. Unfortunately there is the possibility that the decoder needs the code that has been just inserted in the tree (and is not available for the decoder since it lags behind). That case is so specific that it can be reconstructed from the other information (then the unknown letter must be the first letter of the last code).

That is the global view. Wikipedia has a larger example.


Why are lambda-abstractions the only terms that are values in the untyped lambda calculus? I am confused about the following claim: "The only values in the untyped lambda calculus are lambda-abstractions".

Why are the other terms not values? What does it mean for a lambda-abstraction to be a value? The first thing that came to my mind was that maybe lambda-abstractions are the only possible normal forms, but this is not true of course, e.g. $(\lambda x.\; x)\;y \to y$.

Can someone enlighten me?

There are a number of things going on here:

The language you are talking about has no additional data types, otherwise there would be other kinds of values.
The reduction strategy of the language does not reduce inside lambda abstractions. Both call-by-value and call-by-name conform to this. Otherwise, not every lambda abstraction would be a normal.
One generally considers closed expressions as programs, so there are no free variables, hence the example you present is not considered.

Other terms are not values because they can be reduced or they do not appear in closed programs.

That a lambda abstraction is a value means that it cannot be reduced any further (depending on the reduction strategy).

For open terms, variables are also values.


Can starvation occur with interrupts? The Computer Science text book I own describes how an interrupt is handled in an operating system:

At some point at the end of an instruction the processor checks if there are any outstanding interrupts
If there are, the priority of the present task is compared with the highest priority interrupt
If there is a higher priority interrupt, the current job is suspended
The contents of the special registers are stored so that the job can be restarted later (aren't general purpose registers preserved as well? or do ISRs do not use these?)
Interrupts are then serviced until all have been dealt with
Control is returned to the original job
If the current task has more priority than the interrupt, it is queued and serviced later

The last point "If the current task has more priority than the interrupt, it is queued and serviced later". Does this mean that if an I/O interrupt is generated but the current tasks are all very high priority, they will not get serviced (ignored)? moreover, how does the computer determine when to service these if the current task is more "important"?

I quite disagree with your textbook.

First, Interrupts can be very different between architectures. Most does not support nesting interrupts, while others allow some forms of it (fast interrupts for time critical operations in embedded...)

One can imagine a CPU having 3 modes :

User
Supervisor
Interrupt

When the interrupt request signal[s] is active, the CPU automatically saves a few registers, sets the supervisor flag and branches into the interrupt vector. If several interrupts occurs simultaneously, the highest priority interrupt is taken. If one or several interrupts becomes active while the CPU is already in interrupt processing mode, it will wait until the end of the current interrupt service routine to eventually process the next highest level interrupt. This is similar when interrupts are temporarly masked by the OS when it is updating some structures...

Which registers are saved depends a lot of the type of CPU. The minimum is just being able to resume execution later : PC, flags, one register. You can also have a full set of shadow registers reserved for interrupts and which don't need to be saved.

OS tasks are not interrupts. There is usually a timer that regularly tiggers an interrupt which, in turn, wakes the scheduler for switching tasks. It is also done by I/O related interrupts : A network packet is received, an interrupt is triggered, the Ethernet NIC interrupt routine tells the OS to wake the network daemon...

No task has higher priority than interrupts.

Because while being in "interrupt" mode, the CPU cannot be interrupted and cannot process higher priority stuff, OSes try to spend as little time as possible in that state, they instead schedule tasks to asynchronously process events, for one or several symmetric CPUs.


Simple elementary cellular automata with high period? I'm looking for a simple rewrite system which displays high period.

In order to do that, I've ran a brute-force search on every elementary cellular automata, for a few fixed memory lengths L. The result is that, when L=7, there are rules with the max possible period (128). Yet, for L=8, no matter which rule is used, I couldn't get a period > 180. For L=9, the maximum period of 133.

I've, then, tried a few variations of the core idea. For example, I tried using 3 symbols instead of just 2 and do a similar brute-force search, but the results are similar.

Thus, I ask: is there any similar system with a rewrite rule which displays high period?

Used symbols will be $0, 1$, table $T$ with $18$ elements ($L=18$), and one element for register $B$.
Initialize table with any configuration with at least one element set to $1$.

At generation step do:
B = T[0] Xor T[7]
T[i] = T[i - 1]
T[0] = B

The array bounds act like wall, if you read from outside you get $0$. This is simple rewrite system, with minimal number of operations without any fancy operations, only rewrite by one calculate xor of two cells  (hey, Rule 90 takes three), and has period $262143$ giving all $18 bit$ numbers excluding $0$.

How to get such system? This is Linear feedback shift register which fits your description of PRNG, has the highest possible period ($2^L-1$) for given number of bits (cells?) minus 1, the best one would have $2^L$.


lambda calculus as a type theory From the Introduction section of Homotopy Type Theory book:

  Type theory was originally invented by Bertrand Russell ... It was later developed as a rigorous formal system in its own right(under tha name "$\lambda$-calculus").

Can anyone explain me this sentence? I'm having trouble seeing $\lambda$-calculus as a type system.

(also in the same paragraph, $\lambda$-calculus called as "Church's type system")

In the very next paragraph of that book (see HoTT, p. 2) they give an informal characterization of what qualifies a language system (or logic) as a type system, namely that: in it all terms are typed.

By "Church's type system" they're referring to the simply typed lambda calculus (introduced in 1940).

  In 1930s, in particular while preparing his negative solution to the decision problem, Church had introduced a system of untyped lambda calculus. This, of course, was not a type theory.

The 1940 system, however, is a type theory, because in it all terms are typed (see, for example (T&S), Section 1.2 for how exactly this is done). By "lambda-calculus as a type system" they're referring to this second, simply typed version of lambda calculus.

(T&S) Troelstra, A.S. & Schwichtenberg, H. Basic Proof Theory, 1996.


Finite state automata, multiple completion states? I'm currently studying for an exam for a course where some of the material covered included finite state automata, I've completed a question and I'm not sure about my answer.

Exercise

Explain what is meant by a Finite State Automaton (FSA) by drawing an FSA to recognise strings of the form $a^rb^s$, where $r\gt0$ and $s\ge0$ and with an alphabet of $\{a,b\}$, i.e., there must be at least one $a$, zero or more $b$'s and all occurrences of $a$ must precede any occurrence of $b$. Illustrate, how your FSA works given the following sample strings:
$\quad$(i) $abbb$
$\quad$(ii) $aaaa$
$\quad$(iii) $aba$

My Answer

Are multiple completion states allowed?

Your DFA is close, but not quite right. Note that the description requires the strings in the language to have at least one $a$, whereas your DFA will accept the empty string. The fix is simple of course:

And yes, having multiple accept states is fine (in fact, some languages require it).


Is this language L context-free? The language

$$L = \{x^r \# y | x, y \in \{a, b, c\}^*\\
\text{
and }x\text{ is a contiguous sub-string of }y\}$$

where $x ^ r$ denotes the backward written word x, is context-free.

Can someone explain, if this statement is true? I am not able to construct a PDA, so I think the language is not context-free. Does anyone have an idea how to prove it?

A more precise expression of the condition "$x$ is a contiguous substring of $y$" produces

$$L = \{x^r \# wxz | x, w, z\in \{a, b, c\}^*\}$$

That should make it clear that the language is context-free.


How to prove that a language $A$ is decidable? How to prove: A language $A$ is decidable $\Leftrightarrow$ if there is a turing machine which lists $A$ in a word length alphabetically ordering.

Word length alphabetically means a sorting first after the word length and then after the character ordering $(\epsilon,a,b,aa,ab,ba,bb, ...)$.

Hope somebody can help me like give a hint or an approach.

You know that a language $L$ is decidable if there is a TM, $M$ which when given a word $w$ as input always halts and accepts if $w\in L$ or halts and rejects if $w\notin L$. Here are some hints to get you started.

($\Rightarrow$) This is easy. If $L$ is decidable by a TM $D$, you can make an enumerator TM $E$ by trying all possible inputs in order. For word $w_i$ in that order $E$ will run $M$ on $w_i$ and write $w_i$ if $M$ accepts.

($\Leftarrow$) Suppose you had an enumerator $E$ that lists all $w\in L$ in lexicographic order. Use that to construct a decider $M$ which when given $w$ as input, runs $E$ until it finds $w$ among the enumerated strings or fails to find $w$. Your task is to show that it will always either find $w$ or decides it does not appear on the enumeration in a finite amount of time.


Is connecting islands with pontoons NP-complete? I have a problem in my mind, I think it is a NPC problem but I don't know how to prove it.

Here is the problem:

There are k islands in a very big lake, and there are n  fan-shaped pontoons. Those pontoons are in the same size but have different initial directions and are in different original positions in the lake. The pontoons can rotate freely around its center of mass, and no cost associated with rotation.

Now we need to move those pontoons so that all islands in the lake can be connected. We can guarantee the number of pontoons is enough to connect all the islands.

[Note]: We cannot reuse the pontoons!!

The task is to find the solution having the minimum total distance of the moving pontoons in order to make all islands connected. The distance of moving one pontoon can be calculated as the distance between the center of mass's original position and its deployed position.

To make it clear, I have drawn such a figure. Suppose we have 3 islands A, B and C. They are located somewhere in the lake. And I have several fan-shaped pantoons. Now the solution is to find a minimum moving distance summation to connect A, B and C, shown in bottom part of the figure. Hope it help understand the problem. :)

It seems that the problem is a NPC one, but I don't know to prove it. Can anyone help me on this?

After looking at the new diagrams, I see that you may need multiple pontoons to cross between islands. Given that, you could get very close to a solution of the Steiner Tree problem by turning the nodes into islands and creating a sufficiently diverse collection of pontoons with small arcs. Wikipedia says that there is in fact a PTAS for the Steiner tree problem, so I can't say immediately that this renders it NP-complete. However looking at the details of the Steiner tree might either get you a good approximate solution or show that the problem is NP-Complete.


Understanding depth-limited BFS time complexity I'm trying to implement graph power calculation using BFS. According to Wikipedia, BFS with depth limit k will suffice (I'm using adjacency list representation, my graphs are sparse, so adjacency matrix power is not optimal).

Complexity of BFS is O(V+E), running it for every vertex is trivially O(V*(V+E)). I also have depth limit k here and Wikipedia claims (in the page linked above) that running BFS with this constraint for every vertex will be O(V*E). Why is that? In the worst case when every vertex is in the "range" of k from every other vertex I'll have to search the entire graph V times, after all.

There are two cases.

First. $V-1 \leq E$. Then $O(V \cdot (V + E))$ and $O(V \cdot E)$ are equivalent.

Second. $E < V-1$. Then graph is disconnected and the biggest component has size at most $E + 1$. The whole algorithm will consist of $V$ BFS runs each on the component which has at most $E + 1$ vertices and at most $E$ edges. So each BFS run will take $O(E)$ time and the whole algorithm - $O(VE)$.

Note: this reasoning does not depend on $k$.


Determining number of elements divisible by at least one prime of set I have an array ($|A|\leq 10^6$) of numbers ($A_i\leq10^6$) and a set of prime numbers. I have to find the count of the elements in the array that are divisible by at least one of the numbers in the given set.

For example:

  Array: {3,5,7,15,21,143}

  Set: {3,5,7}

  Output : 5

The numbers are 3(3), 5(5), 7(7), 15(3,5), 21(3,7).

If the array size is $10^6$, an $n^2$ algorithm would time out.

Possible approach: I can preprocess all numbers in the array and store the count of elements each prime factors appear in.

For the example given above : The prime factors are 3,5,7,11,13 and values of the count array will be count[3]=3, count[5]=2, count[7]=2, count[11]=1, count[13]=1.

Can the principle of inclusion and exclusion be applied in this case or is there any other approach to the problem?

One possible approach is to use the GCD algorithm: calculate the GCD of each number in your array with the product of the given primes.


How to prove that the reversal of the concatenation of two strings is the concatenation of the reversals? Given languages $L_1$ and $L_2$, how do we prove that
$$(L_1L_2)^{\mathrm{rev}} = (L_2^{\mathrm{rev}})(L_1^{\mathrm{rev}})\,,$$
where ${}^{\mathrm{rev}}$ denotes reversal?

I think using mathematical induction, it can be shown true for two languages $L_1$ and $L_2$ of length $1$ each and then do induction using one of the lengths and then repeat with the other length.
Is there any other way of proving this in a simpler way without making it too big with induction method?

Well, consider the following "proof" (I'll explain afterwords why the quotation marks):

Let $w=a_1\cdots a_n$ be a word, then we have that

$w\in (L_1L_2)^{\mathrm{rev}}$ iff

$a_n\cdots a_1\in L_1L_2$, iff

there exists $0\le k\le n$ such that $a_n\cdots a_k\in L_1$ and $a_{k-1}\cdots a_1\in L_2$, iff

there exists $0\le k\le n$ such that $a_k\cdots a_n\in L_1^{\mathrm{rev}}$ and $a_{1}\cdots a_
{k-1}\in L_2^{\mathrm{rev}}$, iff

$a_1\cdots a_n\in L_2^{\mathrm{rev}}L_1^{\mathrm{rev}}$ iff

$w\in L_2^{\mathrm{rev}}L_1^{\mathrm{rev}}$

In my opinion, this proof is correct, formal, and would be accepted as a proof of the claim.

However, each "iff" along the way (apart from the last one) actually hides an inductive proof. The point is that each of these inductions is extremely trivial.
In fact, even writing $w=a_1\cdots a_n$ actually hides some induction. So you need to ask yourself how "deep" do you want to go into the technicalities.

If you want to prove this claim from basic principles, i.e. from the axioms of set theory, then you need to formalize everything. This would be very painful, but such things are actually useful when we use computer-assisted proofs.


Quantifiers in lambda calculus I'm learning lambda calculus, however I'm quite confused about the quantifiers in lambda calculus. As far as I know, quantifiers such as "∃" are concepts of first order logic (FOL), which are not needed by lambda calculus. Moreover, I didn't find anything about quantifiers in any tutorials I have read.

However, I find this paper (Lambda Dependency-Based Compositional Semantics), in the first page of which the author used quantifier in lambda calculus.

So, are quantifiers used in lambda calculus? If so, what do they mean? Is it the same as in FOL?

Precisely, what does "∃" mean in the following lambda calculus?

λx.∃e.PlacesLived(x, e) ∧ Location(e, Seattle)

There is no notion of quantification in the standard $\lambda$-calculus as introduced by Church. As far as I can tell from Liang's paper, it deals with a specialized version of $\lambda$-calculus in which $\lambda$-expressions can be logical expressions containing quantifiers and logical connectives. This approach is meant as a way of formally representing natural language statements. Thus, we are really dealing with an applied $\lambda$-calculus with function symbols that correspond to logical connectives and function symbols and are to be interpreted in this way.


What does it mean to say that a language is "effectively closed" under an operation? I've been reading some formal language theory papers, and I've come across a term that I don't understand.

The paper will often refer to a set being "effectively closed under intersection" or other operations. What does "effectively" mean here? How does this differ from normal closure?

For reference, the paper I'm seeing these in is:

M. Daley and I. McQuillan. Formal modelling of viral gene compression. International Journal of Foundations of Computer Science, 16(3):453–469, 2005.

"Effectively closed" means that the family is closed under the operation, and that the closure can be computed by giving an automaton/grammar for it (if the original languages are also given in such an effective representation). E.g., given a finite state automaton, we can actually find an automaton for the complement.

Then it is a natural question, whether there are examples of closure properties that are not effective. I know one right now. For a regular language $R$ and any language $L$ the quotient $R/L$ is again regular. There is no effective way to construct a FSA for that quotient if $L$ is e.g. recursively enumarable.


Is the per-vertex error over a PageRank iteration monotonically decreasing? It seems to me that taken over the entire graph, the norm of the error vector must be monotonically decreasing, otherwise we couldn't guarantee that PageRank would ever converge.

However, is the same true on a per-vertex basis? I.e., from iteration t to iteration t+1, is the squared error of a vertex guaranteed to always decrease as it moves closer to its PageRank value? Or is it possible that the vertex squared error would ever increase?

This also seems to me to have some broader relationship with power iterations in general? Some explanation or proof with the answer would be appreciated.

No. Consider the case of an isolated component with a central vertex v that is pointed to by vertices x_1, ...., x_k. The initial value at v is 1/n, and the final value should be roughly k * the restart probability/n. But the value at v in the second round is roughly k/n. If the restart probability is significantly less than 1/k, then the value got further from the ultimate value.


What is the optimal substructure for this greedy-algorithm solvable problem (Domino Piling)? On Codeforces, the first problem that comes up for the tag "greedy" is "50A: Domino Piling". Here is the problem:

  You are given a rectangular board of M × N squares. Also you are given an unlimited number of standard domino pieces of 2 × 1 squares. You are allowed to rotate the pieces. Find the maximum number of dominoes you can place on the board so that each domino covers exactly 2 squares and no dominoes overlap.

I solved it quite easily: the solution is just floor(M*N/2).

I read that in order for a problem to be solved Greedily, it needs to have "optimal substructures". For this problem, what were the "optimal substructures"?

Thank you in advance.

I think there's a slight misunderstanding in the question. The phrase is "optimal substructure", not "optimal substructures". It's not a matter of looking at the individual substructures (e.g., regions of the grid you're trying to tile) and saying, "This one's optimal", "This one's optimal", "This one isn't". Rather, it's a matter of looking at the structure and interactions of the subproblems and saying, "The substructures of this problem (i.e., the subproblems) interact in a way that lets me find an optimal solution easily."

I also don't think this is a great example for greedy algorithms, since greedy algorithms are naturally somewhat recursive and it's so easy to domino-tile a grid iteratively that it feels artificial to force it into a recursive solution. But here goes...

One example of optimal substructure is that, if you can divide your grid into rectangles $A$ and $B$ and you can perfectly tile $A$, then an optimal tiling of the whole grid can be made from the perfect tiling of $A$ along with an optimal tiling of $B$.  This gives the following greedy algorithm.

function tile (int width, int height, int startrow)
if (startrow <= height-1)
    perfectly tile rows startrow and startrow+1 like this | | ... |
    tile (width, height, startrow+2)
else if (startrow == height) then
    tile the last row like this -- -- ... -- , with one empty square
    at the end if width is odd
/* else startrow > height and there's nothing to do */

Note that this just produces tilings like this one for a $7\times3$ grid,

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

which is exactly what you'd do iteratively.


Multi-dimensional Neural Network for fingerprint matching I want to use “Fingerprint matching using multi-dimensional ANN”
by Rajesh Kumar and B.R. Deva Vikram [content link] for fingerprint identification. But I have a serious problem understanding what is a Multidimensional Artificial Neural Network.

I searched for keywords MDANN and Multidimensional ANN but I can't find anything. I also can't be sure what Kumar meant about a MDANN in his article. So far, the closest thing I can relate with Kumar's MDANN is Convolution Nets but I don't believe this is what he meant. Can anybody help me about understanding this type of ANN?

Based on my skim of the paper, I suspect that this is just a standard neural network (in which the entire image is fed into the neural network as an input, one input line per pixel in the image), and they have invented a fancy-sounding name for a standard use of neural networks.  You could of course contact the authors to ask them this question, but that's what it looks like to me.

To replicate their work, I suggest you read Section 5.1 very carefully and use the descriptions there to replicate their work.


NP-complete language as a result of xoring two PTIME languages We define xor operation on languages $L,M\subseteq \{0,1\}^*$:
  $$L\oplus M = \{u\oplus v :|u|=|v|, u\in L, v\in M\}$$   $\oplus$ is
  defined as xor on postions, for example:  $001\oplus 100=101$   Show
  that there exist  languages $L,M\in PTIME$ such that $L\oplus M\in
 NP complete$

It is hard to me. I have been thinking a lot about it. My intuition is:

Write the problem as equations system and reduce 3-SAT to it. But, I am not sure if it is ok and, if yes, how to solve it.

This seems like a rather difficult question. Here is one approach.

Every 3CNF on $n$ variables can be encoded as a binary string of length $8n^3$ (how?). Consider the following two languages:
$$
\begin{align*}
L_1 &= \bigcup_{n=1}^\infty \{ xy0^{8n^3} : |x|=n, |y|=8n^3, \text{$x$ is an assignment satisfying the 3CNF $y$} \}, \\
L_2 &= \bigcup_{n=1}^\infty \{ x0^{8n^3}y : |x|=n, |y|=8n^3, \text{$x$ is an assignment satisfying the 3CNF $y$} \}.
\end{align*}
$$
These two languages are clearly in P, and so their XOR is clearly in NP. However,
$$
(L_1 \oplus L_2) \cap \bigcup_{n=1}^\infty \{0^ny^2 : |y|=8n^3\} = \bigcup_{n=1}^\infty \{0^n y^2 : |y|=8n^3, y \text{ is satisfiable}\},
$$
showing that $L_1 \oplus L_2$ is NP-complete.


How to merge a lot of trees into one single graph? I have a few different trees, which resemble what the AST that compilers often deal with.

For example:

tree 1

( (a, b), (c, d) )

Imagine that each tree split represents the function "add", then tree 1 simply says: add a and b, then add c and d, in the end, add the sum of these 2 sums as the final result.

tree 2

(  ( (a, b), (c, d) ), (e, f)  )

obviously, I can merge tree 1 into tree 2, because tree 2 is simply constructed by adding a sibling (e, f) to tree 1.

By doing so, I don't need to re-visit a, b, c , d twice, I can simply add e and f, and add the result to the result of tree 1, to get the result of tree 2.

If I have a lot of these kind of trees, with overlapping (redundant sub-subtrees),  is there  an algorithm that can automatically create a graph that covers all the computation in the most efficient way ?

PS: all the trees share the same set of leaf,in this case, a b c d e f. Some trees are taller (deeper), some are shallower.

PS2: tree are not necessarily binary trees. A tree could have multiple

PS3: there could be a tree like ( (a,b), (g,h) ), i can still be partially merged with tree 1

Yes, this is sort of common subexpression elimination.

Simple approach for binary trees: introduce nodes 1 for a ... 6 for f.

Traverse your trees. When you have new pair like (1, 2) or (4, 5) introduce for them new nodes like 7 and 8, when you hit old pair, add edge from it.

You will need unordered map from pair of nodes to node, representing this pair:

(1, 2) -> 7
(3, 4) -> 8
(7, 8) -> 9
etc...

More on CSE avaliable by following links from wikipedia

If tree is not binary tree, first make it binary tree with first child / right sibling procedure. CSE in compilers most often is done on three-address code (like GIMPLE in GCC), i.e. on binary expressions only just because it is really more convenient


Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations? My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a solution set that solves the entire set of equations. It only needs to solve the MOST number of these equations. For example, if a given linear system has $n$ equations, then the solution set returned by the algorithm should "fit" the most possible number of equations in the system.

Example: if there are $N$ linear equations in a system $S$ of linear equations, then the algorithm should return a solution set that solves $m$ linear equations in $S$, where $m\le N$.

Based on what I have researched, none of the algorithms I know of will do this. Hopefully I am just missing something and I can get pointed into the right direction. Thanks.

Also, I forgot to add in that the given system of equations will have 10,000-1,000,000 variables, with x being Sparse. Is there a mod 2 algorithm or something similar to it that works on very large matricies?

$\mathsf{3LIN}$ is the following problem:

  Given a set of linear equations of the form $x_i \oplus x_j \oplus x_k = b$, where $1 \leq i,j,k \leq n$ and $b$ is a bit, find an assignment for the bits $x_1,\ldots,x_n$ that satisfies the largest number of equations.

There is a simple 1/2-approximation algorithm, which simply chooses a random assignment. Such an assignment satisfies half of the equations in expectation, and so at least 1/2 of the optimum. Using the method of conditional expectations, it is routine to derandomize this algorithm.

Håstad, in his paper Some optimal inapproximability results, showed that it is NP-hard to approximate 3LIN to within $1/2+\epsilon$ for any $\epsilon > 0$. In other words, the trivial algorithm mentioned above gives the optimal approximation ratio.


Is "sparse subtree" an appropriate term for what I describe in this question? Given a tree, with some nodes annotated, such that the annotations form another tree, I'm thinking "sparse subtree" is an appropriate term for describing the latter tree as it relates to the original tree. But I'd like to check with y'all because I plan to use the term in writing for an audience that will include CS savvy folk.

If not, I think "tree formed by the annotated subset of the nodes of the tree" will work but am hoping one of y'all will suggest something snappier than that.

2021 update: "embedded subtree"
In a discussion elsewhere8, I just encountered a term of interest with its own Wikipedia page: induced subgraph. This was roughly the sort of term I was after when I asked my original question, though it doesn't nail it.
It led me to google for "induced subtree". That has 80 matches and looked more appropriate for what I was after. But it still wasn't right because it disallows ancestor-descendant pairings that aren't parent-child.
That led me to "embedded subtree" in this paper which notes:

[In contrast to "induced subtrees"] Embedded subtrees ... allow not only direct parent-child edges, but also ancestor-descendant edges.

So maybe that's the right term.
On the other hand it still doesn't cover what I'm calling "annotation" -- the key notion that the nodes in the "subtree" are paired up with a subset of nodes in the original tree but are not actually the same nodes.
So due to that technical aspect, and for aesthetic reasons, I currently feel my original answer, which follows, remains as acceptable as it ever was. ;)
AST
This self answer defines the terms and acronyms I've made up to refer to what I asked about.1
The terms I've made up are general definitions of two kinds of tree data structure. I define them more precisely in later sections but in summary they are:

A Sparse Tree aka AST. A sparse subset of a tree.

Annotated Subset Tree aka AST. A sparse tree formed via "annotation".

Why define terms to distinguish the concepts when their acronyms eliminate the distinction? Because the mental modelling utility of eliminating the distinction is what I wanted to emphasize first and foremost, while still defining the distinction to make it clear what's going on behind the scenes.
AST typically refers to Abstract Syntax Tree
One existing typical meaning of AST in the CS world is the specific context I had in mind when I posed my question.2
So now we have not two but three ASTs. In the section Why three ASTs?!? below I'll return to why I'm defining three distinct tree concepts that all share the same acronym.
A Sparse Tree
By A Sparse Tree3 I mean a node of a tree data structure that serves as a root, plus any "well formed"4 potentially sparse subset tree formed of branch and leaf nodes relative to that root.
My example will be A Sparse Tree formed from a parse tree.5
If source code is like this:
foo = bar # Assign bar to identifier foo

And the parse tree is like this:
TOP
  statement                   foo = bar # Assign bar to identifier foo
    assignment                foo = bar
      identifier              foo
      assignment operator     =
      identifier              bar
    end-of-line-comment       # Assign bar to identifier foo

then the following represents two of many possible sparse trees based on that single parse tree:
# A Sparse Tree:
    assignment                foo = bar
      identifier              foo
      identifier              bar

# Another Sparse Tree:
    end-of-line-comment       # Assign bar to identifier foo

Annotated Subset Tree
By Annotated Subset Tree6 I mean A Sparse Tree represented/stored by annotating a subset of the nodes of a tree.
By "annotating" I mean hanging an additional node of data off selected nodes.
Why three ASTs?!?
One abstract use case for sparse trees is forming an Abstract Syntax Tree that consists of annotations of the Parse Tree generated by a parser.
When the distinction between A Sparse Tree, an Annotated Subset Tree, and an Abstract Syntax Tree is moot -- which is most of the time -- just use the acronym AST without worrying about the ambiguity, because, by my definitions, it doesn't matter.7
That's why the terms I've coined share the same acronym: AST -- so they can be understood as theoretically distinct things but, for some parser implementations, the same thing in practice.
Footnotes
1 My question was originally an attempt to find out if there was already an accepted term for what I described, generically in regard to trees, without regard for Abstract Syntax Trees. Then it became documentation of that attempt and the CS exchange community's response:

I'm not sure there is a standard term. Feel free to make up your own.
Just be sure to explain at least once in some detail what the term means.

2 I deliberately didn't state this context for my question because my original goal was to find out if there was a generic CS term about such trees.
3 A google for "sparse tree" suggests a few things, most notably a new christmas tree aesthetic and an aspect of a software feature (Emacs Org mode), as well as some genuinely CSish notions, but I didn't find any matching what I've described in this answer.
4 By "well formed" I mean that each node in the sparse/subset tree contains content from, and/or pointers to, the content of other nodes along branches proceeding in the direction of the tree's leaves from the sparse/subset tree's root node.
5 The word "sparse" is onomatopoeically reminiscent of "parse". This is a "happy mnemonic accident" given that the context for me naming these things is a sparse tree formed from a parse tree. It also reminds me of "A partridge in a pear tree" and I have fantasized that I will one day come up with and publish a worthy pun along those lines.
6 A google for "annotated subset tree" suggests a variety of CSish notions, but I didn't find any matching what I've described in this answer.
7 Of course, the usual use of the term "AST" in a CS context is an Abstract Syntax Tree. The whole point of this SO was to pick abstract terms describing a concrete approach that may be taken by parsers storing an AST. The fact that the terms all initialize to AST, with Abstract Syntax Tree being the dominant meaning of that acronym, is, of course, deliberate, and, imo, delightful.
8 A reddit.com/r/ProgrammingLanguages discussion


Function with minimum sensitivity Let sensitivity be defined as in Sensitivity and Block sensitivity

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity is $O(\log n)$?

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose average sensitivity is $O(\log n)$?

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity and average sensitivity is $O(\log n)$?

The tribes function is the classical example of a transitive balanced function whose average sensitivity is $\Theta(\log n)$. Its maximal sensitivity is however $\Theta(n/\log n)$.

The addressing function is an example of a balanced function depending on all inputs which has sensitivity $\Theta(\log n)$ and average sensitivity $\Theta(\log n)$. It is simpler to describe this function as having an input of size $n + \log n$: the first $n$ bits describe a binary string $x$, and the last $\log n$ bits describe a number $i \in [1,n]$. The output of the function is $x_i$. At any point the function depends only on the $\log n$ bits of $i$ as well as the single bit $x_i$.


There exist countably many enumerable disjoint and inseparable sets I want to formally prove that there are countably many disjoint enumerable sets such that any two of them cannot be separated by a decidable set.

I know that there exist a computable function $f$ that takes only values 0 and 1, and this can be used to define two sets (let's say $\mathcal{A}$ and $\mathcal{B}$, where $\mathcal{A}=\{x$ $s.t. f(x)=1\}$ and $\mathcal{B}=\{x$ $ s.t. f(x)=0\}$).

Could you please help me to extend this arguments to find (countably) many such sets?

Let $\phi$ be an enumeration of the set of recursive partial functions.

For each $i\in\mathbb N$, let $X_i = \{ n\ |\ \phi_n(0)=i \}$.

These sets are pairwise disjoint by construction. Each $X_i$ is recursively enumerable but not recursive.

These sets are pairwise inseparable. By contradiction assume there exist $i\neq j$, and a recursive set $A$ with $X_i \subseteq A$ and $X_j \subseteq \mathbb N\setminus A$. We reach a contradiction as follows. The function

$$
g(k,y) = \begin{cases}
  j & \mbox{if } k \in A \\
  i & \mbox{o.w.}
\end{cases}
$$
is computable, hence $g=\phi_c$ for some $c$. Now
exploit the s-m-n lemma to define $h(k) = \mathsf s(c,k)$, so that
$\phi_{h(k)}(y) = g(k,y)$.
Since $h$ is recursive total, by the second recursion theorem for
some $k$ we have $\phi_{h(k)} = \phi_k$.
Let us take one such $k$.
Finally,

$$
\phi_k(0) = \phi_{h(k)}(0) = g(k,0) = \begin{cases}
  j & \mbox{if } k \in A \\
  i & \mbox{o.w.}
\end{cases}
$$

Now, the result above is either $j$ or $i$. If it is $j$, then $k\in X_j$, hence $k\notin A$, hence the result above is $i$ -- contradiction.
If it is $i$, then $k\in X_i$, hence $k\in A$, hence the result above is $j$ -- contradiction.


Algorithm for selecting a sample that's as spread out as possible? I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as close to evenly distributed as possible).

E.g. if the dates are [1, 2, 3, 4, 100] and I want to sample 3 elements, the ideal sample would be [1, 50.5, 100] and the closest available dates are [1, 4, 100].

Is this a known problem with an existing algorithm?

I assume that for dates $d_1\leq d_2\leq\cdots\leq d_n$ you want $k>1$ samples of minimal total absolute distance from the ideal sample points $s_i=d_1+(i-1)(d_n-d_1)/(k-1)$, $i\in[k]$.

If you can repeat elements, just sample at $\operatorname{argmin}_{j\in[n]}|d_j-s_i|$ for each $i\in[n]$.

Without repeating elements the following dynamic program solves your problem in time $O(n^3)$ and space $O(n^2)$: let $M(i,j)$ be the minimal total absolute distance for $k-i+1$ samples chosen from $a_j,\ldots,a_n$ from the ideal samples $s_i,\ldots,s_k$. Distance $M$ satisfies
\begin{align*}
M(i,j) =
\begin{cases}
  \min_{j\leq j'\leq n} |d_{j'}-s_i|+M(i+1,j'+1), & \text{$i\leq k$, $j\leq n$, }\\
  0, & \text{$i>k$},\\
  \infty, & \text{otherwise},
\end{cases}
\end{align*}
and $M(1,1)$ is the minimum solution value.


For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free Basically I'm wondering if the concatenation of two equal length string is context free. I've seen multiple proofs of this online using PDAs but we aren't covering them in my automata course and my professor says they aren't needed for the proof. Any help would be greatly appreciated!

This is the full question:

For any two languages $A, B$ over $\Sigma$, define
$A \diamond B := \{xy\mid x \in A, y \in B, |x| = |y|\}$.
Show that if $A, B$ are regular then $A \diamond B$ is context-free

One way to show this is as follows. Make another copy of your alphabet, $\Sigma'$. Let $B'$ be the language $B$ over $\Sigma'$. The language $AB'$ is regular. By intersecting this with an appropriate context-free language, we can get the language of all words $xy'$, where $|x|=|y'|$, $x \in A$, and $y' \in B'$. Finally, we can remove the tags, replacing $\Sigma'$ with $\Sigma$.

Another way is using grammars. Construct an automaton $D(A)$ for $A$ and $D(B^R)$ for the reverse of $B$. Construct a grammar whose nonterminals encode a pair of states $(q_a,q_b)$, where $q_a$ is a state in $D(A)$ and $q_b$ is a state in $D(B^R)$. There will be productions $(q_a,q_b) \to \sigma_a (q'_a,q'_b) \sigma_b$ which correspond to transitions in both automata simultaneously, and productions $(q_a,q_b) \to \epsilon$ for all pairs of final states.

Yet another way is using NPDAs. The NPDA first simulates an automaton $D(A)$ for $A$, pushing a symbol $X$ into the stack whenever it reads a letter. It then nondeterministically transitions to simulating an automaton $D(B)$ for $B$ (only when reaching a final state of $D(A)$!), popping a symbol $X$ from the stack whenever it reads a letter. You should arrange matters so that the NPDA accepts only if it reaches a final state of $D(B)$, and moreover exhausts the stack. (You can do this using a special symbol found at the bottom of the stack.)

I'll let you work out the details.


Schedule management optimizer I had this idea of program tohelp me in my everyday life. We both work and don't live in the same city. I was wondering how to make a program that calculate, depending on the work scheduleand the number of travel required between both our house, the best way to spend our weekend, like at which house we have to be and when to spend the maximum time together. I know this sound like a problem you'd get in a school book but i really cant think of how to do it.

There is lots of literature on scheduling, as it is a very important topic. You'd need to make your problem more precise, in particular define your objective and any restictions on the tasks. Note that most such problems are NP complete (no efficient solution likely).

I'd guess that some sort of brute force search is possible, or some sort of dynamic programming solution (but it seems that the restricted subproblems arising are different).


Meaning of # in descriptions of languages This is a very simple question, but I cannot find the answer anywhere, mostly because I don't know how else to ask about what I'm looking for. I have a homework assignment that has to do with pumping lemma, which asks me to use the pumping lemma to prove that the language given is not regular.

{x₁#x₂#x₃|x₁, x₂, x₃ ∈ {a, b}* and x₂ = x₃ᴿ}.

My only question is this — what does the # mean? My teacher is currently unavailable, so I'm unable to ask him.

If someone has a link to a list of notations and their descriptions, I'd very much appreciate it, but if you're only able to tell me what # means, that's fine as well.

It's just a symbol in the alphabet, so the alphabet is $\{a,b,\#\}$ and the language is the set of strings that:

contain exactly two $\#$'s and
the string after the second $\#$ is the reverse of the string between the two $\#$'s.


Why does merge sort run in $O(n^2)$ time? I have been learning about Big O, Big Omega, and Big Theta. I have been reading many SO questions and answers to get a better understanding of the notations. From my understanding, it seems that Big O is the upper bound running time/space of the algorithm, Big Omega is the lower bound running time/space of the algorithm and Big Theta is like the in between of the two.

This particular answer on SO stumbled me with the following statement

  For example, merge sort worst case is both ${\cal O}(n\log n$) and $\Omega(n\log n)$ -
  and thus is also $\Theta(n\log n)$, but it is also ${\cal O}(n^2)$, since $n^2$ is
  asymptotically "bigger" than it. However, it is NOT $\Theta(n^2)$, Since
  the algorithm is not $\Omega(n^2)$

I thought merge sort is ${\cal O}(n\log n)$ but it seems it is also ${\cal O}(n^2)$ because $n^2$ is asymptotically bigger than it. Can someone explain this to me?

This is actually a mathematical matter and not the matter of the worst case running time. First you have to know that Big O does not represent worst case running time of some algorithms. Big O comes from mathematics and it represents an asymptotic upper bound for some mathematical functions.

You can see that the graph of $n^2$ is always above the graph of $n\log n$. so you can say $n^2$ is an upper bound on $n\log n$ as the value of $n\log n$ is always less than $n^2$. So mathematically you can say $n\log n=O(n^2)$. Similarly graphs of all $n^i$ for $i\geq 2$ are always above the graph of $n\log n$. So you can say $n\log n$ is also $O(n^3),O(n^4),O(n^5),\ldots$

But one thing you have to remember that though $n\log n$ is $O(n^2)$ but $n\log n$ is not $\Theta(n^2)$, because $n\log n$ is not $\Omega(n^2)$. Mathematically you can say $n\log n$ is $o(n^2)$.

If you still have any confusion regarding my answer, you can ask me here.


Selection of K elements of given ranks Given a procedure/function

$Select(S,r)$ - which selects element of rank r from set S
which uses at most $|S|. constant$ comparisons

We design another function $Multiselect(S,R)$
with $R =\{r_1<r_2<...<r_k\}$
returns $X =\{x_1<x_2<...<x_k\}$  such that rank of $x_i$ is $r_i$

What is the minimum no of comparisons for this function?

From Wikipedia I found the upper bound for it -

But while utilising this for deriving the answer I got it totally messed up!
I tried using algorithm to utilise Select(S,r) repeatedly each time
each time decreasing the search space by logn  ... but I guess the answer could be found
in a more concise mathematical way.

By the way, answer given was - $constant.|S|(1+logR)$

Hint: Find first the element of rank $r_{(k+1)/2}$, and split the list accordingly into two parts $S_1,S_2$ satisfying $|S_1| + |S_2| = |S|$. Now repeat.


Minimizing the full adder - where did this XOR come from? When minimizing the full adder, I don't understand why $A(\bar{B}\bar{C} + BC)$ reduces to $A\overline{(B\oplus{C})}.$

$(\bar{B}\bar{C} + BC)\to (B\oplus{C})$ is partially decipherable, but why is $(B\oplus{C})$ inverted to $\overline{(B\oplus{C})}?$

Full adder simplification:

$
\bar{A}\bar{B}C + \bar{A}B\bar{C} + A\bar{B}\bar{C} + ABC \\
= \bar{A}(\bar{B}C + B\bar{C}) + A(\bar{B}\bar{C} + BC) \\
= \bar{A}(B\oplus{C}) + A(\overline{B\oplus{C}}) \\
= A\oplus{(B\oplus{C})}
$

Could you help me out?

PS: I hope that this is the correct subforum of StackExchange to ask this (perhaps Electrical Engineering is the proper venue). I couldn't find appropriate tags on either site.

Consider the truth table for $(\overline{B}\overline{C}+BC)$. It has 1's exactly when $B$ and $C$ get the same value, which is exactly when $(B\oplus C)$ gets 0, hence, $\overline{B\oplus C}$ is equivalent to $(\overline{B}\overline{C}+BC)$.


Sorting criteria for Kruskal's algorithm I am studying Kruskal's algorithm. Is the only acceptable sorting criteria to sort edges from lowest weighted edge to greatest weighted edge? I ask this because I assume that if the algorithm used an alternative sorting criteria say, greatest to lowest, then it would not produce a MST. My reasoning is that edges with larger weights would be added first.
Any help with this concept would be greatly appreciated.

Yes, for Kruskal's you have to sort it in ascending order of weights, for precisely the reason that you gave.
There is, however, another algorithm, namely Reverse-Delete which is essentially the opposite of Kruskal's. You start with the original graph, and process edges in descending order of weight. Then we remove each edge while the graph is still connected.


Where can I find a high quality copy of Turing's On Computable Numbers? Currently, I'm reading a photocopied version of Turing's famous article On Computable Numbers, With an Application to the Entscheidungsproblem.

This is the best photocopy of his paper that I can find; most other copies are of pretty low quality to the point that I can't distinguish between different characters. The e in the final m-config column on page 233 for example, looks exactly like a c on many copies (not the one I'm using though). I also have trouble distinguishing between the german capitol letters C and E later in his paper on page 238 and such. Is there any place where I can find a well copied version of the paper? Perhaps a book would have a nice copy.

There is a very high resolution scan in the Turing Digital Archive, however it's presented via a flash player plugin which makes reading mildy awkward and doesn't seem to allow printing.

There are a handful of marginally nicer PDF copies than that Caltech one you link available online [1][2], however they all seem to have been drawn from the same photocopy at some point.


Can the loops be in any order in the Floyd-Warshall algorithm? I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page:
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j]
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

Our professor told us that the loop for k MUST be outside the i and j loops. I am unable to understand why this must be the case. He said that if k is inside we will only compute the best 2 edged or 1 edge path from i to j. I just don't see it. Can someone help?

Suppose that you change the order of loops from $k,i,j$ to $i,j,k$. Let's see what happens when $i=1$ and $j=2$:
for k from 1 to |V|
  if dist[1][2] > dist[1][k] + dist[k][2]
    dist[1][2] ← dist[1][k] + dist[k][2]
  end if
end for

It is not too hard to check that this puts in dist[1][2] the value
$$
\min_{1 \leq k \leq |V|} w(1,k) + w(k,2),
$$
where $w(1,1) = w(2,2) = 0$. This is the cost of the shortest path of length at most $2$ from $1$ to $2$.
The $(1,2)$'th iteration is the only one which modifies dist[1][2], so at the end of the procedure, dist[1][2] will still contain
$$
\min_{1 \leq k \leq |V|} w(1,k) + w(k,2),
$$
which could be arbitrarily off from the real shortest path from $1$ to $2$.


How to compute amoritized cost for a dynamic array? I am trying to understand how to do the amortized cost for a dynamic table. Suppose we are using the accounting method.

Let A of size m be an array of n elements. When $n = m$, then we create a new array of size $4m$, and then copy the elements of A to the new array. When $n = \frac{m}{4}$, then you create a new array of size $\frac{m}{4}$, and copy the elements to that array.

What I am confused about is how to calculate the costs.
From what I know so far:
Before the first expansion, you pay two dollars to insert. 1$ for the insert, and 1$ you just store with the element, so that you can use that later for a copy operation.

Then when you expand it, you use that stored $ to move the element to the new array.
Now in the new array the elements won't have any $ with them. But now as you insert a new element, you use 3$. 1$ for the insert, then one more for itself (for a future copy), and one more for the previous element that was just copied.

The problem here is, what if you have an array like this:

1$ 2$

Then insert an element

1$ 2 3$ _ _ _ _ _

Now how do you handle a delete operation?

I think your particular structure does not have amortized $O(1)$ cost, and you identified the problem.

Your general approach is salvageable, but you either need to grow less aggressively or shrink less aggressively. The standard solution is to grow from capacity & size $n$ to capacity $2n$ and to shrink from capacity $n$ and size $n/4$ to capacity $n/2$.


Red black tree partition to $\sqrt{n}$ trees This is a question I have stumbled upon in an old Algorithms test I found online:

  A) Plan an algorithm that does the following:
  Input: Red-Black tree
  Output: $\sqrt{n}$ seperate trees, so that every tree has $\sqrt{n}$ nodes.
  What is the complexity of the Algorithm you planned? must show analysis.

  B) Assume that you have started from an empty Red Black tree, and that the input is a
  set of nodes and not a Red Black tree.
  Show how can you make a more efficient algorithm of partitioning the nodes to $\sqrt{n}$
  Red Black trees so that every tree has $\sqrt{n}$ nodes.
  What is the complexity of the new Algorithm you planned and how does it affect existing Red Black tree functions? must show analysis.

Now I have answered A and I am pretty sure that's the best answer there is, but I need your help in telling me if I can do better. This is without analysis:

  Algorithm:
  1. Scan the Red Black tree using In-Order traversal to build a sorted array out of it. < > O(n).
  2. Divide the array to $\sqrt{n}$ sub-arrays and build a Red Black tree out of every sub > array - O(n) total.

Now what I don't really understand is how do I solve B.
I'm not exactly sure if the input in B is a Red Black tree or just a set of nodes, so both will be acceptable if you want to share your answer to B with me.
I have asked a student and he told me that the complexity that I should get in B is $O(\sqrt{n}*log(n))$.

I need help reaching that, or maybe something better (hints and stuff).

For question B) you need to make $O(\sqrt{n})$ RB trees from $n$ nodes (there is no tree to start with just bunch of nodes). Thus you need to process each node at least once. Thus time complexity of this building should be $\Omega(n)$. Thus I think there is no hope of getting the $O(\sqrt{n}\log n)$ bound.


Are Kernel Codes (which are written in C) compiled during boot time? I have a confusion regarding how the Kernel is loaded during the boot time. The intuition I have is like following:

During installation of an OS, the compiled Code of the Kernel (depending on the architecture of the system) is written to the part of the Primary Memory that is restricted to the OS. When the PC is turned on, during boot time, initial some of the Assembly Instructions are executed to start-up (like creating the process init and starting other services).

But how the other processes, services are created ? Are all codes are compiled to Assembly codes during installation or Kernel codes (written in C) are compiled during boot time? If the latter happens, then is GCC pre-installed to the OS address space?

Usually, everything is compiled in advance: the kernel and userland applications.

Roughly, the kernel is written in a special place on the disk (or other permanent memory), which the hardware will access at boot time, copy in RAM, and execute.

The kernel includes the disk driver and the filesystem driver, and will look for specific files on the disk, using them to load the first OS process (e.g. /bin/init, in unix-like OSs). This will in turn ask the OS to spawn new OS services/daemons, load new drivers, and finally start the user interface.

There is no need to have a compiler around during this. All the code which is loaded is machine code (already compiled).

The compiler is also not needed at installation time, since whoever produced the installation media (or network repository) wrote binary packages in it, containing compiled code.


How to prove that a transformed language is regular using an NFA I am trying to prove that if a language $ L $ of binary strings (i.e. a subset of [01]*) is regular then so is the transformed language $ plus (L) $ consisting of the binary representations of those integers one greater than those represented by the elements of $ L $. That is to say $ plus (L) = \{ plust (l) : l ∈ L \} $ where $ plust $ transforms a binary of an integer $ n $ to a binary of $ n + 1 $, so $ plust ("0111") = "1000" $.

I am trying to prove this by assuming that there is a DFA that accepts $ L $ and using it to build an NFA that accepts $ plus (L) $.

However, I am totally at a loss as to how to do this. What is a good starting point, or what steps can I take to produce such a proof?

Here's how to do it using closure operations; a similar idea can be used for constructing an NFA.

There are three cases to consider. The first case is words consisting only of ones. In this case, we want to transform $1^n$ to $10^n$. We accomplish this as follows. Let $h\colon \{0,1\} \to \{0,1\}^*$ be the homomorphism defined by $h(0) = 1$ and $h(1) = 0$. We capture this part of $\operatorname{plus}(L)$ by the expression $1h(L \cap 1^*)$.

The second case is words of the form $1x01^n$, which should be transformed to $1x10^n$. Here the construction is a bit more complicated. Let $a\colon \{0,1,0',1'\} \to \{0,1\}^*$ be defined by $a(\sigma) = a(\sigma') = \sigma$ (where $\sigma \in \{0,1\}$). The expression $a^{-1}(L) \cap 1(0+1)^*0'1'^*$ replaces $x01^n$ with $x0'1'^n$. To complete the transformation, define $b\colon \{0,1,0',1'\} \to \{0,1\}^*$ by $b(\sigma) = \sigma$, $b(0') = 1$, and $b(1') = 0'$. The expression $b(a^{-1}(L) \cap 1(0+1)^*0'1'^*)$ handles this part of $\operatorname{plus}(L)$.

The final case is the word $0$ (if it is in $L$), which should be transformed to $1$. This is accomplished by $h(L \cap 0)$.

In total, we obtain
$$
\mathrm{plus}(L) = 1h(L \cap 1^*) \cup b(a^{-1}(L) \cap 1(0+1)^*0'1'^*) \cup h(L \cap 0).
$$
Note that any words in $L$ which are not binary encodings (in other words, the empty string and strings with leading zeroes) are just ignored. This can of course be changed if wanted.


What makes a proof assistant a proof assistant? You open a code editor, define a syntax with lambdas, a few primitives. Then you invent some nice computation rules, some cool typing rules, and write a corresponding interpreter and "type checker". Congratulations! You just built a proof assistant! Now you can formalize all of mathematics on it! Or can you? After all, what makes the thing you built a valid "proof assistant"? What constitutes a "type checker"? As far as I'm concerned, you could have actually implemented Tetris, claimed that blocks are terms, their shapes are types, and the game loop is the computation rule. Who has authority to argue you're wrong?

When it comes to implementing a "programming language", the definition is much more clear. Just invent a syntax, a set of reduction rules and prove your thing Turing-complete. Then it is as good as a programming language is expected to be. When it comes to implementing a proof assistant, I have no idea. Sure, there are common things I see present in proof assistants, so, intuitively, I know what they are. They have lambdas and the corresponding dependent function space, they have inductive datatypes and their introductions and eliminations, and they must be consistent, which mean at least some type is uninhabited. But what if my "proof assistant" has no lambdas nor datatypes? It could have for example just combinators. I don't have a precise definition of what makes a "type theory" a "type theory".

What, formally, makes a program a valid proof assistant, in the same sense that Agda/Coq are? What is a precise and complete definition of a type theory? And what one must do to "justify" his syntax, reduction and typing rules? I'm making this specifically because, while I feel like I can, given enough time, implement something like A Cosmology of Datatypes, I do not feel the freedom to make any change, even minimal, to whatever the author did, because I do not know what justifies those things he did.

I would expect a proof assistant to provide:

a syntax to express some mathematical statements
a syntax to express a proof of one of those statements
a computational process to "check" that a proof of a statement is indeed valid (returns success or failure, or maybe does not return at all)

Finally, for such a proof assistant to be trustworthy, it should come with a justification of the fact that when its checking process says that a proof of a statement is valid, then indeed this statement is valid in the usual mathematical sense -- there exists a mathematical proof that mathematicians will accept.


interactivity between RAM and CPU I have a very silly question, when data is transferred from the RAM to the CPU is this data transferred "copies" of the original data stored inside the RAM?

Yes, I think it's reasonable to consider that as a copy of the data in the RAM.  It's a copy in the sense that if you modify the data in the CPU, the data in RAM remains unchanged.
(But at the end of the day it doesn't really matter what you call it: the computer is going to do what it does, regardless of what words you use to describe it.)


Generate the word using this grammar Using this grammar, over the alphabet $\Sigma=\{a\}$
$$
S \rightarrow a \\
S\rightarrow CD \\
C\rightarrow ACB \\
C\rightarrow AB \\
AB\rightarrow aBA \\
Aa\rightarrow aA \\
Ba\rightarrow aB \\
AD\rightarrow Da \\
BD\rightarrow Ea \\
BE\rightarrow Ea \\
E\rightarrow a \\
$$
Im trying to show that the working string $aaaaaaaaaBBBAAAD$ or $a^{n^2} B^nA^nD$ generates the word $a^{(n+1)^2}$

Start at the end! There is only one applicable production: #8. $D$ moves backward over the $A$'s turning them into $a$'s. Then use #9, and repeatedly #10.

Please take a piece of paper and count the $a$'s generated. Probably the expression $(n+1)^2 = n^2+2n+1$ is useful.


Does topological sort exist for any complete directed acyclic graph? Let's assume that DAG is complete: there is directed edge among every to nodes. Does topological sort of vertices exist for any such graph? I.e. is it possible to make linear list of nodes in which the left node has edge into the right node. Maybe this is the question about existence of Hamiltonian path in every complete DAG?

Yes it exists and the existence of a linear ordering not only shows the existence of the topological oredering over the vertices but also that this ordering is unique. It is not hard to prove that the graph represents a linear ordering using the facts that the graph is complete and acyclic. That should be a good exercise for you (proving a relation is a linear ordering means to prove it is reflexive, asymmetric and transitive).


Longest path length in an undirected tree, can we prove this algorithm is correct (which it is)? Hello I solved this leetcode https://leetcode.com/problems/tree-diameter/ question reserved for people who pay the subscription.

The question:

  Given an undirected tree (tree is not disjoint), return its diameter: the number of edges in
  a longest path in that tree.

  The tree is given as an array of edges where edges[i] = [u, v] is a
  bidirectional edge between nodes u and v.  Each node has labels in the
  set {0, 1, ..., edges.length}.

So the "easy" way to solve it is to start a dfs at each node in the tree and keep track of the longest path seen so far, which would be O(n^2). Given n = number of vertexes in the graph.

However I came up with the below solution that does the job in O(n), I was able to come up with it by going through examples on a piece of paper and then coded it and it passed all the tests, but I can't figure out why it formally works, can anyone help me prove it is correct ?

Here is my code:

   def treeDiameter(self, edges: List[List[int]]) -> int:
    def dfs(graph, vertex, prev, maximums):
        for neighboor in graph[vertex]:
            if neighboor != prev:
                tmp = 1 + dfs(graph, neighboor, vertex, maximums)
                if tmp > maximums[vertex][0]:
                    maximums[vertex][1] = maximums[vertex][0]
                    maximums[vertex][0] = tmp
                elif tmp > maximums[vertex][1]:
                    maximums[vertex][1] = tmp
        return maximums[vertex][0]

    graph = collections.defaultdict(list)
    for vertex1, vertex2 in edges:
        graph[vertex1].append(vertex2)
        graph[vertex2].append(vertex1)

    maximums = [[0, 0] for _ in range(len(edges) + 1)]
    dfs(graph, 0, None, maximums)

    res = 0
    for max1, max2 in maximums:
        res = max(res, max1 + max2)
    return res

The way I came up with this is I realized if I start my dfs at a node that is on the longest path, then the longest path is equal to the sum of the two longest pathes (because it is a tree there are no cycles) out of this node (which is why I store the two longest pathes max1, max2 out of a node in the maximums array) --> but what I fail to see is why that works in all cases.

I think this might help. Copied from https://stackoverflow.com/questions/20010472/proof-of-correctness-algorithm-for-diameter-of-a-tree-in-graph-theory.

Let s, t be a maximally distant pair. Let u be the arbitrary vertex. We have a schematic like,

    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t

where x is the junction of s, t, u (i.e. the unique vertex that lies on each of the three paths between these vertices).

Suppose that v is a vertex maximally distant from u. If the schematic now looks like

    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,

then

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),
where the inequality holds because d(u, t) = d(u, x) + d(x, t) and d(u, v) = d(u, x) + d(x, v).
There is a symmetric case where v attaches between s and x instead of between x and t.

The other case looks like

    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .

Now,

d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)

d(s, t)  = d(s, x) + d(x, t)
         = d(u, s) + d(u, t) - 2 d(u, x)
        <= 2 d(x, v)

2 d(s, t) <= d(s, t) + 2 d(x, v)
           = d(s, x) + d(x, v) + d(v, x) + d(x, t)
           = d(v, s) + d(v, t),
so max(d(v, s), d(v, t)) >= d(s, t) by an averaging argument, and v belongs to a maximally distant pair.

PS: I saw many answers after searching the question. I do not have enough repuation to comment otherwise I would have done so.


Complexity of calculating average across distributed network? What is the communication complexity of the best known algorithm for computing the average of a set of N*D numbers distributed across N nodes with D values per node? Assume you have full control over the network topology and protocol.

You could rely on the fact that, as @polygeric alluded to, the average of a set of numbers is the average of the averages over any partition of the original numbers. In other words, have each node compute the average of its $D$ numbers, send those $N$ averages somewhere and compute their averages.

How you do that efficiently will depend on the network topology and the communication protocol.


In a BOINC project, how are responses checked for accuracy? More specifically, how can project administrators be sure that the answers they receive from nodes are correct and not just simple calculations performed quickly and submitted as complete work units? As various cheating scandals have shown, people are not above stooping to low levels to get to the top of project points tables...

Part of the checking that is performed by the BOINC platform to avoid cheating is to send the same work units to different users, and then verify that the results are the same.


How to prove that there is no better algorithm Input: Set of machines M, Each machine has an availability array D_m[t],
set of activities A, for each activity j its starting time s_j,
its duration p_j and its consumption in D during processing.

Output: True or False if the usage for  each machine at each instant is less than the availability

for each machine m in M

  usage := array[0..L] of zeros

  for each activity j in A
    usage[s_j] += c_{j,k}
    usage[s_j + p_j] -= c_{j,k}

  for each time t in [1, L]
    if usage == 0
       usage[t] += usage[t-1]

  for each time t in [0, L-1]
    if usage[t] > D_m[t]
      return false

return true

The complexity is $O(|M| * (L + |A|))$. But $L$ is not an input length, it's a numerical value. I guess it's pseudo-polynnomial (Am I right ?)
How to prove that there is no better alternative, In other words that its also $\Omega(|M| * (L + |A|))$

I presume that $L$ is the length of $D_m$ for all machines.
Hence your input is of size $O(|M|\cdot (L+|A|))$ because it contains $|A|$ activities for all machines and the $D_m$ array of length $L$ for all machines. Your runtime is $O(|M|\cdot (L+|A|))$. Thus your algorithm runs in linear time with respect to your input
(meaning your algo is not pseudo-polynomial it is in fact polynonmial and even linear).
If a value in $D_m$ could be below $0$ we would have to check every value in $D_m$ for every machine at least once and for every activity that $D_m$ is large enough making the minimum runtime $\Omega (|M|L + |M||A|) = \Omega (|M|(L+|A|))$ and thus your algo optimal.


Is there a specific problem that is in both NP and co-NP but not in P? A problem is in NP if a correct answer to it can be verified to be so in polynomial time.

A problem is in co-NP if an incorrect answer to it can be verified to be so in polynomial time.

P is a subset of the intersection of the sets NP and co-NP.

My question is: what is a specific problem that is in the intersection of co-NP & NP, but is not in P?

An answer to your question would be a problem $p$ which is in $\mathop{NP}\cap\mathop{coNP}$, and thus in $\mathop{NP}$, but not in $P$. Existence of such a problem would easily imply $P\neq\mathop{NP}$, which is a seriously open problem to this date. That is to say, no one can answer your question yet.


What is an algorithm for minimizing the standard deviation of m sums summed from n summands? [with attempt] I have m bins (sums) and n summands. Each summand goes into a bin. In order to minimize the standard deviation, I have a greedy algorithm that appears to accomplish this. I am not sure of the name, but would like to know more. All m bins must have a sum greater than zero at the end of the algorithm.
It seems simple:
sort the summands from highest to lowest.
for each summand in the summands:
find the first available bin with minimum sum and place it in the bin
I haven't proved anything about it, but I've come up with a few test data sets and it appears to work.
EDIT --- Here is my attempt at an analysis:
The algorithm seeks to minimize the standard deviation of m sums summed from n summands.
The mean is always the sum of n summands divided by m, that is given.
To minimize the standard deviation, the algorithm makes the greedy choice to minimize the standard deviation, or variance (either). I want to prove that the greedy choice is always the optimal choice.
Suppose there is a bin m1, not the minimum sum bin, that is a better choice than minimum sum bin m. Adding to this bin will minimize the standard deviation around u.
In other words, placing the next value n into this m will maximally decrease the variance, meaning that we have maximally decreased the sum of (m_i - u)^2. NOTE: m1' = m1 + x, m' = m + x, where x is the next summand.
So:
remaining_sum_var + (m1' - u)^2 + (m - u)^2 < remaining_sum_var + (m' - u)^2 + (m1 - u^2) where m1 is greater than m.
Simplify and factor:
(m1' - u)^2 + (m - u)^2 < (m' - u)^2 + (m1 - u^2)
m1'^2 - 2um1' + 2u^2 + m^2 - 2um < m'^2 - 2um' + 2u^2 + m1^2 - 2um1
m1'^2 - 2um1' + m^2 - 2um < m'^2 - 2um' + m1^2 - 2um1
Ignoring linear terms whose difference will be constant (linearity).
m1'^2 + m^2 < m'^2 + m1^2
If we have added summand x to m1 this expands to:
(m1 + x)^2 + m^2 < (m + x)^2 + m1^2
m1^2 + 2m1x + x^2 + m^2 < m^2 + 2mx + x^2 + m1^2
2m1x < 2mx
m1 < m, this is a contradiction. So it cannot be the case that there is a better choice than minimum sum bin m.

No, your algorithm does not always produce the optimal solution.  When $m=2$, this is (at least as hard as) the Partition problem, which is NP-hard.  Wikipedia discusses the greedy algorithm and lists a counterexample which shows that your algorithm does not work.


Formal grammar with constraints on the number of each symbol I have a language where each type of symbol is only allowed a particular number of times, but the order isn't important. For example, lets say there are three symbols $a, b, c$, and a valid string in the language consists of at most 5 $a$, 3 $b$ and 2 $c$ characters. So $ababbc$ is valid, $ccbbbaaaaa$ is valid, but $abcabcabc$ is not. I'm struggling to come up with a grammar that satisfies such constraints without resorting to enumerating each possibility. Is it possible to have a concise set of rules that encode these constraints?

No.

Since the permutation language is finite, you can produce a grammar by enumerating the individual sentences which comprise the language. Some simplifications are possible, for example by finding common prefixes and/or suffixes. But there is no grammar which is significantly smaller than the language itself (for some definition of "significantly").

This is not really as dramatic a conclusion as it sounds. Most finite languages lack compact grammars; grammars achieve concision when they can use recursive constructs which represent infinite languages.

In fact, in an interesting paper cited in the answer to this question on https://cstheory.stackexchange.com/, there's a proof that the no regular expression for the language $P_n$ consisting of the permutations of $\{1,2,\dots,n\}$ can be shorter than $2^n$. However, the (infinite) inverse $\overline{P_n}$ can be described by a regular expression of size $O(n^2)$. (There are lots of other interesting results in that paper.) @yuval-filmus extended that result in Lower Bounds for Context-Free Grammars to a larger set of languages, including the language of permutations of the multiset of $n$ different elements in which each element appears $k$ times.

In the halcyon era of SGML, whose syntax description language included a permutation operator, there was some investigation into how to optimise state machines to recognise such languages. IIRC, the final conclusion was that it can't be done and therefore the permutation operator is not a good idea. In practice, such languages are generally recognised in two phases: first, the input is matched against the infinite language of unrestricted repetitions, and then a second scan (not implemented with a CFG) is done to count repetitions of each element. But that algorithm is not completely sound. First, it assumes that there is a unique decomposition of a string into elements, which is not always the case, although it certainly was the case for SGML. Second, the algorithm greedily processes all successive elements. If the intention of the grammar were to recognise the longest legal permutation, leaving open the possibility that (over-)repeated elements be part of a different syntactic construct, then legal inputs will fail because of the greediness.


The algorithm yields optimal ternary codes Steps to build Huffman Tree
Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.

Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)
Extract two nodes with the minimum frequency from the min heap.
Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.
Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

If we would like to generalize the Huffman algorithm for coded words in ternary system (i.e. coded words using the symbols 0 , 1 and 2 ) I think that we could do it as follows.

Steps to build Huffman Tree
Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.

Create a leaf node for each unique character and build a min heap of all leaf nodes
Extract three nodes with the minimum frequency from the min heap.
Create a new internal node with frequency equal to the sum of the three nodes frequencies. Make the first extracted node as its left child, the second extracted node as its middle child and the third extracted node as its right child. Add this node to the min heap.
Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

How can we prove that the algorithm yields optimal ternary codes?

We can’t prove that, but we can disprove it. The given algorithm is not always optimal. In step 2, three nodes may not be available, so there is more than one way to build the tree. That can’t happen in the binary case.

Consider a min heap containing four characters, whose frequencies are 0.4, 0.3, 0.2, and 0.1. The given algorithm yields the tree on the left, with mean length 1.6. The optimal tree is shown on the right, mean length 1.3.

@PeterShor’s comment above indicates that a correct algorithm is known, but I haven’t seen it.


Find two contiguous subarrays with the greatest difference Here's an interview question I've seen on a few sites. People claim that an O(n) solution is possible, but I've been racking my brain these last 2 days and I couldn't come up with a solution, nor find one anywhere on the web.

Given an array of integers, find two disjoint, contiguous subarrays such that the absolute difference between the sum of the items in each subarray is as big as possible.

Example input: (2, -1, -2, 1, -4, 2, 8)

Example output: ((1, 4), (5, 6))

The output above is the indices of these two subarrays: ((-1, -2, 1, -4,), (2, 8))

I've been trying to reduce this problem to the Maximum subarray problem but with no success.

Because the two subarrays are disjoint, there exists at least one index $m$ such that one entire subarray lies $\leq m$ and the other subarray lies $\gt m$.

But we do not know what this $m$ is, beforehand. So let us iterate over all the $n$ possibilities for $m$. Now if an $m$ is fixed, then the problem reduces to the Maximum subarray problem, and the Minimum subarray problem. This is because for the absolute difference to be the largest, one side of $m$ should have the maximum possible subarray, and the other side should have the minimum possible subarray. So we try both of these options and take the maximum absolute difference among the two.

But this is still $\mathcal{O}(n^2)$, because there are $n$ different values of $m$, and for each of those values, we have to spend $\mathcal{O}(n)$ time to compute the needed minimum and maximum subarrays.

The next observation is to note that a single $\mathcal{O}(n)$ run of the Maximum subarray algorithm on the entire array can actually give us one of the needed values for all values of $m$:

Given: int A[n]

MaxSubarrayTill[0] = A[0]
MaxSubarrayEndingAt[0] = A[0]
for(i = 1; i < n ; i++)
{
    MaxSubarrayEndingAt[i] = max{A[i], MaxSubarrayEndingAt[i - 1] + A[i]}
    MaxSubarrayTill[i] = max{MaxSubarrayTill[i - 1], MaxSubarrayEndingAt[i]}
}

Here, $\text{MaxSubarrayTill}[i]$ denotes the maximum sum subarray which ends $\le i$, and $\text{MaxSubarrayEndingAt}[i]$ denotes the maximum sum subarray which ends at index $i$.

Similarly, we can compute the $\text{MinSubarrayTill}[i]$ array in $\mathcal{O}(n)$ time. And by repeating the same two algorithms in reverse (ie. from the end of the array to the beginning), we can get $\text{MaxSubarrayFrom}[i]$ and $\text{MinSubarrayFrom}[i]$.

So in $\mathcal{O}(n)$ time we have precomputed all the values that we needed in the first algorithm, which we can now go back to. Interate over all the values of $m$, and find the largest absolute difference in $\mathcal{O}(n)$ time.

If the problem also stipulates that the two subarrays should be adjacent, then we can leave out $\text{MaxSubarrayTill}[i]$ and its analogous arrays, and instead only consider $\text{MaxSubarrayEndingAt}[i]$ and its analogous three other arrays. The rest of the algorthm remains the same.


Find missing value in period of LCG It's well known that linear congruential generators have a full period only if a few properties are fulfilled.

Now I need a LCG that does not generate a full period in 2^32 (easy to find, just violate one requirement) and I need one of those values in the period that's not used.

Is there any clever math trick/algorithm to find such a thing? I can see the obvious bruteforce solution, but that'd take quite some time and tons of memory - also it seems like an interesting math problem. I did check Knuth but he obviously focuses on showing how to get a full period.

PS: For people wondering - I have to trick a compiler into making sure it can't use DCE on some values and this seems like a very performant and hard to figure out way to achieve this.

Actually, bruteforce should work just fine.  You can quickly find a set of taps that doesn't have a full period, then find a value that's not in the period.  Here's what I'd do:

Randomly pick a set of taps (a feedback polynomial).
Verify whether this has a single full period of size $2^{32}-1$, as follows. Randomly pick a starting state $s_0$ (not the all-zeros state).  Iterate forward starting from $s_0$, and see whether you get back to $s_0$ within at most $2^{32}-1$ steps.  In this way, you can compute the period after starting from $s_0$.  If this period is $2^{32}-1$, go back to step 1.
Now you have a LFSR and a starting state $s_0$, such that the full period is less than $2^{32}-1$; next you want to find a state $t$ that is not within the set of states reachable from $s_0$.  Here's one way to do that:

Randomly pick 10 states $t_1,t_2,\dots,t_{10}$.  These will be your 10 candidates for $t$.  Initially, each of them is unmarked.
Now run the LFSR forward, starting from $s_0$, until you get back to $s_0$.  At each step compare the current state of the LFSR to $t_1,t_2,\dots,t_{10}$.  If the current state of the LFSR is equal to $t_i$, then mark $t_i$.
At the end, when you get back to $s_0$, look at which of the $t_i$ are marked.  If one of the $t$'s is unmarked, say $t_j$, then you are done: you have a LFSR feedback polynomial and a starting state $s_0$ such that you know $t_j$ is not within the period of values starting from $s_0$.  If all of the $t_i$'s are marked, go back to step 1.

How long will this take?  Probably about $2^{32}$ operations.  I would expect at least $1/2$ of the choices of feedback polynomials to lead to a LFSR with less than full period, so you shouldn't have to repeat steps 1-2 too many times (on average about 2 times).  Each repetition takes $2^{32}$ operations.

Now once you find a good LFSR, where $s_0$ does not lead to a full period, then the period that's reachable from $s_0$ will be on average about $2^{31}$ or smaller.  Thus, step 3 will take about $2^{31}$ operations.  Also, this means that about $1/2$ of all possible states will be unreachable.  Therefore, with probability $1-1/2^{10}$, at least one of your 10 candidates for the $t$'s will be good, so the chances that you have to repeat step 3 is very low.

So, this is probably good enough.  This is easy to code up and will probably finish within a few hours or less.

There are cleverer things you can do, but they probably don't make sense in practice.  You could spend a bunch of hours thinking hard to write tricky code, to save an hour or two of CPU time -- that's not a good tradeoff.

Nonetheless, since it sounds like you appreciate the math and clever tricks, here are the tricks you could use to make this more efficient.  Let $p(x)$ be the feedback polynomial for your LFSR.  If $p(x)$ is reducible, then the LFSR will certainly not be full period.  In other words, if $p(x)$ factors as $p(x)=q(x) r(x)$, the LFSR won't be full period.  So, you could start by picking two polynomials $q(x),r(x)$ randomly of suitable degree (their degrees must sum to 32, and neither should be a constant), then use their product as the feedback polynomial.

Now once you have a feedback polynomial, there are efficient algorithms to check whether a state $t$ is reachable from starting state $s_0$.  This basically becomes a discrete logarithm problem in $GF(2^{32})$, which can be solved very efficiently.  See, e.g., https://crypto.stackexchange.com/q/17970/351.  That said, you wouldn't want to implement those algorithms for this problem.  They are overkill, and much harder to implement than the simple bruteforce approach I outlined above.

If you want to make the problem easier, you could use a maximally factored feedback polynomial, such as $p(x)=(x+1)^{32} = x^{32} + 1$.  Now the all-ones state has a period of 1, i.e., it repeats forever.  So, you can take $s_0=111\cdots 1$ and $t$ to be anything else.  This is a bit of a trivial example, so it might not be what you are looking for.


How can I prove DP completeness? We defined the class $\text{DP}$ like this:

$$\text{DP} := \{ A \setminus B : A, B \in \text{NP} \}$$

We say a problem $P$ is $\text{DP}$ complete iff $P \in \text{DP}$ and $X \leq P \forall X \in \text{DP}$, meaning that every language $X \in \text{DP}$ can be reduced to $P$ in polynomial time.

For a particular problem (which I do not expect you to solve, so I won't explain all the details), I already proved that $P \in \text{DP}$, but I do not know how to continue. Also, I could not find more information about this class.

Could someone give me a hint how to start such a proof or point me to further information about this complexity class which might help me to achieve it?

Edit: The definition is from a lecture about complexity of algorithms. The task is to prove that

$$\text{SAT-UNSAT} = \{\, (F,G) : F \text{ is satisfiable}, G \text{ is not}\, \}$$

is DP-complete. I proved that $\text{SAT-UNSAT} \in \text{DP}$, but I failed to prove the completeness.

The DP-hardness of SAT-UNSAT is a direct consequence of the fact that SAT is NP-hard.

Suppose that $L \in \mathrm{DP}$. Then there exist languages $A \in \mathrm{NP}$ and $B \in \mathrm{coNP}$ such that $L = A \cap B$. Since SAT is NP-complete, there exists a polytime reduction $f$ such that $x \in A$ iff $f(x) \in \mathrm{SAT}$. Since UNSAT is coNP-complete, there exists a polytime reduction $g$ such that $x \in B$ iff $g(x) \in \mathrm{coSAT}$. You can check that the polytime reduction $h(x) = (f(x),g(x))$ satisfies $x \in L$ iff $h(x) \in \mathrm{SAT\text{-}UNSAT}$. This shows that SAT-UNSAT is DP-hard.

To complete the proof that SAT-UNSAT is DP-complete, you have to show that SAT-UNSAT is in DP. Presumably you already know how to do that.

Note that DP contains both SAT and UNSAT, and in particular differs from NP unless NP=coNP.


What complexity class is this set of grammars? Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

What complexity class does this correspond to?

Related questions:

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? NL-complete?

What complexity class is this set of grammars? In between NL and P?

What complexity class is this set of grammars? RE?

Every unrestricted grammar can be converted to one with the following types of rules:
$$
AB \to CD \\
A \to BC \\
A \to a \\
A \to \epsilon
$$
Wikipedia calls this Kuroda normal form for unrestricted grammars.

You can convert a rule of the form $AB \to CD$ to a pair of rules $AB \to X_{ABCD}$, $X_{ABCD} \to CD$. Following the OP's suggestion, we can convert $A \to \epsilon$ to the rule $A \to E$, and add rules $BE \to B$ and $EB \to B$ for any nonterminal $B$. This allows us to obtain a grammar in your form equivalent to the original one, up to not being able to generate $\epsilon$.


Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set) For data compression, every codding that I've seen is binary. It means we convert a language with $N$ symbol size to a language with $M=2$ symbol size. For example, in Huffman coding, the goal is to find a binary coding ($M=2$) for English language ($N=26$).

If $M$ is not equal to $2$ and have a value larger than $N$, is there any method to find good coding (or optimal coding) for compression? Is there any research for this type of problem?
Is it a right assumption that when the target symbol size is larger, the goal is to find a map from a subset of source symbols to one target symbol?

Both arithmetic coding and asymmetric numeral systems can be done in arbitrary base $b$.

  Is it a right assumption that when the target symbol size is larger, the goal is to find a map from a subset of source symbols to one target symbol?

The above algorithms do not work by finding a 'mapping' from source to target symbols. Such a mapping doesn't deal well with fractional 'bits' - where an event has a probability that does not fit nicely in the output size.

Instead these algorithms work conceptually by dumping buckets of entropy from source symbols into a single uniform pool of entropy (in arithmetic coding this is a single fractional number, in asymmetric numberal systems this is a single large number), while scooping out entropy on the other side with output symbols. The trick is that the 'bucket size' of source symbols and output symbols do not have to have the same size at all.


Encoding algorithms better than or equivalent to Run Length Encoding I have a table in which some values are repeated often as shown in the figure below. I want to encode that table such that it makes use of less memory. I have heard about run length encoding (RLE) but I would like to know if there are any other such encoding techniques or algorithms which can perform better than RLE or their performance is almost equivalent to RLE.

There are many general-purpose compression algorithms, for example Lempel-Ziv and its many variants (used for example by gzip), and Burrows-Wheeler (used for example by bzip2). You can just try them on your input and see how well they perform. If your data has particular structure, then it is possible that a dedicated compression algorithm would perform significantly better, but it's hard to tell without knowing more about the structure.


smallest circle that covers two points with its center in x axis I have a question about the following problem and the two points need not be located on the circumference of such "smallest circle". I know this is a linear-programming problem but I just don't know how to solve it mathematically.

  Give two planar points p1=(a1,b1) and p2=(a2,b2) and a line y=0,
  design an algorithm to find the smallest circle that covers
  both points such that its center (x*, 0) lies on y=0.

Don't solve it mathematically. Solve it by hand for a few cases first, and then have a go at making it mathematical. That way you will actually understand what you are doing.

The plane is divided up into points which are closer to $(a_1,b_1)$ than to $(a_2,b_2)$, points which are further away, and points which are equidistant. The $x$-axis is divided in the same way.

In the zone where points are closer to $(a_1,b_1)$, the radius of the circle (with a centre at such a point) is governed by the distance to the further point, $(a_2,b_2)$. So, in that part of the $x$-axis, you are trying to minimise the distance to $(a_2,b_2)$. That is a quadratic function of $x$ (or rather, its square is; but minimising the distance is the same as minimising the square).

In the zone where points are further from $(a_1,b_1)$, the radius of the circle is governed by the distance to $(a_1,b_1)$. So minimise that.

The zone (or, rather, the point on the $x$-axis) where the points are equidistant doesn't need special treatment because you can treat it as being a member of both the above zones at once.

So you already have an algorithm, more or less: find the minimum radius for the "closer to $(a_1,b_1)$" part of the $x$-axis, find the minimum radius for the "closer to $(a_2,b_2)$ part, and pick the minimum of the two minima.

But for real understanding, consider the possible geometries of the distance function in each of the two halves, and how the geometry of one half might relate to the geometry of the other half. Because nobody wants a solution to the question (it is known!) so the only benefit of doing the work is to gain understanding.


How to find splitting point in [0,1] to maximize sum of sign function? Given two $n$-number arrays $a_1, a_2, \ldots,a_n \in [0,1] $ and $b_1, b_2, \ldots,b_n \in [0,1] $. We would like to find the real number $x^{*} \in (0,1)$ s.t:

$x^{*} =\arg\max_{x} \sum_{i=1}^n  \mathrm{sgn} \big( (a_i-x) (b_i -x)\big) $

Where $\mathrm{sgn} = 1 $ if $x \geq 0$ and
 $\mathrm{sgn} = -1$ if $x < 0$

This question raised from my research work. I am looking for an efficient way to determine value of $x$.

WLOG, let $a_i < b_i$. Then $(a_1 - x)(b_i - x) \geq 0$ when $x \leq a_i \vee x \geq b_i$.

Keep a list of intervals $I$. For each $a_i , b_i$ add $(0, a_i]$ and $[b_i, 1)$ to the intervals. Now you just find point $x$ such that it lies within the most intervals in $I$.