CPU cache - retrieving data from memory Regarding CPU cache, if the CPU does not find the data it needs in the cache, I understand it then looks for it in the main memory (RAM). (Let's assume we have only one level of cache in order to keep this question as simple as possible.)

My question is this: if the data is found in main memory, what happens? Does the processor use this data directly, or is the data loaded into the cache and then read from there?

Nobody can say what every computer will do, but there are some reasonable assumptions.

When you access data that is not in the cache, you want it to be in the cache afterwards. So the CPU will read the data from memory, and move it to the cache. That's one half of the job.

There is some part of the CPU that needs the data, and we want to get the data to that part of the CPU as fast and as cheap as possible. There is already a mechanism in place to provide the data if it is in the cache. So the CPU could just move the data to the cache, then use the existing mechanism. That's cheap and easy.

Or the CPU can move data from memory to the place where it is needed either simultaneously with the cache, or even before the data is moved to the cache. That has the advantage that the data may appear a little bit faster where it is needed. It has the disadvantage that now the two situations (in cache, not in cache) need to be handled by different hardware. That is likely more complicated and more expensive.

Which one is chosen depends on how much quicker the more complicated method is, how much it costs more, and how much the cost is compared to other possible improvements.


Variation of knapsack problem I have a menu of n items, with each item having a value. Given the total amount spent, I have to figure out all the possible combinations of items purchased. Example, I have three menu items:

item 1: $4

item 2: $5

item 3: $8

with the total purchase price = $14

There is only one solution in the case, 1 purchase of item 1 and 2 purchases of item 2.

How do I go about solving this?

This is called the subset sum problem.  There's lots written about the problem; go read about it.

How you could have figured this out on your own: you already know it is a variant of the knapsack problem, so if you had read the Wikipedia page on the knapsack problem, you would have encountered a description of the subset sum problem in the section of that page on variations of the knapsack problem.  In the future, I encourage you to do  research before posting, to make sure your question isn't already answered in the obvious places (e.g., Wikipedia, textbooks).


is the empty language L = ∅ a subset of every languages? I need to show false the following claim

  Every language L which is a subset of $A_{TM}$ ($L \subseteq A_{TM}$) is undecidable.

For this, I wish to use the empty language L = ∅ (I know is decidable).

Is it correct that the empty language L = ∅ is a subset of every languages (and also of $A_{TM}$)?

Yes. Remember that $A\subseteq B$ just means "every element of $A$ is also an element of $B$." In case $A=\emptyset$, this is trivially true ("vacuously true") regardless of what $B$ is.

It may also help to think in terms of counterexamples: $A\subseteq B$ is the "default" situation, and is only false if there is a counterexample: some $x\in A$ with $x\not\in B$. Since there are no $x\in \emptyset$ in the first place, there are never any counterexamples to $\emptyset\subseteq B$ (again, regardless of what $B$ is).

It's worth mentioning that there are less trivial solutions to this problem as well. For example, fix some $a\in A_{TM}$. The padding lemma then builds us a computable infinite set $A\subseteq A_{TM}$ of "equivalent versions" of $a$ (not everything "equivalent to" $a$ shows up in $A$, but infinitely many things do).

And even more is true - $A_{TM}$ is computably enumerable, and we have the following general fact:

  Every infinite computably enumerable set has an infinite computable subset.

This is a good exercise. HINT: think about the fact that any computably enumerable set which we can enumerate "in order" is computable.


Is there a term for "delegate" function in CS? This question is all about terminology (names).

When you consider "list", this term is well defined in CS -- despite the fact programming languages use and misuse this term (for example C# List is not a list).

I am looking for term in Computer Science domain that C++ defines as pointer to a function, C# as delegate, Swift as closure. Consider a function A that takes another function B as a parameter -- is there established term for B? Functor?

I cannot know all the parochial terminologies and concepts used by the
great variety of the many - sometimes disputable - language designs
available in computer science. Some design choices may be motivated by
issues that are only remotely connected with science. But there is
also some more or less established terminology.

When a function A takes a function B as parameter, that is simply
called a functional parameter.

A function can be seen as composed of a control part (the code or
instructions) and of an environment of entities used by the control.
This environment comprises usually two kinds of program entities:

local entities that are normally intended to be used during the
lifetime of a call to the function, that have distict instances for
distinct calls, and are visible only to other entities created (declared)
in the body of the function. They come into existence at each function call, usually only for the duration of that call
global entities that are defined (declared) in some (usually) enclosing structure
(function, method, class instance ...)  containing the function
declaration, hence also visible and usable by the function. They are the same for each call of the function value created by the same declaration instance.

The function code together with its associated global environment is called a
closure. The term is about 50 years old. But a closure is
essentially a functional value.

Often the conceptual closure structure can be ignored as everything
works naturally as one would hope, since a function declared in some environment usually ceases to be
accessible, thus to be used, when this environment is exited. Hence it
will no longer need what it was using there. It is however possible that a
functional value $\gamma$ leaves the environment where its has been declared, and
has to survive the disappearance of this environment where it uses some global entities. This happens mostly when another function returns $\gamma$ as a functional
result.

If function G and variable X are declared in function F,
then G can use X as a global. It may happen that the functional
value $\gamma$ of G is returned by a call to F. This is no problem
because that functional value $\gamma$ can be stored in a functional
variable (some would probably say pointer) and just used from
there. The difficulty comes from the fact that when this functional
value $\gamma$ is called, it may use the variable X of the call to
F that created $\gamma$, and terminated returning it. So special steps must be taken to preserve
X for the closure, even after the call to F has terminated, and
the corresponding environment should be no longer otherwise needed.

Actually, this occurs often in object oriented programming, for
essentially the same reason. Object orientation can be implemented in
a language that does not have it precisely by declaring an object constructor
function with local variables (the state variables of the object constructed) that
return tuples of functional values (the methods of the object class) accessing these variables.
Thus the closure concept is just a very intentional and frequent
occurrence in OO programming. Every method is essentially a closure on
the environment implementing the state of an object. At each call to the constructor, a new tuple of closures is created for the new object, corresponding to function code that does not change, but which is closed on a new environment, the local environment of the constructor call that creates the object.

As said above, a closure is just a pair composed of a function and its
globals. It is not mutable: the pair is essentially fixed when the
function is created. However, the adress of such a pair is just a
pointer to a closure, and can be stored in a variable. It can be
dereferenced and called (no big mystery). But I do not know whether
that is what C++ calls a pointer to a function, though I would hope it
is.

You may note that creation of a closure has nothing to do with caller
or callee. It has to do with the function that declares the closure,
and with the function that returns it out of the environment
where its globals are defined.

I am not experienced with C# delegates (so double check me), but they
seem just to be functional types, that can have functions, closures,
or methods as instances. This typing ensures that instances are not
misused, as might happen with untyped pointers to functions.  It is
not clear to me whether C# allows changing the closure associated with
a delegate instance, i.e. whether delegate instances are to be
considered functional variables or functional constants. From what I read, it seems to be the former, hence the comparison with function pointer. Why that is necessary to pass functions or methods as parameter is apparently due to specific features of C#. Other languages do not need anything special for that: they just declare the parameter like any other, but with a functional type (i.e. a signature).

I suggest you read the wikipedia articles on closure and possibly scoping
(though I have not read them in enough detail to vouch for their
accuracy).


Can a regular language enforce a length limit AND disallow consecutive characters? I was reading the venerable "How to Find or Validate an Email Address [using Regex]", and I came across the following statement at the bottom of the page:

  [A] true regular language cannot enforce a length limit and disallow
  consecutive hyphens at the same time.

This seems wrong to me.

I feel like if the length of a string is bounded ahead of time, you should be able to write a DFA which processes pretty much any rule on the input string, as you can just create $n$ states from the most recent states, where $n$ is the number of letters in the alphabet, repeating for the maximal length of the input string?

If this reasoning is wrong, can someone point me in the right direction?

You are not wrong. In fact, any finite language $L$ over a finite alphabet $\Sigma$ is regular. If $L$ is finite, there must be an integer $d$ such that for all $x \in L$ it holds that $|x| \le d$. Let $|\Sigma| = s$ and construct a complete $s$-ary tree of depth $d$, where each edge from a node to one of its children is a transition associated to some $c \in \Sigma$.

We can see that such a tree enumerates all the strings over $\Sigma$ of length at most $d$; this means that each string of $L$ must correspond to some node of the tree. Marking as an accepting state every such node yields a DFA for $L$.

Notice that the resulting DFA may be very ugly, but it's a valid DFA nonetheless, and that is sufficient if we are only concerned with regularity.


Given a family of hash functions in table form, how can I know whether it's universal? I've been given the following two families of hash functions:

H

and

G

Each family has three functions $\{0,1,2,3,4\} \to \{0,1,2\}$ that can be seen in the tables above. For each family I need to decide whether it's universal. I know that a family of hash functions $F$ is called universal if for every $x \neq y$, $\text{Pr}(f(x) = f(y)) \le \frac{1}{m}$ ($f$ is a function in $F$).
However, I don't understand how to calculate this probability. Should I calculate it for any one of the functions or for the whole family?

As you have stated, given a family $H$ of hash functions, the condition for universality is $\forall x,y, x \neq y: \text{P}_{h \in H}(h(x) \neq h(y)) \le \frac{1}{m}$. The probability is taken over $h \in H$, which is picked following a uniform distribution.

If you think for a while about what that means, you'll realize you need simply check whether there is at most one collision (i.e., equal entries) for any two distinct columns (i.e., every pair of $x$ and $y$) in the respective family's table. Hence, $G$ is universal, but $H$ is not; I'll let you figure out why.


Merge nodes in a graph to form a tree I have an undirected graph which may have 2 edges that connect the same pair of nodes.

A group of nodes that don't need any bridges to go from a node to another should be merged into one node in a new tree. That tree should contains such nodes and all bridges in the original graph.

What is the algorithm to solve this problem, given that the numbers of nodes and edges in the graph are smaller than 2*10^5?

What you want is to find the 2-edge-connected components of your graph.
When you have a simple graph, you can do that by finding all bridges in your graph in linear time, delete them and find the connected components in the resulting graph (every connected component corresponds to a vertex in the final graph).

Now to ensure that this works also in your case where you can have multiple edges between two vertices you can simply ignore when the above algorithm finds an incorrect bridge (u,v), where u and v are connected by multiple edges. Don't delete this edge from your graph when this happens. To detect when this happens you can first find all duplicate edges (either by sorting all edges first or using some hashing method), store those edges in a container where they can efficiently be searched (hashing or binary search) and then for every detected bridge, test if it is in that container.


prove that NDFA = { | M1 and M2 are DFAs such that there is at least one string x that is accepted by neither M1 nor M2} is decidable? How can I prove that $NDFA = \{ \langle M_1,M_2 \rangle | M_1$ and $M_2$ are $DFA$s such that there is at least one string $x$ that is accepted by neither $M_1$ nor $M_2\}$ is decidable using the fact that $ANFA = \{\langle N \rangle | N$ is an $NFA$ with some input alphabet $\Sigma$, and $L(N) = \Sigma^*\}$?

We try to decide the language $NDFA$ using a language that decides $ANFA$.

If $x$ is not in neither $L(M_1)$ or $L(M_2)$, then it means that it's not in $L(M_1) \cup L(M_2)$, in other words there is at least one string $x$ which is not in $L(M_1) \cup L(M_2)$, thus $L(M_1) \cup L(M_2) \neq \Sigma^*$ We know that we can (in finite time) construct a $NFA$, $M$ for language $L(M_1) \cup L(M_2)$. Now since $ANFA$ is decidable, $\overline{ANFA}$ is also decidable, so there is a $TM$ that can decide that $L(M) \neq \Sigma^*$, therefor the original language $NDFA$ is also decidable.


An operational semantics for lambda-calculus normal order evaluation strategy TAPL book, page 56 reads:

  Under the normal order strategy, the leftmost, outermost redex is
  always reduced first.

I understand this as a restriction of the full beta-reduction evaluation strategy, whose reduction rules are given as follows:

$$\frac{t_1 \to t_1'}{t_1 t_2 \to t_1' t_2}$$

$$\frac{t_2 \to t_2'}{t_1 t_2 \to t_1 t_2'}$$

$$\frac{t_1 \to t_1'}{λx. t_1 \to λx. t_1'}$$

$$\frac{(λx. t_1) t_2}{[x \to t_2] t_1}$$

My question is how to transform these rules so that the normal order strategy condition holds.

You can use the following rules:

$\frac{t_1 \longrightarrow t_1'}{t_1 t_2 \longrightarrow t_1' t_2}$

$(λx. t_1) t_2 \longrightarrow [x \mapsto t_2]t_1$


What is the simplest example of a prob whose complement does not have the same complexity? Firstly it is my understanding that the complement of a problem is simply the "reverse" question. So the complement of "Is the sky blue?" would be "Is the sky not blue?". Is my understanding correct?

If so, how can a complement ever be more or less complex than the original problem? Please include the simplest example that you can think of.

The notion of "complex" depends entirely on your model of computation. For example, if you're using DFAs, then by just about every conceivable measure every problem has the same difficulty as its complement. On the other hand, if you're using PDAs as your model of computation, many languages can be recognized by a PDA even though their complements can't. For example, the language

  { ww | w ∈ {a, b}* }

is not recognizable by any PDA, but its complement is.

In the land of NP, we don't know much about the relative difficulties of problems and their complements. It's an open problem whether the complements of any NP-complete problems are in NP.

Looking at decidability, a problem is decidable if and only if its complement is decidable. However, the same is not true of recognizability. The halting problem is recognizable, but its complement isn't.


How can I show that a problem is not $NP$ Consider the following image:

The problem is: can we cover the bigger rectangle with small rectangles such that no two rectangles overlap and no gap opens up? Prove that this problem is $NP-Hard$.

I know that to prove that it is $NP-hard$, I must reduce a $NPC$ problem to it.

However, I guess that the problem is not $NP$, right? For example, even if we have a "Yes" answer for the items above, how can we fit the small rectangles into the big rectangle in polynomial time?

For the above problem, the answer can includes the placement of small rectangles in the bigger rectangle. So, verifying it is easy, and the problem is $NP$.

Suppose, the question was: is there any subset of rectangles that cover the bigger rectangle so no two rectangles overlap and no gap opens up?

Then, what would be the shape of a certificate? Would it be verifiable in polynomial time? Would it be just a subset of items, or their placements too?

What if it was an optimization problem requesting a subset of items that cover the largest area of the bigger rectangle? Then, we had to check other answers to see that the certificate is the optimum one, and that would make the problem non-NP, right?

How a certificate is defined in such cases, and what is its role in categorizing a problem as $NP$ or non-$NP$?!

The only result that I am aware of (assuming your problem is computable) is the time hierarchy theorem, which implies that $NP\neq NEXPTIME$. If you have a problem that is $NEXPTIME$-hard and show that that problem reduces to your problem, you've shown your problem isn't in $NP$. Since $NEXPTIME\subseteq EXPSPACE$, an $EXPSPACE$-hard problem would work as well.

Your problem is in $NP$, however.


Is there an efficient test for if an NFA accepts a subset of another NFA? So, I know that testing if a regular language $R$ is a subset of regular language $S$ is decidable, since we can convert them both to DFAs, compute $R \cap \bar{S}$, and then test if this language is empty.

However, since this requires converting to DFAs, it's possible that the DFAs, and thus the testing algorithm, will be exponential in terms of the number of states in the input NFAs.

Is there a known way to do this in polynomial time? Has this problem in general been proved Co-NP complete?

Note that the problem is in Co-NP since a word accepted by $R$ but not by $S$ would be a polynomial certifier that $R \not \subseteq S $.

EDIT: this is incorrect, as there is no guarantee that such a word would be polynomial in the number of states.

The problem of deciding language containment in NFAs is $PSPACE$-complete. To prove this, it is easy to reduce from the universaility problem for NFAs (testing whether $L(A)=\Sigma^*$)
So, in a way, you have to determinize, but you may do so on-the-fly.

Your observation about co-NP is wrong (but nice). Such a witness can indeed be checked in polynomial time in the witness, but the shortest witness itself may be exponential in the length of the input. Since $PSPACE=co-PSPACE$, then deciding non-containment is also $PSPACE$-complete.

To state things more carefully, deciding whether $L(A)\subseteq L(B)$ is $PSPACE$ in the size of $B$ (since only $B$ needs to be complemented), and $NLOGSPACE$ in the size of $A$.


Quicksort: Probability of an element being compared to fewer than $k$ pivot elements Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements.
Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$.
Furthermore, let $d(i)$ be the number of elements that $S_{(i)}$ is compared to.
Finally, the pivot element is chosen uniformly at random.
How do I then compute the probability that $d(i) < k$ for some $k \in \mathbb{N}$?

This is not the answer to your question, but maybe you can use some elements of it.
For $i<j$, let us denote $X_{ij}$ the random variable:
$$X_{ij} = \left\{\begin{array}{rl}1 & \text{if }S_{(i)}\text{ and }S_{(j)}\text{ are compared}\\0&\text{otherwise}\end{array}\right.$$
and $A_{ij} = \{S_{(i)}, S_{(i+1)}, …, S_{(j)}\}$.
Since a comparison between two elements only occurs if one of them is a pivot, and since a pivot is never compared to other elements after the end of the partition occurring when it was chosen, we can conclude that:
$$\mathbb{P}(X_{ij} = 1) = \mathbb{P}(S_{(i)} \text{ first pivot in }A_{ij}) + \mathbb{P}(S_{(j)} \text{ first pivot in }A_{ij})$$
This is also due to the fact that if another element of $A_{ij}$ is chosen as first pivot, $S_{(i)}$ and $S_{(j)}$ will be put in two different parts of the partition.
Since the choice of the pivot is uniform, we get $\mathbb{P}(S_{(i)} \text{ first pivot in }A_{ij}) = \frac{1}{|A_{ij}|}$ and finaly $\mathbb{P}(X_{ij} = 1)  = \frac{2}{j - i +1}$.
Now, the expected number of comparisons where $S_{(i)}$ is involved is:
$$\begin{array}{rcl}
\displaystyle\mathbb{E}\left(\sum\limits_{j=1,j\neq i}^nX_{ij}\right) & = & \displaystyle\sum\limits_{j=1,j\neq i}^n\mathbb{E}(X_{ij})\\
& = & \displaystyle\sum\limits_{j=1,j\neq i}^n\mathbb{P}(X_{ij} = 1)\\
& = & \displaystyle\sum\limits_{j=1,j\neq i}^n\frac{2}{|j-i| + 1}\\
& = & \displaystyle\sum\limits_{j=1}^{i-1}\frac{2}{i - j +1} + \sum\limits_{j=i+1}^{n}\frac{2}{j - i +1}\\
& = & \displaystyle\sum\limits_{k=1}^{i-1}\frac{2}{k +1} + \sum\limits_{k=1}^{n-i}\frac{2}{k +1}\\
\end{array}$$
This analysis is generally sufficient for the analysis of the average time complexity of quicksort, because this value is $O(\log n)$. However, I am not sure as to how use part of it to find the value you want, which is:
$$\displaystyle\mathbb{P}\left(\sum\limits_{j = 1, j\neq i}^n X_{ij} = k\right)$$
Also it is not so clear that for $j\neq j'$, $X_{ij}$ and $X_{ij'}$ are independant (since for example $X_{ij}$, $X_{ij'}$ and $X_{jj'}$ are not independant because at most two of the three could be $1$).


Minimum bits needed when representing a value in a set I'm reading a paper entitled "Succincter" which discusses a compression scheme that involves encoding a value as a sequence of $M$ bits, along with a "spillover" value which can be recursively encoded.

The details of the encoding scheme are not really relevant for the purpose of this question.  Rather, I am specifically interested in asking for some clarification regarding this following excerpt from the paper:

  Assume we want to represent a value from a set $X$ . Any
  representation in a sequence of memory bits will use at least $\lceil \log_2|X| \rceil$ bits in the worst case, so it will have a redundancy
  of almost one bit if $|X|$ is not close to a power of two.

Okay, so I get the meaning here - the author is saying that if we want to represent any arbitrary element $e \in X$, then in the worst case we need at least $\lceil \log_2|X|\rceil$ bits.  But why is it $\log_2|X|$ and not $\log_2 \max X$?

For example, if I have a set $X = \{1, 2, 1e10 \}$, which contains 3 elements, I need at least $\lceil \log_2 1e10\rceil$ bits in the worst case, not $\lceil \log_2 3\rceil$ bits.

Or am I somehow misinterpreting the statement?  The only thing I can assume here is that the author is implicitly assuming some kind of mapping table over an alphabet $\Sigma$ which we use to map each element in the set to an increasing value starting at 0.  But this is never explicitly stated, and would seem to be a large assumption.

So am I missing something here?

You can encode the set $X$ using only two bits: use $00$ to encode $1$, $01$ to encode $2$, and $10$ to encode $1e10$.

More generally, the exact identity of the elements of $X$ are not important. You can encode letters of the alphabet or even words, if you want.

You haven't defined what an encoding scheme is, so let me assume that it is a uniquely decodable code. Any uniquely decodable code for $X$ must contain a codeword whose length is at least $\log_2 |X|$ (and so at least $\lceil \log_2 |X| \rceil$). This follows from McMillan's inequality.


optimizing the calculation of $\sum^n_{k=2} p(\Omega(k))\Omega(k)$ I want to optimize an algoritm for calculating $g(n)=\sum^n_{k=2} p(\Omega(k))\Omega(k)$
where $$  p(n) =
\begin{cases}
1  &\text{if $n$ is odd} \\
-1 &\text{if $n$ is even}
\end{cases}$$
and $\Omega(n)$ is the prime factor counting function or more exactly, I want to optimize calculating all it's values up to $n$
my current best try is
def Omega(k):
    Factor = 0
    b=1
    while(k>1):
        b +=1
        if (k % b == 0):
            while k % b == 0:
                k /= b
                Factor += 1
    return Factor
sum = 0
for i in range(n)
   w = Omega(i)
   sum += ((w%2)*2-1)*w
   #using it

First, I am trying to calculate the current algorithm's computational complexity.
we calculate $\Omega(k) ~~n$ times, I haven't managed to calculate $\Omega(k)$'s computational complexity but it seems to be $O(\sqrt k \log k)$ thus, I think the entire program is $O(n^{1.5} \log n)$.
Am I correct?
Can any of you help optimize my algoritm?
Note: Is this the correct exchange for this question?
Ideas:
1.Calculating $\Omega$ less,$\Omega$ is an Completely Additive function, i.e. for any $a,b$, $\Omega(ab)=\Omega(a)+\Omega(b)$, I've tried to use this to optimize the calculation, but have not managed to.
2.Optimizing the prime factorizing algoritm, I'm unsure about this.
The reason I'm interested in this is to graph the function, My current code is the first thing that went into my head, i.e, very nonoptimal.
This function is related to Liouville function.

Algorithm in the question
Although it is correct, it is rather slow. In the function Omega(k), b goes from 1 to the largest prime divisor of $k$, which is of order $\dfrac {\pi^2n} {12\,\log n}$ on average for $1 \le k \le n$ as mentioned by the On-Line Encyclopedia of Integer Sequences. So, the running time of computing $g(n)$ is $O(\dfrac {n^2}{\log n})$. It takes more than an hour to compute $g(10^6)$ on my computer.
A Faster Algorithm
Instead of computing directly the number of prime factors of each number $k$, we can add 1 to $\Omega(k)$ whenever $k$ is a multiple of a power of $p$ for all primes $p$. For example, since 72 is a multiple of 2, 4, 8, 3 and 9 but no other powers of primes, we will get
$$\Omega(72)=(1+1+1)+(1+1)=5.$$
Here is the improved algorithm.
def g(n):
    # Omega[k], for k >= 1, is the total number of prime factors
    # of k, honoring their multiplicity. Omega[0]=0 is ignored.
    Omega = [0] * (n+1)
    for k in range(2, n+1):
        if Omega[k] == 0:  # i is a prime.
            power = k
            while power <= n:
                m = power
                while m <= n:
                    Omega[m] += 1
                    m += power
                power *= k

    return sum(map(lambda x: (x % 2 * 2 - 1) * x, Omega))

On average, each $O(1)$ number of operations will yield 1 prime factor. Thus, the running time of the algorithm above is
$$O(1)\cdot O\left(\sum_{k=1}^n\Omega(k)\right)=O(n\log\log n),$$
where $\log\log n$ is the average of $\Omega(i)$ for $1\le i\le n$, as mentioned in Wikipedia. Since $\log\log n$ grows very slowly, this algorithm can be considered as an almost linear algorithm.
It took less than 1 second to run g(10^6) on my computer.


Concrete example of an admissible A* heuristic compared to Djisktra As I understand it, A* is a general form of Djikstra where the selection of the next node to visit can be based on something other than the actual distance. For example, with Djikstra, you'd use a priority queue ordered ascending by distance and shift off the head of the queue to decide where to visit next. But with A*, the order of the priority queue can be based off of the actual distance and/or another factor (the heuristic). The heuristic is considered admissible if the value it returns is guaranteed to be equal to or less than the actual distance. In other words, Djikstra is a form of A* where the heuristic always returns the actual distance.
So, what is a concrete example of an admissible A* heuristic?
It seems like writing a heuristic function that always returns an equal to or lesser value than the actual distance would require some magical insight about the graph obtained if I already knew the shortest distances.

In other words, Djikstra is a form of A* where the heuristic always returns the actual distance.

This is wrong.  Dijkstra's is a form of A* where the heuristic is always 0.
Dijkstra's algorithm is essentially the weighted-graph version of a breadth-first search.  It simply spreads out from the start node in all directions until it researches the end node.  It could spend a lot of time searching paths that are going in the complete opposite direction of the end, because it doesn't know anything about the global properties of the graph.
That's where the heuristic comes in.  Since we know the approximate direction of the end, we can prioritize searches that move in that direction.  In a 2D graph, for example, this would mean prioritizing searches that are closer to the end from a bird's-eye view.
The heuristic is added to the total distance so far to determine which nodes to consider next.  If the heuristic is 0, then we're only using the distances known so far, meaning we don't prioritize any direction and we get Dijkstra's algorithm again.  However, if it's non-zero, we do prioritize certain directions, which hopefully leads to us reaching the end sooner.
Note that the heuristic is just an estimate, not the actual distance to the end.  In fact, it's more than an estimate - it's a lower-bound to the actual distance (that's what "admissible" means).  In our 2D example, our heuristic is the bird's-eye view straight-line, which is the shortest possible path between two points.  Adding obstacles will never decrease this path length, only increase it.


Binary Search Symbol Table Hi I'm attempting to self teach myself from Algorithms (Sedgewick) and ran across the following problem:

3.1.15: Assume that searches are 1,000 times more frequent
than insertions for a BinarySearchST client. Estimate the
percentage of the total time that is devoted to insertions,
when the number of searches is 10^3, 10^6, and 10^9.

As stated in the problem Searches (S) = 1000 * Inserts (I)

$S = 10^3 \to I = 1$
$S = 10^6 \to I = 10^3$
$S = 10^9 \to I = 10^6$

At this point in the book we are using simple arrays and linked lists to back symbol table (not efficient hash maps, trees, etc). This would mean searches take ~log2(N) time and insertions take ~N/2 time (assuming a uniform distribution on where inserts are placed).

Am I correct in calculating the % of insert to search time would approximately be:

$\frac{Inserts \times N/2}{Searches \times \log_2(N)}$

Using $Searches = 10^3 \times Inserts$ this reduces to

$\frac{N/2}{(10^3 \times log_2(N)}$

This would mean the percentage depends heavily on the initial size of the symbol table and is not a steady percentage that we can use to answer the question.

Any suggestions for what I am overlooking, should I be making an assumption about the initial size of the table?

In computation, time consume depends deeply on the algorithm we choose. Since the search time consumes log2(N) and insertion  time consumes N/2, the insertion time increases sharply as compared to the search time. The only thing is that they depend on size of the symbol table, not the initial size because insertion and search time depend on the actual size of data set.

The chart below shows Percentage of Insertion Time over Search Time in your case.


Is there a graph product that is multiplicative in independence number? I know that Stable set cannot be approximated to constant factor. I saw a simple proof using OR product sometime back. I am unable to recall it. If anyone here knows what I am talking about could help fill my memory, that will be helpful.

Is there a graph product $\cdot$ such that $\alpha(G\cdot G)=\alpha(G)^2$ for all  graphs $G$ and $G\cdot G$ the product of $G$ with itself?

I only need an answer to inapproximability to constant factor and I believe there is a one step proof for this.

If we had such a product, then we have $\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)=\alpha(G)^k$. If $\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)$ can be approximated to constant factor $\sigma>0$, then $\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)=\sigma\hat\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)=\alpha(G)^k$ and since $0<\sqrt[k]{\sigma}<\sigma$, we can get an approximation of $\alpha(G)$ that is better than $\sigma$ by $\sqrt[k]{\sigma\hat\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)}=\alpha(G)$.

