How to handle L-attributed SDDs with LR parsers I've read Chapter 5, Syntax Directed Translation, of the Dragon Book but am still unable to understand the following related points:

How to handle L-attributed SDDs in an LR grammar when using a tool such as Bison? I believe, the book says that inherited attributes could be used with an LR parser (via Marker symbols?) provided the grammar is LL, or is (partly?) transformed into LL. Is this true? What if the grammar is LR and/or converting it to LL is not easy -- how do you then use inherited attributes?

If LR grammars are a proper superset of LL grammars and therefore more powerful, then how come LR grammars/parsers won't out-of-the-box allow L-attributed SDDs which, being a superset of S-attributed SDDs, are more powerful?

Avoiding the SDD style - Parsing style mismatch: Is it true that no matter the grammar (LL, LR, ...) or the parsing tool (Antlr, bison, yacc...), I can always first build the AST and then traverse it post-/pre-order any number of times to get whatever SDTs I want? (Ignore the time inefficiency here.)

Is there a text or online resource that covers topics 1 and 2 better or in more detail?

Let's start with #3: Can you always walk the AST in any way you like after it is built? Yes, you can, and the Dragon book has an extensive discussion about how to do that for a given set of attributes; in particular, how to avoid (or detect) infinite regression.
Moreover, there is really no inefficiency in doing it this way. Or, to put it another way, trying to compute attributes on the fly during the parse does not speed things up much if at all, and can even slow things down. Even if it were slightly inefficient, it generally makes the parser much more complicated than it should be, partly because of the artificial hoops which need to be jumped through to perform the analysis online, and partly because it tends to interlace code which doesn't need to be codependent. Separation of concerns is almost always a good programming model.
With that out of the way, and briefly:

