Polynomial Computation of the probability of a number of independent events Suppose to have $n$ independent events $E_1, E_2,..., E_n$, where the probability of occurrence of event $E_i$ is $p_i$ (i.e., each event has its own probability of occurrence). We can easily define new events of type $N_k\equiv$"exactly $k$ events occur".

The probability of event $N_k$ can be computed as
$$\Pr(N_k) = \sum_{I \in \mathcal{I_{n,k}}}\prod_{i \in I}p_i \prod_{i \notin I} (1-p_i)$$
where $\mathcal{I_{n,k}} = \lbrace I \subseteq \lbrace 1,2,\ldots,n \rbrace :|I|=k \rbrace$. However, this calculation requires exponential time w.r.t. $n$.

Is there an algorithm with polynomial time complexity w.r.t. $n$ to compute the probability of each $N_k$, for $k=0,1,...,n$?

You can use dynamic programming. For parameters $m,\ell$, define
$$ q_{m,\ell} = \sum_{I \in \cal I_{m,\ell}} \prod_{i \in I} p_i \prod_{i \in [m] \setminus I} (1-p_i). $$
This satisfies the recurrence
$$
q_{m,\ell} = p_m q_{m-1,\ell-1} + (1-p_m)q_{m-1,\ell}
$$
with initial values $q_{0,0} = 1$ and $q_{m,\ell} = 0$ for $\ell < 0$ and $\ell > m$. This gives an $O(n^2)$ time algorithm.

The same idea can be expressed using generating functions:
$$
\prod_{i=1}^n (1-p_i + p_i x) = \sum_{k=0}^n \Pr(N_k) x^k.
$$


What are the criticisms regarding the performance of HTM? I just recently learned about the existence of this hierarchical temporal memory (HTM). I already read the document Hierarchical Temporal Memory: Concepts, Theory and Terminology (by Jeff Hawkins and Dileep George), which seems rather easy to understand, but one red flag is that the document is neither peer-reviewed nor attempting to explain why it should work in details.

I tried to look around for some independent sources. I found a few papers that compare its performance against others, but none explain why it performs well (or not). I noticed some comments claiming that it was looked down by mainstream expert, but I was unable to find any actual criticisms.

What are the criticisms regarding the performance of HTM? Since HTM is meant to be generic, any domain-specific criticism should be related to a more fundamental problem.

Furthermore, there are a huge amount of training data to use, enough even for multiple months training session. Basically, any criticisms regarding size or length of training is not relevant.

Criticisms against Jeff Hawkins are well summarized in the following essay taken from
http://www.theregister.co.uk/2014/03/29/hawkins_ai_feature/

I myself believe that the HTM theory has a huge potential and will be a foundation of true machine intelligence. IBM recently announced to back up the HTM theory and started the Cortical Learning Center including some hundred members.

http://www.technologyreview.com/news/536326/ibm-tests-mobile-computing-pioneers-controversial-brain-algorithms/

As is pointed out in the essay, Dillep George, a cofounder of Numenta, made the startup Vicarious, which attracted a huge amount of fund, of which fact suggests a potential of the HTM theory.

  Source: Criticisms against Jeff Hawkins, The Register

  His media-savvy, confident approach appears to have stirred up some
  ill feeling among other academics who point out, correctly, that
  Hawkins hasn't published widely, nor has he invented many ideas on his
  own.

  Numenta has also had troubles, partly due to Hawkins' idiosyncratic
  view on how the brain works.

  In 2010, for example, Numenta cofounder Dileep George left to found
  his own company, Vicarious, to pick some of the more low-hanging fruit
  in the promising field of AI. From what we understand, this amicable
  separation stemmed from a difference of opinion between George and
  Hawkins, as George tended towards a more mathematical approach, and
  Hawkins to a more biological one.

  Hawkins has also come in for a bit of a drubbing from the
  intelligentsia, with NYU psychology professor Gary Marcus dismissing
  Numenta's approach in a New Yorker article headlined Steamrolled by
  Big Data.

  Other academics El Reg interviewed for this article did not want to be
  quoted, as they felt Hawkins' lack of peer-reviewed papers combined
  with his entrepreneurial persona reduced the credibility of his entire
  approach.

  Hawkins brushes off these criticisms and believes they come down to a
  difference of opinion between him and the AI intelligentsia.

  "These are complex biological systems that were not designed by
  mathematical principles [that are] very difficult to formalize
  completely," he told us.


Particular techniques for NP-complete problems Is it possible to show particular classes of techniques (for instance dynamic programming) cannot produce polynomial time algorithms to any NP-complete problem?

For such a broad technique as dynamic programming, the answer is almost certainly no. Suppose somebody proves that P = NP (and we don't know that they can't) by giving a polynomial-time algorithm for 3SAT. Surely, that algorithm could be rewritten as some kind of trivial dynamic programming, since pretty much any for loop can be written as dynamic programming.  For example,

total=0
for i=1 to n do
    total = total + data[i]
print total

can be rewritten as

total[n] = data[n]
for i=n-1 downto 1 do
    total[i] = total[i+1] + data[i]
print total[1]

However, one result that is in the spirit of a "yes" answer to the question is in Mihalis Yannakakis's paper "Expressing combinatorial optimization problems by Linear Programs" (Journal of Computer and System Sciences, 43(3):441-466, 1991; DOI, free PDF). This shows that any symmetric linear program for TSP must have exponential size – a linear program is symmetric if, whenever you permute the main variables, you can permute the auxiliary variables to get back the original program. Yannakakis's paper was, as I understand it, written because Ted Swart had been trying to use linear programming to solve Hamiltonian cycle in P and couldn't quite get the very large ($n^8$ to $n^{10}$ variables) linear programs to work.


Preventing oversell, allocation of limited resources with overlapping properties I am trying to solve problem of preventing oversell of limited resources.

Consider resources (people) who are described by set of properties where each property belongs to different category (example properties from four categories:  male, age 25-30, 2 children, interested in games).

Buyers want to allocate access to resources. Buyers can specify subset of categories and one property from each category (example: allocate 1000 males, age 25-30 or allocate 100 females, age 25-30, interested in music).

In my real life example I have 6m+ possible set of properties (profiles) where for each set of properties I know how many profiles exists.

My initial approach was to build a graph like one below:

and then traverse using edge weights, for instance validating if demand for 100 females, age2 can be satisfied:

check if size(female, age2) < 100
for each parent:

check if size(parent) < 100 and go to 2.

for each child:

check if size(child) < 100 * weight(edge(node, child)) go to 1.

(above algorithm is simplified as does not prevent visiting same node multiple times)

It all works fine when graph is small, however when number of nodes and edges (dependencies) between nodes (profile universe groups) grows it does not scale very well.

Consider example:

large graph, 6m nodes, 20m+ edges
buyer wants to allocate 1000 males (and there are only males and females in gender category)

algorithm would start with top-level 'male' node which probably has 10m+ outgoing edges and 10m+ checks would be required (and probably each of those 10m outgoing edges has incoming edges which need to be checked as well).

I was trying to find different approach but failed. I was trying to google out existing solutions but seems like I am unable to even name problem properly. Any reference to what is this problem similar to would be good for me as a starting point.

Thanks for comments/help.

Two more graphs to present exponential growth of the graph:
3 categories

4 categories

Update

Regarding size, assuming 8 categories of properties where each category has: 2, 6, 6, 6, 6, 8, 1140, 150 values respectively then estimated number of profiles: 2*6^4*8*1140*150 ~= 3.5 * 10^9. Number of nodes in graph: at least 7 * 10^9, number of edges in graph: at least 140 * 10^9.

Update #2

Formula for number of nodes is:

$\sum_{i<n}\prod_{k<i \atop j_1, j_2, ..., j_k < n} s_{j_{1}} ... s_{j_{n}}$

where $n$ is number of categories and $s_x$ is size of category $x$.

So in my example there would be 11'169'108'657 nodes.

Update #3

As per @Raphael advice - I have reduced number of nodes and now formula is:

$\sum_{i<n-M}\prod_{k<i \atop j_1, j_2, ..., j_k < n} s_{j_{1}} ... s_{j_{n}}$

where $M<n$ and assumed that distribution of resources across smallest slices of universe is equal.
At the same time removed lot of edges from graph.

Example of sub-graph size reduction:

So the data structure holding pointers for every possible combination of classifiers is huge. Sure, but why build it at all? Don't overengineer this!

Just store the profiles in a database and do one (linear time) filtering sweep for each query, i.e. select/count on demand. For a few millions of records, that should require no further preprocessing.

If the number of requests is large and/or you need really small response times, you can think about caching, or creating equivalence classes along some popular classifiers, or along classifiers with few large classes. Then, the linear sweep has to be done only on small lists.

For example, you can divide your database along gender and age (assuming these are included in most customer queries)

$\qquad \{m, w, o\} \times \{0..5, 10..15, \dots, 95..100\}$

where the values obviously depend on your data. Then, each query will require only few of these small lists, and can even parallelise if you store the individual chunks separately.


Common name for inverse of beta reduction For some transformation, I am currently working on, it is useful to "pull out" subexpressions and replacing them with variables.

i.e. $\textbf{transform}(42 + 3 * 4) = (\lambda x. 42 + x) (3*4)$

This has, of course, the same result (if it does not extract bound variables and is correct only modulo evaluation order, i.e. termination properties might change).

Such a basic operation probably has an established name, but I never heard it. Is it "beta-expansion"?

Yes, it's called beta expansion. Usage examples: Horwitz, Miller, Galbiati and Talcott, Coq manual, …

Similarly $M \to (\lambda x. M \, x)$ (the converse of eta reduction) is called eta expansion, and so on.


Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once? So we know a nondeterministic Turing machine (NTM) is just a theoretical model of computation. They are used in thought experiments to examine the abilities and limitations of computers. Commonly used to dicuss P vs NP, and how NP problems cannot be solved in polynomial time UNLESS the computation was done on the hypothetical NTM.
We also know an NTM would use a set of rules to prescribe more than one action to be performed for any given situation. In other words, attempt many different options simultaneously.

Isn't this what distributed computing does across commodity hardware? Run many different possible calculations in parallel? And the GPU, does this within a single machine. Why isn't this considered an NTM?

In parallel computing, the threads can talk to each other and exchange information during the computation. In nondeterminism, the only "communication" between threads is that we compute the OR of all possible computation paths. This is much more limited.

If you simulate nondeterminism by spawning parallel computations for every nondeterministic choice, you need an exponential number of threads for a polynomial time computation. We know how to build parallel machines in the real world, we don't know how to build nondeterministic ones.


How to find out if a piecewise function is partially computable? I know exactly what a partially computable function is, but I've seen a few functions that I really can not understand why they are not partially computable. As an example in Davis book page 78, he says the following function is not partially computable: ($\uparrow$ means undefined and $\downarrow$ means defined)

Given an infinite set C such that $\phi(c,c) \uparrow$ for all $c \in C$ and such that

  $$
H_4(x) =
\begin{cases}
1 & IF \phi (x,x) \downarrow \\
0 & x \in C \\
\uparrow & Otherwise \\
\end{cases}
$$

is not partially computable.

Or in page 77 he says the following is partially computable while I cannot understand what is difference between these two functions!

Given an infinite set B such that $\phi(b,b) \uparrow$ for all $b \in B$ and such that

  $$