Consider $G = K_2$, for which $\alpha(G)=1$.  The only product defined in terms of subgraphs of $K_4$ and for which $\alpha(G \times G) = 1$, is the strong product (⊠).  This doesn't quite work, since $\alpha(C_5 ⊠ C_5) = 5$, which is not a perfect square.

However, denoting the lexicographic product by $\circ$, there is an easy proof due to Geller and Stahl that $\alpha(G \circ H) = \alpha(G)\alpha(H)$.

So you want the lexicographic product.


Integer factorization: comparing with floor While working on integer factorization algorithm I came to the next problem:

$$\frac{a}{ex} = \lfloor{\frac{a}{ex}\rfloor} + c$$

$a$ the number I want to factor
$x$ factor of $a$
$e$ positive integer that I choose

For $e = 1$ I found a linear representation for short sequences of $\lfloor{\frac{a}{x}\rfloor}$, this allows me to compare it to $\frac{a}{x}$ and find the value of $x$. The problem is that there are to many sequences, for this to be efficient. So I decrease their amount by using $e > 1$. Unfortunately it created $c$, and now I have to test all its possible values, it looks some thing like this:

for $e=2$, $c$ can be $\frac{1}{2}$
for $e=3$, $c$ can be $\frac{1}{3}$ or $\frac{2}{3}$
for $e=4$, $c$ can be $\frac{1}{4}$ or $\frac{2}{4}$ or $\frac{3}{4}$