What the Dragon book says (iirc, because I still don't have either of my copies at my fingertips) is that adding markers can destroy the LR property of a grammar. This doesn't happen if the grammar happens to be LL. It's not actually necessary for the whole grammar to be LL, but it's a bit tricky to provide a formal description of what it means for a part of a grammar to be LL, although it's possible. Before LALR parser generators were available, there was quite a lot of research into left corner parsing (LCP), which you could look at if you're interested in the concepts. (I don't have references handy but the phrase should still be usable as a search term.)
If you want to introduce a marker into an LR grammar, you need to ensure that the reduction action for that marker does not conflict with any shift action. For that to be the case, each itemset which contains an item whose • is just before the marker must be free of items which would allow a shift of a symbol which could follow the marker. This is very similar to the LL(1) criterion, because it is effectively saying that the parser needs to be able to predict a single unique production at that point in the parse, something which is not normally required in an LR parser. (Strictly speaking, the parser only needs to be able to predict a single unique production for some lookahead symbols -- as I said, those which might follow the marker -- but that fact doesn't usually help much.)
A common way of creating this sort of conflict is when you have two similar productions with different markers before the same symbol. See the bison manual for some specific examples. (Bison automatically inserts markers for you when you put an action in the middle of the rule, which is why that section is called what it is called.)

LR grammars can recognise a strictly larger set of languages than LL grammars. But here, we're not talking about just recognising whether a sentence is in a language or not. The goal of parsing (outside of some formal language theory discussions) is almost always to recursively break the input into parts (which is the root of the verb "to parse") and understand the relationships between those parts.
All the same, LR parsers are, by and large, more capable at parsing as well. For example, the common language of arithmetic expressions can easily be recognised by an LL parser, and most textbooks insist that students work through the chore of destroying refactoring a simple operator grammar in order to make it possible to parse with a top-down parser. But the resulting LL grammar does not produce the same AST; it has completely lost any information about operator associativity. In order to use the parse, it is necessary to rewrite the AST to recover that information. The fact that an LL grammar cannot produce a parse tree for left-associative operators seems to me like it should count as a weakness.
In any event, if there is an LL grammar which correctly parses a language then you can indeed insert whatever attributes you like wherever you want to insert them. But that grammar will also be an LR grammar, and you will be able to insert markers freely into that grammar without losing the LR property. Unfortunately, it is possible that adding markers to the $LL(1)$ grammar will produce a grammar which is not $LALR(1)$ (since not all $LR(1)$ grammars are $LALR(1)$). But as far as I know this doesn't show up often in practical grammars.
If you want an academic reference, you can look at Beatty, J. C. (1982). "On the relationship between LL(1) and LR(1) grammars", Journal of the ACM, 29 (4 (Oct)): 1007–1022. (doi:10.1145/322344.322350. I got that from a reference in the Wikipedia entry on LL grammars; the reference link is not pay-walled, at least as of today.)


Count total number of k length paths in a tree This is a question from a competitive programming competition.
Given a tree with n nodes and a number k, find the total number of paths of length k in that tree.

I know for a fact that a solution can be found by using a centroid decomposition, however I am simply not sure on the exact relationship between the original tree and the tree we got from decomposition other than the fact that the length of path A -> B in the original tree can be decomposed into a sum  A -> C + C -> B in the decomposed tree. Where C is the LCA(A, B). All distances being in the original tree.

This can be solved in $\mathcal{O}(n \log n)$ by using the smaller-to-larger merging technique. Root the tree at an arbitrary vertex. We will calculate for every subtree an array where the $d$th position indicates the number of nodes at depth $d$ in the subtree. Of course, the total size of these arrays could be $\mathcal{O}(n^{2})$, so we will not store them, instead building the array at every node by "scavenging" the arrays of its children.

To calculate the number of nodes at depth $d$ in the subtree of $i$, calculate the arrays for all children of $i$, then prepend zero to them, and sum them up, then finally add 1 to the number of nodes at depth $0$ (to count node $i$). For fast prepending, we store the arrays as dynamic arrays with inverted indexing. When we add two arrays together, we only care about the result, not about what happens to the orignal arrays, so we can just add the numbers in the smaller array to the numbers in the larger array and return the larger array.

Thus, if node $i$ has children $c_{1}, \dots, c_{m}$ and $T_{i}$ denotes the subtree of node $i$, we do an amount of work proportional to $w_{i} = |T_{i}| - \max_{j} |T_{c_{j}}|$. Therefore the total complexity is $\mathcal{O}(\sum_{i = 1}^{n} w_{i})$. Note that if $p$ is the parent of $i$ and $|T_{p}| < 2|T_{i}|$ then $|T_{i}|$ does not appear in the sum. Therefore, on any path from the root to some node $x$, at most $\log n$ sets we count appear, and those are exactly the sets $x$ appears in. Since every vertex appears in at most $\log n$ sets, their total size is $\mathcal{O}(n \log n)$. This is tight: consider the perfect binary tree of size $n = 2^{h} - 1$.

It remains to show how to calculate the number of paths of length $k$ from the depth information. To do this, when combining two arrays $A$ and $B$ at some node, just add $\sum_{i} A[i] B[k-i]$ to the answer. If $A$ is the sum of the arrays of previous children, and $B$ is the array of the current child we are handling, this corresponds to counting the paths with one endpoint in the current child's subtree, and the other in some earlier child's subtree. This can be done in $\mathcal{O}(\min(|A|, |B|))$ so it does not affect the runtime.

Here is a C++ implementation of the algorithm:

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
using ll = long long;

ll combine(deque<int>& a, deque<int>& b, int k) {
    if (a.size() < b.size()) swap(a, b);
    int as = a.size();
    int bs = b.size();

    // Count paths of length k
    ll res = 0;
    for (int i = max(0, (k - bs) + 1); i < min(k + 1, as); ++i) {
        res += a[i] * b[k-i];
    }

    // Combine a and b
    for (int i = 0; i < bs; ++i) a[i] += b[i];
    return res;
}

pair<ll, deque<int>> solve(int i, int k, int p, const vector<vector<int>>& g) {
    pair<ll, deque<int>> res = {(k == 0), {1}};
    for (int t : g[i]) {
        if (t == p) continue;
        auto sub = solve(t, k, i, g);
        sub.second.push_front(0);
        res.first += sub.first + combine(res.second, sub.second, k);
    }
    return res;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    ll res = solve(0, k, -1, g).first;
    cout << res << '\n';
}


Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state? The wikipedia page Powerset construction says that the DFA equivalent to this $(n + 1)$-state NFA (with $n=4$ here) "requires $2^n$ states, one for each $n$-character suffix of the input".

I understand that the author wants to say that the smallest DFA equivalent to this NFA needs at least $2^n$ states.

But I can find a very much smaller DFA equivalent to this NFA just below:

Is Wikipedia wrong? Or am I? (which is much more likely)

The NFA accepts strings where the fourth letter from the end is 1. Your DFA doesn't accept 11000.

A DFA doesn't know how much input is left, so the property "the fourth character from the end" is difficult. You need to remember the last four characters to know whether it was a 1 or a 0 once you reach the end of the string. To do so you need a state for each possible combination of the last four characters, so 2^4 states. If you look hard at the DFA the Wikipedia gives you should be able to figure out which of the states stores which combination of characters.


Theory of computation introductory curriculum I want to study theory of computation on my own, so I am looking for books.

What set of books would you recommend for the equivalent of a one-semester course that introduces theory of computation?

Please post answers that describe a complete curriculum, explaining which chapters of each book are relevant at which stage of the course or self-study.

Introduction to the Theory of Computation by Michael Sipser is a relatively recent entry into this field. It was the required book for a class my friend was taking, and I asked him for the PDF so I could browse through at my leisure. I ended up reading almost the whole book, even the chapters on topics I was already very familiar with, just because the book is such a joy to read. It's written at an introductory level, which means less notation, more exposition, and more intuition. The motivation behind every idea and theorem is crystal clear. He precedes every proof with a "proof idea" section that lays out the path the proof is going to take without getting into the gory details. The book covers Automata Theory, Computability Theory, and Complexity Theory to a satisfactory depth for an undergraduate level. I've read many textbooks in computer science and math, and this is probably my favorite.


Why quicksort instead of a B-tree construction? As far as I know (despite some variations which provide empirical average-case improvements) quick-sort is worst case $O(n^2)$ with the original Hoare partition scheme having a particularly bad behavior for already sorted lists, reverse-sorted, repeated element lists.

On the other hand a B-Tree has $O(\log n)$ insertions, meaning worst-case $O(n\log n)$ to process an array of $n$ elements. Also an easy optimization to memoize the memory-address of the lowest and highest nodes (would make it possible to process sorted / reverse-sorted / repeated-element lists in $O(n)$).

While there are more favored sorting algorithms than quicksort now (e.g. timsort) what originally favored its use? Is it the susceptibility to parallelization (also in place swaps, lower memory complexity)? Otherwise why not just use a B-tree?

A B-tree has one significant disadvantage on the fastest deep cache machines, it depends on pointers. So as the size grows each access have a greater and greater risk of causing a cache-miss/TLB-miss.
Effectively getting a K value of z*x, x=sum(cache/TLB-miss per access, L1-TLB misses are typically size of tree / total cache size), z ~= access time of least cache or main memory that can hold the entire tree.

On the other hand the "average case" quicksort streams memory at maximum pre-fetcher speed. Only drawback here is the average case also cause a stream to be written back. And after some partitions the entire active set sit in caches and will get streamed quicker.

Both algorithms suffers heavily from branch mis-predictions but quicksort, just need to backup a bit, B-Tree additionally needs to read in a new address to fetch from as it has a data dependency which quicksort doesn't.

Few algoritmes are implemented as pure theoretically functions. Nearly all have some heuristics to fix their worst problems, Tim-sort excepted as its build of heuristics.

merge-sort and quick-sort are often checked for already sorted ranges, just like Tim-sort. Both also have an insertion sort for small sets, typically less than 16 elements, Tim-sort is build up of these smaller sets.
The C++ std::sort is a quicksort hybrid with insertion sort, with the additional fallback for the worst case behaviour, if the dividing exceed twice the expected depth it changes to a heap-sort algorithm.

The original quicksort used the first element of the array as pivot, this was quickly abandoned for a (pseudo)random element, typically the middle. Some implementations changed to median-of-three (random elements) to get a better pivot, recently a median-of-5-median (of all elements) was used, and last I saw in some presentation from Alexandrescu was a median-of-3-medians (of all elements) to get the a pivot that was close to the actual median (1/3 or a 1/5 of the span).


What is the concept of "encoding" in NP-completeness Hi I have been reading Ch 34(NP-Completeness) Section 34.1 of CLRS and I am confused why do we need to consider different encodings. Everything is represented as binary at the end so why consider different encodings of the input?
Any help is highly appreciated.

Everything is in binary in your electronic computer. However:

We don't want to have to throw away all of the theory of computation if somebody builds a really fast ternary computer.
More importantly, the stuff we wish to compute upon isn't binary. It's strings and graphs and numbers and things like that. So the very first thing you need to do is to encode your string/graph/number into a form that fits into your model of computation. And, since we are forced to encode, we'd better consider whether our encoding is a good one.


NP completeness of closest vector problem Let $\mathcal{B} = \{v_1,v_2,\ldots,v_k\} \in \mathbb{R}^n$ be linearly independent vectors.

Recall that the integer lattice of $\mathcal{B}$ is the set $L(\mathcal{B})$ of all linear combinations of elements of $\mathcal{B}$ using only integers as coefficients. That is $$L(\mathcal{B}) = \{ \sum_{i=1}^k c_i b_i \mid c_i \in \mathbb{Z}\}.$$

The closest vector problem asks us to find a nonzero vector $v \in L(\mathcal{B})$ such that $||v||$ is minimized.

It is apparently well known that this problem is NP-complete though I was not able to find a reduction to any of the "well known" NP-complete problems.

The first proof of this claim seems to be in P. van Emde Boas. "Another NP-complete problem and the complexity of computing short vectors in a lattice"., but I cannot find a copy of this paper.

Can someone give a polynomial reduction of some well known NP complete problem to the closest vector problem?

As far as I know, it is not known that the shortest vector problem is NP-hard for any $L^p$ norm other that $L^\infty$. It is known that the shortest vector problem is "NP-hard under randomized reductions" for all $L^p$, a result first proved by Ajtai. See for example Miccanccio's paper and the results he references. Since then better inapproximability results have been obtained, but as far as I can tell nobody could prove an unconditional NP-hardness result.


Question about "Type checking a multithreaded functional language with session types" by Vasconcelos et al I have been reading the paper[1] in the title. But there are some parts of it that are unclear to me, more specifically the way you typecheck a lambda. I have attached the typing rules below as images[2] [3] Typing them all in Mathjax would have been a lot of work.

I will explain the issue I am having by means of an example.

Given the program in listing 1, we first apply the rule C-Let. This means that we typecheck the first binding, namely new !Int.End which yields the type [!Int.End].  $\Gamma$ now contains a mapping $x \rightarrow [!Int.End]$. Then we typecheck the next let, using C-Let once more. This time we typecheck accept x, which first makes sure that $x$ is of the proper type. $\Gamma$ contains this mapping so that is indeed the case. This yields the type Chan c. Note that when you look at the typing rule for accept, $c$ in this case is a so-called "fresh" variable. The rule C-Accept also inserts the session type into $\Sigma$. So $\Sigma$ contains a mapping $c \rightarrow\ !Int.End$ and $\Gamma$ contains two mappings, namely $\Gamma = x \rightarrow [!Int.End] , v \rightarrow Chan \ c$

We then proceed to typecheck the last body of the most-inner let. The first statement is a send statement so we apply rule C-SendD. Typechecking the number $5$ yields type Int, so that part is correct. $v$ yields the type $Chan\ c$. $\Sigma$ indeed contains a mapping $c \rightarrow\ !Int.End$. So the rule C-SendD finally yields the type $\Sigma;Unit;c:End$ where the first part of the entry in $\Sigma$ has been consumed, leaving the session type for $c$ to $End$.

Finally we can apply the rule C-Close which also typechecks properly.

Listing 1

let x = new !Int.End in
let v = accept x in
  send 5 on v;
  close v;

We can now transform the above example to the following:

Listing 2

let x = new !Int.End in
let v = accept x in
let f = (Lambda x:Int . (close v))
  send 5 on v;
  (f 1);

Listing 2 shows that instead of just calling close on the channel we have stored that operation inside a lambda. We will play typechecker one more.

The first part of the typechecking is the same as above. So we have arrived at typechecking the body of the second let, namely let f =.... At this point $\Sigma = c \rightarrow\ !Int.End$ and $\Gamma = x \rightarrow [!Int.End] , v \rightarrow Chan \ c$.

The body of the lambda uses a channel that is defined outside of the lambda, namely $v$. According to the paper, the required $\Sigma$ should be embedded in the type signature of the lambda. However, this is where things get unclear. If I follow the typing rules I would have written down the lambda as $(Lambda\ [c \rightarrow End,\ x:Int]\ .\ (close\ v))$. But this is impossible, I think.

Recall that the rule C-Accept uses $fresh$ to "generate" a symbol that will be the identifier in $\Sigma$ and the second part of the type of the channel (e.g., $Chan\ c$). This means that it is impossible for the programmer to write down this identifier. Unless, of course, the channel is the parameter of the lambda itself. Then we can use $\alpha$-renaming. But this is not the case here, the channel is simply captured by the lambda and the parameter is $x$ which is ignored in the body of the lambda.

So, there are two options the way I see it. The text in Listing 2 is illegal for the reason that you can not capture a channel that has not been passed to the lambda as a parameter. However, the paper shows an example of this at page 9. So this reasoning is probably faulty.

The second reasoning I can come up with is the following. At the time the lambda is typechecked (as the binding to $f$), the typechecker will error because we are calling close on a channel that has session type $!Int.End$ in $\Sigma$. But, this could then be resolved by delaying the typechecking of the lambda until the point that it is invoked. But then, this does not require the programmer to write down the $\Sigma$ in the type signature of the lambda.

I hope the problem I have sketched here is clear. Any feedback is appreciated.

[1] Paper discussed in this question

I think

(Lambda [c→End, x:Int] . (close v))

is indeed what you need to write.  As you mention, it's "impossible" to write it because "c" is fresh.  From my reading of it, it does seem to be a problem in the paper.

I don't think this is a very serious problem, tho, since the same problem appears in other systems and has known solutions (look at the papers about "Calculus of Capabilities" or "Alias Types", for example).

if, as you do in your own syntax, you rely on type-inference, the problem disappears: the type inference can write the "c" since by that time it is known.
you can change accept and request to return two things: a type c and a value of type Chan C.  I.e. introduce "channel type parameters".  Indeed Chan c is a singleton type, so you need c to be able to parameterize over c in order to be able to do anything useful.


Worst Case running time of the Minimum Vertex Cover Approximation algorithm Considering this factor $2$ minimum vertex cover approximation algorithm :

  Repeat while there is an edge:

  Arbitrarily pick an uncovered edge $e=(u,v)$ and add $u$ and $v$ to the
  solution. Delete $u$ and $v$ from the graph. Finally output the candidate cover.

I want to find the worst case running time of this algorithm. Since in a fully connected graph we have $O(n^2)$ edges, then the loop will run at most $O(n^2)$ times.

Here I am not sure what the maximal number of delete operations could be or perhaps for less than $O(n^2)$ edges being processed in the loop there would be some scenario with a large number of delete operations would contribute to the overall complexity.

I want to say naively that in the worst case you simply multiply the max number of edges possible with the max number of delete operations possible (both $O(n^2))$ giving $O(n^4)$, but this seems wrong.

Any insights appreciated.

It depends on which data structure you use to store the graph.

For example, suppose the nodes are represented as $0,\ldots,n-1$, and the edges are stored as a list of pairs of nodes. We can build an boolean array $\mathrm{arr}$ of length $n$ initialized with all $\texttt{true}$s, and when a node $i$ is deleted, we simply mark $\mathrm{arr}[i]$ as $\texttt{false}$. Each time we deal with an edge, we first check if any of its endpoints is deleted to see if the edge has already been covered. With such data structures, your algorithm runs in $O(n^2)$.


When compiled into binary, what signifies the end of a string? How can this be differentiated from user input which compiles to the same binary? Apologies for the strange title, this is one of those questions I can't find through a Google search just because I don't even know what I'm supposed to be searching for.

As I understand it, programs are ultimately compiled into binary which is then run by a computer.

So say, for example, you have a simple program which takes a user input and then executes some code -- when compiled into binary, there must be some sort of 'signature' that signifies the end of the user input so the computer knows where it ends. Say just for the sake of this example it's something simple like 0110. So after the user has input his data it might look like ...1100 0101 0110 1010 1001..., where the 0110 signifies the end of the string so the computer knows it's ended and that the rest is code from the program.

But what if the user input contained the same signature? Say the user input, after conversion to binary, came out to be ...0110 0010 0110 1010 1001... What is there to prevent the user from 'tricking' the computer into thinking the user input has ended, and then running malicious code now that the PC believes it's part of the program and not the string?

Hope this question makes any sort of sense, I'd be incredibly grateful if someone could explain this to me. It seems so trivial but it's been bugging me that I can't find an answer for it.

Both programs in binary form and binary user data are usually stored in files, and normally the filesystem records the length of all its files separately. So, the operating system always knows the end of the binary string, which is supposed to be loaded and executed as a separate process. Please see this question and its answers for more information.

Could an attacker use a binary input with malicious code, added in the end of input string, to modify normal program behavior? Yes, and this method of attacking is called buffer overflow. Fortunately, modern programs normally don't use input functions, which can lead to the buffer overflow.


Would removing the branch delay slots change the instructions set architecture? I am trying to study for an exam and I noticed a lot of the questions follow the idea of  "Changing the ISA". From my understanding the ISA dictates the structure and format of instructions, so changing instructions or the format (32 to 64 bit) would change the ISA. However I ran into a question which I am not sure how to answer.

"If we remove the branch delay slots, will the ISA be changed?"

My guess would be no, because we're not changing any instructions (right?), but I would like to get an answer from someone more knowledgeable.

The instructions set architecture (ISA) is the contract between the hardware designer and the software designer.  Anything that changes the contract, changes the ISA.

The question you have to answer is: given every possible program written with this particular ISA, do any of them have different behavior (give a different answer) if we remove the branch delay slots.


How do processors fetch instructions that are longer than the word length? From what I have read, instructions under x86 can be as long as 15 bytes. Since x86 is a 32-bit architecture (64-bit for x86-64 obviously) how does it handle these long instructions? How are they stored in memory, and how are they fetched?

In general there is not relation between the processor register size (32-bit for x86, 64-bit for x86_64) and the instruction size. Instructions are fetched by a dedicated hardware unit and the current instruction is stored the instruction register, but this register does not need to (and usually does not) have the same size as the data registers. On x86, this register must be able to hold 15 bytes. Instructions are fetched like everything else by issuing read commands to the memory. In general to speed up things, the CPU has an instruction cache so it will not just fetch one instruction at a time but rather an entire cache line at once.


Min weighted edge cover: don't follow proof in Schrijver I'm reading section 19.3 of Combinatorial Optimization by Schrijver where he details an algorithm for finding the min-weight edge cover. His method works for general graphs, but I'm particularly interested in bi-partite graphs. To find the min-weighted edge cover of a graph $G=(V,E)$ with a weight function $w: E \to R$, he first defines a clone graph, $\tilde{G} = (\tilde{V},\tilde{E})$. He then defines a larger graph, $G'=(V',E')$ whose set of vertices, $V'$ is the union of $V$ and $\tilde{V}$. The edges, $E'$ and weight function $w'(E')$ are as follows:

$w'(e)=w'(\tilde{e})=w(e)$ for $e \in E$
$w'(v,\tilde{v})=2\mu(v)$ for each $v \in V$ where $\mu(v)$ is the minimum weight edge of $G$ incident on $v$.

Now, we construct a minimum weight perfect matching, $M$ for $G'$ and this yields a minimum weight edge cover $F$ for $G$ once we replace any edge $v\tilde{v}$ in $M$ by an edge $e_v$ of minimum weight of $G$ incident on $v$.
Now, for the proof that this works, the author notes that $w(F)=\frac{1}{2}w'(M)$. So far so good.
Then, he states that any edge cover $F'$ for $G$ gives by reverse construction a perfect matching $M'$ in $G'$ with $w'(M')\leq 2w(F')$.
This is the part I don't understand. How does one go about constructing this new perfect matching, $M'$ and further prove the inequality?

Let $M$ be a maximal subset of $F'$ which is a matching. Any vertex $v$ not covered by $M$ must be covered by some edge $e_v=(v,w)$ in $F'$. Since $M$ is maximal, $w$ must be covered by $M$. It follows that if $v_1 \neq v_2$ are not covered by $M$, then $e_{v_1} \neq e_{v_2}$.
The matching $M'$ consists of the two copies of each edge in $M$, and of the edges $(v,\tilde{v})$ for each $v$ not covered by $M$. Edges of the first type have total weight $2w(M)$. Since $w(v,\tilde{v}) \leq 2w(e_v)$, edges of the second type have total weight at most $2w(F' \setminus M)$ (this crucially uses that $e_{v_1} \neq e_{v_2}$ for any $v_1 \neq v_2$ not covered by $M$). Hence $w(M') \leq 2w(F')$.


Complexity of Radix Sort I am a little confused by the complexity proof of Radix Sort.
For counting sort, the complexity reported is $O(n+R)$, where $n$ is the number of items and $R$ is the range.
But this is not entirely correct, right? To do binary arithmetic on numbers as big as $R$, I need $\log_2 R$ operations for any deterministic hashing function. So the complexity of counting shot should be $O(\log_2 R \cdot (n+R))$.
Then the complexity of radix sort with base $b$ should be $O(\log_b R \cdot \log_2b \cdot (n+b))$, which is equivalent to $O(\log_2R \cdot n)$. For range $R = \Omega(n)$, this is $\Omega(n \log n)$ and thus not $O(n)$.
Can someone point out where I am going wrong in my proof? As far as I know, radix sort is $O(n)$ for $R = O(n^c)$.

We typically analyze algorithms in the so-called "RAM machine" or "transdichotomous model". In this model, operations on machine words take $O(1)$, and a machine word has length $O(\log n)$ bits, where $n$ is the size of the input (in bits), or any other polynomially related quantity.
If $R$ is polynomial in $n$ (in this case, the length of the array), then an integer in the range $\{1,\ldots,R\}$ can be stored in a single machine word, and so operations on such integers take constant time in this model.


For proving that L is in NPC, why do we reduce a known L' into L and not the other way around? For proving that $L$ is in NPC, why do we reduce a known $L'$ into $L$ and not the other way around i.e. reducing $L$ into $L'$.

Saying that a problem is NP complete is, approximately, saying that there is no good algorithm for it.

Saying that $L$ reduces to $L'$ means, approximately, that one way of producing an algorithm for $L$ is to use an algorithm for $L'$ as a subroutine.

Now, if $L$ reduces to $L'$ and $L$ is has no good algorithm, then we know that $L'$ also has no good algorithm – if it did, then "use $L'$ as a subroutine" would be a good algorithm for $L$, but no good algorithm exists. However, if $L'$ reduces to $L$ and $L$ has no good algorithm, we know that "use $L$ as a subroutine" isn't a good algorithm for $L'$ but so what? There are infinitely many other algorithms and we know nothing about whether those are good or bad.


Is Turing machine is robust? Is Turing machine is robust ?
if it solved with one tape, can it solved with multi-tape?
I know that TM is robust but i can't understand why

If you can solve it with one tape, you can solve it with multiple tapes by just ignoring all but the first tape.

The other direction is covered by Universal simulation of Turing machines.


Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves This problem is about finding a route on a square grid.
The starting point is $(1,1)$ and the target point $(n,m)$.
I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$.
Now I need to determine if there is a path from $(1,1)$ to $(n,m)$, and if so to return the shortest one.

Now I believe that if I trace back my steps from the input point $(n,m)$ I can always know which move I made out of the two possible ones since if $n=m$ then there is no route, this means I'm always take the smaller coordinate and subtract it from the bigger one.
But that means I have at most only one possible route to $(n,m)$ so why was  I asked to return the shortest one?

Am I missing anything ?

No, your reasoning seems right. Sometimes problem setters just throw in such things in order to make the problem sound harder than it is.


Turing machine which diverges on its own code Show that the set $K^{c}$ = $\lbrace M \mid M(M) \text{ diverges} \rbrace$ is not recursively enumerable.

This question is essentially asking to show that the set of turing machines which diverge when run on their own code is not RE.

My idea is to attempt to reduce this problem to something which is the complement of the halting problem.  Thus, the idea is to take a machine M and a word w, and construct a new machine which diverges on it's own code when M diverges on w, but haven't had much luck with that.

This is from a practise exam, but please treat it as a homework question so I can attempt to work through a solution.

The language $K^c$ is clearly co-RE: given an input $M$, simulate $M(M)$ until it halts and then reject; if it doesn't halt, the simulation doesn't halt.  Now, any language that is both recursively enumerable and co-RE is actually recursive (exercise: prove this).  Since $K^c$ is not recursive (exercise: prove this), it cannot be recursively enumerable, either.

Your idea of reducing to the complement of the halting problem doesn't work.  Firstly, that's the wrong way around: you'd want to reduce the complement of the halting problem to $K^c$ to prove that $K^c$ is hard.  Second, it's possible for a set to be neither RE nor co-RE. (Why?  There are countably many RE languages and countably many co-RE languages, since each such set corresponds to a Turing machine and there are only countably many Turing machines. But there are uncountably many languages over any finite alphabet.) However, from your description, it sounds like you weren't trying to do a reduction but a diagonalization, similar to the proof of the undecidability of the halting problem.  That sounds like it could work but the method I give above is much easier.


How to solve the recurrence $T(n) = T(n/2) + T(n/4) + T(n/8)$? How to solve the recurrence $T(n) = T(n/2) + T(n/4) + T(n/8)$?

We assume that $T(n)$ is constant for sufficiently small $n$.

We guess that $T(n) = \Theta(n^{\alpha})$, where $\alpha > 0$ is a constant.

To find $c$, we use the substitution method.

Assume that $T(n) \le cn^{\alpha}$. (The other direction $T(n) \ge cn^{\alpha}$ is similar.)

Then, we have $$T(n) \le c(n/2)^{\alpha} + c(n/4)^{\alpha} + c(n/8)^{\alpha}.$$

Letting $$c(n/2)^{\alpha} + c(n/4)^{\alpha} + c(n/8)^{\alpha} = cn^{\alpha},$$ we obtain that $$(1/2)^{\alpha} + (1/4)^{\alpha} + (1/8)^{\alpha} = 1.$$

Solving this equation (using Mathematica) yields
$$\alpha = 0.879146.$$


Mixed integer non convex optimization problem If an optimization problem is mixed integer non-convex problem. The optimal solution by applying brute exhaustive search is infeasible to be applied in practice due to high complexity i.e. $O(N^K)$. Can we say that it's NP hard problem? If yes, can someone explain with more details.

No, you can't infer NP-hardness from such an algorithm. Indeed, why should the existence of a slow algorithm mean that there can't be a fast algorithm?

For example, consider the problem of sorting $n$ integers. Suppose the first algorithm I give you is a one that tries all $n!$ permutations. Can we now safely conclude that this problem is somehow hard? Of course not and we know that there are many much faster polynomial-time algorithms for the problem.


Finding small node sets that can not be avoided on paths from source to sink In a directed graph with a starting node and an ending node, how to find a small (doesn't have to be smallest. <10 for example) set S of nodes such that every possible path from the starting node to the ending node contains at least one member of set S. The graph may have loops. This may be NP hard. Is there an approximate method to find one or several such S from the graph? Enumerating and testing every candidate seems not work. thanks.

Finding the smallest number of edges instead of vertices is the famous Minimum Cut problem which can be solved using any of the Max-Flow-Min-Cut algorithms. Picking vertices is a specific case of the generalised max-flow-min-cut theorem and similar algorithms can be used to solve it. In any case, it can be formulated as a linear program with polynomial complexity, which can be solved in polynomial time using any of the LP-solvers.


sum of like indices in circular lists Consider the following problem:

  Let a $k$-wheel be defined as an indexed circularly linked list of $k$ integers. For example…

    {3, 4, 9, -1, 6}

  …is a 5-wheel with 3 at position 0, 4 at position 1, and so on. A wheel supports the operation of rotation, so that a one-step rotation would turn the above wheel into…

    {6, 3, 4, 9, -1}

  …now with 6 at position 0, 3 at position 1, and so on. Let $W_{N_k}$ be an ordered set of $N$ distinct $k$-wheels. Given some $W_{N_k}$ and some integer $t$, find a series of rotations such that…

  $$\forall\ 0 \leq i < k, \sum_{N \in W} N_i = t$$

  In other words, if you laid out the wheels as a matrix, the sum of every column would be $t$. Assume that $W_{N_k}$ is constructed so that the solution is unique up to rotations of every element (i.e., there are exactly $k$ unique solutions that consist of taking one solution, then rotating every wheel in $W$ by the same number of steps).

The trivial solution to this problem involves simply checking every possible rotation. Here is some pseudocode for that:

function solve(wheels, index)
    if wheels are solved:
        return true
    if index >= wheels.num_wheels:
        return false
    for each position 1..k:
        if solve(index + 1) is true:
            return true
        else:
            rotate wheels[index] by 1

solve(wheels, 0)

This is a pretty slow solution (something like $O(k^n)$). I'm wondering if it is possible to do this problem faster, and also if there is a name for it.

For most of this answer, I discuss the decision version of the problem, in which an instance having at most one solution is given (the "promise"), and you have to decide whether it has any solutions or none.

You can reduce PARTITION to your problem (exercise). (PARTITION is the problem of determining whether a set of integers can be partitioned into two parts with equal sum.) Admittedly, this doesn't necessarily satisfy the condition that the solution be unique.

With some more work, you can (directly) reduce SAT to (the decision version of) your problem, and perhaps that can be done in such a way so that if the SAT instance has a unique solution, then so does the resulting instance of your problem. In that case, we get that the decision version is not solvable in polytime unless NP=RP, which is considered unlikely.

Note that if the decision version (more accurately, the promise version) of the problem is not solvable in polytime, then no algorithm can solve all YES instances in polytime: if it did, you could run it up to its allotted running time, and check the solution (if the algorithm stopped in time).


Prefix complexity of x conditioned on prefix complexity of x I wonder what is $K(x|K(x))$, $K$ denoting (Kolmogorov-Chaitin) prefix complexity. Naively, it looks like it should just be $K(x)+O(1)$. Is that right? The same question for plain Kolmogorov complexity is interesting as well.

For plain complexity the assertion is true. One direction is clear: $K(x|K(x))\leq K(x)$ (easier to describe x from something than from nothing). In the other direction one can argue by contraposition. Suppose one could find $x$s with programs $q$s of length $l(q)$ arbitrarily shorter than $K(x)$. Set $K(x)-l(q) \equiv C$. In other words one can find $x$s with arbitrarily large corresponding $C$s. To reconstruct $x$ one needs to only know $q$ and $C$, which can be encoded in $l(q)+2\log(C)$ bits. Now $K(x)-l(q)-2\log(C) = C-2\log(C)$ which can be made arbitrarily large for sufficiently large $C$. Hence, we have obtained a description of $x$ much shorter than $K(x)$, a contradiction. This may be found as problem 43 in the following book (in Russian): https://www.mccme.ru/free-books/shen/kolmbook.pdf (Vereschagin, Uspensky, Shen, "Kolmogorov complexity and algorithmic randomness").


Tree traversal with conditional summing values from nodes Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can be random number).
What i want to do is traverse tree and for each node i want to sum values from all descendant nodes except descendants with lower rank and all nodes under them (irrespective of rank).

My naive solution is to recursively traverse subtree for each node and stop recursion as soon as i find node with lower rank, summing values on my way back to root of subtree. However this feels to me like suboptimal solution. It is possible to have sums for all nodes settled after one traversal?

Edit: There are no special relationships between nodes and also tree doesnt have any special properties. Tree is not binary tree as each node can have <0,Integer.MAX_VALUE> children.

To more describe my naive solution, in worst case - that is each node has only one descendant (its basically linked list) and ranks are sorted ascending to the root this solution would be O(n^2).

This algorithm is simple conceptually, but the implementation is a bit much so I'll try to present it in a couple steps. First, an example.

Linked List Example

Consider the following linked list where rank and value are equivalent: $A = [1, 3, 5, 6, 4, 2, 0]$

We will create auxiliary array $S$ where $S[i]$ is the sum of the subtree (sub-linked list) rooted at node $i$. This will basically be a suffix sum array for our purposes. This takes $O(n)$ time to create and it would be: $S = [21, 20, 17, 12, 6, 2, 0]$.

We will now process the nodes in order, adding them to a stack $T$. We have one rule before adding a node, if the node value on the top of the stack is greater than the node we're adding, then we must pop it from the top of the stack. This will ensure that when we pop a node off the stack, the current node we're at will be the first node lesser than it. Let's say we're popping node $i$ and we're currently at node $j$, then we have the function we're interested in is simply $f(i) = S[i] - S[j]$. Let's run through this with our example:

Let A = [ 1,  3,  5,  6, 4, 2, 0]
Let S = [21, 20, 17, 12, 6, 2, 0] be the suffix sum array of A
Let T be the increasing order stack, initially empty.

1) T = []
2) T = [1]
3) T = [1, 3]
4) T = [1, 3, 5]
5) T = [1, 3, 5, 6]
6) T = [1, 3, 4] and set f(6) = 12 - 6 = 6, set f(5) = 17 - 6 = 11
7) T = [1, 2]    and set f(4) =  6 - 2 = 4, set f(3) = 20 - 2 = 18
8) T = [0]       and set f(2) =  2 - 0 = 2, set f(1) = 21 - 0 = 21
9) T = []        and set f(0) = 0

