GOTO vs. including line in loop - will it affect efficiency? Let's say I have an algorithm something like as follows:

1 eliminate stuff from a list called reactions
2 for each element in reactions:
3    if one thing is computable:
4        compute it
5    else:
6        eliminate element from reactions, GOTO 1

Can I change it too

1 eliminate stuff from a list called reactions
2 while length of reactions is > 0:
3    while thing is computable:
4        for each element in reactions
5            compute it and append it to list called relevant_reactions
6            eliminate element from reactions
7    eliminate element from reactions

without any changes in efficiency? If there are any ways to improve the efficiency please let me know.

For reference, this algorithm is from page 8 of the paper Reachability Problems for Continuous Chemical Reaction Networks. The reason this question is important is because the main result of this paper is showing that the algorithm runs in polynomial time.

The reason the 6th and 7th lines are the same is to eliminate both those elements where the thing is not computable and those where it is computable (those are moved to a new list). I feel like there's a better way to do that part, however, so any advice there would be appreciated.

I should point out that the main reason I am rewriting the algorithm is to remove the GOTO 1. It's hard to implement in Python 3 (my language of choice) and it seems to be generally considered bad practice.

I should also point out what exactly the "thing is computable" is for sake of context/completeness. Basically, that line is computing a vector (that must be $\in \mathbb{Q}^R_{\geq 0}$) that is multiplied by a matrix and when added to another vector should equal another vector. The vector elements are concentrations of chemicals. The matrix contains the net change of various reactions. It would look something like this: (vector that represents current state of the system) + (matrix of net change of every reaction in the list reactions)*(vector we are solving for) = (vector representing current state) and the element in reactions (the one in the iteration of the for loop, also in the vector we are solving for) must be greater than 0. If you found that confusing, no wonder, I did too (especially the last part). The relevant part in the paper is line 3 of Algorithm 1 in section 3. The exact line is

  Compute a vector $F_{\rho}\in\mathbb{Q}^R_{\geq 0}$ such that $\mathbf{c}+\mathbf{M}F_{\rho} = \mathbf{d}$ and $F_{\rho}(\rho) > 0$, if one exists

With the question as it is written right now, I have no idea what "one thing" and "thing" are, the second version modifies a list named "relevant_reactions" that isn't present in the first version, so all in all I would say that your question is impossible to answer.

You say that "goto" is considered bad practice, but instead of removing the "goto", you complete rewrote everything from scratch. If you don't like the "goto" here's a way that doesn't change your algorithm at all:

1 eliminate stuff from a list called reactions
2 all_done = false
3 while all_done is false
4     all_computable = true
5     for each element in reactions:
6         if all_computable is false:
7             do nothing
8         else if one thing is computable:
9             compute it
10        else:
11            eliminate element from reactions, all_computable = false
12     if all_computable is true:
13         all_done = true


How to interpret these asymptotic runtime bounds for discrete logarithm algorithms? I am trying to compare asymptotic runtime bounds of a few algorithms presented in this research paper, A quasi-polynomial algorithm for discrete
logarithm in finite fields of small characteristic.  The functions are,

$L(\alpha) = \exp(O(\log(n)^{a}(\log\log(n))^{1-\alpha}))$,

which I'd like to plot for $\alpha = 1/3, 1/4+O(1)$, and $1/4 + O(n)$,

and $O(n^{\log n})$

  Where n is the bit-size of the input. ... Such a complexity is smaller than any $L(\epsilon)$ for any $\epsilon > 0$

I would like to plot each of these functions together to compare their growth.  The problem is that the second function grows much faster than the first, which implies I am misinterpreting something.

So what is the correct way to interpret and compare these functions?

The confusion is that in the expression for $L(\alpha)$, $n$ is size of the field, whereas in $n^{O(\log n)}$, $n$ is the size of the input. The correct comparison is between $L(\alpha) = \exp O((\log n)^\alpha (\log\log n)^{1-\alpha})$ and $(\log n)^{O(\log\log n)} = \exp O((\log\log n)^2)$, which is indeed much smaller.

Note that your suggestion to plot $L(\alpha)$ for $\alpha = 1/4 + O(1)$ and $\alpha = 1/4 + O(n)$ doesn't make much sense; you should think of $\alpha$ as a constant. It could make sense to consider $\alpha = 1/4 + o(1)$ (or $\alpha = 1/4 + \epsilon$, where $\epsilon$ is understood to be "small"), though it's not clear how exactly you'd plot it. Indeed, there is no reason to plot, and a plot wouldn't make too much sense without knowing the hidden big O constant. In practice you just do experiments.


Why should one not use a 2^p size hash table when using the division method as a hash function? I don't understand what is meant by:

"m should not be a power of 2, since if m = 2^p, then h(k) is just the p lowest-order bits of k." (pg. 231 of CLRS)

Terms defined:

m: size of hash table
h(k): hash function = k mod m
k: key

I don't understand what the p lowest-order bits of k means. Any clarification would be very helpful.

Refresh your knowledge of binary! The $p$ lowest-order bits of $k$ are the last $p$ bits when $k$ is written out in binary (i.e., the $p$ rightmost bits). For example, if $p=3$ and $k=17$ then $k$ is $10001$ in binary and the three lowest-order bits are $001$.

The point is that, in general, computing $k \bmod m$ is a relatively expensive operation.  However, if $m=2^p$ is a power of two, the remainder operation is to just look at the $p$ lowest-order bits. That can be done in a single instruction, by taking the bitwise AND with $2^p-1$.

If it's easier, consider the decimal case. If I ask you what is $8237643\bmod 1034$, your response will be to reach for your calculator; if I ask you what is $8237643\bmod 1000$, you'll tell me that it's $643$ with barely a thought.  This is because $1000=10^3$ is a power of ten, whereas $1034$ is not.  (There's no immediate equivalent of the bitwise AND trick for decimal.)


Why are bytes treated like the base unit? If bits are the base unit of information, why are bytes treated like the base unit?

For example, usually values are expressed in Mega/Giga/Tera/Exa bytes instead of bits. I am aware that bits are sometimes used (e.g. sometimes for internet speed), but generally to me it seems like bytes are used as if they are the base unit instead of bits.

For historical reasons.

In the early days and even so today a byte represented the most commonly used data.

A byte represents one character in ASCII.

A byte was and still is the size of the instruction for the most commonly used opcodes at the assembly level. Having the most common instructions in one byte saved the most amount of memory.

It is a power of two so 8 is better than 7,6, and 5.

You can get two BCD digits in one byte.


Does NP-Complete imply non-satisfiability? I've seen a lot of text concerning the first NP-Complete problem, Boolean Satisfiability. I guess I'm confused concerning the language.

It sounds to me as though the problem could be difficult to compute (hence the NP-complete), however it still might be satisfiable. As in, there exists a satisfying mapping of literals. We can't necessarily compute it easily, but it's out there.

In fact, I would guess that the two adjectives really have no relation to each other. But, when working with problems, I am often asked to see whether a set of clauses is satisfiable. Does that mean, Can we compute a satisfying mapping? And by extension, does NP-complete imply that a given CNF setup is unsatisfiable?

You're confusing languages and instances of them. A 3SAT formula could be either satisfiable or unsatisfiable. The 3SAT problem is to decide whether a given 3SAT formula is satisfiable. The 3SAT language is the set of all encodings of satisfiable 3SAT formulas. Only the 3SAT language is NP-complete. NP-completeness is a property of languages, not of their instances. If every 3SAT formula were satisfiable (or every one were unsatisfiable) then 3SAT (the language) would be very easy.


Bin packing with twin items Assume we are given $k$ bins of capacity $b$ and $n$ items with integral sizes $x_1,\dots,x_n$. The bin packing problem is to decide whether there exists an assignment of items to bins such that no bin exceeds its capacity. In this standard from, the bin packing problem is well known to be NP-hard. However, consider a version of the problem where every items has a twin of equal size. More formally, if $i$ and $j$ are twins, it holds that $x_i = x_j$.

For two bins, the problem is easy since there exists a feasible solution if and only if a packing where no twins share the same bin is feasible. However, what happens if we have more than two bins? I suspect that the problem becomes NP-hard. Unfortunately, I have not been able to prove this so far.

Does anyone have an idea for a reduction or know if the problem has been studied before? Also, if the problem is hard for twins, does the hardness carry over to triplets, quadruplets etc.?

As it turns out by a rather complicated chain of reductions starting from three dimensional matching, which is too involved to be discussed here, bin packing remains NP-hard for twin items. It even remains hard for triplets, quadruplets or any fixed number of similar items.


When to rebalance the AVL tree? Consider we have an AVL tree.

Its left subtree A has disbalance coefficient has value +1 (meaning the right subtree has greater depth). Its right son has disbalance coefficient -1 (meaning left subtree has greater length).

If I understand correctly, we're looking for the most right vertex in the left subtree.

After deleting this specific vertex, what are possible cases regarding the tree rebalancing? When will it have to be rebalanced and when not?

Please correct me, if I've made any mistakes.

Let $w$ be the node to be deleted

1) Perform standard BST delete for $w$.

2) Starting from $w$, travel up and find the first unbalanced node. Let $z$ be the first unbalanced node, $y$ be the larger height child of $z$, and $x$ be the larger height child of $y$. Note that the definitions of $x$ and $y$ are different from insertion here.

3) Re-balance the tree by performing appropriate rotations on the subtree rooted with $z$. There can be 4 possible cases that needs to be handled as $x$, $y$ and $z$ can be arranged in 4 ways. Following are the possible 4 arrangements:

a) $y$ is left child of $z$ and $x$ is left child of $y$ (Left Left Case)

b) $y$ is left child of $z$ and $x$ is right child of $y$ (Left Right Case)

c) $y$ is right child of $z$ and $x$ is right child of $y$ (Right Right Case)

d) $y$ is right child of $z$ and $x$ is left child of $y$ (Right Left Case)

Like insertion, following are the operations to be performed in above mentioned 4 cases. Note that, unlike insertion, fixing the node $z$ won’t fix the complete AVL tree. After fixing $z$, we may have to fix ancestors of $z$ as well (See this video if you have trouble visualizing the above mentioned cases).

Courtesy of Geeksforgeeks.


Solvability of Turing Machines I'm preparing for an exam, and on a sample one provided (without solutions), we have this question: Is the following solvable or non-solvable: Given a turing machine $T$, does it accept a word of even length? - Given a deterministic 1-tape turing machine $T$, does $T$ ever read the contents of the 10th cell?

Thanks! -

"Non-trivial properties" for Rice's theorem are properties of the language, not of the machine itself - for instance, it's decidable how many states a TM has, which is certainly a non-trivial property!  See Perplexed by Rice's theorem for a bit of a clarification on this.  Now, one of your two properties is a property of the language, while one is a property of the machine; this should allow you to apply Rice's theorem in one case but not the other.  Note that this isn't conclusive evidence that the other case is solvable, but it's guidance that you might try looking for a positive answer there.