H_3(x) =
\begin{cases}
1 & IF \phi (x,x) \downarrow \\
0 & x \in B \\
\uparrow & Otherwise \\
\end{cases}
$$

Or between these two functions which one is partially computable? ($K=\{ n \in N | \phi(n,n) \downarrow \}$)

  $$
f_1(x) =
\begin{cases}
2 & x \in K \\
\uparrow & Otherwise \\
\end{cases}
$$

  $$
f_2(x) =
\begin{cases}
\uparrow & x \in K \\
2 & Otherwise \\
\end{cases}
$$

So I would like to know what makes a piecewise function to be partially computable?

UPDATE:

Since $K$ is recursively enumerable (in face m-complete), it is not recursive so checking membership in this set is semi decidable. I guess $f_2(x)$ should be partially computable but I'm not sure!

Page 3 of the book says: "partial function on a set S is a simply function whose domain is a subset of S."

The difference between $H_3(x)$ and $H_4(x)$ are the sets of $B$ and $C$ that you are going to make. for example if you give $B$ such that for all $x$ the other wise don't happen, then $H_3(x)$ will be a total function and we know every total functions are partial functions since $S \subseteq S$.

between $f_1(x)$ and $f_2(x)$ the one is partial computable which gives output for some $x$s in its domain.


Why are Oracle call instances bounded in the definition of FPT Turing reductions? Let's take the following definition of a FPT Turing reduction from Flum & Grohe's book.

Let $F$ and $G$ be parameterised problems. For any instance $x$ of $F$, write $k(x)$ for the parameter of $F$ and $|x|$ for the size of $x$. For any instance $y$ of $G$, write $l(y)$ for the
parameter of $y$. An FPT Turing reduction from $F$ to $G$ is an algorithm with an oracle for $G$
that, for some computable functions $f, g : \mathbb{N} → \mathbb{N}$ and for some constant $c \in \mathbb{N}$, solves any
instance $x$ of $F$ in time at most $f (k(x)) · |x|^c$ in such a way that for all oracle queries the
instances $y$ of $G$ satisfy $l(y) ≤ g(k(x))$.

If we go through the definition in high-level terms I understand:

We have an algorithm for $F$ that is allowed to call an oracle for the problem $G$ (this is done in constant time).
The Algorithm must run in a time that is a computable function of the size of the parameter of our instance of $F$ multiplied by a polynomial function of the size of the instance of $F$.

I understand things thus far. However the final restriction that instances of the problem $y$ for which we make an oracle query must satisfy $l(y) ≤ g(k(x))$ for a computable function $g$ I do not understand. What does this say in high-level terms and why is it important? Thanks.

As Pål GD mentions, the requirement that $l(y)\leq g(k(x))$ is necessary to obtain reductions with the proper result. In particular, the property 'If $X$ is FPT, and there is an FPT-reduction from $Y$ to $X$ then $Y$ is FPT'.

An example to see why this requirement is necessary is to consider reductions between $k$-Clique and $k$-Vertex cover. Recall that we can construct polynomial time reductions both ways between Clique and Vertex cover (without the parameters), using the fact that if $X\subseteq V$ is a maximum clique in the graph $G$, then $V\setminus X$ is a minimum vertex cover in the complement of $G$.

However, this doesn't give a FPT reduction from $k$-clique to vertex cover: If we try to solve $k$-clique by finding a vertex cover in the complement of $G$, we need to find one of size $k'=|V|-k$. As $k$-vertex cover is FPT, applying the reduction and solving $k$-vertex cover can be done in $O(f(k')\cdot|G|^{O(1)})= O(f(|V|-k)\cdot|G^{O(1)}|)$. So, we don't get an FPT algorithm for $k$-clique from this 'reduction', as the 'non-polynomial' part of the running time depends on $|V|$! In fact, we shouldn't expect $k$-clique to have an FPT reduction to $k$-vertex cover, as $k$-vertex cover is FPT, but $k$-clique is $W[1]$-hard.

Additionally, I agree with Pål GD that the definition of parameterized Turing reductions you give is a bit difficult to read. I've looked at Flum & Grohe's book and their presentation of this definition is in fact a lot clearer than than one you provide (from a different book/edition?):

  Definition 2.8. Let $(Q,\kappa)$ and $(Q' ,\kappa' )$ be parameterized problems over the alphabets $Σ$ and $Σ'$, respectively. An fpt Turing reduction from $(Q,\kappa)$ to $(Q' ,\kappa' )$ is an algorithm $\mathbb{A}$ with an oracle to $Q'$ such that:

  $\mathbb{A}$ decides $(Q,\kappa)$.
  $\mathbb{A}$ is an fpt-algorithm, that is, there is a computable function $f : \mathbb{N} \rightarrow \mathbb{N}$
  and a polynomial $p(X)$ such that the running time of $\mathbb{A}$ on input $x \in \Sigma^*$ is bounded by $f(\kappa(x))\cdot p(|x|)$.
  There is a computable function $g : \mathbb{N} \rightarrow \mathbb{N}$ such that for all oracle queries
  “$y \in Q'$?” posed by $\mathbb{A}$ on input $x$ we have $κ'(y) \leq g(κ(x))$.


Time and space complexity of Radix sort I had previously asked a question on space complexity of radix sort here. I have also read this question. However, I still get confused about it which means that the concept is not clear. I have the following implementation which is meant only for positive integers:

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <sstream>
#include <algorithm>

void radix_sort(std::vector<int>& arr)
{
    int rad = 1;
    int max_val = *(std::max_element(arr.begin(), arr.end()));
    while(max_val / rad)
    {
        std::array<std::vector<int>, 10> buckets;
        int n = arr.size();
        for(int i = 0; i < n; i++)
        {
            buckets[arr[i] / rad % 10].push_back(arr[i]);
        }

        auto k = arr.begin();
        for(auto b : buckets)
        {
            k = std::copy(b.begin(), b.end(), k);
        }

        rad *= 10;
    }
}

void print_array(std::vector<int>& arr)
{
    for(auto num : arr)
    {
        std::cout << num << "\t";
    }
    std::cout << "\n";
}

int main()
{
    int val;
    std::vector<int> arr;
    std::string s;
    std::cout << "Enter the numbers in the array: \n";
    std::getline(std::cin, s);
    std::istringstream ss{s};
    while(ss >> val)
    {
        if(val != ' ')
        {
            arr.push_back(val);
        }

    }
    std::cout << "Before sorting: \n";
    print_array(arr);
    radix_sort(arr);
    std::cout << "After sorting: \n";
    print_array(arr);
    return 0;
}

The time complexity is O(kn) and space complexity is O(k + n). Here n is the number of elements and k is the number of bits required to represent largest element in the array. My problem is with k and I am not able to understand how that effects the complexity. In the above code the number of times the outermost while loop runs depends on the number of digits of maximum value. Until recently I assumed that k represented this number of digits of maximum value. However, that is not the case. Can anyone please explain in simpler terms?

Edit: Pseudocode

1) Take the array as input

2) Initialize a variable `rad` as 1

3) Find maximum value element in the array

4) Until all the digits in maximum value element are visited:

          i) Create buckets for digits from 0 to 9.

          ii) Based on `rad`, calculate digits in a particular place of number (eg: unit's, ten's, hundred's etc.).

          iii) Fill the buckets with elements, based on the digit they have in the place under consideration in the loop.

          iv) Take out the numbers from buckets in the order bucket0 to bucket9 and use it to populate the original array.

          v) Update `rad` to change the place under consideration for the next loop.

A

  $k$ represented this number of digits of maximum value.

B

  k is the number of bits required to represent largest element in the array

This translates to number of digits required to represent the max value in binary.

A is equivalent to B.

Here is how:

Say largest element in the array is 1233.

According to B, $k = log_2(1233) \approx 11$

According to A, $k = 4$, which is just $log_{10}(1233)$.

There is formula for converting between the
$$log_a(n) = \frac{log_b(n)}{log_b(a)}.$$

The denominator here $log_a(b)$ is a constant.

So $log_2(n) = O(log_{10}(n))$. So it doesn't really matter to radix sort what base you are using.


Perfect natural number A perfect natural number is that which is equal to the sum of it's divisors.
For example 6 is perfect: 1+2+3=6 also 28 is perfect.

Prove the following language is NP hard:

L={< n> | n is a perfect natural number}.

You can use the fact that if

$$n=p_{1}^{m_{1}}p_{2}^{m_{2}} \cdot \cdot \cdot p_{k}^{m_{k}}$$

where $p_{i}$ are n's prime divisors, then the sum of n's divisors including n would be:

$$(1+p_{1}+p_{1}^2+...+p_{1}^{m_{1}})(1+p_{2}+p_{2}^2+...+p_{2}^{m_{2}})\cdot \cdot \cdot (1+p_{k}+p_{k}^2+...+p_{k}^{m_{k}})$$
Now I know the proof should contain a polynomial time reduction from some NP problem to this language L, most likely from SAT, I only can't figure out how to go about it, any guidance would be appreciated.

NP ≠ NP hard.

NP means: For every perfect number, there is a certificate that lets you prove in polynomial time that it is perfect.

And that is clearly the case. For every perfect number, I can give you the factorisation, plus for all large prime factors a proof that these large factors are primes, and then you can quite easily check that the number is perfect.

NP hard means: If you can solve this problem, then you can solve any problem in NP. I don't see this. Especially since perfect numbers are so rare. (Why does it make it unlikely that this is NP hard? Polynomial time reduction means: If you take a problem in NP, then for any instance with answer "Yes" there is a perfect number so that the fact that this number is perfect proves the answer to your problem is "Yes". For different instances I'd expect different perfect numbers to be needed. But there are so few known...)


Modified Linear Bounded Automata Language We know that linear bounded automatons accept context-sensitive grammars.

  Now suppose that we modify the LBA such that any location of the tape except the
  input part can be changed.What language does this automaton accept?

I think it is as strong as the standard Turing machine because we can copy the input part somewhere else and work with it like a semi-infinite Turing machine so that its tape is limited from the first symbol of the input that we copied.So it accepts recursively enumerable languages.Is this correct?

any location except i/p part means

(total unbounded tape area - tape area that includes i/p string)

= (infinity length - finite length) as we know i/p string length is always finite

= infinity length

in the definition of linear bounded automata it is stated that the tape can be used as a function of the input string length.but here the portion that can be used is of infinite length which is obviously not a function of the input string length.So it acts as a turing machine.


Why is the second operation of a Monad called bind? I understand how monadic computation works, I am just wondering where does the name come from. I cannot relate the thing that the bind operator actually does (i.e. unbox the monadic value, and then apply a function to produce another monadic value) and the name bind (which, to me, means associate two things together).

I understand why we have the name return (I suspect it has to do with the Haskell do-notation), although IMHO it isn't a good name either. Return indicates a change in control flow but it really isn't, all it does is produce a monadic value.

In Haskell the syntactic sugar for bind e₁ (λ x . e₂) is

do x ← e₁
   e₂

That is, the result of the computation e₁ is bound to x, after which e₂ is computed.

In ML-like languages the same thing is written as

let x = e₁ in e₂

which again is a form of binding a variable to a value.

