How to intuitively come up with an example for an ambiguous grammar and how to make that grammar unambiguous? I don't get how to intuitively come up with an example for an ambiguous grammar.

Let's take as an example this grammar:

Declaration ::= Type D ;
         Type ::= "int" | "char"
         D ::= "*" D
            |  D "[" number "]"
            |  D "(" Type ")"
            |  "(" D ")"
            |  name

I am told outright that this grammar is ambiguous. What is expected of me is to find one example that proves that it is. What I'm interested is what is the thought process that allows you to find an example. Our teacher just gave us one example that would show that we would obtain two different derivation tree like:

int *foo[5];  has two derivation tree

            Declaration              Declaration
             /    |   \               /    |   \
           Type   D    ;            Type   D    ;
            |    / \                 |    / \____
           int  *   D               int  /   \ \ \
                   / \____              D    [ 5 ]
                  /   \ \ \            / \
                 D    [ 5 ]           *   D
                 |                        |
                foo                      foo

However I have no idea how he thought to himself that int*foo[5] would be the example before doing the trees. It all boils down to how they did it without trial and error?

How to make that grammar unambiguous?
I was also given the task to make the above grammar unambiguous. However I don't know yet again what is the intuition behind making it unambiguous.

They gave us this solution:

 Declaration ::= Type D ;
       Type ::= "int" | "char"
       D ::= "*" D
          |  "(" D ")" D'
          |  name D'
       D' ::= "[" number "]" D'
           |  "(" Type ")" D'
           |  empty               <== empty string

There must be a pattern in all of this. What it is? What is the general method to solve this type of problem regardless of which grammar is given?

The simple way of seeing this class of ambiguities is to observe that if two right-hand sides for the same non-terminal overlap, then they could be applied in either order:

 D ::=     "*" D
    |          D "[" number "]"

The overlap is pretty clear:

 "*" D "[" number "]"

Another example, where a right-hand side can overlap with itself:

E ::= E "+" E

Overlap:

      E "*" E
            E "*" E
      -------------
      E "*" E "*" E

The solution is to remove the overlap by introducing a new non-terminal for one of the overlapping uses. Here's my solution to the ambiguity in your grammar:

Declaration ::= Type D ;
Type ::= "int" | "char"
D ::= "*" D
   E
E ::= E "[" number "]
   |  E "(" Type ")"
   |  "(" D ")"
   |  name

Which productions you decide to shift to the new non-terminal is not arbitrary; it will define which of the competing parses is correct for the language you are designing. There is no universal answer to that question, so it cannot be done algorithmically.

Note: The clumsy solution you have been provided with is probably because your lesson is being mixed with a discussion of top-down parsing. My grammar, though unambiguous, is not suitable for top-down parsing because it is left-recursive. However, the resulting parse tree reflects the syntactic structure of the declaration.


Generally, does the time it takes to compute (n mod m) depend on the size of n? Example:
Suppose I have a number a with 100 decimal digits, b with 200 decimal digits, and m with 10 decimal digits.

Would the speed of the computation a mod m vary greatly from b mod m because of the size of a vs b?

Yes. You are doing long division. Whatever method you use, you will lose you a roughly constant number of digits per step, so there will be twice as many (well, about $\frac{190}{90}$ times as many) steps for $b$ as for $a$.


prove that minimal number of comparisons to find median among five elements is 5 I would like to prove that we need at least five comparisons to find median amoung five numbers.

And my proposition:
Let's consider tree of comparisons. There are at least $5 \cdot {4\choose 2} = 30$  possiblities, so in our tree we have at least $30$ leaves. So what is minimal height of this tree when we have at least $30$ leaves. (height is number of comparisons).
So $$height \ge \log_2(30) > 4$$
Hence, $height \ge 5$.

Is it correct proof ?

Your proof is correct. But I don't think 5 comparisons is achievable.
Here is the algorithm that finds the median in 6 comparisons.

Sort the first two pairs. [ 2 comparisons]
Order the pairs w.r.t. their respective larger element. [ 1 comparison]

Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$.
Now there are 3 elements less than $d$, hence $d$ can't be the median( i.e. $3^{rd}$element of the sorted array)
WLOG say $c<e$ and $a<b$ (known already). Order the pairs w.r.t. their respective larger element. WLOG $a<b<e$ and $c<e$. Compare $c$ & $b$, greater one is the median.
[ 3 comparisons - 1 for $c$ & $e$, 1 for ordering the pairs and  1 for $b$ & $c$ ]

Hence, total number of comparisons is equal to 6.

Idea taken from here .


Solving recurrences by substitution method: why can I introduce new constants? I am solving an exercise from the book of Cormen et al. (Introduction To Algorithms). The task is:

  Show that solution of $T(n) = T(\lceil n/2\rceil) + 1$ is $O(\lg n)$

So, by big-O definition I need to prove that, for some $c$,

$$T(n) \le c\lg n\,.$$

My take on it was:
$$\begin{align*}
    T(n) &\leq c\lg(\lceil n/2\rceil) + 1 \\
         &< c\lg(n/2 + 1) + 1 \\
         &= c\lg(n+2) - c + 1\,.
\end{align*}$$
As this doesn't seem satisfactory I looked up a solution and the author after getting to the same stage as me decided to introduce a new arbitrary constant $d$:
$$\begin{align*}
    T(n) &\le c\lg(\lceil n/2-d\rceil) + 1 \\
         &< c\lg(n/2+1-d) + 1 \\
         &< c\lg((n-2d+2)/2) + 1 \\
         &= c\lg(n-2d+2) - c + 1 \\
         &= c\lg(n-d-(d-2)) - c + 1\,.
\end{align*}$$

And now, for $d \ge 2$, $c \ge 1$ and $n > d$,

$$c\lg(n-d-(d-2)) - c + 1 \le c\lg(n-d)\,.$$

What I don't understand is how does it prove that $T(n) \le c\lg n$? Cormen et al. make a big point that you have to prove the exact form of the inductive hypothesis which in this case was $T(n) \le c\lg n$. They then go on to show example similar to one above.

How is that the exact form of the inductive hypothesis? This doesn't seem to fit the big-O definition. When can I omit constants or cheat them away? When is it wrong?

I am guessing that the book wants you to proof the stronger hypothesis $T(n) \leq c\log( n -d)$ which implies $T(n) \leq c log(n)$ is also true ( because $n \geq n -d$ for $d\geq 0$. )


System restarted before transaction is committed Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest.

T1 start
T1 B old=1200 new=10000
T1 M old=0 new=2000
T1 commit
T2 start
T2 B old=10000 new=10500
T2 commit

Suppose the database system crashes just before log record 7 is written. When  the system is restarted, which one statement is true of the recovery procedure?

(a) We must redo log record 6 to set B to 10500

(b) We must undo log record 6 to set B to 10000 and then redo log records 2  and 3

(c) We need not redo log records 2 and 3 because transaction T1 has committed

(d) We can apply redo and undo operations in arbitrary order because they are idempotent

According to me, the answer should be (a), as transaction T1 has been committed and has been written back into memory. But my solution says that the answer should be (b).

Am I right or what am I doing wrong?

Thanks in advance!

The correct answer is (b) under the assumption that the recovery algorithm used is the undo-redo algorithm, which is one of the most commonly used, and which can be used if the DBMS adopts both the immediate update policy and the immediate commit policy (instead of the deferred update and the deferred commit policies).

The immediate update policy allows that updated pages can be written to the database before the transaction has committed; The immediate commit policy allows the commit record to be written to the log before all updated pages have been written to the database. Those policies require the use of Write Ahead Log (WAL) rule (write the updates to the log file before writing to disk) and of Commit rule (the after-images of the updates are written to the log file before the commit of the transaction).

Under this hypothesis, when a failure occurs, the recovery algorithm must undo all the transactions non committed, and redo all the transaction committed, going back in the log file until a checkpoint record is found or until the beginning of the log file.

So, the correct answer is (b) since also T1 must be redone. In fact, we do not know if its updates to the database have been written or not (as I said, assuming that we are in the case of immediate commit policy).


My algorithm is different from CLRS' -- is it wrong? Exercise 2.3-7 from "Introduction to Algorithms" by Cormen et al. Third Edition, states:

Describe a O(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether of not there exist two elements in S whose sum is exactly x.

At first, I had no idea how to solve it since I thought you couldn't access elements of a set by index, but assuming you could, here was my solution:
First off, we sort the set S, and then for every element y in S, we search if x - y exists in S. If x - y exists then we are done, otherwise continue the process until we have looked at all elements in S.
Since we sort at the beginning it's O(n log n) and then we perform a binary search for every element, so total cost would be O(n log n) + O(n log n), therefore O(n log n).
But the solution they give in the Lecture Notes is:

The following algorithm solves the problem:

Sort the elements in S.
Form the set S'= {z : z = x − y for some y ∈ S}.
Sort the elements in S'.
If any value in S appears more than once, remove all but one instance.  Do the same for S'.
Merge the two sorted sets S and S'.
There exist two elements in S whose sum is exactly x if and only if the same value appears in consecutive positions in the merged output.

And they go on to say:

Steps 1 and 3 require O(n lg n) steps. Steps 2, 4, 5, and 6 require O(n) steps. Thus the overall running time is O(n lg n).

So obviously they assume a set is just a regular array (you can access elements by index and the elements don't have to be unique). (And just to clarify my assumption, from the beginning of the book up to this point, they haven't put forth their definition of set, so it was easy to assume they were referring to an actual set).
It seems to me that even though their solution is O(n log n), my solution not only does it reduce the "hidden costs" greatly, it's also much more straightforward than theirs.
(To account for the possibility of repeated elements, nothing needs to be modified since the current y is not inside the searching subarray)
I've checked the published erratas (I know it wouldn't be a mistake per se anyway, but I thought it might've said something there), and there is nothing. So my question is: why is my solution wrong? Is my algorithm incorrect or is it my analysis?

You are right, there is a assuption that the set is available as an unsorted array, but I think that most set representations will allow you to obtain all elements in linear time. I also agree with you that your solution is straightforward, and uses no funny tricks.

I guess their solution is to impress you that only sorting and merging is needed, no such complicated things as binary search. (insert smiley here.) Perhaps binary search was not yet introduced at that point?

To illustrate the point Raphael makes — there are infinitely many implementations — here is mine. I believe it is correct, and uses only one sort, and a linear pass over the array. So: sort the array (from small to large). To check whether $y,z\in S$ exist such that $y+z=x$ move over the array from both sides. If the sum of the two elements of the array is larger than $x$ move the larger element one down, if it is less than $x$ move the smaller element one up. (How does this compare to your proposal?)

Nevertheless I would not consider their solution as incorrect. I like to think that it is good to have several solutions available. In some circumstances one implementation may outperform another. E.g., if the set was to be given as a sorted linked list, your solution would be hard to implement. (And mine only works if the list is doubly linked.)


Why is the Boolean hierarchy contained in the class $P^{NP}$? My textbook says: "The Boolean hierarchy is contained in the class $P^{NP}\subseteq\Sigma^P_2\cap\Pi^P_2$." However, it provides neither a proof nor a proof sketch nor some hint. How can I convince myself that the claim is true?

Every language in the Boolean hierarchy can be written as a "Boolean formula" whose "variables" are languages in NP, e.g.
$$ \overline{(L_1 \cap L_2) \cup L_3}. $$
Given an oracle to NP (i.e., an oracle to some NP-complete problem) and an input $x$, we can decide in polytime whether $x \in L_1$, $x \in L_2$, $x \in L_3$. We need polytime since NP-completeness is defined with respect to polynomial time reductions. Given the values of the "variables", it is easy to compute the "formula".


Searching for multiple partial phrases so that one original phrase can not match multiple search phrases Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases:

index      phrase
-----------------------------------------
0          Stack Overflow
1          Math Overflow
2          Super User
3          Webmasters
4          Electrical Engineering
5          Programming Jokes
6          Programming Puzzles
7          Geographic Information Systems

The expected behaviour is:

query         result
------------------------------------------------------------------------
s             Stack Overflow, Super User, Geographic Information Systems
web           Webmasters
over          Stack Overflow, Math Overflow
super u       Super User
user s        Super User
e e           Electrical Engineering
p             Programming Jokes, Programming Puzzles
p p           Programming Puzzles

To implement this behaviour I used a trie. Every node in the trie has an array of indices (empty initially).

To insert a phrase to the trie, I first break it to words. For example, Programming Puzzles has index = 6. Therefore, I add 6 to all the following nodes:

p
pr
pro
prog
progr
progra
program
programm
programmi
programmin
programming
pu
puz
puzz
puzzl
puzzle
puzzles

The problem is, when I search for the query prog p, I first get a list of indices for prog which is [5, 6]. Then, I get a list of indices for p which is [5, 6] as well. Finally, I calculate the intersection between the two, and return the result [5, 6], which is obviously wrong (should be [6]).

How would you fix this?

Let's fix some names. Let $q_1, \dots, q_k$ be the query strings and $w_1, \dots, w_n$ the existing phrases. Denote with $w_{i,1}, \dots, w_{i,k_i}$ the words contained in phrase $w_i$, and with $a \sqsubseteq b$ the relation "$a$ is a prefix of $b$".

Currently, you have implemented to obtain this:

$\qquad\displaystyle \{ i \in [1..n] \mid \forall j \in [1..k]\ \exists j' \in [1..k_i].\ q_j \sqsubseteq w_{i,j'}\}$.

