Using a counting semaphore as a binary semaphore Are there any methods, so that I can use a counting semaphore as a binary semaphore?

A binary semaphore should have two possible states: 0 and 1.  The operation wait() should atomically look at the state, if the state is > 0, the state should be decremented and the process should continue.  If the state is 0, the process should be atomically placed on a queue of waiters and the process should block.  The operation signal() should atomically look at the state, if the state is 0, and there are processes blocked, exactly one of them should be woken.  If there are no blocked processes the value of the semaphore should be set to 1.

I specifically need a binary semaphore, not a mutex. A mutex assumes ownership: that a processes will first lock and then after a resource is used, the process will unlock the mutex. But in my case there are some processes that will only do semaphore signal() operation, without ever performing a wait() operation.

How can I make sure that the value of the counting semaphore never goes above 1?

I asked a similar question, on Stack Overflow, specifically about solving this problem with the POSIX synchronization APIs, but the suggestion I got there was to use file locking, which is much slower than semaphores, and also seems to have the mutex semantics I can't use.

A binary semaphore is just a semaphore whose values are limited to 0 and 1 (locked and unlocked; when locked there can be an unlimited queue of tasks waiting). When using such a semaphore you have to be careful never to increment it past 1. The point is that if the values are thus limited, some tricks are possible that speed up the implementation quite a bit, and this is also the most common use (think using the semaphore as a mutex). There is no real conceptual difference involved.

If you want a detailed discussion of the use of semaphores and other synchronization primitives (with some implementation discussion) see Downey's "Little Book of Semaphores". The Linux kernel used to have highly optimized semaphore implementations for contemplation, but they were removed a while back.


Is there an algorithm for a number line from $0$ to $n$ Where $n + 1 = 0$
and $0 - 1 = n$?

The $n + 1 = 0$ case can be achieved by using the modulus operator, but I can't figure out how to treat the $0 - 1 = n$ case.

For $a,b \in \{0,\ldots,n\}$, subtraction is given by
$$
a - b = [a + (n+1-b)] \bmod{(n+1)}.
$$


Bounds on graph partitioning I am trying to find some generic upper bounds on the "standard" graph partitioning problem.  Say I have a graph with $|V|$ vertices and $|E|$ edges  I want to partition it into two equal $N/2$ (or approximately equal if easier) parts while minimizing the cut i.e.  $\min(|C|)$ where $C$ is the set of edges with nodes on either side of the partition (similarly nodes that the cut goes through).
So far this is standard stuff and clearly the optimal solution depends on the details of the graph. However, what I want is an upper bound on $\min(|C|)$ in terms of $|V|$ and $|E|$ without knowing anything else about the graph. If no upper bound then even some type of average case estimate would help.
Also, the same thing for a multigraph.

This is an area in which I'm not very familiar, but what you are looking for are so-called expander graphs.
A graph $G$ has edge expansion $$h(G) = \min_{0 \leq |S| \leq \frac n 2} \frac{|\partial S|}{|S|},$$
where $\partial S$ is the boundary of $S$, i.e., the edges with exactly one endpoint in $S$.
This isn't exactly what you ask for, but you can also consider only $S$ of size exactly $\frac n 2$.  There are $d$-regular expander graph classes.  Perhaps that will point you towards something.


Program Correctness, The specification From Wikipedia: In theoretical computer science, correctness of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification.

But the problem is that to get the "appropriate" specification is not a trivial task, and there is no 100% correct method (as far as i know) to get the right one, it just an estimation, so if we are going to take a predicate as a specification just because it "looks" like the "one", why not taking the program as correct just because it "looks" correct?

First off, you're absolutely right: you're on to a real concern.  Formal verification transfers the problem of confidence in program correctness to the problem of confidence in specification correctness, so it is not a silver bullet.

There are several reasons why this process can still be useful, though.

Specifications are often simpler than the code itself.  For instance, consider the problem of sorting an array of integers.  There are fairly sophisticated sorting algorithms that do clever things to improve performance.  But the specification is fairly simple to state: the output must be in increasing order, and must be a permutation of the input.  Thus, it is arguably easier to gain confidence in the correctness of the specification than in the correctness of the code itself.
There is no single point of failure.  Suppose you have one person write down a specification, and another person write the source code, and then formally verify that the code meets the spec.  Then any undetected flaw would have to be present in both the spec and the code.  In some cases, for some types of flaws, this feels less likely: it's less likely that you'd overlook the flaw when inspecting the spec and overlook the flaw when inspecting the source code.  Not all, but some.
Partial specs can be vastly simpler than the code.  For instance, consider the requirement that the program is free of buffer overrun vulnerabilities.  Or, the requirement that there are no array index out-of-bounds errors.  This is a simple spec that is fairly obviously a good and useful thing to be able to prove.  Now you can try to use formal methods to prove that the entire program meets this spec.  That might be a fairly involved task, but if you are successful, you gain increased confidence in the program.
Specs might change less frequently than code.  Without formal methods, each time we update the source code, we have to manually check that the update won't introduce any bugs or flaws.  Formal methods can potentially reduce this burden: suppose the spec doesn't change, so that software updates involve only changes to the code and not changes to the spec.  Then for each update, you are relieved of the burden to check whether the spec is still correct (it hasn't changed, so there's no risk new bugs have been introduced in the spec) and of the burden to check whether the code is still correct (the program verifier checks that for you).  You still need to check that the original spec is correct, but then you don't need to keep checking it each time a developer commits a new patch/update/change.  This can potentially reduce the burden of checking correctness as code is maintained and evolves.

Finally, remember that specs typically are declarative and can't necessarily be executed nor compiled directly to code.  For instance, consider sorting again: the spec says that the output is increasing and is a permutation of the input, but there is no obvious way to "execute" this spec directly and no obvious way for a compiler to automatically compile it to code.  So just taking the spec as correct and executing it often isn't an option.

Nonetheless, the bottom line remains the same: formal methods are not a panacea.  They simply transfer the (very hard) problem of confidence in code correctness to the (merely hard) problem of confidence in spec correctness.  Bugs in the spec are a real risk, they are common, and they can't be overlooked.  Indeed, the formal methods community sometimes separates the problem into two pieces: verification is about ensuring the code meets the spec; validation is about ensuring the spec is correct (meets our needs).

You might also enjoy Formal program verification in practice and Why aren't we researching more towards compile time guarantees? for more perspectives with some bearing on this.


Understanding about creating a DFA This is a school assignment, I am fairly new to DFA's.

L = {ww|w∈{0,1}*

I feel like I need to put this in words to understand how it works.

Translating L:

  W can be a string of an infinite combination of 1s and 0s.
  WW is just a string that repeats itself.

For example W="101011",  WW = "101011101011".

Im not a 100% on this. Not really sure how to create a DFA out of
this.

Am I correct with my "translation"? If you can help me further into
making a DFA much appreciated.

You cannot make a DFA for this language because its not a Regular language
in fact its not even a context free language so you can't even make a PDA for it

to prove its not regular and not  context free you should use pumping lemma

but you can make a linear bounded automata for this language so therefore its a context sensitive language

hint for the linear bounded automata: put both of the w's in the tape and separate  them with 0, then compare them.

also here's some examples for some of the strings in the language :

00 , 11 , 0101 , 1010 , 110110 ...


How to delete a node from BST tree with 2 chidren? I googled, read several tutorials and watched several BST node deletion algorithm explanations before posting this question. For some reason, I cannot find a complete explanation of BST node deletion algorithms.

I've found 4 algorithms to remove the node with 2 children from Binary Search Tree:
1) Find the smallest node from right sub tree and replace it with the node which we want to delete.
2) Find the biggest node from left sub tree and replace it with the node which we want to delete.
3) Find the deepest leftmost node from the right sub tree and replace it with the node which we want to delete.
4) Find the deepest rightmost node from the left sub tree and replace it with the node which we want to delete.