Is there any way that I can predict the values of $c$, or give it a better estimation?

The value of $c$ is given by the formula
$$ c = \frac{(a/x) \pmod{e}}{e}. $$


Graph Algorithm (Modification on Dijkstra?) : Tech Interview Problem: Suppose we had a directed graph $G(V,E)$ with strictly positive edge weights, a nonempty set $A$ (special vertices) such that $A \subseteq V$, a positive integer $C$, and a starting vertex $S \in V$. Find the shortest path starting at $S$ and containing at least $C$ vertices in $A$ (cycles are OK). If no path exists, output -INF or +INF. Polynomial time algorithms only (in $V$, $E$, and $C$).

My attempt: If there are at least $C$ vertices in $A$ that I want to find, then maybe I could replicate the graph $C$ times, where each replicated graph is like a layer. So when running Dijkstra, if I step into a special vertex, that vertex connects me to its counterpart in the next layer. If there are 10 vertices in the graph and I want to find when I step into the special vertices 3 times, then there will be 30 total vertices because each layer contains the identical looking 10 vertices.

I have issues translating this idea to any sort of (pseudo) code. Perhaps my idea isn't even valid; in that case, any help would be appreciated in proposals of a different solution.

The Hamitonian path problem is reducible to your problem. Given a directed graph $G(V,E)$, set $C=|V|$ (number of nodes), $A = V$, and weight of each edge is equal to $1$. Thus, this instance of the problem requires to find a shortest path containing all vertices. Since it asks to find the shortest path, cycles are not allowed, and since it asks to include all vertices, the path visits all vertices once. This is a Hamiltonian path. So, your problem is NP-complete meaning it is unlikely to find a polynomial time algorithm. In this case you should try approximation algorithms or Linear/Integer programming algorithms.