Note how the $\exists$-operator does not preclude the same $j'$ for multiple $j$, and that's your problem (as far as I can tell). What you want is

$\qquad\displaystyle \{ i \in [1..n] \mid \exists J = \{j_1, \dots, j_k\} \subseteq [1..k_i]\ \forall j \in [1..k].\ q_j \sqsubseteq w_{i,j_j}\}$.

One way to implement this is to go with the double-indexing I used to describe the problem formally: each node gets the set of labels $(i,j)$ if its corresponding string is a prefix of $w_{i,j}$. Now, $i$ is a match if

every $q_l$ leads to a node with label $(i,\_)$ and
the second components of these labels are pairwise distinct (if there are multiple $(i,\_)$ for a single $q_l$, one has to check if there is a choice fulfilling the condition).

In your example, instead of just adding 6 to all these nodes you list, you'd add (5,1) and (6,1) to the prefixes of programming, and (6,2) to those of puzzles. Now, prog p gives you (5,1), (6,1) for prog and (5,1), (6,1), (6,2) for p; you can exclude 5 because it has the same second component for both query phrases whereas 6 has a "valid" match with (6,1) and (6,2).


Is there a name of this problem? There is $n$ lists (of integers) of the same length.
I want to find the zeros global intersections of those lists.

Example:

$A = [4,6,3,0,7,0,0,0,1,0,0]$

$B = [6,6,7,1,7,0,0,0,4,0,0]$

$C = [2,4,7,0,7,0,0,0,3,0,0]$

The output are the position of those intersections:

The positions are $5, 6, 7, 9$ and $10$

Other than "traversing" the list and checking element by element, is there another way ?

There is no asymptotically better deterministic algorithm than the one that just checks, for each position $i=1,\dots,n$ whether $A[i]=B[i]=C[i]=0$.

This is easy to see since any correct algorithm must read at least one entry per value of $i$. To see this, suppose that there is an instance
$I = \langle A,B,C \rangle$ for which a correct algorithm $\mathcal{A}$ accesses neither of $A[i]$, $B[i]$, and $C[i]$, for some $i$.

Consider two instances  $I' = \langle A',B',C' \rangle$  and  $I'' = \langle A'',B'',C'' \rangle$ that are identical to $I$ except (possibly) for the fact that $A'[i]=B'[i]=C'[i]=0$ and $A'[i]=B'[i]=C'[i]\neq 0$. Clearly $\mathcal{A}$  must return the same set $S$ of indices on all of $I$, $I'$, and $I''$. If $i \in S$, then $\mathcal{A}$ fails on $I''$, otherwise $\mathcal{A}$ fails on $I'$.


How to solve the feasibility problem in 0-1 integer programs? I have an NP-hard 0-1 integer program that I need to solve. The issue with this problem is that even finding a feasible solution (ignoring the objective function) is NP-hard.

Let us look at two examples to illustrate my problem. On the one hand, the knapsack problem is an NP-hard problem which is defined as follows:

$$
    \begin{align*}\tag{$\mathit{P}_1$}
      & {\underset{\mathbf{ x }}{\text{maximize}}}
      & & \sum_{j=1}^nv_jx_j\\[3pt]
      & \text{subject to}
      & & \sum_{j=1}^{n} w_jx_j \leqslant\mathit{W},\\[3pt]
      & & & x_j \in\{0, 1\}, \forall\, j.
    \end{align*}
$$
However, finding a feasible solution to the knapsack problem is not NP-hard. In other words, find $x_j\in\{0, 1\}$ for $j=1,\ldots, n$ such that $\sum_{j=1}^{n} w_jx_j \leqslant\mathit{W}$ is easy.

On the other hand, the variable-sized bin packing problem is also NP-hard and is given by the following 0-1 integer program:

$$
    \begin{align*}\tag{$\mathit{P}_2$}
      & {\underset{\mathbf{ x }, \mathbf{ y }}{\text{minimize}}}
      & & \sum_{j=1}^ny_j\\[3pt]
      & \text{subject to}
      & & \sum_{i=1}^{m} a_ix_{ij} \leqslant\mathit{V}_jy_j,\forall\, j\\[3pt]
      & & & \sum_{j=1}^n x_{ij}=1, \forall\, i.\\[3pt]
      & & & x_{ij}, y_j \in\{0, 1\}, \forall\, i, j.
    \end{align*}
$$
However, finding a binary variables $x_{ij}$ for $i=1\ldots,m$ and $j=1,\ldots,n$ seems to be as hard as finding a solution to the bin packing problem.