Apparently, none of those algorithms works for the next use case (most likely because I am missing or don't understand something). The use case is to remove element 5 from the next tree:

For the first algorithm we would chose element 6 and would lose its right sub tree. For the second algorithm we would chose element 4 and would lose its left sub tree. For the 3rd algorithm we would chose element 7 and which would violate BST rules. For the 4th algorithm we would chose element 3 which would also violate BST rules.

What is the right algorithm for such a use case?

You are right, in BST usually the case where a node has two children is reduced to the case where a node has one child.

Consider a node with two children. Swap this node with its predecessor in the BST (that is the rightmost node in the left subtree), or --totally symmetric-- swap with the successor (the leftmost node in the right subtree).

The node to be removed now has at most one child (in case we went for the predecessor it cannot have a right child).
If it has no children we delete the node, and we are done.

In case the node has a single child, we remove the node and replace it by its subtree. We again obtain a BST.

In your example we want to remove 5 and swap it with its predecessor 4. Now 4 is in the root, and 5 has left child 3. Finally we remove 5 and put its child 3 on its place. Now 3 is the right child of 2.

PS. This method is sometimes called "deletion by copying", because values are copied from one node to another. Some do not approve of this process for two reasons. First copying might be an expensive operation, and second references are lost (if another datastructure points to a node with a certain value). Instead one only changes the pointers.


Algorithm to find longest path in a tree that is smaller than x Suppose we have a weighted binary tree $G$ where the nodes are towns and edges are streets with edge weights being the travel time and we want to find out whether it is possible to travel from any town to any other town within some time $x$.

There are three paths to consider for each node $v$.

Path to the right subtree of $v$
Path to the left subtree of $v$
Path that goes from the left to the right subtree including $v$

My approach to solving this problem is to use dynamic programming and start at leaf nodes to calculate a travel time $T_l$ for every leaf $l$ and set $T_l = 0$. Then work my way up the tree and compute $T_v = max(T_c + w(v,c))$ for every other node where $c$ are the child nodes of $v$ and check if that value is smaller than the given $x$. This would cover the first two cases and would require us to iterate over every node and edge once which is in $O(V+E)$

Where Im not sure is how to cover the third case, i.e. if I wanted to compute the travel time from one leaf node to another. Is that still possible in linear time and how would I do that?

Your dynamic program is a step in the right direction.
My idea would be to maintain two values for a node v:

$L_v$: The longest path starting from v going downwards (these corresponds to your dynamic program and the first two cases)
$U_v$: and the longest path in the subtree of v (i.e., case 3).

You already gave the formula for $L_v$.
For $U_v$ you take the maximum of $U_l$, $U_r$ and $L_l + w(lv) + w(rv) + L_r$ where $l$ and $r$ are the left and right children of v resp.
The last equation corresponds to the path which is formed by the longest paths to the left and to the right which are then joined.


What is the complexity of comparing point sequences? Given two sorted arrays of floating point numbers $X$ and $Y$, we can define the  S-distance as follows. The S-distance is defined as the minimum cost associated with the transformation of one point pattern $X$ into a pattern $Y$ by deleting, adding, and moving points (that is adding a constant to all points).  The cost of a transformation is:

$$p_d|X_{delete}| + p_a|X_{add}| + p_m d$$

where $p_a$, $p_d$ and $p_m$ are parameters and $X_{delete}$ and $X_{add}$ are subsets of $X$ that are deleted and added.  $|X_{delete}|$, for example,  is the number of elements in $|X_{delete}|$ and not the sum of the values. $d$ is the value that we are adding to all the points in the sequence $X$.

For example, say $X = (1,2,3)$ and $Y = (2,4)$ then one possible transformation of $X$ into $Y$ has cost $p_d + p_m$ as we can delete $2$ from $X$ and then increase both the points in $X$ by $1$ to make $(2,4)$ (so $d = 1$).

By adding a point I mean inserting a new point into the array.

I am trying to work out what the complexity of computing this distance
is. It is not obvious to me how to do this by dynamic programming for
example.

@Gassa gives a solution using $O(n^2)$ hash function calls. Is there a simple dynamic programming (or other) solution that doesn't require any hash function calls at all?

Here's a start: an upper bound is $O(n^3)$.

Note that we need either $0$ or $1$ moves: any two moves could be expressed as one.
Furthermore, this one move is commutative with all other operations: it may occur at any point in time, the end result will still be the same.

Barring some degenerate cases, consider one point $X_i$ which does not get deleted and moves into $Y_j$.
There are a total of $n^2$ such possibilities.
For each fixed $i$ and $j$, first, we know whether we need a move, and second, for all other points, we can establish which $X_u$ move into which $Y_v$ in $O(n)$.
For example, put all $Y_v$ in a hash table in $O(n)$, iterate over all $X_u$ and search for them in the hash table in $O(n)$ total.

Here's a speedup to $O(n^2)$.

Consider all possible $n^2$ move distances: each "$X_i$ to $Y_j$" produces a distance.
Some of the distances may turn out to be the same.
In your example of $X = (1, 2, 3)$ and $Y = (2, 4)$, the $X_1 \to Y_1$ and $X_3 \to Y_2$ produce the same distance of $2$.
So, in the end, each distance will have several pairs associated with it.

Now, we will need all $X_i$ to be different, and all $Y_j$ to be different.
Then, if a distance $d$ has $r$ pairs associated with it, all $X_i$ in these pairs are pairwise different, and all $Y_j$ in these pairs are also pairwise different.
It means that, when we move points by distance $d$, we will have $r$ matching points, and all other points will be non-matching, so will have to be deleted from $\{X\}$ or inserted into $\{Y\}$, respectively.

So, implementation-wise, maintain a hash map which maps a distance to the number of times we encountered such distance.
Iterate over all pairs of "$X_i$ to $Y_j$" and fill the map, in $O(n^2)$ total.
Now iterate the map and find the minimum cost, also in $O(n^2)$ total.
For a distance $d$, when the number of pairs with such distance is $r (d)$, the cost is the sum of the following:

$p_m$ if $d$ is nonzero, or $0$ if $d$ is zero;
$p_d \cdot (l_X - r (d))$, where $l_X$ is the length of $\{X\}$;
$p_a \cdot (l_Y - r (d))$, where $l_Y$ is the length of $\{Y\}$.

It may be possible to handle the case when the sequences can contain equal elements, but the details look cumbersome.

All this assumes $O(1)$ performance of hash sets and hash maps.
If that is a problem, at the very least, we can add logarithms and use tree sets and tree maps, respectively.

Also, the solution does not address precision loss for floating point operations.
For example, the implementation may use integers, by multiplying the given floating point values values by a constant.


Deadlock avoidance: How does the system know in advance about the number of resources required by a process? While studying about Deadlock Avoidance I came across a paragraph which states as given below:

  When the system needs to issue any resource to any process, then in making this decision the system must consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process.

So my question is that how can the system know in advance about the number of resources that a particular process will require/request in future?

For many systems, it's impossible to know (for instance, your home computer). In a very controlled system, you could know in advance about the number of resources that a process requires and when these requests occur (for example, an embedded system).

You could probably create some sort of heuristic for what resources might be requested in the future based on previous knowledge (such as past program execution or code analysis) for the impossible cases. I'm not sure how much this is done in practice though.


Algorithm for packing various shapes inside of a rectangle Say I am given a rectangle of width $W$ and length $L$. I now have to fit as many regular shapes of area $A$ into this rectangle as possible. For example, if the shape is a circle, I need to fit as many circles of area $A$ into the rectangle as possible. All the shapes trying to be packed in a given instance are identical, we also assume we are living in 2D.

What would be the general way to approach this problem? Can it be done with a program or is this a mathematical question?

As pointed out by the other answer, this is an example of bin packing, a type of problem that is NP-complete.

Skiena Section 17.9 reports:

  Fortunately, relatively simple heuristics tend to work well on most
  bin-packing problems.

The same source provides the following heuristic recommendation:

  Analytical and empirical results suggest that first-fit decreasing is
  the best heuristic. Sort the objects in decreasing order of size, so
  that the biggest object is first and the smallest last. Insert each
  object one by one into the first bin that has room for it. If no bin
  has room, we must start another bin. In the case of one-dimensional
  bin packing, this can never require more than $22\%$ more bins than
  necessary and usually does much better. First-fit decreasing has an
  intuitive appeal to it, for we pack the bulky objects first and hope
  that little objects can fill up the cracks.

  First-fit decreasing is easily implemented in $O(n \ \text{lg} n + bn)$
  time, where $b \leq min(n,m)$ is the number of bins actually used.
  Simply do a linear sweep through the bins on each insertion. A faster
  $O(n \ \text{lg} n)$ implementation is possible by using a binary tree
  to keep track of the space remaining in each bin. We can fiddle with
  the insertion order in such a scheme to deal with problem-specific
  constraints.

I recommend reading the original material in its entirety.


Data-flow analysis problem adjust to Ullman-Aho's framework? I am reading the classical book "Compilers. Principles, techniques and tools" by Aho et alii. On chapter 9.3 they talk about a general framework to solve data-flow analysis problems that use a framework which is monotone and of finite height.

The technique is shown to be useful for live variable and reaching definition analysis and I'm wondering if it is applicable to the following problems:

Checking if variables are always initialized.
Do range computations (the idea is to apply it on out of bounds array accesses check).
Eliminate common subexpressions.

My question is if this same framework can be used for this problem or I need more general frameworks such as the constant propagation framework described in chapter 9.4.

If the answer is yes what are the values of the framework defined as $(D,F,V,\land)$, where D is the direction of the analysis, F the family of transfer functions, V is the semilattice domain and $\land$ the semilattice operator? If the answer is no for some of the problems I don't really need this parameters for the more general framework but the reason why it doesn't work would suffice so that I can find a more general framework.

I ask this just in case somebody already know the answer and I can save me some time so don't worry about being too specific.

Checking initialization: Yes, you can use this framework.  You need only a single boolean for each variable.  The lattice is $V\to \{\bot,\top\}$, i.e., $2^V$, where $V$ is the set of variables. The height of this lattice is $n+1$ where $n=|V|$ is the number of variables.  The transfer functions are monotonic.  Consequently, you can use the framework.

Range computation:  No.  The lattice of ranges has infinite height.  Consider, e.g., the sequence of ranges $[0,0]$, $[0,1]$, $[0,2]$, $[0,3]$, and so on: it never ends.  Consequently, you need something more, such as widening operators.

Common subexpressions: I don't know of any nice way to express this in that framework (though there could always be something I'm not aware of).


Algorithm for recovering paired lists when elements are broken I am trying to solve an algorithmic problem.  I came from http://math.stackexchange.com upon an advise that this forum would be a better place to ask this.

I would like to hear your advice on where to search for hints.  If my problem has got a name, I would like to know what it is called in the field, and what I should learn to solve it.  Any partial suggestion would be welcome.  Also if there is another forum that fits my question better than here, I would be happy to hear that too.

A description of my problem is as follows.  Suppose you have a number of pairs of objects.  Let $X$ be the first list of objects and $Y$ be the second list. Assume $X = Y$ in a sense they share the same list of objects.

Now, objects in both lists are "broken" into pieces; Each element $x \in X$ is decomposed to $x_1, x_2,...$.  The same happens for $Y$.  As a result, what you have is two sets $X', Y'$, which contain the broken pieces of the original objects.
The task is to recover the original objects in $X$ and $Y$ from $X'$ and $Y'$.

Here is an example where objects are strings.
Suppose $X = Y = [apple, banana]$, and the strings are decomposed as:
$X' = [ban, le, ana, app]$ and $Y' = [na, ple, ap, na, ba]$.  I would like to recover $banana$ and $apple$ from information $X'$ and $Y'$.

Does this problem have a name?  Or, what do you think the good things to learn for me to study this type of problem?

Look at the literature on algorithms for the shotgun sequencing and shortest common supersequence problems.  It appears that your problem might not be exactly identical to them, but researchers have developed sophisticated algorithmic techniques for handling this kind of problem.  Therefore, I suspect you might be able to use the same techniques for your problem, or adapt them to work well for your situation.


Why is EXPTIME in EXPSPACE? What is the intuition behind EXPTIME being inside EXPSPACE?

When space complexity is usually smaller than time complexity or in the worse case, they are equal

As Yuval Filmus states in the comments, any TM (with one tape and one read-write head) whose time complexity is bounded by a function $t$ also has its space complexity bounded by $t$ since, in $t$ steps, the TM can only scan as most as $t$ many tape positions. In terms of complexity classes:
$$\textsf{TIME}(t) \subseteq \textsf{SPACE}(t)$$
$\textsf{P} \subseteq \textsf{PSPACE}$ and $\textsf{EXPTIME} \subseteq \textsf{EXPSPACE}$ is immediate from this. One of the greatest concerns of complexity theory (most of which are yet unsolved questions) is determining under which conditions this is a proper inclusion or not.


Why does the experience propagation rule for checkers work in Tom Mitchell's book? In Tom Mitchell's book "Machine Learning", Chap.1, a checkers game is used to illustrate how machine learning can be applied solve problems.

