LP - given m constraints for 2 variables find maximal radius of circle Given $m$ constraints for 2 variables $x_1,x_2$ :

$d_ix_1 + e_ix_2 \leq b_i$ for $i = 1,...m$

need to create a linear program that finds the maximal radius of a circle such that all the points inside the circle are in the feasible range of the above constraints.  The circle can be located anywhere -- not necessarily centered at the origin.

so I know the formula for distance between some $(x,y)$ and some $ax +by + c = 0$

then I have tried -

$Maximal$ $R$ s.t
$d_ix_1 + e_ix_2 \leq b_i$ for every $i$
$R \leq |d_ix_1 + e_ix_2 - b_i| / {\sqrt{{e_i}^2 +{d_i}^2}}$   for every $i$
$R \geq 0$

I know the standard linear program doesn't get absolute value function but obviously we can just have 2 inequalities to get rid of it.

I'm not sure if this is the correct answer.

furthermore, is it possible that for some constraints if will force the radius to be 0?

You're close to the solution, but aren't there yet. Your third inequality should look like this (no absolute values!):

$$d_i x_1 + e_i x_2 + \sqrt{{e_i}^2 +{d_i}^2}R \le b_i$$

And yes, the maximal inner circle radius can be zero, and even more - this circle might not exist at all. Please see the following explanation to grasp that.

Let's use vector notation to simplify algebraic expressions:

$$a_i=(d_i,e_i)$$
$$x=(x_1,x_2)$$

Then your constraints can be written using Dot Product:

$$a_i \cdot x \le b_i,  i \in [1,m]$$

Let's denote the inner circle center $y$ and focus on the $i$-th constraint for now. Imagine a shortest segment, connecting the point $y$ and the line $a_i \cdot x = b_i$. It's easy to see that this segment will be perpendicular to this line and collinear with vector $a_i$.

Let's find the point $z_i$, lying on the segment above, with the distance from the point $y$ equal to the $R$ (radius of the inner circle). This point is given by the following vector expression:

$$z_i = y + \frac{a_i}{\lVert a_i \rVert}R$$

Now we have to make sure that all the points $z_i$ are located in correct halfplanes:

$$a_i \cdot z_i \le b_i,  i \in [1,m]$$

Simplifying these equations using the expression for the point $z_i$ (above) we'll get:

$$a_i \cdot y + \lVert a_i \rVert R \le b_i,  i \in [1,m]$$

So, now you have an LP problem with three variables $(y_1, y_2, R)$, $m$ constraints (above), an additional constraint $R \ge 0$ and optimization function, which is simply $R$.

Please see the Chebyshev Center page for more information, in particular the reference #4.


Algorithm for Graph merge and recompute I want to construct a complete graph where each node is connected to every other node. The link between the nodes give a distance function (does not follow triangle inequality) between them. What I require is to merge the closest nodes, (bounded by a threshold) into a single node and recompute the graph each time, recursively. This is because if two nodes are merged, then all the links connected to the new node has to be updated with the newly computed distance for the new edge. Since its a complete graph this would be an expensive operation.

I would have a large number of nodes with $N*(N-1)/2$ links for $N$ nodes , and $N=60$ or more ,
What I want to do is to reduce this complete graph into clusters of  sub graphs with low intra node distance, yet with a relatively high distance between the subgraphs. So,How can I go about solving this problem?

This is like applying the graph partitioning techniques to complete graphs.

One of the solutions is this paper which proposes the normalized cut criterion for partitioning the graph  minimizing normalized cuts on graphs which is clearly NP-complete,Is there a practically efficient way and what are the recent developments to achieve this?

So what I want is an efficient solution to the above problem which is not NP complete ? Since this problem is NP Complete , answers using randomization or approximation methods would be welcome

I suggest you start by reading about standard clustering algorithms and methods for clustering.  You could start with Wikipedia: cluster analysis and hierarchical clustering, then move on to textbooks or online resources.  Especially, check out hierarchical clustering to see if any of its methods might do what you want.

It sounds like you're not quite sure what you want.  So, if you learn more about standard clustering methods, you might be in a better position to formulate a narrower, more focused question -- or if you're lucky, maybe you'll find a solution you're happy with.


An algorithm to check if two DFA are disjoint What is the algorithm to check if two DFA are disjoint? I want to know if there exist any string accepted by both automata.

Construct the intersection DFA of both DFA's. Then, check if there is a path from the starting state to any end state.
If there is a path, then the two DFA's are not disjoint. If there isn't, then they are.


Algorithm for solving planar constraint problem ("Pokemon Go monster finding") [Note: This problem was inspired by Pokemon Go. I will first explain the problem in mathematical terms, then explain the connection to Pokemon Go. My goal is not to cheat in the game. If I wanted to cheat, better information would be available more easily.]

Suppose there are $N$ points (the "unknown points") in a plane, call them $n_1,\dots,n_N$, with unknown coordinates. Moreover, we have $M$ measurements taken at known locations $m_1,\dots,m_M$.

Let $\text{dist}(m_i, n_j)$ be the (generally unknown) Euclidean distance from measurement point $m_i$ to the unknown point $n_j$.

For each measurement $m_i$, we have the following information:

The exact coordinates of each unknown point $n_j$ for which $\text{dist}(m_i, n_j)<d_\text{min}$ for some known constant $d_\text{min}$; and
A list of all indices $j$ for which $\text{dist}(m_i, n_j) < d_\text{max}$ for some known constant $d_\text{max}>d_\text{min}$, sorted by $\text{dist}(m_i, n_j)$.

Is there an efficient algorithm for calculating the areas of the plane where the unknown points, or a given unknown point $n_j$, can be?  The algorithm is given the coordinates $(X_i,Y_i)$ of the measurement points, the measurement information listed above, and the number $N$ of unknown points; the goal is to narrow down the region of possible locations for each of the unknown points $n_1,\dots,n_N$ as much as possible.

The Pokemon connection:

In Pokemon Go, an augmented reality game, the goal is to find Pokemons in nature. Every now and then, the game shows the Pokemons in a "visible range" ($d_{min}$) of the player's position. Moreover, it has a "Pokemon finder" which shows a list of nearby ($dist<d_{max}$) Pokemons, sorted by distance. (It's also supposed to show an approximate distance as one, two or three footsteps, but apparently there's a bug and it always shows three footsteps.)

I think you could use a "spatial join". I haven't played the game, but I assume $d_{max}$ is rather small, i.e. there are in the order of 10 or so $n$ and $m$ in the neighborhood of each $m$. I further assume that $N$ and $M$ are large, say 1,000,000 or more.

Put all $m$ as 2D points in a spatial index
For each $m_1$ in the index, perform a spatial range query with distance $2*d_{max}$. This gives you all other $m_x$ that can potentially contain the same $n$ as $m_1$. This should be manageable because the number of $m_x$ should be small (as I assumed above).
Now, by getting all other estimated measurements for a particular $n$, you can try to approximate the correct $n$
(Potential optimisation): Depending on your spatial index, you can remove the $m_1$ after processing all it's $n$. This makes the dataset smaller for the following range queries. Also,

Somehow you would also need to uniquely identify each $n$, so that you don't calculate the position of $n$ again if it turns up when processing another $m$.

As an optimisation, you may want to use window queries (rectangular) rather than circular range queries. Window queries can be much faster and give only slightly more results. Also, it could be that the game actually does not use euclidean distance (circles) but the faster manhatten distance, which would be exactly a rectangle.

For such a spatial join you can use any spatial index, such as R-Tree, kd-Tree, quadtree or any of their variants.

For large datasets I would probably not use a R-Tree (R+tree, R*-tree, X-Tree), or a special variant of the quadtree, the PH-Tree, which is well suited for range queries as well as allowing fast removal (or addition) of points.

For Java, implementations of R-Trees can be found in the anywhere on the internet, for example in the ELKI framework or my own TinSpin Index library. The PH-Tree is also available in Java.

A generic spatial join algorithm is called TOUCH, but I don't think it is open source.


Designing a greedy scheduling algorithm for two sets of non-mutually exclusive tasks Lets just say I have two lists of the running time of tasks A and B. Formally, I would have:

A = {a_1, a_2, a_3 ... a_n}
B = {b_1, b_2, b_3 ... b_n}

I can only have one task from A running at any one time. All other tasks in A have to wait on that task to complete before they can be released. I can have any amount of tasks from B running at any one time, however I cannot run a task from B if its equivalent task from A has not finished. For example, I could not run b_1 if a_1 had not finished beforehand.

To put this in an analogy, say that I have some athletes who will perform a di(duo?)athlon: they will run laps on a running field then cycle for some distance. Only one athlete can be running laps on the field at any one time, and only after he or she has finished can he or she proceed to cycling. Any amount of athletes can be cycling at any one time. In this case, A would be the amount of time I know an athlete will take to run their laps around the field and B would be the amount of time I know it will take them to cycle the required distance.

I would like create an algorithm which devises a schedule for my tasks (or for my athletes) so that the total time it takes for all of them to complete their activities is kept to a minimum.

The basic jist is this: The time it takes for any individual athlete to complete their tasks is running_time + cycling_time + waiting_time. The running and cycling times I know, while the waiting time would be the sum of all running times of all athletes prior to the current one, i.e. For some athlete a_i the waiting_time = a_1 + a_2 + a_3 + ... + a_(i-1). Intuitively, I would like the athletes with shorter running times and longer cycling times to go first since I want to maximize the amount of athletes cycling at any one time.

My question is: how would I go about doing this? How would I schedule my tasks (athletes)?  Obviously, I could go about computing every single possibility and picking the best one, but that would result in some ludicrous O(2^n) algorithm. Subsequently, (it seems?) a greedy algorithm would be the best choice.

EDIT: A few days later.

The way (again, I believe) that seems to be the most optimal is this:
Let a_max = a_1 + a_2 + ... + a_n - a_i. Informally, this is to say that a_max is the worst-case waiting time for a task/athlete i. Then, let completion_time_for_i = a_max + b_i. We compute completion_time_for_i for each task/athlete and order it in a descending fashion. That is to say, tasks/athletes with larger completion_time_for_i will be up a the top of the schedule, while tasks/athletes with lower completion_time_for_i will be lower down on the schedule.

The point is that a_max is larger the smaller a_i is and completion_time_for_i will be largest for tasks/athletes with the greatest difference between their running and biking times. Hence, we are doing what intuition suggests: putting the tasks/athletes with shorter running times and longer biking times first.

Of course, I cannot escape the math, can I? I'm not even entirely certain where to start my proof to show if this algorithm is "correct". I guess it would be something along the lines of: my schedule takes x time. The greedy algorithm is incorrect if there exists a y such that y > x. However (assuming that my algorithm is correct) I cannot construct a schedule which takes y time and hence the proof by contradiction (as suggested in the link from @D.W.).

Nice exercise!

The usual strategy for designing greedy algorithms is to just brainstorm a bunch of different candidate strategies.  You're going to sort by some quantity; try some ideas for what that quantity might be -- maybe it is sorted by $a_i$, or by $b_i$, or by $a_i-b_i$, or something; try to come up with as many possibilities that make sense.  Then, for each candidate strategy, test whether it appears to be correct using the methods in How to prove greedy algorithm is correct.

Try that for a little while.  If you're still stuck, here's an extra hint (don't look until you've tried the above):

   See if you can figure out which of the $n$ items must come last.


