Why doesn't parallelism necessarily imply non-determinism? I'm a student reading a book on threads. And I got when I got to non-deterministic and parallel programs, I got a bit confused. I hope you can help me out.

I understand the difference between concurrency and parallelism. I get that concurrent programs are non-deterministic depending on the precise timing of events. "But parallelism doesn't necessarily imply non-determinism" - as said in the book. Why is that?

Does that imply that it's all dependent on the languages that support parallelism. Which implies that these languages should execute parallel programs in a deterministic manner?

Another question that I have is that the timing of events of concurrent programs depend on what exactly on what exactly? The architecture of the machine?

The book is using the term non-deterministic in two different ways.  In concurrent computations and parallel computations the order in which the computations occur is non-deterministic.  The final result however may (or may not) be deterministic.

Consider the following example:

thread A        thread B
--------        --------
x = 0           y = 1

The x assignment might happen before the y assignment, or the y assignment might happen before the x assignment, so the order is non-deterministic, but the end result after both threads finish is that x contains the value 0 and y contains the value 1.  So the result is deterministic.

The two major ways in which we achieve deterministic results from non-deterministic ordering is (a) by performing completely independent computations in different threads and (b) by taking advantage of operations that are commutative and/or associative.  An example of case (b) is if you have an atomic addition operator:

thread A               thread B
--------               --------
atomic_increment(x)    atomic_increment(x)

At the end of the computation x will have a value 2 larger than it had before the computation, no matter whether thread A's increment happened before thread B's increment, or the other way around.


BinaryTree minimum possible height I have one question for which I don't know any good solution (and my solution doesn't satisfy constraints). Namely, on one of the interviews i got problem like this:

  Determine the minimum possible height of the binary tree, if you could
  remove numNodes leaf nodes from the tree (where after removal of all leaf children of node n, the node n becomes the new leaf node, and can be also counted as leaf). You are given the function int minimumHeight(Node* root, int numNodes), where root is the pointer to the root of the tree, which should be completed, using any oop language.

Constraints are that you can't actually delete node from tree, and you can't use queue or stack, arraylist, list, hashmap, hashset, etc. (you cannot use any built-in c++ stl data structure, you can though make your own from scratch)  My solution used BFS where I stored for each node its level in tree using hashmap m, and created an array arr which contained all nodes, and then sorted it based on node levels in ascending order, and after that the function should return m.get(arr[arr.length-numNodes-2]). (i wrote code in java)
Without constraints I think this could work,but I guess it's not good enough.. Does someone maybe know is there some more elegant way to solve this? (without using unnecessary data structures, and maybe without any sorting) Thank you in advance!

Here if numNodes is 5, the minimum height you could obtain is 2,because first you must delete nodes with 5,11,4 or 2 value,and then you can delete nodes with values 9,6,etc. so in total you will have 5 possibly removed nodes, and 2 will be the minimum height of the tree.

I would leave a comment but I have less that 50 rep.

So, if I understand the question, DFS (or a way to parse the tree) is inevitable and all you need is an array (one cell for each level, plus one for the leaves) to count how many nodes are on each level. So given the numNodes you can start decrementing from the last (non-zero) element and check which would be the last non-zero element you will reach.

Also you don't actually need a stack, cause it is already implemented from the OS for you. So you just need to use a recursive algorithm passing each time the correct part of the array to the next call to calculate the nodes in the sub-tree. Now, all you need to know is the initial length of the tree. You run again the kind-of the same recursive algorithm but this time you are interested to know the total number of elements in the tree. Then the length of the array would be equal to the length of the total elements in the tree.

Time: O(n)

Space: O(n)

I'm not sure if I can write code here. I hope I was clear :)


Are two elements always in a relation within a partially ordered set? In a partially ordered set, am I always able to order two arbitrary elements out of the set? Or is it possible that two elements within the set have no order relation to each other?

For example if there are three elements $\{a, b, c\}$ and $a \leq b$ and $a \leq c$, does either $b \leq c$ or $c \leq b$ have to hold?

I need this to understand the fixed point theory for semantics of programming languages (denotation of while loops).

In a partially ordered set, there may be members which are not comparable. A partial order where all elements are comparable is called a total order.

We say $a$ and $b$ are comparable when at least one of the following holds:

$a\leq b$,
$b \leq a$.


How internet speed is manipulated at the physical level Although I am a computer science major, I am having a hard time understanding how internet providers have control over internet speed (example: offer different speeds to different customers, one with a higher price, etc.).

And I mean how is it that they do it at the physical level or bit level if I may. I think that they might have some tool that let more bits flow through a certain pipe or something like that. I would appreciate if someone could answer my question or ask me any clarification about my inquiry if it's not clear.

This is a very wide topic indeed.

Basically, there are two ways to measure and control the speed of a connection: physical speed and logical speed.

Physical speed is determined by the technology, protocol and sometimes the physical conditions of the line. For example, a Fast Ethernet has a physical speed of about 100 Mbps, meaning that it could in theory transmit information at 100 Mbps at physical layer (brute bits). Most current optical fibre connections can reach several gigabit per second of brute speed.

In some case, the physical conditions may affect the physical speed for a particular link. In those cases, a initial negotiation when the link is established determines the maximum physical attainable speed. This is how old modem and current xDSL systems work.

On the other hand, there is a logical speed in the line, usually lower than the physical connection. In most current systems, at a logical (more abstract) level, the information travels in packets. Ethernet for example uses Ethernet packets, which usually is comparable to IP packets but not always. ATM networks use ATM packets that contains 53 bytes of data (48 of them are payload).

Now the relationship between both speeds: single packets travel at physical speed. If you have at home a GPON (fiber) connection, it may have a physical speed of 2.4 Gbps. Every GPON packet will travel at 2.4 Gbps. So how the speed provided to the user is limited? Limiting the packet rate at a higher level. Send a 1 Kbps packet every 1 ms, and you just limited the perceived speed to 1 Mbps. This can be easily done by software, allowing all kind of traffic control, burst control, congestion control, monitoring, etc.

Deploying a high-speed physical connection to provide low-speed logical speed services has several advantages:

The same physical link can serve for different logical speeds. Same technology makes the deployment easier and the manufacturing cheaper.
Logical speed can be modified to any value, at any time, simply by a change in the configuration of one or more devices. No need to replace equipment unless you need to provide more speed that the one supported by the physical layer.
The same physical link can be used by more people, and this is key. If you have a 1 Mbps service using fibre or cable connection, the physical layer would be unused between your packets. But it can be used for other user's packets, it is shared. And it is aggregated in the network hierarchy. A 10 Gbps link can carry thousands of low-speed link from thousands of users.

I hope this is clear and answers your question, but certainly it is just a very simplified overview. Feel free to ask more questions or clarifications.


