Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best first algorithm.

Edit: I've discovered a related question which can be referenced here:  https://stackoverflow.com/questions/10374357/why-use-dijkstras-algorithm-instead-of-best-cheapest-first-search

The statements are as follows:

•   “…lowest-cost-first search is typically
exponential in both space and time.  It
generates all paths from the start that have
a cost less than the cost of a solution.”
(Poole, 2nd ed., Section 3.5.4, last
sentence)

•   Dijkstra’s algorithm runs in time O(V^2)
(Cormen, et. al., Ch. 24)

•   Lowest-cost-first search is Dijkstra’s
algorithm where you terminate the search
after you have found the shortest distance to
the goal node.

These statements seem contradictory.
How do you resolve the contradictions?

I'm a bit confused about how to approach this question.

From what I've gathered, the answer may have to do with the fact that lowest-cost-first search is said to be an uninformed search strategy whereas, Dijkstra's is said to be an informed search strategy but I don't fully understand the implication.

The first statement confuses me the most, the part that says that:

"It (lowest cost first) generates all paths
from the start that have a cost less than the
cost of a solution"

My guess is that this statement refers to bounded arc costs which the same text further elaborates on by stating:

If the costs of the arcs are all greater than
a positive constant (bounded arc costs) and
the branching factor is finite, the lowest-
cost-first search is guaranteed to find an
optimal solution – a solution with lowest
path cost

and

The bounded arc cost is used to guarantee the
lowest-cost search will find a solution, when
one exists, in graphs with finite branching
factor. Without such a bound there can be
infinite paths with a finite cost.

However this is difficult for me to understand as I am still very much a novice student.  If anyone could help explain this I would be eternally grateful, thank you.

Imagine you're playing a game, and are currently at state $S_{0}$. In order to win, you must reach the state $S_{finish}$.

In every turn, you can do one of $c$ moves. Your goal is to reach $S_{finish}$ in as little moves as possible; in other words, every move has a cost $1$.

To find the optimal path $P = \{S_{0}, S_1, S_2 \dots S_{finish}\} $, would be finding the set of moves $c_1 \dots c_n$ so that $P$ is minimum.

So what would a lower cost first algorithm do? the same thing a $BFS$ would do; in each turn $i$, search $S_i^1...S_i^c$ possible states that can be reached from the previous state $S_{i-1}$.

so, searching $n$ times, how many moves have you effectively searched?

$1$ in turn 1

$c + 1$ in turn 2

$c*c + c+1$ in turn 3

$=\sum_{i=0}^{n-1} c^i$ in turn $n$, which is exponential in $n$.

But its also exponential in terms of space. To search all the next states $S_{i+1}$, you must keep all your current states $S_i$ in your memory.

How many states $S_i$ are there? $c^i$ as shown above.

When your professor mentioned Dijkstra is polynomial in $V$, he meant on input size that is $V,E=n, O(n^2)$ respectively. However, when searching the optimal path to some wanted state, like in chess, the number of states (or $V$ essentially, if we suppose a state is a vertex), grows exponentially.


Prove or disprove if L is CFL? Given $L=\{a^ib^jc^k | i\neq j \space and \space j=k\}$.
Is this CFL? How do I write CFG for it or prove it with pumping lemma?
Thanks.

Suppose that $L$ were context-free. According to Ogden's lemma, there is a constant $p$ such that each word in $L$ with at least $p$ marked positions satisfies the constraints of the lemma. Consider the word $s = \underline{a^p}b^{p+p!}c^{p+p!}$, in which the underlined part is marked. According to Ogden's lemma, there is a decomposition $s = uvwxy$ in which $vx$ contains at least one $a$, and $uv^iwx^iy \in L$ for all $i \geq 0$. We now consider several cases:

$x$ contains $b$s but not $c$s, or $c$s but not $b$s. Choosing $i = 0$, we obtain a word in which the number of $b$s differs from the number of $c$s, and so does not belong to $L$.
$x$ contains both $b$s and $c$s. Choosing $i = 2$, we obtain a word not belonging to $a^*b^*c^*$, and so not belonging to $L$.
$x$ contains no $b$s nor $c$s, and $v \notin a^*$. In this case $x = \epsilon$, and so $v$ must contain at least two different characters. Choosing $i = 2$, we again obtain a word not belonging to $a^*b^*c^*$, and so not belonging to $L$.
$vx \in a^+$, say $vx = a^q$. Let $i = p!/q+1$. Then $uv^iwx^iy = a^{p+p!}b^{p+p!}c^{p+p!} \notin L$.

We have obtained a contradiction, and so $L$ is not context-free.


Algorithm to generate self-avoiding random walk on a lattice Where can I find some code to generate random self-avoiding walks on 2 and 3-dimensional lattices whose side-lengths are powers of two? The walk should pass through every point on the lattice More specifically, how can I find a random hamiltonian path on a large $2^n \times 2^n$ or $2^n \times 2^n \times 2^n$ grid graph?

The distribution doesn't have to be completely uniform, however in general the lattice should look wrinkled. The method used to generate the path should have low probability of producing extremely long stretches of straight line.

A procedure is described in A combinatorial algorithm for effective generation of long maximally compact lattice chains.


The subset sum problem is not in P because the question is about lossy compressed data? Why not? Where is there a gap or error in my reasoning?
The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1).
The compression algorithm in brief:

check if the size of the set r +1 is a power of two. If not, terminate compression
check all combinations without repetition of size log2(r+1) if any of them can be decompressed (summing all possible subsets without empty subset) to the set r of numbers. If so, return the combination
if no suitable combination is found, terminate compression.

The subset sum problem is to check whether the set r of numbers (that is, the set of sums of subsets of the set n of numbers) contains the number you are looking for. To do this, you can represent the set r of numbers as an array and search it. Searching the array in the worst case requires checking each element, which is O(r) (for a decompressed set) or O(2^n) (for a compressed set). Faster ways such as binary search are known, but they require knowledge of the ordering of numbers, so that by checking one number we also gain knowledge of where to look for other numbers. Without knowing anything about the ordering of the numbers in the array, you can't search the array faster than linearly, because by checking the numbers one by one, you don't get any knowledge of where the number you're looking for might be.
Does the compressed set of n numbers have information about the ordering of the array of r numbers? No.
The number of possible orderings of a set r of numbers is r!, or ((2^n)-1)!, which is a number greater than n! Pigeonhole principle says that if we have 'a' objects that we put into b drawers and a > b then there must be at least one drawer where there will be at least two objects. According to this rule, the set of n numbers cannot contain explicit information about the ordering of the elements in the array r of numbers, because many orderings of the array r of numbers can be compressed into the same array of n numbers, with the same elements and their ordering, and we do not get any other information besides this set. The ways to generate combinations in the compression algorithm are many, by which we can consider that every ordering of an array r of numbers can be compressed into every possible ordering of a set of n numbers.
If the subset sum problem is in P, then there exists a search algorithm that will answer the subset sum problem in polynomial time calculated from the size of the compressed set of n numbers. From this, we can conclude that to find a number in an array r of numbers in faster than linear time, it is sufficient to subject the array to lossy compression rather than sorting. When we subject the sorted array r of numbers to compression, we retain the ability to search it in faster-than-linear time, despite the fact that the compression was lossy and as a result, we lost ordering knowledge and most of the content knowledge. The data can be reconstructed, but only by generating the sums of every possible subset and sorting them, since we know from principle pigeonhole that the original ordering knowledge has been lost and must be acquired anew.
Losing knowledge of the ordering of an array r of numbers ( and most of its contents) while still being able to search it in faster than linear time does not make sense, from which it follows that there is no algorithm that allows this, which means that the subset sum problem is not in P, and since SSP is in NP then P != NP.

The subset sum problem is quite different from your problem: Given a list of integers and a target sum $S$, it asks if there is a subset of the list that sums to $S$. No "compression", lossy or not. Any lossy technique will (by definition) tend to miss the target (because it works with an approximation). And we are looking for an exact solution, not one that is 10% off, it has to be right on.
It looks to me that the collection of subsets for which you need to compute the sums is even larger than the numbers in the original list. If so, it isn't any speedup.


How does the Sutherland-Hodgman Algorithm work? The following are the Pages-96 and Page-97 of the book Schaum's outline series of Computer Graphics.

The algorithm considers several things:

(1) Whether the polygon is Convex or Concave.

(2) Whether the polygon is positively or negatively oriented.

(3) And, finally, testing polygon edges against the edges of the clipping window.

Consider the WXYZ as the clipping rectangle in the following picture.

I have several questions:

(1) Do I need to test an edge AB against all of the edges of  wxyz or just wx?

(2) Suppose, I test  AB against  wx. According to the Page-97 of the book, I should be testing whether it is on the left or on the right side of the clipping edge. But,in this case, there are no lefts or rights. There are aboves and bellows. How can I determine whether it is inside or outside?

(3) How can I keep track of the Inside and Outside? For example, Consider the polygon edge BC. If I test it against ZW, it is on the Right side and Inside the Clipping Region. If I test it against YX, it is on the Left side and Inside the Clipping Region. It turns out to me that, it is actually not possible to find the position of a point with respect to the clipping region unless we consider the region at once and as a whole. Then why is the book testing points against one line at a time?

(4) Consider the edge DE. Is it going out or coming in?

As written in book:

  Let edge $E$, determined by endpoints $A$ and $B$, be any edge of the positively oriented, convex clipping polygon.

It means, that first of all you need orient your red rectangle counter-clockwise:

  We clip edge of the polygon in turn against the edge E of the clipping polygon, forming a new polygon. ... The algorithm proceeds in stages by passing each clipped polygon to the next edge of the windows and clipping

I.e.:

Clip green polygon by $\overline{WX}$ (polygon will stay the same);
Clip polygon from step 1 by $\overline{XY}$ (still the same polygon);
Clip polygon from step 2 by $\overline{YZ}$ (yellow part will be cut off, and result of this step will be polygon $ABCKLE$);
Clip polygon from step 3 by $\overline{ZW}$ (blue part will be cut off, and result of this step will be polygon $ABCKLMN$);

Here we can answer on your (1) question - yes, $\overline{AB}$ will be tested against all edges of clipping windows. And answer for question (4): $\overline{DE}$ will not be in resulting polygon, but $\overline{LM}$ (everything that lefts from $\overline{DE}$) will belong to result.

To address question (2) - we need to have a look at this quote (definition when point is on the left side or on the right side):

  Let $A(x_1,y_1)$ and $B(x_2,y_2)$ be the endpoints of a directed line segment. A point $P(x, y)$ will be to the left of line segment if the expression $C=(x_2-x_1)(y-y_1)-(y_2-y_1)(x-x_1)$ is positive.

$\overline{WX}$ is directed line segment and points $A$ and $B$ is on the left side, then whole $\overline{AB}$ edge is to the left of the line segment (cliping edge) $\overline{WX}$.

