What mathematical background is enough to go through the entire Knuth's TAOCP? I am an undergrad. I can do mathematics fine and am a lot more interested to explore.
I turned towards TAOCP as it is highly mathematically oriented so as to excel at maths and programming at the same time.
But I am stuck. I have only studied calculus, numerical analysis and probability (undergrad level) but the first few pages of the first volume itself is too difficult to get through.
Also, the problems are ranked according to their difficulty level. What all can I do to solve those problems? I really need to get better at mathematics.

What books(mathematics) should one read to be able to understand TAOCP? I am ready to go to a series of books just to get better at it.

Also, any suggestion(s) on how to learn/practice MIX(the TAOCP assembly)?

If your only exposure to math is undergrad level calculus, numerical analysis, and probability, you probably don't want to start out with computer science by reading The Art of Computer Programming. This is not an easy set of books. They're also not the hardest books out there in computer science, but they definitely expect some kind of background in discrete math and algorithm analysis. I would start with an easier book, maybe Introduction to Algorithms (CLRS), which is also mathematical and treats its topic formally, but is designed for undergraduate students without previous background in the field. You should also get a more solid background in discrete math—topics such as combinatorics, recursion, Big O, number theory—as well as linear algebra. Knuth co-authored another book called Concrete Mathematics that might help with that.

Working through CLRS and Concrete Mathematics is probably enough to start TAoCP. The first thing you should do is work through the math in Volume 1 of The Art of Computer Programming. Knuth covers several of the topics in combinatorics and discrete math that will reappear in later volumes. However, he typically doesn't spend a ton of time introducing you to the math he uses. He doesn't assume you know everything, but he does dive in pretty quickly. I would solve a bunch of the easier exercises in each topic to get a grasp on it, and leave the harder exercises for a cold winter's evening.

As for MIX, I wouldn't even bother with it. Programming in assembly language is not a terribly useful skill today, and modern assembly languages look nothing at all like MIX because it was designed before CPU architectures had standardized, before everyone was using 32-bit (or 64-bit) binary computers and it was sometimes desirable to support decimal computers or computers with kooky word sizes. In recognition of this, Knuth created MMIX, a more modern-styled assembly language, and he's now porting all the MIX code in earlier books to MMIX. I would just ignore the fake assembly code completely. I found that trying to remember MIX's idiosyncrasies was an impediment to learning the high-level ideas behind algorithm; the pseudocode and the prose were much more helpful. If you want to learn about low-level programming, go learn about computer architecture, and maybe learn some MIPS or ARM assembly, but do it separately from your studies of algorithms; it's a huge topic in its own right, and you won't do yourself any service by trying to learn both at the same time.

If, however, you insist on learning MIX or MMIX, you can hunt down one of the simulators that let you actually run the code, and learn it like you would any other programming language: by figuring out what it can do and solving some simple exercises. (IIRC, the book even has some MIX exercises that you can complete.) Again, though, I wouldn't. As much as I love the books, they were created in an earlier time, and some parts haven't aged well. MIX is one of those things.


Language consisting of all Turing machine encodings $A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ }

What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL?

I would say $A$ is decidable since we can write an algorithm to check whether a string is a valid encoding of a Turing machine .

But, is $A$ Regular[or CFL or CSL] ?

Edit : Someone argued that he could make an encoding where all the possible strings(What would be the alphabet here?-same as the encoding I suppose) are valid encoding of a TM(since there is a one-to-one correspondence between two countable infinite sets), hence making $A$ regular .

The complexity of $A$ depends on the encoding used for Turing machines. It is easy to come up with an encoding in which every string encodes some Turing machine (there are lots of ways). In contrast, it is easy to come up with artificially "hard" encodings, say the $k$th Turing machine being encoded by $1^kb$, where $b=1$ iff the $k$th Turing machine halts on the empty input; under this encoding, $A$ is not decidable. Nevertheless, it seems intuitively clear that any reasonable encoding makes $A$ decidable, though it's hard to say anything more without knowing the exact encoding.


Indirect Left recursion I'm resolving indirect left recursion for these production rules:

S -> Aa / a   eq1
A -> Sb / b.  eq2

Where S is the starting symbol.

Now I can do this in two ways:

Putting A in eq1

So I'll get the solution (sol1):

S -> Sba /a /ba

and then

S -> aS' / baS'
S' -> baS' / epsilon

Replacing S in eq2:

So I'll get the solution (sol2):

S -> Aa / a
A -> abA' / bA'
A' -> abA' / epsilon

Both seem to be correct. Which is the correct answer?

Yes, both your answers are correct. Note that the language under consideration is regular, see wikipedia.

The first grammar is equivalent to this regular expression:
$$r_1 = a(ba)^* \mid (ba)^+.$$

The second grammar is equivalent to this regular expression:
$$r_2 = (ab)^+a \mid b(ab)^*a \mid a.$$

It's easy to prove those regexes generate equal languages $L(r_1) = L(r_2)$.


Regular Expression and NFA: each block of five consecutive symbols contains at least two 0's Consider the alphabet {0, 1}. How do I find the regular expression for the set of all strings such that each block of five consecutive symbols contains at least two 0's?
Here, by block I mean a given set of concurrent substrings. For example, for a string "0011010", the first five characters are "00110", which satisfies the above condition. The next block leaves out only the first character of the given string, giving me "01101", which again satisfies the condition.
I also need help in converting the regular expression into an NFA.

The states of your DFA are pairs of integers $(i,j)$ with $1 \le i \le j \le 5$, plus a $\mathrm{REJECT}$ state.
Intuitively state $(i,j)$ means that the two most recent $0$s have been encountered when $i$-th to last and $j$-th to last character were read.
The transition function $\delta$ satisfies $\delta(\mathrm{REJECT}, x)=\mathrm{REJECT}$ for $x \in \{0,1\}$ while, for any other state $(i,j)$, $\delta$ is defined as follows:
$$
\delta( (i,j), x) =
\begin{cases}
(1, i+1) & \mbox{if } x=0 \mbox{ and } i<5\\
\mathrm{REJECT} & \mbox{if } x=0 \mbox{ and } i=5\\
(i+1, j+1) & \mbox{if } x=1 \mbox{ and } j<5\\
\mathrm{REJECT} & \mbox{if } x=1 \mbox{ and }j=5.
\end{cases}
$$
The initial state is $(1,1)$. All states, except for $\mathrm{REJECT}$,  are accepting states.


A regular expression for an automaton which accepts strings with no more than 3 consecutive zeros This is the automaton I want to find the regular expression for:

As you see, states Q1 to Q4 are accepted and Q5 is a kind of trap. This automaton accepts strings that have no more than 3 consecutive zeros.
Can anybody help finding a regular expression for this?

Note : What I tried ...
I defined A:=(0+00+000)
So the automata accepts the strings which contain no consecutive A's. But I don't know how to find that kind of regular expression.

Hint: A string with no more than 3 consecutive zeroes has the general form
$$0^{p_1} 1 0^{p_2} 1 0^{p_3} 1 \ldots,$$
where $p_i \leq 3$. Try expressing that structure as a regular expression.


What are the exponential alternatives that are skipped in dynamic programming for longest increasing subsequence? I am trying to wrap my head around how dynamic programming helps avoid all possibilities that are exponential after reading Chapter 8 NP-complete problems of Algorithms by Dasgupta et al. where it says:

So far in this book we have seen the most brilliant successes of this quest, algorithmic techniques that defeat the specter of exponentiality: greedy algorithms, dynamic programming, linear programming (while divide-and-conquer typically yields faster algorithms for problems we can already solve in polynomial time).

Going back to Chapter 6 Dynamic programming, I followed along the longest increasing subsequence problem that this video also shows how to solve. It seemed to me that we were considering all other choices in the solution for the sequence $3, 4, -1, 0, 6, 2, 3$, but only did this with $n^2$ time.
What are the other possible subsequences that would reveal that this problem is exponential in nature without dynamic programming? I can see that in the 0-1 Knapsack problem there are $2^n$ possibilities to consider but can't see the exponential counterpart of the longest increasing subsequence problem.

Go over all $2^n$ subsequences. For each one, check whether it is increasing.
There are two meanings of subsequence: contiguous subsequence and arbitrary subsequence. For example, $1,3$ is a non-contiguous subsequence of $1,2,3$.
Formally, a subsequence of $a_1,\ldots,a_n$ is a sequence $a_{i_1},\ldots,a_{i_m}$ for some $1 \leq m \leq n$, where $1 \leq i_1 < \cdots < i_m \leq n$. A subsequence is contiguous if it is of the form $a_i,a_{i+1},\ldots,a_j$, that is, if it contains all elements from $a_i$ to $a_j$.
A sequence of length $n$ has $2^n-1$ subsequences, only $\binom{n+1}{2}$ of which are contiguous.
For example, here are all subsequences of $a,b,c$:
$$
a \\ b \\ c \\ a,b \\ a,c \\ b,c \\ a,b,c
$$
Of these, only $a,c$ is not contiguous.


how to identify patterns in program execution flows? Consider a library, that is used by different programs. Under certain (unknown) circumstances, an error can occur. I want to feed execution traces of faulty programs to some kind of an algorithm / framework so it learns about the "pattern" which led to the error. It should then, when fed a live trace, detect when that error will occur and halt the program execution.

So what I have is a list of totally ordered invocations of library functions with their parameters and return value. A simple fault program, where a memory area is used after being freed, may look like

mylib_allocate()=0x100
mylib_dosomething() // unrelated "noise"
mylib_free(0x100)
mylib_dosomething() // unrelated "noise"
mylib_set(0x100, 0); // error here

So my question is: Are there any existing frameworks that could be fed with that kind of data, which tries to automatically identify patterns from many traces leading to the same error (e.g. "use after free"), and which produces some output which could be used to detect the error (i.e. trigger an event if such an error is going to happen)?

I looked through some data mining approaches, but it seems like they all target "manual" analysis for pattern identification, e.g. by graphic processing to visualize potential "cluster". Then I tried to look at "process mining", but this seemed to be a dead-end as well, because - as far as I understand - my invocation data with an arbitary amount of parameters doesn't fit into that "process" schema. At least I didn't get any reasonable results with ProM.

There's probably no existing turnkey solution that will do what you want, out of the box.  I suspect this would be a research-level task, so you might want to start by searching the research literature to see if anyone else has tried to do something like this.  (Google Scholar is useful.)

If you some advice on how to pursue this yourself, my advice would be:

Try to narrow the scope.  Rather than trying to detect all bugs, pick a single class of bugs (e.g., use-after-free would be a fine choice) and see if you can have any success detecting those, as a first step.  If you're successful then you could broaden the scope.
Think now about how you'll obtain enough data to work with.  I suspect one of the biggest challenges will be how to obtain a large training set with known labels, that have many instances of in-the-wild use-after-free bugs, as well as many other traces with no instances of those type of bugs, labelled with whether there was a bug or not and which function invocations were responsible.
Take a look at association rule learning, sequential pattern mining, grammar induction and automata learning (e.g., my links here; e.g., you might try to learn a small automaton that detects use-after-free bugs), and recurrent neural networks (especially LSTM).
Also, you might need to do some feature engineering.  For instance, when you have pointers or handles (like 0x100), you might want to canonicalize them, as the only useful information is whether two calls used the same pointer or a different pointer -- the actual value of the pointer is irrelevant.  Since you have domain knowledge of that fact, by transforming the data before you feed it to the data mining / machine learning framework, you can help it learn a lot faster and more effectively.