How will Big O be with quantum computers? I don't even know if this is the right place to ask this this...but how will Big O be with quantum computers? More specifically, will the worst case always be constant? If yes, how will this change our understanding of current algorithms? For example, will this mean that the difference between an algorithm running at Big O(2^n) and another running at Big O(n^2) in traditional computers be insignificant in a quantum computer? Would time complexity even be an issue with quantum computers? This might have a very obvious answer but I don't know the answer (and I'm really am curious).

Big-O has nothing to do with quantum computers. This should be obvious by the fact that Big-O notation was introduced in 1894, long before we had any knowledge of quantum theory … or computers for that matter.
Big-O is simply a convenient notation for classifying growth rates of functions. Big-O doesn't care how you interpret those functions.
So, the definition of Big-O will not change for quantum computers for the simple reason that its definition has nothing to do with computers.


About the relationship between non-termination and inconsistency? I've been trying to get into Agda and I noticed that it doesn't have recursion, which implies that it isn't Turing-Complete.

From what I could understand, if Agda had recursion, it would make itself an inconsistency from a type theory perspective.

Something stuck to my mind: Is it possible to exist a language that it isn't strongly normalizing but, yet, consistent? Or does the existence of recursion mandatorily implies inconsistency?

Some trivial type systems

Let the set of types be $\bot,\top$ and the sets of terms be $a,b$, with typing rules

$$
\vdash a:\top \qquad \vdash b:\top
$$
and computational rules
$$
a \to b \qquad b \to a
$$

Then, the resulting system has no (weakly/strongly) normalizing terms, yet it is consistent since no term inhabits $\bot$.

We can also allow recursion on $\top$, if we want.

$$
\dfrac{
\Gamma, x:\top \vdash e:\top
}{
\Gamma \vdash {\sf rec}\ x. e\ :\top
}
$$
with the obvious computational rule
$$
{\sf rec}\ x. e \to e\{{\sf rec}\ x. e/x\}
$$

On adding full recursion

Of course, we can't allow unrestricted recursion on $\bot$, otherwise ${\sf rec}\ x.x:\bot$ leads to an inconsistency.

Adapting more serious type systems

If we take any strongly normalizing typed lambda calculus, we can modify the computational rules to add a silly reduction step
$$
t\to t
$$
for any term $t$.

The new calculus has as inhabited types the same inhabited types, so it preserves consistency. The calculus is not even weakly normalizing, though.


Cliques in an alternate graph representation EDITS: corrected $r$ to add edges just like $f$ does in paragraph 8 per the first comment below. Also specified the Clique problem of interest in paragraph 2.

Having received no response to this question on math.SE, I'm asking it here. Thanks for your help.

In the Wikipedia article on the Clique problem, we are told that under the brute-force algorithm, there are potentially exponentially many subgraphs of a given graph that must be checked as possible cliques. The particular Clique problem I'm interested in is the problem of finding a clique larger than a given size.

Informally, the question here is whether an unknown representation of graphs will also have a possibly exponential number of subgraphs that must be checked as possible cliques under the brute-force algorithm.

I'll try to make this more precise by first giving a function to build up normal graphs, and then a new, different function to build up the unknown representation with properties that the new function must satisfy. The whole discussion here is about undirected graphs.

Let's start by defining an operation that will build up a normal undirected graph. Let $E$ denote the null graph: $0$ nodes, $0$ edges. Let $f$ be the following operation:

$f(n_1, n_2, G)$

$f$ takes a graph $G$ and returns a graph with the edge from $n_1$ to $n_2$ added to $G$. So while the null graph $E$ is definable without $f$, all other standard graphs in our discussion are built by $f$: $f(n_1, n_2, G)$ where $G$ could equal $E$.

As an example, the expression $f(n_1, n_2, E)$ returns the graph $(\{n_1, n_2\}, \{(n_1, n_2)\})$.

Now consider an alternate graph representation $H$, built by a function we'll call $r$ that adds edges like $f$ does. But $H$ is an unknown representation that must obey the properties below.

First let's describe a similarity relation ($\sim$) between $G$ and $H$:

Case 1. $G \sim H$ if $G = E$ and $H = E$.
Case 2. $G \sim H$ if $G = f(n_1, n_2, G_1)$, $H = r(n_1, n_2, H_1)$, and $G_1 \sim H_1$.

As before, the null graph $E$ is definable without $r$, but all others in the unknown representation are built by $r$: $r(n_1, n_2, H)$ where $H$ could equal $E$.

The representation $H$ must obey the following properties:

Just as $G$ is built by successive applications of $f$ to the null graph $E$, $H$ is built by successive applications of $r$ to the null graph $E$.
The order in which the edges of a graph are added doesn't matter:
in ordinary graphs, $f(n_1, n_2, f(n_3, n_4, G)) = f(n_3, n_4, f(n_1, n_2, G))$; in the unknown representation, $r(n_1, n_2, r(n_3, n_4, H)) = r(n_3, n_4, r(n_1, n_2, H))$.
Since we're talking about undirected graphs, the order in which the nodes of an edge are specified doesn't matter: in ordinary graphs, $f(n_1, n_2, G) = f(n_2, n_1, G)$; in the alternate representation, $r(n_1, n_2, H) = r(n_2, n_1, H)$.
Just as for $G$, $H$ has an operation $hasClique(\{n_1,...,n_k\}, H)$ which is true exactly when there is a clique among the nodes $\{n_1,...,n_k\}$.
Consider a graph $G$ with nodes $\{n_1,...,n_m\}$ and a subset $\{n_i,...,n_j\}$ and $G \sim H$ for some $H$. Then we require that nodes $\{n_i,...,n_j\}$ form a clique in $G$ if and only if the nodes $\{n_i,...,n_j\}$ form a clique in $H$. What I'm trying to capture here is that $H$ has a clique wherever $G$ does and vice versa for $G \sim H$.

Question: Can we conclude that $H$ has potentially exponentially many subgraphs that must be checked as possible cliques under the brute-force algorithm, just as in normal graphs?

You haven't specified exactly what your output is, but if it is the standard "output all maximal cliques", then the size of your output is exponential in the worst case, and therefore regardless of what algorithm you use, or what your representation* is, the algorithm may have to spend exponential time, just to output the answer.

*This is assuming the number of cliques you can represent in a single machine word is at most polynomial (which it clearly is, for any reasonable model).


How does the Vertex Cover algorithm by Chen et al find its tuples? I'm still fighting with the aforementioned paper "Improved upper bounds for vertex cover" by Chen, Kanj, Xia (PDF kindly provided by Yuval Filmus).

My current problem is that it's specified that the main vertex cover algorithm VC (page 7/21) has the following header VC(G, T, k), where G is the graph to process, T is a set of tuples and k is the bounding parameter.

My question is: what should the set of tuples contain in the first execution of VC?

It's said multiple times that the algorithm maintains this structure and generates tuples.
This is obvious, given the Reducing subroutine behavior.

What is giving me trouble is that Reducing is called before any further logic in VC and Reducing itself begins with a loop saying for each tuple (S, q) in T, which implies that the set T should be pre-populated.

Should I scan the whole graph for all the structures that would fulfill the criteria for being included in T? This seems a bit drastic, since the operations of Struction and General-Fold will cause the structures in T to be invalidated.

Currently, my best bet is that, given the list of priorities (page 8/21) of certain structures as well as the definition of a good pair (page 5/21, after Observation 3.3) I should search the whole graph for tuples, good pairs and vertices with high degrees and put them into T with appropriate priorities.
The first sentence from section 4. The algorithm VC (page 8/21) seems quite convincing:

  A tuple, a good pair, or a vertex of degree at least seven, will be referred to by the word structure. The algorithm will maintain a list of structures T, and then it will pick a structure and process it.

Can somebody provide some intuition?
Maybe I'm just missing something that's staring at me from the paper itself...

Reading deeper into section updating tuples (page 6/21), one can see the following paragraph:

  Since a tuple imposes certain constraints on the minimum vertex cover sought, one needs to be careful that the
  constraints imposed by the creation of a tuple do not conflict with the conditions imposed by other operations of the algorithm.

  The other operations that do impose constraints on the minimum vertex cover sought are the creation of (other) tuples, the struction operation, and the general folding operation.

  For example, the general folding operation assumes that when we are looking for a minimum vertex cover, we can look for one that either contains the set I or the set N ( I ) in the structure ( I , N ( I )) . This is mainly the reason why the set N ( I ) can be folded.

  If the general folding operation is applied, then this constraint imposed by the operation on the minimum vertex cover might conflict with the constraints
  imposed by a certain tuple. Therefore, to be on the safe side, when we decide to apply the struction or the general folding operations, we will invalidate all the constraints imposed by the tuples. That is, we will basically remove all the tuples.

So, even when I pre-seed T with some structures, they will most likely be removed anyway sooner or later, leaving an empty set and going back to square 1.

The beginning of Section 4 states:

  A tuple, a good pair, or a vertex of degree at least seven, will be referred to by the word structure. The algorithm will
  maintain a list of structures $\mathcal{T}$, and then it will pick a structure and process it. ... We will assume that the algorithm implicitly
  updates the structures in $\mathcal{T}$ and their priorities after each operation.

It seems that you shouldn't really think of $\mathcal{T}$ as a parameter, but as a dynamically updated list. As for intuition, I suggest that you read the full paper. Once you understand the proof, you should be able to come up with some sort of intuition.


Sorting array with two elements - in place and minimal number of comparisons, lower bound Algorithm must be in place.
I would like to find lower bound for comparison algorithm. Algorithm will sort array with only two elements - without loss of generality let assume that there are only $1s$ and $0s$.

Decision tree give us lower bound $\log(n+1)$.  It is to weak, because we know lower bound for findiing minimum, hence our algorithm must do at least $n-1$ comparisons.  If it is lower bound ?  I don't, but I think that it is $n$.

Why Do I think that lower bound is equal to $n$ ?

Let consider array $|a|=n$ such that $a[1]=a[2]=...=a[n-1]=0$ and $a[n]=1$.

It is needed at least $n-2$ comparisons to check that there is $n-1$ equal elements. And additional $2$ comparisons to check that $1$ is greater then rest of elements.

What is it real lower bound? What about my justification ?

Edit: We assume model computation as comparison $\le$.

$n-1$ comparisons are necessary and sufficient. To show that $n-1$ comparisons are necessary, we consider an adversary that always answers "EQUAL". Suppose that an algorithm makes at most $n-2$ comparisons. Construct a comparison graph whose vertices are the array elements and whose edges are the comparisons. Since the graph has at most $n-2$ edges, it is not connected. Let $C_1,C_2$ be two connected components. It is consistent that the value of all elements in $C_1$ is $0$ and that the value of all elements in $C_2$ is $1$. It is also consistent that all elements in $C_1$ are $1$ whereas all elements in $C_2$ are $0$. No monotone ordering of the array is consistent with both options, showing that the algorithm is incorrect.

To show that $n-1$ comparisons are sufficient, consider the algorithm that compares the first element to all other elements. There are three cases to consider:

The first element is equal to all other elements. In this case the array is already sorted.
The first element equals the elements in $S$ and is smaller than the elements in $T$. Thus the first element and the elements in $S$ have the value $0$ and the elements in $T$ have the value $1$, and we can sort the array accordingly.
The first element equals the elements in $S$ and is larger than the elements in $T$. This is symmetric to the previous case.


Generating intermediate code I have a problem in backpatching "if-else"
statements, for generating 3 address codes.

The grammar rule is :

  S -》 if E then M1 S1 N else M2 S2

The semantic rules are : {

 backpatch(E.truelist, M1.quad)
 backpatch(E.falselist, M2.quad)
 S.nextlist = merge(S1.nextlist, N.nextlist,
 S2.nextlist)

}

Explanation :

  Merge(p1, p2) : concatinates lists pointed by p1 and p2)

  Backpatch(p, i) : inserts i as the target label for each of the statements in the list pointed to by p)

  S.nextlist : "goto" statements to the next instruction after this statement (s)

I don't understand why we need "N" in the semantic rules above.
Why should we merge N.nextlist along with S1 and S2 nextlists for getting S.nextlist?? I mean why there is "N.nextlist" among other inputs?
Tnx for answering, in advance :D

Normal assembly for if/then/else looks like:

JMP_FALSE <condexpr> elselabel
<thenstmt>
JMP endlabel
elselabel:
<elsestmt>
endlabel:

(You can substitute mnemonics as appropriate for your instruction set.)

This "backpatch" term is probably something specific to some specific code that your professor wrote, or the author of the textbook that you're using. In either case, it's not a promising term.

The "truelist" and "falselist" likely refer to definite assignment (and definite unassignment) tracking; most modern languages keep track of what variables (aka registers) have been definitely assigned (for at-least-once purposes) and some, like Java, keep track of what variables are definitely unassigned (for at-most-once purposes, like Java "final"). Having implemented this a few times, I've used both a non-sparse (custom bit array/set) and a sparse data structure for tracking assignment impact within a scope; in Java, the language is simple enough that register assignment can occur before definite assignment analysis, so the bit array works beautifully (since you can know the zero-based register numbers and use them as the bit indexes).

The "N" probably refers to the unconditional jump to end of if/then/else statement. Again, it's not a promising term, since it implies a number, and IR/assembly should never be dealing with a number when a label will do.

The "quad" term is another made-up term specific to whomever wrote the material that you are working from.

Also: s/them/then


A* Search Algorithm Implementation with Priority Queue I've got a question regarding the A* search algorithm's implementation.

According to Wikipedia, one has to use a priority queue for retrieving the next node with the lowest f value, is it possible to skip to a node that is not a direct descendant of the current node?

For example:
Say we start with node S (set f=0), then add nodes A (with f=5) and B (with f=3).
B is obviously picked, then we add its descendant C (with f=4). Since the priority queue holds A(5) and C(4), C is now picked.
With C we encounter two additional nodes, D (with f=7) and E (with f=8).
Clearly A has the lowest f value in the queue, which means it should be picked, however, it does not have a direct connection with C.

Is it possible to continue developing A even though it is not a direct descendant of C? or is it that D should be picked to develop.
Using a naive priority queue would choose A, is that fine?

Yes, you move on with A.  You always pick the element in the fringe that minimizes $h(x) = f(x) + g(x)$.