Question (3): again due to edge of clipping windows is directed $\overline{BC}$ really on the left side of $\overline{XY}$, $\overline{ZW}$ (also it's to the left of $\overline{YZ}$ and $\overline{WX}$).

I think, the cause of the questions that you forget to orient clipping rectangle.


Enumeration of BPP machines Can we enumerate all probabilistic Turing machines (with bounded error), like we do for deterministic Turing machines (when using diagonalization arguments against deterministic Turing machines)? If not, does this mean we cannot diagonalize against BPP machines?

Yes. Enumerate over all pairs $(M,p)$ of probabilistic Turing machines $M$ and polynomials $p$. Interpret each such pair in the following way: on input $x$, run $M$ for $p(|x|)$ steps, and if it doesn't halt, output "yes".


What is the time and space complexity of Rete algorithm I am working on pattern matching algorithm. Its working and using very less memory. For the comparison, I have to compare it with the Rete Algorithm. I have checked it in the thesis of the author, some of his paper and he has provided some complexities which are not based on then, nor does its efficiency is provided in the space complexity.

My algorithm despite large inputs worst case is $O(n^2)$. Can someone point me to a good reference where I can find its complexity? I have been searching for a while now, and I did not even get the pseudo code. Things not to consider in order to save your time is algorithms, software, expert systems based on Rete algorithm e.g. Jess etc.
reference link for algorithm thesis pdf  Click to download

citation of the paper "Forgy, C.L., 1982. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artificial intelligence, 19(1), pp.17-37."

finally i found what was needed, thought i wil share here for others who might need it.
http://reports-archive.adm.cs.cmu.edu/anon/1995/CMU-CS-95-113.pdf


Find a maximum matching in linear time I need to describe an algorithm that finds a maximum matching in a given undirected and unweighted graph. The runtime needs to be linear and is a 2-approximation, that is, the matching size (number of edges) should differ from a maximum matching size not more than a factor of two.

The problem I have is coming up with a linear-time algorithm. I know how to find a maximum matching, but this takes polynomial time.

$M\gets\emptyset$
While $E\neq\emptyset$ do

select $(u,v)\in E$
$M \gets M \cup \{(u,v)\}$
delete all edges incident to $u$ and $v$

Return $M$

The above algorithm runs in $O(m+n)$ time if we store $G=(V,E)$ using adjacency list.

Now we prove this algorithm is 2-approximation. Let OPT be the maximum matching. For each edge $e\in$ OPT, there must exist $e'\in M$ s.t. $|e\cap e'|\in\{1,2\}$, i.e. $e$ and $e'$ share one or two common vertex. Moreover, at most two different edges of OPT are incident to the same edge of $M$.

Now we divide OPT into two disjoint subsets OPT$_1$ and OPT$_2$. In OPT$_1$, no two edges are incident to the same edge in $M$. In other words, $M$ has a subset $M_1$ s.t. OPT$_1$ and $M_1$ are one-to-one, which implies $|OPT_1|=|M_1|$. We can pair all edges in OPT$_2$ s.t. different pairt of edges in $OPT_2$ are mapped to different edges in $M_2\subseteq M$. It's easy to show that $M_1\cap M_2=\emptyset$ and $M_1\cup M_2 = M$.

We have $|M|=|M_1|+|M_2|$ and $|OPT|=|OPT_1|+|OPT_2|=|M_1|+2|M_2|$. Therefore, $2|M|\geq|OPT|$.

Edited on Jan. 15, 2020:

The following is a simpler argument. For every matching $M$, we have $2\#edges(M)=\#vertices(M)$. For each $e=(u,v)$ in the maximum matching $M^*$, at least one of $u$ and $v$ appears in a maximal matching $M$. Otherwise, $M$ isn't maximal. Hence,
$2\#edges(M)=\#vertices(M)\geq\#edges(M^*)$.


Why is linear programming in P but integer programming NP-hard? Linear programming (LP) is in P and integer programming (IP) is NP-hard. But since computers can only manipulate numbers with finite precision, in practice a computer is using integers for linear programming. Because of this, shouldn't LP and IP be in the same complexity class?

The short answer: because you can use Integers to simulate Booleans for SAT, but when you don't restrict yourself to this, then you can't actually simulate SAT. You'll get a feasible answer, but it no longer carries any meaning in terms of whatever SAT instance you were trying to simulate.

The tough answer to this is that we don't know that they aren't in the same complexity class. Nobody has a proof that $P \neq NP$. If we understood the deeper reasons why the problems were so different, that would require that we understood why the complexity classes were different, which we don't.


What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$? If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(n)\subseteq DTIME(O(f(n)))$?

I'm not 100% sure on this, but I believe that the best known bound on this comes from the construction used for the best known bound on creating oblivious Turing machines. See this Gödel's Lost Letter blog post on the relationship between circuit size and oblivious Turing machines, and in particular the "Open Problems" section.

Given an arbitrary deterministic Turing machine that runs in time $T(n)$, it is known how to construct an oblivious deterministic Turing machine that accepts the same language in time $O(T(n) \log T(n))$. I believe that this implies $\operatorname{NTIME}(t) \subseteq \operatorname{DTIME}(t^{2d} \log t)$, where $d$ is the CIRCUIT-SAT exponent from the question (the 2 coming from the fact that you wrote $(nm)^d$ instead of $(n + m)^d$). However, I have not verified the details myself.


Minimisatiom using Myhill-Nerode Theorem I have recently studied the Myhill–Nerode theorem and while applying it to minimize these FSMs, I encountered a problem. Is it always the case that the final states should be grouped together because they are indistinguishable?

In the first FSM below, if I group states (q3,q4) on 0, q3 reaches q4 and q4 reaches q4, but on 1 both behave differently as q4 has no transition on 1.

Same trouble with the second FSM.

I want to understand how to group together the states while using the theorem.

In the first automaton, you can see that every accepting state has a transition with 0 to an accepting state, while a transition with 1 goes to either a sink or is just non-existing. But this means that reading a 1 from an accepting state leads always to rejecting the input. Thus, all accepting states are equivalent.

In the second automaton, you can see that $q_2$ has a 0-transition to $q_5$, a non-accepting state, while the other two accepting states have 0-transitions to accepting states. Thus, $q_2$ cannot be equivalent to both $q_4$, and $q_3$. Moreover, $q_3$ and $q_4$ cannot be equivalent because reading 00 from both states leads to different behavior (one run is accepting, th other rejecting). Thus, in this case you cannot merge any of the accepting states.


Algorithm for display nodes of a particular node based on in-degree and out-degree Suppose we have following directed graph. When I click on say node $e$, it should make in-degree and out-degree of node $e$ and connected nodes red. As shown in Resulting Graph. My purpose is, when I click on any node of a directed graph it should tell me what nodes it is influencing(out-degree) and what are nodes which influenced it (in-degree).
I want to make an algorithm for it. I don't know how to make it.

Definition: For a directed graph $G=(V(G), E(G))$ and a vertex $x_1 \in V(G)$, the
Out-Degree of $x_1$ refers to the number of arcs incident from $x_1$. That is, the number of arcs directed away from the vertex $x_1$. The
In-Degree of $x_1$ refers to the number of arcs incident to $x_1$. That is, the number of arcs directed towards the vertex $x_1$.
From mathonline.wikidot.com:

Expected Result:

I want to make mathematical modeling for following pseudo code:

Click on node i (e in example).

look for in-degree relationship r and get nodes(node d in below example).

look for out-degree relationship r and get nodes (node b and f in example).

display the nodes visited    through relationship r including e (expected
result graph).

If you want to highlight the neighbors:
Use adjacency list representation, where each node has a list of all out-edges out of it, and a list of all in-edges into it.  Then given a node you can rapidly identify what to highlight.
If you want to highlight everything connected to that node (at any distance):
Use DFS to find the set of nodes that are reachable from it.


Why does Skiena reserve space for n+1 adjacency lists? I am reading up on graph theory from the book Algorithm Design Manual - Skiena. And he shows a structure of a graph as follows :

#define MAXV        100     /* maximum number of vertices */
#define MAXDEGREE   50      /* maximum outdegree of a vertex */

typedef struct {
    int v;              /* neighboring vertex */
    int weight;         /* edge weight */
} edge;

typedef struct {
    edge edges[MAXV+1][MAXDEGREE];  /* adjacency info */
    int degree[MAXV+1];     /* outdegree of each vertex */
    int nvertices;          /* number of vertices in the graph */
    int nedges;         /* number of edges in the graph */
} graph;

I am confused about why the size of adjacency list or the degree is MAXV+1. Is it to handle edges that begin and end in the same vertex E(v,v) ?

Note that the author uses 1 instead of 0 as the starting point of an array $A$. In other words, $A[0]$ is wasted. For example, to initialize a graph:

for (i=1; i<=MAXV; i++) g->degree[i] = 0;

By the way, in the second edition of this book, it is (Section 5.2):

#define MAXV 1000            /* maximum number of vertices*/

typedef struct {
  int y;                    /* adjacency info */
  int weight;               /* edge weight, if any */
  struct edgenode *next;    /* next edge in list */
} edgenode;

typedef struct {
  edgenode *edges[MAXV+1]; /* adjacency info */
  int degree[MAXV+1];      /* outdegree of each vertex */
  int nvertices;           /* number of vertices in graph */
  int nedges;              /* number of edges in graph */
  bool directed;           /* is the graph directed? */
} graph;


Float number to binary I would like to convert 0,347 and 0,9828 to binary, how can I do that?

I know that sucessive multiplication by 2 can do this, but this method seems very painful and even ineffective since the size of count.

This is for a question, and I think that sucessive multiplication is needed. But, in 0,347, I did more than 20 multiplication and did not reach result. Is this normal?

If I understand your question correctly, you want to determine the binary representation of a floating-point number by hand. I assume you are talking about the IEEE 754 floating-point format, since this is the most common format.

You can indeed do this by successively multiplying with 2. However, just multiplying does not result in anything useful, you should also subtract one (1) every time the intermediate result is greater than or equal to 1. To understand this, you must understand how floating-point numbers are stored. This is explained pretty well on Wikipedia (and probably many other sources), including the algorithm you mean (see here).

To do this by hand is quite painful indeed. It's normal that you have to do more than 20 multiplications. You first need a few multiplications to normalize the number and determine the exponent (i.e. scale the number such that it has the form 1.xxxxx * 2^exponent). After that, each multiplication yields exactly one bit of the mantissa. A single-precision floating-point number has a 23-bit mantissa, so to convert the number 0.347 to single-precision floating-point, you need to do 25 multiplications. A double-precision floating-point has a 52-bit mantissa, so you'll need 54 multiplications!

NB: For sake of simplicity, I did not take into account numbers larger than 1, negative numbers, special numbers (such as NaN, +/- infinity, denormal numbers, etc.) and other aspects such as rounding. These cases seem to be out of the scope of your question.


What's better for an algorithm complexity, O(log n) or amortized O(log n)? Some context: I'm to write a program that sorts the lines of a file in C for Linux. Since I have to read all lines of the file (fgets() for example) I'm thinking about inserting them in a tree like structure in a sorted manner using the so called tree sort algorithm.

Looking for a self-balancing tree structure I came across two that may be interesting, the red-black tree and a splay tree. According to Wikipedia the red-black tree has an O(log n) worst case and the splay tree has amortized O(log n).

The actual question: I know how to roughly compare some complexity levels in O notation but what's that amortized time? Given two algorithms one that runs in O(log n) and the other in amortized O(log n) which one would be preferrable?

$O(\log n)$ in the worst case implies $O(\lg n)$ amortized.

Basically, given two data structures supporting the same operator, one in $O(\lg n)$ time in the worst case and the other one in $O(\lg n)$ amortized time, the first one is considered to be superior asymptotically: being $O(\lg n)$ time in the worst case means that each call of the operator will be supported in this time, while having an amortized complexity of $O(\lg n)$ means that some (very few) operator calls can take $O(n)$ time. Usually, the concept of amortized analysis is used for data-structures which amortized complexity is better than their worst case complexity.

As an illustration, consider a data-structure for integers, storing each such integer $x$ as a string of bits (e.g. $x=8$ represented by $(1,0,0,0)$), and the operator $x.inc()$ which increments $x$ by $1$.

In the worst case (e.g. on $x=7$ represented by $(1,1,1)$), the operator $x.inc()$ corresponds to $\log(x)+1$ binary write (e.g. to write $(1,0,0,0)$ corresponding to $8$).
In the best case (e.g. on $x=8$), the operator $x.inc()$ corresponds to exactly one binary write (e.g. to change the last bit of $(1,0,0,0)$ to $1$, giving $(1,0,0,1)$).

In a sequence of increments of the same integer object (e.g. enumerating all integers from $0$), the "best case" described above happens half of the time, and the worst case one every $n$ increment (i.e. after $1,2,4,8,16,...$ increments). A case requiring $i$ bits write happens $1/2^i$ of the time. Summing all those costs gives an amortized cost of $\sum_i i/2^i \in O(1)$. Hence the operator $inc()$ has a worst case complexity of $O(\lg n)$ but an amortized complexity of $O(1)$.

The notion of amortized analysis is well explained on wikipedia. You might want to see the page on the Potential method for more details.

Hope it helps!


Oracle query’s required The variables $a,b,c \in \{0,1\}$, thus $a^k, b^k, c^k \in \{0,1\}$

I want to pass a query to an oracle that returns the coefficients of each term $(1,a,b,c,ab,ac,bc,abc)$ in the expansion of products such as this one $(1-a+ab)(1-b+bc)(b-bc)$. There could be more variables and more brackets to expand.

Do I require a single FP query to do this or something more?

edit:

Input: $(1-a+ab)(1-b+bc)$

Expand: $a b^2 c - a b^2 - a b c + 2 a b - a + b c - b + 1$

Apply property of idempotence:  $a b c - a b - a b c + 2 a b - a + b c - b + 1$

Simplify: $1 - a - b + ab +bc$

Extract coefficients: \begin{matrix} 1 & 1 \\ a & -1 \\ b & -1 \\ c & 0 \\ ab & 1 \\ ac & 0 \\ bc & 1 \\ abc & 0 \end{matrix}

Question: What is the 'weakest' oracle capable of extracting the coefficients above from the input?

Your problem is #P-hard. Indeed, given a #SAT instance with variables $x_i$ and clauses $C_j$, let $\kappa_{i,b}$ be the product of the clauses $C_j$ satisfied by the truth assignment $x_i=b$, and consider
$$ P = \prod_i (\kappa_{i,0} + \kappa_{i,1}). $$
The coefficient of $\prod_j C_j$ in $P$ is the number of satisfying assignments.

In the other direction, the special case where the input formula is $\Pi\Sigma\Pi$ (that is, the product of polynomials) is #P-complete. Suppose that we are interested in the coefficient of some monomial $m$ in $\prod_k P_k$, where the $P_k$ are polynomials. Substitute zero in all variables not appearing in $m$. Now guess one term from each $P_k$, and accept if the terms together cover $m$.


Understanding A Recursive Definition of CL-Terms in Combinatory Logic From page 26 of Lambda-Calculus and Combinators:

  Definition 2.18 (Abstraction) For every CL-term $M$ and every variable $x$, a CL-term called $[x].M$ is defined by induction on $M$,
  thus:

  (a) $[x].M \equiv \mathbf{K}M$ if $x \notin FV(M)$;

  (b) $[x].x \equiv \mathbf{I}$;

  (c) $[x]Ux \equiv U$ if $x \notin FV(U)$

  (f) $[x]UV \equiv \mathbf{S}([x]U)([x].V)$ if neither (a) nor (c)
  applies.

Here $\mathbf{I}$ is meant to denote the identity operator, $\mathbf{K}$ the constant operator, and $\mathbf{S}$ the "stronger composition operator" where in mathematical notation:

$$
\mathbf{S}(f,g))(x) = f(x, g(x)) \text{ for functions $f$, $g$}
$$