In fact, if I apply the first-fit algorithm to the following instance of bin packing: two bins with capacities $V_1=3$ and $V_2=4$, respectively, and three items with values $a_1=2$, $a_2=2$ and $a_3=3$. The first-fit algorithm (if it processes the items in the order $a_1$, $a_2$ and $a_3$ will put item 1 into bin 1, item 2 into bin 2 and there is no bin left (i.e., $n=2$). Hence, the first-fit algorithm should output error or something since it cannot assign all items to the $n$ bins. Clearly, the optimal assignment can be items 1 and 2 into bin 2 and item 3 into bin 1. How to solve this issue with the greedy first-fit algorithm?

In general, if I have a 0-1 integer program that is hard to check its feasibility, how to design an algorithm that makes few errors? For example, for the bin packing problem, all the papers I found are not interested in finding feasibility but they are trying to the solve the problem when it is feasible.  In many practical cases we cannot pack all the items in $n$ bins using our greedy approaches (even though the optimal algorithm can).

Any suggestions where to find solutions to feasibility of 0-1 integer programs?

The fundamental misconception seems to be: you seem to expect there to be some good way to solve NP-hard problems.  But the whole point of NP-hard problems is that there is (most likely) no good, general way to find optimal solutions to NP-hard problems in a reasonable amount of time.  So, you seem to be asking for something that (most likely) doesn't exist.

To answer your specific questions:

  [Here's an example where the grey first-fit algorithm doesn't find the optimal solution to a bin-packing problem.]  How to solve this issue with the greedy first-fit algorithm?

You can't.  The greedy first-fit algorithm isn't guaranteed to find an optimal solution (and often won't).  Morever, as you said, it's NP-hard even to find a feasible solution -- therefore, you shouldn't expect the greedy first-fit algorithm to be guaranteed to find a feasible solution, either.  It's no surprise that it fails to find a feasible solution to a NP-hard problem.  And there is (most likely) no way to fix it, while still having an efficient running time.

  In general, if I have a 0-1 integer program that is hard to check its feasibility, how to design an algorithm that makes few errors?

In general, there may be no way.

  Any suggestions where to find solutions to feasibility of 0-1 integer programs?

There's lots of literature on methods for solving integer linear programming (ILP).  None of them are guaranteed to find feasible solutions within a polynomial running time (after all, the problem of finding a feasible solution is NP-hard), though some of them might work well enough on some problems that you run into in practice.  Rather than study the literature and try to implement the known methods, you're probably better off using an off-the-shelf ILP solver -- the developers who implemented the ILP solver did that for you.


Do we know how to make a "voice print" and use it for computer generated voice? Well everything is in the title.

After all Siri voice was made from someone, so can I
use software to make a computer generated voice sound
like my voice or anybody else?

See the Voice transformation project from the The Center for Speech Technology Research at the University of Edinburgh.
Thesis: Transforming Voice Quality and Intonation by Ben Gillet.
It doesn't do exactly what you are asking, but something similar; it tries to change the voice of a recording to another voice.
Abstract:

Voice transformation is the process of transforming the characteristics of speech uttered by a source speaker, such that a listener would believe the speech was uttered by a target speaker. In this thesis two aspects of the transformation problem are addressed: voice quality and intonation
The voice quality transformation component of our system has two main parts corresponding to the two components of the source-filter model. The first component transforms the spectral envelope as represented by a linear prediction model. The transformation is achieved using a Gaussian mixture model, which is trained on aligned speech from source and target speakers. The second part of the system predicts the spectral detail from the transformed LPC parameters. A novel approach is proposed, which is based on a classifier and residual codebooks. The system has some similarities with earlier work by Kain, however the work reported here is not restricted to speech spoken in a monotone and with mimicked prosody. Also, on the basis of a number of performance metrics it outperforms existing systems.
We also present a new method for the transformation of pitch contours from one speaker to another based on a small linguistically motivated parameter set. The system performs a piecewise-linear mapping using these parameters. A perceptual experiment, clearly demonstrates that the presented system is at least as good as the existing technique for all speaker pairs, and that in many cases it is much better and almost as good as using the target pitch contour.


Choosing Fitness function for float output in Genetic algorithm I have a NN that has ten outputs. The output values range between 0 and 1. The elements in the target array are all zeros except one element, which is "one".

I am searching for a Fitness Function that will correctly evaluate (score) the Neural Networks.

Currently, I am trying to calculate the distance between the target and the output arrays. The issue is that at the beginning all my NNs return results that are very close to each other and I can't properly choose the fittest individuals.

For Example:

NN1 -> FF score:0.10030096 -> Rank?
NN2 -> FF score:0.09996143 -> Rank?
NN3 -> FF score:0.10015215 -> Rank?

Any suggestions?

The standard solution is: Use a softmax layer at the output of your neural network, and use the cross-entropy loss as your fitness function.


concatenation of context sensitive and context-free is context sensitive or not? Assume that $L_1$ is context sensitive language and $L_2$ is context free language, is the language $L_1 * L_2$ context-sensitive or not?

I almost sure that is not, but can't prove it.

Suppose that $L$ is a context-sensitive language which is not context-free. Then $L\{\epsilon\}$ is not context-free (here $\epsilon$ is the empty word), while $L\emptyset$ is context-free.


"Archiving" byte sequence into human-readable set of chars Ok, lets assume we  have sequence of  1000 bytes.
So the possible  number of value variations is 2^100.

Is there a way to "index" each variation with letters and decimal numbers (A-Z, 0-9), having as shortest length as possible?

So the person can dictate sequence of letters and numbers by phone and it can be recreated into bytes on the other side.

Im really bad at math, and found how to shorten that string up to about 100 symbols. Any way to di it shorter?

A common encoding used for such tasks is Base64. It is easy to implement and it has been implemented multiple times in many main-stream languages. However, it is not exactly suited for being read by humans.

The basic underlying idea is that a character of Latin alphabet is encoded in ASCII using 6 bits. The encoding alphabet is completed by few punctuation symbols to make it the exact multiple of 8.

Here is a nice even if somewhat light-hearted proposal http://www.crockford.com/wrmg/base32.html for alternative Base32 encoding (it also tries to prevent occasional appearance of expletives in the produced encoding, at least if it is interpreted as English language).

Unfortunately, you won't be able to make it much shorter using only Latin alphabet, unless you have more information about the nature of the data being encoded. Text compression algorithms would try to discover such information about the text being encoded and use variable length encoding, assigning shorter sequences in the output to the more common sequences in the source text. For a simple example of such encoding you can look into Huffman coding

Another, obvious way to shorten the output length is to use a larger alphabet.


AI approach for exploring a static grid environment I have a grid environment which contains in each cell a static agent. When my agent enters a cell, the static agent in this cell might take points away from me, give me points, or do nothing. My agent can not observe adjacent cells until it moves into one them, it can only move up, down, left or right.

This agent can not learn whilst it is exploring. It enters the grid from a particular corner, and may only leave from that corner. If the agent manages to successfully explore the environment and return back to the corner with positive health, then it can learn from its collected experience, which includes the (row, column) positions it visited, and the properties of the static agents located in those positions. If the agents' health drops to zero whilst exploring, game over. But I can restart the exploration as many times as I want.

Each static agent has one of three shapes, one of three colours, and one of two sizes. It also has an associated "reward", indicating how many points it adds/removes from me.

Each move in this environment costs me one point. I want to design an agent that correctly recognises the reward associated with each type of static agent in this grid.

Please may someone recommend a learning and/or evolutionary approach to solving this problem? I'm stuck at the moment because of the restriction that agent may not observe adjacent squares. I'm not sure how I can learn anything from this testing environment from the (row, column) and static agent properties encountered alone.

Obviously one of the best learning methods that matches this problem is the Reinforcement Learning and to be more specific Q-Learning.
You'll find a good starting point here.
Hints: Q-learning is quite well-known and I don't repeat others here, but I give you the key point here.

At each step keep track of what happens (reward/punishment - no need to agent types,... if the environment stays fixed and you want to learn this Env. not the agents) using for example an array (Fortunately you're not learning anything so far!). Keep doing this until the agent stops, that as you said can have two reasons :

Agent's health drops to zero : Do nothing! (discard the array)
Agent leaves from the other corner : Apply the following rule with the values in the array


What benefits are obtained by allowing the occurrence of free variables and open terms in lambda calculus? Because of the existence of free variables in lambda calculus, the evaluation of open terms (at least as outlined here) is more complicated relative to the evaluation of closed terms since the evaluator must ensure that the beta-reduction step uses capture-avoiding substitution, i.e., that the variables it substitutes into a term are not free variables of that term.
Combinatory logic can be seen as a subset of lambda calculus that only allows closed terms. Despite this, it is still Turing-complete, and can thus be used to compute everything that lambda calculus can. As such, what are the benefits of allowing free variables and open terms, and the disadvantages of disallowing them? On a related note, why does lambda calculus seem to be a more popular topic of study than combinatory logic despite the apparent shortcoming mentioned? Is the former somehow more relevant and useful to a larger variety of topics than the latter?

A subterm of a closed term is not necessarily a closed term. A calculus of closed terms would have to model open terms as well anyway. Pretty much any definition on terms relies on induction over the structure of the terms, and to define something for closed terms of the form $\lambda x. M$, you need to define that thing for the open term $M$.
There are plenty of models of computation. What's the benefit of using combinator calculus when you can use Turing machines or Conway's game of life? Combinator calculus is a natural model of function application, but doesn't capture function definition. The lambda calculus, with variable names, models function definitions with variable names, which a core concept of most programming languages. For this reason, it's a more useful model of programming languages than combinator calculus.
The point of a theory is not just to be internally simple, it's also to be useful for reasoning.


What Happens if I swap the forget gate and update gate in LSTM model? Consider the following eqautions used in LSTM ( taken from Andrew ng's course on Sequential model)
In an LSTM model, LSTM Cell has three inputs at any time step t

Input($X_t , a^{(t-1)}, C^{(t-1)})$,
Here $X_t$ is the input vector, $a^{(t-1)}$ is the previous hidden state and $ C^{(t-1)}$ is the previous cell state

Now the new cell state $c^t$ is given by the following formula :
$C^t = $  forget_gate * $C^{(t-1)} + $ update_gate* $\overline{C^t}$

Question:
If I swap the places of forget_gate and update_gate, I still get a valid $C^t$, So why are we multilyting the previous cell state with forget gate only and the current cell state with update gate only, what if Imultiply previous cell state with update gate ?
Edit :  After swapping, the formula would look like this,
$C^t = $  update_gate * $C^{(t-1)} + $ forget_gate* $\overline{C^t}$

The two formulas are mathematically equivalent; the only change is that you have swapped the names of the variables (changes them to names that are less intuitive, compared to what effect they have), but that doesn't affect the behavior of the system.


Do height-balanced binary trees have logarithmic depth? A family of binary trees is called balanced if for every tree $t$ in the family the height of $t$ is $O( \log n)$.

Given a family of trees such that for every tree $t$ in the family, for every node $v$ in $t$, the height difference between the right subtree of $v$ and the left subtree of $v$ is at most $c$, where $c$ is some constant.

I understand this claim is true. It is the general case for AVL trees. I just don't know how to prove it formally.

Let us denote by $N_h$ the minimum number of leaves of a tree in your family of height $h$. Clearly $N_0 = 1$, and
$$ N_h = N_{h-1} + \min_{0 \leq d \leq c} N_{h-1-d}. $$
(Here $N_h = 0$ if $h < 0$.) You can prove inductively that $N_h$ is monotone, and so for $h \geq c+1$,
$$ N_h = N_{h-1} + N_{h-1-c}. $$
This is a recurrence relation whose solution is $N_h = \Theta(\alpha^h)$, where $\alpha$ is the maximal real root of $x^{c+1} - x^c - 1= 0$; for example, when $c = 1$, $x$ is the golden ratio.

Since the number of leaves in a tree of height $h$ is $\Omega(\alpha^h)$, it follows that a tree containing $n$ leaves has height $O(\log n)$.


Online algorithm for finding of clique of size k I am trying to write an online algorithm that can detect cliques of size k. I first start out with a set of vertices. For each iteration, I add an edge. The algorithm will detect the first time an edge would create a clique of size k. What is an efficient algorithm that can complete this task, and what is the time complexity?

Since I don't have enough points for a comment:

This problem is not going to have a very efficient solution. Looking at the $k=3$ case should be good start. In this case one can solve this problem with $O(|E|)$ space by keeping an (online) adjacency set for each vertex and when an edge $(u,v)$ arrives comparing the adjacency sets of vertices $u$ and $v$ for a collision (in time linear in the size of the smaller set) and then adding $(u,v)$ to the sets of vertex $u$ and $v$.

The run time of this algorithm would be $\sum_v d(v)^2$, where $d(v)$ is the degree of vertex $v$ in the final graph. This is never bigger than $O(n^3)$, where $n$ is the number of vertices in the final graph.

It is unknown whether triangle detection (i.e., a clique of size 3) can be done in  less than $n^3$ time even if you had the entire graph before you. See this, for instance.


Efficient point grouping algorithm I'm trying to find a good solution to the following problem:
Given a set of 3d real number coordinates inside a cube, I want to group them into containers. The containers should contain all elements that are in predefined distance to at least one of the other elements. Should two elements be closer than a predefined distance, they are to end in the same container.
Note: Two elements that are further apart may end in the same container e.g. if they are both close to a different element

The most straight forward solution I can think of is to go through all points, and compare them with all other points that haven't been visited before to find out if they are in proximity, but it seems rather inefficient.

I tried to find a solution online, but (maybe because I'm missing the correct keywords) can't find any. I stumbled upon k-d-trees and similar concepts but as far as I understood they don't help much here. Are there good algorithms out there that can take care of this or does anybody have a suggestion on what I could do?

Below is a (badly hand drawn) illustration of a possible 2d case with reference distance d marked in blue and the two groups I want to end up with in red. Thanks in advance for any help.

Edit: as pointed out in the comments, this problem can be thought of as finding connected components of a graph. The graph nodes are the points from the data set and two nodes are adjacent if their distance is smaller than the reference value. The problem I see is that establishing the edges seems to be O(n^2), because I don't see a way that doesn't require me to do pairwise checks on all points of the set, is that correct?

My Solutions

I will try to elaborate on what solutions I found, their implementations and those implementation's running time.
As I don't have any real computer science background, please point out any mistakes/unclarities you find.

First: The problem, in general terms, is to partition a set of points from
$A \subset \mathbb{R}^d$ into groups such that every point in them is $\epsilon$-reachable
from every other point in the group.
Reachable,for $x_1, x_n \in A$, means there is a sequence of points $x_1,\dots,x_n \in A$ s.t. $d(x_i,x_{i+1})<\epsilon$.
In other terms: If two points are closer than $\epsilon$ to each other, the algorithm must assign them to the same group/cluster.

DBSCAN:
DBSCAN is a super general algorithm. I will use $B_{\epsilon}(x)$ for the $d$-dimensional sphere around $x$ with
respect to some arbitrary metric $d(\cdot,\cdot)$. DBSCAN finds clusters by defining:

$x \in A$ is a core point, if at least $N$ other points of $A$ lie in $B_{\epsilon}(x)$
$x \in A$ is directly reachable from $y \in A$ if both are core points and $d(x,y)<\epsilon$
$x \in A$ is reachable from $y \in A$ if there exists a sequence $x_1 =x, \dots, x_n =y \in A$ s.t. $x_{i+1}$ is reachable from $x_i$
non reachable points are outliers

Now, as you might see, for $N=2$ (if you include every point itself when counting) and $d(\cdot, \cdot)$ the usual
euclidean metric
this defines exactly the problem I stated above. DBSCAN clusters together core-points deterministically,
but also adds non-core points to clusters. So if $x \in A$ is reachable from core point $y$, it might
end up in the same cluster without being a core point itself. I say might, because non-core points
may be reachable from different clusters. The assignation is then determined by the order in which
the algorithm runs through the clusters. This ambiguity however resolves with $N=2$, as then every point
that is reachable from another is automatically a core point, that is reachability as stated
above is then a symmetric relation. Clusters are then unambiguous.
In case of an indexing structure that does neighborhood querys in $O(logn)$, the runtime complexity is
apparently $O(n \; logn)$, but don't take my word for it.

I used scikit-learn's implementation of DBSCAN (http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html).
I failed to find out what runtime complexity this implementation has, but the docs state memory complexity
of $O(n.d)$.

Intersection graph:
As it has been proposed in a different answer: One can also think of the problem as a graph-theoretical one.
The graphs vertices are represented by the points in $A$, with two vertices being adjacent iff their
points are in $\epsilon$-distance of each other. On this graph the problem translates to finding the
connected components.
The paper of
Bentley, Jon L.; Stanat, Donald F.; Williams, E. Hollins, Jr. (1977), "The complexity of finding fixed-radius near neighbors", Information Processing Letters, 6 (6): 209–212
provides an algorithm for constructing this graph that runs in linear time and is essentially identical to the one proposed
by @D.W.. Finding the connected components can also be done in linear time, e.g. by breadth- or depth-first algortihms.

Python Code:
For the Code, I mainly used the DBSCAN implementation of scikit-learn, networkx for graphs and finding
connected components (it is open source but I couldnt find any reference on the runtime complexity)
and scipy.spatial's cKDTree implementation (which I do not understand in detail).

from sklearn.cluster import DBSCAN
from sklearn.datasets.samples_generator import make_blobs
import networkx as nx
import scipy.spatial as sp

def cluster(data, epsilon,N): #DBSCAN, euclidean distance
    db     = DBSCAN(eps=epsilon, min_samples=N).fit(data)
    labels = db.labels_ #labels of the found clusters
    n_clusters = len(set(labels)) - (1 if -1 in labels else 0) #number of clusters
    clusters   = [data[labels == i] for i in range(n_clusters)] #list of clusters
    return clusters, n_clusters

Is my minimal implementation of the previously described goal. The method returns clusters and their size.
For the graph method, I wrote a little class. The class describes a graph whose vertices are the indices
of the corresponding points in $A$ as list. Using the cKDTree's data structure, finding pairs of
reachable points is lightning fast. You can then slice out the elements via the indices.

class IGraph:
    def __init__(self, nodelst=[], radius = 1):
        self.igraph = nx.Graph()
        self.radii  = radius
        self.nodelst = nodelst #nodelst is array of coordinate tuples, graph contains indices as nodes
        self.__make_edges__()

    def __make_edges__(self):
        self.igraph.add_edges_from( sp.cKDTree(self.nodelst).query_pairs(r=self.radii) )

    def get_conn_comp(self):
        ind = [list(x) for x in nx.connected_components(self.igraph) if len(x)>1]
        return [self.nodelst[indlist] for indlist in ind]

def graph_cluster(data, epsilon):
    graph = IGraph(nodelst = data, radius = epsilon)
    clusters = graph.get_conn_comp()
    return clusters, len(clusters)

I also did a little benchmark, but it is in no way representative. I create a cluster with:

centers = [[1, 1,1], [-1, -1,1], [1, -1,1]]
X,_ = make_blobs(n_samples=N, centers=centers, cluster_std=0.4,
                            random_state=0)

For different N, the methods compare differently, on my machine for example:

$N = 20000$: "cluster": 293.711 ms, "graph_cluster": 422.089 ms
$N = 7000$: "cluster": 87.455 ms, "graph_cluster": 95.322 ms
$N = 700$: "cluster": 3.764 ms, "graph_cluster": 1.689 ms

For small datasets, and this specific clustering, the graph solution wins. But apparently
the DBSCAN shows better scaling behavior. I haven't looked at different dimensions of the data,
but that may also be interesting. Also: the results are exactly the same for both algortihms.
Additional Note: The graph solution scales heavily with $\epsilon$, which is 0.1 in my code. Larger values make it far worse! In other words: If you have small clusters, the graph solution outperforms DBSCAN by ages, for large clusters it is the other way around (apparently).


Speedup with multi-head Turing Machine What sort of speedup can a Turing machine with more than one head give vs a one-headed machine (I do not mean multiple tapes, I mean multiple heads operating on the same tape making concurrent edits on different parts of the tape)?
ie. what is the overhead, worst-case, for a one-head Turing Machine to simulate a multi-head Turing Machine as the number of heads grow?
https://link.springer.com/content/pdf/10.1007/3-540-08342-1_35.pdf
^ This paper ^ says linear time. But the multi-head machines have the additional property of a one-move shift operation (shift a given head to the position of some other given head), is this standard?
Thanks!

First, the one-move shift is definitely NOT standard, but, as far as I understand, it only strengthens the result in that article. If a machine with the special operation can be simulated, then of course a machine without that operation can as well.
Second, here are some papers by Hans-Jörg Stoß dealing with multi-head machines. No one-move shifts here.

k-Band-Simulation von k-Kopf-Turing-Maschinen (1970) - establishes that $k$-head and $k$-tape can simulate each other without changing computation time.
Zwei-Band Simulation von Turingmaschinen (1971) - simulates a machine with $k$ heads on an $m$-dimensional tape by a machine with 1 normal tape plus 1 stack, establishing a rather precise time bound.
Linear-Time Simulation of Multihead Turing Machines (1989) - linearly simulates a machine with $k$-heads on a $d$-dimensional tape by a machine with $k$ separate $d$-dimensional tapes plus 1 normal tape.

Unfortunately, the first two are, as far as I know, only in German. The full text of the third one (translated) is here: doi.org/10.1016/0890-5401(89)90037-0


bounded length CoNP proof Question:
Let $A \subseteq $ {0,1}$^* $ be a language which satisfies $|A \cap ${0,1}$^n|=n^3 $ for all $n\ge 10$ Prove that $A \in NP$ implies $A \in coNP$.

Thoughts
I've been having difficulty with this problem. My idea is somehow showing that each set of $n^3$ words cannot be a verifier for A and therefore A is in coNP. The problem is that as I see it, proving this will take exp time as I have an exponential number of options for strings from which to choose n^3 from.  Would like some suggestions about how to prove this.

Assume that $A\in NP$, and let $V$ be a verifier for it. That is, $V$ takes as input $(x,y)$ and outputs 1 if $y$ witnesses that $x\in A$. That is, we can write $A=\{x:\exists y,\ V(x,y)=1\}$.

We show that $A\in coNP$, by showing that $\overline{A}\in NP$. We construct a verifier $V'$ for $\overline{A}$ as follows:

Given input $x$, $V'$ expects a witness of the form $(w_1,y_1,...,w_{n^3},y_{n^3})$, where $|x|=n$, such that $y_i$ is a witness that $w_i\in A$, and for every $i$ we have $w_i\neq x$. That is, a witness for $x$ not being in $A$ is simply a list of all the $n^3$ words that are in $A$. Clearly verifying this can be done in polynomial time using $V$ (which we assume to run in polynomial time).


Why is DFS considered to have $O(bm)$ space complexity? According to these notes, DFS is considered to have $O(bm)$ space complexity, where $b$ is the branching factor of the tree and $m$ is the maximum length of any path in the state space.

The same is said in this Wikibook page on Uninformed Search.

Now the "infobox" of the Wikipedia article on DFS presents the following for the space complexity of the algorithm:

  $O(|V|)$, if entire graph is traversed without repetition, $O($longest path length searched$)$ for implicit graphs without elimination of duplicate nodes

which is more similar to what I thought was the space complexity of DFS, i.e., $O(m)$, where $m$ is the maximum length reached by the algorithm.

Why do I think this is the case?

Well, basically we don't need to store any other nodes than the nodes of the path we're currently looking at, so there's no point of multiplying by $b$ in the analysis provided both by the Wikibook and the notes I'm referred you to.

Moreover, according to this paper on IDA* by Richard Korf, the space complexity of DFS is $O(d)$, where $d$ is considered the "depth cutoff".

So, what's the correct space complexity of DFS?

I think it may depend on the implementation, so I would appreciate an explanation of the space complexity for the different known implementations.

It depends on what exactly you call DFS. Consider for example the algorithm DFS-iterative described in Wikipedia, and suppose that you run it on a tree so that you don't have to keep track of which nodes you have already visited. Suppose that you run it on a complete $b$-ary tree of depth $m$. We can identify nodes in their tree with words over $[b]$ of length at most $m$. The algorithm operates as follows:

Start at the root. Push $1,2,\ldots,b$ to the stack (in reverse order).
Pop $1$, and push $11,12,\ldots,1b$ to the stack.
Pop $11$, and push $111,112,\ldots,11b$ to the stack.
$\ldots$
Pop $1^{m-1}$, and push $1^m,1^{m-1}2,\ldots,1^{m-1}b$ to the stack.

At this point, the stack contains

$$ 1^m,1^{m-1}2,\ldots,1^{m-1}b,\ldots,112,\ldots,11b,12,\ldots,1b,2,\ldots,b, $$

for a total of $(b-1)m + 1$ nodes. You can check that this is the pint in time in which the size of the stack is maximized.


Time complexity to sort 100 elements by using selection sort? What will be time complexity for sorting 100 elements using selection sort answer given is O(1), but selection sort time complexity is O(n^2) in every case so how O(1)?

That's because you only have a constant number of elements, in this case 100. In other words, $100^2 = O(1)$, i.e., you do a constant amount of work. Usually it is more interesting to analyze the scalability of an algorithm with a growing input size $n$.


Difference between computation in proposition proof and definitional computation? As stated in equality at nLab, "computational equality" is about computational steps which take for example, $s(s(0))+ s(0)$ to $s(s(s(0)))$ and it acts exactly and can be considered same as definitional equality (at least in type theory).

But then if we consider $p$ in $p:Id_\mathbb{N}(a+b, b+a)$ as computation steps taking $a+b$ to $b+a$ then what is the difference between computation steps in $p$ and computation steps in above mentioned computational equality which prevents $p$ to be considered sort of a definitional equality? Are they of different computation level/form?
Or in other words, if I have got it correctly, what is the difference between $p$ in $p:Id_\mathbb{N}(a+b, b+a)$ and $p'$ in $p':Id_\mathbb{N}(s(s(0))+s(0), s(s(s(0)))) $ so that one can be considered almost the same thing as definitional equality but not the other one?
As an example following are the Agda codes in proving above mentioned reactions from Programming language foundations in Agda: Natural Numbers and [Programming language foundations in Agda: Proof by induction][3]correspondingly:

_ : 2 + 3 ≡ 5
  =
-
  begin
    2+3
  ≡⟨⟩    -- is shorthand for
    (suc (suc zero)) + (suc (suc (suc zero)))
  ≡⟨⟩    -- inductive case
    suc ((suc zero) + (suc (suc (suc zero))))
  ≡⟨⟩    -- inductive case
    suc (suc (zero + (suc (suc (suc zero)))))
  ≡⟨⟩    -- base case
    suc (suc (suc (suc (suc zero))))
  ≡⟨⟩    -- is longhand for
    5
  ∎

+-comm : ∀ (m n : ℕ) → m + n ≡ n + m
+-comm m zero =
  begin
    m + zero
  ≡⟨ +-identityʳ m ⟩
    m
  ≡⟨⟩
    zero + m
  ∎
+-comm m (suc n) =
  begin
    m + suc n
  ≡⟨ +-suc m n ⟩
    suc (m + n)
  ≡⟨ cong suc (+-comm m n) ⟩
    suc (n + m)
  ≡⟨⟩
    suc n + m
  ∎

In my understanding both thing are computational steps that take you from left hand side to the right hand side!
 Would you please answer it both intuitively and technically?

P.S. I found the following piece in Homotopy Type Theory(§1.1 p.22) which I thought might be the answer to part of my own question:

  Whether or not two expressions are equal by definition is just a matter of expanding out the definitions; in particular, it is algorithmically decidable (though the algorithm is necessarily meta-theoretic, not internal to the theory).

I guess the above paragraph is talking about $\alpha$ and $\beta$ expansions. But if that is true then it raises the question that: What does a proof of a proposition has in addition to function application that makes it a different equality? Is it that beside application we do have function definitions as well in a proof definition?!

What Agda is showing you in the source code in both cases are the propositional proofs, i.e., elements of the identity type. In Agda the judgemental (definitional) equality is invisible to the user. Agda uses it in the background to verify that terms have required types. When it has to compare $a$ and $b$, it normalizes both of them (based on judgemental equalities, such as $\beta$-reduction) and compares the normalized values for syntactic equalities. There is a theorem which says that $a$ and $b$ are judgementally equal if, and only if, they have syntactically equal normal forms.

When judgemental equality has the property that things are equal preciely when they have syntactically equal normal forms, then people sometimes call it computational equality because it "computes" by computing normal forms. There is a lot of confusion in terminology.

To test judgmental equality in Agda, we can use refl to show that two things are judgmentally equal (because the rule for refl states that refl a has type b ≡ c if, and only if, b and c are both judgmentally equal to a). Here are some examples:

 open import Relation.Binary.PropositionalEquality
 open import Data.Nat

 -- this works, the normal form of 2 + 3 is 5
 p : 2 + 3 ≡ 5
 p = refl

 -- this works, the normal form of 0 + m is m
 q : ∀ m → 0 + m ≡ m
 q _ = refl

 -- this does not work, because hte normal form of m + 0 is m
 -- r : ∀ m → m + 0 ≡ m
 -- r _ = refl

You can also show that $2 + 3 = 5$ by providing an element p' of 2 + 3 ≡ 5 which is not refl, such as the one you posted in the question. In the text you read, they were just trying to demonstrate the normalization steps by making them explicit as elements of an identity type (without saying so explicitly, probably). The thing to remember is that in Agda you will never see "a proof of judgemental equality", as that always happens in the background.


What's the difference between user registers and kernel registers? I am reading Operating Systems: Three Easy Pieces, but I can't fully understand the following paragraph. It's from the 6th chapter of the book. I think it's self-contained, so I quote here.

Note that there are two types of register saves/restores that happen during this protocol (context switch). The first is when the timer interrupt occurs; in this case, the user registers of the running process are implicitly saved by the hardware, using the kernel stack of that process. The second is when the OS decides to switch from A to B; in this case, the kernel registers are explicitly saved by the software (i.e., the OS), but this time into memory in the process structure of the process. The latter action moves the system from running as if it just trapped into the kernel from A to as if it just trapped into the kernel from B.

I understand that OS need to save some registers to do context switch, but what does it mean by saying user registers and kernel registers? What are the differences between them?
Thanks!

It's simple - when each application program runs, it has access to its own set of registers. When you switch to other application, these register contents is saved to memory, and registers, saved from other application, loaded and this application continues its execution.

Similarly, OS has its own register contents. Depending on CPU, it may even has its own, different register set. Moreover, some CPUs has two physical register sets - for apps and for OS, thus allowing fast switching from app to OS and back again (f.e. when app requests some service from OS).

Now let's look at your citation. I'm not an OS specialist, but this text means that for each application, we have specific contents of OS registers. F.e. these registers may hold app-specific data which isn't available to app itself (such as security context of the app). So, when you switch from app to OS (usually by requesting some OS service), OS registers are immediately ready to use, making the call faster. OTOH, when you switch to other app, the entire set of kernel registers need to be saved and kernel registers for other app should be loaded instead.

Since task switching is much less frequent operation, this makes the entire execution faster.


Recurrence $T(n) = T(n - \log n) + 1$ Given recurrence relation : $$
T(n) = \begin{cases}
   T(n-\log n) + 1 & \text{if } n \ge 1,
   \\
   1 & \text{otherwise.}\\
\end{cases}
$$
To find asymptotic order of $T(n)$  i do as follow:
Suppose $n=\log m$ now :
$$T(\log m)=T(\log m-\log \log m) +1$$
$$\implies T(\log m)= T(\log \frac{m}{\log m}) +1$$
,but in this step i get stuck and i don't know how we can transfer relation to get easier relation.

Let $n_0 = n$ and $n_{i+1} = n_i - \log n_i$. Then $T(n)$ is one plust the minimal $t$ such that $n_t \leq 1$.
Clearly $n_{i+1} \geq n_i - \log n$, hence $n_t \geq n - t\log n$, implying that $T(n) \gtrsim n/\log n$.
In the other direction, as long as $n_i \geq \sqrt{n}$, the sequence decreases by at least $\tfrac{1}{2} \log n$, hence it takes at most $2n/\log n$ steps to get down from $n$ to $\sqrt{n}$. After at most $4\sqrt{n}\log n$ steps, we get down to $\sqrt[4]{n}$; and so on. If we carefully count the steps, we see that $T(n) = O(n/\log n)$. Hence $T(n) = \Theta(n/\log n)$.


Shor's Algorithm speed I'm a fledgling computer science scholar, and I'm being asked to write a paper which involves integer factorization. As a result, I'm having to look into Shor's algorithm on quantum computers.

For the other algorithms, I was able to find specific equations to calculate the number of instructions of the algorithm for a given input size (from which I could calculate the time required to calculate on a machine with a given speed). However, for Shor's algorithm, the most I can find is its complexity: O( (log N)^3 ).

Is there either some way I can find its speed/actual complexity from its Big-O Notation? If not, is there someone who can tell me what I want, or how to find it?

The best estimate I know of can be found in Efficient networks for quantum factoring, by David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill, which gives $72 (\log N)^3$.

Having said that, a straight comparison of number of steps on a quantum computer versus number of steps on a classical computer is problematic for various reasons. First, as D.W.'s answer says, the number of steps depends on the exact architecture of the quantum computer, which we won't have until one is built. Second, the time required for a single step on a quantum computer is likely to be quite a bit slower than a single step on a classical computer.1 Again, we won't know how much slower until quantum computers exist.

1 If it was faster, you could use the same architecture to build a classical computer that would be at least as fast, and probably faster because for a classical computer, you don't need to worry about maintaining quantum coherence.


Find the minimum cost of adding the elements of a set (greedy algorithm) I'm VERY stuck with this problem:
Given a set (with possible repeated elements), the cost of adding two elements $x, y$ is $x + y$.
For example, the possible costs of the next set $\{1,2,5 \}$ are:

The cost of adding $1 + 2$ (with cost $3$), plus the cost of $3 + 5$ (with cost $8$). The overall cost is $11$.
The cost of adding $1 + 5$ (with cost $6$), plus the cost of $6 + 2$ (with cost $8$). The overall cost is $14$.
The cost of adding $2 + 5$ (with cost $7$), plus the cost of $7 + 1$ (with cost $8$). The overall cost is $15$.

We want to find the minimum overall cost (implementing a greedy-algorithm).
I've implemented two approaches:
const minCost = (l = []) => {
    sort(l);
    let cost = 0;
    let currentSum = 0;
    for(let i = 0; i < l.length - 1; i++){
        if(i === 0){
            currentSum = l[i] + l[i + 1];
            cost += currentSum;
        }
        else{
            currentSum += l[i + 1];
            cost += currentSum;
        }
    }
    return cost;
}

What im doing here is sorting in ascending order, and then simply computing the costs (like the first option in the example).
The issue I found is with the following instance: [2,2,2,2] will compute a cost of 18. But, I've realized that you can group the elements and compute the cost of the in this way: ((2+2) + (2+2)), with overall cost of 16.
So I also came out with this approach:
const cost = (l = []) => {
    if(l.length <= 1) return 0
    else return l.reduce((acc, val) => acc + val, 0)
}

const minCostRecursive = (l = []) => {
    if(l.length <= 2) return cost(l)
    let left = minCostRecursive([...l.slice(0, Math.ceil(l.length/2) )])
    let right = minCostRecursive([...l.slice(Math.ceil(l.length/2), l.length)])
    let newList = []
    left > 0 ? newList.push(left) : newList.push(...l.slice(0, Math.ceil(l.length/2)))
    right > 0 ? newList.push(right) : newList.push(...l.slice(Math.ceil(l.length/2), l.length))
    return left + right + minCostRecursive(newList)
}

The main idea is to partition the cost of the halves. If you have two items, the cost is the sum of the items. If you have one or fewer items, the cost is 0 (there is nothing to add). If not, I make a recursive call to the function with the halves, and with if its result is greater than zero, then I add it to a new list. If not, I add the element that was there before, and call the function again.
But also, I found a counterexample [1,5,7,9] (in the first implementation it gives 41, but in the second returns 44). Moreover, I think this isn't a greedy solution.

I think the following algorithm can work (and is greedy):

Put all elements in a priority queue
While the priority queue has at least 2 elements, extract the two lowest elements, sum them, then add the sum to the priority queue

It gives a correct order for summing elements to get the minimal overall cost.


What is The correct terminology for expressing *this* notion of complexity Say for example, I have an algorithm $Al_i$ that produces output from the set $S = \{s_i\}$ for problems from the set $P = \{p_i\}$, and another algorithm $Al_j$ that also produces output from the set $S = \{s_i\}$ for problems from the set $P = \{p_i\}$. For the purposes of this question, $Al_j$ and $Al_i$ are the same.

Or, if I have two systems that produce the same output given the same input, then we can treat these systems as the same.

Generally, if two objects do the same things (produce the same output for identical input, convey the same information as output), then these objects are identical. The processing of the systems are not relevant. We're only concerned with the output of the systems, objects, entities, etc.

Now, there are many such identical systems. Say $T_i$ is some set of all identical objects/entities/systems that do some same thing. Let $t_i^*$ be the object in $T_i$ with the smallest Kolmogorov complexity.

  Is there a conventional terminology for expressing $t_i^*$?

An example of a $T_i$ may be the set of all proofs for a particular theorem. (Here the Kolmogorov complexity of all theorems includes each intermediate theorem invoked in its proof (so basically each theorem would first be expressed in axioms first and computing the complexity of that expression)). I may be interested in referring to the least complex theorem (using the aforementioned notion of the complexity of the axiomatic expression of the theorem).

Things can be defined by form or by function. I understand that Kolmogorov complexity traditionally considers the former, while I am concerned with the Kolmogorov complexity of the latter. A picture has a defined form, and an algorithm that only produces that picture is no different from the picture itself. What about an algorithm that produces different output. We could look at the form of the algorithm, or look at its function. Looking at function, all correct algorithms for a particular problem are identical. Bogosort is identical to quicksort which is identical to mergesort, heapsort, etc.
I am concerned with the smallest Kolmogorov complexity of any sorting algorithm.

Kolmogorov's complexity is defined relative to a specific representation. It is rather meaningless to ask what is the minimal Kolmogorov complexity of a certain object over all possible representations (obviously, this requires a precise definition for what constitutes a valid representation).

To see why, consider for example the following question: what is the minimal Kolmogorov complexity of the identity function over all admissible numberings? The answer is trivially $1$, since I can encode the identity function as "0" (a single bit string).


Recognizable vs co-recognizable languages I understand following about recognizable (aka recursively enumerable) and co-recognizable languages:

Definition 1: Recognizable language is one which have one-to-one correspondence with the natural number with the additional property that we could specify an algorithm to enumerate the language elements.
For recognizable language, we can specify Turing machine which can enumerate the language elements.
Given the string in the recognizable language, Turing machine can eventually confirm that the string indeed belongs to the language.
Language L is called co-Turing-recognizable, if L’ is Turing-recognizable.
Given the string not in the co-recognizable language, Turing machine can eventually confirm that the string indeed does not belong to the language.

Doubt

Q1. What is definition 1 equivalent of co-recognizable languages?

Q2. Do they also have one-to-one correspondence to natural numbers?

Q3. Do they also have Turing machine associated with them which can enumerate their elements?

Q4. If answer to Q2 and Q3 is true, then doesnt it make them same as recognizable?

A language is recognizable if there is a Turing machine that enumerates all words in the language. It is co-recognizable if there is a Turing machine that enumerates all words not in the language.

Every language has a one-to-one correspondence to the natural numbers, simply because the number of possible words is countable.

To see the difference between recognizable and co-recognizable, let's take the prototypical example of a recognizable language: it is the language of Turing machines which halt on the empty input. It is easy to enumerate this language: run in parallel all Turing machines on the empty input, and whenever one of them halts, print its index. There is provably no similar way to enumerate the complement of this language.

If a language is both recognizable and co-recognizable, then it is decidable, meaning that there is a Turing machine that always halts and tells you whether the input belongs to the language or not. Indeed, if $L$ is recognizable and co-recognizable, then there is a Turing machine $T_1$ which enumerates all words in $L$, and other Turing machine $T_0$ which enumerates all words not in $L$. Using these, we construct a decider $T$: on input $w$, run $T_1$ and $T_0$ in parallel, until one of them prints $w$. If it were $T_1$, answer "Yes", and if it were $T_0$, answer "No".


Poly-time reduction is not antisymmetric Lemma. (Transitivity) "$\leq_p$" is a transitive relation on languages, i.e., if $L_1 \leq_p L_2$ and $L_2 \leq_p L_3$, then $L_1 \leq_p L_3$.
Proof. By definition, there are poly-time functions $f$ and $g$ such that $x \in L_1 \Leftrightarrow f(x) \in L_2$ and $y \in L_2 \Leftrightarrow g(y) \in L_3$, thus $x \in L_1 \Leftrightarrow f(x) \in L_2 \Leftrightarrow g(f(x)) \in L_3$. Obviously, $g(f(\cdot))$ is poly-time (since $|f(x)|$ is polynomial in $|x|$).

This lemma proves that "$\leq_p$" is transitive, but how would I prove that it is not antisymmetric?

By definition, a relation $R$ is antisymmetric if $aRb$ and $bRa$ implies $a=b$. Therefore, to show that $R$ is not antisymmetric, we have to find $a \neq b$ such that $aRb$ and $bRa$.

Specializing this to your case, you have to find two different languages $L_1 \neq L_2$ such that $L_1 \leq_p L_2$ And $L_2 \leq_p L_1$. Finding a pair of such languages isn't too challenging, so I leave it to you.


How to verify that a heuristic is consistent? A heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the step cost of reaching that neighbor.

I know I can be sure if a heuristic is consistent by verifying the property for each couple (node, child), but is there a smarter and quicker way for doing that?

Another option rather then verifying it for each couple node-child is to use some problem specific properties and prove it this way.

Iff it is known that the triangle inequality stands for the distance between the nodes in the specific problem, then the heuristic is consistent. The triangle inequality is part of definition of a metric. So if the distance in the problem space is some well known metric you can state that the heuristic is consistent. Example for that is the distance metric in the Euclidean geometry.


Why is Boolean satisfiability such a rare case? In the space of all K-sat formulas, True and False should have an equal set size. For every un-Satisfiable formula (F), there will an F' (or F-prime) which will be Satisfiable by definition. I cannot get my head around this.

Edit: Let me put it this way: I have constructed a circuit based on a Boolean formula, it is not Satisfiable, now I add one NOT-gate just before the output of the circuit. Does it make sense?

Your trick doesn't really work.  There are several issues.

First, your trick shows that for every unsatisfiable circuit of size $n$, there exists a satisfiable circuit of size $n+1$.  But that doesn't tell you anything about the relationship between the number of unsatisfiable circuits of size $n$ vs the number of satisfiable circuits of size $n$.  And, in general, there are way more circuits of size $n+1$ than circuits of size $n$, and most circuits are satisfiable, so the mapping you've found doesn't prove what you want it to prove.  To prove what you're trying to prove, you'd need to find a bijection between unsatisfiable circuits of size $n$ and satisfiable circuits of size $n$ (not $n+1$); no such bijection exists.

Second, the mapping you describe isn't a bijection.  Consider for example the circuit $\phi(x) = x$.  This is satisfiable.  Slapping a "not" in front if it, to get $\phi'(x) = \neg x$, yields another circuit that is also satisfiable.  Many circuits are both satisfiable (there exists an assignment that makes $\phi$ true) and their-complement-is-satisfiable (there exists a different assignment that makes $\phi$ false).  So negating an unsatisfiable circuit makes it satisfiable, but negating a satisfiable circuit doesn't necessarily make it unsatisfiable.

Finally, there's the distinction between circuits vs formulas, as David Richerby explains.  If you negate the output of a CNF formula, the result isn't a CNF formula.


How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints? Best reference I could find is this one. However, I could not quite understand this one since there is no numerical example.

What I am trying to achieve with one sentence

How can I answer the following question by using constraint programming:

  The Euclidean distances between a point $p_4$ and points $p_1(0,0)$, $p_2(0,5)$ and $p_3(5,0)$ are $5.00$, $3.16$ and $4.47$ respectively. Where is $p_4$ on the $xy$-plane?

without using quadratic constraints?

Very short version of the question

There are five points placed on a 2D plane.

We only know the pairwise distance between these points.

\begin{matrix}
d_{12} &= 5.00\\
d_{13} &= 5.00\\
d_{14} &= 5.00\\
d_{15} &= 5.00\\
d_{23} &= 7.71\\
d_{24} &= 3.16\\
d_{25} &= 4.47\\
d_{34} &= 4.47\\
d_{35} &= 3.16\\
d_{45} &= 1.41\\
\end{matrix}

In addition, we know the coordinates of first three points.

\begin{matrix}
p_1 &= &(0,0)\\
p_2 &= &(0,5)\\
p_3 &= &(5,0)\\
\end{matrix}

And we want to find the coordinates of remaining two:

\begin{matrix}
p_4 &= &(3,4)\\
p_5 &= &(4,3)\\
\end{matrix}

How can I formulate this problem without using quadratic constraints? Note that in order to impose the Euclidean distance between two points, we need to use square of differences.

Detailed version of the question

I am trying to formulate the graph embedding problem as constraint satisfaction problem.

Graph embedding is simply assigning coordinates to the vertices of a graph by considering edge weights, where the weight $w_{ij}$ of an edge $\{i,j\}$ determines the Euclidean distance between the nodes $i$ and $j$.

My decision variables are two arrays, $X$ and $Y$.
$X_i$ and $Y_i$ are the $x$ and $y$ coordinates of node $i$.

The mathematical model can be written as:

given: $G = (V,E)$

decision variables: $X = \{x_1, \dots, x_{|V|}\}$; $Y = \{y_1, \dots, y_{|V|}\}$

subject to: $\forall \{i,j\} \in E$; $(x_i-x_j)^2 + (y_i-y_j)^2 = w_{ij}^2$

As discussed here,

  $(x_i-x_j)^2 + (y_i-y_j)^2 = w_{ij}^2$

is a non-convex constraint.
Is there any way to formulate this problem using convex constraints?

I came up with something:

Assuming that the coordinates and the edge weights will be integers;

I add two more decision variables: $O^X = \{{O^X}_{12}, {O^X}_{13}, \dots, {O^X}_{21}, {O^X}_{23}, {O^X}_{|V|(|V|-1)}\} $ and  $O^Y = \{{O^Y}_{12}, {O^Y}_{13}, \dots, {O^Y}_{21}, {O^Y}_{23}, {O^Y}_{|V|(|V|-1)}\}$ where ${O^X}_{ij}$ is the offset of the $x$ coordinate of a node $j$ with respect to node $i$. The same goes with $y$ coordinates as well.

For instance, if $x_i = 3$, $y_i = 4$, ${O^X}_{ij} = 2$, ${O^Y}_{ij}j = -1$ then $x_j = 5$ and $y_j = 3$.

As for the constraints, I have written:

\begin{matrix}
\forall \{i,j\} \in E;\\
x_j = x_i + {O^X}_{ij}\\
y_j = y_i + {O^Y}_{ij}\\
|{O^X}_{ij}| + |{O^Y}_{ij}| = w_{ij}
\end{matrix}

My logic behind that approach is as follows:

Since all the coordinates are integers, we are able to assume that we place the graph on a grid.
If the Euclidean distance between $i$ and $j$ is $2$, and $i$ is on $(x,y)$ point, then $j$ should be on one of the following:

\begin{matrix}
(x-2,&y+0)\\
(x-1,&y-1)\\
(x-1,&y+1)\\
(x+0,&y-2)\\
(x+0,&y+2)\\
(x+1,&y-1)\\
(x+1,&y+1)\\
(x+2,&y+0)
\end{matrix}

Of course, this is just an approximation to the actual solution.

However, the tool I work with (IBM ILOG CPLEX) does not give a solution.

I think I am mistaken somewhere.

**Note:** The above model (entitled as "I came up with something" is **not** what I am trying to achieve.
However, I could not find a better way to impose convex constraints.

You can't. You can't express this without using quadratic constraints.  Your requirement is about Euclidean distance.  The Euclidean distance is inherently quadratic.  To be more precise about that: the problem cannot be expressed using solely using linear constraints, as the Euclidean distance is non-linear.

That said, you can solve your one-sentence question directly, if you remove the requirement to use constraint programming.  The basic technique is to use triangulation.  I'll illustrate this below.

Suppose that you know point $p_1$ is at $(0,0)$ and point $p_2$ is at $(0,5)$, and you know $d(p_1,p_4)=r$ and $d(p_2,p_4)=s$ where $r,s$ are given; you want to find the location of $p_4$.  This can be found using some simple algebraic manipulations.  Let $p_4$ be at coordinates $(x,y)$.  Then by the definition of the Euclidean distance, we have

$$\begin{align*}
r^2 &= x^2 + y^2\\
s^2 &= x^2 + (y-5)^2.
\end{align*}$$

Subtracting the two equations, we get

$$r^2 - s^2 = y^2 - (y-5)^2.$$

Simplifying the right-hand side and then solving for $y$, we find

$$y = (r^2 - s^2 + 25)/10.$$

Plugging this into the definition of $r$, we also find

$$x = \pm \sqrt{r^2 - y^2}.$$

Thus, in this way you can compute the coordinates $(x,y)$ of $p_4$ (up to reflection) from the distances $r,s$ using a bit of simple algebra.

So, if you have a point $p_4$ at some unknown location, and you know its distance to two other points at known locations, you can find the location of $p_4$ using triangulation.  Strictly speaking, we have found two possible candidates for the location of $p_4$ (modulo a reflection across the line from $p_1$ to $p_2$), but if we know the distance from $p_4$ to any third point we can try both possibilities and figure out which one of those two candidates is correct.

The same techniques can be used to solve your "very short version of the question".  We know the location of $p_1,p_2$, and for each other point, we know its distances to $p_1$ and $p_2$, so we can calculate its location.  Again, the problem becomes simple if we are allowed to use algebraic manipulations, rather than being forced to express it as a constraint system.

Your "detailed version of the problem" is a different problem entirely.  If you have a complete graph -- or you have three points that are connected to all other points -- you can use the techniques outlined above.  (You can fix locations for those three points, and then derive the location of all other points using the methods above.)

But if you have an arbitrary graph, the above techniques might not be enough.  I don't believe your general problem can be expressed as a constraint program with only convex constraints: I think it's a non-convex problem.  I don't have a proof of that, though.


LL grammars and left-recursiviity Why LL(k) and LL(∞) are incompatible with left-recursion? I understand that a LL(k) language can support left-recursivity provided that with k-overahead tokens can be resolved any ambiguity. But, with a LL(∞) grammar, which type of ambiguities can't be solved?

The problem that $LL$ variants have with left recursion is inherent to the way $LL$ works: it is a top-down type parser, which means it replaces nonterminals by their productions.

An $LL$-style parser works as follows. It traverses the input from left to right in one go. If we are at some point in the input, then we know that everything to the left of this point is OK. For everything to the right of this point, the parser has constructed an 'approximation' of what it expects to see next. Consider for example this grammar:

  1: $E \to E + E$
  2: $E \to x$

Note that the grammar is not $LL$, but we can still parse inputs in $LL$-style. On input $x+x+x$, an $LL$-style parser may end up at position $x+\bullet x+x$. Let's assume it has decided that the left part, $x+$, is fine, and for the rest of the input it expects to see $x+E$. It will then find out that $x+x+$ is fine, with $E$ remaining. It may then replace this $E$ by a production, in particular production 2 above. With $x$ remaining, the parser will accept the input.

The trick is then to correctly decide the replacing production for a given nonterminal. A grammar is $LL(k)$ if we can do this by just looking at the next $k$ input symbols, and other techniques are known that are more powerful.

Now consider the following grammar:

  1: $A \to A a$
  2: $A \to \varepsilon$

If an $LL$ parser tries to replace $A$ by a production, it has to decide between production 1 and 2.

Let's consider what the proper course of action would be if our parser was omniscient. Every time it replaces the $A$ by production 1, it 'adds' an $a$ to what it expects for the remaining input (the expected remainder goes from $A$ to $Aa$ to $Aaa$...), but the $A$ at the start does not go away. Eventually, it must pick production 2, after which the $A$ disappears and it can never again add $a$s to the expectation.

As there is no chance to match a few more input symbols, the parser must decide at exactly that input position how many times production 1 must be matched. This means it must know exactly how many times in our case the $a$ will appear in the remainder of the input at this moment.

However, $LL(k)$ can see only $k$ symbols ahead. This means that if production 1 must be chosen more than $k$ times, the parser cannot 'see' this and so is doomed to fail. $LL(*)$ is better at parsing than $LL(k)$, because it can see arbitrarily far ahead in the input, but the crucial detail (which is not always mentioned) is that this lookahead is regular.

To imagine what happens, you can view the algorithm as follows: when it has to decide which production to take, it starts up a finite state machine (a DFA, which is equivalent in power to regular expressions) and lets this machine look at the rest of the input. This machine can then report 'use this production'. However, this machine is severely limited in what it can do. Although it is strictly better than looking at only the next $k$ symbols, it cannot for instance 'count', which means that it cannot help in the above situation.

Even if you were to 'hack' in some counting function in this finite automaton, then there are still left-recursive grammars for which you really need more power. For instance, for this grammar:

  $A \to A B$
  $A \to \varepsilon$
  $B \to ( B )$
  $B \to \varepsilon$

you would have to match 'towers' of matching braces, which is something a finite automaton cannot do. Worse still:

  $A \to B C A D E$
  $A \to A'$
  $A' \to A' D E$
  $A' \to \varepsilon$
  $B \to a B a \mid b B b \mid a a \mid bb$
  $C \to c C c \mid d C d \mid c c \mid d d$
  $D \to e D e \mid f D f \mid e e \mid f f$
  $E \to g E g \mid h E h \mid g g \mid h h$

is a totally awful grammar, for which I'm pretty sure no known linear time parsing algorithm works and all known general parsing algorithms take quadratic time. Worse still, any grammar describing this language is necessarily left-recursive. The grammar is still unambiguous however. You need a hand-crafted parser to parse these monsters in linear time.


Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random Let $G$ be a graph, and let $s$ and $t$ be two vertices of $G$. Can we efficiently sample a shortest $s$-$t$ path uniformly and independently at random from the set of all shortest paths between $s$ and $t$? For simplicity, we can assume $G$ is simple, undirected and unweighted.

Even in many restricted graphs, the number of shortest paths between $s$ and $t$ can be exponential in the size of $G$. Therefore, we would naturally like avoid actually computing all the shortest $s$-$t$ paths. I don't know about the general case, but it seems to me that we can achieve this for some special graph classes.

This feels like something someone must have considered before. Is there any existing research into this, or is this in fact simple to do even for general graphs?

I am not 100% sure this answer is correct, but here goes:
I think you can reduce this to uniformly random any-paths, from $s-t$, in a DAG with a single source and a single sink.
Given a graph $G$

Make a new empty digraph, $H$.
First: run the BFS part of Dijkstra's shortest-path, starting from $s$, mark all the nodes with their shortest-distance-from-$s$.
Let $d(s,v)$ be the minimum distance from $s-v$; which we know from the BFS step of Dijkstra's shortest-path algorithm.
Then do the next step of Dijkstra's shortest-path algorithm, obtain the shortest-path, store it in $\mathbf p$ (by going backwards from $t$ to $s$).
Now start the following loop; expanation in comments, and below:

$q_0=\{t\}$
While $q_0 \ne \emptyset$

$q_1= \emptyset$
For $u \in q_0$

So we want to find all possible next nodes for this shortest-subpath from $t-u$
For all $\text{edge}(u,v) \in G$ such that $d(s,v) < d(s,u)$

$v$ is a neighboring node, with less $d(s,\cdot)$ (it will be $1$ less)
Therefore, $t-u-v$ is possible subpath in a shortest path.
Put $v \rightarrow H, \text{di-edge}(u,v)\rightarrow H$
Now we need to check $v$'s lesser-neighbors next turn.
Put $v \rightarrow q_1$

Set $q_0$ to $q_1$:

$q_0 \leftarrow q_1$

Essentially, I am collecting all possible nodes that can be used in the shortest-path, and placing them in $H$.
More on how this works:

Dijkstra's shortest-path algorithm works by first running a BFS, and marking all the nodes $v\in G$ with their-shortest paths from $s-v$. The next step is to go back from $t-s$, and follow the least-neighboring nodes back.
The thing is, here you can choose any of the least neighboring nodes. What I do here is collect all the least-neighboring nodes each step, which means I account for all the shortest-paths.
Now you quickly think, but hey, why is enumerating them exponential, but my way is not?
The answer is, because I use a set to avoid adding the same nodes twice, I avoid recalculating this for each possible path.

Now we have a DAG that we can traverse in any way from $t-s$, and obtain a shortest-reversed-path from $s-t$. The graph should have $t$ as the only source, and $s$ as the only sink.

If the above is correct, then I think we can take this a step further and solve the problem as follows.
Give each node in the DAG a node-weight; the node-weight will be the number of paths from from that node to $s$. Let us call this $w(v)$.
You can compute these quickly, see Algorithm that finds the number of simple paths from s to t in G.
Once we have the node-weight, we can uniformly pick a path by:

Layout the DAG as a level-structure (for visualization)
At each level, choose an arbitrary ordering between the nodes ie. a notion of "left to right".
Traversing down the DAG: at each step $i$, $i \in \left[1,\left|\mathbf p\right|\right]$ (where $|\cdot|$ means size-of, in this case, the length of the shortest-path):

Let $u_i$ be the current node (starting at $t$)
Add up all the weights of the children of $u_i$, and using an RNG, choose one child node, $v_i$, uniformly between the weighted children.
Set $u_{i+1} = v_i$, and go to the next step


Size of tree decomposition Given a graph $G$ with $n$ vertices, let $(X, T)$ be a tree decomposition of $G$ with the smallest width. Is the number of nodes in $T$ upper bounded by $n$? I have googled it but all materials I found discuss only treewidth.

Not a complete answer, but in T. Kloks Treewidth you have the following lemma:

  There always exists a nice tree decomposition of width $k$ and with at most $4n$ bags.

It is NP-complete to determine the minimum number of bags in a tree decomposition of width $k$.


Why use languages in Complexity theory I'm just starting to get into the theory of computation, which studies what can be computed, how quickly, using how much memory and with which computational model.

I have a pretty basic question, but am really hoping some of you guys can help me understand the concept behind it:

  Why is everything centered around the notion and definition of
  LANGUAGES (i.e. regular languages and context free languages)? And how
  do these relate and describe the complexity of an algorithm and the
  possible computational models for solving them?

I read these sort of related questions:

https://cstheory.stackexchange.com/questions/14811/what-is-the-enlightenment-im-supposed-to-attain-after-studying-finite-automata
https://cstheory.stackexchange.com/questions/8539/how-practical-is-automata-theory

but still don't have an answer to my doubts, since they provide a practical justification of why they are important (which I do understand) but don't help me understand why complexity theory is based upon them.

It's because languages are the best (only?) way we have of formalizing the concept of a "problem."

An algorithm (Turing Machine) has performance, which we express via big-O complexity. A problem (language) belongs to a complexity class. These are usually defined by existence: if there exists a machine accepting a language $L$ which runs in given performance (space or time), then the language belongs to the corresponding complexity class.

There's a few reasons for this. First is that languages are platform independent. You're not worrying about whether an integer is 32 or 64 bits, or whether floating point operations run in parallel with other operations. These things give performance speedup at the micro-level, but complexity analysis is interested in the macro level. As you scale from 100 to $10^6$ to $10^9$ to $10^{12}$ inputs, how does the algorithm performance change? Does it go from using 1 million tape cells to 1 billion, or from 1 million to more cells than there are atoms in the universe?

The second is that languages are just a nice abstraction for data. You need something you can do proofs about, something you can model formally. Encoding your input and output as a string mean that you're now dealing not with bits in memory, but with mathematical objects with specific properties. You can reason about them and prove proofs about them in a formal, and very simple sense.

Complexity theory tends to be focused on decision problems because they end up being difficult. When the decision version of travelling salesman is NP-complete (i.e. is there a tour shorter than length $k$), then obviously finding the shortest path is harder. There isn't as much focus on function/optimization problems because there's still a lot of open questions and unsolved problems about the simpler decision problems.

I guess here's my challenge to you: find way to mathematically describe problems that isn't languages. I don't know if languages are special, but I think they're the simplest tool we've got, the easiest one to deal with.


Is there a way to predict rendering times? In purpose of load balancing I need to approximatively predict rendering time my graphics software (in the specific case it's Autodesk Maya) needs to render a task given an input file (.ma/.mb) and rendering parameters.

An intuitive way to do it is to render several frames from different parts of a scene and to extrapolate the results. Is there a better way to do it?
If no, is it enough to render several separated frames or I should take short series of frames in different moments of the scene?

You can predict it using Machine Larning / Data Mining algorithms, provided you have prior knowledge of the data. In your case,you should know the rendering time from previous experiments.

You can use any predition models. Some of them like bayesian models gives high accuracy prediction,but are computationally complex. Statistical models are very fast,but the provide less accurate results. You can use decision tree based models for a balanced performance.
CART algorithms is a good one. Use any datamining tools like weka,Rstudio or rapidminer to make the job easy.


An $\mathbb F$-algebra as input to an algorithm I want to specify, what it means to give an algebra as input to an algorithm and didn't find very much literature about it. So first I want to ask if you can recommend a book or paper that deals with the topic of complexity analysis of algebras over fields and clearly define the decision problem.

After some digging I found something and want to share it here and furthermore ask if the definitions make sense and are in compliance with literature (if there is any):

  Definition: Let $\mathbb F$ be a field and $A$ be a finitely generated commutative $\mathbb F$-algebra with additive basis $b_1,\ldots, b_n\in\mathbb F$. We now want to capture the multiplicative structure of the algebra and therefore write every product of base elements as a linear combination of all base elements:
  $$
\forall 1\leq i, j, k\leq n: \exists a_{ijk}: b_ib_j=\sum_{k=1}^n a_{ijk}b_k.
$$
  The $a_{ijk}$ are called structure coefficients. We directly have that:
  $$ A \cong \left.\mathbb{F}[b_1, \ldots, b_n] \middle/ \left<b_i b_j-\sum_{k=1}^n a_{ijk}b_k\right>_{1\leq i,j\leq n}\right..$$
  Now one can define the following decision problem:
  $$
\{(A,B)\mid A, B \text{ commutative $\mathbb F$-algebras with basis $b_1, \ldots b_n$ and } A\cong B\}.
$$
  To specify an isomorphism $\phi:A\rightarrow B$ it is sufficient to write every $\phi(b_i)$ as linear combination of the elements of a basis of $B$.

Does anything in this definition seem strange to you or do you think that one can work with it?

  Motivation: My motivation behind this is to give a very clear definition of the decision problem first to connect it to other problems, i.e. the problem of deciding polynomial equivalence: Given two polynomials $f,g\in\mathbb F[x_1, \ldots, x_n]$, we say that $f$ is equivalent to $g$ if there exists an invertible linear transformation $\tau$ on the variables such that $f(\tau(x_1), \ldots, \tau(x_n))=g(x_1, \ldots, x_n)$. In other words, two polynomials are equivalent if you can replace every variable by a linear combination of all variables to obtain the other polynomial.

I'm not sure if this helps as a motivation but the connection of this problems is established by constructing finitely generated commutative $\mathbb F$-algebras from the two polynomials that are isomorphic if and only if the polynomials are equivalent. For this I wanted to make sure that the decision problem is defined very clearly.

This seems to be consistent with the presentation in Equivalence of $\mathbb{F}$-algebras and cubic forms, Agrawal & Saxena (2006).


Is there a name for a graph whose vertices consist of edges of an existing graph connected by an edge if they shared a common vertex? I was wondering if there is a name for this construction:
Take a graph $G$ and construct a new graph $G'$ in which the edges of $G$ now become vertices, and "vertices become edges" in the sense that vertices are joined by edge in $G'$ if they as edges in $G$ shared a common vertex.

More precisely:
Given a graph $G=(V=\{v_1,v_2,\dots,v_n\},E=\{e_1,e_2,\dots,e_k\})$ where each $e_i=\{u,v\}\subset V$ we define the graph $G'=(V'=\{e_1,e_2,\dots,e_k\},E')$ so that $\{e_i,e_j\}\in E' \iff e_i\cap e_j\neq\emptyset$.

I don't know if this can be used for anything (my guess would be it can't) it just came to my mind and thought that perhaps this has a name.

This is called the line graph of $G$. It actually has a wide variety of uses, as seen on that Wikipedia page, and the terminology is sufficiently standard that you should be able to mention it in a paper without defining it.


How to test for overflow when multiplying floats I am trying to implement a 3-term recurrence relation:
$$
p_{n+1} = ap_n + bp_{n-1}
$$
This can be implemented as

  p0 = P0 // starting value p_0
  p1 = P1 // starting value p_1
  loop n = 2,...,N
    pn = a*p1 + b*p0
    p0 = p1
    p1 = pn

Depending on $(a,b)$ and also the stopping point $N$, this can sometimes overflow, and I would like to detect such a failure. I believe it is bad form to simply let the loop run to completion and then use something like isfinite to check the final value.

A more elegant method would be to somehow test whether the term a*p1 + b*p0 will exceed the floating point maximum (DBL_MAX = 1.7976931348623157e+308) prior to computing it. I could not find much information about this online, so does anyone have suggestions?

One idea I had, was suppose we are just dealing with the first term $a p_n$. Then we could test:
$$
\log{|a p_n|} > \log{\textrm{DBL_MAX}}
$$
or
$$
\log{|a|} + \log{|p_n}| > \log{\text{DBL_MAX}}
$$
It seems that this test would work even if $a p_n$ is not representable as a floating point number. I'm not sure how to extend this test to the general case $a p_n + b p_{n-1}$, or even if this test will account for all possible failure cases in double precision.

I want to further emphasize and underscore gnasher729's comment which is completely correct. NaN and Infinity were added exactly so you wouldn't need to do such checks all the time. That is, they were added to you wouldn't need to do exactly the thing you are suggesting doing. One of the consequences is that it often is the right thing to do to just blindly continue a calculation, checking whether it has overflowed or produced NaN only when you need to make a decision based on the result.

There are at least a few reasons it is this way. First, as you are starting to see, it can complicate your code quite a bit to attempt to preemptively detect potential errors. Second, such checking code tends to significantly slow down computation1. This is especially bad as the vast majority of the time you will not overflow, and so these checks are just wastes of time. Adding early abort code is then optimizing for a very rare case at the significant expense of the vastly more common case. Third, many aspects of IEEE754 have been carefully designed to behave sensibly even in "error" cases. Often this allows correct results despite overflows in intermediate calculations and allows even more error checking code to be eliminated as well as expanding the domain of operations. For example, dividing a finite number by Infinity doesn't cause an error but instead produces a (signed) 0, which is likely the desired result.

So, to reiterate gnasher729's comment, the way you test for overflow when multiplying IEEE754 floating point numbers is by multiplying them and then checking whether they've overflowed. And you shouldn't even do that that often. You should only check for overflow when you need to make a code branch based on the decision2, and otherwise you should just let the error values propagate.

1 This especially true for SIMD architectures such as GPUs. GPUs are much happier doing the same thing to a bunch of data in parallel than doing different things in data dependent ways.

2 These code branches may be hidden, e.g. while calling a print routine may not require a branch in your code, there is one in the print routine to know whether to display "Infinity" or not. Therefore, you should check for overflow before printing assuming you want a behavior other than printing "Infinity", et cetera.


Algorithm for smallest String without a given prefix How can I find the lexicographicaly smallest string that doesn't start with a given prefix AND is lexicographicaly bigger than the given prefix? Example:

prefix : cat;
next string : cau
prefix : cazz
next string; cb

There is no solution if all characters in the input string are equal to the last character in the alphabet (this includes the case of the empty string).

Otherwise, as long as the last character in the input string is the last character in the alphabet, remove it from the string. Then replace the last character of the result with the next character in the alphabet.