We can take $f$ to be our final answer array where $f = [21, 18, 11, 6, 4, 2, 0]$.

Problem with applying this to a Tree

You may notice a problem with applying this to a tree. We are destroying the information of $T$ when we finally get to a leaf node. So to remedy this, we will have to rebuild it in a way as we come back up the recursion stack. For this we will need to keep track of a few more things. First, we will need to know the depth at which a node resides. This is easy to calculate in a single traversal of the tree. Next, we will need to know the depth at which a node was removed from $T$. This is also easy to keep track of during the recursion. So let's move to the next section of the algorithm itself.

The Algorithm Approach

Let's define some things we need. I'll simply add them as pointers on the node itself and assume that our stack $T$ holds a reference to the nodes. For a node $V$ let the node have the following properties:

v.rank - rank of node $v$. (given)
v.value - value of node $v$. (given)
v.sum - the sum of the values of nodes in the subtree rooted at $v$ (precomputed).
v.depth - the depth of node $v$ where the root is at depth 0. (precomputed)
v.removal - the depth we are at when we remove node $v$ from $T$. This may be overwritten multiple times throughout the algorithm if $v$ has multiple children.
v.f - the function we're interested in computing (based on the definition in the question). Initially set v.f = v.sum, and we will subtract away subtrees where necessary.