Question: It seems that (f) of this definition just comes out of nowhere. I have no idea what is motivating it behind the scenes. Does anybody have any insight on where this definition comes from?

Here are some considerations that could have been used to sort of "derive" the (f) rule:

it is natural to define our type of conversion recursively;
the general case when the body of "$\lambda$" is an application $(UV)$ needs to be addressed;
we certainly would like to get $[x].([y].([z].xz(yz)))$ converted into  its corresponding combinator $\mathsf{S}$.

Using the above we get an intermediate version of the (f) rule:

$$[x].UV \equiv A([x].U)([x].V),$$ where some closed CL-term $A$ is to be determined. The position of $A$ is chosen so that the subsequent "calls" of the (c) rule would be possible, or all three positions could be tried in turn.

$$\begin{array}
([x].([y].([z].xz(yz)))) &\equiv [x].([y].A([z].xz)([z].yz)) &\text{rule (f)}\\
                       &\equiv [x].([y].(A x) y)           &2 \times \text{rule (c)}\\
                       &\equiv [x].Ax                      &\text{rule (c)}\\
                       &\equiv A                           &\text{rule (c)},
\end{array}$$
hence $A = \mathsf{S}$ and the final version of the (f) rule
$$[x].UV \equiv \mathbf{S}([x].U)([x].V).$$

Note that the above is not a "real derivation", it's just some informal speculations, which I hope can help you to build up some intuition about that conversion.


Intersection of a recognizable language and a decidable language is decidable? I'm having trouble with proving that "Intersection of a recognizable language anda  decidable language is decidable.

I assume this is true although I have no idea how to proof it. Can somebody point me in the right direction?

It's false. Let $L_1=\Sigma^*$ be a decidable language and $L_2=L_{HALT}$ be the (recognizable) language of all halting TM-string pairs. Then $L_1\cap L_2=L_2$, which is not decidable.


Operations on OBDD: negation through Shannon's expansion I have a problem with the application of the Shannon expansion for to obtain the negation of a formula boolean, than will need for implement the negation operator on OBDD (Order Binary Decision Diagram) that is, show that:

$\qquad \displaystyle \neg f(x_1,\ldots,x_n) = (\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1})$

where $f|_{x_i=b}$ is the function boolean in which replaces $x_i$ with b, that is:

$\qquad \displaystyle f|_{x_i=b}(x_1,\ldots,x_n)=f(x_1,\ldots,x_{i-1},b,x_{i+1},\ldots,x_n)$.

The proof says:

$\qquad \displaystyle\neg f(x_1,\ldots,x_n) = \neg((\neg x_1 \wedge f|_{x_1=0}) \vee  (x_1 \wedge f|_{x_1=1}))$.

Applying the negation (skip the intermediate steps), we get:

$\qquad \displaystyle (x_1 \wedge \neg x_1) \vee (\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1}) \vee (\neg f|_{x_1=0} \wedge \neg f|_{x_1=1}) $.

Now $(x_1 \wedge \neg x_1)= \mathrm{false}$ can be dropped, which leads to

$\qquad \displaystyle (\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1}) \vee (\neg f|_{x_1=0} \wedge \neg f|_{x_1=1}) $

which in turn is, finally, equal to

$\qquad \displaystyle (\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1})$.

Why does this hold?

Maybe it is better to understand if you make a truth table for both functions. You can see that if $(\neg f|_{x_1=0} \wedge \neg f|_{x_1=1})$ is true then $(\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1})$ is also true, because both $f$ terms are true and either $x_1$ is true or $\neg x_1$ is true. And if $(\neg f|_{x_1=0} \wedge \neg f|_{x_1=1})$ is false then you have to do a case study:

If both $f$ terms are false then is $(\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1})$ also false
If exactly one $f$ term (w.l.o.g. $\neg f|_{x_1=0}$) is false then it is equivalent to $(x_1 \wedge \neg f|_{x_1=1})$

Therefore, both formulas $(\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1}) \vee (\neg f|_{x_1=0} \wedge \neg f|_{x_1=1})$ and $(\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1})$ are equivalent.


Complexity of determining whether three points are collinear from a set of points Let $S \subseteq \mathbb{R}^2$ be a finite set of points. Do there exists three collinear points $p, q, r \in S$?

I wan't to know the complexity of this decision problem and present my approach as following.

SOLUTIONS. Let $n = |S|$. A naive brute-force takes time $\mathcal{O}(n^3)$. We can simply go through all triplets of points from $S$ and check for collinearity in time $\mathcal{O}(1)$.

I found additionally a $\mathcal{O}(n^2 \log{n})$ solution. For each $p(x_p \mid y_p) \in S$, we consider all points $q(x_q \mid y_q) \in S \setminus \{ p \}$ and compute the slope $m = \left|\frac{\Delta y}{\Delta x}\right| = \left| \frac{y_p - y_q}{x_p - x_q} \right|$ of the (unique) connecting line through $p$ and $q$. Resulting in a list of $n - 1$ slope values, we sort this list in time $\mathcal{O}(n \log {n})$ and use a linear search taking time $\mathcal{O}(n)$ for checking if two elements of the list are identical. If and only if this happens, three points of $S$ are collinear. Since we need time $\mathcal{O}(n \log {n})$ for each of these $n$ points, the whole thing runs in $\mathcal{O}(n^2 \log{n})$.

(Notice: We may assume the points of $S$ to be unique, because a simple preprocessing in time $\mathcal{O}(n \log {n})$ allows use to find duplicates. If $n \ge 3$ and there exists a duplicate, three points are obviously collinear.)

LOWER BOUNDS. A lower bound of $\Omega(n)$ is trivial. But we can do better. Let the set $X = \{ x_1, x_2, \dots, x_n \} \subseteq \mathbb{R}_+^n$ be an instance of the element distinctness problem (EDP). If is well-known, that EDP has a $\Omega(n \log {n})$ lower bound in many computational models (algebraic decision trees for instance). Define $S := \{ (x_1 \mid x_1^2), (x_2 \mid x_2^2), \dots, (x_n \mid x_n^2)  \}$ and consider the following two cases.

Case 1: All elements of $X$ are distinct. Because the points of $S$ lie on the parabola $y = x^2$, there are no three collinear points.

Case 2: There are two indices $i, j \in \{ 1, 2, \dots, n \}$ with $i \neq j$ and $x_i = x_j$. Then, $x_i^2 = x_j^2$. If $n \ge 3$, select an arbitary value $x^* \in X \setminus \{ x_i, x_j \}$. Hence, we found three collinear points: $(x^* \mid (x^{*})^2), (x_i \mid x_i^2)$ and $(x_j \mid x_j^2)$.

By reduction principle, our problems complexity is $\Omega(n \log {n})$. Can  we do better or is this lower bound optimal? Is there an $\mathcal{O}(n \log {n})$ algorithm?

There is an $O(n^2)$ algorithm for the more general problem of minimum area triangle, see for example these lecture notes. The problem itself (as well as minimum area triangle) is 3SUM-hard, as shown in a survey of King on 3SUM-hard problems, where the problem is known as 3-points-on-line.

See also this stackoverflow question, where I found the links given above.