Counting the number of satisfied models - given mathematical constraints Question
There are plenty of algorithms for solving the #SAT problem, with one being the DPLL algorithm and is implemented for all kinds of programming languages. As far as I've seen, they all take a boolean formula on CNF as input and outputs the number of satisfied interpretations.
Mathematical constraints, on the other hand, is another way defining an instance of SAT-problem and is often used in discrete optimization, where one tries to optimize some function with respect to these constraints. Is there a program taking mathematical constraints as input and outputs the number of satisfied interpretations?
Example
We represent the boolean formula $Q = (a \lor b) \wedge (c \lor d)$ as constraints as $$a + b \geq 1 \\ c + d \geq 1$$ or as a matrix $A$ and support vector $b$
$$
A=
\begin{bmatrix}
    1 & 1 & 0 & 0 \\
    0 & 0 & 1 & 1
  \end{bmatrix} \\
b = \begin{bmatrix} 1 & 1 \end{bmatrix}
$$
where all variables $a,b,c,d \in \{0,1\}$. We know there are programs taking $Q$ as input and outputs the number of interpretations but are there programs taking $A$ and $b$ as input (or similar construction) and outputs the same number of interpretations?

I know of two reasonable approaches.

Approach #1: Count the number of integer points inside a convex polytope.

The set of linear inequalities you provided, together with the inequalities $0 \le a,b,c,d \le 1$, defines a convex polytope.  Now, you want to count the number of integer points that fall within this polytope.

There are standard algorithms for doing that, which you could apply directly.  If you search on "counting integer points in polytope" or "counting lattice points in polytope" you'll find many research papers.  See, e.g., https://cstheory.stackexchange.com/q/22280/5038, Finding all solutions to an integer linear programming (ILP) problem.

Approach #2: Convert to CNF, then use a #SAT solver.

You can always convert your constraints to a CNF formula.  Each linear inequality can be converted to a set of CNF clauses.  A linear inequality of the form $x_i + \dots + x_j \ge 1$ corresponds immediately to the CNF clause $(x_i \lor \dots \lor x_j)$.  For a more general linear inequality of the form $x_i + \dots + x_j \ge c$, you want to express the constraint that at least $c$ out of the $k$ variables $x_i,\dots,x_j$ are true.  There are many standard ways of encoding that.  See https://cstheory.stackexchange.com/q/23771/5038, Reduce the following problem to SAT, Encoding 1-out-of-n constraint for SAT solvers,

(One approach is to convert a Boolean circuit that computes $x_i + \dots + x_j$ and compares it to $c$, then convert the Boolean circuit to CNF using the Tseitin transform.  You can create such a Boolean circuit by using standard adder and comparator circuits.  However, there are many other ways as well.)

Once you have a CNF formula that is equivalent to the set of constraints, then you can use any off-the-shelf #SAT solver to count the number of solutions to that CNF formula.

It's hard to say which of these two approaches will work better;  you might need to try them both on the kinds of instances you're dealing with, to know for sure.  I'd expect that if you have linear inequalities of the form $x_i + \dots + x_j \ge c$ where $c$ is large, then Approach #1 may be superior; but if $c$ is typically small, then Approach #2 may be superior.


cheap multi agent path planning algorithms I am trying to make a tower defence game where some critters are trying to make their ways through a 2D grid-like obstacle course. The idea is these critters cannot walk into the obstacles or into each other during their path, and they would like to get to the other side as soon as possible.

I just need a cheap, not-optimal solution that can path all the agents from one side of the map to another, moving in the grid (up-down-left-right) directions while not walking into each other nor into the obstacles.

I am not wanting an optimal solution, just one that looks reasonably greedily optimal would be nice (i.e. not like not moving the 2nd agent without completing the path on the first agent, etc).

I'm thinking about something with potential fields with a little bit of A* is as much as I am willing to compute. If there's anything simple to implement I'd be happy to know ! !

I would do a unique breadth exploration from the exit to get the shortest distance to exit of any position. Only obstacles (like walls) should be considered, not critters. This exploration should be done again each time an obstacle is added or removed. With some optimization, you may not have to recompute all the positions.

Then each time a critter should move, check if any accessible position has a better (lower) distance to exit. If not, the critter stay in position, else it moves to the one with the lowest distance to exit.

By "any accessible position", you can consider either up-down-left-right or something more complicated (moving more than one space, jumping obstacles and so on...).


minimum number of points a convex hull must have Quick question:
Say for example there are 10 colinear points. my question is does a convex hull have to be a convex polygon? or can it be a line as well according to the formal definition of the convex hull?
Thanks in advance.

The convex hull of 10 collinear points is the line segment between the two extreme points.
No, a convex hull does not have to be convex polygon. A convex hull can be a point, a line segment, a ray, a line, a convex polygon, a circular sector, a half plane, a cubic, etc. .
A definition in math, such as the definition of convex hull, is the strictest kind of definition. It means exactly what it says. No more, no less.


How realistic is the i.i.d assumption in the definition of Shannon's entropy? Let me first say I come from a physics background and have about zero exposure to computer science, so the question may be very naive. Shannon's entropy looks perfectly natural and useful from a statistical/thermal physics point of view, but now I'm trying to understand how it is applied for real computers.

Normally the messages we want to store and process in a computer have grammar and meanings, which seems to suggest the symbols constituting the message must follow some conditional probability distribution, and the utterance of the symbol at the nth position should change the probability distribution of the symbol that will appear at the (n+1)-th position. However, in Shannon's definition symbols are assumed to be independent and identically distributed random variables, which seems to be far from realistic, so how come it is still a useful concept for computers?

No.  Shannon's definition is perfectly general.

There is a special case when the symbols are iid random variables, and you might have seen a formula for that special case (which is indeed simpler), but the definition is fully general.  Note that when we write the entropy $H(X)$, you should take the random variable $X$ to be the entire sequence of symbols.  Then the standard definition applies directly, and doesn't assume that each individual symbol in $X$ is iid.


Checking large number of configurations with multiple constraints I have a very large number of constraints such as:

$ A1 \land B1 \land C1 \land D1 \land E1 \land F1$
$ A2 \land B2 \land C2 \land D2 \land E2 \land F2$
$ A3 \land B3 \land C3 \land D3 \land E3 \land F3$
$ A4 \land B4 \land C4 \land D4 \land E4 \land F4$

Here a constraint is a condition. For example, A1 is (response time < 10). All the condition needs to be satisfied such that the configuration is feasible. For instance, the configuration 1 needs to have A1, B1, C1, D1, E1 and F1 =1. How can I quickly check which configurations are valid? At moment I'm using a CSP (choco-solver) and iterate over each configuration and check the conditions. Is there a better (faster) way to do this rather than just checking the configuration one by one?

Apparently, based on your comments, each condition is a linear inequality, you have a list of conditions, and you want to test whether an assignment satisfies all of the conditions, or find an assignment that satisfies all of the conditions.

Testing whether an assignment satisfies all of the conditions is just a simple matter of programming. For each inequality, you just plug in the values of the variables, then test whether the inequality holds or not.  No special solver or anything is needed.

It's also possible to find an assignment that satisfies all of the conditions, i.e., find values for all of the variables that makes all of the conditions true.  This is exactly the linear programming problem.  There are good, efficiently algorithms known for linear programming.  You can use any off-the-shelf linear programming solver.  They should very rapidly find a valid configuration.


Find Hamiltonian cycle in polynomial time I want to know for what types of graph it is possible to find Hamiltonian cycle in polynomial time. It would be helpful also to show why on some types of graph finding Hamiltonian cycle would be only possible in exponential time.

Perhaps the most comprehensive list is available via ISGCI, along with references. Examples for which the problem is easy include bounded treewidth graphs and many subclasses of chordal graphs.

As to why exponential time seems unavoidable in general, we don't strictly know. As far as we know, P = NP is also possible.


Recursion Tree Analysis by Leaves Assumptions
Let's say we have any recurrence relation (however this is perhaps more applicable to "unpredictable" recurrence relations):
$$T(n) = \;?$$
For example:
$$T(n) = aT\left(\frac{n}{b}\right) + h(n)$$
We could have this recurrence where the input is an array of length $n$ and $a$ and $b$ are determined by particular functions of the array values (e.g. max value, min value, median value, etc.)
This is "unpredictable" in the sense that we do not know precisely how the tree will be structured for any given $n$.
Let's say that in the worst case the following holds:
$$T(n) = \Theta(f(n))$$
Let $L(T(n))$ be the function mapping to the total work (number of basic operations) done at the leaf level (base cases) of the recurrence relation $T(n)$. Now let's say in the worst case of $L$ (not $T$), the following holds:
$$L(T(n)) = \Theta(g(n))$$
Question
Does the following hold:
$$L(T(n)) = \Theta(g(n)) \implies T(n) = \Theta(f(n))$$
That is to say, if the work at the leaf level is worst case, does this imply that work of the total recurrence tree is worst case?

This has particular value if you don't necessarily know how the recurrence is broken up or divided throughout the tree. Perhaps you could bound the worst case work done at the leaf level and reverse engineer the tree to show the worst case overall. Alternatively, though not as useful, you may be able to prove the following:
$$T(n) = \Theta(f(n)) \implies L(T(n)) = \Theta(g(n))$$

Here is an example recurrence:
$$T(n, m) \leq \begin{cases}
n^2 & m = 1\\
m^2 & n = 1\\
O(\min(n,m)) + \displaystyle \max_{i \in \{1 \ldots \min(n,m)\}} \left\{ T(n - i, i) + T(i, m - i)\right\} & \mathrm{otherwise}
\end{cases}$$
In this case, determining the splits is rather difficult. However, analyzing the worst case on the leaf nodes is rather simple. When we think about the recursion tree, the work at the leaves will be maximized when $n$ and $m$ are as large as possible. Namely, $T(1, m - 1) + T(n - 1, 1) = (m-1)^2 + (n-1)^2$. Now, if we know this will be the worst case overall, e.g. $$L(T(n,m)) = \Theta(n^2 + m^2) \implies T(n,m) = \Theta(f(n,m))$$
We can deduce the splits in recursion that made it this way:
$$\begin{align*}
T(n,m) &= T(n-1, 1) + T(1, m-1) + O(m + n)\\
& = \Theta(n^2 + m^2)
\end{align*}$$

The master theorem is a very thorough answer to this question.

Let us consider the three cases of the theorem, as applied to the recurrence $T(n) = aT(n/b) + f(n)$:

$f(n) \ll n^{\log_b a}$: in that case most of the work is done at the leaves.
$f(n) \asymp n^{\log_b a}$: in that case the work done at all levels is similar.
$f(n) \gg n^{\log_b a}$: in that case most of the work is done at the root.

Other recurrence relations behave differently. As an extreme example, there is no natural Case 1 for the recurrence $T(n) = T(n-1) + f(n)$.


What is the reasoning behind magic constancs in hash code calculations found in programming practice? In real-world programming, we frequently need to compute hash codes for complicated objects. The main desired properties are that the values should