Note (on  @user53923's comment): There is a chance to get a path with a cycle, from the problem from the question, which is shortest including all vertices. But in this case we could check in polynomial time if the path has a cycle and if it has then simply reject. This would mean the graph does not have a Hamiltonian path, otherwise it would return it since its length would be shorter from that containing a cycle.


Memory access on byte/word addressable memory I'm doing a question on architecture and I've come across this question which I do not understand how to answer the question.

Q. How many bits are required to address 4G x 32-bit main memory if

a) Main memory is word addressable
b) Main memory is byte addressable

I have read this question Word- or byte-addressable? Correct terminology but it did not clear up my understanding of the question as I am NOT asking what is the difference between byte and word addressable, more specifically I want to understand this question I've written.

The answer given says we need 34 bits for byte addressable memory and 32 bits for word addressable memory. I have thought about this for a while and have come to this conclusion which I do not know if it is correct or not:

Each row in the main memory is 32 bits in width and if it is byte addressable then we have 4 bytes in each row. To select a byte from the row requires log2(4) = 2 bits. Row width + 2 = 34 bits? Similiar concept for 32 bits. Is this correct logic?

The question is probably about address bits, not data bits.

A 4G x 32bits memory size is 16Gbytes.

With a 8bits data bus, you need 34 address bits (typically A[33:0])
With a 32bits data bus, you need 32 address bits (typically A[33:2]. A[1:0] is for selecting individual bytes inside the 32bits word.)


Playing video games to solve SAT instances This paper shows that computer games, such as Super Mario, are NP-hard, by reduction from SAT. It may be possible to use this reduction to help solve hard instances of SAT: use the reduction to construct a Super Mario level and let experienced gamers play it. In the worst case, it might take them exponentially long; but, in some cases, there may be heuristics that experienced gamers may be able to notice, and this may lead them to quick solutions.
The main problem with this scheme is that it is one-sided: if a satisfying assignment exists, then the gamers may find it; but if no such assignment exists, then they will not find any proof for it.
So my question is: is there a way to construct a video game for solving SAT instances, such that if the instance has a solution - a gamer will eventually find it (after possibly exponentially long time), and if the instance has no solution - a gamer will eventually find an evidence for it? Can such a game be useful for solving hard SAT instances?

No. The gamer will basically have to work out the SAT problem in their head.
Think of any video game puzzle you've solved that wasn't easy. You probably solved it by working out a simpler version of the problem and then solving that. If you "complexify" SAT into a video game level, the best way to solve the video game level will be to simplify it back into SAT, then solve SAT.
Example: Perhaps your game lets you create a level where you must collect all the coins from all the rooms but you can only enter each room once. (This is a Hamiltonian Path problem, which SAT can be transformed to). When you collect all the coins, the exit door opens. You then go to the exit door and finish the level. How would you solve it?
Well, you would start by exploring the level and drawing a map. Then you might simplify the map by drawing the rooms as circles and the connections as lines. Then you have to figure out a way to get from the start to the exit while going through every room... i.e. you have to solve the Hamiltonian path yourself. But how do you solve the Hamiltonian path? Well, you might reason that if you go this way, then you can't go that way, and if you go that way, you can't go this way, .... and write down a list of rules about where you can go. Then, you have to logically deduce a path that matches all the rules. Which is SAT. You're back to where you started except with a lot of useless extra work.


Exploring and interpolating a function using machine-learning? Which general machine-learning methods are there that try to "learn" or interpolate a smooth multivariate function and which get to actually choose the points at which the function is evaluated during the learning process (exploration)?

The idea would be that each function evaluation is more or less costly and the algorithm learns to explore the regions of space where the gain of knowledge is greatest (vs. the cost of evaluating the function). The function may be non-analytic (e.g. with kinks) in the most interesting cases.

My background is physics, and I am sure that such methods exist, but despite some searching I could not find something that is directly relevant, possibly because I do not know the right terms to look for. I only know that more broadly speaking 'reinforcement learning' is the area of AI dealing with exploration and rewards, so maybe the methods I am asking for represent some special case of that.

For clarification, here is an example: You might want to get the phase diagram of a substance, i.e. the density as a function of pressure p and temperature T. So we are dealing with a (mostly) smooth function of two variables (p,T). Its evaluation at any given point (p,T) requires an expensive Monte-Carlo simulation (lots of CPU time; how much even depends on where in the p,T-space you are). The ideal algorithm would judiciously pick points (p,T) at which to evaluate the density, trying to go towards regions where the function has the most salient features (e.g. phase transition lines, i.e. non-analyticities). Then afterwards, when you ask the algorithm for the density at any other point (p,T), it provides the best possible interpolation/extrapolation that it can come up with, given all the information it has acquired during its exploratory phase.

I would look into the field of "optimal experimental design" in bayesian inverse problems, particularly the recent work of Alen Alexandrian.

http://arxiv.org/abs/1410.5899

http://www4.ncsu.edu/~aalexan3/research.html

Essentially, one has an inner inverse problem for approximating the function based on point measurements of derived quantities, hosted within an outer optimization problem for choosing the points based on minimizing a combination of the error and the variance.

Furthermore, you don't need to do a full inner-outer solve procedure. Rather, you can use the KKT conditions for the inner problem as the constraint for the outer problem, and formulate a "meta" KKT system for the combined problem.

It is formulated in the language of PDE-constrained inverse problems, but would also apply to simpler situations like your problem (the "PDE" becomes the identity matrix..)


Find all the paths from node A to node B You are given a bunch of nodes evenly spaced in a rectangular grid. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand (northwest) corner and node B is at the bottom right hand corner (southeast). From each node you can only move east, south, or diagonally southeast to the next adjacent node (assuming there is an adjacent node that permits moving in that direction). How many different paths are there from A to B?

I only found a brute-force method using a depth first search with a stack. Is there a more efficient algorithm to solve this puzzle? Specifically, I am looking for an algorithm (preferably efficient) that can determine the total number of paths you can take from node A to node B in a grid of evenly spaced nodes of size M x N.

Let $P(i, j)$ be the number of paths from the start node, $(0,0)$, to the destination node, $(i, j)$. Then it's easy to see that
$$\begin{align}
P(i, 0) &= 1\\
P(0, j) &= 1\\
P(i, j) &= P(i-1,j)+P(i-1,j-1)+P(i, j-1), \text{ if }i,j>0
\end{align}$$
Applying this recursion directly isn't particularly efficient, since you'll wind up making a lot of redundant calls. You could improve this by memoizing the intermediate values: at step $k$, compute and save the values $P(0, k), P(1, k), \dotsc P(k,k)$ and the values $P(k, 0), P(k, 1), \dotsc P(k,k)$. Note that this last series actually doesn't need to be saved at all, since $P(a,b)=P(b,a)$.