As for return being a control-flow mechanism – that's precisely what it is. You are probably thinking of control mechanisms for branching, looping, raising exceptions etc. Well, return is the one that ends a computation and yields a result.


Boat riddle as a combinatorial optimization problem? I remember a riddle about a bunch of people on a river bank, and a boat with limited capacity (lets say the boat can transport 2 people at a time). There are various relations between the people like: person $x_m$ and $x_n$ cannot sail together and cannot even stay on the same bank of the river or $x_m$ and $x_n$ always have to be together.

When I remembered this riddle, I thought whether it could be represented as an optimization problem. The criterial function would be $\min(\text{numberOfSails})$ and the conditions will be my limitations, but I am not sure whether I can model my problem like this (and I am not sure how to model all my conditions).

Could you tell me or give me a hint, how such an approach for modelling this program would look like?

At first I thought it could look something like this:

min i // i = number of sails
x_i1 + ... + x_i2 <= 2 // i-th sail can contain max 2 people
x_im + x_in <= 1 // x_m and x_n cant sail together
etc.

But there is so much wrong with this model (like considering the people left on the first bank or the people already transported) and so on, so I am not sure how to tackle this problem.

The river crossing problem using integer programming is solved by Börndorfer et al. in [1].

[1] Borndörfer, Ralf, Martin Grötschel, and Andreas Löbel. Alcuin's transportation problems and integer programming. ZIB, 1995.


Precedence in regular expressions I'm having trouble finding the language represented by the following:

(AA|BB)*

Should the expression be read as... ( A (A|B) B ) *
or... ( (AA) | (BB) )*

If that isn't clear, should this produce something like... ABABAB or should it produce AABBAABBBBAA

My guess is that AABBAA is part of the represented language, while AB is not.

This depends entirely on convention; with respect to a (proper) formal definition, the expression is invalid as it not properly parenthesised. I'd say that typically, the order is (from stronger to weaker binding)

Kleene Star/Plus (also finite versions),
concatenation,
alternative.

Note that this corresponds (visually) to exponentiation over multiplication over addition in basic arithmetics, so it's probably the natural way.

That is,

$10^*1$ is read as $1(0)^*1$ and
$10|01|11$ as $(10)|(01)|(11)$.

Note that I still drop parentheses due to associativity of concatenation and alternative.


Is $a^n b^n c^n$ context-free? I am new to grammars and I want to learn context free grammars which are the base of programming languages. After solving some problems, I encountered the language

$$\{a^nb^nc^n\mid n\geq 1\}\,.$$

Can anybody tell me if this is a context free language? I can't make any context free grammar for it and I don't know any other proof.

You are asking two different questions. First, is $\{a^nb^nc^n : n \geq 1 \}$ a context-free grammar? Second, is $\{a^nb^nc^n : n \geq 1 \}$ a context-free language?

The answer to the first question is No, since $\{a^nb^nc^n : n \geq 1 \}$ is not a grammar, let alone a context-free grammar; it is a language. What you probably meant to ask was: "Does $\{a^nb^nc^n : n \geq 1 \}$ have a context-free grammar?", which is the same as the second question.

The answer to the second question is also No. In fact, it is one of the standard examples of non-context-free languages, and as such most textbooks will have proofs to that effect.


special case of best first search algorithms I read somewhere that DFS is a special case of Best first search algorithm if f(n)=-depth(n). please justify this i am not getting it.:/

Consider a node $u$ such that $depth(u)=l$.

In Best first Search when you evaluate $u$ with the evaluation function you defined, you have $f(u)=−l$.

queue

╔═══╤═══╤═════╤═══╗
║ r │ a │ ... │ u ║
╚═══╧═══╧═════╧═══╝

When you expand $u$ and you evaluate the first child of $u$ (suppose it is Node $v$) you have $f(v)=−(l+1)<−l=f(u)$ so now you expand $v$ (that means that you put $v$ in the front of the queue) and you continue.

queue

╔═══╤═══╤═════╤═══╤═══╗
║ r │ a │ ... │ u │ v ║
╚═══╧═══╧═════╧═══╧═══╝

This corresponds to what you do when you use Depth First Search.


Reduce the total internal border of a set of touching rectangles (using graphs) I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas

I will go over the algorithm, however the final structure still consisting of rectlinear rectangles has a more complex representation as shown below. I think it will still work.

Possible steps

Example of a Real World problem

Here's a naive attempt at a greedy solution.

I'm assuming the initial input is a polyomino (polygon made up of grid aligned squares) on a grid as in your "real world example".

Let $b = (i, j, w, h)$ be the rectangle with lower left corner containing grid location $(i, j)$ with width $w$ and height $h$. A rectangle is valid if and only if all of its internal grid cells are part of the polyomino.

For a valid rectangel $r$, the boundary edges of $r$ will either also be boundary edges of the polyomino itself, or internal edges. Denote by $B_r$ the number of boundary edges of the rectangle that are internal to the polyomino and $I_r$ the number of grid edges that are internal to both the boundary and the rectangle. In the teal rectangle in my example below, $I_r = 17$ and $B_r = 6$ (the red sketchy edges). Now define the quality of the rectangle $r$ to be $Q_r = I_r - B_r$.

The thought here is that the quality of a rectangle measures how good it is at eliminating internal edges.

Now, the greedy solution I have in mind is:

Generate all of the $O(n^4)$ possible rectangles $r$.
For each rectangle $r$, check if $r$ is valid.
* If $r$ is valid, compute its quality score and maintain the rectangle with the maximum quality.
End for loop.
Add the rectangle that maximized the quality to the output set, and color the squares it covers white. Repeat until all squares are white.

Unfortunately this is $O(n^5)$ where $n$ is the width and height of the grid. But if your problem size really is like the image, then that may not be an issue.

Also, I don't have a proof that it's optimal, but I'll think about it.

Ok, I wrote some code for this. It's quick and dirty, but it returns exactly your optimal result on your original small example. It is quick and dirty, so don't judge ;).

from functools import reduce

# Generates all valid rectangles that have a lower left hand corner in i and j
def validRectanglesFrom(grid, i, j):
    result = []
    w = 1
    while i + w <= len(grid) and grid[i + w - 1][j] == 1:
        h = 1
        row_is_valid = True
        while j + h <= len(grid[i + w - 1]) and row_is_valid:
            for k in range(i, i + w):
                if grid[k][j + h - 1] == 0:
                    row_is_valid = False
                    break
            if row_is_valid:
                result.append((i, j, w, h))
            h = h + 1
        w = w + 1
    return result

def left_edge_is_internal(grid, i, j):
    return i > 0 and grid[i - 1][j] == 1 and grid[i][j] == 1

def right_edge_is_internal(grid, i, j):
    return i < len(grid) - 1 and grid[i][j] == 1 and grid[i + 1][j] == 1

def bottom_edge_is_internal(grid, i, j):
    return j > 0 and grid[i][j - 1] == 1 and grid[i][j] == 1

def top_edge_is_internal(grid, i, j):
    return j < len(grid[i]) - 1 and grid[i][j] == 1 and grid[i][j + 1] == 1

def bottom_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda i: bottom_edge_is_internal(grid, i, rect[1]),
                    range(rect[0], rect[0] + rect[2])
                )
            )
        )
    )

def top_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda i: top_edge_is_internal(grid, i, rect[1] + rect[3] - 1),
                    range(rect[0], rect[0] + rect[2])
                )
            )
        )
    )

def left_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda j: left_edge_is_internal(grid, rect[0], j),
                    range(rect[1], rect[1] + rect[3])
                )
            )
        )
    )

def right_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda j: right_edge_is_internal(grid, rect[0] + rect[2] - 1, j),
                    range(rect[1], rect[1] + rect[3])
                )
            )
        )
    )

def boundary_penalty(grid, rect):
    return (
        bottom_boundary_penalty(grid, rect) +
        top_boundary_penalty(grid, rect) +
        left_boundary_penalty(grid, rect) +
        right_boundary_penalty(grid, rect)
    )

def internal_grid_edges(rect):
    return ((rect[2] - 1) * rect[3]) + (rect[2] * (rect[3] - 1))

def quality(grid, rect):
    return internal_grid_edges(rect) - boundary_penalty(grid, rect)

def get_rectangles(grid):
    result = []
    grid_locations = [(i, j) for i in range(0, len(grid)) for j in range(0, len(grid[i]))]
    unfilled = {cell for cell in grid_locations if grid[cell[0]][cell[1]] == 1}
    while len(unfilled) > 0:
        rects = [rect for cell in unfilled for rect in validRectanglesFrom(grid, cell[0], cell[1])]
        qualityScores = list(map(lambda rect: quality(grid, rect), rects))
        bestRectIdx = reduce(lambda i, j: i if qualityScores[i] > qualityScores[j] else j, range(len(qualityScores)))
        bestRect = rects[bestRectIdx]
        result.append(bestRect)
        for i in range(bestRect[0], bestRect[0] + bestRect[2]):
            for j in range(bestRect[1], bestRect[1] + bestRect[3]):
                unfilled.remove((i,j))
                grid[i][j] = 0
    return result

# Your initial example
grid = [[1, 1, 1], [0, 1, 0], [0, 1, 1], [0, 1, 0]]
get_rectangles(grid)

# Your "real world" example
grid2 = [[0,0,0,0,0,0,0,0,1,1,1,0,0,0,0],
        [0,0,0,0,0,0,0,0,0,0,1,1,1,0,0],
        [0,0,0,0,0,0,0,0,0,1,1,1,0,0,0],
        [0,1,0,0,0,0,0,0,0,1,0,1,1,0,0],
        [1,1,0,0,0,0,0,0,0,0,0,1,1,1,0],
        [1,1,1,1,0,0,0,0,1,0,0,1,0,1,0],
        [0,0,0,1,1,0,0,1,1,1,1,1,0,1,0],
        [1,1,1,1,1,0,1,1,1,1,1,1,0,0,0],
        [1,1,1,0,1,0,1,1,1,1,1,0,0,0,0],
        [0,0,1,1,1,1,1,0,0,1,1,1,0,0,0],
        [0,0,0,1,0,0,0,0,0,0,1,0,0,0,0],
        [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0],
        [0,1,1,1,0,1,1,0,0,0,0,0,0,0,0],
        [0,1,1,1,0,1,0,0,0,0,0,0,0,0,0],
        [0,1,0,1,1,1,1,1,0,0,0,0,0,0,0]]
get_rectangles(grid2)

Here's the result my code returns for your "real world" example.


Local Cache miss using MESI Coherence Protocol My notes on MESI state that there are a few courses of action when we experience a local cache miss on read, depending on the global state of the data (whether other copies already exist, and the state they exist in)
I'm having some trouble understanding how we know the state of the data when we miss on a read.
As far as I'm aware, MESI data is attached to each cache line, so if we have do not have a copy of the required data (we missed on the read) then how do we know the relevant MESI data, so we can make the decision on how to react to the miss? (whether we should read from memory, check for shared/modified copies etc)

In cache coherence protocols there needs to be a single location where the global state can be figured out.  There are two ways to implement this location.  The first is to use a directory.  The second way is to broadcast all information on a shared bus.

If you are using a directory, then the cache that misses sends a message to the directory node that "knows" the global state for that cache line.  The directory records the list of caches that have a copy of the cache line and what the state is at each of those caches.  (This is easier than it sounds at first, the line is either invalid everywhere, modified in exactly one cache, exclusive in exactly one cache, or shared in more than one cache.)