(Note that this is meant to be a very loose hint just to guide you; I can certainly go into more specific details if you'd like...)


CTL* query evaluation order I'm currently trying to evaluate a CTL* expression and am not sure how to stepwisely evaluate the queries.
For example I have EFG p. This means something like 'there is a path where eventually there exists a state s where from there on, globally p holds true'.

Globally means that for all successors of a state on all paths starting at this state a certain property holds true.

Applied to the example above, this would mean when evaluating EFGp on a model with init-state s0, that there exists a path from s0 to a state s' where from there on all succeeding paths have the property p.
But wouldn't this imply that this is equivalent to EFAG p?

Is it in general possible to evaluate such queries stepwise (operator by operator) or do I have to consider all operators at once?

best regards

Your interpretation of the $G$ modality is incorrect; it does not inherently talk about all paths. In particular, the example you give specifies that there is a path such that from some point on, all states on that path satisfy $p$.

As you suspect, for CTL* it is in general not possible to use a simple bottom-up evaluation, as you would for CTL, the reason being the LTL-like nested temporal operators.


LR parsers and ambiguous and non deterministic grammars Dragon book says:

  An ambiguous grammar can never be LR.

And then immediately further it says:

  For example, consider the dangling-else grammar:

  $\begin{align} stmt \rightarrow & \textbf{ if  } expr \textbf{ then }stmt   \\
      &| \textbf{ if  } expr \textbf{ then }stmt \textbf{ else } stmt \\
      &|\textbf{ other} \end{align} $

  If we have a shift reduce parser in configuration

  $$
\begin{matrix}
STACK & INPUT \\
...\textbf{if }expr\textbf{ then }stmt  & \textbf{else...}
\end{matrix}
$$

  we cannot tell whether $\textbf{if }expr\textbf{ then }stmt$ is the handle, no matter what appears below it on the stack. Here there is a shiftl reduce conflict. Depending on what follows the $\textbf{else}$** on the input, it might be correct to reduce $\textbf{if }expr\textbf{ then }stmt$, or it might be correct to shift $\textbf{else}$ and then to look for another $stmt$
  to complete the alternative $\textbf{if }expr\textbf{ then }stmt \textbf{ else } stmt$.

My question is quite simple one. The author starts with saying fact about "ambiguous" grammar but then he gives example of problem with same prefix of right sides of two productions (say non deterministic grammar) but not really related to the ambiguousness of grammar.

Am I right? Also what does that mean? LR grammar cannot work with both: Non deterministic and ambiguous grammars?

The grammar is really ambiguous.

$\textbf{ if  } expr \textbf{ then   if }expr \textbf{ then  } stmt \textbf{ else  } stmt$

has two possible parses with that grammar. (The $ \textbf{ else }$ can attach to either $\textbf{ if }$.)

As you say, determinism and ambiguity are orthogonal. Certainly, there are unambiguous grammars which are not LR. But no ambiguous grammar is LR and this is one such example.


convergence rate of newton's method So, I'm currently studying Newton method used for finding the 0's of a function, however my professor has only announced  that the speed of this algorithm can be more than quadratic, however I'm wondering when this happens, since in the demonstration used by him to explain the quadratic case, there is no evidence about the "more than quadratic"
Using Taylor and Lagrange
$f(\xi)=f(x_n)+f'(x_n)(\xi-x_n)+\frac{f''(z_n)}{2}(\xi-x_n)^2$
$-\frac{f(x_n)}{f'(x_n)}=\xi-x_n+\frac{f''(z_n)}{2f'(x_n)}(\xi-x_n)^2$
$x_{n+1}-x_n=\xi-x_n+\frac{f''(z_n)}{2f'(x_n)}(\xi-x_n)^2$
$e_{n+1}=\left|x_{n+1}-\xi\right|=c_ne_n^2 \quad \text{with} \quad c_n=\frac{1}{2}\frac{\left|f''(z_n)\right|}{\left|f'(x_n)\right|}$
Can someone please tell me when (example) the order of the convergence is cubic, and why?=

Since you asked specifically about cubic, consider $f(x)=x+x^3$.
The Newton iteration would be $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{x_n+x_n^3}{1+3x_n^2}=\frac{2x_n^3}{1+3x_n^2}$$
It converges to the root $x=0$. So, for $1-3|x_n|^2>1/2$,
$$\epsilon_{n+1}=|x_{n+1}-0|=\frac{2|x_n|^3}{|1+3x_n^2|}\leq \frac{2|x_n|^3}{1-3|x_n|^2}\leq 4|x_n-0|^3=4\epsilon_n^3$$


An indexing function for graphs Definition from wikipedia:

  A graph is an ordered pair $G = (V, E)$ comprising a set $V$ of nodes together with a set $E$ of edges, which are two-element subsets of $V$.

The set of all finite graphs (modulo isomorphism: we don't want nodes to have identities) is countable and could be enumerated. But what would be an efficient (low-complexity, from a programming point of view) injection from graphs to $\mathbb{N}$?

Edit: Gilles' comment indicates that it is not know whether there is a such function feasible in polynomial time. An example of an exponential-complexity function would be good enough; we can surely do better than a brute enumeration?

A graph $G$ whose nodes are numbered is uniquely described by its adjacency matrix. Concatenating the matrix's rows yields a natural number $\cal{G}$ in binary representation; in order to deal with leading $0$, prepend a $1$. This mapping is obviously injective. For easier decoding, you might want to use Cantor's pairing function on $(\cal{G}, |V|)$ and use the result as graph number.

Computing this mapping is easy, but the resulting number can be huge ($\approx 2^{|V|^2}$).

In the case nodes cannot be identified, the (conjectured) hardness of Graph Isomorphism (probably) prevents an efficient, real mapping from Graphs to the naturals; for now, we have to be satisfied  with a mapping from graph presentations to naturals---or show considerable genius.


Longest common sequence matrix giving wrong answer I am trying to find longest common sequence for these two strings

SHINCHAN
NOHARAAA

The common sequence is NHA of length 3

But when I am trying to find out this through LCS matrix which I learnt from this link
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Based on the explanation and this example given there

I built this matrix for my case

But my matrix is reaching to the length 6 while it should reach to length 3 only because that is the longest comment sequence of the two strings I am using.

Could anybody please point out the mistake I am doing?
I can see the problem is happening because of the extra 3 A's at the end of one of the string.

Look at row=1 and column=8 (using 0 indexed numbers) in your matrix. That value says that the length of LCS between SHINCHAN and N is 2, which is impossible since N itself is of size 1.

When s1[i] and s2[j] are equal you need to look at the number in matrix[i-1][j-1] and add one and not matrix[i][j-1] (which I think you are doing). You can compare your method to the pseudocode written in the wikipedia article to arrive at the correct matrix (copied below for convenience)

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]


Find X contiguous segments in a range of integers I've been struggling with the following problem: how do I find all possible sub-ranges in a range of integers where each segment is at least length 1, and I specify the total number of segments? A couple examples:

segments=2, range=(0,5)
> [0,1],[2,5]
> [0,2],[3,5]
> [0,3],[4,5]

segments=3, range=(0,8)
> [0,1],[2,3],[4,8]
> [0,1],[2,4],[5,8]
> [0,1],[2,5],[6,8]
> [0,1],[2,6],[7,8]
> [0,2],[3,4],[5,8]
> [0,2],[3,5],[6,8]
> [0,2],[3,6],[7,8]
> [0,3],[4,5],[6,8]
> [0,3],[4,6],[7,8]
> [0,4],[5,6],[7,8]

This feels like a recursion problem because I need to iterate over a varible number of for-loops, but I don't see how to make it work.

Here's a quick piece of pseudo-code off the top of my head.

Given maximum value m and number of non-empty segments n, do so:

  Call Helper(Empty List [passed by reference], Empty List [copied before passing or passed by copy], 0, m, n)

The helper function takes as input:

a reference to the output list of lists,
a list of segments to append more segments to
the lower bound or starting value
the upper bound or stopping value
the number of segments

function Helper(L, S, l, u, n):
  If n = 1 then append to L the list S.append(l, u)
  Else:
    For each t from l+1 up to u-n *inclusive*:
      Make a copy of S into S'
      Append to S' the pair (s, t)
      Call Helper(L, S', t+1, u, n-1)

As you can see, the only "trick" was perhaps just figuring that out you should use a helper function with more arguments to aid the recursion. Of course, different solutions may be possible.

A note here. It should be possible to change the implementation above slightly (e.g., using return values as opposed to passing L by reference) that one can memoize the result of each call for a given triple (l, u, n). Such a DP approach seems to me like it may make the program be significantly faster on large input. I assume this sort of problem has much sharing to be exploited using a DP approach.


Really confused about latency with pipelining I finished watching a video about pipelining https://www.youtube.com/watch?v=eVRdfl4zxfI
which I thought made sense.
Latency is the amount of time it takes to complete each instruction. Even with pipelining, the time it takes to complete an instruction is still the sum of the time it takes for every stage, in this case it's 20ns.

But then I did a bit more studying and found out the latency is supposed to be time for the longest stage to finish execution + the "cost" of pipelining, rather than the sum of time it takes to execute all the stages?
http://web.cs.iastate.edu/~prabhu/Tutorial/PIPELINE/perform.html

Is there something I'm missing?

It is possible that you did not understand the mentioned references. Let say that $T_s$ is the time that is needed for completion of each stage, and $k$ is the number of stages. $T_s$ may or may not include the cost of pipelining. The latency of the first instruction is equal to the sum of times needed for completion of each stage, i.e.,
$kT_s$. Once the pipeline is full, the latency of each subsequent instruction is $T_s$. Therefore, the total time needed for execution of $n$ instructions is: $kT_s$ (first instruction) $+ (n - 1) T_s$ (each subsequent instruction).

Therefore, when pipeline is full, latency of each instruction is $T_s$. Still, the time needed for completion of each instruction is $kT_s$. Please note the difference between the latency and the time needed for completion of instruction. Pipelining only reduces the latency.


Hashing using search trees instead of lists I am struggling with hashing and binary search tree material.
And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And I try to understand what the worst-case and average-case running time for the operations

insert,
find and
delete

is in worth- resp. average case. Do they improve with respect to lists?

For lists, insertion, find and delete are respectively in $O(1)$, $O(n)$, $O(n)$. Sorted list are worse. Binary search itself is for sorted arrays, in which the operations are in $O(n)$, $O(\log n)$, $O(n)$. If you want "insertion" and "delete" operations then you need more than just binary search.

You probably want something like binary search trees. It is a lot easier to find references about it once you have the proper terminology. These operations are in $O(\log n)$ worst-case time, for example for the implementations using AVL trees and red-black trees.


Why do you need to fill the first element of array when implementing heap? I'm looking at Heap data structure implementation from different sources. What I found is that sometimes it's implemented with the first element of array set to magic (default, unused?) value.

For example here the first element is added in constructor.

And visualization here shows that it's also set to something magic.

However, I've seen many examples without the first element. What's the trick and why sometimes it's there and sometimes it's not?

It is not some magic element but $-\infty$, which is because this is min-heap, in max-heap it would be $\infty$.
The sole purpose is consistent representation of all elements inserted - it guarantees that the next element can be compared and it will be smaller (or bigger - for appropriate heap type) - just to avoid checking whether inserted element is the first one or not and then it would be compared to existing ones. In this form you avoid something like isEmpty everytime you insert element, so it saves time, redundant function calls and (rather unwanted) conditional statement at the cost of one element called "guardian" or sometimes "terminator" (popular name in the lists where you check for this element instead of some NULL or isEnd).


Recurrence relation chip and conquer Can anyone explain how to find the $\Theta()$ of this equation...
$$T(n) = 3T(n-4) + cn$$
When I solve this problem I get this using the $k$ -th iteration...
$$T(n) = 3^{k}T(n-4k) + 3^{k-1}c(n-2(k-1)) + 3^{k-2}c(n-2(k-2)) + ... + cn$$
I factor out c and get this...
$$T(n) = 3^{k}T(n-2k) + c(3^{k-1}(n-2(k-1)) + 3^{k-2}(n-2(k-2)) + ... n)$$
I'm not sure if we need to find an upper and lower bounds or solve the geometric series. Any suggestions? I need to find $\Theta()$ and we didn't cover master theorem so this is how my class was taught to approach these.

The answer should be $\Theta(3^{n/4})$. You can go both ways you suggest – find an exact formula, or estimate the sum, using an integral or in more devious ways. There is no loss in generality if you take $c = 1$. If you replace $n$ with $1$ (so we get a lower bound), then we have
$$ 1 + 3 + 3^2 + \cdots + 3^{n/4} = \Theta(3^{n/4}), $$
using the formula for summing a geometric series. If you bring back the $n$, the calculation becomes a bit more difficult, but you should still be able to get a matching upper bound:
$$
n + 3(n-4) + 3^2(n-8) + \cdots + 3^{n/4}(0) = O(3^{n/4}).
$$
There are in fact closed formulas for this kind of sum (try Wolfram alpha), but you can also try to bound without them, say by looking at ratios of consecutive terms and comparison to a geometric series:
$$
3^{n/4} \left(0 + 4\frac{1}{3} + 8\frac{1}{9} + 12\frac{1}{27} + \cdots \right) = O(3^{n/4}),
$$
since the infinite series $4\sum_{m=0}^\infty \frac{m}{3^m}$ converges.


Relaxation of the knapsack constraints A set $\mathcal{A}$ is the relaxation of another set $\mathcal{B}$, if $\mathcal{B} \subseteq \mathcal{A}$.

I have a set of points defined as the knapsack constraint

$$
\mathcal{X} = \{x \in \mathcal{Z}^n: w^{\top}x \leq b \}
$$
where $\mathcal{Z}^n$ is the n-dimensional 0-1 vectors and $w \in \Re^n_+$ and $b \in \Re_+$.

I read that one possible relaxation of the above set is
$$
\mathcal{X} = \{x \in \mathcal{Z}^n: \lfloor w\rfloor ^{\top}x \leq \lfloor b\rfloor \}
$$

where $\lfloor \rfloor$ represents the floor function.

It is very counter-intuitive to me.  $w^\top x \leq b$ represents a half space with left or lower space of the hyperplane defined by $w^\top x = b$. By taking the floor function, we are in fact moving the hyperplane lower and shrinking the size of the set.

Can anyone explain to me why the floor function terms represent a relaxed set ?

Let me call $
\mathcal{X}_1 = \{x \in \mathcal{Z}^n: w^{\top}x \leq b \}
$
and
$
\mathcal{X}_2 = \{x \in \mathcal{Z}^n: \lfloor w\rfloor ^{\top}x \leq \lfloor b\rfloor \}
$ to avoid confusion.

Let $x \in \mathcal{X}_1$. Then: $$b \ge w^T x = \sum_{i : x_i = 1} w_i$$ which implies:
 $$\lfloor b \rfloor \ge  \left\lfloor  \sum_{i : x_i = 1} w_i \right\rfloor \ge \sum_{i : x_i = 1} \lfloor w_i \rfloor = \lfloor w \rfloor^T x.$$

Therefore $x \in \mathcal{X}_2$, and this shows that $\mathcal{X}_1 \subseteq \mathcal{X}_2$.


Architecture of a chatbot - how to organize and fetch possibilities? I'm building a chatbot that would respond to text messages.

Let's say that my chatbot works for customers of an internet provider and it can respond to the following things:

Problems:

About payment;
About internet connection.

General requests:

Change user's account e-mail;
Call for technical assistance.

My question is: what's the data structure that I could use to organize this tree?

When Building AI and ML for you Chatbot, you basically have 2 options:

You can use a 3rd party tool which will take care of the
AI/Conversational part of the Chatbot.
You can make your own using Machine Learning.Overwhelming, but quite
a few developers are choosing to go this route and many companies
are trying to democratize Machine Learning.

You can build your own NLP(Natural Language Processing) by using Machine Learning. One of the first things to consider will be the type of model you want to build.

Using an NLP/NLU Platforms: Natural Language Processing (NLP) and Natural Language Understanding (NLU) platforms attempt to solve the problem by parsing language into entities, intents and a few other categories. Different NLP platforms may have different names however the essence is moreso the same.

Categories:

Agents correspond to applications. Once you train and test an agent,
you can integrate it with your app or device.
Entities: represent concepts that are often specific to a domain as a
way of mapping natural language phrases to canonical phrases that
capture their meaning.
Intents represent a mapping between what a user says and what action
should be taken by your software.
Actions correspond to the steps your application will take when
specific intents are triggered by user inputs. An action may have
parameters for specifying detailed information about it.
Contexts are strings that represent the current context of the user
expression. This is useful for differentiating phrases which might be
vague and have different meaning depending on what was spoken
previously.

NLP Platforms:

API
WIT
LUIS
Microsoft Bot Connector

Reference :

NLP & Machine Learning Tutorial
Chatbot AI Tutorials
Machine Learning in a Year
Neural Networks for Machine Learning
You Too Can Become a Machine Learning Rock Star!


Set notation of a grammar Say I have a grammar e.g,

$$\begin{align}S&\to AB\mid abc\\
A&\to aAb \mid \lambda\\
B&\to bBa \mid ba
\end{align}$$

Now it is obvious the notation for this would be something like,
$$L(G) = \{a^{i}b^{i}b^{k}a^{k} |  i \ge 0, k > 0\}$$

My question is how do I account for the starting state going to abc. How can I represent this in set notation? My only thought would be to append $(abc)^{m}$ to the statement and then say something like if i,k == 0 then m = 1. Though I'm not sure if that is allowed?

In contrast to popular thought, the description of a language doesn't have to be of the exact form
$$
L = \{a^i b^j c^k \mid \text{conditions on $i,j,k$}\}.
$$
A language is a set, and you can describe it in exactly the same variety of ways as you describe sets. For example, we can write
$$
L = \{a,b\}^* \setminus \{a^nb^n \mid n \geq 0\}.
$$
In your case, as rici mentions in the comments, you might as well just take a union with $\{abc\}$ to account for the additional case.


longest sub-sequence in both directions Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.

Example: A = cabca

the sub-sequence S = abc is the longest of such sub-sequences.

reading S forward (abc): cabca

reading S reverse (cba): cabca

How to compute the length of such an S ?

One option is to reduce your problem to Longest Common Subsequence. I'll let you figure out how.


DNF and CNF and Complexity Theory $F(z_1,...,z_n)$ is a Boolean expression. The assignment of variable ($x_1,...,x_n \in {0, 1}$) is the answer of $F$, if $F$ for that assignment equals to $1$.
If that case is true and the conditions are met, then both of them are considered to be NP-Hard.

A) The number of answers of $F$ in $DNF$ format.
B) The number of answers of $F$ in $CNF$ format.

DNF and CNF are HERE

Can anyone describe to me in clear, simple, and concise words why both of them are true?

Counting the number of satisfying assignments to $F$ is at least as hard as determining whether there is a satisfying assignment.  (If the count is 0, there are no satisfying assignments; if the count is $\ge 1$, there is a satisfying assignment.)
For CNF formulas, testing whether there is a satisfying assignment is the SAT problem, which is a classic example of a NP-hard problem.
Counting the number of satisfying assignments of $F$ is at least as hard as determining whether all assignments satisfy $F$.  For DNF formulas, this is NP-hard, too.


Chordal graph question In the below image, the graph is being triangulated (added edges are in red). My question is simple :
Is the red edge between nodes 7 and 10 necessary in order to obtain a chordal graph?

(this image comes from Yaroslav Bulatov's excellent answer on https://cstheory.stackexchange.com/questions/5018/the-origin-of-the-notion-of-treewidth/5020#5020)

No, you can delete that edge and the graph remains chordal. This is so because you don't introduce an induced cycle of length 4 or more.


Is there a context free, non-regular language $L$, for which $L^*$ is regular? I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free.

In case there are none how do you prove it?

$L = \{a^n b^n \mid n\in\mathbb{N}\}$ is context-free but not regular (classical example). So is $L' = \{a^n b^n \mid n\in\mathbb{N}\} \cup \{a,b\}$.

$L'^\ast = \{a,b\}^\ast$ is regular.


Why is LinkedList useful? If you implement a stack with a dynamic array-based with LinkedList you need more memory than with a dynamic array, and with dynamic array for insert in amortized cost is O(1), so the advantage of the LinkedList now is not and advantage, so why you should use a LinkedList, and why is this a useful data structure?

For a normal stack, the implementation on top of a linked list is indeed questionable. Many other uses of linked lists are disappointing in practice as well.

But consider a lock-free stack where push and pop are atomic. A singly-linked list can offer atomic prepend and atomic "remove head" using atomic Compare-and-Swap (some caveats apply). Implementing an atomic stack on top of an array is a bigger problem, one that to my knowledge has not been satisfactorally solved.

The downside that linked lists tend to weave their way somewhat randomly through memory can occasionally be turned into an advantage: elements that are in some other data structure can have a linked list weaved through them without imposing requirements on the addresses of the elements. For example, elements in a hash map can also have a linked list running through them that records their insertion order, while maintaining fast removal (a dynamic array that records the indexes of the elements in insertion order would still allow fast insertion but not fast removal since it could happen in the middle). Elements can even be in several different linked lists at the same time, an example of that is dancing links algorithm which uses linked lists for columns and rows and elements are in both a column and a row at the same time.


Coefficients in cost function in A-star I'd like to expand on this question :

https://stackoverflow.com/questions/52420788/why-does-the-a-star-algorithm-need-gn

Dijkstra's algorithm uses cost function $f(n) = g(n)$
whereas A* uses cost function $f(n) = g(n) + h(n)$, with $g(n)$ being the cost of the path from the start node to node $n$, and $h(n)$ is a heuristic function that estimates the cost of the cheapest path from node $n$ to the goal.

It is clear from the linked question's answer that A* needs its $g(n)$ function in the cost function.
My question however is the following. Can one use the cost function :

$f(n) = \alpha g(n) + (1-\alpha)h(n)$

for some alpha $0<\alpha<1$ ?

I ask because in some cases I observed it can be much faster to prioritize (through a coefficient) estimated cost over already traversed cost. I am not sure however if this still results in an optimal path?

EDIT : multiplying the heuristic $h(n)$ by some alpha $0<\alpha<1$ is allowed, since this operation still underestimates if $h(n)$ already did (which is necessary to obtain the resulting optimal path). I am more concerned about the multiplying of $g(n)$.

For A* to get the optimal path it requires that $f(n) \leq g(goal)$. In other words that the heuristic underestimates the cost from the node to the goal.

Multiplying a valid hueristic with $0 \lt\alpha\lt 1$ will not violate this requirement.

Multiplying $g(n)$ is not allowed because you can end up with $f(goal) = \alpha g(goal) < f(n)$ which would violate the requirement for getting the optimal path.


What is meant by the term 'state' in a finite-state machine? What is meant by the term 'state' in a finite-state machine?

I have not seen a proper definition on the web and am looking for a university-level answer.

Thank you in advance.

A state is simply an assignment of all possible variables of a system to values. A state transition then means a transition from one possible set of values of variables to another set of values.

To see how this might be useful, imagine a set of two switches $S$ and a light bulb $B$ that are connected to emulate some unknown logical gate. If you want to find out what that gate is, you can use a state machine model:

Say $I = \{S,B\} $

Initial State: $I = \{\{0,0\},0\}$

State transitions:

$\{\{0,0\},0\} \rightarrow \{\{1,0\},1\} \rightarrow \{\{0,1\},1\} \rightarrow \{\{1,1\},0\} $

It is evident that every state is just a set of different possible values of $I.$

By looking at the values of $B$ for a set of values of $S$, You can easily deduce that the system emulates a XOR gate.


stable marriage/residency problem with multiple matches Consider the stable marriage problem, where both sides want to match with multiple individuals from the other side (perhaps a fixed number, or perhaps within some range). Something like, if doctors could choose to go to more than one medical school at the same time.

Is there a variation on the deferred acceptance algorithm to handle this generalization? Can I just have each "doctor" propose to n hospitals at each step, where n is the number of hospitals he is trying to attend at once? Also, what if hospitals do not have preferences?

Suppose you have a doctor that you want to assign to three hospitals.  Replace that doctor by three copies of him.  In other words, instead of a single vertex for Dr. Smith, you have three clones, Dr. Smith #1, Dr. Smith #2, and Dr. Smith #3.  They all have the same preference list.

Suppose you have a hospital that wants two doctors.  You can do the same thing: instead of a single hospital, you have one entity per open position at that hospital.  They all have the same preference rankings.

Now use the standard stable marriage algorithm on the resulting set of clones and open positions.  This will find a stable matching that obeys the multiplicity constraints you identified; that follows directly from the correctness property of the standard algorithm.


Why does a software video encoder create higher quality output than a hardware video encoder It is said commonly that a software video encoder has creates higher quality output than hardware encoder. Higher quality here means higher picture quality at a given bit rate.

Hardware encoders are commonly for realtime usage and some are for mobile applications, then there are trade offs in hardware encoders to get realtime performance and have lower power.

Commonly what exactly is the trade off (e.g. which encoding algorithm parameter) in hardware encoder that makes it have lower quality than a software encoder?

Will simply changing some encoding parameter (and as a result more chip area and power consumption) make a hardware encoder have the same quality as a software encoder?

H.264/H.265 are considered.

There is no reason in principle why hardware would have to produce worse results than software. But there are two problems:

Better quality requires better algorithms, and better algorithms in hardware usually take more circuits and cost more money, while higher quality in software can be almost free.
Real-time encoding must finish in given time. If you run a video conference you have one second to encode one second of video. Even if you knew how to produce better quality in more time, you are not allowed to. But if you use an offline encoder, that can give you an option to encode an hour of video in six hours with low quality, in twelve hours with medium quality, or in 36 hours with highest quality.

And of course you can have the latest and best quality software encoder at any time. If your hardware is three years old and not very good, replacing it with much better new hardware is inconvenient and costly.


clique, independent set, and minimum vertex cover I was given a graph problem with 3 different questions and 1 set of answers. The problem is described below. The problem that I'm having is that it seems to me that the answer to all the questions is the same. I keep trying to find a caveat but I don't see one. What am I missing?

Here is the problem

Undirected graph $G$. $n$ - number of vertices. $m$ - number of edges. $d$ - maximum degree of a graph.

The maximum clique size of $G$ is no larger than
The minimum vertex cover size of $G$ is no larger than
The maximum independent set size of $\overline{G}$, the complement of $G$, is no larger than

Set of answers

(a) $d+1$
(b) $n$
(c) $n-1$
(d) $n/2$
(e) $d$
(f) $n-d$

It looks to me that the answer to every problem is (b) $n$, because

Clique cannot have more vertices than there are in a graph
Vertex cover cannot be larger than the number of vertices in a graph
Maximum independent set cannot be larger than the number of vertices in a graph.

I feel like I'm missing something, because the answers seem too obvious.

Any help is appreciated

Of course, $n$ being the largest of the given answers will satisfy all conditions. You are expected to find the least upper bounds though.


Is Datalog negation and the built-in predicate $ \neq $ similar? I was reading "Principles of Database & Knowledge-Base Systems, Vol. 1" by Jeffrey D. Ullman. There is a chapter about Datalog negation and as I was seeing the problems of negation I kept thinking that using the predicate $ \neq $ would solve those problems but then I see the following:

p(X) :- r(X) & ¬q(X).

q(X) :- r(X) & ¬p(X).

The problem is this has 2 minimal models and if I'm not mistaken so does this:

p(X) :- r(X) & q(Y) & X $ \neq $ Y.

q(X) :- r(X) & p(Y) & X $ \neq $ Y.

Is there an equivalence between these 2 operators? If so, did I miss it or is it not mentioned that it's unsafe to use $ \neq $ with recursion?

There was a misunderstanding in regards to the evaluation algorithm/minimal model.

The derivation of new values is atomic e.g.:

step 1:

p = {}
q = {}

step 2:

p = r
q = r

In step 2 p and q only see the value that each other had at step 1(the old value). I thought p and q would have access to the value of the current step and thus, the order of evaluation would produce different results.

To answer the question:

p(X) :- r(X) & q(Y) & X ≠ Y.

q(X) :- r(X) & p(Y) & X ≠ Y.

only has one minimal model: p = r and q = r.


Optimizing greedy solution for choice game Consider the following game: Two players choose numbers from a sequence of integers with even number of elements. The two can only choose from either the front or the end of the sequence. The purpose is to pick a series of numbers that form a sum greater than the opponent's. The first player always starts and tries to beat the second player, which chooses his numbers randomly. Develop a strategy with which the first player always wins. By winning we consider that the first player's sum is greater or at least equal to the second player's sum.

My solution (greedy): At each step, P1 chooses the greater number between the front and the end of the sequence. At the end Sum(P1) >= Sum(P2).

Example:

S: 4 5 3 1
P1: 4
P2: 5 or 1
P1: if P2 picks 1, then P1 picks 5 || if P2 picks 5, then P1 picks 3
P2: picks either 3 or 1, depends on P1's choice
Sum(P1) (= 9 or 7) >= Sum(P2) (= 6 or 4)

Problem: For certain sequences, the above greedy approach does not compute a greater sum for P1. For S: 1 2 80 3, if P1 will choose 3 as it is greater than 1. If P2 then picks 80, the game is lost for P1.

My take on this situation: We scan S for it's greatest numbers and compare them to the greatest sum of numbers chosen up to them and create a strategy for P1 so that he chooses the greater number/ numbers. In the example above we find that 80 > 3 +1 (possible sum up to it), so P1 will first choose 1. This way P2 will have to pick from 5 and 3. After P2 chooses, P1 picks 80 and wins.

Thoughts on this?

The first player cannot always win – consider the case in which all numbers are the same. But we can always guarantee a draw. Here is the strategy – I'll let you figure out why it works.

  Given the sequence $a_1,\ldots,a_{2n}$, calculate $a_{odd} = a_1 + a_3 + \cdots + a_{2n-1}$ and $a_{even} = a_2 + a_4 + \cdots + a_{2n}$. If $a_{odd} > a_{even}$, always pick odd indices. If $a_{even} > a_{odd}$, always pick even indices. Otherwise, the game is a draw.


Propositional logic --- syntactical completeness Lets consider propositional logic. We say a proof system for propositional logic is syntactically (negation) complete if for every $\alpha$, either $\alpha$ or $\neg \alpha$ are provable within the system, i.e., $\Sigma \vdash \alpha$ or $\Sigma \vdash \neg \alpha$. (I assume standard definitions for $\Sigma$ and $\vdash$).

It seems to be me that no sound proof system for propositional logic could prove $p$ or $\neg p$ from empty set of sentences, where $p$ is a propositional atom. So, propositional logic is not syntactically complete.

Now, it is to my understanding that this is kind of completeness Godel was considering in his Incompleteness Theorem for FOL. Since FOL (with abuse of terminology) subsumes propositional logic, it trivially holds that FOL is not syntactically complete either. This seems to simple, so I am wondering what am I doing wrong? Or his proof focused on Peano arithmetic specifically?

Related: link

You are not doing anything "wrong", you just missed the point of the incompleteness theorem, a bit.

What you claim (correctly) is that a proof system with no axioms is incomplete. You also say that this is not very impressive...

What Godel showed is something much stronger: consider the theory of Peano arithmetic, then there does not exist a complete axiomatization for it.

How does this relate to your post? Well, in your suggestion, even when you consider an empty set of axioms, there are still some true sentences (the tautologies), and there are axiom systems that capture exactly those sentences.


Optimal Algorithm for Finding Maximal Number of Colinear Points Given a set of $n$ point in a plane, find the maximal number of colinear points (the points residing on the same straight line).

The crudest algorithm is to compute the slope and intercept of each pair of point, assuming infinite precision, find maximal number of appearance of the same pair of parameters.

Is there an algorithm more efficient (1) in the worst case, (2) on average? What is the optimal one (1) in the worst case which I suspect the crude method with complexity $n\choose 2$ is the optimal, (2) on average; and how to prove it?

Algorithm: RANSAC would be a good algorithm for this problem, if you think there exists a line such that a large fraction of points lie on that line.  (However, if there is no such line, RANSAC is not a good choice.)  In each iteration, it randomly selects two points, draws a line through them, and then checks how many other points fall onto that line.  It then does many iterations repeatedly, and keeps the best line it has found so far.

Analysis: Suppose there exists a line $L$ such that a fraction $p$ of the points are on the line $L$.  Then any particular iteration has a $p^2$ probability of picking two points on the line $L$ and discovering the line $L$.  So, if you run RANSAC for $O(1/p^2)$ iterations, then with high probability the line $L$ will be detected.  Each iteration takes $O(n)$ time, so the total running time will be $O(n/p^2)$.  For some values of $p$, this will be faster than your crude algorithm (which has a $O(n^2)$ running time).

In short, the more points on the optimal line, the faster RANSAC will find it.

This doesn't answer your question about the best worst-case complexity.  I don't know if it is possible to beat ${n \choose 2}$ worst-case complexity.  I don't know if this is optimal or if there are better algorithms.  Also, even in the case where we know there is a line containing many points and where we care about average-case complexity, I don't know if RANSAC is optimal or if one can do better.


Help with understanding Simulated Annealing algorithm I'm trying to wrap my head around it, but no matter what I read, I still can't fully understand it.
I tried to read a little bit about the annealing process in physics, but I have no background whatsoever in physics, let alone in thermodynamics, so I couldn't understand what is it exactly, and how it fits into the algorithm.
Here is the algorithm:

In the Hill Climbing algorithm, the reasoning can be easily described: Of all the successors of the current state - choose the highest-valued. But in Simulated Annealing... well, I can see what the algorithm does, I just don't understand the reasoning behind it:
1. It starts a timer.
2. It chooses a random successor.
3. It evaluates how "far away" the randomly chosen successor from current.
4. If the successor is indeed a "progress in the right direction" ($\Delta E > 0$) then we move ahead towards the direction of successor; otherwise, we move ahead towards the direction of successor with some (odd) probability that depends on the timer(?).

Why is randomly choosing a successor better then the Hill Climbing method?
Can someone please explain the reasoning behind it?
Do I really have to understand the annealing process? If so, can someone please explain it in layman terms?

The variable $T$ is not a timer but the temperature. It starts very high, making it more likely that transitions are taken, and then slowly cools. It's called annealing due to the metallurgical technique of the same name.

Simulated annealing handles one problematic aspect of the hill climbing algorithm, namely that it can get stuck at a local optimum which is not a global optimum. Instead of getting stuck, simulated annealing offers a way out: if the proposed change only marginally deteriorates the objective function, then with some reasonable probability with make it anyway. This way we can escape local optima.

As the process proceeds, we increase the threshold of making unfavorable changes by decreasing the temperature; when the temperature is zero, simulated annealing is the same as hill climbing (and when the temperature is infinite, it is the same as a random walk). The idea is that at first we need to escape local optima more vigorously, but eventually we settle at a good solution which does not require as much tinkering with (except for hill climbing).

You mention that hill climbing always chooses the best neighbor, but this is only one version of the algorithm, and not necessarily the best one. In other versions we choose an improving neighbor in some other fashion. I don't have much intuition which approach is better, though you are right that choosing the best neighbor sounds like a reasonable heuristic.


Complete graph invariant Does anybody know whether the multiset of the determinants (possibly together with the order of the submatrix they refer to) of all the principal minors of the (symmetric) adjacency matrix of a graph is a complete invariant for graph isomorphism (i.e. that multiset uniquely identifies a graph up to isomorphism)?

The  answer is no. A counterexample is given by the following two graphs both having $(-1,
 -1,
 -1,
 -1,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 1)
$ as the multiset that you describe.

If you want to play further, you can use the following Sage program that found them

def tupleDet(G):
    A = G.am()
    L =  []
    for sub in subsets(range(G.order())):
        D = A.matrix_from_rows_and_columns(sub,sub)
        L.append(D.det())

    return tuple(sorted(L))

def search(n):
    d= {}
    for G in graphs.nauty_geng(str(n)):
        des = tupleDet(G)
        if des in d:
            print G.graph6_string(), d[des]
            return
        else:
            d[des] = G.graph6_string()


How to estimate the average time complexity of greatest common divisor? As we know, the time complexity of $\gcd(x,y)$ is $O(\log \min(x,y))$ by using Euclidean algorithm. Now we fix a constant $n$ and consider the average time complexity of $\gcd(x,n)$.

Formally, let $f(x)$ be the number of divisions when calculating $\gcd(x,n)$. How to give a bound of $\frac 1 n \sum_{x=1}^n f(x)$?

I don't konw whether it is strictly $o(\log n)$ or $\Theta(\log n)$. How to prove the bound?

I list some of $n$ and the coresponding value here.

$n$ ; $\frac 1 n \sum_{x=1}^n f(x)$
1000;6.42;
10000;8.34;
100000;10.26;
1000000;12.20;
10000000;14.13;
100000000;16.07;

Since $n\geq x$ in your sum, $O(\log\min(x,n))$ simplifies to $O(\log x)$. Being very careless with constants here, but $$\frac{1}{n}\sum\limits_{x=1}^n f(x)=\frac{1}{n}\left(n\cdot O(\log n)\right)=O(\log n)$$

I'm not sure what this is calculating though; average runtime of all input sizes less than $n$?


Nondeterministic automaton accepting only words whose first letter is identical to their next to last letter I was asked this question and could not come to the correct answer:

Let $L$ be the language of all words over $\{a,b\}$ where the first letter is identical to the letter that is next to last. (Pay attention – every word with length 2 is in the language.)
Sketch a nondeterministic automaton that accepts this language.

Any help would be appreciated.

Hint: you want to make states $x/y/z$  which mean that $x$ is the first symbol of the word, $y$ is the second to last symbol seen, and $z$ is the last symbol seen.

I will show you half of the final machine, the one for words starting with $a$. Note that "!a" here means any symbol not equal to a, or no symbol at all.


Definition of the inverse of the Ackermann function I am somewhat puzzled by the definition of the inverse of the Ackermann function: The normal Ackermann function $A$ can be used to define a function from $\mathbb{N} \to \mathbb{N}$ via $A(n, n)$. The inverse of this function, denoted by $\alpha$, is known as the inverse Ackermann function.

My problem is: Only bijective functions have an inverse. But I have seen no proof that $A(n, n)$ is indeed bijective. It seems highly unlikely to me that this is the case (since the value of $A(n, n)$ increases very quickly in $n$).

My guess is that $\alpha(m)$ should be defined as $\min \{n \mid A(n, n)  \geq m\}$ or $\max \{n \mid A(n, n)  \leq m\}$. Is that the case?

The Ackermann function $n \mapsto A(n,n)$ is definitely very far from being bijective, otherwise it could not grow so quickly. However, in the contexts it is usually employed (complexity theory, oh notations, ...) it is not really relevant which are the actual values of $\alpha$ point by point. You can add one or multiply by three and the results are the same, so nobody really cares about what is the actual definition. Any of your two will work.


Are loop counters spatially or temporally local? Consider this nested loop:

for (i=0 to n)
   for(j=0 to n)
      for (k=0 to n)
         sum := sum +k
      end for
   end for
end for

Do i,j and k have temporal or spatial locality?

I've considered j and k as temporal since they are revisited again in the loop. But I'm confused about i as it does not match the definitions of temporal or spatial.

A set of variables has temporal locality if they are accessed within a relatively short period of time. sum, k and n are all accessed at every iteration of the inner loop; assuming that n is relatively large, i and j are not accessed frequently. So sum, k and n are temporally local, j could be considered temporally local with them but i probably isn't.

Variables have spatial locality if they are stored at addresses that are close together – e.g., close enough to be in the same cache line or, at least, the same page in memory. As such, spatial locality is a property of compiled code, not source code, so it's impossible to say what variables in the code are spatially local: a stupid compiler or memory manager could scatter them to the four corners of the address space. But one would hope that temporally local variables that are accessed repeatedly would be spatially local.


Relation between covering radius and columns of parity check matrix Let $C$ be a $[n,k]$ linear Code over  $\mathbb{F}_q$ .

I want to show that each vector of $\mathbb{F}_q^{n-k} $ is written as a linear combination of $m$ columns of $H$ iff $\rho \leq m$.

I have thought the following:

$$ d(C)=\min \{ d \in \mathbb{N} | \text{ there are d linearly dependent columns of  H}\} $$

So $H$  has $ d-1 $ linearly independent columns , so each vector of $\mathbb{F}_q^n$ can be written as a linear combination of these columns.

But what can we say about the vectors of  $ \mathbb{F}_q^{n-k}$?

Here is the idea. Suppose that $C$ has covering radius $\rho$. Pick a vector $s \in \mathbb{F}^{n-k}$. Since $H$ is full rank, there is a vector $x$ such that $Hx = s$. There is a vector $y \in C$ with $|x-y| \leq \rho$ (here $|\cdot|$ is Hamming distance). Then $H(x-y) = s$, and so $s$ is a sum of at most $\rho$ columns of $H$. The opposite direction is very similar.


Requiring at least one alldiff constraint to be satisfied converted to SAT For generating certain hard puzzles, I am trying to model a problem (ultimately) in SAT. I don't know how to do that, so I am starting with CSP because it's more expressive. In CSP, there is a global alldiff constraint, which requires all variables to take on different values from their domains. I have a set of alldiff constraints. However, out of this set, I only require at least one of them to be true. That is, not all of them have to be satisfied.

For concreteness, suppose we have 8 variables $x_1,\ldots,x_8$. Each take values from the domain $\{0,1,2\}$. We want to satisfy the following formula:

$$\text{alldiff}(x_1,x_2,x_3) \lor \text{alldiff}(x_1,x_6,x_7) \lor \text{alldiff}(x_4,x_5,x_6) \lor \text{alldiff}(x_3,x_4,x_8).$$

We are happy if at least one of the 4 alldiff clauses is satisfied, e.g., if $x_1=0$, $x_2=1$, and $x_3=2$, we are already happy.

But how is then modeled in SAT? Specifically, how do we write an alldiff constraint in SAT?

If you want to model an alldiff() constraint in SAT, there are several options.  Here are two different options you can try:

One way is to expand $\text{alldiff}(x_1,\dots,x_n)$ into $n(n-1)/2$ inequality constraints: $(x_1 \ne x_2) \land (x_1 \ne x_3) \land \cdots$.  Now you can express each inequality constraint $x_i \ne x_j$ on $b$-bit values in turn as a boolean formula: $(x_i[0] \ne x_j[0]) \lor (x_i[1] \ne x_j[1]) \lor \cdots$, where $x_i[k]$ is the $k$th bit of $x_i$.  In this way each alldiff constraint on $n$ $b$-bit variables expands into a boolean formula of size $\Theta(n^2 b)$.
Alternatively, a different way is to use a one-hot encoding.  Suppose each $x_i$ needs to take values from some universe $U$ of $u$ values.  Instead of encoding each $x_i$ as a $\lceil \lg u \rceil$-bit value, encode it as a $u$-bit boolean vector, where $x_i[k]=1$ if $x_i = k$ and $x_i[k]=0$ otherwise.  Now an alldiff constraint on $n$ variables amounts to requiring that there are exactly $n$ ones in the $nu$-bit vector obtained by concatenating the vectors for each of the $n$ variables in the alldiff constraint.  Thus, we obtain a $n$-out-of-$nu$ constraint.

This $n$-out-of-$nu$ constraint can be encoded in multiple ways; one way is to use a tree of half-adders  to sum up these values.  The tree will have $nu$ leaves, and with a $\lceil \lg nu \rceil$-bit output at the root.  You can find more about encoding cardinality constraints here: https://cs.stackexchange.com/a/6522/755.

These approaches give you a boolean formula, i.e., a boolean circuit; it's not in CNF form.  So, strictly speaking, it's not an instance of SAT.  However, there is a standard way to convert any such boolean formula to CNF form: you use the Tseitin transform (equivalently, you use the standard reduction from CircuitSAT to SAT) and then run a SAT solver on the result.  There are several SAT front-ends that will do this work for you; STP is one I have used that is quite convenient, but there are others as well.

This gives you at least options you could consider, for converting your problem to SAT.  Which one is most efficient might depend on your specific problem and the parameters of your problem (the size of the domain, the number of variables in each alldiff constraint).

Also, if you have a lot of alldiff constraints, it seems likely that a CSP solver might do better than a SAT solver.  CSP solvers are designed to handle alldiff constraints well, thus they might perform better than naively bitblasting to SAT, as SAT solvers won't be aware of that structure.

See also When to use SAT vs Constraint Satisfaction? and Converting (math) problems to SAT instances and https://cs.stackexchange.com/a/12153/755.


How to draw a parsing tree according to syntax diagram? I would really appreciate if someone can explain the syntax diagram itself and can help to build the parsing tree.

That diagram describes a language, a set of words over some alphabet.

Intuitively, this language contains all the words that can be obtained traveling over the diagram from the beginning (on the left) and following the arrows.

If we take the upper route, we build a word starting with $x$, then continuing with any string (or at least that's how I read that "String" box), and then ending with another $x$.

If we take the lower route, we form the word $x$, only.

To solve the exercise, you have to find a route which can generate the given string $xxyxx$. When doing so, you have to note down what parts of your string correspond to the nodes in the diagram (e.g. what correspond to the "String" box).

Note that this diagram is somewhat simple, in that it has no loops, so the parse tree is also simple. With loops, it could be more complex.

The last part of the exercise asks you to find a word which can not be generated following the diagram.


Is x86-64 is just an alias of EM64T? I was reading a book which describes a historical perspective:

Pentium 4E (2004, 125 M transistors). Added hyperthreading, a method to run two programs simultaneously on a single processor, as well as EM64T, Intel’s implementation of a 64-bit extension to IA32 developed by Advanced Micro Devices (AMD), which we refer to as x86-64

I'm a little bit confused here, here are my two questions:

Does it mean that 'x86-64' is just an alias of 'EM64T'?

Is IA32 developed by AMD? Isn't IA32 designed by Intel and first implemented in the 80386 microprocessor in 1985? See Wikipedia.

Q1-does it mean that x86-64 is just an alias name of EM64T?

The original name for the architecture is AMD64.
That is also the marketing name that AMD uses for that architecture.
When Intel licensed it from AMD, they first called the feature CT, then IA-32e, then EM64T, and most recently Intel 64. Those are Intel's marketing names. Note that Intel 64 contains extensions on top of AMD64 as well.
x64 is not an official name. It is a marketing name created by Microsoft in order to refer to both Intel's and AMD's (as well as other vendors') implementations without using the name of one of the two main competitors.
x86-64 is not an official name. It is a marketing name used by many vendors in order to refer to both Intel's and AMD's (as well as other vendors') implementations without using the name of one of the two main competitors.
x86_64 is the GNU Autotools architecture designation used in tools such as Autoconf, Automake, and GCC.
IA-32 is, I believe, a term that Intel only introduced after they started working on IA-64. Until then, the architecture was colloquially known as x86, but did not actually have a name.
The bottom line is that you can mostly use the terms AMD64, IA-32e, x86-64, and x64 interchangeably, and people will probably understand what you are talking about. But, the official name for the architecture is AMD64, but that can also refer to AMD's specific implementation of that architecture (which may have AMD-specific extensions). Whereas IA-32e is Intel's specific implementation of the AMD64 architecture, which may have Intel-specific extensions.

Q2- And is IA32 developed by AMD?

No, it isn't.

isn't IA32 designed by Intel and first implemented in the 80386 microprocessor in 1985?

Yes, it is, although the name IA-32 came later.


Search for specific element in sorted array Given sorted array $A[1..n]$. We want to find an element such that
$A[i]=3i+2$  in $O(\log n)$(binary search).

I trying to relate to problem finding element in sorted array $A$ such that $A[i]=i$, but i can't use that technique to solve mentioned problem. Any hint be appreciated.

Define $B[i] = (A[i]-2)/3$. Now you want to find an index $i$ such that $B[i] = i$.


Is it possible to prove Tarski's Undefinability theorem from Turing's Halting Problem? In the Wikipedia page for Turing's Halting problem, they mention that you can prove Gödel's First Incompleteness theorem from it. This is the relevant quote:

  Assume that we have a sound (and hence consistent) and complete
  axiomatization of all true first-order logic statements about natural
  numbers. Then we can build an algorithm that enumerates all these
  statements. This means that there is an algorithm N(n) that, given a
  natural number n, computes a true first-order logic statement about
  natural numbers, and that for all true statements, there is at least
  one n such that N(n) yields that statement. Now suppose we want to
  decide if the algorithm with representation a halts on input i. We
  know that this statement can be expressed with a first-order logic
  statement, say H(a, i). Since the axiomatization is complete it
  follows that either there is an n such that N(n) = H(a, i) or there is
  an n' such that N(n') = ¬ H(a, i). So if we iterate over all n until
  we either find H(a, i) or its negation, we will always halt, and
  furthermore, the answer it gives us will be true (by soundness). This
  means that this gives us an algorithm to decide the halting problem.
  Since we know that there cannot be such an algorithm, it follows that
  the assumption that there is a consistent and complete axiomatization
  of all true first-order logic statements about natural numbers must be
  false.

After reading this proof, I wondered if a very similar proof by contradiction could also prove Tarski's Undefinability theorem?

I was thinking of something along the following lines:

Imagine that a truth predicate isTrue($\ulcorner s \urcorner$) for any arbitrary logic sentence s were computable. In that case, this predicate would also be able to compute the truth status for any arbitrary H(a,i). Therefore, we would be able to compute isTrue($\ulcorner H(a,i) \urcorner$) for any possible H(a,i). Consequently, such isTrue($\ulcorner s \urcorner$) predicate would solve Turing's Halting problem, while we already know that it is fundamentally unsolvable. Therefore, such truth predicate is not computable.

Is there a flaw or a problem with this proof strategy?

The fact that the Wikipedia page mentions this proof strategy for Gödel's First Incompleteness but not for Tarski's Undefinability got me wondering. Maybe it does not work for Tarski after all? What's the catch?

As cody observed, the problem with that strategy is that definable relations need not be computable. For example, the Halting Problem is definable in $(\mathbb{N}; +,\times)$ (see Kleene's $T$-predicate).

That said, a relativized form of the incomputability of the Halting Problem, applied to iterates of the Turing jump, does do the job:

First, we show that for each $n$ and each $\Sigma_n$ formula $\varphi$ the set $\{x: \varphi(x)\}$ is computable from ${\bf 0^{(n)}}$, uniformly in $n$ and $\varphi$.
Next, we show that for each $n$ the set ${\bf 0^{(n)}}$ is itself definable by some $\Sigma_n$ formula $\psi_n$. This is an application of Kleene's $T$-predicate.
Now we're good to go. Suppose we had a $\Sigma_n$ formula $\varphi$ defining the set of (Godel numbers of) true sentences in the language of arithmetic. Then ${\bf 0^{(n)}}$ could compute ${\bf 0^{(n+1)}}$ as follows: given $k$, we ask ${\bf 0^{(n)}}$ whether $\varphi(\underline{\ulcorner\psi_{n+1}(\underline{k})\urcorner})$ holds. (Here "$\underline{i}$" denotes the numeral corresponding to the number $i$, and "$\ulcorner\theta\urcorner$" is the Godel number of $\theta$.)
But that gives ${\bf 0^{(n+1)}}=({\bf 0^{(n)}})'\le_T{\bf 0^{(n)}}$, a contradiction by the relativized unsolvability of the Halting Problem.


About the MNIST data-set Is this known as a fact or from some analysis that the MNIST data-set is almost as if its sampled from some low (~10?) dimensional manifold? Is there a locally linear embedding to a low-dimensional space?  Of course I don't expect the data will be exactly on some low dimensional manifold; there will be some noise.

The short answer is: I don't know.

Visualizations

There's been lots of work on visualizing the MNIST data set, in 2 dimensions, and even in 3 dimensions.

For instance, here's an embedding into 2D space using a neighbor embedding visualization technique (a highly nonlinear embedding):

Credit: Zhirong Yang, Jaakko Peltonen, and Samuel Kaski.  See their page on MNIST visualization.

However, the NE embedding is not linear.  It doesn't try to be a linear map from the image space ($\mathbb{R}^{768}$) to the plot ($\mathbb{R}^2$).  Rather, it tries to preserve the topology: it tries to make images that are nearby (e.g., in L2 metric) be near each other in the visualization.

See also this blog article for exploration of different ways of embedding MNIST into two or three dimensions, including both linear embeddings (e.g., PCA) and nonlinear embeddings.

Here's another visualization of doing PCA to 2 dimensions on MNIST:

Credit: taken from this nice blog post

One thing that is clear from those visualizations is that if you do PCA onto two or three dimensions, the result is not linearly separable.  It's not even close to linearly separable.

Even if you look at just two different digits and apply 2-dimensional PCA to project linearly onto the two principal components, the result is again not even close to linearly separable:

Credit: the same blog post

So at least 2 dimensions don't seem to be enough to distinguish 4's from 9's.

In contrast, PCA onto 2 dimensions does give you something that's pretty close to linearly separable: it's enough to distinguish some other pairs of digits pretty well with a linear classifier, but not perfectly -- to get best accuracy, you need more than a linear classifier and more than 2 dimensions.

Read the rest of that blog post to see what happens when you try to do a locally linear embedding to project all MNIST digits onto 2 dimensions.  You'll see that, while there are some commonalities, the result doesn't look good enough to get high accuracy.

A note of caution

We need to be careful about what you mean by "lay on a manifold".  Of course, if you consider all the ways to write a 7 (say), those 7's will all lie on some manifold in $\mathbb{R}^{768}$.  I doubt that manifold is going to be a linear subspace (i.e., a hyperplane).

If you allow arbitrarily nonlinear manifolds, it's not clear that it is useful or meaningful to ask what is the dimension of this manifold.  For instance, consider a mapping that maps each digit to $\mathbb{R}$ (1 dimension), e.g., all 0 digits get mapped to 0, all 1 digits get mapped to 1, all 2 digits get mapped to 2, and so on.  This is clearly possible in principle, but the mapping is extremely nonlinear.  Would you consider this evidence that the digits lie on a 1-dimensional manifold?  Probably not.  This highlights the challenge in making our intuition more precise.

So you need to make sure you are asking the right question.

Measuring dimensionality by learning

One way to think about this is to look for an embedding $f:\mathbb{R}^{768} \to \mathbb{R}^d$ into some lower-dimensional space ($d$-dimensional space), with the two properties that:

The embedding $f$ is "nice" in some fashion -- it need not be linear, but hopefully it is continuous or locally linear or something like that.
Enough information is preserved that we can still classify which digit it is, based on the result of the embedding.  In other words, given an image $x$ of an image, we should be able to tell which image it is given only $f(x)$: the result $f(x)$ of the embedding should be enough for a classifier to tell which digit it is, with about as high accuracy as would be possible given the original image.

People have studied this.  For instance, people have built autoencoders, which are basically a way to use a deep neural network to build an embedding $f$ such that you can still reconstruct the image with reasonable accuracy.  You can train an autoencoder on the MNIST digits to build an embedding $f$ that maps to a lower-dimensional space, then train a classifier that tries to label the digits based on the result of the embedding.  The following paper looks at one approach to that, on the MNIST data set:

Wei Wang, Yan Huang, Yizhou Wang, Liang Wang.  Generalized Autoencoder: A Neural Network Framework for Dimensionality Reduction.  IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp.490--497.

They build autoencoders that map to a 30-dimensional data space, and where a simple classifier achieve an error rate of 4-5%.  For MNIST, 4-5% error rate is very high: the state of the art is an error rate of 0.5% or so, when training a classifier on the original images.  So this means that, as far as we know, if you try to map down to 30 dimensions, a lot of information is still preserved, but a significant amount is lost: you lose enough information that the classifier's error rate increases by an order of magnitude.

In short, 30 dimensions doesn't seem to be enough, at least for an embedding built in this way.

The other caveat is that the embeddings built in this way use a multi-linear neural network, and thus might still be fairly nonlinear.  If you demand a particularly "smooth"/"nice" embedding, this result might not be relevant.


Is this book's definition of phrase correct? I am fairly confident that my textbook (Concepts of Programming Languages 11th
edition, international edition, Robert Sebesta) has an error in its definition
of what a phrase is in the section on bottom-up parsers. After an infuriating
conversation with the professor using that textbook in which I was told that the
book's definition was correct, but was given no reason why or why my reasoning
was incorrect, I still think it has an error. I haven't been able to find any
information about errata in the book online (not the main point of the question,
but I'd like to find that also).

Here is the book's definition:

$\beta$ is a phrase of the right sentential form $\gamma$ if and only if $S \Rightarrow^{*}\gamma = \alpha_1A\alpha_2\Rightarrow^{+}\alpha_1\beta\alpha_2$.

Here is what I think the definition should be:

$\beta$ is a phrase of the right sentential form $\gamma$ if and only if $S \Rightarrow^{*}\alpha_1A\alpha_2\Rightarrow^{+}\alpha_1\beta\alpha_2 = \gamma$

Here is my reasoning: Definitions are mostly arbitrary, so I can't really prove
that it's "wrong" without comparing it with a bunch of other books out there (I
just have the one, so if those of you with more could check that for me, that'd
be great. I can't seem to find any definitions online). But I can prove that
it's not consistent with the rest of the book.

The book states that simple phrases are a subset of phrases, that the handle of
any rightmost sentential form is its leftmost simple phrase, and that in this
example grammar

$\begin{align}
E &\to E + T \mid T\\
T &\to T * F \mid F\\
F &\to (E) \mid id
\end{align}
$

the handle of the sentence "id + id * id" is the first id. Observe that
according to the book's definition of phrase, a sentential form consisting
entirely of terminals can have no phrases, because the sentential form is never
of the form $\alpha_1{}A\alpha_2$. This means that there are also no simple
phrases of sentential forms consisting entirely of terminals. This means that
there are also no handles of sentential forms consisting entirely of
terminals. This means that there are no handles in "id + id * id", despite them
saying there are. So the definition isn't consistent with what else they
say. Based on what I've read elsewhere and heard in class, the definition seems
wrong, not the other parts.

Is my reasoning sound? Is the definition of phrase correct / what is the "correct" definition of phrase?

(apologies if I left out anything essential, I lost the first draft when I got to the captcha requirement and filled it out with spyblock enabled)

To be a phrase is to be reducible to a single non-terminal. What you call a definition of phrase is actually the definition of what it is to be a phrase of a sentential form.

$\beta$ is a phrase of $\alpha_{1}A\alpha_{2}$, because it will be reduced to $A$. There are (obviously) phrases in sentential forms consisting entirely of terminals, i.e., sequences of symbols that will be reduced to a single non-terminal. They are not phrases of that sentential form, though.

A handle is the simple phrase of the sentential form that will be the result of the reduction to be made immediately, at some point. $\beta$ exists as a phrase, because it will be reduced to $A$. A bottom-up parser will usually reduce first its leftmost simple phrase, which will then be the handle of the resulting sentential form.

Definitions are not arbitrary, they serve a purpose.


Guided Backpropagation in Deep Neural Networks I am reading about a method called guided backpropagation.
https://ramprs.github.io/2017/01/21/Grad-CAM-Making-Off-the-Shelf-Deep-Models-Transparent-through-Visual-Explanations.html#deconv-and-guided-backprop.

As shown in the figure below, you essentially compute the derivates of the output with respect to the input image while zero-ing out negative gradients along the way. The website mentions

  Negative gradients at a particular ReLU neuron, state that this neuron
  has a negative influence on the class that we are trying to visualize.

  During backpropagation there are paths that have positive influence
  and some that have negative influence, and these end up cancelling out
  in a weird interference pattern, causing gradients to seem noisy.
  Whereas in Guided Backpropagation, we only keep paths that lead to
  positive influence on the class score, and supress the ones that have
  negative influence, leading to much cleaner looking images.

My question is why does the resulting image have pixels which are negative? Don't negative pixels indicate that the gradient of the output with respect to the pixel is negative? I.e. that pixel has a negative influence on the class score?

Guided backpropagation from the model output to the input of the first ReLU indeed results in non-negative values (as the gradient from ReLU output wrt. ReLU input is set to zero if it is negative). From the input of the first ReLU the gradient wrt. the input pixels can however become negative. Input images are mostly scaled to the range [-1,1] (e.g. by division by 127.5 and subtraction of 1 for Keras' pretrained models - that means roughly achieving zero mean and unit variance). If a negative input (pixel that is darker than the mean) contributes positively - via negative weights - to the output of the first convolutional layer the gradient for that pixel is negative. As negative gradients are only set to zero in guided backprop when passing through a ReLU and there is no ReLU between the input of the first ReLU and the overall input, guided backprop can result in negative values.


What determines the entropy of a program's source code? a few days ago I asked a question about the limits of compression:
Can PRNGs be used to magically compress-stuff?

The idea common to all the answers was that if you consider all programs
of length < k (Let's call this set $C_k$), then there is only a finite number of possible outputs generated by programs in $C_k$ (let's call that set $S_k$).

In the comments, I asked a followup question roughly equivalent to  "what determines which messages are possible outputs?" and have been thinking about this ever since.

It seemes clear that what determines that is the program that executes
the program. If we ignore TM's and think in terms of source code, then
the output of a piece of code depends only on the syntax and semantics
of the programming language. So the language design determines
the contents of $S_k$. There are some interesting corollaries:

All program transformations that do no affect the AST nor enlarge the program beyond k bits will produce programs that generate the same output.
All refactorings, which might alter the AST but preserve all input/output
relationships, will do the same if they do not inflate the size of the source code.
a PL that provides multiple constructs ("There's more then one way to do it")
for achieving the same result (control flow constructs, for example) will , generally speaking, have more programs of length < k which generate the same output and so a smaller $S_k$ then a similar but "slimmer" PL.

This brings me to the following question: If I consider all programs
in $C_k$ that generate the same output (it's an equivalence relation)
and then proceed to compress them, what would be the results? Would
the equivalent programs compress down to roughly the same size or not?
Does the compressability depend on the meaning of the program (which
is identical) or the bit sequence (which is not)?

A statement given in the answers to the previous question is
that the entropy of a bit sequence determines how compressible it is.
Is that entropy determined by the input/output relationships encoded
in the program, or by it's bit-representation in language X?
What's the right way to think of this?

update
Since a program describes a computational process
rather then merely output, the notion of equivalence
suggested really doesn't indicate me much about
the relative complexity of programs which are equivalent
by that definition.

This is a classical question in the foundations of Kolmogorov complexity: does the programming language matter for the sake of defining minimal description length? It depends on your model, but in general the answer is "no" or "almost no".

Suppose that $P_1,P_2$ are two Turing complete programming languages. In particular, in $P_1$ you can write an interpreter $I$ for $P_2$. Therefore any program $\pi$ written in $P_2$ can be converted in $P_1$ by pasting together $I$ and $\pi$. What is the length of the combined program? In any reasonable programming language, it is $O(|\pi|)$, and so different programming languages only have at most a constant multiplicative advantage over each other. If we are more stringent in our requirements on the programming languages, the answer should be $|\pi| + O(1)$, which is what happens in Kolmogorov complexity. In this case different programming languages only have at most a constant additive advantage over each other.

The idea behind $\pi + O(1)$ is that you should be able to concatenate the code for $I$ with $\pi$. But in practice this is not quite possible. Suppose for example that $P_1$ is $C$. We need to write $\pi$ as a string. If the character set of $\pi$ includes backslash or double quotes, then we will need to escape these, which could result in a multiplicative blow-up. Still, we get a $C$ program whose length is $O(|\pi|)$. If we are careful in our definitions then we can prevent this — check any introductory text on Kolmogorov complexity for the details.


How to sort using $\texttt{SQRTSORT}$ as a subroutine which sorts $\sqrt{n}$ of consecutive elements? I am teaching myself algorithms with the online lecture notes by Jeff Erickson and fails to solve the following problem (Problem 21 of Lecture 1).

  (a) Describe an algorithm that sorts an input array $A[1 \ldots n]$ by calling a subroutine $\texttt{SQRTSORT}(k)$, which sorts the subarray $A[k + 1 \ldots k + \sqrt{n}]$ in place, given an arbitrary integer $k$ between $0$ and $n - \sqrt{n}$. How many times does your algorithm call $\texttt{SQRTSORT}$ in the worst case?

Note: To simplify the problem, assume that $\sqrt{n}$ is an integer. Your algorithm is only allowed to inspect or modify the input array by calling $\texttt{SQRTSORT}$; in particular, your algorithm must not directly compare, move, or copy array elements.

  (b) Prove that your algorithm from part (a) is optimal up to constant factors. In other words, if $f(n)$ is the number of times your algorithm calls $\texttt{SQRTSORT}$, prove that no algorithm can sort using $o(f(n))$ calls to $\texttt{SQRTSORT}$.

and,

  (c) Now suppose $\texttt{SQRTSORT}$ is implemented recursively, by calling your sorting algorithm from part (a). For example, at the second level of recursion, the algorithm is sorting arrays roughly of size $n^{\frac{1}{4}}$. What is the worst-case running time of the resulting sorting algorithm?

Note: To simplify the analysis, assume that the array size $n$ has the form $2^{2^{k}}$, so that repeated square roots are always integers.

My Attempt:

For part (a), I come up with a probably brute-force algorithm behaving like the $\texttt{BubbleSort}$, except that it treats $\frac{\sqrt{n}}{2}$ of consecutive elements as a single one in $\texttt{BubbleSort}$. The number of calls of $\texttt{SQRTSORT}$ is at worst:

$$1 + 2 + \ldots + 2 \sqrt{n} = 2n + \sqrt{n} = \Theta(n)$$

For part (b), $\sqrt{n}$ is a trivial lower bound: Any reasonable algorithm must have done something on each element, consuming $\sqrt{n}$ calls of $\texttt{SQRTSORT}$.

My Questions:

  How to show whether my solution is asymptotically optimal or not?
  Do you have better algorithms with lower complexity, say, $\sqrt{n} \lg n$ or $n^{\frac{3}{4}}$. Actually, I am looking for the optimal one.

Hint for part (b): Consider the statistic $r(\pi) = \sum_i |i-\pi(i)|$. Running SQRTSORT can reduce $r(\pi)$ by at most $n$, while $r(n(n-1)\ldots1) = \Omega(n^2)$.

Hint for part (c): I get a running time of $O(n^2\log^{O(1)} n)$.


Shortest path from source to destination in directed acyclic graph There is an approach given in this article Shortest Path in Directed Acyclic Graph to find the shortest path in O(V+E) using topological sort.

I have another approach which I think is more efficient. If use dynamic programming to store the minimum distance from a vertex to a destination than I don't need to explore that node again. Now, time complexity of this solution would be O(V+E) if I am using top to bottom approach (bottom to top approach would be O(V^2).

The advantage of this method is I don't have to find topological order first to find the minimum distance, I can find it directly.

The only disadvantage I can see of this method is, If the depth of my recursion tree is large, then I can run out of stack space and I have to use bottom to top approach. Now, if I have a sparse graph (E=O(V)), time complexity using this method would be O(V^2) but using topological sort method would be O(V) and I can use kahn's algorithm to find topological sort which is done iteratively so running out of stack space wouldn't be an issue.

Is there anything wrong in whatever I have written above?

If your algorithm runs in $O(V+E)$ time, and their algorithm runs in $O(V+E)$ time, I don't see any basis for calling your approach more efficient.  At least, asymptotic running time does not seem precise enough to determine which will be more efficient in practice.


What is the global function we are trying to Optimise with Clustering Algorithms? I am doing some reading (and implementation) of some Clustering Algorithms.

First I started with the well known K-Mean algorithm and implemented it directly from a paper.
Got a kind of decent understanding of what I going on there.

What I am actually interested in is Particle Swarm Optimisation based clustering.

For Particle Swarm Optimisation, you need to have a global fitness function that will (in this case) tell you how well clusters this is.

The general notion of well clustered I have found is that each cluster is compact.
But how to express this mathematically?

I thought that we would go though each cluster and check its positional variance (away from its centroid).

For some cluster C
 :

$$\mu(C)=\dfrac{1}{|C|}\sum_{\forall\tilde{x}\in C}\tilde{x}$$

$$\sigma^{2}(C)=\sum_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

No point converting to standard deviation, unless using a gradient based optimization approach, which PSO is not.

then the global fitness would be to minimize the average variance, which is proportional to minimizing the total variance since we have a fixed number of clusters.

if $S$ is the set of all clusters the we are to minimise some function $g$.

$g_{mine}(S)=\sum_{\forall C\in S}\sigma^{2}(C)$

ie  $$g_{mine}(S)=\sum_{\forall C\in S}\sum_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

According to Chen, C.-Y. & Ye, F. Particle swarm optimization algorithm and its application to clustering analysis Networking, Sensing and Control, 2004 IEEE International Conference on, 2004, 2, 789-794

Equation 7 (Rewritten to use my notation)

$$g_{chen}(S)=\sum_{\forall C\in S}\sum_{\forall\tilde{x}\in X}(\tilde{x}-\mu(C))
 $$

The difference from what I had is the $\forall\tilde{x}\in X$, for $X$ the whole spaceof data rather than $\forall\tilde{x}\in C$.

This is what got me wondering if I was correct in the first place.
as it can be seen that $g_{mine}\ne g_{chen}$. It can't since the extra points are going to change it and will not cancel since all variances are positive.
However they are equivalent if $\forall S, S'$ $g_{mine}(S)\ge g_{mine}(S') \iff g_{chen}(S)\ge g_{chen}(S')$

In:
 Ahmadyfard, A. & Modares, H. Combining PSO and k-means to enhance data clustering Telecommunications, 2008. IST 2008. International Symposium on, 2008, 688-691

Equation 6 has: (again with notation switched)

$$g_{ahmadfard}(S)=\dfrac{1}{|X|} \sum_{\forall C\in S}\sum_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

This is equivalent to mine (at least in proportionality) as:  $|X| \times g_{ahmadfard}(S) = g_{mine}$, and since $|X|>0$ thus $\forall S, S'$ $g_{mine}(S)\ge g_{mine}(S') \iff g_{ahmadfard}(S)\ge g_{ahmadfard}(S')$

Ye and Chen also came up with another function in:
Ye, Fun, and Ching-Yi Chen. "Alternative KPSO-clustering algorithm." Tamkang Journal of science and Engineering 8.2 (2005): 165.
It is very complicated and beyond the scope of this question

What are the pros and cons of $g_{chen}$ vs $g_{mine}$ vs $g_{ahmadfard}$ ?

About your first, general question: generally, the cost function we want to optimize in clustering algorithms is double: we want to both minimize intra-class variance while maximizing extra-class variance. Replace class by cluster and you understand easily what it means: inside a cluster, we want the elements to be as similar as possible, while elements between different clusters must be as dissimilar as possible. The basic idea is very simple and natural.

Different algorithms will only tweak the way they measure this intra-class similarity and the extra-class dissimilarity, usually in the goal to optimize for a particular kind of dataset with known properties.

About the second, more specific question: I did not read those papers, but from a first look, it seems gchen is using L1-norm (absolute value measure) while gmine is using L2-norm (euclidian measure). gahmadfard seems to only be the L2-norm plus feature scaling or some kind of tf-idf (anyway what is certain is that they are pondering the similarity measure with the number of elements in the group, but I don't know for what purpose).

I can't advise when to use which clustering algorithm, you should read the intro of the papers or find a survey, but usually the best way to find the best clustering algorithm for you is to try several on your dataset and manually select which one fits the best your purpose (since there's no objective way to find which clustering is the best, it all depends on your subjective needs, after all, clustering algorithms belong to the class of unsupervised learning).


Proof that an almost complete binary tree with n nodes has at least $\frac{n}{2}$ leaf nodes I'm having some trouble proving what my title states. Some textbooks refer to almost complete binary trees as complete, so to make myself clear, when I say almost complete binary tree I mean a binary tree whose levels are all full except for the last one in which all the nodes are as far left as possible.

I thought of proving it using induction but I'm not really sure how to do so. Any ideas?

UPDATE

Well I made somewhat of a progress but I also got a somewhat different result, here's what I did:

Let $T$ be an almost complete tree of height $h$ meaning that in the level of height $h$ there should be at least 1 node. Considering the fact that every height has double the number of nodes of the previous level we can derive that $T$ has the least possible number of nodes in the case that at $h$-level there is only one node. (1)

In that case the number of leaf nodes is

$l=2^{h-1}-1+1 \Rightarrow l=2^{h-1}$ and the number of total nodes is

$n=2^{h-1}-1+1$

$\Rightarrow l=2^{h-1}=\frac{2(2^{h-1}+1)}{2}=\frac{n+1}{2}$

$\xrightarrow{(1)(2)} l \geq\frac{n+1}{2}$

Now, I'm getting a bit closer but not really there yet. First problem is that I got $l \geq \frac{n+1}{2}$ and not $l \geq \frac{n}{2}$ which from what I understand stands only in the specific case that $h=1$. Second problem is that this doesn't seem like a formal proof... Any tips/suggestions?

According to this Wikipedia page:

  In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between $1$ and $2^h$ nodes at the last level $h$. An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some authors use the term complete to refer instead to a perfect binary tree as defined below, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree...

So, you are talking about a binary tree with $h$ levels, for which all levels  with numbers $k \in [0,h-1]$ are completely filled up (i.e. have $2^k$ nodes), and the level $h$ is potentially incomplete - it contains $(2^h-r)$ nodes, where $r \in [0, 2^h-1]$ is the number of (rightmost) removed nodes. Total number of nodes of such tree is $(2^{h+1}-r-1)$. Let's find the number of leaves for this tree.

If $r$ is even, then the removal of $r$ nodes on the level $h$ will give you $\frac{r}{2}$ new leaves. So, the total number $l_{even}$ of leaves will be:

$$l_{even}=2^h - r + \frac{r}{2} = 2^h - \frac{r}{2}$$

if $r$ is odd, then the removal of $r$ nodes on the level $h$ will give you $\frac{r+1}{2}$ new leaves. So, the total number $l_{odd}$ of leaves will be:

$$l_{odd}=2^h-r+\frac{r+1}{2}=2^h-\frac{r-1}{2}$$

Now you'll be able to verify, that in both cases:

$$l \ge \frac{2^{h+1}-r-1}{2}$$


Finding the longest path in an undirected node-weighted tree I have a tree where each node is assigned a weight (a real number that can be positive or negative). I need an algorithm to find a simple path of maximum total weight (that is, a simple path where the sum of the weights of the nodes in the path is maximum). There's no restriction on what node the path starts or ends.

I have a possible algorithm, but I am not sure it works and I am looking for a proof. Here it is:

1)Select an arbitrary node u and run DFS(u) to find the maximum weight simple path that starts at u. Let (u, v) be this path.

2)Run DFS(v) to find the maximum weight simple path that starts at v. Let this path be (v, z).

Then (v, z) is a simple path of maximum weight. This algorithm is linear in the size of the graph. Can anyone tell me if it works, and if so, give a proof?

Note: The Longest Path Problem is NP-Hard for a general graph with cycles. However, I only consider trees here.

No, your algorithm does not work sometimes.

Here is a counterexample. Let graph $G$ have five weighted nodes, $A\mapsto 1$, $B\mapsto -1$, $C\mapsto 0$, $D\mapsto 1$, $E\mapsto 1$. There are four edges, $AB$, $BC$, $CD$ and $CE$.

Let us run your algorithm.

Select node $B$ and run DFS($A$). We may get the maximum weight simple path $B, A$, whose weight is 0.
Run DFS($A$), we may find the maximum weight simple path that starts at $A$, which is $A, B, C, D$, whose weight is 1. That path is returned.

However, the simple path with the maximum weight is actually $D,C,E$ whose weight is $2$.