For another way (which turns out to be conceptually the same as Yuval's answer), you could observe that a path consists of a collection of steps:

An eastward move, $E$, from node $(i,j)$ to node $(i+1, j)$.
A southward move, $S$, from node $(i,j)$ to node $(i, j+1)$.
A diagonal move, $D$, from node $(i,j)$ to node $(i+1, j+1)$.

So to get from $(0,0)$ to $(i,j)$ we will need to make $i$ moves east and $j$ moves south. Note that each diagonal move will contribute 1 to the eastward moves and 1 to the southward moves. Thus, every path from the origin to node $(i,j)$ can be uniquely described as a sequence of $E, S, D$ where the number of $E$s plus the number of $D$s equals $i$ and  the number of $S$s plus the number of $D$s equals $j$. For example, $P(2,2)$ is the number of paths

Using no $D$s: $EESS, ESES, ESSE, SEES, SESE, SSEE$.
Using one $D$: $DES, DSE, EDS, SED, ESD, SED$.
Using two $D$s: $DD$

So we see that $P(2,2)=6+6+1=13$.

Now the number of sequences of three symbols $D,E,S$, in order, with $a$ of the $D$s, $b$ of the $E$s, $c$ of the $S$s,  is given by the multinomial coefficient
$$
\binom{a+b+c}{a,\ b,\ c}=\frac{(a+b+c)!}{a!\;b!\;c!}
$$
and from this and the observations we just made, we'll have, for $i\le j$,
$$
P(i, j)=\sum_{k=0}^i\binom{i+j-k}{k,\ i-k,\ j-k}=\sum_{k=0}^i\frac{(i+j-k)!}{k!\;(i-k)!\;\ (j-k)!}
$$
where $k$ is the number of $D$ moves, $i$ is the number of $E$ moves and $j$ is the number of $S$ moves. This sum of factorials is also somewhat computationally expensive, but by recognizing that there are some relations among the terms, you can slightly simplify the number of multiplications and divisions involved. Unfortunately, there doesn't appear to be any nice closed form for this sum, unlike the situation where we don't allow diagonal moves, in which case $P(i,j)=\binom{i+j}{i}$.


Language equivalent states in a deterministic parity automaton Given a deterministic parity automaton $\mathcal{A}$ with state set $Q$ and a state $q \in Q$, we denote with $\mathcal{A}_q$ the same automaton with initial state $q$. Two states $p$ and $q$ are language equivalent if $L(\mathcal{A}_p) = L(\mathcal{A}_q)$.

What is an efficient algorithm to compute the set of all language equivalent pairs, i.e. $\{ (p, q) \in Q \times Q \mid L(\mathcal{A}_p) = L(\mathcal{A}_q) \}$ ?

Two states in the automaton have different languages if and only if there exists a word that is accepted from one state, but not from the other. Checking if this is the case boils down to building a product of the automaton with itself, i.e., starting form the automaton $\mathcal{A'} = (Q, \Sigma, \delta, q_0, \mathcal{F})$, you build an automaton $\mathcal{A'} = (Q \times Q, \Sigma, \delta', (q_0,q_0), \mathcal{F}')$ such that for all $q,q' \in Q$, you have $\delta'((q,q'),a) = (\delta(q,a),\delta(q',a))$.

In this product automaton, you want to cycles along which the parity of the highest color visited infinitely often in the first factor of $Q \times Q$ is not the same as in the second copy. Whenever this is the case, then for every state $(q,q')$, we know that $q$ and $q'$ have different languages.
 Otherwise, if from state $(q,q')$, there is no way to reach a cycle along which one copy of the automaton accepts, but the other one does not, you know that the states have the same languages.

The technique is applied in the paper "SAT-Based Minimization of Deterministic ω-Automata" by Souheib Baarir and Alexandre Duret-Lutz, which bases on a similar construction for deterministic Buchi automata from earlier work. They use a SAT solver to guess an automaton that is equivalent to a given one and add SAT clauses that enforce that in a product between the two automata, you do not have reachable cycles along which the acceptance of the cycle differs between the copies. After an equivalent automaton is fixed, their clauses become Horn clauses, so you can check this in polynomial time. In your case, you would just use the same automaton again.


How to figure out whether two texts refer to the same object or event Let's assume there is something happen in the world - Football world cup final. And team-1 beat team-2 with the score 3:2. So there is whole bunch of articles on every website about it, each contains slightly different wording, sometimes even on different language, but they all about the same event, and contains mostly the same info. Who won, who scored, timing, etc...

So, let's assume we have a 1000 texts about 10 different situation. What is modern approaches in cs, which could

1) group texts about the same situation together (so, instead of 1000 texts - there is 10 groups based on expressed object)

2) packing 1000 texts about the same object into 1, but which contains all new information about object. (Let's say in some text there wasn't coach interview, in some others - no timing where goals was scored, but result text should contain all unique info from each text)

This is a document clusterization problem. A general solution is to define some sort of distance between documents and apply a standard clusterization algorithm, such as k-means or expectation maximization. There are different approaches to picking distance measure $L$:

Build a common vocabulary and convert each document into a bag of words, i.e. a long vector consisting of zeros and ones of length $|Vocab|$. Then let $L$ be the Hamming distance between these two representations.
Compute word2vec embeddings of each word in a document and average them (can be also weighted by TF-IDF -- see this question on SO for details). This will produce a dense $d$-dimensional vector per each document. The distance $L$ can then be defined as Euclidean, Minkowski or more sophisticated distance on vectors in $\mathbb{R}^d$.
Compute doc2vec embedding directly. Once again it's a dense $d$-dimensional vector per document, so the same choice of vector distances applies.


Insert a node in a binary search tree The teacher gave us this code that inserts a node in a binary search tree, but I am not sure what the $z.p = y$ instruction does. wouldn't the algorithm work without it?

abr_insert(T, z) //z is the node that must be inserted
    {
            y = NULL;
            x = T.root;
            while(x != NULL)
            {
                    y  = x;
                    if(z.key < x.key)
                            x = x.left;
                    else
                            x = x.right;
            }
            z.p = y; //here is the instruction that I don't understand
            if(y = NULL)
                T.root = z;
            else if(z.key < y,key)
                    y.left = z;
            else
                    y.right = z;
    }

It seems like this algorithm is keeping track of parent pointers. Each node N has three fields: N.left (left child), N.right (right child), and N.p (parent). The variable y is used to keep track of the most recent parent, so when we fall off the tree (i.e. when x == NULL) we can use y as the parent of the new node z.


What could you learn from studying player movement and behaviour on online FPS games? Just thinking of Counter Strike as a canonical example, if you have a coordinate representation of the map and for every player you have a complete history of everything you might need for every moment of time, say every 10 miliseconds or something and you just recorded where the players went around the map, and what they did. So maybe, for example, at each time t you had v(t) a vector function whose components are (location(t), velocity(t), rotationVector(t), rotationVelocity(t), isFiring(t), ammoCount(t), health(t), isEnemyVisible(t), isTeamMateVisible(t)) or whatever other measurements you think would be useful for the state space.

If you collected a bunch of data like this what sort of hypotheses or models would you consider testing? Would it be possible to construct a probabilistic model to classify histories and possibly predict outcomes of player-enemy encounters? Could you train AI bots on this data?

File each given vector function with the win/loss of the game and the team each vector was on.
Applications of this data: To gauge map balance and provide the least advantage to any one particular team.

Determine how particular elements of the map effect balance.

Make bots more effective by determining common strategies employed against bots, and the manner in which players address situations (going with the counter strike example: We're down players lets group up on the objective).

It would be interesting to see which would provide better balance or more effective bots, conventional testing or this in-depth vector analysis.


Case where anti-dependency doesn't need pipeline stalling While exploring the various types of data hazards in a pipeline, I came across a statement in my book which said that anti-dependency mayn't lead to cycle stalling.

But i couldnt find at example for the same. Can anyone help me with it please?

Thanks in advance!

You can eliminate anti-dependences (WAR dependences) with register renaming, so if you're doing renaming there will be no stalls from anti-dependences.  The other case is if you already know the write isn't going to interfere with the read (for example you know all the instructions with reads in them have already done their register reads).

Note that the traditional "5-stage" pipeline is doing the equivalent of register renaming using its bypass registers, so in that case you never need to stall.


Is there a way to convert a program into a Boolean formula? Let's say I have a program P, in form of a binary code for x86 architecture.

I want to find a Boolean formula F (in form of CNF, or something like that), such that

F(input,output) = true iff P(input) = output

So to answer a question "what output does the program produce on given input" I will only need to run a SAT/SMT solver for X on formula

F(input,X) == true.

I understand that this problem is undecidable in general case, but I only care for some practical cases.

What keywords should I google to find more about this topic?

Disclaimer: I'm not sure how useful any of this is for getting this done practically since you have a program, not a Turing Machine.

The Cook-Levin Theorem essentially states that you can translate the execution of a Turing Machine into a boolean formula that is polynomial in the length of the TM's execution such that the formula is satisfiable iff the TM accepts the input.

In your case 'accepts' means 'returns true'. One could model this in a TM by transitioning to an accepting state instead of returning true.

The linked Wiki article gives a good exposition of the proof but the gist if it is that you have variables that describe the input to the machine, the sequence of states the machine takes during an execution, the position of the head during an execution, and a bunch of conjunctions that force satisfying assignment of the variables to describe a successful execution of the TM on the input.


Why is this automaton considered DFA? So I was watching this video https://www.youtube.com/watch?v=ZjjAbFxjxLQ and the guy was explaining why the top automaton is NFA (because the initial state doesn't know what to do if the input string begins with b) and the bottom is DFA (because the initial state points to a 'dead state' if the input string begins with b):

Okay, fair enough.
But when I went on this Automaton simulator and it generated an example of a DFA for me, I got confused because its the same as the NFA example above:

It doesn't have an option for when the input string begins with b. So what's going on?

Some people in the literature (very few actually) do not consider missing transitions as nondeterminism, and given a DFA, they allow themselves to remove all transitions that lead to states from which we cannot reach an accepting state. The reason for that is technical, as sometimes it may simplify proofs a bit. Or it could be a matter of taste.
Intuitively, allowing missing transitions is justified as nondeterminism, or guessing occurs only when we have a choice, that is, when we have at least two transitions $\langle q, \sigma, s_1 \rangle$ and $\langle q, \sigma, s_2 \rangle$, going out from the same state $q$, and are labeled with the same letter $\sigma$. So, DFAs with missing transitions, or more accurately NFAs such that for every state $q$, and letter $\sigma$, it holds that $|\delta(q, \sigma)|\leq 1$, are considered deterministic in the sense that they have at most one run on a given input word.
The most common formal definition of a DFA does not allow missing transitions. Please note that it does not really matter to which definition you stick as long as you're consistent with it.
Also, given a DFA, it is easy to remove all transitions leading to a state from which we cannot reach an accepting state (because detecting states that do not lead to an accepting state can be done in polynomial time), and this does not affect the automaton's language. Conversely, given an automaton with missing transitions, you can direct all missing transitions to a rejecting sink which is a rejecting state with a self loop labeled with every letter.


Find the number of strings in the language $(∅∅^∗ + ∅)$ Consider the language $L = \emptyset\emptyset^∗ + \emptyset$.

How many words does $L$ contain? Zero or one?

Note: $\emptyset^∗ =\{\epsilon\}$.

Your language could be simplified as follows, using $\emptyset^* =\{\epsilon\}$:

$$
\begin{align*}
L(\emptyset\emptyset^*+\emptyset)
&=L(  \emptyset . \{\epsilon\} + \emptyset) \\
&=L(\emptyset +\emptyset) &    (\emptyset.\{\epsilon\}=\emptyset) \\
&=L(\emptyset) & (\emptyset + \emptyset = \emptyset)
\end{align*}
$$

So the language L accepts empty language which is $L =\{ \}$, which means that it contains zero elements.

Please be aware that the empty language is different from language consisting of the empty string, which is $L =\{\epsilon\}$, and which contains the element $\epsilon$, while the empty language contains zero elements.


Is the set partitioning problem NP-complete? I know that the set partitioning problem defined like this:

  Given $$S = \left\{ x_1, \ldots x_n \right\}$$ find $S_1$ and $S_2$ such that $S_1 \cap S_2 = \emptyset$, $S_1 \cup S_2 = S$ and $\displaystyle\sum_{x_i \in S_1} x_i=\sum_{x_i \in S_2} x_i.$

is NP-complete. But I don't understand why (or am not even sure if) the following problem is NP-complete:

  Given $$S = \left\{ x_1, \ldots x_n \right\}$$ find $S_1$ and $S_2$ such that $S_1 \cap S_2 = \emptyset$, $S_1 \cup S_2 = S$ and $$| \sum_{x_i \in S_1} x_i-\sum_{x_i \in S_2} x_i |$$ is minimized.

The paper 'The Differencing Method of Set Partitioning' by Karp and Karmarkar and some others say that it is NP-complete. But, if I have a sample solution to this problem, I can not tell whether it is an optimal solution (unlike in the first problem) and therefore I feel it NP-hard. If this is not true, how can I conclude that it is NP-complete? Thanks!

Karmarkar and Karp do not claim that the second problem is NP-complete.  It can't be, because it is not in NP. Remember that NP is a class of decision problems, i.e., problems where the answer is either "yes" or "no".  Because the problem is not in NP, it's not required that the answer be efficiently checkable.  The same thing happens with TSP: sure, if I give you a route around the cities and claim that it's less than 50 miles, you can check that easily; but if I give you a route and claim that it's the shortest, there's (probably) no way to check that in polynomial time.

Rather, the second problem is what is known as an NP optimization problem. It asks us to minimize a certain function $f$ and the decision problem, "Given $S$ and $k$, is $f(S)\leq k$?" is in NP.  Now, if this decision problem is NP-complete, the optimization problem is NP-hard: there's a trivial reduction from the decision version to the optimization problem.  Going the other way around, if you had an efficient algorithm for the decision problem, you could find out the optimum by binary search.


Reduction from partition to multiprocessor scheduling I am kind of unsure about a reduction between two problems.
Here are the two problems:

PARTITION:
Instance: A finite set of n positive integers $S= \{a_1,a_2,...a_n\}$.
Question: Can the set $S$ be partitioned into two subsets $S_1$,$S_2$, s.t. the sum of the numbers in $S_1$ equals the sum of the numbers in $S_2$?

MULTIPROCESSOR SCHEDULING:
Instance: A set $J$ of $k$ jobs where job $j_i$ has length $l_i$, and $m$ processors.
Question: Can we schedule all jobs in $J$ on $m$ processors s.t.:
(a) on each processor the next job in the sequence is started immediately after the preceding job is finished and (b) the total time to execute all jobs on each processor takes the minimum possible time $T_{min}=\big(\sum\limits_{i=1}^k l_i\big)/m$

I am a little bit unsure about my try to reduce Partition to multiprocessor scheduling. My attempt is posted as an answer.

(This is the answer that the OP wanted to have checked.)

Let $S=\{a_1,...,a_n\}$ be an arbitrary instance of Partition. In our reduction we set $J=S$. if $\sum\limits_{a \in S} a$ is even, we set $m=2$. Note: If the sum of elements in $S$ is odd, there cannot be a Partitioning. Further, we set the length $l_i$ of job $j_i$ to the value of $a_i$.

So this is my reduction. But I am very unsure if this is just too easy? Note that I do not have to provide the correctness proof but just the reduction. Is this somehow a right reduction? I am very unsure if I have to distinguish between the two cases where the sum of elements of $S$ is odd or even. What if the sum is odd?

Can someone give me some hints on that?


Extracting Randomness from Mouse Acceleration I'm working on trying to make an "entropy pool" that will be fed as input into an RNG (as in, ex, Fortuna). In order to do so, I need to take various collected data and extract as much entropy as possible to turn it into unpredictable bits. I've read many papers about extracting randomness, but I haven't understood how to apply it to real-world data sources.

For example, as one entropy source, I'd like to use the position of the mouse cursor. After some simple experimentation, it seems like using the acceleration of the cursor (resulting in two streams of X acceleration and Y acceleration) is the best representation to use in that it reduces the sample range significantly. Running several min-entropy estimators on the acceleration data (separately for X and Y axis data), I get estimates of at worst 0.75 bits/sample of entropy (ignoring that the two streams are correlated). Beyond that, I'm not sure how to apply any published randomness extractor to this data.

Part of my problem stems from the fact that most entropy extractors talk about entropy rate, which I'm not sure how to calculate in this case. My samples are 8 bits each (signed byte), so that could make the entropy rate 0.75/8 ~= 0.09, which is far too low for most extractors. Another problem is that I have two correlated streams, and I can't remember any extractors that deal with that kind of input.

Any guidance or references on how to extract entropy from this data using any published randomness extractor would be greatly appreciated. I'm very interested in using a "real" randomness extractor and not the common "just hash it" approach.

I have a custom design that I can detail if desired. It essentially computes symbol statistics from the entire test capture (5 million samples) and uses range encoding to encode each symbol using those statistics. It results in about 1.5 bits/sample of output for each stream, and I'm not sure how well founded the idea is.

Edit: One of my end goals is to have a very large state RNG, suitable for being able to shuffle 200 card decks into every possible combination. 200! is ~1246 bits, so (for ex) using a typical PRNG-oriented implementation of AES-256-CTR would not suffice because it has too small a state to store that much entropy.

Also, as for using cryptographic hash functions, some of the early papers on extractors indicate that almost all functions are good extractors for high-entropy data, but I haven't seen any information about using them to reduce low-entropy data to shorter higher-entropy data (keep the entropy level, but reduce the total number of bits). If this is a mathematically valid use, I'd really like to see papers about it.

Start by reading How to extract randomness from a file?.

At a broad level, it seems like you understand pretty well the techniques.

To extract randomness in practice, I recommend you use a cryptographic hash, and use techniques from the cryptographic literature for cryptographic building pseudorandom generators.

You mention "extractors".  I know there's some cool theory surrounding them, but I don't recommend you use extractors.  They are beautiful but not practical.  Cryptographic hash functions are superior in practice.

You talked about estimating the amount of entropy in the data.  Unfortunately entropy estimation is an inexact science.  It's also easy to over-estimate the amount of entropy (e.g., if there are non-trivial correlations in the data that you didn't think to check for).  So, a typical procedure that cryptographers often use is to make some estimate of the entropy rate (typically through a priori calculations), then divide by a factor of 4 or so to provide a safety margin -- and gather random values from many sources, and feed them all into the pool.  The hope is that even if one source provides low-entropy data, or even if one of the entropy estimates is too optimistic, maybe some other source will have enough entropy in it to make up for the problem.

Overall, I recommend you spend some quality time in the cryptographic literature reading about the techniques that have been developed there.  Cryptographers have spent a lot of time worrying and thinking about this, because cryptography relies upon high-quality random numbers.  And, rather than re-inventing the wheel yourself, it's probably better to re-use some existing well-tested cryptographic method.

Here are a few pointers to get you started:

https://crypto.stackexchange.com/q/41967/351
https://crypto.stackexchange.com/q/27028/351
https://crypto.stackexchange.com/q/32984/351
https://crypto.stackexchange.com/q/10517/351
https://crypto.stackexchange.com/q/18355/351
https://crypto.stackexchange.com/q/39186/351

You can look around Crypto.SE and the resources mentioned there, and you'll probably be able to pick up a bunch about this topic.  Have fun!


Is polynomial time reducibility reversible? If a language $A$ is reducible to some language $B$, does it follow that $B$ is reducible to $A$?

My guess is no, it having something to do with the function $f$ in the definition of $A$ reducing to $B$ needing to be invertible.

This is provably not the case. Let $A$ be any non-trivial language in P (different from $\emptyset$ and $\Sigma^*$), and let $B$ be any EXPTIME-hard language. Clearly $A$ is polytime-reducible to $B$ (since $A$ is polytime and $B$ is non-trivial; or since P$\subseteq$EXPTIME and $B$ is EXPTIME-hard), but if $B$ were polytime-reducible to $A$ then it would follow that EXPTIME=P, contradicting the time hierarchy theorem.


First problem to be considered np complete? What is the first problem that was demonstrated to be NP-Complete?

You can find the original paper of Cook online: The complexity of theorem-proving procedures. You can also find Levin's paper in Russian: Universal Sequential Search Problems. A translation can be found in the appendix to a historical survey by Trakhtenbrot: A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms. You can even find Karp's Reducibility Among Combinatorial Problems.

Cook showed that the set of DNF tautologies (i.e., the complement of SAT) is NP-complete in his sense (oracle reducibility). Karp mentioned that SAT is actually NP-complete with respect to many-one reductions. Levin's paper mentions six different problems, but has no proofs (as was customary).


Update all nodes in a graph in a way that at any step all chosen nodes are disconnected There are N nodes in a graph and some of them are connected with edges. All nodes are of type T1. The goal is to update all nodes to type T2. At any step you can choose any set of nodes and change their type to type T2 with the only restrictions that no nodes in the chosen set can be connected with an edge (i.e. this sub-graph should not have edges). Find the minimum number of steps required to update all nodes to type T2.

A graph can have any topology, i.e. nodes can be connected in a random fashion without any pattern

Hint: Your question is tantamount to finding a partition of the vertices of the graph into as few independent sets as possible. This is the same as finding the chromatic number of the graph, which is NP-complete.


What is the set of languages accepted by empty stack pda? I am having a confusion. Empty stack pda will always accept episilon. Therefore a language not accepting episilon will still be accept episilon, so how can we avoid this?

When defining the semantics of PDAs accepting with an empty stack, we initialize the stack with a special "bottom-of-stack" symbol. This solves your difficulty.

The set of languages accepted by empty-stack PDAs is the context-free languages. It is exactly the same set of languages accepted by final-state PDAs. The picture changes when considering deterministic PDAs: final-state DPDA accept the deterministic context-free languages, whereas empty-stack DPDAs accept the prefix-free deterministic context-free languages.


Reduction from $L$ to $L_{TM}$ Let $L$ be the language of all the words with the shape $<M_1,M_2,w>$ such that $M_1,M_2$ are turing machines that accepts $w$, show that $L$ isn't decidable.

I thought to use reduction from $L_{TM}=\{<M,w>\mid M \text{ accepts } w\}$

how can I defined the function $f$ ?

If $L$ were decidable, then you could make a decider for $A_{TM}=\{\langle M, w\rangle\mid M\text{ accepts }w\}$ by deciding $\langle M, M, w\rangle$. We know, however that that's impossible, since $A_{TM}$ is undecidable.


Proving optimality of a dynamic programming algorithm We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is directly preceded by $x^R$, where $x^R$ means string $x$ reversed. In other words, we're choosing some even-length palindrome and erasing it's "right half".

The goal is to minimize the length of the word left when no further can moves be done. In example, from a bit word $100110$ we can erase $01$ from the middle, and be left with $1010$ where no moves can be done. However, starting differently, we can reduce the word to a single $10$, which is optimal. I want to compute this minimal length for a given string, for $100110$ it would be $2$.

Now, I have a dynamic-programming algorithm which I know produces right answers (it has been tested a lot), but don't know how to prove it. It computes the best result for every substring of $s$ in increasing length. For those of length $k$, the answer is surely at most $k$. Also, it's obvious that the only strings in which no moves can be done are of form $1010...$ or $0101...$. For some word we're playing on, as it's first bit can never be erased, we know the exact form of a word that will be left from it, the only thing that we lack is it's length. Now, I assumed that for a word $t$, there exist some words $x$, $y$ that $t = xy$, and if we do the optimal operations just on $x$, producing a word $x'$, then just on $y$ producing $y'$, and in the end on the word $x' y'$, we will acquire the optimal result for $t$. The last step is very easy, because we know how words $x'$ and $y'$ look like only knowing it's lengths, so there are only a couple of cases to consider. The complexity of this process is $O(n^3)$ as it spends linear time on each substring of $s$.

If $DP[i][j]$ is the answer for a substring $[i..j]$, the complete recurrence is as follows:

$$DP[i][j] = \min \{DP[i][k] + F(i,k,j) \cdot DP[k+1][j] : i \leq k < j \}.$$

where

$$
F(i,k,j) = \left\{ \begin{array}{ll}
1 & \textrm{for $s[i] = s[k+1]$ and $DP[i][k] = 1$}\\
1 - DP[i][k] \mod 2 & \textrm{for $s[i] = s[k+1]$ and $DP[i][k] > 1$}\\
DP[i][k] \mod 2 & \textrm{otherwise}
\end{array} \right.
$$

what corresponds to the fact that in some cases $y'$ can be erased using $x'$ (possibly in multiple moves) - in those cases $F(i,k,j)$ is $0$, and it's $1$ otherwise. Also note, that if $s[i] = s[i+1]$ then when dealing with $DP[i][j]$ for $j > i$ at first we initialize $DP[i][j] = DP[i+1][j]$.

For me, the assumption that $t$ can be split into $x$ and $y$ in a such a way that the mentioned procedure is optimal, is non-trivial. I'm asking for a proof that this assumption can be made, or some different solutions for this problem, either would be nice.

Since you're asking how to construct a proof of correctness, I'll give you some tips to get you started.  If you do all of these, I think you'll be able to make a lot more progress.

As Raphael suggests, make that you can write a recurrence relation for the solution.  You don't yet have a recurrence.  A recurrence is an equation for $DP[i][j]$ that is written solely in terms of $i,j,s$ and other "earlier" values of $DP[\cdot][\cdot]$.  Your equation involves a variable $k$, but what is $k$?  Where'd that come from?  It comes out of the blue.  How do we choose $k$?  You haven't yet given us a formula that computes $DP[i][j]$.  Until you do that, you can't possibly hope to prove your algorithm correct.  In fact, until you do that, you don't even have an algorithm!

Hint: I think you'll find you want to write something like

$$DP[i][j] = \min \{...\text{something}... : k=i-1,i,i+1,\ldots,j-1\}.$$

You fill in the $\text{something}$ part.  In short, I recommend that you formulate your recurrence more accurately.

Hint: try writing out the pseudocode for your dynamic programming algorithm, in standard form.  This will force you to write a recurrence for $DP[i][j]$.
Once you have a recurrence, your next step is to prove that it is correct.  Why does it give the correct answer for your problem?  Justify why the recurrence is correct.  Here you might use proof by induction.

See Raphael's answer, which gives an excellent overview for how to prove a dynamic programming algorithm correct.

I recommend that you review the proof of correctness for a few other dynamic programming algorithms.  (Look in a few standard algorithms textbooks; with any luck, they should show you several examples.)  You'll see that they have a similar structure, and this should help you structure your proof.
One more tip that will be very helpful.  You write "I assume (...)".  You might try proving that the "(...)" statement is true.


Can you write a program that alters another program semantically? It is definitely possible to write a program that takes another program as an input and changes it syntactically, but does not alter the meaning.

But is it possible to write a general program $alter$ that alters the output of a given program $P$ for some input, i.e. $\exists x: P(x) \neq alter(P)(x)$? Edit: Let's add the assumption that $\exists k: P(k) \neq \bot$.

I was thinking about doing something simple like this:

alter(Program P)(x):
   k = findSomeInputWhereHalts(P)
   y = P(k)

   if (x == k)
     return y+1 // or something else except y
   else
     return P(x)

This requires that $P$ does halt for some input $x$, which is an OK requirement for me. But it seems that there is probably some other counterexample to this specific algorithm or it might be generally uncomputable, but I failed to figure it out.

Edit: How I imagined implementing findSomeInputWhereHalts:

findSomeInputWhereHalts(P):
    for each int n:
        for each int k <= n:
            y = run P(k) for n steps
            if (y is defined)
                return k

But this obviously never halts if $\nexists k: P(k) \neq \bot$ .

Your idea fails (assuming all P are allowed), and that's not by accident.

You can not find an input for with P halts in finite time.
P may never halt, in which case that line in your program loops;
thus, the program behaves exactly the same as P.
You can skip finding k and do

alter(P, x) =
  P(x) + 1

This is the same idea as you have (note how it alters the semantics on
 all inputs on which P halts) but does not require us to find
 an input on which P halts.

However, it's still fails for the never-halting program -- but, at least,
 only that one!
What if we just output 1 or any other value sometimes?
 That takes care of never-halting P, but for each such
 hack with a static, computable "abort and output c"-criterion
 -- that includes runtime bounds! -- we can build easy counterexamples.
 Idea: if ( criterion ) then c else something.

So that looks bad; we can't compute uncomputable criteria! And we have to "decide"
after finite time for any fixed x (otherwise the never-halting P skrews us).

When prospects are this bleak, it's sometimes wise to try the other direction.
What if the problem can not be solved, that is alter does not exist?
In fact, given sufficient background in computability, it is clear that such
a function can not exist.

Assume any computable, total function $\mathtt{alter} : \mathbb{N} \to \mathbb{N}$.
We understand natural numbers as (the numbers of) programs in some
Turing-complete programming language $\phi$.
More specifically, let $\phi$ be a suitable numbering of all (partially) computable functions;
we then denote by $\phi_i$ the function computed by program $i$.

Now, by Kleene's recursion theorem
there is some index (program) $i^*$ so that $\varphi_{i^*} = \varphi_{\mathtt{alter}(i^*)}$,
that is $\mathtt{alter}$ has no effect on $i^*$, semantically.
Stronger versions show that there are infinitely many such $i^*$ so there's no hope fixing this.

In summary, no such program alter that works on all input programs can exist.

If you allow only P that halt for at least some x, your approach works; the proof is elementary (show that alter is computable, and that alter(P)(k) != P(k) for some k).


CYK algorithm in theory of computation For any context free grammar, there is a parser that takes atmost n^3 time to parse a string of length n.
Doubt: I marked it false in a national level exam.I think it should be any null-free context free grammar and not any cfg because we first have to convert cfg to cnf but only null free cfg can be converted to cnf.
Is this statement correct?

It's true.
If the CFG is not null free, and the input sentence is not null, you can remove the null from the CFG and then parse the input sentence with the resulting grammar.  You already know how to do that in cubic time.
If the CFG is not null free, and the input sentence is null, you can immediately tell whether the input sentence is accepted by the CFG.


Count the possible plans for nurses I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below:

The director of a hospital want to schedule a working plan for a nurse
in a given period of N consecutive days 1,..., N. Due to the policy of
the hospital, each nurse cannot work all the days 1,..., N. Instead,
there must be days off in which the nurse need to take a rest. A
working plan is a sequence of disjoint working periods. A working
period of a nurse is defined to be a sequence of consecutive days on
which the nurse must work and the length of the working period is the
number of consecutive days of that working period. The hospital
imposes two constraints:
Each nurse can take a rest only one day between two consecutive
working periods. it means that if the nurse takes a rest today, then
she has to work tomorrow (1)
The length of each working period must be greater or equal to K1 and
less than or equal to K2 (2)
The director of the hospital want to know how many possible working
plans satisfying above constraint?
input
6 2 3
output
4

I have thought a lot and just give an initial idea: I will use an 1-D array to represent a schedule from day 1 to day N. for each day (ith day), I have two choices: the nurse will work this day or the nurse will not work on this day.
If the nurse does not work on the ith day, the ways for this case is the total ways of the ith-2 day. (Because she must have a day off on the previous day.
Else, the ways for this case will be the sum of total ways of the ith-j day, with j in [K1, K2].
However, I do not know why I am wrong and which way will be the correct answer. I really need your help to derive an appropriate algorithm

You can solve this problem with dynamic programming. Your states are
dp[day_number][worked_sofar]. here is a recursive implementation:
#include<bits/stdc++.h>

using namespace std;

vector<vector<int> > dp;
int n, k1, k2;
int solve(int day, int sofar){
    if(day > n || sofar > k2)return 1;
    if(dp[day][sofar] != -1)return dp[day][sofar];
    int ans = solve(day + 1, sofar + 1);
    if(sofar >= k1)ans += solve(day + 1, 0);
    return dp[day][sofar] = ans;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> k1 >> k2;
    dp.assign(n + 1, vector<int>(k2 + 1, -1));
    cout<<solve(1, 0);
    return 0;
}

```


What is the complexity of $i^i$? What is the complexity of the following algorithm in Big O:
for(int i = 2; i < n; i = i^i)
{
    ...do somthing
}

I'm not sure if there is a valid operator to this type of complexity.
My initial thought was as follows:
After $k$ iterations we want: (using tetration?)
${^{k}i} = n \implies k=\log\log\log..._k\log{n}\implies\mathcal{O(\log\log\log..._k\log{n})}$ (where we have k times the log function) but i'm not sure if this is evan a valid way of writing this.
Anyway, we have a complexity that that includes $k$, which does not seems right to me.

This sequence is OEIS A173566. To understand how large it grows:
$a_n = 2^{2^{b_{n-1}}}$
where:
$b_0 = 0$
$b_n = b_{n-1} + 2^{b_{n-1}}$
The sequence $b_i$ grows faster than $2^{\cdotp^{\cdotp^{2^0}}}$, where there are $i$ 2's in the tower.
EXPTIME is $O(2^n)$, 2-EXPTIME is $O(2^{2^n})$, and in general, you can define n-EXPTIME . The sequence $b_i$ is not in n-EXPTIME for any natural n. So it, and therefore $a_i$, is not in the complexity class ELEMENTARY.
The definition above shows that $a_i$ is primitive recursive, which is interesting, because that means it doesn't grow as fast as the Ackermann function.
I think (but don't really have the time to formally prove or disprove right now) that means it's $\mathcal{E}^4$ in the Grzegorczyk hierarchy. Left as an exercise.


Entropy sources: Weaver (1949) typo? In Recent Contributions to The Mathematical Theory of Communication (Weaver 1949), aka The Mathematics of Communication (Weaver 1949) (various copies exist online), and also published as Part I of The Mathematical Theory of Communication (Shannon and Weaver 1949), Weaver says:

  We are now in a position to state the fundamental theorem, produced in
  this theory, for a noiseless channel transmitting discrete symbols.
  This theorem relates to a communication channel which has a capacity
  of C bits per second, accepting signals from a source of entropy (or
  information) of H bits per second. The theorem states that by
  devising proper coding procedures for the transmitter it is possible
  to transmit symbols over the channel at an average rate* which is
  nearly C/H, but which, no matter how clever the coding, can never
  be made to exceed C/H.

  …

  * We remember that the capacity C involves the idea of information
  transmitted per second, and is thus measured in bits per second. The
  entropy H here measures information per symbol, so that the ratio of
  C to H measures symbols per second.

I have not managed to find published errata for this text.

Am I correct to think the phrase "H bits per second" ought to read "H bits per symbol"? If not, why not?

Yes, your understanding is correct.  The theorem is indeed talking about the entropy of the source, in terms of the amount of information in each symbol.  Since entropy is measured in bits, the units are bits per symbol.


Divide an array into two sub arrays such that their sums are equal and possibly maximum Given an array A, we should partition A into two subarrays whose sums are equal, and that maximizes this sum.  We are free to omit items from the subarrays.

For example, [7,2,5,7,12] can be divided as the following:

[5,2][7] = 7
[5,7][12] = 12
[7,7][2,12] = 14

We need the final answer as 14 because the max possible sum is 14.

I initially tried to generate all possible combinations of from length 1 to N and compare the sums and take intersection between two subsets. But it takes pow(2,N) time.

Is there an efficient algorithm to solve this problem?

Please help how to approach this problem. I have tried state space tree with recursion like in the problem subset_sum. But couldn't solve this. Please help.

The problem is NP-hard, by a straightforward reduction from the partition problem.  Therefore, you should not expect any efficient algorithm.  However, there is a pseudo-polynomial-time algorithm using dynamic programming (see pseudo-polynomial-time algorithm for the partition problem for inspiration).


Why do we need hashed page tables for Paging in Operating Systems? I understand that we might need hierarchical paging to handle page tables with sizes greater than the size of one frame, but what is the use of Hashed Page tables then? I would understand if we were storing page-numbers and mapped frame numbers as $key-value$ pairs, because then hashing would make the process of accessing a particular $key-value$ pair much faster but can't we just store the base of the page table and add the virtual page number, go to that index of Page Table, and get the frame number anyway?

There are several advantages of hashed page tables over the standard flat/hierarchal page tables. One of these being size, a hashed page table will use less space in memory than using a flat or hierarchal page table. It will at most have one entry for every physical frame (worst case scenario; unlikely  as many page numbers will end up having same hash value) instead of having an entry for every page (many of which will be left unused; although this problem is alleviated with the use of hierarchal page tables). Inverted page tables also have this advantage, however hashed page tables have a performance advantage over inverted tables, as the lookup is much faster in hashed page table. So a hashed page table combines the space advantage of an inverted table with the lookup advantage of a standard page table.


Finding users covering a set x by x I have a Set $S$ of objects, a set $U$ of users and a map $c: U \rightarrow S^{\prime}$, where
$S^{\prime} \subset S$ and $\emptyset \notin S^{\prime}$.

Every time I add a new entry to $c$, i.e. adding a new user $u$ with her associated subset of $S^{\prime}$, I need to get the list of other users with whom she covers $S$. However, I don't need to get all possible covers. I only need to get with how many $x$ other users she covers $S$, at most. In other words, I need to find who's complementing each other to cover $S$ 2 by 2, 3 by 3, ... , $x$ by $x$.

Is there an efficient method to do it? Or an efficient data structure? If no, is there any trick I can make to get good results? e.g. encode the elements of $S$ and do some sort of mathematical operations? Is any efficient solution possible at all?

Please let me know if I haven't explained my problem well enough.

Since SET COVER can be reduced to this problem, you can't expect it to have an efficient solution. To reduce SET COVER to your problem, add a dummy user $u$ covering an auxiliary element, add the other users corresponding to the sets in the instance of SET COVER, determine the counts as in your problem, and then you can tell whether there is a set cover of given size.


Intuition behind recurrences with growth O(n log n) vs O(n²) Been trying to get the intuition behind why two very similar recurrence relations don't follow a pattern I would expect. They are pretty well known relations:

Relation 1 -

$T(n) = 2T(\frac{n}{2}) + n$

Relation 2 -

$T(n) = 2T(\frac{n}{2}) + n^2$

When sketching out a tree for the first recurrence, the way I was taught to think that at every level of a tree, you are doing some amount of work.

Height 1 - do some O(n) of work
Height 2 - do some O(n) of work
Height log(n) - do some O(n) of work

Now In my head, If i visualize the work as a sum of all the work done, it seems like its $O(n\log(n))$ of work being done, which according to the master theorem is correct.

However, using the same intuition for the second recurrence is wrong as we know the master theorem tells us the answer is $O(n^2)$.

Any reason why the intuition seems to be correct for the first recurrence, and why it is wrong for the second?

What you are missing is the big O constants. In the first case, at successive heights you are doing work of $$n, 2\frac{n}{2}, 4\frac{n}{4}, \ldots = n,n,n,\ldots. $$ In the second case, at successive heights you are doing work of $$n^2,2\frac{n^2}{4}, 4\frac{n^2}{16}, \ldots = n^2,\frac{n^2}{2},\frac{n^2}{4}.$$ Since the series $1,1/2,1/4,\ldots$ converges, the total work is only $O(n^2)$.


Why should I care about lambda calculus I am a programmer by hobby. I stumbled upon lambda calculus from Kevlin Henney's talk lambdas to the slaughter and I was sold! It was an interesting new way of thinking that's entirely different than the way most of us program. But if I want to push someone to learn lambda calculus, what concrete benefits can I state.
I tried for long but the only one I could come up with is that its fun to play around. And it acts as the base of functional programming.
P.S. when I first heard about Lisp I couldn't understand why so many C brackets. After spending some time with lambda calculus, now I know ;P

Your question is a bit like this: "I am a programmer by hobby, and I learned about von Neumann machines. Why should I care about them?" And the answer is: because they're the theoretical model of computing machines that transformed our society.
Your question about the $\lambda$-calculus has a similar, but less grandiose answer. The $\lambda$-calculus was invented before Turing machines as an answer to "what is computation?" In itself it is not terribly practical, but it has been immensly influential in programming. Many programming concepts that we use today originated in the $\lambda$-calculus. Various languages support $\lambda$-calculus to various degrees, but almost all of them are in debt to $\lambda$-calculus to some degree (even the ones that are claimed to be "anti" $\lambda$-calculus).
If you are a hobby programmer, you should learn a programming language with good support for $\lambda$-calculus, as that will give you the joy of actually using the concepts. For instance, you can try one of the following:

Haskell
OCaml
Racket

Many popular languages have partial support for $\lambda$-calculus, which they implement to varying degree. If you know one of them, you could try the functional programming style (which is what $\lambda$-calculus is about), but keep in mind it's not the Real Thing:

Python lambda give rudimentary support for $\lambda$-calculus.
You can try functional programming in Javascript
Java has been retro-fitted with $\lambda$-expressions to give some rudimentary support for $\lambda$-calculus.
C++ has $\lambda$-expressions too.

LISP belongs to this list as well, as it does not have true support for $\lambda$-abstraction.


What does $\Sigma^0_2$-hard and $\Pi^0_2$-hard for a TM's Acceptance Problem mean? I'm reading about a Turing Machine $M$ and it says the problem of deciding whether M  accepts a string is "$\Sigma^0_2$-hard and $\Pi^0_2$-hard".

I haven't seen this kind of notation before and haven't found a good answer from searching. Is this a more specific form of saying NP-hard?

No, it's unrelated to NP-hardness.  $\Sigma_n^0$ and $\Pi_n^0$ are the levels of the arithmetical hierarchy.  $\Sigma_2^0$ is the class of problems that can be decide by Turing machines that have an oracle for the halting problem and $\Pi_2^0$ is the class of problems whose complement is in $\Sigma_2^0$.

There is the corresponding notion of the polynomial hierarchy, in which $\Sigma_1^\mathrm{P}$ is NP and $\Pi_1^\mathrm{P}$ is co-NP.


What are efficient data structures for inserting and accessing elements? Is there a data structure to keep a list of elements (not necessarily sorted) that performs the Access (by index) and Insert operations in a reasonable asymptotic time?

When I say "reasonable time", I mean that it should be equal to or better than $O(\log N)$.

I'm looking for a structure similar to a dynamic array, but I need a better behavior in the Insertion operation. When the array size grows, the time grows exponentially (Except at the end of the array).

A balanced binary tree should meet your needs.  You can achieve $O(\lg n)$ time for both operations, as long as the tree is kept reasonably balanced.

To support the "access by index" operation, you can augment the tree so that each internal node contains the number of children underneath it.  Insert operations still take $O(\lg n)$ time (find the place where to insert a new leaf, then traverse the path from that leaf to the root, incrementing the counter in each such node).  The "access by index" operation can be done using the counts in each node; they tell you at each stage whether to recurse to the left child or right child.

There are probably other data structures as well, but this should meet all of the requirements you listed.


Is maximum-leaves spanning tree np-complete? How can we show that a maximum-leaves spanning tree is NP-complete? what other np-complete problem we can use as our reduction base?

(maximum-leaves spanning tree: does G have a spanning tree with at least K leaves? )

The maximum leaf spanning tree(MLSPT) is equivalent to the minimum connected dominating set(MCDS), see here. So we just need to prove MCDS is NP-complete. It's easy to verify that the decision version of MCDS is in NP. Similar to proof of NP completeness of dominating set, we perform a reduction from vertex cover(VC), i.e., we prove that $VC \le_p MCDS$:

Given an instance $(G(V,E),k)$ of VC we construct an instance $(G'(V',E'),k)$ of MCDS as follows: $G'$ contains the complete graph on $V$, and for each edge $(u,v)\in E$, an edge vertex $x_{uv}$ is introduced, along with two extra edges $(x_{uv},u)$ and $(x_{uv},v)$. Formally. we have $V'=V\cup\{x_{uv}:(u,v)\in E\}$, $E' = E\cup\{(x_{u,v},u):(u,v)\in E\}$. The reduction can obviously be done in polynomial time. Note that any induced subgraph in $G'$ is a connected graph.

Let $S$ be a vertex cover of $G$. For any $v\in V'\setminus S$, if $v\in V$ then by the definition of vertex cover we know that $v$ dominated by $S$. If $v = v_{xy}$ is an edge vertex of some edge $(x,y)\in E$, because $(x,y)$ is covered by $S$, then $x\in S$ or $y\in S$, $v_{xy}$ is dominated by $S$. Thus $S$ is a connected dominating set of $G'$.

Suppose that $S$ is a connected dominating set in $G'$. We first observe that for any edge vertex $v_{xy}$ in, it can only be dominated by $x$ or $y$. For any edge vertex $v_{xy}\in S$, we replace it with $x$. The replacement does not increase the cardinality of $S$ and mantains $S$'s property of being a dominating set. Now $S$ contains no edge vertex, so every edge vertex is dominated by $S$, that is to say, every edge in $G$ has at least one endpoint in $S$. Therefore, $S$ is a vertex cover for $G$. $\square$


Status questionis for whether a machine can or can't "think" In his paper Computer Machinery and Intelligence, Turing addresses some arguments against the ability of a computer to pass the Turing test, such as the Theological Argument, the Mathematical Objection and the Argument from Consciousness. I wonder what is the current status of this debate; are there strong counterarguments for Turing's objections? Moreover, what is the most relevant bibliography on this topic?

EWD898 might be an intersting starting point.

  The Fathers of the field had been pretty confusing: John von Neumann speculated about computers and the human brain in analogies sufficiently wild to be worthy of a medieval thinker and Alan M. Turing thought about criteria to settle the question of whether Machines Can Think, a question of which we now know that it is about as relevant as the question of whether Submarines Can Swim.