What is the difference between SIZE(n^k) and P/poly? What is the difference between $\text{SIZE}(n^k)$ and $\text{P}/\text{poly}$?
For reference:

$\text{SIZE}(n^k)$ is defined as the class of problems solvable with Boolean circuits (of fan-in two) with $O(n^k)$ gates.

$\text{P}/\text{poly}$ is defined as those problems over $\{0,1\}^*$ which can be solved by an infinite family of polynomial-size circuits ${C_n}$.

What is the difference between these classes?

SIZE($n^2$) consists only of problems that can be solved by circuit families of size at most $O(n^2)$.  P/poly contains problems that can be solved by circuit families of size at most $O(n^3)$, and those solved by families of size at most $O(n^4)$, and so on.
In particular, P/poly = $\cup_k$ SIZE($n^k$).


Is there a name for the problem of turning a bipartite graph into two graphs? Is there a name for the problem of turning a bipartite graph into two graphs in the following way? We form one graph from the vertices on the left, such that two vertices are made adjacent if they share a common neighbour on the right; we form the other graph similarly from the vertices on the right.

This pops up, for example, when finding collaboration relationships in a bipartite graph from scientists to papers or actors to movies.

This being a common problem, I wonder if it has a common name, and maybe specific literature on it.

You're (basically) computing the square of the graph, in which two vertices are adjacent if there is a path of length 2 (or at most 2, depending on the definition) connecting them. The square will contain at least two connected components, corresponding to the two bipartitions.


Sorting array containing elements from $\{1,\ldots,k\}$ in place in $O(n\log k)$ An array $a[1,\ldots,n] \subseteq \{1,\ldots, k\}$ is given, where $k < \sqrt{n}$.
Our goal is a project algorithm which sorts it in place and in time $O(n\log k)$.
We assume that $k < \sqrt{n}$ - otherwise $O(n\log k) = O(n\log n)$ - then we may use HeapSort.

We may assume that we know $k$.  I try to do it. The only thing that I can do is finding all $k$ distinct elements and bring them on beginning of array in $O(n\log k)$  - I use binary search.

However I have no idea how to solve it. Any ideas?

Here is an idea. Use a variant of quicksort with a twist:

Find the median $m$ in-place in time $O(n)$ (this could jumble the array).
Partition the array around $m$ using the quicksort partition routine.
Divide the array into three parts: smaller than $m$, equal to $m$, and larger than $m$, and recurse on the first and the last.

Consider a recursion tree for this algorithm. The tree has depth $\log n$ and $k$ nodes. Imagine "compressing" the tree by short-circuiting all nodes having only one child. You get a tree with depth $\log k$. Can you justify this short-circuiting and prove a running time of $O(n\log k)$? Or is there a counterexample?


What is the minimum square partition of an almost-square rectangle? This question is motivated by an older question about tiling an orthogonal polygon with squares.
It is a generalisation of my former question about how to prove that the minimum square partition of a 3X2 rectangle has 3 squares).
Let:

An almost-square-rectangle be a rectangle that has a width  $w$ and height $h=w-1$.
A square partitioning be a covering by non-overlapping squares; the entire rectangle must be covered, all the squares must be disjoint.
A minimum-square-partitioning be a square partitioning, for which is no square partitioning that is made of a lesser number of squares.

Illustration:

Top row: The almost-square-rectangles of widths $3$, $4$ and $5$. Bottom row: Are these miminum-square-partitions of their corresponding rectangles?
My question is now:

What is the minimum-square-partitioning of an almost-square-rectangle?
Can we prove ${\rm M{\small IN}S{\small QUARES}}(R_{w,h=w-1})=w$?

Note a follow-up question, Minimum square partitions for 4x3 and 5x4 rectangles.

A similar question was asked on Mathoverflow. The commenters mentioned a paper of Kenyon, which shows that the minimum number of squares required to tile a $w \times (w-1)$ rectangle is $\Theta(\log w)$. See also a related paper of Walters.

You can tile a $(4t+7) \times (4t+6)$ rectangle using only $t+5$ squares (for $t \geq 0$).


Basic mapping reductions without using Turing machines I have problems with the basics of mapping reductions.

I can understand how to do reductions using a Turing machine, but without it, I get a little bit confused.

For example:

How do I do a mapping reduction from $a$ to $b$, where $a$ is $\{0,1\}$ and $b$ is $\{0\}$ over the alphabet of $\{0,1\}$?
Does every language have a reduction to itself?

The identity function is a reduction from a language to itself. One reduction from $\{0,1\}$ to $\{0,1\}$ is given by $\lfloor x/2 \rfloor$, which maps $0,1$ to $0$, and all other integers to non-zero values.


How to minimize the following DFA? Consider the DFA, M=({1, 2, 3, 4, 5, 6}, {a, b}, 1, {2, 5}, δ), whose δ is specified below.

I calculated the following and got unmarked states (5,2) and (6,3)

(6,3) looks okay but there is something wrong with (5,2).It is not deterministic so where did I go wrong?

States 2 and 5 are distinguishable. We have $(2, 5)\stackrel{b}{\longrightarrow}(1,5)$ and state 1 is a non-final state while state 5 is final. In addition, as HueHang and Amy have noted, $(6, 3)$ is also distinguishable, so the original DFA is already mimimized.


Proving that an $n$-element heap has at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes I am having trouble proving that an n-element heap can have at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes.

Please note that I am proving a loose bound.

First I proved that a complete binary tree can have at most $2^{h+1} - 1$ nodes. However, I don't know how to use this fact to inductively prove the formula above?

The only thing thus far in my inductive proof is showing the base case ($h=0$), which is trivial.

Probably, you mean this:
A heap of size $n$ has at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes with height $h$.

Proof can be found for example here:
http://www.cs.sfu.ca/CourseCentral/307/petra/2009/SLN_2.pdf


If a grammar is SLR(1) then are the LALR and SLR tables the same? I think they are because, SLR and LALR have same number of states and, since there are no conflicts in SLR table this means all the SLR information is needed and correctly used for parsing, so all that has to be in LALR.

The tables aren't the same.  The effect is not visible on correct inputs but on erroneous one.  The SLR tables may indicate that a reduce operation is in order and then detect that the input is erroneous after the reduction when the LALR one will directly indicates that the input is erroneous without doing any reduction.  That may have an influence on automatic error message generation and error recovery which are using the state of the push-down automaton to do their work.


What kind of data structure should be used for working with dynamic sets where elements follow "normal distribution" and why? I am wondering if Hash tables would be a good choice as it mentions dynamic sets to store data which follows normal distribution.
I have doubt in this because normal distribution has bell shaped curve which means elements near the median are more than others. So, If I use hash table then that would lead to clustering.
So, any insights regarding this would be helpful.
Edit: Common operations on a dynamic set are Find,Insert, Delete, and also
analysing what are the complexities for each operation.

A hash function might not map the nearby elements to the same bucket. For example suppose the hash function is $h(x) = x^2 \mod p$ where $p$ is some prime number say $97$. Suppose $x$ follows normal distribution with values between $1$ to $1000$. And, suppose that most of the values are concentrated around $500$.
If you compute the hash values at $x = 499$, $x = 500$, and $x = 501$,
the hash function gives the following values: $h(499) = 2$, $h(500) = 31$, and $h(501) = 62$. Note that, although the input values are close to each other, their mapped values are not close to each other and they lie in completely different buckets.
Designing a good hash function that uniformly maps the values across the table, mostly depends on a particular use case. But, you can always make your hash function more complex by adding more terms to it, for example, by adding more terms of the form $x^k$ to it, etc. It will hopefully provide a uniform spread of values across the table.


which error is it - a semantic error or a link error? I am having a simple doubt in C programming language.

In any simple C code snippet, if by mistake suppose i have written intmain() instead of main().

Then it represents what type of error ?

It will not be a lexical error as compiler will correctly make a token for it and it is also not a syntax error clearly.

I think it is a semantic error as in this phase compiler checks with the meaningful statements, scoping, binding, variable not declared, function not declared, any variable declared twice, etc.

But, on the other hand, I also think it as a linker error as in the semantic phase, it can throw a error that function intmain() is not declared and it is been directly used.

Can anyone make this crystal clear that what is the actual error ?

We can reproduce your error using this C++ code:

intmain() {
    return 0;
}

The following error is returned during compile time:

error: ISO C++ forbids declaration of ‘intmain’ with no type [-fpermissive]

Every function in C/C++ has to have a type. In this sense, it's a type error, which falls in the category of (static) semantic errors. On the other hand, your error is caused by a typo. This sort of error is considered a lexical error, which falls under syntax errors.

There is a lot of discussion whether certain errors are syntactical or static semantic. My opinion is this case is that the error is lexical, considering the cause.


Help with building a NFA automaton $\Sigma=\{a,b\}$, $L=\{w\in \Sigma^* \Big| |w|=3n+5m, \ n,m\ge 0 \}$.
I need to build NFA automaton for $L$....

Now, I try it for hours but I don't have any idea how to solve it.
I know that any $x\ge 8$ can be written as $3n+5m, \ n,m\ge 0 $
So, the automaton accepts any word the her length is 8 or higher, but it doesn't accepts words at length: 1,2,4,7.
One more rule: $|Q|=5$....

Can you help me please and guide me how should I solve it?
Because I don't have any idea so far...
Any automaton  that I make accepts some of the words in the forbidden length...

Thank you!

Just a hint:

If the requirement was to count the length $3n$, the NFA was simple, and could be done with 3 states. Similarly, if you only needed the $5m$ part, an easy 5-state NFA could do this.

Now think how to "combine" these two NFAs, one on top of the other. Use $\epsilon$-moves to go from the end of one, to the start of the another. Because you need $|Q|=5$, you will have to overload the meaning of 3 states so they serve both the $3n$ and the $5m$ machines.

Another hint that may be helpful: make $q_0$ accepting (and the only accepting state).

Good Luck.


A doubt regarding the acceptance of $\epsilon$ by an automaton testing divisibility of numbers As we know, $\epsilon$ is the empty string, with length 0. It is not part of any any alphabet by default, unless specifically defined so. However, it is a string over any alphabet.

For example, Given that I need to design a Deterministic or Nondeterministic finite state automaton (without $\epsilon$ transitions) that accepts decimal numbers that are say, divisible by 2, would I have to account for the empty string as an input word as well? If so, how does divisibility work for null input?

It is rather standard to assume that 0 represents zero (and is divisible by two). Also it is usually assumed that decimal numbers do not start with 0.

I once presented a finite state automaton without these assumptions, where I took  $\varepsilon$ as a representation for zero, and likewise 0000, and my students protested.


Is it decidable whether a given context free grammar generates an infinite number of strings? Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or not, we can write a program that would test this but would not halt. So it should be undecidable. Is this so?

Let $G$ be a context free grammar, and let us assume that it is in Chomsky normal form. If it's not, we'll convert it first. An important property of this normal form is that the only way to derive the empty word is with the single rule $S_0\to \epsilon$ (where $S_0$ is the initial variable, which cannot be derived from other variables).