An experience propagation rule is described for iterative learning of a hypothesis. Suppose a game has been played and watched by the program, the state of the endgame is labeled 100 for winning and -100 for losing. For each of the states on the path toward the endgame, we label it as $\hat{V}(Successor)$, where $\hat{V}(state)$ is the current model output on some state. Then the model is trained by adding the new label, and iteratively, the model converges to a good checkers program.

Why does this experience propagation rule work? It is mentioned in the book that it works quite well for most chess games.

Sutton's book on reinforcement learning explains it but probably in more detail than what you're looking for, so I'll try to explain it more briefly and clearly.

Start by thinking about the last position before the end of the game. The winning player can win in one move from that position, so that position is almost certainly good for that player and bad for the other player. Now Think about the second to last position: that's only one move away from the last position which we've just established is probably a good position for the player that won in the end. The same logic applies to the third-last, fourth-last, etc.

See also: Wikipedia's page on mathematical induction, which works in a similar way.


Checking if two statements can be reached in one control flow Assume I have a graph representing the control flow and the call graph of a given program. I also have a first and a second statement. I now want to figure out if it is possible to execute both statements (in order) within the same program execution.

Control Flow Graph: I have a graph with all the statements of the program and edges connecting the statements determining the control flow of the program intra function (i.e., within a function).

Call Graph: I also have edges connecting any function call with the start of the function control flow of the called function.

The literature I found concerning control flow covers only intra function flow analysis and the only correct approach I can come up with is a depth first (or breadth first) search starting from the first statement. This, however, hardly feels correct as it is quite cumbersome and I would expect a better solution.

This can be solved with a "context-free reachability" query in a graph.  Each function call corresponds to an open parenthesis, each return corresponds to a close parenthesis, and you want to know whether there is a path in the graph such that the sequence of parentheses formed is properly nested and that traverses those two nodes in order.  If you search on that term you should find papers with algorithms for that problem.

The exact nature of the context-free language depends on how you formulate the question.  Suppose we want to know whether there is a path in the program that respects function calls and returns and visits $u$ and $v$, in that order.  One way is to ask whether there exists a path through the graph that starts at $s$ (the start point of the program), then eventually visits $u$, then eventually visits $v$, and where the word formed by this path is in the Dyck language $L$ of properly nested parentheses, e.g., $S = L(S)$ where $S := \varepsilon | (S)$.  Equivalently, you can ask whether there exists a path in the graph that starts at $u$ and ends at $v$, and where the word formed by this paths in a different context-free language $L'$, namely, the set of all suffixes of words in $L$.  Here $L'$ is context-free, as it can be recognized by the grammar $S' := S | S)$.  This then becomes a context-free reachability query on the graph.  In practice we have multiple parentheses symbols, one per function.  You can find these kinds of details in papers on context-free reachability.


How to calculate number of nodes opened by BFS? In the below diagram, each node takes up a space of 2KB. I need to find the total memory consumed to reach the goal : I

I know that the equation for BFS is

b1 + b2 + ...... + (bd+1 - b)

Where b is the branching factor and d the depth

But how do I calculate the branching factor in the below diagram, where the branches are uneven?

Also, is the depth on A node 0 or 1?

In the case of the above diagram, as you mention, there is no constant branching factor. This means that we cannot solve for the number of nodes explored using the formula you give above.

Instead, we must use knowledge of how BFS works in order to calculate which nodes were visited before Node I was found. In BFS, nodes adjacent to the current node are marked, and then placed in a queue. The next element in the queue is visited (and removed from the queue), and this process repeats. Use this process to figure out which nodes are visited before Node I, and then charge a cost of 2kB for visiting each node.


How can I determine if two vertices on a polygon are consecutive? Suppose I have a set of points that construct a convex polygon in the Cartesian plane with the points as its vertices. I randomly choose two vertices and want to know if they are consecutive vertices on the polygon. Does anyone know of an algorithm that would do this, as in you would input the array of points and the two vertices as parameters and it would return a boolean?

It's given that the polygon exists and is unique.

As the polygon is convex, it is simple! Two vertices are consecutive if all other vertices are located on the same side of the line that goes through these two points. This means that the cross product of the vector feom one of the pionts to the other one with the vector from the first point to any other one in the polygon have the same sign (all negative or all positive). For example, if those two points are called $P_1$ and $P_2$, you should compute all cross product of $\langle P_1, P_2\rangle$ with $\langle P_1, P_i\rangle$ ($P_i$ here means all other vertices).

Also, as discussed in the comment, we have some degenerate cases. The degenerate case is a common phenomenon in computational geometry, that is mostly handled separately. Here, the degenerate case is three points are located on a line.


How to interpret this formal language definition? I am asked to construct a PDA to accept the language:

$\qquad \{w \in \{0, 1\}^* : \#_{0}(w) \ge \#_{1}(w)\}$

I am wondering how to interpret the $\#$ symbols and everything. Could someone please explain what exactly this means and how to construct it?

This is pretty standard notation for

$\qquad \#_a(w) = |w|_a = $ number of occurrences of $a$ in $w$.

Building a PDA for this language is straight-forward. Find a hint below.

   Use the stack to count $\#_0 - \#_1$ in the processed prefix of the input. Figure out how to model negative numbers.


Direct-mapping cache I had this question on a previous homework assignment and was unable to answer it. I've done some research and am not really able to find anything that clears this up for me. Would appreciate any help or explanation.

Q2. Consider a direct-mapping cache of 128 lines and a main memory block size of 8 bytes. What cache line number does byte address 120010 map to?

The address generated by the CPU is divided into 3 parts for the identification of its position in the cache. These three field as you mus be knowing are : BYte Offset , Index and TAG . The index bits determine the line number in the cache.
You need to find the number of bits present in the index field.


Break an authentication protocol based on a pre-shared symmetric key, with message numbers Consider the following protocol, meant to authenticate $A$ (Alice) to $B$ (Bob) and vice versa.

$$ \begin{align*}
 A \to B: &\quad \text{“I'm Alice”}, R_A \\
 B \to A: &\quad E(\langle 1, R_A\rangle, K) \\
 A \to B: &\quad E(\langle 2, R_A+1, P_A\rangle, K) \\
\end{align*} $$

$R$ is a random nonce.
$K$ is a pre-shared symmetric key.
$P$ is some payload.
$E(m, K)$ means $m$ encrypted with $K$.
$\langle m_1, \ldots, m_n\rangle$ means an assemblage of the $m_i$'s that can be decoded unambiguously ($n$ is encoded unambiguously as well).
We assume that the cryptographic algorithms are secure and implemented correctly.

An attacker (Trudy) wants to convince Bob to accept her payload $P_T$ as coming from Alice (in lieu of $P_A$). Can Trudy thus impersonate Alice? How?

This is a follow-up to Break an authentication protocol based on a pre-shared symmetric key.

(re-post of my comment as an answer)

The only party that generates encryptions of messages $m$ such that $m$:

contains 3 parts
begins with a "2"

is Alice. Each time she generates such a chipertext, the last component is $P_A$. If $E$ is a strong enough encryption (non malleable), then Trudy will not be able to generate by herself a an encryption  $E(m)$ of a massage in the formt $m=\langle 2,R,P_T \rangle $ that Bob would accept (except with negligible probability).


Uncomputably coded model of computation There are many different but equivalent models of computation. I assume their equivalence is shown by coding input of one model to the input of the other model and making an argument why should there exists the same algorithm that would solve the problem on that model (e.g. emulation).

I was wondering, if there's a model of computation, that is equivalent to turing machines (the coding translation being just general bijection), but encoding standard input to its input would be an uncomputable problem. In essence making it an model of computation that is cut off from convetional models by it's coding being uncomputable. That would be first part of my question. I

For the second part, if such model exists, let's call it $S$, can you find other models of computations $S_0, S_1, \dots$, such that conversion between $S$ and $S_i$ would be computable by both $S$ and $S_i$? If $T, T_0, T_1,\dots$ were models of turing machine, and other conventional computation models, would $\mathcal{T}=\{T,T_0,T_1,\dots\}$ and $\mathcal{S}=\{S,S_0,S_1,\dots\}$ be two seperate "islands" of computation? Both equivalent, but no member of either family would be able to encode it's inputs to the other family? Or maybe only $\mathcal{S}$ would be able to, making some sort of partial order on such families of models of computation, like $\mathcal{T}<\mathcal{S}$?

note: I'm not sure if it's formal to talk about a model of computation as a mathematcical object, I meant most of the last paragraph mostly informally, but maybe it would suffice to just take set of all instances of such model of computation. Like $T=\{\text{all Turing machines}\}$, $T_0=\{\text{all Lambda expressions}\}$ and such .

Consider a standard coding of Turing machine $T_0$, $T_1$, $T_2$, ... Let $b : \mathbb{N} \to \mathbb{N}$ be a non-computable bijection. Define a new coding of Turing machines $T'_n = T_{b(n)}$. Clearly, the encoding $T'$ can do everything that Turing machines can do (whatever you do with $T$ you can do with $T'$ by composing with $b$ and its inverse), but it is not equivalent to $T$ by a computable bijection (or else $b$ would be computable).


Why is it better to do the data flow analysis in the basic blocks I have been reading about compilers and it is said that doing the data flow analysis in the basic blocks is more optimal.

Sadly, quoting the exact source, would be slightly hard as it is not in English, but a quote from wikipedia can also be used:

Data-flow analysis is the process of collecting information about the way the variables are used, defined in the program. It attempts to obtain particular information at each point in a procedure. Usually, it is enough to obtain this information at the boundaries of basic blocks, since from that it is easy to compute the information at points in the basic block.

Even though, in Wikipedia it is slightly explained, why the basic blocks are the preferred way, I still do not understand the benefits and if it is not obtained from the basic blocks, then from where?

It isn't "better" in the sense that the analysis is more precise. It's just more compact and cheaper to compute.

There's no reason why you can't compute an old-school iterative bit-vector-based dataflow analysis at every point between two intermediate-representation instructions. It will give you the same answer as doing it on basic blocks.

The main issue is that doing it this way, you need to store and manipulate the data at every point between two IR instructions. And remember, the only variable lifetimes that change across an instruction are the variables that participate in that instruction, so the sets on each side of an instruction are mostly the same. This is wasteful, especially on older machines.

Having said all that, we generally don't do dataflow analysis this way any more. Almost all modern compilers use some variant of static single assignment form. SSA form is cheap enough on modern machines, and gives you a more precise analysis: not only does SSA form give you the definitions that reach a program point, for example, it also gives you the paths along which those definitions reach.


Can a Boolean circuit be considered an algorithm? Can a Boolean circuit by itself be considered an algorithm (a single step algorithm if you like)? For instance say you have a simple tree circuit with two AND gates as the input gates feeding a single OR gate for a depth two circuit. Now change the AND gates to XOR gates, is it correct to say that I now have a different algorithm for any given input?

Have a look at Turing-completeness and the Church-Turing thesis (CT). Basically, CT is saying that everything that is computable, is computable on a Turing machine. Many different models of computation are known to be equivalent to the Turing machine. Even if you are considering something esoteric you came up with yourself, if what you have is Turing-complete, you can claim that you really do have an algorithm.

A circuit is a non-uniform model of computation, meaning that different size circuit compute things for different size inputs. A Turing machine on the other hand is a uniform model, so it's used for all input lengths. Given a Turing machine, one can construct a Boolean circuit that is able to simulate all its computation if we put a bound on the Turing machine's memory. Also, given a circuit, we can build a Turing machine that simulates the circuit.


What are common formal techniques for proving functional code correct? I want to provide proofs for parts of a Haskell program I'm writing as part of my thesis. So far however, I failed to find a good reference work.

Graham Hutton's introductory book Programming in Haskell (Google Books)—which I read while learning Haskell—touches on a few techniques for reasoning about programs such as

equational reasoning
using non-overlapping patterns
list induction

in chapter 13 but it's not very in-depth.

Are there any books or article you can recommend which provide a more detailed overview of formal proving techniques for Haskell, or other functional, code?

You can start with

Software Foundations by Benjamin C. Pierce et al.

  Topics include basic concepts of logic, computer-assisted theorem proving, the Coq proof assistant, functional programming, operational semantics, Hoare logic, and static type systems. The exposition is intended for a broad range of readers, from advanced undergraduates to PhD students and researchers. No specific background in logic or programming languages is assumed, though a degree of mathematical maturity will be helpful.

You can skip (or skim) the programming language theory parts and only learn how to deal with formal proofs starting from Preface up to IndPrinciples. The book is really well-written and illuminating.

Then you might want to proceed with

Verified Functional Algorithms by Andrew W. Appel

  In this volume you will learn how to specify and verify (prove the correctness of) sorting algorithms, binary search trees, balanced binary search trees, and priority queues. Before using this book, you should have some understanding of these algorithms and data structures, available in any standard undergraduate algorithms textbook.
  You should understand all the material in Software Foundations Volume 1 (Logic Foundations)

A note of warning: VFA is still in beta-release!


Minimum weighted arithmetic mean partion? Assume I have some positive numbers $a_1,\ldots,a_n$ and a number $k \in \mathbb{N}$.

I want to partition these numbers into exactly $k$ sets $A_1,\ldots,A_k$ such that the weighted arithmetic mean

$$\text{cost}(A_i,\ldots,A_k)=\sum_{i=1}^{k}\frac{|A_i|}{n}c(A_i)$$

is minimal, where $c(A_i)=\sum_{a \in A_i}a$ is simply the sum of all numbers in $A_i$.

Is there actually a (polynomial) algorithm to do this or is this a (NP) hard problem?

I tried to reduce it to some NP-hard problems but didn't get anywhere, especially because the numbers are nonnegative and thus in an optimal partition big sets need to have smaller weight which seems to be some kind of balancing problem instead of a packing problem (which I am more familiar with).

Suppose first that we fix the sizes of the sets $|A_i| = n_i$ in non-decreasing order $n_1 \leq \cdots \leq n_k$. In that case, if we arrange the numbers $a_i$ in non-decreasing order, then an optimal choice is
$$ A_1 = \{a_n,\ldots,a_{n-n_1+1}\}, A_2 = \{a_{n-n_1},\ldots,a_{n-n_1-n_2+1}\}, \ldots, A_k = \{a_{n_k},\ldots,a_1\}. $$
The reason is that given any solution where $a_i \in A_I$ and $a_j \in A_J$, switching $a_i$ and $a_j$ will result in a total change of
$$ -n_Ia_i-n_Ja_j + n_Ja_i+n_Ia_j = (n_I-n_J) (a_j-a_i),$$
so the switch is beneficial (or harmless) as long as $n_I \leq n_J$ and $a_j \geq a_i$.

In view of this, there is always an optimal solution in which $A_1,\ldots,A_k$ is a partition of $a_1,\ldots,a_n$ into intervals. This suggests a dynamic programming algorithm. For each $\ell \leq k$ and $t \leq m \leq n$, we compute
$$ \min_{A_1,\dots,A_{\ell-1} \vdash a_1,\ldots,a_t} \sum_{i=1}^\ell |A_i| c(A_i), \quad \text{where $A_\ell = \{a_{t+1},\ldots,a_m\}$}. $$
Here $A_1,\dots,A_{\ell-1} \vdash a_1,\ldots,a_t$ means that the left-hand side is a partition of the right-hand side into intervals. I am assuming that sets could be empty; the algorithm can be modified to ensure that sets are not empty (just make sure $\ell \leq t < m$).


Greedy algorithm Packing problem Assume that $A$ is the set of objects  such that each object $x_i \in A$ has value $w_i$. We wish to pack these objects into group, each pack containing at least $k$ objects. Our goal is to minimize the maximum difference between the maximum and minimum value of each packs.
in other words, our goal is to minimize $L$ with the constraint that all packs should have more than $k$ object in them.

$$L = \max_{i \in \mathrm{packs}}  \left\{\max_{j \in \mathrm{pack}(i)}w_j - \min_{k \in \mathrm{pack}(i)}w_k \right\}.$$

For example for the following packing, $L$ is $\max{(30-20, 120 - 100)} = 20$.
$$[20, 30] \;\; [100,110,120]$$

I was wondering if there is a greedy algorithm that can do the job.

I would not believe there is a greedy algorithm that can do the job. Instead, sorting followed by dynamic programming as indicated by j_random_hacker's comment seems the appropriate way to find $L$.

Let $n$ be the number of given objects. Assume $k\le n$; otherwise there is no such packing.

First, sort all the weights so that we will have $w_0\le w_2\le \cdots\le w_{n-1}$. Then there is an optimal packing in which each pack consists of consecutive weights. That fact enables dynamic programming, since we can consider only that kind of packing, which has a natural last pack.

Given a packing $P$, let $L(P)$ be the maximum difference between the maximum and minimum value of each pack in $P$. Let
$dp[i]$ be the minimum of $L(P)$ for all packings of the weights $w_0, w_1,\cdots, w_i$, where $k-1\le i\le n-1$. The final answer for all $n$ weights is $dp[n-1]$.

The base case is $dp[i] = w_i-w_0$ for $k-1\le i\lt 2k-1$, as there can be only one pack that contains all the weights.

What if $i\ge 2k-1$? Note that a packing with its last pack removed is still a packing. That critical observation tells us that $dp[i]$ is the minimum of
$$\begin{align}
&\max(dp[i-k],\ w_i-w_{(i-k)+1}), \\
&\max(dp[i-k-1],\ w_i-w_{(i-k-1)+1}), \\
&\max(dp[i-k-2],\ w_i-w_{(i-k-2)+1}), \\
&\cdots,\\
&\max(dp[i-k-\ell],\ w_i-w_{(i-k-\ell)+1}), \\
&\cdots,
\end{align}$$
where the list stops right before $\ell$ becomes $k$, since we can ignore the packings where the last pack (in fact, any pack) contains at least $2k$ objects. We can always split those objects into 2 valid packs, which will not increase $L(P)$. We can also stop as soon as $w_i-w_{(i-k-\ell)+1}$ is no less than the minimum so far.

The time-complexity of algorithm is $O(n\log n + nk)$.


Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages) language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} )
(sorry for the formatting, see screenshot-link for conventional/clear expression)
The purpose is to prove that the given language is not a context-free-language (using the pumping lemma).
So i thought that this language should definitely be pumpable, since you can choose x and z as corresponding parts in one of the u/"halves". So if word to be pumped is "0101" then you choose e.g. x=1 (0101) and z=1 (0101) and the remaining parts that stay static are assigned with u=0 (0101), y=0(0101), and v=empty.
If pumped zero-times/i=0 word reads: 00
i=1: 0101
i=2: 011011
i=3: 01110111
(and so on)
(For more complicated words you would need to use all three (u, y, v), but the basic principle would still be that x and z are assigned corresponding parts of the word and u,y,v would be assigned the remainder. (This doesn't work for the extremely small words 00,01,10,11 that would become empty when zero-pumped, but as long as the exceptions are finite / of finite/fixed number this isn't a problem AFAIU.)
Clearly this is wrong, but can anybody explain how/why?

Some strings in your language are pumpable, others aren't. You have to look for one that isn't pumpable. Use the fact that the relevant piece is of limited length.
In your case, say the pumping length is $N$, and take $\sigma = 0^N 1^N 0^N 1^N$. You'll find that however you position the part that gets pieces repeated, you won't be able to increase the first and second stretch of $0$ or of $1$, or get the correct repeat by pumping around one of the $0/1$ boundaries.


Unique boolean functions with one input I need to write a truth table for all possible unique Boolean functions with one input. However, I am confused regarding the word "unique".

I thought about writing down the truth table for a NOT, since it has just one input.

This task is simple enough if you already know exactly what a function is and how to construct a truth table; you just have to write down every possible combination of assignments to all variables and functions, e.g., $x = 0$, $f(0) = 0$, and so on. If it isn't obvious, it might be beneficial to walk through a more drawn-out reasoning, which might also be more useful whenever you want to count and/or enumerate all possible functions where the number of functions is bigger, and the functions might not be that relatable (like for example how the negation function is relatable).

First of all we can count how many functions there are.

  Given sets $A$ and $B$, there are $|B|^{|A|}$ functions $f : A \rightarrow B$.

So since we have $\mathbb B = \{0, 1\}$, $^*$ and we are concerned with functions $f : \mathbb B \rightarrow \mathbb B$, we have $2^2 = 4$ functions.

The next step is to make a truth table. But first, let's look at what a function is:

  A function $f : X \rightarrow Y$ is a subset of the Cartesian product $X × Y$ subject to the following condition: every element of $X$ is the first component of one and only one ordered pair in the subset.

So we must find all sets that are subject to these constraints. An example of a set that is not a function is:

$S = \{(1,0), (1,1)\} \subset \mathbb B × \mathbb B$

since $1$ is the first component of two ordered pairs, ie. the value $1$ maps to two different values. Moreover, we don't have a mapping for the value $0$, ie. $f(0)$ is undefined.

Since we are dealing with a domain of size two, and since we have one and only one ordered pair for each member of the domain, all sets (functions) that we are considering are on the form:

$f = \{(0,\_),(1,\_)\}$

where $\_$ is either $0$ or $1$.

So then we list all possible enumerations of two ordered boolean values, and put them in the pair as the second component with the $0$ as the first component and the $1$ as the first component, respectively:

$0,0$

$1,1$

$1,0$

$0,1$

Plugging these in, we get:

$f_1 = \{(0,0),(1,0)\}$ ($f(x) = 0$)

$f_2 = \{(0,1),(1,1)\}$ ($f(x) = 1$)

$f_3 = \{(0,1),(1,0)\}$ ($f(x) = \neg x$)

$f_4 = \{(0,0),(1,1)\}$ ($f(x) = x$)

(As a sanity check, we confirm that we ended up with 4 functions, as expected.)

As a truth table:

$$\begin{array} {|c|c|c|c||c|}
\hline
x & f_1(x) & f_2(x) & f_3(x) & f_4(x)\\ \hline
0 & 0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 & 1 \\ \hline
\end{array} $$

* Or $\mathbb B = \{F,T\}$, if you prefer.


What subset of TMs are there where the halting problem is decidable? Halting problem is not decidable in general, but are there interesting/useful subsets where it IS decidable? Bonus points if that subset is actually helpful.
Example:
If we know BB(x), then the halting problem for TMs with x states is decidable. The problem is BB(x) is not a computable function, as it basically requires solving the halting problem in the first place, so this doesn't help construct a general halting problem solver for arbitrary x. We do however, know BB(x) for x < 5 (which isn't very helpful I imagine, but still...).
Still, I guess that means technically the halting problem is decidable for subsets which contain all TMs with the same finite amount of states, but we still can't construct a TM that decides it without first solving the halting problem.
Similarly, any finite subset of TMs is trivially decidable by some TM that just happens to correctly map the input TMs to truth values. Again, we can't construct this TM. Not very interesting or helpful.