be deterministic and
have few collisions.

Let's assume we have access to robust hashing for basic data types such as integers, strings, etc. How do we combine multiple such hash codes to a single one, say for an array or a struct with several properties?

I immediately went for XOR-ing all "child" codes, figuring that the "spread" of the original hash function should be maintained, roughly.
Apparently, I'm not alone.

However, if you google around, you find other approaches.

Here an answerer proposes adding hash codes after perturbing them by some multiplication.
This asker uses XOR but multiplies the individual codes with some numbers, apparently consciously choosing "large" primes.
Here, the author states that "[things] have low values (favour the lower bits), so they should be combined with a multiplication to spread them across a wider bit range of the hash code".

The reasons given, if any, seem vacuous to me. Does multiplying already "random" values with a (small) constant really serve any purpose? Does it matter if the factor is a prime (which everybody seems to assume)?

XOR is not a good method, because then the hash of $(a,b)$ will be equal to the hash of $(b,a)$.  Also, the hash of $(a,a,c)$ will be equal to the hash of $(b,b,c)$ and to the hash of just $c$.  That's not good.

A better method is to make the hash of $(a,b)$ be equal to $H(H(a) || H(b))$, where $H$ is your hash function on basic objects (ints, strings, etc.) and where I am using $||$ to represent concatenation of bit strings.  This avoids all of those degeneracies.

The particular constructions you mention can be viewed as instances of that approach:

The first link basically proposes using $H(a) + 37 \times H(b) \bmod 2^{64}$.  That's equivalent to the construction $H'(H(a) || H(b))$ where $H'$ is a standard Rabin-Karp hash function.
The second link is $1013 \times H(a) \oplus 1009 \times H(b) \bmod 2^{64}$.  That has the form $H''(H(a) || H(b))$ where $H''(x||y) = c_1x \oplus c_2y$, which is also a reasonable hash function (though it takes a little bit of algebra to prove it).
The third link is $(c \times H(a)) \oplus H(b) \bmod 2^{64}$ where $c$ is a prime.  That's the same as the previous one, but with $c_2=1$.  It also turns out to be a reasonable hash function.

Does the constant multiplier (e.g., 37) need to be prime?  No, it only needs to be relatively prime to the modulus.  If the modulus is a power of two (as in these cases), it only needs to be odd.  A prime is sufficient but not necessary.  To obtain provably good results, the constant multiplier should be chosen at random; in practice, we fix a particular value and hope that will be close enough for practical purposes.

Another reasonable method is to use $H_1(a) + H_2(b)$ or $H_1(a) \oplus H_2(b)$ as the hash of $(a,b)$, where $H_1,H_2$ are two independently chosen hash functions.  This also works.. but is a little more annoying to implement, because it requires us to have multiple hash functions.

Is there some theory here?  Yes, you can prove that if $H_1,H_2$ are drawn uniformly at random from a 2-universal hash family, and $+$ is a group operator, then $H_1(a)+H_2(b)$ will be a 2-universal.  The same is true for $H_1(H_2(a)||H_2(b))$.  I am not sure about what one can prove about $H(H(a)||H(b))$; I suspect it's not provably good in a generic sense, but is normally fine in practice.


What are activation records? What are the open activation records of a recursive algorithm ?

Edit:

Activation records are the number of times that we call a function that is not finished yet. Correct?

So we can find the number of activation records only when we are given a specific input array and we cannot say something for a general array with dimension n. Or can we?

Your question is very poorly stated, except for the title. There is not a single sentence that is really correct or meaningful semantically.

So I will stick to the title, and explain what is wrongt with the text.

Activation records are a programming language implementation concept. Programming languages
can be used to implement algorithms in programs, but the concept of an
algorithm is an abstract notion, rather than a concrete realization in
a specific programming language.

An activation record is a chunk of memory containing usually the local
data necessary to execute a subprogram call (the name vary with
languages, such as function, procedure, method, subroutine ...), as
well as memory and code control flow. More dynamic parts of the data
used may be stored in other places (heap).

Thus an activation record is not the number of whatever. But the number
activation records in use do, in general, correspond to the number of
calls that have not been returned ... though that is not
necessarily true in some languages (see below).

In simpler programming languages, subprogram calls are well nested so
that the first subprogram to be returned from is the last one that was
called. Hence activation records can be stored on a pushdown stack.
That will not apply to such control structures as coroutines.

Also, it may be that data in activation records can still be used by
the program after the subprogram has been returned. This happens for
example when the result of a subprogram can be another subprogram to
be executed later (I skip the details).

So, in such a case, one may have to keep in memory more activation
records than there are unfinished calls. And the pushdown stack no
longer works properly without specific techniques to handle the problem.

Last, this is a general concept. I have no idea what your input array is for or what it does in your program. So that I cannot answer you. Many programs do not have arrays at all, but do have activation records.


How to properly name the two types of RAM in a Paper? How do I name VRAM and RAM properly in a paper?
"Video RAM" is clear but the "normal" RAM? Is it called "CPU RAM" or "Processor RAM" or "Main RAM" or totally different?

I have usually heard "main memory" for the CPU-accessible RAM.
Wikipedia calls it "primary storage", with "main memory" listed as a synonym. Although honestly, I would have guessed that "primary storage" referred to the primary nonvolatile medium (SSD or HDD).


Karp hardness of an equidistant set in digraph Following the success of the undirected version:

Karp hardness of an equidistant vertex set

Inspired by the success of this long ago question:

NP-hardness of problem with indices and subsets

We move on asking for the hardness of the directed version of an equidistant set.

  Input: A directed graph $G(V, A)$ and a natural number $k$

  Output: YES if $G$ has an equidistant vertex set of size $k$, otherwise NO

In this problem, we disallow opposite arcs like $(u,v)$ and $(v,u)$ to be both present in the arc set, i.e. either one of them or none.

$\DeclareMathOperator{\dist}{dist}$An equidistant vertex set is a set of vertices $V'\subseteq V$ such that for every two ordered pairs of vertices $u, v\in V'$ and $w, s\in V'$, we have $\dist(u, v) = \dist(w, s)$, where $\dist(u, v)$ is the length of a shortest path between $u$, $v$. Note that in digraph, it is possible that $dist(u,v)\neq dist(v,u)$.

This is $NP$-complete by reducing from the undirected version which was proven hard by Yuval's reduction.

For every pair of vertices $u$, $v$ in the undirected graph, if $dist(u,v)=2$ then we create two new vertices $x_{uv}$, $x_{vu}$ and add 4 arcs $(u,x_{uv})$, $(x_{uv},v)$, $(v,x_{vu})$, $(x_{vu},u)$. This guarantees that $dist(u,v)=dist(v,u)=2$ in our digraph.

Finally, add two vertices $src$ with outgoing arcs to all original vertices and $dst$ with incoming arcs from all original vertices. Add $x_{src,dst}$ with two arcs similarly. Note that we do not have the opposite direction of $x_{dst,src}$.

Now set $k=m+1$.