Thus, any other derivation adds some non-trivial part to a word.

Now, let $n$ be the number of variables in the grammar, and let $k$ be the maximal length on the right-side of a derivation rule. That is, $A\to B_1\cdots B_k$ is the maximal length. We are going to show the following theorem:

  $G$ generates an infinite word iff it generates a word of length at least $k^{n+2}$.

Consider some word $w$ generated by the grammar, and a derivation tree for it. The derivation tree has branching factor of at most $k$, and thus it needs to be of height at least $\log_k |w|$ in order to derive $w$.

Take a really long word $w$. Just how long? take $w$ of length $k^{n+2}$. Then, every derivation tree of $w$ requires at least height $\log_k(k^{n+2})=n+2$. That means that there is some path in the tree of length $n+2$, and on this part there is some variable that repeats (since there are only $n$ variables). We can assume that the derivation from this variable derives other things besides itself, otherwise we can shorten the tree.

Now, you can "pump" the word $w$ to infinitely many other words that are generated, by repeating the subtree of the variable that derives itself.

If this sounds complicated, take a look at the pumping lemma, it's the same idea.

So now what? Well, take your grammar, and "remove" from it all words of length less than $k^{n+2}$ by intersecting it with a regular language of all words of length at least $k^{n+2}$, and check if the resulting grammar is non-empty. If it is, the original grammar generated an infinite language, and otherwise - a finite language.


What is a recursion for Huffman encoding? If I had to write the Huffman encoding as a recursion in terms of the cost $C_{ij}$, given weights/frequencies $W = [w_1,\ldots,w_n]$, how would I do it? (where this is creating a minimum cost tree, $C = \sum_i w_i \cdot \mathrm{depth}_i$).

I am going off of Dasgupta's Huffman procedure:

  procedure Huffman(f)

  Input: An array f[1···n] of frequencies

  Output: An encoding tree with n leaves

  let H be a priority queue of integers, ordered by f

  for i = 1 to n:   insert(H,i)

  for k = n+1 to 2n–1:

    i = deletemin(H),   j = deletemin(H)

    create a node numbered k with children i,j

    f[k] = f[i] + f[j]

    insert(H,k)

It should be something like the matrix multiplication order minimization algorithm, which seeks to minimize the total number of components calculated when multiplying a string of matrices,

$$
C_{ij} = \min(C_{ik} + C_{k+1,j}+(m_i-1) \cdot m_k \cdot m_j)
$$

Where $m_i,m_j$ are the dimensions of the matrix multiplication at the level directly below the node...

I wrote something like:

$$
aC_{ij} = \min((a+1)C_{ik} + (a+1)C_{k+1,j}),\text{ for all } i,j,k
$$

With base case: $C_{ii} = w_i$

Knowing full well that this is probably incorrect.  But I don't understand how I should write it.  I mean, I have the algorithm fine—just Huffman + DFS afterward (which always turns left, then right) to find out the order of the elements.  But I don't understand how the recursion notation works in this situation.

Huffman's algorithm uses the greedy heuristic, which is different from the dynamic programming approach in the other problem you mention. However, we can still define the cost recursively.

There are actually several options. In all cases, given a distribution $p_1,\ldots,p_n$, we will find a formula for $C(p_1,\ldots,p_n)$, which is the optimal cost of a prefix code.

Let's start with Huffman's algorithm itself:

$C(1) = 0$.
$C(p_1,\ldots,p_n) = p_i + p_j + C(p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j)$, where $p_i,p_j$ (for $i < j$) are the two smallest probabilities (i.e. $\max(p_i,p_j) \leq p_k$ for all $k \neq i,j$), and $\widehat{p_i}$ signifies that $p_i$ is removed.

The proof that this recurrence is correct is not immediate.

If we want a Huffman-like recurrence whose correctness is immediate, we need to tweak this only slightly:

$C(1) = 0$.
$C(p_1,\ldots,p_n) = \min_{i<j} [p_i + p_j + C(p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j)]$.

This recurrence holds since (i) given a code for $p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j$ we can get a code for $p_1,\ldots,p_n$ which is worse by $p_i+p_j$ by splitting the node corresponding to $p_i+p_j$ into two, and (ii) given a code for $p_1,\ldots,p_n$, if we choose any two sibling leaves $p_i,p_j$ then $C(p_1,\ldots,p_n) = p_i + p_j + C(p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j)$.

A short reflection reveals that we can always ensure $j = n$ (say), and this leads to a simpler recurrence:

$C(1) = 0$.
$C(p_1,\ldots,p_n) = \min_{i<n} [p_i + p_n + C(p_1,\ldots,\widehat{p_i},\ldots,p_{n-1},p_i+p_n)]$.

The last two recurrences are bottom-up. There is also a top-down recurrence:

$C(1) = 0$.
$C(p_1,\ldots,p_n) = 1 + \min_{S \sqcup T = [n]} [C(p_S) + C(p_T)]$, where the minimization is over all partitions of $\{1,\ldots,n\}$ into two non-empty sets, and $p_S = (p_i : i \in S)$.

In this recurrence we are splitting the root instead of merging two sibling leaves. I leave to correctness proof for the reader.

Only the first recurrence above can be implemented efficiently.