If you don't look at turing machines in particularly: Sometimes you can make an argument "if it halts at all, then it must halt within x steps" where x can be calculated, so you decide the halting problem by calculating x and performing x steps.
One particular case: A program with nested loops, where an upper limit for the number of iterations of each loop can be calculated before the loop is executed, will halt. And if you take such a program and insert identifiable "non-halting" constructs, like "for (;;) {}" in a C program, then the halting problem is decidable.


What makes an MILP problem solvable? Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic programming and 0-1 assignment problem can be solved using Hungarian algorithm in polynomial time. So what makes a MILP problem solvable? Is there any reference?
Thanks

You may be interested in reading about total unimodularity. An ILP is solvable in polynomial time if the associated matrix is totally unimodular (sufficient but not necessary condition). This explains the tractability of assignment and maximum flow problems.

I'm not aware of any "reason" why knapsack is pseudopolynomial time solvable.


Using the rules of inferences I know the rules of inferences and logical equivalence but I cannot seem to validate this argument.  I rewrote the first premise as $\neg p\vee q$ other from that I am stuck.  Any help will be appreciated.

$$
\begin{array}{c}
p \to q \\
(q \land r) \to s \\
r \\
p \\ \hline
s
\end{array}
$$

Since $p$ and $p\to q$, we have $q$ by modus ponens.
Since $q$ and $r$, we have $q \land r$ by definition of conjunction.
Since $q \land r$ and $(q \land r) \to s$, we have $s$ by modus ponens.


Error-correcting rate is misleading In coding theory, 'how good a code is' means how many channel errors can be corrected, or better put, the maximal noise level that the code can deal with.

In order to get better codes, the codes are designed using a large alphabet (rather than binary one). And then, the code is good if it can deal with a large rate of erroneous "symbols".

Why isn't this consider cheating? I mean, shouldn't we only care about what happens when we "translate" each symbol into a binary string?  The "rate of bit error" is different than the rate of "symbol error". For instance, the rate of bit-error cannot go above 1/2 while (if I understand this correctly), with large enough alphabet, the symbol-error can go up to $1-\epsilon$. Is this because we artificially restrict the channel to change only "symbols" rather than bits, or is it because the code is actually better?

Many widely used codes for binary data are concatenated codes, which are composed by using two error-correcting codes. The inner code is over a binary alphabet, and the outer code is over an alphabet whose symbols correspond to the codewords of the inner code. This allows you to use the superior power of larger alphabet sizes to encode binary messages without "cheating".

The standard definition of minimum distance is a natural one to use when considering concatenated codes, as well as in the theory of codes over large alphabet sizes. It would only be "cheating" if you used these numbers to compare a binary code with a large-alphabet code that encodes binary input without using an inner code as well; coding theorists are clever enough not to do this (and I believe that since concatenated codes were invented, large-alphabet codes have often been used along with an inner code, but large-alphabet codes are also very good for correcting error in bursty channels such as CDs, since a large number of consecutive bit errors will only affect a few "symbols").


What are the difference between and consequences of using type parameters and type indexes? In type theories, like Coq's, we can define a type with parameters, like this:

Inductive ListP (Element : Type) : Type
  := NilP  : ListP Element
   | ConsP : Element -> ListP Element -> ListP Element.

Alternatively, we can define a type with an index, like this:

Inductive ListI : Type -> Type
  := NilI  : forall t, ListI t
   | ConsI : forall t, t -> ListI t -> ListI t.

My questions are:

Are these fundamentally different or fundamentally the same?
What are the consequences of using one over the other?
When is it preferable to use one over the other?

ListP t and ListI t are isomorphic: they have exactly the same constructors.

<prompt>Coq < 12 || 0 < </prompt>Check (NilP, NilI).
(NilP, NilI)
     : (forall t : Type, ListP t) *
       (forall t : Type, ListI t)

<prompt>Coq < 13 || 0 < </prompt>Check (ConsP, ConsI).
(ConsP, ConsI)
     : (forall t : Type, t -> ListP t -> ListP t) *
       (forall t : Type, t -> ListI t -> ListI t)

However Coq generates different induction principles.

<prompt>Coq < 14 || 0 < </prompt>Check (ListP_ind, ListI_ind).
(ListP_ind, ListI_ind)
     : (forall (t : Type) (P : ListP t -> Prop),
        P (NilP t) ->
        (forall (t0 : t) (l : ListP t), P l -> P (ConsP t t0 l)) ->
        forall l : ListP t, P l) *
       (forall P : forall T : Type, ListI T -> Prop,
        (forall t : Type, P t (NilI t)) ->
        (forall (t : Type) (t0 : t) (l : ListI t),
         P t l -> P t (ConsI t t0 l)) ->
        forall (T : Type) (l : ListI T), P T l)

The induction principle of ListI requires the property to be parameteric in the element type (P : forall T, ListI T -> Prop) whereas the induction principle of ListP can be instantiated at any type t (P : ListP t -> Prop). This is a weakness of Coq's front-end, in that it is not smart about non-uniform recursive types; you can manually define the same induction principle (the typechecker accepts it, which is unsurprising given that it is ListP_ind transformed by the obvious isomorphism between ListP and ListI).

The parametric form ListP is simpler and easier to use out of the box. The ListI form can generalize to non-uniform recursion, where the parameters in the recursive calls are not the original. See Polymorphism and Inductive datatypes for an example.


Statement of the Goldwasser-Sipser Set Low Bound Protocol I'm trying to understand the statement of the Goldwasser-Sipser Set Low Bound Protocol as presented in "Computational Complexity: A Modern Approach" by Arora and Barak.
In particular, I'm trying to understand why the following claims yields what we would want:
$S \subseteq \{0,1\}^m$ is a set such that membership can be certified. Both parties know a number $K$. Let $k$ be an integer such that $2^{k-2} < K \le 2^{k-1}$.
Claim: Let $S \subseteq \{0,1\}^m$ satisfy $|S| \le 2^{k}/2.$ Then for $p=|S|/2^k$ we have $p \ge \mathbf{P}_{h \in_{_R} \mathcal{H}_{m,k}, y \in_{_R} \{0,1\}^k}\left[\exists x \in S: h(x)=y \right] \ge \frac{3p}{4}-\frac{p}{2^k}.$
My understanding is that we want:

If $|S| \ge K$ then the verifier should accept (corresponding to the prover finding such an $x$ in the claim) with "high" probability;
If  $|S| \le K/2$ then the verifier will accept with probability at most 1/2.

I'm getting thrown off by a few things here:

the claim assumes that $|S| \le 2^k/2 = 2^{k-1} = 2\times2^{k-2} < 2 K$, so how does this place us in one of the relevant cases?
How do we actually use those left ($p$) and right ($3p/4 - p/2^k$) bounds to conlude what we want?

Overall, I'm understand bits and pieces of this setup, but I'm having trouble seeing how it all fits together. Can someone walk through the logic/algebra here?

To succeed in distinguishing the case of $|S|\ge K$ from $|S|\le\frac{K}{2}$, you just need a constant gap (independent of $|S|$) in the acceptance probability in both cases. If you managed to achieve such a gap, then applying Chernoff to multiple executions of the protocol would achieve high success probability.
Observe that the interesting case is $k\le m$, since otherwise $K\ge 2^{k-2}\ge2^{m-2}$, and the verifier can convince himself that $|S|\ge K$ simply by sampling strings in $\{0,1\}^m$ uniformly at random and checking whether they belong to $S$ (in this case $|S|\ge K$ implies that the probability of falling in $S$ is at least $1/4$, so Chernoff with a polynomial number of samples yields the desired result). From now on assume $m\ge k$, and thus the hash functions are $h_{a,b}:GF(2^m)\rightarrow GF(2^k)$ given by $h_{a,b}=(ax+b)_{1...k}$, where $x_{1...k}$ in the truncation of a string obtained by taking the first $k$ bits.
For uniformly distributed $a,b\in GF(2^m)$, and every $x\in GF(2^m)$, $ax+b$ is uniformly distributed. This means that $\forall x\in GF(2^m): \Pr\limits_{\substack{a,b\in GF(2^m)\\y\in GF(2^k)}}\left[(ax+b)_{1...k}=y\right]=\frac{1}{2^k}$. We conclude that $\Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\le \frac{|S|}{2^k}$. On the other hand, we can lower bound the same probability by:
$$
\Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\ge\\
\sum\limits_{x\in S}\Pr\limits_{a,b,y}\left[h_{a,b}(x)=y\right]-\sum\limits_{x\neq x'\in S}\Pr\limits_{a,b,y}\left[h_{a,b}(x)=y \land h_{a,b}(x')=y\right]=\\\frac{|S|}{2^k}-\frac{}{}\binom{|S|}{2}\frac{1}{2^{2k}}\ge \frac{|S|}{2^k}\left(1-\frac{|S|}{2^{k+1}}\right).
$$
So far there were no restrictions on the size of $S$. Now, if $|S|\le K\le 2^{k-1}$ then $\frac{|S|}{2^k}\le\frac{1}{2}$, and we obtain $\Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\ge \frac{3}{4}\frac{|S|}{2^k}$. We conclude that if $|S|=K$ then the probability of acceptance is at least $\frac{3}{4}\frac{K}{2^k}$ (the bound trivially holds for larger $|S|$, just by taking a subset of size $K$). If on the other hand $|S|\le K/2$ then the acceptance probability is at most $\frac{1}{2}\frac{K}{2^K}$ and we have our constant gap $\ge\frac{1}{4}\frac{K}{2^k}$, and Chernoff completes the proof.