Does "contains only" imply "contains"? Written in English, does "the set S contains only members of set T" imply that S does contain some member of set T?

How would this relationship be written formally?

My view is that vernacular would consider that S is not empty,
i.e. $\emptyset \neq S\subseteq T$, while mathematical language would
consider that S can be empty, i.e. $\emptyset\subseteq S\subseteq T$.

Lay people do not speak of empty sets, while mathematicians are
aware of their role in their work.

That means that the sentence is not ambiguous, but the meaning depends
on the community where it is used.

Of couse, people aware of the two readings can play games with it. But
that is yet something else.

You may notice that I did not specifically mention English, because
the same is probably true of many "languages".

To think that English  (or German, or French) is a well defined language is
unrealistic. Actually, I doubt you can find two people who
agree on what is English and the meaning, or on the ambiguity, of its sentences,

It might be interesting to ask the linguists.


On Plus of empty string We know $L^+=L^\star\backslash\{\epsilon\}$. How do we interpret that $\{\epsilon\}^+=\{\epsilon\}$?

Your first definition only holds if $\epsilon \notin L$.

The Kleene star and plus are defined using recursive sets $V_i$. We have:

$$V_0 = \{\epsilon\}$$
$$V_1 = L$$
$$V_{i+1} = \{ vw : v \in V_i \wedge w \in L\}$$

Then:

$$L^* = \bigcup\limits_{i=0}^{\infty} V_i$$
$$L^+ = \bigcup\limits_{i=1}^{\infty} V_i$$

Note that $L^+$ omits $V_0 = \{\epsilon\}$, but does not subtract $\epsilon$ from $L$.


Balanced weight distribution into buckets, but with a twist (aka sharding a list into k even shards) Is there an existing algorithm that can solve the following problem?

Problem

Given an list N comprised of integers of various values, shard the list into k buckets such that:

The sum of the integers in each bucket are roughly evenly divided (as much as possible
Only consecutive integers are placed in the same bucket

Example:

Given k (the number of buckets) = 4

List N = [4 1 2 6 19 1 10 3 2 2]

A Valid Solution

[4 1 2] [6] [19] [1 10 3 2 2]

(Since the bucket weights add up to 7, 6, 19, 18)

An Invalid Solution

[1 1 2 2 2 3] [1 4 6] [10] [19]

(Where the bucket weights would add up to 11, 11, 10, 19)

It's invalid because the buckets no longer contain only numbers that were adjacent in the original list.

Thanks!

Yes, this can be solved as a straightforward application of dynamic programming, once you define an objective function to measure how "evenly divided" the buckets are.  Let $A[j]$ denote the value of the objective function for the best way to split integers 1..j.  Then you can compute the value of $A[j]$ given the values of $A[1],\dots,A[j-1]$ (you just consider all possibilities for how many integers go in the last bucket), so there is a dynamic programming algorithm with running time at most $O(n^2)$.

This problem is sometimes called the Linear Partition Problem, and a solution can be found in Section 8.5 of Skiena's "Algorithm Design Manual".


Dynamic Programming Help Sometimes I can see the recurrence relationship and other times I cannot. This is one of those times. I've gone through a few iterations of trying to solve it but I also find a set of values where my idea fails. If I go exponenetial I can figure it out... but that's a specific no-no.

I'm good with nudges in the right direction. Please make it a little strong though.

Problem

Suppose it’s nearing the end of the semester and you’re taking n courses, each with a final project that still has to be done. Each project will be graded on the following scale: It will be assigned an integer number on a scale of 1 to g > 1, higher numbers being better grades. Your goal, of course, is to maximize your average grade on the n projects. You have a total of H > n hours in which to work on the n projects cumulatively, and you want to decide how to divide up this time. For simplicity, assume H is a positive integer, and you’ll spend an integer number of hours on each project. To figure out how best to divide up your time, you’ve come up with a set of functions{fi :i=1,2,...,n}(rough estimates, of course) for each of your n courses; if you spend h≤H hours on the project for course i, you’ll get a grade of f_i(h). (You may assume that the functions f_i are nondecreasing: if h' < h, then f_i(h')≤f_i(h).) So the problem is: Given these functions{f_i}, decide how many hours to spend on each project (in integer values only) so that your average grade, as computed according to the fi, is as large as possible. In order to be efficient, the running time of your algorithm should be polynomial in n, g, and H; none of these quantities should appear as an exponent in your running time.

When you encounter these types of problems, the typical thing to do is to find some "decision scheme" that can decompose your big problem into a series of smaller problems. The gist of this problem is finding a set $(h_1, \dots, h_n)$ that maximizes your mean grade $\frac{\sum_{i \le n} f_i(h_i)}{n}$ subjected to the constraint that $\sum\limits_{i \le n} h_i \le H$. Notice that maximizing $\frac{\sum_{i \le n} f_i(h_i)}{n}$ is equivalent to just maximizing $\sum\limits_{i \le n} f_i(h_i)$ since the denominator $n$ is independent of the choices of $(h_1, \dots, h_n)$ that we make.

Now, there are various dynamic programming schemes that we can choose to solve this problem, each of which depends on some special interpretation of an "optimal functional" that we define. For me, the intuitive one is based on the idea of variable elimination, in which we eliminate one of the variables $h_i$ at each turn.

Here, let $\textrm{Best}(k, h)$ denote the maximum cumulative grade you can gain for the classes $C_k, C_{k+1}, \dots, C_n$ so that you spend no more than $h$ hours on all of their final projects. Given this interpretation, it is clear that our problem is to find $\textrm{Best}(n, H)$.

Now comes the fun/interesting part. First, we need to convince ourselves that this functional displays what we would call an "optimal substructure." In layman's words, this claims that if we know the best distribution of no more than 5 hours to Networking and Programming Languages' final projects, then we also know the best distribution of 8 hours to the Networking, PL, and OS' final projects if we decide to allocate 3 hours to the OS project. It's simple, we just use the same optimal budget of 5 hours for Networking and Programming languages that we already have.