In a directory-based coherence protocol, when a cache misses it sends a message to the directory for that line.  If the directory sees that the line is invalid everywhere it forwards the request to the main memory, which responds to the cache, and the directory updates its state so that it knows the cache has an exclusive copy.

If the directory sees that the line is modified or exclusive in another cache, it forwards the request to that cache, changes the global state to shared, and (in most versions of the algorithm) saves the identifiers of the two caches that are now sharing the line.

If the directory sees that the line is in state shared, it forwards the request to one of the other caches sharing the line, and adds the requester to the list of sharers.

Directory based cache coherence is elegant, and scalable, but requires more than the necessary number of message hops for small systems, so for small systems a hack is used to replace the directory.  Instead of a directory, all requests from caches or responses to requests (from other caches or from memory) are placed on a shared bus.  Every message is broadcast to all the other nodes on the bus.  So in the case of a read miss: the cache that missed broadcasts a request for the data in state "shared".  All the other caches and the main memory are listening to the bus (this is called snooping).  If one of the other caches has the line in state modified or exclusive, it changes its state to shared and sends the data back on the bus to the requester.  If several of the other caches have the line in state shared then they will all try to send the data back on the bus to the requester (and the bus arbiter will ignore all but one of the replies).  Finally if none of the other caches have a copy of the line then the main memory will respond with the data.  The cache that made the request sees that the responder was main memory rather than another cache, so puts the newly received line in state exclusive.


A partition algorithm I have encountered the following problem that I found very interesting to solve:

  Given an array of positive integers $\{a_1, a_2, ..., a_n\}$ you are required
  to partition the array into $3$ blocks/partitions such that the maximum
  of sums of integers in each partition is the minimum it can be.
  Restriction: you cannot alter the turn in which the numbers appear
  (example: if you have $\{2, 5, 80, 1, 200, 80, 8000, 90\}$ one partition
  CANNOT be the $\{2, 80, 1, 90\}$). The program must output ONLY the maximum sum, not the partitions.

So, for example let's have the array $\{2, 80, 50, 42, 1, 1, 1, 2\}$. The best partitioning according to the problem is
$$\{\, \{2, 80\},\, \{50\},\, \{42, 1, 1, 1, 2\} \,\}$$, so the output of the program in this case would be $82$.

I have already thought of a $\mathcal{O}(n^2)$ algorithm, but isn't there any better ( e.g. $\mathcal{O}(n)$ or $\mathcal{O}(n \log n)$ ) algorithm?

My $\mathcal{O}(n^2)$ algorithm is (it is pseudocode):

  input $n \in \mathbb{Z}$
  Let $m \leftarrow -1$
  Let $r_1 \leftarrow  r_2 \leftarrow r_3 \leftarrow  0$
  Let $A \leftarrow (a_0,...,a_{n-1})$
  Let $S \leftarrow \sum_{i=0}^{n-1}{a_i}$
  for each $i = 1$ until $n-2$ do
  $\quad r_1 \leftarrow (r_1 + a_{i-1})$
  $\quad r_2 \leftarrow 0$
  $\quad$ for each $j = (i+1)$ until $n-1$ do
  $\quad\quad r_2 \leftarrow (r_2 + a_{j-1})$
  $\quad\quad r_3 \leftarrow S - (r_2  + r_1)$
  $\quad\quad \max_{\mathsf{temp}} \leftarrow \max(\max(r_1,r_2),r_3)$
  $\quad\quad$if $(\max_{\mathsf{temp}} < m \, \vee m = -1)$ then
  $\quad\quad\quad  m \leftarrow \max_{\mathsf{temp}}$
  $\quad\quad$endif
  return $m$

Since you find it interesting to solve, I do not want to completely
spoil it too much  for you. So here is a big hint to solve it in linear time.

You start with two indices $i$ and $j$ which are the first and last indices of
central segment.

Initially you set $i=0$ and $j=n$. And you compute the 3 sums in
$s_1$, $s_2$ and $s_3$. So initially $s_1=s_3=0$.

Then you progressively increase $i$ and decrease $j$, by variations of
1, keeping $s_1$ and $s_3$ about the same value (by doing the change on the
smallest sum $s_1$ or $s_3$), until one becomes bigger than $s_2$.
Each increment or decrement  takes constant time (adding or
substracting the value of an element to two of the sums, and doing a
few comparisons).

When one of $s_1$ and $s_3$ becomes larger than $s_2$, say for example
$s_1$. Then you have $s_1\geq s_2 > s_3$.

Then you know that the right value for $i$ is either the current value
or the previous value. Typically it is the previous value of i, if
$s_1$ has become greater that the previous value of $s_2$. But things
are a bit more subtle. So you note this value of $s_1$ as $m_1$, a
possibility for the maximum, and then try to see if you could have
achieved a lower value for the maximum with the previous value of $i$
and $s_1$,
just before the last increase. So you revert $i$ to that previous
value, and you start to decrease $j$ to get the lowest possible maximum for
$s_2$ and $s_3$ without touching $i$ (that is easy, and recall that $s_1$ remains lower
than both others sums). Let $m_{2,3}$ be the lowest maximum found. Now, if
$m_{2,3}$ is greater than $m_1$, then the answer is $m_1$, else the
answer is $m_{2,3}$.

And you must consider the symmetrical case when $s_3$ is the first to
exceed $s_2$.


What should be the way to design code for such a situation? I have a graph as given below:

Let us assume one node as transmitter and another as receiver.

We need to transfer particles in every time slot constrained by maximum particles N and minimum 0. The combination of which particle in which time slot makes a code. I mean if 2 1 0 0 is a code that means that 2 particles in slot zero 1 in slot 1 and 0 particles in slot 2 and 3
Now let us suppose that any particle in a time slot can take any path and suffer through at most K delays. Delays are given by number of dots. More dots more delay. The delay to particles can be assigned randomly. The maximum delay for this graph is 4 it can be generalized to K.
How to design codes so that information is reliably transferred across transmitter and receiver.

I just want to know how these codes are constructed, assuming that other codes must exists to be revealed. Also please tell me the prerequisites I need for such problem as I am not a computer engineer. One way is given in here

Off the top of my head...

Given a Packet, encode both the slot and count into the number
with known limits.... a code can be computed ...
and both the Sender and Receiver know what the limits are.

For example: 5 slots, and 7 possible counts (max count from 0..6 is 7 )

A CODE to determine what slot and count in that slot when it arrives

Code = Count_in_slot + (slot_number * (Max_Counts ) )

   Table of example CODES that could be sent or received

Slot            n counts
       0   1   2   3   4   5   6
      --- --- --- --- --- --- ---
 0     0   1   2   3   4   5   6
 1     7   8   9  10  11  12  13
 2    14  15  16  17  18  19  20
 3    21  22  23  24  25  25  27
 4    28  29  30  31  32  33  34

Decode a Slot  and count from the number :

 Sequence Initialize all ZERO's

 for each Code received
   temp  = Code
   Count = temp mod max_count  (NOTE: Remainder of a division (Modular math )
   temp  = temp \ max_count    (NOTE: integer divide)
   Slot  = temp mod Number_of_slots
   Sequence(Slot) = Count

And when either all slots are received, or max time wait occurs the reconstructed sequence is completed.

ALSO NOTE:
 If time delay is used to close the sequence, then slots with ZERO do not need to be sent.


Understanding Tiernan's Algorithm I am currently working through Tiernan's paper, "An efficient search algorithm to find the elementary circuits of a graph" (published 1970), and I am stuck on point 3 of the following excerpt:

  The algorithm is named EC for "elementary circuit." The function blocks of EC are denoted EC1, EC2, etc. EC requires that there be assigned to the vertices, in any order, the integer designators 1, 2, .-., N. The algorithm utilizes two principal arrays in addition to that describing the graph. The first is a one-dimensional array, P, containing the vertices of an elementary path. The second is a two-dimensional array, H, and is initially zeroed. Elementary path building in P is the basic process of EC. The first path is started as vertex 1. A path is extended from its end, one arc at a time, with three conditions
  checked before a tentative extension is performed:

  The extension vertex cannot be in P.
  The extension vertex value must be larger than that of
  the first vertex of P.
  The extension vertex cannot be  closed  to the last vertex in P. H contains the list of vertices closed to each vertex.

What does Tiernan mean by point 3? I've tried googling the term "closed to [some vertex]", but the results were not entirely helpful.

I think I have managed to figure it out from the paper, and would like to leave my explanation for the next person who struggles with this concept.

From my understanding, Tiernan means nothing of a mathematical nature when he says "$u$ is closed to $v$". He's actually trying to say "$u$ is closed off to $v$", i.e. no longer accessible.

By following along with Tiernan's paper and his example, his algorithm manages to discover a cycle with the following vertices:

  $v_1, v_2, v_4, v_3, v_5$

Now that he has discovered a cycle, he removes the last vertex $v_5$ to see whether another vertex, say $v_x$, can be added to the remaining nodes, e.g. $v_1,v_2,v_4,v_3,v_x$, in the hopes of finding another cycle.

However, to avoid rediscovering the same cycle (such that $v_x \ne v_5$), the vertex $v_5$ is now closed to $v_3$ and $v_3$ cannot extend an arc to it again. In the matrix $H$, we now have $H[3,1] = v_5$ (or simply $5$ since Tiernan requires unique integer labels for each vertex). If $v_3$ would become closed to another vertex before $v_3$ was removed from $P$ (to backtrace and attempt to discover cycles using $v_1, v_2, v_4, v_x$), then that vertex would be placed in $H[3,2]$.

In a nutshell, "closed to" should actually be "closed off to/inaccesible" due to the fact that the node was already used as the last node in either a cycle, or a "non-cyclic dead end". This prevents the algorithm from rediscovering the same cycles over and over.


Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list Most probably, this question is asked before. It's from CLRS (2nd Ed) problem 6.5-8 --

  Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a min-heap for $k$-way merging.)

As there are $k$ sorted lists and total of $n$ values, let us assume each list contains $\frac{n}{k}$ numbers, moreover each of the lists are sorted in strictly ascending order, and the results will also be stored in the ascending order.

My pseudo-code looks like this --

    list[k]   ; k sorted lists
    heap[k]   ; an auxiliary array to hold the min-heap
    result[n] ; array to store the sorted list
    for i := 1 to k                 ; O(k)
    do
        heap[i] := GET-MIN(list[i]) ; pick the first element
                                    ; and keeps track of the current index - O(1)
    done
    BUILD-MIN-HEAP(heap) ; build the min-heap - O(k)
    for i := 1 to n
    do
        array[i] := EXTRACT-MIN(heap)   ; store the min - O(logk)
        nextMin := GET-MIN(list[1])     ; get the next element from the list 1 - O(1)
        ; find the minimum value from the top of k lists - O(k)
        for j := 2 to k
        do
            if GET-MIN(list[j]) < nextMin
                nextMin := GET-MIN(list[j])
        done
        ; insert the next minimum into the heap - O(logk)
        MIN-HEAP-INSERT(heap, nextMin)
    done