Can a CS grad student work on quantum field theory and string theory problems? The mathematical aspect of particle physics theory are interesting and there seems to be a lot more connections being made to computation and information (like with complexity theory having some impact of physics and the whole quantum computation thing). Does it make sense (or is even possible) to work on some of these connections as a grad student in a theoretical computer science department or should I be looking at mathematical physics programs instead?

My main concern is with finding advisors and departments that are game for something like this (given that this makes any sense in the first place).

There are plenty of computer scientists working on quantum computation and quantum information so, yes, there should be plenty of opportunities to work on that sort of thing as a CS grad student.

I'm not aware of any computer scientists working on string theory but it's far from my area of expertise so it's possible it happens without my knowing about it. However, I've been to plenty of theoretical CS conferences where there were a couple of talks about quantum things but I don't remember any talks at all about string theory. And, of course, if you try to Google for something like "string theory computer science", Google thinks you mean strings of text.


Are there algorithms or circuits that can implement addition without the need for carry flags Let two numbers $x,y$ be represented in some digit form (binary, octal, ...): $(x_1 x_2 x_3 \ldots)$ and $(y_1 y_2 y_3 \ldots)$.

Can we add those numbers such that we do not need to carry over: $x_i = x_i+y_i + c(x_{i-1},y_{i-1})$ where $c(x_{i-1},y_{i-1})$ is the carry value of $x_{i-1}$ and $y_{i-1}$.

Are there $O(1)$ step circuit implementations of addition that exist? Are they practical?

In other words, is addition inherently recursive over the number of digits?

For non-redundant representations like $(x_n, x_{n-1}, ..., {x_1})$ the recursion is fundamental (although the operator is associative so you can apply the prefix sum optimization to parallelize the operation down to $O(\lg n)$ steps.)

But there are redundant representations where addition can be performed more efficiently, in some cases.  The carry-save adder is used in most hardware multiplier implementations, where you need to sum together a large list of numbers.

The redundant representation is just to represent every number by two subsums:

c3 c2 c1
x3 x2 x1 x0

so, for example, the number "5" can be stored either as:

 0  0  0
 0  1  0  1

or

 0  0  1
 0  0  1  1

The "addition" operation adds three subsums and produces two subsums:

 0  0  1
+0  0  1  1
+0  0  0  1
-----------
 0  1  1  0
 0  0  0  0

So, not very useful if you are just adding two numbers, but when you need to sum a whole list of numbers, each individual addition is fast, and then only at the end do you have to convert back to a non-redundant representation.

There are other redundant representations used in hardware multiplication algorithms, like Booth encoding where the digits can be positive, zero or negative.


In the "tall cache assumption" what does $\Omega$ represent? Within the field of cache-oblivious algorithms the ideal cache model is used for determining the cache complexity of an algorithm.  One of the assumptions of the ideal cache model is that it models a "tall cache".  This is given by the statement $Z = \Omega(L^2)$.  Where $Z$ is the size of the cache and $L$ is the size of the cache line.  What does $\Omega$ represent?

It's the lower bound counterpart to O($\cdot$). Z is larger than some constant times $L^2$


Is the following Grammar LL(1) I was given the following grammar

$S \rightarrow S (  S  ) S\mid \epsilon$

First I was asked to eliminate left recursion, yielding me the following :

$S \rightarrow S' $

$S' \rightarrow (S)SS' \mid \epsilon$

I was then asked If the grammar is LL(1). So I computed the FIRST and FOLLOW sets shown below:

$\mathrm{FIRST}(S) = \mathrm{FIRST}(S') = \{ ( , \epsilon \}$,

$\mathrm{FOLLOW}(S) = \mathrm{FOLLOW}(S') = \{ \$, ( , ) \}$.

I now tried building the LL(1) parsing table $M$ as follow:

Since we have production $S \rightarrow S' $ and $\mathrm{FIRST}(S') = \{ ( , \epsilon \}$, the table's entry  $M [ S , ( ] = S \rightarrow S'$.

But since $\epsilon$ belongs in $\mathrm{FIRST}(S')$ then for each element $b$ in $\mathrm{FOLLOW}(S)$,

$M [ S , b ] = S \rightarrow S' $.

This would entail that $M [ S , ( ] = S \rightarrow S' $.

Since the entry was already populated, is this a conflict? If yes, what kind?

Or since the 2 productions are the same we can just ignore it?

Also if the second case is the right one, is the grammar LL(1)?

Since the entry was already populated, is this a conflict? If yes, what kind? Or since the 2 productions are the same we can just ignore it? Also if the second case is the right one, is the grammar LL(1)?

Although the entry was populated, this is not a conflict since the same rule is put into the table entry $M [ S , ( ]$, which can be ignored.

However, the grammar is not LL(1). This can be seen from either of the following.

The string ()() has following two different leftmost derivations.
$$S\rightarrow S'\rightarrow (S)SS'\rightarrow (S')SS'\rightarrow ()SS'\rightarrow()S'S'\\
\rightarrow()(S)SS'S'\rightarrow()(S')SS'S'\rightarrow()()SS'S'\\
\rightarrow()()S'S'S'\rightarrow()()S'S'\rightarrow()()S'\rightarrow()()$$
$$S\rightarrow S'\rightarrow (S)SS'\rightarrow (S')SS'\rightarrow ()SS'\rightarrow()S'S'\\
\rightarrow()S'\rightarrow()(S)SS'\rightarrow()(S')SS'\rightarrow()()SS'\\
\rightarrow()()S'S'\rightarrow()()S'\rightarrow()()$$
When we build the table entry $M[S', (]$, it will have two entries, $S' \rightarrow ( S ) S S'$ and $S' \rightarrow\epsilon$.

Although neither the new grammar nor the original grammar is LL(1), the language generated by either of them is LL(1) since it is generated by following LL(1) grammar.

$$S \rightarrow (S)S \mid \epsilon $$


There is an $n^k$ prover if and only if $P = NP$ I am studying computational complexity using Papadimitrious's book: "Computational Complexity".
I am trying to solve the final statement of Problem 8.4.9, but I am stuck and would like some hint on how to proceed.
Problem 8.4.9:

"Let $f(n)$ be a function from integers to integers. An $f(n)$-prover is an algorithm which, given any valid expression in first-order logic that has a proof in the axiomatic system in Figure 5.4 of length $l$, will find this proof in time $f(l)$. If the expression is not valid, the algorithm may either report so, or diverge (so the undecidability of validity is not contradicted).
(a) - Show that there is a $k^n$ prover, for some $k > 1$.
In a letter to John von Neumann in 1965, Kurt Gödel hypothesized that an $n^k$ prover exists, for some $k \geq 1$. For a full translation of this remarkable text, as well as for a discussion of modern-day complexity theory with many interesting historical references, see:

M.Sipser "The history and status of the P versus NP problem" Proc. of the 24th Annual ACM Symposium on the Theory of Computing, pp.603-618, 1992.

Problem: Show that there is an $n^k$ prover, for some $k > 1$, if and only if $P = NP$."

Figure 5.4 that he mentions contains the standard logical axioms for first-order logic (I can post the picture here, if you like).
I tried reading the mentioned article, and although it is very interesting from the historical point of view, it didn't help me figure out the solution. My first attempt was to use the result that a formula $\phi$ is valid if and only if its negation $\neg \phi$ is not satisfiable and try to connect this problem to $SAT$, which we know is $NP$-complete. However, using this result I obtain something about a formula NOT being satisfiable, while $SAT$ is about satisfiability.
Can anyone help me with this statement? Thanks in advance.
PS: Not closely related to what I am asking, but I think I was able to solve letter (a) by noticing that if a formula is valid, then we can apply the logic axioms (and the number of logic axioms is constant) without worrying about how we instantiate variables since a valid formula is true under all possible interpretations.

An $n^k$ prover implies that the set $\{\left(\varphi,1^n\right)|\text{$\varphi$ has a proof of length $\le n$}\}$ is in $P$, since we can simply run the prover for $n^k$ steps and check whether it yields a valid proof.
It remains to show that this language is NP complete. This follows from a straightforward reduction from SAT. Given a CNF $\varphi$ over the variables $x_1,...,x_n$ return the pair $\left(\exists x_1,...,x_n: \varphi, 1^k\right)$ where $k=k(|\varphi|)$ is some upper bound on the length of the satisfiability proof for satisfiable formulas of length $|\varphi|$.


The Church-Turing Thesis (Hello World tester) contradiction and randomized algorithms The Church-Turing thesis proves that there is no algorithm (or program) $H$ that says whether a program $P$ written in a language, say $C$, on an input $I$ outputs the sentence Hello World or not. This is his proof, visit Hopcraft and etc. introduction to automata theory languages and computation, chapter 8.

The prove is by contradiction. Let there is such a program $H$ to do the task. He made several simple changes to $H$ and built a program $H_2$, then showed $H_2$ doesn't exits.

The program $H$ is as follows

On input $P$ and $I$, it outputs yes or no which tells if the output is Hello World or not.

He then build program $H_1$ as follows

$H_1$ takes $P$ and $I$ and runs $H$ on $P$ and $I$, if $H$ prints yes, it prints yes and if $H$ prints no, it prints Hello World. The $H_1$ is as follows

He then built $H_2$ as follows

$H_2$ reads the $P$ and store in an array $A$.
$H_2$ simulates the $H_1$, but whenever $H_1$ would read an input, $H_2$ reads from stored copy in $A$.

Hence $H_2$ prints yes if $P$ prints Hello World when given itself as input and Hello world if doesn't print Hello World.

The contradiction occurs when when the $P$ is actually program $H_2$, the source code of $H_2$ is provided as input to itself. If the $H_2$ prints Yes, then $H_2$ in the box saying $H_2$ on input $H_2$ prints Hello World and the Hello World is the output of no in $H$.

  The basis of contradiction is, $H_2$ on input source code of $H_2$ printed no while we assumed it is yes and a program on the same input can't have different outputs.

If $H$ were a program with randomized algorithm, then on the same input it would have different outputs. The basis of the contradiction is if $H_2$ on input $H_2$ prints something, it can't print something else on $H_2$ again. But if $H$ contains some random process inside it, then on the same input it would print different things and it is not a contradiction at all.

Please explain where I am wring about this.

Thanks in advance.

The Church-Turing thesis proves that there is no algorithm (or program)  that says whether a program  written in a language, say , on an input  outputs the sentence Hello World or not. This is his proof, visit Hopcraft and etc.

The Church-Turing thesis is introduced in the book as "the unprovable assumption that any general way to compute will allow us to compute only the partial-recursive functions (or equivalently, what Turing machines or modern-day computers can compute)". It has little to do with undecidability directly. I will treat "The Church-Turing thesis proves that" as a typo that should not exist.

  Please explain where I am wrong about this.

In fact, you are not necessarily wrong at all. It is just that your argument does not lead us anywhere.

What have been proved in the book is that there is no non-randomized algorithm that can decide whether a non-randomized program on an input outputs "Hello World" or not. No, there is no such adjective "non-randomized" in the original statement in the book. However, it does not matter much whether we add it or not. Why?

Because a randomized algorithm cannot decide anyway. It can only say something like the probability a given program on some given input outputs "Hello world" is less than 23 percent. I will not call that probabilistic prediction a decision. You have not found anything valuable or interesting by considering randomized algorithms. All you have observed is that the proof does not apply to randomized algorithms, which we do not have to consider in the first place anyway.

We might be thinking, wait, there is some information if we can be certain the probability a given program on some given input outputs "Hello world" is less than 23 percent. That could be mean that the undecidability only holds in some relative sense.

However, the conclusion is still something along the line that there is no algorithm, whether randomized or not, can always provide non-zero information regarding whether a deterministic program on a input outputs "Hello world" or not. You can read the question can a probabilistic Turing machine solve the halting problem? and its answers for more explanations.


When LRU is NOT the optimal replacement policy I've been googling this topic but still couldnt get a legit answer. So can someone explain with some examples that if we were to use cache memory instead of LRU we would have lower miss rate (better peformance). Or simply when LRU is not an optimal choise.

Consider a program that plays a video in an endless loop (e.g. an electronic advertising billboard), assuming the RAM is constrained enough that the whole video can't fit at once.

The most recently used page of memory will contain the most recent section of the video, that just played. LRU would be the worst choice, because you're holding onto the parts that have already played, which are the parts that won't be needed for the longest time. They won't be needed again until all other pages are played first, and the video repeats. By definition, such a use case is hitting the least recently used pages, over and over.

The optimal page replacement policy in such a situation is one that either preempts the future pages (which is possible in this case because of the periodicity and simplicity of this usage profile) or one which permanently  holds onto some parts of the video (doesn't matter which parts, as they're all played equally) and uses the rest of the space to cycle through the rest of the pages.


What is the problem with this Busy Wait solution for two threads? We have two processes. One process produces F and the other process consumes F

Initialization:

Consuming = false
Produced = false
F = EMPTY

The first thread (we can think of it as some kind of producer):

P1:
loop_for_ever:
    Produce(F)
    Consuming = true
    Produced = true
    while(Consuming) {Busy Wait)

And here is P2:

P2:
loop_for_ever:
    while(NOT Produced) {Busy Wait}
    Consume(F)
    Produced = false
    Consuming = false

One problem with this solution is after P1 has produced F, there is no way for P2 to consume F until P1 unlocks the Produced variable. Any other problems with this solution with regards to mutual exclusion? Is there a scenario in which P1 and P2 try to produce and consume F at the same time?

EDIT:

After reading fade2black's answer, I think I first need to address another more basic question. So let's add these extra conditions.

Extra conditions:

1- No mutex or semaphore based solution (only busy wait).

2- The threads have no remainder section (in that case this approach would obviously not work). Basically, what I am trying to do is to take a sequential algorithm (such as the one @fade2black has given) and distribute it among two threads. I could have blindly used an algorithm such as Dekker's (with turn given to P1 at the beginning). So I think first I need to find an answer for this question : "Is there any point to try and use a concurrent algorithm for this problem"? (when there is only one consumer and one producer and there is only one shared space between the two).

Your approach works fine providing assignment operations are atomic. But I cannot see any concurrency in your approach. $P_2$ always waits until $P_1$ produces and reaches the upper limit, for example until it completely fills the buffer. Then it triggers $P_2$ to consume and waits until $P_2$ consumes all items, for example empties the buffer. So the algorithm can be rewritten as

doStuff()
  loop-forever
    produce(F) # N items
    consume(F) # N items
  end
end

In fact the consumer(s) consumes as soon as the producer(s) produces items. In this case you would have to use synchronizations techniques such as mutexes.

Also (from here)

  The producer–consumer problem, particularly in the case of a single producer and single consumer, strongly relates to implementing a FIFO or a channel.

So there is no point to try and use a concurrent algorithm for this problem.  But if your model is multi producer/consumer model then your approach may lead to the race condition.


Assumption: A PSPACE-hard problem can be solved in polynomial time Under the assumption that a PSPACE-hard problem A can be solved in polynomial time, is the following argumentation valid?

Since every problem in PSPACE can be reduced to A in polynomial time, every problem in NP which is a subset of PSPACE is included. That means that each Problem in NP is solvable in polynomial time and therefore P = NP.

Since coNP is a subset of PSPACE as well, we can argue that every problem in coNP can be reduced to A and therefore be solved in polynomial time as well, which means that P = coNP.

Therefore we can say that P = NP = coNP.

I don't see a problem with this argumentation at the moment, but it seems a bit too simplistic to me, so is this a valid way of arguing for the equality above?

Your argument is perfectly fine. However, you actually do not even have to argue with polynomial reduction.
Since $\textsf{P} \subseteq \textsf{NP}, \textsf{coNP} \subseteq \textsf{PSPACE}$, under the assummption that there is a $\textsf{PSPACE}$-hard problem solvable in polynomial time (i.e. it is in $\mathsf{P}$), you also have $\textsf{PSPACE} \subseteq \mathsf{P}$. Now $\textsf{NP}, \textsf{coNP}, \textsf{PSPACE}$ are sandwiched in $\mathsf{P}$ and thus, equality holds for the $\subseteq$ relations above.


Optimal prefix-free binary code with several codewords already assigned The classic Huffman algorithm, as Wikipedia states, finds an optimal prefix-free binary code with minimum expected codewords length, given a set of symbols and their weights. Now, suppose codewords for some (but not all) symbols are already assigned (maybe in a suboptimal way). How should we assign remaining codewords to the remaining symbols so as to minimize the minimum expected codewords length, assuming that there exists at least one binary sequence such that none existing codewords have it as their prefix, and neither of the existing codewords is its prefix?

"Ordinary" Huffman is suboptimal

Let's call a symbol "free" if it has not yet been assigned any codeword.  Here's an easy counterexample to the optimality of running the ordinary Huffman algorithm on the set of free symbols:

Suppose we have three symbols $a, b, c$, with frequencies $0.5, 0.25, 0.25$, of which $b$ and $c$ are free; $a$ has already been assigned the codeword $00$.  Then the unique minimum-size tree in which $b$ and $c$ -- the lowest-frequency free symbols -- are siblings is

  /\
 / /\
a b  c

with expected codeword length $0.5*2 + 0.25*2 + 0.25*2 = 2$, which is strictly greater than that of either of the two trees in which they are not siblings:

  /\        /\
 /\ c      /\ b
a  b      a  c

which each have expected codeword length $0.5*2 + 0.25*2 + 0.25*1 = 1.75$.


Language containing all unambiguous grammars Suppose $L$ is the language of the unambiguous grammars. That is, a sentence $w\in{}L$ if it is a string that describes an unambiguous context-free grammar.

Considering that deciding whether a context-free grammar is ambiguous is non-decidable, would it be correct to say that $L$ exists but is not recursively enumerable?

The language $L$ clearly exists — you just defined it!

It’s not hard to check that your language is co-r.e., that is, you can enumerate ambiguous grammars. Since it’s not recursive, it cannot be r.e.


*non-uniform* $ACC^0$ and above classes $NEXP$ smallest class above $ACC^0$ that we know is separated from $ACC^0$.

We do not know if either $NP$ or $P/poly$ is in $ACC^0$.

Suppose every problem in $NP$ can be solved in polynomial time with polynomial sized advice string (that is $NP\subseteq P/poly$ holds) however the circuit that computes it needs only $ACC^0$ type structure?

Would that mean $NP$ is in non-uniform $ACC^0$ or uniform $ACC^0$?

It would imply that NP is in non-uniform ACC0. While in some circumstances non-uniformity can be removed, this one doesn't seem to be one of them, though you never know...


General approach to randomized algorithm for equality problem Using randomized approach we can guarantee that the equality problem has O(1) complexity (in communication).
With other definitions of of equality (not strictly equal), is there a general approach to design a randomized algorithm with bounded error? Or how to determine if there is no way such an algorithm can be designed?

Suppose that the inputs are $x,y \in \{0,1\}^n$.

Consider the following protocol:

The parties decide on a random string $z \in \{1,2\}^n$.
Alice sends Bob $\alpha = \sum_{i=1}^n x_i z_i \pmod{3}$, and Bob sends Alice $\beta = \sum_{i=1}^n y_i z_i \pmod{3}$.
The parties compute $\gamma = \alpha - \beta \pmod{3}$.

Suppose that the Hamming distance between $x$ and $y$ is $d$. Then $\gamma$ is the sum of $d$ random values in $\{1,2\}$. Using linear algebra, we can calculate
$$ \Pr[\gamma = 0] = \frac{1}{3} + \frac{2}{3} \left(-\frac{1}{2}\right)^d.$$
(You can also prove this formula by induction.)

In particular, when $d=0$ the probability is $1$, when $d=1$ the probability is $0$, and otherwise the probability is in the range $[1/4,1/2]$ (corresponding to $n=3$ and $n=2$, respectively).

The suggests a protocol of the following form:

The parties decide on $N$ random strings $z_1,\ldots,z_N \in \{1,2\}^n$.
Alice sends Bob $\alpha_j = \sum_{i=1}^n x_i z_{j,i} \pmod{3}$ and Bob sends Alice $\beta_j = \sum_{i=1}^n y_i z_{j,i} \pmod{3}$, for $1 \leq j \leq N$.
The parties compute $\gamma_j = \alpha_j - \beta_j \pmod{3}$ for $1 \leq j \leq N$.
If all $\gamma_j$ are zero or all are non-zero, output "Hamming distance is probably at most 1", otherwise output "Hamming distance is definitely more than 1".

As in the case of equality, this protocol has only one-sided error: whenever the algorithm outputs "Hamming distance is more than 1", it is always correct. It remains to determine the connection between $N$ and the error probability $\epsilon$. Let $p = \Pr[\gamma = 0]$. If $p \neq 0,1$, the probability that the algorithm outputs the incorrect answer is
$$
p^N + (1-p)^N \leq (1/2)^N + (3/4)^N.
$$
This shows that $\epsilon$ is exponentially small in $N$, and so in order to guarantee an error probability of $\epsilon > 0$, it suffices to take $N = O(\log(1/\epsilon))$.


Is this method of proving non-regularity is equivalent to pumping lemma? I find it really difficult to prove non-regularity of a language using pumping lemma. I do understand that regular language is the language that can be expressed using DFA/RE. So if I can't create DFA/RE for language can I use that as proof of it's non regularity?

For example, following is an attempt to create a DFA for
0^P
where p is prime number.

Following machine accepts 2,3,5,7 which are primes. But it also accepts those which are not primes. Can it be considered as proof of non regularity of said language?

Here is how your method of proof works on the (regular) language $\{0^2,0^3,0^5,0^7\}$. I tried to construct a DFA for this language – the DFA accepting all strings, but while it accepts $0^2,0^3,0^5,0^7$, it also accepts other strings. What when wrong?

To prove that a language is not regular, we have to show that it is impossible to construct a DFA for it. Having tried and failed is not enough – maybe it's just difficult? For example, people believe that P$\neq$NP, but so far we haven't been able to prove this. Does this show that P=NP?

How, then, can we show that a language is not regular? One way is to construct the "canonical" DFA, and this leads to the Myhill–Nerode criterion (look it up). This method is complete in the sense that if a language is not regular, then you can prove this using this method.

Another technique is the pumping lemma, which is popular for historical reasons. The pumping lemma is not complete: there are irregular languages which satisfy the conditions of the pumping lemma, and so the pumping lemma cannot be used to prove that they are not regular.

There are other techniques as well, for example using closure properties of regular languages, or using structure theorems. Your specific language is a unary language (a language over an alphabet with size 1), and we have a complete structure theorem for these languages, which can be used to show that your language is not regular.


Complexity of dynamic card game algorithm Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red card drawn, we get 1 dollar and lose 1 dollar for every black card drawn. The problem consists in finding an algorithm which returns the expected value of the game. If we denote by $b$ and $r$, respectively, the number of black and red cards left in the deck at any time, the expected value of the game $E(b,r)$ satisfies:

$$E(b,r)=\max\left\{b-r,\frac{b}{b+r}\,E(b-1,r)+\frac{r}{b+r}\,E(b,r-1)\right\}\,,$$

with boundary conditions $E(0,r)=0$ and $E(b,0)=b$. The expected value of the game is therefore given by $E(26,26)$.

My question is, if we implement the recursive algorithm associated with the above formula, how can we determine its complexity? Using the trivial cases of $E(1,1)$ and $E(2,2)$, it would appear that we are dealing with exponential complexity, but is there a way to prove this properly, and if so, what is the number of necessary operations to compute $E(n,n)$ for an arbitrarily large integer $n$? Any ideas or references to literature would be greatly appreciated.

As pointed out in the comments, your recurrence is wrong (though equivalent for $b=r$; it's a recurrence for $E(b,r)+b-r$). Also, you can solve this efficiently using memoization or its more principled cousin, dynamic programming. The dynamic programming solution calculates iteratively $E(i,j)$ for $i+j=0,1,\ldots,52$.

Finally, to answer your question, if you implement you original solution, you get a running time satisfying the recurrence
$$
T(b,r) = C + T(b-1,r) + T(b,r-1),
$$
with initial conditions $T(b,0) = O(1)$, $T(0,r) = O(1)$. If $T'(b,r) = T(b,r)-C$ then
$$
T'(b,r) = T'(b-1,r) + T'(b,r-1),
$$
a recurrence solved by $\alpha \binom{b+r}{r}$. Taking the initial conditions into account, we get that
$$
T(b,r) = \Theta\left(\binom{b+r}{r}\right).
$$
In particular,
$$
T(n,n) = \Theta\left(\binom{2n}{n}\right) = \Theta\left(\frac{4^n}{\sqrt{n}}\right).
$$
(This assumes all arithmetic is $O(1)$. The running time is actually somewhat larger since the relevant numbers grow fast, but this is a (multiplicative) lower-order factor.)


Comparing Selection, Insertion, and Bubble Sorts for database application Explain and compare selection, insertion and bubble sorts. Assume
that your application (say a data base application) deals with
large records where comparisons are performed by means of integer keys.
Assume also that your application requires a stable sorting method,
i.e. a method that does not change the relative ordering of elements
that are equal. Which of these sorting methods would you choose,
and why? (Hint: consider sorting based on the following integer keys
19, 14(1), 7, 12, 14(2), 10).

This is a question I'm studying in class, not sure which is the right one and why.

A "database" that isn't ashamed of calling itself "database" will have hundreds of thousands or millions of records. Any algorithm where the number of operations is quadratic except for special cases is totally unsuitable. So the answer is "none of the above".

You'd do some serious measuring to decide whether to just create an in-memory index (that means you don't sort anything at all, but you just record #1 = 7 at record 3, #2 = 10 at record 6, ...), or use merge sort or Quicksort. Quicksort only if you have a backup, in case there's a problem during the sort.


Is best case complexity big Omega of worst case complexity? I need to prove or disprove the following claim:

Given that the best case complexity of the algorithm A is $O(f(n))$ and the worst case complexity of A is $Ω(g(n))$, it follows that $f(n) ∈ Ω(g(n))$.

I know that obviously $A_b \leq A_w$.
I can also conclude obviously that for constants $c_1 , c_2$ and for all $n_0 \leq n$ for some $n_0$ the following happens:
$A_b \leq c_1f(n)$ and $A_w \leq c_2g(n)$.
I can see that it doesn't mean that $f(n) \geq cg(n)$ for some constant $c$ but I am having trouble disproving it.
Any help will be welcomed.

Consider the following algorithm $A$:

If the input consists entirely of zeroes, return.
Otherwise, count from $1$ to $n^2$, where $n$ is the length of the input.

The best case complexity of this algorithm is $O(n)$, and the worst-case complexity of this algorithm is $\Omega(n^2)$. Does $n = \Omega(n^2)$ hold?


DFS - Proof of Correctness I'm currently studying the book "Introduction to Algorithms - Cormen". Although a proof of correctness for the BFS algorithm is given, there isn't one any for the DFS in the book. So I was courious about how it can be shown that DFS visits all the nodes.
I also googled for it. But it seems that every lecturer do some copy-paste work from this book in their pdf's, so I couldn't find anything useful.
By DFS we had to show that it found the shortest path. But since DFS does not calculate something like that I have no idea how to prove it.

Off the topic, why are those proofs so important? Throughout the book there are so many lemmas and theorems which can be really boring sometimes. I understand how an algorithm works in 10 minutes, perhaps need another 5 to 10 minutes to understand how to analyse the running time, but then I'm loosing 1 hour just for some useless lemmas. Besides, and worse even, I studied almost 50 proofs/lemmas of different algorithms till now, I never managed to solve one of them by myself. How can I gain the "proving ability"? Is there a systematical way to learn that? I don't mean the Hoare logic way with invariants, rather the informal way described in the book "Introduction to Algorithms". Is there any book which focuses on "how to prove algorithms" and show that in a systematical, introductory way ?

I had the same problem when I was an undergrad. I can see you understand the algorithm. And, to prove that it works is to explain it formally that it works.

Why we have many proofs ? because we may have algorithms that are not correct, and we need to show that our algorithm is correct and actually work always!.

Same for the analysis. If we want to prove for example that our algorithm is better than others, then we prove it. You may tell me that we can implement our algorithm and and test it, but this does not consider all the possible cases of input. Therefore, what we do is to prove it.

(We usually prove the correctness and complexity of an algorithm (which is a measure of its performance)).

This is just an answer for your second question. For your first question, a hint is to say why we will visit every other vertex if the graph is connected. [Hint: because the graph is connected than for every pair of vertices there is a path.] ...(back to your second question).. if you note here that I am using one fact to prove my original fact (i.e., there is a path connecting every pair of nodes --> DFS is correct). The first fact is clear in our case given the definition of connectivity. In many other cases, it is not clear. So we will need to prove one fact by proving another, and perhaps do that again and again. This is why we have a lot of lemmas and theorems.

They are boring now. but once you see their magic, you will love them ! As a fun excercise try to solve simple algorithmic problems and prove their correctness and analyses. To verify your answers, re-read your answers. If they convince you, then you are correct. If not, then re-do it again.


What formal representation is commonly used to describe compiler optimizations? I have devised a compiler optimization that works on any structured language that has arrays assignments array[index] = value and counted loops (for i = n; i < N; i++) {doTHIS} (*).

Now I want to represent this optimization using some formal semantics. Since I want to publish my results in a Programming Languages venue, I would like to know:

What formal(s) representation(s) is (are) most commonly used to describe compiler optimizations?

I have already described my optimization using operational semantics, but I'm currently reviewing this choice. Hence, I came to the community for advice.

(*) Please forgive this C-like representation in a question asking for formal semantics.

There are many compilers, which compile widely different kinds of languages which serve widely different purposes. For example, a database language will have very different optimizations than an array-based language like APL.

Compilers themselves use several intermediate languages, from the input language, to a de-sugared version of the input language, all the way down to "fancy" assembly-like versions. You might check here to get an idea of the intermediate languages involved.

Optimizations happen at each of these stages. In general it only makes sense to state optimizations in terms of a formal execution semantics of the language in question: an optimization must preserve the observational semantics, aka the result of the computation. Ideally you would use the semantics to say something about the execution time as well: typically the number of abstract reduction steps would get lower (in certain cases) after application of the optimization.

Pragmatically, many optimizations of imperative-style languages happen on an intermediate language that looks a lot like LLVM IR. Characteristics include SSA form (no variable repeated in the left-hand-side of an assignment) and three address code (at most one assignment, and one operation per statement).

The function calls, thunks, memory layout and semantics of things like pointers are going to tend to be specific to your language.