speed, cost and capacity tradoff I'm reading William Stalling's Operating System Design and internals. Talking about memory, the following tradeoff was introduced:

  As might be expected, there is a tradeoff among the three key characteristics
  of memory: namely, capacity, access time, and cost. A variety of technologies are
  used to implement memory systems, and across this spectrum of technologies, the
  following relationships hold:
  • Faster access time, greater cost per bit
  • Greater capacity, smaller cost per bit
  • Greater capacity, slower access speed

Now what exactly makes a faster memory more costly, and why does bigger memory mean slower memory?

Increasing the speed of memory typically involves increasing the size of the bit cell. For example increasing the capacitor size in a DRAM (which using one transistor and one capacitor to store a bit) allows faster reading of the bit but obviously also reduces the number of bit cells that can be fit onto a chip. (Similarly, SRAM is less dense but faster than DRAM.)

From an economic perspective, since speed is generally valued, techniques to increase speed are allowed spend more effort (i.e., cost) in research, design, and manufacture to increase speed.

Aside from the cost factor (users seeking higher capacity will seek lower cost per bit), higher capacity memories are generally slower from a combination of lesser integration and greater distance between a bit cell and the consumer of the data. Greater integration (on the same chip, in the same package, on the same board, in the same system/enclosure) not only reduces physical communication overhead (crossing physical boundaries has overhead) but also interface overhead as less integrated interfaces are typically more generic and less optimized for one specific use.

Indexing overhead is an additional factor making larger memories slower. Hardware effectively traverses a binary tree to select the desired data. (This factor is typically minor, but it seemed worth mentioning.)

Another significant tradeoff in memory system design is access granularity/randomness. Larger access granules and less random access correlate with increased density/lower cost per bit. This is also a result of economic and physical factors.


How to transform a Infinite decimal of $\frac{23}{6}$ into binary? How to transform a decimal of $\frac{23}{6}$  into binary?

$\frac{23}{6}$ is equal to $3.83333\bar{33}$, where the digit $3$s are repeated forever.

I do know how to translate finite decimal into binary, but
is there any procedure to translate such Infinite decimal like $\frac{23}{6}$ into binary?

Any hint is appreciated!

Here is a hint by example.

$\frac{23}6 > 2$
$\frac{23}6-2 = \frac {11}6 > 1$
$\frac{11}6-1 = \frac {5}6 > \frac 12$
$\frac{5}6-\frac12 = \frac {1}3 > \frac 14$
$\frac{1}3-\frac14 = \frac {1}{12} > \frac 1{16}$
$\vdots$

So $\frac{23}6=2+1 +\frac12+\frac14+\frac1{16}+\cdots=(11.1101\cdots)_2$

Exercise. How to determine the period of the fraction part of the binary expansion of $\frac {23}6$?


Neighbourhood in local search metaheuristic I cannot seem to find an answer to this question with Google, so I am  going to ask here: is it required for a good neighbourhood function that it in principle (i. e. by recursively considering all neighbours of a certain solution - which is not practical) can reach all possible solutions?

My question is whether there are references in literature that explicitely state it's a requirement - I can see that it is a good property of a neighbourhood.

I think the property of being able to reach all the successor states from a current state is crucial and needed in order for the problem to be well-defined. If this was not the case, you might miss out on good solutions. Moreover, you might never reach a goal state and hence run forever.

The classic AI book by Russell & Norvig, 3rd edition, page 67 gives a formal definition for a problem. One of the components is a successor function which returns all the successor states for a current state. Together the formal components create a search space, that is the set of all states reachable from the initial state. If one uses a different successor function, namely such that it leaves out some successors, the resulting search space is a different one: goal state(s) might be missing and optimal solutions might very well differ. Perhaps the reason you are unable find it from the literature is that the requirement is obvious.


Sorting elements of linked list I've been looking over sorting algorithms for linked list and here's what I came up with.

As we know, for element access arrays will work better than linked list. Also, there is the benefit of elements being stored in consecutive memory locations: due to spatial locality of cache, arrays give better performance.

Thus for sorting linked list:

Extract all elements from linked list to a array: $O(n)$
Sort the array using quicksort: $\Theta(n \log n)$
Store the elements in linked list: $O(n)$

Is this approach better than other approaches for sorting linked lists such as using merge sort directly, as described on geeksforgeeks.

The downside of your algorithm is that you need to allocate enough space to hold pointers to all the elements in the list. This requires knowing the length of the list (which would need traversing it once to count) and you may not have enough memory to get a contiguous space for it.

A variation of classic merge sort will work a lot better for linked lists:

Have a array of $\lceil \log_2 n \rceil$ linked lists initially empty. (or just fix to size 64 because when are you ever going to need to sort anywhere near $2^{64}$ elements).

For each element in the original list you extract it into a single element list and do the following:

for the first list in the array if a list is already there merge the list into that list and remove the list from the array and repeat for the next list in the array.

otherwise move on to the next element in the original list.

Once you've done the last element of the list you merge the lists in the array starting from the lowest index.

This is the algorithm used for linked lists in the linux kernel. And has a few handy features:

no allocations needed, no recursion, so no chance of an out of memory situation.
you only walk the original list once.
the merge passes except the final ones are all with lists of equal length. This means there are few unbalanced passes which would have more traversing of the longer list than actually merging the two lists together in.


Why S=1, R=1 Is forbidden in RS-Flip Flop I have come across about RS Flip Flop & I have tried implementing that on a simulator & using actual logic gates. But I'm still not sure whether I have correctly understood the case unstable or the forbidden case S=1, R=1 in Flip flop. Can anyone tell me what exactly is that?

By the way I have used 2-INPUT NAND Gates to implement the flip Flop. What is the difference between the NAND Gate Flip Flop & NOR Gate Flip Flop, ?

This question has an accepted answer on another site.

Digest: If you had both inputs set to $1$, both outputs would be $0$ but they are supposed to be complementary.


m-CNF formulas satisfiability approximation I am reviewing for a test, and i am stuck on this question.

the problem is to show it is hard to approximate (for any constant) the following problem:

given m CNF formulas f1,..,fm over variables x1,..,xn find the assignment which maximizes the number of satisfied formulas.

I believe I need to reduce this problem to some kind of graph problem (CSG,IS,CLIQUE), which I know cannot be approximated for any constant. I can't find a way to do this. To what problem do I reduce this to?

thank you.

If such a constant-factor approximation algorithm would exist, and it would run in polynomial-time, you could use it to solve CNF-SAT in polynomial time. Since CNF-SAT is NP-hard, this may give you the desired result.

Sketch:
Given a CNF-formula f, feed sufficiently many copies of the formula to your approximation algorithm. If f is not satisfiable, the algorithm must always output 0. If f is satisfiable,  it should output a number > 0 (at least, if the other numbers are chosen correctly).


When can the coinduction hypothesis be used? We can use the induction hypothesis when we are proving a property for a structure that is well-ordered. I am aware that there is a proof for this.

When it comes to coinduction, I'm confused.

One of the answers to another question "What is coinduction?" mentions that there is a notion of a corecursive definition to be well-formed.

A lot of things I (try to) read related to coinduction mostly talk about bisimulation and equivalence. But to the best of my knowledge, those are trying to prove some relationship for two coinductive data structures. For example, they prove that two streams are equivalent. And the coinductive hypothesis is somehow derived from one of the bisimulation's hypothesis. Even so, I think I'm still lost on the requirements of what constitutes well-formedness in the coinductive world.

I can somehow see that the coinduction hypothesis works when proving those kinds of propositions, but I'm still unclear when they can be used to prove more general propositions such as the one mentioned in What is coinduction?. In that link, the proposition states that "something is infinite". This seems like a more generic form of statement one would be interested in proving.

A possibly related question is whether any proposition can be converted and re-stated as a proposition of equivalence or not.

Is there some simple informal reasoning that talks why co-induction works for some well-formedness requirement?

I'm hoping for an explanation like if possible: https://math.stackexchange.com/questions/432293/well-ordering-and-mathematical-induction/432302#432302.

First, let me recall least and greatest fixed points for $\subseteq$. We are working relative to some set $U$, the universe. In the case of (co)inductive definitions, $U$ is the set of all terms. A function $f:2^U\to2^U$ (from subsets of $U$ to subsets of $U$) is monotone, if $A\subseteq B$ always implies $f(A)\subseteq f(B)$. A fixed point of $f$ is a set $A$ such that $f(A)=A$.

For monotone $f$ there always is a least fixed point $\mu f$, namely the intersection of all $A\subseteq U$ such that $f(A)\subseteq A$. Least means that for arbitrary fixed points $F$ we always have $\mu f\subseteq F$.

For an example, let $f_{\tt nat}$ be defined by $f_{\tt nat}(A)=\{0\}\cup\{n+1\mid n\in A\}$. The function $f_{\tt nat}$ is the one-step closure function under the constructors $0$ and $+1$. The condition $f_{\tt nat}(A)\subseteq A$ means that $A$ is closed under the constructors $0$ and $+1$. The intersection means that the $\mu f_{\tt nat}$ contains only those elements which are in every set closed under the constructors. These happen to be the natural numbers.
The example shows how the inductive definition of natural numbers is the least fixed point of closure under the natural numbers' constructors. Generally, inductively defined sets are least fixed points of closure under constructors.

Dually, for monotone $f$ there also is a greatest fixed point $\nu f$, namely the union of all $A\subseteq U$, such that $f(A)\supseteq A$. Greatest means that for  arbitrary fixed points $F$ we always have $\nu f\supseteq F$. To make the duality complete, let us note that intersection is the $\subseteq$-infimum and union the $\subseteq$-supremum and thus the $\supseteq$-infimum. So, in fact, greatest fixed points for $\subseteq$ are just least fixed points for $\supseteq$ and vice versa.
(Also, observe that the requirement of monotonicity is the same for $\subseteq$ as for $\supseteq$.)

Now, for proof techniques. Let us begin with the example of induction on natural numbers. To show that some property $P$ holds for all natural numbers, we show that $P(0)$ and that $P(n)$ implies $P(n+1)$. Viewing $P$ as a subset of $U$ (the set of all elements where the property holds), the proof obligation for natural induction is that $P$ is closed under $f_{\tt nat}$. Correctness of the proof technique of natural induction then follows from the definition of least fixed point: If $f_{\tt nat}(P)\subseteq P$, then $P$ is part of the intersection that forms $\mu f_{\tt nat}$, so the property holds throughout $\mu f_{\tt nat}$, that is $\mu f_{\tt nat}\subseteq P$.

Induction is just the generalization of the previous paragraph to arbitrary monotone $f$ instead of $f_{\tt nat}$. Coinduction is the dual of induction: The proof obligation is $f(P)\supseteq P$. This means that if $P$ holds on some element $x$, then $x$ is constructed using only base elements on which $P$ also holds.
So, instead of showing that the property survives application of constructors, we have to show that it survives deconstruction. Once the proof obiligation is satisfied, we obtain $\nu f\supseteq P$.

What good is the conclusion $\nu f\supseteq P$? Let us reconsider $P$ not as a property but as a subset of $U$. The conclusion of coinduction establishes that all elements of $P$ are well-formed members of the coinductivly defined set $\nu f$.
This is what happens in the example in What is coinduction? showing forall n, Infinite (from n). Here, $f$ is closure under the constructors of Infinite (not of colist!) and $P$ is the set of all terms of the form from n for some n.