For the sake of dealing with base cases, I will assume w.l.o.g. that leaf nodes will have a dummy node attached to them as a child with value 0 and rank less than that of all nodes in the tree.

So we have our stack $T$, we will also have another stack $R$ which will keep track of the order of the nodes we've removed from $T$. This will be necessary to rebuild $T$ on our way back up from recursion. Assume $T$ and $R$ are global variables.

def visit(v, d):
  // Where v is the node we're visiting, and d is the depth we're at.

  // Before recursion
  while top(T).rank > v.rank:
    u = pop(T)
    u.removal = d     // set depth of removal
    u.f = u.f - v.sum // remove sum of subtree rooted at v because it's lesser
    push(R, u)        // push it onto our removal stack R

  if v is not a dummy node:
    push(T, v)
    for each child u of v:
      visit(u, d + 1)

  // Build back up T, we use d - 1 because we're building it back up
  //   so that it is fixed for the level above (when recursion returns)
  while top(T).depth > d - 1:
    u = pop(T)        // we must remove nodes that are depth below our current

  while top(R).depth <= d - 1 and top(R).removal > d - 1:
    u = pop(R)
    push(T, u)

Example

Consider this tree (assume rank = value):

Let's work through the first few steps of this example explicitly:

d = 0 | v = 2 | T = [2]          | R = [] recurse on 4
d = 1 | v = 4 | T = [2, 4]       | R = [] recurse on 5
d = 2 | v = 5 | T = [2, 4, 5]    | R = [] recurse on 8
d = 3 | v = 8 | T = [2, 4, 5, 8] | R = [] recurse on 7
d = 4 | v = 7 | T = [2, 4, 5, 7] | R = [8] recurse on 0

set 8.f = 15 - 7 =  8 and 8.removal = 4

d = 5 | v = 0 | T = []           | R = [8, 7, 5, 4, 2]

set 7.f =  7 - 0 =  7 and 7.removal = 5
set 5.f = 24 - 0 = 24 and 5.removal = 5
set 4.f = 53 - 0 = 53 and 4.removal = 5
set 2.f = 55 - 0 = 55 and 2.removal = 5
build T back up and return

d = 4 | v = 7 | T = [2, 4, 5, 7] | R = [8]

build T back up and return

d = 3 | v = 8 | T = [2, 4, 5, 8] | R = []

build T back up and return

d = 2 | v = 5 | T = [2, 4, 5]    | R = [] recurse on 3
d = 3 | v = 3 | T = [2, 3]       | R = [5, 4] recurse on 1

set 5.f = 24 - 4 = 20 and 5.removal = 3
set 4.f = 53 - 4 = 49 and 4.removal = 3

d = 4 | v = 1 | T = [1]          | R = [5, 4, 3, 2] recurse on 0

set 5.f = 24 - 4 = 20 and 5.removal = 3
set 4.f = 53 - 4 = 49 and 4.removal = 3

...