Multiplication in $O(n\cdot \log n)$ I was looking in here, and I noticed the best runtime for multiplication of two $n$-bits numbers is $O(n\cdot \log n \cdot 2^{O(\log^* n)}$, but I can easily notice an algorithm that runs in $O(n\cdot \log n)$.

After all, we know how to multiply two polynomials from degree $n$ in $O(n \log n)$ runtime. But multiplying polynomials is the same as multiplying two $n$-bits numbers. So we have an algorithm to multiply two $n$-bits numbers in $O(n \log n )$. Now the only problem that might occur is the carry, but in each phase we can fix that in $O(n)$ time, simply moving on the rightest bit and its left-neighbour, until the end. That is, our runtime shall remain $O(n \cdot \log n)$.

So did I make a new (and pretty obvious) discovery? Or is the wikipedia page out of date? Or perhaps I have some mistake?

Saying that you can multiply two polynomials of degree $n$ in time $O(n\log n)$ implies that, in particular, you can multiply degree-zero polynomials, i.e., constants, in constant time.  Clearly, therefore, the claims "multiplying $n$-bit numbers takes time $O(2^{\log^*n}n\log n)$" and "multiplying degree-$n$ polynomials takes time $O(n\log n)$" are relative to different models of computation so are not directly comparable.


General question on choosing an Assembly language based on my goal So I know assembly is so big and it seems learning assembly is like learning high level programming, you don't need to learn them all, you can learn couple and this will be enough.

The thing is with high-level language it is easier to grasp and implement in your life. But I am having hard time with assembly, I learned ARM at university, but I am not sure which version it was. And, it wasn't practical in real life. Also, it was too primitive. It doesn't even help me read other assemblies. Because when i read other assembly, I am lost seeing too many new commands that I have never seen before.

But I want to learn a language where I can add it to my code or make stand-alone version out of it easily like C++ or C# for Windows, so basically a practical language, also a language with live community and not an abandoned one.
i learned some programming languages and they are useless for me like CLIPS, ADA and Prolog.

So what are the useful and practical assembly languages out there to learn for windows. Is FAsm a good start? Also note that I do not know what I want to do with it, I will learn it them when I get good command of it I will decide, I may use it for images, or AI project or anyother use where my path will lead. I already know C++ (i use it for UE4 and AI code implementations), C# (desktop/web) app and java (desktop).

There is very, very little need for assembler. For is very rarely need for inline assembly - for example, I have some code somewhere that calculates (a * b) / c for unsigned 64 bit integers where a * b overflows.

And asking "which assembler should I learn" - if you ever need assembler, then that's the one you need to learn. Any other assembler is useless.

The only case where you really need to use assembler is at the extreme ends: When you are creating a virtual machine, you need to understand the extremely rarely used instructions to do this safely. If you create codecs, or encryption software, where you have very small amounts of code using up huge amounts of CPU time, that's where you may need assembler. But you don't need to know just assembler. You need to know and understand CPU instructions that have been created exactly for these purposes. You are in a highly specialised area there.


What graph problems are hard to solve even for a small number of verticies? The only graph problem that I worked with is TSP. It is exponentially hard, but there are tons of heuristics which allows to find near to optimum solution.

So I was wondering, is there any graph problems (or optimization problems which could be mapped onto graph) that are exponentially hard and can not be solved (even approximatly) efficiently for small and mid-sized systems? (let's say 10-20 verticies)

I recommend you look at a list of NP-complete problems on graphs.  For each one, research whether there exists a known approximation algorithm.  For some problems we have hardness of approximation results (which say that there is no polynomial-time algorithm that achieves approximation factor $\alpha$, unless $P=NP$).  Those are potential candidates that might be of interest.  In particular, I'd recommend you study the standard methods for dealing with intractability, then look for a candidate problem where none of those seem to work.  You might also look at graph problems that are APX-complete as candidates worthy of further exploration.

For instance, graph coloring might be a possible candidate to look at.  I haven't studied that problems so I don't know whether good heuristics exist.  I doubt it will be hard on graphs with only 10-20 vertices, but it might be hard with somewhat larger graphs.


Using closure properties to show that $a^n b^m a^{n+m}$ is not regular I want to show that $L = \{a^n b^m a^{n+m} \mid n, m \geq 0\}$ is not regular.

Can I say that the complement of $L$ intersected with $a^*b^*$ equals $\{a^n b^n \mid n \geq 0\}$ and since I know that $\{a^n b^n \mid n \geq 0\}$ is not regular, then $L$ is not regular?

Or would I have to use the pumping lemma?

That line of reasoning can work in principle; you are trying to use closure properties of REG for a proof of contradiction. Make sure you understand that that's what you're doing.

Unfortunately, you do not get $\{a^nb^n\}$. For instance, $a^3 b^4 \in \overline{L} \cap a^*b^*$. Check out our reference question for more techniques you can try.


Big-O: Why is the time complexity of these loops O(N)? I have the following function.

int fun(int n)
{
  int count = 0;
  for (int i = n; i > 0; i /= 2)
     for (int j = 0; j < i; j++)
        count += 1;
  return count;
}

It has O(N) time complexity. I thought it's O(N LogN)(i.e. If we remove the inner loop we get)

for (int i = n; i > 0; i /= 2){
...
}

This is O(Log N) isn't it? And the inner loop turns out to be O(N) as it just increase linearly. So I think it's supposed to be O(Log N * N). What might go wrong on my thought?

Look at how many steps the inner loop is taking. It's $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$. However the geometric series tells us:

$$\sum_{k=0}^{\lceil\log n\rceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2^k} = 2n$$


choice of data structure for domino tilings A domino tiling is a tesselation of a region in the plane by 2 × 1 squares.  What is a good data type for storing and manipulating such objects?

In my current manipulation, use an array to store all the half-squares numbering them 1-2 for a horizontal domino, 3 4 for a vertical.  It's not ideal but I can draw the tiling in ASCII or using a graphics editor.

     _ _         _ _
1 2 |_ _|  3 3  | | |
1 2 |_ _|  4 4  |_|_|

In some applications, I have to identify specific features within array.  For example, I might have to count all instances of 2 ×2 squares of dominos in my array, excluding things like

 _ _
 _|_   2 1
|_ _|  1 2

These queries are not difficult, but they make me start to question my use of arrays.

There is an alternative, more compact kind of array representation which might be better if you are working with diamonds as defined in the paper you linked (for axis aligned rectangles you need to find the smallest covering diamond).

The idea is to checkerboard the plane and assign a 2-bit number to each "black" cell, such that the number represents the orientation of the domino relative to the cell. Consider for example:

where $0$ means "horizontal domino pointing east", $1$ means "vertical domino pointing north", etc. Tilting the numbers clockwise yields the array representation:

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

To find two dominos forming a square search for a $0$ adjacent to a $2$ or a $1$ adjacent  to a $3$. Now, if you deal with big tesselations and are into implemtations sped up by bit operations, you can do this:

Let $A$ be a $\{0,1,2,3\}^{m \times n}$ matrix, $b$ be the bit mask $\dots 01010101$, then we can represent the $i^{th}$ row of $A$ as a single integer by using bit-concatenation:

$$r_i = \bigvee_{j=1}^n (a_{ij} << 2(j-1))$$

where $\vee$ denotes a bitwise OR and $<<$ a leftshift. Denoting $\oplus$ as bitwise XOR we can calculate

$$s_i=(r_i \text{ mod } 2^{2n}) \oplus (r_i >> 2) \oplus b \\
t_i=r_i \oplus r_{i+1}  \oplus b, ~~i < m$$

Then domino $a_{ij}$ and domino $a_{ij+1}$ form a square iff bits $(s_i)_{2j-2}$ and $(s_i)_{2j-1}$ are both $1$. Likewise domino $a_{ij}$ and domino $a_{i+1j}$ do so iff bits $(t_i)_{2j-2}$ and $(t_i)_{2j-1}$ are both $1$.

Example calculation for rows 1,2 (little-endian!):

r_1    00 00 00 00
r_2    10 11 11 00
b      01 01 01 01
xor    -----------
       11 10 10 01

Therefore $a_{11}$ and $a_{21}$ form a square.


Operating System: About user thread and kernel thread? Is that a "thread" consists of both "user thread" and "kernel thread" as two parts?

And when I create a "thread", is that I create a "user thread" and another "kernel thread" is created "in the background" by OS also?

I'm confused because of the second picture.

The book I'm reading is "Operating System Concepts, 9th ed., SILBERSCHATZ", and it's at page 169. Thanks a lot

As the given text says, it is not necessary that for every new user thread a new kernel thread is also created. In fact different operating systems can implement this in a different way. Some OS will map every new user thread to a new kernel thread(one to one mapping), some can have a maximum limit on number of kernel threads beyond which a kernel thread will be mapped with more than one user thread(many to one). There can also be an OS which maps a single user thread to more than one kernel thread, and vice versa. This would be a many to many model.

All these models have their own pros and cons. Which model to choose would depend upon what functionality is required from OS, available hardware resources etc.


Non-deterministic algorithm for solving figure of 8 I am struggling in trying to figure out a non-deterministic algorithm for the following problem.

Consider the following problem, called the ﬁgure-of-eight problem (FOE). An instance is an undirected graph $G = (V,E)$ with vertices $V$ and edges $E$. $G$ is a yes-instance if there is a sequence of vertices $(v_{0},v_{1},...,v_{k+1})\ (some\ k \geq 6)$ such that

• Each pair $(v_{i},v_{i+1})$ is an edge $(each\ i < k − 1)$ and $(v_{k−1},v_{0})$ is an edge.

• Every vertex in $V$ occurs at least once in the sequence.

• There is $j$ with $2 < j < k − 2$ such that $v_{0} = v_{j}$.

• No other vertex in the sequence is counted twice, i.e. if $v_{s} = v_{t} (any\ s,t < k)$ then either $s = t$ or ${s,t} = {0,j}$.

If there is no such sequence of vertices then $G$ is a no-instance of FOE.

Thanks

If you want to prove that this problem is in NP, then all you have to do is to come up with a polytime algorithm that verifies the correctness of a solution.  I.e., in polynomial time, verify that a given sequence satisfies the conditions you wrote.

This should also help you in actually construct the non-deterministic algorithm.


Difference between Image Analysis and Computer Vision I have searched the web and I have only found the differences between Image Processing and Computer Vison (also in this website too). In addition, sometimes Image Analysis is confused with Image Processing, which is untrue. Reading the Wikipedia article, it makes me thing that Image Analysis is another name for Computer Vision. Therefore I am confused. What is the real difference of those two?

Maybe the web does not have an answer, but the classical book of Image Processing by Gonzalez and Woods has. I will summarize a part from a chapter that I have read.

There is no clear boundary between the three areas of Image Processing, Image Analysis and Computer Vision. Some say that, what inputs and outputs images is Image Processing, but should the simplest task of computing the average of an image (that is a number) be excluded? Computer Vision though, is a branch of AI, that is much different from the other two fields, since it focuses on learning, making inferences and taking actions based on visual inputs. Image Analysis (a.k.a Image Understanding) is between Image Processing and Computer Vision, but with no clear boundaries. However, one could define three distinct processes based on a hierarchy level. The low-level processes consume and produce images (e.g noise reduction, contrast enhancement, image sharpening), the mid-level processes take images and output attributes (e.g edges, contours, object identities). Example tasks include image segmentation and object description and recognition. Lastly, high-level processes try to comprehend the recognized objects and at the far end, introduce cognitive functions for emulating human vision.

For more details, one can go and read the source, because luckily, that chapter is available online as a sample. The particular content lies in page 18 beginning from the third paragraph "There is no general agreement..." until the end of the next page's first paragraph "...for the methods used in this application area". I would have quote the whole content in case the website shuts down in the future, but I don't know if this is legal.


What is the difference between apprenticeship and imitation learning? There are many sub-domains of reinforcement learning, two of which are apprenticeship and imitation learning - but that appears just to be two different names for the same thing?

In general, yes, they are the same thing, which means to learn from demonstration (LfD). But, usually, apprenticeship learning is mentioned in the context of "Apprenticeship learning via inverse reinforcement learning" (IRL).
Both methods learn from demonstration, but they learn different things:

Imitation learning (a.k.a. behavioral cloning) will try to copy the teacher. This can be achieved by supervised learning alone. The AI will try to copy even irrelevant actions such as blinking or scratching, for instance, or even mistakes. You could use RL here too, but only if you have a reward function.
Apprenticeship learning via inverse reinforcement learning will try to infer the goal of the teacher. In other words, it will learn a reward function from observation, which can then be used in reinforcement learning. If it discovers that the goal is to hit a nail with a hammer, it will ignore blinks and scratches from the teacher, as they are irrelevant to the goal.


When to use recursion? When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?

The solutions to some problems are more naturally expressed using recursion.

For example, assume that you have a tree data structure with two kinds of nodes: leaves, which store an integer value; and branches, which have a left and right subtree in their fields. Assume that the leaves are ordered, so that the lowest value is in the leftmost leaf.

Suppose the task is to print out the values of the tree in order. A recursive algorithm for doing this is quite natural:

class Node { abstract void traverse(); }
class Leaf extends Node {
  int val;
  void traverse() { print(val); }
}
class Branch extends Node {
  Node left, right;
  void traverse() { left.traverse(); right.traverse(); }
}

Writing equivalent code without recursion would be much more difficult. Try it!

More generally, recursion works well for algorithms on recursive data structures like trees, or for problems that can naturally be broken into sub-problems. Check out, for instance, divide and conquer algorithms.

If you really want to see recursion in its most natural environment, then you should look at a functional programming language like Haskell. In such a language, there is no looping construct, so everything is expressed using recursion (or higher-order functions, but that's another story, one worth knowing about too).

Note also that functional programming languages perform optimized tail recursion. This means that they do not lay down a stack frame unless they do not need to --- essentially, recursion can be converted to a loop. From a practical perspective, you can write code in a natural fashion, but get the performance of iterative code. For the record, it seems that C++ compilers also optimize tail calls, so there is no additional overhead of using recursion in C++.


Parametrized reduction from 3-SAT to Independent Set to lower bound running time under ETH assumption I want to prove that, assuming Exponential Time Hypothesis is true, there is no algorithm that solves Independent Set in $2^{o(|V|+|E|)}$ time. I want to apply the following strong parameterized many-one reduction $f$ from 3-Sat to Independent set. Let $\psi$ be the input to 3-SAT with parameter $\kappa_{3-SAT} = \#variables + \# clauses$ and let $(G=(V,E),k)$ be the input for Independent Set with parameter $\kappa_{IS} = |V| + |E|$

For every clause in the input formula $\psi$, add three vertices to the Graph, corresponding the the respective literals. Add an edge between two vertices if:

a) They correspond to literals in the same clause or

b) they correspond to a variable and its inverse

Then 3-Sat has a satisfying assignment if and only if the graph defined by this reduction has an independent set of size $m$, where $m$ is the number of clauses in $\psi$. For example:

I am now wondering whether this reduction suffices to show that (assuming ETH), Independent Set cannot be solved in $2^{o(|V|+|E|)}$ time. If I understand correctly, the number of vertices $|V| = 3m$ and the number of edges $|E| \leq 3m+nm$, since for each clause, we have $3$ edges between the respective vertices and then for each variable we have at most $m$  edges between a variable and its inverse. However, this is not linear in $\kappa_{3-Sat}$ anymore.

Is my upper bound on the numer of edges wrong or do I a different reduction to show the desired result?

First, let me remark that $n=O(m)$ as in each clause only $3$ variables may appear, and that $m=O(n^3)$ without loss of generality as there can be at most $(2n)^3$ clauses up to repetition.

Your bound is not correct. Consider the case where some variable $X$ occurs positive in half the clauses and negative in the other half. This leads to roughly $\frac{m^2}{4}$ edges for $X$ alone. What is correct, however, is your suspicion that the parameter dependence is superlinear.

The reduction can be modified such that $|V|=3m+2n$ and $|E|=6m+n$. This would lead to a linear dependence of $k_{IS}$ on $k_{3-SAT}$. Consequently, with these parameterizations, independent set does not have a subexponential algorithm unless 3-SAT has.

However, there appears to be a further problem: The ETH uses a different parameterization. Namely just the number of variables, disregarding the number of clauses. I am not an expert in ETH. Possibly the sparsification lemma can help here.


Can we somehow get functoriality from purely type-theoretic reasoning? In this question, I asked about how to prove naturality from parametric polymorphism, using parametricity. The current answer to that question simply assumes that the functors in question satisfy the functoriality conditions.
Is there a "free theorem" result for functoriality? i.e. is it sometimes possible to see from the type of a "functor" that it is indeed a functor?

There are two senses in which type formation operations are 'functorial,' but neither matches functoriality on the category of types.
First, you can interpret the collection of types as a groupoid, and consider isomorphisms between types to be 'arrows.' These compose, but also always have inverses, so are in some sense undirected. However, this is also why all constructions are able to be functorial, because type formation operations have both covariant and contravariant positions, and thus may not preserve the direction of arrows.
Anyhow, functoriality here says that if you have $P : A \cong B$ then there is always $F P : F A \cong F B$, and: $$F\ \mathsf{Refl}_A = \mathsf{Refl}_{F A} \\ F (P \cdot Q) = F P \cdot F Q$$ This is essentially the direction of homotopy type theory, where these properties are internalized (and the 'dimension' is not limited to just groupoids).
The second functoriality property is already in the other answer. The "identity extension lemma" is a functoriality property where categories are relaxed to reflextive graphs (rather than tightened to groupoids). Again, type formation operations are able to be functorial because reflexive graphs do not have operations where 'direction' matters. However, this time it is because edges are not assumed to be composible.
So, the identity extension lemma says that every relation $R : A \Leftrightarrow B$ induces a relation $FR : FA \Leftrightarrow FB$ where:
$$F\ \mathsf{Refl}_A = \mathsf{Refl}_{F A}$$
And that's all there is to being a "relator" of reflexive graphs. There are also type systems that can talk about this sort of thing internally, possibly even with homotopy type theory features, like here.
Now, The first approach doesn't give you 'normal' functoriality for all type formations because not every map $f : A → B$ is an isomorphism. And of course, if we do $F A = A → A$, that's not going to extend to $(A → A) → (B → B)$ nor the other direction, without also having some map in the other direction. However, given an isomorphism, it induces $(A → A) \cong (B → B)$
In the second approach, a map $f : A → B$ induces a relation $\mathsf{gr} f : A \Leftrightarrow B$ given by $(x, f\ x)$. However, although we could compose the maps, there is no notion of composition of relations to talk about, and relate back to the composed functions. Considering the same type construction:
$$FR(m,n)\quad \Longleftrightarrow \quad R(x,y) ⇒ R(m\ x, n\ y)$$
So:
$$F(\mathsf{gr}\ f)(m,n)\quad \Longleftrightarrow\quad f \circ m = n \circ f$$
If you try to apply this to composed maps, then you know:
$$f \circ m = n \circ f \\ g \circ m = n \circ g$$
so $$f \circ g \circ m = f \circ n \circ g$$
but then there's nothing to do further.
You can read more about this angle in this paper, which tries to apply parametricity to a wider mathematical scope. A counter-question that the paper kind of motivates is: why do you care specifically about category functoriality? The original intuitive specification of "naturality" sounds very much like the intuitive specification of "parametricity," but the former was eventually formalized in terms of directed maps, rather than undirected relations. However, there is nothing inherently more legitimate about directed maps vs. relations or isomorphisms, and some things work out more appropriately for the latter than the former. Sometimes even in category theory it it necessary to shift into the 'undirected' perspective to make easier sense of something. See for instance here.
On a final note, you can have a type theory that keeps track of category theoretic functoriality of things. Here is early work, and here is something closer to homotopy type theory. The former tracks functoriality of everything explicitly, and is of course significantly more complicated for it. The latter allows functoriality to be an internally definable property, similar to the 'dimension' in homotopy type theory. But in neither would every type expression be necessarily functorial with respect to directed maps, because that would require limiting what one is able to write.


Bipartite graphs with min weights I have a full bipartite graph with node sets $A=\{a_1,a_2,\ldots,a_n\}$ and $B=\{b_1,b_2,\ldots,b_n\}$. Each node has a weight, $v_i$ for $a_i$ and $w_i$ for $b_i$. Each node $a_i$ is connected to exactly one node of $B$, say $b_j$, via an edge $e_i$, whose weight is $\min(v_i,w_j)$. Now I want to find a one-to-one mapping from $A$ to $B$, whose sum of edge weights is as small as possible.
My idea is to sort $v_i$s increasingly and $w_i$s decreasingly and then find the sum of all $\min(v_i,w_i)$ after sorting. Is it correct? Can you give a proof/disproof?
I have run computer simulations for $n=5,6,\ldots,10$ with random vertex weights and found no counterexample.

It is nice that you have checked your idea on some random samples.

To see why your idea work, let us find the simplest but non-trivial case and then take a look at it.  For simplicity and WLOG, the weight of a node will be used to denote that node. For example, if $A$ contains a node with weight $42$, that node will be referred to as node 42.
The case of $n=1$ is trivial.
Let $n=2$. If we happens to look at to $A=\{1, 2\}$ and $B=\{3,4\}$, then however we choose the mapping, the sum will be $1+2=3$. This sample is apparently not enlightening.
How about $A=\{1, 3\}$ and $B=\{2,4\}$?

If we connect 1 with 2 and 3 with 4, the sum is $\min(1,2) + \min(3,4)=1+3=4$.
If we connect 1 with 4 and 3 with 2, the sum is $\min(1,4) + \min(3,2)=1+2=3$.

So this is a non-trivial example. Now we should ask the basic question, why does the second choice produce a smaller sum?
To answer the question, we should observe how those two sums come up. Note that 1 appears in both sums. Is that coincidence? Think for a moment and you will know it is not. 1 is the minimum number of all numbers. So whatever it is connected to, it will be selected as the weight of the connection.
That means, whatever number 1 is connected to, which is 3 in this case, that number will be missing from later computations, i.e., it will be "wasted". The bigger the "waste" is, the less the remaining numbers will be and hence the less weight the remaining connection will produce, since function $\min(\cdot, \cdot)$ is decreasing with respect to both variables.  So 1 should be connected to a number as big as possible. That is why 1 is connected to 4 instead of 3 so as to produce the minimum total sum.
In the case of $n=2$, there are only two choices of the mapping. Either the smaller number in $A$ is mapped to the smaller number in $B$, dubbed "forward mapping", or to the bigger number in $B$, dubbed "reverse mapping".  To make the mapping produce smaller total weight, we should always choose the "reverse mapping", so that a large number will be wasted (or, what is the same, a smaller number will be kept to be used.)

To prove your idea is correct, we first show that for any mapping from $A$ to $B$, there is a mapping that maps $\min(A)$ to $\max(B)$ with no greater total weight. Suppose map $f$ maps $\min(A)$ to some $b_j$ and some number $a_i$ to $\max(B)$. Then we can make another map $f'$, which is the same as $f$ except for these 4 number, $f'$ maps $\min(A)$ to $\max(B)$ and $a_i$ to $b_j$. Since, as we have shown above, for four numbers $\min(A), a_i$ and $b_j$, $\max(B)$, we have
$$ \min(\min(A), \max(B)) + \min(a_i, b_j)\le \min(\min(A), b_j) + \min(a_i, \max(B)),$$
the total weight of $f'$ is not greater than that of $f$.
So we know,

the minimum total weight comes from a mappings that maps $\min(A)$ to $\max(B)$.
For all mappings that map $\min(A)$ to $\max(B)$, the minimum total weight comes from, by the same argument, a mapping that maps the minimum of the remaining numbers in $A$ (i.e. the second minimum number in $A$) to the maximum of the remaining numbers in $B$ (i.e., the second minimum number in $B$).
For all mappings that map $\min(A)$ to $\max(B)$ and the second minimum number in $A$ to the second maximum number in $B$, the minimum total weight comes from a mapping that maps the third minimum number in $A$ to the third maximum number in $B$.
And so on, until the last minimum number in $A$ is mapped to the last maximum number in $B$, i.e., the maximum number in $A$ is mapped to the minimum number in $B$.  $\checkmark$

An even more formal proof could be given. However, the above reasoning might be easier to understand. It should, I believe, convince an ordinary human.

Here is another straightforward way to prove your idea.
First assume all numbers are distinct. Let us prove by reductio ad absurdum. Suppose the minimum total weight can be reached by a mapping $g$ other than the mapping described in your idea. Then $g$ must contain a sub-mapping that is a "forward mapping", i.e., there must be two numbers $\alpha_1\lt \alpha_2$ in $A$ and two numbers $\beta_1\lt \beta_2$ in $B$ such that $g(\alpha_1)=\beta_1$ and $g(\alpha_2)=\beta_2$.
Now we can make another mapping $g'$ which is the same as $g$ everywhere else except that the sub-mapping of $g'$ on $\alpha_1$ and $\alpha_2$ is a "reverse mapping", i.e., $g'(\alpha_1)=\beta_2$ and $g'(\alpha_2)=\beta_1$. Now we can, as before, verify that the total weight of $g'$ is smaller than that of $g$, which contradicts our assumption.
If all numbers are not distinct, we will use the technique of approaching by limit. Perturb all numbers slightly so that they become distinct. Now all weights will be slightly off their original weights. That means the total weight obtained from your idea should not be far from the optimal solution. Let the perturbation go to zero, we see that it is, in fact, the optimal solution.

You might be interested in a similar problem, how to prove the greedy algorithm that minimize the maximum sum of a pairing.


Help in understanding how to apply nonlinear function in hashing Can somebody help in brainstorming how to apply the map as a hashing function?
I am aware that chaos is used in cryptography but I fail to understand how to apply it. Most popular hashing techniques is the modulo hash function Why is it best to use a prime number as a mod in a hashing function?
A modulo chaotic function that comes to my mind  is the Dyadic map $\theta = 2 \theta mod 1$.
  Not getting into the details of collision resolution and other technicalities, it shall be of immense help if the application of chaos map is shown in generating hash codes.
Chaos based cryptography link to paper shows that the equation on page
3 $S^t = (u^t + 2S^{t-1} + t) mod 256$ is the hashing function for cryptography. $t$ are the number of sub-blocks of the message (plaintext) and $u_0$ is the decimal value of the first block of the message.  Please help! Thank you

Cryptographers have studied various schemes for using chaos theory to try to construct cryptographic primitives (hash functions, encryption algorithms, etc.).  None of them have been successful.  Chaos simply does not seem useful for designing cryptographic algorithms.

First, many of the chaos-based schemes have been broken.  They didn't have as much nonlinearity as the designers anticiapted.

Second, the chaos-based schemes are slower than the state of the art.  You need to iterate many times to get reasonable mixing/nonlinearity.  By the time you do that, you end up with something quite slow.  In comparison, we know of alternative schemes for hashing and encryption that are very fast and appear to be very secure.  So, chaos-based schemes are simply not competitive.

In my opinion, chaotic maps do not appear to be a promising angle for hashing or other cryptographic algorithms.


Proving that a language does not belong to a language class by using more specific instances of that language You have a description of a language that you have to prove is regular, context free, or other. In order to prove that it does not belong to a certain class of languages, you might think that it will be more convenient to prove it by using a subset of that language. The problem is that a subset of a language does not necessarily belong to the same language class as the superset language. For example: with $\Sigma = \{0,1\}$, $\Sigma^*$ is a regular language, while $ A = \{ 0^n1^n \mid n \geq 0\} \subseteq \Sigma^* $ is a context free language.
(I have fallen in the trap of trying to use subsets of languages in order to try to prove that they belong to a certain class of languages.)
An example:

Let $\Sigma = \{0,1\} $ and $L = \{ w \in \Sigma^* \mid \text{w contains less 1's than 0's} \}$
Is $L$ regular, context free, or neither?

My intuition says that it is not regular, since finite state machines can't count. I think it is context free.
The strategy I'm thinking of is to show that this language is context free:

$ L_2 = \{ 0^n1^m \mid n \gt m\}$

This language is clearly a proper subset of $L$. But, like we've seen, that may not be a very useful fact if we want to prove things about the proper superset (to my understanding). It seems that $L_2$ is easier to generate than $L$: it seems easier to count how many consecutive 0's there are rather than counting the number of 0's in a string. (Especially if you consider using a PDA to count it, since then it just boils down to pushing consecutive 0's and then popping when you start seeing 1's, accepting the language if there are 0's left on the stack when you have consumed the word.) Consequently, if this intuition of hardness is correct, then $L$ is at least not regular. But then another problem reveals itself; maybe $L$ is not context free? So then you have at least shown it to not be regular, but you still have to show that it is context free or not.
This is not the only problem for which I want to use this strategy. For example:

$L_p = \{ w \in \Sigma^* \mid \text{the number of 0's in w is prime}\}$

Here I think it might be more convenient to use something like the Pumping Lemma on this language:

$L_{p2} = \{ 0^n \mid \text{n is prime}\}$

Is this kind of strategy valid?

Yes. The formal way to name this trick is the use of closure properties. In your specific case the families (regular, context-free) are closed inder intersection with a regular language: if $K$ is regular (context-free) then so is $K\cap R$, where $R$ is regular.

In your examples $L_2 = L \cap 0^*1^*$ and $L_{p2} = L_p \cap 0^*$.

So, if $L_{p2}$ isn't context-free then neither is $L_p$. Also if $L_2$ isn't regular then neither is $L$.

Regarding the first part of you question this will not help: $L_2$ may be context-free while $L$ isn't. (Not is this example, where they both are context-free: use pushing and popping but in a more general way, think how to represent negative numbers.) On the other hand, when you are not able to solve the general case, it might be helpful to develop intuition on the special cases.


What would happen in the variant of the Josephus problem in which people in odd-numbered positions are killed in each round? What would happen in the variant of the Josephus problem in which people in odd-numbered positions are killed in each round?
For example, with $N=10$ people:
$$
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \to 2, 4, 6, 8, 10 \to 4 ,8 \to 8.
$$
As you can see in the above example the killing starts from position $1$.
I was just curious to find out what would be the solution to this variant. I tried out different values of $n$ but could not find a proper algorithm.

Position $2^{\lfloor \log_2 N \rfloor}$ is always safe since it is the position that maximizes the number of trailing zeros in its binary representation.
Claim: The person originally sitting in position $n$ is killed in the $i$-th round iff the binary representation of $n$ has exactly $i-1$ trailing zeroes.
Proof: By strong induction on $i$. If $i=1$ the claim is trivially true since $n$ has $0$ trailing zeroes iff $n$ is odd.
If $i > 1$, by induction hypothesis we have that all remaining people were originally sitting in positions whose binary representation has $i$ or more trailing zeros, i.e, those positions are exactly the integers in $S = \{1, \dots, N\}$ that are multiples of $2^i$.
If $n=2^i k$ then there are exactly $k$ positions in $S$ smaller than or equal to $n$, i.e., $n$ is killed iff $k$ is odd.


Does virtual address space resides in virtual memory? I have several confusion like :

Does virtual address space resides in virtual memory ?
Does each process has its own virtual address space like each process has its own virtual memory and own page table ?
Mapping to physical address takes place from virtual memory or virtual address space if they are different thing ?

A virtual address space maps (addresses) in virtual memory. Typically one uses "virtual memory" when discussing the general concept and "virtual address space" for the concrete instance of a virtual memory.

(Virtual memory may be either relatively fast but expensive physical memory/primary storage [with a simple translation of virtual address to physical address and typically byte-granularity of access] or relatively slow but less expensive secondary storage [which typically involves software "translation", I/O processing, and page-granular access].)

In commonly used OSes, each process (but not necessarily each thread) is given a separate virtual address space, giving each process the illusion that it owns the entire machine's (virtual) memory capacity as if it was running on the computer by itself. Such OSes typically reserve a portion of the virtual address space (usually half) for OS use, in a sense providing the OS with its own address space. (Some earlier ISAs, e.g., Clipper and m88k, provided a separate address space for the OS.) This dedicated OS address range can typically share page tables across multiple processes (and TLB entries by using a global indicator bit). (For x86's hierarchical page tables, the top node cannot be shared since [ordinarily] half of its entries are process-specific. ARM uses separate global and per-process/ASID page table base pointers with indication of how much of the total address range is global.)

(One could consider Address Space IDentifiers as extensions of the virtual address. Segments in Power and Regions in Itanium provide address space extension similar to ASIDs, but apply separate extensions to large sections of the initial untranslated address [e.g., Power uses 256 MiB segments and Itanium provides 8 regions within the 64-bit initial address]. Power actually calls the address types effective [the address computed by the memory access instruction], virtual [the address after the segment translation], and real [i.e., physical].)

On the other hand, a Single Address Space OS shares the entire virtual address space among multiple processes (protection domains). This allows conceptually simple and potentially low overhead communication among processes very much like memory communication among threads within a single process in a more conventional OS. Obviously, in a SASOS a process is not free to use whatever memory address it wants for whatever purpose it wishes; the OS must prevent different processes from using the same address for different storage. This breaks the illusion that the process "owns" the entire machine.

Every virtual address with a valid page table entry maps to a physical address. If the page table entry is invalid, the address does not map directly to a physical address (it may be in secondary storage [e.g., disk] or may not yet be allocated by the process).

(Even the above has simplifications and missing concepts.)


Finite / Infinite Languages True/False and why? Just doing some work on Finite and infinite languages. And came across some statements I know the answer to but not sure how to explain why.

There are finitely many finite languages.
-This is false right? Since there are technically infinitely many finite languages
Union of any two languages over alphabet (1,0) is regular.
-False right? Since you can take a (non-reg U non-reg = non-reg)
Single state NFA can recognize only finite languages
-False, but I have no idea how to explain why...

False. There are infinitely many finite language. Just think of {0,1}*. This is a infinite set of finitely long strings. or say, it is union of infinite number of finite languages over {0,1} which have strings of finite length.
False. Union of two non regular languages MAY BE regular but it not the case always. This answer explains it well.
False. Lets have a single state NFA having state q0. let 'd' be the transition function. d(q0, a) = q0 and since this is single state NFA, q0 is also final state.
This NFA will accept all strings having only 'a'. i.e. {a,aa,aaa,aaaa...} The cardinality of this set is infinite, hence it can accept infinite languages too.


Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete? I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to the other one.

I know that each graph can be mapped to a graph with only two outgoing edges for each node, but i can't find a way to convert from many edges to two edges that allows me to perform the reduction. If I convert a node with 3 edges to something like

A----B-OUT1
|    |
OUT3 OUT2

Then the mimimun edge set will contain AB instead of B-OUT2 and B-OUT1, provided that OUT1 and OUT2 are generating a cycle, since by cutting AB it will save a point in the objective function.

Is this reduction possible?

The reduction is possible.

I'll give a reduction of minimum feedback arc set to minimum feedback arc set with maximum outdegree two. The basic idea is that if node $i$ has outdegree $d_{i}$, we make $d_{i}$ copies of node $i$. We add new nodes representing edges so that edges can still be cut in one operation.

Say the graph we want to solve minimum feedback arc set in is (V, E). We'll build a graph (V', E') such that (V', E') has a feedback arc set of size k or less if and only if (V, E) has a feedback arc set of size k or less, and the maximum outdegree of any node in (V', E') is two.

Let $d_{i}$ be the outdegree of node $v_{i}$ in $(V, E)$. Corresponding to node $v_{i}$ in $V$ we'll have nodes $v'_{i, 1} \dots v'_{i, d_{i}}$ in $V'$. For every node $v'_{i, j}$ we'll also have $d_{i}$ nodes $x'_{i, j, 1}, \dots, x'_{i, j, d_{i}}$.

Corresponding to edge $e_{i} = (s_{i}, t_{i})$ from node indexed $s_{i}$ to the one indexed $t_{i}$ in $E$, we'll have the node $e'_{i}$ and nodes $y'_{i, 1}, \dots, y'_{i, d_{t_{i}}}$ in $V'$.

For all vertices $v_{i} \in V$, let $id_{i, k}$ be the index of the $k$th edge leaving node $i$. In $E'$, for every $1 \leq j \leq d_{i}$ we'll have the edge $(v'_{i, j}, x'_{i, j, 1})$ and further for $1 \leq k < d_{i}$ the edge $(x'_{i, j, k}, x'_{i, j, k+1})$ and for $1 \leq k \leq d_{i}$ the edge $(x'_{i, j, k}, e_{id_{i, k}})$.

For all edges $e_{i} = (s_{i}, t_{i})$ in $E$, we have the edges $(e'_{i}, y'_{i, 1})$, for $1 \leq j < d_{t_{i}}$ the edge $(y'_{i, j}, y'_{i, j+1})$, and for $1 \leq j \leq d_{t_{i}}$ the edges $(y'_{i, j}, v'_{t_{i}, j})$.

By the way we defined the nodes, clearly every node has outdegree at most two.

I'll embed an image of an example of the reduction at the bottom of the proof.

Now we'll prove the main claim.

Clearly if $(V, E)$ has a feedback arc set of size $k$, so does $(V', E')$ (cut edge $(e'_{i}, y_{i, 1})$ for every edge $e_{i})$ cut in the original graph).

For the other direction, Take any feedback arc set of size $k'$ in $(V', E')$. We'll build a feedback arc set of cost $k \leq k'$ for $(V, E)$, by cutting edge $e_{i}$ if and only if one or both of the following hold:

One of the edges corresponding to $e_{i}$ in $E'$ is cut in $(V', E')$
For all of $v'_{s_{i}, 1}, \dots, v'_{s_{i}, d_{s_{i}}}$, at least one edge corresponding to them has been cut.

Note that the second case only happens if we make at least $d_{s_{i}}$ cuts in the copies corresponding to node $v_{s_{i}}$, so $k \leq k'$. Now assume that with these cuts $(V, E)$ has a directed cycle $v_{p_{1}}, \dots, v_{p_{m}}$. Then for the copies corresponding to $v_{p_{j}}$, at least one, say $v'_{p_{j}, h_{j}, 1}$ has has none of its or its $x'$s edges touched, otherwise by condition 2 for cutting an edge we would have no edges leaving $v_{p_{j}}$ in our solution in $(V, E)$.

But then $(V', E')$ also has a directed cycle: the cycle goes through $v'_{p_{j}, h_{j}}$ to $x'_{p_{j}, h_{j}, 1}$ to $\dots$ to $x'_{p_{j}, h_{j}, out_{p_{j}, p_{j+1}}}$ (where $out_{a, b}$ is the index in the edges out of $a$ of the edge to $b$) to $e'_{edi_{p_{j}, p_{j+1}}}$ (where $edi_{a, b}$ is the index of the edge from $a$ to $b$) to $y_{edi_{p_{j}, p_{j+1}}, 1}$ to $\dots$ to $y_{edi_{p_{j}, p_{j+1}}, h_{j+1}}$ to $v'_{p_{j+1}, h_{j+1}}$.

Since a contradiction followed, we must have that the cuts in $(V, E)$ form a feedback arc set, completing the proof.

Here's an image of the reduction graph for $V = \{1, 2, 3, 4, 5\}$, $E = \{(1, 2), (1, 3), (2, 4), (2, 5), (4, 1), (3, 1)\}$. Sorry for the massive size. The rectangles at the top-right show the graph $(V, E)$.


Finding longest chain in poset in subquadratic time Let $(A,\leq)$ be some finite poset. For $a,a' \in A$ we can determine in constant time whether or not $a \leq a'$. The height of an $A$ is by definition the greatest $n$ such that there are elements
$$
a_0 < a_1 < \cdots < a_n
$$
of $A$. By treating $(A,\leq)$ as a directed acyclic graph, we can determine the height of $A$ as the length of the longest path in this graph, which we can compute in linear time in the size of the graph; that is, in $\mathcal O(|A|^2)$.

Can we do any better for this special case where $A$ is a poset?

Edit: if it matters, I am especially interested in the case where the length of the longest path is already known to be significantly shorter than the size of $A$.

Well, start by observing that

when A has no comparable pairs, the height will be 0
and
when A has one or two comparable pairs, the height will be 1

.
Thus, when  $\leq$  is given with one bit for each ordered-pair of distinct elements,

even promised-to-be-at-most-1 height will have

co-nondeterministic query complexity  $(|\hspace{.02 in}A|\hspace{-0.03 in}\cdot \hspace{-0.03 in}(|\hspace{.02 in}A|\hspace{-0.04 in}-\hspace{-0.05 in}1))\hspace{.02 in}/\hspace{.02 in}2$

and probabilistic query complexity  $\Theta$$\left(\hspace{-0.02 in}|\hspace{.02 in}A|^2\right)$ .

Accordingly, we can only hope for better when  $\leq$  is given in some other way,

like as a list of the pairs for which it's true or as

an $A$-indexed array of ordered-pairs of lists, such that for each element $a$ of $A$,

$a$'s left list is the $a'$ such that  $a' < a$  and $a$'s right list is the $a'$ such that  $a < a'$

.
(I currently have no clue regarding the complexity for such representations of  $\leq$ .)

For your case of interest:

See this question and its answer.

(That answer's universe size is your n and that answer's n is your  $|\hspace{.04 in}A|$ .)

However, that negative result does not necessarily apply to

"the case where the length of the longest path is already known to be" short.


How are two layer feed-forward neural networks universal? Across my studies I have noticed the following statement in my Subject Guide; namely, that two-layer feed-forward neural networks using the sigmoidal activation function are universal. My question is how are the networks 'universal' and what does 'universal' actually mean in this instance?

Thanks in advance.

I think they are talking about the universal approximation theorem which states that given a continuous function $f$ over an n-dimensional input vector $\vec{x}$, then a neural network with a single hidden layer can approximate $f(\vec{x})$ arbitrarily closely.


Is log n! = Θ(n log n)? Why is $\log(n!)=\Theta(n\log n)$?

I tried:
$\log(n!) = \log1 + \dots + \log n \leq n \log n \Rightarrow \log(n!) = O(n \log n)$.

But how can we prove $\log(n!) = \Omega(n \log n)$ without Sterling's approximation?

$$\begin{align*}
\log n! &=\sum_{i=1}^n\log i \\
                   &\geq \sum_{i=\lceil n/2\rceil}^n \log i \\
                   &\geq \sum_{i=\lceil n/2\rceil}^n \log \tfrac{n}{2} \\
                   &\geq \tfrac{n}{2}\log \tfrac{n}{2} \\
                   &= \tfrac{n}{2}\big(\log n - \log 2)\\
                   &= \Omega(n\log n)\,.
\end{align*}$$


Are genetic algorithms an effective way to train neural networks? It seems to me that genetic algorithms would be an ideal way to train neural networks so that they come to have the right weights, since they are especially good at escaping local minima, and converging on a global optimum. However, from my rudimentary knowledge of neural nets so far, I haven't come across this method in any tutorial video. Are there inherent challenges that make GA's unsuitable for this purpose? Or is there a better way to accomplish the same thing?

There have been hundreds of papers published over the years on training neural networks with GAs. Here's a starting point Neuroevolution.

The basic problem though is that stochastic gradient descent works really well in vastly less computation time.


Example of inductive sets that are neither least nor greatest fixed point Do there exist a set of inductive rules and a fixed point of these rules but is neither the least nor the greatest fixed points?

Here's a non-trivial example:

Suppose we want to define inductively a subset of reals, so we work on the complete lattice $\mathcal{P}(\mathbb{R})$ ordered by inclusion.

Then, consider the rules
$$
\dfrac{\qquad}{0} \qquad \dfrac{x}{x+1}
$$
This induces the (monotonic, Scott-continuous) function $f : \mathcal{P}(\mathbb{R}) \to \mathcal{P}(\mathbb{R})$ given by
$$
f(X) = \{0\} \cup \{ x+1 \ |\ x\in X\}
$$

All of the following are fixed points of $f$:

$\mathbb{N}$ (least)
$\mathbb{Z}$
$\{x/2 \ |\ x\in \mathbb{Z}\}$
$\{x/3 \ |\ x\in \mathbb{Z}\}$
etc.
for any natural $k \geq 1$, the set $\{x/k \ |\ x\in \mathbb{Z} \}$
$\mathbb{Q}$
$\mathbb{R}$ (greatest)

If we want our definition to be well-formed, beyond specifying the rules, we need to single out one the fixed points. This is typically done by taking the least (induction) or the greatest (coinduction).


Can we check in polynomial time if the language of a DFA is closed against Kleene star? I was wondering if there is a polynomial time algorithm to test whether a DFA recognizes a star closed language ( which is if $A=A^*$). I think that yes, but I do not have an idea to do it.

Assuming your DFA $A = (Q,q_0,F,\delta)$ is minimal, here is one approach:

$L(A) = L(A)^*$ iff $q_0$ is accepting, and adding $\epsilon$-transitions from each accepting state $q$ to $q_0$ does not change the language; the latter is true iff $L(A)\subseteq L(A_q)$ for each $q\in F$, where $A_q = (Q,q,F,\delta)$.

In order to check whether this holds, you can compute the product $A\times A$ and check whether the subset $F\times(Q\setminus F)$ is unreachable from $\{q_0\}\times F$, which you can do in polynomial time. In some more detail:

The product automaton has the form $A\times A = (Q\times Q, (q_0,q_0), F\times F, \delta')$, where

the set of states $Q\times Q$ consists of all pairs $(q_1,q_2)$ with $q_1,q_2\in Q$;
the initial state is the pair $(q_0,q_0)$ (though we won't be needing it for our purposes);
the accepting states are all pairs $(q_1,q_2)$ where both $q_1,q_2$ are accepting in $A$;
the transition function $\delta'$ applies the original transition function to both components of a pair, i.e. $\delta'((q_1,q_2),a) = (\delta(q_1,a),\delta(q_2,a))$.

In order to check whether $L(A)\subseteq L(A_q)$ for some $q\in F$, we start from the pair $(q_0,q)$; there should be no word $w$ such that $\delta(q_0,w)\in F$ and $\delta(q,w)\notin F$, which is equivalent to the set $F\times(Q\setminus F)$ being unreachable from $(q_0,q)$ in $A\times A$.

For example, consider the language given by the regular expression $(a + ab + ba)^*$ mentioned earlier by J-E. Pin. It is accepted by the automaton $A=(Q,q_0,F,\delta)$, where

$Q=\{q_0,q_1,q_2,q_3\}$,
$F=\{q_0,q_1\}$,
$\delta = \{(q_0,a,q_1),(q_1,a,q_1),(q_2,a,q_0),(q_3,a,q_3),(q_0,b,q_2),(q_1,b,q_0),(q_2,b,q_3),(q_3,b,q_3)\}$.

The only pair we have to check is $(q_0,q_1)$; exploring the states we can reach from it, we get:

$\delta'((q_0,q_1),a) = (q_1,q_1)$ - note that both components are the same; since $A$ is deterministic, this will be also be the case for all states reachable from here, in particular we will never reach any $(q,r)$ with $q\in F$ and $r\notin F$. We therefore don't need to explore this branch any further.
$\delta'((q_0,q_1),b) = (q_2,q_0)$. Fine because $q_2\notin F$.
$\delta'((q_2,q_0),a) = (q_0,q_1)$. Back to where we started.
$\delta'((q_2,q_0),b) = (q_3,q_2)$. Not only is $q_3\notin F$, but it is a trap state, i.e. all states we can reach from here are of the form $(q_3,q)$ and therefore not in $F\times(Q\setminus F)$.

Since we cannot reach $F\times (Q\setminus F)$ from $(q_0,q_1)$, we now know $L(A)\subseteq L(A_q)$ and therefore $L(A) = L(A)^*$.


Conditions for an Language to be infinite given 'r' , a regular expression that does not include λ or ∅, What are the Conditions of 'r' so that L(r) would be infinite?

Regular expressions correspond to a simple recursive definition, which starts with the symbols from some alphabet and extends them with applications of three operators: alternation, concatenation and Kleene closure.
So ask yourself: Which of these operators can produce an infinite set?

Formal definition:
Let $\Sigma$ be a finite set of symbols. Then the set of regular expressions $R_\Sigma$ is the smallest set of expressions which can be constructed using these rules:

Every $c \in \Sigma$ is in $R_\Sigma$.

$\lambda$ and $\emptyset$ are in $R_\Sigma$.

If $r$ and $s$ are regular expressions over the alphabet $\Sigma$ then so are:

$(r+s)$
$(rs)$
$(r^*)$

A standard proof technique for properties of regular expressions is to apply mathematical induction to this definition.


How to check if $m$ numbers in a sequence satisfy a condition, such that all these numbers are spaced apart by at least $k$? Suppose we have a sequence $s$ with $n$ elements from $s[1..n]$. I want to check if there exists $m \leq n$ elements in this sequence that each satisfy some simple condition (that can be tested in $O(1)$ for each $s[i]$), such that all of these elements are spaced apart by at least $k$. Is there an algorithm that can achieve this in $O(n)$ time?

For example, suppose we have $s=[3, 4, 13, 2, 6, 4, 1, 9, 11, 5]$ and we are trying to verify if there exists $m=3$ elements that satisfy the condition $s[i] \leq 4$ and are spaced apart by at least $k=2$. This is true because $s[1] = 3, s[4] = 2, s[7] = 1$ and $s[1], s[4], s[7]$ are spaced apart by at least $2$.

A naive solution that I thought of involved iterating through the sequence and recording each $s[i]$ that satisfies the condition, and then for each $s[i]$, trying to find $m-1$ others that don't violate the spacing requirement. I'm not sure how I can do this in $O(n)$ time. Is it possible?

As Yuval Filmus said in the comment, you can solve the optimization version (finding maximum viable $m$, which is a stronger version) by dynamic programming.

Let $m_i$ be the maximum viable elements of the sub-problem on $s[1..i]$. Consider the sub-problem on $s[1..i]$. An optimal solution has two choices.

It excludes $s[i]$, then it must choose an optimal solution of the sub-problem on $s[1..(i-1)]$.
It includes $s[i]$, then it cannot include $s[i-1],\ldots,s[i-k+1]$, and must choose an optimal solution of the sub-problem on $s[1..(i-k)]$.

Now you can write a recursion formula for $m_i$, and compute $m_1,\ldots,m_n$ in order in $O(n)$ time.


how do you prove that SAT is NP-complete? As it is, how do you prove that SAT is NP-complete?

I know what it means by NP-complete, so I do not need an explanation on that.

What I want to know is how do you know that one problem, such as SAT, is NP-complete without resorting to reduction to other problems such as hamiltonian problem or whatever.

I believe 3-SAT was originally reduced from the more general SATISFIABILITY in Karp's paper that outlined 21 NP-complete problems.

Wikipedia has a description of how to show that SATISFIABILITY is NP-complete, a result that's known as the Cook-Levin theorem. The idea of this proof is to show that any polynomial time nondeterministic Turing machine can be modeled as a boolean expression with polynomial size. The boolean expression has terms to represent the valid configuration space of the Turing machine: where the tape head is, what the current state is, what symbols are written on the tape, and what transitions are valid at every position. Because the NTM will halt in polynomial time, the configuration space is bounded and we can make a (large) polynomial expression to represent it.


Bellman-Ford and zero-distance cycle Problem statement: Given a graph G(V,E) which is not acyclic and may have negative edge weights (and thus may possibly have negative-length cycles), how does one detect if the graph has a zero-length cycle, and no negative-length cycles?

Background information: The question came up when I tried to implement in code the solution to what is called the "tramp steamer" problem: Given a graph G(V,E) in which each node is associated with a cost $c_i$ and each edge is associated with a time (number of days) $t_i$, find the cycle with the smallest ratio of cost to time $\frac{\sum_i(c_i)}{\sum_i(t_i)}$ (i.e. minimal cost/day cycle).

One solution is to do a binary search with the range of possible rations, trying to identify the minimum cost-to-time ratio $\mu$. In each iteration of the binary search in the range $[left...right]$, you "guess" a value of $\mu = \frac{left+right}{2}$ and then run Bellman-Ford:

if a negative cycle exists then the value of $\mu$ is too high; the range is reset to $[left...\mu]$
if all cycles are positive then the value of $\mu$ is too low; the range is reset to $[\mu...right]$
if there is a zero-length cycle (with all other cycles being positive), then we have found the best value for $\mu$ and we can stop, returning the zero-length cycle as the answer

How exactly is the third case detected? Assume the graph A->B->C->D->{A,B}  with two cycles (fro D back to A or B) where the cycle B->C->D->B is the optimal one and yields zero length for some selection of $\mu$ for which the other cycle is positive. Suppose we happen to try this particular value of $\mu$ (let's assume it's during the very first iteration because we got lucky). If I am using vertex A as the fixed point from which I run Bellman-Ford on each iteration, it will complete successfully without detecting a negative cycle. But how would the zero-length cycle be identified?

Currently I only handle the first 2 cases and my implementation keeps iterating until the $[left...right]$ range becomes becomes too small, so that floating point precision can't handle a smaller range. At that point I detect that $\frac{left+right}{2}$ is equal to one of the range limits (either left or right) and stop the binary search. How would I go about detecting that a particular value of $\mu$ has produced a zero-length cycle?

Here's how you can detect whether a weighted graph $G$ contains a zero-length cycle, assuming it does not contain any negative cycle.

Run Bellman-Ford on it to compute the distance $d(v)$ from the source to $v$, for each vertex $v$.
Color each edge $(v,w)$ red if $d(v) + \text{wt}(v,w) = d(w)$.
Form a new unweighted, directed graph $G'$ containing just the red edges from $G$.  Check whether $G'$ has any cycles, using a standard algorithm (e.g., depth-first search).  This can be done in linear time.

I'll leave it to you as an exercise to prove that the original graph $G$ contains a zero-length cycle if and only if the new graph $G'$ has a cycle.


Is O(|A| + |B|) the size of the union of two synchronized DFAs A and B? In general, the size of the DFA resulting from the union of two DFAs A and B is O(|A|.|B|) in the worst case (usually the product construction is used to compute the union).

Let's consider the class of 'synchronized DFAs' as the class of DFAs having a synchronizing word : https://en.wikipedia.org/wiki/Synchronizing_word

After looking at some examples of synchronized DFAs A and B, it seems possible to always build a synchronized DFA for the UNION of A and B with a size O(|A| + |B|) in the worst case.

Does anybody have any information, proof or paper about the union of two synchronized DFAs in O(|A| + |B|) ?

Many thanks,
Luz

Your conjecture is wrong. Consider the following languages:

$L_1$ is the language of words over $\{a,b,c\}$ such that the number of $b$s after the last $a$ is a multiple of $x$.
$L_2$ is the language of words over $\{a,b,c\}$ such that the number of $c$s after the last $a$ is a multiple of $y$.

The minimal DFA of $L_1$ contains $x$ states, and that of $L_2$ contains $y$ states. Both DFAs have $a$ as a synchronizing word. The minimal DFA for $L_1\cup L_2$ contains $xy$ states (and also has $a$ as a synchronizing word).


Functional dependencies , minimizing SUU->V Can SUU->V or any functional dependency that contains two or more times each attribute be simplified to the same dependency with one attribute? So SUU->V becomes SU->V or STTT->Q becomes ST->Q ?

Yes, each side of a Functional Dependency is a set of attributes, not a multiset, so SUU -> V can be simplified to SU -> V.

If you think about the definition of Functional Dependency you will understand why this is true.


Karp hardness of a clique with given number of outer-incident edges A clique in an undirected graph $G(V,E)$ is a subset of vertices $\mathcal{C}\subseteq V$ every pair of which is adjacent $u,v\in \mathcal{C}\implies uv\in E(G)$.

Given a clique $\mathcal{C}\subseteq V(G)$ in a graph $G$, an outer-incident edge of $\mathcal{C}$ is an edge $uv\in E$ with $u\in \mathcal{C}$ and $v\not\in\mathcal{C}$. In other word, an outer-incident edge is an edge connecting one vertex in the clique with one other outside of the clique.

Our problem $\mathrm{CLIQUE}$-$\mathrm{OUTWARD}$-$\mathrm{EDGES}$ is formally defined as:

  Input: An undirected graph $G(V,E)$ and a natural number $k$

  Output: YES if $G$ has a clique $\mathcal{C}\subseteq V$ such that $\mathcal{C}$ has exactly $k$ outer-incident edges, otherwise
  NO

The question is what the complexity of $\mathrm{CLIQUE}$-$\mathrm{OUTWARD}$-$\mathrm{EDGES}$ is.

Our problem is $NP$-complete by a reduction from Exact Cover by $3$-sets ($\mathrm{X3C}$).

Given an $X3C$ instance with the universe set $U=\{e_1,e_2,\cdots,e_n\}$ and collection of $3$-sets $\mathcal{C}=\{s_1,s_2,\cdots,s_m\}$, we create an undirected graph $G$ as follows.

For each element $e_i$, create a vertex (which will be referred to by the same name).

For each $3$-set $s_j$, create a vertex (which will also be referred to by the same name).

Connect $e_i$ and $s_j$ whenever $e_i\in s_j$.

Connect $s_{j_1}$ and $s_{j_2}$ whenever they are disjoint.

Pick some large enough $M$, connect each set-vertex to dummy vertices to make sure that every set-vertex is of degree $M$.

Call the obtained graph $G$. Now, set $k=n+(M-3-\frac{n}3+1)*\frac{n}3$. The reduction then outputs an instance, namely $(G,k)$.

Suppose there exists an exact cover for the $X3C$ instance, we can easily form a solution to our problem by taking all the set-vertices of the exact cover. Clearly, this is a clique since every pair of $3$-sets in an exact cover needs to be disjoint. It has exactly $k$ outer-incident edges.

Conversely, if there exists a clique with $k$ outer-incident edges then every vertex of this clique needs to be set-vertex. Indeed, if there is any element-vertex in the clique, then the size of the clique is equal to the number of $3$-sets that includes that element plus one (the element-vertex itself). But then the size of this clique is only $4$, since $X3C$ is still $NP$-complete when each element is included in at most three $3$-sets. So, this is a clique of set-vertices. Thus, they are pairwise-disjoint. With $k$ outer-incident edges, the size of this clique must be exactly $\frac{n}3$. This is due to the fact that $M$ can be large enough (still polynomially) so that the binomial defining $k$ (in variable $x$, the size of the clique) is monotone in $[1,\cdots,m]$.


Prerequisites for studying parametrized complexity Which areas of CS/Math should one have mastered before diving into parametrized complexity?

This shouldn't come as a surprise, but you should definitely be familiar with algorithms and datastructures as well as complexity theory.
Two fundamental text books are downloadable for free, and you can probably find the answer to your question there:

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer, 2015
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi, Kernelization. Theory of Parameterized Preprocessing, Cambridge University Press, 2019.

But to give my own short answer:
I think knowing some recursion theory (computation theory) is of benefit, since some of the levels in the parameterized hierarchies are based directly on Turing machine theory.
Most crucial is it that you have a good understanding of the complexity classes P and NP, and how to prove that algorithms are running in polynomial time, and how to prove that some problems are NP-complete.
Parameterized complexity is a fun area, enjoy your journey!


SSD vs HDD Retrieval Time On an HDD if data is fragmented the discs need to be spun to where the next block in the file is, so how and where data is stored can make a big difference in how long it takes to retrieve the data. With an SSD is the retrieval time for fragmented data constant (due to no moving parts and it being entirely electronic)? Does this mean it doesn't matter how the data is stored on the drive?

TL;DR: You don't have to worry about seek times with SSDs like you do with hard disks.  As a first-order approximation, you can think of them as random-access devices.

SSDs let you read and write entire blocks.  There is some cost to read/write a particular block (usually under 0.1ms).  Once you're reading or writing a block, it's a lot faster to read/write the rest of the block.

As a consequence, SSDs are almost like random-access devices -- but there is some advantage to having data that will be accessed simultaneously be in the same block, so it does matter to some extent how the data is stored on the SSD.

To dive into some more specifics: A SSD is composed of a bunch of erase blocks (think 512KB or so).  Each erase block consists of multiple write pages (think 4KB or so).  A SSD supports three operations: read at some location;  erase an entire erase-block (making all of those write-pages "blank"); and write to an write-page that is currently "blank".

There's no way to to modify just part of a page.  Instead, this is implemented by reading the entire page into RAM, modifying it, writing the entire thing to a blank page, and updating some filesystem data structure to point to the new page instead of the old page.

As a consequence, it's best if writes are clustered at the granularity of the underlying pages.  Small, random-access writes are slower; long, sequential writes are faster.  Many SSDs contain some kind of cache or "write combining" to try to reduce the impact of this.

To give some example performance numbers: it might take 0.05-0.1 ms to read an entire page, 0.3-1 ms to write a page; and 1-3 ms to erase an erase-block.  These are just examples -- don't take them too seriously.  Actual performance will vary from device to device.

More reading:

https://en.wikipedia.org/wiki/Flash_file_system

Design Tradeoffs for SSD Performance.  Nitin Agrawal ∗ , Vijayan Prabhakaran, Ted Wobber, John D. Davis, Mark Manasse, Rina Panigrahy.  Usenix ATC 2008.

Understanding Intrinsic Characteristics and System Implications of Flash Memory based Solid State Drives.  Feng Chen, David A. Koufaty, Xiaodong Zhang.  SIGMETRICS/Performance 2009.

https://en.wikipedia.org/wiki/Write_amplification