What is the name of the other vertex of an undirected edge? Let's say I have an undirected graph with an edge $e = \{a,b\}$ connecting vertices $a$ and $b$.

Taking vertex $a$, what is the name of the other vertex? Is it the "co-vertex"? Or simply the "other vertex"? Or the "neighbouring vertex"?

There's no set phrase; any clear description will do. "The other vertex in $e$", "the other endpoint of $e$", "$b$".

I've never heard of "co-vertex" and "neighbouring vertex" is vague, since $a$ might have multiple neighbours.


Use the pumping lemma to show the language is not regular I can use the pumping lemma to prove simpler examples, but i'm finding this problem rather complex partly due to the notation.

Can anyone explain how I would do this problem:

  For any string $s$ in $\{a, b\}^*$, let $n_a(s)$ be the number of a’s in s, and let $n_b(s)$ be the number of b’s in s. Let L over {a, b} be given by $L = \{x \in \{a, b\}^* | n_b(x) = n_a(x)^2 \space \text{and} \space x \notin ((a^∗b^∗) ∪ (b^∗a^∗))\} $.
  Prove, using the pumping lemma for regular languages, that the language L is not a regular language

I know we suppose that it is regular then by the pumping lemma it has to satisfy the properties of the pumping lemma for regular languages.

Hence, we need to find a decomposition and break it by pumping this decomposition which is no longer in the language forming a contradiction by hypothesis. However, I fail to see the decomposition or what to pump....

Assume $L$ is regular, and let $p$ be as in the pumping lemma.

Note that $s = a^pb^{(2p)^2}a^p\in L$.
Now, by the pumping lemma, we have a decomposition of $s = xyz$.
As $|xy|\leq p$, we must have that $y\subseteq a^p$, Say that $y = a^k$ for some $k\leq p$ (and by the property that $|y|>0$, we have that $k\geq 1$).

Then, we have that:
$$s = \underbrace{a^{p-k}}_x\underbrace{a^k}_y\underbrace{b^{4p^2}a^p}_z$$
Again, by the pumping lemma, we have that $L\ni xz = a^{p-k}b^{4p^2}a^p$.
But, we have that $n_a(xz) = 2p-k$, and $n_b(xz) = 4p^2$, but $n_a(xz)^2 = 4p^2-4pk+k^2\neq 4p^2 = n_b(xz)$, where the lack of equality holds because $1\leq k\leq p$, as stated before.

So, we have a contradiction to the pumping lemma, so $L$ isn't regular.

This all is entirely standard, and the only "trick" is picking the right string $s$.
A few tips for this:

$s$ will generally need to depend on $p$ in some way so it's "long enough to be pumped"
You'll want to carefully choose the first $p$ characters of $s$. If it can all be one character repeated (like in this case we had $a^p$), it makes determining what $y$ is much easier, and you can do the proof with a single case.
Besides that, you want to choose the rest of the string so $s\in L$, and some "pumped version" of $s$ isn't in $L$. This is clearly the hardest part, and the part I don't have a great procedure for. Generally trying a few things ends up with something working eventually. For "counting" based ones like the one you posted (some number of one symbol is equal to some number of some other symbol), usually having the part you pump be of the form $a^k$ is enough to mess with the counting.


Function that spreads input I'd like to know if there is a function $f$ from n-bit numbers to n-bit numbers that has the following characteristics:

$f$ should be bijective
Both $f$ and $f^{-1}$ should be calculable pretty fast
$f$ should return a number that has no significant correlation to its input.

The rationale is this:

I want to write a  program that operates on data. Some information of the data is stored in a binary search tree where the search key is a symbol of an alphabet. With time, I add further symbols to the alphabet. New symbols simply get the next free number available. Hence, the tree will always have a small bias to smaller keys which causes more rebalancing than I think should be needed.

My idea is to mangle the symbol numbers with $f$ such that they are widely spread over the whole range of $[0,2^{64}-1]$. Since the symbol numbers only matter during input and output which happens only once, applying such a function should not be too expensive.

I thought about one iteration of the Xorshift random number generator, but I don't really know a way to undo it, although it should theoretically be possible.

Does anybody know such a function?
Is this a good idea?

You can use Fibonacci hashing, namely

$\qquad h_F(k) = k \cdot \frac{\sqrt{5} - 1}{2} - \left\lfloor k \cdot  \frac{\sqrt{5} - 1}{2} \right\rfloor$.

For $k=1,\dots,n$ you get $n$ pairwise-distinct numbers (about) evenly spread in $[0,1]$. By scaling to $[1..M]$ and rounding (down), you get about evenly spread numbers in that interval.

For example, these are $h_F(1), \dots, h_F(200)$ scaled to $[0..10000]$ (left original sequence, right sorted):

This is an instance of what Knuth calls multiplicative hashing. For $w$ the computer's word size, $A$ some integer relatively prime to $w$ and $M$ the number of addresses needed, we use

$\qquad h(k) = \left\lfloor M \left( \bigl( k \cdot \frac{A}{w}\bigr) \mod 1 \right) \right\rfloor$

as hashing function. The above follows with $A/w = \phi^{-1} = \frac{\sqrt{5}-1}{2}$ (make sure you can compute it with a sufficient precision). While this also works with any other irrational number besides $\phi^{-1}$, it is one of only two numbers that lead to the "most uniformly distributed" numbers.

Find more in The Art of Computer Programming, Volume 3 by Donald Knuth (chapter 6.4 from page 513 in the second edition). In particular you'll find why the resulting numbers are pairwise distinct (at least if $n \ll M$) and how to compute the inverse function if you use natural $A$ and $w$ instead of $\phi^{-1}$.


Number of winning combination in Nim I am studying game theory and I am wondering how many winning combinations are possible for Nim game? Suppose, stones = 500 and piles = 5. With these number, there are many initial game positions are possible. like [1, 2, 4, 3, 490], [100, 100, 100, 100, 100], [100, 200, 100, 100], [0, 200, 200, 50, 50] and so on. So basically there are stones^piles combinations possible. Among these, some will yield Xor > 0 and considered as winning possible.

My question is - how many winning initial positions are possible for given stones and piles? Instead of checking all possible combinations(which is impossible for larger inputs), is there any smart way to solve this?

This is not a homework or programming contest problem.

I assume there are k piles and each pile can have stones in the range [0,n]. Then we can find the losing positions ( you can subtract from total to get no. of winning positions ) using dynamic programming. Let the number of bits in binary representation of n be b. We take a 2-D array called dp of size $kx2^b$, where dp[i][j] denotes number of ways of assigning no. of stones to first $i$ piles such that xor of no. of stones in these first $i$ piles is $j$. It is easy to see that no. of losing positions is dp[k][0]. Now what's left is to come up with the recurrence relation ( I leave the base cases for you to come up with ).

           // take care of the base case
           for i in range 1 to k:
               for j in range 0 to 2^b:
                   dp[i][j] = 0
                   for m in range 0 to 2^b:
                       // first i piles have nim-sum j
                       // ... if first i-1 piles have nim-sum m in the last
                       // ... pile we keep (m xor j) stones
                       dp[i][j] = dp[i][j] + dp[i-1][m]

EDIT
If $k$ piles in total have $n$ stones , you can again solve it by dynamic programming , but this time keeping a 3-D dp array of size $k$x$2^b$x$n$, where dp[x][y][z] means number of arrangements of first x piles having in total z stones and the nim-sum being y. Although I point it out that this method would be feasible only for small values of $k$ and $n$ ( in the order of few  hundreds ). Following is a pseudo code ( again take care of base cases, if you have problem with them you could comment )

            // take care of base cases
            // our answer would be ( no. of losing ) positions = dp[k][0][n]

            for i in range 1 to k:
                for j in range 0 to 2^b:
                   for l in range 0 to n:
                      dp[i][j][l] = 0
                      for m in range 0 to l:
                            dp[i][j][l] = dp[i][j][l] + dp[i-1][m^j][l-m]

Clearly the above method works for small $k$ and $n$ ( you can reduce the memory, which I leave up to you to figure out ).


Appropriate minor to go with CS major I thought this would be the best place for a question like this. Anyway, I was wondering what minor would go well with a Computer Science degree. I was considering a minor in math but I am not entirely sure if that could help out or not. I am currently a second semester freshman and I suppose that this is the best/latest time to decide. Open to many suggestions.

It depends on what you plan to do with your CS degree. If you plan to continue to graduate school, a math minor would certainly be helpful. If your interests turn out to be in hardware, and the courses are available, some courses in electrical engineering would be appropriate, as a minor or not.

On the other hand, if you plan to go straight to Real Life$^{\text{TM}}$, then the possible enhancements widen considerably. Math is still a strong contender, of course, but if, for example, you see yourself in, say, the IT department in banking or finance, a strong background in economics would also serve you well. If you are of an artistic bent and see yourself working for Pixar, a CS major and an art minor wouldn't hurt. These days, so many businesses are in some way or another computational in part, you should really be asking yourself "What do I like to do?" and then tailor your non-CS courses accordingly.

If you go the RL$^{\text{TM}}$ route, my experience with recruiters is that I've stopped asking "what courses should we offer our students to best prepare our graduates for work in your company?" because the answers are almost always "You're doing fine with your courses, but what we really want is people with an adequate technical background who can express their ideas orally and in writing and who have some idea about how the world works". Unless you're a really good writer and speaker, take some courses in writing and oral communication---it will be time well spent. If you go that way, get as broad an education as possible, since you'll eventually be making policy decisions for your company, rather than writing programs.

Finally, be open to all possibilities, since you can't know what opportunities that might open. A number of years ago, I heard from a CS major I had taught who had become a successful rodeo clown. Did he use his major? Nope. Was he happy with his life? It certainly appeared so. The single most important lesson I teach my students is, get a job you love, then you'll never have to "work" a day in your life. Best of luck.


What is the complexity of depth first traversal that don't label nodes as discovered? I've found an algorithm that acts like a depth first traversal that don't recognizes nodes that have been visited before.

  A
 / \
B   C
 \ /
  D
  |
  E

If run on this graph, the algorithm will traverse in this order:

A, B, D, E, D, B, A, C, D, E

Is there any way I can express the run-time complexity of this algorithm in terms of edges, nodes, or the depth of the graph? I expect it would be high, I have the feeling it will be exponential, but I'm struggling to explain why.

EDIT: The real algorithm that I am analyzing is computing the result of an expression tree, only it is not run at a tree, but at a DAG. This means, that nodes that have several parents get computed once for all parents.

Simple pseudo-code for the algorithm might be:

calculate(root){
    if(root.isLeaf){
        return root.value;
    } else {
        leftval = calculate(root.left);
        rightval = calculate(root.right);
        return root.operator(leftval, rightval);
    }
}

For general DAGs, the runtime could indeed be exponential in the depth. Here's an example of a family of such graphs. Let $G_d$ be a digraph comprised of a vertex stacked on a collection of 4-cycles as below, where I've illustrated $G_3$:

In this figure, the edges are directed from top to bottom and every vertex has two children. The number of function calls your algorithm makes (and hence the run time) for a digraph $G_d$ of depth $d$ will satisfy $T(0)=1, T(d)=2T(d-1)+1$, since every $G_d$ is comprised of a root vertex at the top with two overlapping copies of $G_{d-1}$ below it. This recurrence has solution $T(d) = 2^{d+1}-1$, exponential in the depth.


