Enumerator for Word and Halting Problem in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I was wondering what kind of grammar and enumerator could this be. And let the Wordproblem be  $ L = \{ \langle M, w \rangle | M  \space is \space TM  \space and  \space w \in L(M) \} $ and Halting Problem $ L = \{ \langle M, w \rangle | M  \space is \space TM  \space and  \space M \space halts \space on  \space w\} $
Ok for word problem: since there exists a sequence of $M_i$ I would start with $M_1$ and find all words for this TM and give them out. So if I have any TM is there a possibility to give all words out which are accepted by this TM? I probably would have to give all $w_i$ to it and compute the first i words for i steps, then i+1 words for i+1 steps and so on for a sequence of computable words $w_1, w_2,.. \in \Sigma^*  $ Or maybe something like DFS on all configurations. This really sounds like that only for one TM this could go on forever. So I would need to start the second TM for the same period of time after a while... Seems as if something similiar could work for Halting Problem. Do you have any more refined thoughts on this one?
Greets,
Felix

Let $\Sigma = \{0, 1\}$. Clearly $\Sigma^*$ is enumerable. For the word problem you can proceed as follows.

For each pair $(i,j) \in \mathbb{N}_+^2$ in dovetail fashion:

Let $w_i$ be the $i$-th word in $\Sigma^*$.
Check whether $w_i$ encodes a valid Turing machine $T$ (w.r.t. some fixed encoding). If not skip to the next iteration.
Simulate the Turing machine $T$ with input $w$ for at most $j$ steps.
If $T$ halts at the end of the $j$-th step, output $T$.

For the Halting problem you can do as follows:

For each pair $(i, j, k) \in \mathbb{N}_+^3$ in dovetail fashion:

Let $w_i$ be the $i$-th word in $\Sigma^*$.
Let $w_j$ be the $j$-th word in $\Sigma^*$.
Check whether $w_i$ encodes a valid Turing machine $T$ (w.r.t. some fixed encoding). If not skip to the next iteration.
Simulate the Turing machine $T$ with input $w_j$ for at most $k$ steps.
If $T$ halts at the end of the $k$-th step, output $\langle T, w_j \rangle$.


Streaming parsing algorithms A parser is a procedure which decides if an input belongs to a certain language and produces a witness in the form of a parse tree.

Let a streaming parser be a parser which for any prefix $u$ can produce a partial parse tree corresponding to the productions that must be expanded to eventually accept any completion $uv$ of the prefix, for some completion $v$.

For example, if parsing the CFG
$$
\begin{array}{lcl}
S &\to& (a S+ b)
\end{array}
$$

then upon reading the prefix $aaa$, the streaming parser should report that any parse tree must consist of three top-level expansions of $S$.

Edit: I have two motivations for streaming parsing. The first is to provide a best-case constant bound on memory usage in the case where productions can always be resolved by a constant amount of lookahead. The second is to allow the consumer to lazily tear down the parse tree as the result is produced, e.g. by scheduling the execution of semantic actions associated with productions.

I am also interested in streaming parsing based on other foundations than context-free grammars, such as top-down parsing (parsing expression grammars, parser combinators, etc.).

Is there any existing work on such parsing algorithms?

The first solution coming to mind is an extension of Brzozowski's derivatives as context-free grammars are closed under derivative operation with respect to a letter.

Here that question answered: https://cstheory.stackexchange.com/questions/3280/generalizations-of-brzozowskis-method-of-derivatives-of-regular-expressions-to


Efficient algorithm to compute the diameter of a convex set? Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set?
It is possible to do it efficiently for a set of points, but imagine that the set is described by the intersection of linear equations in high dimensional space, so the number of vertices of the set can be exponential in the number of inequalities.
Given a direction, we can easily compute the distance of furthest points along that direction using linear programming. The question is how do we find that direction?

I suspect that if the points in your set are expressed as $Ax \le b$ and you're considering the Euclidean distance, then you can solve the following quadratic program with the ellipsoid method:
$$
\max  \sum_i (x^2_i+y^2_i-2x_i y_i) \\
Ax \le b \\
Ay \le b.
$$
Where we used the fact that optimizing $|x-y|$ is the same as optimizing $ \frac{1}{2} |x-y|^2 = \frac{1}{2} \sum_i (x_i-y_i)^2 = \frac{1}{2} \sum_i (x_i^2+y_i^2 - 2x_iy_i)$.
The objective function can also be written as $\frac{1}{2} z^T Q z$, where $z=(x,y)$ and:
$$
Q= \begin{bmatrix}
I & -I \\
-I & I
\end{bmatrix}.
$$


How do I derive a regular grammars from this regular expression? How do I derive a regular grammars from this regular expression?

(a or b)*ba(ba)*

I'm stuck with the last part
so

S -> A | B | C
A -> aA | bA
B -> bC
C -> cD
D->bE ?
E->af | ^ ?

Any help would be appreciated thanks!

Use Thompson's algorithm to convert the regular expression to a NFA.  Then, you can directly read a regular grammar off, given the NFA: each non-terminal represents one state of the NFA.


Can type information be encoded in the untyped lambda calculus? I'm going to take the few pieces of knowledge I have about lambda calculi and ask a pair of very uninformed questions :-)

Is it possible to "embed" the corners of the lambda cube within the untyped lambda calculus?

It would seem that this might lead to a language where the programmer implements the type system in the language, rather than having it already implemented in the compiler.  Also, maybe the concept of type system could be generalized to "any arbitrary compile-time or run-time constraint checking".  Does such a language already exist?

As mentioned in the comments, it is possible to reduce simply typed lambda calculus to untyped lambda calculus. This is the approach associated with Alonzo Church, called "Church Types" or "intrinsic types". Here, types are embedded in the language, and are intrinsic to the language. Still, the language can be stripped of it's types.

However, it is also possible to construct simply typed lambda calculus from untyped lambda calculus. This approach is associated with Haskell Curry, called "Curry Types" or "extrinsic types". Here, types can be derived from the AST of the language.

The latter type is what you are looking for. A thorough overview of the subject is here


Why is the common explanation to the halting problem an oversimplification? So watching many youtube channels, the explanation to the impossibility of solving the halting problen involves assuming you can, doing the opposite, and feeding it back into itself to create a paradox.
What I don't get is why this is an (over)simplification. The logic seems to check out. What is the flaw in this reasoning?

It's basically correct, but it can be viewed as an oversimplification because that one sentence doesn't explain the details of how to feed it back into itself or why "feeding it back into itself" creates a paradox -- that requires additional explanation or justification.


Absorption Law Proof by Algebra I'm struggling to understand the absorption law proof and I hope maybe you could help me out.

The absorption law states that: $X + XY = X$
Which is equivalent to $(X \cdot 1) + (XY) = X$

No problem yet, it's this next step that stumps me. How can I apply the distributive law when there are two "brackets"?

How can I manipulate $(X \cdot 1) + (XY) = X$ to give me $X \cdot (1+Y)$?

I understand that the absorption law works. I would just like to see how the algebra proof works.

Thank you!

First of all, this is a math question.

I think you are confused on how brackets are used. They indicate precedence of operations, and can be used anywhere, even in places where such indication is not necessary. For example,
$$3 \times 5 + 8$$
and
$$(3 \times 5) + 8$$
are both legitimate expressions and they mean exactly the same thing.

Your expression
$$(x \cdot 1) + (x \cdot y)$$
is exactly the same as
$$x \cdot 1 + x \cdot y.$$
So we may calculate
$$(x \cdot 1) + (x \cdot y) =
  x \cdot (1 + y) =
  x \cdot 1 = x.$$


Greedy algorithm for maintaining drugs Given $n$ drugs such that each drug $d_i$ should maintain in interval
$[c_i,h_i]$.We want to minimize number of containers to maintain
medicines in compatible interval.

My answer is as follows:
I use following greedy algorithm:
in each iteration, for remaining drugs, find an interval that have maximum number of compatible drugs, and remove that drugs, and add to container.
any one can help to find an counter example or proving above idea?

Here is a counterexample.
There are 6 drugs with intervals $$[1, 5],\ [2,8],\ [3,8]$$
and $$[6, 11], \ [6,12],\ [9, 13].$$
We can use containers of volume 4 to cover the first 3 drugs and containers of volume 10 to cover the last 3 drugs. So it is enough to use 2 kinds of containers.
If we use the greedy algorithm, we would first cover $$[2,8],\ [3,8],\ [6, 11], \ [6,12]$$
using, for example, containers of volume 7. And then the remaining two intervals $$[1,5],\ [9,13]$$
that are disjoint will need additional two containers of different volumes to cover.


How do I do a biased shuffling of a deck of cards? I currently have a deck of cards (in fact this deck is an array of sorted elements in descending order as indicated by the picture above), that I want to shuffle. However, the caveat is that I want the card near the top of the deck to be shuffled to a new position relatively close to the top, while a card near the bottom to be shuffled anywhere including the middle and bottom, but have a very unlikely chance of ending up near the top of the deck.

Therefore I would break down the problem as following:

A card in the top 33% of the deck has about:

90% chance of ending up in the top 33%
8% chance of ending up in the middle 33%
2 % chance of ending up in the bottom 33%

A card in the middle 33% of the deck has about:

5% chance of ending up in the top 33%
90% chance of ending up in the middle 33%
5 % chance of ending up in the bottom 33%

A card in the bottom 33% of the deck has about:

2% chance of ending up in the top 33%
8% chance of ending up in the middle 33%
90 % chance of ending up in the bottom 33%

The percentages of the shuffle do not need to be constant. I wouldn't mind if they were continuous probabilities across the entire deck. Would this boil down to a randomized selection problem? I have no clue as to how to approach this problem as of now.

I needed this same thing, a biased shuffling for local/proximity shuffling, but couldn't find any answers, so this is my attempt to create one.
Pseudocode:
For X passes through the array from 0 to len(array)-1:
    Roll for a 50% chance to swap index and index+1
    Swap direction of array traversal

Python:
import numpy as np
import matplotlib.pyplot as plt

swap_passes = 50

player_count = 100

positions = {}

player = np.arange(1,player_count+1)
for p in player:
    positions[p] = []

for i in range(10000):
    player = np.arange(1,player_count+1)

    for j in range(swap_passes):
        pre_rand = np.random.randint(0,2,player_count)
        if j%2 == 0:
            for i in range(len(player)-1):
                if pre_rand[i] == 0:
                    player[i], player[i+1] = player[i+1], player[i]
        else:
            for i in range(len(player)-1,0,-1):
                if pre_rand[i] == 0:
                    player[i], player[i-1] = player[i-1], player[i]

    for idx, p in enumerate(player):
        positions[p].append(idx)

fcs = [(1,0,0,0.3),(0,1,0,0.3),(0,0,1,0.3),(0.5,0.5,0,0.3),(0,0.5,0.5,0.3)]
plt.figure()
for idx, i in enumerate([1,30,50,70,100]):
    bins = np.arange(0,player_count+1)
    plt.hist(positions[i], bins=bins, fc=fcs[idx])
plt.title('Histogram of indices: 1, 30, 50, 70, 100. 10000 trials, 50 swap passes.')