In other words, this optimal substructure property guides us on the decision we have to make at each turn (because we don't have to worry about the subproblems). Here, $\textrm{Best}(k, h)$, according to the substructural property we've introduced above, must make a decision on what $h_k$ should be assigned. In addition, it must

Ensure that $h_k$ does not exceed its allocated hours of $h$, and
Maximize the grades contingent on the choices that it can make.

Therefore, when we consider the problem of computing $\textrm{Best}(k, h)$, there's a range of valid decisions that we can make, each corresponds with an assignment of a single value to $h_k$. For example, say I'm considering $\textrm{Best}(\textbf{Networking}, 5)$, which corresponds to the maximum cumulative grade that I can get in classes Networking, PL, and OS with only 5 hours to distribute between them. Now, I have to make a decision about how I will budge for Networking. Say I budget exactly 0 hours to networking, then I can spend 5 hours on PL and OS; alternative, I can budget 1 hour to networking and spend 4 hours between PL and OS, 2 hours to networking and 3 between PL and OS, etc. Each choice of time budget for Networking also determines a subproblem that I have to solve between PL and OS with the remaining time. Once we consider all of these choices (and subproblems), we must then commit to the problem that will give us the best solution.

This thought process should yield a recurrence for Best that can be computed in some increasing order of its parameter. This computation then takes the form of a tabulation over an $n \times H$ grid, each time spending approximately $O(k)$ (where $k \le n$ is the column number) time between the $O(k)$ choices, which gives an $O(n^2 H)$ algorithm.


Minimum amount of time for two enemies to reach their destinations? Given an undirected, unweighted, and connected graph $G = (V, E)$, what is the minimum amount of time it takes for party $X$ to go from $s_x$ to $t_x$ and party $Y$ to go from $s_y$ to $t_y$? At each unit of time, $X$ and $Y$ can either move to a vertex adjacent to their current position or not move at all. $X$ and $Y$ are enemies with each other and if they go less than a distance of $k$ to each other they will go to war. The distance of $X$ and $Y$ is defined as the number of edges between them on the shortest path. What is an efficient algorithm to find the two optimal paths such that $X$ and $Y$ do not go to war and they both reach their destinations in the minimum amount of time? Note that the two paths can share edges as long as $X$ and $Y$ do not go less than k units of each other during their traversal. In the example below with $k$ = 1 the optimal path for $X$ is in blue and y is in red. This allows for both $X$ and $Y$ to reach their destination in two units of time Notice, if $X$ instead took the black path, this would be suboptimal as $Y$ would have to rest for one unit of time as $X$ moved out of the way. (This would take 3 units of time.)

So far I've started by computing the shortest paths between all pairs of vertices in $V$ by doing a BFS at each vertex. This will take $O(EV)$
Then, I suggest the following greedy algorithm:

At each time tick, $X$ and $Y$ should move to the vertex that is closest to their destination. If that vertex is less than k edges from the other party, choose the next closest vertex and so on. If no such vertex exists, then the current party will rest until the other party moves at least k units away from any of the adjacent vertices. Give priority to $X$ or $Y$ based on who has fewer options.

However, I don't think the greedy solution will work. Some other ideas include A* or a max flow reduction.

Generate the graph $G'$ of all legal configurations. A legal configuration is an ordered pair of vertices $\langle u, v \rangle$ in $V^2$ such that $d_G(u,v) \ge k$, where $d_G(u,v)$ denotes the distance between $u$ and $v$ in $G$.

There is an edge from $\langle u_1, v_1 \rangle$  to $\langle u_2, v_2 \rangle$ in $G'$ if and only if $d_G(u_1, u_2) \le 1$ and $d_G(v_1, v_2) \le 1$.

The amount of time you are looking for is now equal to $d_{G'}(\langle s_x, s_y \rangle, \langle t_x, t_y \rangle)$.


Clarification for binary search in solving optimal TSP when a polynomial algorithm with a budge exists Below is Question 8.1 in Algorithms by Dasgupta et al.

There's a solution to this problem that uses binary search from here. Pasting the answer for posterity.

My questions are:

When they say input size, are they just referring to edges or both
edges and vertices?
Is it correct to say that we make at most $log( |E| log K)$ calls?
Does this work if the edge weights aren't integers, like 10.4 etc?
Why is this NP-Hard as the solution mentions? I thought that Traveling Salesperson Problem was NP-Complete

This question on stackoverflow asks for clarification of binary search use but doesn't answer the above question.

Input size refers to memory size needed to represent the input. In this case, it means number of edges + number of vertices, and you could also add size of the weights (which is logarithmic in their values).
No. It is written that we do $\log T$ calls and $T \leq |E| K$ (and this value can be reached), so the number of calls is at most $\log (|E| K) = \log |E| + \log K$.
Yes. It is never used in the algorithm that weights must be integers.
A $NP$-complete problem is a $NP$-hard problem which also needs to be in $NP$. So when speaking about a $NP$-complete problem, it is not false to state that it is $NP$-hard. However, $NP$ is a set of decision problems, therefore, TSP-OPT being an optimization problem cannot be in $NP$. We can still speak about $NP$-hardness as it can be informally defined for a non-decision problem as "a problem more difficult than all problems in $NP$". When you say "I thought that Traveling Salesperson Problem was NP-Complete", it refers to the decision version, denoted TSP in your reference.


how to create tokens from CFG i have a context free grammar

i  want to create a tokens from the language

is there any techniques to do that ?

for example , this CFG from Prof.Alex Aiken notes :

 D -> D ; P | D

 D -> def id(ARGS) = E ;
 ARGS -> id, ARGS | id
 E -> int | id | if E1 = E2 then E3 else E4 | E1 + E2 | E1 - E2 | id(E1,...,En)

how can i crate the tokens ?

the professor explain how i do that in some inputs

for example , if i have the input :

x = 10

then i have

<id.,x> < opp., = > ......

but how i can do that from the CFG

thank you All

The problem of creating a parse tree given a grammar and a word generated by it is known as parsing. The CYK algorithm parses all context-free grammars, but is slow. In practice, only restricted types of context-free grammars are used, and these can be parsed in linear time. The common example is LALR parsing. Perhaps you will learn more about this topic in due time.


What is the complexity of this matrix transposition? I'm working on some exercises regarding graph theory and complexity.
Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically I just have to give an algorithm to transpose an $N \times N$ matrix.

My first thought was to loop through all rows and columns and simply swapping values in each of the $M[i,j]$ place. Giving a complexity of $O(n^2)$ But I immediately realized there's no need to swap more than once, so I can skip a column every time e.g. when I've iterated over row i, there's no need to start iteration of the next row at column i, but rather at column i + 1.

This is all well and good, but how do I determine the complexity of this. When I think about a concrete example, for instance a 6x6 matrix this leads to 6 + 5 + 4 + 3 + 2 + 1 swaps (disregarding the fact that position [i,i] is always in the right position if you want to transpose a $N \times N$ matrix, so we could skip that as well).
This looks alot like the well-known arithmetic series which simplifies to $n^2$, which leads me to think this is also $O(n^2)$. There are actually $n^2/2$ swaps needed, but by convention the leading constants may be ignored, so this still leads to $O(n^2)$. Skipping the i,i swaps leads to $n^2/2 - n$ swaps, which still is $O(n^2)$, but with less work still..

Some clarification would be awesome :)

You can also "transpose" a matrix in $O(1)$ time and space. Maintain a bit $t$ for your matrix $M$. Whenever $M$ is transposed, flip $t$. Now, consider accessing an entry in $M$. If $t$ is set to true, return $M[j,i]$ instead of $M[i,j]$. This trick is arguably cheating, but not always is the matrix actually needed to be transposed. This might work nicely depending the situation.


Non-regularity of the set of primes in unary encoding using Myhill-Nerode I have found many proofs for this using pumping lemma, I'm curious of how to proof it via Myhill-Nerode theorem.

Suppose $L= \{a^p \mid p \text{ is prime}\}$ is regular. Then we have congruence such $u ∼ v ⇒ uw ∼ vw$ of finite index $k$, so it has $k$ equivalence classes. $L$ is union of some of its equivalence classes.

Let's choose $aa,aaa,...,a^{p_k},a^{p_{k+1}}$, where $p_k$ is $k$-th prime. Then, there exists $i,j$ from $\{1,...,k+1\}$, that $a^i∼a^j$. Now we should concatenate some word to $a^i$ and $a^j$, that one of the words is in $L$, while the other is not, but in contradiction, they are in the same equivalence class.

Any ideas?

We can prove that every string in $L$, $a^p$, $p$ is prime, is in its own different equivalence class. We simply cannot have two strings, $a^p$ and $a^{p'}$, both $p$ and $p'$ prime, in same equivalence class.

Assume $a^p$ and $a^q$, $q>p$, $p$ and $q$ prime, are in same equivalence class. Then since $a^{p}a^{q-p}=a^q$ is in $L$ therefore $a^qa^{q-p}=a^{2q-p}$ will be in $L$. Since $a^{p}a^{2q-2p}=a^{2q-p}$ is in $L$ therefore $a^qa^{2q-2p}=a^{3q-2p}$ will be in $L$. We will be able to show that $a^{p+i(q-p)}$ will be in $L$ for every $i \geq 0 $. But for $i=p$ there is a contradiction.

Factually speaking even $a^c$ and $a^d$ for composites $c$ and $d$ will be in different equivalence classes. If we assume $a^c$ and $a^d$, $d > c$, where $c$ and $d$ are not primes, are in same equivalence class, then we can similarly reach a contradiction. Even if we don't prove this, the number of equivalence classes is still infinite because each $a^p$ for prime $p$ is in different equivalence class.

Thus as number of equivalence classes for $L$ is infinite (because number of primes is infinite), therefore by Myhill-Nerode theorem $L$ is not a regular language.


provably optimal search algorithms? In practical applications, search algorithms are often strengthened using heuristics. e.g., Deep Blue beat gary kasparov by searching through possible chess moves by "guiding" its search with human-chosen heuristics. These heuristics are not proven to be the optimal heuristics.  (they're not optimal obviously).

I am wondering however:

  Is there some kind of search problem (ideally a non-trivial one), where (1) there is a specific known algorithm that solves it, and (2) a proof that the algorithm is optimal in the sense that there does not exist an algorithm that solves it faster in expectation, where (3) the probability distribution for that expectation is the relevant one for that practical search problem?

I'm interested in anything related to this. If you know something that seems partially relevant, please say so.

EDIT: Alternatively, please suggest a different notion of "optimality" if you think it is more relevant. I am not sure how relevant my notion of optimality is.

EDIT 2: I'm also interested in how this question relates to the 'No free lunch' theorems in search and optimization.

Finding an optimal solution for a problem is very difficult. for example in sorting you can prove that the optimal solution with comparison is $O(n \log n)$ but may be you can find an algorithm with $O(n)$ without comparison like hashing! another good example is NP Complete problems we even can't prove they haven't polynomial algorithm. so it is very hard to find an optimal solution for deep blue and similar algorithms and proving that the algorithm is optimal is very hard too.


Is it possible for a Turing machine to halt without reading the complete input string? Is it possible for a Turing machine to halt without reading the complete input string. Suppose there is a string "adc" preceded and succeeded by infinite number of blanks. Can a Turing machine halt after reading just "a" and never touching "dc" or any of the blanks. If yes, will this string be accepted or rejected?

Nothing special happens if the Turing machine doesn't read the entire input. For example, the machine can halt immediately, without looking at the input at all. If the Turing machine halts at an accepting state, then the input is accepted. If it halts at a rejecting state, then the input is rejected. In this way you can construct a Turing machine that accepts all inputs or that rejects all inputs, in both cases without looking at the input string at all.

In your example, the machine accepts "adc" iff it accepts "a".


Can nested structures be encoded more "readably" with a single delimiter? Imagine you have two systems of delimiting.  One with paired delimiters, [ and ]:

 [abc]

Then another system which uses a single interstitial delimiter, /:

 a/b/c

It's easy to see how to encode structure in the first case, as they nest cleanly:

[ab[cd[e]f]]

But let's say you are looking to encode arbitrary nested structures in the second scheme, using only some number of interstitial delimiters.  Whatever the encoding winds up being, a/////b//c////d///e///f would be an example of "following the rules", while //a//b/c///d///e///f/// would not.

So you're basically able to put a unary-encoded integer from 0..∞ (let's say 0 is /, 1 is //) between your elements.

It's obviously possible to encode, though the results won't necessarily be pretty or visually intuitive.  One way would be to consider you have two factors to record at each step.

Whether a nesting level is being entered or not for the ensuing token or if it's going to stay the same.  So for a?b, we want to know ...a[b... or ...ab...
how much of a nesting drop the ensuing token has after it.  So for d?e, we want to know e.g. ...d[e]... or ...d[e]]... or ...d[e]]]

The first is just a yes or no, and the second is a number which can range from 0 to however many nesting levels you've gotten so far.  So multiply the nesting level to drop by 2, add 1 if you're going a level deeper in and leave it alone otherwise.

[ab[cd[e]f]] => a 0 b 1 c 0 d 3 e 4 f => a/b//c/d///e////f

That's pretty mechanical, but if I've got it right, I think it verifies it can be done.

But here's my question: Is there a known encoding for this kind of problem that would more intuitively convey the structure to a human reader, perhaps at the cost of making longer strings?  Let's say a system that would decay such that simple cases like [ab[cd]e] could look more like a/b//c///d//e or similar, while still being able to encode everything distinctly?

I realize the quality I'm asking for is a bit "nebulous", but perhaps you see what I mean.  One thing I don't like about the encoding I chose above is it imposes a left-to-right "leaning" property, when there isn't anything particularly left-like or right-like about the nesting properties being encoded.  I wonder how that might be excised by making different choices.

\n and \t would get the job done as best as I could tell. In memory they're each only a character, but visually they offer a lot more. You then have an encoding scheme of \n then $x$ \t characters where $x$ is the nesting level. So this:

[a b [c d [e] f]]

in memory becomes:

a\nb\n\tc\n\td\n\t\te\n\tf

visually becomes:

a
b
    c
    d
        e
    f

As Evil mentions, you could similarly remove \n and \t between characters at the same level to achieve something like this:

ab
    cd
        e
    f


Hadamard gate on entangled qubit TL;DR: If you have two entangled qubits in the state $|00\rangle + |11\rangle$, what is the result of applying the Hadamard gate on the second qubit, and why?

I am trying to understand $\text{PSPACE} \subseteq \text{QIP}(3)$ (Watrous, 2003), and have troubles understanding the following.

Hadamard gate: Given some qubit, one can test that it is in a uniform superposition by applying the Hadamard gate on it as it will map it to $|0\rangle$ in this case,
$$H(|0\rangle + |1\rangle) = |0\rangle.$$
By measuring it, you have some probability to get a $1$ iff. the qubit was not in a perfectly uniform state.

With entanglement: Now, the paper claims that you can use the Hadamard gate to detect entanglement as well. Given two qubits, $x,y$, that are perfectly entangled, you can have them in the superposition
$$xy = |00\rangle + |11\rangle.$$
I understand that if you measure $x$, then apply the Hadamard gate to $y$, it will not map it to $|0\rangle$ as it will be entirely determinated by the measurement made on $x$.

What I don't understand: They do not claim to be able to measure/collapse the qubits that are entangled with the qubits they want to test, so how does it work? If you have two entangled qubits in the state $|00\rangle + |11\rangle$, what is the result of applying the Hadamard gate on the second qubit, and why?

Where is it in the paper:

When skecthing the protocol at the end of the introduction section (End of first paragraph, page 2):

  If there is significant correlation between the low-index prover responses and the high-index verifier-messages, the uniformity test [Hadamard gate, measure 0s] will fail with high probability

When discussing the completeness of the protocol, in particular step 2. of the verifier (start of page 8):

  Next, the verifier applies the Hadamard transform to every qubit in each register of $\bar{R^u}$. If $\bar{R^u}$ now contains only 0 values, the verifier accepts, otherwise the verifier rejects. In short, the verifier is projecting the state of $\bar{R^u}$ onto the state where $\bar{R^u}$ is uniformly distributed over all possible values. It is easy to check that in the case of the honest
  prover the registers $\bar{R^u}$ are not entangled with any other registers, as each register of $P^u$ depends only on those of $R^u$, and are in a uniform superposition over all possible values. Thus, the verifier accepts with certainty in this case.

Also in the proof of soundess, same page

If you mean result in terms of state, then you can compute this by applying the matrix $I \otimes H$ to the Bell state.