It is necessary to manipulate the case of having some $x_{uv}$ vertex in an equidistant set. But, this is impossible (as long as $k=m+1>4$ like in Yuval's reduction). To see this, suppose that $x_{uv}$ is included in some equidistant set. Clearly, from $x_{uv}$ going out, in one step, you must end at $v$. And, to reach $x_{uv}$ in one step, you must go from $u$. So, there cannot be any vertex within distance 2 (in both directions) of $x_{uv}$, except for $x_{vu}$. So, our equidistant set can be of size only $2<m$.That means we cannot have any $x_{uv}$ vertex in our set. If instead we have $x_{src,dst}$ in our set, we can easily see that there cannot be any other $x_{uv}$ in our set. In all cases, we still have at least $m+1-1=m$-equidistant set without any $x_{uv}$ vertices.

Conversely, if we have an $m$-equidistant set in the undirected graph, then we can add $x_{src,dst}$ to this set to form an $m+1$-equidistant set.


What is the complexity of this bubble sort algorithm? I have been doing a little reading up on bubble sort and have read on wikipedia that it's complexity is measured as $\Theta(n^2)$

This bubble sort however is slightly more efficient. I thought this would be the best place to ask how I would work out this particular implementations complexity seeing that the number of iterations in the inner loop is reduced with each pass.

for (top = items.Length; top > 0; top--)
            {
                for (low = 0, high = 1; high < top; low++, high++)
                {
                    if (items[low].CompareTo(items[high]) > 0)
                    {
                        tmp = items[high];
                        items[high] = items[low];
                        items[low] = tmp;
                    }
                }
            }

The inner loop is executed $(n-1) + (n-2) + (n-3) + \dots + 0 = \tfrac{1}{2}n(n-1) = \Theta(n^2)$ times.


Understanding why ALL_nfa is in co-nspace I'm trying to understand Sipser's example showing that $ALL_{nfa} \in Co-NSPACE(n)$, where $$ALL_{nfa} = \{ <A> | A \text{ is an NFA such that } L(A) = \Sigma^*\}.$$

The algorithm can be seen here.

I'm confused by a few things, but mainly what is meant by "nondeterministically select an input symbol"? If I "nondeterministically" choose symbol 'a' and then mark all the vertices I can reach from the current ones by 'a', then don't I possibly miss out on the vertices reachable by 'b'? And even though we repeat this $2^q$ times, what's to stop me from choosing that 'a' transition each time?

If my instincts are correct, then what we are trying to do is convert the nfa to a dfa (which will have at most $2^q$ states). If the dfa has a single reject state, then we know the nfa has a string that will be rejected. However, we would like to do this without actually converting to a dfa, which might require too much space. So the provided algorithm tries to traverse the corresponding dfa graph, without actually building it?

To show that $ALL_{\mathsf{NFA}}$ is in $\mathrm{co-NSPACE}(n)$, we must show that the complement $\overline{ALL_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$.

The complement is

$$\overline{ALL_{\mathsf{NFA}}} = \{ \langle N \rangle \mid N \text{ is an NFA where } L(N) \neq \Sigma^* \}$$

To show that $\overline{ALL_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$ we therefore need to devise a Turing machine that, given an NFA description $\langle N \rangle$ can tell us if there exists an input that $N$ will not accept.

Essentially, the machine will nondeterministically guess a string $w$ and verify that this string is not accepted by $N$.  Our machine may guess the wrong string, but remember that the machine is nondeterministic -- as long as it is possible to guess a string with this property, the machine will accept $\langle N \rangle$.

To guess such a string $w$ and check that the NFA does not accept it, we need to explore all the possible computations of $N$ on $w$ and show that none of them will lead to an accepting state. This does not require us to construct an equivalent DFA using the subset construction; doing this would require more than linear space. However, even just storing all of the computations of $N$ on $w$ on the Turing machine tape will require more than $n$ tape cells.

The trick is to guess the string symbol by symbol and keep track of the sets of states that $N$ could possibly be in after it has read a symbol. If $N$ has $q$ states, there are $2^q$ such sets of possible states. We start with the set $\{ q_0 \}$ and guess a sequence of $2^q$ symbols. For each symbol that we guess, we record the subset of states that can be visited from any of the states that $N$ could be in now. We can keep track of this subset of possible current states using $q$ bits (represented as $q$ cells on the tape). This is linear in $n$ where $n$ is the length of $\langle N \rangle$. This description must at the very least list the states of $N$, so $q = O(n)$.

If the set of possible current states that we are now in does  not contain an accept state, then we have found a string that cannot be accepted by $N$. We may have to guess $2^q$ symbols, since each symbol could in principle lead us to a new set of possible current states that had not been seen before. But once all sets of possible current states have been examined, we can stop. We can count to $2^q$ in binary using no more than $q$ bits. Again this requires no more than $O(n)$ bits.


$\Omega(\sqrt[3]{n})$ lower bound on random-access memory? Here is a perhaps naive question that has been tingling me: Is there an $\Omega(\sqrt[3]{n})$ asymptotic lower bound for addressing arbitrarily large memory randomly? My cause of belief is that the shortest path to any memory stored physically must be through three-dimensional space, and the diagonal here must have some minimal length.

For example, when sorting arbitrarily many elements, then addressing these elements must eventually cost something proportional to the distance, and even if you have high-speed cable between every single point in some space, it seems as if there is a geometric limit bounded at higher than $\Omega(n \lg n)$.

What is wrong with my argument?

If you are talking about latency, yes, that sounds right to me.  A lower bound on distance implies a lower bound on latency, due to speed-of-light considerations.  However in practice these speed-of-light considerations probably do not dominate until the amount of memory is extremely large.

By the way, the situation is different if we are talking about bandwidth (i.e., the number of random-access memory operations performed per second), rather than latency.  One can process many random-access memory operations concurrently, by using sorting networks.

One important caveat is that you seem to be assuming an architecture where we have one big CPU on the left and one big memory on the right, and they are separated somehow.  However that's not necessarily the only way to structure a computation.  One can also structure a computation, for instance, as a parallel computation, where you have a 2-D or 3-D mesh of small processors each with their own local working memory.  Now accessing your local memory can be very fast, whereas accessing far-away memory is slow.  In some sense there is still a $\sqrt{n}$ or $\sqrt[3]{n}$ bound operating, but the $n$ is much smaller for local memory than for far-away memory, so if your algorithm is designed in a way that ensures that most memory operations are to local memory, then you may be able to "beat" the lower bound you described (in some sense).

In computer architecture, one often measures the performance of a circuit by the $AT$ measure: in other words, the area of the circuit ($A$) multiplied by the time it takes for the circuit to complete a computation ($T$).  If you like, you can think of this as a price-to-performance ratio: it is the price (which is assumed to be proportional to the area of the circuit) divided by the performance (the number of computations that can be performed per second, i.e., the inverse of $T$).  A standard architecture with a single beefy CPU and one big memory is not always the optimal architecture.  Sometimes you can get large speedups (more than a constant factor) by using parallel computation or other architectures.  This is at least partly due to exactly the issue that you mentioned: it is much faster to access memory that is near you than to access memory that is far away.  Caching (e.g., L1 cache, L2 cache, etc.) is also based upon the same principle.

Below is an example of a paper in the world of cryptography that considers design of special-purpose circuits for cryptanalytic tasks, and takes these issues into account.  For instance, it has a bunch of processors, a big memory, and a sorting network in between the two to route memory accesses from the processors to memory.  This enables a high number of memory operations to be "in flight" at once, even though it does not eliminate the latency.

The Full Cost of Cryptanalytic Attacks.  Michael J. Wiener.  Journal of Cryptology, 2004.

If you want to dive further into this line of thinking, there is an interesting (but mostly theoretical) debate one can have over whether the right metric is area or volume, i.e., whether the right lower bound is $\sqrt{n}$ or $\sqrt[3]{n}$.  Yes, the world is three-dimensional, but heat dissipation is two-dimensional; a massive cube of computers would be limited by its ability to dissipate heat, which scales with its surface area, not its volume.  One can continue onward in this vein. If this sounds like a fascinating topic, see Q.9 (pp.45-46) of the following paper:

Non-uniform cracks in the concrete: the power of free precomputation.  Daniel J. Bernstein and Tanja Lange.  ASIACRYPT 2013.


Is square numbers written in binary a regular language? I'm having problem trying to determine if all square numbers (1, 4, 9, 16, ...) written in binary form (1, 100, 1001, ...) is a regular language.

After some attempts to find a common pattern of those numbers, I found out that for any square number $n^2$, $n^2 mod 4$ either equals to 0 or 1, and so I am able to draw a DFA graph with 4 states to recognize this language. But apparently, the DFA I drew actually recognizes a superset of the square number language in question. I'm stuck here.

Anyone could give me some clues on this problem? If it's not a regular language, how should I prove it?

I am also very interested to know how I should approach to this kind of question the best way in the future. I know that in many cases, if we have the intuition that the automata has to keep a track of what is has seen already (like $a^i b^i$), then there's an undetermined states needed for the automata to compute, thus it's not finite or regular. We can then use Pumping lemma to prove it's not regular. However, I can't tell if this language is regular yet, so I don't really have an idea what to do next.

Thanks!

Here is a high-tech solution. Denote your language by $L$. Szalay showed that
$$
L \cap 10^*10^*1 = \{ 10^n10^{n+2}1 : n \geq 0 \} \cup \{110001, 1000010001\}.
$$
From here it's pretty easy to show that $L$ is not regular, by reduction to $\{a^nb^n : n \geq 0\}$.


Tree data structure for fast merges I need trees that have the following properties:

Each node in the tree has two values associated with it - a key and an associated opaque data element.
An internal node in the tree has unbounded number of children. The tree reflects a real world hierarchy that is in flux over time - hence the maximum number of children of a given node are not known ahead of time.
There is an ordering defined on sibling nodes that is a function of the keys stored in the nodes.

Allow the following operations to be $O(\lg n)$.

Update operations

merge(tree_1, tree_2) - Destructively consumes tree_1 and tree_2 to create a new tree which contains keys from both input trees. I realize now that this operation is underdefined, I will put more thought into the semantics of the merge.
insert(tree, parent_key, child_key, value) - inserts the given key-value pair into the given subtree rooted at the node pointed to by the parent key.
delete(tree, key) - Delete subtree rooted at node with given key.
update(tree, key, value) - Destructively updates the existing data associated with the given key-value pair.

Query operations

find(tree, key) - returns the value associated with the given key in the given tree.
get_tree(tree, key) - Return a subtree that is rooted at node with given key. The returned tree must a reference and share identity with corresponding nodes in the incoming tree. Modifying any nodes via the returned tree will hence result in changes to the initial tree.
children(tree, key) - Returns sequence of (key, data) of child nodes of node corresponding to key.

Things I looked at before I asked this question - Binary trees, AVL trees, Red Black trees, 2-3 trees and they were not suitable because of fixed degree of internal nodes.

If you have a guarantee that any given key will be present in at most one tree, you can implement these operations using the Union-Find data structure for disjoint sets.  Basically, you use the disjoint sets data structure to keep track of which keys are present in the same "tree".  Then, you have a separate hash table on the side to map keys to values.  With these two data structures, each of your operations can be implemented in $O(\alpha(n))$ time, where $\alpha(n)$ is the inverse Ackerman function.  In fact, you can treat each operation as running in essentially constant time.

Some examples of how to implement your algorithms:

merge(tree_1, tree_2): Invoke Union(tree_1, tree_2).
insert(tree, key, value): Check that key is not already present, by looking it up in the hashtable.  If it is already present, bail out (abort).  Otherwise, create a new singleton disjoint set containing just the value key.  Merge that new set with tree_1, using a Union() operation.  Insert (key, value) into the hashtable.
update(tree, key, value): Check that key is in this tree, by calling Find(key); if it's not, bail.  Then, update the mapping for key in the hashtable.
find(tree, key): Check that key is in this tree, by calling Find(key); if it's not, bail.  Then, get the mapping for key from the hashtable.
get_tree(tree, key): Check that key is in this tree, by calling Find(key); if it's not, bail.  Then, return key.
children(tree, key): Return the single-entry list [(key, value)] (pretend key is a leaf).

With this implementation, the merge operation has the side effect of destroying the old trees (so you are not allowed to retain handles to the old trees).   If you wanted a persistent data structure, you can look at persistent disjoint-set data structures.

However, this answer has two serious limitations: first, it does not allow you to specify or control the parent-child relationship; second, it requires that the key sets of the trees be disjoint (no key appear in more than one tree).  It sounds like these limitations make this answer unusable in your context, but I'm not certain yet (perhaps a future revision of the question will make this clearer).


What is the smallest $n$ such that $BB(n) > $Graham's number? BB represents the busy beaver function here. Do we even have any idea of what order of magnitude $n$ would have? Is it possibly around 10, or more like 1000?

If I recall correctly it started with $n = 64$, then $n = 25$ shortly after that with $n=23$, $n = 22$ and now $n = 19$.


Finding the sum of four squares There is Lagrange's four-square theorem, which statea that

  Given an integer $N$, we can write $N$ as a sum of four squares
  $A^2+B^2+C^2+D^2=N$.

How can I find a valid solution with time complexity of $O(1)$ or $O(\sqrt N)$? I only have to find one solution.

Here is my $O(1)$ algorithm:

while(count!=4){
     solution = sqrt(N)
     print solution
     N-= solution*solution
     count++
}

But it does not works for all $N$, for example it fails for $N=23$. Is there any other solution?

Try this: Legendre's_three-square_theorem

Assume $4\not\mid N$. If not, divide $N$ by $4^k$ and multiply $2^k$ back in the end. Find an $A$ satisfying $N-A^2\not\equiv0,4,7 \mod 8$. It's always valid to choose $A=\lfloor\sqrt{N}\rfloor$ or $\lfloor\sqrt{N}\rfloor-1$. (Choose the even one if $N\equiv 1,5 \mod 8$ and the odd one otherwise.) Now $N-A^2$ is an integer in $O(\sqrt{N})$ and you can find $B,C,D$ in $O(\sqrt{N})$ easily.

Edit: Since $B,C,D\le cN^{\frac{1}{4}}$ for some small constant $c$, we can enumerate two of them (suppose $B$ and $C$) and check whether the corresponding $D$ is an integer. This works in $O(\sqrt{N})$. There might be some faster solutions.


What is examples of languages to prove the inclusions between families of languages generated by matrix grammars? $\lambda M_{ac}$ = family of languages generated by matrix grammar with appearance checking and with erasing rules

$\lambda M$ = family of languages generated by matrix grammar without appearance checking and with erasing rules

$M_{ac}$ = family of languages generated by matrix grammar with appearance checking and without erasing rules

$M$ = family of languages generated by matrix grammar without appearance checking and without erasing rules

$RE$ = family of recursive enumerable languages

It is stated in [1] that

(a) $\lambda M \subset \lambda M_{ac} = RE$,

(b) $M \subset M_{ac} \subset CS$,

(c) $M \subseteq \lambda M$.

$M_{ac}$ can generate the language $L = \{a^{2^m} : m \geq 0  \}$, but $M$ probably cannot (if I'm not mistaken). Thus this yield the (b) above.

What are the examples of languages that can be used to prove the (a) and (c)?

Your shared wisdom, advice or hints are very appreciated.

[1] http://aleteya.cs.buap.mx/~jlavalle/papers/rewriting/tarraphd.pdf

To my knowledge, it is an open problem whether the inclusion (c) above
is strict. Some (baby) steps toward solving this problem can be found in

"Toward Understanding the Generative Capacity of Erasing Rules in Matrix Grammars", IJFCS 2011, http://dx.doi.org/10.1142/S0129054111008118

"On Erasing Productions in Random Context Grammars", ICALP 2010, http://dx.doi.org/10.1007/978-3-642-14162-1_15

"A Sufficient Condition for Erasing Productions to Be Avoidable", DLT 2011.
http://link.springer.com/chapter/10.1007%2F978-3-642-22321-1_39


In the dataflow programming paradigm programs are modeled as directed graphs. Are the edges of the graph variables? And are the vertexes functions? As I understand it in dataflow programming, programs are structured as directed graphs, an example of which is below

Is it true to say that the arrows (or edges) represent the variables within a program and the vertexes (blue circles) represent programmatic functions? Or is this too much of a simplification?
I am interested in understanding how dataflow languages actually apply graph theory.

To be precise, the nodes represent the blocks (consisting a set of statements) and the edges represent possible data flow (the execution path).
Now basically the data flow analysis gives the information regarding the definition and use of data in the program  (Available Expression, Reaching Definition, Live variable).  This information is needed for code optimization.
And moving on to the graph theory applications in the compiler design, I would say Register allocation is the best example (Btw this can be done after gathering information from the data flow analysis).
This is a vast area, not easy to explain everything clearly. So, I would highly recommend to read a good book on compilers to get deeper insights


Can nfa consume more than one letter at a time If I have a NFA/DFA and I expect inputs of 00, 01, 10, 11 can I read input in groups of 2 binary digits at a time.

like the example shown

Yes, as long as your alphabet is defined as a set of different couples of binary digits


Does a regular expression model the empty language if it contains symbols not in the alphabet? Suppose $\Sigma = \{ a,b \}$ and the regular expression $(a^*b+dc)^*(b^*d + ad)^*$. Is it equal to $\varnothing$?

So I have a regular expression like this: $(a^*b+dc)^*$. As only $(a,b) \in \Sigma$, I see that:

$dc=\varnothing$

So $(a^*b+dc)^*=(a^*b)^*$.

Then:

$(b^*d + ad)^* = (\varnothing + \varnothing)^*=(\varnothing)^*$ and as $(\varnothing)^*=\epsilon$, $(b^*d + ad)^*$ becomes $\epsilon$.

So my regular expression is simply $ (a^*b)^*$? Am I correct, or does the fact that the regular expression contain at least one symbol not in alphabet make it wrong immediately?

Regular expressions only use characters from the alphabet so, if you've fixed your alphabet to be $\{a,b\}$, then $(a^∗b+dc)^∗(b^∗d+ad)^∗$ isn't a regular expression. It doesn't describe any language, in just the same way that "seventy red" doesn't describe any number. In particular, it doesn't describe the empty language, in the same way that "seventy red" isn't equal to zero.

Now, if your alphabet includes all the symbols $a$, $b$, $c$ and $d$, you might want to ask what are the strings in $L((a^∗b+dc)^∗(b^∗d+ad)^∗)$ that contain only $a$'s and $b$'s. That is, what is $L((a^∗b+dc)^∗(b^∗d+ad)^∗)\cap \{a,b\}^*$? And the answer to that is that it's all strings matching $(a^*b)^*$, as you derive in the question.

Appendix. One could attempt to sidestep these issues by redefining regular expressions in a way that gives them well-defined semantics if they include symbols not in the alphabet. However, the standard definition does not do this.

Indeed, trying to do so would seem to open up a huge can of worms. For example, suppose your alphabet is $\{a,b\}$. We could agree that, since $c$ is not a symbol in the alphabet, the regular-expression-like-object $abc$ matches nothing. OK, but $+$ is also a symbol that's not in the alphabet. Maybe you're happy with $ab+$ matching nothing because it's syntactically invalid – note, $ab+$, not $ab^+$! But, now, what does $a+b$ match? Does it mean "$a$ or $b$" or "$a$ followed by some symbol that's not in the alphabet followed by $b$, which is impossible, so it matches nothing"?


What is the time complexity (upper bound) for this simple recursive function? So I have function that I have written to return the maximum value between index i and index x of a given array using recursion as follows:

FindMax( A, i, j )
    if (i == j):
        return A[i]
    else:
        k = (i + j) / 2
    return max( FindMax(A, i, k), FindMax(A, k+1, j) )

What is the correct way to go about calculating the big O asymptotic time complexity of this algorithm? I would appreciate if someone could document a general way to calculate the correct complexity even if it is a different recursive function. I have spent a lot of time watching videos and reading up on the web but sadly I come up with different complexities after each.

Let's say the time of FindMax is $T(n)$ where $n$ is the size of array A. Notice, that FindMax access only the part of array between $i$ and $j$.
Look at the pseudocode step by step. The first if is just comparison, so it's O(1). IF comparison is true, returning is O(1) (exit recursion step). The else step is doing again some arithmetic things which is O(1) and then calling three functions: max with time O(1), FindMax with time $T(n/2)$ and again FindMax. The time is the half, because again those function are "working" on the half of the original array. This gives the recursion $T(n) = O(1) + 2T(n/2)$. Using the master's theorem we get $T(n) = O(n)$ see here. Another proof without using the theorem mentioned above is by induction, pretty straightforward for this relation.


What is the meaning of idiosyncratic when refering to multiprocess abstractions? I am currently reading this paper on library operating systems, more specific on Graphene. I stumbled over the following sentence:

"Because multiprocess abstractions, such as signals or System V IPC, tend to be idiosyncratic, an essential problem is identifying a minimal, host-independent substrate upon which to implement OS-specific abstractions." (Page 3, design options paragraph)

But I don't understand what is meant by idiosyncratic multiprocess abstractions? What is the meaning of idiosyncratic in the context of multiprocess abstractions?

Let me rephrase your quote:

  Implementations of multiprocessing in various systems tend to be rather different. Each system uses its own peculiar "vocabulary". When we port each such system to new hardware, we need to code afresh the entire multiprocessing subsystem. One way to address this difficulty is to come up with a small set of multiprocessing primitives which, on the one hand, can be used to implement all the multiprocessing mechanisms in known systems, and on the other hand, is simple enough to code for each particular hardware. This will drastically reduce the effort required in porting operating systems.


Find a Minimal Set of Combined Tuples Suppose I have a set of n ordered tuples, all of the same, fixed dimension.  The tuples' values are integers, with #s indicating an integer I don't care about.  For example:

  { (1,2,5), (4,2,3), (1,2,#), (#,2,3) }

Tuples can be combined so long as they don't disagree about anything.  For example, (1,2,#) and (#,2,3) can be combined into (1,2,3).  Therefore, we can simplify the above set by combining the last two elements:

  { (1,2,5), (4,2,3), (1,2,3) }

The goal is to simplify the set as much as possible.  We can't simplify from here any more, but by simplifying in a different way, we could have done better by combining the 1st with the 3rd and the 2nd with the 4th (hence, this problem is not convex):

  { (1,2,5), (4,2,3) }

My question:

Is this a well-known problem by a different name?  (E.g., give a reduction from some NP-complete problem, perhaps?)  It's related to the set-cover problem, but somewhat different since elements can be combined and not everything need be chosen.
What algorithms can I use to solve this, even approximately?  Speed is important; I solved a similar, simpler problem in expected O(n); equivalent performance would be ideal.

Call tuples containing at least one # "free tuples" (vs. "complete tuples").  Observation: WLOG every tuple is free: combining a free tuple with a complete tuple or a complete tuple with a complete tuple is never suboptimal, so we can preprocess all such combinations first, then remove all complete tuples--since by construction, nothing can combine with them.

I am not aware of whether this problem has a name or not, but it can be shown that it is NP-complete by reduction from the maximum independent subset problem:

Given an undirected graph of $N$ vertices and $M$ edges, we can map the nodes to a set of $M$-tuples $\{x_1,...,x_n\}$ such that any two tuples are "compatible" if and only if the corresponding nodes do not share an edge:

Given $i$-th undirected edge $\{a,b\}$ with $ a\leq b$ we set $x_{a}[i]$ to 1 and $x_{b}[i]$ to 2.
Any element that remains unset by the previous rule is set to #.

Now:

For each pair of nodes that share an edge, the corresponding tuples will not be compatible because they have different values in the position corresponding to the edge.
For each pair of nodes that do not share an edge, for each position in the tuples at least one of them has # assigned in that position. Hence,they will be compatible.

By definition:

An independent subset of the graph is such that it does not contain two nodes that share an edge.
A compatible subset of tuples is such that it does not contain two tuples that are not compatible.

Hence a subset of nodes is independent if and only if the corresponding subset of tuples is compatible. Then, the size of the maximum independent set in the original graph is equal to the size of the maximum set of compatible tuples.


Time complexity of finding median in data stream I was reading a solution to the problem in the title on leetcode and the article says that the time complexity of the following solution is O(n)

setup a data structure to hold stream value and insert new element in the right place using linear search or binary search
return median

my solution is as follows:
class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.arr = []

    def addNum(self, num: int) -> None:
        idx = bisect.bisect_left(self.arr, num)
        self.arr.insert(idx, num)

    def findMedian(self) -> float:
        # self.arr.sort()
        if len(self.arr) % 2 != 0:
            return self.arr[len(self.arr)//2]
        else:
            return (self.arr[len(self.arr)//2 -1] + self.arr[len(self.arr)//2 ])/2

My question is about the time complexity of the push method. the binary search will take O(log n) to find the index. the insert will take O(n). but since the method will be called on the stream, will the complexity be O(n^2) or O(n) ?

From a brief look at Leetcode streaming problem solutions, the complexity solutions provided for streaming problems refer to the time complexity of a single iteration for the stream i.e. after $n$ elements in the stream, what is the complexity of updating the data structure and answering a query with a new element?


Is a sum of n terms considered O(1) or O(n)? Say I have $n$ numbers in an array and I have to compute the sum of those numbers. Is the complexity considered as $O(1)$ or $O(n)$?

Clarification

Say I have 10 constants, I could precompute the total and claim that overall, the complexity is $O(1)$. Yet, if I have 10 assigned variables, I would have to perform 10 additions to compute the total, which implies $O(n)$.

Another way to formulate my question is: Does $O()$ depends on the number of unknowns (i.e. variables) only? How are constants considered?

If you have ten elements, then that's a constant and considered $O(1)$.  However, if you're given an input to a function, and want to analyze the running time of your algorithm in terms of the input length, then that's $O(n)$, provided that you at least read the entire array (and $n$ is the array length).

It all has to do with what you measure your running time in.  In parameterized complexity, for instance, we typically measure the complexity in two parameters; the length of the input, and an additional parameter $\kappa$.  Hence, there you will often see running times like $O(n \cdot 2^\kappa)$.

In your problem, we say $O(n)$ because we sometimes consider "summing integers" as a constant operation.  That's obviously not possible if we allow arbitrarily large integers.  If the max (absolute) integer is $N$, then your algorithm might be $O(n \log N)$.


AVL tree with fixed height and as few elements as possible I have been reading about AVL trees, at the moment I'm trying to figure out how to determine the height of a tree and how to draw an AVL tree of some height with minimum number of elements.

In a tutorial I found that this: would be a AVL tree of height 7

And this AVL tree with the height 4

This is really confusing by the look I would guess that both of them are of height 4. I'm fairly new to data structures, I could not find a simple documentation/tutorial regarding this most of what i found was about Insertion/Deletion with AVL trees.

So is the top tree of height 7 if not how would I draw it with the minimal number of elements. I understand the each sub tree would have to be balanced.

Generally tree height is defined as the length of the longest path from the root to a leaf. Therefore you're right that the two trees have the same height, but they actually have height 3.

As far as your second question, about how to draw the smallest possible AVL tree of a given height $n$, the trick is to think inductively. Construct a new tree of height $n$ by joining the smallest possible AVL trees of height $n-1$ and height $n-2$ as subtrees of a new common root. Using the definition of AVL trees, it's a straightforward exercise to see that (1) this new tree is a valid AVL tree and (2) it's the smallest possible AVL tree of height $n$.

To get the height 7 tree in particular, find the base case minimal AVL trees of heights 0 and 1, and repeat the above construction 6 times.


Count the number of Euler PATHs in directed graph? I would like to find all Euler PATHs in a directed graph.
Counting (instead of finding) all the Euler PATHs is sufficient.
Circuits are not good for me, only Paths.

I am doing a problem, that I have derived to a point, where knowing the number of paths fast would help.
Currently, I have written (in c++) a recursive function that finds all of them, but it complexity grows quickly, so my algorithm gets slow fast. My algorithm is ~O(2^n). I would like a faster one for counting, if possible.

I have researched the topic, but I can only find proofs (for being NP complete, or polynomial) and algorithms for Euler Circuits in directed and undirected graphs. But again, I am looking for Euler Paths in directed graphs.

My graphs have only two nodes, but a lot of edges, that should be touched only once, like in an Euler Path.

So in summary:

Euler Path.
Directed Graph.
Only two nodes.
High edge count.
Edge costs are the same.

Here is an image to illustrate a possible set up.

You can actually come up with a formula for this. Let $\ell_0,\ell_1$ be the number of self-loops at $0,1$, and let $e_{01},e_{10}$ be the edges from $0$ to $1$ and in the other direction. We must have $|e_{01}-e_{10}| \leq 1$. If $e_{01} = e_{10}+1$ then the path must start at $0$; if $e_{10} = e_{01}+1$ then it must start at $1$; if $e_{01} = e_{10}$ then both are possible. We will count paths starting at $0$.

Given an Eulerian path starting at $0$, we can write it as
$$
L_0 E_1 L_1 E_2 \cdots E_m L_m,
$$
where $L_0,L_2,\ldots$ are collections of self-loops at $0$, $L_1,L_3,\ldots$ are collections of self-loops at $1$, $E_1,E_3,\ldots$ are $0\to 1$ edges, and $E_2,E_4,\ldots$ are $1\to 0$ edges. We can decompose this path into three components:
$$
E_1 E_2 \ldots E_m \\
L_0 L_2 \ldots \\
L_1 L_3 \ldots
$$
We can choose the first component in $e_{01}! e_{10}!$ ways, the second component in $\ell_0!$ ways, and the third component is $\ell_1!$ ways. It remains to choose a way of partitioning the latter two strings into their components. In order to count this, assume that $m$ is even (the case $m$ odd is very similar) and divide the original path differently:
$$
L_0 E_1 L_2 E_3 L_4 \ldots E_{m-1} L_m \\
L_1 E_2 L_3 E_4 L_5 \ldots E_{m-2} L_{m-1} E_m
$$
The first line contains $m/2$ "breakpoints" out of $\ell_0 + m/2$ symbols in total, so the number of ways of breaking $L_0L_2\ldots L_m$ into its $m/2+1$ parts is $\binom{\ell_0+m/2}{m/2}$. The computation is similar for the second line, once we remove the $E_m$ which must appear at the end; we get $\binom{\ell_1+m/2-1}{m/2-1}$.

I'll leave you the task of bringing everything together to one formula.


Finding a closed form for a discrete sum using generating functions Consider this sum: for context sake, the summand appears in the counting of the possible ways to have one cigarette box empty and the other having left N cigarettes when both boxes start with N cigarettes in the Banach cigarette problem ; so there is a combinatorial explanation which I do not consider here.

$$ \sum_{i=0}^{N} \binom{2N-i}{N} 2^i = 2^{2N} $$

I wish to know how one would go about finding this closed form using generating functions. More precisely, how would you evaluate

$$ \sum_{N \geq i} \binom{2N-i}{N} x^N $$

Thanks!

The term $t_N = {2 N - i \choose N} x^N$ of the sum is hypergoemtric ($t_{N+1}/t_N$ is a rational function of $N$) which means that the closed form of the sum can be found using Gosper's algorithm, if it exists and is hypergeometric.

When I run the algorithm with Mathematica it says
$$x^i \cdot {}_2F_1(\frac{i+1}{2}, \frac{i+2}{2}; i+1; 4 x)$$
where ${}_2F_1$ is the hypergeometric function. This means that a closed form of the kind you are expecting does not exist.

Supplemental:

Gosper's algorithm computes
$$\sum _{i=0}^n \binom{2 n-i}{n} 2^i = 4^n$$
and then
$$\sum _{n=0}^{\infty } x^n \sum _{i=0}^n \binom{2 n-i}{n} 2^i = \frac{1}{1 - 4 x}.$$


proving the error bound for a hypothesis Given a hypothesis $h:X\rightarrow Y$ ($h$ is returned by an Empirical Risk Minimization (ERM) strategy with realizable case i.e. $h$ is consistent with the sample examples) over $X=[0,1]\subseteq R$ where $Y=\{0,1\}$ and $D$ is the uniform distribution over $X$. How can I prove that for the accuracy parameter $0\leq\epsilon\leq 1$ we might get $err_D(h)>\epsilon$? where $err_D(h)$ is the true error of $h$ in the distribution $D$.

This is a homework and all I can do is using probabilities (as its shown in the course slides and other sources) to give some bounds on the error (i.e. $P(err_D(h)> \epsilon)\leq k(1-\epsilon)^m$) where $k$ is the number of bad hypotheses $|H_B|$ s.t. ($\bar{h}\in H_B | err_D(\bar{h})>\epsilon)$ and $m$ is the sample size.

MY question is: is there any other way (beside using probabilities) to prove this? It just seems odd to me when the question asks for a prove and the answer is about probability bound. I am new to the field of learning theory and this might seems like a silly question but I am really trying to understand the intuition behind using probabilities.

Consider a case where the actual label is $1$ for all $x\in [0,1]$.
Suppose $H$ consists of two classifiers: one that realizes this (i.e. $\forall x\in [0,1], h(x)=1$), and one that is almost entirely wrong: $g(x)=0$ except for some finite set of numbers $S$.

If the sample is exactly $S$, then both classifiers have the same error on the sample set (0), so you may choose $g$. However, you'll get that $err_D(g)=1>\epsilon$.

As mentioned in the comments, this doesn't really prove anything useful, since the probability that the sample will be exactly $S$ is $0$.


Given two formulae E[G F p] (which is CTL*) and EG EF p ( which is a CTL) with a Model prove that they are not equivalent I am trying to prove they are not equivalent , a model which satisfies the fist one but not the second since I think EG EF p is stronger than E[GF p],any leads would be helpful. Thanks.

Consider a system with 3 states, $s_1,s_2,s_3$ and the following transitions:
$s_1\to s_1$, $s_1\to s_2$, $s_2\to s_3$ and $s_3\to s_3$.

The state $s_2$ is labelled $p$.

Clearly $E[GF p]$ doesn't hold, since every path from $s_1$ has at most one $p$.

However, there exists a path, namely $s_1^\omega$, such that in every state along this path, i.e. in $s_1$, there exists a path that eventually sees $p$, so $E G EF p$ does hold.


Support of a codeword in a binary linear code proof Let $C$ be the binary linear code with the following generator matrix

$G= \begin{bmatrix}
    1 & 1 & 0 & 1 & 0 & 0 & 0 \\
    0 & 1 & 1 & 0 & 1 & 0 & 0  \\
    0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1
\end{bmatrix}$

The support of a codeword is the set of coordinate positions in which the code word has nonzero entries. Let $w$ $\in C$ be a code word of weight $4$. Show that there is no code word of weight $3$ in $C$ whose support is a subset of the support of $w$.

I think I have worked out that the codewords of weight $4$ in $C$ are: $\{(1001011),(0010111),(0111001),(0101110),(1100101),(1110010),(1011100)\}$ so does this mean that the support is $\{(1,4,6,7),(3,5,6,7),(2,3,4,7)$ and so on..$\}$?
Then the codewords of weight $3$ are $\{(1101000),(0110100),(0011010),(0001101),(1000110),(1010001),(010001)\}$ ? with support of  $\{(1,2,4),(2,3,5),(3,4,5)$ and so on..$\}$?

I'm not sure if this is right so far? But this is as far as I can get and do not know what to do next to show that there is no code word of weight $3$ in $C$ whose support is a subset of the support of $w$.

If a codeword of weight 3 existed whose support was a subset of a codeword of weight 4, then you must have a codeword of weight 1 (since the difference of codewords is also a code word).

A codeword of weight 1 has one 1 and the rest zeros. Now, can you show that these don't exist?


Optimal upper bound on the number of states in the complement of an NFA I have my own version of lex and I would like to add the complement operation. Derived from that I can then add the intersection and difference also. My version also supports the generation of NFAs (Non-deterministic Finite Automaton) and of course I try to keep the automatons as small as possible.

My question thus is: what is the most optimal known upper bound on the number of states in the NFA that accepts the complement of another NFA? Of course going through the conversion to a DFA (Deterministic Finite Automaton) and then interchanging accepting and rejecting states, gives an exponential upper bound. Are there any better known upper bounds? Preferably polynomial or even linear of course.

If no better upper bound is known, has it been shown that for some family of languages the lower bound is exponential or otherwise super polynomial?

In the paper State Complexity of Concatenation and
Complementation of Regular Languages by Jirásek, Jirásková, and Szabari (LNCS Volume 3317, 2005, doi 10.1007/978-3-540-30500-2_17) very precise bounds for complexities for complement on non-deterministic automata are obtained. We do not need full details, but the authors cite an earlier report by one of them, stating:

Theorem 2. For any positive integer $n$, there exists a binary NFA $M$ of
$n$ states such that any NFA for the complement of the language $L(M)$ needs at
least $2^n$ states.

So it seems there is no better bound for complementation than via deterministic automata. At least in general.


Show that this algorithm does not work for determining convex polygons Context

Consider this algorithm. If the set $\{\angle p_ip_{i+1}p_{i+2} : i=0,...,n-1\}$  does not contain left and right turns, output "yes the polygon is convex"; otherwise, "no".

My answer

Consider this nonsimple polygon having 4 vertices; the algorithm above will output "yes" as the set of points does not contain both left and right turns, yet the polygon is not convex. Is this a good counterexample rendering the above algorithm incorrect?

Thanks in advance.

A simple counterexample is a pentagram (http://en.wikipedia.org/wiki/Pentagram). It contains right turns (if you go in clockwise direction) only, but it is not convex. The above algorithm will incorrectly say pentagram is a convex polygon. It's actually a complex polygon.

In other words, algorithm might fail if the input polygon is complex.


Fastest nth root algorithm to a lot of digits? What is that fastest algorithm that can calculate a lot of digits of a decimal root? For example: 10,000 digits of the 3.56th root of 60.1?

An iterative method may be as follows:

$x_2=\frac{x_1(n-1)+\frac{x}{x_1^{n-1}}}{n}$

where $n$ is the root desired, $x_1$ is a guess of the root of $x$  and $x_2$ is a better guess.

The iterative method is given in the book The Art of Programming Embedded Systems by Jack G. Ganssle.


Is there a way to efficiently parse this grammar? Consider the following context-free grammar:

  $T \to (*) \mid (T*) \mid (*T) \mid (T*T)$

This effectively forms a notation for binary trees: A binary tree is a $*$, with optional children on either side, all surrounded by $()$. This is clearly unambiguous, because you can distinguish between the presence and absence of a tree, and you can determine where a tree begins and ends.

Now consider the same grammar, except that it does not distinguish between opening and closing parenthesis:

  $T \to aba \mid aTba \mid abTa \mid aTbTa$

Here, we have replaced both $($ and $)$ with $a$ (and $*$ with $b$).

After trying several examples, I believe that this grammar is unambiguous. For example, the string $aaabababaabaababaa$ parses as $(a(a(aba)b(aba)a)b(a(aba)ba)a)$.

However, I don't see an efficient way to parse it. The general idea I had was to go as follows:

The string must start and end with $a$.
If the second character from the start is $b$, recursively parse the part after it, all the way to the second character from the end.
If the second character from the end is $b$, recursively parse the part before it, all the way to the second character from the start.
If the second character from both the start and end is $b$, we have a malformed expression.
If both characters from the start and end are $a$, then... what?

Here it seems that we would have to create a choice point and use a backtracking method to find it. However, this method would have exponential runtime for many pathological inputs, such as $aababababababababababaa$.

Is this grammar unambiguous? If so, is there a way to parse this grammar that avoids pathological exponential runtime for most inputs?

The grammar is ambiguous: (I used | for a and * for b because I find it easier to read.)

||*|*||*|*||
((*(*))*(*))
((*)*((*)*))

However, you can use an Earley grammar to find all possible parses in worst-case cubic time. (As long as you are satisfied with a graph representation of "all possible parses" since the maximum number of parses of a string of a given size is exponential.)

I found this example by using a bison GLR grammar and iterating over inputs until I found one which produced an ambiguity. Out of laziness, I produced the list of inputs by generating all strings consisting of $n$ | and $n$ *| where the first element is |. Most of these inputs are syntax errors, but for small $n$ it doesn't matter.

Here's a simpler approach, using Python to generate valid inputs:

def gen(s, n):
  """Generate left-most derivations of 's' with maximum length 'n'"""
  if n > 0:
    i = s.find('T')
    if i == -1:
      yield s
    else:
      yield from gen(s[:i]+'|*|'+s[i+1:], n)
      yield from gen(s[:i]+'|T*|'+s[i+1:], n-1)
      yield from gen(s[:i]+'|*T|'+s[i+1:], n-1)
      yield from gen(s[:i]+'|T*T|'+s[i+1:], n-2)

If this function generates the same string twice, that string is ambiguous since it has two left-most derivations.


Comprehensive reference for automata I'm looking for a general reference cataloguing types of automata. Any introductory textbook will cover DFAs, NFAs, PDAs, and TMs, but there are countless more automata of practical or theoretical interest — linear bounded, embedded pushdown, nested stack, tagged finite, and so on. Online resources for these tend to be scattered.

Is there any sort of comprehensive reference, whether online or in print? Even incomplete surveys would be helpful.

There is no list out on the web, nor even a partial list. I spent a few days looking and found nothing. The best you can do is piece together a list on your own (and post it here! :D).


What are the reasons for and against using normalized floating point? Floating point number formats can be normalized or not, meaning that ‘normal’ floating point numbers have an implicit (hidden) leading bit 1 in the significand. For example, the binary IEEE 754 formats are normalized, but the decimal IEEE 754 formats are not, i.e., they have an explicit leading bit (or number).

The advantage I see is the larger range or precision possible. (Larger range if compared to a format with one less exponent bit; greater precision if compared to a format with one less significand bit.)

However, the downsides I see are:

Dealing with a more complex format during computations, e.g., normalization steps, the existence of subnormals.
The loss of significance information. With, e.g., decimal IEEE 754 formats, the number of significand digits can be expressed. This would be a very useful feature, e.g., when encoding measurements. I would think that such information could also be exploited during computations.

On the whole, I feel that the larger range or greater precision that can be got with one extra bit does not justify the loss of a qualitative aspect, significance information. So my question is:

What are (other) reasons for or against using a normalized floating point format?

Perhaps the reason is historical and now the choice would be different; also this information is of interest to me. Perhaps the arguments I gave are not valid; it would then be interesting to know why.

Binary IEEE format include both normal and denormal ('subnormal') numbers. The purpose of subnormals is to avoid a gap between the smallest normal numbers and zero larger than the smallest difference between consecutive normal numbers.

This gap make generate instability in some calculations dealing with small numbers,...
Denormal have a performance and/or complexity cost in software and hardware. Sometimes denormals are not handled or a fast mode is provided where all denormals are considered as zero.

(Here is an historical perspective from William Kahan, one of the original creators of the P754 format: https://people.eecs.berkeley.edu/~wkahan/ieee754status/754story.html)


number of ways evaluation of expression such that value not changed one example:

How many ways we can do possible value-preserving parenthesis the following expression in such a way that value not changed after parenthesis with one constraint that parenthesis among one variable is not correct (i.e: $(i)+j+k$ is not acceptable) ?

as an example for expression $i+j+k$, parenthesis like $i+(j+k)$, $((i+j)+k)$ are correct parenthesis but $(i)+j+k$ is not. I take a complete short example as follows.

What's wrong with (i) + j + k ?

I live in a world where floating-point arithmetic has rounding errors, and where integer arithmetic has overflow checks, so (i + j) + k and i + (j + k) are most definitely not the same, for example if i is a large positive integer, and j, k are two large negative integers then the second one can produce an overflow (crash) while the first one doesn't.


Why there's a single accepting state in G-NFA's? It's clear that we can only have a single start state in G-NFA's but I would like to know why we can't have more than one accepting state in G-NFA's.I think it's better to have more accepting states so that we could avoid epsilon transitions.

Is this only a rule that  might make conversion of NFA to Regular expressions simpler or is there any specific reason.If this rule makes the conversion simpler could anyone tell the reason behind it.

A GNFA (generalized NFA) can have any number of accepting states, just like an ordinary DFA/NFA.

But, as you suspect, the conversion of NFAs to regular expressions is easier if there's only one accepting state.  At each step of the conversion algorithm, you remove one state that isn't the start state and isn't the accepting state, and you modify the regular expressions that label the edges of the remaining transitions. The point is that, eventually, you end up with an automaton that has a start state, an accepting state, a single transition between the two and nothing else. The transition is labelled with a regular expression $R$ and the only possible transition from the start state is to reach the accepting state by reading some input that matches $R$.  Therefore, $R$ matches exactly the language of the machine.

If you had multiple accepting states, you'd end up with an automaton that had one start state and multiple accepting states.  In particular, there could be transitions between different accepting states.  That means there's no unique way of reaching an accepting state so it's not at all obvious how to produce a single regular expression that corresponds to the automaton.  You'd probably need to use a modified version of the standard algorithm to "crunch" those accepting states down to a single one. But that seems much more complicated than just having a single accepting state and dealing with a few harmless epsilon-transitions.


Ordering of conditions in multi-way conditional constructs Most programming languages provide multi-way conditional constructs (like cond in Lisp, guards in Haskell, etc) that allow one to define program behavior according to different conditions.  But most of them also implies a default top-down ordering: the next condition is checked only when all preceding conditions are unsatisfied.  I wonder if there is any work on conditional constructs that does not follow this convention but rather automatically sort the conditions according to some order.  I can foresee how hard it is to get conditions independent.  Maybe it is not feasible anyway?

On what basis you want to sort out conditions conditions are not specific. If they are specific then you may sort out the conditions to not follow top down approach.

And conditions are the only thing that decide which condition next to be tested.
That is they handle the flow of your code and one condition is dependent on other.