My overall complexity becomes $O(k) + O(k) + O(n(k + 2 \lg k)) \approx O(nk+n \lg k) \approx O(nk)$. I could not find any way to avoid the $O(k)$ loop inside the $O(n)$ loop to find the next minimum element from k lists. Is there any other way around? How to get an $O(n \lg k)$ algorithm?

The purpose of the heap is to give you the minimum, so I'm not sure what the purpose of this for-loop is - for j := 2 to k.

My take on the pseudo-code:

lists[k][?]      // input lists
c = 0            // index in result
result[n]        // output
heap[k]          // stores index and applicable list and uses list value for comparison
                 // if i is the index and k is the list
                 //   it has functions - insert(i, k) and deleteMin() which returns i,k
                 // the reason we use the index and the list, rather than just the value
                 //   is so that we can get the successor of any value

// populate the initial heap
for i = 1:k                   // runs O(k) times
  heap.insert(0, k)           // O(log k)

// keep doing this - delete the minimum, insert the next value from that list into the heap
while !heap.empty()           // runs O(n) times
  i,k = heap.deleteMin();     // O(log k)
  result[c++] = lists[k][i]
  i++
  if (i < lists[k].length)    // insert only if not end-of-list
    heap.insert(i, k)         // O(log k)

The total time complexity is thus $O(k * \log k + n * 2 \log k) = O(n \log k)$

You can also, instead of deleteMin and insert, have a getMin ($O(1)$) and an incrementIndex ($O(\log k)$), which will reduce the constant factor, but not the complexity.

Example:
(using value rather than index and list index and heap represented as a sorted array for clarity)

Input: [1, 10, 15], [4, 5, 6], [7, 8, 9]

Initial heap: [1, 4, 7]

Delete 1, insert 10
Result: [1]
Heap: [4, 7, 10]

Delete 4, insert 5
Result: [1, 4]
Heap: [5, 7, 10]

Delete 5, insert 6
Result: [1, 4, 5]
Heap: [6, 7, 10]

Delete 6, insert nothing
Result: [1, 4, 5, 6]
Heap: [7, 10]

Delete 7, insert 8
Result: [1, 4, 5, 6, 7]
Heap: [8, 10]

Delete 8, insert 9
Result: [1, 4, 5, 6, 7, 8]
Heap: [9, 10]

Delete 9, insert nothing
Result: [1, 4, 5, 6, 7, 8, 9]
Heap: [10]

Delete 10, insert 15
Result: [1, 4, 5, 6, 7, 8, 9, 10]
Heap: [15]

Delete 15, insert nothing
Result: [1, 4, 5, 6, 7, 8, 9, 10, 15]
Heap: []

Done


Why is one traversal sufficient for the Kuhn's maximal matching problem algorithm? In Kuhn's algorithm for the maximum bipartite matching problem we iterate through the vertices of one partite set and try to build the increasing chain, starting with the current vertex. Once the traversal is completed, we claim that the maximal matching is found. But why don't we need to check again the vertices for which we weren't able to build the increasing chain? How can we prove that if for some vertex v it was not possible to build the increasing chain starting with v during the traversal, then we don't need to check v again? Why shouldn't we perform the second traversal?

Kuhn's algorithm maintains the following invariant: after scanning through vertices $v_1,\ldots,v_k$ on the left, the current matching is a maximal matching of the graph consisting of $v_1,\ldots,v_k$ on the left, and the entire right-hand side. Hence at the end, we get a maximal matching of the entire graph.

How do we know that Kuhn's algorithm maintains the invariant? We prove it when we prove that Kuhn's algorithm is correct. I encourage you to find a correctness proof of the algorithm (such proofs are surely not too hard to find online) and read it.


Is the language of all $a^n$ for which $n$ has an even number of digits in 10-base system regular? Is the language $ L = \{a^n ~| ~n \text{ has even number of digits in 10-base system}\} $ regular?

My approach: let the $ p $ be from the Pumping Lemma. Chose the smallest $ n $ which has even number of digits in 10-base system, but bigger or equal to $ p $, that is $ n = 10^{2m - 1} $ for appropriate $ m $.

According to the Lemma, $ z = a^n = a^{10^{2m - 1}} = uvw $, and $ |uv| \leq p $, with $ v\neq \varepsilon $. So, we pump down $ v $, and we got the $ z' $ which should be in $ L $ (by the Lemma). That is $ uw $ should be in the language. If $ |v| $ is smaller than $ 10^{2m-1} - 10^{2m-3} $, than we reach a contradiction. If $ |v| $ is bigger, than we pump it up 10 times, to reach a contradiction again. I hope this is alright.

A slightly simpler way is to say that if you consider a string $x\in
L$ of size $p$, then there is a non-empty substring $v$ of $x$ that
you can pump without getting out of the language, if it is
regular. Then you can pump it in $x$ until it exceeds a size
$10^{2m}$, which has to be greater than $p$, such that
$10^{2m+1}-10^{2m} > |v|$. And you necessarily get the wrong number of digits.

In other words, you try to find in the sequence of possible sizes a gap
that is too wide to be jumped by pumping a constant pumping
size $|v|$.

This very simple reasonning also works with the context-free pumping
lemma.

Wide gaps, that cannot be pumped exist as soon as empty gaps can
increase in size beyond any bound. This depends on the definition of
the language.

But using the pumping lemma is often a bit more sophisticated.


Showing that CLIQUE can be verified in polynomial time The CLIQUE problem -- problem of finding the maximum clique in a graph -- is NP-complete. That is, CLIQUE is

in NP and
there is an NP complete problem, 3-SAT for one, that reduces to CLIQUE in polynomial time.

Part 2. above is fine -- all over in every resource and very well explained. For Part 1., from what I know, we need to have the following: Given a specific solution instance, we need to show that it can be verified, in polynomial time, that that solution is an answer to this problem. So for instance, given a specific graph and a subgraph of it, we should be able to check whether that subgraph is a clique of maximum size in that graph.

The resources I've read so far are phrasing this Part 1. here as "easy, straightforward, etc" or "it can be shown in $O(n^2)$ time that the given subgraph is a clique/not". However, the verification here is not just whether it's a clique, but also is whether it is a maximum clique in the graph. How can this be decided in polynomial time?

What am I missing here?

What you're missing is the difference between decision problems and optimization problems.  "Finding the maximum clique" is an optimization problem.  The corresponding decision problem is "Does there exist a clique of size $\ge k$?".  The latter problem is in NP.  NP is a class of decision problems, so it doesn't make sense to ask whether an optimization problem is in NP; that's only meaningful for decision problems.  Any textbook or standard resource on NP should explain the difference between decision problems vs. optimization problems in more depth.


How to create DFA from regular expression without using NFA? Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that?

I asked this question to our professor but he told me that we can use intuition and kindly refused to provide any explanation. So I wanted to ask you.

"Regular exp>NFA>DFA conversion" is not an option because such a conversion takes a lot of time to convert a rather complex regular expression. For example, for a certain regex "regex>NFA>DFA" takes 1 hour for a human being. I need to convert regex to DFA in less than 30 minutes.

Since you want "to convert regex to DFA in less than 30 minutes", I suppose you are working by hand on relatively small examples.

In this case you can use Brzozowski's algorithm $[1]$, which computes directly the Nerode automaton of a language (which is known to be equal to its minimal deterministic automaton). It is based on a direct computation of the derivatives and it also works for extended regular expressions allowing intersection and complementation. The drawback of this algorithm is that it requires to check the equivalence of the expressions computed along the way, an expensive process. But in practice, and for small examples, it is very efficient.

Left quotients. Let $L$ be a language of $A^*$ and let $u$ be a word. Then
$$
u^{-1}L = \{v \in A^* \mid uv \in L \}
$$
The language $u^{-1}L$ is called a left quotient (or left derivative) of $L$.

Nerode automaton. The Nerode automaton of $L$ is the deterministic automaton $\mathcal{A}(L) = (Q, A, \cdot, L, F)$ where $Q = \{u^{-1}L \mid u \in A^*\}$, $F = \{u^{-1}L \mid u \in L\}$ and the transition function is defined, for each $a \in A$, by the formula
$$
  (u^{-1}L)\cdot a = a^{-1}(u^{-1}L)=(ua)^{-1}L
$$
Beware of this rather abstract definition. Each state of $\mathcal{A}$ is a left quotient of $L$ by a word, and hence is a language of $A^*$. The initial state is the language $L$, and the set of final states is the set of all left quotients of $L$ by a word of $L$.

Brzozowski's algorithm. Let $a, b$ be letters. One can compute the left quotients using the following formulas:
\begin{align*}
a^{-1}1 &= 0  & a^{-1}b &= \begin{cases}
 1 &\text{if $a = b$}\\
    0 &\text{if $a \not= b$}\\
\end{cases}\\
a^{-1}(L_1 \cup L_2)       &= a^{-1}L_1 \cup u^{-1}L_2,&
a^{-1}(L_1 \setminus  L_2) &= a^{-1}L_1 \setminus  u^{-1}L_2,\\
a^{-1}(L_1 \cap L_2)       &= a^{-1}L_1 \cap u^{-1}L_2,  &
a^{-1}L^* &= (a^{-1}L)L^*
\end{align*}
\begin{align*}
a^{-1}(L_1L_2)             &=
\begin{cases}
  (a^{-1}L_1)L_2                 &\text{si $1 \notin L_1$,}\\
    (a^{-1}L_1)L_2 \cup a^{-1}L_2  &\text{si $1 \in L_1$}\\
\end{cases}\\
%\\v^{-1}(u^{-1}L) &= (uv)^{-1}L.
\end{align*}

Example.
For $L = (a(ab)^*)^* \cup (ba)^*$, we get successively:
\begin{align*}
1^{-1}L &= L=L_1\\
a^{-1}L_1 &=(ab)^*(a(ab)^*)^*=L_2\\
b^{-1}L_1 &= a(ba)^*=L_3\\
a^{-1}L_2 &= b(ab)^*(a(ab)^*)^* \cup (ab)^*(a(ab)^*)^*=bL_2 \cup L_2=L_4\\
b^{-1}L_2 &=\emptyset \\
a^{-1}L_3 &=(ba)^*=L_5\\
b^{-1}L_3 &=\emptyset \\
a^{-1}L_4 &= a^{-1}(bL_2 \cup L_2)=a^{-1}L_2=L_4 \\
b^{-1}L_4 &= b^{-1}(bL_2 \cup L_2)= L_2\cup b^{-1}L_2 = L_2 \\
a^{-1}L_5 &= \emptyset\\
b^{-1}L_5 &=a(ba)^*=L_3
\end{align*}
which gives the following minimal automaton.

$[1]$ J. Brzozowski, Derivatives of Regular Expressions, J.ACM 11(4), 481–494, 1964.

Edit. (April 5, 2015) I just discovered that a similar question: What algorithms exist for construction a DFA that recognizes the language described by a given regex? was asked on cstheory. The answer partly addresses complexity issues.


Universal Multi Head Turing Machine It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" multi head Turing machine?

No. The logarithmic overhead comes from the fact that the machine you're simulating could have an arbitrarily large state set $Q$ and arbitrarily large tape alphabet $\Gamma$. To simulate any such machine using a fixed, constant number of states and a fixed, constant tape alphabet, you need to code $Q$ and $\Gamma$ as multiple symbols in the universal machine's tape alphabet: specifically, you need $\log |Q|$ symbols to write down the current state of the simulated machine, and each character of the simulated tape will take $\log |\Gamma|$ symbols on the universal machine's tape.  (The base of the logarithm will depend on how many symbols you use: for example, simulating in binary will give logs to base 2.)