Results:

Looks roughly gaussian. Increasing the number of passes will increase the spread of the distribution.


Proving correctness of an AVL-Tree colouring algorithm I came up with the following recursive algorithm to colour the nodes of an AVL tree so that the resulting tree is red-black. The logic is that the algorithm first colours the root and, recursively, the left and right subtrees black. Since it is an AVL tree, if the root has height h, one path to a leaf takes distance h, and another is h-1. If h is odd the two subtrees from the root have heights h-1 (even) and h-2 (odd), with the even subtree having an extra black node, hence to be coloured red.

(pseudocode)
colour_tree(root(T)):
r <- root(T)
if r = null:
    return
colour(r) = "black"

colour_tree(right(r))
colour_tree(left(r))

if isodd(height(r)):
    if right(r) != null and iseven(right(r)):
        colour(right(r)) = "red"
    if left(r) != null and iseven(left(r)):
        colour(left(r)) = "red"

I am having trouble starting on a proof of correctness for this algorithm. I know that for any tree with height h, there are at least $\lceil (h+1)/2 \rceil$ blacknodes, and intuitively it seems like I'd have to perform induction on the height, but I am not sure where to start. Thanks.

You are recursing structurally, so you might want structural induction, but in AVL trees structural induction and induction on height are similar. You probably want to prove something a bit stronger than you need at the end - perhaps something like "AVL trees with height n return RB trees with black height n, and if n is even then neither child of the root is colored red."


Why is the video game Braid Turing-complete? It's written in wikipedia https://en.wikipedia.org/wiki/Turing_completeness#Games that the video game Braid is Turing-complete.

I've played Braid before but I can hardly reconcile it with Turing completeness. In what sense is it Turing-complete?

Because Braid can simulate a variant of Rush Hour, which is at least PSPACE-hard.

Additionally, Braid itself is undecidable because it can simulate a counter machine which is equivalent to a Turing machine, and thus determining if any general Braid level is solvable is similar to solving the halting problem, which is undecidable.


How to find nearest number in a sequence that is strictly smaller than given number Given a sequence of numbers $l_1, \ldots, l_k$, I want to find for each $i$ the nearest numbers to the left and right of $l_i$ (if any) that are strictly smaller than $l_i$. Is it possible to do this in linear time?

Converting my comment into an answer.

Here is an algorithm for the interpretation that you are looking for $l_j$ such that $l_j \lt l_i$ and $|i-j|$ is the smallest.

  Traverse left to right, push stuff on stack. If new element to be pushed >= top
  element. If new element < top element keep popping the stack till top
  < new element. For the elements popped, the new element is the $l_j$


Asymptotic of divide-and-conquer type recurrence with non-constant weight repartition between subproblems and lower order fudge terms While trying to analyse the runtime of an algorithm, I arrive to a recurrence of the following type :

$$\begin{cases}
  T(n) = \Theta(1), & \text{for small enough $n$;}\\
  T(n) \leq T(a_n n + h(n)) + T((1-a_n)n+h(n)) + f(n), & \text{for larger $n$.}
\end{cases}$$
Where:

$a_n$ is unknown and can depend on $n$ but is bounded by two constants $0<c_1\leq a_n \leq c_2 < 1$.
$h(n)$ is some "fudge term" which is negligeable compared to $n$ (say $O(n^\epsilon)$ for $0\leq \epsilon < 1$).

If $a_n$ was a constant, then I could use the Akra-Bazzi method to get a result. On the other hand, if the fudge term didn't exist, then some type of recursion-tree analysis would be straight-forward.

To make things a bit more concrete, here is the recurrence I want to get the asymptotic growth of:

$$\begin{cases}
  T(n) = 1, & \text{for n = 1;}\\
  T(n) \leq T(a_n n + \sqrt n) + T((1-a_n)n+\sqrt n) + n, & \text{for $n \geq 2$}
\end{cases}$$
Where $\frac{1}{4} \leq a_n \leq \frac{3}{4}$ for all $n\geq 1$.

I tried various guesses on upper bounds or transformations. Everything tells me this should work out to $O(n\log(n))$ and I can argue informaly that it does (although I might be wrong). But I can only prove $O(n^{1+\epsilon})$ (for any $\epsilon>0$), and this feels like something that some generalization of the Master theorem à la Akra-Bazzi should be able to take care of.

Any suggestions on how to tackle this type of recurrence?

According to the OP, to complete the proof we need to prove that for large enough $n$,
$$
(a_n n + \sqrt{n})^{a_n + 1/\sqrt{n}}((1-a_n)n + \sqrt{n})^{1-a_n + 1/\sqrt{n}} \leq n.
$$
Taking out a factor of $n^{1+2/\sqrt{n}}$, we get
$$
(a_n + 1/\sqrt{n})^{a_n + 1/\sqrt{n}}
(1-a_n + 1/\sqrt{n})^{1-a_n + 1/\sqrt{n}} \leq n^{-2/\sqrt{n}}.
$$
Dividing by $(1+2/\sqrt{n})^{1+2/\sqrt{n}}$, we get
$$
\left( \frac{a_n + 1/\sqrt{n}}{1 + 2/\sqrt{n}} \right)^{a_n + 1/\sqrt{n}}
\left( \frac{1-a_n + 1/\sqrt{n}}{1 + 2/\sqrt{n}} \right)^{1-a_n + 1/\sqrt{n}} \leq
\frac{1}{n^{2/\sqrt{n}} (1+2/\sqrt{n})^{1+2/\sqrt{n}}}.
$$
Raising to the power $1/(1+2/\sqrt{n})$, and defining $p = (a_n + 1/\sqrt{n})/(1 + 2/\sqrt{n})$, we get
$$
p^p (1-p)^{1-p} \leq \frac{1}{n^{(2/\sqrt{n})/(1+2/\sqrt{n})}(1+2/\sqrt{n})}.
$$

The left-hand side is $1/\exp h(p)$, where $h(p)$ is the entropy function. Hence it is maximized when $a_n = 1/4$, at which point $p \approx 1/4$. Since $(1/4)^{1/4} (3/4)^{3/4} < 1$, for large enough $n$ we can bound the left-hand side by some $\theta < 1$.
As for the right-hand side, as $n\to\infty$ it tends to $1$. Indeed, taking logarithm, we get
$$
\frac{2\log n}{\sqrt{n} + 2} + O\left(\frac1{\sqrt{n}}\right) \longrightarrow 0.
$$
In particular, for large enough $n$ it will be larger than $\theta$.


Is knowing ALL factors of a large number an NP? Say I have a number 45

What are the factors of 45?

1, 3, 5, 9, 15, 45

Is there any other factors?

I know that if I want to find some non trivial factor of some number, say 45, I know it's in NP.

I can non deterministically choose some 2 numbers and verify that those 2 numbers are factors of my large number. Verifying is easy. Just multiply the 2 numbers and see if it match.

What about if I want to find ALL factors of a large number? Is it still in NP?

How do we verify, in polynomial time, that 1, 3, 15, 45 are all the factors of 45? It turns out it isn't because we still have 5 and 9. But say someone says

Okay, 1, 3, 15, 45 are all factors of 45. How do we verify it in polynomial time?

Is it in NP?

Is it NP complete?

Does it has P verifier?

Basically, I wonder if the following problems are in NP

Say n is a number

Say S is a set of numbers between 1 and n

Is S the set of ALL factors of n or not.

A program should say it's false when

One element of S, say s, is not a factor of n. We can verify this by dividing n by s and see if there are some reminders.
There exist a number, say f, not in S, but is actually a factor of n.

Now is that problem NP?

NP is a class of decision problems. Only decision problems can belong to NP. The problem "factor a number" is not a decision problem.

You can make up many decision problems that attempt to capture factoring. Here is one: the language of all quartets $(n,i,j,b)$ such that the $j$th bit of the $i$th prime factor of $n$ is equal to $b$. This language is in NP, since the factorization of $n$ functions as a witness (this uses the fact that primality can be tested in polynomial time; in fact, it is enough to know that primality is in NP, which is an easier fact). It is strongly suspected that this language is not NP-complete.


How does a turing machine with doubly infinite tape simulate a normal-taped turing machine? The intuition is that on any input, we can write a symbol like $\#$ on the left that tells the machine to not move past this symbol. However, I'm running into problems trying to show this using the formal definition of a turing machine. It's not simple using the usual 7-tuple definition. Any help would be appreciated.

Given the doubly infinite machine $M = (Q,\Gamma,\sqcup,\Sigma,\delta,q_{0},F)$ where:

$Q$ is the set of states,
$\Gamma$ is the tape alphabet,
$\sqcup \in \Gamma$ is the blank symbol,
$\Sigma \subseteq \Gamma\setminus\{\sqcup\}$ is the input alphabet,
$\delta: Q\setminus F\times\Gamma\rightarrow Q\times\Gamma\times\{L,R\}$  is the transitions function (there are various common modifications to $\delta$ which you can add in if you wish),
$q_{0} \in Q$ is the start state, and
$F$ is the set of final states,

we can simulate a singly infinite Turing machine with the following modifications to $M$:

add a new symbol $\#$ to $\Gamma$ which will mark the "left-hand end" of the simulated tape,
add the new states $k_{0}$, $k_{1}$ and $r$ to $Q$,
make $k_{0}$ the new start state,
add the following transitions:

$(k_{0}, x) \mapsto (k_{1},x,L)$ for every $x \in \Gamma$
$(k_{1}, \sqcup) \mapsto (q_{0}, \#, R)$
$(q_{i}, \#) \mapsto (r, \#, L)$

make $r$ a reject state in whatever way you're handling reject states.

This new machine starts (as suggested in the question) by writing a new, special, end-of-tape symbol just to the left of the input. Then if it ever sees that symbol again, it rejects (it has "fallen off the tape").

A similar technique can be used to prevent a singly infinite TM from falling off the left-hand end of the tape, so you can also encode that into the machine, and it would work similarly.


Circular path visiting fewest nodes I don't know what this problem is called, so I haven't been able to Google for it, but I have a graph problem that I feel must have been solved many times before, and I just cannot find a good solution.
Given a directed graph, and nodes A and B, I want to find a route that takes me from A to B and back to A again, going through the fewest number of nodes. I have attempted to solve it with various versions of the shortest path problem, but it doesn't get me there. There could be a short path [A]->[1]->[2]->[B] from A to B, and one [B]->[3]->[4]->[A], that I can stitch together to get a tour that visits four nodes besides A an B (the nodes 1, 2, 3, and 4). But there might also be longer paths, [A]->[x]->[y]->[z]->[B] and [B]->[z]->[y]->[x]->[A] that ends up only visiting three nodes, because the paths overlap.
If I try to use a standard shortest-path approach, my thinking was to conceptually double the graph, so edges out of B would go into a copy of the graph, and look for the shortest path from A to A' where A' is the copy of node A. That gives me a shortest path cycle, but if I visit the same node going from B to A as I do going from A to B, then it counts as much as visiting a new node, where it should be free. The cost of visiting a node in the "copied" graph depends on the path I took in the first graph, and if I start carrying that information with me, the heap I use for finding the shortest path has to remember not only a node but a path. The state-space explodes, and so does the running time.
I am not convinced that this is something that has an efficient solution, and I might be able to brute-force something with a branch-and-bound approach that does track paths, changing the scoring of nodes in the "copied" graph. But before I start thinking along that path (no pun intended), I would like to know that I am not missing something trivial and that the problem has an efficient solution.
I would greatly appreciate any pointers to how to attack this problem, or just confirmation that it might be a problem that doesn't have an efficient solution, so I can give up on trying to find one.

Consider a directed cycle from $A$ to $B$ and back with the minimum number of nodes, and subject to that, with the minimum number of edges. The directed cycle is composed of two paths: $A\to B$ and $B\to A$. Since the cycle minimizes the number of edges, these paths are simple. However, it may be that the two paths are not disjoint. If so, let $x$ be the first node on $B\to A$ which appears in $A\to B$. This decomposes the cycle as follows:
$$ A\to x \to B \to x \to A. $$
By construction, the cycle $x \to B \to x$ is simple (no nodes are repeated). Also, the condition on the number of edges guarantees that all nodes on this cycle do not appear in $A\to x$ or $x \to A$ (otherwise, we could take shortcuts that would shorten the cycle). Therefore, if we denote the optimal cost of an $A\to B\to A$ cycle by $c(A,B)$ (excluding the two endpoints) and the optimal cost of a simple $A\to B\to A$ cycle by $s(A,B)$, we have
$$
c(A,B) = \min(s(A,B), \min_x c(A,x) + s(x,B) + 1).
$$
We can compute $c(A,B)$ iteratively: start with $c(A,B) = s(A,B)$ (which you know how to compute), and then repeatedly apply the equation above until the situation stabilizes, which should happen within $n$ iterations or so.


Are all problems approached and solved in fundamentally the same way? This question might be a bit to vague, not make sense, or not developed enough yet to ask, but I thought I might give it a shot.

This questions stems from a conversation a friend and I were having about the google interview process. It boiled down to my argument that they are searching for individuals who are fundamentally better problem solvers than others (His argument is that prior job experience proves this, mine is that it doesn't).

This got me thinking. Say we want to solve a simple problem 2 + 2, we could go about this the simply way and just count 1 2, 3 4 to get to the answer or we could chose a much more complex way to arrive there. I argue that both ways fundamentally solve the problem the same way; that the more complex solution is reducible to the simplest.

This linked up in my brain to Big O. It has been shown that all problems in NP are equivalent and can be translated (reduced?) to each other (I might be completely wrong on this); essentially if you solve one (in P time) you solve them all. It kind of shows to me that all problems within their given class are fundamentally the same.

This leads me to question, is the way that problems are solved fundamentally the same? Moreover, is there a way to solve all problems (nothing about running time)?

Again disclaimer, not a full complete thought. I just wanted to get it out there before I forget it and never think of it again. I found it interesting enough to share and just wanted input. Please correct if (where.) I am wrong.

What you're missing is that, although all NP-complete problems can be reduced to one another, so it is true that solving one lets you solve them all, that doesn't mean that they're all equally easy, so they're not all "the same problem".

In particular, the reduction takes some amount of time to perform.  Although all problems in NP can be reduced to, say, SAT, that doesn't mean that all problems in NP are as easy as SAT.  Some require very little effort to translate to SAT; others require much more effort. And there's no bound1 on how much effort might be needed, as you look at more and more complex problems within NP.

A way to make this concrete is with the time hierarchy theorem.  That says that, essentially, allowing more time for computations lets you compute more things, and it applies to nondeterministic machines as well as deterministic ones.  So, solving SAT instances takes some amount of time but, if you allow yourself more time than that, you can solve strictly more things.

1 OK, its always a polynomial but there's no bound on the degree of that polynomial.


Kraft's inequality for Huffman coding Is it true to say that Huffman codes always satisfy Kraft's inequality with strict equality?

At first, I thought the statement is wrong since for Huffman coding there is no assumptions on the probabilities. However, when I tried evaluation the Kraft inequality for several Huffman codes, I realized that it's got nothing to do with the probabilities. It's the algorithm.

I looked for a nice mathematical proof for this, but couldn't find any. Would appreciate your help.

All Huffman codes satisfy Kraft’s inequality with strict equality. We will give two proofs of this fact, one specific to Huffman codes, and the other applying to all minimum redundancy codes.

First proof. The first proof is inductive. Recall that Huffman’s algorithm proceeds as follows. We choose the two symbols with minimal probability, and merge them. We then run the algorithm on the new distribution. Finally, we split the merged symbol into two symbols by adding a suffix of 0 to one of them and of 1 to the other.

When there are only two symbols left, Huffman’s algorithm assigns them the codewords 0 and 1, and since $2^{-1} + 2^{-1} = 1$, we see that Kraft’s inequality is satisfied with equality.

Now suppose that there are more than two symbols. Huffman’s algorithm merges two of them, and then runs on the resulting code. The induction hypothesis shows that Kraft’s inequality is satisfied with equality on the new code. The final step is splitting one of the symbols. In this step, a codeword of length $\ell$ is replaced by two codewords of length $\ell+1$. Since $2^{-\ell} = 2 \cdot 2^{-\ell-1}$, we see that the final code also satisfies Kraft’s inequality with equality.

Second proof. The second proof applies to any minimum redundancy code. We start by associating with each prefix code a binary tree. This is done as follows. If the prefix code consists of just the empty word, then the binary tree is a leaf. Otherwise, we construct a binary tree for all codewords starting with 0, another one from all codewords starting with 1, and join the two at the root. If we think of the edges as labeled by 0 and 1, then we can recover the codewords by traversing the tree from root to leaves and concatenating the symbols written on the edges.

A simple induction shows that $\sum_f 2^{-\ell(f)} \leq 1$, where $f$ goes over all leaves, and $\ell(f)$ is the depth of $f$; this is just Kraft’s inequality. The same proof also shows that equality holds iff all internal nodes have exactly two children. In this case we call the code complete.

If the code is incomplete, there is an internal vertex with only a single child. We can replace this vertex by its child, thus obtaining a new code in which no codeword gets longer, and some get strictly shorter. The new code has less redundancy than the original one. This shows that if we start with a minimum redundancy code, then the code must be complete, and so Kraft’s inequality holds with equality.


The maximum & minimum number of sources that can be multiplexed so that no data loss occurs on TOKEN BUCKET? A link of capacity 100 Mbps is carrying traffic from a number of sources. Each source generates an on-off traffic stream; when the source is on, the rate of traffic is 10 Mbps, and when the source is off, the rate of traffic is zero. The duty cycle, which is the ratio of on-time to off-time, is 1 : 2. When there is no buffer at the link, the minimum number of sources that can be multiplexed on the link so that link capacity is not wasted and no data loss occurs is S1. Assuming that all sources are synchronized and that the link is provided with a large buffer, the maximum number of sources that can be multiplexed so that no data loss occurs is S2. The values of S1 and S2 are, respectively,

A)  10 and 30

B)  12 and 25

C)   5 and 33

D)  15 and 22

I have solved the part (i) of the problem to find the minimum no. of stations & got 10 as there is no bucket,so for no data loss I equated the incoming traffic rate by S1 stations = Maximum capacity of the channel.In 2nd part I'm having trouble what will happen when a buffer is placed.Please help.Make me correct if 1st part is not correct.

A is correct. As 1st part is already described i will explain derivation of S2 only.
Let there are N stations. When buffer is added then even when source is off, data will persist so considering duty cycle here we say that the actual data transmitted per unit time during the whole duty cycle is (1/3)10 [for 1 unit of on-time data is transmitted and for another 2 unit of off-time it stays in buffer so in 3 unit time 10Mbps data is tranferred]. This is the case will all other N-1 stations also. So adding all should be = Max capacity of channel.
N(1/3)*10 = 100
N=30


Determining whether the language of a DFA is closed under reversal The question and its answer is given below:

Let $S = \{ \langle M \rangle \mid \text{$M$ is a $\textsf{DFA}$ that accepts $w^{\mathcal{R}}$ whenever it accepts $w$}\}$. Show that $S$ is decidable.
Answer:
For any language $A$, let $A^{\mathcal{R}} = \{w^{\mathcal{R}} \mid w \in A\}$. If $\langle M \rangle \in S$, then $L(M) = L(M)^{\mathcal{R}}$. The following $\textsf{TM}$ $T$ decides $S$.
$T = $ “On input $\langle M \rangle$, where $M$ is a $\textsf{DFA}$:

Construct $\textsf{DFA}$ $N$ that recognizes $L(M)^{\mathcal{R}}$.
Run $\textsf{TM}$ $F$ from Theorem 4.5 on $\langle M,N \rangle$, where $F$ is the Turing machine deciding $EQ_{\textsf{DFA}}$.
If $F$ accepts, accept. If $F$ rejects, reject.”

But I do not understand in the first line of the answer, in the second statement why does it say that $L(M) = L(M)^{\mathcal{R}}$, could anyone explain this for me please?

For a language $L$, we define the reverse language $L^{\mathcal{R}}$ by
$$ L^{\mathcal{R}} = \{ x^{\mathcal{R}} : x \in L \}. $$
In words, $L^{\mathcal{R}}$ is obtained from $L$ by reversing all words.

It follows that $L = L^{\mathcal{R}}$ if and only if, for each word $x$, we have $x \in L \Leftrightarrow x^{\mathcal{R}} \in L$.


How to prove the existence of the spectral expander with the given parameteres? I need to prove the existence of the $(1944, 144, 0.5)$ spectral expander. I tried to construct it using tensor product of the following graphs:
$$
(1944, 144, 0.5) = (9^2, 9, 1/3) \otimes (24, 16, 0.5)
$$
I already know that expander with parameters $(9^2, 9, 1/3)$ exists and corresponds to the affine expander, but I am not sure about $(24, 16, 0.5)$ one.

There are also expanders with the following parameters: $(3, 2, 1/2)$ — complete graph on 3 vertices and $(8,8, 0)$ — complete graph on 8 vertices with the loop in each vertex. So we have the following tensor product:
$$
(1944, 144, 0.5) = (9^2, 9, 1/3) \otimes (3, 2, 1/2) \otimes (8,8, 0)
$$


How are HOGs calculated? Histograms of oriented gradients for human detection seems to be the paper from which all other papers cite when they use HOG features. However, this was the only description I could find in it:

  [...] In practice this is implemented by dividing the image window into small
  spatial regions (“cells”), for each cell accumulating a local 1-D histogram of
  gradient directions or edge orientations over the pixels of the cell. The
  combined histogram entries form the representation. For better invariance to
  illumination, shadowing, etc., it is also useful to contrast-normalize the
  local responses before using them. This can be done by accumulating a measure
  of local histogram “energy” over somewhat larger spatial regions (“blocks”) and
  using the results to normalize all of the cells in the block. We will refer to
  the normalized descriptor blocks as Histogram of Oriented Gradient (HOG)
  descriptors.

It is not clear to me how the HOG features are now calculated:

How big are the cells? How is that size chosen?
What is a 1-D histogram?
What is a histogram of directions?

Suppose we have the following 5x5 patch of a grayscale image (I hope that is a normal size for a cell - if not, please just copy this block as often as necessary or give another example):

  000 025 255 016 200

  000 255 255 017 201

  010 012 210 012 111

  000 000 000 000 000

  255 254 255 254 255

What would be the HOG features of it?

(Can you give a citable resource for the description?)

First, let's talk about what a histogram of directions is.  You can think of the image as a 2D discrete function of x and y: I(x,y). You can take partial derivatives of this function: Ix and Iy. So at each pixel you have the gradient, which is the vector (Ix(x,y), Iy(x,y)). If you compute the magnitude of the gradient, and look at it as an image, you will see the edge map. If you compute the orientation of the gradient at each pixel, you get the edge orientation at that pixel. This is what you take a histogram of.

You divide the range of orientations into some number of bins (let's say 8). Then you look at a single cell. Inside the cell you compute the gradient of every pixel, take its orientation, and add it to the appropriate histogram bin. You can also weigh the contributions by the gradient magnitude, so that pixels with stronger edges contribute more to the histogram.  Once you are done, the histogram encodes the distribution of edge orientations within the cell. Dividing the image into cells preserves some of the spatial layout of the edges.

The size of the cell is a parameter, which you can tune. Typically, it is set to 8x8. If the cell is too small, then you do not have enough pixels for a meaningful histogram. If the cell is too large, then you lose too much of the spatial information.


Boruvka MST algorithm using doubly linked lists I'm reading Sedgewick & Wayne's Algorithms book, and one of the questions in one of the chapters is the following:

  Develop an implementation of Boruvka's algorithm that uses doubly-linked circular lists to represent MST subtrees so that subtrees can be merged and renamed in time bounded by E during each stage (and the union-find data type is therefore not needed).

I'm aware of the standard version of Boruvka's algorithm that uses a union-find data structure to do the merges and check subtree identifiers (there is also an implementation on the book's official website )

But I'm not being able to figure out how to improve the performance of the algorithm by replacing the union-find data structure for subtrees represented by doubly-linked circular lists.

Any ideas? Thanks!

I came across your question in pursuit of the same answer. Anyway this comment gives a hint, I would say, why a detailed algorithm is not there or easily searchable:

"It is possible to remove the lg*E factor to lower the theoretical bound on the running time of Boruvka’s algorithm to be proportional to E lg V, by representing MST subtrees with doubly-linked lists instead of using the union and find operations. However, this improvement is sufficiently more complicated to implement and the potential performance improvement sufficiently marginal that it is not likely to be worth considering for use in practice (see Exercises 20.66 and 20.67)."

(from: http://apprize.info/c/algorithms_2/36.html)


Non Deterministic Turing Machine Can anyone give an example of a NDTM for a problem (which cannot be solved with DTM) with transition function?

There is no such problem. All problems that can be solved (i.e., decided) by a non-deterministic Turing machine $T$ can also be solved by a deterministic Turing machine that simulates $T$.


Complement of Non deterministic Finite Automata It's known that the complement of a DFA can be easily formed. That is, given a machine $M$, we can construct $M'$ such that $L(M') = \Sigma^* \setminus L(M)$.

Is it possible to construct such a complement for a non-deterministic finite automation (NFA)? To my knowledge, it isn't.

I'm going to assume that you know that there is an equivalence between DFAs and NFAs in the following sense: For every NFA $M$ there exists a DFA $M'$ such that $L(M') = L(M)$. I'm also going to assume that you know how to, given $M$, calculate $M'$. These are standard methods and they (and their proofs) can be found in any good textbook on automata such as: Hopcroft and Ullman

Given these facts the result is almost immediate: Given an NFA $N$ all you have to do is calculate the corresponding DFA $N'$ and use the complement algorithm which you've mentioned you already know. The resulting DFA is an NFA (since DFAs are just special cases of NFAs) which accepts the complement of the language accepted by the NFA you started with.

So to answer your question, yes it is possible to construct such an NFA, however, if you want to do it quickly you may have some problems


Invertible function that randomizes order I am looking for an invertible discrete function $f:\{0,1,2,\dots,n-1\} \to \{0,1,2,\dots,n-1\}$ for some given integer $n$.  I want $f(0),f(1),\dots,f(n-1)$ to return all the integers in range $[0..n)$ exactly once, but in a "messy", random-seeming arrangement.  I anticipate that $n$ will be not bigger than $2^{30}$.

I thought about finding a generator for the group <Zn,*>, but I'm not sure if it would work for any given $n$ (would it?).  Any other ideas?

You are looking for a pseudorandom permutation on the set $\{0,1,2,\dots,n-1\}$.  In cryptography, this has been studied under the (counter-intuitive) name "format-preserving encryption".  There are a number of constructions you could use for your purposes.

There's a bunch of research literature on the problem, with different schemes that are optimized for different values of $n$.  You can also find some summaries on Cryptography.SE.

I recommend you start by reading the question and the answers at Lazily computing a random permutation of the positive integers and Encrypting a 180-bit plaintext into a 180 bit ciphertext with a 128-bit block cipher and What are the examples of the easily computable "wild" permutations?.


If we can $\epsilon-$cover one set with $\frac{K}{2}$ elements and another with 2 elements why isn't their set product $2^{\frac{K}{2}}$ cover? I was reading the following paper on Robustness and Generalization (and covering numbers)and I was reading their example 1:

which didn't quite make sense to me. The reason it didn't make sense is that intuitively it seems to me that each region $X_i$ could have the label either +1 or -1, so it seems to me that the partition of Z should be exponential:
$$2^{\frac{K}{2}}$$
because it region can have either label +1 or -1. However, instead it seems to be that instead if 2 times the epsilon cover of the other set X, which seems puzzling. Any ideas why?

Ok for background definition:
Epsilon cover means the smallest set size that can $\epsilon$ cover some target set T. i.e.:
$$ N(\epsilon,T,\rho) = \min \{ |\hat T | \mid T \subset \cup_{\hat t \in \hat T} B(\hat t; \epsilon, \rho ) \}$$
where $B(\hat t; \epsilon, \rho ) = \{ x \mid \rho(\hat t, x) \leq \epsilon \}$ is the epsilon ball around $\hat t$.
Ab algorithm $A_s(x)$ has a margin $\gamma$ if every point in the input space around it would be classified the same way. i.e. as the paper wrote:
$$ A_{s}(x) = A_s(s_{j | x}) ; \forall x: \| x - s_{j|x}\|_2 < \gamma $$
for more definition the paper has them pretty much on the page and the page before Example 1 I am referencing.

Given a cover for $\mathcal{X}$, you seek to "cover" $\mathcal{X}\times\{-1,1\}$.
To do so, you take any set $A$ from the cover of $\mathcal{X}$, and consider the sets $A\times\{1\}$, $A\times\{-1\}$. If your original cover was of size $K$, then this process results in $2K$ sets (the reason you don't end up with $2^K$ sets is that fixing the label for one set does not affect the labeling of another, so there is no multiplication going on).

In a more straightforward approach, let $\mathcal{C}$ be your original $\frac{\gamma}{2}$-cover for $\mathcal{X}$, then a partition $\mathcal{P}$ of $\mathcal{X}\times\{-1,1\}$ such that for all $ p\in\mathcal{P}$ and $(x_1,y_1),(x_2,y_2)\in p$ it holds that $y_1=y_2$ and $||x_1-x_2||\le\gamma$, is given by $\mathcal{C}\times\{-1,1\}$, which is of size $2|\mathcal{C}|$.


For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes? I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of [nodex, nodey], nodex<=nodey. And also given that the range has exactly  k nodes, k can be at most n ie. total number of nodes. The question asks what is the worst case time complexity of accessing all the
k nodes in given range. According to my knowledge of Time-Complexiy analysis It must be O(k*log(n)) since there are k elements and each element takes O(log(n)) time in worst case ( since the tree is balanced ) this seems very plausible, However the answer seems to be O(k + log(n)), what am I doing wrong?

One way to do it is to construct the tree containing those values:

Explore the BST until you find the root of a subtree that is between the bounds;
Explore the left part of the subtree, and trim branches on the left that have a root $\leqslant node_x$;
Do the same thing on the right for roots $\geqslant node_y$

Each of those steps are done in $O(\log n)$ since the BST is balanced. Once you have constructed the tree, just do a tree traversal (in-order for example) of it. This last step is indeed done in $O(k)$.


Canonical reference on agent-based computing I am interested in exploring the world of BDI agents (software agents that possess "beliefs, desires, intentions", essentially the agent has knowledge of the world, a set of motivations, and carries out certain plans).

I recently read A Canonical Agent Model for Healthcare Applications [1], which left me with a lot of questions, particularly about the specialization of different agent models for particular applications.

The particular modeling language used in their examples was ProForma, and I understand that this is more for the abstract specification of an agent, and that something like 3APL can be used as an actual programming language in this regard, with syntax like:

BELIEFBASE {
    status(standby).
    at(0,0).
    location(r1,2,4).
    location(r5,6,1).
    dirty(r1).
    dirty(r5).
}

My question is, all of these systems clearly reflect years of cumulative efforts, and rather than jumping in to the deep end, I'd like to ease into this world of research a bit more slowly.  Is there a canonical reference in this area that might be able to provide a more general overview of all of these levels of organization, and where the abstractions stop and the implementations begin?

Fox J., Glasspool, D., Modgil, S. A Canonical Agent Model for Healthcare Applications. IEEE Intelligent Systems, 21(6), 21-28, 2006.

If you want to approach this field from a computer science perspective then the standard reference I would recommend is:

Yoav Shoham and Kevin Leyton-Brown [2009], "Multiagent systems: algorithmic, game-theoretic, and logical foundations", Cambridge University press.

Currently, it seems like the focus of theoretical work in this field (and this is obviously biased by my own interests) is to consider environments where agents are limited in their interactions. If you just have agents meet randomly, then ABMs are usually overkill and things can be done analytically. However, if there is some interesting network structure (fixed or dynamic) to the interactions (as there often is in real life) then ABMs become an essential tool. A good book discussing some of these ideas from a CS perspective is:

David Easley and Jon Kleinberg [2010], "Networks, crowds, and markets: Reasoning about a highly connected world," Cambridge University press. (draft available online)

Questions of interest:

Simulation modeling of diseases

Sources for Algorithmic Evolutionary Game Theory


Can each VLIW sub-instruction execute any instruction? say that you have a 128 bit (32*4) VLIW word. Can each 32 bit sub-word contain any operation (ADD,CALL,BRANCH,...) if there are no hazards or can each sub-word only specify one functional unit (so if the BRANCH functional unit doesn't get used, that sub-word becomes a NOP)?

Usually, VLIW instruction sets dedicate bit fields to functional units  (not necessary multiples of bytes, or the same width for all units), and when some parts are unused, they are configured as NOPs.

Of course, there are exceptions, sometimes execution units are coupled, or special configurations are provided for long immediates... There is no absolute rule.

You should look at sample implementations, like the 48bits SHARC DSPs, or the ST200 family.


Sanity check about a linear programming problem given the linear program:

minimize $x+y$

subject to,

$ax+by \leq 1$

$x,y \geq 0$

I need to find real numbers $a,b \in \mathbb{R}$ such that the program (a) is infeasible, (b) is unbounded, and (c) has a unique optimal solution.

Since we are asked to minimize the sum of two non-negative numbers the solution for all $a,b \in \mathbb{R}$ is $(x,y)=(0,0)$, right?

I cannot see any potential values of $a,b$ which would make the program infeasible or unbounded, because we are always looking to minimize the sum of non-negative numbers.

I’d say the program is always feasible because x = y = 0 is a solution.

Most pairs a, b give a unique solution. Only certain pairs don’t.

Now it depends on the definition of “unbounded”. If we talk about the goal function, the minimum is always bounded by 0. If we talk about the points (x, y), they are unbounded if a <= 0 or b <= 0.


What to do when the information gain on decision trees is 0 for all possible splits? I just started studying decisions trees and I am trying to construct a tree for a training set which uses Status as the class label. I am using the misclassification error as measure of impurity. After the first iteration, the information gain indicates that Department should be the tree root. The following table represents the sub-table for Department = Secretary.

I got to this point and I don't know how to add the corresponding nodes to the tree. Should the next node be Age or Salary?

Thanks!

You should process ALL of the possible splits and hope for information gain somewhere down the line.


Use count() in relational algebra Person(name, phone)
  Mike 456-789
  Mike 123-456
  John 230-785
  $\dots \dots$

How to get those people who have more than one phone numbers with relational algebra? This sounds simple, but I am frustrated with all materials that I've learned.

Is it correct syntax to use count() like $\pi_{name}(\sigma_{count(phone)>2}(Person))$ ?

A syntax of aggregate operation in relational-algebra (according to [1]) is as follows :

  $G_1,G_2,...,G_n \hspace{2 mm}\textbf{g}\hspace{2 mm}
  F_1(A_1),F_2(A_2),...,F_m(A_m)(E)$

  where $E$ is any relational-algebra expression; $G_1,G_2,...,G_n$
  constitute a list of attributes on which to group; each $F_i$ is an
  aggregate function; and each $A_i$ is an attribute name.

Thus your query would look like :
$\pi_{name}(\sigma_{phone>1}(name\hspace{2 mm}\textbf{g}\hspace{2 mm} count (phone)( Person)\hspace{2 mm}))$

[1] A. Silberschatz, H. Korth, S. Sudarshan, Database System Concepts, 5th Edition


Can I solve my decision problem in $O(n)$ time? My algorithm solves a custom string problem but it loops twice making it $O(n^2)$ time. I'm asking here as I'm a beginner in self-learning algorithms.

Decision Problem: Given an input list $A$, can our target string $S$ be made from any of the elements of $A$?

If just one element does not exist in $A$ (which exists in $s$) then the algorithm returns false.

A = input_array
s = input_target_array

for i in s:
  if i in A:
    (all elements ∈ s) ∈ A
  else:
    break

(if any element ∈ s) ∉ A:
  return False
else:
  return True

Output

Enter your input for A and include spaces:
Enter letters WITH SPACES: "ab" "cd" "ac"
enter your input for s:
 "abxd"
^ False ^
 "abcd"
^ True ^

I'm looking for an algorithm that solves my made up decision problem faster than $O(n^2)$ time.

Question

Are there any methods that can be used from an algorithmic standpoint that would make this $O(n)$ time?

I use set difference to find out if there are any elements in $s$ that don't exist in $A$. This should be $O(n)$ in the best cases if there is a good hash. Since I'm dealing with integers it should be $O(n)$ Explained here

I then use $len(s)$ and $len(A)$ which takes $O(1)$ time according to here.

A = [1,2,3,4,9]
s = [1,2,3,4,9]

elem_not_in_A = set(s) - set(A)

if len(s) >= len(A):
    if len(elem_not_in_A) > 0:
        output False
    else:
        output True
else:
    output False

If the set difference remains $O(n)$ and all the other statements remain $O(1)$ then yes it can be solved in $O(n)$ time.


What exactly can finite-state machines not do? I know finite-state machines can be used to solve yes/no kind of problems, such as finding whether a word is in language or not. Can somebody tell me exactly what FSM cannot do and why?

The answer depends on what you mean by FSM.

If by FSM you mean finite automaton, then there's a lot that it can't do. As others have pointed out, you can't remember more than a constant amount of information using a finite automaton; the memory must be encoded in the state. This means you can't do things like recognize $a^nb^n$, since you'd need to remember how many $a$ symbols you've seen, which is not possible unless you have an arbitrary amount of memory. The pumping lemma for regular languages and, especially, the Myhill-Nerode theorem offer insight into the kinds of things that can and cannot be done.

If by FSM you mean any automaton formalism which is limited to using finitely many states, then Turing machines are among the most computationally capable FSM models available. Indeed, anything which is effectively computable is computable by a Turing machine, according to the Church-Turing thesis. However, there are still limitations to what a Turing machine can decide: there are problems it cannot answer, such as the halting problem.

Models which aren't limited to a finite number of states aren't particularly interesting for a few reasons, most prominent of which are the following: they are of limited practical importance since we cannot construct real computers with infinitely many configurations; any language can be recognized in such a model by mapping strings in the language to unique accepting states, and strings not in the language to unique non-accepting states.


Solving Budgeted Maximum Coverage Problem using Greedy and Genetic Algorithm I am trying to solve the Budgeted Maximum Coverage Problem.
I have read and implemented the greedy and modified-greedy methods to solve it, as proposed by Khuller.
Both are approximation algorithms. The greedy provides a $1/2(1-1/e)$ approximation, and the modified greedy guarantees $1-1/e$.
I am trying to get better results than this using a genetic algorithm.
However, I am not sure if that is at all possible.
My question is, can GA (or any metaheuristics) provide better results? Or is trying such a thing futile?

Absolutely they can. The approximation algorithms give a formal guarantee that the solution won't be too bad and they quantify what this means whereas with a metaheuristic such as GA all bets are off. Really, the only guarantee you have with GA is that the solution is valid, but that's it.
Your best bet is to just implement the GA and give it a try. Much will depend on the details and choices you make inside the method as well as on your instances and their structure.


How is Johnson's shortest path weighting function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ proven by the triangular inequility? Recap to the Johnson's shortest path algorithm:

By the procedure extending the original graph $G^\prime = (V^\prime, E^\prime), V^\prime = V\ \cup \{s\}, E^\prime = E\ \cup \{(s, v)\ |\ \forall v \in V\}$, and then extend the original weighting function $\forall x \in V,\ w(s, x) = 0.$

Finally define the reweighted function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ where $\forall x \in V,\ h(x) = d(s, x)$ , where $d(s, x)$ is the shortest path from $s$ to $x$.

Problem:

Assume that there is no negative cycle in the graph. The textbook Introduction to Algorithms says that
$w(u, v) + h(u) - h(v)$ is always nonnegative proven by using the triangular inequality theorem to get $w(u, v) + h(u) \ge h(v)$.

This makes me so confused, because I think that there could exist negative weights in the graph and hence triangular inequality can't be applied. (Am I misunderstanding triangular inequality? Or something are skipped I cannot tell?).

Where did I misunderstand about this algorithm? Thanks!

You're right that you can't (necessarily) apply the triangle inequality to the edges of the original graph, but that's not what's being discussed here.

We know $h(u)$ is, by definition, the shortest path to $u$.  Thus we immediately know that $w(u,v) + h(u) \geq h(v)$ because, if it wasn't true, $h(v)$ would not be the shortest path to $v$.  The author is calling this the "triangle inequality" of the reweighted graph.


Converting nested absolute value into linear programming I am having trouble writing the following optimization problem as a linear program (LP)

$$\min_{x \in \mathbb R^2} \big| | x_{1} - a_{1} | - | x_{2} - a_{2} | \big|$$

where $a \in \mathbb Z^2$ is given. I tried adding the following constraints and replacing objective function to min $U$, but it did not work out.

$$x_{i}-a_{i}\le y_{i}$$

$$a_{i}-x_{i}\le y_{i}$$

$$y_{1}-y_{2}\le U_{}$$

$$y_{2}-y_{1}\le U_{}$$

This sounds like a homework problem, so just hints here.

We'd usually just transform $x_1$ and $x_2$ into two new variables,
$$
\begin{array}{ccccc}
x_1^{'}~{\equiv}~x_1-a_1 & & \text{and} & &
x_2^{'}~{\equiv}~x_2-a_2
\end{array}
,
$$such that the new problem is$$
\min{\left|
\begin{array}{c}
{\left|x_1^{'}\right|}-{\left|x_2^{'}\right|}
\end{array}
\right|}.
$$
Then, the absolute values imply symmetries such that we don't need to consider some parts of the domain.

We may ignore:

$x_1^{'}<0$, because it's degenerate with $x_1^{'}>0$ under $\left|x_1^{'}\right|$.
$x_2^{'}<0$, because it's degenerate with $x_2^{'}>0$ under $\left|x_2^{'}\right|$.
$\left|x_1^{'}\right|<\left|x_2^{'}\right|$, because it's degenerate with $\left|x_1^{'}\right|>\left|x_2^{'}\right|$ under $\left|\left|x_1^{'}\right|-\left|x_2^{'}\right|\right|$.

Typically you can specify these sorts of domains to ignore in terms of constraints.

Then, since the degenerate cases have been removed, the objective function's just$$
\min{
\left(
{x_1^{'}}-{x_2^{'}}
\right)
}.
$$


About proofs in descriptive complexity In descriptive complexity, we have theorems that look like $\mathrm{ESO} = \mathrm{NP}$ or "on linearly ordered structures, $FO(LFP) = P$", but I don't really understand the proofs of those.

For the latter, the intuitive equality really means that the statement "$\mathcal A\models \varphi$" can be verified to be true on a linearly ordered structure $\mathcal A$ in time $n^k$ iff $\varphi$ is expressible in some fixpoint logic. The right-to-left inclusion then reads $\forall M\; \mathrm{polytime \;TM}, \exists \varphi\in\mathrm{FO(LFP)} \quad \left[\mathcal A \models \varphi \Leftrightarrow M(\mathcal A) = 1\right]$.

The proof I have been taught in class for the right-to-left inclusion goes as follows: from a Turing machine M (with set of states $S$), we build a formula on the language $\{T_0,T_1\} \cup \{H_i : i\in S\}$, where all relations are of arity $2k$. This formula says that the structure it's being evaluated on is a correct computation of $M$ which ends in an accepting state. How does this prove the theorem? Of course, there is a bijection between accepting computations of $M$ and structures $\mathcal A$ s.t $M(\mathcal A) = 1$, but the statement of the theorem doesn't mention this bijection. In my opinion, the formula $\varphi$ that we create should really check properties of $\mathcal A$, and not properties of the computation of $M$ on $\mathcal A$... Where is my mistake? Am I overthinking this?

Your intuition is correct, though it's probably more useful to think of the statement "[Logic] = [Complexity Class]" as "A property of relational structures can be decided in [Complexity Class] if, and only if, it is definable in [Logic]."

As for the proof, I think you're overthinking it. There's not just a bijection between accepting computations and structures $\cal{A}$ such that $M(\cal{A})=1$ — that's the definition of what it means for $M(\cal{A})$ to be $1$. The property of $\cal{A}$ that the formula verifies is "$\cal{A}$ is a structure accepted by $M$." There's really no difference between the statements (for example), "$\cal{A}$ is a connected graph", "$\cal{A}$ satisfies this formula that defines connectivity", "$\cal{A}$ is accepted by this Turing machine" and "this Turing machine accepts $\cal{A}$."

Perhaps it would help to give some intuition about how the proof works. The point about the linear order is that it lets us use the universe of the structure as digits, to write numbers in base $n=|\cal{A}|$. Since the machine we're dealing with runs in time $n^k$, we can index each time step of its computation by a $k$-digit number in base $n$ and likewise each used cell on its tape (in $n^k$ steps, it can't use more than $n^k$ tape cells).  You can also use base-$n$ numbers (of fixed length) to represent the states of the Turing machine and the characters in its alphabet.  You use this to build up relations that say things like, "At time $t$, cell $i$ of the tape contains character $c$", "At time $t$, the head is at position $p$", "At time $t$, the machine is in state $s$". Now, you write a formula that says:

at time $0$, the tape contains the coding of $\cal{A}$, the head is at position $0$ (and the head is not anywhere else) and the machine is in its start state (and not in any other state) AND
if, at time $t$, the machine is in some configuration, then the configuration at time $t+1$ is what the definition of the machine says it should be AND
at some time $t$, the machine is in an accepting state.

Note that there are various different ways of coding the Turing machine's configuration in relations. For example, since there are only a fixed, finite number of machine states $s_1, \dots, s_\ell$, you could use $k$-ary relations $S_1, \dots, S_\ell$ such that each $S_i$ contains the times at which the machine is in state $s_i$. The tape symbols can be coded similarly.


Is it NP-complete to test if a graph contains $t$ $k$-cliques? Given a graph $G$ along with two non-negative integers $t, k \in \mathbb{N}$, The instance $(G,t,k)$ is a yes instance of the problem if and only if the graph $G$ contains $t$ cliques with $k$ vertices (there are $t$ copies of $K_k$, a cliques of size $k$ in  the graph $G$). How to prove that $(G,t,k)$ is NP-complete?

It is obvious that it is in NP. I have tried to prove that $k$-CLIQUE language $(G,k)$ is reducible to a $(G,t,k)$ language. But I can't get the idea, how to get $t$ of $k$-CLIQUES.

This problem is clearly NP-hard since it is a generalization of many NP-hard problems. The most obvious one is the maximum clique problem, i.e. finding a clique of the maximum size in a graph. The decision version of this problem is a special case of your problem where you set $t$ equal to one. (See below for the hardness-proof).

Further reading.

Other example is the triangle packing problem, assuming you are looking for pairwise vertex-disjoint cliques (note that for the maximum clique it does not matter if the cliques have to be vertex disjoint since we chose $t=1$). In the triangle packing problem we are looking for a set of $k'$ vertex-disjoint triangles ($K_3$) in a graph, which is a special case of your problem where we set $k = 3$ and $t = k'$.

Note that the maximum clique problem is one of the Karp's 21 hard problem, which are probably some of the most important/original proven hard problems. In his paper "Reducibility Among Combinatorial Problems" [Karp, 1972], he provides some of the very first hardness reductions using Cook's theorem. Here is a link to the wiki page of the paper where you can find more information and a link to the original paper.


Does exponentiation reduce to multiplication or the other way around? Is is more accurate to say that in complexity theory:

$$\text{exponentiation} \leq_p \text{multiplication}$$

or

$$\text{multiplication} \leq_p \text{exponentiation}$$

I understand that if we know how to do multiplication, then we can run multiplication in a loop in polynomial time to get the answer to the exponentiation problem.

But which of the two reflects this? Do we say exponentiation reduces to multiplication (the first one), or the other way around (the second one)?

Both statements are accurate, assuming $\le_p$ refers to polynomial-time Turing reductions (i.e., Cook reductions), and assuming that in the exponentiation problem, the exponent is specified in unary (otherwise you can't exponentiate in polynomial time).  Given an algorithm to multiply in polynomial time, you can use it to exponentiate in polynomial-time via a Turing reduction, since $a^k = a \times a \times \cdots \times a$.  Also, given an algorithm to exponentiate in polynomial time, you can use it to multiply in polynomial time via a Turing reduction, since $ab = [(a+b)^2 - a^2 - b^2]/2$.  That said, since both multiplication and exponentiation can be computed in polynomial time directly, there's really no need for such a fancy reduction: it's immediate from the definitions that any problem in P reduces to any other problem in P.

You might want to refresh your understanding of the definition of the reductions.

Note that we usually apply reductions to languages, i.e., to decision problems.  So, to really understand how to apply the formal theory to your question, you'd first need to re-cast it as a question about a formal language or about a decision problem.  "Multiplication" is not a decision problem.  Re-casting as a decision problem will complicate things a little bit, and change the nature of the reductions (for instance, the reductions I hinted at above might no longer work), but the bottom line will still remain true: since you can reduce any problem in P to any other problem in P, there will be a reduction in both directions.

See also What is the definition of P, NP, NP-complete and NP-hard?, What are common techniques for reducing problems to each other?, What is the difference between an algorithm, a language and a problem?, and NP-completeness: Reduce to or reduce from?


Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge A test is consisted of $N$ multiple choice questions, each has $k$ possible answers.

A test solution is the sequence of answers $S\in[k]^N$.

Given is a black box which receives a solution as input and returns the number of correct answers. After failing a test, the student may take the test again, and the questions do not change.

In order to pass the test, a student must have at least $m\le N$ correct answers.

What is the minimal number of attempts you need to make (as a function of $N,k$ and $m$) in order to be sure to pass the test, assuming you have no knowledge about the questions in hand?
Assuming you are allowed to use randomization, how can we minimize the expected number of attempts needed?

A trivial algorithm is to "guess" an initial solution $S_0$, and then change one answer at a time until you have $m$ correct ones. This results in $1+(k-1)\cdot m$ attempts at the worst case.

For the probabilistic part, it seems some kind of an experts algorithm could work here: pick a few random tests and then construct additional tests such that answers appearing in high-scoring solutions will get higher probability.

Here is an algorithm to identify the answers with successive attempts.

It has a worst case complexity of $O(m(1+\log_2 k))$

This corresponds roughly to collecting in each attempt one bit of
information on the right answer, for each question in succession.

Of course we cannot do that, because we can only give one whole answer
per question. So the trick in to transpose the problem, by identifying k
correct answers and trying to find their questions.

Apologies for the rough presentation. I am running out of time.

The algorithm

We assume, to simplify the presentation, that $N\geq k$. But it does
not really matter. We also assume that $k=2^p$ for some positive
integer $p$, again to simplify the presentation.

We assume that the only result of an attempt $T\in [1,k]^N$ is a score $s(T)$
corresponding to the number of correct answers. The individual
answers for each question are noted $T[j]\in [1,k]$ for the answer to question
$j$, ($j\in [1,N]$), in attempt $T$.

We define $T_i=i^k1^{N-k}, \forall i\in[1,k]$

The $N-k$ last answers always contribute the same amount $r$ to the result
$s(T_i)$ since they do not change.

Together, the first $k$ answers of all $k$ attempts will produce $k$
good answers, distributed in some way over all $k$ attempts, since for
each question there is exactly one good answer among the $k$ being
proposed.

If one attempt has 2 good answers, or more, for one of the first $k$
questions, then another must have 0. Thus, if the scores $s(T_i)$ are
not all equal, the smallest is equal to $r$. Furthermore, if they are
all equal, then they are all equal to $r+1$. So the value of $r$ is easily determined.

We first assume $\exists r\in[0,N-k],\; \forall i\in[1,k],\; s(T_i)=r+1$

This implies that each attempt has exactly 1 good answer among the
first $k$ answers (to the first $k$ questions). But we do not know which.

We define a second set of $k-1$ attempts
$T_i'=i^{k/2}1^{N-k/2}, \forall i\in[1,k]$

Note, that $T_1'=T_1$, so that k-1 new attempts only are needed,
but the duplication makes things simpler to explain.

If the good answer $1$ in the first $k$ questions in $T_1$ was for one of
the first $k/2$ questions, then $1$ is a bad answer for questions
$Q_j,\; \forall j\in[k/2+1,k]$. Hence all the $T_i$ attempts that had
a good answer for one of these $k/2$ questions will lose 1 point in
score, thus falling to $r$. All other attempts, that had a good answer
in the first $k/2$ questions will have an unchanged score $r+1$.

If the good answer $1$ in the first $k$ questions in $T_1$ was for one of
the last $k/2$ questions, i.e. for questions  $Q_j,\; \forall
j\in[k/2+1,k]$, then all attempts $T_i'$ benefit from that good
answer $1$. Those that had a good answer for the first $k/2$ questions
will keep it and see their score increase from $r+1$ to $r+2$, while
the others will lose their good answer as before, but have it replaced
by the good answer $1$ for one question, thus keeping the score $r+1$.

Thus we can conclude that, if some score decrease, then the firat
attempt $T1$ has a good answer $1$ in one of the first $k/2$ questions,
and if some increase it is in one of the next $k/2$ questions.
Forall other attempts $T_i'$, those with the higher score have a good
answer for one of the first  $k/2$ questions, and those with the lower
score have a good answer in one of the next $k/2$ questions.

Recall that $k=2^p$, i.e. $p=\log_2 k$.

If we number the first $k$ questions in binary, starting from 0, we
can see that this is a way to determine the $p^{th}$ bit of the index
question that is correctly answered by some attempt $T_i$.

If for some $i>1$, the score decrease from $T_i$ to $T_i'$, then
$T_1$ has a good answer for a question $Q$ such that the $p_{th}$ bit
of its binary index is $0$, while it is $1$ for an increase. For the
other attempts $T_i$, those with the higher score for $T_i'$ have a
good answer for a questions with the index $p^{th}$ bit $0$, and the
lower scores have a good answer for a questions with the index
$p^{th}$ bit $1$

It is then quite simple to repeat the procedure identically for each of
the other bits of the binary index of the first $k$ questions.

That makes $p=\log_2k$ series of $k-1$ attempts, in addition to the
first $k$ attempts, that is a total of $k+(k-1)\log_2k$ attempts,
to get the first k answers.

However we can improve a bit on that count. We do $\log_2 k$ attempts
to identify the question associated with each answer, i.e. each index
$i\in [1,k]$. Actually we need to identify only $k-1$ such question.
The last one in necessarily the one that was not found yet.

Thus in the above algorithm, we do not need to compute $T_{k}'$, nor
any of the other attempts of index $k$, except for the first $T_k$ in
the first attempts of the algorithm. Since it is also unnecessary for
$T_1'$ and similar, we only need, at most $\log_2k$ series of $k-2$
attempts, in addition to the initial $k$ attempts, that is a total of
$k+(k-2)\log_2k$ attempts, to get the first k answers.

But this relied on the assumption that each of the first $k$ attempts
has exactly one good answer for the first $k$ questions. What if that
is not the case?

One of the first $k$ attempts had more than one good answer in the first $k$.

Then there is at least one attempt, say $T_h$ that failed on the first
$K$ questions, which means that answer $h$ is wrong for the first $k$
questions.

Actually there may be several such attempts caracterized by the fact
that they have the same smallest score $r$. They can all be discounted
as containing no information for the first $k$ questions, other than the
fact that their index is not the answer to these questions.

Futhermore, for any attempt $T_i$, we know that it has $s(T_i)-r$
correct answer $i$ in the first $k$ questions.

If there is only one answer, it can be identified with the previous
binary technique using $\log_2k$ attempts, given that we can replace
half the answers (as specfied by a bit in their binary index) by $h$
which is known to be wrong (which makes thing simpler than
previously).

If there are two correct answers, the same technique is used with a
small variation. The binary approach is used again for both answers
together, until one of the attempts separates them by indicating a bit
$0$ for one answer and a bit $1$ in the same position of the question
binary index for the other answer. From then on, one answer can be hidden
by using the answer $h$ in the questions corresponding to that index,
while the binary search is resumed for the other answer. Once that
answer has identified its question, it is replaced by the answer $h$
that is wrong so that the search can be resumed for the question of
the second answer.

The same technique can be used independently of the number of answers,
progressively splitting them until only one is searching for its
question, then replaced by wrong answer $h$ when its question is found, so that another can be searched, and
so on.

Since the splitting and searching is based on the bits of the binary
indexes of questions, it is quite clear that this costs never more
than $\log_2 k$ for each question to be associated with one of the $k$
answers.

So the cost in number of attempts for identifying the questions for
the first $k$ answers (I am deliberately inverting the view) is not
more than $k\log_2 k$, to be added to the first $k$ attempts. It might
be a bit less with a finer analysis.

However we can again use the fact that each question has necessarily
an answer, so as to skip the binary search on one line of answers (i.e., one
answer number).

First recall that we simply ignore all answer numbers that correspond
to no answer. Then we also set aside the answer number that
corresponds to the largest number of questions for which it is the
right answer. This corresponds by hypothesis to at least two good answers.

Then we determine the corresponding question for all other identified
good answers, at most $k-2$ of them, with a cost that is at most
$\log_2 k$ for each. The correct answer set aside can then be assigned
to all questions that have not been identified as associated with
another answer.

This makes for a total cost of at most $(k-2)\log_2k$ attempts, to be added to
the initial $k$ attempts, thus again a total of $k+(k-2)\log_2k$
attempts, to get the first k answers, as in the first case.

Overall

The cost of this algorithm, mesured in number of attemps, is bounded by $k(1+\log_2 k)-2\log_2 k$ for
identifying the $k$ answers to $k$ questions (as the above could have been done for any set of $k$ questions.

So for $m$ questions, assuming for simplicity that $m$ is a multiple of $k$, the total cost is bounded by $m/k$ times that cost,
i.e. $m(1+\log_2 k)-(2m/k)\log_2 k$.

Apparently the total number $N$ of questions does not matter. But the last questions are
not considered with this technique, except to identify their global effect to factor it out. We do not take advantage of the fact that some groups of question-answer pairs might be easier to identify (because their costs can be factored, for example). Possibly this could
help for the worst case analysis with a different technique that would identify  patterns of answers that are easier to analyze, but there might be a cost in finding them.

Regarding purely asymptotical complexity: this algorithm is $O(m\log_2k)$


Approximation ratio of greedy algorithm for makespan In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf

Lemma 5 is given as:

The approximation factor of the modified greedy [scheduling] algorithm is 4/3.

And gives the example:

Note that 4/3 is essentially tight. Consider an instance with m machines, n=2m+1 jobs, 2m jobs of length m+1,m+2,⋅⋅⋅,2m−1 and one job of length m.

now how can number of integers in the range m+1,m+2,....,2*m-1,be 2*m ?

The lecture notes might be misquoting the example. Here is a correct version, copied from lecture notes of Ola Svensson:

The 4/3 bound is tight, an infinite family of instances showing this is given below.
Instance: we are given $m$ machines, and $2m+1$ jobs. There are three jobs with processing time $m$, and $2$ jobs with processing times $m+ 1,m+ 2,\ldots,2m−1$ each. In case of LPT, all but one of the machines get two jobs with a total processing time of $3m−1$, and a single machine gets three jobs with a total of $4m−1$ processing time.  Thus, the makespan is $4m−1$.  OPT schedules the three $m$ jobs on a single machine, and the remaining jobs on the remaining $m−1$ machines, such that each of those machines get jobs with a total processing time of $3m$, thus the makespan of OPT is $3m$.  As $m$ grows towards infinity the approximation ratio approaches $4/3$.

In the quote, LPT is the greedy algorithm. The approximation ratio for given $m$ is $\frac{4m-1}{3m} = \frac43 - \frac1m$, which tends to $\frac 43$ as $m\to\infty$.


lambda calculus reduction: (((lambda f (lambda x (f x))) (lambda y (* y y))) 12) given the input

  (((lambda f (lambda x (f x))) (lambda y (* y y))) 12)

what does this step evaluate to: lambda x (f x)

I am trying to evaluate this and I have the following tree so far:

how do I evaluate this ? looking for guidance on what I might be doing wrong or how to proceed with this.

Lambda expressions are evaluated by reducing the leftmost redex first.  A redex is something of the form $(\lambda a.b)c$ .  Your expression is $(\lambda f.\lambda x.fx)(\lambda y . *yy)~12$.  So your first redex is

$$(\lambda f.\lambda x.fx)(\lambda y . *yy)$$

So you substitute $(\lambda y . *yy)$ for $y$ in $\lambda x.fx$ to get $$\lambda x.(\lambda y . *yy)x~ 12$$

Then your next redex is the entire expression, ($(\lambda y . *yy)x$ is also a redex but it isn't the leftmost one) substituting $12$ in for $x$.  So you get $$(\lambda y . *yy)~12$$

Then your last redex is the entire expression again so you get

$$*~12~12$$


Most frequently tools or programming language for implementation text processing and nlp algorithms in academic papers and journals I want to prototype and try some idea (some algorithm) in the field of text processing and nlp and if the results was good I want to publish some paper or journal article about that.

I am familiar with Weka, RapidMiner, Matlab and Python for text processing and nlp but I don't know what is the most frequently tools for those fields in the academic area?

As you know, comparing results with others is one of the most important parts of any academic paper. For this reason, I want to choose most frequently tools or language for this work.

Sorry for my bad English.

Thanks for your attention.

My personnal opinion is that such comparisons usually make little
sense because they can be too dependent on hidden specificity of tools
or programming languages, or programming style and its interaction
with those specificities.

In my opinion, the only proper way to compare techniques is by a precise knowledge of
the interpretation machines. If you are comparing different algorithms
intended to achieve the same purpose, you want to run them on some
kind of unbiased abstract machine, providing some application
meaningful primitives than can be used to implement on the same
footing all the algorithmic variations.

Then you can actually count elementary computation costs over some
chosen benchmark.

For example, I have seen this type of work done for various parsing
algorithms, using a standardized PDA definition.

Making a slightly better tool than what exist for problem X in
language Y is seldom worth publishing, unless there is some more
abstract consideration of some theoretical work that shows that you
are bringing something to the field, rather than just being a better
hacker. And then the tool or language support does not matter so much,
as long as you can compare with some known work, and explain credibly
why your version works better.

Of course, if you actually manage to get major improvements, undisputable ones, then you have a much better chance of being published. But the the technical support you use will matter even less.


Revert array shuffle faster than in O(n^2) I want to reverse an array that was shuffled with the function

array<integer> shuffle(arr: array<integer>, f: (integer) -> integer) {
    for (i: integer = 0; i < arr.length; i++) swap(arr[i], arr[f(i)]);
    return arr;
}

The array passed to this function is [0, 1, 2, 3, ... n-1] and function f for any i returns a value that is less or equal to i. I have an array returned by the function and I want to restore the results of f(i) for each iteration. What I do currently is:

array<integer> deshuffle(arr: array<integer>) {
    array<integer> result = [];
    for (i : integer = arr.length - 1; i > 0; i++) {
        index: integer = -1;
        for (j: integer = 0; j < i + 1; j++) {
            if (arr[j] == i) {
                index = j;
                break;
            }
        }
        result.push(index);
        swap(arr[i], arr[index]);
    }
}

Here I rely on the fact that the last member of the array can only be shuffled during the last iteration, which means I can find it, push the index and reswap it back and repeat it recursively (this is kinda like the insertion sort if I remember the name correctly). But the trouble is that this code is slow (O($n^{2}$)). Is there any way to do it faster?

It's not very clear what you are asking. It seems you want to find the values of f(i) for all i.

Problem: You can't distinguish between f(0) = 1, f(1) = 0, and f(0) = 0, f(1) = 1.


Proof Big Theta (sum of a geometric) Here sum of a geometric, where c is a positive real number.

$g(n)=1+c+c^2+...+c^n$

$\theta(1)$ if $c<1$

Any idea to solve this?

It is known that
$$
1 \leq g(n) < \sum_{m=0}^\infty c^m = \frac{1}{1-c}.
$$
You take it from here.


Decidablity with exponential number of solution I am trying to understanding this. If a problem has exponential amount of candidate solutions, such as 2^2^n. Is this decidable?
To my understanding, as long as its' verfiable, no matter how big the solutions there are, it's.decidable.

Thanks for clarity

If a problem has a finite number of possible solutions, then you can enumerate all the potential solutions, and if one of them is correct, halt. Otherwise, halt and reject after checking the last solution.

It does not matter how long this process takes, it may be exponential, or superexponential as in your example of $2^{2^n}$, the only thing that matters is that there is a way to enumerate all candidate solutions.


Reducing directed hamiltonian cycle to graph coloring The 3-SAT problem can be reduced to both the graph coloring and the directed hamiltonian cycle problem, but is there any chain of reductions which reduce directed hamiltonian cycle to graph coloring in polynomial time?

Let $Q \in \sf{NP}$ and $Q' \in \sf{NP\text{-}hard}$. Then, by definition, $Q$ is (many-one) reducible to $Q'$ in polynomial time.

The exact chain of the reductions will depend on the $\sf{NP\text{-}hard}$ness proof of $Q'$. Typically, it is proven by a chain of reductions starting from $\mathrm{SAT}$ and ending with $Q'$ and then using the Cook-Levin theorem. So the chain of reductions will be a reduction from $Q$ to $\mathrm{SAT}$ followed by the chain of reductions from $\mathrm{SAT}$ to $Q'$.

There is usually a more direct reduction for specific problems (without using Cook-Levin), since it is usually easy to find a propositional formula directly expressing the required property (with no reference to TMs). For example, in the case of Directed Hamiltionian Path ($\mathrm{DHP}$) and Graph Coloring ($\mathrm{GC}$), you can reduce:

$\mathrm{DHP}$ to $\mathrm{SAT}$,
$\mathrm{SAT}$ to $\mathrm{3SAT}$,
$\mathrm{3SAT}$ to $\mathrm{GC}$.


What is the $4k$ kernelization algorithm for Planar Independent Set? Chen et al. say that

  The four-color theorem implies a $4k$-kernelization for Planar Independent Det, which is the dual problem of Planar Vertex Cover.

I knew that Vertex Cover has a kernelization with $2k$ vertices.  Furthermore, I know that we have a lower bound which is $n/4$ for IS.

But how to get a $4k$ vertex kernel for Planar IS?  Is there a general rule that when we transform "primal" program to "dual" program, then we have a factor of 2.

The formal problem is:

Input: A planar graph $G = (V, E)$ and an integer $k$ (the parameter)
Question: Does $G$ have an independent set of size at least $k$?

A kernelization algorithm for Planar IS with $4k$ vertices.

Recall that we can obtain a four-coloring of $G$ in polynomial time.  That is, we get a partitioning of your vertex set $V$ into $V_1, V_2, V_3, V_4$ such that each class is an independent set.

We now distinguish between two cases:

One class $V_i$ has size at least $k$.  This is a witness and hence $G,k$ is a yes instance, so we may output a trivial yes instance.
Otherwise, every class has size less than $k$, so $V$ has at most $4k-4$ vertices.

Thus in polynomial time, we may output a graph $G'$ with at most $4k$ vertices such that $G,k$ is a yes instance if and only if $G', k$ is a yes instance.

Notice that this only holds for planar graphs.  Independent Set is W[1]-hard on general graphs.


What are the limitations of symbolic model checking? What are the limitations of the Symbolic Model Checking?

As far as I know, "state-space explosion" can still happen by this technique but it can explore much larger state space.

So, is the Symbolic Model Checking always better than the conventional model checking? If not, when to apply which one?

By the conventional model checking I mean:
Clarke Jr, Edmund M., et al. Model checking. MIT press.

And by Symbolic model checking I mean:
McMillan, Kenneth L. "Symbolic model checking." Symbolic Model Checking. Springer, Boston, MA, 1993. 25-60.

The primary limitation is that it can be more complicated to use.


B-tree branching factor boundaries A BTree has a $k$ value that determines that every node has $k$ to $2k$ children. When a node has $2k$ keys it needs to be split into two nodes.

Let's say I want to create a $k/(2k-x)$ tree. (like a 2-3 tree that follows the BTree rules, but isnt $k/2k$)

What is the possible range of $x$? The tree must follow the behavior of a BTree, meaning it needs to hold keys and split accordingly.

More exactly, a B tree has an $m$ value such that the number of children is between $\lceil\frac m2\rceil$ and $m$ children. That differs from your numbers for odd $m$. For $m=3$ the bounds are $2$ and $3$, which is the 2-3-tree you refer to.

As far as I know (I tried this several years ago) these numbers are the smallest interval for which the split and merge operations can work. You can try yourself. If a node has $m$ children, I can add $1$ and the node must be halved. Thus this satisfy the $\lceil\frac m2\rceil$ bound? Check for $m$ odd and even separately.


Merge two series of sorted number, one much longer than the other This is the problem:

  Merge two sorted series of numbers. Their lengths are $n$ and $m$, respectively, but $n \gg m$. Your algoritm should take $O(m \log(n/m))$
  comparisons.

I have come up with this algorithm:

1. Choose n/m "special" elements among n elements.
2. for i = 1 to m do
    2.1 Using binary search find block (between two special elements)
        where m_i should be inserted - time O(log(n/m))

    2.2 Using binary search in found block, find exact position for $m_i$. -
       O(log m)

Step 2.1 takes time $O(\log(n/m)$ and step 2.2 time $O(\log m)$, so I get in total a runtime in $O(m (\log n/m + \log m))$. How do I get rid of the $O(\log m)$ term?

Here's a sketch of the algorithm:

As you can see I have a problem - O(log m). How to eleminate it ?

What exactly does $n \gg m$ mean for your professor?

If it means $m \in o(n)$, then you are allowed $O(\log m)$ time for step 2.2. Note that $\log(n/m) = \log n - \log m$. If $m \in o(n)$, the target runtime bound simplifies to $O(m \log n)$; a summand $m \log m$ is dominated by this.

If $m \in \Theta(n)$ is allowed -- arguably, $m = n \cdot 10^{-10}$ would fulfill "a lot smaller" -- you can have that  $\log n/m \in O(1)$ and the runtime bound is $O(m)$. It's quite clearly impossible to perform this task in time $O(m)$, so I think we can safely ignore this case for the purpose of this exercise.

But here is something more for you to think about.

In step 1, you need to specify "special"; if you don't pick the elements according to your sketch, the rest won't work out. So we have to select the elements $i(n/m)$. In order to do this in $o(n)$ time and perform binary search efficiently, we need the series to be stored as arrays.

We can not copy all values to a new array in the required time. We can not insert values into an array, either. So how is this to work at all?


Intrinsic matrices in stereo camera calibration Suppose I have two cameras, c1 and c2, observing the same scene. I can now

Calibrate each camera independently (e.g., with MATLAB's Camera Calibration App)
Calibrate both cameras simultaneously (e.g., with MATLAB's Stereo Camera Calibration App).

Interestingly, the values calculated for the intrinsic parameters of both cameras are different using method 1) and method 2). To me it is not clear why this should be the case. The intrinsic parameters of camera 1 are independent of the ones of camera 2 and vice versa, why should they influence each other? I suppose there is some form of optimization aiming to optimize simultaneously in the stereo case, however I would think that the "stereo optimum" is the same as the combined "single optimum".

Any insight?

You are correct: during stereo calibration the parameters of both cameras are optimized simultaneously, which is why you get the discrepancy.

When you calibrate a single camera, you are minimizing the reprojection errors  from projecting the checkerboard points into that one camera. When you calibrate a stereo pair of cameras, you are minimizing the reprojeciton errors from projecting the checkerboard points into both cameras. Since you are minimizing different functions, the results will not be the same. However, the difference should be small.


Reductions from non decision problems I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min vertex cover problem instead of the decision version of the vertex cover problem. The problem I am having with reducing from the decision version is that a vertex cover of size k maps to the $Y$ of size $ \leq ck$, where $c$ is a constant. A decision version for problem $Y$ for me makes no sense, as there will always be a brekpoint distance between two genomes. I tried to research on the internet but I always only find reductions from decision problems. Could we reduce from non-decision problems.

Also when doing reductions from the vertex cover problem. I can't assume the given instance $G,k$ is such that k is the size of the optimal vertex cover right? $k$ is just any size of a Vertex cover.

Yes.  See the notion of an approximation-preserving reduction.


How are all NP Complete problems similar? I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.

Prove that current problem is NP, i.e., given a certificate, prove
that it can be verified in polynomial time.
Take any known NP-complete problem (call "Easy") and reduce all
of it's instances to few instances of given problem (call
"Hard"). Note this is not necessarily an 1:1 mapping.
Prove that above reduction can be done in polynomial time.

All is well here. Is this knowledge right "if you can solve any NP-complete problem in polynomial time, then all NP-complete problems can be solved in polynomial time" ?

If yes, then as per above proof technique, let's say "Easy" problem can be solved in polynomial time, how does that imply "hard" can be solved in polynomial time? What am I missing here? Or is this true, that "hard" problem can be reduced to the "easy" problem too?

Your question seems to come from the fact that you're not immediately convinced that the current problem can't be harder. The current problem can't be harder than any NP-complete problem because it is in NP.

If you want to be convinced that the notion of NP-completeness even exists (i.e. that you can reduce anything in NP to an NP-complete problem) you should study the Cook-Levin theorem which states that SAT is NP-complete.

Since NP-completeness states something about being the target of a reduction from any problem in NP, the proof works by encoding the Turing machine which was the verifier of the original problem as a formula. This formula is satisfiable if and only if there exists an input which lets the Turing machine accept. You could in principle use this proof to reduce your current problem to SAT, and after that to every other NP-complete problem via transitivity of polynomial-time reductions.


Nash Equilibrium of 2-players game I have a rather interesting exercise in Game Theory.

Assume there is a 2-players game, and player $i$ has $n_i$ pure strategies. The game is given by listing the payoffs for each player for each $n_1 × n_2$ possible plays.

Give a polynomial time algorithm to check if there is a Nash equilibrium for the game in which each player mixes between at most two strategies.
Give a ﬁnite algorithm for finding a Nash equilibrium for general games with two players. Your algorithm may run in exponential time.

The answer to the first question hopefully can be solved by convex optimization.

In the second case some kind of exhauivet search can be used.

Unfortunately I don't know how to proceed.

Hint: Given a mixed strategy for both players, how can you verify that it's a Nash equilibrium? How many potential strategies do you need to consider in both cases?


Number of ways to fill a 2xN grid with M colors This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri.
In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two cells with the same row or same column have the same color.

The limits given are $1 \leq N$, and $M \leq 1000$ with 1000 test cases per input.

Based on the constraints the approach that comes to my mind after a long struggle includes having a precomputed DP table which can be used for every test case. I tried to apply the inclusion-exclusion principle but could not come up with any solution. I also tried to solve it using bipartite perfect matchings, but no success. How should I approach this question?

You can use inclusion-exclusion. There are $M!/(M-N)!$ choices for the first row. Fix these choices. The number of choices for the second row in which $T$ specific columns are bad (but the row itself is good) is $(M-T)!/(M-N)!$. According to the inclusion-exclusion principle, the required number is
$$ \frac{M!}{(M-N)!} \sum_{T=0}^N (-1)^T \binom{N}{T} \frac{(M-T)!}{(M-N)!}. $$
I'll let you take it from here.


Derandomize MAX-CUT problem using $\log n$ bits Consider the MAX-CUT problem. We can flip $n$ coins to generate a random cut, and  by linearity of expectation we get that with "good probability" our cut we'll be bigger then $\frac{n}{2}$.

Using pseudo random generators (XOR for example) we can generate $n$ pairwise  independent bits from $\log n$ random bits. Using that approach, we can de-randomize the MAX-CUT problem with polynomial complexity.

With that algorithm, we are only checking $n$ possible cuts, where there are total of $2^n$. Is it promised that a "good" cut is within these $n$ cuts? Why?

Consider a graph with $n$ vertices and $m$ edges.

Let $\mathcal{D}$ be a pairwise independent distribution over $\{0,1\}^n$, and suppose that $x = (x_1,\ldots,x_n) \sim \mathcal{D}$. For every edge $(i,j)$, the probability that it is cut in the cut corresponding to $x$ is
$$
\Pr[x_i \neq x_j] = \frac{1}{2},
$$
due to pairwise independence. Therefore the expected number of edges cut is exactly $\frac{m}{2}$, by linearity of expectation. In particular, there is at least one realization of $x$ (that is, one point in the support of $\mathcal{D}$) which cuts at least $m/2$ edges.