Reachability queries on uncertain graphs We have an uncertain graph $G$ where each edge $(u,v)$ exists with a probability $p_{(u,v)} \in (0, 1]$. We want to assign a score in $[0, 1]$ to each pair of vertices $u$ and $v$ which represents the likelihood that they lie in the same connected component.

If the only possible scores were discrete $0$ and $1$, then this problem reduces to the connected components listing or graph reachability problem. Is there any work on uncertain graphs that can solve this problem?

I edited your question to make it self-contained.

The literature on uncertain graphs is really rich for this problem. What you are looking for is "reachability in uncertain graphs", which has been studied extensively in database community [1].

Basically, you have an edge between two vertices $u$ and $v$ with probability $p_{uv} \in (0,1]$. You need to find whether two given vertices are reachable, therefore, lie in the same connected component or disjoint set. I suggest you take a look at the following paper as starting point, which describes the basics and can lead you to more works that have been done on this problem:

[1] Jin, Ruoming, et al. "Distance-constraint reachability computation in uncertain graphs." Proceedings of the VLDB Endowment 4.9 (2011): 551-562.


What type of knapsack problem is this? I need to choose the highest value combination of items given a specific set of constraints. These constraints are:

Exactly 6 items from group A and 2 items from group B must be selected.
Items in group A and group B count towards the same maximum weight.
No item can be selected more than once.
No more than 2 items of the same 'color' can be selected (there is always exactly 2 of each color in group A and 1 of each color in group B).

Example data set:

Group A
Item  -  Weight  -  Value  -  Color
A01  -  32  -  59  -  Teal
A02  -  31  -  65  -  Teal
A03  -  29  -  57  -  Red
A04  -  27  -  16  -  Red
A05  -  25  -  07  -  Orange
A06  -  25  -  20  -  Purple
A07  -  24  -  06  -  Orange
A08  -  23  -  39  -  White
A09  -  22  -  20  -  White
A10  -  21  -  23  -  Purple
A11  -  21  -  31  -  Blue
A12  -  20  -  16  -  Green
A13  -  20  -  17  -  Blue
A14  -  19  -  45  -  Green
A15  -  18  -  22  -  Black
A16  -  18  -  14  -  Yellow
A17  -  17  -  08  -  Yellow
A18  -  17  -  22  -  Gray
A19  -  16  -  13  -  Black
A20  -  16  -  26  -  Gray

Group B
Item  -  Weight  -  Value  -  Color
B01  -  36  -  85  -  Teal
B02  -  33  -  39  -  Red
B03  -  31  -  48  -  Purple
B04  -  30  -  28  -  Orange
B05  -  29  -  71  -  White
B06  -  24  -  65  -  Blue
B07  -  23  -  64  -  Green
B08  -  22  -  61  -  Yellow
B09  -  21  -  36  -  Black
B10  -  20  -  27  -  Gray

Max weight = 200

I'm not necessarily looking for a solution to this problem. I have found all sorts of ways to solve many variations of problems that seem very similar to this, but none seem quite right. If I just knew what to look for, I'm sure I'd be able to find an example and figure out the rest from there.

The closest I've been able to get is an 0/1 multi-knapsack (or maybe multi-dimensional knapsack?) problem. Does anyone have a better description of this problem? Thanks in advance!

Edit: Oh, bonus question, if anyone has any recommendations for languages which are particularly well suited to this type of problem (I was thinking python for itertools), I'd greatly appreciate it.

Multi-dimensional knapsack seem appropriate. The additional dimensions are 1 if item is in group A, else 0, 1 if item is in group B, else 0, 1 if item is green, else 0, ... The maximum weights of additional dimensions are 6, 2 and then 2 for each color.

The condition that there must be exactly 6 items from group A could be forced by an additional dimension -1 if item is in group A, else 0 and maximum weight of -6. However, this is awkward.


How to reduce number of move operations in an array? Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my disposal, I have a single method that I can use:

move(fromIndex, toIndex)

Thus, to achieve my desired array, I could call the method a number of times:

move(2, 0); // [2, 0, 1, 3, 4, 5]
move(1, 2); // [2, 1, 0, 3, 4, 5] (swapped 2 with 0)

move(4, 2); // [2, 1, 4, 0, 3, 5]
move(3, 4); // [2, 1, 4, 3, 0, 5] (swapped 4 with 0)

move(4, 3); // [2, 1, 4, 0, 3, 5] (swapped 0 with 3)

move(5, 4); // [2, 1, 4, 0, 5, 3] (swapped 5 with 3)

Thus, I also have a list of move() operations to achieve my desired result. The list of move() operations can possibly be reduced in size by changing the order and the indexes, to end up with the same result.

Is there an algorithm that I can use on my list of move() operations to reduce its size to a minimum?

The example in the question

The minimum number of moves needed for the example in the question, from [0, 1, 2, 3, 4, 5] to [2, 1, 4, 0, 5, 3] is 3.

            // [0, 1, 2, 3, 4, 5], where 2, 4, 5 are good.
move(2, 1); // [0, 2, 1, 3, 4, 5], where 2, 1, 4, 5 are good.
move(0, 4); // [2, 1, 3, 4, 0, 5], where 2, 1, 4, 0, 5 are good.
move(2, 5); // [2, 1, 4, 0, 5, 3], where 2, 1, 4, 0, 5, 3 are good.

The idea is to split the target array into two subsequences, 2, 4, 5 and 1, 0, 3 where the first subsequence is the longest increasing subsequence. Keeping the order of elements in the first subsequence, we will move the remaining elements  from left to right to their expected positions respectively, i.e, first moving 1 to its expected positions and so on.

An algorithm

Input: Array $A = [0, 1, 2, ..., n-1]$ and array $B[0], B[1], ..., B[n-1]$ which is a permutation of $0, 1, 2, ..., n-1$.

Output: A list of minimum size each of whose elements is an operation of the form move(fromIndex, toIndex) such that after performing that list of operations on $A$, $A$ becomes $B$.

Procedure: $B$ is intact while $A$ will be changed move by move.

Let $B[s_1], B[s_2], \cdots, B[s_m]$ be the longest increasing subsequence of $B$. This can be done as described in this Wikipedia article. It can also be done as described in this Wikipedia article since the longest increasing subsequence of $B$ is the longest common subsequence of $A$ and $B$.  Let $s_{-1}=-1$ and $s_{m+1}=n$.
Let $O$ be an empty list of operations. For $i$ from -1 to $m$ inclusive do:

For $j$ from $1$ inclusive to $s_{i+1} - s_i $ exclusive do:

Find $x$, the index of $B[s_i]$ in $A$. If $i=-1$, let $x=0$.
find $y$, the index of $B[s_j + j]$ in $A$.
Move $A[y]$ to the $j$-th place after the place of $A[x]$.
Add $\text{move}(y, x + j)$ to $O$.

Now all numbers in $B$ up to index $s_{i+1}$ are good, i.e., sorted in the same order in $A$ and in $B$, although the same number might be at different indices in $A$ and in $B$.

Correctness

It is clear that at the end of the algorithm, all numbers in $A$ are sorted in the same order in $B$ and in $B$, i.e., $A$ is $B$. The total number of moves in the algorithm is $$(s_0-s_{-1}-1) + (s_1-s_{0}-1)+\cdots + (s_{m+1}-s_{m}-1) = s_{m+1}-s_0-(m+1)=n.$$

On the other hands, each move(fromIndex, toIndex) in any algorithm can increase the common longest subsequence between $A$ and $B$ by at most 1. So $n-m$ moves are needed.

This is pointed out by xskxzr first.

Complexity

It takes $O(n\log n)$ or $O(n^2)$ to find the longest increasing subsequence. Finding the index of a number in $A$ is performed about $2n$ times, which costs $O(n^2)$ in total. It takes $O(n^2)$ to perform all $n$ moves. So the algorithm runs in $O(n^2)$ time.

The implementation of finding the index of a number can be sped up so that the algorithm can be implemented to run in $O(n\log n)$ time.

Exercises

Exercise 1. (One minute or two) Array $A$ is a permutation of $0, 1, \cdots, n-1$. State an algorithm that find a list of operations of the form move(fromIndex, toIndex) such that will sort $A$ in minimum steps.

Exercise 2. The same input is given. Find an algorithm that computes the minimum number of moves needed to change $A$ so that it ends up the same as $B$ up to a cyclic shift. For example, when $B=[2, 1, 4, 5, 0, 3]$, $A$ should be changed to one of $[2, 1, 4, 5, 0, 3]$, $[1, 4, 5, 0, 3, 2]$, $[4, 5, 0, 3, 2, 1]$, $[5, 0, 3, 2, 1, 4]$, $[0, 3, 2, 1, 4, 5]$ and $[3, 2, 1, 4, 5, 0].$


Proving that the halting problem is not Turing-reducible to the acceptance problem for Turing machines Consider $\mbox{Halt}_\mbox{TM} = \{\langle M, w \rangle: M \mbox{ is a TM and } M \mbox{ halts on input } w\}$ and $\mbox{A}_\mbox{TM} = \{\langle M, w \rangle: M \mbox{ is a TM and } M \mbox{ accepts on input } w\}$. I'd like to prove that any oracle TM $T$ that can query the $\mbox{A}_\mbox{TM}$-oracle cannot decide $\mbox{Halt}_\mbox{TM}$.

Intuitively, it appears that when $T$ queries this oracle with $\langle M, w \rangle$ and the oracle in turn replies "No" (i.e., $M$ does not accept $w$), $T$ is incapable of deciding whether $w$ is rejected by $M$ or $M$ is looping on $w$. Thus, the oracle cannot help $T$ in deciding $\mbox{Halt}_\mbox{TM}$.  However, this doesn't really prove that $\mbox{Halt}_\mbox{TM}$ is undecidable relative to $\mbox{A}_\mbox{TM}$, since $T$ could feed any query it pleases to the $\mbox{A}_\mbox{TM}$-oracle. Would a contradiction proof work best in this case? (I.e., suppose that the halting problem is decidable relative to the acceptance problem...)

The two problems are equivalent up to many-one reductions.

Reducing $\mathrm{Halt_{TM}}$ to $A_{\mathrm{TM}}$. Given a Turing machine $M$ and an input $w$, let $M'$ be the machine obtained from $M$ by marking all rejecting states as accepting. Then $\langle M,w \rangle \in \mathrm{Halt_{TM}}$ if $\langle M',w \rangle \in A_{\mathrm{TM}}$.

Reducing $A_{\mathrm{TM}}$ to $\mathrm{Halt_{TM}}$. Given a Turing machine $M$ and an input $w$, let $M'$ be the machine obtained from $M$ by getting to an infinite loop at every rejecting state. Then $\langle M,w \rangle \in A_\mathrm{{TM}}$ if $\langle M',w \rangle \in \mathrm{Halt_{TM}}$.


The language of Logical Theory as Metalanguage I am reading the Handbook of Satisfiability, and in Chapter 1 (History of Satisfiability), I found the following statement:

  Moreover, necessary and possible are predicates of the metalanguage
  (the language of logical theory) because they are used to describe
  sentences in the “object” language (the language that refers to
  entities in the world that is the object of investigation in logical
  theory).

I have two questions:

Could you help me please, to know what is "The language of logical theory" I have writen "'Language of Logical Theory'" in google and only found this in the same book.
Can I use necessary and possible as predicates? Could you give some example, please?

The concept of metalanguage is central to logic. Here is an example. The following statement is in the language of propositional logic:

  $$ a \lor b $$

The following is in the metalanguage:

  The formula $a \lor b$ is satisfiable.

In formal logic, we have some formalism for logical statements. This formalism specifies the syntax and semantics of logical statements. For example, in propositional logic we specify a set of logical connectives and how they are used to form logical statements (the syntax), and how a truth assignment to the variables yields a truth assignment of statements (the semantics). This constitutes the "object language". The metalanguage is just the usual English prose that we use, which might refer to the object language, as above.

In simple situations, we distinguish between the two by using logical symbolism for the object language, and natural language (like English) for the metalanguage. However, there are exceptions, the most interesting of which is the use of the metalanguage as a "shortcut" for a statement in the object language. For example, consider the following statement in the language of rings:

  $\exists b . ab=1$

This states that $a$ is invertible. We could also write it in this way:

  "$a$ is invertible"

What this means is that "$a$ is invertible" stands for some statement in the object language which states that $a$ is invertible. How is this different from stating in prose that $a$ is invertible? Well, suppose that we have some encoding function $\varphi$ which encodes formulas to integers. Then it is meaningful to consider $\varphi(\exists b.ab=1)$ or $\varphi(\text{"$a$ is invertible"})$ (the two might even be equal if you choose $\exists b.ab=1$ as the denotation of "$a$ is invertible"), but not $\varphi(\text{$a$ is invertible})$, the latter being as meaningless as $\varphi(\text{blue})$.

For further illustration of this difference, I recommend reading on Gödel's second incompleteness theorem.

Necessary and possible are logical concepts (concepts of the metalanguage) which can be thought of as properties of logical statements: a logical statement is necessary if it is always true (i.e., if it is a tautology), and it is possible if it could be true (i.e., if it is satisfiable). As such, you can think of them as predicates on the domain of logical statements. In the philosophical discipline of logic they have greater applicability, beyond propositional and predicate logic.

As an example, $a \lor \lnot a$ is possible and necessary, $a \lor b$ is possible but not necessary, and $a \land \lnot a$ is neither possible nor necessary. Every necessary statement is a fortiori possible.


Algorithm for finding the binary sequence with no 3 consecutive ones and with highest point? The problem is, we are given points $p_1,\ldots,p_n$ on positions of a length-$n$ binary sequence $x_1,\ldots, x_n$, and if the $i_{th}$ position of a sequence is $1$, then we "earn" $p_i$ points. So the total points is $\sum_{i=1}^{n}x_ip_i$. Our rule is that we cannot have three consecutive $1$'s, and we want to know what is highest possible points we can get from a length-$n$ sequence.

I propose an algorithm, but I find examples that leads to non-optimal solution. My algorithm basically goes as follows: let $P(k-1)$ be the highest possible points we can get for the length-$(k-1)$ sequence, with points $p_1,\ldots,p_{k-1}$, and it corresponds to an optimal length-$(k-1)$ sequence $s_{k-1}$, then I add an $1$ at $k_{th}$ position if it's possible to do so. If it is not possible to add $1$, then the previous 3 terms must be $011$. Then I compare $p_k,p_{k-1}$ and $p_{k-2}$, and put two $1$'s at two positions with the highest points, and put $0$ on remaining position. Hence I get $P(k)$, and $P(n)$ is computed by computing each $P(i)$.

However, consider the example of $n=4$, and $p_1=1,p_2=3,p_3=2,p_4=4$, this algorithm will produce $0101$, and $P(4)=7$, while $1101$ will have $8$ points.

Anyone has a suggestions on what is a true algorithm for this problem? Thanks!

Without loss of generality, assume $p_i> 0$. Otherwise we can set all $x_i=0$ where $p_i\le 0$ and consider the separated sequences by these $i$'s respectively.

Let $P(k)$ and $Q(k)$ be the highest possible points we can get for $p_1,\ldots,p_k$ where $x_{k-1}x_k=11$ and where $x_{k-1}x_k\neq 11$ respectively.

If the last two bits are $11$, $x_{k-2}$ must be $0$, and there are no constraint for $x_1,\ldots,x_{k-3}$, hence
$$P(k)=p_{k-1}+p_k+\max\{P(k-3),Q(k-3)\}.$$

If the last two bits are not $11$, there are two cases: $01$ or $10$. Note to get the highest points, the last two bits cannot be $00$.

If the last two bits are $01$, there is no constraint for previous bits, the highest possible points are $p_k+\max\{P(k-2),Q(k-2)\}$.
If the last two bits are $10$, then $x_{k-3}x_{k-2}\neq 11$, the highest possible points are $p_{k-1}+Q(k-2)$.

So

$$Q(k)=\max\left\{p_k+\max\{P(k-2),Q(k-2)\},p_{k-1}+Q(k-2)\right\}.$$

Use the two recursion formulas above, you can compute the final result $\max\{P(n),Q(n)\}$.