If you mean what happens operationally, then observe that applying a hadamard gate on each qubit of the Bell state results in no change -- the resulting state is again the Bell state. So, if you apply two hadamard gates in parallel or none at all and then you measure both qubits, you will get perfect correlations between the measurement outcomes (measurement outcomes on the qubits are guaranteed to be equal). However, if you apply a hadamard gate to either the second qubit or the first qubit and then measure both qubits, then the measurement outcomes  will be completely independent of each other, that is, the measurement result of the first qubit can be $0$ or $1$ with $50\%$ probability and the measurement result of the second qubit can be $0$ or $1$ with $50\%$ probability, regardless of what was seen in the other measurement.

Algebra:

Given the state $|00\rangle + |11\rangle$, you can not compute the Hadamard gate by factoring the state and applying a Hadamard to only one qubit, as the state is entangled and cannot be factored into two independent qubits. You can, however, apply the result of $I \otimes H$, which is the operation of applying Identity gate on the first qubit and the Hadamard gate on the second. The resulting operation is, with scaling factor $s$,

$$ I \otimes H = \left[\begin{matrix}
1 & 0 \\
0 & 1
\end{matrix}\right]
\otimes
\frac{1}{\sqrt{2}}
\left[\begin{matrix}
1 & 1 \\
1 & -1
\end{matrix}\right]
= s\left[\begin{matrix}
1 & 1 & 0 & 0 \\
1 & -1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 1 & -1 \\
\end{matrix}\right]$$

For more details on this, see the question How to apply a 1-qubit gate to a single qubit from an entangled pair?.

Now, you can pass your entangled state, $
\left[\begin{matrix}
\frac{1}{\sqrt{2}} & 0 & 0 & \frac{1}{\sqrt{2}}\\
\end{matrix}\right]^{T}
$ for $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$, through the gate and get
$$
s\left[\begin{matrix}
1 & 1 & 0 & 0 \\
1 & -1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 1 & -1 \\
\end{matrix}\right]
\left[\begin{matrix}
\frac{1}{\sqrt{2}} \\ 0 \\ 0 \\ \frac{1}{\sqrt{2}}\\
\end{matrix}\right]
=
\frac{1}{2}\left[\begin{matrix}
1 \\ 1 \\ 1 \\ -1\\
\end{matrix}\right]
$$
Which is the state
$$|00\rangle + |01\rangle + |10\rangle - |11\rangle.$$
And measurement of the first qubit or the second qubit would be 0 or 1 with equal probability, and give no information on the state of the other qubit.


Range sum query - tree representation efficiency I was reading about possible solutions to the well known problem:

Given array A with length N create a structure that enables

Answering what is the sum $\sum_{k=i}^{j} A[k]$
Updating $A[k]$