Because of this, the logarithmic slowdown is unavoidable, even if you use multiple tapes.  Indeed, if you only use a single tape, it'll be even worse than logarithmic.

However, see Shreesh's answer for a more significant source of logarithmic overhead, which is logarithmic in the running time of the simulated machine, not just the length of its description.


Why is O notation the worst case? I don't understand why O notation is the worst case. If this notations describes a function f such that 0 <= f(n) <= cg(n), we can see that in any case f will be smaller that the original function g that describes the running time. In my idea, f(n) describes a better option because the running time is less for any input n. Someone can explain me please why O notation is the worst case?

It doesn't, if $f \in O(g)$, it "just" tells us that $g$ is an asypmtotic upper bound for $f$.

This tool (asymptotic notation) can then be used to express relationships between the growth rates of functions in any context you want. One of these contexts happens to be the worst case running time of algorithms, so it's not the big-oh that makes it worst case, it's what it's being applied to.

You can quite happily use big-oh to upper bound best-case running time, average-case, in amortised analysis, space usage, or in things that have nothing to do with algorithmic complexity.


How to count all contiguous subsequences with positive sum? I have array $t$ with size $n \leq 10^6$. It has only two kinds of elements inside: $1$ or $-1$.
I need to count how many contiguous subsequences have positive sum.

This pseudocode demonstrates exactly the behavior I want, but is too slow for large $n$:

c = 0
for i = 1 to n do
    for i = j to n do
       if sum(u[i:j]) > 0 then
           c = c + 1
return c

Partial sums can be used to optimize it, but it will still be $O(n^2)$.

Here are some examples if they help:

[-1, 1, -1, -1, -1] $\rightarrow$ 1

[1, -1, 1, 1, -1, 1] $\rightarrow$ 14

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1] $\rightarrow$ 55

Does there exist linear or $n \log n$ solution?

Given the array $A_1,\ldots,A_n$, start by computing $B_i = \sum_{j \leq i} A_j$. You want to count the number of pairs $i_1 < i_2$ such that $B_{i_1} < B_{i_2}$, where $0 \leq i_1,i_2 \leq n$. Each such pair corresponds to a a contiguous subsequence $A_{i_1+1},\ldots,A_{i_2}$ whose sum is positive. This is the same as the classical problem of counting the number of inversions in an array (this is what you get if you reverse $B$), which can be solved in $O(n\log n)$.

It is plausible that you can do better in your case since the numbers are $\pm 1$.


Candy Problem for k size window I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) solutions.
Now, I was thinking about the generalized problem which consider k neighbors(i.e. for the ith child we have to consider children from max(1, i-k)th place to min(n, i+k)th place) rather considering only one neighbour.
So, the problem is basically for every i in range[1, n] distribute candies in the children from max(1, i-k) to min(n, i+k) in such a way that each one gets at least one candy and if there are p children who have higher rating than ith child inside the window, then they will get more candies than the ith child.
Is there any linear time solution for this?