Identifying useless vertices in a directed graph I have a randomly generated directed graph with 3 types of vertices: input, output, and the rest (I'll call them hidden).

A useless vertex is a hidden vertex which:

can't be reached from an input vertex, OR
can't reach an output vertex.

For example:

input = yellow/green
output = blue
hidden = white
useless = red border

Note that:

cycles and self-loops are allowed
the graph may be disjoint
inputs and output nodes are known (i.e. you can determine what type of node an edge connects to and from)

So what do you call this type of problem? Is there any algorithm for this?

I'm looking for more information about this. I have a python script which seems to work. I'm just not sure if it will work for all cases since I don't fully understand it myself. It was a mix of DFS, trial-and-error, manual hand-checking, and a bunch of if statements.

Let $n$ and $m$ be the number of vertices and edges of your input graph $G = (V,E)$, respectively.
You can find all useless vertices in time $O(n+m)$.

You can discover the set $S$ all vertices reachable by at least one source in $O(n + m)$ overall time.

You do this by either:

running one visit from each of the input vertices, marking discovered vertices as visited, and taking care of not revisiting already visited vertices; or
adding a dummy "super-source" vertex $s$ with an outgoing edge towards every input vertex in $G$, and then running a visit from $s$.

By using the same technique on the reversed graph $G^R$, you can find the set $T$ of all vertices that are reachable from an output vertex in $G^R$. In other words a vertex $v$ can reach an output vertex in $G$ iff $v \in T$.

The set you are looking for is then $V \setminus (S \cap T)$.


Does checking the middle bit of an input require a log(n) space pointer? (Reusing space) Let n be an even integer.

Let I be an input of length n.

Positions start at 0: the first bit is bit 0. The second bit is bit 1. etc.

The decision problem is, "Is bit n/2 equal to 1"?

The input is on a tape.

We have a single pointer to the input. We may move the pointer left or right. We cannot overwrite the input tape.

We have a single working-memory tape to compute with. We have a single pointer to it. We may write a 0 or a 1. We may move the pointer left or right. We may not move to the left of, or overwrite the start symbol of the working-memory tape. The working-memory tape is initialized to either the start symbol or immediately to the right.

Space-complexity is the position of the largest cell we write to. This way we "reuse" space.[1]

One way to decide the problem is with a counter of length O(log(n)): Initialize to 0's, then increment until the counter equals n/2, then check the bit.

That takes O(log(n)) space.

Can we do better? Or is O(log(n)) the best space-complexity we can do?

[1] If space complexity was just the total in-use space at any given point in time, we could "move around" the space we're using, using a larger total range of space, but only a smaller portion at any point in time. Defining space as the max position keeps us from "moving around" the space we're using.

You can do this using $O(1)$ space, using two pointers. Initially, the first pointer is at the left end of the input, and the second pointer is at its right end. Each round, advance both pointers toward the middle, until they meet. This requires no additional space at all!

(The latter, assuming we can enlarge the tape alphabet. Otherwise we can still make do with constant additional space, by implementing the pointers as spaces.)


Allocating flows in a network while avoiding a particular node I am considering a network with the max flow problem in a particular situation. I have a set of flows which should pass a certain node A and and another set of flows which should avoid A and pass through another node B. The flows can cross each other at any other arbitrary node.

Under what category of network flow problems should this be considered?

Flows with more than one "thing" flowing are known as "multicommodity flows".

The basic definitions assume that every thing can flow through every vertex and edge. However, the standard way of solving these problems is linear programming and you could easily modify the normal multicommodity flow program to deal with your situation, just by substituting zero for the appropriate variables.


Are poly-reductions to PSPACE problems for following problems are known? List of problems I'm interested in:

$\oplus$SAT
#SAT-decision
Permanent-decision (YES if permanent is greater than given number $k$)

I have discovered poly-reduction for MAJSAT (and MAJQBF). However, I don't know such reduction (practical) for these problems.

How can I solve any of these problems with polynomial runs of TQBF? Or can I make a special TQBF to solve them. The special TQBF length should increase (not more than) polynomially compared to original problem.

The reduction you refer to is called Turing reduction. Given $A,B\subseteq \Sigma^*$, we say $A\le_T B$ if there exists a polynomial time Turing machine which decides $A$, given oracle access to $B$. You might call this practical, and in some sense this is the natural way to say $A$ is no harder than $B$ (give me a program for $B$, and i'll write an efficient program for $A$ which uses the previous program as a subroutine).

The standard notion of reduction in complexity theory is Karp reduction (also called many to one reduction). We say $A$ is reducible to $B$ in this sense, if there exists a polynomial time computable function $f$ such that $x\in A \iff f(x)\in B$. Note that this is a weaker condition, i.e. if $A$ is Karp reducible to $B$, it is also Turing reducible to $B$ (apply $f$ on the input, and query the oracle on the result).

Since TQBF is PSPACE complete, then by definition, every language in PSAPCE has a Karp reduction to it (and thus also a Turing reduction). Not only that we know there exists such a reduction, but given a PSPACE machine for some language $L$, then we know how to construct a reduction from $L$ to TQBF (this is done in the proof for the PSPACE completeness of TQBF).

The decision versions of $\#P$ problems are in PSPACE, since you can go over all possible witnesses and count how many are accepting (the only thing you need to store is the counter). This means that all such problems are reducible to TQBF. This is a very precise statement, but intuitively, it says exactly what you want it to. If you can efficiently decide TQBF, then you can efficiently decide all languages in PSPACE, which includes the decision versions of #SAT and permanent.


Is List comprehension equivalent to composition of filter and map? Wikipedia says

  A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It
  follows the form of the mathematical set-builder notation (set
  comprehension) as distinct from the use of map and filter
  functions.

  A list comprehension has the same syntactic components to represent
  generation of a list in order from an input list or iterator:

  A variable representing members of an input list.
  An input list (or iterator).
  An optional predicate expression.
  And an output expression producing members of the output list from members of the input iterable that satisfy the predicate.

  The order of generation of members of the output list is based on the
  order of items in the input.

I think a list comprehension can be equivalently converted to combining a filter and a map in the following way:

"An optional predicate expression." corresponds to a filter
"an output expression producing members of the output list from members of the input iterable that satisfy the predicate" corresponds to a map

So are list comprehension  and  combination of filter and map  equivalent?

Thanks!

Basic difference

List comprehension and combination of filter and map may be equivalent
only in languages with lazy evaluation.

The reason is that, without lazy evaluation, filter and map will want
to evaluate the whole lists given as arguments, while comprehensions
are built from the start as structure that evaluate on a call by need
basis.

Hence, comprehensions can in principle include infinite lists, and
some languages allow that (e.g. Python)

Also, evaluating all elements of a list may lead to non terminating
programs, if the evaluation of one element (not really needed) does
not terminate, while the corresponding comprehension may never be
asked to produce that element, and will not prevent termination of the
program.

The semantics of the program may also be changed if the computation of a list element produces side-effects. The ccomprehension will produce the side-effects later, if at all, during the execution of the program.

My interpretation of the wikipedia text

From what I always understood, comprehension means the same as
intension, which is itself opposed to extension
(wikipedia).

An extensional definition of a set is an actual enumeration of its
elements (which works moderately well for infinite ones).

An intensional definition is the usual technique that defines the
elements by specifying some property they must have.

The computational counterpart is comprehension, that provides a way of
computing the elements, rather than enumerating them explicitly.

Comprehension is in a sense the Curry-Howard counterpart of intension.

The counterpart for extensional sets is a data structure that
enumerates the elements explicitly.

Now, one can always define a property by extensionally giving the set
of elements that have that property, so that extensional definitions
can always be seen as a special case of intensional ones. But that
does not seem to be the point of view of wikipedia.

The wikipedia text is not too clear, and could be more explicit (no pun
intended)

My feeling is that they do want to exclude lists that are extensional,
maybe for typing reasons. It is not supposed to be a specific data-structure,
but an object to be used as an iterator , or as a stream possibly
(it is very remindful of the literature on coroutines and generators).

Direct use of map and filter with produce extensional lists, data structures actually containing all values.

But similar constructions with the same predicates and functions in comprehensions will produce a non extensional version of the same lists.

Computationally, comprehensions will be naturally evaluated in a call by need mode, which may allow different program organizations. A comprehension need not be finite, depending on how it is used.

Analysis of the various languages that use the concept might confirm,
or not, this understanding.


Solving a in/equality constraint problem with graph search You are given a list of m constraints over n distinct variables x1, ..., xn. Each constraint is of one of the following two types.

An equality constraint of the form xi = xj for some i!=j.
An inequality constraint of the form xi!= xj for some i!=j.

I want to find an assignment, if it exists, for each variable such that it conforms to all the constraints using a graph search algorithm in O(m+n) time.

This reminds me of the graph colouring problem, however that only involves checking graph neighbours where as in any efficient graph I could think of, the nodes sharing a constraint may not be neighbours.

My first thought was to create a graph such that all nodes that equal are connected then use DFS to traverse each node and check if it has an inequality with a parent, however that doesn't seem very efficient as for every node (m) I have to traverse every inequality constraint (at most n) which brings me to nm time, where as DFS inherently has O(m+n)on an ideal representation.

Any clues?

You're on the right track.  Construct an undirected graph with an edge for each equality constraint, as you suggested.  Next, look into the concept of connected components, and algorithms for finding them.  You should be able to take it from here.

This problem can be solved in linear time.


Z-score relations to perceptrons I am learning about preceptrons and my professor noted that z-scores are a commmon pre-processing step to normalizing input variables. Following this, I am having trouble understanding why z-scores are useful when training a preceptron?

My current understanding is that z-scores allows us to calculate the probability of a score landing inside the normal distribution and compare with scores from other normal distributions. However, how does this translate to perceptrons?

There are two parts to your question that need to be addressed.

  What transformation are you performing?
  Why does that help learning?

The transformation of taking your input and turning them into "Z-scores" is really just centering and standardizing the variance for each variable. The reason I put "Z-score" in quotes is because there is no reason to assume that this transformed variable is distributed normally. All you have done is taken a random variable with some unknown distribution and transform it to a random variable with mean 0 and variance 1. That doesn't necessarily mean it is normally distributed. Formally, if we have $$X \sim f(\mu, \sigma^2)$$ where $X$ is a random variable $f$ is the distribution with mean $\mu$ and variance $\sigma^2$, then $$\frac{X - \mu}{\sigma} \sim f(0, 1)$$ using the basic properties of mean and variance. Nowhere does this require $X \sim N(\mu, \sigma^2)$, which is where Z-score comes from.

With that said, why does this help? By centering your data (removing the mean) from both your training data and labels, you don't need to estimate a bias term. Bias (or mean measured effect) is function of the mean of your data; therefore if your data have mean 0, you should have no measurable bias term. Setting all variables to have unit variance places them all on the same scale. Oftentimes in real data the different variables in your model may have widely different variances, which could lead to difficult to compare effect sizes. Setting everything to have similar variance simplifies interpretation.


The XOR cut-set structure, and combinatorial designs Given a graph $G(V,E)$ and a subset of vertices $T \subseteq V$, define $\mathsf{cutset}(T)$ = the set of edges connecting a vertex at $T$ with a vertex at $V\setminus T$.

Our goal is to preprocess $G$ such that, given any set $T$, we can quickly return an edge in $\mathsf{cutset}(T)$, or reply that $\mathsf{cutset}(T)$ is empty. The structure should have space complexity $\widetilde{O}(|V|)$, i.e. we are not allowed to keep all the edges. The query complexity should be $\widetilde{O}(|T|)$.

Kapron et al suggest the following neat solution, which works when the size of each cutset is at most 1.

Give each edge a unique number. For each vertex $v$, keep $\mathsf{xor}(v)$ - the binary XOR of the numbers of all the edges adjacent to it. Given a query on $T$, calculate $\mathsf{xor}(T)$ - the binary XOR of all vertices in T. Every edge which is internal to $T$ (i.e. has both endpoints inside $T$) is XORed twice, and hence is not included in $\mathsf{xor}(T)$. So, $\mathsf{xor}(T)$ is actually a XOR of all edges in $\mathsf{cutset}(T)$.

If the size of each cutset is at most 1, then there are two options: either $\mathsf{xor}(T)=0$, which means that $\mathsf{cutset}(T)$ is empty, or $\mathsf{xor}(T)$ is the number of the single edge in $\mathsf{cutset}(T)$.

The authors then go on and describe a complex, randomized structure to handle the case in which $\mathsf{cutset}(T)$ contains more than a single edge.

But in the conclusion, they say that:

  It is not hard to see that the technique described here can be made deterministic with an additional $\widetilde{O}(k)$ factor in the update time, if we know the cuts are of size no greater than $k$, through the use of combinatorial designs".

Unfortunately, for me this seems to be hard... I don't understand: how can combinatorial designs can be used to solve the problem when the size of all cutsets is at most $k$?

You can use a linear code with distance $2k$ or so. The parity check matrix of the code has the property that the XOR of any set of at most $2k-1$ columns is non-zero. This means, in particular, that given the XOR of at most $k$ columns, you can determine (not necessarily efficiently) how many columns were XORed (since if you couldn't you would obtain a set of at most $2k-1$ columns which XORs to zero). The cost of this encoding is the number of rows of the parity check matrix. If you choose the parameters correctly and an efficiently decodable code (recall that the parity check matrix of a code is the generator matrix of its dual), then you probably obtain the conclusion stated in the remark.


Proving that $xy=yx$ iff $x^2y^2=z^2$ I was given the following problem as homework:

  Let $x$, $y$ be words over an alphabet $Σ$. Prove that $xy = yx$ iff there exists a word
  $z$ such that $x^2y^2 = z^2$.

I was hinted that I am supposed to approach this problem using structural induction. Considering the case where $|x| = |y|$, you obviously get $x=y=z$, as commutativity of concatenation satisfies only under that case.

Taking the case of $|x| < |y|$, we can conclude that $x$ is a prefix of $y$, assuming the induction hypothesis ($xy=yx$), and we can further say that $y=xt$, where $t$ can be assumed to be the trailing symbols of $y$ after the prefix $x$, and hence using $xy=yx$, we get $xxt = xtx$. And I'm stuck here. Can somebody guide me?

One direction is easy: if $xy = yx$ then $x^2y^2 = xxyy = xyxy = (xy)^2$.

In the other direction, we split into cases. If $|x|=|y|$ then, as you mention, $x = y$.

If $|x|<|y|$ then let $y=y_1y_2$, where $|y_1|=|y|-|x|$ and $|y_2|=|x|$. We have $z = x^2y_1$ and $z = y_2y = y_2y_1y_2$. Since $|x| = |y_2|$, it follows that $x = y_2$. Substituting this, we obtain $y_2^2 y_1 = y_2y_1y_2$, and so $y_2y_1 = y_1y_2$. This implies that $xy = y_2y_1y_2 = y_1y_2y_2 = yx$.

If $|y| < |x|$, then notice that $(y^R)^2(x^R)^2 = (z^R)^2$ (where $w^R$ is the reverse of $w$) and $|y^R| < |x^R|$, so we can apply the previous case to deduce that $y^R x^R = x^R y^R$ and so $xy = yx$.

Let us use this opportunity to characterize when $xy=yx$, by proving that there exist a word $w$ and integers $n,m$ such that $x = w^n$ and $y = w^m$ iff $x^2y^2$ is a square.

One direction is easy: if $x = w^n$ and $y = w^m$ then $x^2y^2 = w^{2n+2m} = (w^{n+m})^2$.

In the other direction, we use induction on $|x|+|y|$. The base case $x=y=\epsilon$ is trivial. For the inductive case, we split into cases. If $|x| = |y|$ then $x = y$ and so we can take $w = x = y$.

If $|x| < |y|$ then as before we get that $y = y_1 x = x y_1$, which implies that $y_1^2 x^2 = (y_1 x)^2$. The inductive hypothesis shows that there exist $w,n,m$ such that $y_1 = w^n$ and $x = w^m$. Then $y = y_1 x = w^{n+m}$.

We have shown that $xy = yx$ iff there exists a word $w$ and integers $n,m$ such that $x = w^n$ and $y = w^m$.

Equivalently, let us define the radical $\sqrt{x}$ of a word $x$ as the shortest word such that $x$ is a power of $\sqrt{x}$. Then $xy = yx$ iff $\sqrt{x} = \sqrt{y}$.

Indeed, if $\sqrt{x} = \sqrt{y}$ then clearly $xy = yx$. Conversely, suppose that $xy = yx$. Then there exist $w,n,m$ such that $x = w^n$ and $y = w^m$. We can assume that $w = \sqrt{w}$. I claim that $\sqrt{x} = w$. Otherwise, there exists a word $z$ shorter than $w$ and an integer $\ell$ such that $x = z^\ell$. The word $x$ thus has both $|w|$ and $|z|$ as periods ($p$ is a period of $x$ if $x_i = x_{i+p \bmod |x|}$ for all $i$), and so $|w| \bmod |z|$ is also a period. If $|w| \bmod |z| \neq 0$ then this contradicts the fact that $z$ is the radical of $x$ (since $x$ is a power of $x_1 \ldots x_{|w| \bmod |z|}$). If $|z|$ divides $|w|$ then $w = z^{|w|/|z|}$, contradicting the assumption $w = \sqrt{w}$. We reach a contradiction either way, and so $\sqrt{x} = w$. By the same reasoning, $\sqrt{y} = w$, and so $\sqrt{x} = \sqrt{y}$.