I've seen most solutions use binary index tree but was curios whether it's possible to just use a regular tree that is built using similar qualities.
So given $A = [5, 4, 7, 9, 1]$
I try to construct a tree by creating a tree node for each value that has a start and end (which are just the index in the beginning.
To construct the tree I push all the starting node into a queue $Q$
while not Q.empty():
  next <- []
  for i in range(Q.size()):
    f <- Q.front()
    Q.pop()
    if Q.empty():
      if marker:
        parent <- make_parent(f, marker)
        next.push(parent)
      else:
        marker <- f
    else:
      f2 <- Q.front()
      Q.pop()
      parent <- make_parent(f, marker)
      next.push(parent)

  for n in next:
     Q.push(n)

After the this ends marker will hold the root

(I have working c++ code but I tried to provide something more abstract and simple)
and to get a sum of range I perform the following (assuming I have an array Nodes that holds all the leaves) and that the query starts with the root of the tree that we created above
sumRangeNode(int i, int j, Node* n)
  if i == j
    return Nodes[i]
  if n == null
    return 0
  if j < n->start || i > n->end
    return 0;

  if i <= n->start && j >= n->end
    return n->val

  return sumRangeNode(i, j, n->left) + sumRangeNode(i, j, n->right)

The question is does it still have the $\log(N)$ complexity, I've tried to reason about it but struggled with:

The fact that I might be building a tree with "stragglers" like the $1$ in the example
The fact that I recursively explore right and left. Intuition tells me that because there are "enough" cases where the descent is stopped it's OK but couldn't find a way to formalize/prove it.

This approach does work. A "Binary-Indexed-Tree" is just an implicit balanced binary tree with some extra "compression". See this answer for the details on how and why this is done, but essentially the purpose is just to run in fewer cycles.
Your approach works fine asymptotically and will probably even perform fine in practice.

First, is the resulting tree produced by your queue always guaranteed to be "short"? The answer is yes. The easiest way to see this is notice that your queue's use is naturally into "epochs", where each epoch builds roughly one level of the tree.
First, as a simplification, don't bother tracking the marked separately from the others. Instead, just repeat the loop until Q has only one element, and then let that be your root. This simplifies your state and makes it easier to follow.
while q.size() > 1:
   next = []
   while q.size() > 0:
       a := q.pop()
       if q.empty():
           next.push(a)
       else:
           b := q.pop()
           next.push(make_parent(a, b))
   for v in next:
       q.push(v)
root := q.pop()

If the queue contains all $n$ before an iteration, then afterwards it will contain either $\lfloor n / 2 \rfloor$ or $\lfloor n / 2 \rfloor + 1$ nodes depending on whether $n$ is is even or odd.
In addition, the maximum height of the nodes in the array will increase by at most one, since each node is only paired with one other (a careful analysis will show it always increases by exactly one, but we don't actually care).
The first observation tells us that the loop will run for $O(\log n)$ iterations. The second therefore tells us that the resulting tree will have height at most $O(\log n)$ since the height of the trees in the queue increase by at most 1 every iteration.
So the tree may not be perfectly "balanced", but its height is still bounded by $O(\log n)$ and thus any operation that runs in time bounded by the tree's height will run in $O(\log n)$ time.

The fact that I recursively explore right and left. Intuition tells me that because there are "enough" cases where the descent is stopped it's OK but couldn't find a way to formalize/prove it.

This is actually straightforward. Suppose your tree has nodes in some levels that look the below, where the [--...--] indicate the range of values in the original array that the node represents.
Corresponding queries will be drawn with (...) instead. There are (generically) only a few kinds to worry about:

    [---------------45-----------------]
    [------------30----------][---15---]
  (- - Q1 - -)
           (- - Q2 - -)
                        (- - Q3 - -)
                        (- - - - - Q4 - - - -)
  (- - - - - - - - Q5 - - - - - - - - - - -)

Note that Q2 and Q4 have a symmetric forms that I'm omitting.

Q1 only traverses the left half
Q2 only traverses the left half
Q3 traverses both halves
Q4 traverses both halves
Q5 covers the entire range, so it won't traverse either

Thus we only really need to analyze Q3 and Q4.
Q4 totally covers the right half, so that "traversal" is guaranteed to be constant. So only the left half is traverses to any non-constant depth.
Thus the only "interesting" case is the Q3-type query, which only partially crosses the left child range and the right child range.
Note that the type-Q3 query extends to the left edge of the right child, and to the right edge of the left child.
This means that in the subtrees, there will be no type-Q3 queries, which can't extend to either edge. All queries will either completely miss each node, completely cover them, or extend past an edge.
So there will be at most one type-Q3 query in the entire tree (note that type Q5 also check both children, but that they are "fast").
Since there can only be one of them, you can essentially ignore them in the analysis - at most $O(\log n) + O(\log n) = O(\log n)$ nodes will be visited.


Does every DFA contain a loop? Is there a rule that either every DFA contains or not, a loop(cycle in graph terminology)?

I do not seem to be able to generalize this idea in either direction.

Also if either of these is true, can we assume through DFA - NFA equivalence that the same is true for NFAs?

Every finite directed graph in which every vertex has outdegree at least 1 has a cycle. This is a nice exercise. Thus, even if you look only at edges labeled by a particular symbol, you will find a cycle in every DFA.


Question as regards a proof of the Time Hierarchy Theorem I'm referring to the proof outlined here (and wikipedia.org):
https://proofwiki.org/wiki/Deterministic_Time_Hierarchy_Theorem

In my understanding, if I relaxed the conditions such that $K$ decides the input in time $O(f(m)^3)$, there should not be a contradiction in the final step because an appropriate TM $K$ should really exist.

Under this condition, $N$'s running time should be $O(f(2n+1)^3)$.

Finally, I arrive at the conclusion:

If $N$ rejects $[N]$ (which we know it does in at most $f(2n+1)^3$ operations):
By the definition of $N$, $K$ accepts $([N],[N])$.
Therefore, by the definition of $K$, $([N],[N])\in H_f$.
Therefore, by the definition of $H_f$, $N$ does accept $[N]$ in $f(n)$ steps.

To me it seems that 1. and 4. would still contradict. What did I do wrong?

Your arguments is as follows:

If $N$ rejects $[N]$ then $([N],[N]) \in H_f$.
Since $([N],[N]) \in H_f$, $N$ accepts $[N]$ in $f(m_n)$ steps.

This is indeed a contradiction, so we conclude that $N$ accepts $[N]$. Then we argue again:

Since $N$ accepts $[N]$ then $([N],[N]) \notin H_f$.
Since $([N],[N]) \notin H_f$, it is not true that $N$ accepts $[N]$ in $f(m_n)$ steps.

Since the running time of $N$ is $f(2m_n+1)^3$ in your case, there is no contradiction. After $f(m_n)$ steps the machine $N$ might still be running.


Is De Bruijn Graph Hyper-cube? I do not know if I miss something in the definition of a hyper-cube, but as far as I understand, Hyper-cube graphs have 2^n vertices and if written in binary form, "one-bit difference" strings of numbers are linked with an edge.

From this definition, De Bruijn graph does not look like it is a hyper-cube, because 000 and 010 for example, are not adjacent.

No. I was writing an answer based on vertex and edge counts, but then I realised that there's a simpler argument: the de Bruijn graph of strings of length $n$ over an alphabet of $m$ symbols has $m$ self-loops, whereas a hypercube has none.


What's difference between SUM and OR? While studying ALU I came across this example, now what's difference between operations of OR Gate and SUM(Adder), in binary language

The OR and AND operations are 2-in 1-out.

An Adder is either 3-in 2-out (shown in your diagram) or 2-in 2-out (not shown).  In part, because an Adder has 3 ins and 2 outs, it is composed of more underlying gates than AND and OR.

(But to be clear, it does not require new kinds of gates, the existing AND and XOR, OR, NOT gates, or the negating ones NAND, etc.. suffice.)

If we add two 16-bit numbers (not necessarily on a computer, but speaking mathematically) we get a 17-bit answer.  (That we often send that answer back to 16 bits is to risk errors in our systems; and the potential for these errors require mitigation techniques, but that is off topic to this question.)

Think of base ten.  In the general case, Two one-digit numbers add up to one two-digit number (though the upper digit may be zero).  If we're doing long addition, we carry from one column to the next (going left).  That carry going in means we're now adding 3 digits together, and the result is one digit along with a possible carry for the next column.  That's why adders sometimes take 3 inputs and other times 2 inputs.  The 2-input is for the least-significant-digit, whereas the 3-input is for the rest.

The last column has a carry out that is not used further, but just part of the result.  This is why we get one more digit than have the inputs.

In binary the maximum inputs would be a=1, b=1, and CarryIn=1.  That adds to 3 (decimal) and 3 is represented as 11 in binary.  The first of those one's (from 11 in binary) is the CarryOut and the second pf those one's is the Result in your diagram.


Why algorithms calculating non-tirivial zeros can't be used as proofs of Riemann Hypothesis? Recently I was reading again this propositions as types paper by Philip Wadler:

http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf

It gives an impression, that programs are proofs. So my first question was that why they are not enough for mathematical proofs then, for example in case of Riemann Hypothesis. Billions of zeros on critical line have been calculated in many many ways. I suppose they use some sophisticated algorithms or computer programs in that sense.

http://mathworld.wolfram.com/pdf/posters/Zeta.pdf

So, I was just stuck there. Why aren't these programs, or proofs in the system of Curry–Howard correspondence, enought?

The fact of the matter is, if a proof exists, then a Curry-Howard version of the program exists too. That doesn't mean that it's easy to find, though.

Undecidability still holds for Curry-Howard: if your types are advanced enough to capture logic, then there's no algorithm which takes in a type and outputs a program of that type, if it exists. Just like there's no algorithm that looks at a proposition and tells you if it's true or not.

  Billions of zeros on critical line have been calculated in many many ways.

Curry-Howard does not say that a program to compute zeroes can be turned into a proof of the Reimann hypothesis. It doesn't say that any program is a proof. What it says is, there is a dependently typed programming language where there's a type corresponding to the Reimann hypothesis, and a program with that type iff there's a proof of the Reimann hypothesis.

What this program would actually look like, if it's a proof, is a function that takes a number and a proof that that number is a zero of the Zeta function, and outputs a proof that that number is either a negative integer or has complex part 1/2. (Notice how the type of the input proof depends on the value of the given input, this is the "dependent" of dependent types).


Are qubits written in a big-endian or little-endian order when grouped? Say for instance you layout a quantum simulator like follows:

amps = [0] * 8  # 3 qubits

Therefore you are left with the following in binary:
000, 001, 010, 011, 100, 101, 110, 111

Does the third digit in binary represent the third qubit or the first?

One would assume it would be the third but I'm not certain and I don't want to get the model wrong.

There's no convention. Usually the endian-ness doesn't matter, or else it's clear from the context which endian-ness is being used.

(I'm also not aware of a convention for whether the wires in circuit diagrams are top-endian or bottom-endian. I just always infer from context.)


Number of times statement is executed in complex nested loop I am trying to find out how many times the "statement" is executed by finding its formula based on these loops:

int s = 0;
for(int k = n; k > 0; k /= 2)
{
  for(int l = k; l < n; l++)
  {
    s++; // statement
  }
}

I have been stuck with this problem for a while since I couldn't really get the correct formula whenever I compared the result of my formula to the output s.

I started by doing this:

$$T(n) = \sum_{k=1}^{\left\lfloor{\log_2(n)}\right\rfloor + 1}\sum_{l=k}^{n-1} 1$$

then eventually got this as a result:

$$T(n) = (1/2)(\left\lfloor{\log_2(n)}\right\rfloor + 1)(2n - \left\lfloor{\log_2(n)}\right\rfloor-2)$$

Does anyone know how to solve this kind of problem?

(This is a self-made problem btw since I kind of find analysis of algorithms fun)

We can determine the exact value of $s$ as a function of $n$. For the sake of brevity, let $\lambda = \left \lfloor \lg n \right \rfloor$. We can replace the inner loop with:

  $s \leftarrow s+n-k$

At the end of the program we'll have:

$$
s= \sum_{h=0}^{\lambda} n - \left \lfloor \frac{n}{2^h} \right \rfloor = n \left( \lambda + 1 \right) - \sum_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor
$$

Our problem is now rewriting the last term in a nicer form. . Certainly $n$ has a unique representation in base $2$, in particular it is true that

$$
n = \sum_{u \in S} 2^u
$$

for some $S \subseteq \mathbb{N}_{\le \lambda}$.

Therefore we have:

$$
\sum_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor = \sum_{h=0}^{\lambda} \sum_{u \in S} \left \lfloor 2^{u-h} \right \rfloor =  \sum_{u \in S} \sum_{h=0}^{\lambda} \left \lfloor 2^{u-h} \right \rfloor =
\sum_{u \in S} 2^{u+1} -1
$$

But then:

$$
\sum_{u \in S} 2^{u+1} -1 = 2n - |S|
$$

Piercing it all together, at the end of the program we will have:

$$
s = n \left ( \left \lfloor \lg n \right \rfloor - 1\right) + \textbf{1}(n)
$$

where $\textbf{1}(n)$ is the Hamming norm of $n$, that is, the number of ones in its binary representation.


Inference of a measure for a decreasing chain Set $I_n = \{0,\ldots,n-1\}$.
Given integers $v_0,\dots,v_{n-1} \in \mathbb{N}$, find an integer $t>0$, a map $f:\mathbb{N} \times I_n \to \mathbb{N}^t$, and a well-founded order $>_t$ on $\mathbb{N}^t$ such that: $$\forall i \in I_n, m \in \mathbb{N}. f(m,i) >_t f(m+v_i,i+_n 1)$$
where $+_n$ is addition in $\mathbb{Z}_n$ and $v_0+\dots+v_{n-1}<0$.  Is there an efficient algorithm to do that?
Explanation and motivation
The directed weighted graph $0 \stackrel{v_0}\to 1 \stackrel{v_2}\to \ldots \stackrel{v_{n-2}}\to n-1 \stackrel{v_{n-1}}\to 0$ describes how a magnitude $m \in \mathbb{N}$ varies. For transition $i \stackrel{v}{\to} j$, $m$ gets updated with $m+v$. It must hold that $\sum_{i = 1}^n v_i < 0$. Consider the following problem:
Give an assignment of values in $\mathbb{N}^t$ to nodes and an order that decreases at each transition. That is, if $\text{nodes} = \{0,\ldots,n-1\}$, I want to build a map $f:\mathbb{N} \times \text{nodes} \to \mathbb{N}^t$ with $t > 0$ satisfying: $\forall i \in \text{nodes}. f(m,i) >_t f(m+v_i, i +_n 1)$ where $>_t$ is a well-founded order on $\mathbb{N}^t$.
Is there an algorithm that can built such an $f$ and $<_t$?
Example (my try):
Assume you have the following chain is given:
$1 \stackrel{+3}{\to} 2 \stackrel{-2}{\to} 3 \stackrel{-2}{\to} 1$
In this case, $+3-2-2 = -1 < 0$.
Let's start at 1.
Since $m$ increases, I will annotate measure $(2,m)$ in $1$ and measure $(1,m)$ in $2$ so that lexicographic order decreases.
At $2$, measure $m$ decreases so I can leave annotation $(1,m)$ as it was.
At $3$, measure $m$ decreases so I can copy annotation $(1,m)$ from $2$.
Coming back to $1$, I have a problem, since I had annotated $(2,m)$ before, but now I have annotated $(1,m)$ and these are clearly different measures.
Can you help me out of this problem?
Note on the meaning of the specification
Just to make sure the specification matches my needs, the problem tries to  model how some quatity $m$ varies in a loop of successive function applications. The functions form a loop that ends at $0$. It is guaranteed  that when traversing the whole loop, quantity $m$ decreases (according to the variations $v_i$). In each function one have to check that in the next call certain measure $f$ (depending on the parameter $m$) decreases.

Yes.  This is possible.  $t=1$ suffices.  Take

$$\begin{align*}
f(m,n-1) &= Cm + D\\
f(m,n-2) &= f(m+v_{n-2},n-1) + 1 = Cm + C v_{n-2} + D + 1\\
f(m,n-3) &= f(m+v_{n-3},n-2) + 1 = Cm + C v_{n-3} + C v_{n-2} + D + 2\\
&\ldots\\
f(m,i) &= Cm + C v_{i} + \dots + C v_{n-2} + D + n-1-i
\end{align*}$$

where we take the constant $C>0$ to be at least $n$; we choose a constant $D>0$ that's large enough that the output of $f$ is always positive; we take $t=1$; and we use the standard order on $\mathbb{N}$.  Then you can verify that this satisfies all the conditions.

How do you find this?  As always, start with small cases.  Start with $n=2$ and see what has to hold of $f$, and try to construct a $f$ that meets the conditions.  (One way to ensure that $x>_t y$ is to set $x=y+1$; in the construction above, I used that to construct $f$ that satisfies the condition by definition.)  Then try $n=3$.  Then generalize.  The above definition follows as a straightforward consequence of your requirements; if you choose elements of $f$ in the right order, it becomes routine to fill out the truth table of $f$ so all the requirements are met.


How to avoid getting stuck on local optimum, for genetic algorithms I'm programming a genetic algorithm using grammatical evolution. My problem is that I reach local optimal values (premature convergence) and when that happens, I don't know what to do. I'm thinking about increasing the mutation ratio (5% is it's default value), but I don't know how to decide when it is necessary.

The data I have on every generation is a bidimensional array whose first column is its fitness

adn[i][0] ← fitness
row → is the values of the Grammar
column ↓ Each indiviual result

If you need clarification, please ask and I'll be pleased of modifying. Note that this is not my mother language and sorry for the mistakes and for the inconvenience.

Answering a request, my operations are the following, and exactly in this order:

I generate a random Population (A matrix with random numbers)
I generate a matrix that contains the desired result. For doing this, i have implemented a couple functions that have aditionally a +-5% of variation, for example: fun(x)= (2*cos(x) + sen(x) - 2X) * (0,95+(a number oscillating between 0 and 0,1), the x contains every f(x) with sequentially from 0 to N (Being N the size of row), the y contains exactly the same (more results)
Starts algorithm (generations beginning to change

The actions that make every generation are:

Mutation: A random number of every cromosome can mutate on any gene → adn[i][random] = random number (with a 5% of probability of this happening)
Crossover: I cross every adn with other adn (80% is the chance of mutation for every pair), for the pairing I pick a random number and face adn[i] and adn[(i+j) mod NumADNs]
Translate. I get a matrix that contains the values f(0 to N) making in one step transcription and translate aplying the grammar on the image

-fitness: I compare the values obtained with the expected ones and update the fitness.

-Elitism: After that, i choose the best 4 adn's and get it to the top, they will be selected

-Selection: Any non elitist adn will face a totally random adn, and if its fitness is lower (Lower is better) will prevail, being a possibilities of the worse one surviving

It looks like you're dealing with premature convergence.

In other words, your population fills itself with individuals that represent the suboptimal solution and/or individuals that are (too) close to said solution.

The basic framework of a genetic algorithm is as follows:

P <- Population of size N with N random individuals.
evaluate fitness of all individuals in P
while (stopping criteria not met) {
    C <- empty Child set of size M
    while (size of C is not M) {
        parent1 <- select an individual from P
        parent2 <- select an individual from P

        child1, child2 <- combine parent1 and parent2 somehow.
        child1, child2 <- mutate children by chance
        evaluate fitness of child1, child2
        C <- C + child1 + child2
    }
    P <- combine P and C. (P remains size N)
}
return individual with best fitness

Note that the (e.g.) the size of the population/children doesn't have to be constant per se. Or you might combine a variable number of parents into a variable amount of children (e.g. a crossover between 5 parents resulting in 7 children). But I would keep it simple, at first.

As you can see, the main operators in a genetic algorithm are, in order

Selection: Select individuals from the population that will be combined. Examples: tournament selection, proportionate selection, truncation selection, ...
Crossover: Combine selected individuals (parents) to new indidivuals (children). Examples: one-point crossover, n-point crossover, uniform crossover, cut and splice, ...
Mutation: By chance, (don't) mutate an individual by changing the individual slightly.
Recombination: Somehow insert the children into the set of parents.
Examples: Add all children to the population, sort the thing by fitness and remove the worst individuals so your population is size N again; Sort your population and drop the worst M individuals and add all children; often the same techniques that are presented in the selection phase are used.

In your description, you're confusing multiple steps as if it were one (e.g. you skip the selection step but you incoorperate it in the crossover step). You also describe techniques as if it were a step of the algorithm (e.g. Elitism is a technique used in the recombination step to ensure that at least the best individuals don't die).

An example where premature convergence might/will occur is when you only select the best individuals as parents and only allow the best individuals survive (in the recombination step).

Some possible methods to resolve this:

Increase mutation rate. However, a mutation is usually a very random process. You would need 'pure' luck to escape the suboptimal solution.
Redesign your genetic operations. e.g. allow bad fitness individuals/offspring to survive the generation more frequently. It could be that you're currently selecting too much good individuals to survive. Don't let too much bad individuals survive though, or your algorithm will never converge to something good.
(...)

The goal is to tweek your genetic operations in such a way that in each next generation, the average fitness of your population has (preferably) increased while maintaining a big enough fitness variation. This is not easy.

There are several other methods to avoid premature convergence if the above doesn't help you out. I strongly recommend experimenting with altering your genetic operations first before doing this, however. Search terms: preselection, crowding, fitness sharing, incest prevention, ...


A question about an input in a Halting Problem proof Here is my Halting Problem proof, that largely mirrors other (non-diagonalizing) proofs that I've seen.

$H(p,i)$ returns $1$ if program $p$ halts on input $i$.
$H(p,i)$ returns $0$ if program $p$ does not halt on input $i$.
Let $f(t,t)$ be an interface for any program that returns a $0$ or a $1$.
$g(x)$ is $0$ if $f(x,x)$ is $0$, infinite loop if $f(x,x)$ is $1$
Now use $H$ in place of $f$:

4b. (modified)  $g(x)$ is $0$ if $H(x,x)$ is $0$, infinite loop if $H(x,x)$ is $1$

Run $g(g(i))$ which runs $H(g(i),g(i))$
        If $H(i,i)=0$, then $g(i) = 0$
        If $H(i,i)=1$, then $g(i)$ is undefined
If $g$ halts, then $H(g(i),g(i))$ must return $1$ (line 1).

But then $g$ won't halt. (line 4b)
If $g$ doesn’t halt, then $H(g,g)$ must return $0$ (line 2).

But if $H(g(i),g(i))$ is $0$, then $g$ halts. (line 4b)

My issue is with $g(g(i))$.  I understand that the idea of the proof is to  feed the machine into itself, but what, exactly, is the contents of the $i$?

It is an unspecified input.  Halting program proofs show that, for any given program that one claims can solve the halting problem, there exists an input for which it does not.  The proofs typically do not try to find what that input actually is, merely to prove that one must exist.


Analogue of the topology-computability correspondence for computational complexity There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with continuous functions (in fact it can perhaps be traced back to Brouwer).

Complexity theory can be seen as a refinement of computability theory: we are interested in not only whether a problem is solvable or not but also the efficiency with which it is solvable. Taking this view of complexity theory as a refinement of computability theory, I wonder if there is any research on analogous mathematical structures to provide efficiency-sensitive denotational semantics to programming languages.

The point of topology is that it is distance-blind which is in accord with the efficiency-blind approach in computability theory. So it seems to me that an efficiency-sensitive denotational structure should be a topological space with a notion of distance, i.e., a metric space or something like that.

Has someone worked this out or is this a nonsensical question? If it is the latter, please explain why.

The answer to your literal question is neither. The reasoning in your question makes perfect sense, and there are several researchers working on the details on what exactly is analogous to complexity theory in the same way topology is analagous to computability. However, I don't think I am unfair in claiming that this is nowhere near completed.
In a compact metric context, notions such as metric entropy seem to be important, and the counterpart to "continuous" seems to be "having a modulus of continuity of particular growth". Beyond compact metric, the picture quickly gets very unclear.
I don't know of a comprehensive written treatment, but Martin Ziegler just gave a tutorial on this at the conference "Computability in Europe". The talks are up on this Youtube channel, specifically "Quantitative Coding and Complexity theory...".


What is the average time complexity, for a single linked list, for performing an insert? I thought this would be a very simple O(n) b.c. you can do the insert any where with in the list.

The longer the list, the longer it will take on average to do the insert.

However according to bigocheatsheet it is O(1) or has no dependency on the size of the list.

What is wrong here?

Either if you want to insert at the end of the list or at the beginning of the list, you're going to have $O(1)$ Complexity for that and $O(1)$ space.
If you want to insert at the beginning of the list, you just make the new list head the node you want to insert, and link it to the previous  list head.
If you want to insert at the end of the list, you can also hold the end of the list as a pointer and insert a new node after it.
If you want to insert in an arbitrary place in the list, then linearly going there is going to be the best you can do ( to  my knowledge ).
Statistically  you'll have to go through $(n+1)/2 $ nodes to get through yours.


Algorithm for sorting within windows I am writing an app which displays speeches on various topics, with each speech having a number of attributes. I want to give the user the choice to sort a list of speeches by an attribute, even within a previously sorted list of speeches.
Consider for example: Suppose the previous list had been sorted by the attribute: "speaker's name", and there were three different speakers (so the list was split into three windows with each window consisting of the same speaker). Now, the user wants to sort the speeches based on the attribute: "length of the speech" such that the new list would now be sorted by speaker's name, and within each window of the speaker's name, the speeches would be sorted by the length (creating a new window within this window for each length of speech in the speaker's window).
I would like to give the user the ability to do this with an arbitrary number of attributes. How can I go about doing such sorting, preferably in the most efficient way?
P.S: I am just a teenage programmer who has been programming for a few years and can understand algorithms in concrete steps - I have not taken college classes in CS, so please keep that in mind when explaining the algorithms.

What you require is the lexicographic ordering. Let me describe this.
Suppose the speeches have two attributes. The first one is "speaker's name" and the second one is the "length". For simplification, let me define the speaker's name by the integer value instead of a character string. Now, suppose the speeches are represented using the following tuples: $(0,0)$, $(1,2)$, $(0,3)$, $(1,4)$, $(2,3)$, $(2,4)$, and $(1,1)$. Here, the second speech has the speaker's name: $1$, and length $= 2$.
Requirement 1: You simply want to sort the speeches by the "speaker's name".
Just consider the first attribute for comparing any two speeches and apply any sorting algorithm. You will get the following ordering: $(0,0)$, $(0,3)$, $(1,2)$, $(1,4)$, $(1,1)$, $(2,3)$, and $(2,4)$.
Requirement 2: You want to sort first by the "speaker's name" and then by the "length". This is the requirement that you have mentioned in your question.
Now, define a new comparison operation between two tuples as follows: $(a,b) < (c,d)$ if and only if $(a<c)$ or $(a = c$ and $b<d)$
Here, we are comparing by giving the "first attribute" more priority. And if the first attribute value is the same, we compare based on the "second attribute".
Smilarly, you can define $(a,b) > (c,d)$ if and only if ($a>c$) or ($a = c$ and $b>d$).
Now, you can simply use any sorting algorithm by replacing the standard comparison operation with the above-defined comparison operation.
You will get the following ordering: $(0,0)$, $(0,3)$, $(1,1)$, $(1,2)$, $(1,4)$,  $(2,3)$, and $(2,4)$.
Requirement 3: Suppose, you want to sort by the length and then by the speaker's name
Simply, define the comparison operation between two tuples as: $(a,b) < (c,d)$ if and only if $(b<d)$ or $(b = d$ and $a<c)$. Now, again you can use any standard sorting algorithm by replacing the standard comparison operation with this comparison operation.
You will get the following ordering: $(0,0)$, $(1,1)$, $(1,2)$, $(0,3)$, $(2,3)$, $(1,4)$,  and $(2,4)$.

Similarly, you can define a new comparison operation for the multiple attributes based on your requirements.


How does dynamic programming work in this example(generating the tables ) For example, a sequence has the defined growth property: if it is a
  sequence of positive integers $a_{1}, a_{2}, a_{3}....a_{n}$ and such
  that:

  $a_{1}=1.$
  $a_{n+1} \leq$ Max$_{1\leq i \leq n}$ ($a_{i}+1$)

  We can quickly compute the number of such sequences of length n with the power of dynamic programing:

  Let sequence(l, m)  be the number of possible sequences with length
  l and maximum number in the sequence m. The total number of such
  sequences for a length can be calculated by summing all the sequences
  with maximum value ranging from 1 to n for length l. The recurrence
  can be described as:

  sequence(l,m) = sequence(l-1, m-1 ) + m * sequence(l-1,m);

  (sequence (l,1)=1, sequence(l,m)=0 if l< m)

  As we create a table of size l * m, where we fill the matrix column
  by column. The base case: the first column of the table sequence(l, 1)
  = 1 and for the subproblems where l < m the number of sequences will be 0 since the maximum element in sequence can't be bigger than the
  length of sequence. We can now fill the table in the second column and
  apply the recurrence relation for every cell and obtain the value fro
  all combinations of l and m. Finally, We can sum up the last row to
  calculate the number of sequences.

Understand that the text already gives hint for creating the table.
but I am still struggling to visualize it. First of all,  What exactly is this sequence?

$a_{2} = a_{1+1} \leq max_{1 \leq i \leq 1}(a_{i}+1) $ which mean i can only be 1. Then $a_{2} \leq  max(2)$

and $a_{3}\leq max(3)$ but what are some example of such sequence ?
Any more guidance for completing the table?

What is exactly m in sequence(l, m)?  Where should we place $a_{4}$ in the table of l * m?

Here are all such sequences of length 1.

[1]

Here are all such sequences of length 2.

[1, 1]
[1, 2]

Here are all such sequences of length 3.

[1, 1, 1]
[1, 1, 2]

[1, 2, 1]
[1, 2, 2]
[1, 2, 3]

Here are all such sequences of length 4.

[1, 1, 1, 1]
[1, 1, 1, 2]

[1, 1, 2, 1]
[1, 1, 2, 2]
[1, 1, 2, 3]

[1, 2, 1, 1]
[1, 2, 1, 2]
[1, 2, 1, 3]

[1, 2, 2, 1]
[1, 2, 2, 2]
[1, 2, 2, 3]

[1, 2, 3, 1]
[1, 2, 3, 2]
[1, 2, 3, 3]
[1, 2, 3, 4]

Please observe how the sequences grow longer and longer with the condition
$$a_{n+1} \leq \max_{1\le i \le n} (a_{i}+1) = 1+\max_{1\le i \le n} a_{i}$$
as well as the recurrence relation
$$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m).$$

  $a_{2} = a_{1+1} \leq \max_{1 \leq i \leq 1}(a_{i}+1) $ which mean i can only be 1. Then $a_{2} \leq  \max(2)$. and $a_{3}\leq \max(3)$.

Yes, $a_{2} \leq  \max(2)=2$. However, $a_{3}\leq \max(a_1+1, a_2+1)$. If $a_2=1$, then $a_3\le \max(1+1, 1+1)=2$. While $a_3\le \max(3)=3$ is true, it might be relaxed too much.

Let us see how we are going to fill the two dimensional array sequence($m$,$l$).

For example, how to use the following relation?
$$\text{sequence}(4,4) = \text{sequence}(3, 3 ) + 4 * \text{sequence}(3,4)\,.$$
We know sequence$(3,3) = 1$ since there is only one sequence of length 3 and maximum number 3, $[1,2,3]$ or sequence$(3,3) = 1 + 3 * 0 = 1$. There is no sequence of length of length 3 and maximum number 4, since the maximum number in any sequence of length 3 is at most 3. So $$\text{sequence}(4,4) = 1 + 4 * 0 = 1\,,$$
which corresponds to the unique sequence of length 4 and maximum number 4, $[1,2,3,4]$.

  What is exactly $m$ in $\text{sequence}(l, m)$? Where should we place $a_4$ in the table of $l * m$?

It looks like you need to understand the recurrence relation.

$$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m),$$

where $\text{sequence}(l,m)$, $l\ge2$, $m\ge1$ is the number of sequences whose length is $l$ and whose maximum number is $m$. For example, a sequence $(a_1, a_2,a_3,a_4)$ is a sequence of length 4 and whose maximum number is $\max(a_1, a_2,a_3,a_4)$. If that maximum number is $k$, it contributes 1 to $\text{sequence}(4, k)$ if it satisfies the two conditions. For example, sequence $(1,2,3,2)$ contributes 1 to $\text{sequence}(4, 3)$ while sequence $(1,1,2,2)$ contributes 1 to $\text{sequence}(4, 2)$.

Let $a_1, a_2, \cdots, a_l$ be such a sequence. Let us consider its first $l-1$ items, $a_1, a_2,\cdots, a_{l-1}$.

The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is smaller than $m-1$. Then $$a_{l} = a_{(l-1)+1}\leq \max_{1\le i \le l-1} (a_{i}+1) = 1+\max_{1\le i \le l-1} a_{i}\lt m$$, which contradicts that fact that the maximum number of all of them is $m.

So this situation cannot happen.
The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is $m-1$. Then $a_l$ must be $m$. Otherwise, the maximum number of the whole sequence will be $m-1$ instead of the required $m$.

So for each sequence counted in $\text{sequence}(l-1, m-1 )$, we have a sequence that should be counted in $\text{sequence}(l, m)$. We have a summand $\text{sequence}(l-1, m-1)$
The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is $m$. Then $a_l$ can be anyone of $1, 2, \cdots, m$ $m$. So for each sequence counted in $\text{sequence}(l-1, m)$, we have $m$ sequences that should be counted in $\text{sequence}(l, m)$. That is, we have a summand $ m * \text{sequence}(l-1, m)$.

Combining all three cases above, we obtain that recurrence relation.


Proof for Transitivity of Weak Bisimulation ≈ I have already posted this question on the other page, but I was suggested to post it here as it might be more relevant.

I am currently following a course in concurrency theory and I am currently trying to prove that the Weak Bisimulation relation ≈ is an equivalence relation.

I have managed to prove cases for reflexivity and symmetry, however I can't seem to make the connection for transitivity. Does any one have any clues how can I go about this ?

I have tried the relation {(P,R) | ∃Q.P≈Q,and Q≈R} as my witness relation and then at one point I get stuck.

I assumed that P->a P' which gives me that there is Q =>a Q' and that P' ≈ Q' Now the thing is that since Q =>a Q' then by the definition of => Q ->tau* Q1 ->a Q2 ->tau* Q' Q1 ->a Q2 will cause some R1=>a R2 such that Q2 ≈ R2 Then I am not sure how to proceed to show that somehow there is a transition R =>a R' such that (P', R') are in R. May be I believe I have to use numerical induction on the number of tau ?

Thanks !

You are on the right track. It can be useful to prove the following lemma: if $\sim$ is a weak bisimulation, if $P\sim Q$ and if you have a sequence of transitions $P\xrightarrow{w}P'$ for $w\in (Act\cup\{\tau\})^*$ then there must be a sequence $Q\xrightarrow{w'}Q'$ with $P'\sim Q'$ and $w =_{\tau} w'$, i.e., $w$ and $w'$ are "the same modulo $\tau$". This can be done by induction on $w$, and it will come in handy when you deal with transitivity. Check that $u=_\tau u'$ and $v=_\tau v'$ imply $uv=_\tau u'v'$, i.e., that $=_\tau$ is a congruence.


Would increasing system memory speed reduce a Von Neumann Architecture bottleneck? A Von Neumann Architecture bottleneck is a limit on the amount of data a computer can process due to limited bandwidth between the CPU and RAM. Possible mitigations to the problem according to Wikipedia are...

Providing a cache between the CPU and the main memory
Providing separate caches or separate access paths for data and instructions
Using branch predictor algorithms and logic
Providing a limited CPU stack or other on-chip scratchpad memory to reduce memory access
Implementing the CPU and the memory hierarchy as a system on chip, providing greater locality of reference and thus reducing latency and increasing throughput between processor registers and main memory.

I know that increasing the number of data lanes between the CPU and RAM would help, but would increasing the system memory speed also help?

No, increasing the memory speed won't help solve the Von Neumann architecture bottleneck. The reason is as memory size is increased the time required to access the memory contents increases. So no matter how fast the memory is, if it is large it will be slower. So faster, smaller memories called caches are used to provide the illusion of a large, fast memory to the user.


Semi-streaming algorithm for $s$-$t$ connectivity Let $G=(V,E)$ be an undirected graph. Given a pair of vertices $s,t \in V$, how can we construct a semi-streaming algorithm which determines is $s$ and $t$ are connected? Is there any way to construct such an algorithm which scans the input stream only once?
Note that a semi-streaming algorithm is presented an arbitrary order of the edges of $G$ as a stream, and the algorithm can only access this input sequentially in the order it is given; it might process the input stream several times. The algorithm has a working memory consisting of $O(n\log^{O(1)}n)$ bits.

You cannot do it in a single pass. Consider the set of all graphs of the following form: the vertices are $\{s,t\} \cup A \cup B$, where $|A|=|B|=n/2-1$. The only allowed edges are between $s$ and $A$, between $A$ and $B$, and between $B$ and $t$.
Suppose that the algorithm is first presented with the $(A,B)$ edges, and then with the $(s,A),(B,t)$ edges. After reading the $(A,B)$ edges, it must "remember" all of them, since there could be only one $(s,A)$ edge and only one $(B,t)$ edge, in which case the answer depends on whether the corresponding vertices in $A$ and $B$ are connected. Since there are $2^{(n/2-1)^2}$ choices for the $(A,B)$ edges, the algorithm must have a memory of at least $(n/2-1)^2$ bits (since after reading the $(A,B)$ edges, it could be in any of $2^{(n/2-1)^2}$ possible states).


Is the language of DFAs which do not accept themselves recognizable? I understand how a the language of turing machines which do not accept themselves is not recognizable but I'm not sure if the same proof could be used to describe a DFA... i.e a proof by contradiction in which a recognizer M recognizes a TM which does not accept itself on input ...creates a contradiction in which if M accepts then M does not accept itself.

DFAs always terminate, so if you want to check whether a given DFA accepts or rejects a given word (say its representation), just run it on the word. You can even do this in polynomial time.


Is this language context free? In a recent test, I was asked to recognize if the below language is context  free:

$\qquad\displaystyle L = \{0^{n+m}1^{n+m}0^m \mid n,m \geq 0\}$

I think it is context free, and can be accepted by below context free grammar, where $S$ is the start symbol and $Y$ is a non-terminal:

$\qquad S \to S0 \mid Y$

$\qquad Y \to 0Y1 \mid \epsilon$

However, my answer was considered wrong and that the language $L$  is not context free.

I'm confident about my answer, but the response has got me confused. Is my understanding correct? Please let me know if I've missed something.

You can use Ogden's lemma. Choose the word $w = 0^p1^p0^p$ for large enough $p$, and mark the rightmost $0^p$. Ogden's lemma gives you a decomposition $w = uxyzv$ with $xz$ pumpable and containing at least one marked point. Since $xz$ contains a $0$, it can't contain a $1$, as otherwise $ux^2yz^2v \notin 0^*1^*0^*$. A simple case analysis now leads to a contradiction.


Leftist heap - determining time complexity The time complexity of merge (union) operation is said to be $O(\lg (n_1 + n_2))$, where $n_1$ and $n_2$ are the numbers of elements in the merged heaps, respectively. I do not understand this - the algorithm has to go through all the elements of both rightmost paths of the original heaps - lengths of these paths are bound by $O(\lg n_1)$ and $O(\lg n_2)$. That makes $O(\lg n_1 + \lg n_2)$ in total, which is $O(\lg (n_1 n_2))$. Where am I making a mistake in my assumptions?

Arbitrary delete operation - the complexity should be $O(\lg n)$, where $n$ is the size of the heap. But after the deletion, the algorithm has to go through all the nodes from the parent of the deleted node to the root and correct the Leftist property, and the lenght of this path is bound by $O(n)$. Again, where am I wrong?

For the time complexity of merging, JeffE already pointed out in the comments that $O(\log(n_1n_2)) \in O(\log(n_1+n_2))$.

For arbitrary deletions note the following:

When we merge the two subtrees of the deleted node, the root of the resulting tree will have an s-value that is at least the s-value of the deleted node -1.
Thus, the s-value of any updated node will not be decreased by more than 1. (There is no constant bound for how much it can increase.)
Thus, if we update the s-value of a left child in and that value was strictly larger than the s-value of the right child, the s-values of the parent and all nodes above the parent will not change.
If the s-value of the left child and right child are equal, exchanging them still gives a valid leftist heap.
Thus, the number of updated nodes is bound by the length of a right flank in a leftist tree, which in turn is bound by $O(\log n)$.


What is the TAK function for? We covered this in class today. I understand the mechanics of it, but aside from being a nice example of recursion does it serve any purpose?

Searching the web reveals lots of pages with the formula and it's implementation in code, some talk about the author, but nothing about it's purpose.

You might use it to evaluate the performance of programming languages:

http://en.wikipedia.org/wiki/Tak_%28function%29

since recursive methods are pretty useful for benchmarking. In particular, deep recursion tests the speed with which a language can make method calls. This is important because modern applications have a tendency to spend much of their time calling various API functions.

You will also need it to solve ballot problems like this one:

Suppose A and B are candidates for office and there are 2n voters, n
voting for A and n for B. In how many ways can the ballots be counted
so that B is never ahead of A?

http://mathworld.wolfram.com/BallotProblem.html

or just to generate Takeuchi Numbers:

0, 1, 4, 14, 53, 223, 1034, 5221, 28437, ...


How to identify when to use Genetic Algorithm/Programming I have been reading/studying on genetic algorithm/programming, and have implemented Traveling salesman problem.

TSP is basically a permutation/combination problem, and I can understand how GA helps to narrow down to the solution.

As far as I see GA is helpful in finding solution to

similar permutation/combination problems and
problems like pattern recognition.

Where/What are the other problem areas where GA could be applied and How(just provide a simple explanation) and What/Where GA can not be applied?

One case where I think GA can not applied are where there is no patterns, like Coin-Toss-Guess-Heads-Or-Tails Program, where outcome is purely luck.

Note: I am not looking for practical uses like printing circuit board or NLP. I am looking for what problems GA solves? or How to recognize that GA will help solve a certain problem instead of writing a complex algorithm.

Like TSP is a permutation/combination problem where possible solution could end up in 2.4 billion or more, and finding the right answer would be nearly impossible, Hence GA(or other optimization algorithm like simulated annealing) is useful in finding an optimal solution.

The key point in deciding whether or not to use genetic algorithms for a
  particular problem centers around the question:

  what is the space to be searched?

  If that space is well-understood and contains structure that can be exploited by special-purpose search techniques, the use of genetic algorithms
  is generally computationally less efficient. If the space to be searched is
  not so well understood and relatively unstructured, and if an effective GA
  representation of that space can be developed, then GAs provide a surprisingly powerful search heuristic for large, complex spaces.

(De Jong, Machine Learning, 1990 nr 5, pg. 351)

Here a key point is what is an effective GA representation.

GA initially detects biases in low-order schemas and converges on this part of the search space. Over time, biases in higher-order schemas are detected by combining information from low-order schemas (via crossover) and eventually GA converges (at least according to the building blocks hypothesis).

Situations in which lower-order schemas give misleading information to the GA
about the probable fitness of higher-order schemas are said deceptive.

Most efforts at characterizing the difficulty of problems for GA
have concentrated on deception, but there are other factors:

the presence of multiple conflicting solutions or partial solutions
the amount of information from lower-order building blocks (not
how much this information is misleading)
sampling error
the number of local optima in the landscape
...

A general relation between a given problem's structure and the expected GA
performance on that problem is a very open area of research (actually it's not even clear what is the relation between the degree of deception in a problem and the problem's difficulty for the GA).

In general GA is more suited to find good solutions quickly than to finding the absolute best solution to a problem.

Some references you could find interesting are:

What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation by Stephanie Forrest and Melanie Mitchel (Machine Learning 1993)
Fitness distance correlation as a Measure of Problem Difficulty for Genetic Algorithms by Terry Jones and Stephanie Forrest
Dealings with Problem Hardness in Genetic Algorithms by Stjepan Picek and Marin Golub (2009)


How can I prove that a Regular Language is closed under Union given two languages with different alphabets? I need some help to prove that a Regular Language is closed under the union, using a DFA with two differents alphabets.

Suppose you have alphabets $\Sigma\subseteq\Sigma'$.  You can view any language $L\subseteq \Sigma^*$ as being a subset of $(\Sigma')^*$: it just happens to be language of strings that don't contain any symbols from $\Sigma'\setminus\Sigma$.

So, given languages $L_1\subseteq \Sigma_1^*$ and $L_2\subseteq\Sigma_2^*$, you can view both of these as languages over $\Sigma_1\cup\Sigma_2$, since $\Sigma_i\subseteq \Sigma_1\cup\Sigma_2$ for $i\in\{1,2\}$.  Given automata for $L_1$ and $L_2$, you can also modify them to work over alphabet $\Sigma_1\cup\Sigma_2$.

Now, you have two languages over the same alphabet, so you should be on familiar ground.


Justification behind this heuristic in SMA*+ I'm reading the paper Enhanced Simplified Memory-bounded A Star (SMA*+). In short, the authors propose a limited-memory version of A* where we cull nodes if we are out of memory, to re-expand them later on.

To do this they choose the worst node to cull. And they propose a heuristic to maximize to choose what is considered the worst node:

  For example, a culling heuristic based on the ratio between f-cost and depth, given as $c(n) = f(n) / \ln(d(n) + e)$, where $e$
  is Euler’s number, can improve performance on problems
  with many similar f-costs, if we can reasonably assume that the goal has a high depth.

A quick reminder, $f(n) = g(n) + h(n)$ where $g(n)$ is the cost to reach node $n$ and $h(n)$ is the heuristic to estimate the distance from $n$ to the goal node. $d(n)$ is the depth of the node.

The authors don't further elaborate on this. Is there some logical justification I'm missing for the formula $c(n)$, in particular the natural logarithm and adding $e$ to $d(n)$?

From what I can tell the function $c(n)$ was just chosen as a reasonably simple trade-off between f-cost and depth.

It appears that $e$ is added to simply have the denominator $\ln(d(n) + e)$ always be $\geq 1$ and prevent $\ln(0)$.


Can the Bell-LaPadula model emulate the Chinese Wall model? I have been reading on security policies and the question wether Bell-LaPadula can be used to implement Chinese Wall. Does anyone know more about it?

first the Bell-LaPadula Model cannot capture changes over time. second, more serious problem arises when one considers that subjects in the Chinese Wall model may choose which CDs(company dataset) to access; in other words, initially a subject is free to access all objects. the Bell-LaPadula Model cannot emulate the Chinese Wall model.


Write algorithm for biased toss of a coin Given a biased coin whose probability for Heads is 0.67 and Tails is 0.33, write an algorithm which will print the Heads and Tails with this probability.

I am not able to proceed with the problem. What should be my approach ?

Let $\xi$ be a random variable uniformly distribuited in $[0,1]$ and $t$ a real value in $(0,1)$, consider the function

$$
Y(\xi;t) = \begin{cases}
1 & \xi < t \\
0 & \text{otherwise}
\end{cases}
$$

Which is a discrete random variable therefore

$$
p_Y(y) = (1-t) \delta(y) + t \delta(y - 1)
$$

This means that if pick a random number in $[0,1]$ and you later compute $Y$, this $Y$ will correspond to a randomly picked value in $\left\{0,1\right\}$, but biased accordingly to $t$. If you use @kngtu pseudocode, it's equivalent to define the distribution above where $t = 0.67$.


Maximum number of words in deterministic finished automata with k-states I have exercise:

We have a given finished deterministic automata. It has 5 states and is
based on the alphabet {a, b, c}. It can create n different words (we assume that n <
inf). What maximum value can n be?

W have 5 states so it should be something like this:

$\varepsilon \ | \ (a|b|c) \ | \ (a|b|c)(a|b|c) \ | \ (a|b|c)(a|b|c)(a|b|c) | \ (a|b|c)(a|b|c)(a|b|c)(a|b|c)$

1 + 3 + 9 + 27 + 81 = 121, so n = 121 - maximum number of words in DFA with {a,b,c} alphabet and 5 states.

Its okay?

You are correct. I will try to give an informal justification:

The key is to observe that any 5-state DFA that produces a finite number of words can only produce words up to length 4, assuming the start state is included in the 5 states.

To see why this is, observe by contradiction that if it produced a word of length 5, it would have to go through 5 transitions $s_0 \rightarrow s_1 \rightarrow s_2 \rightarrow s_3 \rightarrow s_4 \rightarrow s_5$ for some set of states $s_i$. Since the DFA only has 5 states, the 6 states $s_0, \ldots, s_5$ cannot all be distinct. Thus this path contains a loop, and we can produce an infinite number of ever-longer words by looping repeatedly.

Thus the DFA can at most produce the words of length up to 4, which as you've observed is 121 words:

$\varepsilon \ | \ (a|b|c) \ | \ (a|b|c)(a|b|c) \ | \ (a|b|c)(a|b|c)(a|b|c)\  | \ (a|b|c)(a|b|c)(a|b|c)(a|b|c)$

To show that 121 is the least upper bound of possible words (in other words, that we cannot find a lower maximum), it suffices to construct a 5-state DFA that produces all 121 words. The following will do:

$C = \{a,b,c\}$

$S = \{s_0, s_1, s_2, s_3, s_4\}$, $s_0$ is the start state

$F = \{s_0, s_1, s_2, s_3, s_4\}$ (all states are accepting states)

$T = \{(s_i,s_{i+1},a), (s_i,s_{i+1},b), (s_i,s_{i+1},c)|0\le i\le 3\}$


P vs NP question from GeeksforGeeks From here: https://www.geeksforgeeks.org/algorithms-np-complete-question-2/

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? (GATE CS 2006)

(A) R is NP-complete

(B) R is NP-hard

(C) Q is NP-complete

(D) Q is NP-hard

The answer they give is B and I can see that. But I'm curious as to what is Q then? If it's not in NP and if it's not in NP hard, is there some other set that I don't know about it belongs to?

In fact, $Q$ is in NP (since you can reduce it to $S$ in poly-time and $S$ is in NP). It's just not necessarily NP-complete or NP-hard.
For example, let's let $Q$ be the following decision problem:

Given a number $n$, is $n$ prime?

This problem is known to be in $P$. But I can reduce it to something NP-complete, like HamiltonianPath:

First, determine whether $n$ is prime (in poly-time).
If it's prime, let $G$ be a graph with two vertices and one edge between them.
If it's not prime, let $G$ be a graph with two vertices and no edges.
Now, pass $G$ to HamiltonianPath, which will give you your answer.

In this case, $Q$ can be reduced to the NP-complete HamiltonianPath, but it clearly isn't NP-hard or NP-complete (since it can be solved in poly-time).


An algorithm to determine probability of one string appearing earlier than another string in an evenly distributed binary sequence Given two binary strings of length $n$ and $m$, determine in polynomial time the probability of the first appearance of one string being earlier than the first appearance of the other one in an evenly distributed infinitely long binary sequence.

Edit: I didn't consider my attempts at solving this to be relevant, they are as follows:

I've considered to use a Markov chain and the fact that $P(A_j)$, the probability of absorbtion of the chain in the $j$-th absorbing state, $=(b^{(0)}NR)_j$, where $b^{(0)}$ is the vector of probabilites of the starting state, $N$ is the fundamental matrix of the chain and $R$ is the matrix that describes the probability of transitioning from some transient state to some absorbing state.

I've indexed the chain states by $(i, j)$, where $i$ is the length of the longest prefix of the first string ($s_1$) that matches in the current state, and $j$ is the same for $s_2$.

Absorbing states are $(n, *)$ and $(*, m)$, where $*$ denotes any number, therefore splitting $P$, the transition matrix of the chain, into $Q$ and $R$ is trivial.

The only thing left is to compute $P$ in polynomial time, which is where I'm stuck. I have written this algorithm, but it's not correct:

for i = 0...n
    for j = 0...m
        if i == n || j == m // absorbing state
            P[(i,j)][(i,j)] = 1
        else if s[i+1] == r[i+1] // bits are the same => either in both strings the next bit will match or it will in neither
            P[(i,j)][(i+1, j+1)] = 0.5
            P[(i,j)][(0,0)] = 0.5
        else // bits are not the same => in both cases only one of the bits will match
            P[(i,j)][(i+1,0)] = 0.5
            P[(i,j)][(0,j+1)] = 0.5

The problem with this algorithm is that in case a bit does not match, the matching prefix length may not be zero, for example on sequence $010...$ for the string $011$ the matching prefix length will be $1\rightarrow 2\rightarrow 1\rightarrow\ldots$, instead of $0$, as my algorithm implies.

Here is the rough idea, for determining the probability that $x$ appears before $y$:

Construct a DFA that accepts the language of all binary strings in which $x$ appears before $y$.
Take the adjacency matrix of the DFA, replace the edges by $1/2$ entries.
Relate the probability that you're after to this matrix, and using this, calculate the probability.

I'll let you sort out the remaining details.