I will not continue the rest cause it will take a while, but you can see at this point all nodes in the subtree rooted at 5 have been completely evaluated.

Analysis

This is where I'm having a bit of trouble. It is technically one traversal of the tree, but I am not sure if this is $O(n + m)$. There would need to be some argument about how many times a node can be pushed and popped onto $T$ and $R$.

Consider a path $p$ from root to leaf. Every node on this path will be popped and pushed from $T$ and $R$ a constant number of times (similar argument as the linked list). Every time a node $v$ forks into $k$ children, this will increase the number of times nodes on the path from root to $v$ will be pushed and popped by a factor of $k$. When we reach the leaf node, $T$ will be empty and $R$ will be full.

You can upper bound this by the following formula. Let $k$ be the total number of leaf nodes, let $d$ be the maximum depth of the tree. Then the runtime is $O(kd)$.

To put this into perspective, for a binary tree of depth $\log n$ and $n/2$ leaf nodes, this runs in $O(n \log n)$.


Software mutexes and consensus number 1 There are numerous possibilities to implement a software mutex using only shared memory (e.g. Dekker's algorithm).

Recently I've read the following from a paper "Wait-free Synchronization" by M. Herlihy:

  there exists no two-process consensus protocol using multireader/multiwriter atomic registers.

And then the theorem: "Read/Write registers have consensus number 1".

I guess I am missing something in my understanding of the definitions. Shared memory is an array of atomic registers, right? And Wikipedia says Dekker's algorithm is deadlock and starvation free. So how is that possible with consensus number 1?

Herlihy's result, indeed the whole paper, is about wait-free synchronization. Corollary 1 states that there is no wait-free two-process consensus protocols using atomic registers. Wait-free is defined informally at the beginning of the introduction, and defined formally in the automata model in §2.3.

Dekker's algorithm is not wait-free. The busy-wait loop to enter the critical section is a wait in the sense of Herlihy. It's possible to have P0 set its wants_to_enter flag, then P1 sets its own, then P0 sees that P1 wants to enter and one of the processes busy-waits (depending on the turn value).

Think of wait-free as “must work even with a hostile scheduler”, i.e. with a scheduler that always switches between processes at the most inconvenient time. Dekker's algorithm requires a scheduler that's at least weakly fair, i.e. guaranteeing that if a process is schedulable then it's eventually scheduled (as opposed to being locked in an order of execution that causes a livelock, such as never exiting the busy-wait loop). Wait-free algorithms complete in finite time with any scheduler that doesn't completely lock up the system if there's work to do (no fairness requirement).

Busy-wait loops require the scheduler to be preemptive (otherwise the loop runs forever). In practice a busy-wait loop would be written with a yield call, and even non-preemptive schedulers try to avoid immediately re-scheduling a process that just yielded. But even with a preemptive scheduler, busy-wait is generally bad: if nothing else it uses up CPU time and electricity. A case where Dekker's algorithm doesn't work at all is if the two processed have different priorities and the scheduler never schedules the process that would enter the loop because the busy-waiting process has a higher priority.

A naive solution to avoid waiting is to put in a time delay. It isn't a good solution because in practice it means an additional useless delay when there is contention on the mutex, and in theory the delay isn't enough since the scheduler could take that long to make its decision and so end up scheduling the busy-wait loop only anyway. A good solution avoid busy-wait altogether is to add a primitive that lets a process block until some shared variable is modified; with such a primitive, I think it's easy to achieve an infinite consensus number.

It is instructive to contrast Dekker's algorithm with a wait-free consensus solution, such as the one Herlihy gives for two processes (fig. 7).

prefer[P] := input
if RMW(r,f) = v
  then return prefer[P]
  else return prefer[Q]
end if

RMW is a primitive operation with a consensus number of at least 2, for example test-and-set. There's no busy-wait in the consensus protocol itself: both processes run pretty much instantly, without ever waiting for the other one. In a real scenario, the processes that doesn't acquire the mutex may well wait for it; but the process that does acquire the lock isn't stopped, and in practical terms that means at least an expected performance gain both when there is contention and when there isn't.


Why do we use persistent data structures in functional programming? Functional programming employs persistent data structures and immutable objects. My question is why is it crucial to have such data structures here? I want to understand at a low level what would happen if the data structure is not persistent? Would the program crash more often?

When you work with immutable data objects, functions have the property that every time you call them with the same inputs, they produce the same outputs.  This makes it easier to conceptualize computations and get them right.  It also makes them easier to test.

That is just a start.  Since mathematics has long worked with functions, there are plenty of reasoning techniques that we can borrow from mathematics, and use them for rigorous reasoning about programs.  The most important advantage from my point of view is that the type systems for functional programs are well-developed.  So, if you make a mistake somewhere, the chances are very high that it will show up as a type mismatch.  So, typed functional programs tend to be a lot more reliable than imperative programs.

When you work with mutable data objects, in contrast, you first have the cognitive load of remembering and managing the multiple states that the object goes through during a computation.  You have to take care to do things in the right order, making sure that all the properties you need for a particular step are satisfied at that point.  It is easy to make mistakes, and the type systems are not powerful enough to catch those mistakes.

Mathematics never worked with mutable data objects.  So, there are no reasoning techniques we can borrow from them.  There are plenty of our own techniques developed in Computer Science, especially Floyd-Hoare Logic.  However, these are more challenging to master than standard mathematical techniques, most students can't handle them, and so they rarely get taught.

For a quick overview of how the two paradigms differ, you might consult the first few handouts of my lecture notes on Principles of Programming Languages.


Program counter in a CPU I know that the CPU has a program counter which takes instructions that are required to execute a program, from the memory, one by one. I also know that once the first instruction is executed, the program counter automatically increments by 1 and accesses the data in the cell with the corresponding address.

Now my question is, what if the next instruction in the memory cell, i.e. the instruction in the memory cell after incrementing the counter by 1 is not the required instruction to execute the given program? And what if the next instruction that is required is, in a memory cell who's address can be got to only after 'n' increments?

If it helps I used this video as a reference

EDIT: If it isn't clear, what I'm trying to ask is this:
Suppose to execute a given program I need 5 instructions- A,B,C,D,E.

Now suppose instruction A is loaded in a  memory cell with address 0000H. So when the program counter reads 0000, it takes the instruction from 0000H, and when the counter reads 0001, it takes the memory from 0001H and so on. Now what if instruction C is in 0007? After 0001H the program counter would increment to 0002. But i don't need the instruction from 0002H. I need it from 0007. So what does the counter do in such a situation?

Code isn't arranged randomly in memory. The next instruction to be executed will, by default, be the one at the next memory location, unless something specific (a "jump" instruction) is done to execute code from somewhere else.

So, if your program is literally "Do A, then B, then C, then D, then E", the compiler will place those instructions in consecutive memory cells. If, for some reason, they were in non-consecutive memory cells, the program would have to become something like "Do A, then jump to B's location, then do B, then jump to C's location, etc." The computer has no way of knowing that it's not supposed to execute the next instruction in memory, except being told to do that. And being told to do that requires the execution of some kind of instruction.


Growing multiples of variable combinations I need to find growing combinations of variables a, b, c etc. I don't know names of math things in English well, so my description of the problem will be in pseudocode. This is for a programming problem, but I want to understand the underlying mathematics. I would highly appreciate proper names of techniques used so I can look them up further.

Lets say we have a list of variables

L (a, b, c)

And one single variable l which is the maximum desired count of a single variable from L.

I need to find every combination of elements from L multiplied by numbers from 0 to l.

So, for l = 3 I expect the following result:

1a0b0c
0a1b0c
0a0b1c
1a1b0c
1a0b1c

... and so on until ...

3a3b3c

You can think of these combinations as 3-digit numbers in base $l+1$. For example, if $l=9$ then the solutions to your problem are in one-to-one correspondence with 3-digit decimal numbers, from 000 to 999. There are in total $(l+1)^3$ of them.

As an aside, it is not clear why you omitted 0a0b0c.


Coloring graph with constraints on assortativity I have come across the following problem and I would love for your thoughts on an optimal solution or approximate calculations worth trying.
The formulation of the problem in the form of graph theory:
Given a weighted graph $G=(V, E)$. In addition, we have $C$ colors and $f([C_1, ...C_n])$ the distribution function of vertices in the graph by color (That is, how many nodes of each color are in the graph). Also given an assortativity parameter, $M$. In general, assortativity is the tendency of nodes in the graph to attach to others that are similar in some way. For simplicity, set it to be the number of edges between vertices of the same color (Originally it is a little more sophisticated calculation. But unnecessary for our needs.).
Now, I want to color the graph such that the constraint on the number of vertices of each color is met and in addition, we minimize the expression: $|M-M(G)|$ (recall,  $M$ is the desired parameter and $M(G)$ is the parameter as it is calculated on the given coloring). Of course, we are not only interested in the minimum value, but also the coloring that created it.
This problem also has a parallel formulation for matrices:
Given symmetric matrix $A$ ($n\times n$) - this is the adjacency matrix of the above graph. The value of the entry $A_{ij}$ is set to equal the weight of the edge $(i,j)$. Here, too, we are given a distribution function of the rows and the columns in the matrix by color. As before, we have an assortativity parameter, $M$.
Now, let's try to find symmetric coloring of rows and columns in the matrix (if any line is colored in a certain color, so is the corresponding column) such that the constraint on the number of rows and columns of each color is met.
In addition, we will try to minimize the expression: $|M-\Sigma(A_{i,j}|\text{where column } i \text{ and row } j \text{ are in same color})|$ (which means, the difference between the desired $M$ and the sum of all entries that their colum and their row are in same color).
Epilogue:
I know that both formulas are completely equal. I hope the two different perspectives help me and others to think about different directions to solve the problem.
For the sake of curiosity, I will say that this problem is part of a challenge I face and it is to generate pseudo-synthetic social networks with real-life constraints. This is a problem that I formulated and not part of an article or a home exercise.
Thanks in advance.

Your problem is NP-hard.  Consider the special case where $M=0$; then your problem is as hard as the graph coloring problem, which is NP-hard. (Ok, with an additional constraint on the distribution function, but it will still be NP-hard.)  In particular, if $M=0$ and the graph is $C$-colorable, then the optimal solution have $|M-M(G)|=0$; if the graph is not $C$-colorable, then the optimal solution will have $|M-M(G)|>0$.  So, if we could find the optimal solution for your problem for arbitrary $M$, we could determine whether the graph is $C$-colorable by setting $M=0$, finding the optimal solution, and checking whether $|M-M(G)|=0$.
One possible approach to finding an approximate solution would be to try local search or simulated annealing.


How are problems classified in Complexity Theory? I'm reading Sipser's Introduction to the Theory of Computation (3rd edition). In chapter 0 (pg. 2), he says we don't know the answer to "what makes some problems computationally hard and others easy," however, he then states that "researchers have
discovered an elegant scheme for classifying problems according to their computational difficulty. Using this scheme, we can demonstrate
a method for giving evidence that certain problems are computationally hard,
even if we are unable to prove that they are."

So my question is: HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?

Also, what/where is this "scheme" that does this classifying. (I did some googling and couldn't find anything)

That's what you get when you distill a whole bunch of theory to a wider audience.

In his book, Sipser addresses a general audience at the undergraduate level, possibly with no notion of computability theory; hence, he can only hint at concepts which are to be given a more formal treatment later on in the book. The part you cite is from chapter 0 (i.e., not really a chapter), whereas the material for complexity theory only appears at the end (i.e., part three). This is why the passage is so fuzzy. Most likely it is intended only as motivation and to give a broad overview for the topics to be covered in the book.

The "scheme" Sipser is talking about are reductions. If we know a problem $A$ is reducible to a problem $B$, then we know $B$ is at least as hard as $A$. (Incidentally, this is also why it is common practice to denote reductions with a "$\le$" sign.) This gives us a way of ordering problems according to their difficulty, at least for those having reductions we are aware of. As Sipser states, though, by using only reductions "we are unable to prove" whether the problems are really hard or not; reductions only give us relative, not absolute notions of hardness. This is why separation results are still rare in modern complexity theory: We have a bunch of reduction (e.g., NP-completeness) results, but only a handful of separation results (e.g., the time and space hierarchy theorems).


Where does the process reside in memory? When a program runs in CPU, it turns into a process. In what kind of data structure is the process stored in a system memory?

In Heap or Tree or some other data structures?

A process is not a single data structure. In the Windows operating system, for example, a running process has a number of different structures in its memory including a copy of its PE header and its environment variables. Here is a table from a debugger showing the layout of one process after it has been loaded into memory:

The various pieces of data have different structures. For example, the PE header is a record, but the heap is usually some kind of tree or list.


Showing that $BPP \subseteq EXP$? I am trying to understand why $BPP \subseteq EXP$. This question almost gives the answer (simulate $BPP$ machine on all possible toin cosses and then "act accordingly"). However, it is not clear to me what act accordingly means: I am thinking we need to count how many times the probabilistic Turing machine accepts and how many times it rejects and then act upon this information - but how exactly?

A $\mathsf{BPP}$ machine $A$ has randomness complexity $r(n)$ which is polynomial in $n$. Hence, an $\mathsf{EXP}$ machine $B$ can loop over all $2^{r(n)}$ values of the random tape of $A$, simulating $A$ with each random input (each simulation taking polynomial time), and count how many times $A$ accepts or rejects. The overall decision of $A$, then, is whichever of the two counters contains a larger value at the end of this process.

Interestingly, the same reasoning also explains why $\mathsf{PP}$ is contained in $\mathsf{EXP}$.


Sphere packing inequality for error-correcting codes i am wondering if the following inequality is correct:

if a code allows repairing of no more than k errors (inclusive, included) and m is the number of information bits and r the check bits, then $$∑^k_{i=1}\binom{m+r}{i}+1≤2^r$$

holds true?

please if you can explain so i can understand how you choose answer you give.

the only inequality i find in books that look similar is about "perfect code" with the inequality given is: $2^n = 2^k\sum_{i=0}^k\binom n i$. but i not see how this code is relevant. i try to do research in other books or internet and no answer sadly. please help me understand if given inequality is true or not based on information given.

thank you much.

For a codeword $x$, let $B_k(x)$, the ball of radius $k$ around $x$, consist of all words at distance at most $k$ from $x$. Notice that
$$|B_k(x)| = \sum_{i=0}^k \binom{m+r}{i}. $$
If the code supports correcting up to $k$ errors, then the sets $\{ B_k(x) : x \in C \}$ must be disjoint. The code contains $2^m$ many different codewords, hence we get
$$
2^m \sum_{i=0}^k \binom{m+r}{i} \leq 2^{m+r},
$$
which is the same as your inequality. Here $m+r$ is the length of each codeword, and $2^{m+r}$ is the number of possible vectors.

If your code is $q$-ary rather than binary, then the same calculation shows that
$$
\sum_{i=0}^k (q-1)^i \binom{m+r}{i} \leq q^r.
$$


Efficiently generating a prime polynomial of a given degree I'm playing around with finite field arithmetic and implementing it in a little library. I'd like to be able to handle arbitrary finite fields given their size and characteristic. I don't want to write down a prime polynomial for every given possible finite field though. How can I generate a prime polynomial of a given degree for use in multiplication? To be clear I don't care which polynomial I get, and I don't want all of them. I just want any old one of a given degree. If this is an open research question what if we only try to solve it for $GF(2^n)$?

It suffices to construct an irreducible polynomial of degree $n$ over $GF(2)$ (as this immediately induces an explicit construction for $GF(2^n)$).  So, how do you generate an irreducible polynomial?

One approach is to repeatedly choose a random polynomial of degree $n$, then test whether it is irreducible.  You can test for irreducibility by factoring the polynomial over $GF(2)$.  There are standard algorithms for polynomial factorization; they run in polynomial time.  Moreover, about a $1/n$ fraction of all polynomials are irreducible (see here).  It follows that on average about $n$ iterations will suffice, and since each iteration can be done in polynomial time, the whole thing runs in (randomized) polynomial time.


Checking whether all integers appear exactly once Let $\texttt{a[]}$ be a finite array. We want to check whether every number between $\texttt {min(a[])}$ and $\texttt {max(a[])}$ appears exactly once.

An obvious solution is sorting the array in time $O(n\log(n))$ and go through the sorted array in linear time and check that $\texttt{a[k+1] == a[k]+1}$ for $0\leq\texttt{k} < \texttt{length(a)-1}$.

The total complexity of this would be again $O(n\log(n))$. Is there a better way to do this?

Let $A$ contain $n$ elements. Scan $A$ to determine the maximum value $m$ in $A$. Then, initialize a bit vector $B$ of size $m$ to all zeros. Then scan $A$ and use $B$ for bookkeeping: when you encounter $i$ in $A$, set $B[i]$ to one (if $B[i]$ is already set, return false). In the end, return true if and only if $B$ contains exactly $n$ ones. This algorithm runs in $\Theta(n+m)$ time, or even in $\Theta(n)$ time if we assume $m = O(n)$.

We can also be a little bit more clever with David Richerby's idea. Let us scan $A$ to find its minimum value $s$. Then initialize an array $B$, this time of size $n$, to all zeros. Go through $A$ again, and when you encounter the value $i$ in $A$: if $i - s > n$ or $B[i-s]=1$, return false. Otherwise, set $B[i-s]=1$. Obviously, this algorithm runs in $\Theta(n)$ time (independent of $m$).

In both cases we assume reading the index of an array is done in unit time, and also that arbitrary width arithmetic is performed in unit time.


What's wrong with the following argument that $NP \subset coNP$? What's wrong with the following argument that $NP \subset coNP$?

let $L \in NP$; then there exists an NTM $N$ that decides $L$ in $f(n)$ time where $f(n) = O(n^k)$ for some natural number $k$.

Define $H = $ on input $z$:

run $z$ on $N$ for at most $f(|z|)$ steps.
if $N$ accepted, reject. If hasn't accepted, accept.

Then if $z \in \bar{L}$ then $N$ will not have accepted $z$ after any number of steps, so $z \in L(H)$.

If $z \in L(H)$ then $N$ hasn't accepted $z$ after $f(|z|)$ steps. If $z \in L$ then $N$ would have accepted it after $f(|z|)$ steps.

Is the problem here that computing $f(|z|)$ may not take polynomial time, in $|z|$? It seems like it should.

This is not true:

  Then if $z \in \bar{L}$ then $N$ will not have accepted $z$ after any number of steps, so $z \in L(H)$.

It might be $z \in \bar{L}$, but the machine will not be stopped anytime!


Size of address spaces (logical and physical) Suppose a system in which addresses (physical and logical) occupy 32 bits, page size is 1024 bytes
(210), and physical memory is of size 32MB. How many frames are in physical memory? Is the logical
address space larger than physical memory? Explain.

The solution given is:

232 byte logical address space (assuming byte-addressable machine)

225 byte physical memory

210 byte pages

At one page per frame, there are 225/210 = 215 pages in physical memory. The logical memory address
space is larger than physical memory.

Can someone explain how to arrive at this solution?

The size of a frame is the same as that of a page, so the size of a frame is 1024 bytes (210 bytes).

If the physical memory is 32MB (225 bytes), the number of frames is 225 / 210 = 215 and this is also the maximum number of pages that can be present in memory at the same time.

The logical address space is larger than the physical address space, a process can address 232 memory locations that is 232 / 210 = 222 pages.


$O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right Assume A is an m sized array containing n ($m \ge n$) natural numbers (excluding $0$), sorted on the left of it.
All remaining cells on right are filled with zeros.

For example, $m=10, n=4$:

$$A = \{5,7,11,24,0,0,0,0,0,0\}$$

How can I find the index of a natural number x in A with $O(\log \boldsymbol{n})$ complexity?

Edit: $n$ is not known.

A two-stage binary search works. First, for the purposes of this search define $0$ to be greater than any positive integer.

Then, let $l = 1$ and $h = 2$ and:

While $A_h \leq x$ let $l \leftarrow h$ and $h \leftarrow 2h$. Since for all $h > n$ we have $A_h = 0$, which we defined to be greater than any positive number, this loop must exit within $O(\log n)$ iterations.
Now $A_l \leq x < A_h$, and $A$ is sorted, so we can do a binary search in range $[l, h]$. This also takes $O(\log n)$ steps since $l,h \leq 2n$.


Divide and conquer algorithm to sort nk items in n lists that runs in O(nk*logn) time? In trying to write pseudocode for it, this is my attempt:

I'm just trying to write a pseudo-code for it and explain the run time.

So far this is what I have:

k-merge-sort(L)
  { if length(L1) <2 return L1
   else
     { split L into L1, L2, L3
     A1 = k-merge-sort(L1)
     A2 = k-merge-sort(L2)
     ....
     An = k-merge-sort(Ln)
     Bn = k-merge(A1..An)
     }

Thoughts? Thank you! As for the run time, the logn part of it comes for it being a complete binary tree's height, the height being the number of lists and the n*k part from the items.

This is classic multi-way merge: Create a heap of pairs (element, which list did it come from). Initialize with first elements of each list. Repeatedly remove the minimum element and add the next element from its originating list.

Also discussed before at https://stackoverflow.com/questions/5055909/algorithm-for-n-way-merge .


Can one truly build a schedule from graph coloring? I know that with graph coloring we can build a simple schedule with maybe 9 students and 9 lectures (i.e. these notes) and determine the minimum number of meeting times, but is this feasible in a real world scenario? Say I have 30 professors and 200 students, can we determine a minimum number of meeting times with a graph this size? And does the graph tell us when they need to meet? Pointing to any available examples would be greatly appreciated.

In addition, could the graph take into account some lectures twice as long as other lectures?

[...] is this feasible in a real world scenario?

I'm not sure.  But note that determining the chromatic number of a graph and determining the minimum number of timeslots needed to schedule lectures with a given pattern of conflicts are exactly the same problem. So, if the scheduling problem can't be feasibly solved by colouring, it can't be feasibly solved any other way, either.

  Say I have 30 professors and 200 students, can we determine a minimum number of meeting times with a graph this size?

Note that the size of the graph depends only on the number of classes. The only effect that the number of students has is that having more students means there are more likely to be conflicts between more classes.

  And does the graph tell us when they need to meet?

No. It will just tell you "Here are sets $S_1, \dots, S_k$ that partition the classes."  All the classes in one set should be scheduled at the same time; different sets need to be at different times. The graph doesn't care whether you study algorithms at 10am and Java at 11am, or algorithms at 11 and Java at 10, or algorithms at 3am and Java at 3pm. All it knows is that, if at least one person is studying algorithms and Java, those two classes have to be at different times.

  In addition, could the graph take into account some lectures twice as long as other lectures?

Not directly.  But you could pretend that your two-hour electronics lab is really two one-hour labs called electronics1 and electronics2 which, of course, can't be at the same time, because students take both courses. And, because the graph doesn't care what time the classes are at, you can schedule electronics2 to be in the slot immediately after electronics1.


A question about type rule I realized that almost no one explained how to selected the type variable T1

 Γ ⊢ e1 : T1 -> T  ,  Γ ⊢ e2 : T1
 -------------------------------- T-APP
 Γ ⊢ e1 e2 : T

when doing type checking (from bottom to top).

So, the question is how T1 is introduced? Is there any condition about T1?

T1 is a schematic variable. Every consistent substitution of T1 with a type produces an instance of the rule. In a simple enough system, the inference rules can be used directly as the blueprint for a type-checking algorithm. In languages with richer type systems, type-checking algorithms become more complex or even undecidable (which is not a desirable features). Let me give an example where I type-check the program using a simple derivation.

Let's say I have the following program I wish to type-check:

(lambda x: nat. x = 0)(4)

First, we can deduce that 4 : nat by using the usual typing rules for natural numbers, which I will not reproduce here. Then we type-check the lambda abstraction with following derivation (I apologize for the sloppy latex):

$$ \underline{x : nat ⊢ x: nat \quad x: nat ⊢ 0 : nat} $$
$$ \underline{x : nat ⊢ x = 0 : bool}$$
$$ \underline{\lambda x: nat. \ x = 0 : nat \to bool} $$

Finally, using the application rules:

$$ \underline{\lambda x: nat. \ x = 0 : nat \to bool \quad 4 : nat} $$
$$ (\lambda x: nat. \ x = 0)(4) : bool $$

Note that type-checking is much simpler when we're working in a type system without subtyping, in that ever expression is monomorphic. The typing rules are syntax-directed. That is, the structure of the program dictates the type of every expression.


Is the following problem NP-hard? (or have you seen it before?) I genuinely don't know if the following problem is NP-hard. I have never seen it mentioned online, but it's hard to even search for exact problems like this. I have been trying to find an efficient algorithm for a while and intuitively it feels very NP-complete to me, but I haven't been able to prove it. A solution would be directly applicable to my work, if it could be found.

Problem: Assume you have $N$ different tasks which each have a unique integer length $l_n$. These tasks are arranged in a dependency tree so that each task can only be started after zero or more other tasks are completed. You also have $M$ different resources. Each task requires a given resource and each resource can only be used by one task at a time. What ordering of tasks allows for the fastest completion of the overall program (based on maximizing the amount of tasks that can be parallelized).
Example: In less abstract terms, imagine that each task is a step in a recipe. The resources are elements of a kitchen like an oven or mixer. If cooking one part of a meal requires a short use of the oven followed by a lot of manual work, and cooking the other part of the meal requires a long oven time, you should schedule the shorter cook first so that you can do the rest of the work for that component while the other half is in the oven.
Another example: Consider the dependency tree below. $a \rightarrow b$ indicates "$a$ depends on $b$". The length of a block indicates the time it takes to complete (1 or 3 in this case). There are two resources/channels: red and blue.

An example solution might look like this:

This shows that a greedy approach (like scheduling (1) and (2) simultaneously) is not sufficient -- you have to look ahead to minimize waiting for resources.

This problem (more formally its decision version) is NP-complete.
NP-hardness can be shown via a reduction from the Job-Shop Scheduling Problem (JSP) with makespan objective, which is well-known to be NP hard.
In the JSP, we have $n$ jobs $J_1, J_2, ..., J_n$. Within each job there is a set of operations $O_1, O_2, ..., O_n$ which need to be processed in a specific order. Each operation $o$ has a specific machine $m_o \in M$ that it needs to be processed on and only one operation in a job can be processed at a given time. (adapted from Wikipedia)
Now it is easy to see that JSP is just a special case of your proposed problem (one task per operation of JSP, dependencies only between successive operations in a job), which makes it at least NP-hard too.
Membership in NP can be shown by guessing an optimal schedule and verifying in polynomial time that it fulfills all constraints.


Physical significance of Don't cares in Digital Logic design In many Digital functions we come across don't care conditions where we use don't cares to minimize functions.
What is the significance of these don't cares in real world scenario where we actually implement the functions using logic gates?

Yes they do have physical significance.Input combinations  for which value of a function ( or a device) is not specified are called don't care conditions.
They are met when the number of inputs are more than expected.
For example, conversion of binary to BCD. Both are 4 bits long but using 4 bits 16 binary numbers are possible whereas only 10 BCD numbers.

Consider another example: Suppose there are 8 locations to be addressed and we have a total of 4 address lines. To address 8 locations we only need 3 bits hence three address lines. The forth extra address line is like dont care. We actually don't care the logical value of contained in that address line.

Actually don't cares allow us to choose from a class of many functions.
Each don't care bit represents 2 values {0 or 1}, hence a function containing 'k' don't care bits correspond to a class of $2^k$ distinct functions ( as 'k' inputs can give rise to $2^k$ combinations).
The task is to choose a function out these $2^k$ functions which has the most minimal representation. Thereby decreasing the number of inputs hence making the implementation faster.


Can someone interpret what this is asking for I have this programming problem, but I really cant figure out what it wants me to do. Heres what it is:

  The cube root of a number can be found based on the observation that, if $t$ is an approximation of the cube root of $a$, then $\tfrac13\left(\tfrac{a}{t^2} + 2t\right)$ is a better approximation.

  Create a method double betterCubeRoot(double a, double t) that will find the cube root of $a$ accurate enough so that the difference between $t^3$ and $a$ is less than 0.0001. Use recursion.

  Then write the method double cubeRoot(double a) that makes use of the method with 1 as the initial value of $t$. Write a program that will test values both positive and negative.

Can someone please explain what this means. I dont understand how I am supposed to find the cube root of 'a' using the given equation. Thanks.

Here is what i have done:

public static double betterCubeRoot (double a, double t)
{
    double tCubed = Math.pow (t, 3);
    double dif = Math.abs (tCubed - a);

    double eq = ((a / (t * t)) + 2 * t) / 3;

    if (dif < 0.001)
    {
        return eq;
    }
    else
    {
        return betterCubeRoot (eq, t) ;
    }
}

Guess anything at all for the cube root of $a$: call that value $t$. $t′=\tfrac13(a/t^2+2t)$ is closer to $\sqrt[3]{a}$ than $t$ is, so use $t′$ as your next guess. Keep going.


Maximize ratio of sums I have a $2 \times n$ matrix of positive integers, where the elements are denoted by $a_{ij}$ for all $i$ in the set $\{1,2\}$ and for all $j$ in the set $\{1,\ldots,n\}$.

I would like to select a subset $S$ of the columns that maximizes the ratio $$\left(\sum_{j\in S}a_{1j}\right) / \left(\sum_{j\in S}a_{2j}\right)\,.$$

Can this be done efficiently?  Is this a known problem?

For example, if

$$A=\begin{pmatrix} 1 & 2 \\ 2 & 3\end{pmatrix},$$

then the best thing to do is to choose the second column. Because, (i) if I choose column $1$ I will get $1$ as the sum of the first row and $2$ as the sum of the second row, (ii) if I choose column $2$ I will get $2$ as the sum of the first row and $3$ as the sum of the second row and (iii) if I choose column $1$ and column $2$ I will get $3$ as the sum of the first row and $5$ as the sum of the second row.

There's a linear-time algorithm for this problem.  Find the index $j$ that maximizes the ratio $r_j = a_{1j} / a_{2j}$.  This $r_j$ is the maximum possible value of the ratio of sums.

Proof: The ratio of sums can be made $\ge c$ if and only if there exists a set $S$ such that $\sum_{j \in S} a_{1j} - c a_{2j} \ge 0$.  That's possible iff there exists $j$ such that $a_{1j} - c a_{2j} \ge 0$, i.e., such that $a_{1j}/a_{2j} \ge c$.

As a tip for how you could discover this on your own: play with some examples.  If you try many examples and work out by hand the optimal solution, you might happen to notice the pattern (that the best ratio for the sums matches the largest ratio of columns), and that would give you a hypothesis that you could then try to prove.


Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P? Just as the title says: Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P? Additionally, if one could show that a problem known to be in NP had a polynomial time quantum solution, would that be enough to show that P=NP?

No.

The class $P$ refers to the classical Turing machine model, we don't know if $BQP\subseteq P$ (we suspect that it isn't), thus this does not mean that factoring is in $P$.
We don't know how to simulate a quantum algorithm in a classical machine with only polynomial slowdown (the naive translation would result in an exponential algorithm for factoring).

Many problems in $NP$ have a quantum polynomial time solution, and also classical polynomial time solution, since $P\subseteq NP$. See our reference question for an overview and precise definitions.

The more interesting question would be if quantum computers can solve NP-hard problems efficiently, or formally, if $NP\subseteq BQP$. We suspect that this statement is false, though even $PH\subseteq BQP$ is still open. Proving $NP\not\subset BQP$ would also in turn prove that $P\neq NP$ (since $P\subseteq BQP)$.

It is also worth mentioning that factoring in not known to be NP-hard (and believed not to be) so we can still have both $NP\not\subset BQP$, and a polynomial algorithm for factoring in a quantum computer.

See these questions:

Consequences of SAT∈BQP,

Can a parallel computer simulate a quantum computer? Is BQP inside NP?,

for a discussion on the possibility of $NP\subseteq BQP$.


Coverage problem (transmitter and receiver) I try to solve the following coverage problem.

  There are $n$ transmitters with coverage area of 1km and $n$ receivers. Decide in $O(n\log n)$ that all receivers  are covered by any transmitter. All reveivers and transmiters are represented by their $x$ and $y$ coordinates.

The most advanced solution I can come with takes $O(n^2\log n)$. For every receiver sort all transmitter by it distance to this current receiver, then take the transmitter with shortest distance and this shortest distance should be within 0.5 km.

But the naive approach looks like much better in time complexity $O(n^2)$. Just compute all distance between all pairs of transmitter and receiver.

I am not sure if I can apply range-search algorithms in this  problem. For example kd-trees allow us to find such ranges, however I never saw an example, and I am not sure if there are kind of range-search for circles.

The given complexity $O(n\log n)$ assumes that the solution should be somehow similar to sorting.

You can use the Voronoi diagram, together with Kirkpatrick's data structure to solve this problem.

Like Raphael and Syzygy suggested, you can use Fortune's (sweepline) algorithm to create the Voronoi diagram. Worst case time: $\mathcal{O}(n \log n)$.

The Voronoi diagram will have a bunch of polygons, each one containing a transmitter. Any point within the polygon is closest to that transmitter. Thus, if you can find out which polygon contains the receiver, you can find the closest transmitter to it by somehow finding out which polygon it is in. After that, you check if that transmitter is within $1\ \text{km}$.

To determine which Voronoi polygon contains the receiver, you first triangulate each polygon in the diagram. Now you have a triangle mesh. Next you use Kirkpatrick's data structure to locate any triangle containing a given point in $\mathcal{O}(\log n)$ time, worst case. Constructing Kirkpatrick's data structure takes $\mathcal{O}(n\log n)$ worst case. Once you know the triangle, you will know the polygon that contains it, and thus the closest transmitter. Doing this for all the receivers will be $\mathcal{O}(n\log n)$, worst case.

  Each cell in a Voronoi
  diagram is a convex polygon, possibly
  unbounded.

  ...

  The number of vertices [of a Voronoi diagram of n sites] V ≤ 2n-5

  ― www.cs.arizona.edu

Each polygon in a Voronoi diagram is a convex polygon. Therefore, since triangulation of a convex polygon takes $\Theta(v)$ time, $v$ being the number of of sides, we can triangulate each cell efficiently. If you fear that triangulation can be pathological (that we might have $n$ cells, each with $n$ sides), then consider this. The Voronoi diagram has $\mathcal{O}(n)$ vertices (see quote above). The triangulation of the Voronoi diagram is planar, and so is a sparse graph, and thus has $\mathcal{O}(n)$ edges and faces. Thus triangulation of a particular cell might take $\mathcal{O}(n)$, but the overall triangulation also takes $\mathcal{O}(n)$. (Basically, we will not encounter many cells with $\mathcal{O}(n)$ sides, this would result too many triangles for a planar graph).

Great explanation/implementation of Fortune's algorithm
Illustration of Kirkpatrick's data structure
Psuedocode for Kirkpatrick's algorithm


Is a unary language regular iff its exponent is a linear function? While doing the current assignment for my formal languages and automata course, I kind of got stuck on exercises involving unary languages (I hope that's the right term), i.e., languages which build upon a single letter. I don't want to ask about the specific exercises, though, but rather about a much more general conjecture I've come up with:

Let $\Sigma=\{a\}$ and $L=\{a^{f(n)}\in\Sigma^*:n\in\mathbb N_0\}$. My conjecture is:
$$L\text{ is regular}\Leftrightarrow \exists x,y\in\mathbb N_0:f(n)=x\cdot n+y$$

Has this question seen any scientific treatment before? Is it "obviously" true / false?

To me, obviously the "$\Leftarrow$" direction is true because one can just construct a DFA with $x+y$ states that cycles through the $x$ states after having read through $y$ states and accepts iff it is at state number $y$.

Linear is close, but the technical term you're looking for is semilinear:, that is, a finite union of linear sets.

Half of the proof of this is a corollary of Parikh's Theorem, which says that any context-free language has a semi-linear Parikh map (that is, the set of vectors containing the occurrences of each letter in the alphabet).

For a unary language, the parikh map of the language is the language itself (i.e. each word is uniquely identified by how many letters it has), so every unary regular language is semi-linear.

The other half of the proof is showing that you can construct a regular language containing every unary semi-linear set. This takes a bit of work, but it's not too hard if you use regular expressions:

$a^k$ recognizes the language $\{ k \}$
$(a^k)^*$ recognizes $\{xk \mid x \in \mathbb{N}_0 \}$
$R_1 R_2$ recognizes $S_1 + S_2$ if $R_1$ recognizes $S_1$ and $R_2$ recognizes $S_2$, where $+$ here is element-wise addition
$R_1 | R_2$ recognizes $S_1 \cup S_2$ if $R_1$ recognizes $S_1$ and $R_2$ recognizes $S_2$, where $|$ here is regular-expression union.


Is machine epsilon the largest relative error in representing a number as a floating point number? Is machine epsilon the largest relative error in representing a number as a floating point number?
There are so many definitions of machine epsilon. I'm starting to get confused.
Isn't the machine epsilon the smallest?

In the most common usage, and in particular in IEEE-754, machine epsilon is the smallest number $\epsilon$ such that $1 + \epsilon \ne 1$.
It does have an interpretation in terms of relative distance between numbers: It is the largest relative separation of two consecutive normal numbers.
There are a couple of important points to understand here:

This is only about normal numbers, as opposed to subnormal numbers (i.e. what older standards called "denormal numbers").
It is about consecutive numbers, namely, some floating point number and its closest neighbour.
Machine epsilon measures separation, not error. It is the relative distance between those floating-point numbers, not the relative error between a floating point number and anything.

So if $x_1$ and $x_2$ are consecutive normal numbers, then:
$$0.5\epsilon \le \frac{|x_2 - x_1|}{\max(|x_1|,|x_2|)} \le \epsilon$$
So if you have a candidate real number, and you want to represent it as a floating-point number, how bad can the relative error be?
As gnasher729 rightly pointed out, it can be as large as you want if the real number would overflow, underflow, or be subnormal. But assuming that it's in a reasonable range, meaning that it is between two consecutive normal numbers, then one of those normal numbers is within $0.5\epsilon$ of it in a relative sense.
Because this is a fraught definition, the term that we usually use is "units of last place", or "ulp" for short. If a real number is within the normal number range, there is a floating point number whose error is at most 0.5ulp.


Context-free grammar for $L=\{0^n1^{2n} \mid n \geq 0\}$ How can I express this language $L = \{0^n 1^{2n} \mid n ≥ 0\}$ as a context-free grammar?

I am new to this field and I am not sure what should I do. Please help me.

As Yuval commented, this is a very basic exercise so you should probably go over the basic definitions. One simple answer for this particular question is:
$$S\rightarrow0S11|\varepsilon$$


What is the graphic TSP? I'm not sure if I understand the following definition of the (well-known apparently) Graphic TSP, also known as graph-TSP :

  ...graph-TSP, that is, the traveling salesman problem where distances between cities are given by any graphic metric, i. e., the distance between two cities is the length of the shortest path in a given (unweighted) graph.

this is from Mömke and Svensson's paper : https://arxiv.org/pdf/1104.3090.pdf

I understand this as follows :
- one is given an input graph, say G, that is unweighted (and supposedly connected).
- one then can construct a complete graph, say G', where cost of edge (u,v) is the minimum distance between u and v in G.
- obtaining an optimal TSP solution in G' results in an optimal solution for the graphic TSP on G.

Is this correct?

Your understanding is correct.

The key point about TSP is that we are given a distance between every pair of cities. In other words, formally speaking, TSP is the problem of finding a minimum-weight Hamiltonian path/cycle on a weighted complete graph, given the weight function.  This doesn't quite correspond to the standard intuition where a salesman is travelling around an actual road network and is forbidden from visiting the same city twice, for reasons nobody can really explain.

In graphic TSP, the distance function is defined in terms of some (possibly weighted, possibly directed) graph on the given vertices.  This is much closer to the usual intuition about what TSP is: driving from, say, Baltimore to New York by the fastest route might involve passing through Philadelphia but, even if we've already visited Philadelphia, we're allowed to pass through again without stopping.


Why is TIME(n log (log n)) \ TIME(n) = ∅? In my computation book by Sipser, he says that since every language that can be decided in time $o(n \log n)$ is regular, then that can be used to show $TIME(n \log (\log n))\setminus TIME(n)$ must be the empty set. Can anyone show me why this is?

both $TIME(n\log(\log n))$ and $TIME(n)$ are regular. I think that only means we can subtract the two sets and the result will still be regular. I just dont understand how its possible to subtract the collection of $O(n\log(\log n))$ time TM decidable languages from the collection of $O(n)$ time TM decidable languages and get the empty set. These two collections are not equal so I feel like there will be something left over

The quick explanation is that

$TIME[o(n\log n)]\subseteq REG\subseteq TIME[n]\subseteq TIME[o(n\log n)]$, and therefore $TIME[o(n\log n)]=REG$.

Similarly:

$TIME[n\log\log n]\subseteq TIME[o(n\log n)]\subseteq REG\subseteq TIME[n]\subseteq TIME[n\log \log n]$, so $TIME[n\log\log n]=REG$

But I think this is not the point you are missing.

You say that $TIME[n\log \log n]$ is regular. This is not exact. When we say that something
 is regular, we mean that it is a language $L\subseteq \Sigma^*$, which is regular (i.e. can be recognized by a DFA).

The class REG is not a language, but a set of languages. That is, $REG\subseteq 2^{\Sigma^*}$. Similarly, $TIME[f(n)]\subseteq 2^{\Sigma^*}$ for every function $f$. These are all classes of languages.

Since we have that $TIME[n\log\log n]\subseteq TIME[o(n\log n)]\subseteq REG$, then
$REG\setminus TIME[n\log\log n]=\emptyset$. This follows from the simple property that if $A\subseteq B$, then $A\setminus B=\emptyset$.