Compute the sorted scores (and associated children) in the first window with a persistent sorted tree. This step takes $O(k \log k)$ time.
Create a DAG on children and add a directed edge from each child to each other child who is between $p$ and $2p$ places lower than it. This step takes $O(pk)$ time.
Shift the window forward one child at a time. Incrementally update the tree to obtain a new one for this window in $O(\log k)$ time per tree.
In each tree in step 3, place directed edges between pairs of children of distance $p$ where the child that entered the window in this tree is in between the children in the pair. This can be done in $O(p)$ time per tree (avoiding a $\log k$ factor) if one starts at the node obtained by insertion in step 3.
Assign candies to children topologically: each leaf child gets 1 candy; each internal child gets max(child's candies) + 1 candies. This runs in $O(n)$ time.
Sum the candies.

Note: the DAG with all of the edges from steps 2 and 4 sorts children by relative number of candies.

The resulting algorithm runs in $O(n(p+\log k))$ time.


What's a fast algorithm to decide whether there is an $A_G$ corresponding to a given $\chi_G(\lambda)$? Given an adjacency matrix $A_G$ of an undirected graph $G$, it is easy and straightforward to compute the characteristic polynomial $\chi_G(\lambda)$. What about the other way around? The problem can be formulated as follows.

Problem Given a polynomial $P$, decide whether there is a graph $G$ with the corresponding adjacency matrix $A_G$ such that its characteristic polynomial $\chi_G(\lambda)$ equals the given $P$.

For an arbitrary $P$, it is not always the case that there is a corresponding $A_G$. The naive exhaustive algorithm for the problem uses a basic theorem in algebraic graph theory:

Theorem Let $G=(V,E)$ be a graph with adjacency matrix $A_G$ and $\chi_G(\lambda) = \lambda^n+c_1\lambda^{n-1}+c_2\lambda^{n-2}+\cdots+c_{n-1}\lambda+c_n$, then
(1) $c_1=0$,
(2) $-c_2 = |E|$, and
(3) $-c_3 = \text{twice the # of triangles in G}$.

Now, given $P$, the algorithm goes through every candidate $A_G$ of a corresponding $G$ with $|E|=-c_2$ and number of triangles ($K_3$) equal to $-c_3$. For each $A_G$, compute $\text{det}(A_G - \lambda I)$ and see if it equals the given $P$. If none match, return false. Otherwise, return the $A_G$.
This works, but is clearly not fast. The exhaustive algorithm would work even without the above theorem. Its use makes the search space smaller. What's a fast and more clever algorithm?

The short answer is no. No quick algorithm for this problem is known.

A big open problem (for at least 50 years) in algebraic graph theory asks about  the existence a regular graph of degree 57 order 3250 girth 5 and diameter 2. This is known as a Moore graph.

However, it is known that if such a graph exists its characteristic polynomial has to be $p(x) = (x-57)(x+8)^{1520}(x-7)^{1729}$ [1, Proposition 1].

So if there would be a quick solution to your problem, this big open problem would  be solved already.

In fact, the theorem that you stated can be further generalized. The $i$'th coefficient of the characteristic polynomial of $G$ is given by $$(-1)^{i}c_i = \sum (-1)^{r(H)} 2^{s(H)}$$ where the summation is taken over all subgraphs $H$ of $G$ that have order $i$ and whose connected components are $K_2$ and cycles. The function $s(H)$ counts the number of components of $H$ that are cycles while $r(H)$ denotes the rank of $H.$

[1] M. Macaj, J. Siran. Search for properties of the missing Moore graph, Linear Algebra Appl., 432 (2010), 2381–2398.


The Communication Complexity of Majority, What does Bob send to Alice? Can Bob just wait for Alice's input? I'm following along the examples in https://people.csail.mit.edu/rrw/6.045-2020/note-cc.pdf
and in specifically the following text:

What’s a good protocol for computing MAJORITY? The natural thing to do
is to have Alice and Bob send the vote counts! Over multiple rounds,
when it’s Alice’s turn, she sends bits of the integer $N_x$ which is the
number of 1s in $x$, Bob computes $N_y$
which is the number of 1s in $y$, and Bob sends 1 to Alice if and only if $N_x+N_y$ is greater
than $n$. (Note the total number of voters is $2n$.) If Alice sends $N_x$
encoded in binary, this takes $O(\log n)$ rounds. We therefore have:

If Alice is sending her total number of 1s over $\approx \log n$ bits to Bob ... what is Bob sending in back in return before the Alice is done with her input? I assumed or thought that in communication complexity, Alice and Bob are always taking turns back and forth right? Can Bob not send anything and just wait for Alice to send the $\log n$ bits?

Yes it's perfectly fine for one player to send multiple bits while the other waits. In fact, "the" trivial upper bound on communication complexity is having one party send its input to the other one, who can then compute the output locally (although note that there are some very nice and non-trivial probabilistic algorithms -- e.g. for EQ -- even for one-way communication, where Alice can talk to Bob but not the reverse). A deterministic communication protocol specifies, as a function of the transcript so far, if Alice or Bob should speak next. Additionally it always specifies when the communication has ended.
Ryan Williams' notes, which you linked, deals at first with the simplified setting:

In general, Alice and Bob will speak one bit each, in rounds. Alice will always start the communication, and speak one bit in odd-numbered rounds.  Bob will always speak a bit in even-numbered rounds.

If you only care about communication complexity and not round complexity, you can replace the above with "Alice and Bob will speak at most one bit each, in rounds [...]" to capture the more general case.


Definition of a regular language I'm a little confused by Wikipedia's definition of a regular language:

  The collection of regular languages over an alphabet $\Sigma$ is defined recursively as follows:

  The empty language $\emptyset$ is a regular language.
  For each $a \in \Sigma$ ($a$ belongs to $\Sigma$), the singleton language ${a}$ is a regular language.
  If $A$ and $B$ are regular languages, then $A \cup B$ (union), $A \cdot B$ (concatenation), and $A^\ast$ (Kleene star) are regular languages.
  No other languages over $\Sigma$ are regular.

This seems defines a regular language as any set that contains a finite number of unique elements, though the set can be countably infinite (it's worth noting that the article doesn't explicitly state that $\left\vert{\Sigma}\right\vert$ is finite in the definition), i.e., a regular language is any set $S$

$$
\left\vert{S}\right\vert \le \left\vert{\infty}\right\vert, {S} \in \Sigma \\
\left\vert{\Sigma}\right\vert \lt \left\vert{\infty}\right\vert
$$

I think this is correct because the union, concatenation or Kleene star of a singleton that is part of a finite set or the empty set must be also part of that set, even when operated on recursively.

It's been a fair while since I did any maths, and even longer since I've touched set theory. Have I completely misread Wikipedia's definition? If so, how? If I haven't how is a regular language different from my definition?

Regular languages over a finite alphabet are always countable: indeed, $\Sigma^*$ is countable. However, not every subset of $\Sigma^*$ is regular. This is because the set of regular languages is only finitely additive rather than $\sigma$-additive. That means that if $A_1,\ldots,A_\ell$ are regular then so is $A_1 \cup \cdots \cup A_\ell$, but the same isn't true for an infinite sequence. Indeed, every subset of $\Sigma^*$ can be written as an infinite sum of singletons (sets of size $1$), which are regular, but not all subsets of $\Sigma^*$ are regular. For example, the following subset of $\{0,1\}^*$ isn't: $\{ 0^n 1^n : n \geq 0 \}$.

You define a regular language as one which has a finite number of unique elements. Unfortunately, you don't define what these unique elements are, so your definition is vague at best. Regular languages have other definitions than the one given by Wikipedia - for example, they are the languages accepted by deterministic finite automata, by non-deterministic finite automata, and by Turing machines running in time $o(n\log n)$. Each of these has a finite number of states, which might correspond to your unique elements. A third approach defines a regular language as one having finitely many Myhill-Nerode equivalence classes (two words $x,y \in \Sigma^*$ are equivalent with respect to a language $L$ if for all $z \in \Sigma^*$, $xz \in L$ iff $yz \in L$).

Here is a Wikipedia-like definition of the regular languages (both definitions are the same for finite $\Sigma$). It is the smallest collection of languages which:

Contains all singletons $\{a\}$ for $a \in \Sigma$.
Closed under finite unions and intersections, under complementation, under concatenation, and under Kleene star.

Every regular language has a "proof" of its being regular which comes from applying the operations above. In the case of the Wikipedia definition, this proof is a regular expression, which is why they chose their particular definition. For example, $0^*1^* + 1^*0^*$, the language of "monotone" sequences over $\Sigma = \{0,1\}$, can be derived as follows from Wikipedia's rules:

$0$ is regular (singleton axiom).
$0^*$ is regular (Kleene star applied to (1)).
$1$ is regular (singleton axiom).
$1^*$ is regular (Kleene star applied to (3)).
$0^*1^*$ is regular (concatenation of (2) and (4)).
$1^*0^*$ is regular (concatenation of (4) and (2)).
$0^*1^* + 1^*0^*$ is regular (union of (5) and (6)).

My rules are more permissive: they allow complementation and intersection. You can try to prove that both definitions are equivalent - this is quite difficult from these definitions, but becomes much easier using either DFAs (deterministic finite automata) or Myhill-Nerode relations.


For which c, d is Gap2SAT[c, d] in P (such that 0<c<d<1)? For which $c, d$ is $Gap2SAT[c, d]$ in $P$  (such that $0<c<d<1$)?

(I know if d=1 then for each c it will be in P, however with which c,d such that  $0<c<d<1$ can I simply return YES?)

Assuming the Unique Games Conjecture, your problem is solved for MAX-CUT in Ryan O'Donnell and Yi Wu, An optimal SDP algorithm for Max-Cut,
and equally optimal Long Code tests, who determined the gap curve for this problem.

I am not aware of any such work for MAX-2SAT, but Per Austrin has essentially determined the optimal approximation ratio (again, assuming the Unique Games Conjecture) in his paper Balanced MAX 2-SAT might not be the hardest.

In celebrated work, Prasad Raghavendra has essentially determined the optimal approximation ratio for any constraint-satisfaction problem, again assuming the Unique Games Conjecture.


Any significance to why a lot of big names in AI have math PhD? I've been looking into AI research and I've noticed a nontrivial amount of individuals either received a PhD in math or had advisors who received a PhD in math. Some names include (Ben Goertzel, Marvin Minsky, Jürgen Schmidhuber).

I can see how a formal (arguably more difficult) training in math would help tackle issues in AI, but it'd make more sense to do a PhD in AI if one wants to make a career studying AI, no?

In contrast, all the high impact papers for top machine learning conferences (KDD, ICML, NIPS) were mostly from CS labs, but I cannot say that this is the norm in other AI subareas.

Is it actually better to do a PhD in math and do research in a topic that converge with AI?

All computer science is born out of Math.  The are a lot of computer programmers, web designers and the like who may not have math background, but they do not count as as computer scientist.

AI and other machine learning is all based on Math and statistics, so even going for a PhD in AI would mean that would have to learn a significant amount of math anyway.


Understanding the Diameter Constrained MST Problem I am interested in understanding the DCMST problem, explained in this paper (http://www.dcc.ic.uff.br/~celso/artigos/cpdcmst.pdf). I don't think I understand it as I should. Here is how I understand it, we have a undirected connected graph $G=(V,E)$, a cost $c$ for every edge $e(i,j) \in E$ and a value $d$ we want to find an minimum spanning tree whose diameter is at most $d$. This paper say's that the diameter is of a tree is equal to the number of edges in
the longest path between any pair of its nodes. Does this mean that the cost or weight of the edges are not considered when computing the diameter, in other words the weights do not add any meaning for the diameter? To compute the diameter we treat every edge as constant $1$? But I would assume the weights have meaning for the MST? Also, what are we minimizing here, the spanning tree or the diameter, because I don't think it can be both?

Clearly, I am misunderstanding something here. Could someone explain this problem in more detail? I've been cracking my head with this problem for some days now.

For example if we find an MST with $k$ diameter less than $d$ , and a spanning tree with a lower diameter than k but it's total weight is greater then the MST we found prior, the correct solution would be the MST because it is most minimum and the diameter constraint is satisfied, and does not need to be the most minimum diameter? or which is the correct solution and why?

The diameter of a graph is the longest shortest-path distance over all pairs of vertices. This distance can be measured in terms of edge weights or in terms of number of edges (which is known as geodesic distance). The measure that you choose depends on your particular application. In the paper that you mention, the authors focus on geodesic distance.

When you want to obtain a Minimum Spanning Tree (MST), you focus on edge weights because all spanning trees have the same number of edges: $|V|-1$.

Aiming for an MST that is constrained by a maximum diameter is perfectly possible. The authors of the paper are not setting two conflicting optimization goals, but, rather, just adding an additional constraint to the MST problem. Adding this contraint, however, turns the MST problem into an NP-Hard problem (even though computing the diameter of a graph and obtaining an MST, separately, are problems that can be solved in polynomial time).

To gain further insight into the notion of diameter (in the context of MSTs), consider the following example:

The spanning tree on the left (whose edges are highlighted in red) is minimum. Its total weight (i.e., the sum of the weights of its edges) is 7 and its diameter is 5 (because the vertices that are farthest from each other are 5 edges apart). If we add the constraint that the diameter must be at most 2 (that is, $d=2)$, then the diameter-constrained MST is the tree on the right. Its total cost is 12 (higher than the tree on the left), but it is the only spanning tree whose diameter (ignoring weights) is $\leq 2$.


Analyze undirected weight graph and generate two sub graphs I have a weighted undirected graph $G_0$, from which I want to derive weighted undirected graphs $G_1$ and $G_2$.

All nodes in $G_0$ have a degree of at least one.
$G_1$ and $G_2$ can contain the same node but not the same edge.
All nodes in both $G_1$ and $G_2$ should have a degree of at least one.
All edges from $G_0$ should be contained in either $G_1$ or $G_2$
Both $G_1$ and $G_2$ are subgraphs of $G_0$ and cannot contain additional nodes.
Edit (Added constraint): $G_1$ and $G_2$ are both traversable trails

Let's assume that the sum of all the edges in $G_0$ is $x$.

I need to find the pair of $G_1$ and $G_2$ for which the sum of all edges in $G_1$ is closest to $x/2$.

How would you go about solving that?

Edit: After much hassle due to my lack of explanatory powers, here is a better explanation of the problem (this is for an unweighted graph, but it will at least point me in the general direction of a suitable algorithm, also it avoids technical terms because is obvious that I struggle understanding them at the moment)

Lets assume that we have an undirected Graph with Vertices A,B,C,D,E

A --- B
|   / | \
|  /  |  C
| /   | /
D --- E

Which means an adjacency matrix like this one:

  A  B  C  D  E
A -  1  0  1  0
B 1  -  1  1  1
C 0  1  -  0  1
D 1  1  0  -  1
E 0  1  1  1  -

Assuming all edges are undirected, we have the following edges:

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

What I want is to generate two groups of edges of roughly the same size. (In this particular case, since we have 7 edges, we would get a group of 3 edges and another one of 4 edges.

Group 1: (a,b) (a,d) (b,d) (e,d)
A --- B
|   /
|  /
| /
D --- E

Group 2: (b,e) (b,c) (e,c)
B
| \
|  C
| /
E

Notice that all edges in each group are connected by at least one node, that is a requirement.

Another valid solution could be, for example:

Group 1: (d,a) (a,b) (b,c) (c,e)
A --- B
|      \
|       C
|      /
D     E

Group 2: (d,b) (b,e) (e,d)
      B
    / |
   /  |
  /   |
D --- E

And so on, as you see there are many valid solutions but I want to know if there's an algorithm to find one.

Sorry about the poor explanation, but after a lot of help here, Stack Overflow and Math Exchange and a lot of reading, I finally understood that what I'm actually trying to do is:

Given a Graph G, obtain two disjointed trails of approximately the same size so that every edge is visited by one of those trails.

Thanks to everyone!


An one-sentence proof of P ⊆ NP Recently I am reading a document [1]. In this document, Prof. Cook provides a brief proof of $\mathbf{P} \subseteq \mathbf{NP}$, which is only one sentence:

  It is trivial to show that $\mathbf{P} \subseteq \mathbf{NP}$, since for each language $L$ over $\Sigma$, if $L \in \mathbf{P}$ then we can define the polynomial-time checking relation $R \subseteq \Sigma^* \cup \Sigma^*$ by
  $$R(w, y) \Longleftrightarrow  w \in L$$
  for all $w, y \in \Sigma^*$.

I know the definitions of $\mathbf{P}$ and $\mathbf{NP}$, as in [1], but I still can't understand this proof. Could any one explain the proof to me? Even one sentence is good.

By the way, I think $\Sigma^* \cup \Sigma^*$ should be $\Sigma^* \times \Sigma^*$. Am I right?

Reference

[1] S. Cook, The P versus NP problem, [Online] http://www.claymath.org/sites/default/files/pvsnp.pdf.

Since L is in P, you can answer the word problem in polynomial time. To show that L is in NP as well, we need to provide a polynomial checking relation $R$ such that

$$ w\in L \Leftrightarrow \exists y.(|y|\le |w^k| \text{ and } R(w,y))$$

Now Prof. Cook says to take a very simple $R$. For every $w$ in $L$, no matter what $y\in \Sigma^*$ you take, $R(w,y)$ is true and for every $w$ not in $L$, $R(w,y)$ is false, regardless of the $y$. This is a polynomial time relation, since we can decide whether $w\in L$ or not in polynomial time (since $L \in P$), without looking at $y$ at all. And as any $y$ works, there are also some $y$ that are short enough to satisfy the length restriction in the above definition.


Can a Turing Machine be defined over many languages? What does it mean, if possible, for a Turing machine to be defined over many languages?

A Turing machine isn't defined over a language.

Given a Turing machine $M$, we can define the language of inputs on which $M$ halts; or the language of inputs which $M$ accepts; or the language of inputs which $M$ either accepts or doesn't halt on; and so on.

Usually we are interested in either the language of all inputs on which $M$ halts, or (for a machine halting on all inputs), in the language of all inputs which $M$ accepts.


How does treewidth behave under graph minor operations? It is a well-known fact that for any minor H of a graph G (commonly written as $H \leq_m G$), the treewidth of H is smaller than or equal to that of G.

Minors of a graph are created through the operations of (1) vertex deletion, (2) edge deletion and (3) edge contraction. I am curious as to whether one can bound the decrease in treewidth when applying any single operation from (1)-(3).
Of particular interest for me is the question whether said decrease can always be bounded by some constant.

The decrease in tree width of any of the three operations will be 0 or 1.  The proof is simple (I will take the case of the vertex deletion).

Let $G$ be the original graph and $G' = G - v$ be the graph obtained by deleting $v$.

Let $T'$ be an optimal tree decomposition of $G'$, with $\text{tw}(G') = w'$.

Now, construct $T$ from $T'$ by adding $v$ to every bag of $T'$.  Clearly, $T$ is a tree decomposition for $G$ with width $\text{tw}(G) \leq \text{tw}(T) = 1 + \text{tw}(G') = 1 + w'$.


Does Thompson's algorithm produce optimal NFAs? I'm using Thompson's algorithm to convert from a regular expression to a NFA.  Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of states?

For instance, consider this example.  I have the regular expression $(a|b)$.  According to this website, Thompson's algorithm converts it to the following NFA:

   o--->o
  /ε  a  \ε
>o        O
  \ε  b  /ε
   o--->o

However, the following NFA is smaller and seems like it would also be equivalent:

   o
 a/ \ε
>o   O
 b\ /ε
   o

Why doesn't Thompson's algorithm output the latter NFA?  What did I miss here? Is that Thompson's construction algorithm not optimized at all?

Minimizing NFAs is known to be PSPACE-hard: Meyer and Stockmeyer showed that given an NFA, it is PSPACE-hard to find the size of the minimal equivalent NFA, and Jiang and Ravikumar showed that given a DFA, finding the size of the minimal equivalent NFA is PSPACE-hard. Later some hardness of approximation results were proved, showing that it is even hard to approximate the size of the minimal equivalent NFA. See these lecture notes by Artem Kaznatcheev for more details.

Since a regular expression can be converted to an NFA of comparable size using Thompson's algorithm, these hardness results show that we can't expect any efficient algorithm to convert an regular expression to a minimal-size NFA.


Type theory for imperative programming languages? The type theory that I have seen is all developed over lambda calculus, which is an inherently functional language.

Nevertheless, in practice imperative languages have type systems. Are there differences in the type theory for imperative vs functional languages?

Sure there are type systems for all sorts of programming languages, including the imperative ones. It's probably best to look at something simple first that exposes the gist of the matter. A classic is John Reynold's The essence of algol, which was quite influential historically, and develops many important ideas.


Proof of big-o propositions I don't understand the proof of below sentences.

$O(f(n))=O(g(n)) \iff \Omega(f(n))=\Omega(g(n)) \iff \theta(f(n))=\theta(g(n))$
$f(n)=\theta(g(n)) \iff g(n)=\theta(f(n))$

How can I prove these statements?

We will be using the following definitions:

  Let $f\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ be a function mapping positive integers to positive integers.

  The class $O(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $C>0$, for all $n \in \mathbb{Z}_+$ we have $g(n) \leq Cf(n)$.

  The class $\Omega(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $c>0$, for all $n \in \mathbb{Z}_+$ we have $g(n) \geq cf(n)$.

  The class $\Theta(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $C,c>0$, for all $n \in \mathbb{Z}_+$ we have $cf(n) \leq g(n) \leq Cf(n)$.

  We also write $g(n) = O(f(n))$ instead of $g(n) \in O(f(n))$, and similarly for the other two.

These are equivalent to the more standard definition in which the above only has to hold for large enough $n$. You can also carry out the proofs below using the standard definitions — this entails only small changes.

Let's start with the second statement: $f(n) = \Theta(g(n))$ iff $g(n) = \Theta(f(n))$.

Suppose that $f(n) = \Theta(g(n))$. Then there exist $C,c>0$ such that for all $n$ we have $cf(n) \leq g(n) \leq Cf(n)$. Therefore for all $n$ we have $C^{-1} g(n) \leq f(n) \leq c^{-1} g(n)$, and so $g(n) = \Theta(f(n))$. Similarly, if $g(n) = \Theta(f(n))$ then $f(n) = \Theta(g(n))$.

Now let us go back to the first statement: $O(f(n)) = O(g(n))$ iff $\Omega(f(n)) = \Omega(g(n))$ iff $\Theta(f(n)) = \Theta(g(n))$.

Suppose that $O(f(n)) = O(g(n))$. It is easy to check that $g(n) = O(g(n))$ (take $C = 1$), and so $O(f(n)) = O(g(n))$ implies that $g(n) = O(f(n))$. That is, there exists $D>0$ such that $g(n) \leq Df(n)$ for all $n$. Similarly, $f(n) = O(g(n))$, and so there exists $E>0$ such that $f(n) \leq Eg(n)$ for all $n$. Suppose now that $h(n) = \Theta(f(n))$. Then there exist $C,c>0$ such that $cf(n) \leq h(n) \leq Cf(n)$ for all $n$. This implies that $cD^{-1} g(n) \leq h(n) \leq CEg(n)$, and so $h(n) = \Theta(g(n))$. Similarly, if $h(n) = \Theta(g(n))$ then $h(n) = \Theta(f(n))$, and so $\Theta(f(n)) = \Theta(g(n))$.

Similarly, if $\Omega(f(n)) = \Omega(g(n))$ then $\Theta(f(n)) = \Theta(g(n))$.

Conversely, if $\Theta(f(n)) = \Theta(g(n))$ then, as before, $f(n) = \Theta(g(n))$. This means that there exist $C,c>0$ such that $cg(n) \leq f(n) \leq Cg(n)$ for all $n$. Now suppose that $h(n) = O(f(n))$. Then there exists $D>0$ such that $h(n) \leq Df(n)$ for all $n$. Since $h(n) \leq Df(n) \leq DCg(n)$, we see that $h(n) = O(g(n))$. Similarly, if $h(n) = O(g(n))$ then there exists $E>0$ such that $h(n) \leq Eg(n)$. This implies that $h(n) \leq Ec^{-1} f(n)$, and so $h(n) = O(f(n))$. Thus $O(g(n)) = O(f(n))$. Similarly, $\Omega(g(n)) = \Omega(f(n))$.


what is a shearlet/shearlet transform and how can i use it? from what wikipedia says shearlet is a successor to wavelets(whatever that is) and that they are extremely good at representing complicated data efficiently. But neither wikipedia nor other articles that i found have any layman definition of shearlets in it. A layman definition would be great and algorithm to implement them on say images would be awesome and a python implementation would be godsend.

Shearlets are a family of basis functions. Cartesian coordinate systems have already made you familiar with orthonormal basis functions: scaling up a rightward- and an upward-pointing unit vector lets you express any (x, y) point in the plane.
Suppose you are Seurat, the pointillist, and you have a budget of 100 brushstrokes with which to express a monochromatic landscape. In addition to (x, y) information we can also give each stroke a radius r, for big blobs or fine dots. This is not too far away from a wavelet representation of the landscape.
Linear features like grass or tree limbs will be a poor fit for such a scheme, requiring many dots. Imagine replacing circles with ellipses of defined aspect ratio and orientation, a and theta, or in your case replacing them with parabolic shapes of defined narrowness and orientation. This is not too far away from a shearlet representation. It uses a shearing transform, rather than an angular rotation transform, as the math works out more conveniently that way. The rubber sheet deformation of shearing expresses the direction of each landscape feature, and resembles rotation. In fact, a sequence of three shears can rotate an image exactly.
For an implementation you should refer to https://github.com/stefanloock/pyshearlab or http://shearlab.org. Quoting the latter:

... shearlet systems are particularly well adapted to represent anisotropic features (such as curves) that are often crucial in multidimensional data. The resulting representation has proven well-suited for image processing tasks such as inpainting, denoising or image separation. ...
Similiar to wavelet systems, shearlet systems are constructed by modifying generator functions. For wavelet systems, these functions are isotropically scaled and translated. While this is enough to provide an optimally sparse representation for an interesting class of 1D functions it fails to do so in higher dimensions. To compensate this shortcoming, the direction of the generator functions has to be varied. In shearlet theory, this is accomplished by shearing and anisotropic scaling.


What is considered arithmetic when dealing with bits? In a recent homework question we were asked to implement a program that would use only bitwise operations. From our notes, this includes & | ^ ~ >> << and >>>. We are not allowed to use arithmetic operations, or loops.

Since immediately addition can be defined with the above accepted operators, what constitutes "arithmetic"? Would unary operations be allowed?

For example, I could define incrementation and decrementation using ~ and the unary -, and recursively call both until the decremented number reached 0, meaning both numbers were added (think addition in brainfuck). Is this arithmetic?

A program that uses only bitwise operations is just that – a program which only uses bitwise operations. Bitwise operations are universal, that is, you can define any function using them. What makes things interesting is that we care about the complexity of implementing a given function using only bitwise operations.

In particular, suppose that we only care about the complexity up to multiplicative constants (i.e. we only care about the big O). Any operation which can be implemented using a constant number of bitwise operations is admissible – the resulting notion of complexity is the same (up to multiplicative constants). So if you can implement addition using a constant-size formula, then you are welcome to use addition.

The constraint doesn't mean that at no point of your program are you allowed to compute by chance some arithmetic function – it just means that the basic operations you are allowed are only the bitwise ones.


Linux OS/HW VM cooperation From what i've learned, the HW is responsible for setting the accessed and dirty bits in the PTE of a process, and the OS is responsible for turning them off.
My question is why?
The first part, i think is because only the HW is preforming the page table walk and it's a good opportunity for it to set them (because by doing the page walk or checking the tlb, it implies that a process wanted to access/write to a page).
Does the second part have something to do with the fact that the OS manages the page cache and all the paging to the disk go through it?

Why?  Because this design works pretty well and meets the requirements, and most alternative don't or would be more expensive or slower.  In particular, this division of responsibilities lets the system implement a suitable page replacement policy for virtual pages in a way that is relatively efficient.

When asking a "why is it done this way?", it's often helpful to try to imagine some concrete alternative way of doing it, and then analyze the advantages and disadvantages of the current method compared to that alternative.  You haven't listed a specific alternative, so it's hard to be a lot more specific.  But for instance if you tried to do it all in software (so the OS has all responsibility), without the hardware managing the accessed or dirty bits, that would be very difficult: the only methods I can think of for doing that are clunky and will cause many context switches and thus will slow down the system a lot.


Can a graph have a cycle containing all nodes but not Hamiltonian? Is it possible for a graph to have a cycle that goes through all the nodes, but it does not have a Hamiltonian cycle (i.e. the cycle goes through some nodes more than once)? If yes, can anyone prove it? If not, can anyone give a counterexample?

Just pick a tree which - by definition - doesn't have any simple cycle, but is connected, so you can visit all the nodes and return to the starting one but you must pass on some nodes more than once.

There are also graphs which have an Eulerian cycle (a cycle that traverses every edge exactly once) but not an Hamiltonian cycle. For example pick a graph made with two triangles having one vertex in common.


Using Subset Sum algorithm $O(n)$ times to find the subset Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given number. I was asked to use this algorithm (however it is implemented) at most $O(n)$ times to build a subset which satisfies the sum. My solution is given below:

    findSubset(A[1,...,n], sum){
      if(blackBox(A,sum)){
        for i = 1 to n do
          if(blackBox(A - A[i], sum))
               return findSubset(A - A[i],sum);
          endif
      return A;
      }else
        return [];
      endif
    }

The problem with this solution is that it uses the subSetSum algorithm $O(n^2)$ times. As a hint to optimize the problem to $O(n)$ is that I should not use the loop and appeal only to recursion. Can anyone give a hint for an optimal solution to this problem?

Suppose that $\mathit{sum}$ is the sum of some subset of $A[2],\ldots,A[n]$. Then you can just remove $A[1]$.

Conversely, if $\mathit{sum}$ is not the some of any subset of $A[2],\ldots,A[n]$, then any subset summing to $\mathit{sum}$ must contain $A[1]$. Therefore it consists of $A[1]$ together with a subset of $A[2],\ldots,A[n]$ summing to $\mathit{sum}-A[1]$.

Either way, we have eliminated $A[1]$. We can then go on and eliminate $A[2],\ldots,A[n]$ in sequence.